Quokka: Accelerating Program Verification with LLMs via Invariant Synthesis

Anjiang Wei, Tianran Sun, Tarun Suresh, Haoze Wu, Ke Wang, Alex Aiken

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:

  1. Is the candidate invariant valid? ($d_a$)
  2. Does the invariant actually help prove the target assertion? ($d_b$)
Figure 1: Illustration of Quokka’s evaluation pipeline. The LLM proposes an invariant by specifying a program location and predicate (e.g., location B with x % 7 == 3). The verification algorithm then incorporates this invariant to prove the property x != 700 using two verifier queries, and we measure the resulting speedup relative to a baseline without LLM assistance.

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.
Dataset statistics comparing Quokka to prior work

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.
Table 2: Performance comparison of LLMs on invariant generation: number of verified invariants, additional instances solved beyond UAutomizer baseline (∆), total solved in- stances, and average solving time (T) under 60s and 500s timeouts.
  • Best-of-N Gains: Implementing Best-of-N sampling showed clear performance scaling, peaking around $N=8$ before hitting resource contention plateaus.
Figure 2: Effect of Best-of-N sampling on the num- ber of ∆instances solved over Uautomizer under different timeout settings.
  • 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

Abstract

Program verification relies on loop invariants, yet automatically discovering strong invariants remains a long-standing challenge. We investigate whether large language models (LLMs) can accelerate program verification by generating useful loop invariants. We introduce Quokka, a framework for LLM-based invariant synthesis with soundness guarantees and state-of-the-art performance. Unlike prior work that treats LLM outputs as noisy symbolic material requiring substantial post-processing, Quokka adopts a simpler algorithm design that directly validates whether each LLM-generated invariant helps prove the target assertion. We construct a benchmark of 866 evaluation instances and 3589 training instances derived from SV-COMP, and evaluate 9 LLMs spanning multiple model families. We demonstrate that supervised fine-tuning and Best-of-N sampling yield measurable improvements, and we show that Quokka consistently outperforms prior LLM-based verifiers. Our code and data are publicly available at https://github.com/Anjiang-Wei/Quokka
BibTeX
@inproceedings{wei2026quokka,
  author = {Anjiang Wei and Tianran Sun and Tarun Suresh and Haoze Wu and Ke Wang and Alex Aiken},
  title = {{Quokka: Accelerating Program Verification with LLMs via Invariant Synthesis}},
  booktitle = {COLM},
  year = {2026},
  url = {https://openreview.net/forum?id=YvyAcGrpcJ},
}
Figure