betaFeedback

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 S5S_5 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 S5S_5 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 (M,∘,1)(M, \circ, 1) of some (finite) set MM, a composition operation ∘\circ, and a neutral identity element 11. 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 ww over MM is a string w1w2…wnw_1w_2 \ldots w_n of elements of MM concatenated together, representing the composition w1∘w2∘⋯∘wnw_1 \circ w_2 \circ\cdots\circ w_n. Intuitively, ww represents a sequence of updates to a system: given some initial state s0s_0, observing w1w_1 moves the system to state s1s_1; observing w2w_2 moves it to s2s_2; so forth. Since MM is closed under composition, the word w=w1w2…wnw = w_1w_2 \ldots w_n is itself an element of MM; computing exactly which element is known as the word problem1 on MM.

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 MM can be decomposed into the iterated wreath product, denoted M1≀M2≀⋯≀MkM_1 \wr M_2 \wr\cdots\wr M_k, of finitely-many irreducible factors, loosely analogous to a (non-unique) prime factorization.1 Each irreducible factor MiM_i in this decomposition is either the two-element semilattice U1≜{1,0}U_1 \triangleq\{1,0\} where 0x=00x = 0, corresponding to immutable writes; the “flip-flop” monoid U2≜{1,a,b}U_2 \triangleq\{1,a,b\} where xy=yxy = y for x,y∈{a,b}x,y \in\{a,b\}, corresponding to mutable writes by value; the commutative group Zp\mathbb{Z}_p of integers modulo pp for some prime pp, 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 MM is called (i) r-trivial if for all x,y∈Mx,y \in M, xM=yMxM = yM implies x=yx = y [8]; (ii) aperiodic if for every x∈Mx \in M there is some n≥1n \ge1 with xn=xn+1x^n = x^{n+1} [37]; and (iii) soluble if every subgroup of MM 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 MM with KR decomposition M1≀M2≀⋯≀MkM_1 \wr M_2 \wr\cdots\wr M_k is (i) r-trivial if every MiM_i is U1U_1; (ii) aperiodic if every MiM_i is U2U_2;2 and (iii) soluble if every MiM_i is either U2U_2 or Zp\mathbb{Z}_p for some prime pp.

As illustrated in Figure 1, these classes form a nested hierarchy: Rtrv⊆Aprd⊆Sol⊆Fin\mathsf{Rtrv} \subseteq\mathsf{Aprd} \subseteq\mathsf{Sol} \subseteq\mathsf{Fin}, 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 S5S_5. 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.

