acceptodds
Under review as a conference paper at ICLR 2027

Efficient Deductive Natural Language Reasoning with A*-Informed Learning

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 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.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Deductive reasoning, Search, LLMs, A*, Efficiency, Reinforcement Learning

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_WL6HOpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

Authors formulate deductive logical reasoning as hypergraph search and fine tune LLMs to generate proof steps following search algorithms intuitions, rewards, and execution traces. Several methods are compared including untrained/ICL on a stronger base model, SFT, and RL (GRPO) against several reward variants (correctness, step-count, or A*-priority rewards). The authors show on Llama-3.2-1b/3b on ProofWriter and DeepRD tasks show accuracy/efficiency trade-offs with different rewards being on the pareto frontier, highlighting no single best choice.

Critical strengths
  1. Their evaluation also checking for derivation correctness guards against unfaithful reasoning/incorrect reasoning that happens to land on correct answers. From a scientific perspective, the study advances understanding about the full reasoning process rather than final accuracy only.

  2. All results are plotted against both accuracy and efficiency. Instead of claiming universal benefit in one method in accuracy only, the paper also reports negative results and substantial variations showing trade-offs between variations.

Critical weaknesses
  1. Efficiency is only computed on correct proofs so efficiency comparison may be over different problem subsets. This may act as a confounder since stronger methods that are able to solve more difficult problems may be hurt by having longer proofs in their average. Also, efficiency is computed by push/pop steps from the search algorithm rather than token generation, so a specific efficiency is being highlighted, though this is acknowledged in the paper.
Questions for authors
  1. Do the efficiency comparisons hold when the problem subset is normalized? With token counts?
  2. Are there controls around SFT exposure to off-path inferences for different traces?
2 comments

Thank you for the positive review and for appreciating research into understanding the full reasoning process! We respond to your questions below.

Efficiency is only computed on correct proofs so efficiency comparison may be over different problem subsets. This may act as a confounder since stronger methods that are able to solve more difficult problems may be hurt by having longer proofs in their average. [...] Do the efficiency comparisons hold when the problem subset is normalized?

Thanks for pointing this out; it is true that the manner in which we compute the efficiency metrics may penalize high-accuracy models. We chose to focus on a metric that is comparison-independent but we agree that we should also present normalized metrics. We have now measured efficiency on the intersection of problems solved by all four reward model checkpoints for each (model, SFT checkpoint)-combination and observe that the rankings are largely preserved as compared to the non-normalized scores. For example, see the following results for the checkpoints stemming from the A* dependency heuristic:

Llama-3.2-3B:

Methodn_ownn_interpush_eff_ownpush_eff_interpop_eff_ownpop_eff_inter
SFT43822620.8%22.1%27.3%29.3%
+Correctness42022622.7%23.4%30.0%31.3%
+Steps37222639.2%43.0%64.4%72.4%
+A*-dep.36622635.3%37.9%57.0%61.9%
+A*-true38022633.5%36.5%52.5%58.6%

Llama-3.2-1B:

Methodn_ownn_interpush_eff_ownpush_eff_interpop_ eff_ownpop_eff_inter
SFT25511718.4%19.8%24.2%25.9%
+Correctness30511718.8%19.3%24.5%24.8%
+Steps26911722.8%23.7%29.2%30.2%
+A*-dep.29911719.7%20.8%26.0%27.0%
+A*-true29911719.7%20.5%25.7%26.3%

We will report corresponding results for all (model, SFT checkpoint)-combinations in the appendix for the camera-ready version of the paper, should the paper be accepted.

Also, efficiency is computed by push/pop steps from the search algorithm rather than token generation, so a specific efficiency is being highlighted, though this is acknowledged in the paper. [...] With token counts?

We indeed chose to focus on inference steps rather than on token efficiency in this work, but the two are highly correlated in our experiments: Spearman’s rank correlations between number of generated tokens and push and pop counts for DeepRD is 0.94 and 1.00, respectively, while the corresponding numbers for ProofWriter are 0.85 and 0.74. We will report these numbers in the paper.

