# Neural Networks and the Chomsky Hierarchy

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

## Key facts

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

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [Sequence to Sequence Learning with Neural Networks](https://mlsanity.com/paper/1409.3215/) (2014)
- [Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context](https://mlsanity.com/paper/1901.02860/) (2019)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation](https://mlsanity.com/paper/2108.12409/) (2021)
- [Neural Turing Machines](https://mlsanity.com/paper/1410.5401/) (2014)
- [Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets](https://mlsanity.com/paper/2201.02177/) (2022)
- [Adaptive Computation Time for Recurrent Neural Networks](https://mlsanity.com/paper/1603.08983/) (2016)
- [Memory Networks](https://mlsanity.com/paper/1410.3916/) (2014)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Thinking Like Transformers](https://mlsanity.com/paper/2106.06981/) (2021)
- [On the Turing Completeness of Modern Neural Network Architectures](https://mlsanity.com/paper/1901.03429/) (2019)
- [Neural GPUs Learn Algorithms](https://mlsanity.com/paper/1511.08228/) (2015)
- [On the Practical Computational Power of Finite Precision RNNs for Language Recognition](https://mlsanity.com/paper/1805.04908/) (2018)
- [Overcoming a Theoretical Limitation of Self-Attention](https://mlsanity.com/paper/2202.12172/) (2022)
- [Unveiling Transformers with LEGO: a synthetic reasoning task](https://mlsanity.com/paper/2206.04301/) (2022)
- [Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity](https://mlsanity.com/paper/2204.06618/) (2022)
- [Inferring Algorithmic Patterns with Stack-Augmented Recurrent Nets](https://mlsanity.com/paper/1503.01007/) (2015)
- [A Formal Hierarchy of RNN Architectures](https://mlsanity.com/paper/2004.08500/) (2020)
- [Learning to Transduce with Unbounded Memory](https://mlsanity.com/paper/1506.02516/) (2015)
- [Sequential Neural Networks as Automata](https://mlsanity.com/paper/1906.01615/) (2019)
- [How Can Self-Attention Networks Recognize Dyck-n Languages?](https://mlsanity.com/paper/2010.04303/) (2020)
- [LSTM Networks Can Perform Dynamic Counting](https://mlsanity.com/paper/1906.03648/) (2019)
- [Associative Long Short-Term Memory](https://mlsanity.com/paper/1602.03032/) (2016)
- [On the Computational Power of RNNs](https://mlsanity.com/paper/1906.06349/) (2019)

## Built on by (most cited first, 30 of 217)

- [GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Models](https://mlsanity.com/paper/2410.05229/) (2024)
- [The Impact of Positional Encoding on Length Generalization in Transformers](https://mlsanity.com/paper/2305.19466/) (2023)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Language Modeling Is Compression](https://mlsanity.com/paper/2309.10668/) (2023)
- [Repeat After Me: Transformers are Better than State Space Models at Copying](https://mlsanity.com/paper/2402.01032/) (2024)
- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [TiRex: Zero-Shot Forecasting Across Long and Short Horizons with Enhanced In-Context Learning](https://mlsanity.com/paper/2505.23719/) (2025)
- [Randomized Positional Encodings Boost Length Generalization of Transformers](https://mlsanity.com/paper/2305.16843/) (2023)
- [Mechanistically analyzing the effects of fine-tuning on procedurally defined tasks](https://mlsanity.com/paper/2311.12786/) (2023)
- [General-Purpose In-Context Learning by Meta-Learning Transformers](https://mlsanity.com/paper/2212.04458/) (2022)
- [Can Mamba Learn How to Learn? A Comparative Study on In-Context Learning Tasks](https://mlsanity.com/paper/2402.04248/) (2024)
- [Unlocking State-Tracking in Linear RNNs Through Negative Eigenvalues](https://mlsanity.com/paper/2411.12537/) (2024)
- [Transformers Can Achieve Length Generalization But Not Robustly](https://mlsanity.com/paper/2402.09371/) (2024)
- [Physics of Language Models: Part 1, Learning Hierarchical Language Structures](https://mlsanity.com/paper/2305.13673/) (2023)
- [DeltaProduct: Improving State-Tracking in Linear RNNs via Householder Products](https://mlsanity.com/paper/2502.10297/) (2025)
- [Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions](https://mlsanity.com/paper/2211.12316/) (2022)
- [SynCode: LLM Generation with Grammar Augmentation](https://mlsanity.com/paper/2403.01632/) (2024)
- [Understanding In-Context Learning in Transformers and LLMs by Learning to Learn Discrete Functions](https://mlsanity.com/paper/2310.03016/) (2023)
- [The Expressive Capacity of State Space Models: A Formal Language Perspective](https://mlsanity.com/paper/2405.17394/) (2024)
- [Neural Redshift: Random Networks are not Random Functions](https://mlsanity.com/paper/2403.02241/) (2024)
- [Modeling rapid language learning by distilling Bayesian priors into artificial neural networks](https://mlsanity.com/paper/2305.14701/) (2023)
- [On Expressive Power of Looped Transformers: Theoretical Analysis and Enhancement via Timestep Encoding](https://mlsanity.com/paper/2410.01405/) (2024)
- [Never Train from Scratch: Fair Comparison of Long-Sequence Models Requires Data-Driven Priors](https://mlsanity.com/paper/2310.02980/) (2023)
- [(How) Do Language Models Track State?](https://mlsanity.com/paper/2503.02854/) (2025)
- [The What, Why, and How of Context Length Extension Techniques in Large Language Models -- A Detailed Survey](https://mlsanity.com/paper/2401.07872/) (2024)
- [Sparse Universal Transformer](https://mlsanity.com/paper/2310.07096/) (2023)
- [Mission: Impossible Language Models](https://mlsanity.com/paper/2401.06416/) (2024)
- [Counting Ability of Large Language Models and Impact of Tokenization](https://mlsanity.com/paper/2410.19730/) (2024)
- [Learning Universal Predictors](https://mlsanity.com/paper/2401.14953/) (2024)
- [DAPE: Data-Adaptive Positional Encoding for Length Extrapolation](https://mlsanity.com/paper/2405.14722/) (2024)

## 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.