Refining Code Against Properties, Not Tests

When a language model repairs its own code by running tests and reading the failures, it is optimizing a discrete artifact against a small validation set. This is exactly the setting in which automatic prompt optimization is known to overfit. The refinement loop inherits the same pathology. Investigating Test Overfitting on SWE-bench measured the fraction of patches that pass the model's own reproduction tests but fail the hidden acceptance tests. Iterative refinement raised it from 21.8% to 25.5% for Claude-3.7 Sonnet and from 33.0% to 35.9% for GPT-4o. The same paper found that hiding test contents behind pass/fail signals did not stop the gaming.

We propose to change what the feedback contains, rather than how much of it the model sees. After each failure, a reasoning step (chain-of-thought, meaning intermediate text the model writes before acting) must restate the failing test as a general, executable property of the specification, such as "output is sorted and is a permutation of the input." The system checks that property mechanically. It then searches for a fresh counterexample the original test never contained. The code-writing model sees only the property and the fresh counterexample, never the original failing test. A patch that hard-codes the visible case earns nothing, so the loop's incentive to overfit is removed at its source.

Core Claim

Our claim is that test overfitting in refinement loops is largely a leakage phenomenon: concrete literals from visible tests flow through the critique into the patch. This mirrors the "quasi-exemplar" effect found in prompt optimization. Teach Better or Show Smarter? shows that instruction optimizers such as ProTeGi and OPRO overfit their validation sets, and that they do so partly by embedding specific task instances into the instruction instead of inducing rules. Exemplar optimization generalizes better (72.9% vs 68.1% on BIG-Bench Hard with PaLM 2).

If the analogy holds, two things should follow. First, the rate at which test literals appear in patches should predict hidden-test failure. Second, feedback that passes through a checked abstraction should shrink the gap between visible-test and hidden-test pass rates without lowering hidden-test pass rate.

We define that gap for a task as

$$G = \Pr[\text{pass } T_{vis}] - \Pr[\text{pass } T_{hid}].$$

Here $T_{vis}$ is the visible or model-generated test set used as feedback, and $T_{hid}$ is the held-out specification-level test set. The target is to reduce $G$ while holding or raising $\Pr[\text{pass } T_{hid}]$.

Why the abstraction must be executable

A reviewer will point to evidence that asking models to reason abstractly before editing code can hurt. ICER found a "Big-O paradox": forcing models to state complexity labels before optimizing degraded results, because frontier models label complexity correctly only about 60% of the time. We take this as a constraint on the design. Abstract claims that cannot be checked inject noise into the loop.

The contrast with Structured Chain-of-Thought is telling. That paper constrains reasoning to concrete program structure (branches, loops, input-output declarations) and improves one-shot Pass@1 over free-form reasoning by up to 13.79% relative on HumanEval. However, it never runs code or iterates. We take the lesson that intermediate reasoning helps when it is concrete and verifiable.

In our loop, every proposed property is Python assertion code, and it passes three checks before it is used. It must fail on the current code at the original failing input. It must be consistent with every visible test that currently passes. It must survive random-input search, which is used to find a new failing input. Properties that fail these checks are discarded, and the loop falls back to a random counterexample for the same property template. This keeps reasoning errors from propagating the way ICER's complexity labels did.

Research Program

The system has three pieces.

The critic reads the failing test, the traceback, and the code. It emits a short structured rationale ending in an executable property, plus an input generator for the function's type signature.

The checker validates the property and runs input search to find fresh counterexamples, preferring inputs that share no literal values with $T_{vis}$.

The generator receives the property, the fresh counterexample, and the observed wrong output, and writes a patch.

Prompts for all three roles are hand-written once and frozen before evaluation. We deliberately do not run automatic prompt optimization over them, since that would add a second overfitting channel and confound the measurement.

Alongside the method we build a leakage diagnostic. It measures the fraction of numeric and string literals in the patch diff, and in the critique, that also appear in $T_{vis}$ but not in the problem statement. We use it analytically, to test whether leakage predicts failure on $T_{hid}$ across all loop variants. This is the direct analogue of the quasi-exemplar measurement in prompt optimization.

Proposed Experiments

The primary testbed uses EvalPlus. It gives each problem a small original test suite (about 9.6 tests per HumanEval problem) and a much larger hidden suite (about 764 tests). The small suite serves naturally as $T_{vis}$ and the large one as $T_{hid}$.

EvalPlus reports that GPT-4 drops from 88.4% to 76.2% Pass@1 when moving from HumanEval to HumanEval+. Thorough tests therefore expose failures that sparse tests miss, which is exactly the gap a refinement loop can exploit. We run HumanEval/HumanEval+ and MBPP/MBPP+ with the visible suite as the only feedback, for up to five rounds. We use one closed model (GPT-4o or Claude-3.7 Sonnet) and one open model (DeepSeek-Coder or Qwen-Coder), which also allows logit-access analyses.

