acceptodds
Under review as a conference paper at ICLR 2027

A Fine-Grained Hierarchy and Benchmark for State Tracking in Language Models

Abstract

Theoretical limitations of transformers on state tracking—the ability to track information about entities or variables over long contexts—have motivated new recurrent language modeling (LM) architectures such as Gated DeltaNet (GDN). These architectures have, in particular, been benchmarked against the word problem, a theoretically hard state-tracking task that captures abilities such as code evaluation under arbitrary variable assignment. It, however, remains open whether other, simpler forms of state tracking might both be more relevant in practice and already explain observed differences between these architectures. We propose evaluating state tracking using a hierarchy of word problems with four increasing levels of difficulty: r-trivial, corresponding to immutable assignment to variables in programming; aperiodic, where assignments are mutable; soluble, where assignments are self-referential; and general finite state tracking. Theoretically, we show that the class of problems transformers are thought to length-generalize on does not even contain all aperiodic state tracking. On the other hand, we prove that GDN with positive eigenvalues expresses precisely the class of all aperiodic problems, and the regular languages recognized by certain transformers are precisely all soluble ones, thus providing a fine-grained picture of state tracking capabilities of various architectures. Taking these ideas to practice, we construct StateBench, a 4-tier long-horizon state-tracking benchmark. Our systematic direct training experiments across architectures largely align with theoretical expectation, albeit with interesting observations at very large scale length-generalization. Additionally, unlike prior work, we also evaluate pretrained models—both open hybrid and closed frontier ones—on StateBench, finding that none of them robustly solves even soluble state tracking, suggesting a direction for future improvement.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
state tracking, transformers, linear RNNs, GDN, expressivity, length generalization

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_QtK8OpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The paper describes several theoretical results on the state tracking capabilities of sequence models (transformers / gated delta-net), and it introduces a new state tracking benchmark along with performance results of the different models. Both the theoretical results and the benchmark are derived from the perspective of the Krohn-Rhodes theory, which studies the decomposition of finite state automatons into simpler ones. The authors argue that this perspective onto state tracking gives rise to a natural hierarchy of tasks, forming the basis for the theoretical results and benchmark.

Critical strengths

The paper is very informative and well-written, and I truly enjoyed diving into the rabbit hole of Krohn-Rhodes theory alongside reading the paper. I used to consider group structure as key aspect to consider in the context of studying state tracking, and this work made me rethink this (in favor of monoids, allowing for studying exactly the interplay between information-preserving and information-erasing structures).

Studying state tracking capabilities through the Krohn-Rhodes perspective seems to close a critical open gap in our understanding of what models can and cannot do.

Critical weaknesses

The paper could be more accessible. For example, it took me an effort to really appreciate the role of periodicity and presence/absence of non-trivial group structure in studying state tracking. This may be because I wasn’t familiar with Krohn-Rhodes theory. But I suspect many potential readers won’t be.

A high level criticism of the line of work studying representation capabilities of models could be that the question “what can a model do” may be less important in practice than the question “how well can a model efficiently learn“ (in terms of data efficiency, generalization, etc.). For example, the fact that certain variants of transformers are Turing-complete does not change the fact they can be extraordinarily hard to train to generalize on even simple tasks like Parity. I admit that this is a somewhat philosophical point though.

Questions for authors

The sensitivity analysis seems really interesting and would have been worth elaborating on more deeply in my opinion. Similarly, for the CruxEval experiments, as these help make the paper much more directly practically relevant.

There is no detailed mention of the experimental details, like the amount of training data, mentioned in the main text.

Small typo, line 130: “these types of monoids is in terms of”?

3 comments
AuthorsOpenReview ↗

Response to Reviewer QtK8

Thank you for your careful reading and thoughtful review of our work. We offer the following for your specific questions.

Accessibility. We sympathize with this point; if accepted, we will use the additional page of room to provide more intuition on how these algebraic concepts relate to the practical implications for data distributions, in particular about the role of periodicity.

Expressivity vs Learnability. We agree with this broad point. Two of our specific results highlight this contrast: first, the fact that sensitivity curricula help transformers, and second, the fact that GDN+-/Hybrid+- models fail at generalizing on general finite data despite being able to express it. We will more explicitly note that we hope these kinds of non-expressivity failures from our benchmark can be used to advance progress on learnability as well.

