WorksComputer Science
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 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, 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.
Introduction
Tracking the state of the world across a long context is necessary for understanding discourse, documents, and code ([14, 18, 12]). Prior work has examined the difficulty of state-tracking tasks by viewing them as equivalent to word problems for finite monoids, and relating the algebraic properties of these structures to their computability by various neural architectures ([22, 27]). While much focus has been given to the hardest class of state-tracking problems, such as the word problem, less attention has been given to intermediate levels of problem difficulty, which may prove more representative of the kinds of real-world state-tracking tasks language models are expected to solve and might already explain observed performance differences across architectures.
To better understand finegrained state-tracking differences between architectures, we propose evaluating state tracking capabilities across four hierarchical levels naturally motivated by the classical Krohn–Rhodes decomposition for finite monoids ([19]): general finite, involving arbitrary transpositions of variables; soluble, involving variable assignment by self-reference; aperiodic, involving the reassignment of variables to new values; and r-trivial, involving constant registers which can only be written to once. We then evaluate the theoretical expressivity and empirical performance of various language model architectures across levels of this hierarchy.
We first theoretically explore the ability of Transformers {(citep}(Vaswani et al., 2017)} and Gated DeltaNet (GDN; Yang et al. 2024) models to represent state tracking problems across this hierarchy and the role of particular hyperparameters. Complementing existing results relating low-precision softmax transformers to r-trivial and aperiodic state tracking {(citep}(Li & Cotterell, 2026; Yang et al., 2025)}, we show that the state tracking problems expressible by log-precision averaging hard-attention transformers, a well-studied theoretical model, are exactly the soluble ones. Next, whereas GDN with an extended eigenvalue spectrum can represent all state tracking tasks, we characterize the state tracking capabilities of GDN with positive eigenvalues as containing all aperiodic monoids and even some periodic (soluble) ones. Synthesizing prior work and our new results reveals finegrained distinctions between the theoretical state tracking capabilities of transformers and GDN, as well as the role of precision and parameterization details on the state tracking expectations for each architecture.
Motivated by these theoretical results, we introduce StateBench, a long-context evaluation benchmark with state-tracking problems at varying levels of complexity and supporting evaluation of very large scale length-generalization (up to 64K state changes). We evaluate models trained directly on StateBench data, showing that models containing recurrent modules length-generalize fully on r-trivial, aperiodic, and soluble data and show limited generalization on general finite data, while transformers fail to generalize on r-trivial data and fail to learn even in-distribution general finite data. Surprisingly given prior work {(citep}(Grazzi et al., 2025)}, we find that recurrent models with non-negative eigenvalues succeed on StateBench’s soluble state tracking tasks, which we explore theoretically in Theorem 1. On open-source pretrained models including two Olmo 3 7B variants, we find that all architectures do well on r-trivial data, degrade meaningfully on aperiodic data, and fail completely on general finite data. We find that a variety of frontier proprietary Gemini, Claude, and GPT LLMs can solve r-trivial and aperiodic tasks well but exhibit strong degradation on soluble and general finite state tracking tasks as a function of sequence length, dropping to near-zero performance on the hardest problems in StateBench. Lastly, we contextualize these results by connecting monoid periodicity to the sensitivity of boolean functions, showing that proper understanding of many tasks involving real-world source code requires state-tracking capabilities beyond the expressivity and learned capacity of current language models.
A Hierarchy of Finite State Tracking
To analyze the difficulty of state-tracking problems and connect their solvability to neural architectures, we construct a formal model of them based on an algebraic object known as a (finite) monoid, defined as a triple of some (finite) set , a composition operation , and a neutral identity element . Prior work has noted that monoids are a natural model of state tracking by means of their composition operator {(citep}(Liu et al., 2023; Merrill et al., 2024; Nowak et al., 2026a,b; inter alia)}. A word over is a string of elements of concatenated together, representing the composition . Intuitively, represents a sequence of updates to a system: given some initial state , observing moves the system to state ; observing moves it to ; so forth. Since is closed under composition, the word is itself an element of ; computing exactly which element is known as the word problem1 on .
We will formalize different levels of complexity for state tracking in terms of word problems for different types of monoids. A useful source of intuition for this will be the different kinds of variable state manipulation that are possible in programming. We can distinguish between four kinds of state updates: (i) immutable writes, such as defining a constant value like let x = 4; (ii) mutable writes, such a (re)defining a variable value like var x = 4; ... x = 2; (iii) self-referential writes, such as incrementing a variable like var x = 4; x += 3; and (iv) referential writes, such as swapping two variables like var x = 4; var y = 2; (x,y) = (y,x).
By modeling state-tracking as a word problem on a finite monoid, we can relate these various kinds of state update operations to the algebraic structure of the monoid and use this to understand the computational difficulty of tracking the state-space—calculating the value of the system after observing an arbitrary sequence of updates. The well-known eponymous theorem of Krohn & Rhodes [19] establishes that every finite monoid can be decomposed into the iterated wreath product, denoted , of finitely-many irreducible factors, loosely analogous to a (non-unique) prime factorization.1 Each irreducible factor in this decomposition is either the two-element semilattice where , corresponding to immutable writes; the “flip-flop” monoid where for , corresponding to mutable writes by value; the commutative group of integers modulo for some prime , corresponding to self-referential writes; or a non-commutative finite simple group, corresponding to referential writes.
Different kinds of state tracking can be formalized based on the kinds of finite monoids they represent. A finite monoid is called (i) r-trivial if for all , implies [8]; (ii) aperiodic if for every there is some with [37]; and (iii) soluble if every subgroup of is soluble [4]. For our purposes, however, a more useful and equivalent characterization of these types of monoids is terms of the kinds of core operations that appear in their Krohn–Rhodes (KR) decomposition:
Proposition 1 (Monoid types, informal; cf. §A for a formal statement). A finite monoid with KR decomposition is (i) r-trivial if every is ; (ii) aperiodic if every is ;2 and (iii) soluble if every is either or for some prime .
As illustrated in Figure 1, these classes form a nested hierarchy: , where Rtrv is the class of word problem languages3 whose monoid is r-trivial, Aprd is the class for aperiodic monoids, Sol is the class for soluble, and Fin contains all word problem languages on finite monoids including . Thus, Rtrv can be understood as a generalized class of all state tracking involving only immutable writes, Aprd as a natural class of state tracking problems involving only writes “by value”, Sol as a harder class of state tracking where interaction between variables is limited, and Fin as the class of unconstrained finite state tracking problems.

