acceptodds
Under review as a conference paper at ICLR 2027

Direct Optimization of Generators for Search in Automated Theorem Proving

Abstract

Fine-tuned Large Language Models (LLMs) significantly advance Automated Theorem Proving (ATP), but are often deployed as guiding policies within tree search rather than for single-attempt generation. Recent work shows cross entropy is suboptimal for an LLM used in flat search strategies such as aggregation or filtering and that work has developed new loss functions to correct this misalignment. Extending this alignment to tree search is more challenging: proof discovery depends on exploration and recovery through off-trace states that supervised demonstrations do not reveal. We extend Compute-Aligned Training (CAT) to this setting through an abstraction of policy-guided search, deriving tractable, trace-supported losses. Alongside these search-aware losses, we introduce a search-agnostic uniform-allocation (UA) loss that accounts for the budget without specifying the specific search. Both induce scalar weights on per-tactic cross-entropy gradients. We characterize how off-trace behavior affects the search-aware weights, including conditions for vanishing approximation error at large budgets. On a Lean benchmark, both approaches achieve higher observed proof-success rates than cross-entropy across six search strategies, with strong results from a single shared UA adapter. Budget sweeps show larger gains over cross-entropy at than at expansions, implying CAT scales with test time compute.

Primary area:
optimization
Keywords:
Policy Guided Search, LLMs, Automated Theorem Proving

Reviews

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

The paper studies how supervised fine-tuning objectives can account for finite-budget search in automated theorem proving. It introduces strategy-specific Compute-Aligned Training (CAT) objectives and a search-agnostic Uniform-Allocation (UA) objective, both implemented through weighted tactic-level cross-entropy gradients. The theoretical analysis examines how alternative proofs, off-trace exploration costs, and recoverability affect approximation error. Experiments evaluate Qwen2.5-Math-7B-Instruct on 458 LeanDojo theorems across six search strategies and multiple computational budgets.

Critical strengths

The paper connects training objectives with proof discovery under finite computational budgets, extending compute-aligned training to tree search and providing a unified framework for addressing the mismatch between supervised training and deployment-time search.

By introducing both strategy-specific and shared objectives and observing improvements across multiple search methods, the paper demonstrates the feasibility of improving deployment-time search through changes to offline supervised training objectives.

Critical weaknesses

The trace-supported objectives omit aspects of deployed search. Non-demonstrated actions are collapsed into a single deviation event, while the best-first search surrogate replaces frontier competition with repeated sampling at a single node. Demonstrations alone cannot determine alternative proof opportunities, recovery costs, or irreversible deviations, so the theoretical conclusions depend on explicit modeling assumptions.

The experiments use one model and theorems whose reference proofs contain only two to five steps. The budget sweep trains separate adapters for each strategy and budget, and the completed evaluation subsets differ across budgets. Consequently, cross-budget comparisons involve changes in both adapters and evaluated theorem sets.

Questions for authors

What motivates using (N/4) to approximate the rollout budget for Pass@N training, and how does this conversion account for actual proof lengths and early rollout failures?

How large is the common theorem subset evaluated at every budget in Table 2, and what are the gains over CE at 16 and 256 expansions on that shared subset?

3 comments
AuthorsOpenReview ↗

We would like to thank the reviewer for their positive perspective on our work and the careful review.

Q1

Kindly refer to our response to reviewer amMw on Q3.

Q2

The common completed subsets contain 408 theorems for Pass@N and 407 for BFS. Recomputing the paired results on these subsets, the respective alignment gains at budgets 16 and 256 are +1.96 versus +4.17 percentage points for Pass@N, and +3.93 versus +6.88 points for BFS.

These comparisons eliminate changes in theorem composition across budgets. As noted in our response to Reviewer amMw in their Q2, the point-estimate increases remain positive.

Thank you for your responses and clarifications. I maintain my overall positive assessment of the work, while retaining views on the potential issues.

Thank you for your positive perspective on our work. We appreciate the reply and the broader review.