Hierarchy of finite state tracking complexity classes and language model architectures

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 TC0\mathrm{TC}^{0}. 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 AC0\mathrm{AC}^0 [31 Theorem 3], Fin to the regular languages in NC1\mathrm{NC}^1 (all of them), and Sol to the regular languages in AC0\mathrm{AC}^{0} as well as those in TC0\mathrm{TC}^{0}, assuming TC0≠NC1\mathrm{TC}^{0} \ne\mathrm{NC}^{1} (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 dd 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 ii outputs ∑j≤isoftmax⁡j(qiTkj)vj\sum_{j \le i} \operatorname{softmax}_{j}(\mathbf{q}_{i}^{\mathsf{T}}\mathbf{k}_{j})\mathbf{v}_{j}.

  • Averaging hard attention (AHAT): an idealization in which token ii attends uniformly to tied positions j≤ij \le i that maximize qiTkj\mathbf{q}_{i}^{\mathsf{T}}\mathbf{k}_{j} and averages their values (Pérez et al. [35]).

  • Gated DeltaNet (GDN) (Yang et al. (2024)): a linear recurrence over a matrix-valued state,

St=αt(I−βtktktT)St−1+βtktvtT,ot=StTqt,(1)\mathbf{S}_{t}=\alpha_{t}\left(\mathbf{I}-\beta_{t}\mathbf{k}_{t}\mathbf{k}_{t}^{\mathsf{T}}\right)\mathbf{S}_{t-1}+\beta_{t}\mathbf{k}_{t}\mathbf{v}_{t}^{\mathsf{T}}, \qquad\mathbf{o}_{t}=\mathbf{S}_{t}^{\mathsf{T}}\mathbf{q}_{t}, \tag*{(1)}

with gate αt∈[0,1]\alpha_{t} \in[0,1] and write strength βt\beta_{t}. The eigenvalues of the transition I−βtktktT\mathbf{I}-\beta_{t}\mathbf{k}_{t}\mathbf{k}_{t}^{\mathsf{T}} are 11 and 1−βt1-\beta_{t}. Following Grazzi et al. [7], we write GDN+\mathrm{GDN}^{+} when βt∈[0,1]\beta_{t} \in[0,1] (nonnegative eigenvalues) and GDN±\mathrm{GDN}^{\pm} when βt∈[0,2]\beta_{t} \in[0,2] (eigenvalues in [−1,1][-1,1]).

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 (ff; a fixed number of bits w.r.t. input length nn), log precision (ℓ\ell; O(log⁡n)O(\log n) bits, enough to represent positions and uniform averages over the context), and mixed precision (mm; 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, Dp,d\mathbb{D}_{p,d}, defined in § A.4. Informally, it represents numbers in the form a/da/d where dd is a fixed positive denominator that controls the rounding behavior, and aa is either an integer in the range [−2p,2p][-2^{p},2^{p}] or a special overflow value ⊥\bot. We write, e.g., SMATf\mathrm{SMAT}_{f} and GDNf\mathrm{GDN}_{f} for the classes of languages recognized by fixed-precision SMATs and GDNs, respectively. Throughout, we say an architecture solves the word problem over MM if a single model in that architecture computes the correct output for every word over MM.

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 ff, mixed mm, or log ℓ\ell). First, Li & Cotterell [20] and Jerad et al. [13] showed SMATf=Rtrv\mathrm{SMAT}_{f}=\mathrm{Rtrv}, i.e., fixed-precision SMAT solves precisely the word problem over rr-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 SMATm⊂Aprd.\mathrm{SMAT}_{m} \subset\mathrm{Aprd.}, i.e., only for a strict subset of aperiodic monoids MM can mixed-precision transformers solve the word problem over MM. 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 TC0\mathrm{TC}^{0} (Merrill & Sabharwal 2023). Moreover, under the circuit complexity assumption TC0≠NC1\mathrm{TC}^{0} \ne\mathrm{NC}^{1}, the regular languages in TC0\mathrm{TC}^{0} are exactly Sol\mathrm{Sol} (Mix Barrington et al. [ [31], Theorem 8). Thus, assuming TC0≠NC1\mathrm{TC}^{0} \ne\mathrm{NC}^{1}, we have both SMATℓ∩Fin⊆Sol\mathrm{SMAT}_{\ell} \cap\mathrm{Fin} \subseteq\mathrm{Sol} and AHATℓ∩Fin⊆Sol\mathrm{AHAT}_{\ell} \cap\mathrm{Fin} \subseteq\mathrm{Sol}. 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 (aa)∗(aa)^{*}, but they assumed exact arithmetic, in contrast to our fixed-precision arithmetic model that allows rounding. Merrill et al. [28] show GDNf±=Fin^{\pm}_{f} = \mathrm{Fin}, 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±^{\pm} 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 (U1U_1, U2U_2, and Zp\mathbb{Z}_p) that various architectures can implement. Here, “implement” means that given a one-hot representation of a monoid element wiw_i in the input-layer hidden state at token ii, there will be a subspace of the representation of token ii in the final layer that encodes the partial product w1w2…wiw_1w_2\ldots w_i 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 SMATf_f that implements U1U_1.

b. There exists a one layer GDNf+^{+}_{f} that implements U2U_2.

c. There exists a one layer AHATℓ_{\ell} that implements U2U_2.

d. For any prime pp, there exists an 8-layer AHATℓ_{\ell} that implements Zp\mathbb{Z}_p.

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 kk basic monoids can be implemented by a depth-wise composition of the corresponding gadgets:

Lemma 2 (Implementing Monoid Composition). Let MM be a finite monoid with a KR decomposition M1≺M2≺⋯≺MkM_1 \prec M_2 \prec\cdots\prec M_k. Suppose that for each ii, an attention-based or recurrent architecture AiA_i of depth did_i can implement MiM_i compositionally with its own datatype. Let d≜∑i=1kdid \triangleq\sum_{i=1}^{k} d_i. Then the depth-dd composition Ak∘…∘A2∘A1A_k \circ\ldots\circ A_2 \circ A_1 of the architectures implements MM.

Armed with these lemmas, we are ready to state our main technical findings, in which MM refers to a finite monoid. Our first result shows that GDNf+^{+}_{f} can solve all aperiodic monoid word problems, and even some periodic (soluble) ones:

Theorem 1 (GDNf+⇏Aprd^{+}_{f} \not\Rightarrow\mathrm{Aprd}). For any aperiodic MM and for some periodic but soluble MM, there exists a fixed-precision GDN+^{+} that solves the word problem over MM.

Our proof leverages the fact that aperiodic monoids can be decomposed into flip-flops, implying via Lemma 1.b that GDNf+^{+}_{f} can solve all of Aprd. Specifically, for any aperiodic monoid that has a KR decomposition with kk basic monoids, our lower bound (Lemma 4 in §B) constructs a fixed-precision GDN+^{+} of depth kk. 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 (aa)∗(aa)^{*}:

Lemma 3. There exists a GDN+^{+} that recognizes (aa)∗(aa)^{*} under datatype Dp,25\mathbb{D}_{p,25} for all large enough pp.

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 AthA_t h and At′h′A'_t h') 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 (aa)∗(aa)^{*} if the AtA_t 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ℓ⊇_\ell\supseteq Sol). For any soluble MM, there exists a log-precision AHAT that solves the word problem over MM.

As discussed in § 3.1, assuming TC0≠NC1\mathrm{TC}^{0} \ne\mathrm{NC}^{1}, AHATℓ∩_\ell\cap Fin ⊆\subseteq Sol. Since Sol ⊆\subseteq Fin, Theorem 2 implies that, under this circuit complexity assumption, AHATℓ∩_\ell\cap 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ℓ∩_\ell\cap Fin ≈\approx Sol). Assuming TC0≠NC1\mathrm{TC}^{0} \ne\mathrm{NC}^{1}, AHATℓ∩_\ell\cap Fin = Sol, i.e., there exists a log-precision AHAT that solves the word problem for MM if and only if MM 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±^{\pm} 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 pp, suppose we have an architecture GMp^{p} (a mod gadget) that, given a number z∈Z≥0z \in\mathbb{Z}_{\geq0} (represented as 1/z1/z or layer-norm hash ϕ(z)\phi(z); [25]) as input, can compute a representation of z mod pz \bmod p. Proposition 2 (cf. §B) leverages KR decompositions to show that a hybrid model consisting of this gadget, along with GDNf+_f^{+} and SMATℓ_\ell, 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 mm variables, initialized to starting values and updated with nn 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 4+14+1 variables. Each variable is assigned an initial value (e.g., b←10b \leftarrow10, c←9c \leftarrow9). At step tt, a variable may be overwritten by a new constant value (as in a←37a \leftarrow37 at t2t_2) or it may be swapped with another (as bb and dd are swapped between t6t_6 and t8t_8). right: Five possible final states for the sequence, with the correct one (δ\delta) annotated with a green star.

