Winner-Preserving Twins: Certified Game Perturbations for Detecting Memorized Reasoning

When a language model answers a benchmark question correctly, we usually cannot tell whether it worked the answer out or recognized the question from its training data. Current fixes rewrite or regenerate test items so that memorized copies no longer match. Examples include perturbing reasoning graphs, paraphrasing with helper models, and scraping post-cutoff news. None of these can prove that a rewritten item still has the same answer, or that a small change really flips it. We propose to borrow the missing guarantee from model checking of two-player games. That field has worked out exactly which moves in a game can be dropped or reordered without changing who wins.

The idea is simple. Pose perfect-information two-player reachability games to models: a controller tries to reach a goal while an adversarial environment tries to prevent it. Then apply stable reduction conditions to each game. These are rules, developed for partial order reduction, that say when a subset of moves (a "stubborn set") can be explored in place of all moves while provably preserving each player's winning strategy. Moves the rules allow us to prune or reorder give "twins": textually and structurally different games with a certified-identical winner. Moves the rules forbid us to prune, chiefly environment moves protected by the visibility condition, give "near-misses": minimal edits where the winner may flip, which a solver then confirms. A model that reasons should agree with itself across twins and change its answer on confirmed near-misses. A model that memorized the seed game should do neither.

Core Claim

Winner-preserving reductions give a contamination probe with a formal guarantee that paraphrase- and heuristic-perturbation methods lack. We claim that the gap between twin-consistency and near-miss sensitivity separates memorization from reasoning more reliably than accuracy drop under ad hoc perturbation. We test this directly by deliberately contaminating models and checking which probe notices.

The mechanism comes from Bønneland et al. They define game labelled transition systems, which split moves between controller and environment. They then prove that a stubborn-set selection satisfying their conditions (named I, W, R, G1, G2, S, V, D) preserves winning strategies for both players (Stubborn Set Reduction for Two-Player Reachability Games, Partial Order Reduction for Reachability Games). They also show that environment moves which can affect the outcome must stay visible (Stubborn Set Reduction for Timed Reachability and Safety Games). That work treats reduction purely as a speed-up for verification. We use the same conditions as a generator of equivalence classes and minimal counterexamples.

Their theorems assume perfect information. We therefore restrict ourselves to perfect-information games, and we make no claims about hidden-information arenas such as UNO Arena.

Research Program

We start from the Petri net game families used in TAPAAL experiments: NIM, MW, AIM, PCS, Railway Scheduling, and LyngbySmall. In these, concurrency creates many independent moves. From each family we sample seed instances and render them in natural language. A rendering lists the players, the available moves with their preconditions and effects, and the goal, and asks either "does the controller have a winning strategy from this position?" or "name a winning first move."

For each seed we compute a stable stubborn set at each state. We then produce twins in three ways. First, we reorder independent moves in the textual history that leads to the current position. Second, we delete transitions that no stubborn set at any reachable state ever needs, so the reduced game is a smaller but strategically identical game. Third, we rename places and actions and re-order the description. The first and third leave the game unchanged. The second produces a genuinely different game with the same winner, which is what defeats a memorized answer keyed to the seed.

Near-misses come from removing or reordering exactly one move whose pruning violates visibility or a game condition, typically an environment counter-move. We keep only those where the TAPAAL solver confirms that the winner flips. The reduction also keeps exact ground truth affordable on larger instances. The file reports a 97% time and 99% marking reduction on NIM-9-49500 (Partial Order Reduction for Reachability Games). This avoids the sampling variance of Monte Carlo move labels used in UNO Arena.

For a model $f$ and seed $g$, let $T(g)$ be its certified twins and $N(g)$ its confirmed near-misses. We score

$$\Delta(f) = \mathbb{E}_g\big[\,\mathrm{agree}_f(g, T(g))\,\big] + \mathbb{E}_g\big[\,\mathrm{flip}_f(g, N(g))\,\big] - 1,$$

where $\mathrm{agree}$ is the fraction of twins on which $f$ gives the seed's answer, and $\mathrm{flip}$ is the fraction of near-misses on which $f$ changes its answer. A reasoner that solves every item scores 1. A memorizer that repeats the seed answer scores near 0 on flips, which leaves $\Delta$ near 0 even when its seed accuracy is perfect. A model that ignores the input scores near 0 overall.

Baselines