Typos. Thank you! This will be fixed.

Experimental Details. We will add the following details in an appendix. For all direct training experiments, we use 275m-parameter models trained from scratch. Models use the Dolma2 tokenizer. We train using the AdamW optimizer with values β1=0.9,β2=0.95\beta_1=0.9,\beta_2=0.95 with non-embedding weight decay of 0.10.1. Peak learning rate is ≈1.7×10−3\approx 1.7 \times 10^{-3}. We use a WSD-S schedule. Global batch size is ≈0.6M\approx 0.6M. We use a 1×1\times Chinchilla multiplier for data volume, which amounts to ≈5.5B\approx 5.5B tokens. For frontier models, we use generative scoring with a cap of ≈16k\approx 16k output tokens per request, inclusive of reasoning tokens; truncated replies, which happened only very infrequently, score as incorrect. We use the provider-default reasoning levels for each model, and evaluate 10 samples per length tier and complexity class.

In addition to these points, we have slightly revised our statement of Theorem 1:

Theorem 1. After submission, we realized that the upper bound of Aprd\mathsf{Aprd} on GDNf+\mathsf{GDN}^+_f that we cited in prior work depends on a particular choice of fixed-precision arithmetic. Prior work has largely assumed one specific fixed-precision model, but we think a slightly revised and generalized definition more accurately incorporates how rounding works in fixed-precision environments, and is a better model for GDNs as typically instantiated in practice. We have therefore revised Theorem 1 to GDNf+⊋Aprd\mathsf{GDN}^+_f \supsetneq \mathsf{Aprd} and exhibited a specific example of a GDN+ model that can solve a soluble problem, if one admits rounding. This change better accords with our experimental results, which showed GDN+ and Hybrid+ models generalize far better than would otherwise be predicted on the Soluble split of StateBench.

Expressivity vs Learnability: Personally, I believe expressivity analyses on their own will ultimately prove to be insufficient for characterizing what models are good at or able to do. It seems likely that there will be no way around incorportating insights from learning theory and thinking about inductive biases and generalization to gain any real insights.

That being said, I agree that results on expressivity help us understand the models better, and I stand by my rating (which is already 4).

Thank you again for reading our work and for giving helpful comments and critiques. We sincerely appreciate the time you have dedicated to reviewing our paper and helping improve it.

Reviewer_yqHsOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes to use an alternative hierarchy of word problems rather than the more commonly used S5 problem to benchmark sequence models. Moreover, they propose a synthetic dataset to benchmark sequence models experimentally. Finally, they evaluate pre-trained models, providing analysis on how each sequence model behaves on each task set.

Critical strengths

Fine-grained analysis of Fig. 3 is interesting. The sensitivity indeed seems like an important quantity to control, as otherwise a low-sensitivity task might hide the state tracking errors.

Critical weaknesses

The theoretical results are dense and beyond my expertise, so I did not check them. My comments below are based on the empirical results and the general theme of the paper.

It is known that the classes of problems GDN and transformers tackle are different from each other, e.g., https://arxiv.org/pdf/2604.03444. Is the goal of this paper to present an alternative hierarchy to classify those models? I don't understand the significance of this beyond the fact that it is just another way to do it.

In Fig. 7, how is the x-axis computed? This is not specified.

Can you have a table clearly showing which theorem predicts which experimental finding, so that it is easy to check whether theory indeed predicts the outcome? This will help parsing the dense theory part of the paper.

Questions for authors

See weaknesses.

2 comments
AuthorsOpenReview ↗

Response to yqHs

Thank you for your careful reading and thoughtful review of our work. In addition to the general points addressed in the broader response, here are our responses to your specific questions.

Significance beyond known separations. Our main contribution here is in refining the “easier” cases of state tracking and showing that there are separations here as well. Prior work (including 2604.03444 "Olmo Hybrid") has focused on the hardest kinds of state-tracking, with general finite monoids with S5-style word problems as a prototypical instantiation. While it’s known that GDN models are better than Transformers here, we note that there are many relevant kinds of state tracking that are easier than S5; furthermore, we find that Transformers and different kinds of GDN models have weaker upper bounds than just S5 vs not S5. Our hierarchy does not replace the S5 classification, but rather refines to to include more kinds of state-tracking. In addition to this broader theoretical classification, we also provide new theoretical results identifying new separations based on these complexity levels.

