- 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
-
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.
-
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:
-
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?
-
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?
-
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?
-
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.
-
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?
-
Which λ values produce the operating points in Fig. 3 and the point comparisons in Sec. 4.2, and how should a practitioner choose λ?
-
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
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.
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 k and λ favor any method?
No, the interpolation seems to be valid. By running our simulations for all 64 possible values of k, and 64 logarithmically spaced values for λ 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.
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 λ are listed in Appendix A (p16). We use 9 lambdas ranging from 2⋅10−8 to 4⋅10−6
Q8. How should one choose lambda in practice?
The scale of λ depends on the expected cost and quality of the routing model. For an initial estimate of λ, one can estimate the expected quality q^ and cost c^ of baselines on the validation set. A λ of roughly correct order of magnitude can then be chosen as λ=q^/c^, as then q^−λc^=0 is satisfied. This relies on the interpretation of λ 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:
Q10. Why are no baselines from the cascading and routing literature included?
Please see Q3 in the general response.