The Expressive Limits of Diagonal SSMs for State-Tracking
Authors: Mehran Shakerinava
Behnoush Khavari
Siamak Ravanbakhsh
Sarath Chandar
Venue: ICLR 2026 Poster (2026)
Keywords: state-space model
SSM
LRNN
linear RNN
expressivity
complex
dynamical system
state-tracking
semigroup
group
automata
Krohn-Rhodes
Primary area: learning theory

Abstract: State-Space Models (SSMs) have recently been shown to achieve strong empirical performance on a variety of long-range sequence modeling tasks while remaining efficient and highly-parallelizable. However, the theoretical understanding of their expressive power remains limited. In this work, we study the expressivity of input-Dependent Complex-valued Diagonal (DCD) SSMs on sequential state-tracking tasks. We show that single-layer DCD SSMs cannot express state-tracking of any non-Abelian group at finite precision. More generally, we show that $k$-layer DCD SSMs can express state-tracking of a group if and only if that group has a subnormal series of length $k$, with Abelian factors. That is, we identify the precise expressivity range of $k$-layer DCD SSMs within the solvable groups. Empirically, we find that multi-layer models often fail to learn state-tracking for non-Abelian groups, highlighting a gap between expressivity and learnability.

Published as a conference paper at ICLR 2026
THE EXPRESSIVE LIMITS OF DIAGONAL SSMs FOR STATE-TRACKING
Mehran Shakerinava Behnoush Khavari*X Siamak Ravanbakhsh
Sarath Chandar
Equal contribution" School of Computer Science, McGill University Chandar Research Labx Mila Quebec AI Institute' Polytechnique Montréal
khavaribêmi 1a. quebec mehranshakerin www.aaawaaiiaaaaaaaaaa...mmm cco
ABSTRACT
State-Space Models (SSMs) have recently been shown to achieve strong empirical performance on a variety of long-range sequence modeling tasks while remaining efficient and highly-paralle parallelizable. However, the theoretical understanding of their expressive power remains limited. In this work, we study the expressivity of input- Dependent Complex-valued Diagonal (DCD) SSMs sequential state-tracking tasks. We show that single-layer DCD SSMs cannot express state-tracking any non-Abelian group at finite precision. More generally, DCD SSMs can express state-tracking of group if and only if that group has a subnormal series of length k with Abelian factors. That is, identify the precise expressivity range of k-layer DCD SSMs within the solvable groups. Empirically, we find that multi-layer models often fail to learn state-tracking for non-Abelian groups, highlighting gap between expressivity and learnability.
show that k-layer
INTRODUCTION
Alternative architectures to Transformers are often motivated by efficiency and computational cost. Equally important, however, is the need to understand their failure modes. Addressing these failures key to designing better models and requires analyzing three aspects: (1) the model's intrinsic expressive capacity, (2) whether standard learning algorithms (e.g., gradient descent on finite data) reliably realize solutions within that capacity, and (3) the extent to which these limitations actually transfer to or predict performance on real-world tasks. In this work, we focus on the first aspect, architectural expressivity, and provide empirical observations for the second aspect.
A particularly illustrative class of tasks where Transformers are known to fail is state- tracking (Deletang et al., 2023; Liu et al., 2023; Hahn & Rofin, 2024; Bhattamishra et al., 2022). These tasks are closely related to regular languages in formal language theory and include simple tasks like parity and modular addition. State-tracking tasks are considered representative of model's performance on real-world problems, such as code execution and program analysis. Examples of Transformers failing to generalize to duitt--iisttibuution (OOD) inputs highlight how limited expressivity can lead models to rely on shortcut solutions that do not generalize beyond the training distribution (Liu et al., 2023). An example of sequence modeling task that requires keeping track of state that is being manipulated is program state analysis from big-bench (GoogleResearch, 2021). For example, given the following code,
x, y, 0, F. y, 21
v. = 2,2=2,11 2, x, V y,
what the value of x after the fourth command? This specific example requires the ability to model permutations of three objects, i.e., the group Sz.
State Space Models (SSMs) have emerged as efficient alternatives to Transformers, promising linear- time sequence modeling with recurrent state representations (Gu et al., 2022b). Initially, they were expected to outperform Transformers on state-tracking tasks, because their recurrent statefulness. However, Merrill et al. (2024) showed that, despite having explicit state representations, SSMs still fail on these tasks, much like Transformers. They highlight this issue for time-invarianl or diagonal SSMs in the context of tracking states over sequences of non-solvable group operations. Later

---

Published as a conference paper at ICLR 2026
work by Sarrof et al. (2024); Grazzi et al. (2025) reveals that these models are unable to track even solvable groups such as parity and modular counting, due to design limitations in their state transition matrices. We defer detailed discussion of these findings to Section 3.
In this work, we study the expressivity of input- Dependent Complex-valued Diagonal (DCD) SSMs and show that single-layer DCD SSM cannot track any non-Abelian group at finite precision. We then show that stacking additional diagonal layers allows the model to track group if and only if that group has a subnormal series of length equal to the depth of the SSM, with Abelian factors. This result establishes the strict benefit of depth for modeling non-Abelian groups with diagonal SSMs and identifies the precise expressivity range k-layer DCD SSMs within the solvable groups.
G₁
D G
P G2
t G
layer &
G1
layer kt
G G
Finally, we empirically evaluate diagonal SSMs, both single- and multi-layer, state-tracking tasks, including Abelian groups, such parity (C2) and mod-60 addition (Cso), well as non- non-Abelian groups, such as permutations of 3 elements (S3). In practice, we observe a clear gap between expressivity and learnability of multi-layer models on non-Abeliag groups. This suggests that, although some of these models are theoretically expressive enough, they encounter training challenges with standard gradient-based optimization.
layer 2
Ge-1/GR-2
range of group
layer
Ck/Ca-1
Figure 1: A group Gg be tracked by k-layer DCD SSM iff the group has subnormal chain of length with Abelian factors. Each layer tracks one such Abelian factor as shown in the diagram.
2 BACKGROUND
2.1 SSMs
We review SSMs and provide background on some of the variants that we refer to in this paper. We begin by defining SSM layer using notation inspired by previous works (Sarrof et al., 2024; Grazzi et al., 2025).
Definition (SSM Layer). A d-dimensional SSM layer is parametrized function that takes as input sequence of x, E [F" and outputs a sequence of y, E 1 via an affine recurrence:
h = (1,,,),-11+ b(xz),
(1)
V/1 dec(h),
(2)
where h2 E Fd is the state, A(x²) gddd is the transition matrix, b(xz)) E Fdd is the input vector, and dec 1ed x 1Fn + 1. is the decoder. The learnable components of the SSM layer are A, b, dec, and possibly the initial state hig A(x) is diagonal for all æ E F", we say the SSM layer is diagonal. If F R and A(x) has only real eigenvalues, we say the SSM layer is real. Otherwise, we say the SSM layer is complex.
Computation The state's affine recurrence can be efficiently parallelized with the parallel scan (a.k.a,, prefix sum) algorithm (Blelloch, 1990) to run in depth Olog as opposed to the naive O(T), where T is the sequence length. The parallel scan algorithm leverages the fact that the composition of affine maps simplifies into another affine map to compute the states in parallel. This is particularly efficient when A(x) is diagonal, as matrix-matie and matrix-vector multiplications reduce to element-wise multiplications.
Most variants of SSMs captured by Definition 1. We review some of the most relevant ones.
2

---