Reviewer_amMwOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how to align training objectives for automated theorem proving with deployment-time search and compute budgets. It introduces trace-supported, strategy-specific CAT objectives and a search-agnostic uniform-allocation objective, UA. Both yield scalar weights on per-tactic cross-entropy gradients. The analysis examines how alternative proofs and off-trace recovery costs affect the weight approximation. On 458 Lean theorems with reference proofs of 2–5 steps, both approaches achieve higher observed proof-success rates than CE across six search strategies, with strong performance from a single shared UA adapter.

Critical strengths
  1. The experiments provide useful controls: within each experiment, methods share a CE warm-up and retain the same subsequent training data, ordering, and optimizer settings. This helps distinguish the effect of the objective from that of additional training.
  2. UA uses a single adapter across search strategies and achieves the highest point estimates under all five branching strategies, demonstrating practical value. The theoretical analysis also distinguishes recoverable excursions from permanent loss of recovery, making the limitations of trace-only approximation explicit.
Critical weaknesses
  1. The additional benefit of modeling the search strategy over UA is not sufficiently established. In Table 1, UA has higher point estimates than the corresponding CAT objective under all five branching strategies. CAT leads UA only under Pass@N, at 26.6% versus 25.1%. The main text also reports matched-versus-mismatched strategy comparisons, but these point estimates do not establish whether the additional gains are reliable.
  2. The comparison of gains across budgets uses different theorem cohorts. Table 2 evaluates all 458 theorems at budgets 16 and 64, but only 408 and 407 theorems at budget 256. Consequently, the larger gains at budget 256 than at budget 16 reported in §5.2 have not been separated from changes in the evaluation cohort. Figure 2 acknowledges this limitation, but a common-cohort comparison is still missing.
Questions for authors
  1. Could you provide paired comparisons between CAT and UA with uncertainty estimates, particularly for the 26.6% versus 25.1% difference under Pass@N, to assess whether modeling the search strategy provides a reliable additional benefit?
  2. Could you recompute Table 2 using the common set of completed theorems across budgets within each strategy, and report a confidence interval for the change in CAT’s gain over CE between budgets 16 and 256?
  3. Footnote 7 in §5 uses a fixed N/4N/4 conversion from expansion budget to the training-time rollout budget for Pass@N. How was this factor selected, and how sensitive are the results to this choice?
2 comments
AuthorsOpenReview ↗

We would like to thank the reviewer for their time and clear review. We hope that our rebuttal clarifies some key details of the paper.

Q1

We agree that the advantage of strategy-specific CAT over UA is not established by Table 1. However, this is precisely a key takeaway of our paper (Please see our response to Reviewer JDfS on W2). The key idea we were trying to convey was that consideration of the search strategy during training generally seems helpful, while the specific strategies are not cleanly able to be modelled with only offline data. We theoretically characterized why this is the case in Section 4.

We include a full table of the paired comparisons here:

Search strategyCE (%)CAT (%)UA (%)UA-only / CAT-onlyUA − CAT (pp)95% CI (pp)McNemar p
Pass@N21.226.625.112 / 19−1.53[−3.93, 0.87]0.281
BFS23.825.126.919 / 11+1.75[−0.66, 4.15]0.200
DFS19.220.723.627 / 14+2.84[0.22, 5.68]0.060
RDFS20.723.625.318 / 10+1.75[−0.44, 3.93]0.185
VDFS21.223.824.514 / 11+0.66[−1.53, 2.84]0.690
MCTS20.322.525.129 / 17+2.62[−0.22, 5.46]0.104

Again, we are not at all concluding that CAT outperforms UA. In fact, the opposite being true is one of our key observations.

Q2

We thank the reviewer for identifying the cohort-comparison issue. We recomputed the alignment gains using the common set of completed theorems across all three budgets for each strategy.

For Pass@N, the common cohort contains 408 theorems, with CAT–CE gains of +1.96, +5.88, and +4.17 percentage points at budgets 16, 64, and 256, respectively. For BFS, the corresponding common cohort contains 407 theorems, with gains of +3.93, +4.67, and +6.88 points.

