mlsanityData to 7 Oct 2026

RNNs can generate bounded hierarchical languages with optimal memory

arXiv 2010.07515 ↗First posted 15 Oct 2020cs.CLcited by 59

Not on the map. Why?

Abstract (arXiv)

Recurrent neural networks empirically generate natural language with high syntactic fidelity. However, their success is not well-understood theoretically. We provide theoretical insight into this success, proving in a finite-precision setting that RNNs can efficiently generate bounded hierarchical languages that reflect the scaffolding of natural language syntax. We introduce Dyck-(k,m), the language of well-nested brackets (of k types) and m-bounded nesting depth, reflecting the bounded memory needs and long-distance dependencies of natural language syntax. The best known results use O(k^fracm2) memory (hidden units) to generate these languages. We prove that an RNN with O(m log k) hidden units suffices, an exponential reduction in memory, by an explicit construction. Finally, we show that no algorithm, even with unbounded computation, can suffice with o(m log k) hidden units.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

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

59 papers.

Sort:

By area:

  1. 2021Thinking Like Transformerscited by 182
  2. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 137
  3. 2023What Formal Languages Can Transformers Express? A Surveycited by 120
  4. 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
  5. 2021Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformerscited by 101
  6. 2024In-Context Language Learning: Architectures and Algorithmscited by 86
  7. 2023How Do Transformers Learn Topic Structure: Towards a Mechanistic Understandingcited by 85
  8. 2024Mechanistic Design and Scaling of Hybrid Architecturescited by 57
  9. 2025How Linguistics Learned to Stop Worrying and Love the Language Modelscited by 50
  10. 2024The Expressive Capacity of State Space Models: A Formal Language Perspectivecited by 45
  11. 2024Theoretical limitations of multi-layer Transformercited by 43
  12. 2024Mission: Impossible Language Modelscited by 31
38 more
  1. 2024Transformers Can Represent n-gram Language Modelscited by 31
  2. 2023Transformers are uninterpretable with myopic methods: a case study with bounded Dyck grammarscited by 30
  3. 2024Separations in the Representational Capabilities of Transformers and Recurrent Architecturescited by 29
  4. 2023Interpretability Illusions in the Generalization of Simplified Modelscited by 24
  5. 2024Training Neural Networks as Recognizers of Formal Languagescited by 23
  6. 2024Learned feature representations are biased by complexity, learning order, position, and morecited by 22
  7. 2024What Languages are Easy to Language-Model? A Perspective from Learning Probabilistic Regular Languagescited by 20
  8. 2024A Survey on Compositional Learning of AI Models: Theoretical and Experimental Practicescited by 15
  9. 2022Benchmarking Compositionality with Formal Languagescited by 12
  10. 2024Emergent Word Order Universals from Cognitively-Motivated Language Modelscited by 11
  11. 2025On the Query Complexity of Verifier-Assisted Language Generationcited by 10
  12. 2021Causal Transformers Perform Below Chance on Recursive Nested Constructions, Unlike Humanscited by 8
  13. 2023Feature Interactions Reveal Linguistic Structure in Language Modelscited by 8
  14. 2021Learning Bounded Context-Free-Grammar via LSTM and the Transformer:Difference and Explanationscited by 7
  15. 2023Recurrent Neural Language Models as Probabilistic Finite-state Automatacited by 6
  16. 2021The Limitations of Limited Context for Constituency Parsingcited by 5
  17. 2024Understanding the Logic of Direct Preference Alignment through Logiccited by 5
  18. 2024Lower Bounds on the Expressivity of Recurrent Neural Language Modelscited by 4
  19. 2024Stability Analysis of Various Symbolic Rule Extraction Methods from Recurrent Neural Networkcited by 3
  20. 2025Rectifying LLM Thought from Lens of Optimizationcited by 3
  21. 2026Characterizing the Expressivity of Local Attention in Transformerscited by 3
  22. 2021Synthesizing Context-free Grammars from Recurrent Neural Networks (Extended Version)cited by 2
  23. 2022Assessing the Unitary RNN as an End-to-End Compositional Model of Syntaxcited by 2
  24. 2023Evaluating Transformer's Ability to Learn Mildly Context-Sensitive Languagescited by 2
  25. 2025Deciphering Trajectory-Aided LLM Reasoning: An Optimization Perspectivecited by 2
  26. 2026Exploration of Fast-Slow Latent Recurrence for Train-Short, Test-Long Generalizationcited by 2
  27. 2023Algorithms for Acyclic Weighted Finite-State Automata with Failure Arcscited by 1
  28. 2023On the Representational Capacity of Recurrent Neural Language Modelscited by 1
  29. 2024On Efficiently Representing Regular Languages as RNNscited by 1
  30. 2026A Provable Expressiveness Hierarchy in Hybrid Linear-Full Attentioncited by 1
  31. 2026On the Emergence of Syntax by Means of Local Interactioncited by 1
  32. 2024Precision, Stability, and Generalization: A Comprehensive Assessment of RNNs learnability capability for Classifying Counter and Dyck Languagescited by 0
  33. 2025Understanding Syntactic Generalization in Structure-inducing Language Modelscited by 0
  34. 2025Post-Norm can Resharpen Attentioncited by 0
  35. 2025Language models as tools for investigating the distinction between possible and impossible natural languagescited by 0
  36. 2025Large language models have learned to use languagecited by 0
  37. 2025Large language models are not about natural languagecited by 0
  38. 2025Linguists should learn to love speech-based deep learning modelscited by 0

50 most cited of 59 All 59 (JSON)