Are there controls around SFT exposure to off-path inferences for different traces?

Not directly, but implicitly through the search orders, which is the variable we manipulate. For ProofWriter, the percentage of off-path inferences in the training data for Dijkstra’s, A* with the dependency heuristic, and A* with the true cost-to-go are 44.7%, 20.3%, and 6.1%, respectively. The corresponding numbers for DeepRD are 84.5%, 76.9%, and 45.5%. We will report these numbers in the final version of the paper.

Thanks for the responses and additional analysis. My score remains "accept".

Reviewer_vtuPOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This article proposes a method for training a large language model for natural language deductive reasoning using A * search signals, combined with supervised fine-tuning based on search trajectories and reinforcement learning based on A * guided rewards. The experiment was conducted on ProofWriter and DeepRD, and the results showed that this method can improve inference correctness and search efficiency, but there is a trade-off between different reward functions, and the effect is affected by the complexity of the search space and heuristic strategies

Critical strengths
  1. Clear and detailed mathematical principles.
  2. Innovative method.
  3. Adequate experimentation.
Critical weaknesses
  1. The proposed framework mainly combines existing A* search, supervised fine-tuning, and reinforcement learning. The technical novelty beyond adapting established algorithms to natural language reasoning appears limited.

  2. The evaluation focuses on reasoning accuracy and efficiency but does not measure whether the model actually learns A* search behavior. Metrics such as search-order similarity and priority compliance would provide stronger evidence.

  3. The experiments rely on synthetic or structured logic-programming datasets with predefined rules and verifiable inference steps. It remains unclear whether the approach generalizes to open-domain natural language reasoning.

  4. The experiments mainly compare different A* heuristics and reward functions. Comparisons with other search strategies or process-supervision methods would help establish the specific contribution of A* guidance.

  5. The efficiency metrics are based on proof steps and inferred node expansions rather than actual inference latency, token consumption, or computational cost. Therefore, the practical efficiency gains remain unclear.

  6. Although imperfect heuristics outperform optimal search traces on more complex problems, the paper provides limited analysis of why this occurs or how the learned search strategies differ across training settings.

Questions for authors

None

3 comments

Thanks for the review and feedback! We are glad that you appreciated the mathematical framework and the innovativeness of the method. We respond to your weaknesses below. In summary, our revision adds (i) search-order similarity analysis to show that the models closely learn A*, (ii) efficiency analysis in terms of token counts, (iii) an analysis and explanation on why imperfect heuristics outperform optimal search traces on more complex problems, and (iv) further discussion around scope and contributions.

  1. The proposed framework mainly combines existing A* search, supervised fine-tuning, and reinforcement learning. The technical novelty beyond adapting established algorithms to natural language reasoning appears limited.

We see our contribution not as a new algorithm, but as (i) a framework for training and evaluating LLMs on verifiable search traces for deduction in natural language and (ii) an empirical study on how such training affects model behavior. In general, we believe that valuable and interesting contributions often take the form of innovative combinations of ideas, without those ideas necessarily being novel in isolation. With that said, we are happy to clarify the nature of our contributions in the revision.

  1. The evaluation focuses on reasoning accuracy and efficiency but does not measure whether the model actually learns A* search behavior. Metrics such as search-order similarity and priority compliance would provide stronger evidence.

Thanks, this is a useful suggestion. We note that our main interest is whether the model learns to generate efficient proofs based on A*-inspired reward shaping rather than if it can accurately imitate the algorithm, but we agree that such an analysis would be an interesting addition to the paper. We therefore computed step-order similarity between proofs generated from the SFT checkpoints and reference A* traces using Kendall's tau, restricted to the conclusions shared between the two sequences. We find high correlations (tau >= 0.96) across all models and datasets, suggesting that the trained models closely reproduce the steps from the underlying algorithms. Moreover, models consistently match the ordering of the data they have been trained on more closely than other orderings. We will add this analysis to the paper.

  1. The experiments rely on synthetic or structured logic-programming datasets with predefined rules and verifiable inference steps. It remains unclear whether the approach generalizes to open-domain natural language reasoning.

