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

What it claims

StateBench is an Allen AI benchmark that separates long-context state tracking into four levels, each defined by the kind of variable assignment it allows. The levels map to classes of word problems over finite monoids in Krohn–Rhodes theory. The central finding is that recurrent and hybrid models trained on the task generalize far past their training length, while transformers never learn the hardest level. Frontier models also fail at that level on long inputs.

How it works

Each level adds one assignment type:

• R-trivial: immutable assignment (let x = 4). The model only has to recover the first value.
• Aperiodic: reassignment by value (x = 4, then x = 2). The latest value wins.
• Soluble: self-referential updates (x = x + 5). Changes must be carried forward.
• General finite: assignment by reference (x = y, swaps). This level includes the S₅ problem of tracking five objects through repeated swaps.

To keep levels comparable, each problem starts from a general finite sequence and three easier versions are derived from it. All four share the same number of variables, the same distinct values and the same assignment positions. Only the assignment type changes. The same problem is also posed in several surface formats, such as RULER-style retrieval and spreadsheet edits.

Evidence

Open pretrained models. These were Olmo 3 7B (transformer), Olmo Hybrid 7B (adds Gated DeltaNet layers), and smaller models at 275M and 2.7B parameters. All were pretrained on the same data with contexts no longer than 64,000 tokens, and most were tested beyond that length. Nearly all scored well on r-trivial, lost accuracy on aperiodic as length grew, and stayed at chance on general finite. Soluble was not tested in this setting. Format mattered a lot: the 275M hybrid and Gated DeltaNet models were near ceiling on RULER-style r-trivial problems but near chance on the same problems framed as spreadsheet edits.

Frontier models. Gemini 3.8 Flash, Claude Opus 5.5, GPT-6 Sol and GPT-6 Luna were asked to output the final value of every variable. All did well on r-trivial and aperiodic. On soluble and general finite, accuracy fell sharply with length, reaching 13% or lower on the longest general finite problems. The authors attribute this partly to sensitivity: at harder levels, many more steps affect the answer, so one missed update produces a wrong result.

Models trained from scratch. Six 275M models were trained: two transformers, two hybrids, and two Gated DeltaNet variants with different memory-update constraints. They trained on sequences of up to 256 assignments and were tested on up to 64,000, which is 250 times the training length. Gated DeltaNet and hybrids generalized almost perfectly on r-trivial, aperiodic and soluble out to tens of thousands of assignments. Transformers learned the easier levels but degraded with length, and never learned general finite. On general finite, the Gated DeltaNet variant with the more flexible memory update stayed near perfect to roughly 10 times training length. The authors conclude that for recurrent and hybrid models, the pretrained failures come from training data rather than architecture.

Limits

A new proof shows that Gated DeltaNet with non-negative eigenvalues solves all aperiodic tasks and some periodic ones, such as parity, under fixed-precision arithmetic with rounding. Whether it solves all soluble tasks is still open. The effects of numerical precision and of mixing it with attention are also unresolved. StateBench assumes a fixed set of variables, so it does not cover settings where new entities appear over time, as in long conversations. The post links a tech report, data and code, but gives no licence, dataset size or run commands.