cs.LGNov 12, 2026

Symmetry in Time: A Representation Theory of Linear Recurrent Memory

Authors: Anif N. Shikder, Ramit Dey, Jan Minac, Lyle E. Muller

Organizations: Fields Lab for Network Computation, Fields Institute, Toronto ON, Canada · Department of Mathematics, Western University, London ON, Canada · Department of Neuroscience, University of Texas at Dallas, Richardson TX, United States

Abstract

State space models (SSMs) are an emerging alternative to Transformers. SSMs offer linear-time inference and parallel training, but most implementations make the parallel scan efficient by making the recurrence diagonal: each channel of the hidden state is multiplied by an input-dependent real or complex number. These numbers commute, so the state records which inputs occurred but not their order. We formalize this with representation theory, which explains and fixes the state-tracking failures previously reported for SSMs. The state update defines a linear representation of the monoid of input sequences, and we show that an SSM tracks a group at every sequence length exactly when that group is a quotient of the group generated by its transition matrices. Two consequences follow. Diagonal real- and complex-valued SSMs can track only commutative groups, while the transition matrices of any SSM that can track a group must split into independent blocks over the real, complex, and quaternion numbers. We then introduce HyperSSM, which adds quaternion channels while keeping linear-time inference and parallel training. Trained only on final answers, HyperSSM solves the group tasks of recent state-tracking benchmarks exactly with at most five state numbers. This includes S5S_5 with 32 generators, where previous SSMs are at chance, and HyperSSM generalizes to sequences 25 times longer than those seen in training. Because the theory says what the transitions must encode, the learned weights of the linear recurrence can be interpreted directly. We demonstrate this by recovering the calibration of a real gyroscope, the rotations of imperfect qubit gates and the geometry of protein backbones.

Figures & tables

Explore similar work

Sep 29, 2026

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

Structured state-space sequence models (SSMs) achieve linear-time inference and logarithmic-time parallel training via associative scans, yet diagonal transitions generate solvable semigroups unable to track non-solvable group words or 3D rigid-body manifolds. We present Non-Commutative Lie-Algebraic State-Space Models (Lie-SSMs), parameterizing recurrent updates on Lie algebra tangent spaces via the matrix exponential. First, using an o-minimal cylindrical flag collar, we establish an unconditional single-layer finite-division criterion for contracting SO(3)SO(3) and SU(2)SU(2) heads, proving odd-prime Sylow abelianity, odd-pp-core centrality, and exponent-30 commutator obstructions excluding S5S_5 in SO(3)m,SU(2)m,SO(3)^m, SU(2)^m, and SO(4)mSO(4)^m while identifying the sharp threshold d∗(S5)=d∗(A6)=5d^*(S_5)=d^*(A_6)=5 in SO(5)SO(5). Second, Depth-2 semidirect and Schreier 22-cocycle cascades resolve S5S_5, 2I≅SL2(F5)2I\cong SL_2(F_5), and Heis(Fp)\mathrm{Heis}(F_p) in O(log⁡T)O(\log T) scan depth, whereas unnormalized contracting coupling collapses exponentially without Directional RMSNorm. Third, we characterize the Θ(εc−1)Θ(\varepsilon^{c-1}) Chen--Magnus--Hall--Witt commutator saddle and 1/∣[G,G]∣1/|[G,G]| coset-centroid dilution, proving generic first-order symmetry breaking at ε=0\varepsilon=0 and teacher-forced local Polyak--Łojasiewicz convergence under dense prefix supervision and factored readouts (99.90%/99.40%99.90\%/99.40\% on S5S_5 at T=128T=128; 100.00%100.00\% on D16D_{16}). Across SE2(3)SE_2(3) Left-Jacobian odometry, Hillis--Steele/Blelloch GPU scans (48.24×48.24\times forward, 20.27×/10.28×20.27\times/10.28\times full-layer speedup at T=2048T=2048), and three 3D IMU benchmarks (UCI HAR, UCI HAPT-PT, and 17-subject REALDISP), Lie-SO(3)SO(3) models reach 95.69%±0.14%95.69\%\pm 0.14\% on HAR, 88.44%±0.83%88.44\%\pm 0.83\% episode logit-vote (83.97%±1.20%83.97\%\pm 1.20\% C3 window in 30-subject 5-fold CV; 87.16%±0.64%87.16\%\pm 0.64\% 9-subject split) on HAPT-PT, and 84.23%±1.00%84.23\%\pm 1.00\% on REALDISP.
Mar 2, 2026

The Expressive Limits of Diagonal SSMs for State-Tracking

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 kk-layer DCD SSMs can express state-tracking of a group if and only if that group has a subnormal series of length kk, with Abelian factors. That is, we identify the precise expressivity range of kk-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.
Oct 9, 2026

ReplaySSM: Cache SSM Inputs, Not State

State-space models (SSMs) maintain a fixed-size recurrent state, but reading and writing it at every decoding step can bottleneck hybrid models. This eager state management causes large state I/O with low arithmetic intensity, leaves speculative decoding no cheap rollback, and feeds state quantization error into subsequent recurrent updates. We introduce ReplaySSM, which unrolls the recurrence to represent the state as a checkpoint and a buffer of recent SSM inputs. This separates output computation from checkpoint updates. By updating the checkpoint periodically, ReplaySSM avoids state writes on most steps and roughly halves the dominant state memory traffic. Keeping recent inputs also makes speculative rollback a buffer-pointer operation and enables output-only verification without materializing intermediate states. The same separation allows a low-precision checkpoint to serve output computation on most steps while a higher-precision checkpoint serves recurrent updates, so rounding error in the low-precision copy never enters later updates. We implement ReplaySSM in vLLM for Mamba-2 and Gated DeltaNet. At serving batch size 256, it accelerates standard decoding by 1.201.20--1.47×1.47\times over a tuned vLLM baseline across four hybrid models, and delivers about 1.8×1.8\times the throughput of vLLM's speculative decoding on the two 120B-class models. Separate state precisions also reduce output KL divergence and downstream accuracy losses compared with a shared low-precision checkpoint.