# Recurrent Neural Language Models as Probabilistic Finite-state Automata

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 58 references that are in the map.
- First posted on arXiv 8 Oct 2023.

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

- [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)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Training Compute-Optimal Large Language Models](https://mlsanity.com/paper/2203.15556/) (2022)
- [On the Properties of Neural Machine Translation: Encoder-Decoder Approaches](https://mlsanity.com/paper/1409.1259/) (2014)
- [Probing Classifiers: Promises, Shortcomings, and Advances](https://mlsanity.com/paper/2102.12452/) (2021)
- [A Primer in BERTology: What we know about how BERT works](https://mlsanity.com/paper/2002.12327/) (2020)
- [Linguistic Knowledge and Transferability of Contextual Representations](https://mlsanity.com/paper/1903.08855/) (2019)
- [Language Models can Solve Computer Tasks](https://mlsanity.com/paper/2303.17491/) (2023)
- [Assessing the Ability of LSTMs to Learn Syntax-Sensitive Dependencies](https://mlsanity.com/paper/1611.01368/) (2016)
- [From Softmax to Sparsemax: A Sparse Model of Attention and Multi-Label Classification](https://mlsanity.com/paper/1602.02068/) (2016)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Distilling Reasoning Capabilities into Smaller Language Models](https://mlsanity.com/paper/2212.00193/) (2022)
- [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)
- [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)
- [Limitations of Autoregressive Models and Their Alternatives](https://mlsanity.com/paper/2010.11939/) (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)
- [Recurrent Neural Networks as Weighted Language Recognizers](https://mlsanity.com/paper/1711.05408/) (2017)
- [Learning Deterministic Weighted Automata with Queries and Counterexamples](https://mlsanity.com/paper/1910.13895/) (2019)
- [On the Practical Ability of Recurrent Neural Networks to Recognize Hierarchical Languages](https://mlsanity.com/paper/2011.03965/) (2020)
- [Rational Recurrences](https://mlsanity.com/paper/1808.09357/) (2018)
- [Extracting Finite Automata from RNNs Using State Merging](https://mlsanity.com/paper/2201.12451/) (2022)

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

- [Latent Thinking Optimization: Your Latent Reasoning Language Model Secretly Encodes Reward Signals in Its Latent Thoughts](https://mlsanity.com/paper/2509.26314/) (2025)
- [Learning State-Tracking from Code Using Linear RNNs](https://mlsanity.com/paper/2602.14814/) (2026)
- [Exact Learning of Arithmetic with Differentiable Agents](https://mlsanity.com/paper/2511.22751/) (2025)
- [Codified Finite-state Machines for Role-playing](https://mlsanity.com/paper/2602.05905/) (2026)
- [Space-Efficient Language Generation in the Limit](https://mlsanity.com/paper/2606.25777/) (2026)
- [Efficiently Vectorized MCMC on Modern Accelerators](https://mlsanity.com/paper/2503.17405/) (2025)

## Abstract (arXiv)

Studying language models (LMs) in terms of well-understood formalisms allows us to precisely characterize their abilities and limitations. Previous work has investigated the representational capacity of recurrent neural network (RNN) LMs in terms of their capacity to recognize unweighted formal languages. However, LMs do not describe unweighted formal languages -- rather, they define probability distributions over strings. In this work, we study what classes of such probability distributions RNN LMs can represent, which allows us to make more direct statements about their capabilities. We show that simple RNNs are equivalent to a subclass of probabilistic finite-state automata, and can thus model a strict subset of probability distributions expressible by finite-state models. Furthermore, we study the space complexity of representing finite-state LMs with RNNs. We show that, to represent an arbitrary deterministic finite-state LM with N states over an alphabet alphabet, an RNN requires Omegaleft(N |Sigma|right) neurons. These results present a first step towards characterizing the classes of distributions RNN LMs can represent and thus help us understand their capabilities and limitations.