TL;DR
Quokka is a new framework that uses Large Language Models (LLMs) to automatically synthesize loop invariants—the "missing links" needed to prove programs are correct. By moving away from complex post-processing and adopting a simple, parallel "verify-and-use" approach, Quokka achieves state-of-the-art performance on the largest and most complex verification benchmark to date.
What Problem Does This Paper Address?
Formal program verification is the process of mathematically proving that a piece of software behaves exactly as intended. This is critical for safety-sensitive systems (like flight controllers or medical devices), but it has a major bottleneck: loops.
To prove a loop is correct, you need a loop invariant—a logical statement that remains true before, during, and after every iteration. Finding these invariants is a "long-standing challenge" because they must be both correct (always true) and strong (useful enough to actually prove the final goal).
Prior attempts to use LLMs for this task suffered from two main issues:
- Unsound Evaluation: Some compared LLM outputs to dynamic analysis tools, which can be wrong themselves.
- Over-Engineering: Many frameworks treated LLM output as "noisy" material that needed complex, slow algorithmic "repair" or "reassembly" before it could be used.
Methods
The authors introduce Quokka, a framework that shifts the focus from "fixing" LLM output to "directly evaluating" it.
The core of Quokka is its Evaluation-Centric Design:
- Direct Validation: Instead of complex post-processing, Quokka takes an LLM-generated invariant and immediately asks a formal verifier (like UAutomizer) two questions in parallel:
- Query A ($d_a$): Is this a valid invariant for this loop?
- Query B ($d_b$): If we assume this is true, can we prove the final program assertion?
- Parallelism: By running these queries at the same time, Quokka reduces latency and identifies useful invariants faster.
- Best-of-N Sampling: Quokka generates multiple candidate invariants and selects the one that leads to the fastest verification time.
- Supervised Fine-Tuning (SFT): The team fine-tuned models (like Qwen2.5-7B) on a custom dataset of successful invariants to improve their "intuition" for what a strong invariant looks like.
Datasets
The researchers significantly raised the bar for evaluation:
- The Quokka Benchmark: They constructed a dataset of 866 instances derived from the SV-COMP (Software Verification Competition). Unlike previous datasets, these programs are longer (avg. 52 lines) and include complex features like multiple loops, pointers, and arrays.
- Synthetic Training Data: To train their models, they used GPT-4o to generate 3,589 synthetic C programs and used a formal verifier to extract "ground truth" invariants for them.
Key Insights and Ideas
- Simplicity is a Feature: As LLMs get smarter, we don't need "harness-heavy" designs to rescue bad outputs. Quokka proves that a "focused approach"—asking the LLM to commit to one location and one invariant—is more effective than exhaustive search.
- The Strength Gap: The authors found that LLMs are actually quite good at generating correct invariants, but often fail because those invariants are weak (e.g., they just restate the obvious or provide trivial bounds).
- Scaling Test-Time Compute: Using Best-of-N sampling (specifically N=8) provided a massive boost in performance, showing that simply giving the model more "tries" is a highly effective strategy for verification.
- Verification as Decomposition: A strong invariant effectively "decomposes" a hard proof into smaller, easier steps. LLMs struggle when they simply restate the target assertion in a different algebraic form rather than finding a simpler intermediate property.
Key Results
Quokka consistently outperformed prior state-of-the-art LLM verifiers (like LEMUR and Clause2Inv):
- State-of-the-Art: Quokka with GPT-5.2 achieved the best results across all speedup metrics.
- Solving the Unsolvable: Under a 60-second timeout, Quokka solved 21 additional instances that the base verifier (UAutomizer) could not solve on its own.
- Speedups: In many cases, Quokka reduced the average solving time significantly (e.g., from 41.9s down to 22.2s for certain model configurations).
- Model Comparison: The study evaluated 9 different LLMs, finding that larger, newer models (like the GPT-5 and Claude 3.5 series) are substantially better at generating "strong" invariants.
Limitations and Future Work
- The "Hardest" Problems: While LLMs help with moderately difficult programs, their benefit diminishes on the most complex problems (those requiring >500s of solver time). LLMs still struggle to provide meaningful invariants for these "hardest" cases.
- Trivial Invariants: A significant portion of failures (18% in their sample) occurred because the LLM generated "trivial" invariants that didn't capture essential loop behavior.
- Resource Contention: While Best-of-N sampling helps, it eventually hits a plateau due to memory and CPU constraints when running many verifier queries in parallel.
- Future Direction: The authors suggest that future work should focus on developing LLM-based verifiers atop the most powerful existing solvers (like UAutomizer) rather than building them from scratch.
Summary updated