TL;DR
Quokka is a simple, sound framework that leverages Large Language Models (LLMs) to automatically synthesize loop invariants for program verification. By abandoning the complex, heavy post-processing architectures of prior work and directly validating LLM proposals using parallel verifier queries, Quokka achieves state-of-the-art verification performance while providing formal soundness guarantees.
What Problem Does This Paper Address?
In formal program verification, proving that software behaves correctly requires finding loop invariants—logical conditions that remain true before and after every iteration of a loop. Automatically discovering these invariants has been a grand challenge in computer science for over forty years because generating an invariant that is merely correct is easy, but finding one strong enough to help a solver prove a final program assertion is incredibly difficult and generally undecidable.
Recently, researchers have turned to LLMs to generate these invariants. However, early frameworks treated LLM outputs as highly noisy and imperfect, wrapping them in complex symbolic machinery (like recursive backtracking, repair loops, or predicate filtering) to "fix" the invariants before handing them to a verifier. The authors of Quokka ask a fundamental question: As LLMs become increasingly capable, do we really need these elaborate, harness-heavy designs?
Methods
Quokka introduces a radically simpler "prove-then-use" design. Instead of trying to algorithmically rescue or repair an LLM's generated invariant, Quokka directly evaluates it by issuing two verification queries in parallel:
- Is the candidate invariant valid? ($d_a$)
- Does the invariant actually help prove the target assertion? ($d_b$)
If both queries return true, the program is successfully verified. This decoupled approach allows the framework to run queries concurrently, drastically reducing wall-clock time. The authors also mathematically prove the Decision Soundness of this calculus, ensuring that Quokka will never falsely claim a buggy program is correct.
To boost performance further, the authors explore two optimization techniques:
- Supervised Fine-Tuning (SFT): Fine-tuning models on ground-truth invariants extracted from automated verifiers.
- Best-of-N Sampling: Generating multiple invariant candidates from the LLM and selecting the one that yields the fastest verification time.
Datasets
The authors constructed a massive evaluation benchmark to rigorously test Quokka against prior state-of-the-art verifiers:
- Evaluation Dataset: 866 instances derived from the latest SV-COMP (Software Verification Competition) 2025. Unlike previous benchmarks, these programs are significantly longer and feature complex structures like multiple loops, multiple functions, arrays, and pointers.
- Training Dataset: 3,589 synthetic programs generated using GPT-4o from seed programs, with valid loop invariants extracted directly via the UAutomizer verification tool.
Key Insights and Ideas
- Simplicity Scales Better: As frontier models evolve, complex symbolic scaffolding designed to "fix" LLM outputs becomes a bottleneck. Treating the LLM as a direct proof-candidate generator is cleaner, faster, and more effective.
- The Decomposition Bottleneck: A failure mode analysis revealed that LLMs rarely fail because they generate incorrect invariants (only 14% of failures). Instead, they fail because they struggle with problem decomposition—often generating trivial invariants or simply restating the final assertion, which provides no logical shortcut for the solver.
- Constrained Prompting Forces Better Reasoning: By restricting the LLM to proposing exactly one invariant at the loop header, the model is forced to reason more deliberately about the most impactful property, outperforming exhaustive search strategies.
Key Results
The authors evaluated 9 LLMs across multiple model families (including Llama, Qwen, Claude, and GPT series).
- State-of-the-Art Performance: Quokka consistently outperformed all prior LLM-based verifiers (such as LEMUR and Clause2Inv).
- Model Rankings: GPT-5.2 achieved the highest performance, verifying 710 invariants and solving 21 additional instances that the baseline verifier (UAutomizer) could not solve within a 60-second timeout.
- Best-of-N Gains: Implementing Best-of-N sampling showed clear performance scaling, peaking around $N=8$ before hitting resource contention plateaus.
- Fine-Tuning Impact: Fine-tuning a smaller model (Qwen2.5-7B) using the synthetic dataset led to modest but measurable improvements, increasing the number of verified invariants from 419 to 431.
Limitations and Future Work
Despite its success, Quokka hits a wall on the hardest verification problems. Under a longer 500-second timeout, the incremental benefit of the LLM diminishes, indicating that current models struggle to generate the highly complex invariants required for deeply difficult code.
Additionally, the framework currently relies on the LLM getting the invariant right in a single shot (or within a Best-of-N batch). Future work could explore lightweight, non-recursive feedback loops where the verifier provides specific counterexamples to help the LLM refine its invariants without reintroducing the heavy algorithmic complexity of prior systems.
Summary updated