acceptodds
Under review as a conference paper at ICLR 2027

LEVER: Adaptive Cost-Aware Proof Search Over AND/OR Graphs

Abstract

Mathematicians value proofs for more than correctness: among correct proofs, simplicity, purity and the computational cost of finding them vary widely. Yet LLM-powered theorem provers largely search for any correct proof, and improve its quality only after it is found. We propose LEVER, a proof search algorithm that makes the objective over correct proofs programmable and optimizes it during search. LEVER scores partial proofs over an AND/OR proof graph, combining realized objective values with predictions for open subgoals, so the objective guides search before a proof is complete. The same mechanism optimizes computational cost, proof length, topical impurity, and even their weighted combinations, while the Lean kernel enforces correctness. On PutnamBench in Lean 4, under matched budgets, LEVER costs 34% less than a strong single-conversation agent while raising the solve rate from 80% to 96%. On reducing topical impurity, i.e., how far a proof strays from its theorem's subject, it improves over post-hoc refactoring (42% reduction against 33%) at two-thirds of the cost and more reliably; on proof length, the metric refactoring is built for, it approaches refactoring. Varying the objective's weights traces a quality-cost trade-off curve, so the user can choose how much a better proof is worth. Overall, LEVER is a performant, cost-efficient and tunable proof search algorithm for navigating the space of correct proofs.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
neural theorem proving, proof search, formal reasoning, AI for math, neurosymbolic AI

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_kRGbOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper introduces LEVER, an LLM-based theorem-proving system that guides proof construction using computational cost and user-selected proof metrics. It represents alternative proof decompositions as an AND/OR graph, combines measured contributions with estimates for unfinished subgoals, and can revisit goals to seek better decompositions. Completed proofs are checked in Lean. On 80 selected PutnamBench problems, LEVER reports a 96.3% solve rate versus 80.0% for a single-conversation baseline, with average cost falling from $1.44 to $0.95 under standardized cache pricing. On 20 problems, it also explores proof-length and topical-impurity objectives. The results demonstrate improvements in these measured objectives, although the comparison supporting superior impurity reduction over refactoring needs clarification. Appendix D establishes the additive backup equations’ exactness under its stated assumptions, rather than an optimality guarantee for the implemented adaptive search.

Critical strengths
  1. I liked the explicit treatment of proof characteristics during construction. Sections 3–4 describe a concrete mechanism for balancing unfinished work against measured proof properties, and Table 2 shows that changing the objective produces meaningfully different outcomes. This makes the system useful beyond simply finding another correct proof.

  2. I found the reported cost and solve-rate improvements substantial within the evaluated setting. Table 1 shows improvements on both measures, and Appendix C.3 reports that the advantage remains under actual cache behavior: 96.3% versus 86.3% solved, at $0.90 versus $1.07 per problem. Including planning and value-function calls in the reported cost strengthens this evidence.

Critical weaknesses
  1. I would appreciate clarification on how the refactoring baseline handles rewrites that worsen the original proof. Section 5.2 gives an example where impurity increases from 29 to 132, although the original valid proof could be retained. If this outcome contributes to the reported average, keeping the better proof could substantially change the comparison. LEVER’s lower cost would remain a strength, but I am currently unsure whether its advantage in impurity reduction would hold under this adjustment.

  2. I found the overall efficiency gains encouraging, but I had some difficulty determining how much comes specifically from adaptive search. Section 5.1 compares systems that also differ in planning, decomposition, and context management, and the paper notes that early rejection of expensive decompositions is rare. A focused comparison retaining these components while disabling adaptive redraws and prior updates would help me assess the contribution of the proposed search mechanism. I would reconsider this concern if such evidence shows a meaningful benefit from adaptation.

Questions for authors
  1. I would appreciate clarification on whether the impurity increase from 29 to 132 is included in Figure 5’s average. Could you report the reduction and variability when the refactoring baseline retains whichever proof has lower impurity, with the computation charges unchanged? This would help me assess whether the reported quality advantage remains. Clarification / Additional evidence/analysis.

  2. I would like to understand how LEVER performs when adaptive redraws and prior updates are disabled, while keeping the planner, local contexts, tools, and direct-proof routing unchanged. Is there evidence showing how these adaptive components affect solve rate and cost? Additional evidence/analysis.

