CS Paper Radar

Non-Commutative Lie-Algebraic State-Space Models: Finite-Division Variety Laws, Semidirect Cascades, and Gradient Saddle Escape

Zeyu Jia

cs.LG ·submitted 2026-09-29 11:14 UTC · v6
unusual

Abstract

Structured state-space sequence models (SSMs) achieve linear-time inference and logarithmic-time parallel training via associative scans, yet diagonal transitions generate solvable semigroups unable to track non-solvable group words or 3D rigid-body manifolds. We present Non-Commutative Lie-Algebraic State-Space Models (Lie-SSMs), parameterizing recurrent updates on Lie algebra tangent spaces via the matrix exponential. First, using an o-minimal cylindrical flag collar, we establish an unconditional single-layer finite-division criterion for contracting $SO(3)$ and $SU(2)$ heads, proving odd-prime Sylow abelianity, odd-$p$-core centrality, and exponent-30 commutator obstructions excluding $S_5$ in $SO(3)^m, SU(2)^m,$ and $SO(4)^m$ while identifying the sharp threshold $d^*(S_5)=d^*(A_6)=5$ in $SO(5)$. Second, Depth-2 semidirect and Schreier $2$-cocycle cascades resolve $S_5$, $2I\cong SL_2(F_5)$, and $\mathrm{Heis}(F_p)$ in $O(\log T)$ scan depth, whereas unnormalized contracting coupling collapses exponentially without Directional RMSNorm. Third, we characterize the $Θ(\varepsilon^{c-1})$ Chen--Magnus--Hall--Witt commutator saddle and $1/|[G,G]|$ coset-centroid dilution, proving generic first-order symmetry breaking at $\varepsilon=0$ and teacher-forced local Polyak--Łojasiewicz convergence under dense prefix supervision and factored readouts ($99.90\%/99.40\%$ on $S_5$ at $T=128$; $100.00\%$ on $D_{16}$). Across $SE_2(3)$ Left-Jacobian odometry, Hillis--Steele/Blelloch GPU scans ($48.24\times$ forward, $20.27\times/10.28\times$ full-layer speedup at $T=2048$), and three 3D IMU benchmarks (UCI HAR, UCI HAPT-PT, and 17-subject REALDISP), Lie-$SO(3)$ models reach $95.69\%\pm 0.14\%$ on HAR, $88.44\%\pm 0.83\%$ episode logit-vote ($83.97\%\pm 1.20\%$ C3 window in 30-subject 5-fold CV; $87.16\%\pm 0.64\%$ 9-subject split) on HAPT-PT, and $84.23\%\pm 1.00\%$ on REALDISP.

Comment
37 pages, 4 figures, 13 tables; includes 5 ancillary Python reproducibility scripts in anc/

Closest papers

Nearest neighbours by meaning across the whole index.

$\mathbb{SL}(n)$ Representation Learning: An Intrinsic Mixed-Curvature Space with Higher Curvature Capacities and Deeper Order-Aware Composition

cs.LG ·2026-09-14 ·Xingrun Li, Yusuke Mukuta, Xin Yang, Yinyu Ye, Tatsuya Harada
theory similarity 0.56
Abstract · 35 pages, 8 figures

Mixed-curvature representation learning seeks to capture rich geometric structures that cannot be adequately modeled by a single curvature regime. Existing approaches largely rely on product manifolds, which require manually specifying how different curvature spaces are combined and separate their curvature contributions across factors. We introduce the $\mathbb{SL}(n)$ space, a representation geometry defined by the simple $\det(A)=1$ constraint and a left invariant Schatten-$p$ Finsler structure. Despite this minimal construction, $\mathbb{SL}(n)$ exhibits pointwise negative, zero, and positive flag curvature around a common flagpole, while its mixed-curvature and curvature-coupling capacities are asymptotically maximal relative to the intrinsic geometric upper bound. Beyond geometry, its noncommutative group structure provides inherent order sensitivity, and its non-nilpotent Lie algebra admits nonzero nested Lie brackets at arbitrary depth, enabling deep order-aware composition. Empirically, $\mathbb{SL}(n)$ consistently outperforms a broad range of representation manifold baselines across graph benchmarks at different scales. It reduces average distortion over the strongest baselines by $44.3\%$ on KEGG and $40.5\%$ on HumanCyc, and improves Hits@20 by $42.8\%$ on OGBL-PPA. Experiments on Flickr30k-Order further support its ability to capture higher order dependencies from ordered composition. Together, these results show how a seemingly simple structural constraint can yield unexpectedly rich geometry, capacity, and composition within a unified representation space.

0.32

Symmetry in Time: A Representation Theory of Linear Recurrent Memory

cs.LG cs.NEmath.RT ·2026-11-12 ·Anif N. Shikder, Ramit Dey, Jan Minac, Lyle E. Muller
similarity 0.54
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.

0.31

Explicit matrix hitting points for noncommutative algebraic branching programs

