Structural Twins: Separating Recall from Repair in Code Benchmarks

When a code model fails a test, sees the error, and then fixes its program, we usually credit it with debugging. On benchmarks the model may have read during training, there is a second explanation. The error message may simply cue the model to recall a solution it memorized. Current contamination tools cannot tell these apart. They either flag problems whose text resembles the training data or switch to problems published after the training cutoff. Both approaches change difficulty and topic along with contamination, so any drop in scores mixes "the model memorized" with "the problems got harder."

We propose to build structural twins of benchmark problems and use them to measure how much of iterative code repair on standard benchmarks is actually recall. A structural twin is a new problem whose reference solution has exactly the same tree shape as the original: the same nesting, the same number of arguments at every node, the same types. The operators and constants are resampled, so the computation is genuinely different. Writing each solution as a delimiter-free prefix sequence makes the construction mechanical, and it also gives an exact distance between any candidate program and any reference. With that distance we can ask a question no current benchmark answers. When a model repairs its code on a twin, does it move toward the twin's solution, or does it drift back toward the memorized original?

Core Claim

Holding tree shape fixed while changing the computation turns contamination from a per-problem similarity score into a controlled experiment. The design is a difference-in-differences:

  1. Build twins both for suspected-contaminated problems (MBPP and HumanEval items with known matches in StarCoderData) and for fresh problems (post-cutoff LiveCodeBench items).
  2. On fresh problems, the gap between original and twin estimates the cost of twinning itself, such as slightly unnatural specifications.
  3. On contaminated problems, any additional gap beyond that cost is attributable to memorization.

We will measure this separately for single-shot generation and for repair gain, where repair gain is the extra problems solved by feedback-driven repair beyond what the same compute buys through independent sampling.

We predict that on contaminated items repair gain is inflated relative to twins. We also predict a visible snap-back signature: on twins, repair turns will measurably move the candidate toward the original problem's solution. If both effects are absent, the reported self-repair gains on static benchmarks are trustworthy, and that is also worth knowing.

Where this sits in prior work

Several papers motivate the question.

  • Quantifying Contamination in Evaluating Code Generation Capabilities of Language Models finds exact matches in StarCoderData for 20.8% of MBPP problems. It reports StarCoderBase-15.5B at 72% on the most-similar decile versus 22% on the least-similar decile. Similarity and difficulty are not separated in that analysis, and it studies only single-shot generation.
  • LiveCodeBench shows a sharp drop in scores after the training cutoff. It also reports self-repair lifting GPT-4-Turbo from 24.5% to 36.9% on fresh problems. So repair is real at least for strong models, but the paper cannot say how much repair gain on older benchmarks is inflated.
  • Is Self-Repair a Silver Bullet for Code Generation? shows GPT-4's own diagnoses are obviously wrong in 40% of sampled cases. It also finds that independent sampling often matches or beats repair at equal compute. That makes a hidden recall channel a live possibility: repair can succeed even when the diagnosis is wrong.

Other papers supply the method.

  • DyVal generates reasoning tasks from graphs with controlled depth, but only for arithmetic, logic, and graph problems, not executable programs. It builds fresh tasks from scratch; we anchor ours to existing benchmark items so the effect of contamination can be isolated.
  • A²RBench exposes memorization by remapping symbols, a 17.7% drop. Renaming changes surface tokens but leaves the logic intact, and the Quantifying paper had to use AST-level matching with the Dolos toolkit precisely because renamed copies circulate in training data. We keep the renaming manipulation as an ablation rather than the main probe.
  • Deep Learning For Symbolic Mathematics, ODEFormer, and Most of a Formal Proof is Forced establish that prefix serialization with fixed arity is unambiguous and inverts back to exactly one tree. That property is what lets us swap operators while keeping the shape, and compute exact tree distances.

One paper constrains the design. The "Forced" paper finds that models need substantial capacity just to absorb unfamiliar tree syntax. We therefore never make the model read or write prefix code. Prefix form is only the internal representation for the generator and the analysis. Models see Python and natural-language specifications.

The most relevant prior connections between repair and contamination are TGPR and LiveCodeBench. TGPR decontaminates its training data by n-gram filtering and evaluates on a later LiveCodeBench window. Both treat contamination as something to filter out. Neither measures how contamination changes the behavior of the repair loop itself.

