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

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

    Sep 29, 2026Zeyu JiaState Space ModelsSequence Modeling

  2. The Expressive Limits of Diagonal SSMs for State-Tracking

    Mar 2, 2026Mehran Shakerinava, Behnoush Khavari, Siamak Ravanbakhsh +1State Space ModelsState Tracking

  3. ReplaySSM: Cache SSM Inputs, Not State

    Oct 9, 2026Ze-Wei Liou, Harris Nover, Amey Naik +4Inference AccelerationLLM Inference Acceleration