Language models (LMs) have substantially lowered the barrier to applying formal verification for building reliable and secure software. Existing approaches commonly follow the verifier-in-the-loop paradigm, but the verifier often provides only coarse, binary pass/fail feedback, which offers little actionable signal on how the proof should be repaired. Recent work shows that counterexamples provide more actionable feedback by grounding proof failures in concrete program states, but generating useful ones at inference time requires costly iterative refinement. We present TopoVerus, an LM-based framework for Verus proof repair that internalizes counterexample-guided diagnosis as a model capability, producing useful counterexamples in a single pass. Our key insight is to train counterexample generation not as a standalone validation task, but as a data-driven diagnostic objective: a counterexample is useful when conditioning on it helps the model produce a safe, verifier-passing proof. Given a failed Verus proof and verifier error, TopoVerus generates a structured source-level counterexample, repair rationale, and repaired proof in one trajectory, optimized with reinforcement learning from Verus feedback and a proof-code safety gate. To guide the order of invariant repairs, TopoVerus introduces a curriculum with a topological graph reward based on invariant dependencies derived from inductiveness tests, which encourages counterexample generation to follow the same topological order. Across seven Verus benchmarks with 471 problems, TopoVerus achieves 61.6%/72.2% weighted-average Safe-Pass@1/Safe-Pass@3, outperforming the strongest baseline, Claude Sonnet 4.5, by 5.7/6.3 points. We also show that TopoVerus's learned counterexamples can directly augment the reasoning of existing LM-based proof repair approaches, improving their success rate by 64.3% compared to chain-of-thought diagnostics.
Figures & tables
Figure 2: Comparison of dependency-unaware (top) and dependency-aware (bottom) diagnostics.
Approach
VerusBench
DafnyBench
HumanEval
Leetcode
VeriCogen
ObfsBench
VeruSAGE
k=1
k=3
k=1
k=3
k=1
k=3
k=1
k=3
k=1
k=3
k=1
k=3
k=1
k=3
Cloud LLMs
Sonnet-4.5
73.1
84.6
70.6
76.5
13.3
13.3
40.0
40.0
26.7
30.0
62.0
75.2
75.5
84.9
GPT-4o
42.3
42.3
76.5
76.5
6.7
13.3
0.0
0.0
40.4
41.4
21.8
22.9
17.0
24.5
Qwen3-Coder
34.6
34.6
52.9
52.9
6.7
6.7
0.0
0.0
20.0
25.6
14.3
18.8
45.3
64.2
DeepSeek-V4
23.1
38.5
47.1
82.4
13.3
20.0
0.0
0.0
28.9
36.7
12.8
29.3
58.5
66.0
Table 1: Overall verification repair safe pass rates. Each cell reports Safe-Pass@ k (%) across seven benchmarks. Cloud LLMs use iterative repair with verifier feedback; our models use 3 chains × 10 iterations. A solution is safe if Lynette confirms only ghost (proof) code changed.
CEX source
DeepSeek
Sonnet
Qwen
CoT-Init
11.9%
31.4%
13.6%
CTX-Init
15.3% (+28.6%)
32.2% (+2.7%)
12.7% (-6.2%)
CTX-Binary
19.5% (+64.3%)
33.1% (+5.4%)
15.3% (+12.5%)
CTX-Dep
19.5% (+64.3%)
39.0% (+24.3%)
15.3% (+12.5%)
Table 2: Counterexample usability on 118 hard failed states. Cells report frozen-repair success; colored deltas are relative changes over CoT-Init.
Figure 3: Safe test-time scaling. The sample-scaling panel reports Safe Pass@ K as the number of chains increases, while the iteration-scaling panel reports Safe Pass@1 as the repair budget increases.
Figure 4: Maximum-profit case study: buggy proof, Verus feedback, and generated counterexample.
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Dataset
Files
n (mean)
Calls (total)
Naive (total)
Reduction
Est. time
Dafnybench
55
1.9
205
205
1.0 ×
1.4 min
HumanEval-Alphaverus
47
3.4
1,135
2,669
2.4 ×
7.9 min
LeetCode
23
6.6
2,817
72,955
25.9 ×
19.7 min
Obfuscated-VerusBench
266
3.0
3,498
3,498
1.0 ×
24.5 min
cleaned-VerusBench
140
2.7
1,561
1,816
1.2 ×
10.9 min
Total
531
3.0
9,216
81,143
8.8 ×
≈ 64 min
Appendix
Table 3: Preprocessing statistics per dataset. “Calls” = actual verifier invocations (total). “Naive” = calls without the budget cap ( 2n−1 per file, summed). “Reduction” = Naive / Calls. “Est. time” assumes 0.42 s per Verus call (measured mean on our hardware; range 0.25–0.71 s).
Micro average
Macro average
Method
Safe-Pass@1
Safe-Pass@3
Safe-Pass@1
Safe-Pass@3
Sonnet-4.5
55.9
65.9
51.6
57.8
CTX-Binary
53.7
67.9
51.0
61.4
CTX-Dep
61.6
72.2
54.0
61.5
Appendix
Table 4: Micro- and macro-averaged Safe-Pass (%) over the 471 evaluation problems in seven benchmark suites. Micro averaging gives each problem equal weight; macro averaging gives each suite equal weight.
Iterations
CTX-Binary
CTX-Dep
Difference
1
47.6
47.6
0.0
2
49.2
55.6
+6.4
4
57.1
60.3
+3.2
8
61.9
63.5
+1.6
16
68.3
69.8
+1.5
32
68.3
69.8
+1.5
Appendix
Table 5: Safe-Pass@1 (%) under iteration scaling on the 63-task subset. Differences are CTX-Dep minus CTX-Binary in percentage points, computed from the displayed percentages.
Benchmark
Ghost unique
Ghost rate
Ghost distance
Four in-distribution benchmarks
2.524 / 2.357
84.9% / 79.4%
0.058 / 0.040
VeriCogen
2.522 / 2.217
94.2% / 88.4%
0.388 / 0.316
ObfsBench
2.618 / 2.640
96.9% / 93.9%
0.072 / 0.067
VeruSAGE
1.667 / 1.667
72.2% / 66.7%
0.220 / 0.202
Appendix
Table 6: Diversity of proof-only signatures among paired safe verified repairs from the 471-task evaluation. Each cell reports CTX-Binary / CTX-Dep; each metric is averaged over the paired eligible tasks in its benchmark group.
Metric
CTX-Binary
CTX-Dep
Difference
Mean invariant coverage, α
98.6%
98.5%
−0.1 pp
Mean edge satisfaction, β
43.8%
95.8%
+52.1 pp
Tasks with full edge satisfaction, β=1
10/24 (41.7%)
23/24 (95.8%)
+54.2 pp
Mean topology score, αβ
0.424
0.943
+0.519
Appendix
Table 7: Invariant coverage and dependency ordering on 24 paired tasks accepted by Verus, using the post-hoc diagnostic matcher. Differences are CTX-Dep minus CTX-Binary, computed before rounding; “pp” denotes percentage points.
Large Language Models (LLMs) have shown promising results in automating formal verification. However, existing approaches treat proof generation as a static, end-to-end prediction over source code, relying on limited verifier feedback and lacking access to concrete program behaviors. We present EXVERUS, a counterexample-guided framework that enables LLMs to reason about proofs using behavioral feedback via counterexamples. When a proof fails, EXVERUS automatically generates and validates counterexamples, and then guides the LLM to generalize them into inductive invariants to block these failures. Our evaluation shows that EXVERUS significantly improves proof accuracy, robustness, and token efficiency over the state-of-the-art prompting-based Verus proof generator.
Jun Yang, Yuechun Sun, Yi Wu +5
The University of Chicago · Purdue University · The University of Toronto +1
Automated formal verification remains challenging for large language models because data for proof assistants and verification-aware languages is scarce, and correctness depends on satisfying precise machine-checkable specifications rather than producing plausible code. This thesis studies how verifier environments can improve LLM generation of verified programs and proofs through reinforcement learning from verifiable rewards (RLVR) and verifier-guided inference-time search. First, we train open-source models in Dafny with RLVR using Group Relative Policy Optimization (GRPO) and related variants, assembling generated candidates into complete programs and scoring them with compiler and verifier outcomes. Initial experiments on an APPS-derived Dafny dataset increased verified reward from 2.2% to 58.1%, but revealed specification hacking, where models exploit weak formal specifications instead of implementing the intended solutions. After filtering underspecified and vulnerable tasks, multi-turn RLVR on the refined benchmark improves the verified pass rate from 9.7% to 31.1%. Second, we develop a verifier-guided inference scaffold in Lean that treats proof generation as structured search over decomposed subgoals, verifier feedback, diagnostics, and repair. With a fixed base model, the full scaffold with proof reviser improves pass rate on an initial VeriCoding pilot set from 46.2% under direct repair to 69.2%. On the larger VERINA dataset, whole-task decomposition plus proof reviser solves 7 of 42 previously unsolved tasks. We also introduce Dalek-Bench, a repository-scale Lean benchmark derived from the Rust curve25519-dalek verification project; preliminary results remain weak, indicating that stronger progress evaluation and task-specific tool-use policies are still needed.
Max Tan
Department of Electrical Engineering and Computer Science · Massachusetts Institute of Technology
Verifier-guided self-repair conditions a model on feedback from failed attempts before it tries again, without weight updates. Yet two findings in prior work are in tension: verifier feedback can improve repair of failures, but self-repair itself can provide little-to-no advantage over independent resampling. We reconcile these findings in Lean theorem proving through controlled one-step experiments that hold the preceding failure fixed while varying whether the failed proof is shown, whether the compiler error corresponds to that failure, and the retry instruction. We test frozen Qwen3.6-27B, a general-purpose model, and DeepSeek-Prover-V2-7B, a specialized prover, on difficult MiniF2F problems. We find two opposing effects. Showing the model its failed predecessor reduces success and sharply increases copying of it, while on Qwen adding that attempt's compiler error recovers the loss, to the level of the diagnostic alone. Replacing the predecessor with another theorem's failed proof largely removes the degradation on both models; on Qwen, replacing the diagnostic with another problem's error substantially reduces the recovery. Without the failed proof, correct diagnostics show no resolved advantage over wrong-diagnostic controls on either model. The failed-proof penalty persists with and without the retry instruction, whereas Qwen's diagnostic recovery is weaker without it. In 11-problem sequential experiments through 64 attempts, Qwen retains a correct-diagnostic benefit within failed-proof histories, while DeepSeek-Prover shows no resolved recovery. However, no tested one-step feedback condition establishes an advantage over instruction-only resampling, nor does 64-attempt sequential repair with failed proofs and correct diagnostics at equal token budgets. Verifier feedback can thus improve repair without overcoming the performance loss from conditioning on a failed attempt.
Jack Li, Sophia Li
Department of Computer Science, Stanford University