We first generate a general finite state tracking sample that mixes assignments-by-reference (x↔yx \leftrightarrow y, 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 [1,64][1,64]. 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 (x←x+δ mod Nx \leftarrow x + \delta\bmod N, for some max value NN), an aperiodic sample by replacing it with the value it would have copied (x←Kx \leftarrow K), and an r-trivial sample by replacing every assignment with the variable’s initial value (x←x0x \leftarrow x_0). 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, mm, nn, 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-trivialAperiodicSolubleGeneral finite
0021.332.1
Sensitivity0.080.080.760.75
[0.00–0.91][0.00–0.91][0.06–1.00][0.04–1.00]
Prompt tokens (K)1.161.161.341.25
[0.07–981][0.07–981][0.09–768][0.06–939]
Shared across classes
Samples per condition2,720
Variables (mm)2, 4, 8, 16
Assignments (nn)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 nn of assignments; and second, whether the models are able to generalize to longer sequences with larger nn. We train models with nn between 8 and 256, and evaluate them on sequences with nn 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 o(n)o(n) sensitivity if they are aperiodic and Ω(n)\Omega(n) 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±^{\pm} 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±^{\pm}, and Hybrid±^{\pm}); and 2.7B parameters (Hybrid±^{\pm}). 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 ∼90%\sim90\% 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±^{\pm} model, manage to maintain accuracy of ∼50%\sim50\% 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 rr-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 GDN\mathrm{GDN} 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 GDN+\mathrm{GDN}^{+} in the hierarchy. It would be interesting to understand better understand the relation of GDN+\mathrm{GDN}^{+} 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 (M,∘,1)(M, \circ, 1) of a set MM, an associative binary relation ∘:M×M→M\circ: M \times M \to M, and an identity element $1suchthat$1∘a=a∘1=asuch that \$1 \circ a = a \circ1 = a for all a∈Ma \in M. We say that a monoid is finite if MM is finite.

Definition 2 (Word Problem). Let MM be a monoid, and let w=w1∘w2∘⋯∘wkw = w_1 \circ w_2 \circ\cdots\circ w_k be a word in MM, i.e., a composition of finitely many elements wi∈Mw_i \in M. Since MM is closed under ∘\circ, this composition is in MM as well. The word problem on MM is to determine the identity of w∈Mw \in M.

Definition 3 (Monoid Division). For monoids AA, BB, we say that AA divides BB, written A∣BA \mid B, if there exists a submonoid B′≤BB' \leq B and a surjective homomorphism B′↠AB' \twoheadrightarrow A.

Definition 4 (Wreath Product). For finite monoids MM, NN their wreath product M≀NM \wr N is the set MN×NM^N \times N of pairs (f,n)(f,n), where ff is a map from NN to MM and n∈Nn \in N, under the composition

(f,n)(g,n′)≜(h,nn′),where h(x)≜f(x)g(xn) for all x∈N,(f,n)(g,n') \triangleq(h,nn'), \qquad\text{where } h(x) \triangleq f(x)g(xn) \text{ for all } x \in N,

with identity (1,1)(1,1), where 1(x)≜11(x) \triangleq1 for all x∈Nx \in N.

Intuitively, M≀NM \wr N is a cascade in which NN processes an input and MM processes the input according to NN’s current state.

Definition 5 (Irreducibility). A finite monoid MM is irreducible if M∣(A≀B)M \mid(A \wr B) implies that M∣AM \mid A or M∣BM \mid B for all finite monoids AA, BB.

Theorem 3 [19]. Let MM be a finite monoid. Then there exist finitely-many irreducible factors M1,…,MkM_1, \ldots, M_k such that M∣(M1≀M2≀…≀Mk)M \mid(M_1 \wr M_2 \wr\ldots\wr M_k) and each MiM_i is either (a) the flip-flop monoid U2≜{1,a,b}U_2 \triangleq\{1,a,b\} where xy=yxy = y for all x,y∈{a,b}x,y \in\{a,b\}; or (b) a finite simple group that divides MM.

Definition 6 (R-trivial Monoid). A finite monoid MM is rr-trivial if xM=yMxM = yM implies x=yx = y for all x,y∈Mx,y \in M.

Theorem 4 (Stiffler 1973). A finite monoid MM is rr-trivial if and only if M∣(U1≀U1≀⋯≀U1)M \mid(U_1 \wr U_1 \wr\cdots\wr U_1) for some finite number of copies of U1U_1.

Definition 7 (Aperiodic Monoid). A finite monoid MM is aperiodic if and only if M∣(U2≀U2≀⋯≀U2)M \mid(U_2 \wr U_2 \wr\cdots\wr U_2) for some finite number of copies of U2U_2.

Definition 8 (Soluble Monoid). A finite monoid MM is soluble if and only if M∣(M1≀M2≀⋯≀Mk)M \mid(M_1 \wr M_2 \wr\cdots\wr M_k) for some finite kk and each MiM_i is either (a) U2U_2 or (b) a cyclic group of prime order Zp\mathbb{Z}_p which itself divides MM.

The Transformer Model

We adapt our formal model of transformers and RNNs from Merrill et al. [28]; Merrill [26]. Let Σ\Sigma be the token alphabet. We first define our notion of a multi-layer sequence model that will consume a sequence w∈Σ∗w \in\Sigma^* and produce a next token:

