Edge-Flip Twins: Detecting Hidden Benchmark Contamination with Hybrid Graph Problems

When a language model has seen benchmark questions during training, its score stops measuring reasoning. The usual way to catch this is to inspect the model's token probabilities and ask whether the benchmark text looks "too familiar." For modern reasoning models that approach has stopped working. A short round of reinforcement learning, or training on worked solutions, pushes these detectors to near coin-flip accuracy even when contamination inflates scores by about ten points. We propose a behavioral test in their place. For each benchmark item, build a twin that reads almost identically but whose correct answer is provably different. A model that learned a reusable procedure answers both correctly. A model that memorized the pairing between this kind of question and its answer keeps giving the original answer to the twin.

Making such twins requires problems where a one-word change in the text forces a different answer that we can certify. Hybrid dependency models supply this. These are graphs that mix three kinds of links between variables: "A causes B" (directed), "A and B settle into a mutual balance" (undirected, as in peer influence or equilibrium), and "A and B share a hidden common cause" (bidirected). Swapping one link type for another changes which variables are independent, or whether a causal effect can be computed at all. The theory of these graphs lets us compute the new answer exactly. We would build a generator of hybrid-graph reasoning problems with exact labels and edge-flip twins, and use it for two things: as a contamination probe that does not depend on token probabilities, and as a fresh benchmark testing whether models reason about link semantics or fall back on familiar causal clichés.

Core Claim

The claim is that answer stickiness under certified edge flips detects contamination in reasoning models better than the probability-based detectors that the fragility study of contamination detection showed collapse to 50–58% AUROC. Answer stickiness means the rate at which a model gives a seen item's answer to its flipped twin. The same twin design also settles a question that study left open. When contamination with worked solutions inflates scores, it is unclear whether the model has learned a transferable procedure, which would make the inflation partly real skill, or a template-to-answer mapping that the detectors simply cannot see. Twins separate these two cases because the procedure gives the right twin answer and the mapping gives the wrong one.

Formally, let item $i$ have certified answer $y_i$ and let its twin $\tilde{x}_i$ have certified answer $\tilde{y}_i \neq y_i$. The item-level stickiness score is

$$s_i = \Pr\big[f(\tilde{x}_i) = y_i\big],$$

where $f$ is the model under test, sampled several times. A high $s_i$ combined with a correct answer on $x_i$ is the contamination signature. Answer-preserving perturbations cannot produce this signature. Paraphrases are one example, and the same holds for DyVal's reordering of the problem description (DyVal). Under those perturbations a memorized answer is still the correct answer.

Why hybrid graphs, and what prior work supplies

Current dynamic benchmark generators supply the template but constrain the scope. DyVal generates arithmetic, logic and reachability problems from directed acyclic graphs (DAGs). It found that models with strong static scores, such as phi-1.5 and WizardMath-13B, scored near zero, and that GPT-4 lost 13.6% on reachability when the description order was reversed. DARG extracts DAGs from GSM8K, BBQ and BBH items, perturbs their depth and width, and verifies labels by running Python forward along the graph. Both are restricted to DAGs and to forward computation. Neither builds problems where one link-type change flips the answer, and DARG's forward-execution check cannot label equilibrium or confounding structure.

Three bodies of work supply the method. The first is Gaussian chain graphs. In these, variables sit in ordered layers, directed links carry regressions between layers, and undirected links carry residual partial correlations within a layer, estimated as in penalized multi-layered Gaussian graphical models. Labels can be computed exactly from the implied covariance. Second, Peña's faithfulness result for Gaussian chain graphs (Faithfulness in Chain Graphs: The Gaussian Case) proves that almost all parameter draws produce exactly the independences the graph implies. It also proves that moralization and c-separation are complete separation criteria. Together these guarantee that a link-type flip changes the true independence answers for generic parameters, not merely in principle. Third, the identification algorithm for segregated graphs is sound and complete for graphs mixing all three link types. It provides exact yes/no labels, and when the answer is yes, an estimating formula for whether an effect is identifiable under interference.

Work on separating contagion from latent confounding in networks motivates the confounding-versus-influence twin family. That distinction is exactly what network analysts find hard, and it is exactly where a "correlation means causation" shortcut gives a wrong answer.

The causal-reasoning motivation comes from Chi et al.. They showed that near-perfect scores on COPA-style benchmarks collapse on post-cutoff news, with Claude 3 Opus below 70% on CausalProbe-H. Their probe covers only one-directional cause–effect pairs, and once it is published it can be scraped like any other web text. Reasoning-driven synthesis found that LLM-written multi-step questions show no post-cutoff decay, and that influence-function hit rates fall from 77.5% to 17.5%. The authors could not tell whether this reflects real robustness or blind detectors. Our twins test that distinction directly and offer an alternative to their unstructured prompting.

Research Program

We would build a generator with three problem families. The first family asks conditional-independence queries ("given Z, does learning X tell you anything about Y?") on randomly drawn chain graphs. The second asks numeric queries, such as a partial correlation or a regression coefficient, computed in closed form from sampled layer parameters. The third asks identifiability queries ("can the effect of A on Y be computed from observed data?") on segregated graphs, labeled by our implementation of the Sherman–Shpitser fixing procedure.

