StateBench: Testing how language models track state changes over long documents

Understanding StateBench

StateBench is a diagnostic benchmark designed to measure how effectively language models track information about entities as they evolve throughout long documents. State tracking is a fundamental capability for tasks ranging from code execution, where variables are continuously reassigned, to narrative comprehension, where the positions and states of characters change over time. By categorizing these tasks into four distinct levels of complexity, StateBench allows researchers to identify where specific model architectures—ranging from standard transformers to recurrent and hybrid designs—begin to fail as input length increases.

The Four Levels of State Tracking

StateBench organizes state-tracking problems into a hierarchy based on the complexity of their update operations, rooted in Krohn–Rhodes theory. These levels represent increasing difficulty in maintaining an accurate internal state:

  • R-trivial: Problems involving immutable assignments where values never change, requiring the model to simply recover the initial state.
  • Aperiodic: Problems allowing reassignment by value, where the model must identify the most recent update while ignoring earlier data.
  • Soluble: Problems involving self-referential updates (e.g., x = x + 5), requiring the model to carry a running total forward.
  • General Finite: The most complex level, involving assignment by reference (e.g., swapping variables or tracking objects across multiple containers), which creates intricate dependencies across the sequence.

Performance of Pretrained and Frontier Models

Evaluations of current models reveal a consistent degradation in performance as input lengths grow, particularly on harder tasks. When testing frontier models—including Gemini 3.8 Flash, Claude Opus 5.5, and GPT-6 Sol and Luna—researchers observed that while these models handle R-trivial and aperiodic tasks well, their accuracy drops sharply on soluble and general finite problems as inputs lengthen. This suggests that the current generation of large-scale models struggles with the cumulative nature of complex, long-dependency state tracking.

Architectural Limitations and Direct Training

To determine if these failures are inherent to model architectures or a result of insufficient training, researchers trained 275-million-parameter models from scratch on StateBench. The findings indicate that architectural differences significantly impact generalization:

  • Transformers: Even when trained directly on the tasks, transformers failed to learn the hardest (general finite) level of state tracking.
  • Hybrid and Gated DeltaNet: These architectures demonstrated superior generalization. When trained directly, they successfully handled R-trivial, aperiodic, and soluble problems out to tens of thousands of assignments. The Gated DeltaNet variant with flexible memory updates showed the most robust performance, remaining near-perfect at lengths 10 times greater than those seen during training.

Implications for Future Development

StateBench highlights that while current frontier models are highly capable, they remain limited by their underlying architectural constraints when managing complex, long-range state dependencies. The benchmark provides a framework for researchers to evaluate new recurrent and hybrid architectures, serving as a tool to guide the development of systems capable of more robust, long-context reasoning. Future work aims to address limitations in the current framework, such as the handling of dynamic entity creation, where new variables are introduced throughout a document.

Sources