Figure 1. Placement of various language model architectures within the hierarchy of state-tracking (monoid word problem) complexity, along with examples of the kinds of tasks that fall into these categories. Areas below the long horizontal line indicate circuit complexity classes that, when restricted to regular languages, are equal to the monoid classes above them. The two log-precision architectures extend into . Dashed lines represent conjectured strict boundaries between classes.
Correspondence to Formal Language, Logic, and Circuit Complexity Classes. In addition to having intuitive interpretations in terms of variable assignments, these levels within the state tracking hierarchy coincide with other notable classes of problems. From a formal language theory perspective, Fin is exactly the class of regular languages, and Aprd is exactly the class of star-free languages [37]. From a logical perspective, Fin = MSO, the languages definable in monadic second-order logic [5], whereas Aprd = FO[] = LTL: it corresponds to the languages definable in first-order logic [23] or, equivalently, linear temporal logic [15]. Sol = FO[] + MOD, the languages definable in first-order logic augmented with modular predicates (Tesson & Thérien, 2007), and Rtrv = LTL[past], the languages definable in the restricted past fragment of FO[] or LTL [20, 13].
Finally, from a circuit complexity perspective, Aprd corresponds to the regular languages in [31 Theorem 3], Fin to the regular languages in (all of them), and Sol to the regular languages in as well as those in , assuming (Mix Barrington et al. [ [31], Theorem 8). The convergence of these classes with other areas suggests the hierarchy reflects fundamental distinctions in state tracking capabilities relevant across computational models.
Expressivity of Architectures for State Tracking
We now explore the state tracking abilities of various transformer and recurrent architectures, in relation to our state tracking hierarchy. Our goal is to characterize models based on whether or not they can express a length-general solution to the word problem for the particular class.
Transformers and GDN. We adopt the formal model of Merrill et al. [28] and Merrill [26]; see § A.2 for formal definitions. Each architecture uses a stack of layers, interleaving tokenwise feedforward sublayers with sequence-mixing sublayers that are defined as follows:
Softmax attention (SMAT): the standard causally-masked attention of Vaswani et al. (2017), where token outputs .
Averaging hard attention (AHAT): an idealization in which token attends uniformly to tied positions that maximize and averages their values (Pérez et al. [35]).
Gated DeltaNet (GDN) (Yang et al. (2024)): a linear recurrence over a matrix-valued state,
with gate and write strength . The eigenvalues of the transition are and . Following Grazzi et al. [7], we write when (nonnegative eigenvalues) and when (eigenvalues in ).
Arithmetic Precision. The expressive power of these models is well-known to depend on the numerical precision of the network’s activations. Following Merrill et al. [28], we distinguish fixed precision (; a fixed number of bits w.r.t. input length ), log precision (; bits, enough to represent positions and uniform averages over the context), and mixed precision (; fixed precision everywhere except inside attention aggregation, as in Yang et al. (2025)). Our fixed-precision analysis uses a fixed-precision, fixed-point overflow datatype, , defined in § A.4. Informally, it represents numbers in the form where is a fixed positive denominator that controls the rounding behavior, and is either an integer in the range or a special overflow value . We write, e.g., and for the classes of languages recognized by fixed-precision SMATs and GDNs, respectively. Throughout, we say an architecture solves the word problem over if a single model in that architecture computes the correct output for every word over .
Known expressivity results
Transformers. We first review some known results relating softmax transformers (SMAT) to different levels in the state tracking hierarchy, parameterized by different levels of precision (finite , mixed , or log ). First, Li & Cotterell [20] and Jerad et al. [13] showed , i.e., fixed-precision SMAT solves precisely the word problem over -trivial monoids. Second, Yang et al. (2026) showed that the language C-RASP, often used as an abstraction of transformers, is equivalent to the wreath product closure of bounded-depth Dyck languages, which is a strict subset of aperiodic. C-RASP is known to be equivalent to mixed-precision SMATs (Yang et al. 2025). It follows that , i.e., only for a strict subset of aperiodic monoids can mixed-precision transformers solve the word problem over . Thus, while going from finite precision to mixed precision increases SMAT expressivity above Rtrv, mixed-precision SMATs remain properly within Aprd. Third, even in the log-precision regime, both SMAT and AHAT are known to be in the circuit class uniform (Merrill & Sabharwal 2023). Moreover, under the circuit complexity assumption , the regular languages in are exactly (Mix Barrington et al. [ [31], Theorem 8). Thus, assuming , we have both and . Overall, while more precision may increase the state tracking capabilities of SMAT, they remain within Sol, and it remains unknown whether they fully realize Sol.
GDN. Beyond transformers, we consider some partial results about GDNs. Sarrof et al. [36] derived an upper bound of (word problems over) aperiodic monoids for diagonal RNNs with non-negative eigenvalues. Grazzi et al. [7] showed GDN cannot represent certain periodic languages like , but they assumed exact arithmetic, in contrast to our fixed-precision arithmetic model that allows rounding. Merrill et al. [28] show GDN, i.e., for any finite monoid, there exists a fixed-precision GDN (with both positive and negative eigenvalues) that solves the word problem over it.6 It is worth noting that this captures the full gamut of finite state tracking problems, implying, in particular, that hybridization of fixed-precision GDN with SMAT or AHAT does not further increase the architecture’s expressivity for state tracking.
New results leveraging Krohn–Rhodes decomposition
We now leverage the Krohn–Rhodes view of state tracking to derive several new results placing transformer and GDN variants at various levels of the state-tracking hierarchy. These results help relate the state tracking capabilities of the two different architectures and elucidate the role of key parameters like precision and attention type for state tracking. Proofs are deferred to §B throughout.
The following lemma provides the foundation for our formal results, identifying the “building block” monoids (, , and ) that various architectures can implement. Here, “implement” means that given a one-hot representation of a monoid element in the input-layer hidden state at token , there will be a subspace of the representation of token in the final layer that encodes the partial product as a one-hot vector.
Lemma 1 (Implementing Basic Monoids). Various attention and recurrent mechanisms can solve various basic finite monoid word problems, as follows:
a. There exists a one layer SMAT that implements .
b. There exists a one layer GDN that implements .
c. There exists a one layer AHAT that implements .
d. For any prime , there exists an 8-layer AHAT that implements .
Lemma 1 shows that for each basic monoid, there is a block of layers of various types of architectures that can be used as a gadget to implement that monoid. Moreover, the iterated wreath product of basic monoids can be implemented by a depth-wise composition of the corresponding gadgets:
Lemma 2 (Implementing Monoid Composition). Let be a finite monoid with a KR decomposition . Suppose that for each , an attention-based or recurrent architecture of depth can implement compositionally with its own datatype. Let . Then the depth- composition of the architectures implements .
Armed with these lemmas, we are ready to state our main technical findings, in which refers to a finite monoid. Our first result shows that GDN can solve all aperiodic monoid word problems, and even some periodic (soluble) ones:
Theorem 1 (GDN). For any aperiodic and for some periodic but soluble , there exists a fixed-precision GDN that solves the word problem over .
Our proof leverages the fact that aperiodic monoids can be decomposed into flip-flops, implying via Lemma 1.b that GDN can solve all of Aprd. Specifically, for any aperiodic monoid that has a KR decomposition with basic monoids, our lower bound (Lemma 4 in §B) constructs a fixed-precision GDN of depth . Our result holds for (ungated) DeltaNet in addition to GDN, but we state it with the more common GDN acronym. To prove that this lower bound is not tight, we construct a fixed-precision GDN that recognizes the periodic language :
Lemma 3. There exists a GDN that recognizes under datatype for all large enough .
This appears to contradict Theorem 1 of Grazzi et al. [7], which states that no linear RNN with non-negative eigenvalues can recognize parity. The rectification is that their result assumes exact, unrounded multiplication. In contrast, Lemma 3 depends critically on rounding (specifically in the computation of and ) to achieve periodic behavior. Moreover, we show (Lemma 5 in §B) that general linear RNNs with non-negative eigenvalues can, in fact, recognize certain periodic languages even under exact arithmetic, and that this extends even to if the matrices are parameterized as products of matrices with non-negative eigenvalues (Corollary 2 in §B), similar to DeltaProduct ((Siems et al., 2025)).
Next, we leverage Krohn–Rhodes in a similar way to obtain a lower bound on log-precision AHAT:7
Theorem 2 (AHAT Sol). For any soluble , there exists a log-precision AHAT that solves the word problem over .
As discussed in § 3.1, assuming , AHAT Fin Sol. Since Sol Fin, Theorem 2 implies that, under this circuit complexity assumption, AHAT Fin is precisely Sol, i.e., the regular languages recognized by log-precision AHAT are exactly those whose underlying monoid is soluble:
Corollary 1 (AHAT Fin Sol). Assuming , AHAT Fin = Sol, i.e., there exists a log-precision AHAT that solves the word problem for if and only if is soluble.
A picture of architectures’ relative state tracking capabilities emerges from these results. For GDN, these capabilities are controlled by the eigenvalues, not gating: GDN is limited to aperiodic problems while GDN covers all finite monoids. On the other hand, AHAT with log precision sits in-between, solving word problems over soluble monoids. For SMAT, precision controls expressivity, with mixed- and fixed-precision transformers corresponding to proper subclasses of aperiodic. The exact expressivity of log-precision SMAT or GDN on state tracking problems remains open.
Another interesting open question is: Could a GDN based hybrid model, possibly under higher precision, solve word problems over soluble monoids? Krohn–Rhodes theory lets us derive a conditional result. For any prime , suppose we have an architecture GM (a mod gadget) that, given a number (represented as or layer-norm hash ; [25]) as input, can compute a representation of . Proposition 2 (cf. §B) leverages KR decompositions to show that a hybrid model consisting of this gadget, along with GDN and SMAT, covers all soluble monoids. It remains open whether GDN with mixed- or log-precision is contained in aperiodic or, on the other hand, can implement the mod operation; if it’s the latter, Proposition 2 shows that hybrid GDN models would capture all soluble monoids.
The StateBench Dataset
To evaluate how well language models can learn and solve state-tracking problems we introduce StateBench, a new benchmark of synthetic state-tracking data that can be used to generate training and evaluation samples at targeted levels of algebraic complexity. Each StateBench problem is a monoid word problem over variables, initialized to starting values and updated with assignments. Assignments may be transpositions which swap two variables (finite), self-increment (soluble), reassignments by value (aperiodic), or constant assignments (r-trivial; see Figure 1). Each sequence is paired with one correct and four incorrect candidate final states (Figure 2), supporting use as both a generative and a multiple-choice evaluation.
Figure 2. left: A visualization of an 8-assignment general finite sequence with variables. Each variable is assigned an initial value (e.g., , ). At step , a variable may be overwritten by a new constant value (as in at ) or it may be swapped with another (as and are swapped between and ). right: Five possible final states for the sequence, with the correct one () annotated with a green star.
We first generate a general finite state tracking sample that mixes assignments-by-reference (, implemented with a temporary variable) with aperiodic assignments-by-value to a new constant value. For each sample, the number of aperiodic assignments is drawn log-uniformly from . From this general finite state tracking source task, we derive a soluble sample by replacing all assignments-by-reference with the equivalent self-increment value (, for some max value ), an aperiodic sample by replacing it with the value it would have copied (), and an r-trivial sample by replacing every assignment with the variable’s initial value (). Deriving all four from one source controls for the number of variables, the number of distinct values, and the positions of assignments across complexity levels.
We create a static evaluation set containing r-trivial, aperiodic, soluble, and finite samples with 8 to 64,000 assignments. Each sample is annotated with its complexity class, , , sensitivity, and length in Olmo-3 tokens; see Table 1 in §D. Since pretrained models may be sensitive to surface form, each sample is rendered in six textual formats that share the same underlying algebraic structure (§C).
| Monoid Complexity Class | ||||
| Max. dependency length (K) | R-trivial | Aperiodic | Soluble | General finite |
| 0 | 0 | 21.3 | 32.1 | |
| Sensitivity | 0.08 | 0.08 | 0.76 | 0.75 |
| [0.00–0.91] | [0.00–0.91] | [0.06–1.00] | [0.04–1.00] | |
| Prompt tokens (K) | 1.16 | 1.16 | 1.34 | 1.25 |
| [0.07–981] | [0.07–981] | [0.09–768] | [0.06–939] | |
| Shared across classes | ||||
| Samples per condition | 2,720 | |||
| Variables () | 2, 4, 8, 16 | |||
| Assignments () | 49 [11–64K] |
Table 1. Descriptive statistics for StateBench. Cells give medians, with [min, max] ranges in grey below. Token counts and dependency lengths are in thousands.
Directly-Trained Model Evaluations
We first validate our theoretical placement of various language model architectures on the state-tracking hierarchy by training models directly on data from StateBench and evaluating their ability to generalize to longer sequences. We consider six architectures: Transformers (Vaswani et al. (2017)) with rotary position embedding (RoPE; Su et al. (2021)) and without any positional embedding (NoPE; Wang et al. (2024)); Gated DeltaNet (GDN; Yang et al. (2024)) with only positive eigenvalues (+) and with both positive and negative eigenvalues (±); and Transformer-NoPE–GDN hybrid models with only positive eigenvalues (+) and both positive and negative eigenvalues (±) eigenvalues (Merrill et al. [29]). For each architecture we randomly initialize 275M-parameter models and train them with a language modeling objective on sequences of a StateBench prefix and its valid completion. We train each model on 1× the compute-optimal amount of data for pretraining following the “Chinchilla” methodology of Hoffmann et al. [11]. We consider two aspects of performance: first, whether models are able to learn the task sufficiently well to attain near-ceiling performance on in-distribution numbers of assignments; and second, whether the models are able to generalize to longer sequences with larger . We train models with between 8 and 256, and evaluate them on sequences with up to 64,000 (i.e., 250× longer), looking in particular at generalization up to 4× the training length as well as all the way to 64,000.
Figure 3 shows that language model architectures show clear differences in their ability to learn state tracking at in-distribution lengths as well as to generalize to longer sequences. Transformers learn in-distribution r-trivial and aperiodic data well but do not generalize perfectly beyond the training distribution; NoPE models degrade immediately beyond the training cutoff, while RoPE models generalize to roughly 10× the training length before degrading. On general finite data, transformers do not even completely learn the in-distribution data. GDN models generalize perfectly on r-trivial, aperiodic, and soluble data. They also perfectly learn the training distribution for general finite data but fail to generalize perfectly beyond the training cutoff: GDN± models generalize to roughly 10× the training lengths, whereas GDN+ models degrade immediately beyond the training cutoff. Hybrid models pattern like their GDN components, generalizing near-perfectly on r-trivial, aperiodic, and soluble data; Hybrid± models generalize longer than Hybrid+ ones on general finite data.
Figure 3. Direct Training: GDNs generalize perfectly on r-trivial, aperiodic, and soluble data, and partially on general finite data; Transformers fail to generalize beyond their training distribution on r-trivial, aperiodic, and soluble data and fail to even learn in-distribution general finite data. Error bars show Wilson confidence intervals.
Sensitivity makes tracking state harder. To interpret models’ lackluster performance on general finite problems, we draw a connection between the periodicity of samples and their sensitivity, a well-studied complexity measure that describes how much perturbations in a function’s input affect its output. Theoretically, monoid word problems have sensitivity if they are aperiodic and otherwise ([1 Remark C.2]). In other words, a state tracking problem is highly sensitive if and only if the underlying monoid is periodic.
We first measure the sensitivity of our derived evaluation samples and compare it to that of samples from real-world code evaluation data from CruxEval ([9]), a code-understanding benchmark of Python methods paired with canonical inputs and their expected outputs. In both cases, we measure sensitivity by calculating at how many steps during a program’s execution modifying a variable’s value could affect the final output.8 As Figure 4 shows, r-trivial and aperiodic data has low average sensitivity, while soluble and general finite sequences are far more sensitive, validating that they truly reflect periodic state tracking. Code samples from CruxEval show a split distribution, with peaks at very high and very low sensitivities and a smoother distribution of sensitivities in the middle. Due to the correspondence between sensitivity and periodicity, this suggests periodic state tracking is important for evaluating natural code.
Figure 4. Sensitivity Analysis: Histograms of sample sensitivities in (left) the four complexity distributions in StateBench and (right) code samples from CruxEval.
We next compare performance on general finite problems with per-sample sensitivity, finding a clear negative relationship: even among models that can learn general finite data in-distribution, samples with higher sensitivity are harder (cf. Figure 7 in § D). This is aligned with prior observations that highly-sensitive functions are difficult for Transformers to learn ([10]). A data curriculum may aid learning sensitive state tracking problems ([3, 16] (Siems et al. 2026)). To test if this helps for our models, we compare the results of training on randomly-shuffled general finite sequences to the same training distribution ordered by ascending sensitivity. We find, however, that this has negligible effects on GDN and Hybrid models and on Transformers with NoPE (cf. Figure 8 in § D), and only a weak positive effect on Transformers with RoPE on in-distribution general finite sequences.
Figure 7. Effect of Sensitivity: On general finite state tracking data, direct trained models perform worse on higher sensitivity data. Error bars show Wilson confidence intervals.
Figure 8. Curriculum Training: Sorting general finite sequences by sensitivity during training (right) boosts direct training performance of Transformer-RoPE models on in-distribution data compared to training on the same randomly-shuffled sequences (left, repeated); Transformer-NoPE, GDN, and Hybrid models are unaffected. Error bars show Wilson confidence intervals.
Pretrained Model Evaluations
To measure how well language models solve state-tracking at differing levels of complexity without task-specific training, we also evaluate a suite of pretrained models on StateBench. We study two 7B parameter models: Olmo-3 ((Team Olmo et al., 2025)), a Transformer-NoPE model; and Olmo-3-Hybrid ([29]), a Hybrid model, both pretrained, midtrained, and extended for long context on the Dolma dataset ((Soldaini et al., 2024)). We also study a family of smaller, custom pretrained models trained on the same dataset, at two size classes: 275M parameters (Transformer-NoPE, GDN, and Hybrid); and 2.7B parameters (Hybrid). Pretraining and midtraining data were capped at 8K tokens for all models, while long-context data was capped at 64K.
Since pre-trained models are frequently meant to be ‘task-agnostic’ tools, evaluating on one particular formatting may bias results or make them unreflective of general state-tracking performance. To account for this, we generate six different sequence formats for all evaluation samples, including integer code, spreadsheet cell filling, and cube painting (cf. § C for details and examples). We include sequences of lengths up to 128K to test how well models can perform on sequences with lengths seen during pretraining (first vertical green line in the plots), seen only during long-context extension (second vertical green line), and longer than have been seen at all during training.
Pretrained models underperform at tracking state. We evaluate models on all six different sequence formats, and report in Figure 5 the maximum value obtained by the model on any of those formats. Pretrained models consistently under-perform relative to theory and direct training. All models perform quite well on the r-trivial tasks except for the 275M-parameter transformer, which falls to at-chance accuracy beyond the pretraining length distribution. On aperiodic data, all models underperform expectations. The 7B models attain only accuracy, and all models exhibit some degree of performance degradation within the pretraining length window, and noticeably drop afterwards. Some models, particularly the 275M GDN model, manage to maintain accuracy of beyond the long-context cutoff, but no higher. On general finite data, all models perform at-chance for all sequence lengths. In general, we find that Krohn–Rhodes complexity, sample length, and model size are the dominant factors impacting accuracy.
Figure 5. Pretrained models underperform theoretical expectations and direct-training results, showing consistent performance degradation on aperiodic data and completely failing on general finite data. Error bars show Wilson confidence intervals.
Models are sensitive to problem formatting. We find models exhibit a strong preference for some task formats over others (cf. Figure 9 and Figure 10 in §D). Data formatted like sequences from RULER ([12]) are much easier for models than the exact same sequences formatted like manipulations of named spreadsheet cells. This is especially true for small models, which attain near-ceiling performance on RULER-formatted r-trivial data but are near-chance on spreadsheet-formatted data, but even 7B-parameter models also generalize better to longer sequences when they are formatted like RULER tasks. RULER-formatted samples also have lower aggregate variance. This suggests that pretrained models are strongly affected by the particular choice of formatting for state-tracking tasks, and hence that evaluations of state-tracking capabilities in pretrained models should take care to measure performance across a variety of different formats.
Figure 9. Pretrained base models perform better on RULER-formatted StateBench sequences (top) than on the same sequences formatted as spreadsheet manipulations (bottom). Error bars show Wilson confidence intervals.
Figure 10. Pretrained models evaluated on StateBench problems by complexity class and formatting. Error bars show Wilson confidence intervals.
Frontier models struggle on long-horizon hard state tracking. We also run StateBench evaluations on four recently-released, proprietary frontier models: Gemini 3.8 Flash ([6]), Claude Opus 5.5 ([2]), and GPT-6 Sol and Luna ([34]). We evaluate these models in a generative setting, where they are asked to produce the final state of the system instead of choose among 5 possible answers. As shown in Figure 6, all frontier models show strong performance on r-trivial and aperiodic problems; however, they fall to at-chance accuracy on soluble and finite state-tracking problems when inputs reach between 10K–64K tokens. The diminished performance of frontier reasoning LLMs shows that there is substantial headroom for improvement on generalizing on sensitive state-tracking problems.
Figure 6. Frontier LLMs struggle on long-horizon soluble and general finite state-tracking tasks. Error bars show Wilson confidence intervals.
Conclusion
We introduce a hierarchy of state tracking based on the Krohn–Rhodes decomposition of finite monoids, classifying problems as -trivial, aperiodic, soluble, and general. We place various models of Transformers and Recurrent architectures within this hierarchy, showing the kinds of state-tracking tasks they can express length-general solutions to. We validate these results by constructing StateBench, a benchmark of state-tracking problems, and evaluate directly-trained, pretrained, and frontier language models on it. Our empirical findings support our theoretical results and highlighting the headroom left for language models to improve on state-tracking tasks.
One surprising takeaway from our empirical findings and novel theoretical results is that with non-negative eigenvalues is capable of certain kinds of periodic state tracking, which is notable given prior work (cf. Grazzi et al., [7]). Several questions remain open. First, we do not know the exact placement of in the hierarchy. It would be interesting to understand better understand the relation of to soluble state tracking, as well as the impact of numerical precision or hybridization with attention layers. Extending the hierarchy beyond finite monoids, i.e., to unboundedly-many variables, would bring many practical state-tracking tasks within the same framework, such as arbitrary discourse tracking. Empirically, our sensitivity analysis of code data suggests that general finite state tracking matters for code understanding, but where periodicity arises in natural data more broadly, and how much it drives the gaps between architectures in practice, remains an open question.
AI Use Statement
The numerical constructions in Lemmas 3 and 5 were developed interactively using Claude Opus 5.5 High and Gemini 3.6 Flash. We used generative AI tools for code generation, including to help write the library used to generate state-tracking data and to help write plotting code used to generate figures. We also used generative AI tools to offer critiques on drafts of this paper and offer phrasing suggestions. We have not used generative AI to generate evaluation data directly, nor to directly generate any figures present in this paper.
We have reviewed all AI-assisted work through manual review. We take responsibility for the final content of this work, including text, claims, or artifacts produced with the aid of generative AI.
Reproducibility Statement
For all formal results, we include detailed definitions and proofs in §§ A and B. For all empirical results, we provide a more detailed overview in §§ C and D. We will publicly release all data, code, and experimental setup conditions needed to reproduce our results in full.
Formal Definitions
Monoids and Krohn–Rhodes
Definition 1 (Finite Monoid). A monoid is a tuple of a set , an associative binary relation , and an identity element $1 for all . We say that a monoid is finite if is finite.
Definition 2 (Word Problem). Let be a monoid, and let be a word in , i.e., a composition of finitely many elements . Since is closed under , this composition is in as well. The word problem on is to determine the identity of .
Definition 3 (Monoid Division). For monoids , , we say that divides , written , if there exists a submonoid and a surjective homomorphism .
Definition 4 (Wreath Product). For finite monoids , their wreath product is the set of pairs , where is a map from to and , under the composition
with identity , where for all .
Intuitively, is a cascade in which processes an input and processes the input according to ’s current state.
Definition 5 (Irreducibility). A finite monoid is irreducible if implies that or for all finite monoids , .
Theorem 3 [19]. Let be a finite monoid. Then there exist finitely-many irreducible factors such that and each is either (a) the flip-flop monoid where for all ; or (b) a finite simple group that divides .
Definition 6 (R-trivial Monoid). A finite monoid is -trivial if implies for all .
Theorem 4 (Stiffler 1973). A finite monoid is -trivial if and only if for some finite number of copies of .
Definition 7 (Aperiodic Monoid). A finite monoid is aperiodic if and only if for some finite number of copies of .
Definition 8 (Soluble Monoid). A finite monoid is soluble if and only if for some finite and each is either (a) or (b) a cyclic group of prime order which itself divides .
The Transformer Model
We adapt our formal model of transformers and RNNs from Merrill et al. [28]; Merrill [26]. Let be the token alphabet. We first define our notion of a multi-layer sequence model that will consume a sequence and produce a next token:
Definition 9 (Multi-layer, multi-head sequence model; Merrill et al. [28]; Merrill 2025) ). A decoder-only transformer with heads, layers, model dimension (divisible by ), and feed-forward width is parameterized by
A fixed embedding matrix ;
For and , query, key, and value projections . We also specify for each the head type: SMAT, AHAT, or GDN.
For , an output projection matrix , initial feedforward projection , and final feedforward projection .
An output projection matrix .
We now define how such a model computes a function .
Definition 10 ([28, 26]). Given an input , we apply inductive rules for each component, producing internal representations and, finally, an output as follows:
Embedding layer: Let is the embedding of . For , we define
Self-attention sublayer: At each layer , we compute attention heads. We first compute the sublayer input . For each head , we compute queries , keys , and values . The type of the head specifies a function that maps to each head output in a way we will return to defining. Finally, the self-attention sublayer then concatenates the output of heads and then applies a linear projection to compute
Feedforward sublayer: Let . The feedforward sublayer computes the following tokenwise transformation:
Unembedding layer: The transformer outputs the token associated with .
In this way, a multi-layer, multi-head sequence model implements a function . To view such models as language recognizers, we can simply identify a token in as a special “accept” symbol and say that the transformer recognizes a language if, for any string , .
This architecture follows peri-norm ([17]): the use of layer-norm both before and after each sublayer (as well as on the embeddings). As discussed in Appendix § 8.§ 1 of Li et al. [21], this is capable of simulating projected pre-norm ([25]), a standard tool in AHAT constructions.
Sequence Mixers
The last step is to define the types of sequence mixers used by each architecture:
Definition 11 (SMAT Head). The output of head at token on queries , keys , and values is
and .
Definition 12 (AHAT Head). The same as an SMAT head, but taking the limit .
Definition 13 (GDN Head). The output of head at token is defined via
with gate and write strength parameterized as in Yang et al. (2024). The eigenvalues of the transition are and . Following Grazzi et al. [7], we write GDN when (nonnegative eigenvalues) and GDN when (eigenvalues in ).
By the classes SMAT, AHAT, GDN, and GDN, we denote the classes of languages expressible when all heads are the corresponding type.
Fixed-Precision Fixed-Point Overflow Arithmetic
We use the following fixed-precision arithmetic model in our analysis. Let denote a datatype of numbers of the form where is a fixed positive integer and is a bounded signed integer or a special overflow value. Each number in can be specified using bits. When , corresponds to fixed-point arithmetic with decimal digits. Similarly, when , we have fixed-point arithmetic with fractional bits. , however, does not have to take one of these forms; it can be any positive integer. We next discuss three important aspects of this datatype: overflow, left-to-right evaluation, and rounding.
When computing arithmetic operations over two numbers in , if the resulting value lies in the range , it is projected on to the nearest value (breaking ties upwards) in . If the resulting value would exceed or drop below , it goes to the overflow state and cannot be further modified.
Expression over are evaluated by applying arithmetic operators in a standard order. However, under this arithmetic model, operations are not associative. For instance, equals , while for any , results in an overflow, yielding .9 To make the arithmetic well defined, we assume a left-to-right evaluation order for any iterated additions/-subtractions as well as multiplications/divisions.
When two numbers and in are added or subtracted without overflow, we obtain a result of the form that lies in . However, their product is , and when , this (again assuming no overflow) must be rounded out to the form where denotes rounded to the nearest integer, breaking ties upward. The larger the is, the stronger the rounding is. E.g., when , we effectively round away the least significant digits of the product. As we will see later (e.g., Lemma 3), this rounding behavior plays an important role in simulating certain state tracking primitives with GDNs.
Remark. Going beyond fixed precision would break the upper bounds we report. Further, even within fixed-precision, as discussed by Nowak et al. [32], the expressivity of linear RNNs can be sensitive to the choices in the specific arithmetic model used. For example, if large values wrapped around to rather than overflowing, this would allow simulating , adding expressive power to otherwise aperiodic architectures. Finally, we leave it to future work to understand how different evaluation orders might affect expressivity.
Expressivity Proofs
Basic Monoids
Lemma 1 (Implementing Basic Monoids). Various attention and recurrent mechanisms can solve various basic finite monoid word problems, as follows:
There exists a one layer SMA that implements .
There exists a one layer GDN that implements .
There exists a one layer AHAT that implements .
For any prime , there exists an 8-layer AHAT that implements .
Proof of Lemma 1.a. To recognize word problems in the monoid , we simply need to check if any occurs in the context . We do this by constructing an attention head where the query is , the key a boolean encoding whether token , and the value is . will return iff there exists some such that . Thus, taking will compute the word problem for .
Proof of Lemma 1.b. Ignoring the gating, GDN has the form
Fixing a vector dimension , let be the one-hot vector for . If , , and , then the GDN update can be understood to replace the vector in row of the state matrix with . We now describe the updates required to implement . For , let and be or , respectively, with in either case. Thus, these updates overwrite the first row of to be either or . For , let , reducing the update to the identity. Thus, the first row of is a representation of the word problem output, with , and .
Proof of Lemma 1.c. To compute the word problem, we construct an AHAT attention head that attends over all tokens in the context and retrieves the rightmost one. To do this, we add two terms to key : the first term is a boolean indicator for whether , and the second is tiebreaking term in that monotonically increases with [25 Appendix E]. The query at is just , and the value at is simply . Thus, at token , the AHAT head returns the rightmost such that , effectively solving the word problem.
Proof of Lemma 1.d. Let representations of be the input to a log-precision AHAT layer. To implement , we would like it to compute at each token . The “division lemma” of Merrill & Sabharwal (2025) is a valuable tool here: it shows how to compute from a representation of at position using a few layers of AHAT. However, it assumes , whereas our partial sum can be as large as . We get around this hurdle by leveraging the fact that is a fixed constant, as follows.
First, for each , we construct a log-precision uniform attention head that computes the representation of , i.e., the number of input values for that equal . By definition, . We can rewrite in terms of as follows:
Since , we can now apply the division lemma of Merrill & Sabharwal (2025) to the output of in order to compute for each in parallel, using a total of 7 AHAT layers. An MLP layer can then multiply the result (which is at most ) with , resulting in a representation of , which is at most . Another MLP layer can now compute , which is at most . A final MLP layer can now apply a operation to this sum, resulting in . We thus have an 8-layer log-precision AHAT that implements .
Lemma 2 (Implementing Monoid Composition). Let be a finite monoid with a KR decomposition . Suppose that for each , an attention-based or recurrent architecture of depth can implement (potentially each with its own datatype). Let . Then the depth- composition of the architectures implements .
Proof. We prove this by induction over the number of composed monoids. In the base case of , we simply have the input word (equivalently, the identity applied to ) encoded in the initial layer. For the inductive step, assume layer has a representation of the partial products for input for the monoid . We have a monoid whose elements are from , where is a map from to (cf. Definition 4). We can first compute a representation of these elements using a feedforward network since is simply a finite lookup table of the already represented partial products. By assumption, network can implement with a block of layers. We augment our inductive composed network with layers of . In case operates over a different datatype than , we can first cast the output representations of to the corresponding nearest values in the datatype of . Layer of this composed network will thus have a representation of the partial products for input under , finishing the inductive step.
Linear RNNs with Non-Negative Eigenvalues
Theorem 1 (GDN Apnd). For any aperiodic and for some periodic but solvable , there exists a fixed-precision that solves the word problem over .
We divide the proof of Theorem 1 into Lemmas 3 and 4. We first show that GDN with positive eigenvalues can recognize any aperiodic language via the Krohn-Rhodes decomposition. This resembles Theorem 4 of Sarrof et al. [36], but the construction is instantiated for GDN rather than an arbitrary linear RNN, and the arithmetic model assumed is slightly different.
Lemma 4. Let be an aperiodic monoid. Then there exists a fixed-precision GDN that solves the word problem over .
Proof. By Proposition 1, has a KR decomposition such that every is the flip-flop monoid . By Lemma 1.b, can be implemented with a single GDN layer. Applying Lemma 2, we obtain a -layer GDN that implements .
Lemma 3. There exists a GDN that recognizes under datatype for all large enough .
Proof. On input , define the key , which satisfies . It follows that
It suffices to show that there exist two states such that and vice versa: we can use and . Letting denote rounded to the nearest integer (breaking ties upward), we have
To leverage this to recognize , we use use the value associated with the beginning-of-sequence token to initialize the GDN state to . Then we can detect which state we are in using a linear projection that checks whether . For the product , this detects whether is even or odd, allowing us to recognize .
This construction works for any datatype where is large enough to represent the constants needed to perform the above computation.
The above construction uses a fixed-precision fixed-point datatype with denominator . Such a construction is also possible when is a power of 10, for instance when , i.e., rounding to two decimal places, which is perhaps more natural. In this case, we can set , which has unit norm and yields . Let and . As seen below, and under rounding to two decimal places, denote :
This provides another construction, with , supporting Lemma 3.
Further, as we show next, rounding isn’t necessary if we don’t limit ourselves to GDN style RNNs. Specifically, general linear RNNs with non-negative eigenvalues can recognize certain periodic languages even under exact arithmetic:
Lemma 5. There exists a linear RNN where has only non-negative eigenvalues that recognizes under datatype for all .
Proof. Define the linear RNN’s transition matrices on inputs and as
Note that these transition matrices are not parameterizable as GDNs, and instead form general linear RNNs. Their product is
It can be verified that corresponds to a rotation with eigenvalues , which implies that . Assume the beginning-of-sequence token creates the initial state as a diagonal matrix with diagonal entries and , represented here as . Then, upon seeing input , we will cycle through the following 6 states at every :
Note that and in the next step cycles back to . Each of these states can be detected via a simple linear projection. On input of the form , this yields a one-hot representation of mod 6 in the residual stream. Applying a finite lookup table allows us to determine mod 2 and recognize .
The construction in the above proof, in fact, shows that if we allow to be parameterized as the product of matrices with non-negative eigenvalues, then this idea extends to even recognizing the parity language . Specifically, following Equation (2), we can set
where the two constituent matrices have only non-negative eigenvalues. This product structure is similar to that of DeltaProduct ((Siems et al., 2025)), which parameterizes as the product of DeltaNet matrices. We thus have the following:
Corollary 2. There exists a linear RNN where is parameterized as the product of matrices with only non-negative eigenvalues that recognizes under datatype for all .
Log-Precision Attention
Theorem 2 (AHAT Sol). For any soluble , there exists a log-precision AHAT that solves the word problem over .
Proof. By Proposition 1, has a KR decomposition such that every is either the flip-flop monoid or for some prime . By Lemma 1.c, can be implemented with a single AHAT layer. By Lemma 1.d, can be implemented by a 8-layer AHAT. Applying Lemma 2, we obtain that AHAT can implement . More specifically, if contains groups of the form , then there exists a -layer AHAT that implements .
Proposition 2. Hybrid (GDN : SMAT : GM) Sol, i.e., for any soluble , there exists a hybrid model composed of fixed-precision GDN, log-precision SMAT, and mod gadgets GM for a fixed set of value that solves the word problem over .
Proof. By Proposition 1, has a KR decomposition such that every is either the flip-flop monoid or the group for some prime . By Lemma 1.b, can be implemented with a single fixed-precision GDN layer. What remains to implement is . Let representations of be the input to a single layer of log-precision SMAT. At token
, this layer can use uniform attention to compute a representation of the sum , e.g., or or . We can now feed this to the mod gadget to compute a representation of , thereby implementing . Applying Lemma 2 shows that the full hybrid model can implement .
Formatting Examples
Below are instances of the abstract general finite sample from Figure 2 rendered in the six different formats we use.
Integer Code
Track the current value of each variable after executing the assignments.
// ........
a <- 8;
c <- 10;
// ........
// ........
TMP <- 81;
b <- 11;
// ........
d <- 59;
TMP <- b;
// ........
a <- 38;
TMP <- a;
a <- c;
c <- TMP;
TMP <- d;
d <- b;
b <- TMP;
a ?= 9; b ?= 58; c ?= 37; d ?= 10; TMP ?= 58;
Spreadsheet Cells
Track the contents of each spreadsheet cell after following the instructions.
Enter 8 in cell A1.
......................................
......................................
......................................
Enter 10 in cell C1.
......................................
Enter 81 in scratch cell.
Enter 11 in cell B1.
Enter 59 in cell D1.
Copy the current contents of cell B1 into scratch cell.
Enter 38 in cell A1.
Copy the current contents of cell A1 into scratch cell.
Copy the current contents of cell C1 into cell A1.
......................................
Copy the current contents of scratch cell into cell C1.
Copy the current contents of cell D1 into scratch cell.
Copy the current contents of cell B1 into cell D1.
Copy the current contents of scratch cell into cell B1.
Final cell contents:
cell A1 contains 10. cell B1 contains 59. cell C1 contains 38. cell D1 contains 11. scratch cell contains 59.
Cube Painting
Determine the final color of every cube after following the instructions.
Paint cube 1 teal.
...............................
Paint cube 3 gray.
Paint mixing cube topaz.
Paint cube 2 maroon.
Paint cube 4 brick.
...............................
Paint mixing cube the same color as cube 2.
Paint cube 1 ivory.
Paint mixing cube the same color as cube 1.
Paint cube 1 the same color as cube 3.
Paint cube 3 the same color as mixing cube.
Paint mixing cube the same color as cube 4.
Paint cube 4 the same color as cube 2.
Paint cube 2 the same color as mixing cube.
...............................
...............................
...............................
Final colors:
cube 1 is gray. cube 2 is brick. cube 3 is ivory. cube 4 is maroon. mixing cube is brick.
People in Rooms
Track where each person is after following the movements in order.
Alice enters the basement.
.................................
Carol enters the studio.
.................................
.................................
Taylor enters the toolshed.
Bob enters the lounge.
David enters the lighthouse.
Taylor moves to Bob's current location.
Alice enters the canteen.
Taylor moves to Alice's current location.
Alice moves to Carol's current location.
Carol moves to Taylor's current location.
Taylor moves to David's current location.
David moves to Bob's current location.
.................................
Bob moves to Taylor's current location.
.................................
Final locations:
Alice is in the studio. Bob is in the lighthouse. Carol is in the canteen. David is in the lounge. Taylor is in the lighthouse.
Status Lights
Track the color displayed by each status light after following the instructions.
Set light A to teal.
Set light C to gray.
Set buffer light to topaz.
Set light B to maroon.
..........................................
Set light D to brick.
Set buffer light to the color currently displayed by light B.
Set light A to ivory.
Set buffer light to the color currently displayed by light A.
Set light A to the color currently displayed by light C.
..........................................
Set light C to the color currently displayed by buffer light.
..........................................
Set buffer light to the color currently displayed by light D.
..........................................
Set light D to the color currently displayed by light B.
Set light B to the color currently displayed by buffer light.
..........................................
Final light colors:
light A displays gray. light B displays brick. light C displays ivory. light D displays maroon. buffer light displays brick.
RULER
Some special magic numbers are hidden within the following text. Make sure to memorize it. I will quiz you about the numbers afterward.
One of the special magic numbers for hollow is: 9931280. must have been when they first started to. It was presumably many One of the special magic numbers for golden is: 3017169. thousands of years between when people first started describing things as One of the special magic numbers for temporary is: 8434201. One of the special magic numbers for silver is: 5570834. One of the special magic numbers for crimson is: 1829661. The special magic number for temporary becomes the number currently assigned to silver. hot or cold and when someone asked ''what is heat?'' No doubt it was a very One of the special magic numbers for hollow is: 9580157. The special magic number for temporary becomes the number currently assigned to hollow. gradual process. We don't know if Plato or Aristotle were the first to ask any of the questions they did. But their works are the oldest we have The special magic number for hollow becomes the number currently assigned to golden. The special magic number for golden becomes the number currently assigned to temporary. The special magic number for temporary becomes the number currently assigned to crimson. The special magic number for crimson becomes the number currently assigned to silver. The special magic number for silver becomes the number currently assigned to temporary. hollow is 3017169. silver is 1829661. golden is 9580157. crimson is 5570834. temporary is 1829661.
Additional Statistics and Results
References
- [1]Alireza Amiri, Xinting Huang, Mark Rofin, and Michael Hahn. Lower bounds for chain-of-thought reasoning in hard-attention transformers, 4 February 2025. URL http://arxiv.org/abs/2502.02393.
- [2]Anthropic. Claude Opus 5.5. https://www.anthropic.com/claude-opus-5-5, 22 September 2026. Accessed: 2026-9-25.
- [4]David A Mix Barrington and Denis Thérien. Finite monoids and the fine structure of NC¹. Journal of the ACM, 35(4):941–952, 1 October 1988. ISSN 0004-5411,1557-735X. doi: 10.1145/48014.63138. URL http://dx.doi.org/10.1145/48014.63138.
- [5]J. Richard Büchi. Weak second-order arithmetic and finite automata. In Saunders Mac Lane and Dirk Siefkes (eds.), The Collected Works of J. Richard Büchi, pp. 398–424. Springer New York, New York, NY. 1990. ISBN 978-1-4613-8928-6. doi: 10.1007/978-1-4613-8928-6_22. URL https://doi.org/10.1007/978-1-4613-8928-6_22.
- [6]Google. Introducing Gemini 3.8 Flash and 3.8 Flash Cyber. https://blog.google/innovation-and-ai/models-and-research/gemini-models/3-8-flash-and-3-8-flash-cyber/, 2 September 2026. Accessed: 2026-9-25.
- [7]Riccardo Grazzi, Julien Siems, Jörg K.H. Franke, Arber Zela, Frank Hutter, and Massimiliano Pontil. Unlocking state-tracking in linear RNNs through negative eigenvalues. In The Thirteenth International Conference on Learning Representations, 2025. URL https://openreview.net/forum?id=UvTo3tVBk2.arxiv.org/abs/2411.12537
- [8]J A Green. On the Structure of Semigroups. Annals of Mathematics, 54(1):163, 1 July 1951. ISSN 0003-486X,1939-8980. doi: 10.2307/1969317. URL http://dx.doi.org/10.2307/1969317.
- [9]Alex Gu, Baptiste Rozìere, Hugh Leather, Armando Solar-Lezama, Gabriel Synnaeve, and Sida I Wang. CRUXEval: A benchmark for Code Reasoning, Understanding and execution, 5 January 2024. URL http://arxiv.org/abs/2401.03065.
- [10]Michael Hahn and Mark Rofin. Why are Sensitive Functions Hard for Transformers?, 15 February 2024. URL http://arxiv.org/abs/2402.09963.
- [11]Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, Tom Hennigan, Eric Noland, Katie Millican, George van den Driesche, Bogdan Damoc, Aurelia Guy, Simon Osindero, Karen Simonyan, Erich Elsen, Jack W Rae, Oriol Vinyals, and Laurent Sifre. Training Compute-Optimal Large Language Models, 29 March 2022. URL http://arxiv.org/abs/2203.15556.
- [12]Cheng-Ping Hsieh, Simeng Sun, Samuel Kriman, Shantanu Acharya, Dima Rekesh, Fei Jia, Yang Zhang, and Boris Ginsburg. RULER: What’s the real context size of your long-context language models?, 9 April 2024. URL http://arxiv.org/abs/2404.06654.
- [13]Selim Jerad, Anej Svete, Jiaoda Li, and Ryan Cotterell. Unique hard attention: A tale of two sides. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pp. 977–996, Stroudsburg, PA, USA, 2025. Association for Computational Linguistics.
- [14]H Kamp. A Theory of Truth and Semantic Representation. In Jeroen A G Groenendijk (ed.), Formal methods in the study of language. U of Amsterdam, 1981.
- [15]Hans Kamp. Tense Logic and the Theory of Linear Order. Ph.d. dissertation, University of California, Los Angeles, 1968.
- [16]Michael J. Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM, 45 (6):983–1006, 1998. doi: 10.1145/293347.293351. URL https://doi.org.DOI
- [17]Jeonghoon Kim, Byeongchan Lee, Cheonbok Park, Yeontaek Oh, Beomjun Kim, Taehwan Yoo, Seongjin Shin, Dongyoon Han, Jinwoo Shin, and Kang Min Yoo. Peri-LN: Revisiting normalization layer in the transformer architecture. In Forty-second International Conference on Machine Learning, 2025. URL https://openreview.net/forum?id=ci1S6wmXtO.arxiv.org/abs/2502.02732
- [18]Najoung Kim and Sebastian Schuster. Entity tracking in language models. In Anna Rogers, Jordan Boyd-Graber, and Naaoaki Okazaki (eds.), Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 3835–3855, Toronto, Canada, July 2023. Association for Computational Linguistics. doi: 10.18653/v1/2023.acl-long.213. URL https://aclanthology.org/2023.acl-long.213/.DOI
- [19]Kenneth Krohn and John Rhodes. Algebraic theory of machines. I. Prime decomposition theorem for finite semigroups and machines. Transactions of the American Mathematical Society, 116(0):450–464, 1965. ISSN 0002-9947,1088-6850. doi: 10.1090/S0002-9947-1965-0188316-1. URL http://dx.doi.org/10.1090/s0002-9947-1965-0188316-1.
- [20]Jiaoda Li and Ryan Cotterell. Characterizing the Expressivity of Fixed-Precision Transformer Language Models. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2026. URL https://openreview.net/forum?id=29LwAgLFpj.arxiv.org/abs/2505.23623
- [21]Yanhong Li, Anej Svete, Ashish Sabharwal, and William Merrill. Efficiently representing algorithms with chain-of-thought transformers, 2026. URL https://arxiv.org/abs/2606.19697.
- [22]Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts to automata. In The Eleventh International Conference on Learning Representations, 2023. URL https://openreview.net/forum?id=De4FYqjFueZ.arxiv.org/abs/2210.10749
- [23]Robert McNaughton and Seymour A. Papert. Counter-Free Automata. Number 65 in M.I.T. Research Monograph. The MIT Press, Cambridge, Mass., 1971.
- [25]William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought, 11 October 2023b. URL http://arxiv.org/abs/2310.07923.
- [26]William Merrill and Ashish Sabharwal. A little depth goes a long way: The expressive power of log-depth transformers, 5 March 2025. URL http://arxiv.org/abs/2503.03961.
- [27]William Merrill, Jackson Petty, and Ashish Sabharwal. The illusion of state in state-space models. In Forty-first International Conference on Machine Learning, 12 April 2024.arxiv.org/abs/2404.08819
- [28]William Merrill, Hongjian Jiang, Yanhong Li, Anthony Lin, and Ashish Sabharwal. Why Are Linear RNNs More Parallelizable?, 2026a. URL http://arxiv.org/abs/2603.03612.
- [29]William Merrill, Yanhong Li, Tyler Romero, Anej Svete, Caia Costello, Pradeep Dasigi, Dirk Groeneveld, David Heineman, Bailey Kuehl, Nathan Lambert, Chuan Li, Kyle Lo, Saumya Malik, D J Matusz, Benjamin Minixhofer, Jacob Morrison, Luca Soldaini, Finbarr Timbers, Pete Walsh, Noah A Smith, Hanneleh Hajishirzi, and Ashish Sabharwal. Olmo Hybrid: From theory to practice and back, 3 April 2026b. URL http://arxiv.org/abs/2604.03444.
- [31]David A Mix Barrington, Kevin Compton, Howard Straubing, and Denis Thérien. Regular languages in NC1. Journal of Computer and System Sciences, 44(3):478–499, 1 June 1992. ISSN 0022-0000,1090-2727. doi: 10.1016/0022-0000(92)90014-a. URL http://dx.doi.org/10.1016/0022-0000(92)90014-A.
- [32]Franz Nowak, Ryan Cotterell, and Reda Bounamoud. An algebraic view of the expressivity of recurrent language models, 1 June 2026a. URL http://arxiv.org/abs/2606.01765.
- [33]Franz Nowak, Ryan Cotterell, and Reda Bounamoud. A compositional theory of causally masked transformers, 29 July 2026b. URL http://arxiv.org/abs/2607.26988.
- [34]OpenAI. Introducing GPT-6 Sol and Luna. https://openai.com/index/introducing-gpt-6-sol-and-luna/, 23 September 2026. Accessed: 2026-9-25.
- [35]Jorge Pérez, P Barceló, and Javier Marinkovic. Attention is Turing-complete. Journal of Machine Learning Research, 22(75):751–75:35, 2021. ISSN 1532-4435,1533-7928. URL https://www.jmlr.org/papers/volume22/20-302/20-302.html.
- [36]Yash Sarrof, Yana Veitsman, and Michael Hahn. The expressive capacity of state space models: a formal language perspective. In Proceedings of the 38th International Conference on Neural Information Processing Systems, NIPS ’24, Red Hook, NY, USA, 2024. Curran Associates Inc. ISBN 9798331314385.DOI
- [37]M P Schützenberger. On finite monoids having only trivial subgroups. Information and Control, 8 (2):190–194, 1 April 1965. ISSN 0019-9958,1878-2981. doi: 10.1016/S0019-9958(65)90108-7. URL http://dx.doi.org/10.1016/S0019-9958(65)90108-7.








