Back to AI News
arxiv

ProofCoder brings continuous reasoning to automated software verification

ProofCoder is an agentic proof-synthesis system for the Rocq proof assistant that treats theorem proving as a coding-agent task rather than a fixed tactic-generation loop. It uses proof-assistant feedback to decide when to retrieve information, inspect proof states, revise proof fragments, or backtrack, supporting tactic-level and whole-proof generation. On 280 tasks from the AutoRocq Benchmark, the best configurations raise proof success from 47% to 60% over the state-of-the-art AutoRocq system, a 27.7% relative improvement at approximately half the cost. Ablations identify continuous reasoning as a key design choice, with its removal leading to fewer solved lemmas, higher cost, more backtracking, and more discarded revisions.

AI Brief

It presents a concrete agentic advance in LLM-based formal verification, with benchmark evidence that feedback-guided continuous reasoning improves proof success at lower cost.

arXiv:2611.14106v1 Announce Type: cross Abstract: Formal verification using proof assistants provides strong correctness guarantees for software, but constructing proofs remains labor-intensive and requires significant expertise. Recent approaches based on large language models (LLMs) have shown promise in automating proof synthesis. However, these approaches typically constrain the model to a rigid tactic-generation loop, in which the surrounding system controls premise retrieval, proof-state management, and backtracking. We introduce ProofCoder, an agentic proof-synthesis system for Rocq that approaches theorem proving from a coding-agent perspective. Rather than generating tactics within a fixed loop, ProofCoder reasons continuously throughout proof search and uses proof-assistant feedback to decide when to gather additional information, inspect proof states, revise previously generated proof fragments, or backtrack to an earlier point in the proof. This allows it to iteratively construct, repair, and refine proofs, at either tactic-level or whole-proof granularity. We evaluate ProofCoder on 280 challenging verification tasks from the AutoRocq Benchmark. On the best-performing configurations, ProofCoder increases proof success from 47% to 60% over the state-of-theart AutoRocq system, corresponding to a 27.7% relative improvement at approximately half the cost. Our ablations identify continuous reasoning as a key design choice: without it, the agent solves fewer lemmas at substantially higher cost, backtracks four to six times more often, and more frequently discards its own revisions. Whole-proof and tactic-level generation achieve similar success rates but follow distinct search and repair strategies. These results suggest that effective automated software verification requires more than improved tactic selection: continuous reasoning and feedback-guided proof revision are critical ingredients for robust proof synthesis.
Be the first to rate this article.

Comments & Questions (0)

Captcha
Please be respectful — let's keep the conversation friendly.

No comments yet

Be the first to comment!