Unlocking State-Tracking in Linear RNNs Through Negative Eigenvalues
Authors: Riccardo Grazzi
Julien Siems
Arber Zela
Jörg K.H. Franke
Frank Hutter
Massimiliano Pontil
Venue: ICLR 2025 Oral (2025)
Keywords: State Tracking
State Space
Mamba
Linear RNN
Linear Attention
GLA
DeltaNet
Formal Languages
Products of Householders
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: We show that expanding the eigenvalue range of Linear RNN from [0, 1] to [-1,1] enhances their state-tracking capabilities, enabling them to solve complex tasks like parity and modular counting, while preserving their efficiency in language modeling.

Abstract: Linear Recurrent Neural Networks (LRNNs) such as Mamba, RWKV, GLA, mLSTM, and DeltaNet have emerged as efficient alternatives to Transformers for long sequences. However, both Transformers and LRNNs struggle to perform state-tracking, which may impair performance in tasks such as code evaluation. In one forward pass, current architectures are unable to solve even parity, the simplest state-tracking task, which non-linear RNNs can handle effectively. Recently, Sarrof et al. (2024) demonstrated that the failure of LRNNs like Mamba to solve parity stems from restricting the value range of their diagonal state-transition matrices to $[0, 1]$ and that incorporating negative values can resolve this issue. We extend this result to non-diagonal LRNNs such as DeltaNet. We prove that finite precision LRNNs with state-transition matrices having only positive eigenvalues cannot solve parity, while non-triangular matrices are needed to count modulo $3$. Notably, we also prove that LRNNs can learn any regular language when their state-transition matrices are products of identity minus vector outer product matrices, each with eigenvalues in the range $[-1, 1]$. Our experiments confirm that extending the eigenvalue range of Mamba and DeltaNet to include negative values not only enables them to solve parity but consistently improves their performance on state-tracking tasks. We also show that state-tracking enabled LRNNs can be pretrained  stably and efficiently at scale (1.3B parameters), achieving competitive performance on language modeling and showing promise on code and math tasks.

Published as a conference paper at ICLR 2025
UNLOCKING STATE-TRACKING IN LINEAR RNNS THROUGH NEGATIVE EIGENVALUES
Riccardo Grazzi Julien Siems Arber Zela
Jörg K.H. Franke Frank Hutter Massimiliano Pontil V
Equal contribution", CSML, Istituto Italiano di Tecnologia 8 University of Freiburg ELLIS Institute Tübingen*. AT Centre, University College London
ri ccardograzzi 4 40gmail w.gmall.com com
jul illienssems gma com
ABSTRACT
Linear Recurrent Neural Networks (LRNNs) such Mamba, RWKV, GLA, mL- STM, and DeltaNet have emerged as efficient alternatives to Transformers for long sequences. However, both Transformers and LRNNS struggle to perform state-tracking, which may impair performance in tasks such as code evaluation. In one forward pass, current architectures are unable to solve even parity, the sim- plest state- tracking task, which non-linear RNNs can handle effectively. Recently, Sarrof et al. (2024) demonstrated that the failure of LRNNNs like Mamba to solve parity stems from restricting the value range of their diagonal state-transition ma- trices to [o, 1] and that incorporating negative values can resolve this issue. We extend this result to non-diagonal LRNNs such as DeltaNet. We prove that finite precision LRNNS with state-transition matrices having only positive eigenvalues cannot solve parity, while non -rianrian matrices Notably, we also prove that LRNNs can learn any regular language when their tate-transition matrices are products of identity minus vector outer product trices, each with eigenvalues the range 1_ Our experiments confirm that extending the eigenvalue range of Mamba and DeltaNet to include negative values not only enables them to solve parity but consistently improves their performance on state-tracking tasks. We also show that state tracking enabled LRNNS can be pretrained stably and efficiently at scale (1.3B parameters), achieving competitive performance on language modeling and showing promise on code and math tasks.
needed count modulo 3.
INTRODUCTION
Transformer architectures (Vaswani et al. 2017) have revo-
Scaled Accuracy
1.00
lutionized NLP but scale quadratically sequence length,
Eigenvalue Range
0.75
posing computational challenges for long sequences. To
0.50
address this, Linear Recurrent Neural Networks (LRNNs)
[0. 1]
have emerged promising alternatives that offer linear scal-
0.25
[ 1,1]
ing while maintaining competitive performance (Gu Dao
0.00
2024 Dao & Gu 2024 Yang al. 2024a Peng et al. 2023
10000
20000
Deletang et al. 2023 Sun et al. 2024 Beck et al. 2024). LRNNs update their state via matrix-vector products with structured and often input-dependent state-transition matri- ces. The structure of the state-transition matrices largely de- termines the expressivity of LRNNs. While successful mod- els like Mamba (Gu & Dao, 2024) and GLA (Yang al. 2024a) use diagonal matrices (diagonal LRNN) which only mix tokens along the sequence dimension, recent work ex- plores more complex forms. Notably, non-diagonal ma- trices using generalized Householder (GH) transformations, defined as uu where is learnable vector and I is the identity, enable models like DeltaNet (Schlag et al.] 2021] Yang et al., (024b) and TTT-Linear (Sun et al., 2024) to achieve richer expressiveness through simultaneous token-channel mixing while maintaining efficiency.
Training Steps
Figure 1: Extending the eigenvalue range of the state transition matri- ces of diagonal LRNNs improves performance from random guessing (range [0, 1]) to perfect score (range -,,1) on learning parity. Trained on sequences up to length 40; Tested on lengths 40-256 (3 seeds).

---

