📄 Technical Report | 🤗 Data | 💻 Code
We introduce StateBench, a benchmark for long-context state tracking designed to evaluate language models’ ability to track evolving entity information across long documents.
State tracking underpins a wide range of tasks: from reading variable assignments and renames in code to following characters moving around and exchanging items in a story. For example, if a mystery novel states before a murder that “John handed the knife to Mary,” knowing how each character’s state has changed is crucial. However, not all state-tracking problems are equally difficult: some only require locating the most recent update, while harder ones demand tracking a long chain of changes where missing a single step leads to an incorrect final answer. A harder variant of the mystery novel example would be: John hands the contents of his backpack to Mary, after Edward had previously placed a knife inside it.
On complex state-tracking variants with long dependency chains, the Transformer architecture has well-established theoretical limitations. This has motivated the development of recurrent and hybrid architectures, such as Gated DeltaNet, capable of carrying a running memory forward. Existing state-tracking benchmarks often focus on the most extreme edge cases, but as these new architectural designs become increasingly common, researchers need to understand exactly which types of state tracking each architecture can handle. We aim to understand how different architectures perform not only on the hardest state-tracking tasks, but also on simpler, potentially more common ones.
To this end, we developed StateBench to span state-tracking problems across varying levels of complexity, and used it to evaluate differences among language models of different architectures. We found that when trained directly on these tasks, recurrent and hybrid models exhibit generalization capabilities far exceeding those of Transformers; meanwhile, frontier models—including Gemini 3.8 Flash, Claude Opus 5.5, and GPT-6 Sol and Luna—still break down on more complex forms of state tracking as input length grows.
Four Levels of State Tracking
StateBench features four difficulty tiers that permit state update operations of increasing complexity. For programmers, these tiers of state-tracking complexity can be understood as supporting different kinds of variable assignments:
-
R-trivial problems use immutable assignment. A variable’s value never changes, so the model only needs to retrieve the value it was originally assigned. In code, this is like
let x = 4;; in everyday life, it is like a birth date—fixed and unchanging. -
Aperiodic problems allow reassignment by value. The model needs to find the latest value and can ignore earlier ones. In code, this is like running
x = 4followed later byx = 2; in everyday life, it is like a thermostat, where the latest setting determines the current temperature. -
Soluble problems add self-referential updates. Each update builds on the current value, so the model must continually carry changes forward rather than simply looking for the most recent assignment. In code, this is like
x = x + 5; in everyday life, it is like a game score, where each point accumulates onto the existing total. -
General finite problems add assignment by reference. A variable can take on another variable’s current value, creating dependencies across different updates. In code, this is like
x = yor swapping two variables. Imagine a magician hiding a ball under one of five cups and repeatedly swapping them. Finding the ball requires tracking how each swap permutes its position. This exemplifies the $S_5$ state-tracking problem: tracking how successive transpositions rearrange five objects. It represents the hardest of our four tiers and has been discussed in prior work on state-tracking limitations.
Beyond an intuitive understanding through variable assignments, these tiers represent a theoretically grounded classification of state tracking rooted in Krohn–Rhodes theory. This branch of algebra describes how state-tracking problems—which can be viewed as word problems over finite monoids—can be decomposed into atomic primitives. Each tier in our hierarchy corresponds to a class of state-tracking problems that can be constructed from a different set of primitives.
To fairly compare these four tiers, we start from a general finite sequence of variable assignments and derive three simpler versions from it, yielding four comparable StateBench problems—one for each difficulty tier. All four problems use the same number of variables and distinct values, with assignments occurring at the same positions in the sequence; only the type of assignment changes.
What We Found
Pretrained Models
We evaluated a range of open-source pretrained models across the R-trivial, aperiodic, and general finite tiers of StateBench to observe where their state tracking breaks down and whether different architectures fail where theory predicts. Under standard theoretical assumptions, Transformers can robustly handle R-trivial problems (and to some extent soluble and aperiodic problems), but are expected to fail on general problems. In contrast, Gated DeltaNet, with its more flexible memory-update mechanism, can in principle handle all four tiers.
We first tested open-source pretrained models whose training data and context lengths are fully public. These included two 7-billion-parameter (7B) models: Olmo 3 (Transformer-based) and Olmo Hybrid (incorporating Gated DeltaNet layers), along with smaller 275-million (275M) and 2.7-billion (2.7B) parameter models. All these models were pretrained on the same data; none had seen contexts exceeding 64,000 tokens during training, yet we evaluated most of them on inputs far beyond that length.
Evaluating each model revealed that nearly all models performed well on R-trivial problems, but their accuracy gradually declined on aperiodic problems as inputs lengthened, while remaining at random-chance levels on general finite problems. The presentation format of the problem played a crucial role here—the 275M hybrid and Gated DeltaNet models scored near 100% on RULER-style R-trivial problems, but when the same problem was framed as spreadsheet editing, their performance dropped to near chance. This disparity is one reason why StateBench tests the same underlying problems across multiple formats.
Frontier Models
We then evaluated four frontier models—Gemini 3.8 Flash, Claude Opus 5.5, and GPT-6 Sol and Luna—prompting them to read each sequence of variable assignments and output the final value for each variable.
All four models performed well on R-trivial and aperiodic problems. However, on soluble and general finite problems, accuracy dropped sharply as input length increased, falling to 13% or lower on the longest general finite instances. One likely factor is sensitivity: at these higher tiers, far more steps can influence the final answer, leaving virtually no margin of error for the model to produce the correct result if it misses a single update.

