acceptodds
Under review as a conference paper at ICLR 2027

Optimizing the Cost-Quality Tradeoff of Agentic Theorem Provers in Lean

Abstract

Large language models (LLMs) are increasingly used in workflows for generating formal proofs in Lean. These workflows often decompose problems into smaller lemmas, sample many proof attempts, and use compiler feedback to guide search. However, they can be prohibitively expensive, often spending substantial compute on attempts that ultimately fail. In this work, we address this problem with an action routing agent that consists of a data plane and a control plane. The data plane generates natural-language lemma decompositions, formalizes them in Lean, and samples proof attempts for the resulting theorem and lemma targets. The control plane observes previous failed Lean attempts, estimates both the likelihood of success and cost of another attempt, and decides whether to continue proving the current target or restart from a new breakdown. On a subset of PutnamBench, our agent decreases the cost by 28.9% over a fixed-step baseline on average, preserving performance while using substantially less compute. These results suggest that failed Lean trajectories provide actionable signals for cost-aware resource allocation in agentic theorem proving.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Automated theorem proving, Lean, LLM Agents, Cost-aware routing, Cost-quality tradeoff

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_yzsrOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper targets the cost of agentic Lean provers, which typically allocate a fixed number of attempts per target. It proposes a two-part agent. The "data plane" is a lemma-style prover: GPT-OSS-20B writes a natural-language breakdown into lemmas, Goedel-Formalizer-V2-8B formalizes them, and Goedel-Prover-V2-8B first proves the main theorem with the lemmas as axioms and then proves each invoked lemma (up to 8 breakdowns per problem). The "control plane" is a router that, after each failed attempt on a target, decides whether to ATTEMPT again or TERMINATE the breakdown, using the utility q̂ − λĉ, where ĉ is the mean output tokens of prior attempts and q̂ comes from a logistic regression on attempt count, proof similarity, and Lean error diversity. Evaluation uses the 85 PutnamBench problems reportedly solved by Goedel-Prover-V2-32B, split 42/43 into router-training and test problems, with cost measured as parameter count × output tokens, and policies evaluated by replaying 64 pre-generated attempts per target over 64 shuffled seeds. Against a fixed-attempt baseline, the router reports a 28.9% reduction in cost AUC and a 7.9% increase in solve-rate AUC; an oracle with ground-truth target success rates reaches 62%, and the lemma pipeline solves 48/85 problems vs. 23 for whole-proof generation with the same 8B prover.

Critical strengths
  1. An important and under-studied problem. Agentic Lean provers are expensive (the paper cites $40–50 per problem for top systems), and prior work has largely optimized solve rate rather than cost. Framing attempt allocation as a cost-quality routing decision over failed proof trajectories is a sensible and practically relevant direction.

  2. A simple, interpretable router with useful diagnostics. The control plane is lightweight (a logistic regression on three trajectory features) with an explicit cost-quality objective, and the paper contextualizes it well: the oracle and noisy-oracle comparisons (Table 1) indicate how much headroom better difficulty estimation could unlock, and the feature ablation and coefficient analysis (Table 2, App. B) are easy to interpret. Code is provided to reviewers.

Critical weaknesses

1. Evaluation setup. The evaluation is too narrow and has several design choices that make the headline numbers hard to interpret.

  • Problem selection isn't consistent with the motivation. The paper motivates routing by compute wasted on infeasible or misformalized problems (Sec. 1), but evaluates only on the 85 PutnamBench problems already known to be solved by Goedel-Prover-V2-32B (Sec. 4.1), which is the regime where early termination should help least.
  • Scale and variance: results are on 43 test problems, one random train/test split, one benchmark, and one prover model, and lacking error bars or confidence intervals. At the high-budget end the reported solve-rate differences (0.2–0.4 points) are smaller than one problem.
  • The results are produced by replaying 64 pre-generated attempts per target (App. A), which is not stated in Sec. 4. This detail of this setup affect fairness: the pool caps the baseline at 64 attempts per target.
  • Reporting: the claim that the agent "improves solve rate by 7.9%" (Sec. 1, Sec. 6) is an AUC average over budgets, which should be stated explicitly. Figure 3 does not indicate which λ produces which point, and the λ values behind the point comparisons are not given, so there is no guidance on choosing λ in practice. The data-plane comparison (Fig. 4) reports results on all 85 problems including the router-training set, unlike the other results.

