- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2(−1)
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper introduces CoCo-Prover, a framework for cost-efficient theorem proving in Lean. Unlike existing LLM-based provers that primarily optimize proof success rates, CoCo-Prover jointly considers proof success and inference cost. CoCo-Prover maintains a two-level proof graph consisting of a lemma-dependency DAG and an AND/OR hypergraph. Based on these graphs, a symbolic scheduler identifies available proof goals, and an LLM-based router selects appropriate proving strategies and reasoning budgets. The paper evaluates CoCo-Prover on five benchmarks using three backbone LLMs and achieves superior performance. The results demonstrate that CoCo-Prover achieves the highest or tied-highest solve rates across all evaluated settings while reducing costs compared to the baselines.
Critical strengths
-
Well-motivated and effective pipeline design. The paper concentrates on cost efficiency, which is an important but comparatively underexplored objective in LLM-based theorem proving. The paper proposes a coherent framework that combines two-level proof graphs with adaptive agent orchestration to address the challenges of cost-efficient theorem proving. The ablation studies further demonstrate the importance of adaptive routing and lemma planning in reducing costs. This design effectively addresses a meaningful limitation of existing LLM-based provers and represents a valuable contribution to program verification.
-
Strong evaluation results. CoCo-Prover achieves the highest or tied-highest solve rates across all evaluated settings while reducing costs compared to the baselines. The improvements are particularly substantial on repository-level verification tasks especially Vero. These results provide compelling evidence of the CoCo-Prover's effectiveness and practical value.
Critical weaknesses
W1: Insufficient and potentially unfair baseline comparisons. Several relevant baselines are missing, including Optimizing-LeanAgent and Goedel-Code-Prover, whose exclusion is not sufficiently justified. Repository-level comparisons are limited to general-purpose coding agents, which may be disadvantaged when handling numerous interdependent proof obligations. Furthermore, it is unclear whether baselines are restarted after early termination, potentially resulting in unequal budget utilization. Notably, the paper reports only 2.3% (1/43) for Codex with GPT-5.6-Terra on Vero, while the official Vero leaderboard reports 58.1% (25/43) for Codex with GPT-5.5 (xhigh). While these results are not directly comparable due to differences in model capabilities, reasoning effort, and computational budgets, the large discrepancy raises questions about the reliability and fairness of the evaluation.
W2: Insufficient experimental evidence supporting the core contributions. The experiments do not sufficiently isolate the benefits of adaptive routing from simpler heuristics or context management optimizations. Ablations are limited to 30 problems without repository-level evaluation or analysis of evolving routing rules. The lack of code implementations further weakens the reliability and reproducibility of the results.
Questions for authors
Q1: Baseline configuration and Vero results The paper reports a 2.3% (1/43) solve rate for Codex with GPT-5.6-Terra on Vero, whereas the official Vero leaderboard reports 58.1% (25/43) for Codex with GPT-5.5 (xhigh) in proof-only mode. Although these results are not directly comparable, could the authors explain this discrepancy, clarify the reasoning effort and configurations used for Codex, and justify that the baseline is appropriately configured and competitive?
Q2: Missing baselines and budget fairness. Why are relevant approaches such as Optimizing-LeanAgent and Goedel-Code-Prover excluded from the evaluation? Additionally, are baselines restarted if they terminate before exhausting their allocated budgets? Could the authors provide stronger evidence that the comparisons are fair under matched computational budgets?
Q3: Effectiveness of adaptive routing. Could the authors compare CoCo-Prover against simpler heuristic routing strategies and provide an ablation without evolving routing rules? Furthermore, since context management appears to contribute substantially to cost savings, how much of the improvement can be attributed specifically to adaptive routing rather than context optimization?
Q4: Reproducibility and reliability of experimental results. The paper does not release implementation code or sufficient experimental artifacts to verify the reported results. Providing the code and experimental data would substantially alleviate my concerns about reproducibility and reliability.
8 comments
Response to Reviewer gCct (contd.)
Q2. Missing baselines and matched-budget fairness
Why are relevant approaches such as Optimizing-LeanAgent and Goedel-Code-Prover excluded from the evaluation? Additionally, are baselines restarted if they terminate before exhausting their allocated budgets? Could the authors provide stronger evidence that the comparisons are fair under matched computational budgets?
Why Optimizing-LeanAgent and Goedel-Code-Prover are excluded. We discuss both works in Section 2 and Appendix C.1, and will expand their justification in the revision:
- Optimizing-LeanAgent (Rögnvaldsson et al., 2026): (i) Incompatible paradigm: It trains a supervised logistic classifier (choosing only binary continue vs. restart) on trajectories from 85 mathematical PutnamBench tasks specifically tailored to the fine-tuned prover
Goedel-Prover-V2. By contrast, CoCo-Prover is a training-free framework orchestrating public frontier API models across multi-goal graphs and heterogeneous specialists. (ii) Toolchain incompatibility: Its public repository (eth-sri/optimizing-lean-agents) is pinned to Lean 4.9.0, whereas our five program-verification benchmarks rely on newer Lean 4 releases andInit/StdAPIs that cannot be downgraded without altering benchmark definitions. - Goedel-Code-Prover (Li et al., 2026c): Its primary contribution is RL post-training of a specialized open-weights model, paired with a lightweight decompose-and-repair script whose effectiveness relies on multi-sample () generation from that fine-tuned checkpoint. Its reported function-level solve rates do not exceed recent frontier coding agents. Moreover, when we evaluated its public scaffold under our single-run () frontier-LLM protocol (Gemini-3.5-Flash, Appendix C.1), it failed within a 5 USD budget on tasks that both CoCo-Prover and coding agents solve for under 0.50 USD.
Workload-level expenditure and restarting after early termination. Under our original protocol, baselines were not externally restarted if they stopped before exhausting their budgets. In inspection, baseline runs ended unproved in three ways: (i) declining a hard or large problem early, (ii) introducing sorry/axioms or weakening definitions later rejected by our post-run proof checker, or (iii) stalling in repetitive repair loops. We first report total API expenditure across all attempted tasks including failed runs under the original protocol in Table R2, and then evaluate in-loop proof checking with automatic workspace resumption across all five benchmarks and three backbones for the Coding Agent, where early invalid exits were most frequent as shown in Table R3.
Table R2. Original evaluation protocol: proved tasks and total API expenditure (USD), including failed attempts, across all five benchmarks and three backbones. Each cell reports # proved tasks; total API cost.
| Backbone | Method | CLEVER (161) | VERINA (189) | AlgoVeri (77) | NTP4VC (300) | Vero (43) |
|---|---|---|---|---|---|---|
| GPT-5.6-Terra | Ax-Prover-Base | 144; $163.71 | 162; $260.15 | 63; $209.52 | — | — |
| GPT-5.6-Terra | Humanize | 157; $245.39 | 187; $359.40 | 66; $322.85 | — | — |
| GPT-5.6-Terra | Coding Agent | 148; $122.05 | 165; $160.25 | 52; $74.45 | 256; $245.96 | 1; $76.20 |
| GPT-5.6-Terra | CoCo-Prover | 161; $100.21 | 189; $245.43 | 69; $180.86 | 268; $354.98 | 23; $977.25 |
| Gemini-3.5-Flash | Ax-Prover-Base | 138; $699.04 | 137; $847.68 | 59; $457.74 | — | — |
| Gemini-3.5-Flash | Humanize | 157; $391.90 | 180; $768.90 | 62; $662.02 | — | — |
| Gemini-3.5-Flash | Coding Agent | 152; $415.17 | 166; $675.29 | 55; $290.97 | 239; $1,919.49 | 3; $1,099.28 |
| Gemini-3.5-Flash | CoCo-Prover | 161; $235.56 | 186; $578.46 | 62; $389.81 | 284; $827.27 | 26; $1,605.77 |
| DeepSeek-V4-Flash | Ax-Prover-Base | 119; $69.21 | 125; $137.81 | 45; $29.81 | — | — |
| DeepSeek-V4-Flash | Humanize | 148; $70.68 | 139; $130.23 | 51; $44.03 | — | — |
| DeepSeek-V4-Flash | Coding Agent | 127; $68.62 | 110; $65.76 | 61; $80.34 | 117; $72.29 | 0; $15.18 |
| DeepSeek-V4-Flash | CoCo-Prover | 156; $41.39 | 189; $80.29 | 72; $60.05 | 285; $215.35 | 6; $228.35 |
Even under the original protocol (Table R2), summed over the 427 function-level tasks, CoCo-Prover strictly dominates both Ax-Prover-Base and Humanize under every backbone, proving 9 to 128 more tasks while reducing total API spend by 16.9%–43.2%.
Response to Reviewer gCct (contd.)
Table R3. Matched-budget fairness with automatic resumption: Coding Agent with in-loop proof checking vs. CoCo-Prover. Each cell reports # proved tasks; total API cost (including failed runs).
| Benchmark | Backbone | Coding Agent + in-loop proof checking | CoCo-Prover |
|---|---|---|---|
| CLEVER (161) | GPT-5.6-Terra | 157; $169.47 | 161; $100.21 |
| CLEVER (161) | Gemini-3.5-Flash | 158; $455.93 | 161; $235.56 |
| CLEVER (161) | DeepSeek-V4-Flash | 150; $77.66 | 156; $41.39 |
| VERINA (189) | GPT-5.6-Terra | 175; $476.58 | 189; $245.43 |
| VERINA (189) | Gemini-3.5-Flash | 174; $953.38 | 186; $578.46 |
| VERINA (189) | DeepSeek-V4-Flash | 186; $136.52 | 189; $80.29 |
| AlgoVeri (77) | GPT-5.6-Terra | 61; $217.53 | 69; $180.86 |
| AlgoVeri (77) | Gemini-3.5-Flash | 59; $521.62 | 62; $389.81 |
| AlgoVeri (77) | DeepSeek-V4-Flash | 66; $107.22 | 72; $60.05 |
| NTP4VC (300) | GPT-5.6-Terra | 271; $608.45 | 268; $354.98 |
| NTP4VC (300) | Gemini-3.5-Flash | 263; $2,137.93 | 284; $827.27 |
| NTP4VC (300) | DeepSeek-V4-Flash | 284; $225.97 | 285; $215.35 |
| Vero (43) | GPT-5.6-Terra | 19; $1,313.96 | 23; $977.25 |
| Vero (43) | Gemini-3.5-Flash | 6; $2,302.42 | 26; $1,605.77 |
| Vero (43) | DeepSeek-V4-Flash | 10; $250.55 | 6; $228.35 |
Once early invalid exits are resumed under matched caps (Table R3), CoCo-Prover achieves strictly lower total API expenditure in all 15/15 benchmark–backbone settings and more proved tasks in 13/15 settings: summed across all the tasks, CoCo-Prover cuts total spend by 33.3% on GPT-5.6-Terra, 42.9% on Gemini-3.5-Flash, and 21.6% on DeepSeek-V4-Flash. In the only two solve-count exceptions (NTP4VC under GPT-5.6-Terra and Vero under DeepSeek-V4-Flash), the solve-count margin is narrow (only 3 and 4 tasks), while CoCo-Prover still spends 41.7% and 8.9% less.
Q3. Adaptive routing vs. heuristics, evolving rules, context optimization, and repository ablations
Could the authors compare CoCo-Prover against simpler heuristic routing strategies and provide an ablation without evolving routing rules? Furthermore, since context management appears to contribute substantially to cost savings, how much of the improvement can be attributed specifically to adaptive routing rather than context optimization?
1. Heuristic routing and frozen routing rules (Table R4). On the same 30-task subset used in Table 3 (Gemini-3.5-Flash), we added two internal controls holding the two-level proof graph, shared failure memory, execution history, goal clusters, specialist agents, and configuration space strictly fixed: (i) a handwritten deterministic heuristic router over surface goal structure and failure counts without LLM router calls, and (ii) an LLM router with frozen written rules ( throughout, disabling in Algorithm 1).
Table R4. Routing ablation on 30 function-level tasks (Gemini-3.5-Flash), with identical graph and context management across all variants. Cells report # proved tasks; total API cost (USD) including failures.
| Routing variant | CLEVER (10) | VERINA (10) | AlgoVeri (10) | Total (30) | Router API cost |
|---|---|---|---|---|---|
| Fixed specialist order (no LLM router) | 10; $41.02 | 9; $60.38 | 10; $53.80 | 29; $155.20 | $0 |
| Handwritten heuristic router (no LLM router) | 8; $76.46 | 8; $89.10 | 6; $96.47 | 22; $262.03 | $0 |
| LLM router, frozen written rules () | 10; $24.98 | 10; $50.03 | 10; $44.18 | 30; $119.19 | $9.1 |
| LLM router, evolving written rules (CoCo-Prover) | 10; $28.64 | 10; $43.49 | 10; $38.82 | 30; $110.94 | $13.7 |
- Adaptive LLM routing vs. non-LLM heuristics: Both LLM-router variants prove all the tasks while cutting total spend by up to 28.5% against Fixed Order and 57.7% against the Handwritten Heuristic, whose syntactic rules frequently misjudge semantic proof difficulty and misallocate budgets.
- Frozen vs. evolving rules: Evolving leaves solve count unchanged and reduces total spend by a modest 6.9%. Because the frozen-rule router still observes shared failure memory, execution history, Lean diagnostics, and graph context in , it adapts implicitly in context at each step; thus, evidence-grounded agentic routing drives the primary gain, with explicit rule evolution providing a secondary refinement.
Response to Reviewer gCct
We thank the reviewer for the constructive evaluation and encouraging feedback. We appreciate your recognition of the importance of cost efficiency in LLM-based theorem proving, the coherence of combining two-level proof graphs with adaptive agent orchestration, and our strong empirical gains.
Below, we address each of your questions with new controlled experiments and open-sourced artifacts:
W1,Q1).W1,Q2).W2,Q3).W2,Q4).Q1. Baseline configuration and Vero results
Codex configuration. Across all benchmarks, we ran the official
@openai/codexCLI (v0.146.0, Table 6) paired with GPT-5.6-Terra at high reasoning effort.Why the original run solved 1/43 (2.3%) vs. the leaderboard. Two factors account for the gap:
sorryholes / altered declarations that were rejected by our post-run Lean proof checker, thereby spending only $76.20 in total across all 43 tasks, which is well below its 60 USD per-task cap.Closing the gap with in-loop proof checking. To ensure competitive budget utilization, we augmented all coding-agent baselines with in-loop proof checking: whenever the coding agent reports completion, an in-loop Lean checker validates every target theorem against our exact mechanical review criteria (no unresolved goals or
sorry, unmodified target statements, and no added axioms). If validation fails, Lean diagnostics are returned and the agent resumes from its existing workspace until all obligations pass or the $60 / 8h cap is reached.Table R1. Vero repository-level (43 tasks) and obligation-level (2,705 target theorems) comparison with in-loop proof checking.
Preventing premature exits lifts Codex (GPT-5.6-Terra) from 1/43 to 19/43 (44.2%) repositories and 81.6% of individual obligations, confirming both that our Codex configuration is competitive and that early termination explained the original 2.3% figure. Crucially, CoCo-Prover still outperforms this strengthened baseline on GPT-5.6-Terra and Gemini-3.5-Flash because its persistent dependency graph, the adaptive agentic routing and selective rollback close tightly coupled tail obligations without monolithic transcript growth.