We deliberately restricted the scope to logic programs and datalog, which captures a broad class of reasoning tasks computable in polynomial time; see discussions in 2.1 and App. A. Note that evaluating entire proofs requires a ground-truth notion of what a valid inference is and measuring search efficiency requires knowing the search space---neither of these is available in an open-domain setting. We will add this remark to our limitations section (App. A). An interesting future direction could be to apply autoformalization to open-domain proofs written in natural language, producing logic programs to which our traces and rewards can then be used.

  1. The experiments mainly compare different A* heuristics and reward functions. Comparisons with other search strategies or process-supervision methods would help establish the specific contribution of A* guidance.

We note that our experiments already include several non-A* comparisons. At the SFT stage, we include Dijkstra’s algorithm. Note that, while Dijkstra’s can be viewed as A* search with a zero heuristic, it is typically viewed as a separate, non-informed search algorithm. In addition, at the RL stage we include two reward models that do not rely on A* search: a correctness reward and a step-count efficiency reward. Regarding process supervision, note that our correctness reward already requires every proof step to be valid, which is stricter than the final-answer rewards commonly used with GRPO.

  1. The efficiency metrics are based on proof steps and inferred node expansions rather than actual inference latency, token consumption, or computational cost. Therefore, the practical efficiency gains remain unclear.

Our paper indeed concerns efficiency in terms of how much work is made by the underlying algorithm that gets executed, rather than in terms of token count. This is deliberate. The two problems are related but separate, as we discuss in the related work section in App. B. We agree, however, that it is relevant to understand whether our results have implications for token efficiency. We found that they are indeed correlated: Spearman’s rank correlations between the number of generated tokens and push and pop counts for DeepRD is 0.94 and 1.00, respectively, while the corresponding numbers for ProofWriter are 0.85 and 0.74. We will report these numbers in the paper and hope that they will help clarify the practical benefits.

  1. Although imperfect heuristics outperform optimal search traces on more complex problems, the paper provides limited analysis of why this occurs or how the learned search strategies differ across training settings.

Thank you for this observation! We agree that more analysis would strengthen the paper. In short, we believe that exposure to off-path exploratory steps provides a more robust learning signal which compounds for large search spaces. In more detail, the key difference between the two datasets is the size of the search space: ProofWriter problems require little exploration while DeepRD problems are substantially more complex; compare Figs. 5 and 6 in the paper. On ProofWriter, A* with the true cost-to-go and dependency heuristic traces are similar in length and both orderings achieve similar accuracy with SFT. On DeepRD, roughly 45% of the steps in traces from A* with the true cost-to-go are off-path. Note that these off-path conclusions are never used as premises; the pop efficiency is 100% by construction: the model sees that alternative branches exist, but never sees a derivation continue from them. The dependency heuristic explores far more; about 77% of the steps it uses are off-path. A model trained on these traces has thus seen a much broader range of intermediate states, including states reached after steps that do not lead to the goal. By contrast, once a model trained on oracle traces takes a wrong step, it is in a state it never saw during training, and errors compound. This is consistent with previous work by Ross & Bagnell (2010).

  • Stephane Ross and Andrew Bagnell. PMLR 2010. Efficient Reductions for Imitation Learning.
AuthorsOpenReview ↗

Follow-Up on Author Response

Dear Reviewer,

Thank you again for your review! As the discussion period is coming to an end in a few days, we wanted to check whether our response addresses your concerns. Thank you.

Reviewer_mHvEOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The authors study how to train LLMs for deductive reasoning using the A* algorithm. They start from the logic programs of two deductive reasoning datasets and generate search traces with the A* algorithm, using different heuristics. They use these traces to train an LLM through SFT, then continue training with RL using several different rewards. The authors report substantial performance improvements over the base models.