The change in alignment advantage from budget 16 to 256 is +2.21 points for Pass@N (95% paired bootstrap CI: [−1.23, +5.64]) and +2.95 points for BFS (CI: [−0.74, +6.63]).

Thus, the positive direction of the observed change persists after removing differences in theorem composition. Furthermore, to clarify, these budgets use separately trained adapters; the results concern budget-matched training and deployment, rather than increasing inference compute for a fixed policy.

Q3

Our evaluation budgets are measured in tactic expansions, whereas, Pass@N's natural budget is usually expressed in complete rollout attempts. We wanted results to be comparable across different search strategies. To make these budgets comparable, we examined the lengths of demonstrated proofs in the training set, whose mean was approximately 3.6 tactics. We rounded this upward to four and used N/4 nominal rollouts for an evaluation budget of N tactic expansions.

This was a fixed, dataset-based approximation rather than a claim that every deployed rollout requires four expansions. In particular, failed rollouts may terminate before reaching the full proof length, and demonstrated proof lengths vary. We agree that the conversion does not capture these effects but the alternative was making comparison unnatural between search strategies.

We checked results (on the same setup as table 1) of dividing budget in the training objective for Pass@N by 3.6 instead of 4 and the results changed negligibly. The success rate was the same 122/458 with 6 total discordant pairs.

AuthorsOpenReview ↗

Less than 48 hours until the discussion window closes.

Thank you again for your review.

We address your comments and questions in our answers above.

We hope that we've clarified that our goal was not that CAT beats UA, but rather that the role of these two objectives is to provide nuance on the tractability of supervised search-aware losses in our setting.

If you have further questions, we are very happy to answer them.

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

This paper studies the mismatch between SFT with cross-entropy (CE) loss and test-time tree search in automated theorem proving. Standard CE implicitly assumes each tactic must succeed on its first attempt. In deployment, however, the policy is paired with a budgeted search (Pass@NN, BFS, DFS variants, MCTS). Contributions:

  1. Compute-Aligned Training (CAT) for tree search. Search dynamics are restricted to the demonstrated trace, and all off-trace deviations are collapsed into a single "trace-miss" event. This yields tractable surrogate objectives whose gradients are scalar reweightings of per-tactic CE gradients (Prop. 1). The surrogate is instantiated for Pass@NN, BFS, RDFS, VDFS, and MCTS.
  2. Search-agnostic Uniform Allocation (UA). A closed-form objective that gives each demonstrated step a uniform local budget Kˉ=N/L\bar{K} = N/L.
  3. Approximation-error theory. The gap between surrogate and true weights is characterized through a bypass channel (unobserved alternative proofs, which deflate weights) and a trap channel (off-trace excursions consuming shared budget, which inflate weights), with large-budget limits (Thms. 1–3).
  4. Lean 4 experiments. With Qwen2.5-Math-7B-Instruct + LoRA on 458 theorems (2–5 reference steps) from leandojo-benchmark-4-random, both CAT and UA outperform an epoch-matched CE control across six search strategies.
Critical strengths
  1. Clean formalization. Prop. 1 unifies trace-supported search surrogates as scalar weights on per-step CE gradients, so they drop easily into existing SFT pipelines.
  2. Honest, insightful theory. Section 4 and Appendix C carefully characterize what offline demonstrations cannot reveal: the bypass-vs-trap tension and the irreducible ambiguity of trace-only supervision (Prop. 4).
  3. Simple, effective UA. UA is closed-form with negligible overhead, and a single shared adapter transfers across all tested strategies.
  4. Statistical care and transparency. The paper uses paired McNemar tests and openly documents its experimental caveats (Appendix G).
Critical weaknesses