2. Incomplete cost accounting and missing baselines.

  • Cost is measured as effective parameters × output tokens only (Sec. 4.1). In agent workloads input tokens are often a large share of cost, and they are not counted. It is also unclear whether the GPT-OSS-20B breakdown/selection calls and the formalizer calls are included, the router's own cost is not reported, and "effective parameter count" is not defined (relevant because GPT-OSS-20B is a mixture-of-experts model). Lean compilation is assumed negligible (Sec. 3.2.3); that is plausible, but it should be measured. Wall-clock time or dollar cost for the router vs. the baseline would make the savings concrete.
  • The only baseline is a fixed per-target attempt budget. There are no simple adaptive heuristics (e.g., stop after repeated identical errors, or thresholds on attempt count plus output length) and none of the routing/cascading methods cited in Sec. 2.
Questions for authors

Questions that could change my assessment:

  1. Can you add baselines beyond the fixed-step policy, e.g., simple adaptive stopping heuristics and at least one of the routing/cascading methods from Sec. 2?

  2. Can you report total cost including input tokens, the breakdown/formalizer/selection calls, the router itself, and Lean compilation, along with wall-clock time or dollar cost, for the router vs. the baseline? How is "effective parameter count" defined for GPT-OSS-20B?

  3. Can you report error bars (e.g., across Monte Carlo seeds and across multiple train/test splits), and compute AUCs with matched operating-point grids (or a denser k sweep for the baseline) so that interpolation does not favor either method?

  4. How does routing perform on problems outside the "known solvable" subset, where wasted compute on infeasible targets is the main motivation? I recognize running the full PutnamBench may exceed the available budget (Sec. 5 estimates 12k–16k GPU hours); even a random sample of unsolved problems, or the full benchmark if feasible, would substantially strengthen the claims.

  5. Lemma dependencies: the router's loss considers only the next attempt on the current target, but a breakdown succeeds only if all remaining invoked lemmas are proven, and TERMINATE discards already-proven lemmas. In the replay, how are lemma attempts handled given that which lemmas must be proven depends on which theorem-level proof succeeded — were attempts pre-generated for every lemma of every breakdown?

  6. Which λ values produce the operating points in Fig. 3 and the point comparisons in Sec. 4.2, and how should a practitioner choose λ?

  7. Can you double check: whole-proof baseline yields 23 solves at pass@256 on your subset vs. 25 at pass@32 reported by Geodel Prover Lin et al. (2025b).

3 comments

Q1. Can you create additional baselines based on heuristic approaches and cited works?

See Q2 and Q3 in the general response. Additionally, thresholds on attempt counts and output length are essentially the routing model using only attempt count as a feature. As we see in Table 2 (p8), our router improves upon this baseline, by 14.8% cost AUC reduction.

Q2. Can you clarify how lemma dependency is handled in the replay experiment?

For each breakdown, we pre-generate 64 proof attempts for the main theorem and every formalized lemma. During replay, the successful theorem-level proof determines which lemmas are added to the proof stack. We then draw attempts from the corresponding lemma pools. Each successful lemma proof can add further required lemmas to the stack. Thus, the targets visited depend on the particular proofs accepted during replay.

Q3. Does the interpolation between values of kk and λ\lambda favor any method?

No, the interpolation seems to be valid. By running our simulations for all 64 possible values of kk, and 64 logarithmically spaced values for λ\lambda we observe a +0.4% increase in cost AUC reduction of our router compared to the fixed-step baseline.

Q4. Can you explain why you only use output tokens as the cost? What about other alternative metrics?

For several alternative metrics, our method significantly outperforms the baseline. The table below shows the improvements of the learned router for input tokens, output SFLOPs, and input + output SFLOPs.

Cost metricCost AUC improvement
Input tokens20.2%
Output SFLOPs28.2%
Input + output SFLOPs27.3%

We do not use input tokens as our main metric for two reasons. First, we do not include any tool calls and therefore the input tokens are only a small part of the tokens processed. For the fixed-step baseline at the maximum inference setting of 64 attempts per target, we process 400k input tokens, and over 3.5M output tokens. Second, the compute required to process input tokens is much smaller than for output tokens. As a proxy, API providers usually charge around 5x less for input tokens than output tokens. Combined, input tokens therefore only contribute around 2% of compute cost.