Published as a conference paper at ICLR 2026
Model
A(r)
B(x)
dec(h,
S4
Br
o ( + Dx)
S4D
A (diagonal)
Bx
oR(Ch) + Dx)
Mamba
exp (x) O A)
A A exp(( 4 (x))) O O 1) Br
oCC()) +D(x))
Negative Mamba
2 exp A (x) O A) -I
A ( (x) @ A) Br
o(C(z) +Dx)) aCC(a) + D(x))
AUSSM
exp (A (x) O (x))
A (x))rr
Table 1: Summary of SSM variants in terms of their transition matrix A(x), input vector (zx), and decoder 2)).
S4 The Structured State Space Sequential model (S4) (Gu et al., 2022b) is based on continuous- time linear time-invariant (LTT) state-space models from control theory. It is obtained from Definition by setting IF = C, A(x) A, b(xx) Ba, and dec(h, o (RR(h)) + Dx), where E Cdxd, B Cdxn, C E Lmad, and D E Rmxx are learnable parameters, and a is a nonlinearity.
Careful initialization of the parameters, especially the transition matrix A, e.g. via HiPPO (Gu et al., 2020), allows these models to mitigate the vanishing gradient problem that affects classical RNNs. Moreover, the structure imposed on the A matrix (normal plus low-rank) makes learning efficient. S4 achieved state-of- off-the-an art results on set of long-range sequence modeling tasks (Tay et al., 2021), I), where transformers had previously struggled. As a result, it was seen as a promising alternative or complement attention-based models.
S4 inspired several follow-up models. On the one hand, simpler variants such as DSS (Gupta et al., 2022), S4D (Gu al., 2022a), and S5 (Smith et al., 2023) simplified S4's architecture while retaining strong performance. On the other hand, more sophisticated models such as H3 (Fu et al., 2023) and Mamba (Gu & Dao, 2024) extended SSMs to handle more diverse set of tasks, particularly language modeling.
S4D S4D is a simplified version of S4 in which the complex transition matrix A is constrained to be diagonal. This reduces the cost of matrix multiplication in the recurrence equations and hence leads to more efficient computation.
Mamba Designed specifically for language modeling tasks, Mamba introduces input dependence (also called selectivity) in the transition matrix while maintaining the diagonal structure of S4D, is obtained from Definition 1 by setting F = R. A(x) = cxp(A(x) o A), b(x) = A (cxp(A(ar A) - B), and dec(h, = (C(z)h + D(=)), where A E Su A(x) E Rd B E Rdxn, C(x) E Rmxd and D(x) E R" Icarnable functions of the input x, and is nonlinearity. Note that Mamba's 's transition matrix A(x) is real-valued and in (0, due to the constraints on A and (xx). Another variant, due Grazzi et al. (2025), is negative Mamba which simply replaces A(x) with 2A(x) - I to bring the eigenvalue range to (-1
AUSSM The Adaptive Unitary SSM (AUSSM) (Karuvally al., 2025) is input-dependent complex diagonal SSM with unit-modulus transitions. It is obtained from Definition 1 by setting F = C. A(x)
exp(iA(x) A(z)), b(x) A(z) and dec(h, x) a (C(z)h + D(x)), where (xx) E Rd A(x) E Rd, B(x) E C", C(x) E grad and D(x) E C are learnable functions of the input x, and a nonlinearity.
These models have been summarized in Table 1.
2.2 GROUPS, AUTOMATA, AND STATE-TRAA TRACKING
A semigroup is a set G equipped with an associative binary operation ;, where the set is closed under
the binary operation. If the operation has an identity element such that e-g g. g for all g E G.
then G is a monoid. If every element g E G has an inverse g such that 9.g = - = e, then G is a group. A group is Abelian if its operation is commutative, i.e., 91 01-90 92 92 92 for all 91 92 E G. A subgroup H < G is a subset closed under and inverses (equivalently, a group under the restricted operation). A subgroup N 4 G is normal if g N for all g E G. Note that, by convention,
3

---

Published as a conference paper at ICLR 2026
juxtaposition such g.N g.Ng denotes the set obtained by multiplying each element of N by g (and by 9 on the right, respectively). When N < G, the set G/N = {9N 9 E G} forms the quotient group, with operation (gNN) (hN) (g h)N. A subnormal series is chain
GG 2 G G. D (Gn = {e})-
(3)
Its facters are the quotients Gi+1 /G. A group is solvable if it admits subnormal series whose factors are all Abelian. A group is simple if it has no non-trivial normal subgroups. See Rotman (2012) for more details.
Example 1. The group of all permutations of 3 items is denoted Sa and consists of the elements {e, (12), (23), (13), (123), (132)). It admits the subnormal series
{e} C3 4 S3,
(4)
where C3 { e. (123). (123)²} is the cyclic group of order 3. The factors C3/fe} C3 and
S3/O3 = C2 are both Abelian, so S3 is solvable.
The set of state-transition functions of a finite automaton when receiving a (possibly empty) sequence of inputs, equipped with composition, forms monoid. If the automaton is reversible, this monoid in fact a group. The Krohn-Rhoder theorem (Krohn & Rhodes, 1965) states that any finite automaton can be decomposed into cascade product of simple groups and reset automata (i.e., flip-flops). An automaton is called solvable all the simple groups in its decomposition are solvable. In cascade product of automata, the state and input of the first automaton provide the input to the second, loosely resembling stacked neural network layers with skip-connections. The Krohn-Rhoon Rhodes theorem thus reduces the simulation of complex automata to the simulation of simple groups, flip-flops, and their interactions. Since the latter two are relatively easy. the essential challenge lies in the system's 's ability to simulate groups, which is the focus of this work.
Sequential hate-tracking tasks are meant to capture the ability to simulate semigroups. Given semigroup G its state- trac-tracking task is, given a sequence of elements ø1, ..,, Dr E G, to output sequence y1, ./...... V/ E G such that y/: 21 .22 Tt. Some specific tasks of interest are parity, which corresponds to the cyclic group C2, and mod-n counting, which corresponds to the cyclic group Cn.
3 RELATED WORK
Merrill et al. (2024) study the state-tracking capability of SSMs through the lens of circuit complexity. They show that both input-independent non-diagonal and input-dependent diagonal SSMs with real-valued transition matrices belong to the complexity class TC the class of problems solvable by constant-depth, polynomial-size circuits of AND, OR, and threshold gates with unbounded fan-in. This class is widely conjectured to be incapable of expressing non-solvable state- tracking tasks such as tracking S3. To address this, they propose either adding nonlinearities to the recurrence, which renders the model non-parallelizable or making the recurrence non-diagonal and input-dependent. They thus propose an DepundDe S4 (IDS4) and empirically show that it performs better non-solvable state-trace tatte-tracking tasks of relatively longer length. However, the drawbacks of the circuit-complexig approach are that it does not tell us which problems within TC can be solved by these SSMs, and it relies on a conjecture in circuit complexity. In this work, we precisely describe the groups that can be tracked with k-layer diagonal SSM (unconditional to any conjecture). In the limit of Ie + oo all solvable groups can be tracked.
While Merrill et al. (2024) focus on the limitations of SSMs non-solvable groups, Sarrof et al. (2024) highlight a significant limitation on parity, which is the simplest non-trivial solvable group. They prove that input-dependent non-negative diagonal SSMs (e.g., Mamba) cannot solve parity in finite precision for arbitrary sequence lengths. They also show that time-invariant complex-valuee diagonal SSMs (e.g., S4D) fail parity. Connecting with the result of Merrill et al. (2024), this means that common SSM models only cover very small subset of TC On the positive side, Sarrof et al. (2024) show that a Mamba layer can simulate a flip-flop, and as a result, multi-layer Mamba can simulate counter-free automata.
4

---

Published as a conference paper at ICLR 2026
Extending these results to non-diagonal models, Grazzi et al. (2025) prove that a multilayer SSM can solve parity in finite precision for arbitrary sequence lengths only at least one layer has a negative eigenvalue. This implies that even DeltaNet' fails to solve parity in its standard form. They argue that existing SSMs typically lack either input dependence or negative (resp. complex) eigenvalues. Having both of these properties in some layer is essential for solving parity (resp- modular counting) (Khavari et al., 2025). To address this, they modify Mamba and DeltaNet to allow eigenvalues in the range [-1, 1] instead of [0, 1]. This leads to empirical improvements on both parity and real-world tasks.
While negative eigenvalues are sufficient for solving parity, Grazzi et al. (2025) show that complex eigenvalues are necessary for harder tasks such as modular counting. Thus, although modifying Mamba to include negative eigenvalues enables it to solve parity, solving more complex tasks demands transition matrices with complex eigenvalues. They note that such matrices can be constructed by multiplying several real-eigenvalued matrices, provided the product is non- triangular."
Building on this idea, Siems et al. (2025) proposes DeltaProduct, an adaptive extension of DeltaNet that generalizes the transition matrix from diagonal-plus-rantee to structured rank-n matrix. Here n is tunable to trade off between expressivity and efficiency. Their construction based on products of n generalized Householder matrices. A limitation of this approach is the computational cost of multiplying non-diagonal matrices.
Karuvally al. (2025) propose the Adaptive Unitary SSM (AUSSM), which is complex-valued input-dependent diagonal SSM with unit-modulus eigenvalues. They show that a single-layer AUSSM can simulate any Abelian group but it cannot simulate flip-flops. Since Mamba is able to simulate flip-flops, they propose interleaving Mamba and AUSSM layers to handle solvable currently unknown (1) if a single- layer AUSSM can simulate non-Abelian groups, (2) what the expressive capacity of k-layer AUSSM is, and (3) if it is unconditionally true that multi-layer AUSSMs cannot simulate non-solvable groups. These are questions that we aim to address.
automata (according to
theory). However,
THEORETICAL RESULTS
4.1 SINGLE-LAYER DCD SSM
We begin by analyzing the limitations a single-layer imput-Depended Complex-vale Diagonal (DCD) SSM (recall Definition 1) on sequential state-tracking tasks for groups. We assume that A, b, and dec are universal function approximators. In this section, we build up to the following theorem.
Theorem 1. There is single-layer DCD SSM that tracks G at finite precision iff G is Abelian.
Having b in the state recurrence makes the problem non-trivial. Without b, the state recurrence is given by h, = A(z,)/, and since A(x,) is assumed to be diagonal and since diagonal matrices commute, the expressed group operation has to be commutative, i.e., the group Abelian. However, with 6, the SSM can perform non-commutative state updates. We show that even with b, a single- layer DCD SSM cannot express non-Abelian groups at finite precision. In other words, our result implies that having b does not increase expressivity for tracking groups at finite precision.
Another point that makes the problem difficult is the existence of a decoder (especially a powerful one), as it can implement complex decision boundaries in the state space. For example, we cannot assume that feeding the sequence (g. 1) to the SSM layer results in the identity map on the state. As long the initial state hn and the final state fı2 decode to the same group element, i.e., dec(ho) deo(h2), the SSM is treating the input sequence correctly.
DettaNet is a linear attention model that can also be interpreted as an SSM, with a diagonal plus low-rank transition matrix. More specifically, generalized Houscholder matrix.
"Because the eigenvalues a triangular matrix are the diagonal elements, and the product of two triangular matrices remains triangular.
Unnonditionllyy means that the argument does depend any conjecture.
5

---

Published as a conference paper at ICLR 2026
An important property of SSMs (and linear RNNs in general) is that the state update corresponding to a finite sequence of inputs simplifies into an affine map. More specifically, given an input sequence
I (21, 22 ... 2T), the state update from 0 to t T of a diagonal SSM is given by
hr ( @ ho + b(æ),
(5)
where
T
A(z) = I Mxx),
(6)
=
T
(() = Σ
πI #=++1
Mayz)
b(a)).
This is a key property that we use in our proofs. Importantly, note that we have now overloaded and b to also accept sequence of inputs.
First, we show that if some input æ causes some coordinate j of the state to contract ((xz))) < 1), expand ([A(r))l 1), or drift ((A(z),) 1 A b(x) * 0), then still solves the task while keeping state-coordinate j fixed. As a result, such state-coordinates are useless for tracking groups and can be effectively ignored by the decoder.
construct another SSM that
Notation. We sometimes use multiplicative notation for groups. For example, g2 means g g and gh means g h. Sometimes we may want concatenate group elements form sequence. We use parentheses to denote sequences and write (g) for sequence of length one consisting only of g- We use multiplicative notation for the concatenation of sequences as well. For example, (g) (h) is sequence of length six consisting of single g followed by five h elements
Lemma 1. Ler M be a single-layer DCD SSM that tracks group G at finite precision with [A(x))] # or (*(x))l = A b(x); # for some x and j [d], then there exists another single-layer DCD SSM M that also tracks group G at finite precision with M()) = 0 and b(g); = c (for some constant c) for all g E G.
A proof is provided in Appendix C.I.
Repeating the lemma above for all coordinates j [d] lets us construct another SSM that tracks the same group but has no contracting, expanding, or drifting coordinates. Therefore, we can now assume that all coordinates of the state have neutral rotation dynamics (case in Appendix A) for all inputs. Next, we show that two inputs have neutral rotation dynamics with distinct centers of rotation, then the SSM diverge. The following lemma useful.
Lemma 2.
The composition of neutral rotations + A(h - (1) + ei and h + (h - c2) + C2 where X* is the conjugate of X, with distinct centers of rotation e₁ 02 is a non-zero translation.
A proof is provided in Appendix C.2.
The above lemma gives us a strategy to make certain SSM configuration diverge.
Lemma 3. If a single-layer DCD SSM tracks group G at finite precision and there exist two inputs g, h E G that induce neutral rotation about distinct centers in some coordinate j [d] of the state, then the SSM diverges on some input sequence.
A proof is provided in Appendix C.3.
By putting the lemmas together, we can prove Theorem 1. A proof is provided Appendix C.4.
4.2 MULTI-LAYER DCD SSM
In this section, extend our results to the multi-layer setting, where the input to the rth layer is the input token and the states of the previous layers, denoted (1(1,,.. (r-1), We aim to prove the following theorem.

---

Published as a conference paper at ICLR 2026
Theorem 2. There is k-layer DCD SSM that tracks G at finite precision iff one can write
(G= = GR) 2 Gk-1 22 G1 2 (Go {et)
(8)
where Gi+1/G, is Abelian for all i E [R)].
We begin by applying the same approach as the single-layer case to construct another SSM with simpler state space and state transitions that tracks the same group.
Lemma 4. If a k-layer DCD SSM tracks group G at finite precision, then there exists another k-layer DCD SSM that also tracks group G at finite precision, where, for all layers r E [k] and all state-coorlinates E [d), the transition dynamics is fixed neutral rolation about center that is a function of the states of previous layers (h(1), hr-l)).
proof is provided in Appendix C.5. We then use it to prove the main theorem in Appendix C.6.
5 A DIAGONAL SSM FOR S3
In this section, we present an example of a two-layer diagonal SSM that can track the non- commutative yet solvable group S3 for arbitrary sequence lengths. This section has two purposes. First, it provides concrete illustration of the theory introduced in the previous section. We begin by showing how two relatively simple automata can be combined form a non-Abelian solvable automaton, and then demonstrate how this construction can be encoded in stacked diagonal SSM layers. Secondly, it highlights the gap between expressivity and learnability. While the theory suggests that two-layer diagonal SSM can track the non-Abelian group S3, our experiments in the next section show that, in practice, the model often struggles to learn solutions that generalize to longer sequences. This implies that while generalizable solutions would lie within the expressive power of the diagonal SSMs we study, they may be difficult for the learning algorithm to find.
5.1 THE S3 GROUP
The symmetric group S3 the group of all permutations of three elements. has six elements in total and provides the smallest non-Abelian example of finite group. The elements can be written in cycle notation as S3 = e, (12), (13), (23), (123), (132) }, where e denotes the identity permutation, the transpositions (12), (13), (23) swap two elements, and the 3-cycles (123) and (132) permute all three elements cyclically in opposite directions. S3 can be decomposed as the semi- direct product of two Abelian groups, C2 and Cz. It can also be presented by two generators, for example S3- = { (12), (123) ), of orders 2 and 3, i.e. (12)² = e, (123) e. The Cayley table of group multiplications for S3 is given in Appendix B.I.
5.2 DECOMPOSING THE S3 AUTOMATON
Now, we show that there exists a finite state automaton, built as cascade product of two simpler automata, that can track S3. Figure 2 illustrates one such composition of automata capable of tracking Sz. To illustrate how this solution works, we encode each g E S3 r" with (12), r = (123) denoting swap and rotation generators, and multiplication applied left to right. Under this encoding, S3 can be rewritten S3 {c, 8, sr sr, r, r²). The combined automaton operates as follows: r. first applies swaps the two-state automaton with state Q(1)
1),
yielding ((1) = (-1)=, with Q8 being the initial state. The second automaton then takes as input both the input group element and the state of the first automaton and transitions its state Q(2) E {Q1, Q2, Qa} according to the transition rule illustrated in Figure 2; that is, if the state of the first automaton is Q 1, upon seeing group element with 3 1, it rotates its states according to the cyclic permutation (123), and if 3 = 2, the cyclic permutation (132) is applicd; however, if (1)) = 11 the cyclic permutations are applied in the other direction, i.e. for 3 = 1, the state transitions according to (132) and for 3 = 2, it transitions according (123). In Appendix B.2, we give concrete examples showing how this encoding, together with the transition rule of the two automata, correctly reproduces group multiplication and thus tracks S3 with the compounded
7

