Measuring How Far Contamination Spreads, Using Functions With Decidable Equivalence

When a language model scores well on a leaked benchmark, the usual worry is that it memorized the answers. The harder worry, raised by recent work on reasoning models, is that it learned the task family well enough that items which merely resemble the leaked ones are also inflated. Nobody can measure that spread on today's benchmarks, because nobody can say exactly which test items are "the same problem" as a leaked one. This proposal builds a benchmark where that question has a provably correct answer. Each task is a string transformation drawn from a class of programs, copyless streaming string transducers, for which a decision procedure exists for whether two programs compute the same function. With that in hand, we can contaminate a model on chosen functions under controlled conditions. We then measure how far the inflation travels: to the same function written differently, to near neighbours that are certified to compute different functions, and to fresh functions with matched structure. The same machinery yields a behavioural audit that does not rely on the log-probability gap that reinforcement learning is known to erase.

A streaming string transducer reads its input once, left to right, keeping a few string-valued variables ("registers") that it updates at each step. The output is assembled from those registers. The copyless rule says that in any single update, each register's old contents may be used at most once. Contents can be appended to, prepended to, or swapped between registers, but never duplicated. Expressiveness of streaming string transducers shows this rule keeps output length linear in input length. Under the rule, these machines compute exactly the transformations definable in monadic second-order logic, the standard logical characterization of "regular" string transformations. They are also closed under composition. Streaming transducers for algorithmic verification of single-pass list-processing programs shows that functional equivalence is decidable in PSPACE for the data-string version. Two operations matter for our purposes. Reversal is possible through prepending, and duplication is ruled out. Together these give a class that is rich enough to be nontrivial for language models, small enough to compare exactly, and free of the exponential blow-up that unrestricted copying would cause.

Core Claim

The unit of benchmark contamination should be a function, not a string. Copyless transducers are a class in which that unit can be computed. We claim three things. First, a benchmark built from randomly sampled copyless transducers allows certified splits: every held-out function is proven inequivalent to every leaked one, and every "rewrite" is proven equivalent. Second, these splits let us measure a contamination radius, meaning how score inflation decays as test functions move away from leaked ones in program space. Third, a gap test between published items and freshly sampled, structurally matched, certified-inequivalent controls detects contamination after clean reinforcement learning, a regime where log-probability detectors fall to chance.

The closest existing work generates fresh tasks but cannot reason about equivalence between them. A²RBench has an author model write invertible Python transformations and checks them by testing that the inverse undoes the forward map on examples. Equivalence of two of its rules is undecidable, and its authors observe that author models simplify rules to keep code valid. DyVal samples reasoning tasks from graph templates with depth and width knobs. It has no notion of two templates computing the same thing. P⁴Bench hides answers behind zero-knowledge proofs. That works only for search problems encodable as arithmetic constraints, such as SAT and discrete logarithm. None of these can tell you whether a test item is a disguised copy of a leaked one. That is precisely the question On The Fragility of Benchmark Contamination Detection in Reasoning Models makes urgent: it finds that chain-of-thought contamination generalizes to distributionally similar questions.

Research Program

The first component is a generator and an equivalence engine. We sample deterministic copyless transducers over a small finite alphabet. Size is controlled by four parameters: number of states, number of registers, the fraction of updates that prepend versus append, and the fraction that permute registers. Degenerate machines, such as constant or identity functions, are rejected. Every sample is minimized, and samples are bucketed into equivalence classes using the decision procedure from the transducer literature, which reduces equivalence to reachability in a one-counter machine. PSPACE is a worst-case bound. We expect machines with at most eight states and four registers to be checkable quickly, and we will report checking times. The data-string extension, which compares unbounded values by relative order, comes in a second phase. The finite-alphabet results in Expressiveness of streaming string transducers are the safe foundation.

Each function is posed to models in two formats. In the execution format, the model sees the transducer written as a short imperative single-pass program and must produce the output on a new input. In the induction format, the model sees input–output pairs and must predict the output on a query, or write a program. A written program is graded by exact equivalence to the hidden target, not by unit tests. For any target we construct three kinds of related functions. Equivalent rewrites rename registers, split states, reorder independent updates, and re-express the program text; every rewrite is certified equivalent. Near neighbours are one or two syntactic edits away and are certified inequivalent, with the distinguishing input recorded. Fresh controls are new samples with identical structural parameters, certified inequivalent to everything in the leaked set.

The second component is controlled contamination. We follow the staged protocol of On The Fragility of Benchmark Contamination Detection in Reasoning Models on open models, including DeepSeek-R1-Distill-Llama-8B, which that paper uses. There are three conditions. In the first, we fine-tune on answers to a leaked subset. In the second, we fine-tune on chain-of-thought traces that walk through register updates. In the third, we follow either kind of fine-tuning with GRPO, a group-based reinforcement learning method, on clean, disjoint functions. From these we measure inflation at each ring of the radius: exact items, new inputs to the same function, equivalent rewrites, one-edit neighbours, two-edit neighbours, and fresh controls.

The third component is the audit. Given a model and a published item set, we sample many fresh controls matched on structural parameters and test whether accuracy on published items exceeds accuracy on controls. Equivalence classes are treated as units: a published item and its rewrites count as one. Because fresh supply is unlimited and certified, the test's power is limited only by evaluation budget, not by a fixed held-out set.

A secondary analysis uses the generator's knobs to ask a question the DyVal "reversal" result raises but cannot isolate. DyVal reports a 13.6% GPT-4 drop on reachability when the description order is flipped. We ask whether failures concentrate on prepend and register-swap updates specifically, holding everything else fixed.

