Where Does a Leaked Benchmark Live? Locating Memorization by Structural Order

When a language model has seen a test set during training, its benchmark score goes up. Current detectors can say whether that happened. They cannot say what the model actually retained. It might have kept the exact wording. It might have kept the specific numbers and answer. Or it might have kept the shape of the solution, meaning which operations combine which quantities in which order. These cases matter differently. A model that memorized a solution's shape will still score well on a "rephrased" or "renumbered" test, so the rephrasing checks people rely on will miss it. This proposal turns an old idea from probabilistic grammars into a measuring instrument for this question. The old idea is the context-free independence assumption: a grammar rule's probability does not depend on where in the tree the rule is used.

The plan has three steps. First, parse each benchmark item into a derivation tree, which records how its solution is built. Second, build a ladder of test variants that keep progressively more of the original tree's structure. The lowest rung keeps only the rules, as a context-free grammar would see them. Higher rungs keep parent–child–sibling configurations, then the whole tree with new surface words, then everything. Third, compare each rung against freshly generated items that cannot have been leaked and that have the same size and shape. The rung at which a model's accuracy jumps above its fresh-item accuracy shows the structural order at which the leaked item is stored.

Core Claim

Contamination is not a single yes/no property. It has a structural order: the size of the fragment of the original derivation that the model retained. That order can be measured inside a single model, without a separate clean reference model. The measurement varies how much context the regeneration grammar is allowed to keep. Two parts are new. One is using the ladder of context-free, parent-conditioned and fragment-based grammars as a controlled perturbation axis for contamination. The other is the matched-fresh control, which a grammar supplies for free.

Formally, let $a_k$ be a model's accuracy on variants of the benchmark items that preserve structure up to rung $k$. Let $\tilde a_k$ be its accuracy on freshly sampled items with the same number of nodes, depth and operation counts, generated by the rung-$k$ grammar. The contamination excess at rung $k$ is

$$\Delta_k = a_k - \tilde a_k .$$

For a clean model, $\Delta_k \approx 0$ at every rung, because original-derived and fresh items differ only in provenance. For a contaminated model, $\Delta_k$ should stay near zero below the rung where the memorized fragment first survives and become positive at and above it. The location of that step is the diagnostic.

Research Program

Parsing items into derivations. The program starts with domains where items can be parsed reliably. SCAN has a known generating grammar, which makes it an exact sanity check (Generalization without Systematicity). In GSM8K, the solutions' calculator annotations give each problem an expression tree with typed quantities and entities (Training Verifiers to Solve Math Word Problems). HumanEval reference solutions have abstract syntax trees, and the program will use them as a harder stretch domain (Evaluating Large Language Models Trained on Code).

The grammar ladder. Each rung corresponds to a grammar family from the parsing literature, which defines precisely how much context each rung keeps.

Fragment probabilities are refined with latent subcategories (Latent-Variable PCFGs: Background and Applications), so recombined trees stay plausible.

Improving Grammar-based Sequence-to-Sequence Modeling with Decomposition and Constraints constrains the design. In that work, the fully factorized E model, which discards cross-node dependencies, fails on SCAN, while the P model, which keeps them, reaches 91–97%. That result is direct evidence that height-two structure carries information a context-free factorization drops, so Rungs 1 and 2 are not interchangeable.

Turning trees back into text. Each derivation must be written out as a natural-language problem. A language model is used only to verbalize a given tree. The output is accepted only if an independent parser recovers the same tree and the answer is recomputed by execution. This avoids the "generative ceiling" that A²RBench reports when an author model must invent the logic itself: here the grammar supplies the logic and the model only writes the words. Fresh controls at every rung go through the same writing pipeline, so any artifacts from that step cancel in $\Delta_k$.

Ground truth by deliberate contamination. Open models are fine-tuned on known subsets of GSM8K and SCAN under four leak types:

  • verbatim leaks;
  • paraphrase leaks, with the same tree and new words;
  • structure-only leaks, with the same height-two fragments and different trees;
  • no leak.

This follows the controlled-contamination protocol of ConStat and the explicit/implicit split of Generalization or Memorization. The question is whether the step in $\Delta_k$ recovers which leak type was applied.

Baselines

Naive reference: n-gram overlap. The do-nothing reference is n-gram overlap between items and model outputs, or against an open corpus such as FineWeb when the model's training data is known. It is run on exactly the same contaminated checkpoints. It is expected to catch verbatim leaks only. Beating it means detecting the paraphrase and structure-only leaks.