Additionally, LLM generation takes approximately 10 times as long as Lean compilation and 10,000 times as long as router execution, so wall-clock time is dominated by generation. Thus, both wall-clock time and dollar cost are expected to track SFLOPs well.

Q5. Why do data-plane comparison reports results on all 85 problems?

The data-plane comparison requires no training, so we evaluate all 85 problems without a train-test split. This gives us a larger set of problems to compare the three methods.

Q6. Is there a lack of problems where early termination would be most beneficial? Can you include more problems from PutnamBench?

The problem set includes plenty of problems where early termination is beneficial. The problems are selected based on the 85 problems Goedel-Prover-V2-32B successfully solves. However, our main experiment is based on the Goedel-Prover-V2-8B model, and over half of the problems in our test set are unsolved by our agent in eight breakdowns. All of the unsolved problems benefit from early termination. Additionally, computational constraints prevent us from evaluating more PutnamBench problems.

Q7. What values of lambda are chosen for the experiments?

The values for λ\lambda are listed in Appendix A (p16). We use 9 lambdas ranging from 2⋅10−82\cdot 10^{-8} to 4⋅10−64\cdot 10^{-6}

Q8. How should one choose lambda in practice?

The scale of λ\lambda depends on the expected cost and quality of the routing model. For an initial estimate of λ\lambda, one can estimate the expected quality q^\hat{q} and cost c^\hat{c} of baselines on the validation set. A λ\lambda of roughly correct order of magnitude can then be chosen as λ=q^/c^\lambda = \hat{q}/\hat{c}, as then q^−λc^=0\hat{q} - \lambda \hat{c} = 0 is satisfied. This relies on the interpretation of λ\lambda as unit conversion between accuracy and cost.

Q9. Can you double check that the whole-proof baseline yields 23 solves at pass@256?

We double checked our data and confirmed the number. We used the public inference pipeline code and default configuration on the problems claimed to be solved by them. We ran Goedel Prover V2 8B on each of these problems for 256 samples without self-correction. We got 23 solved problems out of 85 problems. We list these 23 problems here:

1965_a6, 1965_b3, 1967_b2, 1968_a1, 1968_a2, 1975_a1, 1975_b1, 1977_a3, 1982_a5, 1984_b2, 1985_a4, 1986_a1, 1986_a2, 1986_b1, 1988_b1, 1988_b2, 1990_a1, 1990_a5, 1998_b1, 2001_a1, 2005_b1, 2008_a1, 2015_a2

Q10. Why are no baselines from the cascading and routing literature included?

Please see Q3 in the general response.

Thank you for the thorough response. The two new baselines (per-breakdown cost budget and repeated-error stopping), the confidence intervals over 16 train/test splits and seed sets, and the results under alternative cost metrics, including input tokens, address my main concerns. The clarification of how lemma attempts are replayed resolves my question about the simulation. My remaining reservation is scope: one benchmark, one prover family, and 43 test problems. I have raised my score to 3.

Thank you for the response and for raising your score. We are happy you appreciate our new baselines and analysis into statistical significance and alternative cost metrics. Although we unfortunately do not have the funds to test our method on other models or benchmarks, we believe our analysis on performance under different train/test splits and transferring our router between models provides evidence that our method generalizes across other data distributions and models.

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

The paper builds a Hilbert-style Lean prover and adds a control plane that decides, after each failed attempt on a target, whether to attempt again or terminate the breakdown and restart. On a 43-problem test split of an 85-problem PutnamBench subset, it gives a 28.9% lower cost AUC and 7.9% higher solve-rate AUC than the baseline.

Critical strengths
  • The problem (wasted compute on hopeless targets in agentic provers costing $40–50 per problem) is real and the formulation is simple and easy to adopt.
  • Code is provided, and the compute cost of the study is stated.
Critical weaknesses

Baselines are weak. Only a fixed-k policy is compared. Simple adaptive heuristics (stop after r repeated identical errors, global budget split across breakdowns, a difficulty prior from the problem text or from the breakdown) are not tested. Attempt count alone already gives 13.1%, so it is unclear how much the learned features add over a hand rule. There is also no comparison with existing routing/cascading methods the paper cites.

Questions for authors

Can you compare with simple heuristic stopping rules (repeated-error stopping, per-problem global budget, etc.) and with a cascade-style baseline (e.g. tiny model first, escalate on failure)? This answers whether the learned features are needed. Does the router transfer, that is, trained with one prover (8B) and applied to another (32B) or a different breakdown model, without retraining?

