Beyond Diagonal State Space Models: Exact Non-Abelian Group Tracking, Solvability Barriers, and Geometric Physical Manifolds

Zeyu Jia

cs.LGSep 29, 2026

Beyond Diagonal State Space Models: Exact Non-Abelian Group Tracking, Solvability Barriers, and Geometric Physical Manifolds

Authors: Zeyu Jia

Organizations: School of Biomedical Engineering and Technology, Tianjin Medical University, Medical School, Tianjin University · School of Biomedical Engineering and Technology, Tianjin Medical University · Medical School, Tianjin University

Abstract

Selective state space models (SSMs), such as Mamba, S4D, and LRU, are bounded by transition matrix commutativity (A_t A_t' = A_t' A_t) and solvable affine transformation groups (Aff_D of derived length <= 2). Consequently, stacked multi-layer diagonal networks face severe optimization degradation on non-solvable simple groups such as A_5 due to the exponential circuit emulation depth required to simulate non-abelian commutators. We propose Non-Commutative State Space Models (NC-SSM), their real-orthogonal counterpart SO(3)-SSM, and arbitrary-dimension Cayley-SSM, lifting state transitions to compact Lie groups SU(2), SO(3), and SO(N). Via closed-form Euler-Rodrigues maps and rational Cayley transforms, NC-SSM achieves exact norm-preserving isometry (||U_t|| = 1). We introduce pure Hopf-fibration Bloch projective readouts (S^3/{+-1} =~ S^2 =~ SO(3)) to eliminate sign ambiguity, true quaternion parallel prefix scans (9.06x speedup at T=2048), and Identity-Gated Lie SSMs to eliminate sparse syntax phase drift. Extensive benchmarks across 14 experimental regimes show: (1) NC-SSM achieves 100% tracking on S_3, D_4, Q_8 and simple group A_5, where a 3-layer deep diagonal baseline collapses to 6.60% (p = 8.81e-4); (2) Cayley-SO(5)-SSM breaks Klein's 1884 ceiling on symmetric group S_5 (50.92% vs diagonal 5.25%, p = 0.0015, delivering 7.8x variance reduction over SO(3)); (3) SO(3)-SSM preserves Riemannian manifolds across 300 steps (< 3.12e-6 drift, > 580,000x advantage), achieving 0.04 deg dead-reckoning error and active tangent denoising; (4) NC-SSM achieves 74.36% on Dyck-2 and 30.26% on deep AST scope tracking (p = 0.0081); and (5) ablation confirms strict isometry is mathematically necessary for lossless long-range associative memory.

Figures & tables

Task / Benchmark	Metric	Baseline-SSM	Ablated / Alt	NC-SSM / SO(3) / Cayley / SE(3)	Statistical Test
$D_{4}$ Tracking ( $T=32$ )	Acc (%)	$50.33\pm 0.47$	$47.75\pm 0.82$	$\mathbf{100.00\pm 0.00}$	$p=1.16\times 10^{-3},d=1.74$
$Q_{8}$ Tracking ( $T=32$ )	Acc (%)	$50.92\pm 0.38$	$52.00\pm 0.65$	$\mathbf{100.00\pm 0.00}$	$p=1.16\times 10^{-3},d=1.74$
$S_{3}$ Pure Bloch ( $T=32$ )	Acc (%)	$33.33\pm 0.00$	$33.33\pm 0.00$	$\mathbf{100.00\pm 0.00}$	Exact Quotient Invariance
$A_{5}$ Simple Group ( $L=32$ )	Acc (%)	$2.00\pm 0.60$	$2.07\pm 0.31$	$\mathbf{100.00\pm 0.00}$	$p=1.25\times 10^{-5},d=163.3$
$A_{5}$ Full-Affine ( $L=32$ )	Acc (%)	$9.00\pm 5.07$	$48.24\pm 2.70$ (prefix)	$\mathbf{100.00\pm 0.00}$	Solvability barrier collapse
$A_{5}$ Deep-3Layer ( $L=32$ )	Acc (%)	$6.60\pm 4.80$	$34.00\pm 10.64$ (final)	$\mathbf{100.00\pm 0.00}$	$p=8.81\times 10^{-4},d=19.4$

