- 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
-
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.
-
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
- 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
- Do the efficiency comparisons hold when the problem subset is normalized? With token counts?
- Are there controls around SFT exposure to off-path inferences for different traces?
2 comments
Thanks for the responses and additional analysis. My score remains "accept".
Thank you for the positive review and for appreciating research into understanding the full reasoning process! We respond to your questions below.
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:
Llama-3.2-1B:
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.
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.
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.