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

Back to Articles StateBench: Testing how language models track state changes over long documents Enterprise Article Published November 3, 2026 Upvote 1 Kyle Wiggers Ai2Comms Follow allenai 📄 Tech Report | 🤗 Data | 💻 Code We’re introducing StateBench, a benchmark for long-context state tracking—how well language models keep track of information about entities in long documents as they evolve.

State tracking underlies tasks from reading code, where variables are assigned and reassigned, to following a story as characters physically move around and objects change hands.

For example, if a mystery novel states that “John gave Mary the knife” right before a murder occurs, it’s important to know that the state of each character has changed.

However, not all state-tracking problems are created equal: some require only finding the latest update; harder ones require following a chain of changes, where one missed step can throw off the final answer.

For example, a harder variant of our mystery state tracking would be if John gave Mary the item in his backpack, with it previously known that Edward put a knife in John’s backpack.

Transformers have well-documented theoretical limits on hard variants of state tracking with long dependency chains, helping motivate recurrent and hybrid architectures such as Gated DeltaNet that carry a running memory forward.

Existing state-tracking tests tend to focus on the hardest cases, but as these designs become more common, researchers need to know which kinds of state tracking each architecture can handle.

We would like to understand the differences between architectures not just on the hardest kinds of state tracking, but also on the simpler, potentially more common kinds.

To this end, we developed the StateBench benchmark to capture state-tracking problems of different complexity, which we used to evaluate the differences between language models with different architectures.

We find that recurrent and hybrid models can generalize much farther than transformers when trained directly on these tasks, while frontier models including Gemini 3.8 Flash, Claude Opus 5.5, and GPT-6 Sol and Luna still break down on harder forms of state tracking as inputs grow longer.

Four levels of state tracking StateBench consists of four difficulty levels that permit increasingly complex state update operations.

For programmers, these levels of state tracking complexity can be understood as allowing different types of variable assignment operations: R-trivial problems use immutable assignment.A variable’s value never changes, so the model only needs to recover what it was first set to.

In code, this looks like let x = 4; in everyday life, it’s like a birth date—it stays fixed.Aperiodic problems allow reassignment by value.The model needs to find the most recent value and can ignore earlier ones.

In code, this looks like x = 4 followed later by x = 2; in everyday life, it’s 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 has to carry changes forward rather than simply find the latest assignment.In code, this looks like x = x + 5; in everyday life, it’s like a game score, where each point adds to the running total.

General finite problems add assignment by reference.One variable can take on another variable’s current value, creating dependencies across updates.In code, this looks like x = y or swapping two variables.

Imagine a magician hiding a ball under one of five cups, then repeatedly swapping their positions.Finding the ball means keeping track of how those swaps change its location.This illustrates the S₅ state-tracking problem: following how successive swaps rearrange five objects.

It belongs to the hardest of our four levels and is discussed in previous work on the limits of state tracking.

These levels can be intuitively understood in terms of variable assignments, but they also represent theoretically motivated distinctions in state tracking rooted in Krohn–Rhodes theory, a branch of algebra that describes how state-tracking problems – which can be viewed as word problems over finite monoids – can be decomposed into atomic primitives.

Each level in our hierarchy corresponds to a class of state-tracking problems that can be built out of a different set of primitives.

To compare the four levels fairly, we start with a general finite sequence of variable assignments and derive three easier versions from it, producing four comparable StateBench problems—one at each difficulty level.

All four use the same number of variables and distinct values, with assignments appearing at the same points in the sequence; only the type of assignment changes.

What we found Pretrained models We tested a range of open pretrained models on the r-trivial, aperiodic, and general finite levels of StateBench to see where their state tracking breaks down, and whether different architectures fail where theory predicts.

Under standard theoretical assumptions, transformers can handle r-trivial robustly (and soluble and aperiodic to some degree) but are predicted to fail on general problems.In contrast, Gated DeltaNet with a more flexible memory update can, in principle, handle all four levels.

We started with open pretrained models, where the training data and context lengths are fully documented.These included two 7-billion-parameter models, Olmo 3 (a transformer) and Olmo Hybrid (which adds Gated DeltaNet layers), along with smaller models with 275 million and 2.7 billion parameters.

All of these models were pretrained on the same data; none had seen contexts longer than 64,000 tokens during training, and we tested most of them on inputs well beyond that length.

When we scored each model, almost all performed well on r-trivial problems, lost accuracy on aperiodic ones as inputs grew, and stayed at chance on general finite problems.

Problem format mattered here—the 275-million-parameter hybrid and Gated DeltaNet models scored near the ceiling on RULER-style r-trivial problems but were near chance on the same problems framed as spreadsheet edits.

That gap is one reason StateBench tests the same underlying problem in several formats.Frontier models We then tested four frontier models – Gemini 3.8 Flash, Claude Opus 5.

5, and GPT-6 Sol and Luna – asking them to read each sequence of variable assignments and generate the final value of every variable.All four performed well on r-trivial and aperiodic problems.

But on soluble and general finite problems, accuracy fell sharply as inputs grew longer, dropping to 13% or lower on the longest general finite problems.

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

Models trained directly on the task Next, we investigated whether models’ difficulty with the harder levels reflects limits of the architectures themselves, or whether pretraining simply doesn’t teach models to solve them.

Targeted direct training is a more favorable setting that reveals to what degree state-tracking issues come from the underlying architecture and optimizer rather than the data used to pretrain a model.

We trained several 275-million-parameter models from scratch on StateBench: two transformer variants, two hybrids, 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.The architectures began to diverge as sequences grew longer.

Gated DeltaNet and hybrid models generalized almost perfectly on r-trivial, aperiodic, and soluble problems out to the longest sequences we tested, 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, staying near perfect out to roughly 10 times the length of the longest sequences it saw during training.

For Gated DeltaNet and hybrid models, the gap points to training rather than architecture; trained directly, they learned to handle state-tracking levels their pretrained counterparts couldn’t.Transformers were different—even trained directly, they could never learn the hardest level.

Open questions and the release Some questions remain open.

Our new proof shows that Gated DeltaNet with a more limited memory update (non-negative eigenvalues) can solve all aperiodic tasks and certain periodic tasks, such as tracking whether a repeated input has occurred an even or odd number of times, under the paper’s fixed-precision arithmetic with rounding.

Its exact placement in the hierarchy remains open, including whether it can solve all soluble tasks and how numerical precision or combining it with attention layers affects 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 can appear as it unfolds, and the model has to begin tracking them too.The current framework doesn’t yet cover that setting.

As new flavors of recurrent and hybrid architectures emerge, understanding which kinds of state tracking each can handle could help guide how future systems are developed and trained.

We hope StateBench gives researchers a finer-grained way to find where models break down—and to build training and evaluation data for the capabilities that still fall short.

More fundamentally, we hope it serves as a North Star for researchers to develop new architectures with more robust state-tracking abilities compared to current models.Datasets mentioned in this article 1 More from this author Can we trust LLMs to judge whether a research idea is novel?

18 October 27, 2026 LitPivot: Developing research ideas through dynamic contextualization within the literature landscape 39 October 23, 2026 Community EditPreview Upload images, audio, and videos by dragging in the text input, pasting, or clicking here.

Tap or paste here to upload images Comment · Sign up or log in to comment Upvote 1 Datasets mentioned in this article 1