Research Program

Step 1: A small typed language for solutions. We define a functional language with fixed arity. It covers integer and float arithmetic, comparisons, conditionals, list operations (map, filter, fold, slice, sort, zip), string operations, and bounded iteration. The goal is for the core logic of a meaningful subset of MBPP, HumanEval, and easy or medium LiveCodeBench reference solutions to be expressible in it.

  • Reference solutions are translated into the language by an LLM translator.
  • Each translation is accepted only if it matches the original's outputs on all benchmark tests plus extra randomly generated inputs.
  • We report what fraction of each benchmark this process covers. We make no claim about uncovered problems and do not guess the fraction in advance.

Step 2: Generating twins. Each accepted solution is written as a prefix sequence. Every operator token belongs to a signature class, meaning a set of operators with the same number and types of arguments. A twin replaces a random subset of operator tokens with others from the same class and resamples constants, which keeps the arity sequence identical.

A twin is kept only if all of the following hold:

  • It type-checks.
  • It terminates on the test inputs.
  • Its outputs differ from the original's on most test inputs.
  • It is not trivially degenerate, for example a constant function.

Test inputs come from the original benchmark and from random generation. Expected outputs come from executing the twin's tree. Each twin gets a natural-language specification written by a separate model from the tree alone, never from the original problem text. Spot-checked human audits confirm that each specification determines the tree's behavior on the tests.

Step 3: Repair protocol and trajectory analysis. We run the same repair protocol on originals and twins: generate a program, execute it, show the model the failing tests and traceback, and let it revise for up to $R$ rounds. We follow the compute accounting of the Self-Repair paper so that repair can be compared with independent sampling at an equal token budget.

For every intermediate program that parses into the language, we compute tree edit distance to the twin's reference, $d_{\text{twin}}$, and to the original problem's reference, $d_{\text{orig}}$. A snap-back event is a repair turn in which $d_{\text{orig}}$ drops sharply while $d_{\text{twin}}$ does not improve. A secondary diagnostic, in the spirit of the "Forced" paper's entropy analysis, compares the model's per-token surprise on the original's reference solution with its surprise on the twin's reference.

Step 4: The estimate. For model $m$ and metric $y$ (pass@1, or repair gain at matched compute), we compute

$$\Delta_m = \big(y_{\text{orig}}^{\text{contam}} - y_{\text{twin}}^{\text{contam}}\big) - \big(y_{\text{orig}}^{\text{fresh}} - y_{\text{twin}}^{\text{fresh}}\big),$$

where "contam" means problems flagged by Dolos or Levenshtein matches in the model's known training corpus, and "fresh" means LiveCodeBench problems released after that model's cutoff. The second bracket subtracts the pure cost of twinning, so $\Delta_m$ estimates the memorization premium.

We prioritize open models whose training data is documented or whose cutoffs are known: StarCoderBase-15.5B, Code Llama, DeepSeek-Coder-33B, and OpenCodeInterpreter-33B. The last was trained on multi-turn repair dialogues from Code-Feedback, which makes it the most interesting test of whether repair training amplifies recall.

Baselines

Naive reference point. This is the repair gain measured on the static benchmark as-is: pass@1 before and after feedback on HumanEval or MBPP. The file gives OpenCodeInterpreter at 79.3 single-turn rising to 82.9 with execution feedback on HumanEval pass@1. It is the number the community actually reports, so any claimed inflation is measured against it. We rerun it with our exact harness and budget.

Similarity-split decontamination. This follows Quantifying Contamination: compare scores on high-similarity versus low-similarity items, or drop items above 80% similarity. It reports a 34.4% relative HumanEval drop for StarCoderBase-15.5B after decontamination. It is the strongest existing contamination estimator for static code benchmarks. We apply it to the same models, the same items, and the same repair protocol.

Temporal split. This is LiveCodeBench's self-repair evaluation on post-cutoff problems, which reports GPT-4-Turbo rising from 24.5% to 36.9%. It is the strongest contamination-free reference and the one a reviewer will say makes our work unnecessary. We rerun it with the same number of repair rounds and the same token budget as our other arms.

