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.
- The Algebra Ladder: They prove that the "expressive power" of a memory channel is strictly limited by its number system.
- Real numbers can only track parity (even/odd).
- Complex numbers can count and handle periodic patterns (abelian groups).
- Quaternions (4D numbers) are the "cheapest" way to track non-commutative rotations and complex permutations.
- HyperSSM: They introduce a new architecture where each channel can choose its own algebra (Real, Complex, or Quaternion).
- 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.
- 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$.
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.
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.
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