In other words, the Olmo Hybrid work demonstrates existence & focuses solely on the hardest cases of state tracking; here we look at easier variants that may be more common in practice and get a better qualitative sense of where separation actually occurs.

Fig 7 axis. The x-axis is sensitivity coverage, i.e., the fraction of variable-state pairs for which changing the value could affect the final output. This is the same metric reported in Fig. 4, and is calculated by directly measuring the proportion of states whose values are directly carried through to the output (for StateBench, this is done during sample generation; for CruxEval samples, we unroll each sample into loop-free forms and perform an analogous analysis). We will update the caption to clarify this.

Theory–Prediction Table. This is an excellent suggestion, and we will include the following summary:

ResultImplicationObservedAgrees?
SMAT_f = r-trivial; SMAT_m ⊊ AperiodicTransformers can't solve periodic tasksTransformers fail to length-generalizeYes¹
AHAT_ℓ ∩ Fin = Sol (assuming TC⁰ ≠ NC¹)No transformer solves general finiteTransformers fail, even in distributionYes
GDN⁺_f ⊋ AprdGDN⁺ can solve aperiodic and some soluble tasksPerfect on aperiodic; ≥93% on soluble to 23K assignmentsYes
GDN±_f = FinGDN± can represent every levelPerfect up to soluble; general finite holds to ≈10×Consistent¹
Periodic ⇔ Ω(n) sensitivityPeriodic tasks are harderAccuracy falls with sensitivity (Fig. 7)Yes

¹ Expressivity bounds what a model can learn but doesn't guarantee learning. For example, transformers can express r-trivial tasks yet fail to learn length-general solutions.

In addition to these points, we have slightly revised our statement of Theorem 1:

Theorem 1. After submission, we realized that the upper bound of Aprd\mathsf{Aprd} on GDNf+\mathsf{GDN}^+_f that we cited in prior work depends on a particular choice of fixed-precision arithmetic. Prior work has largely assumed one specific fixed-precision model, but we think a slightly revised and generalized definition more accurately incorporates how rounding works in fixed-precision environments, and is a better model for GDNs as typically instantiated in practice. We have therefore revised Theorem 1 to GDNf+⊋Aprd\mathsf{GDN}^+_f \supsetneq \mathsf{Aprd} and exhibited a specific example of a GDN+ model that can solve a soluble problem, if one admits rounding. This change better accords with our experimental results, which showed GDN+ and Hybrid+ models generalize far better than would otherwise be predicted on the Soluble split of StateBench.

Thank you again for reading our work and for giving helpful comments and critiques. As the author–reviewer discussion period is ending soon, we want to ask if our response to your review has adequately addressed your questions, or if not if there is any additional information we can provide to help you evaluate our work.

Thank you for your time!

Reviewer_6CsSOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper organizes finite-state tracking into four levels, from immutable assignments to unrestricted finite-state updates. It uses this hierarchy to characterize the capabilities of transformer and Gated DeltaNet variants, then introduces StateBench to test them. Experiments test diverse settings and show substantial differences across architectures, sequence lengths, and input formats.

Critical strengths
  • Evaluating only a difficult permutation task can hide meaningful differences on simpler forms of state tracking. The four levels provide a thorough analysis of model capabilities.
  • The benchmark design supports controlled comparisons.
  • The evaluation covers both learning and existing capabilities.
Critical weaknesses
  • In Lemma 1(a), constant attention values cannot detect whether a zero occurs. In Lemma 1(b), setting α\alpha to zero discards the previous state rather than preserving it.
  • The main text describes computing the full product, while footnote 4 asks only whether it equals the identity. These differ for general monoids, including the paper’s flip-flop example. The language-class claims need a consistent formulation.
  • The experiments perturb variable values during execution, whereas the cited result concerns sensitivity to changes in the input. The paper should establish the connection before using the CruxEval measurements as evidence of periodic state tracking.
  • The experimental setup is insufficiently specified. The supplied paper does not report optimizer settings, learning rates, or frontier reasoning and output budgets.
  • As per Figure 3, transformers fail to generalize beyond training, while the text reports roughly 10x generalization for RoPE models on some tasks. The positive and negative GDN variants are also difficult to distinguish where their curves overlap. More precise captions and distinct line styles would help.

