The challenge of state tracking in extensive contexts
State tracking is a fundamental capability for language models to understand long documents, code, or narratives. It involves tracking how entity properties change throughout the text, such as the position of an object, the value of a variable, or the state of a character. Without this skill, a model may lose coherence when processing information that is repeatedly updated.
Although current models handle contexts of tens of thousands of tokens well, their ability to follow chains of linked changes remains limited. StateBench, developed by the Allen Institute for AI (AI2), seeks to measure these limits precisely through a hierarchy of tasks ranging from recovering an initial value to tracking complex dependencies between multiple variables.
Four levels of complexity in StateBench
StateBench organizes tasks into four difficulty levels based on Krohn-Rhodes theory, which describes how state-tracking problems can be decomposed into algebraic primitives. Each level introduces a more complex type of variable update than the previous one, allowing evaluation of exactly where a model fails.
The most basic level, R-trivial, uses immutable assignments where a variable's value never changes. The model only needs to recover the initial value. The next level, Aperiodic, allows value reassignment, requiring the model to identify the latest update. These two levels are manageable for most pretrained models.
StateBench difficulty levels
Comparison of the four StateBench levels with their programming equivalents and everyday examples.
| Level | Assignment Type | Code Example | Everyday Example |
|---|---|---|---|
| R-trivial | Immutable | let x = 4 | Birth date |
| Aperiodic | Reassignment by value | x = 4; x = 2 | Thermostat |
| Soluble | Self-referential update | x = x + 5 | Game score |
| General Finite | Assignment by reference | x = y; swap(x, y) | Balls under cups |
Results in pretrained and frontier models
AI2 evaluated a series of open and frontier models on the R-trivial, Aperiodic, and General Finite levels. Pretrained models, such as Olmo 3 (transformer) and Olmo Hybrid (with Gated DeltaNet layers), showed solid performance on basic levels but lost accuracy on Aperiodic problems as inputs grew longer. On General Finite problems, all pretrained models remained near chance level.
Frontier models, including Gemini 3.8 Flash, Claude Opus 5.5, and GPT-6 Sol and Luna, performed well on R-trivial and Aperiodic levels. However, on Soluble and General Finite levels, their accuracy dropped sharply with input length, falling below 13% on the longest problems. This suggests that sensitivity to accumulated errors in long chains is a significant limit for current architectures.
Direct training and architectural differences
To determine whether limitations stem from architecture or pretraining data, AI2 trained 275-million-parameter models from scratch directly on StateBench. Transformer, hybrid, and Gated DeltaNet variants were compared. Models were trained on sequences of up to 256 assignments and evaluated on sequences of up to 64,000 assignments, 250 times the maximum training length.
Results showed a clear divergence: Gated DeltaNet and hybrid models generalized almost perfectly on R-trivial, Aperiodic, and Soluble levels up to the longest sequences. In contrast, transformers learned the easier levels but degraded on long sequences and failed to learn the General Finite level. This indicates that for recurrent and hybrid models, the issue is training, while for transformers it is a fundamental architectural limitation.
Limits and open questions
StateBench assumes a fixed number of variables, which does not fully reflect real tasks where new entities appear during a conversation or document. Additionally, the exact position of certain Gated DeltaNet variants in the theoretical hierarchy remains open, especially regarding numerical precision and combination with attention layers.
Despite these limits, StateBench offers a valuable tool for researchers. It allows identifying with high granularity where models fail and guides the development of new architectures with more robust state-tracking capabilities. The availability of data and code facilitates replication and extension of these experiments.
How to interpret StateBench results
When evaluating a model with StateBench, it is crucial to consider the difficulty level and input length. Good performance on R-trivial does not guarantee success on General Finite. Generalization beyond training length is a key indicator of architectural robustness.
- 01Identify the difficulty level of the task (R-trivial to General Finite).
- 02Compare the input length with the model's maximum training length.
- 03Evaluate whether accuracy degradation is gradual or abrupt as length increases.
- 04Consider whether the model was trained directly on the task or only pretrained.
Keep exploring
Corrections and transparency
If you spot incorrect or outdated information, send us a correction with the page and source we should review.
Submit a correction