Skip to main content
Back to timeline
arXivSource publication:

Order in linear recurrent memory gets an algebraic test: HyperSSM stays exact on a 32-generator group task with quaternion channels

Synopsis

Whether a linear recurrent memory can retain the order of its inputs depends on the number system its transition matrices live in. Efficient parallel scans have relied on diagonal recurrences, and real or complex transitions commute, so the state records which inputs occurred but not their order. HyperSSM adds quaternion blocks to each channel while keeping linear-time inference and parallel training, solving group tasks exactly with at most five state numbers, including 32 generators, and staying exact on sequences 25 times longer than training.

Source-provided article image: Symmetry in Time: A Representation Theory of Linear Recurrent Memory
arXiv

Interpretation

The state update of a linear recurrent memory is a linear representation of the monoid of input sequences, so a channel tracks a group at every length exactly when that group is a quotient of the group generated by its transition matrices. Earlier analyses fixed a family of transitions and asked what it could do, such as complex diagonal layers and abelian stacks; this work asks first which memory a task requires. The criterion holds for a channel over any associative algebra, and the earlier depth theorem for complex diagonal layers becomes its special case for complex channels.

Every such memory splits into independent blocks over the real, complex and quaternion numbers, so an order-preserving channel needs at least four real dimensions in its transitions. In diagonal SSMs all transitions commute and can be diagonalized together, splitting memory into one-dimensional channels; non-commuting transitions cannot be diagonalized but can still be block-diagonalized. Unitary matrices, Householder products, permutation matrices and rotations, previously studied as separate families, all become blocks of these three kinds.

HyperSSM lets each channel choose its own number system, and a quaternion channel's input sets both a rotation axis and an angle; the rest matches Mamba's selective SSM. Real and complex multiplication commute, so reordering steps leaves the state unchanged and no readout can recover order; quaternion multiplication does not commute. All channels share one parallel scan, so linear-time inference and parallel training keep the same work and depth, with a quaternion product costing 16 real multiplications against 4 for a complex one.

On formal-language and group benchmarks, HyperSSM is exact with one to five state numbers, including permutations of five objects with 32 generators. In that setting PD-SSM with 128 complex numbers reaches 1.07% accuracy and Gated DeltaProduct 1.23%, near the 0.83% chance level. The model is trained only on final answers, receives no information about the task's group, and stays exact on sequences 25 times the training length.

Perspective

The theory covers linear recurrences, bounded transitions and continuous readouts; experiments are limited to formal-language and group benchmarks, BROAD gyroscope data, single-qubit gate sequences and a torsion-angle representation of protein backbones.

A quantitative theory under decay and noise, a depth bound when lower layers take a continuum of values, extensions to resets and all regular languages, and whether this legibility survives in large models mixing such channels with attention all remain open; for modular arithmetic an exact three-number memory exists but gradient descent does not find it.