1 comment

We thank the reviewer for their thorough review. We appreciate that they find our problem relevant and that our work contributes to an under-explored direction. In this rebuttal, we address their questions and concerns.

Q1. Can you create additional baselines based on heuristic approaches?

Please see Q2 in the general response.

Q2. Do a priori difficulty features provide value?

No, estimating the difficulty of a problem is generally very hard. As a simple proxy, we tried adding the number of Lean tokens in the active target as a feature for the router. This increased the performance on the training set, but on the test set, our router scores 22.9% by including this feature. Therefore, adding the feature makes the model overfit on the training data.

Q3. Does the quality estimator model transfer to other agent setups?

Please see Q1 in the general response.

Q4. Why are no baselines from the cascading and routing literature included?

Please see Q3 in the general response.

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

The paper proposes a cost-aware routing framework for agentic theorem proving in Lean. Its data plane generates natural-language lemma decompositions, formalizes the lemmas in Lean, and produces proof attempts for theorem and lemma targets. Its control plane uses failed proof trajectories to estimate the success probability and computational cost of an additional attempt, then decides whether to retry the current target or discard the decomposition. The main contribution is a lightweight routing mechanism that adaptively allocates proof attempts according to a cost–quality tradeoff. Experiments on a 43-problem test split of an 85-problem PutnamBench subset show improved cost–solve-rate tradeoffs over a fixed-step baseline.

Critical strengths
  • Meaningful gains from a simple routing mechanism.

The paper implements an intuitive cost–quality tradeoff through a lightweight router. Despite the limited action space of continuing or terminating a proof trajectory, the mechanism reduces computational cost while largely preserving solve rate in the evaluated setting. This shows that even simple adaptive control can meaningfully improve the efficiency of an existing proof-generation workflow.

Critical weaknesses
  • Single-benchmark evaluation.

The evaluation relies exclusively on PutnamBench, leaving it unclear whether the observed routing gains generalize to other theorem-proving datasets. While the computational constraints are understandable, evaluating subsets of additional benchmarks would help establish whether the gains extend beyond PutnamBench.

Questions for authors
  • Inconsistent cost reporting for the whole-proof baselines.

Section 4.3.3 refers to Appendix C for details of the whole-proof baselines, and Figures 4 and 5 report costs in the same unit (average M SFLOPs per problem). However, the corresponding baseline curves show matching solve rates but approximately 1.5 times higher costs in Figure 5 than in Figure 4. The numerical examples in Appendix C.2 agree with Figure 5. Could the authors explain the discrepancy between the baseline costs in Figures 4 and 5, and clarify which costs were used to compute the +88.2% and −23.2% solve-rate AUC comparisons in Section 4.3.3? Please tabulate the cost–solve-rate points underlying Figures 4 and 5, indicate which points were used for the AUC comparisons in Section 4.3.3, and report the integration range for each comparison.

3 comments

We thank the reviewer for their thorough review of the paper. We are happy they find our methods intuitive and the gains of using a simple routing mechanism meaningful. In this rebuttal, we address their questions and concerns.

Q1. Can you evaluate your method on other benchmarks?

Unfortunately, running the agent on a single problem costs 20 GPU hours. We currently do not possess the resources to run our agent on more problems. However, we did perform additional evaluations with Goedel-Prover-v2-32B, with which we also obtained good results as explained in Q1 of our main reply.

Q2. Is there an inconsistency on cost reporting in Figure 4 and Figure 5?

Yes, and it has been fixed in the revised manuscript. Previously, in Figure 5, we had the sum of input and output tokens on the x axis which led to inconsistencies between Figure 4 and Figure 5. Now across the paper, cost includes only output cost in the SFLOPs metric.

We integrate from k = 1 to k = 64 in the fixed step baseline for all plots. In all cases, we integrate over the y-axis interval 17.73% to 44.04%. For cost calculations, we integrate from the x-axis interval of 1.7M to 28.1M SFLOPS. These consistent intervals have negligible effect on our results.

Thank you for the detailed response and revisions. I appreciate the addition of stronger baselines, confidence intervals across train–test splits and simulation seeds, and the experiment with a substantially different agent configuration. These additions strengthen the empirical evaluation. I also appreciate the clarification and correction of the inconsistent cost accounting in the whole-proof baseline figures.

