Refute Before You Weaken: Adversarial Roles for Loop Invariant Synthesis

To prove that a program with a loop is correct, a verifier needs a loop invariant. A loop invariant is a logical statement that is true when the loop starts, stays true after every iteration, and is strong enough at loop exit to imply the property you want. Writing these by hand is the main reason formal verification is rarely used in practice. Large language models (LLMs) now write good candidate invariants, but they fail in a characteristic way. When the verifier rejects a candidate, the model usually deletes or loosens clauses until something passes, and what passes is often too weak to prove anything. Quokka traces 18% of its sampled failures to such trivial invariants and gets nothing on the hardest SV-COMP instances (Quokka). LORIS reports that LLMs "inadvertently weaken" invariants when they are told the invariant is not preserved by the loop (LORIS).

This proposal targets a logical mistake behind that behavior. When the verifier says "your invariant is not preserved," it returns a counterexample to induction: a state that satisfies the invariant, but which one loop iteration maps to a state that violates it. Weakening is the correct response only if that starting state can actually occur when the program runs. If it cannot occur, the correct response is the opposite: strengthen the invariant so it excludes that state. LLMs appear to treat both cases the same way. We propose to separate the two responses into two agents with opposing goals and firewalled contexts. A Strengthener may only add clauses. A Refuter may only remove a clause, and only by producing a concrete, actually reachable program state that falsifies it. Both work on a shared ledger of clauses in which no clause can be dropped without evidence. This rule is enforced by the harness, not requested in a prompt.

Core Claim

Weakening a candidate without evidence explains much of the "strength gap" and much of the plateau of verifier-in-the-loop refinement. Our central hypothesis is that sorting counterexamples by reachability, and letting clause removal depend on a concrete refutation, lets refinement keep improving on hard instances, where Best-of-N sampling has stopped improving. The Refuter is kept in a separate agent. It never sees the Strengthener's reasoning and never uses tests the Strengthener wrote. This addresses the co-adaptation failure documented in ClassInvGen, where a model's own weak tests failed to expose its bad invariants.

The design keeps two separate hypotheses. The first is the mechanical routing rule, together with a record of each clause's status. The second is the role separation. Either could carry the gain, and the experiments are designed to tell which one does.

Research Program

The system maintains an invariant as a list of clauses (a conjunction). Each clause is tagged with one of four statuses: proved-relative (it is preserved given the other clauses), refuted (a reachable state violates it, so it is removed permanently and recorded as a negative example), needed-for-sufficiency, or unknown.

On each round the verifier (UAutomizer, or Frama-C with Z3, depending on the benchmark) checks three things: initiation, preservation, and sufficiency. Its output is then sorted by type.

A sufficiency failure goes to the Strengthener, which must add a clause.

A preservation counterexample goes first to the Refuter. The Refuter tries to show the counterexample's starting state is reachable. It does this by running the program on generated inputs, by bounded model checking from the program entry, or by directed fuzzing whose seeds come from the program text rather than from the Strengthener. If it succeeds, the specific clauses that state violates are removed, and the state is added to a store of reachable examples that every future candidate must satisfy. If it fails within budget, the counterexample is treated as probably unreachable and goes to the Strengthener with an instruction to exclude that state.

Edits are clause-level differences, not whole-invariant rewrites. This directly addresses the whole-proof replacement that SAFE identifies as discarding partially correct work. Program code stays frozen throughout, following the frozen-code inner loop of Adversarial Review. Unlike that system, disagreements here are settled by execution evidence and a solver, not by agents negotiating toward consensus.

The method borrows from several prior systems and differs from each. From Adversarial Review it takes the structured, evidence-bound disagreement and the lesson that unconstrained debate reaches false consensus. It replaces LLM judgment with formal and execution oracles. From Spec-Agent it takes the use of fuzzing, but only for refutation. Spec-Agent accepts specifications that survive fuzzing, which, as its authors note, cannot establish validity or strength. Here, acceptance is always by the verifier. Compared with LORIS, which splits roles into a Synthesizer and a Formalizer and pinpoints errors in local reasoning steps, this proposal splits roles by the opposite directions an invariant can be changed. That is the axis on which LORIS reports failures.

Our Refuter's reachability checks resemble counterexample-guided and template pruning methods such as Houdini-style clause elimination, discussed in SpecGen. The difference is that those methods can only remove clauses, while our loop also strengthens in response to unreachable counterexamples.

Baselines

The naive reference point is the verifier alone, UAutomizer with no invariant hints, under the same wall-clock timeout. On the Quokka benchmark this defines the "hard" set: instances it does not solve in the time budget.