These concerns are provisional, and I would be open to revising my recommendation based on further clarification or evidence addressing them.

2 comments
AuthorsOpenReview ↗

Response to Reviewer kRGb

N.B. a mix of USD and $ notation is used below due to a LaTeX rendering bug.

W1 / Q1. Clarification on how the refactoring baseline handles rewrites that worsen the original proof. Section 5.2 gives an example where impurity increases from 29 to 132 … Could you report the reduction and variability when the refactoring baseline retains whichever proof has lower impurity, with the computation charges unchanged?

Yes, putnam_2007_a2 is included in the reported average. When the refactoring baseline keeps whichever of NearAI's original proof and the refactored version is purer, with charges unchanged, the mean impurity reduction rises from 33% (SD 101) to 53% (SD 38), at USD 2.88 per problem. LEVER at λ = 0.1 reduces impurity by 42% (SD 32) at $1.85. LEVER's advantage is cost, about two-thirds of the refactoring pipeline's. We will report both versions of the baseline and correct the claims in the relevant sections in the paper.

The putnam_2007_a2 rewrite replaced one linear-algebra step (a linear map scales area by its determinant) with a direct computation by shears and scalings. It traded NearAI's 11 linear-algebra references for 131 references to measurability, which lies outside the subjects read off the statement. Whether that trade counts as a loss depends on whether measurability is part of this theorem's subject, and in this case it was not per our implementation (see "Topical impurity" in the general response).

W2 / Q2. Difficulty determining how much comes specifically from adaptive search … A focused comparison retaining these components while disabling adaptive redraws and prior updates … while keeping the planner, local contexts, tools, and direct-proof routing unchanged. Is there evidence showing how these adaptive components affect solve rate and cost?

With adaptation disabled, cost and solve rate barely move: 96.3% at USD 0.95 against 95.0% at $0.97, a cost ratio of 0.98. Adaptive redraws were 8% of LEVER's attempts, and the routing those prices drive is cost-neutral on its own.

We take your point: on this benchmark, adaptation as implemented does not show a meaningful benefit. The general response explains why with measurements. Alternatives differ in cost on about a third of problems. In a pre-registered test on 10 harder problems, the value function's choice among three root decompositions was 12% cheaper than a random choice, but the two extra draws cost more than that, so drawing three and choosing did not beat drawing one. LEVER's search commits to its first root and redraws only when the value function flags, so it rarely gets to choose. We will revise the paper to state this and report these measurements. The natural next step is to draw an alternative only when its expected saving exceeds its cost.

AuthorsOpenReview ↗

Discussion reminder

Dear reviewer,

Thank you again for your detailed review. As the discussion period draws to a close, we would be happy to discuss any remaining questions. In addition to our responses above, our follow-up to Reviewer Yvqh isolates the effect of objective-guided search: with adaptive redraws disabled, LEVER's proofs are no purer than the baseline's, while at λ = 0.1 they are purer on 19 of the 20 problems. If our responses have addressed your concerns, we would appreciate it if you could re-evaluate your assessment and update your score accordingly.

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

This paper proposes LEVER, an adaptive cost-aware proof search algorithm for LLM-based theorem proving. The main idea is to represent partial proofs using AND/OR graphs and guide the search using value functions that estimate the remaining cost of completing open subgoals. The novelty lies primarily on optimizing different objectives during the proof construction, including computational cost, proof length, and topical impurity, rather than optimize it post-hoc. The authors evaluate LEVER on PutnamBench using Lean 4 and DeepSeek-V4-Flash, with the main comparison with single-conversation theorem-proving agent, achieving higher solve rates while reducing computational cost.

Critical strengths

I appreciate the motivation to optimize proof quality and computational efficiency during theorem proving, rather than simply searching for any correct proof. The empirical results also seem promising, largely improving the solve rate while optimizing for computational efficiency. The methodology also makes sense with the formalization of AND/OR graph search, evaluation estimations, and I appreciate the author's finding the adaptive decompositions, which I believe will motivate more work in this line.

