The Expressive Limits of Diagonal SSMs for State-Tracking

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$ in $SO(3)^m$ and $[u^{30},v^{30}]\in Z(G),[u^{30},v^{30}]^2=e$ in $SU(2)^m,SO(4)^m$, excluding $S_5$), and sharp threshold $d^*(S_5)=d^*(A_6)=5$ in $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)$ in $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\%$ at $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.

We study how depth, finite precision, state dimension, and chain-of-thought (CoT) affect the expressive power of multi-layer state-space models (SSMs). For the explicit-table $K$-function-composition problem, a canonical benchmark for sequential information propagation, we prove that any $L$-layer SSM solving $(L+3)$-function composition must satisfy $d^2p=Ω(N/L^3)$, where $d$ is the state dimension and $p$ is the per-scalar precision. Conversely, $K$-function composition is solved exactly by a $(K+1)$-layer generalized SSM with $d=1$ and $p=Θ(\log N)$. This gives a worst-case depth hierarchy for this formal problem family. We then distinguish post-input reasoning, in which all thought tokens are generated after the input, from input-interleaved reasoning, in which thought tokens may be inserted while the input stream is being read. Post-input reasoning does not circumvent our communication-based lower-bound pipeline, whereas input-interleaved reasoning admits bidirectional simulations with general deterministic one-pass streaming algorithms at the granularity of persistent memory. Finally, width and precision are not interchangeable under exact step-preserving simulation in the base affine-state model, but become interchangeable through the streaming-memory characterization once input-interleaved reasoning is allowed.

State Space Models (SSMs) have emerged as a powerful paradigm for efficient long-sequence modeling, offering parallel training and fast linear-time recurrent inference. However, like other recurrent architectures, SSMs must compress an unbounded history into a fixed-size state, which limits context retention and makes precise retrieval over long-range context inherently difficult. To overcome this limitation, we propose Delay State Space Models (DSSMs), a delay differential equation (DDE)-inspired extension of diagonal SSMs that augments discrete SSM recurrences with explicit delayed-state feedback. Making explicit delayed feedback practical requires new stability parameterization, history management, and FFT-training tools. We address these challenges with a practical discretization and parameterization grounded in a simple delay-independent stability condition. To bypass direct time-domain kernel construction, we derive the DSSM transfer function and compute kernels in the frequency domain, using a kernel contour shift to suppress aliasing and recover accurate FFT training. Empirically, DSSMs substantially improve targeted delayed-retrieval tasks while outperforming S4D on most standard sequence metrics and remaining close on the others.