The naive reference point is plain accuracy on the seed games and on freshly sampled games from the same families. We give no perturbation, only a check of whether performance on unseen instances matches performance on seen ones. This is the fresh-instance logic of Can Large Language Models Reason? A Characterization via 3-SAT. That paper generates random formulas and reports GPT-4 search accuracy falling to roughly 10% at the 3-SAT phase transition. Beating this baseline means detecting contamination when a model's fresh-instance accuracy is already high, which happens when a model has learned the family's distribution rather than individual seeds.

The strongest structural competitor is DyVal-style graph perturbation, which alters order, depth, and width without any guarantee that the answer is preserved (DyVal, DARG). The relevant reported number is from DyVal: GPT-4 suffers a 13.6% accuracy drop on reachability when the description order is flipped. We run the DyVal and DARG operators on the same seed games, then re-solve each perturbed game with the solver, so their labels are exact too. We match them to our twins in number of variants per seed and in token length.

The strongest paraphrase competitor is Meta Probing Agents from DyVal 2. It reports a 15.54% accuracy decrease for GPT-4-Turbo on MMLU and a 94% human-verified equivalence rate. We apply its paraphrase and distractor agents to the same renderings with the same judge budget.

The ablation that isolates our key ingredient is random single-edit plus re-solve. It deletes or reorders a random move, labels the result with the solver, and sorts it into "same winner" and "flipped" bins. It costs the same, and its labels are just as exact. The only thing it lacks is the stable-condition targeting. We count ourselves as beating these baselines if the contamination-detection AUC of $\Delta$ exceeds each competitor's detection statistic at matched query budget, with non-overlapping bootstrap intervals. On games with LLM respondents specifically, we found no reported result on Lacuna for LLM accuracy on Petri net reachability games, so these numbers will be new.

Why not just…?

Why not just paraphrase with helper models, as DyVal 2 does? Paraphrase changes the words but not the game. A model that memorized the seed's structure answers every paraphrase correctly, so paraphrase cannot detect structural memorization. Its 94% verified equivalence (DyVal 2) also means some variants are silently wrong. Our experiment measures this directly. We contaminate on structure, fine-tuning on seeds rendered in many phrasings, and test whether paraphrase probes stay blind while reduced-game twins and near-misses do not.

Why not just perturb randomly and re-solve with the model checker? This is the real threat, because re-solving already gives exact labels. The difference is in what the edits target. Random edits mostly hit irrelevant moves, so few of them flip the winner. The flips they do produce often reshape the game broadly rather than minimally. Visibility-violating edits, by contrast, target exactly the counter-moves a reasoner must track. If the random-edit ablation matches our detection AUC at equal budget, the reduction theory adds nothing beyond cheaper ground truth. We would then report the result as such and narrow the claim to solver tractability on large instances.

Why not just collect fresh post-cutoff data? CausalProbe-2024 shows that post-cutoff news exposes memorization: Claude 3 Opus scores under 70% on its hard split (Unveiling Causal Reasoning in Large Language Models: Reality or Mirage?). But fresh data leaks into the next crawl, and it gives no control over difficulty or minimal pairs. Twins can be regenerated from any seed indefinitely, and we will measure whether $\Delta$ stays stable across regeneration rounds.

Why not just have the model translate the game into a solver's input language? Hazra et al. report nearly 100% accuracy for GPT-4 in SAT-Translate (Can Large Language Models Reason?). That measures transcription, not reasoning about counter-strategies. We include translation as an upper reference, and we report it separately rather than as a competitor.

Proposed Experiments

The decisive experiment is controlled contamination. We take open models, fine-tune one copy on a held-in set of seed games with their answers and a matched copy on unrelated games, and ask which probe separates the two. The probes compared are fresh-instance accuracy, DyVal-style perturbation, Meta Probing Agent paraphrase, random edit plus re-solve, and $\Delta$. We vary contamination dose from one exposure to many, and rendering diversity from a single phrasing to many. Paraphrase is expected to fail at high rendering diversity, and $\Delta$ is expected to hold across the whole grid.

Second, we evaluate frontier and open models on all six game families at increasing size. We report twin agreement and near-miss flip rate separately. This lets us tell presentation-order failures, which appear as disagreement on reorder-only twins in the spirit of DyVal's reversal effect, from genuine strategic failures, which appear as missed flips on environment counter-moves.

Third, we report generation cost: stubborn-set computation plus confirmation solves, compared against unreduced solving. We give LyngbySmall its own report, since the reduction papers flag it as a case where reduction slows the search.

The proposal fails if the random-edit ablation matches $\Delta$, or if twin disagreement in uncontaminated models is so high that it swamps the contamination signal. Either outcome is informative, and both are measurable within this design.