Table 1: Comprehensive performance summary across discrete group tracking, non-solvable simple groups, continuous physics, hierarchical syntax, associative recall, real-world noisy IMU odometry, algebraic mixture-of-experts, and shared-vocabulary program environment tracking. Results report Mean

\pm

Std across independent random seeds. Under strict zero-leakage protocols with generic closing tokens, NC-SSM achieves

74.36\%

on Dyck-2 (

+13.33\%

non-commutative gain over commutative linear models,

p<0.001

). Under realistic MEMS IMU sensor noise and Brownian bias drift (EXP-24,

N=5

), SO(3)-SSM reduces geodesic odometry error to

\mathbf{3.42^{\circ}\pm 0.13^{\circ}}

, outperforming nearest SVD-projected baselines (

10.81^{\circ}\pm 1.59^{\circ}

) by

+7.40^{\circ}

(

t=9.23,p<10^{-3},d=4.13

) and numerical dead-reckoning (

3.80^{\circ}\pm 0.15^{\circ}

p=0.00116

), demonstrating active Lie algebra bias suppression. Under aggressive MAV aerobatic flight with angular rates up to

40\,\mathrm{rad/s}

(EXP-25,

N=5

), linear models undergo catastrophic collapse (

104.44^{\circ}\sim 110.79^{\circ}

), while SO(3)-SSM maintains

\mathbf{1.64^{\circ}\pm 0.09^{\circ}}

attitude tracking, outperforming baseline by

+102.81^{\circ}

(

p=2.70\times 10^{-9}

) and dead-reckoning (

2.08^{\circ}\pm 0.09^{\circ}

p=4.51\times 10^{-7},d=26.99

) via tangent-space Lie algebra denoising. On authentic Python code parsed directly from the standard library under a canonical shared vocabulary (EXP-22), natural class imbalance ( if/elif/else

\approx 48\%

) enables baseline models to achieve

47.68\%\sim 50.42\%

by absorbing marginal priors (

p=0.92

L=64

p=0.19

L=128

), highlighting the methodological necessity of balanced synthetic grammars (EXP-13, uniform

12.5\%

chance,

+8.39\%,p=0.0043,d=8.81

) to isolate stack depth tracking.

\mathrm{SE}(3)

Affine Lie SSM (EXP-21) unifies non-solvable group tracking (

\mathbf{100.00\%}

A_{5}

) with counter accumulation (

\mathbf{91.41\%}

on Dyck-2,

+8.38\%

over pure

SO(3)

p=0.00644

). Capacity-matched MQAR ablation (EXP-23) isolates strict unitarity (

|\lambda|=1.0

+10.40\%

gain over decay,

p=0.0482

) from non-commutativity. Continuous rigid body kinematics under relative dead reckoning (

R_{0}=I_{3}

) achieves

\mathbf{0.04^{\circ}\pm 0.00^{\circ}}

geodesic tracking error, outperforming nearest SVD-projected baselines (

1.61^{\circ}\pm 0.26^{\circ}

) by

\mathbf{40.25\times}

(

p=0.0137,d=4.88

) and unconstrained baselines (

5.86^{\circ}

) by

\mathbf{146.5\times}

, while maintaining

10^{-7}

Riemannian manifold orthogonality by Euler-Rodrigues construction. Algebraic-MoE-SSM (EXP-28,

N=5

) liberates associative memory to achieve

\mathbf{23.65\%\pm 0.92\%}

on MQAR (

+4.92\%

over hybrid,

p=0.0173,d=1.75

;

+16.05\%

over vector baseline,

p<10^{-4}

). Orthogonal-MoE-SSM (EXP-29,

N=5

) with straight-through estimator (STE) binary routing eliminates memory logit noise, achieving

