mlsanityData to 7 Oct 2026

A Formal Hierarchy of RNN Architectures

arXiv 2004.08500 ↗First posted 18 Apr 2020cs.CL cs.FLcited by 61

Not on the map. Why?

Abstract (arXiv)

We develop a formal hierarchy of the expressive capacity of RNN architectures. The hierarchy is based on two formal properties: space complexity, which measures the RNN's memory, and rational recurrence, defined as whether the recurrent update can be described by a weighted finite-state machine. We place several RNN variants within this hierarchy. For example, we prove the LSTM is not rational, which formally separates it from the related QRNN (Bradbury et al., 2016). We also show how these models' expressive capacity is expanded by stacking multiple layers or composing them with different pooling functions. Our results build on the theory of "saturated" RNNs (Merrill, 2019). While formally extending these findings to unsaturated RNNs is left to future work, we hypothesize that the practical learnable capacity of unsaturated RNNs obeys a similar hierarchy. Experimental findings from training unsaturated networks on formal languages support this conjecture.

Key facts. Cited by 61 papers in the map (data through 7 Oct 2026). First posted on arXiv 18 Apr 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 6; 2023: 13; 2024: 17; 2025: 9; 2026: 10.

61 papers.

Sort:

By area:

  1. 2022Neural Networks and the Chomsky Hierarchycited by 214
  2. 2024Repeat After Me: Transformers are Better than State Space Models at Copyingcited by 208
  3. 2021Thinking Like Transformerscited by 182
  4. 2023What Formal Languages Can Transformers Express? A Surveycited by 120
  5. 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
  6. 2024Unlocking State-Tracking in Linear RNNs Through Negative Eigenvaluescited by 97
  7. 2022Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functionscited by 68
  8. 2024Findings of the Second BabyLM Challenge: Sample-Efficient Pretraining on Developmentally Plausible Corporacited by 48
  9. 2023Modeling rapid language learning by distilling Bayesian priors into artificial neural networkscited by 40
  10. 2025Between Circuits and Chomsky: Pre-pretraining on Formal Languages Imparts Linguistic Biasescited by 36
  11. 2024Mission: Impossible Language Modelscited by 31
  12. 2024Transformers Can Represent n-gram Language Modelscited by 31
38 more
  1. 2024Mechanistic?cited by 25
  2. 2024Training Neural Networks as Recognizers of Formal Languagescited by 23
  3. 2025Implicit Language Models are RNNs: Balancing Parallelization and Expressivitycited by 21
  4. 2023Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensionscited by 20
  5. 2024What Languages are Easy to Language-Model? A Perspective from Learning Probabilistic Regular Languagescited by 20
  6. 2023Exploring the Promise and Limits of Real-Time Recurrent Learningcited by 19
  7. 2022Extracting Finite Automata from RNNs Using State Mergingcited by 17
  8. 2024Bridging the Empirical-Theoretical Gap in Neural Network Formal Language Learning Using Minimum Description Lengthcited by 14
  9. 2021Formal Language Theory Meets Modern NLPcited by 9
  10. 2025Sequential-Parallel Duality in Prefix Scannable Modelscited by 8
  11. 2022Exploring the Long-Term Generalization of Counting Behavior in RNNscited by 7
  12. 2026Why Are Linear RNNs More Parallelizable?cited by 7
  13. 2023Recurrent Neural Language Models as Probabilistic Finite-state Automatacited by 6
  14. 2025Compositional Reasoning with Transformers, RNNs, and Chain of Thoughtcited by 6
  15. 2025Fast weight programming and linear transformers: from machine learning to neurobiologycited by 6
  16. 2026Learning State-Tracking from Code Using Linear RNNscited by 5
  17. 2022Implicit N-grams Induced by Recurrencecited by 4
  18. 2024Simulating Weighted Automata over Sequences and Trees with Transformerscited by 4
  19. 2024Lower Bounds on the Expressivity of Recurrent Neural Language Modelscited by 4
  20. 2025Transformers are Inherently Succinctcited by 4
  21. 2021Extracting Weighted Automata for Approximate Minimization in Language Modellingcited by 3
  22. 2023Theoretical Conditions and Empirical Failure of Bracket Counting on Long Sequences with Linear Recurrent Networkscited by 3
  23. 2024Stability Analysis of Various Symbolic Rule Extraction Methods from Recurrent Neural Networkcited by 3
  24. 2024A Tensor Decomposition Perspective on Second-order RNNscited by 3
  25. 2026Synthetic Pre-Pre-Training Improves Language Model Robustness to Noisy Pre-Training Datacited by 3
  26. 2022Memory-Augmented Graph Neural Networks: A Brain-Inspired Reviewcited by 2
  27. 2025A Constructive Framework for Nondeterministic Automata via Time-Shared, Depth-Unrolled Feedforward Networkscited by 2
  28. 2021Generalized Optimal Linear Orderscited by 1
  29. 2023DDNAS: Discretized Differentiable Neural Architecture Search for Text Classificationcited by 1
  30. 2023Refined Kolmogorov Complexity of Analog, Evolving and Stochastic Recurrent Neural Networkscited by 1
  31. 2023On the Representational Capacity of Recurrent Neural Language Modelscited by 1
  32. 2023On The Expressivity of Recurrent Neural Cascadescited by 1
  33. 2024On Efficiently Representing Regular Languages as RNNscited by 1
  34. 2025On the Existence of Universal Simulators of Attentioncited by 1
  35. 2025RNN Generalization to Omega-Regular Languagescited by 1
  36. 2026Universal computation is intrinsic to language model decodingcited by 1
  37. 2026Why Depth Matters in Parallelizable Sequence Models: A Lie Algebraic Viewcited by 1
  38. 2026On the Expressive Power and Limitations of Multi-Layer SSMscited by 1

50 most cited of 61 All 61 (JSON)