Baselines

The naive reference point is a static benchmark of sampled transducers with a random train/test split and no certification. It shows what contamination looks like when "held out" means only "a different sample." We expect some held-out functions to be equivalent to training functions, especially at small sizes, and we will count how many.

The strongest existing detection methods are the log-probability membership tests evaluated in On The Fragility of Benchmark Contamination Detection in Reasoning Models, with LiRA (a likelihood-ratio membership attack using reference models) as the strongest. That paper reports LiRA at 89.1% AUROC after answer fine-tuning. After one epoch of clean GRPO, LiRA drops by roughly 14 points, and many reference-free methods approach 50%. Under chain-of-thought contamination, almost all ten methods average 50–58% AUROC. We run LiRA, Min-K%, and loss on our own contaminated checkpoints, with the same reference models and the same item pools as our audit. The audit beats them if it holds AUROC substantially above their post-GRPO and chain-of-thought levels at an evaluation budget a leaderboard could afford, a few hundred control queries per audited set. On our tasks there is no reported result found on Lacuna. The cited numbers are calibration targets: our replication should land near them before any comparison is trusted.

The strongest existing dynamic-generation baseline is a DyVal-style fresh-sample gap test. It compares published items against new instances drawn from the same templates, with no equivalence reasoning. It is run on the same transducers, sampled with the same parameters but without certification or class grouping. This is the ablation that isolates our key ingredient. If it matches the certified audit in detection power and radius estimates, then decidable equivalence contributes nothing beyond fresh sampling.

A second ablation replaces the decision procedure with random testing: two functions are declared equivalent if they agree on N random inputs, with N swept upward. This is the cheap engineering substitute. We report its misclassification rate against the exact procedure and how much that error corrupts the radius curve.

For context on task difficulty, the best model on A²RBench reaches 40.9% overall accuracy against a 68.5% human baseline. DyVal reports models strong on static benchmarks, such as phi-1.5 and WizardMath-13B, scoring near zero. We aim for a difficulty range where uncontaminated frontier accuracy falls between those extremes.

Why not just…?

Why not just check equivalence by random testing? This is the most serious threat. Random testing proves inequivalence whenever it finds a counterexample, and that is all a held-out split strictly needs. Its weakness is the other direction. Two regular transformations can disagree only on rare, long inputs, so random testing will sometimes merge distinct functions into one class or keep two distinct-looking functions apart that actually coincide. We measure this directly in the random-testing ablation. If misclassification is negligible at practical N across our size range, we will say so: the contribution then reduces to a structured generator with controlled rewrites, and the exact procedure becomes a guarantee rather than a necessity. Exact checking still matters for certifying equivalent rewrites, which random testing can never prove.

Why not just use DyVal-style dynamic generation? DyVal already defeats verbatim leakage by sampling fresh instances. It cannot define contamination of a function independent of its surface form, so it cannot measure the radius. The uncertified fresh-sample baseline above runs exactly this design on our tasks. The decisive comparison is whether radius estimates and audit power differ once equivalent items are grouped. If they do not differ, the simpler design wins on the audit question.

Why not just remap tokens or perturb surface form? A²RBench reports a 17.7% drop under symbol remapping, which shows surface sensitivity. Remapping keeps the underlying function fixed, so it probes only the innermost ring of our radius. It says nothing about whether learning one function inflates a different one. Our equivalent-rewrite ring contains remapping as a special case.

Why not just use plain finite-state transducers, which are simpler and also have decidable equivalence? Finite-state transducers that emit output symbol by symbol cannot reverse a string or move material between buffers. Those register manipulations are where we expect language models to struggle and where memorized shortcuts are plausible. Copyless transducers keep decidability while adding exactly those operations. We include a finite-state-transducer-only stratum so that any difference in radius between the two classes is visible.

Why not just hide answers cryptographically, as P⁴Bench does? Secrecy prevents leakage of answers but does not tell an auditor what an already-contaminated model has learned. P⁴Bench is also limited to arithmetic-constraint search problems; on its hard discrete-logarithm tier only Qwen 3.5 Plus scores above zero (11%). The two approaches are complementary, and answer hiding could be layered on top of our generator.

Proposed Experiments

The first decisive check is the radius curve. For each contamination condition, we plot accuracy inflation relative to an uncontaminated twin model on each ring, from exact items to fresh controls. The literature leaves this open, so we state no expected direction. If answer fine-tuning inflates only exact items, while chain-of-thought fine-tuning inflates near neighbours but not fresh controls, that would be the first measurement of the "similar question" generalization reported in On The Fragility of Benchmark Contamination Detection in Reasoning Models. If inflation stays flat across inequivalent neighbours, chain-of-thought contamination is teaching the family, not the item. We then ask whether GRPO on clean data shrinks the radius or only hides it from log-probability tests.

The second check is the audit comparison. AUROC of the certified gap test is set against LiRA, Min-K%, loss, and the uncertified gap test, before and after GRPO, as a function of query budget. The claim fails if the uncertified gap test performs as well.

The third check is the random-testing ablation. We report how often random testing errs at each N and transducer size, and how much those errors shift the radius curve. The fourth is a cost check: equivalence-checking time across the size grid, to confirm the PSPACE bound is not a practical obstacle at benchmark scale. A short diagnostic study holds all other knobs fixed and varies the share of prepend and swap updates. It tests whether difficulty and contamination sensitivity concentrate on the register operations that make reversal possible, giving the reversal effect a mechanistic reading in terms of copyless state updates.