cs.CC math.RAmath.CO ·2026-10-11 ·Zhipeng Lu
similarity 0.50
Abstract · 24 pages. There's statement about reproducibility and Lean verification in section 5

We give a deterministic polynomial-resource black-box identity test for noncommutative algebraic branching programs (ABPs), using ordinary matrix evaluations of the output polynomial. Given an alphabet of size $m\ge1$ and an ABP vertex bound $S\ge1$, we construct one fixed tuple of integer matrices of order $R=(m+2)d(d+1)/2$, where $d=(m+2)S$, with entry bit length $O(d\log(d+1))$. Every nonzero polynomial computed by an ABP with at most $S$ vertices has a nonzero evaluation at this tuple. The construction accesses neither the hidden ABP nor its intermediate gates. A rectangular variant improves the order to $O(m^{3/2}S^2)$. Matrix order, description length, and all returned entries are counted; the total resources are polynomial. The result holds in characteristic zero and in characteristic $p>\binom d2$. The main ingredient is a fixed polynomial frame spanning the joint cyclic module of every matrix tuple from every prescribed vector. A compensating block makes a tagged encoding nilpotent of index at most three, while preserving the original cyclic module. A differential exterior-vector argument then gives a single triangular recurrence with polynomially many outputs. Its shared left-linear circuit is converted into actual integer query matrices by coefficient duality. Two-sided pairing further gives deterministic nonadaptive reconstruction of an equivalent ABP from polynomially many output-only matrix queries. The same frame gives polynomial-cardinality explicit trace separators for simultaneous-conjugation orbit closures, and a fixed nilpotent substitution for bounded-dimensional recognizable series. The latter also tests rational formulas whose given syntax is defined at the scalar origin. We provide complete proofs, construction costs, and exact implementation checks.

0.16

Nearly Linear Private Learning of Littlestone Classes

cs.LG ·2026-10-16 ·Shay Moran, Chao Yan
theory similarity 0.49
Abstract

Differentially private learning aims to learn from data while protecting individual training examples. For binary classification, finite Littlestone dimension characterizes approximate private PAC learnability (Alon et al., JACM 2022). Understanding how this dimension controls private sample complexity remains a central question. For classes of Littlestone dimension $d$, the first general upper bound was doubly exponential in $d$ (Bun, Livni, and Moran, FOCS 2020). Subsequent work improved this to $\widetilde O(d^6)$ (Ghazi et al., STOC 2021) and then to $\widetilde O(d^5)$ (Lyu, STOC 2026). We prove a nearly linear upper bound of $O(d\log d)$. Our main algorithmic contribution is a structural exponential mechanism for data-dependent candidate sets equipped with a rank satisfying suitable stability conditions. For natural Littlestone classes such as subspace indicators, this rank has a simple geometric interpretation: it is the codimension. This yields a private PAC learner for subspaces of dimension at most $d$ over any field, with tight linear dependence on $d$ and no dependence on the ambient dimension, improving the quadratic dependence of Kaplan et al. (STOC 2025). Our second contribution is combinatorial: drawing on model-theoretic ideas, we construct a suitable rank for general Littlestone classes and establish the counting bounds required by the mechanism.

0.40

Tracking States or Tracking Cosets? An Algebraic Account of Learned State Tracking

cs.LG cs.AI ·2026-09-24 ·Zhiyu Zhang, Yupeng Li
theoryunusual similarity 0.49
Abstract · 69 pages including appendices; 9 pages of main text

State tracking requires composing a sequence of updates, but accuracy alone does not reveal what a model has learned. We study neural networks trained to predict the running product of group elements. We identify quotient solutions in Transformers, where models recover the quotient class while predicting nearly uniformly among its members. The reciprocal of class size predicts partial accuracy without a fitted parameter, extending parity-based accounts to non-parity quotients. Our baseline Transformers' predictions change little under prefix reordering beyond the exact-tracking frontier. We prove that, for finite groups under uniform i.i.d. full-group inputs, optimal order-blind exact accuracy converges to the reciprocal of abelianization class size as prefix length grows, consistent with the observed abelianization plateaus. Sequential updates permit more: any partition into right cosets of a subgroup, normal or not, survives sequential updates. In our census of standard Transformers, every recovered coset partition comes from a normal subgroup, whereas parameter-matched recurrent networks pass through both normal and non-normal right-coset stages during training. On $A_5$, we identify low-dimensional subspaces of the recurrent state that encode non-normal cosets. In the three-dimensional cases, coset mean vectors form approximate dodecahedra, and swapping the state components in these subspaces transfers the donor's coset state through a shared input suffix. Our results connect partial accuracy, learning stages, and internal computation through the subgroup cosets that models learn to track.

0.56

MIRA: Mitigating Pole Geometry Bias in Recurrent Language Models

cs.AI ·2026-11-06 ·Róisín Luo, Ihsan Ullah, Christian Gagné, Dong Li, Karyn Morrissey
similarity 0.47
Abstract

