mlsanityData to 7 Oct 2026

Neural Networks and the Chomsky Hierarchy

arXiv 2207.02098 ↗First posted 5 Jul 2022cs.LG cs.AI cs.CLcited by 214

Not on the map. Why?

Cited by 23 in LLM reasoning, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

Reliable generalization lies at the heart of safe ML and AI. However, understanding when and how neural networks generalize remains one of the most important unsolved problems in the field. In this work, we conduct an extensive empirical study (20'910 models, 15 tasks) to investigate whether insights from the theory of computation can predict the limits of neural network generalization in practice. We demonstrate that grouping tasks according to the Chomsky hierarchy allows us to forecast whether certain architectures will be able to generalize to out-of-distribution inputs. This includes negative results where even extensive amounts of data and training time never lead to any non-trivial generalization, despite models having sufficient capacity to fit the training data perfectly. Our results show that, for our subset of tasks, RNNs and Transformers fail to generalize on non-regular tasks, LSTMs can solve regular and counter-language tasks, and only networks augmented with structured memory (such as a stack or memory tape) can successfully generalize on context-free and context-sensitive tasks.

Key facts. Cited by 214 papers in the map (data through 7 Oct 2026). Builds on 47 of its 95 references that are in the map. First posted on arXiv 5 Jul 2022.

Builds on

47 of 95 references.

References · 47

  1. 2017Attention Is All You Needcited by 59,932
  2. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  3. 2020Scaling Laws for Neural Language Modelscited by 6,411
  4. 2021RoFormer: Enhanced Transformer with Rotary Position Embeddingcited by 4,581
  5. 2014Neural Machine Translation by Jointly Learning to Align and Translatecited by 4,530
  6. 2014Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translationcited by 4,016
  7. 2014Sequence to Sequence Learning with Neural Networkscited by 2,974
  8. 2019Transformer-XL: Attentive Language Models Beyond a Fixed-Length Contextcited by 1,830
  9. 2018Relational inductive biases, deep learning, and graph networkscited by 1,341
  10. 2021Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolationcited by 1,085
  11. 2014Neural Turing Machinescited by 630
  12. 2022Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasetscited by 599
35 more
  1. 2016Adaptive Computation Time for Recurrent Neural Networkscited by 479
  2. 2014Memory Networkscited by 354
  3. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 286
  4. 2021Thinking Like Transformerscited by 182
  5. 2019On the Turing Completeness of Modern Neural Network Architecturescited by 129
  6. 2015Neural GPUs Learn Algorithmscited by 118
  7. 2018On the Practical Computational Power of Finite Precision RNNs for Language Recognitioncited by 117
  8. 2022Overcoming a Theoretical Limitation of Self-Attentioncited by 110
  9. 2022Unveiling Transformers with LEGO: a synthetic reasoning taskcited by 105
  10. 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 92
  11. 2015Inferring Algorithmic Patterns with Stack-Augmented Recurrent Netscited by 76
  12. 2020A Formal Hierarchy of RNN Architecturescited by 61
  13. 2015Learning to Transduce with Unbounded Memorycited by 54
  14. 2019Sequential Neural Networks as Automatacited by 54
  15. 2020How Can Self-Attention Networks Recognize Dyck-n Languages?cited by 51
  16. 2019LSTM Networks Can Perform Dynamic Countingcited by 45
  17. 2016Associative Long Short-Term Memorycited by 37
  18. 2019On the Computational Power of RNNscited by 35
  19. 2022End-to-end Algorithm Synthesis with Recurrent Networks: Logical Extrapolation Without Overthinkingcited by 33
  20. 2015Neural Random-Access Machinescited by 32
  21. 2019Memory-Augmented Recurrent Neural Networks Can Learn Generalized Dyck Languagescited by 31
  22. 2017Recurrent Neural Networks as Weighted Language Recognizerscited by 30
  23. 2015Grid Long Short-Term Memorycited by 19
  24. 2020A Survey of Neural Networks and Formal Languagescited by 17
  25. 2018Evaluating the Ability of LSTMs to Learn Context-Free Grammarscited by 16
  26. 2021Learning Hierarchical Structures with Differentiable Nondeterministic Stackscited by 16
  27. 2020Learning Context-Free Languages with Nondeterministic Stack RNNscited by 15
  28. 2018Context-Free Transductions with Neural Stackscited by 14
  29. 2015Learning Simple Algorithms from Examplescited by 12
  30. 2015Reinforcement Learning Neural Turing Machines - Revisedcited by 11
  31. 2017The Neural Network Pushdown Automaton: Model, Stack and Learning Simulationscited by 10
  32. 2016Extensions and Limitations of the Neural GPUcited by 7
  33. 2020Recognizing Long Grammatical Sequences Using Recurrent Networks Augmented With An External Differentiable Stackcited by 5
  34. 2017Improving the Neural GPU Architecture for Algorithm Learningcited by 4
  35. 2016Lie-Access Neural Turing Machinescited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 6; 2023: 38; 2024: 57; 2025: 57; 2026: 56.

214 papers.

Sort:

By area:

  1. 2024GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Modelscited by 533
  2. 2023The Impact of Positional Encoding on Length Generalization in Transformerscited by 319
  3. 2022Transformers Learn Shortcuts to Automatacited by 260
  4. 2023Language Modeling Is Compressioncited by 225
  5. 2024Repeat After Me: Transformers are Better than State Space Models at Copyingcited by 208
  6. 2023What Formal Languages Can Transformers Express? A Surveycited by 120
  7. 2023Randomized Positional Encodings Boost Length Generalization of Transformerscited by 114
  8. 2023Mechanistically analyzing the effects of fine-tuning on procedurally defined taskscited by 110
  9. 2025TiRex: Zero-Shot Forecasting Across Long and Short Horizons with Enhanced In-Context Learningcited by 107
  10. 2024Can Mamba Learn How to Learn? A Comparative Study on In-Context Learning Taskscited by 104
  11. 2022General-Purpose In-Context Learning by Meta-Learning Transformerscited by 102
  12. 2024Unlocking State-Tracking in Linear RNNs Through Negative Eigenvaluescited by 97
38 more
  1. 2023Physics of Language Models: Part 1, Learning Hierarchical Language Structurescited by 83
  2. 2024Transformers Can Achieve Length Generalization But Not Robustlycited by 82
  3. 2025DeltaProduct: Improving State-Tracking in Linear RNNs via Householder Productscited by 69
  4. 2022Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functionscited by 68
  5. 2024SynCode: LLM Generation with Grammar Augmentationcited by 66
  6. 2023Understanding In-Context Learning in Transformers and LLMs by Learning to Learn Discrete Functionscited by 62
  7. 2024The Expressive Capacity of State Space Models: A Formal Language Perspectivecited by 45
  8. 2024Neural Redshift: Random Networks are not Random Functionscited by 43
  9. 2023Modeling rapid language learning by distilling Bayesian priors into artificial neural networkscited by 40
  10. 2023Never Train from Scratch: Fair Comparison of Long-Sequence Models Requires Data-Driven Priorscited by 33
  11. 2024The What, Why, and How of Context Length Extension Techniques in Large Language Models -- A Detailed Surveycited by 32
  12. 2024Mission: Impossible Language Modelscited by 31
  13. 2025(How) Do Language Models Track State?cited by 31
  14. 2024DAPE: Data-Adaptive Positional Encoding for Length Extrapolationcited by 30
  15. 2022Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Taskscited by 29
  16. 2024Learning Universal Predictorscited by 29
  17. 2024Separations in the Representational Capabilities of Transformers and Recurrent Architecturescited by 29
  18. 2024Counting Ability of Large Language Models and Impact of Tokenizationcited by 29
  19. 2025Why Prompt Design Matters and Works: A Complexity Analysis of Prompt Search Space in LLMscited by 29
  20. 2023Sparse Universal Transformercited by 28
  21. 2024The CLRS-Text Algorithmic Reasoning Language Benchmarkcited by 28
  22. 2024On Expressive Power of Looped Transformers: Theoretical Analysis and Enhancement via Timestep Encodingcited by 28
  23. 2024Language Models Need Inductive Biases to Count Inductivelycited by 25
  24. 2024Universal Length Generalization with Turing Programscited by 25
  25. 2024Language Models as Models of Languagecited by 24
  26. 2024Training Neural Networks as Recognizers of Formal Languagescited by 23
  27. 2025Can Language Models Learn Typologically Implausible Languages?cited by 23
  28. 2024On Provable Length and Compositional Generalizationcited by 22
  29. 2024Position Coupling: Improving Length Generalization of Arithmetic Transformers Using Task Structurecited by 22
  30. 2025Implicit Language Models are RNNs: Balancing Parallelization and Expressivitycited by 21
  31. 2023Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensionscited by 20
  32. 2024What Languages are Easy to Language-Model? A Perspective from Learning Probabilistic Regular Languagescited by 20
  33. 2022Systematic Generalization and Emergent Structures in Transformers Trained on Structured Taskscited by 19
  34. 2023Pushdown Layers: Encoding Recursive Structure in Transformer Language Modelscited by 18
  35. 2023Can Transformers Learn to Solve Problems Recursively?cited by 17
  36. 2024Algorithmic Capabilities of Random Transformerscited by 17
  37. 2025Finite State Automata Inside Transformers with Chain-of-Thought: A Mechanistic Study on State Trackingcited by 17
  38. 2025GSM-Infinite: How Do Your LLMs Behave over Infinitely Increasing Context Length and Reasoning Complexity?cited by 16

50 most cited of 214 All 214 (JSON)