Detecting Benchmark Contamination with Minimal Pairs from Networked Fair Division

When a language model scores well on a benchmark, we usually cannot tell whether it solved the problems or had seen them, or problems very like them, during training. This proposal builds a test set out of a family of problems from economics called local envy-freeness. In these problems, goods are split among people who sit on a social network, and each person only compares their share with the shares of the people they are connected to. What makes this family useful is not that it is exotic. Its theory tells us exactly when a problem is easy, when it is provably hard, and when it has no solution at all. Often a single change to the network, such as reversing one arrow, is enough to move a problem from one of these regimes to another. We use such nearly identical twin instances, which read almost the same but require different reasoning, to separate genuine reasoning from memorization and from shortcut heuristics. The approach needs no fleet of reference models to estimate what "hard" means.

The core claim is narrow and testable. Existing contamination detectors catch item-level leakage, where the exact test questions were seen, reasonably well. They are weak against generator-level contamination, where a model has been trained on many samples from the same procedural generator and has learned the generator's habits rather than the problem. Twin instances whose correct answers diverge because of a provable structural fact should expose generator-level contamination and shortcut use in cases where comparing scores on fresh resamples cannot.

Why this intersection

Two lines of contamination work motivate the gap. ConStat redefines contamination as performance that fails to generalize. It compares a model's score on a benchmark against rephrased or synthetic reference sets, using a difficulty correction fitted across about 20 reference models, and it reports catching 89% of syntax-contaminated and 98% of sample-contaminated models. Its measure of difficulty is itself a statistical fit over models that may be contaminated. DyVal generates fresh math, logic and graph problems from directed acyclic graphs, so no fixed test set exists to leak. Models that led static leaderboards scored near zero on it, and reversing the order in which the graph is described cost GPT-4 13.6% on reachability. But DyVal's graphs only encode single-agent dependency chains. Its difficulty knobs, depth and width, move difficulty up or down smoothly and never change the kind of reasoning required. A model trained heavily on DyVal-style data would look clean on fresh DyVal samples.

A third paper constrains the design. Can Large Language Models Reason? A Characterization via 3-SAT shows that performance collapses at the phase transition where 3-SAT becomes hard. That supports using known complexity structure as a probe, and it also means that "use a hardness transition" is not new by itself. What 3-SAT lacks is a family of natural twins that cross between solvable, provably unsolvable, and easy-versus-hard while keeping the surface text almost identical. Back to Square One supplies the methodological template. On Winograd twin sentences, requiring both members of a pair to be right ("group scoring") dropped the top WSC score from 89.71% to 79.41% and pushed zero-shot WinoGrande to chance. We import that pair-scoring logic into a domain where the twins come with proofs rather than crowd annotations.

The fair-division theory supplies the pairs. Weak graph envy-freeness requires that each agent $i$, with additive utility $u_i$ over bundles, values its own bundle $A_i$ at least as much as the bundle of every agent it can see:

$$u_i(A_i) \ge u_i(A_j) \quad \text{for every edge } (i,j) \text{ in the attention graph.}$$

Envy-Free Allocations Respecting Social Networks shows that on acyclic attention graphs this can be satisfied in linear time by processing source agents first. It also shows that the strict version is impossible on any graph with a directed cycle when agents have identical preferences. Fair Division via Social Comparison proves the "proportionality paradox". An allocation can give everyone at least $1/n$ of the total value, so it looks fair globally, while some agent's neighbors all hold more-valued pieces. That gives instances where a global-fairness shortcut predicts the wrong answer. The Complexity of Extending Fair Allocations of Indivisible Goods shows that completing a partial envy-free allocation is fixed-parameter tractable in the number of open items plus agent types, but W[1]-hard in open items plus item types. It also shows that every envy-free partial allocation extends to an allocation that is envy-free up to one item (EF1), a guaranteed-yes answer that does not depend on the instance. None of these papers touches machine learning. We use their theorems as ground truth, not as objects of study.

Research Program

We will build a generator of local envy-freeness tasks in four formats, each graded programmatically by checking a certificate rather than matching a string. In verification, the model receives a graph, additive valuations and an allocation, and must say whether it is weakly envy-free and name one violating edge if not. In construction, the model must output an allocation that satisfies weak envy-freeness on the given graph. In impossibility, the model must decide whether a strictly envy-free allocation exists and justify the answer. In extension, the model must complete a partial allocation with $k$ open items. Checking a submitted allocation takes time proportional to the number of edges times the number of items, so grading is cheap even when finding an answer is hard.

Every instance comes with at least one twin produced by a single structural edit, chosen so that the twins differ in their correct answer or complexity regime:

  • reversing one edge to close a directed cycle under identical preferences, which flips "strict envy-freeness exists" to "impossible";
  • perturbing values so that an allocation that is globally proportional but locally unfair becomes locally fair, or the reverse;
  • changing agent types versus item types, which moves an extension instance across the tractable/hard boundary;
  • presenting the same graph in topological, reversed or random order, following DyVal.

We record a structural descriptor $\theta(x)$ for each instance $x$: acyclic or cyclic, cycle count, $k$, number of agent types, number of item types, depth, and presentation order.

From these we compute three contamination signals, all without reference models. The first is a stratified residual. For a model $M$ and a static test set $S$,

