A model that has memorized a benchmark question can often give the final answer without being able to compute the intermediate quantities that answer depends on. A model that actually reasons cannot. This proposal turns that asymmetry into a contamination detector. Each benchmark item is written as its reasoning graph, a small directed acyclic graph whose nodes are intermediate results and whose edges are operations. From that graph we build sub-questions at every scale: single operations, two-hop chains, and so on up to the full problem. Each sub-question is asked in a fresh context. Under genuine reasoning, accuracy should fall smoothly as scale grows. Under memorization, we expect a "scale inversion": the item is solved at the top scale more often than its own sub-scales predict. The test looks only at answers, not at token likelihoods. That matters because likelihood-based detection is now unreliable. Paraphrased contamination drops detection to about 1% true-positive rate at 1% false-positive rate (Evading Data Contamination Detection for Language Models is (too) Easy). Reinforcement-learning post-training pushes ten detectors to 50–58% AUROC on reasoning models (On The Fragility of Benchmark Contamination Detection in Reasoning Models).
The multi-scale graph literature contributes the measurement lens, not a gimmick. Jumping Knowledge networks read out a node's representation at every depth instead of only the last one (Representation Learning on Graphs with Jumping Knowledge Networks). We apply the same idea to the evaluated model's behaviour, reading out its competence at every hop-depth of the problem graph. The moment-depth result of Understanding the Representation Power of Graph Neural Networks in Learning Graph Topology says that computing a depth-$p$ relational quantity requires $p$ composition steps. That gives the principle behind the test: a computed answer passes through its sub-results, and a recalled one need not.
Core Claim
Contamination leaves a within-item signature: success at the top of the reasoning graph that is not supported by success at lower scales. This signature survives paraphrasing, because sub-questions are regenerated from the graph rather than from the leaked text. It also survives the RL-induced collapse of log-probability gaps, because it never uses log-probabilities. We further claim that the expected clean profile for an item is best predicted by a model that mixes local and path-level structure of its graph. Whether that predictor needs to be a multi-scale graph network or can be a simple regression is an empirical question we settle, not assume.
Formally, for item $i$ with reasoning graph $G_i$ of depth $D_i$, let $a_i(d)$ be the target model's accuracy over $K$ samples on sub-questions rooted at depth $d$. Let $\hat a_i(D_i)$ be the root accuracy that a clean-behaviour predictor $f$ expects given the graph and the lower-scale accuracies. The contamination score is
$$s_i = a_i(D_i) - \hat a_i(D_i), \qquad \hat a_i(D_i) = f\big(G_i,\ a_i(1),\dots,a_i(D_i-1)\big).$$
Here $f$ is fit only on reference models trained on data we control and know to be clean for these items. A large positive $s_i$ means the model "knows" the answer more than its demonstrated sub-competence explains. Benchmark-level significance is obtained by bootstrapping $s_i$ over items, in the spirit of the hardness-corrected testing of ConStat: Performance-Based Contamination Detection in Large Language Models.
Relation to Prior Work
Two lines of prior work supply the graphs. DyVal generates reasoning problems directly from directed acyclic graphs, so its intermediate nodes are exact. DARG extracts such graphs from existing GSM8K-style questions and verifies them with code execution. Both use the graph to create new, harder, uncontaminated items and then report aggregate accuracy retention. We instead decompose each existing item downward into its own sub-scales and compare scales within the item. That turns their evaluation scaffolds into a per-item detector for contamination that has already happened.
The detectors we must beat motivate the design by having failed. Likelihood methods (Loss, Min-K%, LiRA) collapse under GRPO and chain-of-thought training (On The Fragility of Benchmark Contamination Detection in Reasoning Models). Self-Critique entropy comparison (Detecting Data Contamination from Reinforcement Learning Post-training for Large Language Models) still reads token-level statistics and is limited when many valid reasoning paths exist. Partial-prompt reconstruction (Reasoning or Memorization? Unreliable Results of Reinforcement Learning Due to Data Contamination) needs the leaked surface text to match the benchmark text. CAP's consistency ratio (CAP: Data Contamination Detection via Consistency Amplification) perturbs items "horizontally" through shuffles and paraphrases. We perturb them "vertically" across reasoning scale, which a paraphrase-trained model has not seen.
Two papers constrain the design. The finding in Can Large Language Models Reason? A Characterization via 3-SAT that models exploit length shortcuts warns that sub-questions must not differ systematically from full questions in surface features. DARG's report that depth increases sharply hurt even strong models (Claude-3-Opus down over 50% with four extra steps) shows that clean accuracy falls with depth. That is exactly why the expected profile must be learned from reference models rather than assumed flat.
Research Program
The first component is a decomposition pipeline. For DyVal arithmetic and logic items, sub-graphs rooted at each intermediate node are rendered with DyVal's own description function, so they are exact by construction. For GSM8K and MATH-500 we use DARG-style extraction, producing a code-verified graph per item. For each intermediate node we render a self-contained question whose answer is that node's value, matching the original's style and length distribution. Every sub-question is checked by executing the graph.
The second component is the clean-profile predictor $f$. Its inputs are the graph and the lower-scale accuracies; its output is the expected root accuracy. We fit it on reference models fine-tuned on data we control, and therefore know to be clean for these items. The simplest version is a logistic regression on depth, width, operation counts and the lower-scale accuracies. The multi-scale version is a Jumping-Knowledge graph network that reads node features from every message-passing layer. The hypothesis is that an item's difficulty mixes local properties, such as operation type and operand size, with path-level properties, such as chain length and branch merges. This is the mixing of low- and high-order moments that Understanding the Representation Power of Graph Neural Networks in Learning Graph Topology shows single-scale graph networks miss. If the regression matches the graph network, we report that and use the regression. The contamination claim does not depend on the graph network.
The third component is controlled contamination. We take open models, among them Qwen2.5-7B-Instruct and DeepSeek-R1-Distill-Llama-8B, which appear in the cited contamination studies. We contaminate a random half of each benchmark under four regimes:
- verbatim supervised fine-tuning;
- paraphrased fine-tuning following the evasive augmentation recipe of Evading Data Contamination Detection for Language Models is (too) Easy;
- chain-of-thought supervised fine-tuning;
- supervised fine-tuning followed by one epoch of GRPO on clean data, the cloaking setup of On The Fragility of Benchmark Contamination Detection in Reasoning Models.
The uncontaminated half serves as negatives, which yields item-level ground truth.
Baselines
The naive reference point is raw top-scale accuracy, which a contaminated model inflates by construction. For calibration, the fragility study reports an average pass@1 inflation of 8.8% from supervised contamination (On The Fragility of Benchmark Contamination Detection in Reasoning Models). A second naive detector scores items by depth-adjusted accuracy alone, without sub-question queries. It checks whether the sub-scale queries add anything beyond item difficulty.
Likelihood detectors, Loss, Min-K% and LiRA, run on the same models and items with their standard settings. LiRA gets the same reference-model budget as our predictor $f$. LiRA is the strongest detector before RL. It reaches 89.1% AUROC on supervised-contaminated models, but falls about 14% after one GRPO epoch and to 50–58% AUROC on post-training reasoning models (On The Fragility of Benchmark Contamination Detection in Reasoning Models).
Self-Critique (Detecting Data Contamination from Reinforcement Learning Post-training for Large Language Models) is the strongest existing method for RL-stage contamination. It reports an average AUC of 0.70 on Qwen2.5-7B-Instruct on RL-MIA, where likelihood methods score 0.42–0.53. We run it on RL-MIA and on our GSM8K and MATH-500 splits, with a sampling budget matched to ours in total generated tokens.
Partial-prompt answer accuracy (Reasoning or Memorization? Unreliable Results of Reinforcement Learning Due to Data Contamination) reports 65.8% exact match on MATH-500 from an 80% prompt for Qwen2.5. CAP and ConStat are run as benchmark-level tests, comparing detection power at fixed item counts.
Two ablations isolate the key ingredients. The first replaces vertical sub-scale queries with CAP-style horizontal paraphrases at the same query budget. It tests whether scale, rather than mere re-querying, carries the signal. The second swaps the multi-scale predictor for a single-scale graph network and for plain regression.
Beating these baselines would mean the following. On the post-GRPO and chain-of-thought regimes, item-level AUROC should be clearly above Self-Critique's 0.70 and above the 50–58% likelihood range. On the paraphrased regime, true-positive rate at 1% false-positive rate should be far above the roughly 1% reported for existing detectors.
Why not just…?
Why not just compare accuracy on the original benchmark against DARG-perturbed or ConStat reference versions? That detects contamination of a benchmark on average. It cannot say which items are contaminated, and it needs a reference benchmark of matched hardness. Our score is computed within each item, and its benchmark-level aggregate can be compared directly against ConStat's. ConStat reports δ≈8.2% for Mistral-7b on GSM8K, so it is a real competitor at the aggregate level. If it matches us there, our contribution narrows to item-level localization, and we will say so.
Why not just check the intermediate steps in the model's own chain of thought? A model contaminated with chain-of-thought data reproduces plausible intermediate steps along with the answer. Its own transcript is therefore part of what was memorized. Asking sub-questions in fresh, separately phrased contexts removes the scaffold of the memorized trajectory. The chain-of-thought contamination regime tests this directly, by scoring transcript-step correctness as a baseline against independent sub-question accuracy.
Why not just regenerate items with new numbers, as in RandomCalculation? Regeneration produces a clean benchmark going forward, which is valuable. It does not tell you whether reported results on the existing GSM8K or MATH-500 were inflated. DARG also notes that numerical perturbation mainly tests arithmetic rather than reasoning structure. The two approaches are complementary, not substitutes.
Why not just a regression on depth instead of a multi-scale graph network? This may well be enough, and the predictor ablation decides it. The detector stands either way. The graph network earns its place only if it reduces false positives on clean models with irregular graphs, such as wide-and-shallow versus narrow-and-deep items.
Proposed Experiments and Decisive Checks
The main experiment reports item-level AUROC and true-positive rate at 1% false-positive rate across the four contamination regimes. It covers DyVal arithmetic and logic, where graphs are exact, then GSM8K and MATH-500 with extracted graphs, and RL-MIA for the RL setting. Every baseline above runs on identical splits.
A false-positive check runs the full test on clean models over freshly generated DyVal items and RandomCalculation-style problems, where no contamination is possible. The score distribution there must center on zero. Otherwise the inversion reflects sub-question rendering artifacts, not memorization.
An adaptive-adversary check contaminates the training set with the sub-questions as well as the full items. This is a known limit: the signal should shrink. We will measure how much extra leaked data the adversary needs to erase it. The detector is useful if evasion requires leaking the full multi-scale decomposition of every item, which is far harder than the paraphrasing evasion that currently works.
A localization check applies the score to public instruction-tuned models on GSM8K, without ground truth. It tests whether high-scoring items cluster where ConStat-style aggregate tests already flag inflation.
The proposal fails if any of three things happens: scale inversion does not separate contaminated from clean items after GRPO cloaking, horizontal paraphrase queries do as well as vertical ones, or clean models show inversion at comparable rates.
References
- Evading Data Contamination Detection for Language Models is (too) Easy
- On The Fragility of Benchmark Contamination Detection in Reasoning Models
- Representation Learning on Graphs with Jumping Knowledge Networks
- Understanding the Representation Power of Graph Neural Networks in Learning Graph Topology
- ConStat: Performance-Based Contamination Detection in Large Language Models
- DyVal: Dynamic Evaluation of Large Language Models for Reasoning Tasks
- DARG: Dynamic Evaluation of Large Language Models via Adaptive Reasoning Graph
- Detecting Data Contamination from Reinforcement Learning Post-training for Large Language Models
- Reasoning or Memorization? Unreliable Results of Reinforcement Learning Due to Data Contamination
- CAP: Data Contamination Detection via Consistency Amplification
- Can Large Language Models Reason? A Characterization via 3-SAT