A model that has actually worked out a multi-step problem has also worked out its pieces. If it reliably gets the final answer to a grade-school word problem, it should be at least as good at the smaller questions the problem is built from, such as "how many apples remain after step three?" A model that has seen the benchmark item during training does not have to follow this logic. It can produce the right final answer while failing the pieces it supposedly computed along the way. We propose to turn this asymmetry into a contamination detector. Each benchmark item's reasoning structure is represented as a graph and coarsened hierarchically into self-contained sub-problems at several scales. Each sub-problem is posed on its own, and the detector flags items where final-answer accuracy exceeds what the model's accuracy on the pieces can support. We call that excess the compositional deficit.
This matters now because the standard detectors have stopped working on reasoning models. Most of them ask whether the model assigns suspiciously high probability to test text. On The Fragility of Benchmark Contamination Detection in Reasoning Models shows that one epoch of reinforcement learning on clean data drives such detectors toward chance. When the contamination is supplied as chain-of-thought training data, all ten detectors it evaluates sit at 50–58% AUROC. Our test needs no log-probabilities and no comparison of long sampled traces. It only needs correctness on short, automatically generated questions, and it rests on a logical inequality rather than a statistical fingerprint that training can erase.
Core Claim
Represent a benchmark item as a directed acyclic graph, a dependency graph with no cycles, in which nodes are intermediate quantities or propositions and edges say which results feed which. This is the representation that DyVal uses to generate problems and that DARG extracts from GSM8K questions. Hierarchical coarsening merges nodes into "super-nodes" repeatedly, which yields nested partitions $\mathcal{G}^{(0)} \to \mathcal{G}^{(1)} \to \dots \to \mathcal{G}^{(L)}$. Every super-node $v$ at level $l$ is a connected piece of the computation with a single output. It can be written as a stand-alone question that contains only its own premises and the values flowing in from its boundary.
If the final answer is derived rather than recalled, it requires computing every super-node on the path to the answer. For each level we therefore define
$$s_l = \hat p(\text{full}) - \min_{v \in \mathcal{V}^{(l)}} \hat p(v),$$
where $\hat p(\text{full})$ is the model's empirical accuracy on the original item over repeated samples, and $\hat p(v)$ is its accuracy on the stand-alone sub-question for super-node $v$ at level $l$.
For a genuine reasoner, $s_l$ should be near or below zero. The only slack comes from posing a sub-question out of context, which can make it slightly harder or easier. We measure that slack instead of assuming it away. For each model we fit the distribution of $s_l$ on freshly generated DyVal instances, which cannot be contaminated. An item's contamination score is how far its profile $(s_1,\dots,s_L)$ sits above that calibration.
The new element is the use of logically entailed, strictly easier sub-problems as a consistency test. Existing dynamic benchmarks only grow or perturb graphs. DyVal adds depth and width, and DARG adds steps, branches and larger numbers. None of them removes structure to build an internal consistency check for a specific item.
Research Program
The first component is a coarsening procedure suited to reasoning graphs. Classical coarsening targets undirected graphs and aims to preserve spectra. Examples include the local multilevel merging and spectral k-means methods of Graph Coarsening with Preserved Spectral Properties, and the Graclus-style binary hierarchy in Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. We reuse their multilevel greedy-merging design but change the objective in two ways.
First, the contracted graph must stay acyclic. We therefore only merge node sets that are convex, meaning any path between two members stays inside the set. Second, each super-node should have a small boundary, so that its sub-question needs few injected values and reads naturally. The boundary constraint follows the intuition behind CoRe-GNN. That paper separates computation within a cluster from the few messages passing between clusters. For us, a super-node's interior becomes a sub-problem, and its boundary edges become the given values.
We aim for levels that roughly halve the length of the longest chain of dependencies. DyVal and DARG both find that depth drives difficulty far more than width, so halving depth gives each level a predictable drop in difficulty.
The second component turns each super-node into text and computes its answer. For DyVal tasks this is exact, because the graph is the ground truth. For GSM8K we follow DARG's pipeline: an LLM extracts the graph, generated code verifies it, and the code also computes every super-node's value. Items whose extracted graph fails to reproduce the gold answer are discarded. Sub-questions are rewritten in fresh wording rather than cut out of the original text. Otherwise, surface overlap with a memorized item could leak its answer into the sub-question.
The third component is the scoring and calibration described above. We will also analyze which levels carry the signal. Our hypothesis is that verbatim answer memorization shows up at every level. Chain-of-thought contamination, where the model has memorized a trace, should appear mainly at coarse levels, because fine-grained single steps are easy regardless of contamination.
Baselines
The naive reference point is final-answer accuracy alone, together with the gap between accuracy on the original item and accuracy on a DARG-style numerically perturbed twin. The perturbation gap is the check most practitioners would run first. It shows what can be learned without any decomposition.
The strongest likelihood-based competitor is LiRA, a reference-model likelihood ratio test for membership. On The Fragility of Benchmark Contamination Detection in Reasoning Models reports 89.1% AUROC for LiRA on Stage I SFT contamination of Qwen2.5-7B-Instruct before RL, a drop of about 14 points after one GRPO epoch on clean data, and 50–58% AUROC across detectors in Stage II chain-of-thought contamination. We rerun LiRA on our own contaminated checkpoints with the same reference models and membership splits.
The strongest behavioral competitor is Min-kNN Distance from Detecting RLVR Training Data via Structural Convergence of Reasoning. It samples 32 completions per prompt and averages the smallest nearest-neighbour edit distances among them. That paper reports an average AUC of 0.70 across 1.5B–32B models and 0.76 on OpenR1-Distill-7B. We run it with N=32 on the same items. We also give our method a matched budget of generated tokens, so the comparison is not won by extra sampling.
To beat these baselines, our method must reach higher item-level AUROC than both in the post-GRPO and Stage II settings under the matched token budget, with a confidence interval from bootstrap over items. A pre-registered target is at least 0.75 AUROC in Stage II, where likelihood detectors sit near chance.
Three ablations isolate what matters. The first replaces the hierarchy with random connected contraction at matched super-node sizes, which tests whether principled coarsening matters at all. The second uses only the finest level, one question per step, which tests whether multi-scale structure matters. The third uses a single "truncated prefix" sub-question, which tests whether a partition of sub-problems matters. If random contraction matches our coarsening, we will report that the signal comes from decomposition itself and not from the coarsening algorithm.
Why not just…?
Why not just perturb numbers or rephrase the question? Perturbation catches verbatim memorization, and A²RBench finds a 17.7% drop under symbolic remapping. It is weaker when a model has internalized a problem's reasoning pattern. Fragility's Stage II result shows exactly this case: models become confident on unseen, similar problems, so a perturbed twin is solved about as well as the original and the gap vanishes. Our sub-questions are not new problems. They ask about values that the original solution must contain, so a model that recalls the answer pattern without the computation should fail them. This is a real competitor on Stage I contamination, and the perturbation-gap baseline will show whether we add anything there.
Why not just apply Min-kNN with a better distance, such as parsing traces into graphs or using sentence embeddings? This was the other obvious combination of the two directions. We set it aside because it keeps Min-kNN's main costs: 32 long samples per item and roughly 6.65 seconds per query as reported. It would also add trace-parsing noise. An off-the-shelf embedding distance would probably capture "same strategy" as well as a hand-built graph metric. Our test instead exploits a logical constraint that trace similarity cannot express. We still include embedding-based Min-kNN as a variant, in case it closes the gap.
Why not just ask about every intermediate step? Single steps are usually trivial, so $\min_v \hat p(v)$ sits near one and the inequality has no power. A contaminated chain-of-thought model may also have learned local steps honestly. Coarse super-nodes test multi-step composition, which is what contamination inflates. The finest-level ablation settles this empirically, and if it matches the full hierarchy we will adopt it for its simplicity.
Why not just use a likelihood detector before RL? Auditors rarely control the training stage, and Fragility shows the likelihood signal is erased by exactly the pipelines used to build current reasoning models.
Proposed Experiments
Ground-truth membership comes from contaminating models ourselves, reproducing Fragility's protocol. In Stage I, we fine-tune Qwen2.5-7B-Instruct on half of a pool of DyVal arithmetic, linear-equation and deductive-logic items at complexity levels D3–D4, plus GSM8K items with verified extracted graphs. We then run one GRPO epoch on clean data. In Stage II, we fine-tune DeepSeek-R1-Distill-Llama-8B on chain-of-thought solutions for the member half. A third condition trains on member prompts with verifiable-reward RL, matching the setting in which Min-kNN was designed. The held-out halves are the non-members. Fresh DyVal instances, generated after training, provide the per-model calibration of $s_l$.
We report item-level AUROC for every detector in every condition, the generated-token cost per item, and the accuracy inflation due to contamination. The last figure lets us check that we reproduce Fragility's reported 8.8% and 11.7% boosts.
The decisive checks are threefold. On uncontaminated models, the calibrated score must stay flat: its false-positive rate on fresh instances should match the nominal rate. Otherwise the inequality is broken by context effects and not by memorization. In Stage II, the compositional deficit must clearly beat both LiRA and Min-kNN at matched token cost. The coarsened hierarchy must also beat random contraction and the finest-level-only ablation. If it does not, the contribution reduces to "ask sub-questions", which we would report as such.
A final stress test targets the method's known blind spot. We contaminate a model with full solution traces that include all intermediate values, rather than only the final answer, and ask whether the deficit survives. If the model then solves every sub-question too, its inflated score is at least consistent with the computation. Characterizing that boundary is itself a result.
References
- On The Fragility of Benchmark Contamination Detection in Reasoning Models
- DyVal: Dynamic Evaluation of Large Language Models for Reasoning Tasks
- DARG: Dynamic Evaluation of Large Language Models via Adaptive Reasoning Graph
- Graph Coarsening with Preserved Spectral Properties
- Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering
- CoRe-GNN: Multilevel Message passing on Coarsened graphs
- Detecting RLVR Training Data via Structural Convergence of Reasoning
- A²RBench: An Automatic Paradigm for Formally Verifiable Abstract Reasoning Benchmark Generation