The hierarchy and benchmark are useful, but the proof errors, inconsistent problem definition, and missing experimental details need to be addressed. If fixed rigorously, I will consider changing my assessment.

Questions for authors

Please see the weaknesses above

5 comments
AuthorsOpenReview ↗

Response to 6CsS

Thank you for your careful reading and thoughtful review of our work. Here are our responses to your specific points.

Lemma 1(a). Thank you for the observation. The value should be set to 1 if the token is zero, and zero otherwise (that is, letting the key equal the value).

Lemma 1(b). Thank you for catching this. This is a typo; α\alpha is supposed to be 1. We have updated the proof to let βt=0\beta_t = 0, which correctly recovers the identity. βt=kt=1\beta_t = k_t = 1, on the other hand, captures overwriting the state with aa or bb.

Full product vs Identity. These are equivalent definitions in our case. The full product captures the functional variant of a computation, while the “=1” version lets us talk about the corresponding decision problem or language class. Our results apply to both variants. For instance, Lemma 1(b) says that GDNf+GDN^+_f can implement partial products w1w2…wiw_1 w_2 \ldots w_i of elements of the monoid U2U_2, and also that the language class recognized by GDNf+GDN^+_f contains the language of all words over U2U_2 whose product equals 1. We will clarify this.

Sensitivity. We believe these formulations are equivalent in our cases; the inputs are the sequences of assignments, whereas the output is the final state; similarly, for the code data, we take as input to the problem an unrolled method (itself with a fixed input) and consider perturbations to its internal state (which manifest as a series of variable-value assignments) as input to the state tracking problem. Does this clarify the position?

Experimental details. This is a very valid request; we will add the following details in an appendix. For all direct training experiments, we use 275m-parameter models trained from scratch. Models use the Dolma2 tokenizer. We train using the AdamW optimizer with values β1=0.9,β2=0.95\beta_1=0.9,\beta_2=0.95 with non-embedding weight decay of 0.10.1. Peak learning rate is ≈1.7×10−3\approx 1.7 \times 10^{-3}. We use a WSD-S schedule. Global batch size is ≈0.6M\approx 0.6M. We use a 1×1\times Chinchilla multiplier for data volume, which amounts to ≈5.5B\approx 5.5B tokens. For frontier models, we use generative scoring with a cap of ≈16k\approx 16k output tokens per request, inclusive of reasoning tokens; truncated replies, which happened only very infrequently, score as incorrect. We use the provider-default reasoning levels for each model, and evaluate 10 samples per length tier and complexity class.

Fig 3. We will update the caption/text to clarify that we see partial generalization of Transformer-RoPE models above the generalization of Transformer-NoPE models. We will also use distinct line styles to distinguish between ++ and ±\pm variants to make the line series clearer.

In addition to these points, we have slightly revised our statement of Theorem 1:

Theorem 1. After submission, we realized that the upper bound of Aprd\mathsf{Aprd} on GDNf+\mathsf{GDN}^+_f that we cited in prior work depends on a particular choice of fixed-precision arithmetic. Prior work has largely assumed one specific fixed-precision model, but we think a slightly revised and generalized definition more accurately incorporates how rounding works in fixed-precision environments, and is a better model for GDNs as typically instantiated in practice. We have therefore revised Theorem 1 to GDNf+⊋Aprd\mathsf{GDN}^+_f \supsetneq \mathsf{Aprd} and exhibited a specific example of a GDN+ model that can solve a soluble problem, if one admits rounding. This change better accords with our experimental results, which showed GDN+ and Hybrid+ models generalize far better than would otherwise be predicted on the Soluble split of StateBench.

Thank you again for reading our work and for giving helpful comments and critiques. As the author–reviewer discussion period is ending soon, we want to ask if our response to your review has adequately addressed your questions, or if not if there is any additional information we can provide to help you evaluate our work.

Thank you for your time!

Thank you for the rebuttal. The clarifications are helpful, but three concerns remain:

  1. Lemma 1(a): How is exact zero detection achieved with fixed-precision softmax as sequence length grows?
  2. How do the results extend from identity testing to full matrix multiplication?
  3. Theorem 1: Could you provide the revised proof and arithmetic assumptions supporting strict inclusion?

The CruxEval interpretation also remains somewhat heuristic. Given these unresolved concerns, I am maintaining my score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.