---

Published as a conference paper at ICLR 2026
(-1/1,0)
start
(19 2.11
11. (-1.A)
tnd to cress
111-1-11 (-1.)
start
(1.3)---223
(-1/1,0)
Qa
(-1/1,0)
(.20.(-11)
Figure Compound automaton combining (left) two-state parity and (right) three-state cyclic group. The dashed curved line represents the connection between the two cyclic automata, equivalent to the semi-direct product of their groups. It shows that the automaton on the right considers the state of the first automaton, besides the original input. Commas separate inputs that produce the same state transition. States labelled start are the initial states of the automata.
automaton. In what follows, the result of Example 2 in Appendix B.2 based this specific encoding, summarized Table 4, to parameterize a two-layer AUSSM that tracks Sy consistently.
5.3 SIMULATING THE 2-AUTOMATON FOR S3 WITH DIAGONAL SSMS
From Theorem 1, each diagonal SSM layer can model one Abelian automaton; remains show that we can stack them in way that simulates the cascade product of the two Abelian automata.
With the encoding (a, 3) for the input , for the first AUSSM, with the state equation hr -(((()))())) h4 + Bxxx), set B(x)= 0, A(x) 1, and A((0, 8)) O, A(1,, π. The second layer gets the input (h()),,,3 with (1) being the state of the first AUSSM layer, fed to the second layer with a skip connection. Here we set ((2)
O. A (x) 1.
and (12( a, B))
3 3. The full state of the SSM will be e (1 - A Bng ( ) This results in finite number of states, and with correct decoding, we can map the states to the elements of the group.
3 B, (
6 EXPERIMENTS
We evaluate single- and two-layer diagonal SSMs set of solvable group state-tracking tasks. Our goal is to measure what these models learn with standard training, not just what they can represent in theory. Our models include Mamba (Gu & Dao, 2024), negative Mamba (Grazzi et al., 2025), AUSSM (Karuvally et al., 2025), RNN, and simplified AUSSM where and B have been removed since they are theoretically not needed for expressing groups.
Datasets. Our set of tasks consists of different kinds of solvable groups that we are interested in: parity, which is C2. a small, a medium and a large cyclic Abelian group, Co. C24 and Coo respectively, two products of cyclic groups, C2 x Ca and C3 Cs. and two small solvable non- Abelian groups with subnormal chains length 2, S3 and A4. We also include the non-solvable group As. which expect model can leamn
For cyclic group Cy with N E N, the task is essentially addition mod N, with the input tokens being chosen uniformly random from the group. An example input for the task Cso is the sequence [51, 20, 4, 49] and the correct output is [51, 11, 15, 4].
The group Sy was introduced in detail in Example 1. The alternating group A₁ consists of the 12 even permutations of four elements. Like Sg, admits a subnormal chain of length two with Abelian factors, and is therefore solvable.
8

---

Published as a conference paper at ICLR 2026
The alternating group As consists of the 60 even permutations of five items. In contrast S3 and A4, its shortest subnormal series is {e} < As. with the non- non-Abelian factor As/ [e] = As. Consequently, Aş is not solvable.
Experimental Details. Models were trained on sequences of up to length 60 and tested on sequences up to length 1000 to assess their length generalization performance. We applied curriculum learning by gradually increasing the length of training sequences, starting from length 2. We report the longest sequence length > 100 at which the trained model can obtain above 90% accuracy. If the model was unable to extrapolate we report x. The results can be seen in Table 2.
All experiments three state dimensions {32, 64, 128}, three learning rates {le 4, 5e 0e *.1e-3) rate schedulers (fixed, reduce on plateau, cosine). The AdamW optimizer learning rates and a weight decay of 0.01. Each experiment was run with three random seeds, and we reported the best result across seeds. The embedding and model dimensions were fixed at m = π = 698 across all experiments. The choice of a relatively large embedding dimension was motivated by stabilizing optimization across both real- and complex-valune
conducted with standard FP32 precision. We performed grid search over and three learning-
5,1e 3) used with these
kernels. Unless otherwise noted, models were trained with a batch size of 256. We used gelu nonlinearities between SSM layers and residual connections within each SSM layer. The initial state hg of the SSMs was set to 1 and normalized to unit norm.
Tisk
Mansba
Negutive Manth
Simple AUSSM
AUSSM
RNN
Tolk
Maniaa
Negutive Mumba
Sangle AUSSM
AUSSM
RNNN
0
1000
140
1000
1000
C
X
1000
1000
200
1000
Cl
X
240
940
1000
X
240
100
1000
X
1000
150
Gyn
X
300
240
X
250
CC
X
140
1000
X
S
A
1000
4
(a) Single-layer models.
(b) Two-layer models.
Table 2: Performance of various models state-tracking tasks. Each table reports the longest sequence length 2 100 where a model is able to achieve accuracy greater than 90%. The maximum training length was 60 for all models over all state-tracking tasks. X indicates that the model failed to extrapolate to long sequences.
Results. For RNNs, there no theoretical expressivity barrier that would stop them from successfully learning all tasks. However, in our experiments, the single-layer RNN struggles Cso. likely due to the large size of the group, and the two-layer variant struggles on both Coo and A4. is possible that with different architectural hyperparameters longer training the RNN would have succeeded.
For Mamba, since does not have negative eigenvalues, in accordance with previous theoretical results (Sarrof et al., 2024). we expect it to not be able to track any group. This is indeed observed in our experiments. Negative Mamba is a modified version of Mamha which allows for negative eigenvalues and with a single layer, is expected to only be able to solve parity (Grazzi et al., 2025). This is also observed in our experiments. On the other hand, according to our theory, stacking two layers, each of which is capable of solving C2 (e.g., Negative Mamba), can do state-tracking for C. This is because the group C4 can written as the subnormal chain C4 P C2 E {e), where the factors are all C2, i.e., Abelian. We see in practice that 2-layer Negative Mamba is able to do state- tracking for C2 x C.. Interestingly, this is a case where the increased expressivity from stacking layers is usable through gradient-based learning.
For AUSSM and simple AUSSM, their single-layer variants are theoretically able to express Abelian groups, which in our case are the six groups C2, Cs. C24. Ceo. C2 x C4, and C3 x Cs- Gradient- based optimization has successfully been able to find solutions that extrapolate in this case as well (with the exception of two anomalies for two-layer AUSSM), However, their two-layer variants have not been able to match the expressive capacity that is expected from them as they fail on S3 and Aq-
*This has also heen stated in Theorem 2 of (Grazzi al., 2025).

---

Published as a conference paper at ICLR 2026
Overall, these experiments point to a learnability gap. The main bottleneck of non-Abelian tracking is not expressivity but optimization and the model's 's built-in bias: the solutions exist in weight space, yet standard training does not reliably reach them.
To gain insight into the potential causes of this learnability issue, we initialized AUSSM near the analytical solution for S3 from Section 5.3. We observed that sufficiently close initialization improves training: the model successfully learns and extrapolates to sequences at least four times longer than those seen during training. This suggests that solutions lie within basin of attraction in the loss landscape. However, the broader structure of the loss landscape is still not well understood. A study analogous to Hahn Rofin (2024), which investigates transformers, would be a valuable future direction for SSMs. Notably, since initialization near the solution aids optimization in SSMs, the challenges they face may differ substantially from those of transformers, where solutions have been shown by Hahn & Rofin (2024) to correspond to isolated points in weight space.
7 DISCUSSION
Our results reveal sharp distinction between what diagonal SSMs can represent in principle and what they can learn in practice. Theoretically, a single diagonal layer suffices for all Abelian groups, and stacking layers expands expressivity exactly to solvable groups with subnormal series matching length. This characterization places diagonal SSMs within a precise group- theoretic boundary: they are strictly weaker than non-diagonal recurrent models, yet depth provides a disciplined pathway to handle increasingly complex dynamics.
Empirically, however, experiments show that diagonal SSMs often fail to realize their expressive potential. Even two-layer models, which can provably represent S3, rarely discover solutions that generalize beyond training lengths. This gap points to difficulties of gradient-base based optimization when searching for encodings of non-Abelian structure within the restricted hypothesis class, It also suggests that diagonality, while efficient, imposes inductive biases that may actively hinder training on harder tasks.
From a broader perspective, our findings connect other architectural choices in sequence models. Allowing block block-diagonal structure, even in 2 x 2 form, would in principle lift the expressivity of SSMs into NC1. enabling simulation of non-solvable groups Similarly, introducing complex-valued attention weights in Transformers may bring them closer to the expressivity frontier we identify here for SSMs. Finally, it is worth noting that many practical applications do not demand arbitrary-lengte state-tracking being able to stably handle moderately long sequences may be sufficient, though our results clarify what is lost at the limit.
Finally, although we state the main results for groups, the framework extends naturally to semigroups and monoids. Allowing inputs that reser a layer (i.e., map coordinate to fixed center under finite precision) lets a diagonal SSM simulate reset automata in addition to group components. Consequently, the same depth-based view applies to cascade products comprising Abelian group factors and resets, bringing the analysis in line with the Krohn-Rhodes perspective on solvable automata.
CONCLUSION
We have given a complete characterization of the expressive power of diagonal SSMs on group state-tras trackeraaking tasks. A single diagonal layer cannot track non-Abelian groups, while a k-layer SSM can track precisely those groups admitting subnormal series of length & with Abclian factors. This establishes a provable expressivity gap between single- and multi-layer diagonal SSMs.
Our experiments further demonstrate a learnability gap: despite their theoretical capacity, multi- layer diagonal SSMs struggle to learn even small non-Abelian solvable groups such as S3 and A4. Together, these results highlight the importance of separating expressivity from learnability when evaluating new sequence architectures. Future progress will require not only expanding the expressive frontier through, for example. block-diagonal transitions or hybrid models but also developing training methods that can reliably reach solutions guaranteed to exist in principle.
10

---

Published as a conference paper at ICLR 2026
9 ACKNOWLEDGEMENTS
We thank Ashish Sabharwal and Razvan Pascanu for useful discussion and Yusong Wu, Alex Hemandez- Gauthier Gidel, and Ioannis Mitliagkas for feedback on an earlier draft this paper. This research is in part supported by CIFAR AI Chairs and the NSERC Discovery program. Mila and the Digital Research Alliance of Canada provided computational resources.
REFERENCES
Satwik Bhattamishra, Arkil Patel, Varun Kanade, and Phil Blunsom. Simplicity bias in transformers and their ability to learn sparse boolean functions. arXiv preprint arXiv:2211.12316. 2022. Cited at 1.
Guy E Blelloch. Prefix sums and their applications. 1990. Cited
Gregoire Deletang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg. Joel Veness, and Pedro Ortega. Neural networks and the chomsky hierarchy. In International Conference on Learning Representations, 2023, Cited at 1.
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, 2023. Cited at 3.
GoogleResearch, Big-bench: Auto debugging task. https://github. http://..ooo///o/////eoee/o// goog/ e/ 2021.
BIG-bench/ten /tannech/tereeeeee Catrre/main/beeee heiiiniigggeniie Accessed: 2025-11-22 112
Cited wwwiibench/bbncheeeeeeee tattaaakktaakkktttotdoooeee
Riccardo Grazzi, Julien Siems, Jörg K.H. Franke, Arber Zela, Frank Hutter, and Massimiliano Pontil. Unlocking state-tracking linear RNNs through negative eigenvalues. In The Thirteenth International Conference Learning Representations, 2025. Cited at 2, 3, 5, 8, and 9.
Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces. In First Conference Language Modeling, 2024. Cited at 3 and 8.
Albert Gu, Tri Dao, Stefano Ermon, Atri Rudra, and Christopher Ré. Hippo: Recurrent memory with optimal polynomial projections. In Conference Advances in Neural Information Processing Systems, 2020. Cited at 3.
Albert Gu, Karan Goel, Ankit Gupta, and Christopher Ré. On the parameterization and initialization of diagonal state space models. In Conference on Advances Neural Information Processing Systems, 2022a. Cited at 3.
Albert Gu, Karan Goel, and Christopher Re. Efficiently modeling long sequences with structured state spaces, In International Conference on Learning Representations, 2022b. Cited at and 3.
Ankit Gupta, Albert Gu, and Jonathan Berant. Diagonal state spaces are as effective as structured state spaces, Advances in Neural Information Processing Systems, 35:22982-22994 2022. Cited at 3.
Michael Hahn and Mark Rofin. Why are sensitive functions hard for transformers? In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 14973-15008 2024. Cited at and 10.
Arjun Karuvally, Franz Nowak, Anderson T Keller, Carmen Amo Alonso, Terrence Sejnowski, and Hava T Siegelmann. Bridging expressivity and scalability with adaptive unitary ssms. arXiv preprint arXiv:2507.052:: 00538, 2025. Cited at 3, 5, and 8.
Behnoush Khavari, Mehran Shakerinava, Jayesh Khullar, Jemyy Huang, François Rivest, Siamak Ravanbakhsh, and Sarath Chandar. Parity requires unified input dependence and negative eigenvalues in ssms. arXiv preprint 33Xivv2508.073355 2025. Cited 5t

---

Published as a conference paper at ICLR 2026
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. Cited at 4.
Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts to automata. In International Conference on Learning Representations, 2023. Cited at
William Merrill, Jackson Petty, and Ashish Sabharwal. The illusion of state in state-space models. In International Conference on Machine Learning, 2024. Cited at I and 4.
Joseph Rotman. An introduction the theory of groups, volume 148. Springer Science & Business Media, 2012. Cited at and 16.
Yash Sarrof, Yana Veitsman, and Michael Hahn. The expressive capacity of state space models: A formal language perspective. In Conference on Advances Neural Information Processing Systems, 2024. Cited at 2, 4, and 9.
Julien Siems, Timur Carstensen, Arber Zela, Frank Hutter, Massimiliano Pontil, and Riccardo Grazzi. Deltaproduct: Improving state-tracking linear rmns via householder products. arXiv preprint arXiv:2502.10297 2025. Cited at 5.
Jimmy T.H. Smith, Andrew Warrington, and Scott Linderman. Simplified state space layers for sequence modeling. In International Conference on Learning Representations, 2023. Cited at 3.
Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Donald Metzler. Long range arena A benchmark for efficient transformers. In International Conference on Learning Representations, 2021. Cited at 3.
12

---

Published as a conference paper at ICLR 2026
A BACKGROUND: ONE-DIMENSIONAL COMPLEX AFFINE DYNAMICS
We consider the affine recurrence
J++1
X,bEC, 0,
(9)
with initial condition 2o E C. This section records complete, self-contained classification of the dynamics and then isolates the bounded regimes relevant for our work.
Closed form and fixed points.
Iterating (9) yields
c) X (a)
tc, X
2t = X'2o + 3 x k=0
c 1-X (A
(10)
1o +1,
==1,
A fixed point exists iff either À + (unique fixed point (A and 0) (every point is fixed). When À = 1 and b # 0 there is no fixed point.
b
Sfift-of-origin reduction.
When + 1, define the shift yr = 2, c with c
Then
1-X
Vo+1
XWe+
(11)
so the inhomogeneous recurrence (9) conjugate the homogeneous linear map y + Ay. All asymptotics therefore reduce to the magnitude and argument of A:
Complete case split. Let À = re with r = AN]
1. Strict contraction ([>) < 1): 34 + e exponentially at rate r' (independent of mn).
X E R50 there is rotation; otherwise each step rotates by while contracting.
2. Neutral rotation (l^l 1, 1): J and is dense on the circle centered at c otherwise.
100 - c|; the orbit periodic iff 0/2T Q
3. Neutral translation (A 1):
b 2t (every point is fixed).
b 2t = xo + t (unbounded linear drift).
4. Expansive (|>) 1): generically [rr|] - oo exponentially: the unique nongeneric exception
is (then c).
3(1)
((A)
Figure 3: We distinguish 4 cases for A: (teal) ||||| < 1, (purple) ||aa| = 1, + 1, (pink) À 1,
(gray) |||||
Boundedness. The trajectory (xt)) is bounded if either |\] 1 |X| with (A * 1) (A=11 and = 0). It is unbounded if [A] > (unless xo = c) or (A = and + 0).
Higher Dimensions. IfA E dd diagonal and b E Cd the dynamics decouple coordinate-wise and the above ID classification applies each coordinate independently.
13

---

Published as a conference paper at ICLR 2026
B THE EXAMPLE OF THE GROUP S3
B.1 CAYLEY TABLE FOR S3
(12)
(13)
(23)
(123)
(132)
(12)
(13)
(23)
(123)
(132)
(12)
(12)
e
(132)
(123)
(13)
(23)
(13)
(13)
(123)
(132)
(23)
(12)
223
(23)
(132)
(123)
(12)
(13)
(123)
(123)
(13)
(23)
(12)
(132)
e
(132)
(132)
(23)
(12)
(13)
6
(123)
Table 3: Cayley table symmetric group S3-
B.2 TWO-AUTOMATON CORRECTLY SIMULATES S3
Example 2. Consider the s" encoding for Sy elements, with (12), (123), {0,1} and 3 E {0, 1, 2]. and the transition rules described above. We represent the three states 4im This representation does not change the fact that the automaton has discrete states; rather, provides convenient way describe transitions rotations, and later to connect the automaton to SSMs with continuous states. In this view, a rotation between states corresponds to multiplying by a
26m
Q1, Q2 Q3 of the second automaton by the cube roots of unity e- e, 3 and -
20m discrete power of e 3 Starting from the initial state (1, e0), we apply each group element to obtain the automaton states and derive decoding rule that maps any automaton state back its associated group element.
For the identity e, the automaton remains (1, The swap = s' flips Q(1) to -1 while leaving
the second automaton unchanged, giving (-1,1), decoded as s. For sr Q(1) flips to 11, and the second automaton rotates according to Q( 1 and 3 2, resulting in (-1, 2: 3r decoded as
sr Similarly for sr, Q(1) flips to -1 and the second automaton rotates (-1, 25 ), decoded as
sr. Finally, for and r², with no swap, the second layer rotates positively by 3 (1,e-(3) and (I, e - 3r) decoded as and 2
2x and 4m giving
3
Table 4 summarizes this decoding rule by providing map between the states of the two-automaton and the elements of Sz.
Automaton State
Group Element in S3
(1,1)
1-1,1)
5
(-1,e'
8y
(- e
ST
(1, (1
(1, (1,)
2
Table 4: Mapping between automaton states and group elements of Sg.
Example 3. Using the encoding, decoding, and transition rules above, one can principle reproduce the full Cayley table of S₃ with the two-automaton. Here, we verify several nontrivial products to illustrate this behavior.
Trivial products such as Sr ?r? The first ? maps the automaton to (-1, ef the second flips Q(1) back to 1 and
follow immediately. For less obvious cases, consider
14

---

Published as a conference paper at ICLR 2026
rotates the second automaton by 4T/33 in the positive direction, returning the system to (1, 1), which is the correct result for two consecutive applications of the same swap. Similarly, sr sr returns the automaton to (1. Next, a sr maps to (-1,0) after 8, then sr flips Q back to and rotates the second automaton by 2 yielding e (2m/3)) = r, with = denoting the equivalence. Reversing the order, sr gives (-1, e/2 after sr, then flips Q back to 1, giving (1, e/2/3) = r².
Finally, for sr -sr?, the first sr gives (-1, e /32m/3), and 2T flips Q and rotates the second r. Conversely, sr² or maps first to (-1, e and then (1, e225/3) 2², These checks confirm that the two-automaton correctly reproduces the nontrivial entries of the Cayley table.
automaton by 4x /3/3. yielding (1,e-
C
PROOFS
C.1 PROOF OF LEMMA
Proof. We split the proof into two cases:
(Case (A(z)yl 1) In M. for g E G, we have (())())") X(9))\<)} for sufficiently large n, where z means equality at finite precision. We pick a sufficiently large such that x² = as well. Note that this is always possible for all group elements z. For this n, the input sequence (x)" transitions hj into z's center of rotation (i.e., fixed point) in coordinate Let be this center of rotation. We thus construct new SSM M with X(g) = X(gx") = (((g)(z))) R3 0 and b(g) = b(gz") = (x)("))) 22 c for all g E G, where 2, means that we are referring to the jth coordinate. In this new SSM, all inputs transition state-coordinate j into the fixed point of input x. Note that M has been constructed in such a way that it respects the group law of G. Intuitively, this new SSM acts the way the old SSM would if we were to input for times after every g seen in the input sequence and ignore the first n outputs, and since x = e, the output the new SSM should be the same.
(Case |{())y] > 1 or |(x)), = 1 A b(),, * 0) With similar argument to the previous case one construct new SSM where all inputs transition state-coordinat into inf, that is, the constant e will be equal to inf. We are assuming here that in our finite- pratte-preisionn model, whenever the magnitude of variable grows beyond some threshold, the variable gets fixed value, denoted by inf, that represents infinity.
C.2 PROOF OF LEMMA 2
Proof. With some simple algebra get
X (A(h - c1) + - -2) + = (AX*) h (AX*)a + (1 -2) +
(12)
=
h + (A* - 11)a + (1 X0
(AX = 1)
(13)
h - X²)(e2 (((22-c))
(14)
Thus, the composition simplifies to h h+ (1- c1), which is a non-zero translation since
X" # 1 and C # C2.
C.3 PROOF OF LEMMA
Proof. We can find a1, 02 E N such that A(g1) ) X(22) R 1 at finite precision, X(g1) * 1, and Xgg2) + 1. If the rotations are rational, this can be done exactly; if not, it can be done to arbitrary precision. Note that (g1)au and (g2)a2 induce neutral rotations about distinct centers in coordinate j. Thus, according to Lemma 2, the input sequence (g1)") (22 induces non-zero translation in coordinate j. Similar to Lemma 1, repeating this sequence causes the SSM to diverge inf. L
C.4 PROOF OF THEOREM
Proof of Theorem I. (+) We assume there is a single-layer DCD SSM that tracks group G and we show that G is Abelian. Applying Lemma 1 to all coordinates implies that there exists DCD
15

---

Published as a conference paper at ICLR 2026
SSM layer M that tracks G at finite precision, where input and no coordinate has contraction or expansion or translation dynamics. In other words, all inputs and all coordinates have neutral rotation dynamics. Lemma 3 then implies that all inputs must induce neutral rotations about the same center in each coordinate. As a result, the effect of any input sequence is independent of the order of the inputs, and hence the group G must be Abelian.
(=) We assume G is Abelian and we show there is a single-layer DCD SSM that tracks G. We construct a single-layer DCD SSM that tracks G. By the fundamental theorem of finite Abelian groups (Rotman, 2012), G is isomorphic to a product of n cyclic groups Ck2 x X Ck., for some n and .... kn- Every group element g can be represented as (m1.... man E [K1] x ... [k,]- The group's diagonal complex matrix representation 9 E G + A(g) E Caxn, where A(g)ss = exp(2ri K2 ) can be used as the SSM transition matrix. With enough precision bits, ky roots of unity can be distinguished for all j. Let ho 1 and b(z)= = 0. The decoder simply maps each state to the corresponding group element. This SSM tracks G at finite precision.
C.5 PROOF OF LEMMA 4
Proof. We do a proof by induction. The hase case is the single-layer case (k = 1), which says that there exists another single-layer DCD SSM that also tracks group G at finite precision, where, for all state-coordinates j E [d]. the transition dynamics is fixed or a neutral rotation about a fixed center. We have already proved this in Theorem 1.
Let's assume the claim is true for k S r 1 layers, and the goal will be to prove it for k: = r. Let (( be the SSM with the first r 1 layers simplified. We apply the same strategy as the single-layer case in Lemma 1. Arbitrarily fix a coordinate j E [d] for the rth layer and the states of the first 1 layers of (r(-1) to (1:--1), If some input sequence E keeps (1(:--1) fixed and induces a contraction or expansion or translation in the jth component of the rth layer, with similar arguments as the single-layer case, we can construct another SSM where ((rr()(1=-1),,, .g)3 R 0 for all E G. Otherwise, we skip this j. (1=--) pair as it already satisfies the claim. Intuitively, this new SSM acts the way the old SSM would if every time the state of the first r- layers was h (1:--) would input z for n times, where n is sufficiently large and such that the sequence F evaluates to identity, and ignore the first n outputs. We repeat this procedure for all j. h (1:r-1) pairs, which are finite due to the finite precision assumption. Call the final SSM ((r)
C.6 PROOF OF THEOREM 2
Proof of Theorem 2. (=) We assume there is k-layer DCD SSM M that tracks at finite precision and we show that G admits a subnormal series of length & with Abelian factors. First step of the proof is to replace the SSM with another SSM M' that tracks the group according to Lemma 4. We now do layer peeling argument starting from the first layer.
Due to finite precision, the state space is finite. There thus exists a finite input sequence that drives the system into strongly connected component C.5 Let g be the product of this sequence. For any E G. appending g - yields running product f within C, so contains at least one state decoding to each group element. Since the model is exact at all input lengths, it correctly tracks G within C. We work within C from this point.
Constructing Gk-1- For a first-layer state 21, define (overload) dec(21) as the set of group elements decodable from some state in C with first-layer component Z1. We show these decoding sets are either disjoint or equal.
Suppose g E dec(x1) ) O dec(y)). Then there exist states 8, in C with first-layer components æ1, 3/1 respectively, both decoding g. By strong connectivity, there exists a path from to s'. Since both decode to g. this path has product e. So dec(x1) S dec(y1). Similarly, there exists a path from s' to with product e. So dec(y1) C dec(x1).
The decoding sets thus partition G. Let Gk-1 = dec([x.]) where [xr]] is the equivalence class of first-layer states containing the identity. We show GR-1 subgroup. Take g, h E Gk-1- Starting
'In fact, one can show that the state space strongly connected to begin with but we don't 't need that.
16

---

Published as a conference paper at ICLR 2026
from a state decoding to h (first-layer in class [x:]], append h. The running product is g E Gk-1, so we land in class [ze]. Hence h maps class [ze] to itself. In particular, starting from e E Gk-1 and appending h 9, the running product h g lands in class [ae], so h Gk-1- It is easy to show with similar arguments that dec((a.)) for any class is a coset of Gk-1- See Figure 4 for an example.
doo(an) = Ge-1
G
Gk
a
G
dec(ra) = bG
dec(zs) = G
e, e.
a, agg
b, bgr.....
dec([r.])
deo((z.))
deo((zs))
doc(us) = -GG,
3/
dec(za) = =GG
[Tx] = {xi, maf
[xa] = {2z, m5)
dec(zr) Ga-1
[no] {ua, 26)
Figure 4: A simple example where the first-layer state is C² the group G partitioned into cosets, and each equivalence class has size 2.
Normality, For 91 E Gk-1 and a E G. the input sequences (a, 91, a )) and (g1, a, a produce the same accumulated rotation on the first layer (since rotations commute). The second has product I E Gk-1; ; the first has product agı a11 Since they land in the same first-layer class, agia E Gk-1- Thus G 2 Gk-1-
Abelian quotient. Similarly, (a, b) and (b, a) produce the same first-layer rotation for any o, b E G, so ab and ba lie in the same class, i.e., abGk-1 baG
Peeling off. Fix a first-layer state xn E [xte]- Let X' be the set of input sequences that fix zn- We claim that the set of products of these sequences is exactly Gk-1- The forward inclusion is immediate. For the reverse, take g E Gk-1- Starting from a state so with first-layer zo decoding to e, apply g to reach state 81 with first-layer y/1 (same class) decoding to g. Since g E dec([zo)), there exists state 82 in C with first-layer decoding to By strong connectivity, there is a path from 81 to 82 with product e (both decode to g). Concatenating gives a sequence with product taking 30 V1 T7-
We now restrict to inputs from X' and thus fix the first layer to xn- Note that X' closed under concatenation. With the first layer fixed, Lemma 4 gives layer 2 fixed center and inputs (from X) cause rotations on layer 2. We can now apply the same argument as we did for the first layer to obtain G P2r - with GR-1/Gr Abelian. Iterating over all k layers produces the chain.
Termination. After layers, Go consists of elements whose input sequences fix all layers. Since the model is exact, distinct elements produce distinct states, Go {e).
(=) We assume there a subnormal series (G = G₂) 2 G 2 ... P G1 (Gu = {e}) where G/11/ is Abelian for all E [k] and show that there exists k-layer DCD SSM that tracks G. We do a proof by induction on k. The base case (k = 1) is the single-layer setting which we have already proved in Theorem 1.
We now assume that we have a l - 1 layer DCD SSM that tracks the group N == Gh-1 which normal subgroup of G. We show that can add initial layer to get a k-layer DCD SSM that tracks G. The first layer is constructed following Theorem to track the Abelian group H = Ge/Ge-1-
We now describe how the first layer interacts with the top layers. Fix a section s: H - G of the quotient map G + H. Every g G be written as g s(h) for some n N and h E H, and we use this representation for the SSM state. For an input token we write = s(h) and assume it gight-multiplies the state.
Let the current state be g' n' s(h') and the input be g = s(h) n. Then
و'g n' s(h') s(h) n.
(15)
17

---

Published as a conference paper at ICLR 2026
Since (h)) and s(hhh) lie in the same coset of N, there exists d(W, Rt) E N such that
s(h') s(h) = d(h', h) s(h'h).
(16)
Substituting and inserting shhhh)- on the right gives
9'g= = n' d(h', h) (s(h'h) n s(h'h) s(hhh).
(17)
Because N 4 G. the conjugated term s(hh)) ((hih) lies in N. Thus the updated state has the form n' (Nh',, ())h,, where k(h', = d(h', h) (k") -1) E N. This means that the first layer should update its state by applying h E H and output n: a(h,99 .9) N as input to the top k 1 layers to achieve the overall desired update of group G. See Figure 5.
state: g' n' s(h) G
state: n' s(hh)
state: n' k( g) s(hh)= = 96g
layer k
state: n' E N
state: n
state: n' k(K( :
layer 2
[x( g)
layer
state: M E H
state: 1/h
state: Rh
g s(h)
(a)
(b)
(c)
Figure 5: (a) Model is in state g' and receives input g. (b) First layer updates from h' h'h and outputs s<h'.g) g)- (c) Higher layers update from n' to n' n'k(h', ,)) The final collective state is n'rs(h' ()s((h)))))))) g'g g as desired.
18


Reviews:
[{"review_id": "ejf47MYGGz", "reviewer": "Reviewer_6RjB", "summary": "This paper demonstrates the limitations of input-dependent complex diagonal SSMs in terms of expressiveness for groups state tracking. The authors show that a single layer can track Abelian groups, and k layers can solve up to depth k; thus a two-layer model can track S_3. The paper also shows that diagonal models are expressive enough in theory, but in fact hard to train on non-Abelian tasks.", "questions": "- How many, and what different training settings have the authors tried?\n- Do the results look the same no matter how the settings (e.g., hyperparam, learning rate, weight decay, scheduling) change?\n- how crucial is the universal decoder?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The authors provide clear iff theorems and link depth with group structure: i.e., 1-layer - Abelian, and k-layer - length <= k. The paper also provides a good demonstration of two-layer S_3 that illustrates the theory, and presents an interesting observation that expressivity does not directly lead to learnability in reality.", "weaknesses": "- It is uncertain if the observations in this paper will directly lead to same results in real-world benchmarks such as language modeling.\n- the experiments in the paper are limited, not providing results with different state dimensions, precisions, and decoders.\n- it is uncertain how the training details in the paper, and unclear if it is actually true that expressivity != learnability.", "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": "twFcin9i59", "reviewer": "Reviewer_1jQf", "summary": "The paper studies the expressivity of input dependent, complex valued diagonal state space models. Is shows that under some mild decoder conditions, the single layer can track any abelian group but not any non-abelian group. The paper performs empirical experiments that show that while multi-layer DCD SSMs are theoretically expressive enough for non-abelian groups, they fail to learn it in practice.", "questions": "Is there some relevant real world task that correspond to non-abelian group?", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper improves the understanding of the expressivity of State Space Models (SSM), by focusing on a specific type of SSM and a particular data type (abelian vs non-abelian groups). This seems to be a fresh perspective on analyzing expressivity and the theory appears to be rigorous.", "weaknesses": "One concern is on the significance of the result. Does this make the SSM architecture more expressive (or less) than a transformer? Does this have any practical implications on how we should train SSMs? \n\nAnother point that makes it harder to understand the significance of the theory is that the experimental results do not directly support the theory but instead suggest that the finding that even if the models theoretically can learn certain tasks, the optimization fails to do it. This is not in itself bad, but the paper would have been much stronger if there were empirical results that supported the theory. \n\nFor the task C_60, for instance, it's not clear how the training task is generated. Is the input 1,2,3,4,..., or is it a random draw of numbers between 1 and 59, or something else. \n\nMinor: \nSomewhat unusual formatting with the theorem boxes.\nI suspect that many people who are experts on SSMs may not be deeply familiar with group theory. Hence giving concrete example to show what for instance, C_60, is may allow a broader audience enjoy the paper.", "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": "rngLtKBJRS", "reviewer": "Reviewer_644N", "summary": "This paper studies the theoretical expressivity of diagonal State-Space Models (SSMs) on group state-tracking tasks. They show that a single-layer input-dependent complex-valued diagonal (DCD) SSM can track a group G at finite precision if and only if G is Abelian. A $k$-layer DCD SSM can track a group G if and only if G has a subnormal series of length at most $k$ with Abelian factor groups. The authors show a gap between this theory and their experiments. While the theory shows multi-layer diagonal SSMs can express solvable non-Abelian groups, experiments demonstrate they struggle to learn these solutions in practice. Even 2-layer models that can theoretically represent S3 fail to learn generalizable solutions.", "questions": "1. Which real-world sequence modeling tasks actually require tracking non-Abelian groups? I'm not familiar enough with the matter to know how common these requirements are in NLP and other related domains\n2. Can you identify any specific optimization challenges when learning non-abelian groups? (e.g. loss landscape, initiatlization?) Given the explicit construction for S3, could we initialize models closer to theoretical solutions to improve learnability?\n3. What's the minimal architectural change needed to make non-Abelian groups learnable? Would 2×2 block-diagonal suffice for S3?\n4. How do these limitations apply to transformers, if at all?", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper provides necessary and sufficient conditions for when diagonal SSMs can track groups, not just sufficient conditions or impossibility results\n2. The connection to group theory seems an elegant way to relate architectural constraints to algebraic properties.\n3. The paper doesn't just prove existence - it shows explicit constructions demonstrating how multi-layer diagonal SSMs can track non-Abelian groups.\n4. The experimental section reveals an important gap between expressivity and learnability\n5. The paper carefully handles finite precision constraints, which are practically relevant and often glossed over in theoretical work.\n6. The results apply to popular SSM variants like Mamba", "weaknesses": "1. The experiments only test on 5 groups and don't explore what makes some solvable groups learnable vs others. More extensive experiments would strengthen claims about the learnability gap.\n2. While the paper identifies that multi-layer models fail to learn non-Abelian groups, it doesn't deeply investigate why or propose solutions beyond noting \"optimization difficulties\"\n3. State-tracking is a specific synthetic task family. The paper doesn't clearly connect these limitations to practical sequence modeling tasks\n4. The paper doesn't compare with non-diagonal SSMs empirically, which would help quantify the cost of the diagonal constraint in practice.\n5. While mentioning block-diagonal structures could help, the paper doesn't explore intermediate architectures between fully diagonal and fully dense.\n6. The paper could better position results relative to circuit complexity findings ($TC^0$) and explain what new understanding this group-theoretic view provides--that was not very clear to me.", "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": "a7ZOsZAXI6", "reviewer": "Reviewer_MdGT", "summary": "This paper provides a theoretical characterization of what diagonal State-Space Models (SSMs) can and cannot learn when tracking sequential state information. The main results can be summarized as\n    1. A single diagonal SSM layer with complex values can track any Abelian group but cannot track any non-Abelian group.\n    2. A k-layer diagonal SSM can track a group if and only if that group has a \"subnormal series\" of Abelian factor groups with length ≤ k. This means stacking layers expands expressivity to solvable groups in a precise, depth-dependent way.\n    3. While multi-layer models are theoretically expressive enough for certain non-Abelian groups, they consistently fail to learn these solutions in practice with standard gradient descent.", "questions": "The theoretical contribution is significant. I'm interested in whether there are any real applications that can make use of this results. For example in material science, there may exists certain task that the symmetry property may exists?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The notations and logical flow is very clear make it easy to follow the results.\nThis work provides a complete characterization of diagonal SSM expressivity and exposes a critical gap between representational capacity and optimization. \nDiagonal SSMs form a strict subset of the computational hierarchy: sufficient for Abelian group structures but provably insufficient for non-Abelian groups at single-layer depth, with depth providing only limited help in practice.", "weaknesses": "The results are pure theoretical, it would be good if there is any connections to real applications.", "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 (Poster)