Repair-method baseline. Throughout, the comparison for repair is independent sampling at matched compute, as in the Self-Repair paper. That paper reports GPT-4 self-repair beating independent sampling by only about 8% on its APPS subset.

What counts as beating these baselines. Our estimator must predict something the others cannot. Concretely, for each model we use its twin-corrected repair gain on MBPP and HumanEval to forecast its repair gain on a LiveCodeBench window released after the twins are built. The twin estimate succeeds if its forecast error is lower than the error from the raw static gain and from the similarity-split gain, with difficulty-matched items and bootstrap intervals.

Ablation of the key ingredient. A renaming-only twin changes identifiers and specification wording but keeps the tree and operators identical, in the style of A²RBench's symbol remapping. It isolates whether changing the computation is what matters.

Why not just…?

Why not just use LiveCodeBench's temporal split? Post-cutoff problems differ from older ones in topic mix, difficulty distribution, and platform style. A drop after the cutoff therefore mixes contamination with distribution shift. The file itself notes the limited supply, 612 problems over fifteen months, and the risk of later ingestion. Temporal splits also cannot correct scores on existing benchmarks that papers keep reporting. We use the temporal split as a control inside the difference-in-differences and as the validation target. If the twin estimate forecasts fresh-problem repair no better than the raw static number does, the temporal split was sufficient, and we will report that.

Why not just rank problems by similarity to the pretraining corpus? Similarity and difficulty are entangled. Famous, simple problems are both the most copied and the easiest, so the 72% versus 22% decile gap in the Quantifying paper cannot be read as a pure memorization effect. Twins hold shape and signature fixed per item, so the comparison is within-problem. We will check directly whether the similarity-split estimate and $\Delta_m$ agree. Large disagreement on high-similarity easy items would show the confound.

Why not just rename symbols and paraphrase the prompt? This is the strongest threat, because it is far cheaper. Renaming removes surface cues but leaves memorized logic reachable. The Quantifying paper's need for AST-level matching indicates that logic-level copies exist in training data. The renaming-only ablation settles the question. If renaming twins produce the same $\Delta_m$ and snap-back rates as structural twins, the tree machinery is unnecessary and the recommendation becomes "just rename." We will state that plainly if it is what we find.

Why not just compare repair to independent sampling, since the Self-Repair paper already shows repair is weak? That paper measures whether repair beats resampling. It cannot tell whether the repair that does succeed is diagnosis or recall. Snap-back toward the original solution on a twin is a behavioral signature that no compute-matched comparison can detect.

Proposed Experiments

Validity of the construction. First we show that twins are real, fair problems:

  • Human-audited specification fidelity on a random sample of twins.
  • Twin versus original pass rates on post-cutoff LiveCodeBench problems for every model, which estimates the twinning cost. We want this cost to be small and similar across models.
  • Twin-generation coverage on MBPP, HumanEval, and LiveCodeBench, reported per benchmark.

Main measurement. We compute $\Delta_m$ for pass@1 and for matched-compute repair gain, across the open models listed, stratified by Dolos similarity band. We predict that $\Delta_m$ is largest for StarCoderBase-15.5B on items with 100% matches in StarCoderData, and that it is larger for repair gain than for single-shot pass@1 in models trained on repair dialogues.

Placebo check. We compute $\Delta_m$ using, as the "contaminated" group, LiveCodeBench problems released after the model's cutoff. The estimate should be indistinguishable from zero. A nonzero placebo means the estimator is picking up something other than contamination.

Snap-back analysis. We report the fraction of twin repair trajectories containing snap-back events, as a function of the original's similarity band. The decisive pattern is that snap-back rises with similarity to the training corpus and is near zero on twins of fresh problems. If snap-back is common even on fresh-problem twins, it reflects generic attraction to typical code rather than memorization, and we will interpret it that way.

Predictive validation. Using the protocol in the Baselines section, we freeze the twin-corrected estimates, collect a later LiveCodeBench window, and compare forecast errors across the three estimators.

Ablations. Renaming-only twins isolate the value of changing operators. Twins that change only constants test whether shallow changes suffice. Varying the number of repair rounds shows whether any recall premium concentrates in early rounds, which relates to the 2–4 round plateau noted in the literature.