Definition 9 (Multi-layer, multi-head sequence model; Merrill et al. [28]; Merrill 2025) ). A decoder-only transformer with hh heads, dd layers, model dimension mm (divisible by hh), and feed-forward width ww is parameterized by

  1. A fixed embedding matrix E:Qm→Q∣Σ∣\mathbf{E} : \mathbb{Q}^m \to\mathbb{Q}^{\lvert\Sigma\rvert};

  1. For 1≤ℓ≤d1 \leq\ell\leq d and 1≤k≤h1 \leq k \leq h, query, key, and value projections Qkℓ,Kkℓ,Vkℓ:Qm→Qm/h\mathbf{Q}^{\ell}_k, \mathbf{K}^{\ell}_k, \mathbf{V}^{\ell}_k : \mathbb{Q}^m \to\mathbb{Q}^{m/h}. We also specify for each ℓ,k\ell,k the head type: SMAT, AHAT, or GDN.

  1. For 1≤ℓ≤d1 \leq\ell\leq d, an output projection matrix Oℓ:Qm→Qm\mathbf{O}^{\ell} : \mathbb{Q}^m \to\mathbb{Q}^m, initial feedforward projection W1ℓ:Qm→Qw\mathbf{W}^{\ell}_1 : \mathbb{Q}^m \to\mathbb{Q}^w, and final feedforward projection W2ℓ:Qw→Qm\mathbf{W}^{\ell}_2 : \mathbb{Q}^w \to\mathbb{Q}^m.

  1. An output projection matrix U:Qm→Q∣Σ∣\mathbf{U} : \mathbb{Q}^m \to\mathbb{Q}^{\lvert\Sigma\rvert}.

We now define how such a model computes a function Σ∗→Σ\Sigma^* \to\Sigma.

Definition 10 ([28, 26]). Given an input w∈Σ∗w \in\Sigma^*, we apply inductive rules for each component, producing internal representations and, finally, an output as follows:

  1. Embedding layer: Let E[wi]E[w_i] is the embedding of wiw_i. For 1≤i≤n1 \leq i \leq n, we define

hi0=layer_norm⁡(E[wi]).\mathbf{h}_i^0 = \operatorname{layer\_norm}(E[w_i]).
  1. Self-attention sublayer: At each layer ℓ\ell, we compute hh attention heads. We first compute the sublayer input h^iℓ−1=layer_norm⁡(hiℓ−1)\hat{\mathbf{h}}_i^{\ell-1} = \operatorname{layer\_norm}(\mathbf{h}_i^{\ell-1}). For each head 1≤k≤h1 \leq k \leq h, we compute queries qi,kℓ=Qkℓh^iℓ−1\mathbf{q}_{i,k}^{\ell} = Q_k^{\ell}\hat{\mathbf{h}}_i^{\ell-1}, keys ki,kℓ=Kkℓh^iℓ−1\mathbf{k}_{i,k}^{\ell} = K_k^{\ell}\hat{\mathbf{h}}_i^{\ell-1}, and values vi,kℓ=Vkℓh^iℓ−1\mathbf{v}_{i,k}^{\ell} = V_k^{\ell}\hat{\mathbf{h}}_i^{\ell-1}. The type of the head specifies a function that maps qi,kℓ,k:,kℓ,v:,kℓ\mathbf{q}_{i,k}^{\ell}, \mathbf{k}_{:,k}^{\ell}, \mathbf{v}_{:,k}^{\ell} to each head output ai,kℓ∈Qm/h\mathbf{a}_{i,k}^{\ell} \in\mathbb{Q}^{m/h} in a way we will return to defining. Finally, the self-attention sublayer then concatenates the output of hh heads and then applies a linear projection to compute

giℓ=hiℓ−1+layer_norm⁡(⟨ai,1ℓ,…,ai,hℓ⟩⋅Oℓ).\mathbf{g}_i^{\ell} = \mathbf{h}_i^{\ell-1} + \operatorname{layer\_norm}\left(\langle\mathbf{a}_{i,1}^{\ell},\ldots,\mathbf{a}_{i,h}^{\ell}\rangle\cdot O^{\ell}\right).
  1. Feedforward sublayer: Let g^iℓ=layer_norm⁡(giℓ)\hat{\mathbf{g}}_i^{\ell} = \operatorname{layer\_norm}(\mathbf{g}_i^{\ell}). The feedforward sublayer computes the following tokenwise transformation:

hiℓ=giℓ+W2ℓ(W1ℓg^iℓ)+.\mathbf{h}_i^{\ell} = \mathbf{g}_i^{\ell} + W_2^{\ell}(W_1^{\ell}\hat{\mathbf{g}}_i^{\ell})_+.
  1. Unembedding layer: The transformer outputs the token associated with arg⁡max⁡hndU\arg\max\mathbf{h}_n^d U.

In this way, a multi-layer, multi-head sequence model M\mathcal{M} implements a function Σ∗→Σ\Sigma^* \to\Sigma. To view such models as language recognizers, we can simply identify a token in Σ\Sigma as a special “accept” symbol aa and say that the transformer recognizes a language LL if, for any string ww, w∈L⟺M(w)=aw \in L \Longleftrightarrow\mathcal{M}(w) = a.

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 ii on queries qi\mathbf{q}_i, keys ki\mathbf{k}_i, and values vi\mathbf{v}_i is

ai=∑j=1iexp⁡(1/τ⋅qiTkj)Zi⋅vj,where Zi=∑j=1iexp⁡(1/τ⋅qiTkj)\mathbf{a}_i = \sum_{j=1}^{i} \frac{\exp(1/\tau\cdot\mathbf{q}_i^{\mathsf{T}}\mathbf{k}_j)}{Z_i} \cdot\mathbf{v}_j,\quad\text{where } Z_i = \sum_{j=1}^{i} \exp(1/\tau\cdot\mathbf{q}_i^{\mathsf{T}}\mathbf{k}_j)

and τ=d/h\tau= \sqrt{d/h}.

Definition 12 (AHAT Head). The same as an SMAT head, but taking the limit τ→0\tau\to0.

Definition 13 (GDN Head). The output of head at token ii is ai\mathbf{a}_i defined via

