Non-Commutative Dynamics for Expressive State Space Models

41 concepts23 papers1 proposal

Modern sequence modeling has seen a shift toward State Space Models (SSMs) like Mamba and S4, which offer linear-time scaling by replacing the quadratic attention of Transformers with linear recurrence. To achieve this efficiency, these models typically constrain their state transition matrices to be diagonal. While this allows for fast parallel computation via prefix sums, it introduces a fundamental mathematical bottleneck: commutativity.

The Commutativity Constraint

In a standard linear recurrence, the hidden state $h_t$ is updated by a transition matrix $A$: $h_t = A h_{t-1} + B x_t$. When $A$ is restricted to a diagonal matrix, the operations performed at each timestep effectively commute. Mathematically, if you have two diagonal transition matrices $A_1$ and $A_2$, their product is the same regardless of order ($A_1 A_2 = A_2 A_1$).

As Shakerinava et al. demonstrate, this commutativity prevents a single layer from capturing any logic where the specific order of inputs is critical. This is not just a theoretical curiosity; it means that a single diagonal SSM layer is restricted to tracking Abelian (commutative) groups. It can count, but it cannot easily track permutations or complex state transitions where "doing A then B" results in a different state than "doing B then A."

The Representational Ceiling

The limitation of diagonal dynamics manifests as a failure to represent certain classes of Finite State Automata (FSA). Kremer established early on that architectures with restricted recurrence lack the computational power to represent state cycles like modulo-3 counters. More recently, Terzic et al. showed that diagonal SSMs are fundamentally limited to commutative automata, making them unable to solve tasks involving non-solvable groups.

This "expressivity gap" explains why efficient models often struggle with algorithmic reasoning. For example:

  • State Tracking: Merrill et al. argue that because diagonal SSMs can be reduced to parallel prefix sums, they fall into the complexity class $\mathsf{TC}^0$. This prevents them from solving "hard" tracking problems—like evaluating code or tracking chess pieces—without increasing depth significantly as sequences grow.
  • Arithmetic and Logic: Fan et al. identify that many linear recurrent networks (LRNNs) cannot represent non-commutative operations like subtraction, causing them to rely on spurious shortcuts that fail during length extrapolation.
  • Permutations: Movahedi et al. note that diagonal models fail at tracking permutations because their transition matrices cannot represent the necessary data mixing across channels.

Hierarchies of Expressivity

Researchers have begun to map out exactly what different matrix structures can represent. Shakerinava et al. provide a hierarchy: a single diagonal layer tracks Abelian groups, while stacking $k$ layers allows the model to track solvable groups of length $k$. However, even with infinite depth, purely diagonal architectures remain unable to represent non-solvable group structures.

To break this ceiling, the dynamics must become non-commutative. Ebrahimi et al. suggest an algebraic hierarchy where complex-valued rotations are required for commutative groups, but full bilinear forms—where the input multiplicatively interacts with the state—are necessary for true non-commutative state tracking.

Beyond Diagonal Matrices

To recover expressivity without sacrificing the linear scaling that makes SSMs attractive, several structural alternatives have been proposed:

  1. Dense and Structured Sparse Transitions: Terzic et al. introduced the Selective Dense SSM (SD-SSM), which uses non-commutative dynamics to emulate complex regular languages. To maintain efficiency, Terzic et al. later proposed "Structured Sparse" matrices ($P \times D$) that provide the expressivity of dense models with the speed of diagonal ones.
  2. Block-Diagonal and Higher-Order Units: Dubinin et al. and Fan et al. utilize block-diagonal matrices to enable richer state mixing. This allows the model to capture dependencies that a strictly diagonal matrix would miss.
  3. Complex and Negative Eigenvalues: Cohen et al. prove that complex parameterizations are essential for modeling oscillatory signals. Similarly, Grazzi et al. show that allowing negative eigenvalues enables models to solve parity and modular arithmetic tasks that are impossible for models restricted to positive real values.
  4. Fixed-Point Iterations: Movahedi et al. propose "unfolding" a diagonal model through parallelizable fixed-point iterations, effectively approximating a dense recurrent network while keeping the computational benefits of the diagonal structure.

By moving toward non-commutative state dynamics, these researchers are bridging the gap between the high-speed "passive memory" of early SSMs and the "active state tracking" required for true algorithmic reasoning.

Key Foundational Work

Parallelizing Linear Recurrent Neural Nets Over Sequence Length (2018) — contributed 1 concept elements to this direction.
Finite State Automata that Recurrent Cascade-Correlation Cannot Represent (1995) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_non_commutative_state_dynamics_6897ec61,
  title = {non-commutative state dynamics},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-commutative-state-dynamics/rdr_6897ec61b9384bdd823d70207fe730c3},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_non_commutative_state_dynamics_6897ec61_v1,
  title = {non-commutative state dynamics},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-commutative-state-dynamics/rdr_6897ec61b9384bdd823d70207fe730c3/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake