acceptodds
Under review as a conference paper at ICLR 2027

Cost-Efficient Theorem Proving via Agent Orchestration in Program Verification

Abstract

Program verification establishes software correctness through machine-checkable proofs constructed in theorem provers. It’s a guarantee especially valuable for code generated by large language models (LLMs), which is fluent but carries no assurance of correctness. Almost all existing provers, however, pursue pass rates alone at whatever sampling or search budget it takes, and overlook the success-vs-cost frontier; yet real software often carries hundreds of interdependent proof obligations, so what matters at scale is not whether one theorem can be proved, but how many can be proved economically. We introduce CoCo-Prover, which formalizes cost-efficient program proving as metalevel decision-making under cost, grounded on two-level proof graphs: an AND/OR proof hypergraph within each declaration is joined to a lemma-dependency graph across declarations; and at each step, it answers two questions: which open goals to select, and which actions to purchase on these goals. Selection stays symbolic as a topological pass over the proof graphs. Action choice is agent orchestration via metalevel decision-making: an agentic router treats every bounded specialist invocation as a separately priced, best-effort computation, matching heterogeneous specialist agents together with configurations, under evolved routing rules as evidence accumulates. On five program verification benchmarks in Lean 4, including function-level CLEVER, VERINA, and AlgoVeri, and repository-level NTP4VC and Vero, we show that CoCo-Prover achieves a better success-vs-cost frontier than baselines including frontier coding agents and state-of-the-art LLM-based provers: it achieves the best solve rate on every benchmark and up to 100% on two benchmarks. It also reduces cost by up to 30.9% compared to the strongest baseline with the strongest LLM in our evaluation.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Theorem Proving, Program Verification, LLM Agents, Neurosymbolic AI

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_gCctOpenReview ↗
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
  1. 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.

  2. 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
AuthorsOpenReview ↗

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:

  • Clarifying our Codex configuration and resolving the Vero solve-rate discrepancy via in-loop proof checking (W1, Q1).
  • Justifying excluded baselines and establishing workload-level cost fairness across all five benchmarks and three backbones (W1, Q2).
  • Isolating adaptive routing from heuristic rules, rule evolution, and context/caching effects, alongside repository-level ablations (W2, Q3).
  • Releasing anonymized artifacts for reproducibility (W2, Q4).

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. 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?

Codex configuration. Across all benchmarks, we ran the official @openai/codex CLI (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:

  1. Model/effort sensitivity on repository tasks: Even on the official Vero leaderboard, Codex with GPT-5.5 at medium reasoning effort solves only 6/43 (14.0%), illustrating how sensitive whole-repository runs are to model tier, reasoning budget, and outer harness design.
  2. Premature termination without external proof-validation restarts (primary cause): In our original evaluation, coding agents ran out-of-the-box without modifying their native stopping loop. Even with strict prompt instructions prohibiting placeholders or statement edits, Codex frequently stopped early on large multi-obligation repositories: either concluding the remaining goals were too hard or leaving sorry holes / 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.

MetricMethodGPT-5.6-TerraGemini-3.5-FlashDeepSeek-V4-Flash
Proved repositories (of 43); total spendCoding Agent + in-loop proof checking19 (44.2%); $1,313.966 (14.0%); $2,302.4210 (23.3%); $250.55
Proved repositories (of 43); total spendCoCo-Prover23 (53.5%); $977.2526 (60.5%); $1,605.776 (14.0%); $228.35
Proved individual obligations (of 2,705)Coding Agent + in-loop proof checking2,207 (81.6%)915 (33.8%)1,547 (57.2%)
Proved individual obligations (of 2,705)CoCo-Prover2,309 (85.4%)2,081 (76.9%)1,337 (49.4%)

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.

AuthorsOpenReview ↗

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 and Init/Std APIs 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 (pass@k\text{pass}@k) 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 (pass@1\text{pass}@1) 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.

BackboneMethodCLEVER (161)VERINA (189)AlgoVeri (77)NTP4VC (300)Vero (43)
GPT-5.6-TerraAx-Prover-Base144; $163.71162; $260.1563; $209.52——
GPT-5.6-TerraHumanize157; $245.39187; $359.4066; $322.85——
GPT-5.6-TerraCoding Agent148; $122.05165; $160.2552; $74.45256; $245.961; $76.20
GPT-5.6-TerraCoCo-Prover161; $100.21189; $245.4369; $180.86268; $354.9823; $977.25
Gemini-3.5-FlashAx-Prover-Base138; $699.04137; $847.6859; $457.74——
Gemini-3.5-FlashHumanize157; $391.90180; $768.9062; $662.02——
Gemini-3.5-FlashCoding Agent152; $415.17166; $675.2955; $290.97239; $1,919.493; $1,099.28
Gemini-3.5-FlashCoCo-Prover161; $235.56186; $578.4662; $389.81284; $827.2726; $1,605.77
DeepSeek-V4-FlashAx-Prover-Base119; $69.21125; $137.8145; $29.81——
DeepSeek-V4-FlashHumanize148; $70.68139; $130.2351; $44.03——
DeepSeek-V4-FlashCoding Agent127; $68.62110; $65.7661; $80.34117; $72.290; $15.18
DeepSeek-V4-FlashCoCo-Prover156; $41.39189; $80.2972; $60.05285; $215.356; $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%.

AuthorsOpenReview ↗

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).

BenchmarkBackboneCoding Agent + in-loop proof checkingCoCo-Prover
CLEVER (161)GPT-5.6-Terra157; $169.47161; $100.21
CLEVER (161)Gemini-3.5-Flash158; $455.93161; $235.56
CLEVER (161)DeepSeek-V4-Flash150; $77.66156; $41.39
VERINA (189)GPT-5.6-Terra175; $476.58189; $245.43
VERINA (189)Gemini-3.5-Flash174; $953.38186; $578.46
VERINA (189)DeepSeek-V4-Flash186; $136.52189; $80.29
AlgoVeri (77)GPT-5.6-Terra61; $217.5369; $180.86
AlgoVeri (77)Gemini-3.5-Flash59; $521.6262; $389.81
AlgoVeri (77)DeepSeek-V4-Flash66; $107.2272; $60.05
NTP4VC (300)GPT-5.6-Terra271; $608.45268; $354.98
NTP4VC (300)Gemini-3.5-Flash263; $2,137.93284; $827.27
NTP4VC (300)DeepSeek-V4-Flash284; $225.97285; $215.35
Vero (43)GPT-5.6-Terra19; $1,313.9623; $977.25
Vero (43)Gemini-3.5-Flash6; $2,302.4226; $1,605.77
Vero (43)DeepSeek-V4-Flash10; $250.556; $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 Θo\Theta_o 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 (ρt=ρ0\rho_t = \rho_0 throughout, disabling AMEND\mathrm{AMEND} 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 variantCLEVER (10)VERINA (10)AlgoVeri (10)Total (30)Router API cost
Fixed specialist order (no LLM router)10; $41.029; $60.3810; $53.8029; $155.20$0
Handwritten heuristic router (no LLM router)8; $76.468; $89.106; $96.4722; $262.03$0
LLM router, frozen written rules (ρt=ρ0\rho_t = \rho_0)10; $24.9810; $50.0310; $44.1830; $119.19$9.1
LLM router, evolving written rules (CoCo-Prover)10; $28.6410; $43.4910; $38.8230; $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 ρt\rho_t 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 ev(st,Ut)\mathrm{ev}(s_t, U_t), 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.
Reviewer_mE1DOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

CoCo-Prover tracks proof and lemma dependencies, then routes open goals to automation, proof writing, lemma planning, or recovery. Experiments cover five Lean program-verification benchmarks and three model backbones.

Critical strengths

The Vero result stands out: Gemini solves 26 of 43 tasks, compared with 3 for the coding agent. Keeping dependencies and reusing lemmas seems well suited to these tasks. The paper also checks for changed statements and added axioms, which matters when evaluating proof agents. The fixed-backbone comparisons make the solve-rate gains more persuasive than a comparison between different underlying models would be. I lean toward acceptance because the system tackles repository-level proof organization and shows a substantial benefit there, even if the efficiency accounting needs revision.

Critical weaknesses

The cost results do not yet answer what it costs to run each method on the same workload. Table 2 includes only problems both methods solve. Figure 4 gives solve counts against a per-problem spending cap, rather than total spending. Failed attempts still cost money. Appendix F also omits local checking and retrieval costs and reports slower wall time with two backbones. Cost on shared successes is a valid quantity, but answers a narrower question. I would keep that table and add workload-level spending.

The router ablation compares against one fixed specialist order. As Appendix C.5 acknowledges, this does not isolate the benefit of updating routing rules. A control with frozen rules should retain access to history, so that explicit rule updates are the only change.

Questions for authors

Can you plot solve count against total model spending, including failed runs? What happens if routing rules are frozen while the router still sees the same state and history? Please keep the task set and stopping conditions fixed when comparing total spending.

5 comments
AuthorsOpenReview ↗

Response to Reviewer mE1D

We thank the reviewer for the positive assessment and constructive feedback. We appreciate your recognition of our repository-level results on Vero, the suitability of persistent dependency tracking and lemma reuse for multi-obligation program verification, our checks against altered theorem statements and added axioms, and our fixed-backbone experimental design.

Your review raises two focused questions:

  • How methods compare in proved-task count versus total model spending (including failed runs) when the task set and stopping conditions are held fixed, alongside the scope of local compute and wall-clock latency (W1, Q1).
  • What happens when written routing rules are frozen (ρt=ρ0\rho_t = \rho_0) while the router still observes the same proof-graph state and execution history (W2, Q2).

We have conducted new experiments directly addressing both points. Following your suggestion, we will retain Table 2 (cost on commonly solved tasks) in the revised paper and pair it with the full workload-level spending tables below as well as cumulative solved-task versus realized total model expenditure curves (including failed runs).


Workload-level model spending, failed runs, and fixed stopping conditions

Can you plot solve count against total model spending, including failed runs? ... Please keep the task set and stopping conditions fixed when comparing total spending.

Workload-level spending under the original protocol. To complement Table 2 (common-success cost) and Figure 4 (per-task budget caps), Table R1 reports proved-task counts alongside aggregate API expenditure over every attempted task, including failed runs, across all five benchmarks and three backbones.

Table R1. Original evaluation protocol: proved tasks and total API expenditure (USD), including failed runs, across all five benchmarks and three backbones. Each cell reports # proved tasks; total API cost.

BackboneMethodCLEVER (161)VERINA (189)AlgoVeri (77)NTP4VC (300)Vero (43)
GPT-5.6-TerraAx-Prover-Base144; $163.71162; $260.1563; $209.52——
GPT-5.6-TerraHumanize157; $245.39187; $359.4066; $322.85——
GPT-5.6-TerraCoding Agent148; $122.05165; $160.2552; $74.45256; $245.961; $76.20
GPT-5.6-TerraCoCo-Prover161; $100.21189; $245.4369; $180.86268; $354.9823; $977.25
Gemini-3.5-FlashAx-Prover-Base138; $699.04137; $847.6859; $457.74——
Gemini-3.5-FlashHumanize157; $391.90180; $768.9062; $662.02——
Gemini-3.5-FlashCoding Agent152; $415.17166; $675.2955; $290.97239; $1,919.493; $1,099.28
Gemini-3.5-FlashCoCo-Prover161; $235.56186; $578.4662; $389.81284; $827.2726; $1,605.77
DeepSeek-V4-FlashAx-Prover-Base119; $69.21125; $137.8145; $29.81——
DeepSeek-V4-FlashHumanize148; $70.68139; $130.2351; $44.03——
DeepSeek-V4-FlashCoding Agent127; $68.62110; $65.7661; $80.34117; $72.290; $15.18
DeepSeek-V4-FlashCoCo-Prover156; $41.39189; $80.2972; $60.05285; $215.356; $228.35

Under the original protocol, CoCo-Prover dominates both theorem-proving baselines (Ax-Prover-Base and Humanize) across all three backbones on the 427 function-level tasks: proving 9 to 128 more tasks while reducing total API spend by 16.9%–43.2% (winning 16 of 18 benchmark–backbone comparisons). Against the unmodified Coding Agent, CoCo-Prover already proves more tasks at lower total spend across all 770 tasks on Gemini-3.5-Flash and on function-level DeepSeek-V4-Flash, while spending more in raw total dollars on GPT-5.6-Terra and repository-level DeepSeek-V4-Flash where it solves far more tasks (e.g., 23/43 vs. 1/43 on Vero under GPT-5.6-Terra).

AuthorsOpenReview ↗

Response to Reviewer mE1D (contd.)

Why fixing stopping conditions is essential. As your question anticipates, raw total spend in Table R1 does not yet compare methods under identical stopping conditions. Although every method ran under the same external caps (\30/5hforfunction−levelbenchmarksandNTP4VC;30 / 5h for function-level benchmarks and NTP4VC; \\60 / 8h for Vero) and the same post-run Lean proof check (Appendix C.1), general-purpose coding agents have no explicit proof-graph state and frequently terminated prematurely despite strict prompt instructions (Ax-Prover-Base and Humanize have their own special control mechanisms): (i) declaring hard or multi-obligation tasks intractable and stopping early, or (ii) exiting with incomplete placeholders (sorry/admit), added axioms, or weakened definitions/statements that were later rejected by our post-run checker. Such early invalid exits make a failing baseline look artificially cheap simply because it stopped trying. By contrast, CoCo-Prover follows its same-provability, cheap-first rule over the two-level proof graph and enforces strict mechanical exit criteria: it stops only when all target declarations are Lean-accepted as stable, when a root target is refuted by a verified counterexample, or when the external cap is reached.

Aligning stopping conditions via in-loop proof checking. To hold both the task set and stopping conditions fixed, we augmented the Coding Agent across all five benchmarks and all three backbones with an in-loop Lean proof checker. Whenever the coding agent attempts to finish, the checker validates its output against the exact mechanical criteria of our final review (no unresolved goals, unmodified target declarations, and no unapproved axioms). If validation fails, the Lean diagnostics are returned and the agent resumes from its existing workspace until the proof passes validation or reaches the same external time/cost cap.

Table R2. Fixed task set and aligned stopping conditions: Coding Agent with in-loop proof checking vs. CoCo-Prover. Each cell reports # proved tasks; total API cost (including failed runs).

BenchmarkBackboneCoding Agent + in-loop proof checkingCoCo-Prover
CLEVER (161)GPT-5.6-Terra157; $169.47161; $100.21
CLEVER (161)Gemini-3.5-Flash158; $455.93161; $235.56
CLEVER (161)DeepSeek-V4-Flash150; $77.66156; $41.39
VERINA (189)GPT-5.6-Terra175; $476.58189; $245.43
VERINA (189)Gemini-3.5-Flash174; $953.38186; $578.46
VERINA (189)DeepSeek-V4-Flash186; $136.52189; $80.29
AlgoVeri (77)GPT-5.6-Terra61; $217.5369; $180.86
AlgoVeri (77)Gemini-3.5-Flash59; $521.6262; $389.81
AlgoVeri (77)DeepSeek-V4-Flash66; $107.2272; $60.05
NTP4VC (300)GPT-5.6-Terra271; $608.45268; $354.98
NTP4VC (300)Gemini-3.5-Flash263; $2,137.93284; $827.27
NTP4VC (300)DeepSeek-V4-Flash284; $225.97285; $215.35
Vero (43)GPT-5.6-Terra19; $1,313.9623; $977.25
Vero (43)Gemini-3.5-Flash6; $2,302.4226; $1,605.77
Vero (43)DeepSeek-V4-Flash10; $250.556; $228.35

Under matched stopping conditions, CoCo-Prover achieves strictly lower total API expenditure in all 15/15 benchmark–backbone settings, while proving more tasks in 13/15 settings:

  • Aggregate workload savings: Across all 770 tasks, CoCo-Prover reduces total model API 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 revised paper, we will also plot cumulative proved tasks against cumulative total model spending (including failed runs) across the workload to visualize this frontier directly alongside Figure 4.
  • Repository-scale gains on Vero: Preventing premature exits lifts the coding agent from 1/43 to 19/43 on GPT-5.6-Terra and 3/43 to 6/43 on Gemini-3.5-Flash, yet CoCo-Prover still proves more repositories (23/43 and 26/43) at 25.6%–30.3% lower total spend.
  • Solve-count qualifications: Enforcing continuation also reveals two settings where the resumed coding agent proves more tasks (NTP4VC under GPT-5.6-Terra and Vero under DeepSeek-V4-Flash), but CoCo-Prover spends 41.7% and 8.9% less respectively, and the solve-count margin is narrow (only 3 and 4 tasks). We will state both qualifications explicitly in the revised paper.
AuthorsOpenReview ↗

Response to Reviewer mE1D (contd.)

Freezing written routing rules while preserving state and history

What happens if routing rules are frozen while the router still sees the same state and history?

We agree with your point in W2 that w/o Router (fixed specialist order) in Table 3 measures adaptive routing as a whole rather than isolating explicit rule updates. On the same 30-task subset used in Table 3, we evaluated (1) an LLM router with frozen written rules (ρt=ρ0\rho_t = \rho_0 throughout, disabling AMEND\mathrm{AMEND} in Algorithm 1 while holding the two-level proof graph, shared failure memory, execution history, Lean diagnostics, goal clusters, specialist set, and configuration space Θo\Theta_o strictly fixed), as well as (2) a handwritten deterministic heuristic router over surface goal and history features (goal structure and failure counts, with zero LLM router calls). We also report direct Router API cost separately.

Table R3. Routing ablation on 30 function-level tasks (Gemini-3.5-Flash). Benchmark and Total cells report # proved tasks; total API cost (USD) across all attempts, including failures.

Routing variantCLEVER (10)VERINA (10)AlgoVeri (10)Total (30)Router API cost
Fixed specialist order (no LLM router)10; $41.029; $60.3810; $53.8029; $155.20$0
Handwritten heuristic router (no LLM router)8; $76.468; $89.106; $96.4722; $262.03$0
LLM router, frozen written rules (ρt=ρ0\rho_t = \rho_0)10; $24.9810; $50.0310; $44.1830; $119.19$9.1
LLM router, evolving written rules (CoCo-Prover)10; $28.6410; $43.4910; $38.8230; $110.94$13.7

Table R3 yields two clear takeaways that confirm your intuition regarding Appendix C.5:

  1. Evidence-conditioned LLM routing drives the primary gain. 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. Surface-feature heuristics underperform even a fixed cycle because syntactic goal features misjudge semantic proof difficulty, triggering unproductive decompositions or misallocated reasoning budgets.
  2. Explicit rule evolution (ρt\rho_t) contributes only modestly to provability and cost savings. Relative to frozen rules (ρt=ρ0\rho_t = \rho_0), evolving ρt\rho_t leaves the solve count unchanged and reduces total spend by only 6.9%. This limited gap arises precisely because even with frozen written rules, the agentic router still observes shared failure memory, execution history, Lean diagnostics, and proof-graph context in ev(st,Ut)\mathrm{ev}(s_t, U_t), enabling it to adapt implicitly in context at each decision epoch. Thus, the primary gain comes from evidence-grounded agentic decision-making over the proof graph, while persisting evolved rules provides a modest secondary refinement. We will make this distinction explicit in the revised paper.

We first share these new experimental results and responses here for your timely review. We are currently incorporating all of these updates into the manuscript and will upload the revised paper shortly.

Reviewer_7YmkOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

To address the cost of constructing proofs for program verification, this paper proposes CoCo-Prover, an agent orchestration framework for Lean 4. The method maintains an intra-declaration AND/OR proof graph and an inter-declaration lemma-dependency graph. A symbolic scheduler exposes available goals, while an LLM router selects among deterministic automation, proof writing, lemma planning, and recovery, together with their configurations. Partial proofs and shared lemmas are retained across invocations. The paper formulates this process as metalevel decision-making and evaluates it on five proof-only verification benchmarks with three LLM backbones. The results show competitive or higher solve rates and lower API cost on commonly solved problems, with additional budget curves, ablations, and detailed proof traces.

Critical strengths
  • S1. This paper studies an important practical problem: verification requires completing many dependent obligations, and repeatedly generating whole proofs can waste both partial progress and reusable facts. The combination of persistent proof states, shared helper lemmas, and targeted recovery is reasonable and technically useful. The distinction between provisional and stable lemmas is also clearly stated, and the final checks for unchanged statements, unresolved placeholders, and newly introduced axioms provide meaningful safeguards for the reported proof success.

  • S2. The evaluation covers several benchmarks and three backbones, with consistently strong results. CoCo-Prover reaches 100% on CLEVER and VERINA with GPT-5.6-Terra, and solves 26 of 43 Vero tasks with Gemini-3.5-Flash, compared with three for the corresponding coding agent. Common-success comparisons, budget curves, repeated full-system runs, and detailed case studies provide complementary evidence. In particular, the traces show concretely how retained lemmas and focused contexts can reduce repeated proof work.

Critical weaknesses
  • W1. The evidence for the distinctive orchestration mechanisms is incomplete. Specialized proof agents and error-driven repair are already established in [AutoVerus (OOPSLA 2025)], while [Hilbert (ICLR 2026)] combines recursive decomposition and several proving components. These methods do not subsume CoCo-Prover's persistent two-level graph or its program-verification setting. However, those distinctions make cross-target reuse, selective rollback, and evolving routing rules central to the contribution. The fixed-order and no-planner controls on 30 function-level tasks do not isolate these mechanisms on repository tasks. Graph-preserving controls would be more informative than removing the entire graph: sharing can be disabled, rollback broadened, and explicit routing rules frozen while retaining the same representation and history inputs. The existing gains over general coding agents leave uncertainty about which distinctive mechanisms are responsible.

  • W2. The main cost comparison does not establish the total expenditure needed to verify an attempted workload. Table 2 reports costs on the intersection of tasks successfully solved by both methods, excluding unsuccessful attempts. Figure 4 adds useful evidence about success under per-problem caps, but does not show aggregate actual expenditure against verified-task count. Moreover, the dollar figures exclude local verification, retrieval, and embedding costs, and mean latency is higher for two backbones. Conditional API savings are a valid result, and the full-system repeated runs should be credited. However, the gap between that result and the broader economic motivation remains consequential for a paper centered on cost-efficient verification.

Questions for authors
  • Q1. Can the authors report total API expenditure over all attempted tasks, including failures, alongside verified-task counts for the main methods? How do the rankings change when total spend, rather than only common-success cost or per-task caps, is compared?

  • Q2. Can the authors evaluate graph-preserving repository controls that disable cross-target lemma sharing or replace selective rollback with broader rollback? A breakdown by the number of dependent obligations would help identify where these mechanisms matter.

  • Q3. With history and graph inputs held fixed, how does a frozen-rule router compare with the evolving-rule router in solve rate, total API spend, and routing overhead? Appendix C.1's explanations for incompatible or expensive prover baselines are useful; this internal control would test the claimed adaptive component without requiring an unmodified prover to accept an incompatible task format.

7 comments
AuthorsOpenReview ↗

Response to Reviewer 7Ymk

We thank the reviewer for the thorough evaluation and constructive feedback. We appreciate your recognition of the practical importance of repository-scale program verification, our persistent two-level proof representation, the distinction between provisional and stable lemmas, and our Lean proof-checking safeguards.

Your comments highlight two important questions:

  • How methods compare in total workload-level API expenditure including failed runs under fair stopping conditions (W2, Q1).
  • How much of CoCo-Prover's gain comes specifically from cross-target sharing, selective node-level rollback, and explicitly evolving routing rules under graph-preserving controls (W1, Q2, Q3).

We have conducted extensive new experiments directly addressing each question and will incorporate all results, protocols, and discussions into the revised paper.


Q1. Total workload expenditure, failed attempts, and stopping-condition fairness

Can the authors report total API expenditure over all attempted tasks, including failures, alongside verified-task counts for the main methods? How do the rankings change when total spend, rather than only common-success cost or per-task caps, is compared?

Complementary roles of common-success cost and workload-level spend. In the submitted paper, Table 2 measures the like-for-like cost of obtaining valid proofs on commonly solved tasks, while Figure 4 measures solve counts under per-task expenditure caps. We agree that practitioners also need aggregate API expenditure across the entire attempted workload, including failed runs, alongside the number of proved (Lean-validated) tasks. In the revision, we will report both metrics side by side so that common-success cost is complemented by full workload accounting.

Table R1. 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.

BackboneMethodCLEVER (161)VERINA (189)AlgoVeri (77)NTP4VC (300)Vero (43)
GPT-5.6-TerraAx-Prover-Base144; $163.71162; $260.1563; $209.52——
GPT-5.6-TerraHumanize157; $245.39187; $359.4066; $322.85——
GPT-5.6-TerraCoding Agent148; $122.05165; $160.2552; $74.45256; $245.961; $76.20
GPT-5.6-TerraCoCo-Prover161; $100.21189; $245.4369; $180.86268; $354.9823; $977.25
Gemini-3.5-FlashAx-Prover-Base138; $699.04137; $847.6859; $457.74——
Gemini-3.5-FlashHumanize157; $391.90180; $768.9062; $662.02——
Gemini-3.5-FlashCoding Agent152; $415.17166; $675.2955; $290.97239; $1,919.493; $1,099.28
Gemini-3.5-FlashCoCo-Prover161; $235.56186; $578.4662; $389.81284; $827.2726; $1,605.77
DeepSeek-V4-FlashAx-Prover-Base119; $69.21125; $137.8145; $29.81——
DeepSeek-V4-FlashHumanize148; $70.68139; $130.2351; $44.03——
DeepSeek-V4-FlashCoding Agent127; $68.62110; $65.7661; $80.34117; $72.290; $15.18
DeepSeek-V4-FlashCoCo-Prover156; $41.39189; $80.2972; $60.05285; $215.356; $228.35

Table R1 shows two clear patterns under the original protocol:

  • Strict dominance over theorem-proving baselines: Summed over the 427 function-level tasks, CoCo-Prover dominates both Ax-Prover-Base and Humanize under every backbone: proving 9 to 128 more tasks while reducing total API expenditure by 16.9%–43.2% (winning 16 of 18 benchmark–backbone comparisons, with the only cost exceptions on AlgoVeri under DeepSeek-V4-Flash where baselines quit hard goals early; Appendix C.3).
  • Trade-off against the unmodified Coding Agent: CoCo-Prover already proves more tasks at lower total spend across all 770 tasks on Gemini-3.5-Flash (+104 tasks, 17.3% lower spend) and on function-level DeepSeek-V4-Flash (+119 tasks, 15.4% lower spend). On GPT-5.6-Terra and repository-level DeepSeek-V4-Flash, CoCo-Prover proves substantially more tasks (e.g., 23/43 vs. 1/43 on Vero under GPT-5.6-Terra) at higher raw spend. Accordingly, we do not claim universal dominance in raw total spend under the original stopping behavior.
AuthorsOpenReview ↗

Response to Reviewer 7Ymk (contd.)

Why stopping behavior distorts raw workload spend. Under the original protocol, every method faced the same external caps (\30/5hpertaskforfunction−levelbenchmarksandNTP4VC;30 / 5h per task for function-level benchmarks and NTP4VC; \\60 / 8h for Vero) and the same independent post-run Lean proof check (Appendix C.1), which rejects unresolved goals (sorry/admit), modified theorem statements, and added axioms. However, post-run checking does not prevent an agent from terminating prematurely without exhausting its budget. We observed this frequently in general-purpose coding agents (Ax-Prover-Base and Humanize have their own special control mechanisms): on hard or multi-obligation tasks, they either gave up early or produced Lean files containing placeholders or altered statements that were later rejected by our post-run proof checker, even when strict instructions were given in prompts. Such runs make a failing baseline appear inexpensive simply because it exited early without valid proofs, whereas CoCo-Prover tracks explicit proof status on its graph and continues until all target declarations are Lean-accepted or the external cap is reached.

Coding-agent control with in-loop proof checking. To align stopping conditions fairly, we augmented the coding-agent baseline with in-loop proof checking across all five benchmarks and all three backbones. Whenever the coding agent reports completion, an in-loop Lean checker validates the produced file against the exact mechanical criteria of our final review (no unresolved goals or sorry, unmodified target declarations, and no unapproved axioms). If proof validation fails, the checker returns the Lean diagnostics to the agent, which resumes from its existing workspace until the proof passes validation or the run hits the same external caps. All target tasks, backbones, token prices, and post-run checks remain identical.

Table R2. Coding Agent with in-loop proof checking vs. CoCo-Prover across all five benchmarks and three backbones. Each cell reports # proved tasks; total API cost (including failed runs).

BenchmarkBackboneCoding Agent + in-loop proof checkingCoCo-Prover
CLEVER (161)GPT-5.6-Terra157; $169.47161; $100.21
CLEVER (161)Gemini-3.5-Flash158; $455.93161; $235.56
CLEVER (161)DeepSeek-V4-Flash150; $77.66156; $41.39
VERINA (189)GPT-5.6-Terra175; $476.58189; $245.43
VERINA (189)Gemini-3.5-Flash174; $953.38186; $578.46
VERINA (189)DeepSeek-V4-Flash186; $136.52189; $80.29
AlgoVeri (77)GPT-5.6-Terra61; $217.5369; $180.86
AlgoVeri (77)Gemini-3.5-Flash59; $521.6262; $389.81
AlgoVeri (77)DeepSeek-V4-Flash66; $107.2272; $60.05
NTP4VC (300)GPT-5.6-Terra271; $608.45268; $354.98
NTP4VC (300)Gemini-3.5-Flash263; $2,137.93284; $827.27
NTP4VC (300)DeepSeek-V4-Flash284; $225.97285; $215.35
Vero (43)GPT-5.6-Terra19; $1,313.9623; $977.25
Vero (43)Gemini-3.5-Flash6; $2,302.4226; $1,605.77
Vero (43)DeepSeek-V4-Flash10; $250.556; $228.35

When premature invalid exits are prevented, the workload-level comparison becomes decisive: CoCo-Prover achieves lower total API expenditure in all 15/15 benchmark–backbone settings, while proving more tasks in 13/15 settings:

  • Consistent workload-level savings across backbones: Summed over all tasks, CoCo-Prover reduces total API spend by 33.3% on GPT-5.6-Terra, 42.9% on Gemini-3.5-Flash, and 21.6% on DeepSeek-V4-Flash (+12 tasks).
  • Repository-scale impact on Vero: In-loop proof checking lifts Codex from 1/43 to 19/43 under GPT-5.6-Terra, confirming that early termination explained its low original solve rate, yet CoCo-Prover still proves more repositories (23/43 on GPT-5.6-Terra and 26/43 vs. 6/43 on Gemini-3.5-Flash) at 25.6%–30.3% lower total spend.
  • Solve-count qualifications: This stronger baseline surfaces only two exceptions in solve count (NTP4VC under GPT-5.6-Terra and Vero under DeepSeek-V4-Flash). In both cases, the solve-count margin is narrow (only 3 and 4 tasks), while CoCo-Prover still reduces total API spend by 41.7% and 8.9%, respectively. We will report Table R2 in full and explicitly state both qualifications in the revised paper.
AuthorsOpenReview ↗

Response to Reviewer 7Ymk (contd.)

Scope of cost accounting and wall-clock latency. All dollar figures report LLM inference API expenditure. Local Lean checking and hash-cached Lean Finder embeddings run on modest shared hardware used identically across baselines, making their amortized cost negligible compared to frontier API expenditure. We will state this scope explicitly in the main text. Regarding latency (Figure 5, Appendix C.2), CoCo-Prover incurs higher mean wall-clock time on GPT-5.6-Terra and Gemini-3.5-Flash (while running faster on DeepSeek-V4-Flash) for two reasons: (i) instead of generating monolithic proofs in one shot, it generates small, bounded Lean steps over compact contexts and checks each before purchasing the next action, trading sequential round-trips for lower token spend; and (ii) our current prototype processes one frontier goal group per epoch sequentially without parallelizing across the proof graph. Parallelizing specialist calls and Lean checking across independent frontier groups is a straightforward systems extension that can substantially reduce wall-clock latency without increasing API cost.


Q2. Graph-preserving repository controls and obligation-level analysis

Can the authors evaluate graph-preserving repository controls that disable cross-target lemma sharing or replace selective rollback with broader rollback? A breakdown by the number of dependent obligations would help identify where these mechanisms matter.

Isolating graph mechanisms from generic agent primitives. We agree with your characterization in W1: specialist proof-repair loops (e.g., AutoVerus) and recursive decomposition for standalone math theorems (e.g., Hilbert) already exist, and our function-level w/o Lemma Planner ablation (Table 3) removes intra-theorem helper introduction along with cross-theorem reuse. CoCo-Prover's distinctive structural mechanisms in repository-level program verification are cross-target reuse on the inter-declaration DAG and selective node-level rollback on the intra-declaration AND/OR hypergraph. Testing them therefore requires graph-preserving single-mechanism interventions.

We evaluated both controls on a repository-level pilot of five Vero tasks (using Gemini-3.5-Flash under the standard $60 / 8h per-task caps) and the results are shown in Table R3. Because full 43-task Vero reruns per ablated variant cost thousands of dollars, these five tasks were drawn from full-system successes as a mechanism-focused pilot. We will state this sampling scope explicitly.

Table R3. Graph-preserving repository controls on five Vero tasks (Gemini-3.5-Flash). Total API cost sums across all five runs, including failed attempts.

VariantProved tasksTotal API cost (USD)
CoCo-Prover (full)5/5$184.14
Cross-target sharing disabled; Lemma Planner retained2/5$216.81 (+17.7%)
Broader rollback at the declaration root1/5$243.84 (+32.4%)
  1. Disabling cross-target sharing only: This control retains the Lemma Planner, two-level graph, and intra-target helper reuse: helpers can still be proposed, checked for counterexamples, and reused within the originating target theorem's sub-DAG, but neither helpers nor already-proved targets may be imported across other root target declarations. Removing cross-target edges forces shared data-structure invariants to be repeatedly re-conjectured and re-proved across specifications, exhausting per-task budgets.
  2. Replacing selective rollback with declaration-root rollback: Keeping the Recovery Reviewer's trigger, diagnosis, and cross-target sharing unchanged, this control resets to the root of the affected declaration rather than rewinding to the nearest safe AND node in HℓH_\ell, discarding internal partial proofs and reopening dependent work. Although restarting from the root gives the LLM a chance to rethink the entire proof when early steps take a wrong direction, most dead ends in repository verification arise mid-proof on a specific subgoal (e.g., after unfolding a recursive definition too far) while earlier steps and sibling subgoals remain valid. Throwing away all Lean-checked progress inside the declaration forces the prover to repeatedly reconstruct valid steps from scratch, driving up cost and exhausting the budget.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General Response

We sincerely thank all reviewers for their thorough, constructive, and encouraging evaluations. Following your feedback, we have conducted extensive new experiments and uploaded the revised manuscript, with all newly added results, analyses, and revisions highlighted in blue. Below, we summarize the core contributions recognized by the reviewers and the manuscript revisions made to address every concern.


1. Core Contributions, Novelty, and Reviewer Consensus

Real-world software verification involves hundreds or thousands of interdependent proof obligations with sharply asymmetric difficulty, where every kernel-accepted proof certifies equally. Rather than pursuing pass rates alone under uniform sampling or monolithic repair loops, CoCo-Prover poses the success-vs-cost frontier as a primary objective for theorem proving in program verification (Section 1). Specifically, we formulate cost-efficient code proving as metalevel decision-making under cost grounded on persistent two-level proof graphs involving an intra-declaration AND/OR hypergraph over Lean goal states with an inter-declaration lemma-dependency DAG tracking provisional and stable artifacts (Section 3.1). We instantiate it via evidence-grounded agent orchestration that combines cross-target lemma/target reuse, selective node-level rollback, and adaptive dispatch across heterogeneous proving specialists (Section 3.2).

We are encouraged that all reviewers recognized the significance, technical coherence, and empirical strength of these contributions:

  • Importance of cost-efficient and repository-scale program verification: Reviewers highlighted the practical importance of addressing cost efficiency in LLM-based theorem proving (gCct) and tackling multi-obligation, repository-scale verification (7Ymk, mE1D).
  • Coherence of two-level proof graphs and cross-obligation reuse with agent orchestration: Reviewers appreciated our persistent two-level proof representation (7Ymk, gCct), the distinction between provisional and stable lemmas (7Ymk), the suitability of dependency tracking and helper reuse for multi-obligation program verification (mE1D), and the synergy with adaptive agent orchestration (gCct).
  • Rigorous verification safeguards and strong empirical gains: Reviewers commended our strict post-run Lean proof-checking safeguards against altered theorem statements, placeholders, and added axioms (7Ymk, mE1D), our controlled fixed-backbone evaluation design (mE1D), and our strong empirical results across function- and repository-level benchmarks (mE1D, gCct).

2. Manuscript Revisions Addressing Reviewer Concerns

To thoroughly resolve the questions raised across the reviews, we added the following controlled experiments, analyses, and artifacts to the revised paper:

  1. Total workload expenditure and matched-stopping comparisons (Section 4.1, Tables 3–5; Appendix C.6, Figure 6 — addressing 7Ymk, mE1D, gCct): To address concerns about omitted failed-run costs and premature baseline exits (including the unmodified Codex solve rate on Vero), we added aggregate LLM API expenditure across all attempted tasks under the original protocol (Table 3) and re-evaluated coding agents across all 5 benchmarks and 3 backbones with an in-loop Lean proof checker and automatic workspace resumption up to identical external caps (Tables 4–5, Figure 6). Preventing premature invalid exits lifts Codex on Vero from 1/43 to 19/43 repositories on GPT-5.6-Terra (confirming early termination explained the original gap), yet CoCo-Prover achieves lower total API expenditure in all 15/15 benchmark–backbone settings (cutting 770-task spend by 33.3% on GPT-5.6-Terra, 42.9% on Gemini-3.5-Flash, and 21.6% on DeepSeek-V4-Flash) while proving more tasks in 13/15 settings, with only two narrow solve-count exceptions where CoCo-Prover still cuts spend by 41.7% and 8.9%.

  2. Graph-preserving repository controls and obligation-level breakdown (Appendix C.7, Tables 13–14 — addressing 7Ymk, gCct): To isolate repository-scale graph mechanisms beyond function-level ablations, we evaluated graph-preserving single-mechanism interventions on Vero (Table 13): disabling cross-target sharing while retaining intra-target lemma planning drops completion from 5/5 to 2/5 (+17.7% spend), and replacing selective node-level rollback with broader rollback drops completion to 1/5 (+32.4% spend). We also added an individual-obligation breakdown across all 2,705 Vero target theorems (Table 14), showing how persistent cross-target dependencies close tightly coupled tail obligations where monolithic coding-agent transcripts stall.

AuthorsOpenReview ↗

General Response (contd.)

  1. Isolating evidence-grounded routing from heuristics, rule evolution, and prompt caching (Sections 3.2 & 4.2; Appendix C.5, Tables 11–12 — addressing 7Ymk, mE1D, gCct): Holding the two-level proof graph, execution history, and compact context packets strictly fixed on the 30-task ablation set, we evaluated a deterministic surface-feature heuristic router and a frozen-rule LLM router (ρt=ρ0\rho_t = \rho_0) alongside direct Router API cost (Table 11). Results show that evidence-conditioned LLM routing drives the primary gain, whereas explicit rule evolution provides a modest secondary refinement because the router already observes shared history and graph context in ev(st,Ut)\mathrm{ev}(s_t, U_t). A token-type breakdown (Table 12) further shows that CoCo-Prover achieves these savings despite reading 2.5×2.5\times–13.5×13.5\times fewer cached prompt tokens than append-only coding agents.

  2. Sharpened novelty positioning, baseline justifications, and compute/latency scope (Sections 1, 2, 4, & 5; Appendices C.1, C.2, & F — addressing 7Ymk, mE1D, gCct): We sharpened our Introduction, Related Work, and Conclusion to explicitly contrast CoCo-Prover with AutoVerus and Hilbert. We documented Codex's high-reasoning-effort configuration and expanded exclusion rationales for Optimizing-Lean-Agent (supervised binary math classifier pinned to Lean 4.9.0) and Goedel-Code-Prover (RL post-trained pass@k\text{pass}@k checkpoint) in Appendix C.1. We also clarified our LLM-API cost-accounting scope relative to shared local hardware as well as sequential-epoch latency and frontier-group parallelization in Appendices C.2 and F.

  3. Public anonymized artifact release (Reproducibility Statement — addressing gCct): To support full reproducibility, we released our anonymized artifacts at anonymous Github as shown in Reproducibility Statement.

We thank the reviewers again for their valuable guidance, which has substantially strengthened our paper.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.