Many families of graphs are defined by what they must not contain. A graph is a "cograph" if no four of its vertices induce a path, "claw-free" if no vertex has three mutually non-adjacent neighbours, and a line graph if it avoids nine specific small graphs. Checking membership in such a class is a clean reasoning task. The model has to find a small set of vertices whose induced pattern (those vertices plus every edge among them) matches a forbidden graph. The answer comes with a certificate, the witness vertex set, that anyone can check. Current anti-contamination benchmarks only make the instances fresh, by generating new random graphs on the fly. The rules stay the same: the famous characterizations sit in every textbook and on Wikipedia, and models have seen them thousands of times. If a model does better on "is this graph claw-free?" than on an equally hard question about a class nobody has ever named, then a benchmark built on famous classes is partly measuring recall of theorems rather than search.
We propose to measure this directly. For each famous class we build matched synthetic classes, defined by forbidden sets with the same sizes and search difficulty but with no name and no literature. We test models on instances where every confound we know of (density, degree profile, number and position of witnesses) is equalized across the pair. The accuracy gap between a famous class and its synthetic twins is a class-level contamination signal. It does not depend on the test instances ever having been seen. We then calibrate the signal by deliberately teaching small open models invented "theorems" about some synthetic classes and checking that the gap opens for exactly those classes. Existing likelihood-based contamination detectors should not see this effect, because no test instance was ever leaked.
Core Claim
Contamination in reasoning benchmarks can live at the level of the rule rather than the instance. Forbidden induced subgraph characterizations make rule-level contamination measurable. Membership in a class defined by a finite forbidden set is decided exactly by checking every small vertex subset. Because of this, we can construct unnamed classes that are computationally interchangeable with famous ones and attach a verifiable certificate to every answer. The matched-pair gap is
$$\Delta_C = \mathrm{Acc}(C) - \frac{1}{|S(C)|}\sum_{C' \in S(C)} \mathrm{Acc}(C'),$$
where $C$ is a named class, $S(C)$ is its set of matched synthetic twins, and $\mathrm{Acc}$ counts an answer as correct only if the accompanying certificate verifies. The claim is threefold. First, $\Delta_C$ is reliably positive for textbook classes in current models. Second, it rises under controlled rule-only contamination. Third, it is invisible to instance-level detectors.
The motivation comes from two findings in the contamination literature. On The Fragility of Benchmark Contamination Detection in Reasoning Models fine-tunes reasoning models on benchmark data and audits ten detectors. It shows that when models learn a reasoning schema rather than verbatim strings, ten detectors fall to 50–58% AUROC. It also shows that one epoch of clean reinforcement learning erases a signal LiRA (a likelihood-ratio membership test) had caught at 89.1% AUROC. That is exactly the regime where rule-level leakage would hide. Can Large Language Models Reason? A Characterization via 3-SAT generates random satisfiability formulas across a hardness parameter. It shows that shortcuts such as prompt length collapse only at the hard threshold, where GPT-4 search accuracy fell to about 10%. We borrow this lesson by generating instances at the membership boundary.
Relation to Existing Graph Benchmarks
Four benchmarks already use generated or curated graphs to sidestep contamination. Each differs from this proposal in a specific way.
- DyVal generates directed acyclic graph tasks on the fly and found that models strong on static benchmarks scored near zero.
- NLGraph generates random-graph problems over eight algorithmic tasks. Removing spurious degree correlations dropped accuracy by over 40%.
- GraphGym composes graph tasks up to 10,000 nodes.
- GrAlgoBench uses real-network graph slices and reports that graph memorization errors make up over 21% of top-model errors.
All four keep the task definitions fixed and familiar: shortest path, cycle detection, maximum clique. None asks whether familiarity with the task definition itself inflates scores. NLGraph's degree-correlation result motivates our matching. DyVal's finding that 33.8% of GPT-4 failures were unsubstantiated answers motivates scoring only verified certificates.
Building Matched Classes
The structural graph theory supplies the material. Named classes come in three familiarity tiers:
- Textbook classes: cographs, claw-free graphs, split graphs, threshold graphs, and line graphs via the nine Beineke graphs that BOREL LINE GRAPHS extends to the measurable setting.
- Research-literature classes: for example the $(P_5, K_{1,3}+P_1)$-free graphs, whose 344 five-vertex-critical members are catalogued in Some Results on Critical (P5,H)-free Graphs. These are published but rarely repeated.
- Synthetic classes: for each named forbidden set, we sample several unnamed sets of graphs. Each matches the named set in member count, vertex counts and edge counts, so the brute-force search space is identical. We discard any combination that a literature search associates with a studied class.
All four-vertex graphs have names, so twins differ mainly in which five- and six-vertex graphs they forbid, or in how familiar graphs are combined. We restrict attention to classes with finite forbidden sets. k-Leaf Powers Cannot be Characterized by a Finite Set of Forbidden Induced Subgraphs for k ≥ 5 builds an infinite chain of gadget obstructions for 5-leaf powers. It shows that some natural classes have no finite certificate set, so they cannot be checked the same way.
Instances are generated near the boundary. For a forbidden set $F$, we grow a graph on 12–30 vertices by random edge additions, rejecting any addition that creates an induced copy of a member of $F$. Then we either stop (a "member" instance) or plant exactly one induced copy and repair any accidental second copies (a "non-member" instance). For every pair of matched classes, we resample until edge density, degree sequence statistics, and the witness's position in the edge listing are statistically indistinguishable.
Vertex labels and edge order are randomized per instance. This blocks the order sensitivity DyVal found, where reversing the description order cost GPT-4 13.6% on reachability.
The model receives the forbidden list explicitly, as adjacency descriptions, in every condition. We use the class name only in an added "named" condition. In that condition, the class name is shown together with the explicit list; it isolates how much the name alone adds.
Every answer must include a witness vertex set for non-membership, which we verify exactly.
Research Program
The program has three stages.
Stage 1: Observational audit. We evaluate frontier and open models on all tiers and estimate $\Delta_C$ with confidence intervals from a permutation test over twins. We report it separately for the explicit-list condition and the named condition.
Stage 2: Controlled injection. This turns the observational gap into a calibrated measurement. Starting from Qwen2.5-7B-Instruct and DeepSeek-R1-Distill-Llama-8B (the models used in the Fragility study), we create twenty synthetic classes. For ten of them we write a small corpus that treats the class as established mathematics: an invented name, a "theorem" stating its forbidden set, alternative characterizations, and worked examples with certificates on graphs disjoint from the test pool. We fine-tune on this corpus mixed with general data; the other ten classes are held out.
A second arm leaks actual test instances with answers, which is classic instance contamination. A third arm follows either contamination with one epoch of clean reinforcement learning (GRPO) on unrelated graph tasks, reproducing the cloaking effect from the Fragility paper.
Stage 3: Code mode. We repeat Stages 1 and 2 with the model allowed to write and run Python. Familiar classes have ready-made library routines (networkx ships chordality and bipartiteness checks), while synthetic classes do not. A residual gap in code mode would be library recall, the "networkx cheating" pattern GraphGym describes.
An optional rule-induction variant gives labeled graphs and membership queries and asks the model to name the forbidden set. Here name recall should bite hardest. The counterexample-shrinking learner of Learning minor closed graph classes with membership and equivalence queries learns minor-closed classes by repeatedly shrinking counterexamples to isolate an excluded minor. We adapt it to induced subgraphs, where shrinking means deleting vertices only, and use it as an exact reference learner whose query count sets the efficiency bar.
Baselines
Naive shortcut classifier. This is the "do nothing" reference: logistic regression on edge count, degree sequence and instance length, trained per class. NLGraph and the 3-SAT study show that such surface cues carry real signal, so a model that only matches this classifier is not searching. Because the generator matches these features across members and non-members, the classifier should sit near 50%. If it does not, our matching has failed, and we fix the generator before reporting any model result. Beating it means certificate-verified accuracy well above it on both famous and synthetic classes.
Instance-level contamination detectors. These are the strongest existing competitor for detecting contamination. We run Min-K%, Loss, and LiRA as audited in On The Fragility of Benchmark Contamination Detection in Reasoning Models. That paper reports LiRA at 89.1% AUROC on supervised contamination before cloaking, and all ten detectors at 50–58% AUROC on reasoning-model contamination. Fairness: we apply them to the same injected models and test items, with the same reference models for LiRA. The question is which of two statistics identifies the ten injected classes among twenty: detector scores aggregated per class, or $\Delta_C$ computed per class. Beating the detectors means our statistic attains clearly higher class-identification AUROC in the rule-only arm, and stays high after GRPO cloaking. We expect detectors to remain competitive in the instance-leak arm before cloaking, and we will report it if they win there.
Surface perturbation. This baseline applies symbol and label remapping in the style of A²RBench, which reported a 17.7% drop under remapping. We apply the same remapping to famous-class instances, with the same models and sampling budget, and compare the drop to $\Delta_C$. If remapping recovers the same per-class ranking as matched twins, our construction is unnecessary.
Ablations.
- Unmatched synthetic classes. We swap the twins for synthetic classes that are not matched on obstruction sizes or density. This shows how much of $\Delta_C$ is real versus difficulty mismatch.
- Answer-only scoring. We drop the certificate requirement and score yes/no answers alone. This shows how much a correct verdict without a valid witness hides.
Known LLM performance on this task. We found no reported result on Lacuna for forbidden induced subgraph detection by language models.
Why not just…?
Why not just rename vertices or remap symbols? Remapping changes the tokens of an instance but leaves the rule ("claw-free") as familiar as before, so it cannot remove rule-level familiarity. The A²RBench drop of 17.7% shows that remapping disturbs pattern matching. It does not say whether the remaining accuracy reflects search. Our surface-perturbation baseline tests this directly. If remapping alone predicts the injected classes as well as matched twins do, we will say so.
Why not just run contamination detectors? The Fragility study shows these detectors collapse to near chance when models absorb a reasoning schema, and that one epoch of clean reinforcement learning erases a signal LiRA had caught. Rule-only contamination never exposes a test instance, so instance-level likelihood has nothing to find. The injection experiment checks this prediction rather than assuming it.
Why not just let the model use code, since tool use reaches near 100% on graph algorithms (GrAlgoBench)? This is a real threat to the practical relevance of text-mode results. We take it on directly in Stage 3. If the code-mode gap is zero on both famous and synthetic classes, intrinsic textual search matters less than we argue, and the contribution narrows to auditing text-mode benchmarks. We expect a residual gap instead, because famous classes have library recognizers and synthetic ones do not. GraphGym's 14.7-point drop for DeepSeek-V3.2 on problems without standard library solutions points the same way.
Why not just use DyVal or NLGraph random graphs? They make instances fresh but keep task definitions fixed and familiar. They therefore cannot separate searching from knowing the rule, which is the quantity we measure.
Isn't a positive gap just because famous classes are genuinely easier? This is the most serious confound. Classes like chordal graphs are famous partly because they have elegant structure that may also make them easier to recognize. Matched sizes do not remove this. The injection experiment is the clean answer: injected and held-out synthetic classes come from the same random pool, so any gap that opens between them is caused by the contamination alone.
Proposed Experiments and Decisive Checks
The audit covers at least six textbook classes, two research-literature classes, and three to five twins each, with 500 boundary instances per class split evenly between members and non-members. Metrics are:
- certificate-verified accuracy;
- the rate of correct verdicts with invalid certificates;
- $\Delta_C$ with permutation-test intervals;
- in the injection study, AUROC for identifying which classes were injected.
The decisive check is the injection study. Rule-only contamination should raise verified accuracy on fresh instances of the ten injected classes but not on the ten held-out classes. $\Delta$ should rank injected classes above held-out ones with high AUROC, and that ranking should survive GRPO cloaking. Instance-level detectors should stay near chance in the rule-only arm. Two outcomes would falsify the approach: injection that does not move $\Delta$, or detectors that match $\Delta$ in the rule-only arm.
A second check uses the three familiarity tiers. If $\Delta$ tracks how often a characterization appears in literature (textbook above research-catalogue above synthetic), that supports the recall interpretation over intrinsic difficulty.
References
- On The Fragility of Benchmark Contamination Detection in Reasoning Models
- Can Large Language Models Reason? A Characterization via 3-SAT
- DyVal: Dynamic Evaluation of Large Language Models for Reasoning Tasks
- Can Language Models Solve Graph Problems in Natural Language?
- Unified Multi-Dimensional Benchmark for Complex Graph Reasoning in Large Language Models
- Exposing Weaknesses of Large Reasoning Models through Graph Algorithm Problems
- BOREL LINE GRAPHS
- Some Results on Critical (P5,H)-free Graphs
- k-Leaf Powers Cannot Be Characterized by a Finite Set of Forbidden Induced Subgraphs for k ≥ 5
- Learning minor closed graph classes with membership and equivalence queries
- A²RBench: An Automatic Paradigm for Formally Verifiable Abstract Reasoning Benchmark Generation