The Expressive Limits of Diagonal SSMs for State-Tracking

Mehran Shakerinava; Behnoush Khavari; Siamak Ravanbakhsh; Sarath Chandar

cs.LGMar 2, 2026

The Expressive Limits of Diagonal SSMs for State-Tracking

Authors: Mehran Shakerinava, Behnoush Khavari, Siamak Ravanbakhsh, Sarath Chandar

Organizations: School of Computer Science, McGill University · Mila – Quebec AI Institute · Chandar Research Lab · Polytechnique Montréal

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.

Figures & tables

Model	$A(x)$	$B(x)$	$\dec(h,x)$
S4	$\Lambda$	$Bx$	$\sigma(\Re(Ch)+Dx)$
S4D	$\Lambda$ (diagonal)	$Bx$	$\sigma(\Re(Ch)+Dx)$
Mamba	$\exp(\Delta(x)\odot\Lambda)$	$\Lambda^{-1}\!\big(\exp(\Delta(x)\odot\Lambda)-I\big)Bx$	$\sigma(C(x)h+D(x))$
Negative Mamba	$2\exp(\Delta(x)\odot\Lambda)-I$	$\Lambda^{-1}\!\big(\exp(\Delta(x)\odot\Lambda)-I\big)Bx$	$\sigma(C(x)h+D(x))$
AUSSM	$\exp(i\Delta(x)\odot\Lambda(x))$	$\Delta(x)Bx$	$\sigma(C(x)h+D(x))$

Table 1: Summary of SSM variants in terms of their transition matrix

A(x)

, input vector

B(x)

, and decoder

\dec(h,x)

Panel of Figure 2 — Figure 2: 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.

Table 2: Performance of various models on state-tracking tasks. Each table reports the longest sequence length

\geq 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. ✘ indicates that the model failed to extrapolate to long sequences.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 3 — Figure 3: We distinguish 4 cases for $\lambda$ : (teal) $\|\lambda\|<1$ , (purple) $\|\lambda\|=1,\lambda\neq 1$ , (pink) $\lambda=1$ , (gray) $\|\lambda\|>1$ .

$\cdot$	$e$	$(12)$	$(13)$	$(23)$	$(123)$	$(132)$
$e$	$e$	$(12)$	$(13)$	$(23)$	$(123)$	$(132)$
$(12)$	$(12)$	$e$	$(132)$	$(123)$	$(13)$	$(23)$
$(13)$	$(13)$	$(123)$	$e$	$(132)$	$(23)$	$(12)$
$(23)$	$(23)$	$(132)$	$(123)$	$e$	$(12)$	$(13)$
$(123)$	$(123)$	$(13)$	$(23)$	$(12)$	$(132)$	$e$
$(132)$	$(132)$	$(23)$	$(12)$	$(13)$	$e$	$(123)$

Appendix

Table 3: Cayley table of the symmetric group

S_{3}

Automaton State	Group Element in $S_{3}$
$(1,1)$	$e$
$(-1,1)$	$s$
$(-1,e^{i\frac{4\pi}{3}})$	$sr^{2}$
$(-1,e^{i\frac{2\pi}{3}})$	$sr$
$(1,e^{-i\frac{2\pi}{3}})$	$r$
$(1,e^{-i\frac{4\pi}{3}})$	$r^{2}$

Appendix

Table 4: Mapping between automaton states and group elements of

S_{3}

State Space Models

State space models represent sequences through evolving latent states, enabling efficient temporal modeling, system identification, and forecasting.

See all 295 papers

