Symmetry in Time: A Representation Theory of Linear Recurrent Memory

Anif N. Shikder, Ramit Dey, Jan Minac, Lyle E. MullerarXiv 2026 · arXiv

TL;DR

State Space Models (SSMs) are efficient alternatives to Transformers, but they often fail to track the order of events because their underlying math is "commutative"—like adding numbers, the order doesn't change the result. This paper uses representation theory to prove that tracking non-commutative order requires more complex number systems, leading to HyperSSM, a model that uses quaternions to achieve perfect state tracking on tasks where previous models failed completely.

What Problem Does This Paper Address?

While Transformers dominate sequence processing, their computational cost grows quadratically with sequence length ($O(L^2)$). State Space Models (SSMs) like Mamba offer a linear-time ($O(L)$) alternative. However, to make SSMs fast to train, researchers usually make them "diagonal," meaning each hidden state channel is just a single real or complex number.

The problem is that real and complex multiplication is commutative: $a \times b$ is always equal to $b \times a$. If your memory is just a product of these numbers, it can tell you which inputs occurred, but it fundamentally cannot tell you the order in which they happened. This makes SSMs struggle with "state tracking" tasks—like following a sequence of moves on a Rubik's cube or tracking variables in a computer program—where the order of operations is everything.

Methods

The authors bridge the gap between deep learning and abstract algebra by treating the hidden state of an SSM as a linear representation of the input sequence.

  1. The Algebra Ladder: They prove that the "expressive power" of a memory channel is strictly limited by its number system.
  2. Real numbers can only track parity (even/odd).
  3. Complex numbers can count and handle periodic patterns (abelian groups).
  4. Quaternions (4D numbers) are the "cheapest" way to track non-commutative rotations and complex permutations.
  5. HyperSSM: They introduce a new architecture where each channel can choose its own algebra (Real, Complex, or Quaternion).
  6. Parallel Scan: Despite using quaternions, HyperSSM remains efficient because quaternion multiplication is associative, allowing it to use the same "parallel scan" algorithms that make standard SSMs fast.
  7. Sign-Invariant Readout: They use a specific readout mechanism for quaternions that ignores the "global phase" (the fact that $q$ and $-q$ represent the same rotation), which is crucial for tracking certain mathematical groups like $A_5$.
FIG. 2. The algebra ladder. Each box represents an alge- bra with its associated properties. The number of real compo- nents is indicated; on the right, bounded transitions and the groups tracked by a single channel are shown (Theorem 1). For fewer than four components, every algebra is commutative (Corollary 1). Increasing the width of a layer results in lateral movement and does not cross the dashed line, above which S5 is tracked. In contrast, increasing depth does: a sign chan- nel beneath a quaternion channel tracks S5 with five numbers (Proposition 2; Table II). Shaded regions indicate channels of standard diagonal SSMs.

Datasets

The authors evaluated HyperSSM on three types of tasks:

  • Formal Languages: Parity, Even pairs, Cycle navigation, and Modular arithmetic.
  • Group Word Problems: Tracking permutations in the symmetric group $S_5$ (32 generators) and rotations of an icosahedron ($A_5$). These are considered "hard" benchmarks for recurrent models.
  • Physical Systems:
    • BROAD: Real-world gyroscope data for orientation estimation.
  • Qubit Gates: Sequences of quantum gates with simulated noise.
  • Protein Backbones: Reconstructing the 3D geometry of proteins from the Protein Data Bank (PDB).

Key Insights and Ideas

  • Order has a minimum cost: The paper proves a "Corollary 1": to preserve order in a single channel, you need at least four real dimensions. This explains why 1D real or 2D complex SSMs were doomed to fail on non-commutative tasks.
  • Diagonal SSMs are Fourier Transforms: The authors show that standard diagonal SSMs are essentially performing a Fourier decomposition of time-invariant memory.
  • Depth vs. Algebra: While stacking many simple layers (depth) can help track some ordered sequences, it only works for "solvable" groups. To track "simple" groups like $A_5$ (the symmetries of an icosahedron), you must have the right algebra in the channel itself.
  • Weights are Interpretations: Because the model is mathematically grounded, the learned weights aren't just "black box" numbers. In the gyroscope task, the weights directly recovered the sensor's physical calibration. In the qubit task, they recovered the actual rotation angles of the gates.
FIG. 1. Order in a linear memory. (a) One step of a selective SSM; shaded, the tracking regime (no decay, x0 = 1, one transition per symbol). (b) After a word w, a channel holds the ordered product Q(w); it tracks the group if a continuous readout recovers π(w) from Q(w) at every length. (c) A complex channel stores a phase; turns add, and order is lost. (d) A quaternion channel stores a 3D orientation; 90◦turns about x and z in either order give different states. (e) q and −q are the same rotation; a sign-invariant readout tracks A5, a sign-aware one tracks Q8. (f) H tracks A5 but not S5; M2(H) tracks S5.

Key Results

  • Perfect Tracking: HyperSSM solved the $S_5$ permutation task (32 generators) with 100% accuracy using only 5 state numbers. Previous state-of-the-art SSMs performed at chance (near 0%).
  • Extreme Generalization: Models trained on sequences of length 40 maintained 100% accuracy on sequences of length 1,000—a 25x generalization.
  • Physical Accuracy: On the protein backbone task, a single quaternion channel was more accurate than standard bond geometry reconstructions, capturing the average geometry of real proteins better than traditional methods.
  • Efficiency: HyperSSM achieves these results while maintaining the linear-time scaling required for long-context modeling.
HyperSSM maintains near-zero error on physical rotation tasks even as sequence length grows far beyond training.

Limitations and Future Work

  • The "Tracking Regime": Much of the theory assumes no "decay" (the model remembers everything forever). While the authors show HyperSSM works with decay, a full quantitative theory for noisy, decaying memory is still open.
  • Scaling: While HyperSSM excels at these "pure" tracking tasks, its performance as a component in massive, multi-billion parameter language models remains to be tested.
  • Solvability Bound: The paper notes that while depth helps, there is a hard limit to what commutative stacks can do. Exploring how this interacts with the "attention" mechanism in hybrid models is a promising next step.

Summary updated

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 $S_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.
BibTeX
@misc{shikder2026symmetry,
  author = {Anif N. Shikder and Ramit Dey and Jan Minac and Lyle E. Muller},
  title = {{Symmetry in Time: A Representation Theory of Linear Recurrent Memory}},
  year = {2026},
  eprint = {2611.17162},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.17162},
}
Figure