Critical strengths
  • The authors introduce the background (deductive reasoning, logic programming) clearly and precisely.
  • Their method rewards a valid proof, rather than only a correct final answer.
  • The reported performance gains are substantial.
Critical weaknesses
  • As noted by the authors, efficiency is evaluated only on solved problems, which introduces a bias that complicates comparisons between models.
  • The discussion of the results is rather brief. I would have appreciated the authors sharing their intuition or possible explanations for why some rewards work better than others, and why each affects accuracy and efficiency differently.
  • (Minor point) Figures 3, 4, 8 and 9 are not very readable. They contain different shapes, colours and borders, and the hatching is difficult to see. I recommend improving their readability if possible.
Questions for authors
  • Could efficiency be evaluated on a common set of problems solved by the models being compared?
  • Do you have any insights that could explain the differences in results between rewards?
1 comment

Thank you for the review and feedback! We respond to your stated weaknesses and questions below.

As noted by the authors, efficiency is evaluated only on solved problems, which introduces a bias that complicates comparisons between models.

Yes, that is right: A model with higher accuracy solves more problems, so its efficiency is evaluated over a larger set which may contain problems for which it is harder to find an efficient proof. We agree that it would be useful to additionally report efficiency on a common intersection set. Comparing the four reward models by taking the intersection of problems solved by all four checkpoints, we obtain scores that mostly preserve the efficiency rankings reported in the submitted draft. For example, see the following results for the checkpoints stemming from the A* dependency heuristic:

Llama-3.2-3B:

Methodn_ownn_interpush_eff_ownpush_eff_interpop_eff_ownpop_eff_inter
SFT43822620.8%22.1%27.3%29.3%
+Correctness42022622.7%23.4%30.0%31.3%
+Steps37222639.2%43.0%64.4%72.4%
+A*-dep.36622635.3%37.9%57.0%61.9%
+A*-true38022633.5%36.5%52.5%58.6%

Llama-3.2-1B:

Methodn_ownn_interpush_eff_ownpush_eff_interpop_ eff_ownpop_eff_inter
SFT25511718.4%19.8%24.2%25.9%
+Correctness30511718.8%19.3%24.5%24.8%
+Steps26911722.8%23.7%29.2%30.2%
+A*-dep.29911719.7%20.8%26.0%27.0%
+A*-true29911719.7%20.5%25.7%26.3%

We will report corresponding results for all (model, SFT checkpoint)-combinations in the appendix for the camera-ready version of the paper, should the paper be accepted.

The discussion of the results is rather brief. I would have appreciated the authors sharing their intuition or possible explanations for why some rewards work better than others, and why each affects accuracy and efficiency differently.

Thanks for pointing this out; we agree and had planned to include further discussion in the final version. For example, we had commented out a paragraph discussing the efficiency in comparison to the underlying oracle algorithms (i.e., A* and Dijkstra’s) that we will restore for the final version. Regarding your specific request on intuition around reward signals: The correctness reward is only a binary signal, providing a positive reward only if the proof is correct, regardless of its length. This leads to the model learning to solve more problems but it has no pressure to be concise, explaining why it generally yields lower efficiency but higher accuracy than the other rewards. The step count reward is generally the most efficient in terms of push efficiency, which comes at the cost of accuracy. The intuition behind this trade-off is that shorter proofs are harder to produce; they require less exploration, which could lead to more difficult proof steps (e.g., taking steps that require more lookahead). The A* rewards provide a more subtle signal derived from the algorithm. Note that the priority queue in A* determines the ordering of the items that get popped, and only indirectly determines the items that get pushed. We therefore, expect the A* rewards to favor pop efficiency over push efficiency, which is indeed what we observe empirically.

We will include the above discussion in the final version of the paper.

(Minor point) Figures 3, 4, 8 and 9 are not very readable. They contain different shapes, colours and borders, and the hatching is difficult to see. I recommend improving their readability if possible.

Thanks for the feedback on this; we will make sure to iterate further on the figures to improve readability. We have played around with vertical hatches with thicker lines, which helped.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.