Non-Commutative Lie-Algebraic State-Space Models: Finite-Division Variety Laws, Semidirect Cascades, and Gradient Saddle Escape
Sep 29, 2026Zeyu JiaState Space Models Sequence Modeling
School of Biomedical Engineering and Technology, Tianjin Medical University, Medical School, Tianjin University · School of Biomedical Engineering and Technology, Tianjin Medical University · Medical School, Tianjin University
On the Expressive Power and Limitations of Multi-Layer SSMs
Apr 16, 2026Nikola Zubić, Qian Li, Yuyi Wang +1CoT Reasoning State Space Models
Robotics and Perception Group, University of Zurich · Shenzhen International Center For Industrial And Applied Mathematics, Shenzhen Research Institute of Big Data · Tengen Intelligence Institute, CRRC Zhuzhou Institute
DSSMs: State Space Models with Explicit Memory via Delay Differential Equations
Jul 11, 2026Yixiao Qian, Song Chen, Jiaxu Liu +2Dynamical Systems Long-Context Modeling
College of Control Science and Engineering, Zhejiang University · Department of Mathematics, National University of Singapore · School of Mathematical Sciences, Zhejiang University

Sep 29, 2026J/K move · Enter open · S save

Non-Commutative Lie-Algebraic State-Space Models: Finite-Division Variety Laws, Semidirect Cascades, and Gradient Saddle Escape

Zeyu Jia

School of Biomedical Engineering and Technology, Tianjin Medical University, Medical School, Tianjin University · School of Biomedical Engineering and Technology, Tianjin Medical University · Medical School, Tianjin University

State Space Models Sequence Modeling Lie Group Methods Associative Memory

Open paper AskPDF arXiv

Structured state-space models (SSMs) achieve linear-time inference and logarithmic-time parallel training via associative scans, yet homogeneous diagonal transitions generate solvable semigroups unable to track non-solvable group words or 3D rigid-body manifolds. We develop a theoretical and empirical framework for Non-Commutative Lie-Algebraic State-Space Models (Lie-SSMs), parameterizing recurrent updates on Lie algebra tangent spaces via the matrix exponential. First, via an o-minimal multi-rate cylindrical flag collar, we establish an unconditional single-layer finite-division criterion for homogeneous contracting

SO(3)

and

SU(2)

heads, proving odd-prime Sylow abelianity, odd-

p

-core centrality

[u^2,x]=e

, exponent-30 commutator laws (

[u^{30},v^{30}]=e

SO(3)^m

and

[u^{30},v^{30}]\in Z(G),[u^{30},v^{30}]^2=e

SU(2)^m,SO(4)^m

, excluding

S_5

), and sharp threshold

d^*(S_5)=d^*(A_6)=5

SO(5)

. Second, Depth-2 semidirect and Schreier

2

-cocycle cascades resolve

S_5

2I\cong SL_2(F_5)

, and

\mathrm{Heis}(F_p)

O(\log T)

depth, whereas unnormalized contracting coupling collapses exponentially without Directional RMSNorm. Third, we characterize the

O(\varepsilon^{c-1})

Chen--Magnus--Hall--Witt commutator saddle and

1/|[G,G]|

coset-centroid dilution, proving

\varepsilon=0

symmetry breaking and local Polyak--Łojasiewicz convergence (

θ_{\max}<π

), solving

S_5

(

99.90\%/99.40\%

T=128

) and

D_{16}

(

100.00\%

) via dense prefix loss and factored readouts. Across

Q_8,A_5,S_5,D_{16}

, Dyck-2,

SE_2(3)

Left-Jacobian odometry, GPU scans (

26.03\times

speedup), and three 3D IMU cohorts (UCI HAR, HAPT-PT 30-subject CV, and REALDISP), Depth-2 Lie-

SO(3)

cascades reach

95.69\%\pm 0.14\%

on HAR,

87.16\%\pm 0.64\%

(

88.32\%\pm 0.93\%

30-subject episodes) on HAPT-PT, and

84.23\%\pm 1.00\%

under displacement on REALDISP.

Abstract

State Space Models

Explore similar work

Non-Commutative Lie-Algebraic State-Space Models: Finite-Division Variety Laws, Semidirect Cascades, and Gradient Saddle Escape

On the Expressive Power and Limitations of Multi-Layer SSMs

DSSMs: State Space Models with Explicit Memory via Delay Differential Equations