Language models are increasingly asked to act as controllers. They drive apps through their screens, step through scientific workflows, and write hardware that implements sequential logic. Most of these jobs reduce to following a finite state machine: a small set of discrete modes plus rules that say which input moves the system from one mode to the next. The world is also full of textbook state machines that models have certainly read many times, such as the vending machine, the turnstile, the traffic light, the TCP connection lifecycle, and the "101" sequence detector. This proposal asks a pointed question. When a model is handed an explicit transition table for a familiar-looking machine, does it follow the table, or does it follow the version it memorized? The test is simple. We take canonical machines, change exactly one transition, state the change plainly in the specification, and count how often the model behaves as if the original transition still held.
That single-edge "counterfactual" gives something current contamination probes do not. Existing probes show that performance drops when inputs are changed. This one records which wrong answer the model produces, and whether that answer is the memorized one. Because the machines are fully specified, every step of every run can be checked exactly. That makes it possible to separate three things: memorization leaking into behavior, general difficulty, and weakness in keeping track of the current state over long runs. It also tells agent designers whether an explicit state tracker, like the ones used in robotics and GUI agents, actually protects a model from its priors.
Core Claim
We hypothesize that when a model makes an error on a perturbed transition, the error is disproportionately the canonical answer, well above what uniform confusion among wrong states would produce. We expect this effect to grow with how familiar the machine is and with how many steps have passed since the specification was read. We further hypothesize that it survives renaming the states only partially, because the memorized structure can be recognized from the shape of the machine and not just from its words. The central quantity is the canonical override rate. It is computed over queries whose correct answer depends on the perturbed edge, and it is the fraction of those queries on which the model outputs exactly what the unperturbed canonical machine would produce. This is compared against a chance level set by the number of alternative wrong states. A high override rate is direct behavioral evidence that memorized structure is overriding in-context evidence. Accuracy drops alone cannot show this.
Relation to Prior Work
Four lines of work motivate this proposal. The first establishes that familiarity inflates scores. To the Cutoff... and Beyond? uses model training cutoffs as a natural experiment and shows that GitHub popularity raised pass rates only for pre-cutoff problems. The EvoEval results summarized in Benchmark Data Contamination of Large Language Models: A Survey report a 39.4% average drop when HumanEval problems are rewritten. VeriContaminated finds near-total contamination on Verilog benchmarks, a domain that is largely about sequential state machines. All three measure aggregate drops on problems whose ground truth is fixed. None asks whether the model's specific wrong output is the memorized one.
The second line supplies our transformation method. A²RBench introduces symbolic remapping, which renames tokens while keeping the rule, and reports a 17.7% drop. DyVal generates reasoning tasks from random directed acyclic graphs, meaning graphs with no loops, and reports a 13.6% drop for GPT-4 on reachability when the description order is reversed. We reuse remapping as one arm of our design and DyVal-style random generation as a matched control. Both prior works differ from ours in two ways. Their tasks are stateless or acyclic, whereas controllers run in loops. And neither pairs a familiar structure with a minimally edited copy, so neither can attribute an error to memorization as opposed to difficulty.
The third line comes from state machine control and defines the regime we care about. SPlanner wraps a vision-language GUI agent in a hand-built extended state machine and lifts AndroidWorld success from 35.0% to 63.8%. The scientific workflows perspective models agents as state machines whose transition function is chosen by the model. Neither tests whether the agent's transitions come from the stated machine or from a remembered one. We borrow SPlanner's separation between tracking state and choosing an action as a scaffold, and test whether it protects against override.
The fourth line uses game benchmarks such as GAMEBOT and TCG-Bench. These show that checking intermediate steps exposes failures that final outcomes hide. We adopt that lesson by scoring every transition. Their environments are monolithic, however, and not built from parameterized state machines with controlled familiarity.
Research Program
We will build a generator over roughly forty canonical machines. They will be drawn from textbooks and common web examples: protocol lifecycles, coin-operated devices, door and elevator controllers, parity and sequence detectors from digital-design courses, and common workflow pipelines of the kind MLAgentBench found agents reproducing on classic Kaggle tasks. Each machine is encoded as a formal transition table so that ground truth is computed by a simulator and never by a model.
From each machine we produce five matched variants. The canonical variant is written as usually described. The relabeled variant renames states and inputs to neutral tokens, following A²RBench. The counterfactual variant keeps the familiar names but redirects one transition, and the specification says so explicitly. The relabeled-counterfactual variant combines both changes. The random control matches the machine's state count, branching, and query depth but has no familiar structure, in the DyVal spirit.
Every variant is posed in four formats. In the trace format, the model receives an input sequence and must report the final state and outputs. In the specified control format, the model interacts with an environment by sending inputs and observing outputs until it reaches a goal state, with the table in context. In the hidden control format, the table is withheld and the model must explore. In the synthesis format, the model writes a Verilog module for the specified machine, and we check it by simulation. This last format links directly to VeriContaminated's finding that models reproduce memorized templates.
We will score familiarity for each machine using Min-K% Prob on its canonical description in open-weight models. Min-K% Prob is the average log-probability of a text's least likely tokens, and high values suggest the text was seen in training. We will also use a web-frequency proxy for the phrasing. This lets us test whether override rises with familiarity, analogous to the GitHub-presence effect in the longitudinal study. Finally, we will vary how many steps the query takes before first reaching the perturbed edge. This tests whether the prior reasserts itself as the specification recedes in the context window.
Baselines
The naive reference point is the canonical variant's accuracy alone. This is the score a static benchmark of familiar machines would report, and it is what our familiarity premium is measured against. It uses the same models, prompts, and query distribution as every other arm. We will count the naive reading as misleading if canonical accuracy exceeds matched-random accuracy by more than the confidence interval from bootstrapping over machines.
The strongest existing contamination diagnostic is symbolic remapping as in A²RBench, which reports a 17.7% average drop across advanced models. We run it as our relabeled arm with identical queries and budgets. The counterfactual probe beats it if it finds substantial override in cases where relabeling shows little drop. It also beats it if the counterfactual arm yields canonical-consistent errors that relabeling cannot, by construction, distinguish from generic difficulty. The second existing diagnostic is DyVal-style random generation, which reports a 13.6% reversal-induced drop for GPT-4 on reachability. We run it as the matched-random arm. It serves as the "contamination-free" score that the familiar variants are compared against.
For the control formats, the strongest agent baseline is a plain ReAct loop, in which the model alternates between thinking and acting. The strongest structured competitor is a SPlanner-style scaffold. SPlanner reports 63.8% versus 35.0% on AndroidWorld for its scaffold, but no reported result was found on Lacuna for any scaffold on counterfactual state machines. We will implement a state-register scaffold. At every step the model must write down its current state, and the environment then re-displays the specification row for that state. The model still chooses the transition itself, unlike SPlanner, where search executes the machine. This is the ablation that isolates our key ingredient. If override persists while the correct row is literally on screen, the memorized prior is beating visible evidence and the problem is not forgetting the specification. We also run a fully executed scaffold, where code applies the table, as a sanity ceiling that should drive override to zero. All arms get the same step limit, token budget, and prompt-tuning budget, with prompts tuned only on held-out random machines.
Why not just…?
Why not just use symbolic remapping, which already exposes reliance on familiar tokens? Remapping is a real competitor, which is why it is an arm of our study. Its limitation is that a drop under relabeling mixes two causes. One is lost memorization. The other is that neutral tokens are simply harder to read, as the ABCD-style bias literature and DyVal's order effects suggest. The counterfactual edge keeps the familiar tokens and changes the structure. Our dependent measure is whether errors match the canonical answer, which difficulty alone does not predict. If relabeling and the counterfactual produce the same ranking of models and machines, and override stays near chance, we will report that remapping suffices and the counterfactual adds nothing.
Why not just generate random state machines and avoid contamination entirely? Random generation gives a clean score but cannot measure how much contamination is distorting the scores people actually report on familiar tasks. DyVal shows that static-benchmark leaders collapse on random graphs but cannot say why. The matched pairing lets us attribute the gap. The matched-random arm is included precisely so that the familiarity premium is defined against it.
Why not just run membership inference on the canonical descriptions? Min-K% Prob and similar scores indicate that a text was seen. They do not indicate that seeing it changes behavior on a new specification. We compute them anyway, and one decisive check is whether they predict override rate across machines. A weak correlation would itself be informative: memorization detectors would then be poor proxies for behavioral contamination.
Why not just wrap every agent in an explicit state machine, as SPlanner does, and move on? If code executes the table, override vanishes trivially. But in the settings where state machines are used with language models, the model chooses the transition, as in the workflow agents of the scientific workflows perspective, and hand-built machines cost SPlanner 1–2 hours per app. The state-register ablation tests whether partial structure is enough. We genuinely do not know the answer, and a negative result would argue for executed rather than model-chosen transitions in safety-relevant controllers.
Proposed Experiments
We will evaluate open-weight models where log-probabilities are available (Llama 3.1 8B and 405B, Qwen2.5-72B, matching the size contrast VeriContaminated found) alongside GPT-4o and Claude models, on all five variants and four formats. For the synthesis format we will add perturbed versions of RTLLM and VerilogEval state machine items and check functional correctness in simulation.
The first decisive check compares override on perturbed edges with error on unperturbed edges of the same counterfactual machines, and compares override with chance. Canonical-consistent errors well above chance, with low error elsewhere, confirm the core claim. The second check regresses override on familiarity score and on distance to the perturbed edge. The third check is the state-register ablation described above.
The fourth check tests external validity. Across models, we ask whether override rate predicts the static-to-fresh drops reported elsewhere, for example OpenHands with Claude 3.7 Sonnet falling from 43.20% on SWE-bench Verified to 19.25% on SWE-bench-Live in SWE-bench Goes Live!. If it does, a cheap synthetic probe could flag models whose benchmark scores are likely inflated before a live benchmark exists. If override tracks nothing outside our generator, we will say the phenomenon is local to textbook machines and report that.
References
- To the Cutoff... and Beyond? A Longitudinal Perspective on LLM Data Contamination
- Benchmark Data Contamination of Large Language Models: A Survey
- VeriContaminated: Assessing LLM-Driven Verilog Coding for Data Contamination
- A²RBench: An Automatic Paradigm for Formally Verifiable Abstract Reasoning Benchmark Generation
- DyVal: Dynamic Evaluation of Large Language Models for Reasoning Tasks
- Building a Stable Planner: An Extended Finite State Machine Based Planning Module for Mobile GUI Agent
- The (R)evolution of Scientific Workflows in the Agentic AI Era: Towards Autonomous Science
- GAMEBoT: Transparent Assessment of LLM Reasoning in Games
- Cards Against Contamination: TCG-Bench for Difficulty-Scalable Multilingual LLM Reasoning
- SWE-bench Goes Live!