# On the Practical Ability of Recurrent Neural Networks to Recognize Hierarchical Languages

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Nov 2020.

## Built on by (most cited first, 22 of 22)

- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [A Review on Language Models as Knowledge Bases](https://mlsanity.com/paper/2204.06031/) (2022)
- [Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions](https://mlsanity.com/paper/2211.12316/) (2022)
- [Understanding In-Context Learning in Transformers and LLMs by Learning to Learn Discrete Functions](https://mlsanity.com/paper/2310.03016/) (2023)
- [How Linguistics Learned to Stop Worrying and Love the Language Models](https://mlsanity.com/paper/2501.17047/) (2025)
- [Separations in the Representational Capabilities of Transformers and Recurrent Architectures](https://mlsanity.com/paper/2406.09347/) (2024)
- [Training Neural Networks as Recognizers of Formal Languages](https://mlsanity.com/paper/2411.07107/) (2024)
- [Benchmarking Compositionality with Formal Languages](https://mlsanity.com/paper/2208.08195/) (2022)
- [Learning Bounded Context-Free-Grammar via LSTM and the Transformer:Difference and Explanations](https://mlsanity.com/paper/2112.09174/) (2021)
- [Recurrent Neural Language Models as Probabilistic Finite-state Automata](https://mlsanity.com/paper/2310.05161/) (2023)
- [A Provable Expressiveness Hierarchy in Hybrid Linear-Full Attention](https://mlsanity.com/paper/2602.01763/) (2026)
- [Learning Model Successors](https://mlsanity.com/paper/2502.00197/) (2025)
- [MapFormer: Self-Supervised Learning of Cognitive Maps with Input-Dependent Positional Embeddings](https://mlsanity.com/paper/2511.19279/) (2025)
- [Language models as tools for investigating the distinction between possible and impossible natural languages](https://mlsanity.com/paper/2512.09394/) (2025)
- [Large language models have learned to use language](https://mlsanity.com/paper/2512.12447/) (2025)
- [Large language models are not about natural language](https://mlsanity.com/paper/2512.13441/) (2025)
- [Linguists should learn to love speech-based deep learning models](https://mlsanity.com/paper/2512.14506/) (2025)
- [Are Language Models Models?](https://mlsanity.com/paper/2601.10421/) (2026)
- [Across the Levels of Analysis: Explaining Predictive Processing in Humans Requires More Than Machine-Estimated Probabilities](https://mlsanity.com/paper/2604.09466/) (2026)
- [You Can't Fight in Here! This is BBS!](https://mlsanity.com/paper/2604.09501/) (2026)
- [Not-So-Strange Love: Language Models and Generative Linguistic Theories are More Compatible than They Appear](https://mlsanity.com/paper/2605.10061/) (2026)
- [Causally Evaluating the Learnability of Formal Language Tasks](https://mlsanity.com/paper/2606.09822/) (2026)

## Abstract (arXiv)

While recurrent models have been effective in NLP tasks, their performance on context-free languages (CFLs) has been found to be quite weak. Given that CFLs are believed to capture important phenomena such as hierarchical structure in natural languages, this discrepancy in performance calls for an explanation. We study the performance of recurrent models on Dyck-n languages, a particularly important and well-studied class of CFLs. We find that while recurrent models generalize nearly perfectly if the lengths of the training and test strings are from the same range, they perform poorly if the test strings are longer. At the same time, we observe that recurrent models are expressive enough to recognize Dyck words of arbitrary lengths in finite precision if their depths are bounded. Hence, we evaluate our models on samples generated from Dyck languages with bounded depth and find that they are indeed able to generalize to much higher lengths. Since natural language datasets have nested dependencies of bounded depth, this may help explain why they perform well in modeling hierarchical dependencies in natural language data despite prior works indicating poor generalization performance on Dyck languages. We perform probing studies to support our results and provide comparisons with Transformers.