Tool Reviews

StateBench evaluates how language models track state changes across lengthy documents

StateBench tests long-context LLM state tracking across four difficulty levels, revealing where architectures fail and aiding model selection.

StateBench evaluates how language models track state changes across lengthy documents

Key Takeaways

  • StateBench evaluates how well long-context language models track changing variables and entities across documents, helping diagnose where architectures fail.
  • It defines four difficulty levels—R-trivial, Aperiodic, Soluble, and General finite—corresponding to different kinds of variable assignment and grounded in Krohn–Rhodes theory.
  • Pretrained models mostly succeed on R-trivial tasks, degrade on Aperiodic tasks as context grows, and perform near chance on General finite tasks; task format also affects results.
  • Frontier models remain strong on easier tasks but struggle sharply on Soluble and General finite tasks as dependency chains lengthen, with the hardest cases reaching 13% accuracy or lower.
  • Direct training on StateBench helps separate model-architecture limits from gaps caused by pretraining data.

StateBench tests whether language models track changing variables, helping researchers and developers see where long-context systems break down.

StateBench evaluates how language models track state changes across lengthy documents

A research team introduced StateBench in a technical report, a benchmark for long-context state tracking that measures how well models keep track of information about entities as documents evolve. For researchers, engineers, and teams selecting long-context language models, StateBench offers a practical diagnostic: it separates simple and hard forms of state tracking and reveals where model architectures fail. The benchmark targets the ability to follow changes that matter in code, stories, and conversations. A model may read a long document, but if it cannot tell which character holds an object, which variable has which value, or which update is current, the answer may be wrong.

Four difficulty levels turn state tracking into variable assignments

StateBench organizes tasks into four levels: R-trivial, Aperiodic, Soluble, and General finite. For programmers, the levels can be read as different kinds of variable assignment.

R-trivial problems use immutable assignment. A variable’s value never changes, so the model only needs to recover the value it was first set to. In code, this resembles let x = 4. In everyday life, it is closer to a birth date: the value stays fixed.

Aperiodic problems allow reassignment by value. The model must identify the most recent value and ignore earlier ones. In code, this looks like x = 4 followed later by x = 2. In everyday life, it resembles 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 carry changes forward rather than simply find the latest assignment. In code, this looks like x = x + 5. In everyday life, it resembles a game score, where each point adds to a running total.

General finite problems add assignment by reference. One variable can take another variable’s current value, creating dependencies across updates. In code, this looks like x = y or swapping two variables. A more vivid version is a magician hiding a ball under one of five cups, then repeatedly swapping the cups’ positions. Finding the ball requires tracking how each swap changes the ball’s location. This illustrates the S₅ state-tracking problem: following how successive swaps rearrange five objects. It belongs to the hardest level in StateBench and connects to earlier work on state-tracking limits.

These levels are not only practical categories. They also reflect theoretical distinctions in Krohn–Rhodes theory, a branch of algebra that describes how state-tracking problems can be viewed as word problems over finite monoids and decomposed into atomic primitives. Each StateBench level corresponds to a class of problems built from a different set of primitives.

To compare the four levels fairly, the benchmark starts with a general finite sequence of variable assignments and derives easier versions from it. That produces four comparable problems, one at each level. They use the same number of variables and distinct values, and the assignments appear at the same points in the sequence. Only the type of assignment changes.

Pretrained models fail differently by architecture and format

The authors first evaluated a range of open pretrained models on the R-trivial, Aperiodic, and General finite levels. The goal was to see where state tracking breaks down and whether failures match theoretical expectations. Under standard theoretical assumptions, transformers can handle R-trivial tasks robustly, and can manage Soluble and Aperiodic problems to some degree, but are predicted to fail on general problems. Gated DeltaNet, with a more flexible memory update, can in principle handle all four levels.

The tests used open pretrained models with documented training data and context lengths. These included two 7-billion-parameter models: Olmo 3, a transformer, and Olmo Hybrid, which adds Gated DeltaNet layers. Smaller 275-million-parameter and 2.7-billion-parameter models were also tested. All were pretrained on the same data. None had seen contexts longer than 64,000 tokens during training, and most were tested on inputs well beyond that length.

The results showed a common pattern. Almost all models performed well on R-trivial problems. Accuracy dropped on Aperiodic problems as inputs grew longer. On General finite problems, the models stayed at chance.

Format 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 problems were framed as spreadsheet edits. This gap is one reason StateBench tests the same problem in several formats.

Frontier models struggle as dependency chains grow

The researchers next tested four frontier models: Gemini 3.8 Flash, Claude Opus 5.5, and GPT-6 Sol and Luna. Each model was asked to read a sequence of variable assignments and generate the final value of every variable.

The frontier models performed well on R-trivial and Aperiodic problems. On Soluble and General finite problems, accuracy fell sharply as inputs grew longer. On the longest General finite problems, performance dropped to 13% or lower.

One likely factor is sensitivity. At the harder levels, many more steps can affect the final answer. That leaves less room for a model to miss an update without getting the result wrong.

Direct training separates architecture limits from pretraining gaps

The next question was whether the harder levels expose limits of the model architectures themselves, or whether pretraining simply does not teach models to solve them. The team tested this by training models directly on StateBench, a more favorable setting that isolates architecture and optimizer effects from pretraining data.

They trained several 275-million-parameter models from scratch: two transformer variants, two hybrid variants, 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 as long as 64,000 assignments, or 250 times the maximum training length.

As sequences grew longer, the architectures diverged. Gated DeltaNet and hybrid models generalized almost perfectly on R-trivial, Aperiodic, and Soluble problems out to the longest tested sequences, which reached 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. It stayed near perfect out to roughly 10 times the length of the longest sequences it saw during training.

The contrast matters. For Gated DeltaNet and hybrid models, the gap between pretrained and directly trained performance points to training, not architecture alone. Trained directly, they learned state-tracking levels their pretrained counterparts could not handle. Transformers were different: even with direct training, they could never learn the hardest level.

Open questions and what the benchmark may change

StateBench also leaves important questions open. A new proof in the work shows that Gated DeltaNet with a more limited memory update, using non-negative eigenvalues, can solve all Aperiodic tasks and certain periodic tasks. Those periodic tasks include tracking whether a repeated input has occurred an even or odd number of times, under fixed-precision arithmetic with rounding. Its exact placement in the hierarchy remains open. It is still unclear whether it can solve all Soluble tasks, or how numerical precision or combining it with attention layers affects its capabilities.

Another limitation is that StateBench assumes a fixed number of variables. Real tasks often introduce new entities over time. In a long conversation, for example, new people and objects can appear as the exchange unfolds, and the model must begin tracking them too. The current framework does not yet cover that setting.

The benchmark gives researchers a finer-grained way to find where models break down. That matters as recurrent and hybrid architectures become more common. Knowing which kinds of state tracking each architecture can handle could help guide how future systems are developed and trained. StateBench may also help teams build training and evaluation data for capabilities that still fall short, and push new architectures toward more robust state tracking than current models.

Tags: StateBench, long context, language models, state tracking, Gated DeltaNet

Comments (0)

  1. No comments yet. Be the first to share what worked for you.

Leave a comment

Comments are reviewed before they appear. Your email address is not published.