# On the Expressivity of Selective State-Space Layers: A Multivariate Polynomial Approach

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Placed in Core SSM architectures for language, one of 10 directions in State-space sequence models (S4, Mamba).
- Builds on 42 of its 56 references that are in the map.
- First posted on arXiv 4 Feb 2025.

## Placed in

- State-space sequence models (S4, Mamba) / [Core SSM architectures for language](https://mlsanity.com/ssm/core-ssm-architectures-for-language/)

## Builds on (most cited first, 30 of 42)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [Training data-efficient image transformers & distillation through attention](https://mlsanity.com/paper/2012.12877/) (2020)
- [Efficiently Modeling Long Sequences with Structured State Spaces](https://mlsanity.com/paper/2111.00396/) (2021)
- [VMamba: Visual State Space Model](https://mlsanity.com/paper/2401.10166/) (2024)
- [Simplified State Space Layers for Sequence Modeling](https://mlsanity.com/paper/2208.04933/) (2022)
- [Combining Recurrent, Convolutional, and Continuous-time Models with Linear State-Space Layers](https://mlsanity.com/paper/2110.13985/) (2021)
- [Gated Delta Networks: Improving Mamba2 with Delta Rule](https://mlsanity.com/paper/2412.06464/) (2024)
- [Jamba: A Hybrid Transformer-Mamba Language Model](https://mlsanity.com/paper/2403.19887/) (2024)
- [Diagonal State Spaces are as Effective as Structured State Spaces](https://mlsanity.com/paper/2203.14343/) (2022)
- [VideoMamba: State Space Model for Efficient Video Understanding](https://mlsanity.com/paper/2403.06977/) (2024)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Griffin: Mixing Gated Linear Recurrences with Local Attention for Efficient Language Models](https://mlsanity.com/paper/2402.19427/) (2024)
- [Repeat After Me: Transformers are Better than State Space Models at Copying](https://mlsanity.com/paper/2402.01032/) (2024)
- [Transformer Quality in Linear Time](https://mlsanity.com/paper/2202.10447/) (2022)
- [The Illusion of State in State-Space Models](https://mlsanity.com/paper/2404.08819/) (2024)
- [An Empirical Study of Mamba-based Language Models](https://mlsanity.com/paper/2406.07887/) (2024)
- [Mega: Moving Average Equipped Gated Attention](https://mlsanity.com/paper/2209.10655/) (2022)
- [Swin-UMamba: Mamba-based UNet with ImageNet-based pretraining](https://mlsanity.com/paper/2402.03302/) (2024)
- [MiniMax-01: Scaling Foundation Models with Lightning Attention](https://mlsanity.com/paper/2501.08313/) (2025)
- [Graph-Mamba: Towards Long-Range Graph Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2402.00789/) (2024)
- [SOFT: Softmax-free Transformer with Linear Complexity](https://mlsanity.com/paper/2110.11945/) (2021)
- [The Hidden Attention of Mamba Models](https://mlsanity.com/paper/2403.01590/) (2024)
- [Mamba-ND: Selective State Space Modeling for Multi-Dimensional Data](https://mlsanity.com/paper/2402.05892/) (2024)
- [Gradient Descent Learns Linear Dynamical Systems](https://mlsanity.com/paper/1609.05191/) (2016)
- [Theoretical Foundations of Deep Selective State-Space Models](https://mlsanity.com/paper/2402.19047/) (2024)
- [Theory, Analysis, and Best Practices for Sigmoid Self-Attention](https://mlsanity.com/paper/2409.04431/) (2024)
- [The Expressive Capacity of State Space Models: A Formal Language Perspective](https://mlsanity.com/paper/2405.17394/) (2024)
- [Falcon Mamba: The First Competitive Attention-free 7B Language Model](https://mlsanity.com/paper/2410.05355/) (2024)
- [Replacing softmax with ReLU in Vision Transformers](https://mlsanity.com/paper/2309.08586/) (2023)

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

- [A Theoretical Analysis of Mamba's Training Dynamics: Filtering Relevant Features for Generalization in State Space Models](https://mlsanity.com/paper/2602.12499/) (2026)
- [On the Recall Scaling Laws in Mamba: A Theoretical and Mechanistic Study via Hashing](https://mlsanity.com/paper/2609.07681/) (2026)
- [How Wrong Can a Good Predictor Be? Diverging Updates with Vanishing Predictive KL](https://mlsanity.com/paper/2609.11132/) (2026)
- [A Comparative Analysis of Attention versus State-Space Models for In-Context Learning](https://mlsanity.com/paper/2609.32341/) (2026)

## Abstract (arXiv)

Recent advances in efficient sequence modeling have introduced selective state-space layers, a key component of the Mamba architecture, which have demonstrated remarkable success in a wide range of NLP and vision tasks. While Mamba's empirical performance has matched or surpassed SoTA transformers on such diverse benchmarks, the theoretical foundations underlying its powerful representational capabilities remain less explored. In this work, we investigate the expressivity of selective state-space layers using multivariate polynomials, and prove that they surpass linear transformers in expressiveness. Consequently, our findings reveal that Mamba offers superior representational power over linear attention-based models for long sequences, while not sacrificing their generalization. Our theoretical insights are validated by a comprehensive set of empirical experiments on various datasets.