Curriculum proof repair with learned counterexamples

Yuechun Sun, Jun Yang, Kexin PeiarXiv 2026 · arXiv

TL;DR

TopoVerus is a new framework that transforms automated formal proof repair from a "trial-and-error" process into a structured diagnostic pipeline. By training language models to generate their own source-level counterexamples and rewarding them for following a logical "topological" order of proof dependencies, it significantly outperforms state-of-the-art models like Claude 3.5 Sonnet in verifying Rust code.

What Problem Does This Paper Address?

Formal verification—the process of using mathematical proofs to guarantee software correctness—is a "holy grail" for security-critical systems. However, writing these proofs is notoriously difficult. When a proof fails, the verifier (like the Rust-based Verus) often provides only a cryptic "binary" signal: Pass or Fail.

For a developer (or an AI), a simple "postcondition not satisfied" error offers little guidance on why the proof failed. While counterexamples (concrete program states that trigger the failure) are much more helpful, they are computationally expensive to generate and refine. Furthermore, proofs have a hidden structure: you often can't prove a complex property about an array's contents until you've first proven that your array indices are within bounds. If an AI tries to fix a high-level property while the foundational bounds are still broken, it ends up chasing "hallucinated" errors.

Methods

The authors present TopoVerus, which internalizes counterexample generation as a core model capability. Instead of treating counterexamples as a separate validation task, they treat them as a data-driven diagnostic objective: a counterexample is "good" if it helps the model successfully repair the proof.

Key components include:

  1. Structured Trajectory: In a single pass, the model generates a <think> block, a <counterexample> (State, Execution Trace, and Violation), a <reasoning> repair plan, and finally the repaired code.
  2. Topological Graph Reward ($R_{dep}$): This is the paper's primary innovation. The authors pre-compute a dependency graph of invariants (e.g., Invariant A must be true for Invariant B to be provable). During Reinforcement Learning (using GRPO), the model is rewarded not just for passing the verifier, but for establishing prerequisite invariants before dependent ones.
  3. Safety Gate: To prevent the model from "cheating" by changing the actual program logic to make the proof pass, they use an AST-level checker called Lynette. This ensures only "ghost code" (proof annotations) is modified.
Figure 2: Comparison of dependency-unaware (top) and dependency-aware (bottom) diagnostics.

Datasets

The model was evaluated on 471 problems across seven diverse Verus benchmarks:

  • VerusBench & DafnyBench: General verification tasks.
  • HumanEval & LeetCode: Algorithmic problems.
  • VeriCogen: Proof-stripped variants of HumanEval.
  • ObfsBench: Problems with obfuscated variable names to test reasoning over memorization.
  • VeruSAGE: Complex systems-level tasks (e.g., memory allocators, OS kernels).

Key Insights and Ideas

  • Actionability > Validity: The authors argue that a counterexample doesn't need to be a mathematically perfect formal certificate to be useful. As long as it provides an "actionable signal" that helps the model find the right fix, it serves its purpose.
  • The Micro-Curriculum: By rewarding the model for following the topological order of invariants, they induce a "micro-curriculum" within every single repair attempt. This forces the model to build a robust logical foundation before tackling complex semantic properties.
  • Transferable Diagnostics: Surprisingly, the counterexamples generated by TopoVerus are so high-quality that they can be used to "boost" other models. When TopoVerus's diagnostics were fed to models like DeepSeek or Claude, their repair success rates jumped by up to 64%.

Key Results

TopoVerus (based on a 32B parameter model) achieved a 61.6% weighted-average Safe-Pass@1, outperforming Claude 3.5 Sonnet by 5.7 points.

The gains were most dramatic on ObfsBench, where the model cannot rely on familiar variable names or "memorized" proof templates. Here, TopoVerus reached 69.9% success, beating Sonnet by nearly 8 points. The ablation studies showed that the topological reward alone improved performance by 7.9 points over standard binary reinforcement learning.

Scaling performance of TopoVerus compared to baselines.

Limitations and Future Work

  • Loop Invariant Focus: The current dependency-aware curriculum is primarily designed for loop invariants. Extending this to complex assertions and inter-procedural proofs is a clear next step.
  • Hallucination Risks: Because the model is optimized for repair success rather than absolute mathematical validity of the counterexample, it may occasionally hallucinate execution traces that are "plausible" but technically incorrect.
  • Generalization: While highly effective for Verus/Rust, the framework's reliance on pre-computed dependency graphs means it requires some offline preprocessing for new languages or verification tools.

Summary updated

Abstract

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.
BibTeX
@misc{sun2026curriculum,
  author = {Yuechun Sun and Jun Yang and Kexin Pei},
  title = {{Curriculum proof repair with learned counterexamples}},
  year = {2026},
  eprint = {2611.13627},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.13627},
}
Figure