Siℓ=αiℓ(I−βikikiT)Si−1+βikiviT,ai=SiTqi,S_i^{\ell} = \alpha_i^{\ell}(I-\beta_i\mathbf{k}_i\mathbf{k}_i^{\mathsf{T}})S_{i-1}+\beta_i\mathbf{k}_i\mathbf{v}_i^{\mathsf{T}},\qquad\mathbf{a}_i=S_i^{\mathsf{T}}\mathbf{q}_i,

with gate αi∈[0,1]\alpha_i \in[0,1] and write strength βi\beta_i parameterized as in Yang et al. (2024). The eigenvalues of the transition I−βikikiTI-\beta_i\mathbf{k}_i\mathbf{k}_i^{\mathsf{T}} are 11 and 1−βi1-\beta_i. Following Grazzi et al. [7], we write GDN+^+ when βi∈[0,1]\beta_i \in[0,1] (nonnegative eigenvalues) and GDN±^{\pm} when βi∈[0,2]\beta_i \in[0,2] (eigenvalues in [−1,1][-1,1]).

By the classes SMAT, AHAT, GDN+^+, and GDN±^{\pm}, 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 Dp,d\mathbb{D}_{p,d} denote a datatype of numbers of the form a/da/d where d∈Z>0d \in\mathbb{Z}_{>0} is a fixed positive integer and a∈(Z∩[−2p,2p])∪{⊥}a \in(\mathbb{Z}\cap[-2^p,2^p]) \cup\{\perp\} is a bounded signed integer or a special overflow value. Each number in Dp,d\mathbb{D}_{p,d} can be specified using p+2p+2 bits. When d=10qd=10^q, Dp,d\mathbb{D}_{p,d} corresponds to fixed-point arithmetic with qq decimal digits. Similarly, when d=2qd=2^q, we have fixed-point arithmetic with qq fractional bits. dd, 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 Dp,d\mathbb{D}_{p,d}, if the resulting value lies in the range (1/d)[−2p,2p](1/d)[-2^p,2^p], it is projected on to the nearest value (breaking ties upwards) in Dp,d\mathbb{D}_{p,d}. If the resulting value would exceed 2p/d2^p/d or drop below −2p/d-2^p/d, it goes to the overflow state ⊥\bot and cannot be further modified.

Expression over Dp,d\mathbb{D}_{p,d} are evaluated by applying arithmetic operators in a standard order. However, under this arithmetic model, operations are not associative. For instance, (1/d)(a+(2p−2p))(1/d)(a+(2^p-2^p)) equals a/da/d, while for any a>0a>0, (1/d)((a+2p)−2p)(1/d)((a+2^p)-2^p) results in an overflow, yielding ⊥\bot.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 a/da/d and b/db/d in Dp,d\mathbb{D}_{p,d} are added or subtracted without overflow, we obtain a result of the form c/dc/d that lies in Dp,d\mathbb{D}_{p,d}. However, their product is ab/d2ab/d^2, and when d>1d>1, this (again assuming no overflow) must be rounded out to the form c/dc/d where c=[ab/d]c=[ab/d] denotes ab/dab/d rounded to the nearest integer, breaking ties upward. The larger the dd is, the stronger the rounding is. E.g., when d=10qd=10^q, we effectively round away the qq 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 00 rather than overflowing, this would allow simulating Zp\mathbb{Z}_p, 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 SMAf†{}_{f}^{\dagger} that implements U1U_1.

  • There exists a one layer GDNf+{}_{f}^{+} that implements U2U_2.

  • There exists a one layer AHATℓ{}_{\ell} that implements U2U_2.

  • For any prime pp, there exists an 8-layer AHATℓ{}_{\ell} that implements Zp\mathbb{Z}_p.

Proof of Lemma 1.a. To recognize word problems in the monoid U1={1,0}U_1=\{1,0\}, we simply need to check if any 00 occurs in the context ww. We do this by constructing an attention head hh where the query is 11, the key jj a boolean encoding whether token wj=0w_j=0, and the value is 11. hh will return 11 iff there exists some jj such that wj=0w_j=0. Thus, taking 1−h1-h will compute the word problem for U1U_1.

Proof of Lemma 1.b. Ignoring the gating, GDNf+{}_{f}^{+} has the form

St=(I−βtktktT)St−1+βtktvtT.S_t=(I-\beta_t\mathbf{k}_t\mathbf{k}_t^{\mathsf{T}})S_{t-1}+\beta_t\mathbf{k}_t\mathbf{v}_t^{\mathsf{T}}.

Fixing a vector dimension dd, let i⃗\vec{i} be the one-hot vector for i≤di\le d. If kt=i⃗\mathbf{k}_t=\vec{i}, vt=j⃗\mathbf{v}_t=\vec{j}, and βt=1\beta_t=1, then the GDN update can be understood to replace the vector in row ii of the state matrix with j⃗\vec{j}. We now describe the updates required to implement U2U_2. For wt∈{a,b}w_t \in\{a,b\}, let kt=1⃗\mathbf{k}_t = \vec{1} and vt\mathbf{v}_t be 1⃗\vec{1} or 2⃗\vec{2}, respectively, with βt=1\beta_t = 1 in either case. Thus, these updates overwrite the first row of StS_t to be either 1⃗\vec{1} or 2⃗\vec{2}. For wt=1w_t = 1, let βt=0\beta_t = 0, reducing the update to the identity. Thus, the first row of StS_t is a representation of the U2U_2 word problem output, with 0⃗≡1\vec{0} \equiv1, 1⃗≡a\vec{1} \equiv a and 2⃗≡b\vec{2} \equiv b.

Proof of Lemma 1.c. To compute the U2U_2 word problem, we construct an AHAT attention head that attends over all tokens a,ba,b in the context and retrieves the rightmost one. To do this, we add two terms to key jj: the first term is a boolean indicator for whether wj∈{a,b}w_j \in\{a,b\}, and the second is tiebreaking term in (0,1)(0,1) that monotonically increases with jj [25 Appendix E]. The query at ii is just 11, and the value at jj is simply wjw_j. Thus, at token ii, the AHAT head returns the rightmost wjw_j such that wj∈{a,b}w_j \in\{a,b\}, effectively solving the word problem.

