Proving that a C program with loops is correct usually hinges on one hard step: finding a loop invariant, a logical statement that holds before and after every iteration and is strong enough to imply the assertion being checked. Language models can now propose invariants that a solver then checks. Their main failure is not bad syntax but weakness. They propose true yet useless facts such as $x \ge 0$ when the proof needs something like $x \bmod 7 = 3$, and the solver then runs until it times out. Yet the strong facts that proofs need are often idioms that recur across verification benchmarks: modular counters, linear relations between loop counters, difference bounds between array versions. Many of them have already been proved for some other program.
We propose to retrieve invariants that have already been verified for structurally similar loops, and to generate the new invariant with a decoder that has two separate ways to copy. It may copy operators, constants and relational structure from the retrieved invariants, and it may copy variable names only from the target program. This is a pointer-generator: a decoder that, at each step, mixes ordinary vocabulary prediction with directly copying a token from its input. Our version splits copying by token role, so that retrieved structure transfers while foreign variable names cannot. The claim to test is that retrieval supplies the strength that current invariant generators lack, and that role-split copying is what lets a small open model adapt retrieved invariants faithfully instead of paraphrasing them into weaker ones.
Where this sits
This note treats software verification as the application, retrieval as the source of the missing strength, and the pointer-generator as the mechanism that controls how retrieved content enters the output. Four recent invariant-synthesis systems frame the problem, and none of them retrieves anything. InvBench / Quokka asks an LLM for candidate invariants. It checks them with two parallel solver queries in UAutomizer: one proves that the invariant is valid, the other checks that it implies the assertion. The same work documents the "strength gap": 18% of sampled failures were trivial invariants, and timeouts dominate on hard loops (Quokka). These findings motivate our proposal, and we reuse Quokka's checking protocol as our evaluator. LORIS repairs failed invariants by having one model write reasoning steps and another turn them into logical implications, which Z3 then checks one by one. It still asks the model to invent structure from scratch, and it breaks down when a proof needs global reasoning about the program. WONDA cleans solver-produced invariants and uses them to fine-tune small models, so that 4B–14B models match much larger ones. We reuse its curated corpus, but as a retrieval index rather than only as training data. That choice also lets us test a tension the research file identifies: simplifying invariants for learnability may strip out exactly the constraints that give an invariant its strength.
Retrieval has already been joined to formal specification. PropertyGPT retrieves audited smart-contract properties into GPT-4's prompt and repairs them using compiler errors, reaching 80% recall against human-written properties. That supports the premise that verified specifications transfer across programs. However, PropertyGPT decodes with plain softmax, so nothing stops the model from carrying over foreign identifiers or quietly weakening a retrieved constraint. It also does not address numerical loop invariants.
Two works supply our copy mechanism. FiD-PGN adds a copy gate of 1,537 parameters to a retrieval-augmented T5 reader by reusing its cross-attention. It raised NaturalQuestions exact match from 48.5 to 51.4, with fewer retrieved passages. LargePiG builds a copy gate for an LLM without any training: it reads attention as the pointer distribution and uses the divergence between intermediate-layer and final-layer predictions to decide when to copy. Both treat the input as one undifferentiated pool of text and were tested only on natural-language tasks. Our change is to split the pointer by source and by token role, because in formulas, unlike prose, copying the wrong kind of token from the wrong source produces an unsound result.
Core Claim
Consider a target program $P$ and retrieved verified invariants $R_1,\dots,R_k$ from programs other than $P$. The decoder outputs
$$P(w) = g_{\text{gen}}\,P_{\text{vocab}}(w) + g_{\text{prog}} \sum_{i \in P:\, w_i = w} a_i + g_{\text{ret}}\,\mathbb{1}[w \notin \mathcal{I}] \sum_{j \in R:\, w_j = w} b_j .$$
In this formula, $g_{\text{gen}}, g_{\text{prog}}, g_{\text{ret}}$ are gate weights that sum to one, $a_i$ and $b_j$ are attention weights over target-program tokens and retrieved-invariant tokens respectively, and $\mathcal{I}$ is the set of identifier tokens. The indicator term forbids copying identifiers from retrieved invariants. Variables must therefore come either from the target program's pointer or, in principle, from generation, and during decoding we also mask generated identifiers to the program's symbol table. The prediction is that accepted invariants, those that are both valid and strong enough to prove the assertion, will carry a large share of retrieval-copied operator and constant structure. The number of trivial invariants should fall accordingly, and hard instances should become solvable within a fixed number of solver calls.
Research Program
We build three components. The first is a retrieval index. Its entries are loops from WONDA's curated UAutomizer invariants on SV-COMP together with InvBench's 3,589 synthetic programs, each paired with its verified invariant. We store both the raw form and the WONDA-simplified form of each invariant, so that the strength-versus-simplicity tension becomes something we can measure. Retrieval uses structural keys: a normalized loop skeleton with names abstracted away, the update operators, and the shape of the assertion. We compare these keys against BM25 over raw code as a text-matching baseline.
The second component is the decoder. It runs on an open-weight Qwen3-8B, the model family WONDA uses, because the copy mechanism needs access to attention. We train a learned three-way gate FiD-style, adding a few thousand parameters and fine-tuning on WONDA pairs augmented with retrieved neighbors. We also build a training-free LargePiG-style variant as an ablation.
The third component is the evaluator. It applies Quokka's parallel validity and usefulness queries in UAutomizer, and Frama-C/Z3 on the LORIS suites. On top of the evaluator, we log the provenance of every emitted token (generated, copied from the program, or copied from retrieval). This lets us ask whether proofs succeed because of borrowed structure.
Leakage is the main threat to validity, since SV-COMP contains many near-duplicate program families. We therefore split the index from the evaluation set at the level of program families and report results both with and without near-duplicate removal.
Baselines
The naive reference point is UAutomizer run alone under the same time limit. Quokka reports that LLM-generated invariants solved 21 extra instances under a 60-second timeout, gave a 2.0x speedup on 51 instances and a 1.2x speedup on 81, and cut average solving time from 41.9s to 22.2s in some configurations (Quokka; InvBench). Any credible system must first beat the solver alone, and Quokka's numbers are the published bar for doing so.
The strongest competitor under equal compute is a WONDA-fine-tuned model of the same 8B size (WONDA). It already closes much of the gap to frontier models without retrieval. The file reports only relative claims for it (roughly doubled correctness, and matching GPT-OSS-120B verification time), and we found no absolute InvBench figure for it on Lacuna. We will retrain it on exactly our training data and give it the same eight solver calls per instance. We also run Quokka-style Best-of-8 prompting of a frontier model as the strongest system with unlimited model size.
On the LORIS suites, the bar is LORIS's reported 93.1% success rate (445 of 460 programs) and 47 of 50 on the non-linear suite with GPT-4.1 (LORIS). The main suite is near its ceiling, so the non-linear suite and the hard InvBench instances are where real separation is possible.
Three baselines isolate our ingredients. PropertyGPT-style retrieval prompting puts the same retrieved invariants in the prompt of the same 8B model with ordinary decoding. Retrieval prompting plus symbol-table-constrained decoding tests whether identifier fidelity alone explains any gain. Our own model with the retrieval pointer removed or the role split disabled tests the copy mechanism directly.
We count the proposal as beating these baselines if, under family-level splits and an equal budget of eight solver calls, it proves strictly more hard instances (those beyond UAutomizer's reach at 60s) than both the WONDA 8B model and retrieval prompting with constrained decoding. Its trivial-invariant rate must also fall well below Quokka's 18%.
Why not just…?
Why not just put retrieved invariants in a frontier model's prompt? This is the PropertyGPT recipe, and it is a real threat, since strong models may adapt retrieved invariants well on programs averaging 53 lines. The evidence against relying on it is indirect. Frontier prompting in Quokka still produced trivial invariants, and LargePiG argues that ordinary decoding drifts from the source because the model substitutes knowledge stored in its own weights. Our frontier Best-of-8 retrieval-prompting baseline settles the question. If it matches our 8B system, the contribution shrinks to "retrieval helps," and we will report it that way.
Why not just constrain identifiers to the symbol table and skip the pointer? Constrained decoding does guarantee that no foreign variable appears, so if identifier drift were the whole problem, it would suffice. Our hypothesis is that the pointer's value lies in faithfully copying constants and operator structure from retrieved invariants, which a symbol-table mask cannot provide. The comparison between retrieval prompting with constrained decoding and our role-split model, together with provenance logs showing which copied tokens appear in accepted invariants, tests this directly.
Why not just instantiate retrieved invariants as templates and enumerate variable bindings? Classical template-based synthesis needs no neural decoder. With few variables, enumeration is cheap per candidate, though every candidate costs a solver call. We run this as a baseline under the same solver budget. Our expected advantage is on instances where the retrieved invariant must be partly changed rather than simply re-bound; the copy gate allows this mixing, and enumeration does not. If enumeration wins, the right conclusion is that retrieval rather than decoding is the key ingredient.
Why not just sample more, or fine-tune harder? Quokka reports that Best-of-N reaches a plateau because running many verifier queries in parallel hits memory and CPU limits. WONDA's fine-tuned models learn from a fixed training set and cannot absorb newly proved invariants without retraining, whereas an index can be updated. Matching the solver-call budget across all systems keeps this comparison honest.
Decisive Checks
Four results decide whether the idea holds.
First, the main comparison. On hard InvBench instances and the 50 non-linear LORIS programs, the full system must outperform both the WONDA 8B model and constrained retrieval prompting at eight solver calls, under family-level splits.
Second, leakage. The gain must survive near-duplicate removal. If it disappears, retrieval was memorization rather than transfer.
Third, provenance. Among accepted invariants, the share of retrieval-copied tokens should be higher in the parts that carry strength, such as modular and relational clauses, than in plain bounds. The trivial-invariant rate should fall relative to the ablation without the retrieval pointer.
Fourth, the simplicity trade-off. Comparing a raw-invariant index with a simplified one tells us whether WONDA-style simplification removes the strength that retrieval is supposed to supply, which settles the tension the research file identifies either way.
References
- InvBench: Can LLMs Accelerate Program Verification with Invariant Synthesis?
- Quokka: Accelerating Program Verification with LLMs via Invariant Synthesis
- Guiding LLM-Based Loop Invariant Synthesis via Feedback on Local Reasoning Errors
- Not All Invariants Are Equal: Curating Training Data to Accelerate Program Verification with SLMs
- PropertyGPT: LLM-driven Formal Verification of Smart Contracts through Retrieval-Augmented Property Generation
- A Copy-Augmented Generative Model for Open-Domain Question Answering
- LargePiG: Your Large Language Model is Secretly a Pointer Generator