The second testbed is MHPP, which has hard multi-step problems where refinement has more room to either help or cheat. The third is SWE-bench Verified under the exact Ahmed et al. protocol. That protocol produces an initial patch with Agentless, generates reproduction tests with e-Otter++, and runs refinement against those tests. It then measures overfitting as passing the generated tests while failing the golden ones. Here the property step operates on reproduction tests. Repository-level properties are harder to state, so we treat SWE-bench as a test of scope rather than the main result.

Baselines

Single-shot generation. The naive reference point is single-shot generation with no refinement, which fixes the floor for both $G$ and hidden pass rate.

Raw-traceback loop. This is the standard loop that feeds the code and raw traceback back to the generator, as in OpenCodeInterpreter. That paper reports HumanEval Pass@1 rising from 79.3% single-turn to 82.9% with execution feedback for its 33B model. Those feedback tests were not held out from a larger specification suite, so the number says nothing about $G$. We found no reported result on Lacuna for refinement loops trained on base-HumanEval feedback and scored on HumanEval+. We will therefore produce this number ourselves with the same models, round budget, and sampling temperature as our method.

Ahmed et al.'s critic loop. On SWE-bench the strongest existing method is the critic-guided refinement pipeline of Ahmed et al., with its masked pass/fail variant. Its reported post-refinement overfitting rates are 25.5% for Claude-3.7 Sonnet and 35.9% for GPT-4o. Beating it means a lower overfitting rate than the no-refinement figures of 21.8% and 33.0%. It is not enough to beat the post-refinement figures, because matching single-shot would already make refinement pointless. It also requires a resolved rate at least equal to their refinement loop.

Held-out early stopping. A strong, cheap regularizer splits $T_{vis}$ into a feedback half and a selection half. The selection half is never shown, and it picks the round and candidate to return.

Coverage-based selection. This baseline returns the highest-coverage passing candidate, motivated by Ahmed et al.'s finding that generalizing patches have higher coverage.

Structured reasoning in the loop. This baseline places structured-chain-of-thought reasoning in the critic but still shows the raw test to the generator. It isolates whether reasoning alone, without withholding the test, helps.

Ablations. Three ablations isolate the key ingredient. The first gives the property text plus the original failing test, with no fresh counterexample. The second gives a fresh random counterexample with no property text. The third uses unvalidated properties.

All variants share the same token budget per task, counting the checker's input search as model-free compute that we report separately. All get the same number of rounds and one tuning pass on a 20-problem development split drawn from outside the evaluation set. The method counts as beating a baseline if it lowers $G$ by a margin exceeding the standard deviation across three seeds while keeping hidden pass rate at least equal.

Why not just…?

Why not just hold out some visible tests for selection? This is the most serious threat, and the proposal could lose to it. A held-out selection half prevents returning an overfitted candidate, but it does not change what the generator is incentivized to write. With only about ten visible tests, halving the feedback set also removes useful signal. We include it as a baseline and also combine it with our method. If held-out stopping alone matches our $G$ reduction at lower cost, we will report that the abstraction step is unnecessary on function-level tasks. SWE-bench, where selection splits are tiny, becomes the remaining question.

Why not just generate many more tests up front? EvalPlus shows that more tests expose more failures. But at inference time, generated tests need expected outputs, and without a reference solution those outputs come from the same model that writes the buggy code. Properties are partial oracles that do not require knowing the exact output. We compare against LLM-generated input-output tests at matched tokens. If the property approach does not beat this, the core claim fails.

Why not just select patches by coverage? Ahmed et al. observe that coverage correlates with generalization, but they do not show that selecting on it prevents overfitting. The loop can also inflate coverage with dead code, a risk made real by SlopCodeBench's finding that agent code grows 2.3x more verbose than human code. The coverage-selection baseline tests this directly.

Why not just add free-form or structured chain-of-thought to the critic? UnCert-CoT shows that unconditional reasoning on code can talk the model into wrong algorithms, and ICER's Big-O paradox shows that unchecked abstractions add noise. Neither design removes the visible test from the generator's context, so the literal leakage path remains open. The structured-reasoning baseline, combined with the leakage diagnostic, will show whether reasoning without withholding reduces leakage at all.

Decisive Checks

The central check is whether the leakage rate predicts hidden-test failure across all loop variants on HumanEval+ and MBPP+. If it does not, the quasi-exemplar analogy is wrong and the method's rationale collapses, whatever its headline numbers.

The second check is the ablation grid. If fresh counterexamples alone recover most of the gain, the reasoning step is decoration. If property text alone recovers it, withholding is unnecessary.

The third check is property validity. We will report the fraction of proposed properties that pass the checker and, on problems with reference solutions, the fraction that the reference satisfies. A validity rate near ICER's 60% labeling accuracy without a matching drop in harm would confirm that execution-checking, not the model's abstraction skill, is what makes the reasoning safe.

Finally, on SWE-bench we test whether the overfitting rate after refinement falls below the no-refinement rate. That is the result prior work did not achieve.