What does StateBench reveal about language models tracking state changes over long documents?

Four levels of increasing complexity

StateBench organizes state-tracking problems into four difficulty levels. Each level corresponds to a class of variable assignment operations that programmers recognize. R-trivial problems use immutable assignment — a variable's value never changes, so the model only needs to recover what it was first set to. Aperiodic problems allow reassignment by value; the model must find the most recent value and can ignore earlier ones. Soluble problems add self-referential updates where each update builds on the current value, forcing the model to carry changes forward. General finite problems add assignment by reference, letting one variable take on another variable's current value and creating dependencies across updates.

The magician's cup-and-ball trick illustrates the hardest level. A ball hides under one of five cups; the magician repeatedly swaps their positions. Finding the ball means keeping track of how those swaps change its location. This S₅ problem belongs to the general finite level and appears in previous work on the limits of state tracking.

All four StateBench levels use the same number of variables and distinct values, with assignments appearing at the same points in the sequence. Only the assignment type changes.

Pretrained models hit a wall

Researchers tested a range of open pretrained models on the r-trivial, aperiodic, and general finite levels. Two 7-billion-parameter models — Olmo 3, a transformer, and Olmo Hybrid, which adds Gated DeltaNet layers — were evaluated alongside smaller models with 275 million and 2.7 billion parameters. All models shared the same training data. None had seen contexts longer than 64,000 tokens during training, yet most were tested on inputs well beyond that length.

Almost all models performed well on r-trivial problems. Accuracy dropped on aperiodic problems as inputs grew. On general finite problems, models stayed at chance.

Problem format mattered: the 275-million-parameter hybrid and Gated DeltaNet models scored near the ceiling on RULER-style r-trivial problems but were near chance on the same problems framed as spreadsheet edits. That gap is one reason StateBench tests the same underlying problem in several formats.

Frontier models still break down

Four frontier models — Gemini 3.8 Flash, Claude Opus 5.5, and GPT-6 Sol and Luna — were asked to read each sequence of variable assignments and generate the final value of every variable. All four performed well on r-trivial and aperiodic problems. On soluble and general finite problems, accuracy fell sharply as inputs grew longer, dropping to 13% or lower on the longest general finite problems. One likely factor is sensitivity; at these harder levels, many more steps can affect the final answer, leaving less room for a model to miss an update without getting the result wrong.

Direct training separates architecture from data

The team trained several 275-million-parameter models from scratch on StateBench: two transformer variants, two hybrids, and two Gated DeltaNet variants with different memory-update constraints. Models trained on sequences of up to 256 assignments and were tested on sequences as long as 64,000 assignments — 250 times the maximum training length.

Architectures began to diverge as sequences grew longer. Gated DeltaNet and hybrid models generalized almost perfectly on r-trivial, aperiodic, and soluble problems out to the longest sequences tested, tens of thousands of assignments. Transformers learned the easier levels but degraded on longer sequences, and they never learned general finite problems. On the hardest level, the Gated DeltaNet variant with a more flexible memory update generalized the farthest, staying near perfect out to roughly 10 times the length of the longest sequences it saw during training.

For Gated DeltaNet and hybrid models, the gap points to training rather than architecture; trained directly, they learned to handle state-tracking levels their pretrained counterparts couldn't. Transformers were different — even trained directly, they could never learn the hardest level.

Open questions remain

A new proof shows that Gated DeltaNet with a more limited memory update — non-negative eigenvalues — can solve all aperiodic tasks and certain periodic tasks, such as tracking whether a repeated input has occurred an even or odd number of times, under the paper's fixed-precision arithmetic with rounding. Its exact placement in the hierarchy remains open, including whether it can solve all soluble tasks and how numerical precision or combining it with attention layers affects its capabilities.

The benchmark also assumes a fixed number of variables, while real tasks often introduce new entities over time. In a long conversation, new people and objects can appear as it unfolds, and the model has to begin tracking them too. The current framework doesn't yet cover that setting. As new flavors of recurrent and hybrid architectures emerge, understanding which kinds of state tracking each can handle could help guide how future systems are developed and trained.