Critical weaknesses

There are several critical weaknesses I have in mind. The most important problem is the lack of systematic component ablations. The author compares to the single-conversation baseline, yet LEVER introduces several changes all at once, including proof decompositions, localized contexts, planning, value-guided search, and so on. The author also notes that the computational efficiency actually comes from the reduced context length rather than a carefully designed value-guided search ("The savings come from how LEVER manages context. ", line 377). I think a more systematic ablation study would substantially strengthen the paper, particularly including the variants such as 1. without value-guided search but with heuristics, like BFS, DFS, random subgoal selection, while keeping the remainder the same, 2. without adaptive redrawing, 3. without adative value updates, 4, without llm-based value evaluation, and finally 5, without the initial planner. I believe a systematic breakdown of the proposed framework will not only make the gain from LEVER more convincing, but also can reveal interesting observations. This is my major concern.

Additionally, I am not entirely convinced by the design of topical impurity metrics. The proposed metric relies on Mathlib namespaces and directory structures to identify references outside the theorem's subject, but by no mean these reflect meaningful mathematical distinctions. To start with, the metric may be sensitive to how mathematical results are organized within Mathlib, rather than reflecting intrinsic properties of the proofs themselves. While the authors acknowledge some of these limitations, I believe additional validation is needed, potentially through human assessment of proof quality.

Finally, the submission might benefit from additional evaluations over different datasets, and in particular different langauge models. The model part is particularly important since one of the optimization targets are LLM cost, which has different rates across and might affect different search behaviour.

Questions for authors

Can the authors provide component ablations, particularly comparisons against simpler decomposition-based search strategies with identical agent infrastructure and context management? (Most important!)

Could the authors provide additional validation, such as human evaluation or qualitative comparisons of proofs with different impurity scores, in order to justify topical impurity?

Does LEVER achieve similar improvements with other language models?

3 comments
AuthorsOpenReview ↗

Response to Reviewer Yvqh

W1 / Q1. The lack of systematic component ablations … 1. without value-guided search but with heuristics, like BFS, DFS, random subgoal selection, while keeping the remainder the same, 2. without adaptive redrawing, 3. without adaptive value updates, 4. without llm-based value evaluation, and finally 5. without the initial planner. … Can the authors provide component ablations, particularly comparisons against simpler decomposition-based search strategies with identical agent infrastructure and context management?

See the general response. LEVER-U is the comparison with identical infrastructure and context management. It removes LLM value evaluation (item 4) and, in practice, adaptive redrawing (item 2); it ties LEVER on cost.

Item 1. LEVER expands open goals in parallel, so it does not depend on an expansion order the way BFS or DFS does. The value function's job is choosing among alternatives: which decomposition to pursue, and whether to redraw. LEVER-U removes exactly that, so it is the relevant ablation here.

Item 3. LEVER-U keeps the update rule, but its uniform prior never outbids a live decomposition, so updates cannot change a decision.

Item 5. We did not ablate the planner, because it is part of what makes local contexts work: each subgoal is proved in its own context, and the plan carries the global argument into every one of them (see our response to zRXp W1).

Beyond the component ablation, the general response measures the conditions under which value guidance can matter. On a random sample of our 80 evaluation problems, about a third have alternatives that differ in cost. In a pre-registered test on 10 harder problems, the value function chose among alternatives better than chance, but not by enough to pay for drawing them.

W2 / Q2. Not convinced by the design of topical impurity metrics … relies on Mathlib namespaces and directory structures … may be sensitive to how mathematical results are organized within Mathlib … Could the authors provide additional validation, such as human evaluation or qualitative comparisons of proofs with different impurity scores?

See "Topical impurity" in the general response. It gives the qualitative comparison the reviewer asks for, and measures the sensitivity to Mathlib's organization that the reviewer anticipates.

W3 / Q3. Additional evaluations over different datasets, and in particular different language models … one of the optimization targets are LLM cost, which has different rates across and might affect different search behaviour. Does LEVER achieve similar improvements with other language models?