Strongest existing detector: ConStat. ConStat compares performance on original versus rephrased or synthetic items against clean reference models. It reports detecting 98.4% of sample-specific contamination in controlled experiments, where the best earlier baseline reached 71%. It is the strongest competitor because it is also performance-based. ConStat will be run with its own rephrasings and reference models, on the same checkpoints and with the same number of evaluation queries. On binary detection, the realistic target is to match it, not to exceed 98.4%. The method beats ConStat if it does two things ConStat cannot. First, it correctly identifies the leak type, measured as accuracy at recovering the structural order. Second, it keeps its detection rate when ConStat's reference models are removed.

Distribution-based detector: CDD. CDD from Generalization or Memorization measures how much sampled outputs collapse toward one string under token edit distance. That paper reports 21.8–30.2% relative gains over earlier baselines in accuracy and AUC. It is run with the same sampling budget. A strengthened variant is also run, applying CDD with tree edit distance over parsed solution trees. This variant isolates whether gains come from structural representation alone or from the ladder.

Ablations. The two-rung ablation keeps only Rung 0 and Rung 5, which amounts to a DyVal-style fresh-versus-original comparison (DyVal). It tests whether the intermediate rungs add anything. A second ablation removes the size matching of fresh controls, which tests whether difficulty confounds $\Delta_k$. A third replaces Rung 2's original fragments with random fragments of the same height, which tests whether item-specific structure, rather than fragment size, drives the excess.

Why not just…?

Why not just use n-gram overlap? ConStat and CDD both report that overlap methods are bypassed by rephrasing; the 71% ceiling of earlier baselines comes from ConStat. Overlap is also blind by construction to structure-only leaks. The structure-only leak condition in the experiments tests this directly. Overlap detection should sit near chance on it.

Why not just ask GPT-4 to rephrase the benchmark, as ConStat does? This is the real threat for binary detection, and the proposal concedes it may tie. The problem is control. A free rephrasing keeps the full derivation tree by default and adds variation that nobody has measured. That makes it effectively one point near Rung 3, so it cannot separate a paraphrase leak from a structure leak. It also needs clean reference models, which become scarcer as web crawls absorb more benchmarks. The two-rung and reference-free comparisons will show whether the extra rungs earn their cost. If $\Delta_k$ is flat between Rungs 1 and 3 in the deliberate-contamination experiments, the ladder adds nothing over rephrasing and the claim fails.

Why not just use DyVal's fresh generation and skip the original items? Fresh generation measures ability, not contamination: it can show that a model is weak, but not that a score was inflated, or by what. DyVal's own finding that WizardMath-13B "scored nearly zero" is consistent with contamination but does not localize it. The two-rung ablation is DyVal's comparison plus difficulty matching, so this proposal directly tests whether intermediate structure is needed.

Why not just run CDD on canonicalized parse trees? This is a plausible cheaper route to structure awareness, and it is included as a baseline rather than dismissed. It still needs heavy sampling, which Generalization or Memorization flags as costly. It also detects collapse onto one tree rather than which fragment order is retained. If tree-edit CDD recovers leak type as well as the ladder, the ladder is unnecessary, and the experiments will report that.

Proposed Experiments

Controlled contamination. The core experiment uses GSM8K and SCAN on deliberately contaminated open checkpoints. The main metric is accuracy at recovering the leak type from where $\Delta_k$ steps up. AUC for binary detection is a secondary metric.

The decisive check is the structure-only leak condition. The prediction is that $\Delta_k$ stays near zero through Rung 1 and becomes positive from Rung 2, while ConStat-style rephrasing and n-gram overlap show either full or no contamination with no localization. SCAN, whose grammar is exact, must reproduce this cleanly. If it does not, the parsing and rewriting pipeline is at fault, not the hypothesis.

A second check is calibration. On never-contaminated checkpoints, $\Delta_k$ must be statistically indistinguishable from zero at every rung. A nonzero value would mean the matched fresh controls do not actually control difficulty.

Audit of public models. The ladder is applied to public models where contamination is suspected. ConStat estimates about 8.3% inflation on GSM8K for Mistral-7b-v0.1. The aim is to ask, for the first time, at which structural order that inflation lives, and whether "renumbered GSM8K" variants still carry it.

Code stretch domain. HumanEval is the stretch domain. Tests for regenerated items are produced by executing transformed reference solutions. Generalization or Memorization reports a Leak Ratio of about 41.5% for ChatGPT on HumanEval based on HumanEval_R. The ladder can test whether that leak survives at the tree level, where a rephrasing such as HumanEval_R would not remove it.