# Lower Bounds on the Expressivity of Recurrent Neural Language Models

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

## Key facts

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

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

- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [On the Properties of Neural Machine Translation: Encoder-Decoder Approaches](https://mlsanity.com/paper/1409.1259/) (2014)
- [Exploiting Cloze Questions for Few Shot Text Classification and Natural Language Inference](https://mlsanity.com/paper/2001.07676/) (2020)
- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [From Softmax to Sparsemax: A Sparse Model of Attention and Multi-Label Classification](https://mlsanity.com/paper/1602.02068/) (2016)
- [On the Expressive Power of Deep Neural Networks](https://mlsanity.com/paper/1606.05336/) (2016)
- [Breaking the Softmax Bottleneck: A High-Rank RNN Language Model](https://mlsanity.com/paper/1711.03953/) (2017)
- [On the Properties of the Softmax Function with Application in Game Theory and Reinforcement Learning](https://mlsanity.com/paper/1704.00805/) (2017)
- [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021)
- [On the Practical Computational Power of Finite Precision RNNs for Language Recognition](https://mlsanity.com/paper/1805.04908/) (2018)
- [Text Classification via Large Language Models](https://mlsanity.com/paper/2305.08377/) (2023)
- [Universal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activations](https://mlsanity.com/paper/1708.02691/) (2017)
- [How to Construct Deep Recurrent Neural Networks](https://mlsanity.com/paper/1312.6026/) (2013)
- [A Formal Hierarchy of RNN Architectures](https://mlsanity.com/paper/2004.08500/) (2020)
- [RNNs can generate bounded hierarchical languages with optimal memory](https://mlsanity.com/paper/2010.07515/) (2020)
- [Sequential Neural Networks as Automata](https://mlsanity.com/paper/1906.01615/) (2019)
- [On the Computational Power of RNNs](https://mlsanity.com/paper/1906.06349/) (2019)
- [A Measure-Theoretic Characterization of Tight Language Models](https://mlsanity.com/paper/2212.10502/) (2022)
- [Rational Recurrences](https://mlsanity.com/paper/1808.09357/) (2018)
- [A Survey of Neural Networks and Formal Languages](https://mlsanity.com/paper/2006.01338/) (2020)
- [Extracting Finite Automata from RNNs Using State Merging](https://mlsanity.com/paper/2201.12451/) (2022)
- [Context-Free Transductions with Neural Stacks](https://mlsanity.com/paper/1809.02836/) (2018)
- [FETA: A Benchmark for Few-Sample Task Transfer in Open-Domain Dialogue](https://mlsanity.com/paper/2205.06262/) (2022)

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

- [On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning](https://mlsanity.com/paper/2406.14197/) (2024)
- [Autoregressive + Chain of Thought = Recurrent: Recurrence's Role in Language Models' Computability and a Revisit of Recurrent Transformer](https://mlsanity.com/paper/2409.09239/) (2024)
- [An Algebraic View of the Expressivity of Recurrent Language Models](https://mlsanity.com/paper/2606.01765/) (2026)
- [Provably Shorter Scratchpads in Hybrid DeltaNet-Attention Decoders](https://mlsanity.com/paper/2605.16640/) (2026)

## Abstract (arXiv)

The recent successes and spread of large neural language models (LMs) call for a thorough understanding of their computational ability. Describing their computational abilities through LMs' representational capacity is a lively area of research. However, investigation into the representational capacity of neural LMs has predominantly focused on their ability to recognize formal languages. For example, recurrent neural networks (RNNs) with Heaviside activations are tightly linked to regular languages, i.e., languages defined by finite-state automata (FSAs). Such results, however, fall short of describing the capabilities of RNN language models (LMs), which are definitionally distributions over strings. We take a fresh look at the representational capacity of RNN LMs by connecting them to probabilistic FSAs and demonstrate that RNN LMs with linearly bounded precision can express arbitrary regular LMs.