All costs use one fixed price table and a fixed 90% cache rate, so differences between providers' rates do not enter any comparison. A different model changes the search through the model's own behavior, and that is what a second-model run would test. We did not run a second model in the rebuttal period. LEVER's value function and prior are calibrated to the model's costs, so a second model needs its own calibration; we will state this as a limitation.

Thank you for the detailed rebuttal and additional experiments. I appreciate the LEVER-U ablation, which clarifies that most efficiency gains come from decomposition and local context management rather than adaptive value-guided search. One follow-up question: Under the topical-impurity objective, how does LEVER compare with a variant that disables adaptive value-guided redraws while retaining the same decomposition and local contexts?

Thank you for the follow-up. We measured this on the same 20 problems as Figure 5.

A variant with adaptive redraws disabled keeps the first decomposition it draws for each goal, and draws another only when that one fails. An impurity objective then has no decision to act on: in LEVER, impurity changes the outcome only by making the search set aside a live decomposition, whose estimated cost includes λ times its impurity, and draw a new one. LEVER-U (general response) is such a variant: the same planner, decomposition and local contexts, with 0 adaptive redraws in its 178 attempts on these problems.

VariantAdaptive redraws (of attempts)Impurity reductionCost per problem
LEVER-U (adaptive redraws disabled)0 of 178 (0%)−17.1%$0.79
LEVER, λ = 08 of 82 (10%)−0.6%$0.83
LEVER, λ = 0.0126 of 150 (17%)15.0%$0.88
LEVER, λ = 0.1152 of 403 (38%)41.5%$1.85

Impurity reduction is measured against NearAI's proof of the same problem, as in Figure 5. With adaptive redraws disabled, LEVER's proofs are no purer than NearAI's. At λ = 0.1, LEVER's proofs are purer than LEVER-U's on 19 of the 20 problems. The impurity reduction therefore comes from the adaptive redraws, and it costs more search: USD 1.85 per problem against $0.79 for LEVER-U. All numbers are single runs.

If any remaining points need further clarification, please let us know, we would be glad to address them right away. If everything is resolved, we would sincerely appreciate it if you would consider updating your evaluation and increasing your score. Thank you!

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

LEVER is a proof search algorithm that keeps correctness as a hard constraint, checked by the Lean kernel, and optimizes a user-specified objective over correct proofs during search. Partial proofs form an AND/OR graph and are scored by the realized cost of solved parts plus value-function predictions for open subgoals. A prior node on each goal allows the goal to be redrawn, and the prior is updated from realized draws. The same mechanism optimizes compute cost, proof length, topical impurity, or weighted sums of them. On 80 PutnamBench problems with DeepSeek-V4-Flash and a $3 budget, LEVER solves 96.3% of problems versus 80.0% for the NearAI agent, at 34% lower cost. On 20 problems, it reduces impurity by 42% versus 33% for post-hoc refactoring, and length by 21% versus 31%.

Critical strengths
  1. The problem framing is novel. Searching among correct proofs under a programmable objective is a clear change of perspective that unifies cost and quality optimization, and the weight λ gives users an explicit quality–cost trade-off.
  2. The algorithm design is sound. Prior nodes that allow redraws under a stochastic expander, a conjugate update that learns from realized spend, and the separation of sunk from remaining cost are natural extensions of AO*.
  3. In the authors' controlled comparison (same model, Lean version and prices), LEVER lowers cost while solving more problems.