W1. Limited significance relative to current formal-math systems.

  • §1.1 places the work in the tactic-level SFT paradigm (ReProver, Llemma) and explicitly excludes RL and informal–formal pipelines.
  • It claims that "state-of-the-art theorem provers rely on branching strategies." That is no longer accurate. Current provers instead use:
    • whole-proof generation with compiler feedback (DeepSeek-Prover-V2, Goedel-Prover-V2, Kimina-Prover), or
    • agentic loops over lemma DAGs and proof drafts (LEAP, AlphaProof Nexus), often with general-purpose LLMs and no fine-tuning, or with RL.
  • In these systems, search and budget operate over lemmas, compile attempts, and LLM calls, not tactic-node expansions.
  • The paper's own theory (Prop. 4) shows the core limitation is missing off-trace information. Agentic and RL pipelines produce exactly that information.
  • The work would be much more relevant if a "step" were reframed as a lemma or refinement round. UA is then close to allocating budget across the AND-children of a lemma DAG.
  • Note: LEAP and Nexus may count as contemporaneous work, so I do not penalize the lack of a direct comparison. The broader paradigm shift dates back to 2025.

W2. Search-aware CAT loses to search-agnostic UA.

  • Shared UA beats strategy-matched CAT on all five branching strategies: BFS 26.9 vs. 25.1, DFS 23.6 vs. 20.7, MCTS 25.1 vs. 22.5.
  • CAT wins only under flat Pass@NN, where it is close to DCO.
  • As the authors acknowledge, projecting a search tree onto a single trace removes cross-branch competition: BFS collapses to DFS (Eq. 13), and MCTS keeps only its widening schedule. The strategy-specific losses, which are the main methodological contribution, therefore add little.

W3. Narrow evaluation.

  • Only 2–5-step proofs, with search depth capped at 5. This is the regime where budget allocation should matter least.
  • No results on miniF2F, ProofNet, or PutnamBench.
  • Only one base model (7B, LoRA).
Questions for authors
  1. Relevance to agentic and whole-proof provers. Can CAT/UA be instantiated with a "step" defined as a lemma or refinement round, and the budget defined as compile attempts or LLM calls? Is there any evidence, even small-scale, that alignment helps in that setting?
2 comments
AuthorsOpenReview ↗

We would like to thank the reviewer for a thorough and well-thought-out review. This review helped us focus on and articulate how our methodology and perspective can remain relevant as the field rapidly moves.

W1/Q1

We agree state-of-the-art has moved and will correct §1.1. Our goal isn't advancing the strongest end-to-end system, but to ask how to train when deployed within budgeted search. This remains relevant for three reasons.

SFT remains useful within RL and agentic pipelines. Verified proofs discovered by humans or machines can be reused as demonstrations. DeepSeek-Prover-V2 uses SFT to warm start RL, while Goedel-Prover-V2 combines proof collection, SFT, and RL. Online exploration doesn't eliminate the question of which supervised loss to optimize. Not using SFT would mean throwing out all demonstrations of successful proofs. Cross-entropy (CE) doesn't account for how SFT interacts with the rest of the pipeline. Our method takes steps in this direction by coordinating the objective with the rollout procedure, helping integrate SFT into more modern pipelines. Also, off-trace rollouts could improve the estimates of our loss. However, we found naively constructing stable weight estimates for each tactic would cost ≈1000\approx1000 times the GPU hours.

Our abstraction can be instantiated directly for agentic lemma-level search. Consider a prover that decomposes a goal GG into lemmas and searches for proofs of the lemmas. Define a configuration c=⟨F,M⟩c=\langle F,M\rangle, where the frontier FF contains unresolved lemmas xix_i with priority scores sis_i, and MM contains the lemma dependencies, the partial proof, previously verified lemmas, and the remaining budget. The selection rule SA(xi∣c)S_A(x_i\mid c) chooses which lemma to attempt next. The generator proposes complete proofs y∼πθ(⋅∣xi)y\sim\pi_\theta(\cdot\mid x_i), and T(xi,y)T(x_i,y) returns its verification outcome. The update rule UA(c,xi,z)U_A(c,x_i,z) does a compilation attempt, records successful proofs, and checks off dependencies if verification succeeds. Search terminates when the assembled proof of GG is verified, or the budget is exhausted. Demonstrated lemma-solving trajectories could then support our supervised objectives. The underlying training–search alignment question remains unchanged. However, we can't recreate such a system in time.

