Efficient Deductive Natural Language Reasoning with A*-Informed Learning

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 search in a hypergraph, where a correct solution requires a valid proof rather than just a final answer. Under this framework, we investigate whether LLMs can learn to generate correct proofs in an efficient manner with guidance from forward chaining algorithms, specifically A* search. We explore two training techniques: supervised fine-tuning on execution traces from A* and reinforcement learning with A*-informed reward models. Empirically, we find that Llama-3.2 models in the 1B–3B range benefit substantially from A*-guided training, going from near-zero accuracy to outperforming DeepSeek-V3.2. Our analysis uncovers a trade-off: while 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 to learning from a true cost-to-go oracle. Our results demonstrate a promising direction towards reasoning guided by classical search algorithms.