The Best Models Track State Well. At 10,000 Tokens, They Fall to Chance

Long-context benchmarks mostly test retrieval: find the needle, quote the passage, answer the question. State tracking is different. It asks whether a model can hold a changing picture of the world in its head across a long sequence of updates, and report the final state correctly. That is what an agent does when it edits code, runs a multi-step workflow, or keeps a spreadsheet current. Retrieval finds a fact. Tracking maintains a state.

A paper from Jackson Petty, William Merrill and Ashish Sabharwal at the Allen Institute for AI and NYU, submitted 2 November 2026, argues that state tracking breaks into a hierarchy of four skills, and that the hierarchy explains why some architectures generalize to long sequences and others do not. They back the claim with theory and with StateBench, a benchmark built to test each level separately, at lengths up to 64,000 assignments. The results are uncomfortable for anyone shipping long-horizon agents on transformer models.

The four levels of tracking

The paper models state tracking as a word problem over a finite monoid, then uses the Krohn-Rhodes decomposition to split it into four nested levels. The algebra is dense, so here is the programming intuition. Each level corresponds to a kind of variable update you write every day:

Level	The update	Code example
r-trivial	Immutable write, set once	let x = 4
Aperiodic	Mutable write by value	x = 4, then later x = 2
Soluble	Self-referential write	x = 4, then x += 3
General finite	Referential write, swap	(x, y) = (y, x)

Each level contains the ones below it. A model that can track swaps can track plain reassignments. The reverse does not hold. That nesting is the whole point: a benchmark that only tests easy updates will never reveal which level a model actually reaches.

The theory then places architectures on this ladder. A log-precision averaging hard-attention transformer, the standard theoretical model of a transformer, can express exactly the soluble problems and no further. A Gated DeltaNet with only positive eigenvalues expresses all aperiodic problems. A Gated DeltaNet with both positive and negative eigenvalues covers all finite monoids, the whole ladder. The paper also proves a surprise: a GDN with non-negative eigenvalues can recognize the periodic language (aa)*, using rounding, which contradicts a 2025 result that said such models cannot recognize parity under exact arithmetic. The fine print matters: the earlier result assumed exact multiplication, and rounding changes what the model can do.

What StateBench actually tests

StateBench turns the hierarchy into data. Each problem is a sequence of assignments over a set of variables, starting from initial values. Every sequence is paired with one correct final state and four incorrect ones, so the same item works as a multiple-choice test or as a generative one where the model must produce the final state itself.

Three design choices make the benchmark harder to game than most. First, all four levels are derived from the same source task, so the number of variables, the distinct values and the positions of assignments are held constant across levels. Only the kind of update changes. A score gap between levels is a gap in capability, not a gap in the data. Second, the static evaluation set spans 8 to 64,000 assignments, so length generalization is measured directly rather than inferred. Third, every sample is rendered in six textual formats, including integer code, spreadsheet cell filling and cube painting, because the authors found format alone moves scores by a lot. More on that below.

Finding 1: Transformers fail to generalize even on the simplest tier

The authors trained six architectures from scratch at 275M parameters, on sequences of 8 to 256 assignments, using a Chinchilla-optimal amount of data, then evaluated them on sequences up to 64,000 assignments, 250 times longer than training.

Transformers learned the r-trivial and aperiodic tasks inside the training distribution, then failed to generalize past it. Models without positional embeddings degraded immediately beyond the training cutoff. Models with rotary embeddings held to roughly 10 times the training length, then degraded. On general finite data, transformers did not even learn the training distribution fully.

Gated DeltaNet models behaved differently. They generalized perfectly on r-trivial, aperiodic and soluble data. On general finite data they learned the training distribution perfectly, and the version with both positive and negative eigenvalues generalized to roughly 10 times the training length. Hybrid transformer-GDN models patterned like their GDN components.

The takeaway is sharp: the failure does not come from training data. The same data, the same compute budget, the same scale. One architecture generalizes, the other does not, and the split lines up with the theory.

Finding 2: Pretrained models underperform their own theory

Training from scratch is a clean experiment. In practice models are built by pretraining, so the authors also evaluated pretrained models: Olmo-3 7B, a transformer, and Olmo-3-Hybrid 7B, plus smaller custom models at 275M and 2.7B parameters, all pretrained and midtrained on the Dolma dataset, with pretraining capped at 8,000 tokens and long-context extension capped at 64,000 tokens. Evaluation sequences ran up to 128,000 tokens.

Pretrained models underperformed both the theory and the direct-training results. The 7B models reached only about 90% accuracy on aperiodic data, below ceiling on the second tier of four, and degraded noticeably after the pretraining length window. One small bright spot: a 275M GDN model held about 50% accuracy beyond the long-context cutoff on aperiodic data. But on general finite data, every pretrained model performed at chance for all sequence lengths.

Length, complexity class and model size were the dominant factors in accuracy. Scale helped, but it did not close the gap. A 7B model still failed completely on the hardest tier.

Finding 3: Frontier models fall to chance at 10,000 tokens

The headline test ran four recently released frontier models, Gemini 3.8 Flash, Claude Opus 5.5, GPT-6 Sol and GPT-6 Luna, in a generative setting, asking them to produce the final state rather than pick from five options.

