WorksComputer Science
ProofCoder: Continuous Reasoning for Automated Software Verification
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.
CCS Concepts: • Software and its engineering → Formal software verification; • Security and privacy → Logic and verification.
Additional Key Words and Phrases: Formal Methods, Program Verification, Theorem-proving, LLM Agent
Introduction
As large language models (LLMs) are increasingly used for code generation, there is a growing need to verify generated software for bugs, vulnerabilities, and violations of intended specifications [6]. Formal verification offers a principled way to establish strong correctness guarantees and has been used in several real-world systems [21, 22, 29, 32]. In many verification workflows, programs and specifications are translated into logical proof obligations that can be discharged using interactive theorem provers (ITPs), such as Lean [10] and Rocq [40]. However, formal verification through ITPs remains expensive: users must formulate appropriate specifications and construct proof scripts accepted by the proof assistant, a process that is time-consuming and requires substantial expertise. Moreover, changes to the program or its specifications can invalidate existing proofs, requiring proofs to be adapted or reconstructed as the software evolves.
LLM-based proof synthesis is a promising direction for reducing the burden of interactive theorem proving. Compared with code generation, proof generation has a distinctive advantage: candidate
Authors’ Contact Information: Martim Afonso, INESC-ID & IST, University of Lisbon, Lisbon, Portugal and Politecnico di Torino, Turin, Italy, [email protected]; Inês Lynce, INESC-ID & IST, University of Lisbon, Lisbon, Portugal, [email protected]; Maurizio Morisio, Politecnico di Torino, Turin, Italy, [email protected]; João F. Ferreira, INESC-ID & Faculty of Engineering, University of Porto, Porto, Portugal, [email protected]. proof scripts are checked by the proof assistant. As a result, hallucinated or nonsensical model outputs do not silently compromise correctness, as they are rejected by the proof assistant and can be treated as failed attempts. This makes theorem proving well suited to LLM-based approaches, combining strong, executable feedback with the soundness guarantees of the underlying prover.
A common design in prior LLM-based proof systems is to place the model within a controller-driven search loop, where the surrounding algorithm determines when and how to retrieve context, backtrack, or repair [26, 34, 35, 39, 41] [13, 18]. AutoRocq [42] moves toward an agentic formulation of software verification, showing that giving the model greater control over proof search can substantially improve over earlier controller-driven approaches. Instantiated in Rocq, it targets program-verification obligations and allows the LLM to select among tools for planning, tactic generation, and querying the verification environment. Nevertheless, its autonomy is bounded by a semi-constrained protocol that restricts tool use and guides subsequent actions.
In this work, we introduce ProofCoder, an agentic proof-synthesis system inspired by modern coding agents [47]. Rather than following a fixed or highly structured interaction loop, ProofCoder gives the agent greater control over the proof process: it can inspect previous proof states, query the environment, read the source file, edit the proof script, and continuously reason about how to combine these actions, using ITP feedback to guide proof construction and repair. This design lets us study whether a coding-agent-style interaction model is better suited to interactive theorem proving than more constrained tactic-generation loops, and how restrictions on tools, generation granularity, and interaction structure affect proving performance.
We evaluate ProofCoder on 280 challenging verification lemmas from the AutoRocq Benchmark, drawn from SV-COMP [3] and the Linux kernel (Verker). Our primary comparison is with AutoRocq [42], the state of the art in agentic Rocq-based software verification. We additionally compare against Rango [41], PALM [26], COPRA [39], QEDCartographer [35], and Proverbot9001 [34].
Across both benchmarks and two different models, ProofCoder outperforms the state of the art, increasing proof success from 47% to 60% in the best-performing configuration while also reducing inference cost by approximately half. We further conduct a series of ablations showing that continuous reasoning and localized repair are key to these gains.
In summary, the main contributions of this paper are:
A new approach to agentic theorem proving, inspired by coding agents, that uses continuous reasoning and a more flexible agentic loop to outperform the state of the art.
Several ablations and analyses that quantify the impact of different constraints on agent performance and behavior.
A pipeline for theorem proving in Rocq with a simple and adaptable Model Context Protocol.
Motivating Example
We illustrate the behavior of ProofCoder with the loop-invariant preservation property shown in Listing 1, adapted from the SV-COMP benchmark. This example is representative of the verification lemmas and proof engineering tasks encountered in software verification with interactive proof assistants such as Rocq, particularly those generated by tools such as Frama-C [20].
Theorem wp_goal :
forall (t : addr -> int) (i i1 : int) (a : addr),
let x := t (shift a i1) in
0 < i1 -> 0 < i1 <= i ->
(* region and bound hypotheses omitted *)
is_sint32 (t (shift a i)) ->
(forall i2,
let x1 := t (shift a i2) in 0 < i2 -> i2 < i ->
-2147483648 <= x1 <= 2147483647) ->
-2147483648 <= x <= 2147483647.
Listing 1. Abridged loop-invariant preservation lemma.
Intuition. The loop invariant states that every array element processed so far (i.e., every index i2 < i) is a valid signed 32-bit integer (i.e., within the bounds −2147483648 and 2147483647). The goal is to prove that the same property holds for an arbitrary index i1 satisfying i1 <= i.
Challenge. The proof obligation is simple at a high level, but it requires careful interaction with the evolving proof state. The invariant hypothesis applies only to indices strictly smaller than i, while the context gives only i1 <= i. Thus, applying the invariant directly is insufficient: the proof must distinguish between the cases i1 < i and i1 = i. In the first case, the invariant applies directly. In the second case, the goal reduces to the existing hypothesis is_sint32(t (shift a i)), after unfolding the definition of is_sint32.
AutoRocq behavior. AutoRocq, the state of the art in agentic Rocq-based software verification, identifies the main proof structure early: it observes that the proof must distinguish between the cases i1 < i and i1 = i. This is the right high-level decomposition, since the loop invariant can only be applied to indices strictly smaller than i, while the context provides only i1 <= i. However, after reaching the boundary case i1 = i, AutoRocq fails to turn this decomposition into a completed proof.
In this branch, rewriting i1 to i reduces the goal to an arithmetic bound on t (shift a i). The context already contains the hypothesis
H_sint32_i_val : is_sint32 (t (shift a i))
which is sufficient after unfolding the definition of is_sint32. AutoRocq retrieves this definition via Print, but does not unfold it, instead exploring transformations of the address expression such as rewriting and unfolding shift, and attempting to prove equalities between terms. These steps move the proof away from the fact needed to close the branch.
Thus, AutoRocq’s failure is not due to missing the global proof idea. It finds the same case split that is needed for the proof. The failure occurs at the level of local proof-state interpretation: once the proof reaches the branch where i1 = i, AutoRocq does not recognize that the remaining goal is an unfolded form of an existing is_sint32 hypothesis. The result is a long sequence of unproductive repairs, eventually exhausting the token budget without completing the proof.
How ProofCoder succeeds. ProofCoder begins from the natural but incomplete strategy of applying the loop invariant directly at index i1. Initially, it tries the following:
intros ... H_forall.
unfold x.
apply H_forall.
- assumption.
This attempt fails because the remaining subgoal is i1 < i. The proof state therefore exposes the missing condition: the context contains i1 <= i, but the invariant requires a strict inequality. ProofCoder receives this feedback and, through continuous reasoning, revises its strategy rather than abandoning the proof or continuing with unrelated rewrites:
The issue is that we need to show i1 < i, but we only have i1 <= i. Let me reconsider the proof strategy. The universal quantifier requires i2 < i, but we only know i1 <= i. I need to handle the case where i1 = i separately.
It backtracks to the beginning of the proof fragment and introduces the needed case split:
intros ... H_forall.
unfold x.
assert (i1 < i \/ i1 = i) as [H_lt | H_eq] by lia.
This repair preserves the useful prefix of the proof, namely the introduced variables and the unfolding of , while replacing only the incorrect attempt to apply the invariant unconditionally. In the branch, ProofCoder reuses the original idea and applies H_forall successfully:
apply H_forall.
assumption.
The remaining branch is the boundary case . Rewriting with H_eq gives:
Here, assumption fails because the matching hypothesis uses the defined predicate:
H_sint32_i_val : is_sint32 (t (shift a i))
ProofCoder queries the definition of is_sint32, learns that it expands to , and, through its continuous reasoning process, comes up with:
The goal requires ... while is_sint32 uses . These are equivalent for integers. Let me apply H_sint32_i_val and use lia.
It then locally replaces the failed assumption step with:
unfold is_sint32 in H_sint32_i_val.
lia.
This closes the proof. The first repair adds the missing case split, while the second changes only the closing tactic for the boundary case. Together, continuous reasoning and localized repair allow ProofCoder to complete the lemma; the final proof is shown in Listing 2.
intros t i i1 ... H_sint32_i H_sint32_succ H_sint32_0 H_sint32_i_val H_forall.
unfold x.
assert (i1 < i \/ i1 = i) as [H_lt | H_eq] by lia.
apply H_forall.
assumption.
assumption.
rewrite H_eq.
unfold is_sint32 in H_sint32_i_val.
lia.
Listing 2. Final proof generated by ProofCoder.
Takeaway. This example shows that the key difference is not whether the agents find the right high-level idea: both AutoRocq and ProofCoder identify the split between and . The difference is how they react to the resulting proof states. AutoRocq reaches the right decomposition but fails to close the boundary case, while ProofCoder uses each failed tactic to revise its local plan. This is where focused repair matters. The failed steps do not invalidate the whole proof: the introduced context, the unfolding of , the case split, and the solved branch remain useful. ProofCoder can preserve this prefix and replace only the failing fragment. Its continuous reasoning between tool calls becomes the main driver in proof repair, allowing the agent to interpret proof-state feedback more accurately and fix the script, first adding the missing case split and then unfolding is_sint32 to close the final arithmetic goal.
Agentic Proof Synthesis with Continuous Reasoning
Figure 1 summarizes ProofCoder’s workflow. Inspired by coding agents, ProofCoder treats the proof script as an editable artifact: at each step, it uses Rocq feedback to reason about the current state, retrieve context when needed, and either extend the proof or revise a previously generated suffix. This gives the agent control over when and where to construct and repair proofs.
Figure 1. Overview of ProofCoder’s workflow.
Proof Sessions
Each proof attempt is executed inside a preconfigured Rocq session. The harness binds the agent to a single proof obligation, including the theorem name, the source file, and the workspace containing the generated verification condition. The agent does not invoke Rocq directly or edit files outside this workspace; interactions with the proof assistant go through the tool interface described below.
At the beginning of a session, the agent receives the initial proof state, including the current hypotheses and goals. From there, it incrementally constructs a proof script. The script is represented as an ordered list of tactic lines, and the proof assistant is used as the verifier after every edit. A session terminates successfully when Rocq accepts the generated script and all goals are discharged. The agent is not allowed to use placeholder proof commands such as admit or shelve/unshelve; only fully checked proofs are counted as successful. Furthermore, the environment’s setup prevents the agent from changing the theorem statement.
Tool Interface
The agent interacts with Rocq through a small set of tools. These tools expose both read-only operations, used to inspect proof states or retrieve context, and a single mutating operation, used to edit the proof script.
check_state. Read-only tool that replays the proof script up to a given tactic index and returns the corresponding proof state. The index denotes the length of the prefix to execute: index 0 corresponds to the initial goal, while index n corresponds to the state after the first n tactic lines. This allows the agent to inspect not only the current state, but also earlier states in the proof. In practice, the agent should use this tool sparingly, primarily when it needs to revisit the context at an earlier point before deciding where to repair the script.
call_command. Read-only tool that provides access to standard Rocq commands such as Search, Print and Locate. The agent can search for relevant lemmas, inspect definitions, locate identifiers, or check the type of a term before using it in the proof. The output of these commands is returned as text and becomes part of the subsequent model context.
read_proof_file. Read-only tool that enables the agent to inspect files in the session workspace. This is useful when the compact proof-state display omits information that is easier to understand from the source theorem, or when the agent needs to verify definitions and local context present in the file.
edit_proof. This is the only tool that modifies the proof script. The tool takes a proof fragment and inserts it into the current script. By default, the fragment is appended to the end of the proof. Alternatively, the agent may provide an edit index . In that case, the environment preserves the first proof lines, discards the remaining suffix, and appends the newly generated fragment. This interface is independent of the granularity of proof generation. In a tactic-level configuration, the generated fragment is restricted to a single tactic. In a whole-proof configuration, the fragment may contain an entire proof attempt or the suffix necessary to complete it. Thus, it provides a uniform mechanism for forward proof construction, localized repair, and full proof revision.
After each edit, the environment rechecks the resulting script and returns feedback from Rocq. If the edit is accepted but goals remain, the response contains the updated proof state. On failure, the response reports the failing tactic index and the corresponding proof state at the point of failure. The agent can then continue from the current prefix, replace the rejected step, or backtrack further by editing from an earlier index.
Continuous Reasoning
The integration of continuous reasoning [50] with verifier-guided proof repair is a central part of our agent design. At each step, the model produces a natural language message, along with the tool call, recording the model’s interpretation of the current proof state, the local proof objective, the intended action, and, when relevant, its diagnosis of a previous failed attempt. The tool call executes the action described in this reasoning, such as inspecting a proof state, querying Rocq, or editing the proof script.
The role of these messages is to guide the agent’s control policy. Proof search often requires decisions that are not captured by the next tactic alone: whether a failed subgoal indicates a minor syntactic error, a wrong lemma application, an unhelpful case split, or a proof prefix that should be abandoned. By making this diagnosis explicit before each action, the agent maintains a running account of the proof attempt that conditions later decisions.
This mechanism is especially important for proof repair. When an edit fails or leads to an unproductive state, the agent can use its previous reasoning together with the new proof-state feedback to decide how much of the proof should be preserved. For example, it may conclude that only the last tactic should be replaced, that an earlier assertion was formulated incorrectly, or that the proof should restart from a previous case split. Continuous reasoning therefore supports not only tactic selection, but also the higher-level decision of where and how to revise the proof script.
This differs from systems where the model primarily emits isolated tactics, or where an external proof-search loop predetermines when to query the environment and when to backtrack, such as Rango [41] or PALM [26]. It also differs from AutoRocq, where reasoning is organized primarily around an explicit initial plan rather than a continuous rationale before each proof-editing action. In our setting, the model controls both the proof edits and the surrounding reasoning process. The resulting workflow resembles coding-agent repair: progress is made by repeatedly editing an artifact, observing the result, diagnosing the failure mode, and revising the artifact accordingly.
Experimental Setup
This section describes the experimental setup, including the research questions, benchmark, baselines, implementation and configurations, and stopping criteria.
Research Questions
To evaluate the effectiveness of ProofCoder on verification tasks, our evaluation answers three research questions:
RQ1. How does ProofCoder compare with the state of the art, and which design choices contribute most to its performance?
RQ2. How do different agentic configurations affect backtracking behavior during proof search?
RQ3. How do different proof generation granularity strategies compare in our setup?
Benchmarks
SV-COMP. We consider the SV-COMP dataset of the AutoRocq benchmark [42], consisting of verification lemmas generated from annotated C programs through a deductive-verification workflow. In the Frama-C ecosystem [20], these programs are typically specified in ACSL [5], and the resulting verification conditions can be discharged by automatic provers, for example through Why3 [11], or exported to interactive proof assistants when more expressive reasoning is required. Due to cost constraints, we select the 200 verification lemmas with the highest term count, one of the complexity metrics used by Tu et al. [42]. Their term counts range from 178 to 703, with a mean of 292.4 and a median of 265.5. Since no ground-truth proofs are available, the benchmark does not establish which lemmas are provable; however, 88 tasks in our subset were solved by AutoRocq or one of its baselines in the original evaluation. Thus, while provability is not established for the full subset, it retains most obligations known to be solvable by existing approaches and provides a challenging setting without being dominated by obligations for which no proof has yet been found.
Linux Kernel. We select 80 verification lemmas from Verker, a benchmark that formalizes functional correctness of Linux kernel code, used in AutoRocq’s own case study. As reported by Tu et al. [42], these lemmas are used to reason about the correctness of intricate program behaviors, and come from various source files, such as memory management (e.g., memmove) and utilities such as string operations (e.g., strcpy) and type conversion (e.g., hex2bin). In terms of complexity, these lemmas have term counts ranging from 29 to 549, with a mean of 178.66 and a median of 130.
Baselines
We compare ProofCoder against several existing theorem-proving systems, using AutoRocq [42] as our primary baseline because it is the state of the art in agentic Rocq-based software verification and the closest system to our approach. In its original evaluation, AutoRocq also compared against Rango [41], PALM [26], COPRA [39], Proverbot9001 [34], and QEDCartographer [35], outperforming these systems. We reuse these published baseline results to provide broader context, while focusing our new experiments on AutoRocq.
AutoRocq is an agentic loop with access to four tools: Plan, which allows it to generate a free-form plan for the proof, stored in the context; Query, to execute query commands like Search, Print and Locate; Tactic, used to generate tactics; and Rollback, used to delete a certain number of previously accepted steps. Rollback was not evaluated originally in [42], but the tool implementation was present in the replication package and early experiments showed that, with more recent models, it improved the performance. AutoRocq processes the proof script and proof state as a tree. Context retrieval, either by using query commands or by feeding proofs from history, is usually done at the beginning of a new state or after a certain number of failed attempts to generate a tactic.
AutoRocq was originally evaluated using gpt-4.1. We revisit this design choice by replacing it with the more recent models claude-sonnet-4-5 and gpt-4o.
As previously mentioned, one further challenge when evaluating theorem provers on AutoRocq benchmark is that ground-truth proofs are generally unavailable. Consequently, some obligations may be unprovable, or simply beyond the capabilities of current automated approaches. To account for this, the agent terminates a proof attempt when it determines that further search is unlikely to succeed. We refer to this behavior as give up. In order to save costs and ensure a fair comparison across approaches, we equip our agent with an equivalent mechanism in our evaluation.
Agent Implementation and Configurations
We implement ProofCoder as a thin integration layer on top of the OpenCode agent runtime [1], connected to Rocq through a custom Model Context Protocol (MCP) server of approximately 3,100 lines of Python. This separates agent orchestration, including reasoning, tool selection, and conversation management, from theorem-prover interaction, including script maintenance, replay, and goal reporting. The Rocq backend reuses AutoRocq’s CoqInterface, based on CoqPyt [7], coq-lsp [15], and Rocq 8.18, which the MCP server imports at runtime rather than reimplementing. We run our experiments across claude-sonnet-4.5 and gpt-6-sol both with temperature 0.
We define the following ProofCoder configurations, where WP and TL stand for, respectively, Whole Proof and Tactic-Level:
ProofCoder-WP: the agent generates multiple tactics per edit_proof call and is prompted to always try to complete the proof. It repairs proofs through the default behavior of edit_proof.
ProofCoder-TL: the agent generates one tactic per edit_proof call. It repairs proofs through the default behavior of edit_proof.
ProofCoder-TL-NoCR: an ablation that uses a plan tool instead of continuous reasoning between tool calls (tactic-level).
ProofCoder-TL-NoCR+Rollback: an ablation that more closely matches AutoRocq: the agent performs tactic-level generation, backtracks only through Rollback and produces no continuous reasoning between calls.
ProofCoder-WP-NoCR: uses a plan tool instead of continuous reasoning between tool calls (whole proof).
ProofCoder-WP-Reset: replaces localized backtrack with a deterministic reset that restarts the proof after every failed generation.
Stopping Criteria
Evaluating agentic provers can be computationally expensive, so we impose a fixed resource budget on each proof attempt. Limits were set on the basis of practical cost constraints and preliminary experiments, which showed diminishing improvements in proof success beyond these thresholds.
Our primary stopping criterion is a budget of 200k non-cached tokens. This metric is better suited to comparing agents with different proof-generation granularities than the number of tool calls, which would favor some configurations over others. Non-cached token usage provides a more consistent measure of the model usage required for a proof attempt.
We impose two secondary limits for edge cases. First, we cap total token usage at 5M tokens, since some tactic-level configurations can produce very long interactions while consuming relatively few non-cached tokens due to context reuse. Second, we set a 30-minute wall-clock timeout per verification lemma to prevent a small number of unusually expensive searches from dominating the evaluation time. These additional limits make the experiments predictable while having little impact on typical proof attempts.
Experimental Results
This section presents the experimental results and answers our research questions.
RQ1. How does ProofCoder compare with the state of the art, and which design choices contribute most to its performance?
Table 1 reports proof success on the SV-COMP lemmas, including our ProofCoder configurations, AutoRocq using the same models (claude-sonnet-4.5 and gpt-6-sol), and the baselines reported in the original AutoRocq evaluation. AutoRocq benefits substantially from the stronger model, improving from 86 to 94 solved lemmas when moving from claude-sonnet-4.5 to gpt-6-sol, which shows that its agentic design continues to benefit from advances in the underlying LLM. ProofCoder shows the same trend and, importantly, both of its configurations outperform AutoRocq with either model. With claude-sonnet-4.5, ProofCoder-WP proves 113 lemmas, 27 more than AutoRocq, a 31.4% relative improvement, while ProofCoder-TL proves 25 more. With gpt-6-sol, ProofCoder-WP and ProofCoder-TL prove 26 and 25 more lemmas than AutoRocq, respectively.
| System | Passed | Avg. cost (USD) | Avg. time (s) | Assert reachability | Signed int overflow | Loop invariant |
| Rango | 40 (20.0%) | — | — | 22 (44.9%) | 4 (13.3%) | 14 (11.6%) |
| PALM | 24 (12.0%) | — | — | 6 (12.2%) | 1 (3.3%) | 17 (14.0%) |
| QEDCartographer | 46 (23.0%) | — | — | 25 (51.0%) | 2 (6.7%) | 19 (15.7%) |
| Proverbot9001 | 56 (28.0%) | — | — | 24 (49.0%) | 2 (6.7%) | 30 (24.8%) |
| COPRA | 71 (35.5%) | — | — | 23 (46.9%) | 8 (26.7%) | 40 (33.1%) |
| AutoRocq (GPT-4.1) | 70 (35.0%) | — | — | 21 (42.9%) | 11 (36.7%) | 38 (31.4%) |
| AutoRocq (claude-sonnet-4.5) | 86 (43.0%) | 0.678 | 609 | 30 (61.2%) | 22 (73.3%) | 34 (28.1%) |
| Tactic-Level (claude-sonnet-4.5) | 111 (55.5%) | 0.516 | 747 | 31 (63.3%) | 22 (73.3%) | 58 (47.9%) |
| Whole-Proof (claude-sonnet-4.5) | 113 (56.5%) | 0.352 | 895 | 32 (65.3%) | 23 (76.7%) | 58 (47.9%) |
| AutoRocq (gpt-6-sol) | 94 (47.0%) | 0.177 | 475 | 29 (59.2%) | 20 (66.7%) | 45 (37.2%) |
| Tactic-Level (gpt-6-sol) | 119 (59.5%) | 0.090 | 230 | 33 (67.3%) | 25 (83.3%) | 61 (50.4%) |
| Whole-Proof (gpt-6-sol) | 120 (60.0%) | 0.084 | 229 | 34 (69.4%) | 25 (83.3%) | 61 (50.4%) |
Table 1. Pass rates, average cost, and average time on 200 SV-COMP lemmas. The last three columns are solved lemmas of each obligation type (49 assert reachability, 30 signed int overflow, and 121 loop invariant).
Furthermore, as shown in Figure 2a and Figure 2b, all verification lemmas proved by AutoRocq were also proved by at least one configuration of ProofCoder.

