Abstract Counter-Regions: Feedback That Breaks the Plateau in LLM Proof Repair

When a language model writes a formally verified program in a language like Dafny, a verifier checks the proof and reports either success or a failure. A failure usually means a loop invariant that does not hold, sometimes with one concrete counterexample state, and often just a timeout. Models then retry. These loops stall within a handful of attempts: they cycle through equivalent rewrites or patch the single counterexample they were shown. This proposal gives the model a different kind of feedback, computed by a cheap, sound but incomplete program analysis. The analysis reports which facts about the loop are already guaranteed true, and it describes the whole region of states where the model's failing invariant breaks, for example "every state with $i > n$ and $s < 0$." It does not report one point inside that region.

The bet is that region-level feedback lets the model generalize its fix instead of overfitting to a point. Abstract interpretation is the analysis family that approximates a program's behavior over simple shapes such as intervals or octagons. It produces exactly this kind of feedback in polynomial time and never asserts something false. It also cannot prove everything. That trade is what makes it usable inside an iterative loop. The approximate-reasoning literature has long made this trade for theorem provers. Nobody has used it to decide what a code-repair model gets told.

Core Claim

Sound but incomplete abstract analysis can supply two pieces of feedback that exact verifiers and test suites do not. The first is a set of proven-true facts the model can rely on. The second is a symbolic counter-region for each failing invariant clause, checked against the exact solver so that it contains at least one real violation. On the hard slices of current Dafny benchmarks, region feedback should solve more tasks per verifier call than the strongest feedback in use today, Dafny's concrete counterexamples. It should also beat the obvious cheap imitation of a region, which is showing several counterexamples. The improvement should show up in the late turns where existing loops plateau. It should also scale with how much of the failing invariant the abstract domain can express.

Where This Sits

The plateau that motivates this work is well documented. DafnyBench built a 782-program benchmark for filling in proof annotations. It found that up to 10 retries with verifier error messages give quickly diminishing returns, and that success falls below 20% on long, deep programs. Yan et al. report the same early plateau for compiler-feedback refinement in code translation.

Three systems represent the current state of verified-code refinement, and all three treat the exact verifier as their only semantic signal. AlphaVerus bootstraps Verus code and adds tree search scored by counts of verifier errors. It also uses an exploit-finding critic against specification weakening. DafnyPro adds three things: a syntax-tree diff checker that lets the model touch only proof annotations, a verifier-driven pruner for bad invariant clauses, and retrieved proof hints. DafnyProver (AxDafny) does joint code-and-proof synthesis. It feeds Dafny's --counterexamples models back to the model and keeps a memory scratchpad. We reuse DafnyPro's diff checker and AlphaVerus-style exploit checks as safety rails. We take AxDafny as the system to beat. Where they differ from us is in what the model is told after a failure: a scalar state from the solver in their case, an analyzer-derived region plus guaranteed facts in ours.

The approximate-reasoning side supplies the method and the justification. Kautz and Selman showed that cheap logical upper and lower bounds settle most queries before a full prover is needed, with total query time cut by over two orders of magnitude on hard random theories. Reynolds et al. showed that incomplete length- and multiset-based abstractions inside CVC4 raised solved TermEq problems from 35 to 61 out of 80. Both papers are evidence that sound incomplete abstractions carry real information that exact search misses. Neither ever exposes that information to a learner. Optimal Program Synthesis via Abstract Interpretation is the closest use of abstract interpretation inside synthesis search. There, intervals over partial programs give admissible bounds for A* in a monotone domain-specific language. It involves no language model, no general-purpose code, and no feedback text. Neural Abstract Interpretation learns abstract transformers. We deliberately use classical hand-built domains instead, because soundness of the reported facts is the whole point.

Two papers constrain the design. Roth shows that approximate reasoning can itself remain intractable for general representations, so we restrict ourselves to domains with polynomial transfer functions and accept their blind spots. LLM-Vectorizer applied approximation only to make the verifier finish, through loop unrolling and case splitting. Its authors note that failures still return no root cause to the model. That is precisely the gap we fill. TELPA injects static-analysis facts into prompts for test generation. Its facts are structural (call sequences and data dependencies), not value ranges, and it does not do repair.

Research Program

We build an analyzer for the integer and array-length fragment of Dafny loops. It uses three domains of increasing precision: intervals, octagons (constraints of the form $\pm x \pm y \le c$), and convex polyhedra. Array contents are summarized and sequence quantifiers are left out of scope, so the analyzer simply says nothing about them. We will measure that blind spot rather than hide it.

For each verification attempt, the analyzer runs forward from the method's precondition to compute an over-approximation of the reachable states at each loop head. Every constraint in that over-approximation is a guaranteed invariant. We render these as "already established" facts. When Dafny reports that a candidate clause $c$ is not maintained, we compute a counter-region.