My main concern, however, remains the scope of the evaluation. The new transfer experiment provides useful evidence that the routing model can remain effective when the prover and other agent components are changed. Nevertheless, it is still conducted on the same PutnamBench subset. It therefore demonstrates transfer across agent configurations, but not across datasets with different problem distributions or formalization characteristics. I understand that evaluating this system is computationally expensive, but the available evidence still leaves its cross-dataset generality unclear.

Overall, the revisions improve the paper, but they do not resolve the principal weakness underlying my original assessment. I am therefore maintaining my rating and confidence.

Thank you for appreciating our clarification on cost report and additional results on strong baselines, statistical significance and the router’s generalization. Although we are unfortunately not able to test on new problems and benchmarks, we believe that our experiments on different train/test splits provide evidence that our method generalizes across different data distributions (see Q4 in general response).

Comments on the paper

1 comment

We thank the reviewers for their responses. We are happy they find the problem, wasted compute on hopeless targets, real and understudied (cHeV, yzsr), and that they appreciate that even a simple routing mechanism can achieve meaningful gains (BJW1, yzsr) over our baseline. We reply to common questions from reviewers here.

We have made the following revisions to the paper (all marked in red):

  • Model generalization: We run our router using the Goedel-Prover-V2-32B as a backbone (Section 4.4), both with and without retraining the parameters. Our method also significantly improves performance in this case.
  • New baselines: Added two more baselines (Section 4.1), both of which are significantly outperformed by our routern.
  • Statistical significance analysis: We added confidence intervals to the results, with respect to train-test splits and seed variation (Section 4.3.5).
  • Integration intervals made consistent: All figures now share the same interval of integration.
  • Oracle router bug fix: In the original manuscript, the oracle had incorrect ground truth values. This has been fixed (see Table 1, p9).
  • Method clarifications: We clarify that the solve rate improvement is based on AUC improvement over budgets, and explain in Section 4.1 that we base our empirical results off pre-generated 64 attempts per target to be able to quantify the robustness of our results.

Q1. Does the quality estimator trained under one agent configuration transfer to another? Yes, we added a transfer experiment in Section 4.4 in the revised manuscript that shows the quality estimators transfers. In this experiment, we change all data-plane models (breakdown, formalization and prover models) and reduce the per-goal attempt limit from 64 to 16. Without retraining, our routing model reduces cost AUC by 15.2% and increases solve-rate AUC by 3.7% over the fixed-step baseline, compared with 20.0% and 4.8% after retraining on this new agent configuration. It retains most of the retrained gains, demonstrating strong generalization of the routing model.

Q2. Can you add a few more baselines?

Yes, we consider two additional baselines in Section 4.1 (p7), both of which are significantly outperformed by our learned router:

  • Per breakdown cost budget: In this baseline, we set a fixed cost budget in SFLOPs per breakdown and continue the breakdown until this budget is exhausted. This results in a slight improvement over the fixed-step baseline, but the learned 8B router still has a 22.7% cost reduction over this baseline.
  • Repeated error stopping: We consider a fixed-step baseline which terminates if rr out of the last nn generations had the same error. There is only minimal gain compared to the fixed-policy baseline. Sweeping values of nn and rr from 2 to 64, the optimal values on our training set are r=n=5r = n = 5, which achieve 3.5% cost reduction compared to the fixed-step baseline. Our baseline remains 25.8% better.

Q3. Why are no baselines from the cascading and routing literature included?

The decision we study differs from conventional model routing and cascading. Within a certain agentic framework, we decide whether further proof attempts on the current breakdown are worth their cost. This requires estimating the value of continuing an agent trajectory from its accumulated attempts and Lean feedback. Existing routing and cascading methods therefore do not provide a direct baseline without adapting their actions and estimators to this setting. Our fixed-step, per-breakdown budget, and repeated-error baselines instead compare alternatives within the same proving pipeline.

Q4. Are the results statistically significant?

Yes. To estimate the statistical significance of the results, we consider two sources of noise: (1) the choice of the 64 seeds in the simulations, and (2) train-test-split. To tackle this, we consider 16 train-test splits. For each train-test split, we retrain the router model on 16 sets of 64 seeds. For each of these 16x16 experiments, we calculate the cost AUC gain of our trained router compared to each of the three baselines (see Q2 of the general response). The confidence intervals of the experiment are listed in Table 3 (p10). The router significantly improves upon all three baselines.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.