Figure 2. Overlap of verification lemmas proved by AutoRocq and ProofCoder.
Because the agentic systems substantially outperform the other baselines on SV-COMP, we compare our approaches exclusively with AutoRocq on Verker. In Table 2, we see a similar difference in performance between approaches, with ProofCoder-WP proving 38.8% and 60% of lemmas with claude-sonnet-4.5 and gpt-6-sol, respectively and ProofCoder-TL proving 42.5% and 57.5%. AutoRocq, on the other hand, proved 36.2% and 47.5%.
| System | Passed | Avg. cost (USD) | Avg. time (s) | Assert reachability | Loop invariant |
| AutoRocq (claude-sonnet-4.5) | 29 (36.2%) | 1.336 | 856 | 17 (32.1%) | 12 (44.4%) |
| Tactic-Level (claude-sonnet-4.5) | 34 (42.5%) | 1.177 | 727 | 23 (43.4%) | 11 (40.7%) |
| Whole-Proof (claude-sonnet-4.5) | 31 (38.8%) | 0.970 | 1007 | 22 (41.5%) | 9 (33.3%) |
| AutoRocq (gpt-6-sol) | 38 (47.5%) | 0.388 | 653 | 27 (50.9%) | 11 (40.7%) |
| Tactic-Level (gpt-6-sol) | 46 (57.5%) | 0.288 | 391 | 31 (58.5%) | 15 (55.6%) |
| Whole-Proof (gpt-6-sol) | 48 (60.0%) | 0.182 | 420 | 33 (62.3%) | 15 (55.6%) |
Table 2. Pass rates, average cost, and average time on 80 Verker lemmas. The last two columns are solved lemmas of each obligation type (53 assert and 27 loop invariant).
The Venn diagrams in Figure 2c and Figure 2d show that, although our approach outperforms AutoRocq, the two approaches do not solve exactly the same lemmas: a small number are proved exclusively by AutoRocq. This suggests that, on the more challenging Verker dataset, different agentic approaches can still succeed on different proof obligations, with our best configuration proving three AutoRocq-unsolved lemmas compared with one lemma solved exclusively by AutoRocq.
Cost and Time Analysis: Whole-Proof is the cheapest of the three systems, and AutoRocq is the most expensive. On SV-COMP with claude-sonnet-4.5, ProofCoder-WP ($0.352) costs about two-thirds as much as ProofCoder-TL ($0.516) and about half as much as AutoRocq ($0.678). gpt-6-sol the two agents are close: $0.084 against $0.090, both about half of AutoRocq ($0.177). On Verker, the Whole-Proof saving is larger for gpt-6-sol ($0.182 against $0.288 and $0.388) than for claude-sonnet-4.5 ($0.970 against $1.177 and $1.336).
Time does not follow cost. With claude-sonnet-4.5, ProofCoder-WP is the slowest configuration on both datasets (895 s on SV-COMP, 1007 s on Verker), while ProofCoder-TL is faster than Whole-Proof and, on Verker, faster than AutoRocq (727 s against 856 s). With gpt-6-sol the two agents take almost the same time, and both are faster than AutoRocq: about 230 s against 475 s on SV-COMP, and about 391–420 s against 653 s on Verker. Verker is the more expensive dataset for every system, at roughly two to three times the SV-COMP cost per lemma, reflecting the increase in difficulty for this dataset.
Verification Lemma Categories: The SV-COMP tasks fall into three categories: Assert Reachability (49 lemmas), Assert (RTE) Signed Overflow (30 lemmas), and Loop Invariants (121 lemmas). As shown in Table 1, ProofCoder’s gains over AutoRocq are concentrated on loop invariants. With claude-sonnet-4.5, AutoRocq solves 34 of these lemmas (28.1%), while ProofCoder-TL and ProofCoder-WP each solve 58 (47.9%). That increase of 24 lemmas is the whole net gain of Tactic-Level over AutoRocq (111 against 86) and 24 of Whole-Proof’s 27 additional proofs (113 against 86). On the other two categories claude-sonnet-4.5 AutoRocq is already close to the agents: 30 against 31 and 32 of the 49 assert-reachability lemmas, and 22 against 22 and 23 of the 30 signed-overflow lemmas. With gpt-6-sol the same concentration holds, above a stronger AutoRocq baseline. AutoRocq solves 45 loop invariants (37.2%), and both agents solve 61 (50.4%), which is 16 of the 25 and 26 extra proofs by ProofCoder-TL and ProofCoder-WP, respectively. The rest is split across the other categories: assert reachability rises from 29 to 33 and 34, and signed overflow from 20 to 25 for both agents.
Loop invariant lemmas are not substantially more complex by syntactic metrics, such as hypothesis count, term count, or statement length. They differ in proof structure, requiring reasoning about multiple memory snapshots, universally quantified array properties, map updates, and case distinctions over indices. This makes them a natural setting for agents that inspect intermediate proof states, reason continuously about the evolving context, and revise partially constructed proofs. Manual inspection suggests that ProofCoder’s advantage is not primarily due to discovering entirely new proof strategies. In more than half of the tasks solved only by ProofCoder, AutoRocq attempted the same key proof steps, such as unfolding Map.set, splitting on index equalities, or instantiating universally quantified hypotheses. The difference lies in execution: ProofCoder preserves promising prefixes, inspects previous states, and repairs localized failures, while AutoRocq often remains stuck in local repairs until eventually resetting the proof through rollback.
The Verker tasks fall into two categories, Assert Reachability (53 lemmas) and Loop Invariant (27), as shown in Table 2. Unlike SV-COMP, where ProofCoder’s gains are concentrated on Loop Invariant lemmas, the Verker results with claude-sonnet-4.5 are driven by Assert Reachability. AutoRocq solves 17 of 53 Assert Reachability lemmas (32.1%) and 12 of 27 Loop Invariant lemmas (44.4%), compared with 23 (43.4%) and 11 (40.7%) for ProofCoder-TL and 22 (41.5%) and 9 (33.3%) for ProofCoder-WP, respectively. Thus, the additional proofs obtained with claude-sonnet-4.5 come entirely from Assert Reachability, while both configurations solve fewer Loop Invariant lemmas than AutoRocq. With gpt-6-sol, however, the pattern changes: all three approaches improve on both categories, and both ProofCoder configurations surpass AutoRocq on Loop Invariants. AutoRocq solves 27 Assert Reachability lemmas (50.9%) and 11 Loop Invariant lemmas (40.7%), compared with 31 (58.5%) and 15 (55.6%) for ProofCoder-TL and 33 (62.3%) and 15 (55.6%) for ProofCoder-WP. This suggests that the relative advantage of ProofCoder depends not only on the proof category but also on the underlying model: the stronger model enables gains on Loop Invariants that are not observed with claude-sonnet-4.5 on this dataset.
Ablations. To better understand the impact of ProofCoder’s design choices, we evaluate the four ablation configurations described above using our best-performing model, gpt-6-sol. Table 3 summarizes the results. Removing continuous reasoning reduces performance while substantially increasing cost and runtime for gpt-6-sol. For ProofCoder-TL, performance drops from 119 to 115 solved lemmas on SV-COMP and from 46 to 40 on Verker, while cost more than doubles on both datasets and Verker runtime nearly doubles. ProofCoder-WP shows the same trend, dropping from 120 to 113 solved lemmas on SV-COMP and from 48 to 43 on Verker, with cost increasing by 55% and 79%, respectively. Replacing our backtrack with an explicit rollback tool to reasoning-free ProofCoder-TL has little effect on SV-COMP performance, which remains at 115 solved lemmas, while performance on Verker decreases to 35. These results are consistent with the hypothesis that the reasoning step helps the agent coordinate tool use and proof search. Replacing ProofCoder-WP’s localized repair with a full restart from the beginning on error leads to a much larger performance drop, from 120 to 81 solved SV-COMP lemmas and from 48 to 24 on Verker. The restart strategy also slightly increases SV-COMP cost from $0.084 to $0.192. This result is consistent with the hypothesis that preserving the existing proof and repairing the failing suffix is more effective than discarding the proof and restarting.
| Ablation | SV-COMP (200 lemmas) | Verker (80 lemmas) | ||||
| Passed | Avg. cost (USD) | Avg. time (s) | Passed | Avg. cost (USD) | Avg. time (s) | |
| TL-NoCR | 115 (57.5%) | 0.206 | 358 | 40 (50.0%) | 0.674 | 768 |
| TL-NoCR+Rollback | 115 (57.5%) | 0.154 | 339 | 35 (43.8%) | 0.689 | 646 |
| WP-NoCR | 113 (56.5%) | 0.130 | 301 | 43 (53.8%) | 0.326 | 653 |
| WP-Reset | 81 (40.5%) | 0.192 | 346 | 24 (30.0%) | 0.403 | 542 |
Table 3. ProofCoder ablations with gpt-6-sol: proof success, cost, and time on SV-COMP and Verker.
Overall, the ablation results show that continuous reasoning and localized repair are key to ProofCoder’s effectiveness: removing either reduces proof success, with localized repair having the larger impact.
Answer to RQ1: ProofCoder consistently outperforms the state of the art across both benchmarks and both models. On SV-COMP, every lemma proved by AutoRocq is also proved by at least one ProofCoder configuration. ProofCoder-WP improves over AutoRocq by 31.4% with claude-sonnet-4.5 and 27.7% with gpt-6-sol, while requiring roughly half the inference cost, with gains concentrated on loop-invariant lemmas. Whole-proof and tactic-level generation achieve similar success rates, with ProofCoder-WP generally offering the best success–cost trade-off. The ablations show that continuous reasoning and localized repair are key design choices: removing continuous reasoning lowers success while substantially increasing cost, whereas replacing localized repair with full restarts causes much larger performance drops. Replacing our backtracking mechanism with AutoRocq’s rollback tool does not improve performance.
RQ2. How do different agentic configurations affect backtracking behavior during proof search?
Backtracking lets agents revise accepted proof fragments rather than follow a monotonic tactic sequence, ranging from local repairs to broader exploration or full restarts. Its behavior depends on the interaction interface, including rollback mechanisms, editable proof scripts, and continuous reasoning. Effective backtracking therefore requires deciding which proof prefix to preserve and which suffix to discard. We compare backtracking across tactic-level approaches by analyzing backtrack depth and frequency, tactic replacement patterns, and the fraction of preserved revisions. We use the gpt-6-sol configuration of our agent and its ablations.
Backtrack depth and frequency. We define backtrack depth as the percentage of the current proof discarded by a backtrack, and backtrack frequency as the mean number of backtracks per task. Depth captures repair aggressiveness: higher values indicate larger discarded suffixes, while lower values indicate local edits near the end of the script.
Figure 3 shows substantial differences between approaches. The most pronounced effect of continuous reasoning is on frequency: ProofCoder-TL backtracks roughly 4–6× less often than both ablations (0.45 vs. 2.4 for ProofCoder-TL-NoCR and 3.05 for ProofCoder-TL-NoCR+Rollback on SV-COMP; 1.39 vs. 5.8 and 7.6 on Verker). Moreover, for the ablations, the frequency over all tasks is 2–5× as high than over successful tasks alone, indicating that heavy backtracking is characteristic of failing runs, whereas ProofCoder-TL shows only a small gap between the two. The approaches also differ in how they backtrack. Without reasoning, ProofCoder-TL-NoCR favors shallow, local edits (median depth ≈43% on SV-COMP and ≈22% on Verker), while ProofCoder-TL-NoCR+Rollback tends towards near-complete restarts on SV-COMP (median depth ≈90%) and, even in successful proofs, backtracks the most of the three variants. ProofCoder-TL sits between these extremes (median depth ≈67% on SV-COMP and ≈50% on Verker). This suggests that reasoning about a failure before acting lets the agent choose a single, appropriately placed resumption point, instead of repeatedly patching locally or discarding most of the proof.
Figure 3. Comparison of backtrack depth and frequency across tactic-level approaches.
Tactic replacement patterns. Table 4 and Table 5 report the five most frequently deleted tactics and their three most common replacements. Across tactic-level variants, intros is by far the most frequently deleted tactic. For ProofCoder-TL, it is replaced by intros in 92.3% of cases on SV-COMP and 89.7% on Verker. Removing continuous reasoning changes this substantially: ProofCoder-TL-NoCR retains intros in only 34.5% and 31.7% of cases, respectively, with replacements dispersed across tactics such as lia, pose, and idtac. This suggests that, without reasoning, the chosen resumption point does not always correspond to the proof decision the agent intends to revise.
| Deleted tactic | #1 | #2 | #3 | |
| ProofCoder-TL | ||||
| intros | 52 | intros (92.3%) | cbn (5.8%) | idtac (1.9%) |
| apply | 6 | apply (33.3%) | destruct (33.3%) | rewrite (16.7%) |
| eauto | 6 | congruence (33.3%) | exfalso (33.3%) | nia (16.7%) |
| destruct | 4 | specialize (50.0%) | assert (25.0%) | destruct (25.0%) |
| specialize | 3 | destruct (66.7%) | specialize (33.3%) | |
| ProofCoder-TL-NoCR+Rollback | ||||
| Deleted tactic | #1 | #2 | #3 | |
| intros | 337 | intros (89.9%) | intro (5.6%) | cbv (1.8%) |
| intro | 22 | intros (50.0%) | intro (13.6%) | cbn (9.1%) |
| destruct | 21 | assert (33.3%) | destruct (28.6%) | exfalso (14.3%) |
| assert | 16 | assert (37.5%) | destruct (37.5%) | exfalso (6.2%) |
| exfalso | 11 | pose (18.2%) | all (9.1%) | assert (9.1%) |
| ProofCoder-TL-NoCR | ||||
| Deleted tactic | #1 | #2 | #3 | |
| intros | 142 | intros (34.5%) | lia (10.6%) | pose (8.5%) |
| assert | 61 | assert (29.5%) | pose (14.8%) | destruct (13.1%) |
| destruct | 38 | assert (23.7%) | destruct (21.1%) | exfalso (13.2%) |
| pose | 37 | assert (27.0%) | clear (18.9%) | pose (13.5%) |
| idtac | 32 | idtac (21.9%) | clear (12.5%) | intros (12.5%) |
Table 4. Most frequently deleted tactics and their three most common replacements on SV-COMP.
| ProofCoder-TL | ||||
| Deleted tactic | #1 | #2 | #3 | |
| intros | 68 | intros (89.7%) | cbn (2.9%) | cbv (2.9%) |
| apply | 9 | apply (22.2%) | pose (22.2%) | eapply (11.1%) |
| eapply | 4 | apply (25.0%) | assert (25.0%) | destruct (25.0%) |
| assert | 3 | assert (66.7%) | destruct (33.3%) | |
| replace | 3 | eapply (33.3%) | rewrite (33.3%) | unfold (33.3%) |
| ProofCoder-TL-NoCR+Rollback | ||||
| Deleted tactic | #1 | #2 | #3 | |
| intros | 239 | intros (92.5%) | intro (3.8%) | cbv (2.1%) |
| assert | 74 | assert (48.6%) | pose (20.3%) | destruct (14.9%) |
| pose | 41 | pose (36.6%) | destruct (26.8%) | assert (17.1%) |
| destruct | 36 | destruct (30.6%) | assert (27.8%) | pose (25.0%) |
| intro | 17 | intro (64.7%) | intros (17.6%) | pose (17.6%) |
| ProofCoder-TL-NoCR | ||||
| Deleted tactic | #1 | #2 | #3 | |
| intros | 101 | intros (31.7%) | idtac (17.8%) | intro (6.9%) |
| assert | 68 | assert (22.1%) | apply (13.2%) | destruct (13.2%) |
| destruct | 50 | destruct (36.0%) | assert (16.0%) | apply (12.0%) |
| pose | 47 | clear (27.7%) | pose (14.9%) | apply (12.8%) |
| apply | 35 | apply (54.3%) | exact (17.1%) | destruct (8.6%) |
Table 5. Most frequently deleted tactics and their three most common replacements on Verker.
ProofCoder-TL-NoCR+Rollback shows a different pattern. It deletes intros much more often than either other variant (337 and 239 times on SV-COMP and Verker, compared with 142 and 101 for ProofCoder-TL-NoCR and 52 and 68 for ProofCoder-TL) and replaces it with intros or intro in over 95% of cases. This is consistent with rollback frequently discarding the proof setup, which the agent then reconstructs before diverging later. Beyond setup, ProofCoder-TL-NoCR+Rollback resembles ProofCoder-TL-NoCR, with dispersed revisions among tactics such as assert, destruct, pose, and exfalso.
Other frequently revised tactics include apply, assert, and destruct, which correspond to substantive proof decisions such as lemma selection, intermediate facts, and case decomposition. They are often replaced by the same or closely related tactics (e.g., apply by apply in 54.3% of cases for ProofCoder-TL-NoCR on Verker and assert by assert in 48.6% for ProofCoder-TL-NoCR+Rollback), suggesting that the agent often preserves the overall strategy while revising its realization. For ProofCoder-TL, however, deletions beyond intros are rare (), so these replacement distributions should be interpreted cautiously.
Overall, continuous reasoning primarily reduces how often revisions are needed: ProofCoder-TL performs far fewer deletions and largely preserves proof setup, whereas the reasoning-free variants revise more aggressively. Rollback stabilizes the setup only because it is repeatedly reconstructed after near-complete restarts.
Proof revision stability. We measure whether backtracks lead to stable proof revisions. A backtrack is preserved if the proof search following it is not entirely undone at the end of the run. If a backtrack resumes generation from index , it is preserved unless a later backtrack resumes from some index , thereby discarding the branch introduced after the original backtrack.
We compute preservation at the proof level: for each successful proof with at least one backtrack, we calculate the fraction of preserved backtracks, and then average these fractions across proofs:
with as the set of successful proofs with at least one backtrack. This is a retrospective measure of stability: discarded backtracks still have diagnostic value, but the metric captures whether a repair became part of the surviving search trajectory.
Figure 4 shows a consistent ordering on both benchmarks: ProofCoder-TL > ProofCoder-TL-NoCR > ProofCoder-TL-NoCR+Rollback. On SV-COMP, preservation drops from 88.7% to 65.0% without continuous reasoning and to 48.5% with rollback, while the distributions widen substantially (interquartile ranges 80–100%, 33–100%, and 21–67%, respectively). Verker shows the same ordering (77.6%, 72.0%, 68.2%), but with smaller differences and largely overlapping distributions. This complements the depth and frequency results: ProofCoder-TL-NoCR’s shallow backtracks are more often overridden by later revisions, whereas ProofCoder-TL-NoCR+Rollback’s near-complete restarts discard earlier revisions by construction. Since the final backtrack is always preserved, ProofCoder-TL’s higher rate also partly reflects its lower backtrack frequency. Overall, continuous reasoning reduces both the need for revision and the likelihood that revisions are later undone.
Figure 4. Backtrack preservation rate for the tactic-level ablations. Backtrack is considered preserved if the subsequent proof search is not entirely undone by the end of the run.
Answer to RQ2: Continuous reasoning substantially changes backtracking behavior, mainly by reducing the need for revision: ProofCoder-TL backtracks approximately 4–7× less often than its ablations, and the revisions it does make are rarely undone. Without continuous reasoning, the agent performs frequent shallow backtracks that are later overridden by deeper ones, suggesting that continuous reasoning helps identify which proof prefix should be retained and which should be discarded. The interaction model also influences recovery strategy: adding the rollback tool leads to the most frequent and least stable backtracks, often near-complete restarts, indicating that multiple revision mechanisms lead the agent to discard its own repairs rather than refine them. Finally, across configurations, backtracking most frequently revises proof setup, particularly intros, followed by tactics such as apply, assert, and destruct that make substantive changes to the proof state. This suggests that agents use backtracking to revise higher-level proof decisions rather than simply regenerate failed tactics.
RQ3. How do different proof generation granularities compare?
Prior work explores proof synthesis at different granularities, from tactic-level generation [34, 39, 41] [16] to whole-proof generation [25, 46] [14]. Tactic-level generation provides intermediate proof states for early error detection and adaptive search, while whole-proof generation reduces proof-assistant interactions. Direct comparison can be confounded by training-data contamination, as whole-proof generation may benefit from reproducing known proofs. AutoRocq benchmark mitigates this concern because its proof obligations have no ground-truth proofs available online. We therefore compare ProofCoder-TL and ProofCoder-WP within the same agent framework to isolate the effect of proof-generation granularity.
As discussed in RQ1 and shown in Table 1 and Table 2, whole-proof generation tends to achieve slightly better overall performance. We next compare both configurations in terms of tool calls and backtracking, proof length, and proof similarity.
Tool calls and backtracking. The tool-call traces show that ProofCoder-WP relies more heavily on explicit state inspection, particularly with gpt-6-sol. On SV-COMP, ProofCoder-WP and ProofCoder-TL make 567 and 521 check_state calls with claude-sonnet-4.5, but 206 and only 6 with gpt-6-sol. The same pattern holds on Verker, where the configurations make 203 vs. 107 calls with claude-sonnet-4.5 and 98 vs. 14 with gpt-6-sol. This reflects their different feedback granularity: ProofCoder-WP receives the proof state only after each generated fragment and therefore uses check_state to inspect intermediate states, whereas ProofCoder-TL receives the state after every tactic. The other context-retrieval actions remain broadly similar within each model: read_proof_file is comparable across configurations (131–148 with claude-sonnet-4.5; 184–189 with gpt-6-sol), while call_command is frequent for both and, on Verker, more frequent for ProofCoder-TL with gpt-6-sol (695 vs. 483).
Backtracking shows the same configuration- and model-dependent pattern. On SV-COMP, ProofCoder-WP backtracks on 70.0% of claude-sonnet-4.5 lemmas (140/200), with 5.35 backtracks on average, compared with 65.0% (130/200) and 3.69 for ProofCoder-TL; with gpt-6-sol, these rates fall to 58.5% and 26.5%, with means of 1.01 and 0.45, respectively. Verker exhibits more frequent backtracking overall: with claude-sonnet-4.5, the corresponding rates are 91.2% (73/80) and 86.2% (69/80), with means of 10.89 and 6.04; with gpt-6-sol, they are 68.8% and 51.2%, with means of 2.16 and 1.39. Thus, ProofCoder-WP consistently performs more explicit state inspections and backtracks than ProofCoder-TL, with both differences substantially larger for gpt-6-sol.
Proof length and similarity. Figure 5 compares proofs produced by ProofCoder-TL and ProofCoder-WP on lemmas solved by both configurations. This intersection contains 109 and 118 SV-COMP lemmas for claude-sonnet-4.5 and gpt-6-sol, respectively, and 28 and 45 Verker lemmas. Before computing Jaccard similarity, we remove comments and canonicalize introduced and generated variables, and numeric literals.
Figure 5. Comparison of length and similarity between proofs generated by ProofCoder-TL and ProofCoder-WP.
On SV-COMP, proofs are generally short and similar in length across configurations. With claude-sonnet-4.5, ProofCoder-WP and ProofCoder-TL average 14.7 and 12.9 tactics, respectively; with gpt-6-sol, they average 10.8 and 10.6. At least 93% contain 25 tactics or fewer, although ProofCoder-WP exhibits a somewhat longer tail. Proof similarity is moderate, with mean Jaccard scores of 0.41 for claude-sonnet-4.5 and 0.40 for gpt-6-sol. Only 3 and 8 proof pairs, respectively, are identical, indicating that the two configurations generally construct distinct proofs despite sharing many tactic steps.
On Verker, proofs are longer and the effect of granularity depends on the model. When using claude-sonnet-4.5, ProofCoder-WP averages 30.4 tactics compared with 20.8 for ProofCoder-TL; with gpt-6-sol, the pattern reverses, with averages of 16.7 and 23.8. Similarity is also lower than on SV-COMP, with mean Jaccard scores of 0.30 and 0.31 for claude-sonnet-4.5 and gpt-6-sol, respectively. Across both models, only two proofs are identical with gpt-6-sol.
Taken together, the results show no consistent advantage of either granularity in proof length, while the relatively low similarity indicates that granularity materially affects how proofs are constructed. Combined with the tool-call traces, this suggests different search and repair strategies: ProofCoder-WP relies more on explicit state inspection and backtracking, whereas ProofCoder-TL receives feedback after every tactic and therefore requires fewer explicit revisions.
Answer to RQ3: Whole-proof and tactic-level generation achieve similar proof success, differing by at most three lemmas per setting, with ProofCoder-WP ahead in three of four. Granularity mainly affects interaction behavior: as ProofCoder-WP receives feedback only after each generated fragment, it performs more explicit state inspections (by up to 34× with gpt-6-sol) and backtracks more often, while ProofCoder-TL receives the proof state after every tactic, requiring fewer explicit checks and revisions. Despite this, ProofCoder-WP is cheaper in all settings, as larger fragments require fewer model turns. On lemmas solved by both configurations, proofs have moderate tactic overlap (mean Jaccard 0.30–0.41), are rarely identical, and neither granularity consistently yields shorter proofs. Granularity has little effect on success rate but substantially shapes search, repair, and the resulting proof scripts.
Related Work
Deep learning has become prominent in theorem proving [19, 23, 24, 30, 34, 35, 39, 41, 42, 43, 44, 48, 49, 51, 52, 53] [4, 8, 12, 13, 14, 17, 18] and software verification [24, 27, 28, 31, 33, 36, 37, 38, 42, 45, 51, 54]. Recent work on automated theorem proving for software verification has particularly benefited from LLMs.
Rango [41] fine-tunes an LLM for tactic-level Rocq proof generation: at each step, the model receives proof-assistant context, relevant lemmas, and premises, and generates the next tactic. When a tactic fails, Rango recovers by restarting proof search from the beginning. COPRA [39] also performs tactic-level generation, prompting the model with the current proof state and additional context at each step. However, backtracking is controlled by an external depth-first search procedure: once the allowed attempts from a state are exhausted, the controller returns to an earlier proof state and asks the model for a different tactic. PALM [26] follows a generate-then-repair pipeline: retrieves relevant lemmas and definitions, prompts the LLM to generate a proof script, executes it, and applies symbolic repairs when errors occur. If repair fails, PALM backtracks and attempts to solve earlier goals using CoqHammer [9]. Cobblestone [18] uses a divide-and-conquer strategy. It executes LLM-generated proof scripts in a fail-safe mode, preserves the fragments accepted by Rocq, replaces failing parts with temporary admits, and recursively proves the remaining subgoals. The final assembled proof is accepted only after Rocq checking, often with support from tools such as CoqHammer. Baldur [14] explores whole-proof generation for Isabelle/HOL, using LLMs to produce complete proof scripts rather than individual tactics. When a proof fails, Baldur conditions a learned repair model on the failed script and proof-assistant error message to revise local mistakes. In these systems, the model is primarily invoked at a specific step to generate tactics, proof scripts, or proof
fragments, while search control, retrieval, and recovery are largely managed by the surrounding algorithm in a deterministic, yet more restrictive manner.
AutoRocq [42] is, to our knowledge, the state-of-the-art agentic approach for Rocq-based software verification and an important step toward more autonomous proof synthesis. It equips the LLM with tools for context retrieval, planning, tactic generation, and rollback, and shows that this agentic formulation can substantially outperform earlier approaches. AutoRocq nevertheless retains a structured interaction policy, with prompting that guides tool selection, limits repeated queries, and encourages particular actions in specific situations. ProofCoder proposes a less prescribed interaction model, allowing the agent to freely call and combine tools and to revise proofs through a compact editing and backtracking mechanism.
Threats to Validity
Construct validity. Comparing whole-proof and tactic-level approaches introduces inherent differences in resource consumption, as whole-proof generation typically requires fewer LLM calls. Using the number of LLM calls as the stopping criterion would therefore systematically favor whole-proof generation. To mitigate this threat, we use the total number of non-cached LLM tokens as the primary stopping criterion, providing a more comparable computational budget across approaches. We additionally impose maximum wall-clock time and total token-budget limits. Preliminary experiments showed that increasing these limits yielded only marginal improvements in proof success, suggesting that performance had largely saturated under the allocated resources.
Internal validity. Although both ProofCoder and AutoRocq are agentic theorem provers that interact with Rocq through CoqPyt, they use different agent frameworks. AutoRocq relies on LiteLLM [2], whereas ProofCoder is a thin integration layer over OpenCode. Consequently, framework differences in context management, conversation history, or tool-call serialization may influence performance. To mitigate this threat, we complement the comparison with an ablation study in which all ProofCoder variants use the same OpenCode-based infrastructure, isolating the impact of the proposed design choices.
External validity. Due to resource constraints, we do not evaluate on the full AutoRocq benchmark. Since there are no ground-truth proofs, evaluating every obligation would require spending a substantial fraction of the token budget on obligations that may not be provable. Instead, we evaluate the 200 SV-COMP obligations with the highest term complexity, yielding a challenging yet tractable subset. To ensure that this subset contains a substantial number of provable obligations, we confirmed that 88 were solved in the original AutoRocq evaluation by either AutoRocq or one of its baselines. Thus, our findings should be interpreted as evidence of ProofCoder’s effectiveness on this challenging subset rather than as a complete characterization of AutoRocq’s benchmark.
Conclusion
We presented ProofCoder, an agentic Rocq prover that advances the state of the art on challenging verification benchmarks while introducing a new perspective on LLM-based theorem proving. Our results demonstrate that the design of the agent interface is an important factor in proving performance. In particular, continuous reasoning and structured proof revision substantially improve an agent’s ability to recover from failed proof attempts. These findings suggest that LLM-based theorem provers should be designed not only around tactic generation, but also around feedback-driven proof repair. More broadly, our work indicates that continuous reasoning and robust backtracking policies are key ingredients for building effective agentic verification systems.
Future work includes evaluating these ideas on additional proof assistants and verification-aware languages, as well as exploring richer verifier interactions and collaborative multi-agent proof search.
Data Availability
We make all code, experimental scripts, and data publicly available: https://doi.org/10.5281/zenodo.21084811
Acknowledgments
This work was supported by national funds through Fundação para a Ciência e a Tecnologia, I.P. (FCT) under projects UID/50021/2025 (DOI: 10.54499/UID/50021/2025), UID/PRR/50021/2025 (DOI: UID/PRR/50021/2025), and co-funded by the European Union through the Lisboa 2030 Programme (ERDF) and by national funds through FCT, I.P., under project no. 15018 (project SafeIaC, DOI: 10.54499/2023.18089.ICDT). We thank Amazon Science for the Amazon Research Awards (Fall 2024), which enabled the experiments through access to AWS Bedrock.
References
- [19]Zhanna Kaufman, Emily First, Alex Sanchez-Stern, Kyle Thompson, Sorin Lerner, and Yuriy Brun. 2026. FooProof: Collaborative Automated Formal Verification. In Proceedings of the 48th International Conference on Software Engineering (ICSE). Rio de Janeiro, Brazil.DOI
- [20]Florent Kirchner, Nikolai Kosmatov, Virgile Prevosto, Julien Signoles, and Boris Yakobowski. 2015. Frama-C: A software analysis perspective. Formal aspects of computing 27, 3 (2015), 573–609.DOI
- [21]Gerwin Klein, Kevin Elphinstone, Gernot Heiser, June Andronick, David Cock, Philip Derrin, Dhammika Elkaduwe, Kai Engelhardt, Rafal Kolanski, Michael Norrish, et al. 2009. seL4: Formal verification of an OS kernel. In Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles. 207–220.
- [22]Xavier Leroy, Sandrine Blazy, Daniel Kästner, Bernhard Schommer, Markus Pister, and Christian Ferdinand. 2016. CompCert-a formally verified optimizing compiler. In ERTS 2016: Embedded Real Time Software and Systems. 8th European Congress.
- [23]Zhaoyu Li, Jialiang Sun, Logan Murphy, Qidong Su, Zenan Li, Xian Zhang, Kaiyu Yang, and Xujie Si. 2024. A Survey on Deep Learning for Theorem Proving. In First Conference on Language Modeling.arxiv.org/abs/2404.09939
- [24]Xiaohan Lin, Qingxing Cao, Yinya Huang, Haiming Wang, Jiangqiao Lu, Zhengying Liu, Linqi Song, and Xiaodan Liang. 2024. FVEL: Interactive Formal Verification Environment with Large Language Models via Theorem Proving. Advances in Neural Information Processing Systems 37 (2024), 54932–54946.arxiv.org/abs/2406.14408
- [25]Yong Lin, Shange Tang, Bohan Lyu, Jiayun Wu, Hongzhou Lin, Kaiyu Yang, Jia Li, Mengzhou Xia, Danqi Chen, Sanjeev Arora, et al. 2025. Goedel-prover: A frontier model for open-source automated theorem proving. arXiv preprint arXiv:2502.07640 (2025).arxiv.org/abs/2502.07640
- [26]Minghai Lu, Benjamin Delaware, and Tianyi Zhang. 2024. Proof automation with large language models. In Proceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering. 1509–1520.
- [27]Zhengxiang Luo, Huan Zhao, Dylan Wolff, Cristian Cadar, and Abhik Roychoudhury. 2026. Agentic Concolic Execution. In Proceedings of the IEEE Symposium on Security and Privacy (S&P). 1–19.
- [28]Lezhi Ma, Shangqing Liu, Yi Li, Xiaofei Xie, and Lei Bu. 2025. SpecGen: Automated Generation of Formal Program Specifications via large language models. In 2025 IEEE/ACM 47th International Conference on Software Engineering (ICSE). IEEE, 16–28.arxiv.org/abs/2401.08807
- [29]Gregory Malecha, Greg Morrisett, Avraham Shinnar, and Ryan Wisnesky. 2010. Toward a verified relational database management system. In Proceedings of the 37th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages. 237–248.
- [30]Maciej Mikula, Szymon Tworkowski, Szymon Antoniak, Bartosz Piotrowski, Qiaochu Jiang, Jin Zhou, Christian Szegedy, Łukasz Kucinski, Piotr Miłos, and Yuhuai Wu. 2024. Mangushammer: A transformer-based approach to premise selection. In International Conference on Learning Representations, Vol. 2024. 39326–39350.DOI
- [31]Md Rakib Hossain Misu, Cristina V Lopes, Iris Ma, and James Noble. 2024. Towards ai-assisted synthesis of verified dafny methods. Proceedings of the ACM on Software Engineering 1, FSE (2024), 812–835.
- [32]Talia Ringer, Karl Palmskog, Ilya Sergey, Glicoric Milos, and Zachary Tatlock. 2019. QED at large: A survey of engineering of formally verified software. Foundations and Trends in Programming Languages 5, 2-3 (2019), 102–281.
- [33]Haifeng Ruan, Yuntong Zhang, and Abhik Roychoudhury. 2025. Specrover: Code intent extraction via llms. In 2025 IEEE/ACM 47th International Conference on Software Engineering (ICSE). IEEE, 963–974.arxiv.org/abs/2408.02232
- [34]Alex Sanchez-Stern, Yousef Alhessi, Lawrence Saul, and Sorin Lerner. 2020. Generating correctness proofs with neural networks. In Proceedings of the 4th ACM SIGPLAN International Workshop on Machine Learning and Programming Languages. 1–10.
- [35]Alex Sanchez-Stern, Abhishek Varghese, Zhanna Kaufman, Dylan Zhang, Talia Ringer, and Yuriy Brun. 2025. QED-Cartographer: Automating formal verification using reward-free reinforcement learning. In 2025 IEEE/ACM 47th International Conference on Software Engineering (ICSE). IEEE, 307–320.
- [36]Melvin Sevenhuijsen, Khashayar Etemadi, and Mattias Nyberg. 2025. VecoGen: Automating Generation of Formally Verified C Code with Large Language Models. In 2025 IEEE/ACM 13th International Conference on Formal Methods in Software Engineering (FormaliSE). IEEE, 101–112.
- [37]Xujie Si, Hanjun Dai, Muyan Ruan, Mayur Naik, and Le Song. 2018. Learning loop invariants for program verification. Advances in Neural Information Processing Systems 31 (2018).
- [38]Xujie Si, Aaditya Naik, Hanjun Dai, Mayur Naik, and Le Song. 2020. Code2inv: A deep learning framework for program verification. In International Conference on Computer Aided Verification. Springer, 151–164.DOI
- [39]Amitayush Thakur, George Tsoukalas, Yeming Wen, Jimmy Xin, and Swarat Chaudhuri. 2024. An In-Context Learning Agent for Formal Theorem-Proving. In First Conference on Language Modeling.arxiv.org/abs/2310.04353
- [40]The Coq Development Team. 2017. Coq, v.8.7. https://coq.inria.fr.
- [41]Kyle Thompson, Nuno Saavedra, Pedro Carrott, Kevin Fisher, Alex Sanchez-Stern, Yuriy Brun, João F Ferreira, Sorin Lerner, and Emily First. 2025. QED: Adaptive Retrieval-Augmented Proving for Automated Software Verification. In 2025 IEEE/ACM 47th International Conference on Software Engineering (ICSE). IEEE, 347–359.arxiv.org/abs/2412.14063
- [42]Haoxin Tu, Huan Zhao, Yahui Song, Mehtab Zafar, Ruijie Meng, and Abhik Roychoudhury. 2026. Agentic Verification of Software Systems. Proc. ACM Softw. Eng. 3, FSE (2026). doi:10.1145/3808164DOI
- [43]Haiming Wang, Huajian Xin, Zhengying Liu, Wenda Li, Yinya Huang, Jianqiao Lu, Zhicheng Yang, Jing Tang, Jian Yin, Zhenguo Li, et al. 2024. Proving theorems recursively. Advances in Neural Information Processing Systems 37 (2024), 86720–86748.arxiv.org/abs/2405.14414
- [44]Haiming Wang, Huajian Xin, Chuanyang Zheng, Zhengying Liu, Qingxing Cao, Yinya Huang, Jing Xiong, Han Shi, Enze Xie, Jian Yin, et al. 2024. Lego-prover: Neural theorem proving with growing libraries. In International Conference on Learning Representations, Vol. 2024. 31566–31597.arxiv.org/abs/2310.00656
- [45]Guangyuan Wu, Weining Cao, Yuan Yao, Hengfeng Wei, Taolue Chen, and Xiaoxiao Ma. 2024. LLM Meets Bounded Model Checking: Neuro-Symbolic Loop Invariant Inference. In Proceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering. 406–417.DOI
- [46]Huajian Xin, ZZ Ren, Junxiao Song, Zhihong Shao, Wanjia Zhao, Haocheng Wang, Bo Liu, Liyue Zhang, Xuan Lu, Qiushi Du, et al. 2025. Deepseek-Prover-v1. 5: Harnessing proof assistant feedback for reinforcement learning and monte-carlo tree search. In International Conference on Learning Representations, Vol. 2025. 72724–72303.arxiv.org/abs/2408.08152
- [47]John Yang, Carlos Jimenez, Alexander Wettig, Kilian Lieriet, Shunyu Yao, Karthik Narasimhan, and Ofir Press. 2024. SWE-agent: Agent-computer interfaces enable automated software engineering. Advances in Neural Information Processing Systems 37 (2024), 50528–50652.arxiv.org/abs/2405.15793
- [48]Kaiyu Yang and Jia Deng. 2019. Learning to prove theorems via interacting with proof assistants. In International Conference on Machine Learning. PMLR, 6984–6994.arxiv.org/abs/1905.09381
- [49]Kaiyu Yang, Aidan Swope, Alex Gu, Rahul Chalamala, Peiyang Song, Shixing Yu, Saad Godil, Ryan J Prenger, and Animashree Anandkumar. 2023. LeanDojo: Theorem proving with retrieval-augmented language models. Advances in Neural Information Processing Systems 36 (2023), 21753–21612.arxiv.org/abs/2306.15626
- [50]Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izzhak Shafran, Karthik R. Narasimhan, and Yuan Cao. 2023. ReAct: Synergizing Reasoning and Acting in Language Models. In ICLR. OpenReview.net. http://dblp.uni-trier.de/db/conf/iclr/iclr2023.html#YaoZYDSN023arxiv.org/abs/2210.03629
- [51]Huan Zhao, Haoxin Tu, Zhengyao Liu, Martin Rinard, and Abhik Roychoudhury. 2026. Lemma Discovery in Agentic Program Verification. arXiv preprint arXiv:2603.22114 (2026).DOI
- [52]Xueliang Zhao, Wenda Li, and Lingpeng Kong. 2024. Subgoal-based demonstration learning for formal theorem proving. In Forty-first International Conference on Machine Learning.
- [53]Chuanyang Zheng, Haiming Wang, Enze Xie, Zhengying Liu, Jiankai Sun, Huajian Xin, Jianhao Shen, Zhenguo Li, and Yu Li. 2023. Lyra: Orchestrating dual correction in automated theorem proving. arXiv preprint arXiv:2309.15806 (2023).arxiv.org/abs/2309.15806
- [54]Xinyue Zuo, Yifan Zhang, Hongshu Wang, Yufan Cai, Zhe Hou, Jing Sun, and Jin Song Dong. 2025. PAT-Agent: Autoformalization for Model Checking. In 2025 40th IEEE/ACM International Conference on Automated Software Engineering (ASE). IEEE, 2122–2133.