# The Expressive Limits of Diagonal SSMs for State-Tracking

arXiv: https://arxiv.org/abs/2603.01959 · HTML: https://mlsanity.com/paper/2603.01959/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 23 references that are in the map.
- First posted on arXiv 2 Mar 2026.

## Builds on (most cited first, 18 of 18)

- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [Efficiently Modeling Long Sequences with Structured State Spaces](https://mlsanity.com/paper/2111.00396/) (2021)
- [Simplified State Space Layers for Sequence Modeling](https://mlsanity.com/paper/2208.04933/) (2022)
- [Long Range Arena: A Benchmark for Efficient Transformers](https://mlsanity.com/paper/2011.04006/) (2020)
- [HiPPO: Recurrent Memory with Optimal Polynomial Projections](https://mlsanity.com/paper/2008.07669/) (2020)
- [Hungry Hungry Hippos: Towards Language Modeling with State Space Models](https://mlsanity.com/paper/2212.14052/) (2022)
- [On the Parameterization and Initialization of Diagonal State Space Models](https://mlsanity.com/paper/2206.11893/) (2022)
- [Diagonal State Spaces are as Effective as Structured State Spaces](https://mlsanity.com/paper/2203.14343/) (2022)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [The Illusion of State in State-Space Models](https://mlsanity.com/paper/2404.08819/) (2024)
- [Unlocking State-Tracking in Linear RNNs Through Negative Eigenvalues](https://mlsanity.com/paper/2411.12537/) (2024)
- [DeltaProduct: Improving State-Tracking in Linear RNNs via Householder Products](https://mlsanity.com/paper/2502.10297/) (2025)
- [Why are Sensitive Functions Hard for Transformers?](https://mlsanity.com/paper/2402.09963/) (2024)
- [Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions](https://mlsanity.com/paper/2211.12316/) (2022)
- [The Expressive Capacity of State Space Models: A Formal Language Perspective](https://mlsanity.com/paper/2405.17394/) (2024)
- [Bridging Expressivity and Scalability with Adaptive Unitary SSMs](https://mlsanity.com/paper/2507.05238/) (2025)
- [Parity Requires Unified Input Dependence and Negative Eigenvalues in SSMs](https://mlsanity.com/paper/2508.07395/) (2025)

## Built on by (most cited first, 9 of 9)

- [Rethinking State Tracking in Recurrent Models Through Error Control Dynamics](https://mlsanity.com/paper/2605.07755/) (2026)
- [A Held-Out Transition-Pair Falsifier for Long-Horizon Non-Abelian State Tracking](https://mlsanity.com/paper/2606.07254/) (2026)
- [Indexing: the Beginning and the End](https://mlsanity.com/paper/2607.22361/) (2026)
- [Why Depth Matters in Parallelizable Sequence Models: A Lie Algebraic View](https://mlsanity.com/paper/2603.05573/) (2026)
- [SHiPPO: Recurrent Memory with Transported Polynomial Projections](https://mlsanity.com/paper/2607.03055/) (2026)
- [The Rank the Task Demands: A Causal Rank Law for Matrix Memories Trained on Group Composition](https://mlsanity.com/paper/2609.12259/) (2026)
- [How Wrong Can a Good Predictor Be? Diverging Updates with Vanishing Predictive KL](https://mlsanity.com/paper/2609.11132/) (2026)
- [The Automaton Underneath: The Additive Input Pathway Is a Parasitic Attractor for State Tracking in Householder Linear RNN](https://mlsanity.com/paper/2609.18966/) (2026)
- [Length-Independent State Tracking Under a Parallel Scan](https://mlsanity.com/paper/2609.32447/) (2026)

## Abstract (arXiv)

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.