用A*搜索指导模型生成高效准确的推理链。
Learning to Reason Efficiently with A* Post-Training
- 以A*搜索为指导，通过监督微调和强化学习训练模型生成正确推理步骤。
- 1B-3B参数模型经A*后训练，准确率从接近零提升至超过更大模型DeepSeek-V3.2。
- 在复杂搜索空间中，使用不完美启发式也能获得更高准确率，适合需要高效推理的应用。
大语言模型（LLMs）在许多应用中需要演绎推理，但常产生错误或冗余的推理步骤。本文将自然语言推理视为一个搜索问题，最终答案即为有效证明，要求推理过程中的中间推导均正确。我们探索了是否可通过A*搜索——一种保证最优路径到达目标的算法——引导LLM学习生成正确且高效的证明。研究采用两种训练方法：基于A*执行轨迹的监督微调，以及结合A*-启发奖励模型的强化学习。实验表明，Llama-3.2系列1B至3B参数规模的模型在经过A*后训练后，准确率从近乎零跃升至超越远大于自身的DeepSeek-V3.2模型。分析发现，单纯追求正确性奖励可最大化准确率，而基于A*的信号则在准确率与效率间取得平衡。此外，在更大搜索空间下，使用不完美启发式训练的模型表现出更优准确率。结果展示了受经典搜索算法原则指导的推理新方向。
原文摘要 · Abstract (English)
Many applications of large language models (LLMs) require deductive reasoning, yet models frequently produce incorrect or redundant inference steps. We frame natural language inference as a search problem where the final answer is the valid proof itself, requiring a reasoning procedure in which intermediate inferences are correct. Specifically, we investigate whether LLMs can learn to generate correct and efficient proofs with guidance from A* search -- an algorithm that guarantees an optimally efficient path to a goal. We explore two training techniques: supervised fine-tuning on execution traces from A* and reinforcement learning with A*-informed process reward models. Empirically, we find that Llama-3.2 models in the 1B--3B range benefit substantially from A* post training, going from near-zero accuracy to outperforming DeepSeek-V3.2 -- a much larger model. Our analysis uncovers a trade-off: while simple correctness rewards maximize accuracy, A*-informed signals strike a balance between accuracy and efficiency. Furthermore, we find that on larger search spaces, models trained with imperfect heuristics exhibit superior accuracy. Our results demonstrate a promising direction towards reasoning guided by principles derived from classical search algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。