# State space models can express n-gram languages

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 57 references that are in the map.
- First posted on arXiv 20 Jun 2023.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [XLNet: Generalized Autoregressive Pretraining for Language Understanding](https://mlsanity.com/paper/1906.08237/) (2019)
- [Efficiently Modeling Long Sequences with Structured State Spaces](https://mlsanity.com/paper/2111.00396/) (2021)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [A Closer Look at Memorization in Deep Networks](https://mlsanity.com/paper/1706.05394/) (2017)
- [RWKV: Reinventing RNNs for the Transformer Era](https://mlsanity.com/paper/2305.13048/) (2023)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Combining Recurrent, Convolutional, and Continuous-time Models with Linear State-Space Layers](https://mlsanity.com/paper/2110.13985/) (2021)
- [TinyStories: How Small Can Language Models Be and Still Speak Coherent English?](https://mlsanity.com/paper/2305.07759/) (2023)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [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)
- [Visualizing and Understanding Recurrent Networks](https://mlsanity.com/paper/1506.02078/) (2015)
- [On the Convergence Rate of Training Recurrent Neural Networks](https://mlsanity.com/paper/1810.12065/) (2018)
- [Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity](https://mlsanity.com/paper/1810.07770/) (2018)
- [Tighter Bounds on the Expressivity of Transformer Encoders](https://mlsanity.com/paper/2301.10743/) (2023)
- [How Can Self-Attention Networks Recognize Dyck-n Languages?](https://mlsanity.com/paper/2010.04303/) (2020)
- [On Generalization Bounds of a Family of Recurrent Neural Networks](https://mlsanity.com/paper/1910.12947/) (2019)
- [Memorization Capacity of Multi-Head Attention in Transformers](https://mlsanity.com/paper/2306.02010/) (2023)
- [Stabilizing Gradients for Deep Neural Networks via Efficient SVD Parameterization](https://mlsanity.com/paper/1803.09327/) (2018)
- [Non-normal Recurrent Neural Network (nnRNN): learning long time dependencies while improving expressivity with transient dynamics](https://mlsanity.com/paper/1905.12080/) (2019)
- [A Survey of Neural Networks and Formal Languages](https://mlsanity.com/paper/2006.01338/) (2020)
- [Evaluating the Ability of LSTMs to Learn Context-Free Grammars](https://mlsanity.com/paper/1811.02611/) (2018)
- [MLRegTest: A Benchmark for the Machine Learning of Regular Languages](https://mlsanity.com/paper/2304.07687/) (2023)
- [N-gram Language Modeling using Recurrent Neural Network Estimation](https://mlsanity.com/paper/1703.10724/) (2017)
- [Eigenvalue Normalized Recurrent Neural Networks for Short Term Memory](https://mlsanity.com/paper/1911.07964/) (2019)

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

- [Generalization Error Analysis for Selective State-Space Models Through the Lens of Attention](https://mlsanity.com/paper/2502.01473/) (2025)
- [An expressivity analysis of hierarchical modelling in deep transformers via bounded-depth grammars](https://mlsanity.com/paper/2606.17522/) (2026)
- [A theoretical model for task routing in mixture-of-expert transformers](https://mlsanity.com/paper/2606.14398/) (2026)

## Abstract (arXiv)

Recent advancements in recurrent neural networks (RNNs) have reinvigorated interest in their application to natural language processing tasks, particularly with the development of more efficient and parallelizable variants known as state space models (SSMs), which have shown competitive performance against transformer models while maintaining a lower memory footprint. While RNNs and SSMs (e.g., Mamba) have been empirically more successful than rule-based systems based on n-gram models, a rigorous theoretical explanation for this success has not yet been developed, as it is unclear how these models encode the combinatorial rules that govern the next-word prediction task. In this paper, we construct state space language models that can solve the next-word prediction task for languages generated from n-gram rules, thereby showing that the former are more expressive. Our proof shows how SSMs can encode n-gram rules using new theoretical results on their memorization capacity, and demonstrates how their context window can be controlled by restricting the spectrum of the state transition matrix. We conduct experiments with a small dataset generated from n-gram rules to show how our framework can be applied to SSMs and RNNs obtained through gradient-based optimization.