acceptodds
Withdrawn from ICLR 2027

Budget-Aware Predict-and-Verify Theorem Proving with Heterogeneous LLM Solvers

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Large language model (LLM) theorem solvers differ in both proving capability and inference cost. Applying an expensive solver to every subgoal wastes computation when cheaper models are sufficient, while always starting from the cheapest solver wastes attempts on subgoals that require stronger models. We present BudgetPV, an agentic budget-aware predict-and-verify system that allocates computation across unresolved subgoals and heterogeneous LLM solvers. BudgetPV uses a cross-solver predictor to guide solver selection for each subgoal and revises the allocation as verification feedback becomes available. The allocation problem changes as proving progresses. Early decisions mainly determine which solver should handle an untried subgoal, while later decisions determine which previously attempted subgoals should receive additional computation. We train the predictor with two objectives for these two stages. Class-weighted cross-entropy improves assignment to less frequent stronger solvers during the initial stage, while plain cross-entropy provides better calibrated probabilities for later allocation among previously attempted subgoals. We evaluate BudgetPV on Lean Workbook, miniF2F, ProofNet, and PutnamBench using three progressively expanded solver settings: a strong but expensive solver alone, adding a medium-cost solver with intermediate solving capability, and further adding a cheap solver with lower solving capability. BudgetPV requires less LLM generation computation than uniform allocation to solve the same number of subgoals across the evaluated settings. The experiments further show the computation savings obtained as medium- and lower-cost solvers are added.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Formal theorem proving, LLM theorem proving, test-time computation, adaptive computation allocation, heterogeneous LLM solvers

Reviews

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

The paper proposes BudgetPV, a budget-aware framework that allocates proof attempts across unresolved subgoals and heterogeneous LLM solvers. It uses a cross-solver predictor to rank actions by estimated success relative to generation cost, updates estimates after failed attempts, and switches between two predictors trained for different stages of proving. Experiments on four datasets report lower proof-generation costs than uniform allocation at matched subgoal-solving targets in both live and replay settings.

Critical strengths
  1. The paper studies computation allocation jointly across proof subgoals and heterogeneous solvers, addressing a meaningful efficiency challenge when models differ in capability and inference cost.

  2. The paper evaluates the method through both live proof generation and controlled replay across four datasets. Using shared proof-attempt pools in replay helps isolate the effect of allocation decisions from variation in proof generation.

Critical weaknesses
  1. The evaluation does not establish theorem-level proving effectiveness. The main results measure generation cost at fixed subgoal-solving targets, rather than the fraction of complete theorems proved under a fixed budget. These targets are defined relative to the subgoals solved by Goedel-Prover-V2-32B, so the reported “90%” target should not be interpreted as a benchmark-level theorem success rate. Since completing a theorem requires solving every necessary subgoal, prioritizing inexpensive subgoals may improve the reported metric without increasing the number of completed proofs. The paper should report complete-theorem success rates across matched computation budgets, with final proof assembly and verification.

  2. The reported efficiency gains exclude the predictor’s inference cost. The evaluation counts only proof-generation GPU-seconds, although BudgetPV relies on an 8B predictor with two stage-specific variants. The paper does not quantify this overhead or clearly specify the inference and caching protocol, including what is recomputed when switching predictors. Consequently, the reported generation savings do not establish a net inference-cost advantage. A cost breakdown including prediction, proof generation, and verification is needed, particularly where the advantage over Uniform is small. Meanwhile, the BudgetPV should require 4 models (one predictor, and 3 solver) in the environment, much larger than the baseline.

  3. The cost of constructing the predictor’s training data is not quantified. Although the paper describes the basic labeling procedure, the three-solver configuration requires eight proof attempts per solver for each of 3,488 training subgoals—83,712 proof-generation attempts, together with verification. The paper does not report the total data-collection and fine-tuning costs, or sufficiently explain the upstream subgoal-construction process. Reporting these costs separately and estimating how much deployment usage is needed to amortize them would clarify the method’s practical value.

  4. The comparisons do not isolate the benefit of the proposed allocation design. Uniform is the only practical allocation baseline, while the Statistics Oracle uses unavailable outcome information. Comparisons with a cheap-to-expensive cascade and a static learned router would help establish whether the proposed adaptive mechanism is necessary. Moreover, the predictor analyses in Appendix B do not substitute for end-to-end comparisons of weighted-CE-only, plain-CE-only, and the proposed two-stage policy. Such comparisons are needed to substantiate the claimed benefit of switching objectives during proving.