Proof of Lemma 1.d. Let representations of z1,z2,…,zn∈{0,1,…,p−1}z_1,z_2,\ldots,z_n \in\{0,1,\ldots,p-1\} be the input to a log-precision AHAT layer. To implement ZpZ_p, we would like it to compute Si≜(∑j=1izj) mod pS_i \triangleq\left(\sum_{j=1}^{i} z_j\right) \bmod p at each token ii. The “division lemma” of Merrill & Sabharwal (2025) is a valuable tool here: it shows how to compute a mod pa \bmod p from a representation of aa at position ii using a few layers of AHAT. However, it assumes a≤ia \leq i, whereas our partial sum can be as large as (p−1)i(p-1)i. We get around this hurdle by leveraging the fact that pp is a fixed constant, as follows.

First, for each r∈{0,1,…,p−1}r \in\{0,1,\ldots,p-1\}, we construct a log-precision uniform attention head hrh_r that computes the representation of cr≜∣{j≤i∣zj=r}∣c_r \triangleq|\{j \leq i \mid z_j = r\}|, i.e., the number of input values zjz_j for j≤ij \leq i that equal rr. By definition, cr≤ic_r \leq i. We can rewrite SiS_i in terms of crc_r as follows:

Si=(∑r=1p−1rcr) mod p=(∑r=1p−1r(cr mod p)) mod p\begin{aligned} S_i &= \left(\sum_{r=1}^{p-1} r c_r\right) \bmod p \\ &= \left(\sum_{r=1}^{p-1} r(c_r \bmod p)\right) \bmod p \end{aligned}

Since cr≤ic_r \leq i, we can now apply the division lemma of Merrill & Sabharwal (2025) to the output of hrh_r in order to compute cr mod pc_r \bmod p for each rr in parallel, using a total of 7 AHAT layers. An MLP layer can then multiply the result (which is at most p−1p-1) with rr, resulting in a representation of br≜r(cr mod p)b_r \triangleq r(c_r \bmod p), which is at most (p−1)2(p-1)^2. Another MLP layer can now compute ∑r=1p−1br\sum_{r=1}^{p-1} b_r, which is at most (p−1)3(p-1)^3. A final MLP layer can now apply a  mod p\bmod p operation to this sum, resulting in SiS_i. We thus have an 8-layer log-precision AHAT that implements ZpZ_p.

Lemma 2 (Implementing Monoid Composition). Let MM be a finite monoid with a KR decomposition M1≀M2≀⋯≀MkM_1 \wr M_2 \wr\cdots\wr M_k. Suppose that for each ii, an attention-based or recurrent architecture AiA_i of depth did_i can implement MiM_i (potentially each with its own datatype). Let d≜∑i=1kdid \triangleq\sum_{i=1}^{k} d_i. Then the depth-dd composition Ak∘⋯∘A2∘A1A_k \circ\cdots\circ A_2 \circ A_1 of the architectures implements MM.

Proof. We prove this by induction over the number of composed monoids. In the base case of k=0k=0, we simply have the input word ww (equivalently, the identity applied to ww) encoded in the initial layer. For the inductive step, assume layer ∑i=1k−1di\sum_{i=1}^{k-1} d_i has a representation of the partial products for input ww for the monoid M1≀M2≀⋯≀Mk−1M_1 \wr M_2 \wr\cdots\wr M_{k-1}. We have a monoid MkM_k whose elements are from fk(M1≀M2≀⋯≀Mk−1)f_k(M_1 \wr M_2 \wr\cdots\wr M_{k-1}), where fkf_k is a map from M1≀M2≀⋯≀Mk−1M_1 \wr M_2 \wr\cdots\wr M_{k-1} to MkM_k (cf. Definition 4). We can first compute a representation of these elements using a feedforward network since fkf_k is simply a finite lookup table of the already represented partial products. By assumption, network A~k\widetilde{A}_k can implement MkM_k with a block of dkd_k layers. We augment our inductive composed network A~=Ak−1∘⋯∘A2∘A1\widetilde{A} = A_{k-1} \circ\cdots\circ A_2 \circ A_1 with dkd_k layers of AkA_k. In case AkA_k operates over a different datatype than A~\widetilde{A}, we can first cast the output representations of A~\widetilde{A} to the corresponding nearest values in the datatype of AkA_k. Layer ∑i=1kdi\sum_{i=1}^{k} d_i of this composed network will thus have a representation of the partial products for input ww under M1≀M2≀⋯≀MkM_1 \wr M_2 \wr\cdots\wr M_k, finishing the inductive step.

Linear RNNs with Non-Negative Eigenvalues

Theorem 1 (GDNf+⊉_f^+ \not\supseteq Apnd). For any aperiodic MM and for some periodic but solvable MM, there exists a fixed-precision GDN+GDN^+ that solves the word problem over MM.

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 MM be an aperiodic monoid. Then there exists a fixed-precision GDN+^{+} that solves the word problem over MM.

Proof. By Proposition 1, MM has a KR decomposition M1≀M2≀…≀MkM_1 \wr M_2 \wr\ldots\wr M_k such that every MiM_i is the flip-flop monoid U2U_2. By Lemma 1.b, U2U_2 can be implemented with a single GDNf+_f^{+} layer. Applying Lemma 2, we obtain a kk-layer GDN+^{+} that implements MM.

Lemma 3. There exists a GDN+^{+} that recognizes (aa)∗(aa)^* under datatype Dp,25\mathbb{D}_{p,25} for all large enough pp.