\mathbf{88.67\%\pm 24.60\%}

A_{5}

(

+66.00\%

over hybrid,

p=0.0169,d=1.76

, 3 seeds at

100.00\%

) while maintaining high associative recall on MQAR (

\mathbf{15.90\%\pm 1.54\%}

2.09\times

over vector baseline,

p=1.39\times 10^{-4}

), definitively resolving the cross-domain Pareto dilemma. On the shared-vocabulary program environment benchmark (EXP-31,

N=5

), Hybrid-Dual-Track-SSM achieves

\mathbf{98.28\%\pm 1.50\%}

overall accuracy (

\mathbf{97.17\%\pm 2.84\%}

syntax,

\mathbf{99.38\%\pm 0.57\%}

query), delivering a

+54.83\%

advantage over diagonal baselines (

43.45\%\pm 13.51\%,t=9.09,p=8.11\times 10^{-4},d=4.07

) and

+28.01\%

over Algebraic-MoE (

70.26\%\pm 7.19\%,t=8.41,p=0.00109,d=3.76

Group Type	Group	Commutative-Diag	Full-Affine-Diag	Deep-Affine-Diag	NC-SSM ( $SU(2)$ )	Cayley-SO5-SSM
Solvable	$S_{3}$ (order 6)	$45.92\pm 1.27$	$\mathbf{99.61\pm 0.32}$	$68.46\pm 27.33$	$\mathbf{100.00\pm 0.00}$	$\mathbf{100.00\pm 0.00}$
	$D_{4}$ (order 8)	$54.75\pm 0.14$	$\mathbf{95.90\pm 3.31}$	$89.39\pm 15.75$	$\mathbf{100.00\pm 0.00}$	$\mathbf{100.00\pm 0.00}$
	$Q_{8}$ (order 8)	$54.60\pm 0.16$	$\mathbf{96.78\pm 0.47}$	$60.75\pm 38.57$	$84.79\pm 25.68$	$\mathbf{100.00\pm 0.00}$
Non-Solvable	$A_{5}$ (order 60)	$18.20\pm 0.85$	$48.24\pm 2.70$	$74.05\pm 7.32$	$\mathbf{100.00\pm 0.00}$	$\mathbf{100.00\pm 0.00}$
Non-Solvable	$S_{5}$ (order 120)	$25.61\pm 0.55$	$72.12\pm 0.57$	$70.53\pm 5.13$	$69.87\pm 9.37$	$\mathbf{79.64\pm 7.87}$

Table 2: EXP-15: Solvable vs. Non-Solvable Algebraic Barrier Benchmark. Prefix tracking accuracy (%) and final-step accuracy (%) at

L=32

(Mean

\pm

Std across 3 seeds). Full-Affine SSM (

h_{t}=A_{t}h_{t-1}+B_{t}x_{t}

) successfully solves solvable non-abelian groups (

S_{3},D_{4},Q_{8}

) but collapses on non-solvable groups (

A_{5},S_{5}

), where Lie group SSMs achieve near-perfect or superior tracking.

State Space Models

State space models represent sequences through evolving latent states, enabling efficient temporal modeling, system identification, and forecasting.

See all 295 papers

Mar 2, 2026

The Expressive Limits of Diagonal SSMs for State-Tracking

State-Space Models (SSMs) have recently been shown to achieve strong empirical performance on a variety of long-range sequence modeling tasks while remaining efficient and highly-parallelizable. However, the theoretical understanding of their expressive power remains limited. In this work, we study the expressivity of input-Dependent Complex-valued Diagonal (DCD) SSMs on sequential state-tracking tasks. We show that single-layer DCD SSMs cannot express state-tracking of any non-Abelian group at finite precision. More generally, we show that

k

-layer DCD SSMs can express state-tracking of a group if and only if that group has a subnormal series of length

k

, with Abelian factors. That is, we identify the precise expressivity range of

k

-layer DCD SSMs within the solvable groups. Empirically, we find that multi-layer models often fail to learn state-tracking for non-Abelian groups, highlighting a gap between expressivity and learnability.

Mehran Shakerinava, Behnoush Khavari, Siamak Ravanbakhsh +1

School of Computer Science, McGill University · Mila – Quebec AI Institute · Chandar Research Lab +1

State Space Models State Tracking

Ask PDF

Jun 5, 2026

A Held-Out Transition-Pair Falsifier for Long-Horizon Non-Abelian State Tracking

State tracking exposes a sharp limitation of sequence models: the relevant signal is often not a summary of observed tokens, but an ordered latent state that evolves through non-commutative transformations. We introduce a held-out transition-pair falsifier for finite non-Abelian group tracking. The protocol forbids selected ordered generator pairs during training and requires the same local patterns during evaluation, blocking one direct local-transition memorization pathway. In a controlled

S_3 \times S_3

benchmark, a projected recurrent state model trained only on length-8 sequences produces error-free final-state predictions (perfect 250/250 per horizon) through evaluation horizons up to 1,048,576 tokens across five seeds. Matched native-readout baselines, including bag, GRU, and a single-configuration structured state-space model, remain near floor under the same protocol. Projection-matched GRU, structured SSM, and bag baselines equipped with analogous finite-group prototype readouts also remain near chance under the same split. Mechanism diagnostics show that hard projection coincides with low homomorphism error, low state-consistency drift, and non-trivial commutator separation, while softened projection collapses final-state accuracy. Clean-split audits verify zero verbatim reduced-word overlap and zero structural-template overlap between training and evaluation partitions. The evidence is scoped to this controlled finite-group falsifier rather than to a general architecture ranking. Within that regime, explicit projected non-commutative state composition acts as a useful inductive bias for long-horizon hidden-state tracking.

Jeonghoon Lee

Attractor Dynamics

Recurrent Neural Networks State Tracking Sequence Modeling

Ask PDF

Sep 28, 2026

Riccati State Space Models: Non-iterative Parallelization for Nonlinear Sequence Modeling

State space models (SSMs) achieve efficient sequence processing because their affine state updates are closed under composition and can therefore be evaluated with an associative parallel scan. Nonlinear recurrent models can provide richer, state-dependent dynamics, but generally lose this compositional structure: parallel evaluation then requires iterative methods that repeatedly linearize and scan the recurrence. We ask, what state-dependent nonlinear dynamics can be designed to remain exactly composable? We answer by introducing RiccatiSSM, a nonlinear SSM, in which each state dimension follows an input-conditioned Riccati differential equation. Its quadratic state dependence makes the local Jacobian explicitly state-dependent, while its exact per-step flow under piecewise-constant inputs is a Möbius transformation. Since Möbius maps are closed under composition and compose through

2\times 2

matrix multiplication, the complete nonlinear state trajectory can be evaluated exactly with a single associative parallel scan, without iterative linearization. We further derive a constrained parameterization that ensures bounded, contractive dynamics, and avoids poles in the fractional-linear state update. Across long-sequence classification, regression, and forecasting tasks, RiccatiSSM achieves competitive predictive performance while reducing runtime by

22{-}33\%

compared to the nonlinear LrcSSM under matched architectures. These results demonstrate that state-dependent nonlinear dynamics can retain exact composability and be evaluated efficiently within a single parallel scan.

Mónika Farsang, Ramin Hasani, Daniela Rus +1

TU Wien · MIT CSAIL · Liquid AI

Sequence Modeling State Space Models

Ask PDF

Abstract

State Space Models

Explore similar work

The Expressive Limits of Diagonal SSMs for State-Tracking

A Held-Out Transition-Pair Falsifier for Long-Horizon Non-Abelian State Tracking

Riccati State Space Models: Non-iterative Parallelization for Nonlinear Sequence Modeling