mlsanityData to 7 Oct 2026

Recurrent Neural Language Models as Probabilistic Finite-state Automata

arXiv 2310.05161 ↗First posted 8 Oct 2023cs.CL cs.CC cs.LGcited by 6

Not on the map. Why?

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.

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

Builds on

31 of 58 references.

References · 31

  1. 2017Attention Is All You Needcited by 59,932
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  3. 2020Language Models are Few-Shot Learnerscited by 32,199
  4. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,302
  5. 2021Evaluating Large Language Models Trained on Codecited by 8,053
  6. 2022PaLM: Scaling Language Modeling with Pathwayscited by 5,304
  7. 2022Large Language Models are Zero-Shot Reasonerscited by 4,323
  8. 2022Training Compute-Optimal Large Language Modelscited by 2,927
  9. 2014On the Properties of Neural Machine Translation: Encoder-Decoder Approachescited by 1,303
  10. 2021Probing Classifiers: Promises, Shortcomings, and Advancescited by 831
  11. 2020A Primer in BERTology: What we know about how BERT workscited by 807
  12. 2019Linguistic Knowledge and Transferability of Contextual Representationscited by 382
19 more
  1. 2023Language Models can Solve Computer Taskscited by 371
  2. 2016Assessing the Ability of LSTMs to Learn Syntax-Sensitive Dependenciescited by 350
  3. 2016From Softmax to Sparsemax: A Sparse Model of Attention and Multi-Label Classificationcited by 337
  4. 2022Neural Networks and the Chomsky Hierarchycited by 214
  5. 2022Distilling Reasoning Capabilities into Smaller Language Modelscited by 155
  6. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 137
  7. 2018On the Practical Computational Power of Finite Precision RNNs for Language Recognitioncited by 117
  8. 2020A Formal Hierarchy of RNN Architecturescited by 61
  9. 2020RNNs can generate bounded hierarchical languages with optimal memorycited by 59
  10. 2019Sequential Neural Networks as Automatacited by 54
  11. 2020Limitations of Autoregressive Models and Their Alternativescited by 54
  12. 2019On the Computational Power of RNNscited by 35
  13. 2022A Measure-Theoretic Characterization of Tight Language Modelscited by 32
  14. 2017Recurrent Neural Networks as Weighted Language Recognizerscited by 30
  15. 2019Learning Deterministic Weighted Automata with Queries and Counterexamplescited by 22
  16. 2020On the Practical Ability of Recurrent Neural Networks to Recognize Hierarchical Languagescited by 22
  17. 2018Rational Recurrencescited by 18
  18. 2022Extracting Finite Automata from RNNs Using State Mergingcited by 17
  19. 2018Context-Free Transductions with Neural Stackscited by 14

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 3; 2026: 3.

6 papers.

  1. 2025Latent Thinking Optimization: Your Latent Reasoning Language Model Secretly Encodes Reward Signals in Its Latent Thoughtscited by 18
  2. 2026Learning State-Tracking from Code Using Linear RNNscited by 5
  3. 2025Exact Learning of Arithmetic with Differentiable Agentscited by 1
  4. 2026Codified Finite-state Machines for Role-playingcited by 1
  5. 2026Space-Efficient Language Generation in the Limitcited by 1
  6. 2025Efficiently Vectorized MCMC on Modern Acceleratorscited by 0