Learning to Reason Efficiently with A* Post-Training

• URL: http://arxiv.org/abs/2605.24597v1
• Date: Sat, 23 May 2026 14:28:57 GMT
• Title: Learning to Reason Efficiently with A* Post-Training
• Abstract summary: We investigate whether large language models can learn to generate correct and efficient proofs with guidance from A* search.<n> Empirically, we find that Llama-3.2 models in the 1B--3B range benefit substantially from A* post training.<n>On larger search spaces, models trained with imperfects exhibit superior accuracy.
• Score: 119.18396754931602
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: 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.

Related papers

• The Art of Efficient Reasoning: Data, Reward, and Optimization [20.542546956993363]
  Large Language Models (LLMs) benefit from scaled Chain-of-Thought (CoT) reasoning, but also suffer from heavy computational overhead.<n> efficient reasoning aims to incentivize short yet accurate thinking trajectories, typically through reward shaping with Reinforcement Learning (RL)<n>We conduct extensive experiments (about 0.2 million GPU hours) in a unified protocol, deconstructing training prompts and rollouts, reward shaping, and optimization strategies.
  arXiv  Detail & Related papers  (2026-02-24T14:28:16Z)
• InT: Self-Proposed Interventions Enable Credit Assignment in LLM Reasoning [32.274434679047395]
  Outcome-reward reinforcement learning (RL) has proven effective at improving the reasoning capabilities of large language models (LLMs)<n>Standard RL assigns credit only at the level of the final answer, penalizing entire reasoning traces when the outcome is incorrect.<n>We introduce Intervention Training (InT), a training paradigm in which the model performs fine-grained credit assignment on its own reasoning traces.
  arXiv  Detail & Related papers  (2026-01-20T18:15:38Z)
• Neural Chain-of-Thought Search: Searching the Optimal Reasoning Path to Enhance Large Language Models [61.55758048622473]
  We introduce Neural Chain-of-Thought Search (NCoTS), a framework that reformulates reasoning as a dynamic search for the optimal thinking strategy.<n>By quantitatively characterizing the solution space, we reveal the existence of sparse superior reasoning paths that are simultaneously more accurate and concise than standard outputs.
  arXiv  Detail & Related papers  (2026-01-16T14:38:18Z)
• EpiCaR: Knowing What You Don't Know Matters for Better Reasoning in LLMs [9.412828452977553]
  Existing approaches reinforce successful reasoning paths, incurring a substantial calibration cost.<n>This failure has been characterized as a form of model collapse in alignment.<n>We proposeEpiCaR as a training objective that jointly optimize reasoning performance and calibration.
  arXiv  Detail & Related papers  (2026-01-11T06:21:13Z)
• Verifying Large Language Models' Reasoning Paths via Correlation Matrix Rank [71.09032766271493]
  Large language models (LLMs) are prone to errors and hallucinations.<n>How to check their outputs effectively and efficiently has become a critical problem in their applications.
  arXiv  Detail & Related papers  (2025-10-28T11:01:10Z)
• Teaching LLM to Reason: Reinforcement Learning from Algorithmic Problems without Code [76.80306464249217]
  We propose TeaR, which aims at teaching LLMs to reason better.<n>TeaR leverages careful data curation and reinforcement learning to guide models in discovering optimal reasoning paths through code-related tasks.<n>We conduct extensive experiments using two base models and three long-CoT distillation models, with model sizes ranging from 1.5 billion to 32 billion parameters, and across 17 benchmarks spanning Math, Knowledge, Code, and Logical Reasoning.
  arXiv  Detail & Related papers  (2025-07-10T07:34:05Z)
• The Price of a Second Thought: On the Evaluation of Reasoning Efficiency in Large Language Models [54.88805865447848]
  We show that instruct models achieve higher efficiency overall, and problem difficulty affects efficiency.<n>We propose COTHINK, a simple two-stage pipeline: an instruct model drafts a brief outline, and a thinking model expands it.<n>On GSM8K, MATH500, and AIME24, COTHINK cuts token usage by 21.1% while keeping accuracy on four thinking models, and remains competitive with strong efficiency baselines.
  arXiv  Detail & Related papers  (2025-05-28T06:24:45Z)
• S$^2$R: Teaching LLMs to Self-verify and Self-correct via Reinforcement Learning [51.84977135926156]
  We introduce S$2$R, an efficient framework that enhances LLM reasoning by teaching models to self-verify and self-correct during inference.<n>Our results demonstrate that Qwen2.5-math-7B achieves an accuracy improvement from 51.0% to 81.6%, outperforming models trained on an equivalent amount of long-CoT distilled data.
  arXiv  Detail & Related papers  (2025-02-18T13:40:22Z)
• Learn from Failure: Fine-Tuning LLMs with Trial-and-Error Data for Intuitionistic Propositional Logic Proving [41.23045212775232]
  We demonstrate the benefit of training models that additionally learn from failed search paths. Facing the lack of such trial-and-error data in existing open-source theorem-proving datasets, we curate a dataset on intuitionistic propositional logic theorems. We compare our model trained on relatively short trial-and-error information (TrialMaster) with models trained only on the correct paths and discover that the former solves more unseen theorems with lower trial searches.
  arXiv  Detail & Related papers  (2024-04-10T23:01:45Z)
• The Wisdom of Hindsight Makes Language Models Better Instruction Followers [84.9120606803906]
  Reinforcement learning has seen wide success in finetuning large language models to better align with instructions via human feedback. In this paper, we consider an alternative approach: converting feedback to instruction by relabeling the original one and training the model for better alignment in a supervised manner. We propose Hindsight Instruction Relabeling (HIR), a novel algorithm for aligning language models with instructions.
  arXiv  Detail & Related papers  (2023-02-10T12:16:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.