The problem occurs outside mathematics wherever learned policies guide structured search. In settings like Go or Chess, one would like to make use of already collected expert games. Our work would allow a practitioner to make supervised learning from these games account for downstream MCTS use. Likewise, in Erata et al. (2026), Learning How to Cube, demonstrations are used to train a policy that is used in Cube-and-Conquer (a search strategy) for SAT solving. These illustrate the framework's broader motivation.

W2

We agree UA usually beats CAT and CAT collapses many search dynamics. Both are our methods. However, the intended main contribution isn't strategy-specific adapters. We had two questions: whether training should account for deployment-time procedure, and whether explicitly modeling the deployed search with offline data provides additional advantage. Our results provide evidence for the former and against the latter. That's the conclusion we mean to present. UA precisely demonstrates that accounting for a finite search budget can be beneficial without an exact model of the search procedure. This connects to our analysis in Section 4. A large chunk of the paper is understanding what trace-supported approximations of the loss necessarily lose. Our strategy-specific objectives can't fully reproduce the deployed algorithms. No fully offline loss can. Our results show search awareness is useful, while illustrating the practical limitations of approximating structured search using offline demonstrations alone. We will make this distinction more explicit in our discussion of the empirical results.

W3

We agree evaluation on one 7B model and theorems with 2–5-step proofs is narrow. However, short reference proofs don't imply search is unimportant. Even with few steps, discovering a proof can require a lot of exploration. Our evaluation still probes the central question of allocating finite test-time compute. We set the depth cap because excessively long proofs are uninformative since no amount of searching found the proofs.

To broaden evidence, we are evaluating CE, CAT, and UA under both Pass@N and BFS on miniF2F (n=244), with matched inference budgets and the full test set. This uses the adapters trained on LeanDojo.

MethodPass@NBFS
CE79 (32.38%)80 (32.79%)
CAT81 (33.20%)82 (33.61%)
UA81 (33.20%)81 (33.20%)

The margins on miniF2F are smaller than on Mathlib, potentially reflecting both greater statistical uncertainty from the smaller test set and a shift in search dynamics. This raises a broader question for our framework: how does training–search alignment generalize across problem distributions? These results suggest that alignment benefits may depend on the distribution of proof states encountered at test time.

AuthorsOpenReview ↗

Less than 48 hours until the discussion window closes.

Thank you again for your review.

We address your comments and questions in our answers above.

We hope that we've given a broader perspective on the scientific relevance of our work.

If you have further questions, we are very happy to answer them.

Comments on the paper

2 comments
Area_Chair_LMBxOpenReview ↗

Response to the rebuttal

Dear reviewers,

The authors have submitted rebuttal responses. Please read through their replies and update your review as you see fit. Thank you for your work.

AC.

AuthorsOpenReview ↗

Summary of Reviews and Rebuttals for AC

Dear Area Chair,

We thank the reviewers for their thoughtful feedback. We summarize how our rebuttal addressed their main concerns.

Reviewer JDfS (2): We clarified that our focus is on the scientific problem of supervised training with knowledge of the model being used for search at test time, rather than us trying to beat state-of-the-art theorem provers. We then explained why compute-aware SFT matters for the development of theorem provers going forward and its relevance to non-mathematical settings. We also clarified that UA's strong performance is a key finding designed as a tool to analyze limitations of trace-only search modeling. Finally, we provided additional out-of-distribution results on miniF2F. We really appreciated this review and found it constructive.

Reviewer amMw (2): We directly addressed all three questions with new analyses.

(1) Paired CAT–UA comparisons with confidence intervals and significance tests. We believe the underlying concern, however, was better addressed in our response to reviewer JDfS on why we included UA.

(2) Common-cohort budget comparisons confirming that the positive scaling trend persists after removing cohort differences.

(3) A small sensitivity analysis showing unchanged Pass@N accuracy when varying the budget conversion factor.

Reviewer 5PY5 (3): We addressed both experimental questions through our responses to the other reviewers. The reviewer subsequently reaffirmed their positive assessment of the paper.

We thank the AC again for their consideration.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.