Critical weaknesses
  1. There are no ablations, so the effect of the value function and of objective-guided search is unclear. The paper attributes the savings to local contexts (§5.1) and notes that value-based rejections are rare, while LEVER also adds a planner, a depth cap, routing of cheap goals to direct proofs, and parallel expansion. Without variants such as a constant value function, no redraws, or no planner, the gains cannot be separated from decomposition with local contexts, which HILBERT and Goedel-Architect already offer.
  2. The value function is weak, and the paper barely discusses it. Per Table 4 and Appendix C.2, only 34% of comp predictions fall in the correct bin, predictions are low by a factor of 1.53 on average, and the prior weighs only n ≈ 0.33 draws. Impurity has no real predictor: every open goal is scored at a constant 4, with n = 0.05. The prior therefore carries little information and the search relies mainly on realized draws, which does not match the claim that LLM-based value functions steer the search.
  3. Several key settings are heuristics without justification or sensitivity analysis. Examples include the 0.2 multiplier on length estimates and the constant 4 for impurity, which replaced 0 after the authors found that 0 made search unstable. These appear tuned to make the system work, and the paper does not report how sensitive the results are to them.
  4. The validity of topical impurity is not established. It is defined entirely by Mathlib namespaces and directories, and the infrastructure set is the authors' judgment on a single pilot corpus (Appendix B). No human evaluation shows that it agrees with mathematicians' notion of purity, so the meaning of a 42% reduction is unclear.