Published as a conference paper at ICLR 2025
Surprisingly, both Transformers and current LRNNs face fundamental limitation: they struggle to learn how to track the state of even simple finite-state machines from sequences of state- transitions (Deletang et al. 2.23). This limitation may impair performance on tasks such as entity tracking in narratives, handling nested structures in code, and reasoning tasks that can benefit from maintaining and updating internal state over time (Merrill et al., (0024). Even the simplest state-tracking task, computing the parity of a sequence of bits, cannot be solved by modern architectures, while
non-linear RNNs like LSTM (Hochreiter & Schmidhuber, (197) and sLSTM (Beck al. 2024)
can effectively track the state of any finite state machine. However, parallelizing non-linear RNNs
across the sequence length presents significant challenges (Lim et al. 2024] Gonzalez et al.) 2024).
Recently,Saane Sarrof et al. (2024) demonstrated that the inability of diagonal LRNNs to solve the parity problem stems from the fact that the eigenvalues of their state-transition matrices are constrained to be positive. Specifically, they proved that finite precision diagonal LRNNs with exclusively positive real eigenvalues, cannot solve the parity problem in one forward pass for sequences of arbitrary length. However, their work did not provide empirical evidence showing that diagonal LRNNS with negative eigenvalues can be successfully trained to overcome this limitation. We prove that the same limitation also affects LRNNS with non-diagonal stae-transstion matrices, and further prove that additionally, non- con-triangular matrices are necessary to solve the more challenging task of modular counting (when the modulus is not power of two). Our findings also apply to the GH matrices used by DeltaNet, as they share the same eigenvalue limitations. To overcome this, we propose a simple yet powerful solution: extend the range of possible eigenvalues from [0, to []. This change enables state-tracking and significantly improves the expressivity of LRNNs without compromising their efficiency and training stability. As illustrated in Figure [ it allows diagonal LRNNs to learn parity successfully. The code for part of our experiments is available httpss//giithb..oom/// www///toom//mlooooiiiiiiiioo statee tracking
In summary, we make the following contributions:
We prove that any finite precision LRNN with only positive real eigenvalues in the state-transitonn matrices (most LRNNs used in practice) cannot solve parity at arbitrary sequence lengths (Theo- rem while non-triangular matrices are also required to learn counting modulo (Theorem ( 2. By extending the eigenvalue range, we significantly improve the state-tracking capabilities of LRNNs. We prove that LRNNS with state-transition matrices formed by products of generalized Householder (GH) matrices, each with eigenvalues in the range [-1. 1.. can learn any regular lan- guage (Theorem 4 in some cases with just one layer (Theorem 3. Notably, this range extension allows LRNNs using just one GH matrix (like DeltaNet), to learn substantially harder tasks, the repeated composition of permutations of two (over n) elements, compared to diagonal LRNNs.
3. We show that the eigenvalue range of Mamba and DeltaNet can be extended to [-1, 1] without compromising efficiency or training stability. We test the modified methods on parity, modular arithmetic, and permutation composition, demonstrating improved state-tracking performance.
4. We pre-train modified versions of DeltaNet and Mamba (up to 1.3B parameters) and show that they reach performance comparable the original models on generative language modeling tasks, while DeltaNet shows improved perplexity on code and math datasets.
2 RELATED WORK
Linear RNNs encompass state-space models and causal, linear attention mecha- nisms. State-space models, originally used for continuous dynamical systems, inspired LRNN vari- ants like S4 (Gu et al. 2022) and H4 (Fu et al.) 202T) (see Tiezzi et al. (2024) for survey). Recent advancements, such as Mamba (Gu & Dao 2024| Dao & Gu (024). introduced input-dependent gating of the hidden state, significantly improving language modeling performance. Concurrently, linear attention has emerged as an alternative to classical softmax attention, with KKahharppollos jt al. (2020) demonstrating that causal linear attention Transformers can be reformulated as RNNs with linear scaling in sequence length. Building on this. Yang et al. (2024a) proposed Gated Linear Attention (GLA), adding a gating mechanism similar to Mamba, while DeltaNet (Schlag et al. 2021 Yang al. 2024b) and TTT-Linear (Sun et al., 2024) explored more expressive recurrences with non-diagonal state-transitiin matrices. |Bck et al. (2024) recently proposed xLSTM, a successor to LSTM (Hochreiter & Schmidhuber) 1997) which combines non-linear and linear RNNs.
Linear RNNs.
Expressivity Results. Several studies have explored the expressive power of Transformers and
RNNs (see e.g. (Merrill et al. 2020 (ttrobl et al. 2024 Bhattamishra et al. 2024h). Here,
2

---

Published as a conference paper at ICLR 2025
focus on the ones most relevant to work. While Hahn (0200) proved that Transformers not model periodic languages such as parity, see also Bhattamishra et al. 2020, Lemma C.4), and some context-free languages at arbitrary sequence lengths, et al. (2023) demonstrated that Trans- formers can learn shorteut solutions for solvable finite state automata, though these solutions lack generalizability arbitrary sequence lengths and perform poorly outrof-distribution. Unlike RNNs, the high parallclizabiltty of Transformers prevents them from learning unsolvable finite state au- tomata (Merrill & Sabharwal 2023). These findings typically use techniques from algebraic formal language theory (we refer to Liu et al. (2023) for short tutorial) and circuit complexity, using the log-pre prpeciiiioon assumption and number of layers scaling linearly or logarithmically with sequence length. While earlier research established Transformers' Turing completeness, it relied on either arbitrary precision (Pérez et al., 202T) or arbitrary depth and weight sharing (Giannou et al. (023). Diagonal LRNNS can simulate any RNN with infinite depth (Gu et al. [021] and approximate reg- ular enough functions when the state dimension grows linearly with sequence length (Orvieto et al,, 2024]. However, things change when depth and state size are fixed. Merrill et al. (2024) proved that finite-depth diagonal LRNNs, like Transformers, struggle to learn unsolvable finite state automata when restricted to log-precinn precision arithmetic. The work by Fan et al. (2024) highlights similar lim- itation, while in a finite precision setting, |Sarrof et al. (2024) showed that diagonal LRNNs with positive values in the state-transition matrix, while capable of learning all star-free languages, can- not solve even the simple parity problem, a non-star-free language recognizable by an automaton with two states. However, their analysis was limited to the diagonal case and they did not test the benefit of negative eigenvalues in practice. Using a continuous time framework. also Cirone et al. (2025) pointed out the limitations of diagonal state transition matrices. Irie et al. (2021) 2023) empirically showed how srate-tracking can be enabled by modifying DeltaNet grammer (Schmidhuber 1992). but this makes its recurrence non-linear, hence hard to parallelize. Unlike previous work, we demonstrate that non-diagonal LRNNS like DeltaNet can achieve robust state- trackin through a minimal modification while maintaining efficient large-scale training.
fast weight pro-
BACKGROUND
3.1 LINEAR RECURRENT NEURAL NETWORKS (LRNNs)
We describe LRNNS using notation inspired by Sarrof et al. (024). focusing on the core linear recurrences while abstracting away the non-linear computations for each token. LRNNs are stacks of layers that share a common structure but have distinct learnable parameters. Each layer takes input vectors 21....,22 Ft E R (outputs of the previous layer) and outputs ÿ1. ....... 9t. E Rº as:
B(x,), D: = dec dec(H,, 2;), for all i E (I, Ho E Caxd, A C"Xn, B
H: = A(x;)H:,11 H;
(1)
Caxd dec: : x R B
Here, A, B and dec are learnable, generally non-linear functions, with dec usually containing a nerd-forward neural network. This definition encompasses most LRNN variants, which differ in the form of A, B and dec. Table [ illustrates how three popular LRNNs fit this framework. For other ar- chitectures see Yang al. 2024b Table 4). Additional details on the notation in Appendix A.
Table 1: Instances of LRNN layers in where sigimoid W:). sofolpuus CeaissWWACC Waw:), 3. 3--iggoid((w: æx),, while q:, k R U. E Rd are output of learnable functions of æ.. Also, ab: :d + Rd is another learnable function usually containing an MLP and a normalization, while Wi E R WA ddd W. E R wa E R' and w2 Rd are learnable parameters. For simplicity, we omitted ID convolutions. For Mamba, the matrices in the first two columns represent the recurrence for the i-th row of H, and we set ky -k-(k,,,.... ..., ke,.) W1 (11,,, Wi,))"
and / = d.
A(x,)
B(x))
deu (H,, w.)
Mamba GLA DeltaNet
Diag (exp (- A @ exp(w))))))
A, ② De
(HH, q: + w2 A xx)
Diag (axs)
kpy,
d H,, 4:)
I- k,
d( "(H, q:)
The state-transition matrices A Aax:) are typically diagonal generalized Householder (GH), i.e.. identity minus vector outer product, as shown in Table to enable efficient matrix-vector products on modern hardware. These matrices consistently have eigenvalues (and norm) in the range [0, 1].
3

---

Published as a conference paper at ICLR 2025
3.2 FORMAL LANGUAGE THEORY
Finite State Automata and Regular Languages. A (deterministic) finite state automaton (FSA) tuple A= (2, Q, 9o, d) where > is a finite set of letters called alphabet, Q is finite set of states, q0 E Q is the starting state and 8: Q x Σ -> Q is the fate-transition function (see Hopproft & Ullman 200T for an introduction). We define the set Σ", whose elements are sequences called words, as the smallest superset of Σ that contains the empty word E and is closed under word concatenation. We extend the state-transition function to 8: Q x E - Q by defining 8(g, {) - q and 8(g, w) = 5(0(4, W1 ... w;-1); w;) for any w W1 .... W0; E Σx with 2 2. We say that 0go,, w) is the state that A reaches after reading the word w E Σ" A language L C Σ is said to be recognized by A if there exists a recognizing set R Q such that L= {w E > 8(go. w) R). Regular languages are the ones that can be recognized by an FSA. Given an FSA A. the set ((AA= = {5(, w) w E Σ²} of functions p: Q -> Q, together with the function composition operation forms monoid called transition monoid, i.e. it is associative, closed and contains the identity ō(-,e). This monoid has finite number of elements, since [Q| < Co. Moreover, if 6(,, w) is bijective for every w E E, then ((A) forms a group, i.e. it contains the inverse of each element.
State-Tracking Tracking and Monoid Word Problems. State-tracking is the problem of determining the state of a system only by observing sequence of updates applied to it. Formally, it can be expressed as a monoid word problem (Merrill et al. 2024). where given a monoid (M, (M is the set and is the associative operation), we want to send words m. m.....MM me E M describing the sequence of updates, to their product my m22- ... m, E M, representing the state of the system after the updates. If M is finite there is a corresponding FSA (M, (M,,,e, d) that solves the word problem, where the starting state is e (the identity element), and the transition function is 8(mi,, m2) = mg m for m1, m2 M. In this work, focus on group word problems, i.e. problems where the monoid is also a group. In particular, on the cyclic group Zm, i.c. addition modulo m, and the symmetric group S.., i.c the group of permutations on m elements. Parity is equivalent to the S2 word problem, while many state-tracking problems such as tracking chess moves or code evaluation, can be shown to be harder than the S5 word problem, which cannot be solved by Transformers and diagonal LRNNS even in bog-precision for arbitrary word lengths (Merrill et al. 2024 Merrill & Sabharwal (023).
One LRNN Layer is an automaton. Given an alphabet Σ C, we can view one layer of an LRNN in ① as the automaton Ann (E, H, Ho, Ōnn), where Otin (H, w) = A(w) H + B(w), which is extended as we saw previously [T] and H. {f8in (Ho. w) : w E Σ _ S Ro We say that
an LRNN layer in (1) implements the FSA A= (E, Q, 90. 5) if Aun can mimic the state transitions of Formally, if there exists a surjective function g H -> Q such that for any H E H. w E Σ 50g H),w) g H. w)) ((((w) H + B(w)). Every language I. recognized by A can also be recognized by this LRNN layer with a sufficiently powerful dec. In particular if R R Q is the recognizing set for L and go g( Ho), then the decoder dec H,, wx) = ( E R). will correctly determine if w E L. Therefore, implementing A is at least as hard as recognizing L. A principal goal of this work is to show that current LRNNS cannot recognize simple languages such as parity (negative results) while appropriate modifications to the state- transition matrices, enable LRNNS implement broader classes of FSA (positive results), with certain classes of FSA requiring a single layer. Note, that while IRRNN with one layer can recognize any regular language, the state transition matrices might not fit into the structure imposed by current LRNNs, such as those in Table I (see Appendix f for more details).
4 THEORETICAL ANALYSIS
4.1 LIMITATIONS OF CURRENT LRNNS
In this section, we describe how positive eigenvalues and non-triangular state transition matrices limit LRNNs state-tracking capabitlies. In particular, we focus on parity and modular addition. The parity V/ E {0. 1] of a sequence of ones and zeros 21 .2, ber of ones in the sequence is odd, and 0 if it's even. Equivalent to addition modulo 2, it can be computed by summing the values in the input sequence and then applying the modulo 2 function:
10 is I if the total num-
(Ei 2.)) mod 2. This solution can be implemented by an LRNN with one layer and scalar Vi =
'We let 6un : Raxd x E-+ Ra and extend it to hna Raxd x D" + < then we define H. This definition is equivalent to that of FSA homomorphism, see Maler & Pnueli 1994 Definition 3).
4

---

Published as a conference paper at ICLR 2025
hy A(T]h, B()), ((L)) 2
h = a())ae 1 + b(1), a(1) =-1
Parity automaton
States
Odd
Clear
converge or diverge
separation
Even
Odd
Even
Figure 2:
Parity requires negative eigenvalues. States of one-layer LRNNS with the sequence 1111... as input. If the eigenvalues of (1) are nonnegative, the states either diverge or con- verge monotonically, and so, for large enough and in finite precision, cannot be distinguished. In contrast, the LRNN with a(1) -1 alternates between two states like the parity automaton.
states by setting A(x,) = (xx)) x. Ho = 0, and dec(H,, H, mod 2 in ① However, implementing such a solution with finite precision presents an issue: the state h4 can grow indefi- nitely with 4, eventually reaching the limit of our precision range. Indeed, he E {O..... (), requiring (t + 1) bits for storage. Moreover, in practice dec must approximate the modulus 2 function, which is challenging to learn due to its discontinuous and periodic nature.
A more efficient solution, which implements the two-state FSA solving this problem, can still be re- alized by finite precision LRNN with one layer and scalar states (and consequently also with vector states and diagonal state- transition matrices) using the recurrence h2 = a a(x; ( + b(2z), hg =
6(0) 00 0, b(1) a(0) 1, a(1) = -1, 1/2 he- Note that the state-transition scalar (11) is negative, while current diagonal LRNNS do not allow negative values. (Sarrof et al.] [222 Theorem 2) states that this fact makes real-valued diagonal LRNNs unable to solve parity, which raises the question: can non-diagonal LRNNs which allow only positive eigenvalues. such as DeltaNer, solve parity? The following result answers this question negatively by generalizing (aarrff et (2024) Theorem 2) to non-diagonal matrices. To solve parity, the state transition matrices must allow at least one eigenvalue to be neither real nor positive. For non-diagonal matrices, this eigenvalue could simply have nonzero imaginary part. The main idea of the theorem is illustrated in Figure 2
Theorem 1 (Parity). A finite precision LRNN with finitely many layers as in 7 can solve parity for arbitrary input lengths, in particular, it can recognize the language (11)", only if in at least one
layer, there exist x such that A(x) has at least one eigenvalue $ {x R x 2 0}.
The proof in Appendix B. uses the same core idea as the one in Sarrof et al. 2024 Theorem 2).
For one layer, we show that when x = 1* and the conditions for the eigenvalues of A(1) are not met, the mapping k + H4 and consequently also the one k yv will be constant (in finite precision and for large enough k), while k + Y/k, with yı being the parity of æ, alternates between and 1. To show this, we use the expression for the powers of the Jordan canonical form of A
We now study the problem of counting modulo m, an easier version of addition modulo m where the input of length & never changes and is x 1s, while the correct output is yı. = = 2;) mod m. The following theorem shows that to solve this problem, products of state-transition matrices must have at least one eigenvalue with nonzero imaginary part.
Theorem (Modular Counting). A finite precision LRNN with layers, each as in ① can count modulo m, i.e. it can recognize the language (1m*),, with m not power of two, only if there exist i {1..... L} and æ1...., Z2 such that for the i-th layer the product A(x;)A(z)) ... -1) has at least one eigenvalue X with nonzero imaginary part, i.e. X & R.
When L 1 key step is to show that if A(1) has real (even negative) eigenvalues, the map k + HA will alternate between two values (in finite precision and for large enough kt), not enough to count modulo m 2. For 1, we proceed by induction using our assumption on the eigenvalues of the product of state-transition matrices.
The proof is in Appendix B. 22
Discussion Theorems T and 2 identify a fundamental limitation of current design choices on the structure of the state-transition matrices of LRNNS. Specifically, current LRNNs, as the ones out- lined in [able are incapable of solving parity, as the eigenvalues of their state-transition matrices are confined to the interval [0, 1]. Further, even if we allow negative eigenvalues, LRNNs using common structures for the state transition matrices, such as diagonal or triangular with real entries, will show, LRNNs with
cannot solve counting modulo m. In contrast, that are (products of) generalized Householder matrices, each with eigenvalues in the range [-1, 1], much more expressive.
matrices
5

---

Published as a conference paper at ICLR 2025
4.2 ALLOWING NEGATIVE EIGENVALUES
We focus on two classes of LRNNs determined by the structure of their state-transition matrices: diagonal (such Mamba, Mamba2, and GLA) and generalized Houscholder (GH, in DeltaNet). In particular, if we let 8: R' + [0, 1]". Φ : - [0, 1] and v RR' + R", being learnable functions such that [|x(()]]| 1 for every x E R', then the state transition matrices of each layer of many LRNNs, such as those in Table can be written as either
: I- (a) == Diag(s(x)), or A (
where (a) is diagonal with eigenvalues s(x); E [0, while (CH( is GH with all eigen- values equal to one except for the one associated to the eigenvector v(x), which is equal to 1 - Φ(x:) [0, 1]. To address the limitations discussed in the previous section, we propose the following modification that can be easily applied to LRNNs belonging to either class.
A Ading (x) == (2a
(z) == I - 26(z))(22)((x)"
(2)
Hence, Ading (2)) has eigenvalues 2x(x); - 1 E [-1,1] and Ann(z) has one eigenvalue equal to 1 26(x) [-1, 1]. Thus, we have extended the eigenvalues range from [o, 1] to [-1,, The norm of the matrix is still less than or equal to one, keeping the recurrence stable at long sequence lengths.
LRNNS with the modified state transition matrices can implement the solution to parity in (2) by setting s11 0 and ((1) 1 so that if we consider a scalar recursion, then A ding (1) 11 However, Theorem Q shows that we cannot count modulo 3 with triangular state transition matrices, even when allowing negative cigenvalues. Therefore, in the next section, we examine the impact of our change to the eigenvalue range on non-triangular state-transition matrices.
4.3 EXPRESSIVITY OF PRODUCTS OF GENERALIZED HOUSEHOLDER MATRICES
We focus on state-transition matrices that are products of & GH matrices. For DeltaNet k = 1. For any n, k E N. we define the set of all matrices in R=x" that can be expressed product of &o GH matrices, each having the only interesting eigenvalue in the range C I, as
Mg(2)= = (C C2 C I ",a,, (1 E Ω,
E E.ER, ||:ll = 1}. (3)
Intuitively, higher i means higher expressivity but also higher cost for matrix-vector products. Fur- thermore, as long as Q S 1,] the norm of the matrices is bounded by one, which guaran- tees that repeated matrix product do not diverge. We observe that if M E Mf([-11), then M is a reflection (or Householder) matrix, and that for any æ E IR! ACH(#) E (f and A (Z)) E (f((-1,1) so that with our change we also include reflections. Moreover, ME (1) S. (2') if C S and either k' = k or k > k, Ω.
Our next result shows that products of GH matrices can represent any matrix with Euclidean norm less than or equal to 1, but only when [-1, C Ω. In contrast, repeated products of (e.g. upper) triangular matrices with eigenvalues in [- remain triangular, with eigenvalues in the same range.
Proposition 1 (Expressivity of products of GH matrices). The following hold for ME in (3)
1. For any N E ()), ||]]] < 1.
2. For any M E Raxx with || S 1, then M E MM ((),,)) and if M is orthogonal then M E M2((-1,1), while M E (M-1((11,)))
when M is a permulation matrix. 3. Any eigenvalue of any matrix N E (M(((111 1]) is either 1 or satisfies | < 1 and if in addition N E (M, 1)) and l < 2, then [0, 1] R.
The proof in Appendix C.2 uses mainly linear algebra arguments such as the SVD decomposition and the fact that every n x n orthogonal matrix can be written as product of reflections, due to the Cartan-Dieudonné Theorem (Gallier& & Gallier 2011).
A consequence of Proposition 3 is that LRNNS with layers of the form where A RR MI (I0, 1)), have state transition matrices that are either the identity or not orthogonal, and hence cannot be reflections or rotations. Also, if l < 2 the eigenvalues are positive and hence the LRNN cannot learn parity due to Theorem I In contrast, if we allow A : R' + ([-1,, 1) and &s is large enough, the following theorem shows that an LRNN with one layer can implement any FSA whose transition monoid is group, and that k 2 is enough for cyclic groups (modular addition).

---

Published as a conference paper at ICLR 2025
swup
Figure 3: A permutation of &o elements is also composition of most k 1 swaps.
3
3
2
2
This maps to a product of k-1 Hosehold- ers, each representing a swap. Illustrated
0
0
0
0
0
X
0
1
=
0
0
for k: = 3. 1
1
V1
v2 0)
3
.v. (0. -/ )
I 20,0!
20201
V2
Theorem 3. Every FSA A = QE,Q.90 whose transition monoid T(A) is a group, can be implemented by a finite precision LRNN with one layer and A Σ - M1,,((-1,13), where n is the smallest natural number such that T(A) is isomorphic to a subgroup of Sn, and k = maxwex. EgEQ 18(g, w) * q} is the maximum number of changed states after applying a single transition. Moreover, if T(A) is isomorphic to the cyclic group Lea, then we can set A: MB((-1,11 and if = (parity) we can set A ( (-1.1).
In the proof in Appendix C.3 we map each state-transition function to a matrix representation. This can always be done using permutation matrices, but for cyclic groups, we can also use rotation matrices (Appendix C.I. For permutations, if every state-transition permutes at most & states then the corresponding permutation matrix will be in Mg-1((-1)) 13), since it is either the identity or can be written product of at most k - 1 permutations of two elements (swaps), each in MT (1-1)) (see Figure 3 A consequence of Theorem 3 is that if every transition function of the FSA has permutation representation corresponding to swap the identity, then LRNN layer with ACH can implement it. This is useful in practice because the time complexity of an LRNN
A = having a product of k GH matrices as one transsttnniii matrix increases linearly with k. Also, for natural language tasks, the state-transitions for the FSA might be either simple or encoded using multiple letters. For example, for addition modulo 5, word may look like "3+2+4=4" (two letters per addition). This allows an LRNN with transitions. Indeed, if each transition uses letters and we set B = and
matrices in MM (I ([- 1, 1]) to model complex
TR. - ([- 1])
in I then the LRNN layer can model permutations that change up to k + elements since
H; = H C( R1- = A A ( A(x,,)) E M ([-1, 1))-
In Appendix D we also show that, interestingly, an LRNN with two layers (instead of just one), each having only reflections (instead of rotations) as state-transition matrices, can solve addition modulo m. We now present an important result on the expressivity of LRNNs with multiple layers.
Theorem 4. LRNNs with state transition matrices that are repeated products of GH matrices, each with eigenvalues in the range 1., can recognize any regular language. In particular, every FSA A [, Q, qu, 5) can be implemented by a finite precision LRNN with < 2 layers, each of the form where n < Q), p < s, d = 1, A R' (1 1]) and B R + N
The proof in Appendix C.3 exploits the landmark Theorem by Krohn & Rhodes 19655) which states that every FSA can be decomposed as a cascade of simpler FSAs whose state-transife functions constant. Each layer of the LRNN will implement one FSA (with states) either one-to-one of the cascade using n x n permutation matrices, which are in M ({ (1),, 1}), transitions, while for constant (state-independent) transitions it will set the corresponding state- transition matrix to 0 E ((0)) and the function B appropriately. Note that we can obtain the zero matrix only inefficiently single diagonal matrix. This points towards LRNNs using mix of GH and diagonal matrices, as recently explored by Gated DeltaNet (Yang et al. 2025) and RWKV-7
for the one-to-one
product of n GH matrices, while it could also be obtained with
Discussion The results in Theorems 3 and for LRNNs are in sharp contrast with the ones for Trans- formers (Liu et al., 2023 Merrill & Sabharwal 2023) and diagonal LRNNS (Merrill et al., 2024). which require either the number of layers or the precision growing with the input sequence length, and can only implement an FSA if all groups in its transition monoid are solvable, i.c. excluding groups isomorphic to S,, with n > 5. However, compared to LRNNs without any restriction to the matrices, which need only one layer to recognize any regular language,
norm of the result requires both the number of layers and the width of the LRNN to be (in the worst case) exponential in the number of states of the FSA, although we conjecture that the number of layers might be reduced to at most linear using more refined decomposition.
7

---

Published as a conference paper at ICLR 2025
5 EXPERIMENTS
We investigate the effects of expanding the eigen- value range of state-transition matrices from [0, 1] to [-,, as explained in Section 4.2 on both syn- thetic tasks and language modeling. Our experi- ments involve Mamba, and DeltaNet, with variants trained using both the original and extended eigen- value ranges, as shown in Table 2 We label these variants accordingly. Note that the changes increase the expressivity of Mamba and DeltaNet while com- ing no additional computational cost. Detailed in- formation on the implementation can be found in Appendix E.4
Table 2: Summary of modifications to the state-transition matrices A(x;) to tend the eigenvalue range from [0. 1| (Ta-
ble 1 to [-1,1]- We set s(x))
exp A exp(w1,))
[0.1]
[,,
Mamba DeltaNet
Diag (xx:))
Diag (2((x))))))
I B k
I - k3,
5.1 CHOMSKY HIERARCHY
We conducted experiments with some of the formal language tasks proposed by Deletang et al. (2023) and similarly used to benchmark xL.TTM (Beck et al., 2024). Our focus was on tasks where mLSTM (an LRNN) previously under- performed while sLSTM (a non-linear RNN) succeeded, specifically parity, mod- ular arithmetic without brackets (both reg- ular languages) and modular arithmetic with brackets (context-free language). As in Beck et al. (2024). we trained each model with sequence lengths ranging from 3 to 40 and evaluated on lengths from 40 to 256, to assess length generaliza- tion. Note that our theoretical results cover just regular languages, excluding modular arithmetic with brackets. We compared a Transformer, mLSTM and sLSTM against two variants each of Mamba and DeltaNet- with and without eigenvalue range extension.
Table 3: Performance comparison of various recurrent models on formal language tasks. We report the best of 3 runs (Table[5jin in the Appendix reports the median). Scores are scaled accuracy, with 1.0 indicating perfect performance and 0.0 random guessing. The positive impact of allowing negative eigenvalues 1, 1] range)
versus restricting to positive eigenvalues (io. 1] range) is evident for both Mamba and DeltaNer. Results in parenthesis are as reported in Beck et al. (024)).
Mod. Arithm.
Mod. Arithm. (w/ brackets)
Parity
(wfo brackets)
Transformer
0.022
0.031
0.067
mLSTM
0.087 (0.04)
0.040 (0.04)
0.114 (0.03)
sLSTM
1.000 (1.00)
0.787 (1.00)
0.178 (0.57)
Mamba 00, 1] 0.000
0.095
0.123
Mamba 1,
1.000
0.241
0.116
DeltaNet [0. 0.017
0.314
0.194
DeltaNet [1,
1.000
0.971
0.260
Results Our findings, presented in Table B demonstrate that expanding the range of eigenvalues from [0. 1] to [-1, 1] enables all examined models to fully solve the parity task, confirming Theo- remp | For both modular arithmetic tasks, this expansion led substantial performance improve- ments for Mamba and especially DeltaNet, since the latter has non-diagonal state-transition matrices that are more suited for these tasks (see Theorem 3 In Figure 6 in the Appendix, visualize the length extrapolation performance of each model on all considered tasks. Note that we were unable reproduce the sLSTM results reported by Beck et al. (2024) for the modular arithmetic tasks. Additional experiments and details on the tasks in Appendix
5.2
STATE-TRACKING
We perform experiments on group word problems, relying on the code provided by Merrill et al. 2024 We focus on the Sş group-the the first unsolvable symmetric group where current LRNNs and Transformers are known underperform. We also report results for addition modulo 60 (i.e., the cyclic group Z in Appendix [.2.2] and note that parity corresponds to Sz. In these experiments, the model receives a sequence of group elements as input, and the supervision is another sequence of group elements, each representing the product of the preceding input elements. Since solving S₁ might need LRNNS with state- transitttniiiionn matrices formed by repeated products of four GH matrices (see Theorem 3) each with eigenvalues in [-,, we also consider three simplified setups: (i) al- lowing only permutations of up to 2 elements (identity and swaps), (ii) allowing only permutations of up to 3 elements, and (iii) using 4 tokens for each permutation. Additional details are in Ap-
8

---

Published as a conference paper at ICLR 2025
-9- (1.121 100
S: only swaps
S, swaps, 3-perm.
S tokens per trans.
Sg
100
[el (1L)
DeltaNet (SL)
DelaNet [1 50
50
Mamba (SL)
Mamba (5L)
Full matrix simple
0-
01
10
10 10
10
10
10
10 10"
Sequeace Length
Sequence Length
Sequence Longth (9 tokens)
Sequence Length
Figure 4: Sequence accuracy for varying sequence lengths on S3 after 100 epochs of training. We
report the best of 3 seeds for each method (in Figure 7 we report all seeds). The dashed vertical line indicates the sequence length used during training (32 except for the third plot from the left where it is 64). Each method is labeled with name, eigenvalue range, and number of layers. The dashed vertical line indicates the sequence length used during training. "Full matrix simple" " is a one-layer baseline where the state update matrices are full and have control over the eigenvalue range.
CodeParrot
Math-Hard
Trivia
SlimPajama
25
18
Perplcaity
26
24
DelisNN: 340M Eigenvalce Range:
24
16
[0, 1]
22
[-1.1]
15
24
14
DeliaNo: 1.3B Eigenaaus Range:
Peplondy
14
12
13
[0, U]
[.1.]]
13
12
2046
2048
2048
Sequence Lougth
Sequence Length
Sequence Length
Sequenee Length
Figure 5: Performance sequence length of DeltaNet variants (340M (top) and 1.3B (bottom) parameters) on four datasets. DeltaNet with eigenvalue range 1) improves perplexity in coding and math compared to the [0, 1] baseline. Dashed vertical line at training context length (2048).
pendix E.2
We stress that, even when restricting the inputs to only identity and swaps, the group elements for the supervision still cover the entire group, because swaps are generators of the group.
Results Figure 4 shows that, as predicted by Theorem 3 restricting the inputs to only swap permu- tations allows DeltaNet [-1, 1] with even layer to fully learn the task (since its transsrannition matrices can model swaps), while DeltaNet [o. 1] with 5 layers generalizes just slightly beyond the training length. In contrast, by including also permutations of elements, decrease in the performance of all models. Interestingly. extending the range is still advantageous in this case and DeltaNet [-1, 1] with layers reaches a good length generalization. Moreover, using 4 tokens per group element seems also beneficial compared to standard S5, since DeltaNet [-1, with 5 layers manages to extrapolate very well until around length 200, which corresponds to 50 group elements, while on standard S5 all models have 0 sequence accuracy prior to sequence length 30. We also report that Mamba, a diagonal LRNN, performs poorly on all setups, with and without increased eigenvalue range.
notice a substantial
5.3 LANGUAGE MODELING
Experimental Setup We train DeltaNet models with 340M and 1.3B parameters and Mamba models with 370M parameters, each using both original and extended eigenvalue ranges. Training done on the full Web-100B dataset (Penedo et al. 2024). We chose Web rather than Webe since it contains more code. We aligned our training pipeline with Yang et al. (2024b); see Ap- pendix F. for details. Given our previous theoretical and experimental findings, we hypothesize that models (especially DeltaNet) with extended eigenvalue range will perform better on language modeling tasks linked to state-tracking such coding mathematics, compared to unmodified models. To test this hypothesis, we evaluate the perplexity these models in a length extrapolation setup using various datasets: CodeParrot (Tunstall et al. 2022) for coding, Math-Hard (Hendrycks) et al. 2021 for mathematics. TriviaQA (Joshi et al. 2017 and SlimPajama (Soboleva et al. 2023).
Results All models trained stably with our modification and without changing the learning rate. The validation perplexity of the proposed variants was comparable, albeit slightly worse than that of the original models throughout training (see Figure Saaureeinnn in the Appendix). The experiments in Fig-

---

Published as a conference paper at ICLR 2025
Table 4: Performance comparison using Im-harness benchmark (Gao et al. 2024) (SlimPajama (SPJ) reproduced from Yang et al. (2024b), Fine- Web (FW) ours). Results are shown for the original and extended eigenvalue range. Our models show comparable performance across tasks.
Mudel
Wiki.
LMB.
LMB.
PIQA
Hella. acc.n
Wino. 800
ARC-
ARC-e
Avg.
SWDE
SQUAD
FDA
ppl
ppl
900.n
T
cont.
coot. T
340M params
Sieehjinss
Transformere+
28.39
42.69
31.0
63.3
34.0
50.4
44.5
24.2
41.2
42.2
22.1
21.4
Mamha (0.
39.66
50.1
23.0
GLA [0.1]
29.47
45.53
31.3
65.1
33.8
$1.6
44.4
24.6
41.8
24.0
24.7
7.3
DeltaNet (0,
28.24
37.37
32.1
64,8
34.3
52.2
45.8
23.5
42.1
26.4
28,9
12.8
340M params
DeltNNet (0.
24.68
31.49
33.7
70,3
45.1
51.3
50.0
26.1
46.1
35.2
28.7
11.8
DeltaNet (-1, 11
24.54
31.15
34.0
69.9
44.6
51.9
50.0
24.4
45.8
37.2
33.1
370M params
Mamba
24.69
51.2
27.7
Mamba (-1, 1
25.02
24.71
36.2
70,5
47.8
$3.3
$4.7
26.7
48.2
20.9
24.8
2,5
m JAMP Steohiisss rote
1.38 params
Transfomere+
16.85
13:44
48.9
70.8
49.6
53.6
56.0
26.5
50.9
66.6
31.5
27.4
Mamba 0. 1
17.06
13.89
46.2
72.2
40.1
54.1
59.0
28.2
50.0
41.4
35.2
[0.
71.8
49.8
53.9
42.6
DeltuNet (0, 1]
16.87
12.21
48.9
71.2
50.2
53.6
57.2
28.3
51.6
49.5
37.4
17.2
paraans
DeltaNet [o, 1]
18.54
14.32
41..5
73.7
56.2
56.9
$8.2
29.9
53.1
49.1
35.1
8.6
DeltaNet [-1
12.73
33.9
demonstrate that coding and math datasets, DeltaNet with eigenvalue range of [-1, 1] achieves lower perplexity than the baseline with range [0. 1] for both model sizes. For TriviaQA, the perplexity of DeltaNet [-1, slightly higher. Note, that this is task relying on memoriza- tion, not linked to state-tracking, and hence we do not expect an improvement. On SlimPajama, we also observe slight improvement with our modification. For Mamba instead, our modifications consistently degrades the performance on these tasks (Figure in the Appendix).
ure
To ensure that our models are comparable with those obtained by Yang et al. (2024b), we evaluate them on the same benchmark tasks from Im-harness (Gao et al.) 2024) in Table 4 Note, that we trained on 100B tokens of FineWeb, while Yang et al.] (2024b) reported results from training on 15B and 100B tokens of SlimPajama. At 340-370M parameters, with the extended range both architectures show enhanced performance in some of the tasks: Mamba the second subset of tasks (+2.1% average accuracy) and DeltaNet in retrieval tasks (+2% SWDE, +4.4% SQUAD). At 1.3B parameters, extending the eigenvalue range of DeltaNet shows mixed results, suggesting that the increased expressivity may need training beyond 100B tokens to fully unlock the model's 's capacity.
6 CONCLUSION
In this work, showed the substantial impact of extending the eigenvalue range of state-transition matrices LRNNS from [0, 1] to [-,, This modification provably enhances LRNN expressivity in state-tracking tasks, without adding overhead in training inference. While Mamba successfully solves the parity problem, its diagonal matrix structure limits further gains. In contrast, DeltaNet, thanks to its non-diagonal state transition matrices which enable simultaneous token and channel mixing, excels across a broader spectrum of tasks. Our results underscore the critical role of non- diagonal transsttanitiionn matrices in augmenting state-tracking capabilities, highlighting a promising direction for future LRNN advancements.
Limitations and Future work Our modification is not directly compatible with numerical tech- nique used by some diagonal LRNNS such as Mamba2, GLA and mLSTM. In particular, these mod- transitinn matrices to compute cumulative products in log space, which im- proves numerical accuracy and potentially training stability (see Appendix [E.4 for details). Further research is needed assess the impact of training large-scale language models with state-tracking capabilities. To this end, we aim to understand the potential downsides of increased expressivity. For example, we hypothesize a fundamental trade-off between state-tracking and associative recall, which is also of theoretical interest and could guide hybrid model design. Moreover, the theoretical expressivity of DeltaNet [-1, 1] with multiple layers is still unclear. We showed that it can solve addition modulo m (in Appendix DD) which is equivalent to the Zo group word problem, but do not know if it can also solve other word problems, such as the ones for the symmetric groups S, with 2 3.
els rely on positive
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We would like to thank David Salinas, Herilalaina Rakotoarison, Eric Alcaide, Arya Akhavan, Matia Bojovic, Erfan Mirzaei and the active members of the Flash Linear Attention discord channel for their constructive discussions and feedback. We acknowledge the support and assistance of the Data Science and Computation Facility and its Support Team, in particular Mattia Pini, in utilizing the IIT Righ-Performance Computing Infrastructure, research was partially supported by the following sources: PNRR MUR Project PE000013 CUP 153C2200301 "Future Artificial Intelligence Research (FAIR)", funded by the European Union NextGGenerationFU, and EU Project ELSA under grant agreement No. 101070617. TAILOR, a project funded by EU Horizon 2020 research and innovation programme under GA No 952215; the Deutsche Forschungseemeinscaaatt (DFG, German Research Foundation) under grant number 417962828: the European Research Council (ERC) Consolidator Grant "Deep Learning 2.0" (grant no. 101045765). Frank Hutter acknowledger financial support by the Hector Foundation. The authors acknowledge support from ELLIS and ELIZA. Funded by the European Union. The authors gratefully acknowledge the Gauss Center for Supercomputing eV (www. www.:aaassscceeee reetre.eeeeeeeeeeeeeeeeeee.eee.e eu) for funding this project by providing computing time on the GCS supercomputer JUWELS Jüllic Supercomputing Center (JSC). The MATH-HARD dataset which use in one of our experiments was compiled from AoPS the AoPS Community, MATHCOUNTS, the MAA, the Centre for Education in Mathematics and Computing. the Harvard-MIT Math Tournament, the Math Prize for Girls, MOEMS, the Mandelbrot Competition, and the Institute of Mathematics and Applications. Views and opinions expressed are however those of the author(s) only and do necessarily reflect those of the European Union or the ERC. Neither the European Union nor the ERC can be held responsible for them.
which run largest experiments. This
Funded by European Union
REFERENCES
Simran Arora, Brandon Yang, Sabri Eyuboglu, Avanika Narayan, Andrew Hojel, Immanuel Trum- mer, and Christopher Ré. Language Models Enable Simple Systems for Generating Structured Views of Heterogeneous Data Lakes. Proceedings of the VLDB Endowment, 17(2)92--055 2023.
Maximilian Beck, Korbinian Pöppel, Markus Spanring, Andreas Auer, Oleksandra Prudnikova, Michael Kopp. Günter Klambauer, Johannes Brandstetter, and Sepp Hochreiter. xLSTM: Ex- tended Long Short-Term Memory. In Advances Neural Information Processing Systems. Cur- ran Associates, Inc., 2024.
Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the ability and limitations of transformers to recognize formal languages. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 7096-7116 16, 2020.
Satwik Bhattamishra, Michael Hahn, Phil Blunsom, and Varun Kanade. Separations in the represen- tational capabilities of transformers and recurrent architectures. Advances in Neural Information Processing Systems, 36, 2024.
Yonatan Bisk, Rowan Zellers, Ronan Le bras, Jianfeng Gao, and Yejin Choi. PIQA: physical commonsense in natural language. Proceedings of the AAAI Conference on Artificial Intelligence, 34(05):7432-7439 Apr. 2020.
Reasoning about
Nicola Muca Cirone, Antonio Orvieto, Benjamin Walker, Cristopher Salvi, and Terry Lyons. The- oretical foundations of deep selective state-space models. Advances in Neural Information Pro- 2025.
cessing Systems, 37:127226-
Peter Clark, Isaac Cowhey, Oren Etzioni, Tushar Khot, Ashish Sabharwal, Carissa Schoenick, and Oyvind Tafjord. Think you have solved question answering? Try arc, the ai2 reasoning challenge. arXiv preprint arXiv: 05457, 2018.

---

Published as a conference paper at ICLR 2025
Tri Dao and Albert Gu. Transformers SSMs: Generalized models and efficient algorithms through structured state space duality. In International Conference on Machine Learning. PMLR, 2024.
Gregoire Deletang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, et al. Neural Networks and the Chomsky Hierarchy. In The Eleventh International Conference on Learning Representations, 2023.
Ting-Hap Han Fan, Ta-Chung Chi, and Alexander Rudnicky. Advancing Regular Language Reasoning in Linear Recurrent Neural Networks. In Proceedings of the 2024 Conference of the North Amer- ican Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 2: Short Papers), pp. 45-53, 2024.
Daniel Y Fu, Tri Dao, Khaled Kamal Saab, Armin W Thomas, Atri Rudra, and Christopher Re. Hungry Hungry Hippos: Towards Language Modeling with State Space Models. In The Eleventh International Conference on Learning Representations, 2021.
Jean Gallier and Jean Gallier. The Cartan-Dieudon Theorem. Geometric Methods and Applica- lions: For Computer Science and Engineering, pp. 231-280, 2011.
Leo Gao, Jonathan Tow, Baber Abbasi, Stella Biderman, Sid Black, Anthony DiPofi, Charles Fos- ter, Laurence Golding, Jeffrey Hsu, Alain Le Noac"h, Haonan Li, Kyle McDonell, Niklas Muen- nighoff, Chris Ociepa, Jason Phang, Laria Reynolds, Hailey Schoelkopf, Aviya Skowron, Lintang Sutawika, Eric Tang, Anish Thite, Ben Wang, Kevin Wang, and Andy Zou. A framework for few-shot language model evaluation, 07 2024.
Angeliki Giannou, Shashank Rajput, Jy-yong Sohn, Kangwook Lee, Jason D Lee, and Dimitris Papailiopoulos. Looped transformers as programmable computers. International Conference on Machine Learning, pp. 11398-11444 PMLR, 2023.
Xavier Gonzalez, Andrew Warrington, Jimmy T.H. Smith, and Scott Linderman. Towards Scalable and Stable Parallelization of Nonlinear RNNs. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Albert Gu and Tri Dao. Mamba: Linear-Time Sequence Modeling with Selective State Spaces. In First Conference on Language Modeling, 2024.
Albert Gu, Isys Johnson, Karan Goel, Khaled Saab, Tri Dao, Atri Rudra, and Christopher Ré. Com- bining recurrent, convolutional, and continuous-time models with linear state space layers. Ad- vances in neural information processing systems, 34:572-585, 2021.
Albert Gu, Karan Goel, and Christopher Re. Efficiently Modeling Long Sequences with Structured State Spaces. In International Conference on Learning Representations, 2022.
Sylvain Gugger, Lysandre Debut, Thomas Wolf, Philipp Schmid, Zachary Mueller, Sourab Man- grulkar, Mare Sun, and Benjamin Bossan. Accelerate: Training and inference at scale made sim- ple, efficient and adaptable. https://
2022.
Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8: 1711, 2020.
Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the math dataset. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021.
Sepp Hochreiter and Jürgen Schmidhuber. Long Short-Term Memory. Neural Computation, 9()): 1735-1780) 1997.
John Hoperoft and Jeffrey Ullman. Introduction to Automata Theory, Languages, and Computation. Addison Wesley, 2001.
Roger A Horn and Charles R Johnson. Matrix Analysis. Cambridge University Press, 2012.
12

---

Published as a conference paper at ICLR 2025
Kazuki Irie, Imanol Schlag, Róbert Csordás, and Jürgen Schmidhuber. Going beyond linear trans- formers with recurrent fast weight programmers. Advances in neural information processing systems, 34:7703-7717, 2021.
Kazuki Irie, Róbert Csordás, and Jürgen Schmidhuber. Practical computational power of linear transformers and their recurrent and self-referential extensions. arXiv preprini urXiv:2310 1...i:2300.16076, 2023.
Mandar Joshi, Eunsol Choi, Daniel S Weld, and Luke Zettlemoyer. Triviaqa: A large scale distantly supervised challenge dataset for reading comprehension. In Proceedings of 55th Annual Meet- ing of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1601-1611, 2017.
Angelos Katharopoulos, Apoory Vyas, Nikolaos Pappas, and François Fleuret. Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention. In International Conference Machine Learning, pp- 5156-5165. PMLR, 2020.
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: 450-464, 1965.
Yi Heng Lim, Qi Zhu, Joshua Selfridge, and Muhammad Firmansyah Kasim. Parallelizing non- linear sequential models over the sequence length. In The Twelfth International Conference on Learning Representations, 2024.
Bingbin Liu, Jordan Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers
Learn Shortcuts to Automata. In The Eleventh International Conference Learning Represen- tations, 2023.
Colin Lockard, Prashant Shiralkar, and Xin Luna Dong. When open information extraction meets the semi-structured web. NATCL-HLT. Association for Computational Linguistics, 2019.
Ilya Loshchilov and Frank Hutter. SGDR: Stochastic Gradient Descent with Warm Restarts. In International Conference Learning Representations, 2017.
Ilya Loshchilov and Frank Hutter. Decoupled Weight Decay Regularization. In International Con- ference Learning Representations, 2019.
Oded Maler and Amir Pnueli. On the cascaded decomposition of automata, its complexity and its application to logic. ACTS Mobile Communication, 48, 1994.
William Merrill and Ashish Sabharwal. The parallelism tradcoff: Limitations of log-precision trans- formers. Transactions of the Association for Computational Linguistics, 11:531-545, 2023.
William Merrill, Gail Weiss, Yoav Goldberg, Roy Schwartz, Noah A Smith, and Eran Yahav, A Formal Hierarchy of RNN Architectures. Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 443-459, 2020.
William Merrill, Jackson Petty, and Ashish Sabharwal. The Illusion of State in State-Space Models. In Forty-first International Conference on Machine Learning, 2024.
Antonio Orvieto, Soham De, Caglar Gulcehre, Razvan Pascanu, and Samuel L Smith. Universality of Linear Recurrences Followed by Non-linear Projections: Finite-Widd Guarantees and Benefits of Complex Eigenvalues. In Forty-first International Conference on Machine Learning, 2024.
Denis Paperno, Germán Kruszewski, Angeliki Lazaridou, Ngoc-Quan Pham, Raffaella Bernardi, Sandro Pezzelle, Marco Baroni, Gemma Boleda, and Raquel Fernández. The LAMBADA dataset: Word prediction requiring a broad discourse context. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1525-1534, 2016.
Guilherme Penedo, Hynek Kydlfček, Loubna Ben allal, Anton Lozhkov, Margaret Mitchell, Colin Raffel, Leandro Von Werra, and Thomas Wolf. The FineWeb Datasets: Decanting the Web for the Finest Text Data Scale, 2024.
13

---

Published as a conference paper at ICLR 2025
Bo Peng, Eric Alcaide, Quentin Gregory Anthony, Alon Albalak, Samuel Arcadinho, Stella Bi- derman, Huanqi Cao, Xin Cheng, Michael Nguyen Chung. Leon Derezynski, et al. RWKV: Reinventing RÑNs for the Transformer Era. In The 2023 Conference Empirical Methods in Natural Language Processing, 2023.
Jorge Pérez, Pablo Barceló, and Javier Marinkovic. Attention is turing-complete. Journal of Ma- chine Learning Reseurch, 22(75):1-35, 2021.
Samyam Rajbhandari, Jeff Rasley, Olatunji Ruwase, and Yuxiong He. Zero; Memory optimizations toward training trillion parameter models. In SC20: International Conference for High Perfor- mance Computing, Networking. Storage and Analysis, pp. 1-16. IEEE, 2020.
Pranav Rajpurkar, Robin Jía, and Percy Liang. Know what you don't 't know: Unanswerable questions for squad. In Proceedings of the 56th Annual Meeting of the Association for Compulational Linguistics (Volume 2: Short Pupers), pp. 784-789, 2018.
Keisuke Sakaguchi, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. Winogrande: An adver- sarial winograd schema challenge at scale. Communications of the ACM, 64(9):99-106, 2021.
Yash Sarrof, Yana Veitsman, and Michael Hahn. The Expressive Capacity of State Space Models: A Formal Language Perspective. Advances in Neural Information Processing Systems, 2024.
Imanol Schlag, Kazuki Irie, and Jürgen Schmidhuber. Linear transformers are secretly fast weight programmers. In International Conference on Machine Learning, pp. 9355-9366. PMLR, 2021.
Jürgen Schmidhuber. Learning to control fast-weight memories: An alternative to dynamic recurrent networks. Neural Computation, 4(1):131-139 1992.
Daria Soboleva, Faisal Al-Khateeb, Robert Myers, Jacob R Steeves, Joel Hestness, and Nolan Dey. SlimPajama: A 627B token cleaned and deduplicated version of RedPajama, June 2023.
Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. What Formal Lan- guages can Transformers express? A Survey. Transactions of the Association for Computational Lingnistics, 12:543-561, 2024.
Yu Sun, Xinhao Li. Karan Dalal, Jiarui Xu, Arjun Vikram, Genghan Zhang, Yann Dubois, Xinlei Chen, Xiaolong Wang. Sanmi Koyejo, et al. Learning to (learn at test time): RNNs with expressive hidden states. arXiv preprint arXiv:2407.04620, 2024.
Matteo Tiezzi, Michele Casoni, Alessandro Betti, Marco Gori, and Stefano Melacci. State-Space Modeling in Long Sequence Processing: A Survey Recurrence in the Transformer Era, 2024.
Alexandre Torres. mamba.py: simple, hackable and efficient Mamba implementationn in pure PyTorch and MLX., 2024. URL httpps://gttuu. com/ alxndr TLA CaainddrrL/maama....mm py
Lewis Tunstall, Leandro Von Werra, and Thomas Wolf. Natural Language Processing with Trans- formers. O' O'Reilly Media, Inc., 2022.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, ukasz Kaiser, and Illia Polosukhin. Attention is All you Need. In Advances in Neural In- formation Processing Systems, volume 30. Curran Associates, Inc., 2017.
Songlin Yang and Yu Zhang. FLA: A Triton-Based Library for Hardware-Efficien Imple- mentations of Linear Attention Mechanism, January 2024. URL htttttts//gtthhit com/ sustcsong htt.///ashhhl wtw.///ss--inneer-ttttetee
Songlin Yang, Bailin Wang, Yikang Shen, Rameswar Panda, and Yoon Kim. Gated Linear Atten- tion Transformers with Hardware-Efficient Training. In Forty-first International Conference on Machine Learning. 2024a.
Songlin Yang, Bailin Wang, Yu Zhang, Yikang Shen, and Yoon Kim. Parallelizing Linear Trans- formers with the Delta Rule over Sequence Length. Advances in Neural Information Processing Systems, 36, 2024b.
14

---

Published as a conference paper at ICLR 2025
Songlin Yang, Jan Kautz, and Ali Hatamizadeh. Gated Delta Networks: Improving Mamba2 with Delta Rule. In The Thirteenth International Conference on Learning Representations, 2025.
Rowan Zellers, Ari Holtzman, Yonatan Bisk, Ali Farhadi, and Yejin Choi. HellaSwag: Can a Ma- chine Really Finish Your Sentence? In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 4791-4800, 2019.
15

---

Published as a conference paper at ICLR 2025
SUPPLEMENTARY MATERIAL
The supplementary material is structured as follows.
Appendix A contains additional details on the notation used, on Table on the relationship between RNNs and regular languages, on the assumption of finite precision, on the states, and on the function dec.
Appendices B and C contain the proofs for the theoretical results in Sections 4.1 and
Appendix D contains a theorem showing that a Layer LRNN having reflections as state- transition matrices can solve addition modulo m.
Appendix contains additional details on the experiments and additonal results.
A ADDITIONAL BACKGROUND
A.1 NOTATION
We denote with C, IR, N the sets of complex, real, and natural numbers, respectively. We use low- erease letters for scalar quantities (e.g. x E R), bold lowercase letters for (column) vectors (e.g. E R"), and bold uppercase letters for matrices (e.g. M E R=*d), Some functions with matrix (vector) outputs, such as and B [. are also bold upper (lower) case letters to emphasize fact that they output matrices (vectors). We use @ to indicate the element-wise (Hadamard) product between two vectors or matrices. We denote with ||0||| the Fuclidean norm of the vector v E IR". When M Radd || also refers to the Euclidean norm, corresponding to the largest singular value. The vector e, E I" is the i-th vector of the canonical bases in R", i.c. the one-hot vector with 1 only in the i-th component and in the others. We define the binomial coefficient for every k,j E N with j S as
-
k
k
= k(k - 1).............. (I - -j+11 11
=
j!
We also define for Boolean and æ E IR
1(s} = [1 if a is true
2
sign(x) =
if is false
<<<<0
We define sigmoid = 1/(1 + e) and softplus(x) = In(1 1111+00 e.).
We sometimes regular expressions (see e.g. (Hopcroft & Ollman 2001), represent their
responding regular language. So that e.g. (11)* = [1]]", where (11} is the set containing the
word 11 and is the Kleene star operation, is the language containing the empty word and all the
words with an even number of ones, while (1m)** = {1mm is the language containing the words with number of ones divisible by m since 1 indicates the word containing repeated m times. A language is star-free if it can be expressed with a regular expression that does not contain the Kleene star.
A.2 DETAILS OF TABLE
The Mamba recurrence in Equations and 4 (Gu Dao 2024) is applied independently to each channel of the input sequence. Expressing the full recurrence in the matrix-form of (I is
challenging, as would require concatenating the rows of the matrix He For simplicity. in Table write instead the recurrence for each of He. In particular, Let 2, E Rd be the input of W2 E Rdd Wi = (w),..., Wn) E x be learnable parameters,
the layer, WA E Rdxd Rn k. (kr,1..... .........he k.,.. E R be learnable functions of the input and A, softplus (aallussWaan (W...).
E
Then, if we set H,- (h.. h..). Raxd and Ho 0, we can write the recurrence for the
i-th row of H, and the output as
h = A,(x, (4 B((x)),
ÿ (H, q: W2 xx))
16

---

Published as a conference paper at ICLR 2025
where A, and (z,) are the matrices stated in Table | i...
Ax(x)) == Diag (exp - @ exp(wn,))) RRddd
(a(+))) A @ ay E IR
Alternatively, as done Yang et 2024b
Table 4), one could write the full matrix recurrence as:
H exp
1 exp(Wi)) (W)) @H,11 + (A ② x.)
A(me)
B(x.))
where 1 is the vector of ones. However, such recurrence is not in the form ① since have replaced the matrix matrix product A H with the clement-wise product A @ H,. Note that follow the implementation of ((x+)) used in the official Mamba codebase, which simplifies the expression originally presented in Equation 4 of (Gu & Dao 2024) as described by the authors in a GitHub Issue"
A.3 REGULAR LANGUAGES AND RECURRENT NEURAL NETWORKS
RNNs Can Recognize Any Regular Language A layer of general RNN can be formulated similarly to ①T just by replacing the linear state update with a generic transition function g as:
h = g(hh-1h xt), hg R...
Clearly, any FSA can be implemented by an RNN layer if g is sufficiently expressive to model its state transition function.
LRNNs Can Recognize Any Regular Language As explained in (Liu al. 2023 Appendix A.2) and in the proof of (Merrill et al.) 2024] Theorem 5), we can implement any FSA A = (E, Q, qu. 5), and thus recognize any regular language, using matrix-vector multiplication. As result, a single-layer LRNN by using one-hot vectors as the LRNN states and having boolean state transition matrices can recognize any language. More specifically, in [. we can set n = [Q), Ho O1,0..., ...0.....0. 0) and for any letter w E Σ, B (ww) =0 0 and A(w) E Raxn being the matrix with entries A ,4 = 1( q) ' Note that in such a construction, the matrix A(w) can have norm greater than one, and enabling the state-transie tran-trannstion matrix of LRNNSs to have norm greater than one can make the recurrence unstable and is therefore never done in language models (see e.g.
Table
A.4 FINITE PRECISION
For our positive results on LRNNS expressivity (Theorems and by finite precision we mean that since we have finite number of quantities involved in the computations, then there exists finite set D C. R that contains them and thus we do not require computations to be done in the reals but we can use D as datatype. In particular, D does not depend on the length of the input sequence. In practice, such data type is chosen beforehand, e.g. floating point numbers requiring given number of bits of precision, which may not capture all quantities in our constructions.
In our negative results of Theorems and insteed,, we can pick the finite set ID C R arbitrarily, e.g. floating point numbers, and we also make the use of the function cast IR + D, defined in ( that we extend to C by applying it separately to the real and imaginary part and to vector and matrices by applying it clement-wise. The cast function is used because some computations of the state of the LRNN will be allowed to be in infinite precision and then transformed to finite precision using cast as specified in the proofs. This function provides a simplification of the actual conversion that happens in practice.
We believe that the finite precision setup is not only realistic but also allows a better focus on the drawbacks of modern LRNN. Note that for Transformers, results usually rely instead on the weaker notion of log-precision (Liu et al. 2023), meaning that the size of ID grows logarithmically with the sequence length. This is mainly due to their limited expressivity compared to LRNNN.. We also note that concerning the snteetrranstion matrices of modern LRNNS (see Table D. the values at the extremes of the eigenvalue range are technically not included (because of the use of the sigmoid and softplus functions). However, since we are working with finite precision, we can still include them by choosing the appropriate datatype ID, which practice includes key values such as 0, 1, and -1.
htttps://git thw.. com/ statt-ttteeeeeeeee.eee spwces sauea/19
17

---

Published as a conference paper at ICLR 2025
A.4.1 INITIAL STATE, MATRIX-VALLE VALUED STATES, AND THE DECODER FUNCTION
When introducing the LRNN layer in ( we mention that A, B and dee are learnable functions. However, to learn the constructions in our theoretical results, we need also Ho S Cn to be learabll.. We do this only to simplify the results, since the same effect can also be achieved by using a special token S at the beginning of each sequence input to the model, called the beginning of sequence token and setting, Ho = 0 for each LRNN layer so that (x1) will have the same role as the learnable Ho in our constructions. This practice is standard and used in all our experiments.
While we mention that the states H, are generally matrices of dimension n. x d, for our theoretical constructions (excluding the first two theorems), we set d = 1, so that states are vector-valued. Hence, for the problems that we consider, we find that having a matrix-valued state (d > 1) brings no theoretical advantage, while it is very important for associative recall.
To compute the output ÿt from the state H, and the vector a; of an LRNN layer in I.. we use the function dec, to abstract away the computations that are done H, and Dt, since they not part of the recurrence. In this work, we do not consider the internal structure of dec, but it usually contains normalization and ford-forward neural network and it can approximate any continuous function.
In negative results on LRNNs expressivity in Theorems and 2 our choice of arbitrary decoder guarantees the stronger results. For our positive results instead, we either do not consider the decoder (Theorem recognize regular languages efficiently and with smaller LRNN state it is beneficial to have more powerful (non-linear) decoder, as in the case of word problems for cyclic or permutation groups. However, such a decoder may be hard to learn.
we make use of a linear decoder (Theorem 4. We point out that to
B PARITY AND MODULAR COUNTING PROOFS
We report the proofs for the theorems in Section 4.1
We start by defining the function cast R + D,
for finite set ID C R, which provides a simple model for the conversion of real numbers into finite precision representation.
cast(r) = min 2, Dmnn == arg min |a - z/- =ED
(4)
2ED
Note that Diin might not be a singleton. We naturally extend this function on complex numbers by applying it separately to the real and imaginary part, and then to complex-valued matrices by applying it element-wise. The following lemma is a key element of the proofs of Theorems and There, the sequence ag in the lemma takes the form of the imaginary or real part of the elements of the k-th power of matrix with real eigenvalues (\; will be eigenvalue), expressed using the Jordan canonical form. See Appendix B for more details on the Jordan Canonical Form. Intuitively, the lemma shows that if some of the x negative then for k large enough, ag in finite precision will alternate between two values. Instead, if the A are only nonnegative, an in finite precision becomes constant for large enough k.
Lemma 1. Let n, m E I and for every ls >> mn let
(+))) x
k
a3 = Σ c
with c, A E R. m. E m, S m, Vi (l.......,
m
then there exist To N such that for every lo 2 To there exist ā₁ 0g ID such that cast(az)) = ā1, cast(a22+1) 02. Furthermore, if X 2 0 for every E (I,...,n) n.), then cast(ax) āē = @2 for k k.
Proof. If c; = O for every i, or A; = 0 for every i, then ag O for all & and the statement is trivially satisfied. Without loss of generality we can assume that that c, * 0 and X # 0 for every i E {1...., n.), since for each i where this is not true we can remove the corresponding term in the sum (since it will be 0) and use smaller value for n. We divide the proof into two parts.
Positive powers: Assume that X; > 0 for all i E n... This yields that for every and every k>m, (k) A xm=m > O. Since the cast function is piecewise constant with finite number of pieces,
18

---

Published as a conference paper at ICLR 2025
can divide the real line into finite number of intervals where cast is constant. We now show that for large enough, the interval where aş belongs, and hence cast(a;), does not vary with k.
Without loss of generality we assume that for every i,j {L....,,.} n2 we have that (m,, Ac) of (my. X3), since otherwise can factor out (m.)) X and use smaller Note that (m) > x
(m,)) x for large k behaves like the function km XR, i.e. the product of polynomial and an exponential function of k. Without loss of gen- erality, we therefore take the order of the indices of the terms in the sum such that the functions ga are in decreasing order of growth:
k(k ((k-I)..((kan (k] x and hence g:(k)
my!
A Xy or A Xz. m, my
W;j:i> j.
By factoring out 91 (k), i.. the fastest growing term, from ag we get
m A xk-ms
k mi)
ag
x Th (c1 bk)
by
Co
k A
mm
A1
with lim 0y- = 0 and therefore, since for every i and every 1: > m. k ) k > 0 and c1 # 0, there exist k E such that for every k: 2 k sign(ar) = sign(c: + by) = sign(c1). Now let D = [=1..... za) with < 22 < < za and let yı -o,, Vd+1 oo and yı- = (zi- + 21//2 for E (2.....d) d). From its definition, cast is a piecewise constant function such that cast(z) 2 for every (y,, 31+1). We now consider three cases according the values of X and m1.
1) If A 1 or À 1, mi 0, then limp-soo ( (oh)) Xf x-mm oc and there exists K > k such
that for every & 2 k, either ak > ya (if sign(c:) = 1) or as < y22 (if sign(c1) = -1) and hence cast(aa) = ā E za].
2) If \1 then lime (m) ) A/-m- 0 and hence there exist e > 0, {4, .,. d). k k such that for every h: 2 k ag E Q S (yr, 1y+1). where Ω = (0, e) if sign(c) = and Ω = (-e, if sign(()) = -1 Therefore, cast(ax) = 2j for every 2 k.
3) If = 1, mm = 0, then $ ( k- = 1 for every k and hence (mi)
1: mi
a = c1 + bk.
by
x m,
with A < 1ii E .2,
2=2
Note that by has now the same structure as ag. just with one less term in the sum, therefore we can factor out the term (A²) X bm-m and, since X2 < 1, apply the same reasoning as for the second case (A1 1) to ei + by and prove that there exist > 0. j {l...., d). k k such that for every k 2 k we have that sign(be) = sign(c2), ag E Ω C (zz- M)+1), where Ω = (c1, e) if sign(c2) = and Ω = (-e, (1) if sign(c2) = 11 Therefore cast(az) = 2j for every l 2 k.
In summary, we proved that when A Z 0 for every i, there exist ā E D, k E N such that for every k 2 1: 0z a, which concludes the first part of the proof.
Some powers can be negative: Consider the general case where b E R can be negative. We can write
X ( Rms
as
ci mi
1=1
Since sign(x)22 and sign(z) (2) 26- m. do not vary with k we consider the two subsequences
13
(2k
02k
|&,
28-m,
4 = cssign()))) (A,)) (2. 28-
m4
(2k +
1
1
é c,sign ) 2k+1-
02k+1
m4
and we can apply the same proof as for the case when X > for every i to each of the subsequences above, which gives the final result in the case X; IR for every i.
19

---

Published as a conference paper at ICLR 2025
B.1 PROOF OF THEOREM I
The language (11)* contains all sequences with an even number of ones. An FSA recognizing the language, for the sequence 1 will output yk if l is even and yA = 0 if is is odd. Consider an LRNN with one layer in (1. We will prove that if ((1) has only nonnegative eigenvalues, then there exists a k > 0 such that for every k 2 k, the finite precision version of the state H₃ corresponding to the sequence 1& does not depend on l and is equal to H. Hence, no matter the choice of dec, also the finite precision version of ÿk will not vary with k and thus for some K' 2 k ÿr * k' mod 2 = yk.. An inductive argument can then be used for the case of LRNNs with multiple (finitely many) layers, using the fact that the input of the next layer will be constant for large enough, as the input of the first layers.
By unrolling the recursion in we obtain a closed-form expression for the state
(1 A(a2)
k-1
k
H = Σ II f=1+1
B(ær;) +
II A 1=1
Ho.
where we set 11 = I to avoid clutter. We follow Merrill et al. (0244) and make the simplifying assumption that finite precision the state at time & is computed by first evaluating all products involving the matrices A(x,) separately and in infinite precision, followed by casting them into finite precision, and finally executing the sum also in infinite precision and casting the result in finite precision. This avoids having deal with the individual matrix sums and products in finite precision, which would break associativity and be harder to analyze. Hence, if we set 2 ... Fg 18, get the following exact and finite precision expressions for the state at time k.
k-1
H Σ +
H = cast Σ cast (A(1) + cast (A(1)*
where cast, defined in 4 is an operation that converts matrices with complex values element-wise into finite precision by e.g. separately converting real and imaginary parts.
Using the Jordan canonical form theorem (see e.g. Horn& & Johnson 2012 Chap. 3.1), we can write A(1) = PJP-1, where J is block diagonal made of the Jordan blocks JI...., J. with s S n, J. E R and with corresponding complex eigenvalues A1... (with multiplicity taken into account). Such decomposition is useful because it allows, for h 2 max; ki 1, to write
X
( x X
(1)
k
k
(
A(1)* P J
Then, from the structure of the Jordan decomposition, the imaginary and real part of each element of the matrices A(1)* (1) and A(1)* Ho will be a linear combination of elements of the Jordan blocks taking the same form of aş in Lemma [] Therefore since A 2 0 for every i, we can apply Lemma | component-wiss and conclude that there exists T E N. C E Caxd and D E Cuxd such that for every l 2 T, Č₁ cast(A(1)* B()) Ö and D (1)) Ho) D and hence
r-1
H 1 = cast
1=0
Note that only the matrix kō varies with A and for large enough k, the real and imaginary parts of each element of kC will be either 0 smaller than mingeR cast(x) or larger than max.eR cast (x:). Therefore, we obtain that there exists H E aoxd and & 2 such that for every k 2 1o we have H H. which concludes the proof.
20

---

Published as a conference paper at ICLR 2025
B.2 PROOF OF THEOREM! 2
One Layer Let HA and ÿ := cast(dec( Tx)) be the finite precision versions of the state H and (scalar) output of one-layer LRNN on the input a -... 1 Let also y/ 1 mod m = 0} be the correct output recognizing the word æ. We will show that if the assumptions on the eigenvalues are not satisfied, i... if for any 2, every eigenvalue of A(x) is real, then there
exist H1, H2 C" 91, D2 E I2" and T E N such that for all k:
2
H if mod 2 = 0
if mod 2 = 0
H =
Uk
(5)
H otherwise
1/2
otherwise
where without loss of generality we take 71 3/2 E {0.1}. If Ø1 1/2. then, similarly to parity, Dx
1 for all k >> while since m > 2, k mod m = m--11 1. then 1 -/++11 + yı 0. Otherwise
Ø1 + 1/2 then if we assume that mod d = and ÿı: = y/ = O, then = f/++1 * yh+ since >> 2. This will prove the result for one-layer LRNN. Then, we will proceed with the proof of finitely many layers.
To prove 5 we set
H₂ = cast Σ cast (A(I) + cast (A(1)* Ho)
cast
and proceed similarly to Theorem Indeed, using the k-th power formula for the Jordan Decompo- sition of the matrix (1) with eigenvalues 11y.---As,, the imaginary and real part of each element of the matrices A(1)*B(1 and A(1) Ho will be a linear combination of elements of the Jordan blocks taking the same form of ag in Lemma [ Therefore since our assumptions with L = imply that
X; R for every we can apply Lemma 1 to show that there exist 7 E N. C₁ C2, D,, D1,D2 Caxd such that for every l 2 T we have
[C i mod ==1
D2 if mod 2 D2 k mod
C2 == (1)) B)
D =- cast(A(1)**
Cc2
if mod
Finally, if for simplicity we consider 7 mod 2 = 0, we have that for 2k 2T
2 (k - T ; +1) 02 (k- 01-2) DD
H2 cast
Har+1 cast
Σ C
k r う/ + 1) (C2 + +c)
where by factoring out i inside cast, note that for large enough k the real and imaginary parts of each element of the matrices inside cast will be either constant, smaller than min cast(r)) or
larger than maxzeR (2r). Thus there exist HI, H₂ E Caxd and 2 such that 5 is satisfied, concluding the proof for the case of a single layer.
Multiple Layers Note that for one layer we have two subsequences (one even and one of odd elements) of the output sequence ÿ1 .2.... converging after finite number of elements. This means that there exist a, b E IR such that for all k > & we have
g2k+1 = b. Now, consider an additional layer that takes as input m12) (2)
122 =
(2) with (:
x
ÿ: and outputs
as
H A (2)
(x (x
H (2) + (x) (2), y dec (2) (H o (2)
Without loss of generality, assume for simplicity that ie 1 and that (2) and a (2)
2k+1 = for
all k. If we set
A == (a),
Ag A (2) (b).
B = B (a))
B₂ ((2)
C = A,A
C = A, B
21

---

Published as a conference paper at ICLR 2025
then write the states of the second layer at even indices as
(2) H
A, A, 2k-1 + Bi = A
(2)
A2 28- A, B2 - B
24
k-1
= H 2(k-1) + C2 Σ
2
CH
Furthermore, for the states at odd indices, we have
k-1 1
H (2) 2k+1
A2 A 2h = Σ
(2) B2
A2C Ho + B2.
We notice that the sequences H () and H
26+11 are in form similar to Hę of the first layer. If the assumption on the cigenvalues of the state- seatetrranstion matrices of the second layer does not hold, this means that for all æ; y each eigenvalue of A (xx (2) (y). including C₁ is real (but possibly negative). Therefore, we can proceed similarly to the case of one layer, i.e. using the powers of
()
the Jordan canonical form of C1, to show that if we let H2 and H 2k+1 being the finite precision
counterparts of (2) and ( 2 then there exist H (2) H (2)
H (2)
H E Caxd hg 2 0 such
26
that for every k: 2 k
H (2)
if k mod 2 2=
H (2)
if mod 2 0
2k+1
H K mod 2 1
H if mod 2
Therefore, for k 2 k2 the function ko + (2) k will be periodic with period a divisor of four and hence no matter the choice of (2) also the function & + Uk will be periodic with period a di- recognize the language (1m)** only when m = 2, or m = 4, since those are the only cases where k + ys has a period which is a divisor of 4. Thanks to the assumption on the eigenvalues of the products of state-transition matrices, can extend this argument inductively to the case of an LRNN with L layers. In particular, for the i-th layer, the induction hypothesis is that we assume i + z mapping & to the k-th input to the layer, to be periodic with period divisor of 2 for A large enough. Hence, there will be 2 sub- sequences of states, each containing powers of the product of 2 state-transition matrices. From hypothesis the eigenvalues of products of state-transition matrices, such product will have only real eigenvalues and hence each subsequence will have 2 converging subsequences resulting in A + (( and consequently k + g!¹ and hence k ++ 2 (i+1) for l large enough, being periodic with period a divisor of 2'. Therefore, for the L-th layer, there exists kr. 2 0 such that for every divisor of 24 and thus it can recognize the language (1m) only when 2 mod m = O, which happens only when there exists p < L such that m 2 and hence y is power of two, ending the proof.
visor of 4. Consequently, with two layers
1,
(6)
2 kr, the function k- - (((4) is periodic with a period which
C PRODUCTS OF GENERALIZED HOUSEHOLDER MATRICES PROOFS
We provide proofs for the results stated Section 4.3 Before that, we illustrate how a linear RNN with one layer and state transition matrices that are products of 2 Householder matrices can count modulo m..
C.1 PRODUCTS OF TWo HOUSEHOLDERS AND MODULAR COUNTING
Counting modulo m can be achieved by rotating a vector in R2 by an angle of 2nt /m radians, and express rotation matrix as product of two reflection matrices, which are GH matrices with eigenvalues in {-1, 1} (see Appendix C.I). Inded, for any m E N there exist unit norm vectors 11, U2 I2 such that
R(0)= == cos 0
sin 0 cos 0
2T ] - 20l0 (I 2020.), 0
sin 0
m
22

---

Published as a conference paper at ICLR 2025
If we set the state-transition matrix in 1 to (() = R(0), an LRNN with one layer can count modulo m, since if we also set Hu = (1 and dec ()) = arg max, D H. with D; = R(10) Ho for all i {O,................ .......,, 1), then for the imput 1' and since R has period 2n, we get
Dr dec H 1) dec(((()) Ho, 1) dec ( 1) mod m.
C.2 PROOF OF PROPOSITION
First item It can be shown by noting that if C E Mf((-1,1), then ||C]| < and using the sub-multiplicative property of the Euclidean norm, i.c the fact that ||AB||| S |||||
Second item Note that any real matrix has a singular value decomposition. Hence we can write
M = USV
with U, V& E Rax" orthogonal and S Diag( Tn) with o; E [0, 1]. since [| S 1.
follows from the n-reflections theorem" that we can write U and V as either the identity I e
MT ((1)) or the product of at most reflections, each of which is in Mf((-1)). Hence U, V E
Ma ( 1)). We can also write the matrix S as the product of n GH matrices as
S == S Sn, S. -- --))ee
where e; is the i-th element of the canonical basis of IR".. Hence, S E (M 1)). The proof of the first part is concluded since wrote each of U, S, V as a product of at most GH matrices. If M is orthogonal, we apply the n-reflections theorem directly. We also note that M = P E (0. ] with P being a permutation matrix different from the identity, it can be written as products of at most n 1 swaps, i.e. permutation matrices permuting only two elements. Therefore we have that there exists an integer & S n 1 and indices .1...., 2 and Jk such that + ji and
1/v2 if
k
P= II Pude Pvj = (1 - 220 1=
Uaft =
1/V2 ifl=j
0
otherwise
where we set Vij = (UszI...., Uign). Note that since ||:;y|| = 1, P.j E MM(((11) with & S n. For the the case where M = I we can use the fact that I (MT(())).
Third item Let N = C2C2 ... C E MM((-1,1), with C, = 2, with || 1 and 33 E [0, 2). If N I the statement is satisfied, otherwise, let V = span/z; i (1.....k) k] 8, > 0}. Any unit vector v E _R" can then be written as v = V1 + U2 with t1 E V. v/2 E V and 1 < 1. Now, if
0, then Nu v. and hence v is eigenvector with eigenvalue 1. Instead, if 02 + 0, then there exists i' E fI.....,k) .b (we take the largest one) such that Br E (0. 2) and (v )x)² (v zz )2 E (0, 1]. Therefore, if 8' < k then either B, 0 or 23 e 0 so that
C,v= for all j (i' + 1, ........... k). Moreover, we have that
|| = | 8,z2,2, 01 = B2 - (B:(()) T x2)² <1,
where the last line comes from the fact that min x=2 x) = 0 and only reached at x and x 2, while Br 20, Therefore, since for every i, ||C,|| < and the Euclidean norm is sub- sub-multipliattio we have
|| N =
C.. < C1 || ... |Capll <.
Therefore, if e is also an eigenvector with eigenvalue E C, then |No| = | < 1. Hence, we proved that for every eigenvector with eigenvalue À either À = 1 or |X| < 1.
remains to show that all cigenvalues of N E MM 1)) are in [0, 1]. From the assumptions N = C, C2 with C1, C2 symmetric and positive semi-definite, therefore C₁ has unique symmetric and positive semi-definite square root ///² such that c//² c /2 = Ci. If C2 non-singular (invertible) then
C₁C₂ = C C C/ C
This is a specializaion of the Cartan Theorem to RM see Thenrem in wttptttpps//cm /ala::/faaee //acu//////uyy. htt.eee//klaainrrhogooooo pdf for proof
23

---

Published as a conference paper at ICLR 2025
Thus, C2 is similar C2C// and shares its eigenvalues. Moreover C 1/2 C2C is sym- metric positive semi-definite (having real nonnegative eigenvalues) because Cf 2 and C2 are sym- metric and v C/
C2= 2 with 2 = -l/²0 since C2 is positive semi-definite. Instead, if C is singular, for t > 0 the matrix C1 + +I is positive definite and non-singular. Hence (C1 + has real and nonnegative eigenvalues. Since C2 lim + (C2) and the eigenvalues are a continuous function of the entry of the matrix, C₁ C₂ has positive real eigenval- ues, Since the modulus of any eigenvalue is smaller or equal than the euclidean norm of the matrix, which is smaller than one from the first point of the theorem, the statement follows.
C.3 PROOF OF THEOREM 3
We first recall the notion of group isomorphism. Two groups (G,*) and (H, where G. H are the sets and * and are the associative operations, are isomorphic, there exists a bijective map f G + H such that for every y E G, h E H
f(g * h) = f(g) f(h).
We view the LRNN layer in 1 as the automaton Alin = (E, H. Ho. ) where dna H w) = A(w) H + Bw)), which is extended in the usual way, and H {dtin (inn(H (Ho: ()) w ). Since we assumed that ((A) is a group, from Cayley's 's theorem we have that it is isomorphic to subgroup of Sn, which is the set of permutations on a set of n elements. Furthermore, each element in S, can be represented as an n X n permutation matrix. Since in general n + [Q), we cannot let H to be a set of one hot vectors each corresponding to states in Q. Instead, we let Ho = (l,..., n) P c {0, 1) jaxm be the set of permutation matrices and set B = 0 and A : E - P to be the function mapping each letter w E Σ to the permutation matrix corresponding to 5(-, m²) With this choice we
can see that the function f T ((Aii)) - T(A) such that (- w)) 5(-, w) for every w E" is one-to-one (bijective), and from our choice of Ho. the map / T (AAin) + H such that for every w Σ', h(Biaa w)) 6umm (Ho, w) is also bijective. Moreover, the map ø (TA)) - Q such that 6(5(,, w)) = 8(qu, w) is surjective because without loss of generality we can consider states that are only reachable from the initial state qo, i.e. Q {ō(go, w) w E Σ*} ). Hence if we set = @o o f o h-1 then H + Q is surjective and for every w E E and H E H we have that
g H, w)) = ( H), w)
Thus, we have shown that such an LRNN implements A and does so with finite preci- sion because the entries of all vectors and matrices are bounded integers. Moreover, Let k maxwes Egeq 1[0(q, w) # q} = max En 1((((w) Ho); = Ho,3 be the maximum num- ber of displaced element of the permutation associated with the alphabet Σ. Then, this means that each permutation can be written product of at most k permutations of two elements. Hence, for every w E Σ, A(w) E Mf
in addition there exists m E N such that T(AA is isomorphic to a subgroup of the cyelic group Zn.. with elements {0..... ...
1}, we can modify the construction above to use smaller dimension. If m = 2, then Eg has elements {0, 1}, and A implements the parity automaton. Thus, we can set Hu 11 A()) = 1, A(1) -1 and g(1)
1 while g(-1) = O, which means that we can use a scalar recursion. Otherwise, if m 2 3, we can modify the construction above by setting Ho (1, and, if for simplicity we assume Σ E {0, (O...., m 1}. for every E Σ we let A(w) be the 2 x 2 rotation matrix corresponding to 5(,,
cos O., sin Onn sin Ow
2Tw
A(w) (w) = R(Ow) =
0..
cos On
such that R(0w.) E (2((-1)) (from Proposition
This concludes the proof.
C.4 KROHN-RHODER THEOREM
Before presenting the proof for Theorem 4 provide the statement for the landmark result of Krohn-Rhoder (Krohn & Rhodes 1965). after giving the definition of the cascade product of two FSA.
24

---

Published as a conference paper at ICLR 2025
Definition 1 (Cascade product). Given nwo FSA A= (E, Q.900 8) and B (Q Q', 4/ 8'), we
q0.
define the cascade product FSA as C = Bo A= (Σ, A= Q', (90. 80), 8") where for any w E
(' w) (8(q,w), 5(9', (q. w))
Theorem IKrohn-Rhodes Theorem 4 in Maler & Pnueli (1994)) For every FSA A =
(I, Q, (0,0) there exists 1 2 and cascade product FSA C A ..... A
(E,Q², 96 5%)) with A = (EW, , " _,)), with |Q(0 S [Q), and a function W Q² (8)
90
Q such that for any E E", 8(go, w) -W(6* (40" ( .w) and each A is permulation au- tomaton, which means that for every w0( e E(), (1 is either a bijection (i.e. permulation
over Q) or constant, ie, ò(, w()) = E Q
C.5 PROOF OF THEOREM 4
We apply the Krohn-Rhodes theorem (Theorem 5 to write A as the cascade product FSA
A o ...... o A()) with each FSA A(() = (M(), Q0), 40 5(0)) being permutation-resee and we show how the LRNN can implement by first showing how its i-th layer, with the structure in can implement (46),
Let n | and without loss of generality assume that E {1,2..... |E|} and Q( {1, .n, n with (t) = 1. For every w E ()() we set A (w) E {0, 1j"xn, Bl0 E {0, 1)3"
such that for every 9.9 E Q()
(9) (w)g'' = 160 w) = d/), (w) =
( w) is bijective, or if 800 (., w) = ((w).
A (9) (w) p' 0,
(w) = 1(1' = a(w)},
Then, for every word (i)) = w(t ... w E E00, we set g : R + R, such that g(x) =
(
m)) Tx x and
H = A 10 (w) (1) H 1-1 + (w!
(1)
H = (1,0. 0) ERT ( (ab))
y00 = dec (1) (H w
= (o(H)) (1) w/
10 w ()), w()
So that such construction implements A In addition, by letting w wi input to the LRNN, i.e. w/ wy, and setting the output of each layer as the input to the next, i.e.
E Σ* be the
(i- 1) for 2 2, for the output of the last layer we get w yj
3 ()) dec(*) w!("))
(g))) (a) w w())), 3r 1)
(8))) (o) w ) 16 (1b (s-1) w w(--1)) 11 (0-2) (1)
= (g()) (e) w (*))
80)) (4u w) w.) E N
(s) where we removed the nested parenthesis for simplicity. Hence, the first s elements of yt are exactly the output of the cascade FSA C. Note that our construction can be implemented in finite precision since we only used matrices/vectors with entries either in {0, 1}. requiring only one bit, or in Q() N, that can also be implemented using finite precision with [Q(*] integers, requiring loga( ( (Q(0) ) bits. Also note that we can exclude we from the output y! (s) by changing (s) to bring
the dimension of the output, end hence the width of the LRNN, to N
It is also the case that ||A < 1 for every
Σ since A (0(ww) (w) is either a permutation matrix (I) (w)) = ) or the zero matrix (| (w) = 0). Also, for every permutation matrix
jxn P E (0. 1 which permutes only & S n elements we have that E (p-1((-111))
Furthermore, for the zero matrix, we have
0
II (T e.e)) E (M(())) 1=1
It follows that (w0) E (1-111 for every E (1,...,8) and w E E00
n
25

---

rotation (since Published as a conference paper at ICLR 2025
D LRNNS CAN DO MODULAR ADDITION USING ONLY REFLECTIONS
In this section, we explain how an LRNN with two layers and using only Householder state transition matrices (reflections) can compute addition modulo m E N, ie it can map words -i,-... F with I; E {O..... m 1 into yt (Ei= Fi) mod m for arbitrary t N. This corresponds to solving the group word problem associated with the cyclic group Σ. We note that our modification of DeltaNet, namely DeltaNet [-1,1] 1] can therefore solve addition modulo m with 2 layers.
If the state transition matrices be generic rotation matrices, then LRNN can perform addition modulo m using just one layer by mapping each element of Zm to the corresponding 2 x 2 rotation matrix shown in Appendix C Such construction requires number of states for the LRNN equal to m, i.e. the number of elements the group Zm. However, since here we assume that state transition matrices are reflections, we cannot map each element of the group
those are a product of 2 reflections) and our construction for the LRNN will require two layers.
Specifically, the first layer will count modulo 2, i.e. it will output the sequence yi " Vi (1) where y; (1) (I;; i mod 2). while the second layer will have 2m states and will use two different reflection (1) matrices for each group element, depending on the value of Vi.2 i mod Formally, we have the following result.
Theorem 6 (Modular addition with reflections). An LRNN with two layers in the form ①.. where A IN- - {-1} for the first layer and A IR2 - -M for the second layer, with Mi defined in (3), can perform addition modulo for any E N. In particular, the LRNN will have 2 scalar states in the first layer and 2m states, each being a vector in IR?,, in the second layer.
Proof. The first layer of the LRNN will implement counting modulo follows.
0 =0, 0, n.()) = - + 1, _ ( (h,, ..)) = (atz, he).
We note that the state-transition matrix (the scalar -1) reflection since {-1} = Mi(--1)). For the second layer, we have instead
(2)
(1,0)T, 1o(2) A (v) (2)
yiah dec! (1(²)) 1,, ))
ho
(11 (1,,, 922
sin 019 922)
A (1) = ((((1), (((()118))) sin 0111 M2)
- cos (811 122
dec (2) (), y) arg max max(c, h, d,
mE(0....m-1)
where y (y1, M2) T (0, .... 1- 11 {0, 1}. H(a) is the 2 2 reflection matrix that reflects all vectors by a line having an angle of a with the line passing from the origin and the vector (1, 0) and 8 {0. {O..... m 1} {0, 13 + determines the angle of the reflection and is defined as
8(i, 1) (1 26)
((1,0) = (1 28)x
for all i E (0....
- 1}.
Moreover C = (co..... cm-1) } and D = {do- dm-13 are the two sets of states corresponding to reflections and rotations respectively and are defined
dg ho
(2) (1, co (T/m))do
C, = R( (1--2i//mo 2ir/m)co for all e {O....,m m m- 1}, where R(3) is rotation matrix with angle 3 R.
d, = R-2iiiz//n
Let at y E R, the following are standard identities of products of 2D rotations and reflections. R(a) R(7) = R(a + +7), R(o)H( = H (a +) From our choice of 8, d; and c, using the identities above and the the fact that R is a periodic function with period 2n we have that
H(a) (7) = R(a y),, H()) = H (7 - a).
H (O(i, 1))d;
H (22r
(O(j, 1)) R(2in/m) (mmmmm)((mmmmee))
=H(O(j, 1)) ( (0(i, 0))co
(6)
-R(O(j, 1) 0(i, 0))co
- -R(-2(i ( +j)m/mmco Ci+j mod ms
26

---

Published as a conference paper at ICLR 2025
and similarly
((0(),0) R(
((((), 0) ())))((((///))) 2it/mmm H (TT mo
-H(O(j, H) 1)
(7)
=R(0(j,0) - ((i
-R(2(i + j)/m/m/ do = d3+j mod ms
for every i,j E {o,..... -... 1]. We will now prove by induction that
ng Cy. if mod
(8)
dy if mod
where we recall that y; = { j= 13) mod m and that, by definition, h = do and h (0( i mod 2)) since (1) (zi, i mod 2). For the base case we have that
h ()) H(0(z), 1)) (2) H(() d) Cx₁ mod m Cy:
h2 (2) (( 0) ( 02 mad = dzitzz mod = d22
where we have used (6) and 77). As induction hypothesis, suppose that for i 2 2
h
(2)
Cy. if mod 2 = 1 dy if i mod 2 0
then, using again (6) and 7 obtain
H(0(a 1))h (2) H(0(1:41: 1)) C2:11 mod m Cys11 if mod 2 = 1
h (2)
H(0 0)
(2) (0(T:+1 0)) = dr te mod = d if mod =
which completes our proof by induction yielding 8). Finally, using the definition of de 8 and
as long d, + cj. d, # dj and c, # Cj for every i, with # j. which is guaranteed by our choice of 0, we have that dec (2) (h Yr:
(2) (1) (Ej-1 x.) mod m y/. ending the proof.
E EXPERIMENTS
E. CHOMSKY HIERARCHY
Here, we provide details on the formal language tasks and experimental protocol of Section 5.1
E.I.1 DETAILS ON THE EXPERIMENTAL SETUP
LikeBBcck et al. (2024). we trained each model with sequence lengths ranging from 3 to 40 and eval- uated on lengths from 40 to 256, understand the length generalization capabilities. We compared mLSTM and sLSTM with two models: Mamba (Gu & Dao 2024) and DeltaNet (Yang et al. 2024b). Moreover, also include Transformer (Vaswani al. 2017) baseline. For parity, all models con- tain 2 blocks (layers), with 4 heads for the XLSTM and DeltaNet models. We set the embedding and heads' dimensions 128. For Mamba and DeltaNet, we also enable the 1-D depthwise-separable convolution layer with kernel size equal to 4 after the query/key/value projection. For modular arithmetic, we increase the number of layers former, Mamba, and DeltaNet, while for mLSTM and sLSTM we decrease the embedding size and number of heads to 64 and 1, respectively, as well as use a standard initialization for the bias param- eters. We train each model using AdamW (Loshchilov & Hutter, 2019) without gradient clipping, using different learning rates (le-2, le-3, 5e-4 le-4), with 3 different seeds each. We pick the best based the median of the 3 seeds for every learning rate value. We use a batch size of 1024 (except for mLSTM, where we use 512 due to OOM error) and a cosine annealing learning rate schedule (Loshchilov & Hutter 2017) (minimum learning rate: Ie-6) after 10% warm-up steps. The weight decay is set to 0.1 during training. We train on every task for 100k steps in total. At each training step, make sure generate valid random sample from the task hand (see below).
and use gradient clipping norm of 1.0 for Trans-
27

---

Published as a conference paper at ICLR 2025
Table 5: Performance comparison of various recurrent models on regular and context-free language tasks. recurrent models on formal language tasks. We report the median = median absolute de- viation (left table) and best score (right table) of 3 independent runs with different random seeds. Scores represent scaled accuracy, with 1.0 indicating perfect performance and 0.0 random guessing. The positive impact of allowing negative eigenvalues ([-1, 1] range) versus restricting to positive eigenvalues (0, 1] range) is evident across different model architectures.
Mod. Arithm. (w/ brackets, mult)
Mod. Arithmetic (w/o brackets)
Mod. Arithmetic (w/ brackets)
Parity
Transformer
0.003 0013
0.018 cow
0.064 0003
0.025 + 0.00
mLSTM
0.018 + 000
0.027 + 0015
0.114 + 0000
0.034 t 000
sLSTM
1.000 + 0,000
0.124 + o.w
0.163 + 0015
0.153 + 0000
Mamba
0,000 0.000
0.066
0.116 0007
0.072 +
Mamba 1, 1]
1.000) 0.00
0.214
0.098 0.09
0.126 +
DeltaNet [0, 1]
0.010 + 0.ons
0.214 + c.06
0.162 + 0015
0.113 + 0.009
DeltaNet 1, 1]
0.999 + 0.005
0.826 + 0.046
0.227 = 0011
0.129 + 0.016
E.1.2 DETAILS ON THE EVALUATED TASKS
In Section 5.1 we conducted empirical evaluations on tasks -parity, modular arithmetic without brackets and with brackets- from various levels of the Chomsky Hierarchy, proposed by Deletang et al. (202)) and similarly used in XLSTM (Beck et al. 2024). Details for each task are given below, where |X] is the vocabulary size and AcCrand is the accuracy of random guessing:
Parity (Σ) = 2, AcCrand = 0.5). The parity y1 E 1) of a sequence of ones and zeros a I1 ......2 3t E {0, 133 is equal (resp. 0) if the total number of ones in the sequence odd (resp. even). It is equivalent to addition modulo 2, it can be computed by summing all previous values and then using the modulo 2 function as y/- (Ei= 2;) mod 2.
Modular Arithmetic w/o Brackets (22 = 10, Accrand = 1/5). Given a set of special tokens set Σ Σ, (0, ...., - 1] and y is equal to the result of the operations modulo m in the sequence x = I1, It with 23 E Σ. In our
Σ, (+,- , =, [PAD]} and a modulus 2
experiments m 5. An example sequence is follows:
2
2 [PA]]
Modular Arithmetic w/ Brackets, ( 12, AcCrand 1/5). Same definition the modular arithmetic without brackets with a set of special tokens Σg = {+,
=,),), (, [PAD]] In our
experiments m 5. An example sequence is follows:
() + ((3 (-3)) + ((11 + 4))) [PAD]
F.2 STATE-
E.2.1 DETAILS OF THE EXPERIMENTS
For the experiments in Section 5.2 map each element of the group Sş to integer from 0 to 119. where 0 corresponds to the identity permutation, and then construct inputs and output sequences of integers æ ...... Iy and ./..... ye as follows
Sg We sample 2; uniformly at random from {O..... 119). ys is computed as the product of the permutations corresponding æi.... 24 applied in order from
Ss only swaps As Sş but x; is sampled from the permutations that permute up to two elements (swaps and identity).
Sg swaps, 3-permutations As Sş but r; is sampled from the permutations that permute up to three elements.
S₃ 4 tokens per transition i mod 4 = 0, then x, is sampled uniformly at random from {o..... 119), otherwise F; 120 (special token). For i >> 3, 3/+3 is the product of the permutations corresponding to II,..., where 120 is treated as the identity permutation.
y/ = 0 for E (1,2,3)
28

---

Published as a conference paper at ICLR 2025
Purity
Mod. Arilhmetic wio Brackets
Mod. Anithmetic wi Bracket
1.0
1.0
Sealed Accuncy
0.5
0..5
0.5
Trameformer
0.0
0.0
0.0
10
10²
10
10
10'
10
Sequence Length
Sequence Length
Sequence Length
(a) Transformer
Parity
Med. Arilhmetic wib Brackets
Med. Arilhmetic Brackets
1.0
1.0
Scaled Accurncy
0.5
0.5
0.5
mLSTM
sLSTM
0.0
0.0
0.0
10
10
10'
10
10'
10y
Sequence Length
Sequence Length
Sequence Length
(b) mLSTM and XLSTM
Parity
Mad. Ariflmetic Brackets
Mod. Arilhmatic Rrackets
1.0
1.0
Sealed Acquracy
Eigenvalue
0.5
0.5
0.5
Range
10, 11
[-L. 1]
0.0
0.0
0.0
10
10
10
10'
10
Soquenee Longth
Soquence Longth
Soquence Length
(c) Mamba
Parity
Mod Arithmeric win Bricktts
Mod. Antimmtt Brackets
1.0
1.0
Scaled Accurney
Eigenvalue Range
0.5
0.5
0.5
[0. 1]
[L. 1]
0.0
0.0
10
10a
10'
Sequence Length
Sequence Length
Sequence Length
(d) DeltaNet
Figure 6: Performance (scaled accuracy) vs sequence length of Transformer, mLSTM, sLSTM, Mamba and DeltaNer variants on different formal language tasks. Trained on sequences up to length 40 (dashed vertical red line). At test time, we sample uniformly at random 8192 sequences with lengths between 40 and 256. The curves show the mean and 95% CI. Note, that the Transformer model fails to length extrapolate, but performs nearly perfectly within the training context length.
For each setup, we randomly sample 1.6M examples for and 40K examples of length 500 to con- struet the train and test dataset. We note that we are using a substantially larger training set com- pared to (Merril & Sabharwal 2023), to reduce the chances of overfitting. We run 3 seeds for each method, changing the network initialization and sampling of the minibatches. The train and validation datasets are kept the same across runs.
29

---

Published as a conference paper at ICLR 2025
Sg only swaps
S. swaps, 3-perm.
Sequeee Accuracy (5)
DetaNeet [0.1] (1L)
Seguence Ascuracy (%)
DelaaNet (-L)
DelaaNet [0. (5L)
DeltaNet (SL)
Mamba [0.1] (SL)
Mamha [-1,]] (SL)
Full matrix simple
20
10
10'
10
10"
10'
10
Sequence Length
Sequence Length
Sg tokens per trans.
S
100
Sequence Accuracy (%)
Sequence Accunicy (%)
80
60
40
20
0-
10"
10"
10"
10"
10'
10"
Sequence Length tokens)
Sequence Lengsh
Figure 7: Validation sequence accuracy across different lengths on S3 after 100 epochs of training (3 seeds). The dashed vertical line indicates the sequence length used during training. Each method labeled with name, eigenvalue range, and number of layers. The dashed vertical line indicates sequence length used during training.
We train all models using AdamW with weight decay 0.01, learning rate 0.0001, gradient clipping to 1.0, and a batch size of 512. Both DeltaNet and Mamba models use an embedding dimension of 128 and heads for DeltaNet. In the case of DeltaNet, we not use 1-D convolutions for these experiments. Other parameters are kept default.
Full Matrix Baseline. For the full matrix baseline we use single layer and map directly each token o; to a learnable full state-transition matrix A(x;) E Raxx via one-hot encoding. We then compute, for E (I,...,4} . the recursion
H A(c.) HD = I paxn
where n is set to 32 for efficiency reasons (memory and compute time grow quickly with n). After that, we flatten each H, into vector and apply first projection on the unit ball and then linear decoder to get the final outputs. The projection was added increase stability since we do not bound the norm Azx,). Since this model uses a full matrix, with n 2 5 should fully able to learn Sş without restricting the transitions in input using more tokens per transition. However, in some situations, the performance degrades quickly after some input sequence length, probably because the vanish or explode for long sequences.
of the learned A(x:) not close enough one and hence part of the state either
Plots with all runs. We report the plots with all 3 runs per method in Figure (In Figure 4 reported only the best one for each method). Despite our efforts to decrease the variance of the results by increasing training time and dataset size, we report that there is still some variability. For example, one of the runs of DeltaNet [-1, 1] (5L) on Sş with 4 tokens per transition did not achieve a good accuracy.
E.2.2 CYCLIC GROUPS
We report in Figure some experiments group word problems with the group Zeo. For this experiment, we also consider the simplified version where each transition is encoded using tokens. This is done as in the experiments of Sş with 4 tokens, but using tokens instead of 4. Extending the
30

---

Published as a conference paper at ICLR 2025
6o with tokens per transition
Z,
100
100
80
80
DeltaNet [-1,1] (5 layes)
60
DeltaNal [0,1] (5 layers)
Mamba [-1.1] layers)
40
Mamba [0.1] layers)
20
10
10'
10
Sequence Length of tokens)
Sequence Length
Figure 8: Validation sequence accuracy at different sequence lengths the eyclic group Zoo (1 seed). Dashed vertical lines indicate the sequence length used for training (left 32, right 64). Using 2 tokens per transition seems to help only marginally in this case. Mamba [-1, is the best- performing model. The variants with cigenvalues in [0,1] performed worse.
eigenvalue range seems to help in both settings, although surprisingly, Mamba [-1, 1]. even though has a diagonal state-transition matrix, seems to perform best. We conjecture that this case, the models might learn the shortcut solutions, also because they do not generalize very well to longer sequences.
E.3 LANGUAGE MODELING
E.3.1 DETAILS ON THE EXPERIMENTAL SETUP
We use the training pipeline which is part of the flash-linear-attention library (flame) (Yang & Zhang,
2024) and which in turn based on HuggingFace accelerate (Gugger et al. 2022). We use stage-2 of the ZeRO optimizer (Rajbhandari et al. 2020) with gradient clipping set to auto. The 1.3B parameter
DeltaNet models are trained on 32 Nvidia A100s using a per-device batch size of 6 and 5 gradient accumulation steps for 50,000 steps. The 340M parameter DeltaNet models and the 370M parameter Mamba models are trained using a training batch size of 16 and 200,000 steps on 16 Nvidia A100s. All models are trained using context length of 2048, learning rate of 3e-4. For optimization, we use Adam W (Loshchilov & Hutter 2019). the learning rate was adjusted using cosine annealing [oshchilov & Hutter (017) following linear warm-up period of 250/500 steps for the 340/370M and I.3B parameter models respectively. We applied a weight decay of 0.01 throughout the training process.
E.3.2 DETAILS ON THE EVALUATED TASKS
To produce the results in Table 4 use the Im-harness benchmark (Gao al. 2024), focusing
the same tasks as Yang et al. (2024b): LA MBADA (LMB) (Paperno et al. 2016). PIQA (Bisk et al.,
2020), HellaSwag (Hella.) Zellers al. 2019). Winogrande (Wino.) (Sakaguchi al.
2021 ) and
ARC-easy (ARC-e) and ARC-challenge (ARC-c) (Clark et al., 2018). Additionally. we evaluate the performance on -eeell-nttensive tasks (like Yang al. (2024b)) including FDA (Arora al. 2023),
SWDE (Lockard et al., 2019), and SQUAD (Rajpurkar et al. 2018), to provide comprehensive evaluation of our models' capabilities.
E.4 IMPLEMENTATION
We build on the original code for HambsFJand DeltaNe For DeltaNet. implementing the extended eigenvalue range is straightforward, since there is no need to modify the Triton kernel. However, Mamba requires modifications the CUDA code of the associative sean for both forward and back- ward passes which however had no impact computational cost. We ensured the accuracy of the modifications by comparing the results with naive implementation using a for-loop. For ini- tial testing of the extended eigenvalue range, used the pure PyTorch implementation of Mamba by Torres (2024). We provide listings of the necessary code changes in Mamba and DeltaNet in Ap- pendix E.4.1 For DeltaNet, this changes also B (xx.) in Table 1 multiplying it by 2.
31

---

Published as a conference paper at ICLR 2025
15.0
15
Perplexity (train)
14.5
Eigenvalue Range
14
[0. 1]
14.0
[-1,1]
13.5
13
80000
160000
80000
160000
Training Steps
Training Steps
15
Perplexity (trai))
14
Eigenvalue Range
13
[0. 1]
[ 1,
12
30000 Training Steps
Figure 9: Learning curves of DeltaNet 340M (top left), Mamba 370M (top right) and DeltaNet 1.3B (bottom); training on 100B tokens of Fine- Web 100B. 1.3B runs required only 50k optimizer steps the 200k of the 340M runs due the 4x larger batch size. All models trained stably with the same hyperparameters. Training curves were smoothed with rolling window of 500 steps.
CodeParrot
Math-Hard
Trivia QA
SlimPajama (6B)
Perpexity
18
Eigenvalue Range []
40
32
15
[-1.1]
16
30
20488
2044
2048
2018
Saquenoe Length
Sequenee Length
Sequence Length
Sequence Lengh
Figure 10: Length extrapolation performance of Mamba variants on different datasets. Mamba with eigenvalue range [-1, 1] shows worse perplexity on coding and math tasks compared to the (o, 1] baseline. The dashed, vertical line indicates the training context length of 2048 tokens.
Products in Log-space We note that some diagonal models such Mamba2 (Dao & Gu 2024
GLA (Yang al. [024a),, and mLSTM (Beck et al. (2024) take advantage of the fact that all values of the state-transition matrices
positive to compute their repeated products in dog-space. Our change would not allow us to do this directly, and carly tests on the chunkwise parallel form of GLA showed degraded performance. Therefore, for this work. we decided to focus Mamba and DeltaNet since they do not compute the products in log space. We mention however, that at the cost of increased computation time, it would be possible to do products in log space by converting each value in the diagonal state-transition matrix to the product of its absolute value and sign. This way, absolute values can be multiplied in log space, while products of signs are coincidentally equivalent to addition modulo 2, i.e. parity, and hence can be done stably. We leave the investigation of this approach to future work. Furthermore, we also believe that our change may be less suited for methods that use a normalized RNN state, such as mLSTM, since it might happen that the normalization term can be very close to zero due to the negative values.
32

---

Published as a conference paper at ICLR 2025
E.4.1 IMPLEMENTATION OF EXTENDED EIGENVALUE RANGE
if constoxpr (IkIsComplex]
221
threadLoata, []] make_t (exp2r (delta.vals [r]] Alval [r]t,
thread.dsts maka.flost2
exp2e tdeloo.vll [i] Aval(e]]
233
IkTavarianleR de delita_u_va a [r] R_vals[1]
[1])
224
LE constexp: [
225
if (thresdIdx.x kkItems serans.eegles, chunk kChunkSize)
226
thread_data mnke_float2(11. 0.fl7
228
Figure 11: Modifications to the forward pass of the Mamba associative scan. These changes extend the eigenvalue range from [0, 1] to 1,, 1]. enhancing the model's expressive capacity. Adapted from isclective_scart wwwdssannwwwwwweeeeee kerne..cc.. justed version (in green).
The original implementation (in red) is replaced with an ad-
flost deltc.a.exp exp2f (delta.valass) A.scoled)
254
const float del ta_a_exp 2.01 exp2r (delta_ve a [1) ALsca led) 1.0r
212
typename Ktraits: :Blockscant (amensccen) inclusivascen
typename Ktraitat:Blooke (amem.acon) Exclusivvseee thread_data, thread_data, 8SMS BBNScannpoce..ght.ttlll prefix_op
274
float thread data (IkTavrriableR dalta vals[1] f'ost vala(!))
289
della.vals Flost [luvall(l]] [.vala(
delta.a.exp
(deltaaaaa. Ascclled)
291
const float ddelta.a.exp delca_a.exp 1,
flost a ddeltaun_exp thread_data
293
const Float h1 deltá_a.exp thread.data(l).y (IKIeVariables ? deltaavals(i]
294
float [u.vals delta.vels(i) float (uvallss)) B.vals(E));
constexpr [KKTaVariableR [KTaVa-(ablec]
292
if constexpr (IkIsVariableB)
aBCl_val is dBL_val
293
dBC val +- dout vals[i] (XIsVariablee ? thread datalil.y thread datalil.y valls())> Lvala(s;))
dBC,val dout.voloi]] (Skiavaiiablec
295
sl // dRCI_ val is dc)_val
dout.vals (hread.data(1).g)
297
vac.val +s dout.vols thread.data
299
300
if constexpr (kisveriables! { di_vals(t) dx delts_vels[s] * flces (u.vass())) }
if constexpr (klaveriablec)
302
[C]vals[i] dout_vals[1] (IKtaWariableR 7 thread_data v Baral [1]
dC.sels(i dout.vals(i] (Ikiaveriables
Bwaal hi);
304
Figure 12: Necessary changes to selective scan bwd kernel.cuh red) replaced with an adjusted version (in green).
The original implementation (in
f.uus__eetaa aetaa
197
beta
rearrange fae.:.b.pre........... b.pro (hidden.states/ "b b 1t).t.)).ss............. siggoodd()
198
beta rearrange (self f.b.prod (h deddddnttttta) *b -> h. 17) aiigmmgo
200
beta q.new_ones (q. shape [0], shshapel1;; [1", q.shape (2])
Figure 13: Simple modification to the beta calculation in DeltaNet (Source) allowing the extension of the cigenvalues to the range [-1, The original implementation (in red) replaced with an adjusted version (in green).
33


Reviews:
[{"review_id": "DYgijAESeA", "reviewer": "Reviewer_tfg3", "summary": "This paper explores the connection between the eigenvalue range of the state transition matrix of a linear RNN and its ability to perform certain fundamental tasks, including parity and count modulo 3. The results point to changing the allowed eigenvalue range from [0,1] to [-1, 1] both for diagonal state transition matrices and ones constructed via identity plus a rank one component like DeltaNet. The authors show how to practically extend the eigenvalue range of both Mamba and Delta without harming training stability. Finally empirical results are shown on a 340M parameter DeltaNet and 370M parameter Mamba model with and without this eigenvalue range extension.", "questions": "Do you any hypotheses for why for Mamba the [-1,1] model had worse perplexity on the datasets (Fig. 8) while for DeltaNet the [-1,1] model typically has better perplexity (Fig. 4)? More generally, when using this [-1,1] extension, would you have any recommendation for whether to use DeltaNet or Mamba?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper provides a number of expressivity results which motivate considering state transition matrices with extended eigenvalue range. The first is an extension of previous work that for non-diagonal state transition matrices of a finite-precision LRNN, it still holds that solving parity for arbitrary input lengths requires at least one eigenvalue that is not real and positive (Theorem 1). Second, for modular counting with modulus greater than 2, at least one eigenvalue with a nonzero imaginary part is required to perform the task for arbitrary input lengths (Theorem 2). The paper then turns to practically how to extend the eigenvalue range for diagonal and generalized Householder state transition matrices (identity plus rank 1 component). Finally Theorem 3 and 4 provide two more expressivity results culminating in the  fact that \"LRNNs\" with state transition matrices that are repeated products of GH matrices each with eigenvalues in the range [-1,1] can recognize any regular language. \n\nThe work also provide a number of empirical results comparing Mamba and DeltaNet with eigenvalues in the range [0,1] and in the range [-1,1] as proposed by the paper. This includes looking at length generalization on a number of these more fundamental tasks discussed in the expressivity results, and the eigenvalue range is typically shown to be helpful. A 340M parameter DeltaNet and 370M parameter Mamba are then trained on 32B tokens of FineWeb with and without the eigenvalue range extension. I will discuss these experiments more in the next section.\n\nOverall the paper is well-written, the results easy to follow, and the limitations clearly discussed. My confidence score reflects that I am not as familiar with related work in this area.", "weaknesses": "The main weakness of the results is that the performance of the eigenvalue range extension is somewhat mixed for the larger models discussed in Section 5.3. In particular, for the LM-harness benchmarks in Table 4, the accuracy is mostly at or below the original model. This means that the work may not have immediate impact on the SSM model architectures used at scale.\n\nIt would be very helpful in Table 4 to have the better accuracy/perplexity bolded for each model group. Figure 3 does not have the y-axis labelled.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ULkUScvvqL", "reviewer": "Reviewer_i3oU", "summary": "### Summary of contributions\n\nThis paper studies the expressive capabilities of Linear Recurrent Neural Networks (LRNNs) on tasks requiring state-tracking. In particular, they look at the impact of the state-transition matrix structure which is usually a diagonal or a Generalized Householder (GH) matrix with positive values. They provide four theoretical findings promoting the use of non diagonal state-transition matrices with negative eigenvalues.\n\n1) Building on the result from Sarrof et al. 2024 which states that LRNNs constrained to diagonal positive state-transition matrices cannot solve parity, they show the same is true for non-diagonal LRNNs.  \n2) Furthermore, to count modulo $m$ ($m\\>2$), a LRNN (with finite precision and number of layers) requires at least one eigenvalue of the state-transition matrix to have modulus greater than or equal to one and with non-zero imaginary part.  \n3) One layer LRNNs\\* can implement finite state-automata whose transition monoid are groups.  \n4) Multiple layer LRNNs\\* can implement any FSA and thus can recognize regular languages.\n\n\\*(with transition matrix structured as product of sufficiently many GH matrices with eigenvalues ranging from \\-1 to 1\\)\n\nThese findings are supported by experiments comparing Mamba and DeltaNet, with and without negative eigenvalues. The results show that the architecture modifications suggested do not interfere with training and stability as well as confirming the applicability of these theoretical insights.", "questions": "### Recommendation:\n\nAccept\n  \nThis work brings important clarification on the capabilities of LRNNs when given greater flexibility in their parameterization than the current widely used one. In particular, the result demonstrating the ability of LRNNs (with finite precision, depth and width) to recognize any regular languages independently of the sequence length is a strong one. Moreover, the experiments confirm that these findings do translate in practice without impacting training or stability.\n\n### Questions (to clarify and increase confidence in the assessment):\n\n- Some issues with the references:  \n  - 113:  Why referring to Liu et al 2023 for a tutorial on language theory and circuit complexity?  Did you mean to reference *Saturated Transformers are Constant-Depth Threshold Circuits* from Merrill et al 2022 (for circuit complexity)?  \n  - 116: Why citing Deletang et al. 2023 for Turing completeness of Transformers with arbitrary precision? Perez et al. 2021 seems to be the appropriate reference for arbitrary precision. *Theoretical Limitations of Self-Attention in Neural Sequence Models* by Hahn 2020 might be relevant for infinite depth.  \n- Could you explain how you obtained the equations for $\\\\mathbf{A(x\\_t)}$ and $\\\\mathbf{B(x\\_t)}$ for Mamba in Table 1? I am not able to come to this result from Algorithm 2 and the discretization (equation 4\\) of Gu and Dao 2024\\. Despite the mention that the matrices are applied to each row of the matrix $\\\\mathbf{H\\_t}$, there needs to be more clarifications since the dimensions of the equations in Table 1 are in contradiction with the ones in equation (1) ($\\\\mathbf{A(x\\_t)}$ is dxd vs nxn). This does not affect the theoretical results of the paper, but the experiments appear to rely on this definition given the chosen expression of $\\\\mathbf{s(x\\_t)}$.  \nAs suggested by the ICLR AI reviewer assistant, can you\n\n>    1) Provide a step-by-step derivation of $\\mathbf{A(x_t)}$ and $\\mathbf{B(x_t)}$ for Mamba in Table 1.\n>    2) Clarify how these equations relate to Algorithm 2 and equation 4 from Gu and Dao 2024.\n>    3) Address the dimension mismatch between Table 1 and equation (1) for $\\mathbf{A(x_t)}$.\n>    4) Explain how this affects (or doesn't affect) the experimental results, particularly in relation to the expression of $\\mathbf{s(x_t)}$.\n\n- How does the comment on shortcut solutions (lines 220 to 222\\) relate to the argument on finite precision? (The explanation as to why this example of recurrence can not be implemented in a finite precision LRNN is clear without this sentence.)  \n- 229: the statement *“so are unable to learn parity.”* in this context is too strong, the example simply proves that current diagonal LRNNs cannot implement *this* specific FSA for parity. To conclude they cannot solve parity would require a reference to Sarrof et al.  \n- 313: Why does the inclusion over the domain of eigenvalues imply inclusion over the sets of matrices (despite $k\\neq k’$)? Is it implied that  $k=k’$?  \n- 314: Why mention that *“Repeated products of diagonal matrices… remain diagonal…”* given that GN matrices are not in general diagonal?\n\n### Feedback to help improve the paper (not influencing assessment)\n\n- 108 : Given the sentence *“Several studies have explored the expressive power of transformers”* a more comprehensive list would be appropriate. Some additional related references:  \n  - Separations in the Representational Capabilities of Transformers and Recurrent Architectures by Bhattamishra et al. 2024,  \n  - What Formal Languages Can Transformers Express? A Survey by Strobl et al. 2024  \n  - Simulating Weighted Automata over Sequences and Trees with Transformers by Rizvi-Martel et al. 2024  \n- Also, any reason why limiting to transformers and not mentioning the line of work on the expressive power of RNNs?  \n- 248 : Adding parenthesis in the counting modulo $m$ equation would be preferable to be consistent with line 212 and to prevent any ambiguity on operation priority.  \n- Figure 3 : Interesting that DeltaNet with 1 layer outperforms DeltaNet with 5 layers on S\\_5 only swaps. Any intuition other than simple over parameterization?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "### Strong and weak points of the paper (list):\n\n- The paper is well written and structured which enhanced clarity of the results and overall fluidity. In particular, the few lines introducing each section give a great summary of the key take-aways.  \n- The study of LRNNs expressivity, more precisely their capacity to achieve state-tracking, is well motivated through its connection to more complex and higher level problems such as reasoning and handling nested structures. The authors do contextualize their results by comparing and contrasting them with similar studies in the literature.  \n- The mathematical arguments presented in the paper are sound and rigorous which suggests the proofs (in appendix) are reliable. However, in some instances, more clarity should be provided (see questions below).  \n- Experiments supports not only the main claims of the theorems (e.g. Parity can be solved with negative eigenvalues, but not without), but also the more detailed insights (e.g. different levels of complexity explored in 5.2 State-tracking) and higher level conjectures (e.g. improved performance on language modeling tasks relying on state-tracking like coding). These experimental results make a compelling practical case for the modifications suggested by the theory in particular since the non-diagonal case is conclusive even with only one GH state-transition matrix (DeltaNet) while some theoretical results relied on a *product of $k$* GH matrices.", "weaknesses": "(see above)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Pzl5bRLni6", "reviewer": "Reviewer_LYF4", "summary": "This paper investigates the expressivity of linear recurrent neural networks (LRNNs), which is a term synonymous with recent state space models (SSMs) and linear attention variants such as GLA. The paper proves a number of theoretical results on the representation power of different LRNNs with various structures on the transition matrices. First it shows several \"necessary\" theoretical results, such that simple language recognition problems such as parity and modulus counting can only be solved by LRNNs with more expressive state transitions, in particular those that extend the eigenvalue range from $[0,1]$ to $[-1, 1]$ or complex numbers. A number of \"sufficient\" theoretical results are also proven for the expressivity of products of generalized Householder matrices (i.e. those found in the recent DeltaNet model), showing its ability to recognize any regular language.", "questions": "1. Do the models with this larger eigenvalue range run into more stability issues, especially at scale (e.g. the largest LM experiments)?\n2. For Table 3, it may be nice to include a simple Transformer baseline.\n3. Differences between models are sometimes conflated with differences in the neural network architecture (sometimes called the \"block\"). Meanwhile your results are about the inner recurrent layers and does not account for the block architecture. Does controlling for these two orthogonal factors affect results at all?\n4. For Figure 4, does extending the eigenvalue range of Mamba also help on coding/math tasks?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The theoretical results are very comprehensive and illuminating.\n- The paper's writing is very clear.\n- There are empirical results on both these synthetic tasks (tracking the theory) as well as more end-to-end language modeling evaluations.", "weaknesses": "- No major weaknesses. Some minor additional inclusions could be helpful (see below)\n- The paper's impact may be somewhat limited by the focus on synthetic tasks - it's not clear whether these actually matter in practice for real world tasks, restricting its applicability to large scale models on end-to-end modeling. E.g. these flavor of negative expressivity results for Transformers clearly haven't limited their applicability. I don't think this is a weakness of this particular paper, but a property of this broader research area, which prevents me from increasing my score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)