TL;DR
Automated loop invariant synthesis is essential for formal program verification, but existing LLM evaluations rely on unsound heuristics or narrow benchmarks. InvBench introduces a sound, verifier-based evaluation calculus that tests whether LLM-generated invariants actually accelerate verification against state-of-the-art symbolic solvers like UAutomizer. The findings reveal that while frontier models can occasionally accelerate easy problems, traditional solvers still dominate overall, though supervised fine-tuning and Best-of-$N$ sampling substantially boost LLM utility.
What Problem Does This Paper Address?
Loop invariants—logical predicates that hold true across every iteration of a loop—are fundamental for proving software safety assertions using Hoare logic. However, discovering loop invariants is undecidable in general.
While recent work explores large language models (LLMs) for invariant synthesis, prior evaluation approaches suffer from two core limitations:
- Unsound and syntactically fragile evaluation: Pioneering studies compared LLM invariants against dynamic analysis tools like Daikon, which infer properties from runtime tests rather than formal mathematical proofs, often rejecting logically equivalent invariants while accepting unsound ones.
- Ignoring verification utility (speedup): A proposed invariant can be trivially "correct" (e.g., $x > 0$) without being strong enough to discharge the target assertion. Worse, poorly formulated invariants can increase the symbolic solver's computational burden rather than reducing it.
Furthermore, existing neuro-symbolic verifiers (e.g., LEMUR, Loopy, LaM4Inv) were evaluated only on custom, non-standardized benchmarks, making cross-comparison difficult.
Methods
The authors propose InvBench, a sound verification pipeline and evaluation protocol:
- Verifier-Based Decision Procedure: Given program $P$, target property $p^*$, and LLM candidate invariant $q$, the framework issues two parallel queries to a sound verifier:
- $d_a = V(P, \emptyset, q)$: Is $q$ an invariant across all executions?
- $d_b = V(P, \{q\}, p^*)$: Does $p^*$ hold when assuming $q$?
- Sound Proof Calculus: A candidate can definitively refute the property (
DEC-FALSE), prove the property if the invariant is sound (DEC-PROP), or return inconclusive (DEC-U) in case of timeouts. The authors prove this decision procedure is sound. - End-to-End Speedup Metric: Instead of checking syntactic overlap, InvBench measures the runtime speedup relative to the standalone traditional solver UAutomizer, explicitly factoring in LLM token generation time.
- Inference & Training Enhancements: The authors explore Low-Rank Adaptation (LoRA) fine-tuning and parallel Best-of-$N$ sampling ($N=16$) to evaluate whether test-time compute and domain adaptation improve invariant generation.
Datasets
- InvBench Evaluation Benchmark: 226 C programs drawn from SV-COMP 2025 split evenly into:
- Easy split (113 instances): Solved by UAutomizer alone within 30 seconds.
- Hard split (113 instances): Solved by UAutomizer between 30 and 600 seconds.
- Unlike previous benchmark datasets (average 22–27 lines of code), InvBench programs average 51–62 lines and include complex structures like nested loops, arrays, and pointer manipulation.
- Synthetic Fine-Tuning Corpus: 3,589 compilable, valid C programs generated by prompting GPT-4o using few-shot SV-COMP seeds disjoint from the evaluation set. Each program is paired with invariants automatically extracted from UAutomizer runs.
- Existing Custom Benchmarks: Evaluated UAutomizer directly against the proprietary benchmarks from LaM4Inv (316 instances), Loopy (469 instances), and LEMUR (47 instances).
Key Insights and Ideas
- Correctness $\neq$ Utility: Generating a valid invariant is far easier than generating a strong invariant. Across models, there is a massive drop-off between the percentage of verified-correct invariants and the percentage that actually yield an execution speedup.
- LLMs Struggle with Solver Ergonomics: Detailed failure analysis shows that the most common failure mode is "Assume + Assert Timeout"—the invariant is so poorly structured that the symbolic solver times out trying to verify both the invariant itself and the downstream goal. LLMs currently lack an internal model of what makes a formula easy for an SMT solver to check.
- Traditional Solvers Are Still SOTA: The non-LLM baseline, UAutomizer, out-verified prior LLM-based systems (LaM4Inv and Loopy) even on those systems' own datasets. LEMUR only outperformed UAutomizer because its dataset was curated exclusively from problems UAutomizer failed.
Key Results
- Zero-Shot Base Performance:
- On the Easy Split, OpenAI's
o3led all models, generating correct invariants on 39.8% of problems and accelerating verification on 28.3% of cases (averaging $1.37\times$ speedup on accelerated runs, $1.09\times$ overall). - On the Hard Split, zero-shot LLM performance collapsed: almost all models achieved a 0% speedup rate, with rare outliers (e.g.,
gpt-oss-120baccelerated one problem by $29.57\times$). - Supervised Fine-Tuning:
- On the Easy Split, fine-tuning Qwen3-Coder-480B increased correct invariants from 14.2% to 40.7% and the speedup frequency from 8.0% to 29.2% ($1.29\times$ speedup on accelerated cases).
- Best-of-$N$ Sampling ($N=16$):
- On the Easy Split, Best-of-16 boosted
claude-sonnet-4's speedup rate from 8.8% to 22.1% ando3's speedup rate to 35.4% (50.4% correct invariants).
Limitations and Future Work
- The Hard Split Remains an Open Challenge: Fine-tuning on the synthetic dataset yielded no noticeable performance gains on the hard benchmark split, indicating that complex loop control and memory-heavy programs require fundamentally better reasoning.
- Inference Latency Overhead: While the speedup calculation accounts for model generation latency, running large models (or Best-of-16 sampling) introduces substantial compute requirements.
- Future Direction — Solver-Aware Reward Models: Future work must move beyond pure code generation by training reward models or verifier-guided critics that help LLMs internalize SMT solver difficulty, ensuring proposed invariants break proofs into strictly simpler sub-goals.
Summary updated