Each graph is rendered into text in two styles. One is abstract variables. The other is domain stories drawn from settings the literature actually models, such as gene–protein–drug layers or peer networks. Each link type has a small fixed set of phrasings. A twin is produced by replacing one link's phrasing. The pair is kept only if the labeler certifies that the answers differ.

We would also tag a subset of items as heuristic-conflict items. These are items where reading every link as a DAG arrow gives the wrong answer. The canonical case is the chain-graph structure in which an undirected within-layer link changes what conditioning opens, compared with the DAG reading. On these items, systematic errors reveal a fallback to the DAG reading, as opposed to random failure.

Label correctness gets two independent checks. Every label is computed by two separate solvers: symbolic separation and numeric covariance. In addition, Monte Carlo samples from each Gaussian graph are tested to confirm that the stated independences hold empirically. We would release the generator, not a fixed item set, inside PromptBench, so that items can be regenerated after any leak.

Baselines

The naive reference is raw accuracy with no contamination check, reported for contaminated and clean models. It shows how large the inflation is that any detector must explain.

The strongest existing competitors are the ten probability-based detectors evaluated in the fragility study, with LiRA and loss as the main ones. They are the only established contamination test that needs no knowledge of the training data. Reported numbers set the bar. LiRA reaches 89.1% AUROC after supervised contamination, then falls about 14 points after one epoch of GRPO. In the worked-solution setting, which inflated DeepSeek-R1-Distill-Llama-8B by 11.7%, nearly all ten detectors average 50–58% AUROC. We would rerun these detectors with the published settings on our own contaminated checkpoints, using the same seen/unseen item splits and the same reference models for LiRA. Our method beats them if stickiness AUROC exceeds the best detector by at least ten points in the post-reinforcement-learning and worked-solution conditions, with bootstrap confidence intervals that do not overlap. It must also not lose in the plain supervised condition.

The third baseline is answer-preserving perturbation consistency. It uses paraphrases plus DyVal-style reversed and random description orders, scored as the accuracy drop from the original to the perturbed item. This is the closest behavioral competitor, and it costs no new labeling machinery.

The key ablation is DAG-only twins. In this ablation, flips reverse or delete arrows inside DyVal-style DAG problems, using the same models, item counts and contamination budget. It isolates whether the three-link-type hybrid structure adds detection power beyond flip-based twins in general.

Finally, an oracle reports the accuracy gap between seen and freshly generated items. Only the experimenter can compute it, so it serves as an upper bound, not a usable detector.

Why not just…?

Why not just use the existing probability-based detectors? The evidence against them is direct. The fragility study shows that reinforcement-learning clipping shrinks the probability gap between seen and unseen items, and that worked-solution training leaves almost no token-level trace. We rerun them as our main baseline, so that failure is measured again on our own checkpoints, not assumed.

Why not just paraphrase or reorder items and check whether accuracy holds? Answer-preserving perturbations cannot separate procedure learning from template-answer memorization, because under both explanations the memorized answer stays correct. Contamination of the worked-solution kind is exactly what survives rewording, which the reasoning-synthesis results suggest. This is a real competitor in the supervised-only condition, and the head-to-head comparison will show whether it remains competitive after reinforcement learning.

Why not just flip arrows in DyVal-style DAGs and skip the hybrid machinery? This is the most serious threat, and we treat it as an ablation, not a straw man. If DAG flips give the same stickiness AUROC, then hybrid graphs add nothing for detection. Their contribution would then shrink to the benchmark side: testing equilibrium and confounding semantics that DAGs cannot express, and exposing a DAG-reading fallback on heuristic-conflict items. We would report that outcome honestly. Our prior is that hybrid flips give more twins per item, with three link types and therefore two alternatives per link, and that undirected-to-bidirected flips are harder to get right by surface association.

Why not just harvest fresh post-cutoff text? Probes like CausalProbe-2024 lose freshness once they are published. They also cannot control structure, and they offer no item-level twin with a certified different answer (Chi et al.).

Proposed Experiments

The first experiment validates the generator. We would generate 500 items per family at four graph sizes, matching DyVal's per-level scale, and report agreement between the two solvers and the Monte Carlo checks.

The second experiment evaluates open models such as Llama-3, Mistral and DeepSeek-R1-Distill-Llama-8B, with accuracy broken down by link type and by twin pair. It asks whether models treat "share a hidden cause" as "causes." The diagnostic is the error rate on heuristic-conflict items compared with matched non-conflict items. No reported result was found on Lacuna for any model on hybrid-graph reasoning tasks, so these numbers would be new.

The third experiment is the decisive contamination study. It reproduces both stages of the fragility protocol on our items. In stage I, supervised contamination is followed by one epoch of clean GRPO. In stage II, a model is fine-tuned on worked solutions for a seen half of the items. For both stages we measure stickiness AUROC against all baselines.

Two outcomes would decide the question. If seen items gain accuracy while their twins show high stickiness, then the inflation is memorized answer mapping that the probability detectors miss. If twins and fresh items gain as much as seen items, the "cloaking" is largely genuine procedure transfer, and the study's alarm should be reframed. Either outcome resolves a tension the literature currently leaves open. The DAG-twin ablation then tells us whether hybrid structure was necessary to reach that answer.