$$\hat\delta_M(S) = \mathrm{acc}_M(S) - \frac{1}{|S|}\sum_{x \in S} \bar a_M(\theta(x)),$$

where $\bar a_M(\theta)$ is $M$'s accuracy on freshly generated instances sharing descriptor $\theta$. This is the naive detector done carefully, and we expect it to catch item-level leakage.

The second is twin consistency. We take the gap between single-instance accuracy and the probability of getting both members of a twin pair right, in the spirit of group scoring. We also track the rate at which the model gives the same answer to twins whose correct answers differ. A model reasoning about cycles should answer the twins differently. A model matching surface patterns will not.

The third is off-support shift: the accuracy change when $\theta$ moves outside the range a suspected generator covers, for example from acyclic to cyclic graphs or from topological to reversed order, while the verification rule stays fixed. The central hypothesis is that generator-level contamination leaves the stratified residual near zero while inflating twin-answer agreement and off-support shift.

Baselines

The naive reference point is the fresh-resample gap: a model's accuracy on a released set minus its accuracy on unconditioned fresh samples from the same generator. This is what DyVal-style evaluation implicitly provides. We run it on exactly the same instances and models as our detectors. Our method must beat it on generator-level contamination. We expect a tie on item-level leakage and will report the tie honestly.

The strongest existing method is ConStat, run two ways. The first uses its standard recipe of rephrased references and a difficulty correction fitted across a reference fleet. The second uses fresh generator samples as its synthetic reference, which is the most favorable version for ConStat. Both get the same models, the same test sets and the same number of reference evaluations as our method. The reported number to beat is ConStat's 89% detection of syntax-contaminated and 98% of sample-contaminated models on its own suite. No reported result exists for ConStat, or for any detector, on fair-division tasks. Beating it here means higher detection rate and area under the ROC curve (AUROC) at a matched false-positive rate on the generator-contaminated population, without losing ground on item-level leakage.

A 3-SAT phase-transition probe, following Can Large Language Models Reason?, serves as a hardness-transition baseline with no twin structure. It uses satisfiable/unsatisfiable instances near and away from the critical ratio, contaminated in the same regimes.

The key ablation removes the twins. It keeps the fair-division generator and the stratified residual but scores instances independently. If this ablation matches the full method, the fair-division content contributes nothing beyond being a fresh generator, and the claim fails.

Why not just…?

Why not just resample DyVal, or any procedural generator? Fresh samples defeat memorization of specific items, but they come from the same distribution a model may have been trained on. A model fine-tuned on DyVal-like data would show no gap on fresh DyVal-like samples. DyVal's knobs change difficulty smoothly, so they offer no twin whose correct answer flips. This alternative is the real threat for item-level leakage, and the no-twin ablation plus the naive baseline test it directly.

Why not just rephrase existing benchmarks, as ConStat does? Rephrasing detects syntax-level contamination, and ConStat's own numbers show it works there. But the rephrased references are produced by an LLM whose artifacts are hard to control. Back to Square One shows that rewritten datasets such as WinoGrande still carry exploitable artifacts. More importantly, rephrasing cannot produce references that are harder or easier by a provable amount. Our twins can.

Why not just use the 3-SAT phase transition? It already provides proven hardness structure, and it may perform comparably. That is why it is a baseline rather than a straw man. Our bet is that 3-SAT's transition is a statistical property of random instances near a critical ratio, not a single-edit flip, and that it has no counterpart to the global-versus-local shortcut. If the 3-SAT probe matches our detector on generator-level contamination, we will report that the benefit comes from hardness transitions in general and not from fair division specifically.

Why not just use a live benchmark like LiveBench? LiveBench limits contamination by refreshing tasks monthly, and even o1-preview topped out at 64.7%. But it only bounds how long leakage goes unnoticed, requires continual curation, and does not diagnose why a score is inflated. Our goal is diagnosis, and the two approaches are complementary.

Proposed Experiments

The decisive experiment is controlled contamination on open-weight models of the Llama-3 and Mistral-7b families that ConStat studied. We produce a population of fine-tuned variants in three regimes. In the item-leak regime, models are fine-tuned on a released set of fair-division instances with answers. In the generator-leak regime, models are fine-tuned on many fresh generator samples restricted to acyclic graphs, topological ordering and tractable extension parameters. The clean regime applies matched fine-tuning on unrelated text. We sweep leak proportion and number of epochs, and apply the same regimes to the 3-SAT baseline. For each detector we report AUROC for separating contaminated from clean variants within each regime, and the error of its inflation estimate against the known accuracy lift caused by the injection. The proposal succeeds if twin consistency and off-support shift reliably separate generator-leak models that both the fresh-resample gap and ConStat miss, and if the no-twin ablation loses most of that advantage. It fails if the ablation or the 3-SAT probe performs as well.

A secondary experiment runs the benchmark on frontier API models. We check whether DyVal's order-reversal effect reappears, whether hidden cycles lead models to falsely certify strict envy-freeness, and whether models accept globally proportional but locally unfair allocations as fair. We also test textbook fair-division instances against relabelled copies with the same structure. Relabelling is a rephrasing-style check, and we use it only as corroboration. No reported result exists for any model on local envy-freeness tasks, so these numbers will be the first of their kind and are descriptive, not the main test of the claim.