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