We show that the Transformer's recurrent successors --- such as selective state-space models (SSMs), Receptance Weighted Key Value (RWKV), and Retentive Network (RetNet) --- can be characterized as infinite-impulse-response (IIR) systems. The zero--pole geometries of these IIR systems characterize the temporal modes they can represent. However, to trade parallelism, the algebraic structures of the parameterizations of these recurrent systems often give rise to poles constrained to the real axis, thereby inducing an architectural bias in their recurrent dynamics. To unify these recurrent architectures and eliminate their pole geometry bias, inspired by the lattice--ladder realization of general IIR systems, we present \textsc{Mira} (\textbf{M}odal \textbf{I}IR \textbf{R}ecurrent \textbf{A}rchitecture), a unified family of linear-time recurrent architectures for building large language models (LLMs) with a highly parallel algebraic structure. Each \textsc{Mira} block realizes a higher-order IIR system that represents temporal modes from token streams through a lattice--ladder structure, followed by a feed-forward network (FFN). This realization enables the model to represent the temporal modes associated with both real and complex-conjugate poles. We pretrain \textsc{Mira-S}, a 12-layer small-scale LLM with 0.14B parameters composed entirely of \textsc{Mira} blocks. Throughout the pretraining, \textsc{Mira-S} achieves lower perplexity than strong recurrent baselines, exhibits stronger context-window generalization beyond the training length, and attains higher throughput with a dedicated CUDA kernel.

0.24

Learning a Group Element from Its Action: Galois Correspondences, Optimal ERM, and an Abel-Ruffini Threshold for the Natarajan Dimension

cs.LG math.GRstat.ML ·2026-10-13 ·Xiaoyu Li
theory similarity 0.47
Abstract · 55 pages, 5 figures. The abstract has been shortened to meet arXiv's submission requirements

We study learning an unknown element $g$ of a group acting with finite orbits on a countable set, from examples $(x,gx)$. After a sample on $A$, the consistent hypotheses are the restrictions of a coset of the pointwise stabilizer of $A$, and the sample forces exactly the labels of points this stabilizer fixes; for a Galois group, they form the field generated by the data. Through this correspondence, multiclass dimensions become group invariants: the DS and graph dimensions equal the height, the Littlestone dimension the longest irredundant sequence length, and the teaching dimension the minimal base size. Among deterministic learners, symmetry makes empirical risk minimization optimal: on nondegenerate classes every consistent learner, whatever its tie-breaking, attains the optimal realizable sample complexity up to constant factors, and every consistent online learner the optimal mistake bound. Agnostically, every ERM's sample complexity exceeds the known lower bound by at most the DS-to-Natarajan ratio, up to constants. For finite Galois extensions of countable fields, the Natarajan dimension equals a group invariant, the coset-cube number, which is at least the number of complemented factors of any chief series of any subgroup. Hence the dimensions coincide for every solvable Galois group, while for the groups $A_5$ and $S_5$ of the quintic they are $2<3$ and $3<4$, and $A_5$ is the smallest group with a gap. For the Galois group $S_n$ of the general equation of degree $n$, they coincide exactly when $n\le 4$, i.e., in characteristic zero, exactly when the equation is solvable by radicals; the implication is one-way, as the simple group $\mathrm{PSL}(2,8)$ has no gap. For linear, orthogonal and unitary maps of $\mathbb R^d$ or $\mathbb C^d$ both dimensions equal $d$, and a two-fibered pseudo-cube is a disjoint union of Natarajan cubes exactly when its monodromy group is abelian.

0.25

Non-Commutative State Tracking with Input-Dependent Low-Rank Updates in Mamba-3

eess.SY cs.LG ·2026-09-23 ·Hiroki Fujii, Masaki Yamakita
similarity 0.47
Abstract · 12 pages, 4 figures. Updated experimental results and discussion. Added IEEE submission notice

State tracking from sequential observations can require both retaining information and updating it by composing observed operations. We extend Mamba-3's diagonal transition with an input-dependent low-rank reflection term to support noncommutative state tracking, in which the order of operations matters. The rank-one update couples state coordinates along an input-dependent direction, enabling non-diagonal state transitions within a single Mamba-3 block. The extension preserves Mamba-3's exponential-trapezoidal discretization, rotary embeddings (RoPE), and readout. For training, we adapt chunkwise computation to parallelize the proposed recurrence within each chunk. Experiments cover group word problems with discrete inputs and a shell game with continuous observations, in which a policy is trained by behavioral cloning. Among the models selected for their strong performance under fixed timing, the proposed model maintains higher tracking success on longer swap sequences in the shell game with continuous observations and timing jitter. These experiments show that the proposed method achieves high accuracy on the evaluated non-commutative tracking tasks, improving on standard Mamba-3. The extension thus offers a Mamba-3-based approach to non-commutative state tracking.

0.30