# Evaluating the Ability of LSTMs to Learn Context-Free Grammars

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Nov 2018.

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

- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Thinking Like Transformers](https://mlsanity.com/paper/2106.06981/) (2021)
- [Self-Attention Networks Can Process Bounded Hierarchical Languages](https://mlsanity.com/paper/2105.11115/) (2021)
- [Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions](https://mlsanity.com/paper/2211.12316/) (2022)
- [Feature Interactions Reveal Linguistic Structure in Language Models](https://mlsanity.com/paper/2306.12181/) (2023)
- [Learning Bounded Context-Free-Grammar via LSTM and the Transformer:Difference and Explanations](https://mlsanity.com/paper/2112.09174/) (2021)
- [MLRegTest: A Benchmark for the Machine Learning of Regular Languages](https://mlsanity.com/paper/2304.07687/) (2023)
- [What do Large Language Models Learn beyond Language?](https://mlsanity.com/paper/2210.12302/) (2022)
- [Can recurrent neural networks learn process model structure?](https://mlsanity.com/paper/2212.06430/) (2022)
- [State space models can express n-gram languages](https://mlsanity.com/paper/2306.17184/) (2023)
- [Stability Analysis of Various Symbolic Rule Extraction Methods from Recurrent Neural Network](https://mlsanity.com/paper/2402.02627/) (2024)
- [Synthesizing Context-free Grammars from Recurrent Neural Networks (Extended Version)](https://mlsanity.com/paper/2101.08200/) (2021)
- [Are Transformers a Modern Version of ELIZA? Observations on French Object Verb Agreement](https://mlsanity.com/paper/2109.10133/) (2021)
- [Assessing the Unitary RNN as an End-to-End Compositional Model of Syntax](https://mlsanity.com/paper/2208.05719/) (2022)
- [Enhancing Reinforcement Learning with discrete interfaces to learn the Dyck Language](https://mlsanity.com/paper/2110.14350/) (2021)
- [Exploring Learnability in Memory-Augmented Recurrent Neural Networks: Precision, Stability, and Empirical Insights](https://mlsanity.com/paper/2410.03154/) (2024)

## Abstract (arXiv)

While long short-term memory (LSTM) neural net architectures are designed to capture sequence information, human language is generally composed of hierarchical structures. This raises the question as to whether LSTMs can learn hierarchical structures. We explore this question with a well-formed bracket prediction task using two types of brackets modeled by an LSTM. Demonstrating that such a system is learnable by an LSTM is the first step in demonstrating that the entire class of CFLs is also learnable. We observe that the model requires exponential memory in terms of the number of characters and embedded depth, where a sub-linear memory should suffice. Still, the model does more than memorize the training input. It learns how to distinguish between relevant and irrelevant information. On the other hand, we also observe that the model does not generalize well. We conclude that LSTMs do not learn the relevant underlying context-free rules, suggesting the good overall performance is attained rather by an efficient way of evaluating nuisance variables. LSTMs are a way to quickly reach good results for many natural language tasks, but to understand and generate natural language one has to investigate other concepts that can make more direct use of natural language's structural nature.