Questions for authors
  1. The evaluation uses only 100 PutnamBench problems of moderate difficulty (ranks 51–150 by NearAI's cost, 80 for evaluation). Does LEVER keep its low cost and high solve rate on harder Putnam problems or on other datasets? The abstract should also state that the 96% figure refers to this subset.
  2. Refactoring reduced both length and impurity of NearAI's proofs. Does it also improve LEVER's proofs? The paper's own argument (§1) that length is amenable to local compression while purity depends on the chosen argument suggests the two are complementary, for example running LEVER for impurity and then refactoring for length.
  3. The paper lacks failure analysis. Could the authors report how many subgoals were reported false and how many of these informal claims were wrong, how much budget was spent on abandoned subgraphs, and why the three unsolved problems failed?
4 comments
AuthorsOpenReview ↗

Response to Reviewer zRXp

N.B. a mix of USD and $ notation is used below due to a LaTeX rendering bug.

W1. There are no ablations, so the effect of the value function and of objective-guided search is unclear. The paper attributes the savings to local contexts (§5.1) and notes that value-based rejections are rare, while LEVER also adds a planner, a depth cap, routing of cheap goals to direct proofs, and parallel expansion. Without variants such as a constant value function, no redraws, or no planner, the gains cannot be separated from decomposition with local contexts, which HILBERT and Goedel-Architect already offer.

See the general response. The constant value function is the LEVER-U ablation, which in practice also means no chosen redraws and no routing. It ties LEVER on cost as shown above.

We agree the cost savings come from decomposition with local contexts. We will position the contribution accordingly. The quality-objective framework is what goes beyond HILBERT and Goedel-Architect.

On routing in particular: 16 roots that LEVER sent to a direct proof cost USD 0.53 on average, against $0.57 when LEVER-U decomposed the same roots. Routing is cost-neutral here.

We did not ablate the planner, because it is part of what makes local contexts work. Each subgoal is proved in its own context and never sees the whole proof. The plan, written once in informal mathematics, carries the global argument into every one of those contexts, and keeps informal reasoning separate from Lean development. We will state this design rationale in the revision.

W2. The value function is weak, and the paper barely discusses it. Per Table 4 and Appendix C.2, only 34% of comp predictions fall in the correct bin, predictions are low by a factor of 1.53 on average, and the prior weighs only n ≈ 0.33 draws. Impurity has no real predictor: every open goal is scored at a constant 4, with n = 0.05. The prior therefore carries little information and the search relies mainly on realized draws,which does not match the claim that LLM-based value functions steer the search.

We agree the predictor is noisy, but we read its role differently. The prior is what lets LEVER decide before any draw exists: which arm to try at a goal, and whether a live decomposition is worth replacing. Adaptive redraws and routing both run on it. The small weight, n ≈ 0.33, is the conjugate update calibrated to that noise. One realized draw counts about three times as much as the quote, which is the statistically right response to a predictor with this spread.

Bin accuracy also understates the predictor. Every decision compares two prices, so what matters is ranking, not absolute values. A predictor biased low by 1.53× makes the same choices as an unbiased one if it orders alternatives correctly. On 10 harder problems chosen in advance, its choice among three roots was 12% cheaper than a random choice, capturing about 40% of what a perfect choice would.

On cost, the ablation is clear: removing the LLM predictor leaves cost unchanged on this benchmark. We will revise the claim accordingly. The paper will say the search is driven mainly by realized measurements, with the value function as a weak prior. It will report rank correlation next to bin accuracy, and state conditions [A]–[C] under which a better predictor matters. For impurity, a constant estimate suffices: what the search needs is a price for unexplored goals, not a learned one.

W3. Several key settings are heuristics without justification or sensitivity analysis. Examples include the 0.2 multiplier on length estimates and the constant 4 for impurity, which replaced 0 after the authors found that 0 made search unstable. These appear tuned to make the system work, and the paper does not report how sensitive the results are to them.

The impurity constant is the 25th percentile of impurity over calibration goals (§4); the 0.2 length factor is a deliberate underestimate, chosen by hand. The impurity constant prices an open goal before anything about it is known. At 0, an open goal looks free, so the search prefers splits with more unsolved subgoals and never settles. That is the structural reason objective-driven search needs some estimate for open goals.

To measure sensitivity to the impurity constant, we re-ran LEVER at λ = 0.1 with the constant at 2, 4 and 8, on the 5 problems drawn for Q2, holding the plan fixed. Impurity fell by 54%, 62% and 45% at constants 2, 4 and 8, at USD 1.85, USD 1.52 and $1.66 per problem, against 14% without the impurity objective (λ = 0) on the same problems. The differences between constants are within run-to-run noise: two runs at constant 4 on the same problem reduced impurity by 33% and 69%. Across a fourfold range, the result does not hinge on the constant's value; what matters is that it is nonzero, so that open goals are not free.

AuthorsOpenReview ↗

Response to Reviewer zRXp (contd.)

N.B. a mix of USD and $ notation is used below due to a LaTeX rendering bug.

W4. The validity of topical impurity is not established. It is defined entirely by Mathlib namespaces and directories, and the infrastructure set is the authors' judgment on a single pilot corpus (Appendix B). No human evaluation shows that it agrees with mathematicians' notion of purity, so the meaning of a 42% reduction is unclear.

See "Topical impurity" in the general response. The 42% reduction counts every reference outside the subjects read off each statement, whether or not it reflects a change of argument. In the revision we will make this dependence explicit.

Q1. The evaluation uses only 100 PutnamBench problems of moderate difficulty (ranks 51–150 by NearAI's cost, 80 for evaluation). Does LEVER keep its low cost and high solve rate on harder Putnam problems or on other datasets? The abstract should also state that the 96% figure refers to this subset.

We will state in the abstract that the 96.3% is on an 80-problem subset of PutnamBench, and give the selection rule.

We did not evaluate problems outside this subset, for lack of time and compute during the rebuttal period. Harder problems need larger budgets: on the 50 problems NearAI's baseline found most expensive, its cheapest solving attempt costs a median of USD 0.62 and up to $5.24, above our USD 3 budget, and its attempts on a single problem took up to five and a half days in total.

Q2. Refactoring reduced both length and impurity of NearAI's proofs. Does it also improve LEVER's proofs? The paper's own argument (§1) that length is amenable to local compression while purity depends on the chosen argument suggests the two are complementary, for example running LEVER for impurity and then refactoring for length.

We ran this check on 5 of the 20 problems, drawn at random; in the interest of time we did not run all 20. The refactoring pass shortened LEVER's impurity-optimized proofs on 2 of the 5, by 25% and 23%, and left impurity essentially unchanged (47 → 46 and 5 → 6). Where it succeeds, the two combine as the reviewer suggests: the search fixes the argument, and refactoring compresses it without making it less pure. On the other 3, the pass exhausted its budget without producing a valid shorter proof, so LEVER's proof stands. Overall, composing search and refactoring is feasible, but their budgets add up, as one would expect: under the paper's accounting, the cost per problem rises from USD 1.69 for LEVER alone to $4.12 with the refactoring pass, which hit the USD 4.5 cap on the three problems where it failed.

Q3. The paper lacks failure analysis. Could the authors report how many subgoals were reported false and how many of these informal claims were wrong, how much budget was spent on abandoned subgraphs, and why the three unsolved problems failed?

Yes. On the 80 evaluation problems:

  • Subgoals the value function marked false: 14. None was attempted, because a false quote rules a decomposition out. We read all 14: 12 are genuinely false, nearly all lemmas missing a hypothesis, and 2 (both Fubini-type statements) are unclear.
  • Subgoals the prover disproved during search: 18 of the 342 subgoals LEVER created (5%), against 67 for LEVER-U. A disproof is currently the prover's informal claim, with a reason, not a formal proof of the negation; it abandons the goal. Given how rare disproofs are, their effect on the search is small. Requiring formal disproofs is left for future work.
  • Spend on abandoned subgraphs: USD 9.9 of LEVER's total, against $18.6 for LEVER-U. That is not part of the delivered proof.
  • The three unsolved problems:
    • 1982_a6: the prover wrongly disproved the root after $0.18, which ends the search. NearAI solved it, so the statement is provable.
    • 1962_a2 and 2014_b4: the $3 budget ran out after 13 and 7 iterations. The decompositions repeatedly contained false lemmas: 8 and 2 subgoals were disproved.

We will add this analysis as an appendix.

AuthorsOpenReview ↗

Discussion reminder

Dear reviewer,

Thank you again for your detailed review. As the discussion period draws to a close, we would be happy to discuss any remaining questions. In addition to our responses above, our follow-up to Reviewer Yvqh isolates the effect of objective-guided search: with adaptive redraws disabled, LEVER's proofs are no purer than the baseline's, while at λ = 0.1 they are purer on 19 of the 20 problems. If our responses have addressed your concerns, we would appreciate it if you could re-evaluate your assessment and update your score accordingly.

I thank the authors for their response, which addresses some of my concerns. However, I still doubt that the value function is valid, that the impurity measure has practical meaning, and that the method generalizes to a broader range of formalization problems. I will therefore keep my score.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General Response

We thank all the reviewers for their insightful remarks. There are two primary concerns that overlap among reviewers, which we attempt to address here. The first is related to the role of the value function in steering search and the second touches upon the validity of the topical impurity metric.

Value function ablations

All reviewers primarily ask the same central question: how much of LEVER's gain comes from the value function and adaptive search, as opposed to decomposition with local contexts? We have run that ablation, and we report it here.

Ablation. LEVER-U is LEVER with the LLM value function replaced by a uniform one. Every split is priced the same, so the search takes the first decomposition it draws and redraws only when one fails. Planner, local contexts, tools, depth cap and parallel expansion are unchanged. LEVER-U also has no direct-proof arm, since a uniform price cannot choose between arms.

Table 1.

NearAI (baseline)LEVERLEVER-U (no LLM value function)
Adaptive redraws–30 of 376 attempts (8%), on 16 of 80 problems (20%)0
Solved80.0%96.3%95.0%
Mean cost per problem$1.44$0.95$0.97

The cost savings over the single-conversation baseline therefore come from decomposition with local contexts, as §5.1 states. We will revise the paper to say so plainly.

When can a value function save cost? We hypothesize that this happens when all these conditions hold:

  • [A] Drawing an extra alternative costs less than the money it saves;
  • [B] Alternatives really differ in cost, by more than the noise of solving any single one;
  • [C] The value function can tell which alternative is cheaper.

To test these conditions, we took the 10 problems from our 80 evaluation set that NearAI's baseline found most expensive. For each problem, we drew three root decompositions (AND nodes), each from an independently generated plan, and priced them with the paper's value function. We then froze each root and solved each root twice, with the uniform value function, the paper's $3 budget and its 90% cache rule, so the measured cost reflects the root itself. Before solving anything, we fixed the comparison below. Each row changes just one thing:

Table 2.

Total cost, 10 problemsWhat changed
Draw 1 root and solve it (LEVER-U)$15.92
Draw 3, pick one at random (all three draws paid)$18.62+$2.70: the two extra draws
Draw 3, the value function picks$16.38−$2.24: the value function's choice
Draw 3, perfect pick$13.13−$3.25: what a perfect value function would add

The two extra draws cost $2.70 over the 10 problems. With the same three roots, the value function's choice is 12% cheaper than a random one, and cheaper on 7 of the 10 problems. It captures about 40% of what a perfect choice would ([C], in part). On these problems, that saving does not cover the extra draws: drawing three and choosing costs 3% more than drawing one. The binding condition is [A]. A perfect choice would save 18% over a single draw, so the room exists ([B]). A cheaper way to draw alternatives, or a sharper value function, would turn it into a net saving.

On a separate random sample of 10 problems, five independent root decompositions per problem take materially different routes on about a third of the problems; on the rest, the roots are interchangeable. Where they differ, the drawn root largely decides the cost: re-solving three such problems from frozen roots, 83–99% of the variance in log cost lies between roots rather than between repeated solves.

Overall these measurements explain the tie in the ablation from Table 1 above:

  • Alternatives differ materially on only about a third of problems ([B]).
  • The value function's choice among them is informative but imperfect ([C]).
  • LEVER, as submitted in the paper, commits to its first root decomposition and redraws only when that root looks bad, so it rarely draws alternatives at all. When it does, as in the test above, the extra draws cost more than the choice saves ([A]).

We will add this analysis to the paper and state the conditions under which value guidance pays off. The natural extension is to draw another alternative only when its expected saving, the predicted spread times the value function's reliability, exceeds the cost of a draw. We leave it to future work.

AuthorsOpenReview ↗

General Response (contd.)

What LEVER contributes. To optimize any objective during search, you have to score incomplete proofs. That needs an estimate for every open goal. Without one, unfinished work looks free and the search does not settle; we saw exactly this with impurity priced at 0. LEVER makes that estimate pluggable, from a constant to an LLM predictor. For quality objectives, the λ sweep shows the objective changing the outcome. The prover's first prompt is the same at λ = 0 and λ > 0, so the gain comes from the search.

As a concrete example, the machinery that rarely fires for computational cost does the work for impurity. A decomposition's cost lies mostly in subgoals not yet solved, so comparing alternatives requires prediction. Its impurity is largely visible the moment it is drawn, in the references of its own Lean file. Accordingly, redraws by choice rise with λ: from 17% of attempts at λ = 0.01 to 38% at λ = 0.1, on all 20 problems (the two runs differ only in λ). At λ = 0.1, the decompositions the search set aside by choice carried 12.8 out-of-subject references when drawn, against 5.4 for those it kept, with the same number of open subgoals.

Topical impurity

Reviewers zRXp and Yvqh ask whether the topical impurity metric tracks a mathematician's notion of purity, or only how Mathlib is organized. We give a qualitative comparison, and measure the metric's noise.

On putnam_2016_b5, both of LEVER's proofs reduce the problem to showing that mlog⁡2−nlog⁡3m \log 2 - n \log 3 comes arbitrarily close to any given value. At λ = 0, LEVER proves this with topology: the multiples of an irrational rotation are dense in the circle group (AddCircle.denseRange_zsmul_coe_iff, Dense.inter_open_nonempty). At λ = 0.1, it uses Dirichlet's approximation theorem, a pigeonhole argument, and makes no topology references. As a result, impurity falls from 42 to 5. This is the classical contrast between a topological and an elementary proof of the same fact, and the metric's references identify it.

The count depends on which areas of Mathlib are taken to be the theorem's subject. Our metric reads them off the constants in the statement and counts every reference outside them. Whether a given area belongs to the subject is a choice for whoever defines the objective. In the example above, 13 of the 37 references in the gap are topology. The other 24 are casts and finite sums, which also lie outside the subjects read off this statement. On putnam_1967_a4, two proofs with the same argument differ by 62 references, nearly all to measurability, which lies outside that statement's subjects too. With a wider subject, these differences would shrink. Further, whether a certain violation is indeed undesirable is ultimately the mathematician's call, the study of which is outside scope here. Our goal here is to demonstrate that LEVER as a framework is able to optimize an objective that can be read off the AND/OR graph. While we have attempted to emphasize this in the paper already, we will make this clearer in the revision.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.