All four performed strongly on r-trivial and aperiodic problems. Then they fell to at-chance accuracy on soluble and general finite problems when inputs reached between 10,000 and 64,000 tokens. The paper describes the drop as reaching near-zero performance on the hardest problems in StateBench. A writeup of the paper reports the four models scored 13% or lower on the longest, hardest tasks.

Read that again. These are the best models available, tested on synthetic tasks with no ambiguity, no retrieval, no tool use, no long-tail knowledge. The task is to apply a list of assignments and report the final values. At 10,000 tokens of updates, they cannot do it reliably, because tracking a changing state over a long sequence is, for a transformer, a genuinely hard computation, and the paper shows exactly where the boundary sits.

Finding 4: The same sequences, formatted differently, give different scores

Pretrained models were strongly affected by surface format. Data formatted like sequences from RULER, a long-context retrieval benchmark, was much easier than the exact same sequences formatted as spreadsheet cell manipulations. Small models reached near-ceiling performance on RULER-formatted r-trivial data and near-chance on spreadsheet-formatted data. Even the 7B models generalized better to longer sequences in the RULER format, and RULER-formatted samples showed lower variance.

The authors report the maximum score across all six formats, which is generous. The lesson for anyone running evaluations is the opposite of generous: if you test a capability in one format only, you are measuring format familiarity as much as capability. Run the same test in several surface forms, and trust the worst one more than the best one.

Finding 5: Periodic tracking is hard because it is sensitive, and curricula do not fix it

The paper connects the difficulty to sensitivity, a measure of how much changing one input step can change the final output. Aperiodic problems have sensitivity that grows slower than the sequence length. Periodic problems have sensitivity that grows linearly with it. One wrong step early on can flip the answer, and the longer the sequence, the more steps can do that.

To check whether this matters outside synthetic data, the authors measured sensitivity on CruxEval, a benchmark of real Python methods with inputs and expected outputs. Code samples showed a split distribution, with peaks at very high and very low sensitivity. Periodic state tracking shows up in real code, and it is the part of code understanding that models handle worst. Among models that could learn general finite data at all, higher-sensitivity samples were consistently harder.

They also tested whether ordering training data by ascending sensitivity, a curriculum, would help. It had negligible effects on GDN and hybrid models and on transformers without positional embeddings, and only a weak positive effect on transformers with rotary embeddings on in-distribution general finite sequences. A curriculum does not rescue an architecture from a capability gap.

What this means for data and AI practitioners

1. Test agents on long stateful tasks, not just retrieval. A model that scores well on needle-in-a-haystack tests can still lose track of a spreadsheet after a few hundred edits. If your agent maintains state across a session, build an eval that grows the number of updates and watch where accuracy breaks.
2. Treat the 10,000-token mark as a cliff. Frontier models held up on the easy tiers and then collapsed on soluble and general finite tracking between 10,000 and 64,000 tokens. If your workflow crosses that length, verify the final state independently rather than trusting the model to carry it.
3. Report the worst format, not the best. The same StateBench sequences scored near ceiling in one format and near chance in another. One-format evaluations flatter models. Run several surface forms and take the minimum seriously.
4. Do not assume scale closes the gap. A 7B pretrained model failed completely on general finite data, and direct-training experiments show the split is architectural. If your task needs periodic state tracking, a bigger transformer will not close it. A different architecture, or an external state store the model reads and writes explicitly, will.
5. Keep state outside the model when it matters. The honest engineering response to this paper is to stop asking the model to be the database. Log every state change in a store you control, and have the model read the current state back instead of reconstructing it from a long transcript.

Against

StateBench measures a narrow, synthetic skill. The sequences are generated, the variables are abstract, and the tasks have no noise, no ambiguity and no real-world context. A model could fail here and still do fine on practical stateful work where it can re-read the document, call a tool, or ask a clarifying question. The frontier evaluation also used a generative setting, which is harder than the five-choice setting used for the smaller models, so the frontier numbers are not directly comparable to the pretrained ones.

In favour

The narrowness is the point. By controlling variables, values and positions across levels, the benchmark isolates the one thing it claims to measure. The results line up with the theory, with the direct-training experiments, and with the sensitivity analysis of real code. Three independent lines of evidence pointing at the same boundary is harder to dismiss than any one benchmark score.

What would make me wrong

If a transformer-based frontier model, evaluated in the same generative setting, holds well above chance on soluble and general finite StateBench tasks at 64,000 tokens, the architectural ceiling claim weakens. If the format effect turns out to be an artifact of one format being badly specified rather than a real capability gap, the formatting lesson softens. And if agents given an external state store show no advantage over agents asked to track state internally on the same long tasks, the engineering advice above is overkill. All three are testable, and the benchmark and code are public.

Sources

• Petty, Merrill and Sabharwal, "A Fine-Grained Hierarchy and Benchmark for State Tracking in Language Models", arXiv:2611.03094
• Full text of the paper
• A plain-language summary of the paper, including the 13% figure on the longest tasks

Related on Everyday Data Science

• Switching Agent Harnesses Changed 13% of Tasks. Rerunning the Same One Changed 13% Too
• Five Leaks That Inflate Your AUC: I Measured Each One
• A True Tool Result Can Still Be Wrong: ReplayBench Found a 64.9% Error Rate

How do you test whether your agent actually remembers what changed, rather than just sounding like it does?