StateBench Evaluates How Language Models Track State Changes in Long Documents

StateBench Evaluates How Language Models Track State Changes in Long Documents

Published November 3, 2026

Ai2 introduced StateBench, a benchmark for evaluating long-context state tracking: the ability of language models to retain information about entities as that information changes throughout a document.

State tracking supports tasks such as reading code, where variables are assigned and reassigned, and following narratives in which characters move or objects change hands. If a mystery novel says that John gave Mary a knife immediately before a murder, for example, the model must recognize that the objects associated with the characters have changed. Some tasks only require finding the latest update. More difficult tasks require following a chain of changes, where missing one intermediate step can produce an incorrect final result. One example is determining what John gave Mary when Edward previously placed a knife in John’s backpack.

Transformers have documented theoretical limitations on difficult state-tracking tasks involving long dependency chains. These limitations have helped motivate recurrent and hybrid architectures, including Gated DeltaNet, which maintain a running memory. Existing evaluations often focus on the hardest cases, but researchers also need to understand which types of state tracking different architectures can handle, including simpler cases that may occur more frequently.

StateBench was designed to measure state-tracking problems across several complexity levels. Ai2 used it to compare language models with different architectures. Recurrent and hybrid models generalized much farther than transformers when trained directly on these tasks. Frontier models, including Gemini 3.8 Flash, Claude Opus 5.5, and GPT-6 Sol and Luna, still failed on harder state-tracking problems as the inputs became longer.

Four Levels of State Tracking

StateBench has four difficulty levels, each allowing more complex state-update operations. The levels can be compared to different types of variable assignment:

• R-trivial problems use immutable assignment. A variable’s value never changes, so the model only needs to recover its initial value. In code, this resembles let x = 4. In everyday life, a birth date is an example of information that remains fixed.
• Aperiodic problems allow reassignment by value. The model must identify the most recent value and can disregard earlier ones. In code, this resembles x = 4 followed later by x = 2. A thermostat setting is a practical analogy because the latest setting determines the current state.
• Soluble problems add self-referential updates. Each update depends on the current value, so the model must carry changes forward instead of locating only the latest assignment. In code, this resembles x = x + 5. A game score works as an everyday example because each point changes the running total.
• General finite problems add assignment by reference. One variable can take the current value of another, creating dependencies across updates. In code, this resembles x = y or swapping two variables. Another example is a magician hiding a ball under one of five cups and repeatedly swapping the cups. Locating the ball requires tracking how every swap changes its position. This is an example of the S₅ state-tracking problem, one of the most difficult levels discussed in previous work on the limits of state tracking.

These levels can be explained through variable assignments, but they also reflect distinctions from Krohn-Rhodes theory, a branch of algebra concerned with state-tracking problems represented as word problems over finite monoids. The theory describes how such problems can be decomposed into atomic primitives, with each level in the StateBench hierarchy corresponding to a different set of primitives.

For a fair comparison, StateBench starts with a general finite sequence of variable assignments and derives three easier versions. This produces four comparable problems, one at each difficulty level. Each version uses the same number of variables and distinct values, and assignments appear at the same points in the sequence. Only the assignment type changes.

Findings

Pretrained Models

The evaluation included open pretrained models on the r-trivial, aperiodic, and general finite levels. The goal was to identify where state tracking failed and whether the failures matched theoretical expectations. Under standard theoretical assumptions, transformers can handle r-trivial tasks reliably, and can handle soluble and aperiodic tasks to some extent, but are expected to fail on general problems. Gated DeltaNet, with a more flexible memory update, can in principle handle all four levels.

The evaluation began with open pretrained models whose training data and context lengths are documented. The models included two 7-billion-parameter systems, Olmo 3, a transformer, and Olmo Hybrid, which adds Gated DeltaNet layers. Smaller models with 275 million and 2.7 billion parameters were also tested. All models were pretrained on the same data. None had encountered contexts longer than 64,000 tokens during training, while most were evaluated on inputs substantially longer than that.

Almost all models performed well on r-trivial problems, lost accuracy on aperiodic problems as inputs grew, and remained near chance on general finite problems. The format of the problem also mattered. The 275-million-parameter hybrid and Gated DeltaNet models scored near the ceiling on RULER-style r-trivial problems but were near chance when the same underlying tasks were presented as spreadsheet edits. This difference is one reason StateBench represents each underlying problem in multiple formats.

Frontier Models

Four frontier models were tested: Gemini 3.8 Flash, Claude Opus 5.5, GPT-6 Sol, and GPT-6 Luna. Each model read a sequence of variable assignments and generated the final value of every variable.

All four performed well on r-trivial and aperiodic problems. On soluble and general finite problems, however, accuracy fell sharply as the inputs became longer. Accuracy reached 13% or lower on the longest general finite problems. A likely factor is sensitivity: at the harder levels, many more steps can affect the final answer, so missing a single update is more likely to produce an incorrect result.

Models Trained Directly on StateBench

The next evaluation examined whether failures on the harder levels reflected architectural limitations or whether pretraining simply failed to teach the necessary procedures. Direct task training provides a more favorable setting for separating limitations caused by architecture and optimization from those caused by pretraining data.

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

The architectures diverged as sequence lengths increased. Gated DeltaNet and hybrid models generalized almost perfectly on r-trivial, aperiodic, and soluble problems through the longest tested sequences, which contained tens of thousands of assignments. Transformers learned the easier levels but degraded on longer sequences and never learned general finite problems.

On the hardest level, the Gated DeltaNet variant with the more flexible memory update generalized the farthest. It remained near perfect through approximately 10 times the length of the longest sequences used during training.

For Gated DeltaNet and hybrid models, the results indicate that training was an important factor. When trained directly, these models learned to handle state-tracking levels that their pretrained counterparts could not. Transformers showed a different pattern: even with direct training, they could not learn the hardest level.

Open Questions

Several questions remain unresolved. A new proof shows that Gated DeltaNet with a more limited memory update, using non-negative eigenvalues, can solve all aperiodic tasks and certain periodic tasks. One example is determining whether a repeated input has occurred an even or odd number of times. This result assumes the paper’s fixed-precision arithmetic with rounding.

The architecture’s precise position in the hierarchy remains open. It is not yet known whether this version can solve all soluble tasks, or how numerical precision and the addition of attention layers affect its capabilities.

StateBench also assumes a fixed number of variables, while real tasks often introduce new entities over time. In a long conversation, for example, new people and objects may appear as the conversation progresses, requiring the model to begin tracking them. The current framework does not yet cover this setting.

As recurrent and hybrid architectures continue to develop, identifying the types of state tracking each architecture can handle may help researchers design and train future systems. StateBench provides a more detailed way to identify where models fail and to develop training and evaluation data for capabilities that remain limited.