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

  1. Unsound Evaluation: Some compared LLM outputs to dynamic analysis tools, which can be wrong themselves.
  2. 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

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, an evaluation-oriented framework for LLM-based invariant synthesis that provides sound evaluation and achieves state-of-the-art performance. Unlike prior work that treats LLM outputs as noisy symbolic material requiring substantial post-processing, Quokka adopts a simpler and evaluation-centric design that directly validates whether each LLM-generated invariant helps prove the target assertion. We construct a benchmark of 866 instances derived from SV-COMP and evaluate 9 state-of-the-art LLMs across 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.
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