$$R \;=\; \gamma\big(\mathrm{pre}^\#_{B}(\neg c)\big)\;\cap\;\gamma(I^\#\wedge g)$$

Here $I^\#$ is the abstract value of the model's current invariant conjoined with the analyzer's facts, $g$ is the loop guard, $\mathrm{pre}^\#_{B}$ is the abstract backward transfer through the loop body $B$, and $\gamma$ maps an abstract value to the set of concrete states it describes. Because the abstraction over-approximates, $R$ may contain spurious states. We therefore ask Z3 for a model inside $R$ and present the region only if one exists. Every region shown thus contains at least one real violation. We then translate $R$ into short text naming the variables and inequalities involved, plus one witness point.

The repair loop itself is AxDafny's proposer–reviewer–memory design, kept unchanged apart from the feedback channel. Keeping the loop fixed keeps the comparison clean.

The first deliverable is a reach measurement, before any language-model experiment. For failing clauses produced by a baseline loop on the hard slices, what fraction are expressible in each domain, and for what fraction does the analyzer return a confirmed region? This is a go/no-go gate. If octagons reach only a small minority of failures on the hard slice, the method's ceiling is low. In that case we report this as a finding and stop at intervals plus guaranteed facts.

Baselines

The naive reference is linear retry with raw Dafny error messages over the same 20-turn budget, as in the DafnyBench protocol. It shows how much any structured feedback adds. Its published comparator on DafnyBench is the Claude 3 Opus success rate of 67.8% reported by DafnyBench, alongside a "no LLM" baseline of 26.9%.

The strongest existing method is AxDafny from DafnyProver. It reports 92.7% verification success on DafnyBench, and on LCB-Pro-Dafny it reports 56.4% overall, 75% Easy, 52% Medium and 28% Hard. It is the strongest competitor because it already does what we are improving on: it extracts solver counterexamples and feeds them to the model inside a reviewed, memory-equipped loop.

Those numbers were obtained with Gemini-3.1-Pro, so we cannot match them exactly. We will reimplement the AxDafny loop and run it, and every variant of our method, with the same base model (one open model and one frontier API model). All runs get the same 20-iteration budget, the same Dafny version and timeout, the same diff checker and exploit critic, and the same prompt-tuning budget of a fixed number of development tasks per arm. We will quote the published figures as context, not as head-to-head numbers. Beating AxDafny means a statistically reliable gain in verified-and-specification-preserving success on LCB-Pro-Dafny Medium and Hard, together with the long-program slice of DafnyBench, at equal or lower total verifier seconds. A gain confined to DafnyBench overall would not count, because the 92.7% leaves too little headroom to be informative.

We also include AlphaVerus-style tree search as a search-strategy baseline, again at matched verifier calls. Its published result is 32.9% on HumanEval-Verus against prompted GPT-4o's 27.1% (AlphaVerus). This tests whether better feedback beats more branching.

Three ablations isolate the key ingredient. The first gives guaranteed facts only, with no regions. The second gives regions only, with no facts. The third gives a shuffled region taken from a different failing clause, padded to the same length. The shuffled control tells us whether the model reads the content of the region at all.

Why not just…?

Why not just show several counterexamples instead of a region? This is the most serious threat. Asking Z3 for $k$ distinct models with blocking clauses is easy, and a handful of points may let the model infer the region itself. We include it as a baseline with $k$ chosen so that its prompt length matches the region feedback. If $k$-counterexample feedback matches region feedback on the hard slices, the core claim is wrong. The honest conclusion would then be that diversity of points, not abstraction, is what breaks the plateau, and we would report it that way. Our prediction is that regions win when the violated relation involves two or more variables, because scattered points underdetermine such a relation. We will report results split by the number of variables in the failing clause to test exactly that.

Why not just inject the inferred invariants as hints and skip the region text? Analyzer-inferred invariants as hints are close in spirit to DafnyPro's hint augmentation (DafnyPro), and they may account for much of any gain. The facts-only ablation measures this directly. If facts alone capture the improvement, the contribution shrinks to "add abstract interpretation as a hint source." That is useful but smaller, and we would say so.

Why not just spend the compute on more turns or more samples? ReVeal shows that test-time scaling over 25 turns does help, moving LiveCodeBench Pass@1 from 34.8% to 38.7%. The plateau results in DafnyBench suggest the curve flattens for formal proofs. We settle this by plotting success against cumulative verifier seconds and tokens for every arm, out to twice the standard budget for the baselines. Our method must sit above the baselines' curves, not merely beat them at one budget.

Why not just raise the solver timeout? Many failures are not timeouts at all; they are clauses that are genuinely not inductive, and more solver time cannot fix those. For the timeout subset, we run an arm with a tripled Dafny timeout and report it separately.

Proposed Experiments and Decisive Checks

The benchmarks are LCB-Pro-Dafny (250 problems, with Medium and Hard as primary), the long-program tercile of DafnyBench, and Clover and dafny-synthesis as smaller held-out checks. Lacuna has no reported results for Clover or dafny-synthesis, so we establish their baselines ourselves.

The primary metric is verified success that passes the diff checker and the exploit critic. Secondary metrics are four. The first is the late-turn solve rate, meaning the fraction of tasks still open at turn 5 that are solved by turn 20; this is the direct plateau measure. The second is the repeat-error rate, meaning turns that reintroduce a previously failed clause. The third is verifier seconds per solved task. The fourth is, for LCB-Pro-Dafny, execution pass under time limits. AxDafny found only 6 of 52 verified Medium solutions passed execution, so we track whether better proof feedback changes this complexity gap at all. We expect it will not, and say so in advance. The point of tracking it is that a method that verifies more programs but pushes the model toward simpler, slower algorithms would be a hidden cost.

Four results would decide the question. First, region feedback beats the matched $k$-counterexample arm on the hard slices, with the gain concentrated in late turns. Second, the shuffled-region control erases the gain. Third, gains grow monotonically from intervals to octagons to polyhedra on clauses each domain can express, and vanish on clauses outside every domain. This dose-response is the evidence that the abstraction, not the extra prompt text, is doing the work. Fourth, results hold for both base models. If the first check fails, the proposal reduces to its facts-only variant, and we will report it as such.