Questions for authors

Please refer to my weaknesses.

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

This paper introduces BudgetPV, a budget manager for decomposed formal theorem proving with heterogeneous LLM solvers. It jointly selects a subgoal and a solver using predicted success and generation cost, and updates the allocation after verification. The method uses separate predictors for initial assignment and later allocation. Experiments include both live execution and controlled replay on four benchmarks.

Critical strengths
  • The paper addresses a practical problem: additional inference compute is useful, but spending it uniformly across subgoals and models is unlikely to be efficient.
  • The budget manager operates on top of existing provers, which makes the approach potentially useful beyond a particular proof-search implementation.
  • The combination of live and replay experiments is a strength. The reported generation-cost reductions over Uniform are encouraging, including in the single-solver setting, where the gains cannot come simply from using a cheaper model.
Critical weaknesses
  • The evaluation would be stronger with a tuned cheap-to-expensive cascade and direct ablations of the two-stage predictor and failure update. The current predictor analyses provide motivation, but do not fully isolate their contribution to computation savings.
  • The main metric measures proof-generation cost at subgoal coverage targets. This is useful, but leaves open how much of the benefit carries over to total online cost and complete theorem proofs.
Questions for authors
  • How should the cumulative probabilities in Eq. (1) be interpreted when a cheaper solver succeeds on a subgoal but a more expensive solver does not? Relatedly, how does the eight-attempt training label relate to the probability of the next attempt succeeding?
  • Could the authors report the cost of predictor inference and Lean verification, and ideally a theorem-level completion result?
  • How does BudgetPV compare with using the plain-CE predictor throughout? Also, how is the 75% switching threshold determined for a new workload without knowing the strong solver’s eventual coverage?
Reviewer_Pz9zOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

This paper study a critical problem that how to make Lean proof generating more efficient. It proposed BudgetPV, an agentic system dynamically allocate resource on different subgoals in Lean proof generating. The evaluation on four benchmakrs show that BudgetPV achieves the same subgoal solve rates with much less resource.

Critical strengths

The paper studies a less explored topic in Lean proof generating agents. It focuses on how to solve math problems in Lean more efficiently.

Critical weaknesses

I have three main concerns about this paper, listed from most to less serious.

  • First, the actual benefit of BudgetPV for the efficiency of generating Lean proofs is unclear. It shows lower computation costs for fixed subgoal solve rates, but a higher subgoal solve rate does not translate into more completed proofs. A single subgoal failed prevents the original problem proved. BudgetPV cannot revise the proof sketch when this happens. Therefore, problem level results are necessary to show its practical benefit.
  • Second, the paper neither compares BudgetPV with existing agentic systems nor shows that it is easy to extend to general agentic systems. Comparisons with other agentic systems used to generate Lean proofs would help, such as Claude Code, Codex, or Goedel-Architect [1]. On the other hand, the design of BudgetPV is based on a fixed workflow. It is unclear whether its dynamic resource allocation idea can be extended to other agentic systems.
  • Third, the evaluation does not reflect recent progress in Lean theorem proving. The evaluation uses Goedel-Prover-V2 and Kimina models from 2025. Newer general-purpose models have demonstrated strong Lean proving capabilities, and harder evaluation benchmarks such as FATE-X [2], Formal Conjectures [3], and IMO 2026 are available. It is unclear whether its reported efficiency applies to newer models and more challenging problems.

References

[1] Jui-Hui Chung et al. Goedel-Architect: Streamlining Formal Theorem Proving with Blueprint Generation and Refinement. arXiv:2606.06468.

[2] Jiedong Jiang et al. FATE: A Formal Benchmark Series for Frontier Algebra of Multiple Difficulty Levels. arXiv:2511.02872.

[3] Moritz Firsching et al. Formal Conjectures: An Open and Evolving Benchmark for Verified Discovery in Mathematics. arXiv:2605.13171.

Questions for authors

I don't have additional questions. I will be appreciate if the authors can provide clarification or more results to address the concerns in Weaknesses section.

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

Related papers

Discussion (0)

Sign in to comment.