The strongest competitor on SV-COMP-style C is Quokka's direct Best-of-N sampling against the verifier (Quokka). It is the strongest because its authors argue explicitly that multi-step pipelines add cost without benefit. They report solving 21 additional instances that base UAutomizer could not solve at a 60-second timeout, and cutting average solving time from 41.9s to 22.2s in some configurations. The file reports no per-stratum pass rate for the over-500-second instances beyond the statement that direct sampling fails on them. We will run Best-of-N with the same base model and the same total token budget and verifier-call budget as our system, with N tuned on a held-out split.

On the LORIS numerical suites, the strongest method is LORIS itself: 445 of 460 programs (93.1%) on the main suite and 47 of 50 on the non-linear suite with GPT-4.1 (LORIS). With so little headroom, beating LORIS here means matching its solve count at lower token cost and with fewer evidence-free weakenings.

On heap-manipulating programs, LLM-SE reports pass rates of 38.78% at pass@1 and 42.95% at pass@8 on LIG-MM (LIG-MM). We treat this as a stretch target. Our Refuter would need a heap-shape execution tracer, and the claim there is secondary.

Three ablations isolate the key ingredients. The first is a single agent in one context with the same tools and the same ledger rule. It tests whether role separation matters beyond the rule. The second keeps the two agents but removes the reachability gate, so either agent may remove clauses on any counterexample. It tests the routing rule itself. The third is LLM-generated clause pools pruned by Houdini, which isolates strengthening as an ingredient.

For all conditions we use the same base model, the same verifier version and timeouts, and the same prompt-tuning budget, and we report tokens and verifier seconds for every condition. Beating the strongest baseline means solving statistically more instances in the Quokka hard set than compute-matched Best-of-N, over three seeds with a paired test. A pure latency win on easy instances does not count.

Why not just…?

Why not just use Best-of-N with a larger N? This is the most serious threat. Quokka's argument is that sampling plus a verifier beats harness complexity. If the hard instances fail because the needed clause is simply rare in the model's distribution, more samples will eventually find it, and our loop only adds overhead. If instead they fail because each sample is independently trivial, sampling will not converge, and accumulating clauses in a ledger will. The file supports the second reading but does not settle it. We will plot solved hard instances against token budget for both methods up to eight times our system's cost. If Best-of-N catches up within that range, we will report that our method is not needed at this scale.

Why not just run a LORIS- or SpecGen-style single refinement loop? These loops feed verifier errors back to one model. Both LORIS and Yan et al. document the failures we target: evidence-free weakening and a plateau after three to five rounds. The first ablation is exactly this condition given our tools. If it matches the two-agent system, the contribution becomes the reachability-gated ledger rather than multi-agent decomposition, and we will state it that way.

Why not just have the LLM propose many clauses and let Houdini prune? This is cheap and sound. However, it can only remove clauses. It fails whenever the needed clause was never proposed, which is the situation an unreachable preservation counterexample signals. The Houdini-pruned ablation measures how often that happens. SpecGen's result that Houdini alone reaches 25.5% against 72.5% for LLM refinement suggests that proposing the pool is the bottleneck, not pruning it.

Why not just use classical tools like Polar or SLING? They are sound but limited in scope. Polar handles restricted classes of loops whose behavior can be solved as recurrences (Polar), and SLING reaches 12.82% on LIG-MM. We include UAutomizer alone as the classical reference rather than rebuilding these tools.

Proposed Experiments

The primary experiment is on the Quokka benchmark: 866 SV-COMP C instances, stratified by the verifier's unaided solve time. The headline outcome is the number of hard-stratum instances solved at matched budget. We report three diagnostics alongside it:

  • the fraction of final or near-final candidates that are trivial, using Quokka's criterion of restating preconditions or type facts;
  • the number of clause removals without a reachable witness, which is zero by construction in our system but measurable in the baselines and ablations;
  • whether solve rate keeps rising past round five instead of plateauing.

The secondary experiment is the LORIS main and non-linear suites. It checks that we do not regress where LORIS is near saturation, and it compares cost.

The exploratory experiment is LIG-MM with a heap-aware Refuter. It is reported against LLM-SE's 42.95% pass@8.

The decisive check is the pair of ablations. If removing the reachability gate erases the gain, the routing rule is the mechanism. If the single-context version matches the two-agent version, role separation is not needed. If Best-of-N at equal compute matches everything, the hypothesis is refuted on these benchmarks, and we will say so.