Proof. On input aa, define the key k=15⟨−3,4⟩k = \frac{1}{5}\langle-3,4\rangle, which satisfies ∥k∥=1\lVert k\rVert= 1. It follows that

A=I−kkT=125(1612129).A = I - kk^{\mathsf{T}} = \frac{1}{25}\begin{pmatrix} 16 & 12 \\ 12 & 9 \end{pmatrix}.

It suffices to show that there exist two states h,h′h,h' such that Ah=h′Ah=h' and vice versa: we can use h=125⟨9,8⟩h=\frac{1}{25}\langle9,8\rangle and h′=125⟨10,7⟩h'=\frac{1}{25}\langle10,7\rangle. Letting [x][x] denote xx rounded to the nearest integer (breaking ties upward), we have

Ah=A⋅125(98)=125([16×925]+[12×825][12×925]+[9×825])=125(6+44+3)=125(107)=h′.Ah=A\cdot\frac{1}{25}\begin{pmatrix}9\\8\end{pmatrix} =\frac{1}{25}\begin{pmatrix} \left[\frac{16\times9}{25}\right]+\left[\frac{12\times8}{25}\right]\\ \left[\frac{12\times9}{25}\right]+\left[\frac{9\times8}{25}\right] \end{pmatrix} =\frac{1}{25}\begin{pmatrix}6+4\\4+3\end{pmatrix} =\frac{1}{25}\begin{pmatrix}10\\7\end{pmatrix}=h'.
Ah′=A⋅125(107)=125([16×1025]+[12×725][12×1025]+[9×725])=125(6+35+3)=125(98)=h.Ah'=A\cdot\frac{1}{25}\begin{pmatrix}10\\7\end{pmatrix} =\frac{1}{25}\begin{pmatrix} \left[\frac{16\times10}{25}\right]+\left[\frac{12\times7}{25}\right]\\ \left[\frac{12\times10}{25}\right]+\left[\frac{9\times7}{25}\right] \end{pmatrix} =\frac{1}{25}\begin{pmatrix}6+3\\5+3\end{pmatrix} =\frac{1}{25}\begin{pmatrix}9\\8\end{pmatrix}=h.

To leverage this to recognize (aa)∗(aa)^*, we use use the value associated with the beginning-of-sequence token to initialize the GDN state to hh. Then we can detect which state we are in using a linear projection that checks whether h1−h2>2h_1-h_2>2. For the product AkA^k, this detects whether kk is even or odd, allowing us to recognize (aa)∗(aa)^*.

This construction works for any datatype Dp,25\mathbb{D}_{p,25} where pp 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 d=25d=25. Such a construction is also possible when dd is a power of 10, for instance when d=100d=100, i.e., rounding to two decimal places, which is perhaps more natural. In this case, we can set k=⟨−0.8,0.6⟩k=\langle-0.8,0.6\rangle, which has unit norm and yields A=(0.360.480.480.64)A=\begin{pmatrix}0.36&0.48\\0.48&0.64\end{pmatrix}. Let h=⟨0.12,0.15⟩h=\langle0.12,0.15\rangle and h′=⟨0.11,0.16⟩h'=\langle0.11,0.16\rangle. As seen below, Ah=h′Ah=h' and Ah′=hAh'=h under rounding to two decimal places, denote [x]2[x]_2:

Ah=A(0.120.15)=([0.36×0.12]2+[0.48×0.15]2[0.48×0.12]2+[0.48×0.15]2)=(0.04+0.070.06+0.10)=(0.110.16)=h′.Ah=A\begin{pmatrix}0.12\\0.15\end{pmatrix} =\begin{pmatrix} [0.36\times0.12]_2+[0.48\times0.15]_2\\ [0.48\times0.12]_2+[0.48\times0.15]_2 \end{pmatrix} =\begin{pmatrix}0.04+0.07\\0.06+0.10\end{pmatrix} =\begin{pmatrix}0.11\\0.16\end{pmatrix}=h'.
Ah′=A(0.110.16)=([0.36×0.11]2+[0.48×0.16]2[0.48×0.11]2+[0.48×0.16]2)=(0.04+0.080.05+0.10)=(0.120.15)=h.Ah'=A\begin{pmatrix}0.11\\0.16\end{pmatrix} =\begin{pmatrix} [0.36\times0.11]_2+[0.48\times0.16]_2\\ [0.48\times0.11]_2+[0.48\times0.16]_2 \end{pmatrix} =\begin{pmatrix}0.04+0.08\\0.05+0.10\end{pmatrix} =\begin{pmatrix}0.12\\0.15\end{pmatrix}=h.

This provides another construction, with d=100d=100, 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 AtA_t has only non-negative eigenvalues that recognizes (abab)∗(abab)^* under datatype Dp,1\mathbb{D}_{p,1} for all p>0p>0.

Proof. Define the linear RNN’s transition matrices on inputs aa and bb as

A(a)=(1101),A(b)=(10−11).A(a)=\begin{pmatrix}1&1\\0&1\end{pmatrix},\qquad A(b)=\begin{pmatrix}1&0\\-1&1\end{pmatrix}.

Note that these transition matrices are not parameterizable as GDNs, and instead form general linear RNNs. Their product is

A=A(b)A(a)=(11−10)(2)A=A(b)A(a)=\begin{pmatrix}1&1\\-1&0\end{pmatrix} \tag*{(2)}

It can be verified that AA corresponds to a rotation with eigenvalues e±iπ/3e^{\pm i\pi/3}, which implies that A6=IA^{6}=I. Assume the beginning-of-sequence token creates the initial state as a diagonal matrix with diagonal entries 11 and 00, represented here as ⟨1,0⟩\langle1,0\rangle. Then, upon seeing input (ab)∗(ab)^{*}, we will cycle through the following 6 states at every bb:

h0=⟨1,0⟩h1=⟨1,−1⟩h2=⟨0,−1⟩h3=⟨−1,0⟩h4=⟨−1,1⟩h5=⟨0,1⟩.\begin{aligned} h_{0}&=\langle1,0\rangle\\ h_{1}&=\langle1,-1\rangle\\ h_{2}&=\langle0,-1\rangle\\ h_{3}&=\langle-1,0\rangle\\ h_{4}&=\langle-1,1\rangle\\ h_{5}&=\langle0,1\rangle. \end{aligned}

Note that h3=−h0h_{3}=-h_{0} and h5h_{5} in the next step cycles back to h0h_{0}. Each of these states can be detected via a simple linear projection. On input of the form (ab)k(ab)^{k}, this yields a one-hot representation of kk mod 6 in the residual stream. Applying a finite lookup table allows us to determine kk mod 2 and recognize (abab)∗(abab)^{*}.

The construction in the above proof, in fact, shows that if we allow AtA_{t} to be parameterized as the product of matrices with non-negative eigenvalues, then this idea extends to even recognizing the parity language (aa)∗(aa)^{*}. Specifically, following Equation (2), we can set

A(a)=(1101)(10−11)=(11−10)(3)A(a)=\begin{pmatrix}1&1\\0&1\end{pmatrix}\begin{pmatrix}1&0\\-1&1\end{pmatrix}=\begin{pmatrix}1&1\\-1&0\end{pmatrix} \tag*{(3)}

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 AtA_{t} as the product of DeltaNet matrices. We thus have the following:

Corollary 2. There exists a linear RNN where AtA_{t} is parameterized as the product of matrices with only non-negative eigenvalues that recognizes (aa)∗(aa)^{*} under datatype Dp,1\mathbb{D}_{p,1} for all p>0p>0.

Log-Precision Attention

Theorem 2 (AHATℓ⊇_{\ell}\supseteq Sol). For any soluble MM, there exists a log-precision AHAT that solves the word problem over MM.

Proof. By Proposition 1, MM has a KR decomposition M1≀M2≀…≀MkM_{1}\wr M_{2}\wr\ldots\wr M_{k} such that every MiM_{i} is either the flip-flop monoid U2U_{2} or Zp\mathbb{Z}_{p} for some prime pp. By Lemma 1.c, U2U_{2} can be implemented with a single AHATℓ_{\ell} layer. By Lemma 1.d, Zp\mathbb{Z}_{p} can be implemented by a 8-layer AHATℓ_{\ell}. Applying Lemma 2, we obtain that AHATℓ_{\ell} can implement MM. More specifically, if M1≀M2≀…≀MkM_{1}\wr M_{2}\wr\ldots\wr M_{k} contains r≤kr\leq k groups of the form Zp\mathbb{Z}_{p}, then there exists a (k+7r)(k+7r)-layer AHATℓ_{\ell} that implements MM.

Proposition 2. Hybrid (GDN+^{+} : SMATℓ_{\ell} : GM) ⊇\supseteq Sol, i.e., for any soluble MM, there exists a hybrid model composed of fixed-precision GDN+^{+}, log-precision SMAT, and mod gadgets GMp^{p} for a fixed set of value pp that solves the word problem over MM.

Proof. By Proposition 1, MM has a KR decomposition M1≀M2≀…≀MkM_{1}\wr M_{2}\wr\ldots\wr M_{k} such that every MiM_{i} is either the flip-flop monoid U2U_{2} or the group Zp\mathbb{Z}_{p} for some prime pp. By Lemma 1.b, U2U_{2} can be implemented with a single fixed-precision GDN+^{+} layer. What remains to implement is Zp\mathbb{Z}_{p}. Let representations of z1,z2,…,zn∈{0,1,…,p−1}z_{1},z_{2},\ldots,z_{n}\in\{0,1,\ldots,p-1\} be the input to a single layer of log-precision SMAT. At token

ii, this layer can use uniform attention to compute a representation of the sum yi≜∑j=1izjy_i \triangleq\sum_{j=1}^{i} z_j, e.g., 1/yi1/y_i or ϕ(yi)\phi(y_i) or yi/iy_i/i. We can now feed this to the mod gadget GMpG_{\mathrm{M}}^p to compute a representation of z mod pz \bmod p, thereby implementing Zp\mathbb{Z}_p. Applying Lemma 2 shows that the full hybrid model can implement MM.

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. [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. [2]Anthropic. Claude Opus 5.5. https://www.anthropic.com/claude-opus-5-5, 22 September 2026. Accessed: 2026-9-25.
  3. [3]Boaz Barak, Benjamin L. Edelman, Surbhi Goel, Sham M. Kakade, eran malach, and Cyril Zhang. Hidden progress in deep learning: SGD learns parities near the computational limit. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL https://openreview.net/forum?id=8XWP2ewX-im.arxiv.org/abs/2207.08799
  4. [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. [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. [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. [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. [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. [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. [10]Michael Hahn and Mark Rofin. Why are Sensitive Functions Hard for Transformers?, 15 February 2024. URL http://arxiv.org/abs/2402.09963.
  11. [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. [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. [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. [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. [15]Hans Kamp. Tense Logic and the Theory of Linear Order. Ph.d. dissertation, University of California, Los Angeles, 1968.
  16. [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. [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. [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. [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. [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. [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. [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. [23]Robert McNaughton and Seymour A. Papert. Counter-Free Automata. Number 65 in M.I.T. Research Monograph. The MIT Press, Cambridge, Mass., 1971.
  24. [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.
  25. [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.
  26. [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
  27. [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.
  28. [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.
  29. [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.
  30. [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.
  31. [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.
  32. [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.
  33. [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.
  34. [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
  35. [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.

Paper details

vlnc:W_6ukkf4ea
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude Opus 5.5 High, Gemini 3.6 Flash, generative AI tools

View statement
Looking for related papers…
Contents