The Expressive Limits of Diagonal SSMs for State-Tracking

arXiv:2603.01959v2 Announce Type: replace Abstract: 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.

Related

• Latent Matters: Learning Deep State-Space Models
• Learning to Defer in Non-Stationary Time Series via Switching State-Space Models
• Diffusion-Driven State Space Models
• Exemplar-Free Continual Learning for State Space Models
• Assumed Density Filtering and Smoothing with Neural Network Surrogate Models

Source: arXiv cs.LG | 2026-08-17