# State Space Models are Provably Comparable to Transformers in Dynamic Token Selection

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 34 references that are in the map.
- First posted on arXiv 29 May 2024.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [Robust Speech Recognition via Large-Scale Weak Supervision](https://mlsanity.com/paper/2212.04356/) (2022)
- [Efficiently Modeling Long Sequences with Structured State Spaces](https://mlsanity.com/paper/2111.00396/) (2021)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Hungry Hungry Hippos: Towards Language Modeling with State Space Models](https://mlsanity.com/paper/2212.14052/) (2022)
- [Nonparametric regression using deep neural networks with ReLU activation function](https://mlsanity.com/paper/1708.06633/) (2017)
- [Hyena Hierarchy: Towards Larger Convolutional Language Models](https://mlsanity.com/paper/2302.10866/) (2023)
- [Repeat After Me: Transformers are Better than State Space Models at Copying](https://mlsanity.com/paper/2402.01032/) (2024)
- [HyenaDNA: Long-Range Genomic Sequence Modeling at Single Nucleotide Resolution](https://mlsanity.com/paper/2306.15794/) (2023)
- [The Illusion of State in State-Space Models](https://mlsanity.com/paper/2404.08819/) (2024)
- [Optimal approximation of piecewise smooth functions using deep ReLU neural networks](https://mlsanity.com/paper/1709.05289/) (2017)
- [It's Raw! Audio Generation with State-Space Models](https://mlsanity.com/paper/2202.09729/) (2022)
- [Diffusion Models are Minimax Optimal Distribution Estimators](https://mlsanity.com/paper/2303.01861/) (2023)
- [Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality](https://mlsanity.com/paper/1810.08033/) (2018)
- [Theoretical Foundations of Deep Selective State-Space Models](https://mlsanity.com/paper/2402.19047/) (2024)
- [Deep Neural Networks Learn Non-Smooth Functions Effectively](https://mlsanity.com/paper/1802.04474/) (2018)
- [Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space](https://mlsanity.com/paper/1910.12799/) (2019)
- [State-space Models with Layer-wise Nonlinearity are Universal Approximators with Exponential Decaying Memory](https://mlsanity.com/paper/2309.13414/) (2023)
- [Approximation and Estimation Ability of Transformers for Sequence-to-Sequence Functions with Infinite Dimensional Input](https://mlsanity.com/paper/2305.18699/) (2023)
- [Diagonal State Space Augmented Transformers for Speech Recognition](https://mlsanity.com/paper/2302.14120/) (2023)
- [Laughing Hyena Distillery: Extracting Compact Recurrences From Convolutions](https://mlsanity.com/paper/2310.18780/) (2023)
- [State Space Models as Foundation Models: A Control Theoretic Overview](https://mlsanity.com/paper/2403.16899/) (2024)
- [The universal approximation power of finite-width deep ReLU networks](https://mlsanity.com/paper/1806.01528/) (2018)

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

- [CodeSSM: Towards State Space Models for Code Understanding](https://mlsanity.com/paper/2505.01475/) (2025)
- [Context-Selective State Space Models: Feedback is All You Need](https://mlsanity.com/paper/2510.14027/) (2025)
- [Analysis of Long Range Dependency Understanding in State Space Models](https://mlsanity.com/paper/2601.13048/) (2026)
- [Towards Understanding What State Space Models Learn About Code](https://mlsanity.com/paper/2602.06774/) (2026)
- [A Deep State-Space Model Compression Method using Upper Bound on Output Error](https://mlsanity.com/paper/2510.14542/) (2025)
- [Deep learning from a control vantage point](https://mlsanity.com/paper/2610.14385/) (2026)

## Abstract (arXiv)

Deep neural networks based on state space models (SSMs) are attracting significant attention in sequence modeling since their computational cost is much smaller than that of Transformers. While the capabilities of SSMs have been demonstrated through experiments in various tasks, theoretical understanding of SSMs is still limited. In particular, most theoretical studies discuss the capabilities of SSM layers without nonlinear layers, and there is a lack of discussion on their combination with nonlinear layers. In this paper, we explore the capabilities of SSMs combined with fully connected neural networks, and show that they are comparable to Transformers in extracting the essential tokens depending on the input. As concrete examples, we consider two synthetic tasks, which are challenging for a single SSM layer, and demonstrate that SSMs combined with nonlinear layers can efficiently solve these tasks. Furthermore, we study the nonparametric regression task, and prove that the ability of SSMs is equivalent to that of Transformers in estimating functions belonging to a certain class.