Learning Bounded Context-Free-Grammar via LSTM and the Transformer: Difference and the Explanations

Hui Shi, Sicun Gao, Yuandong Tian, Xinyun Chen, Jishen ZhaoAAAI 2022 · OpenReview

Introduction

In theoretical computer science, both LSTMs (Long Short-Term Memory) and Transformers are recognized as Turing-complete, implying they possess the theoretical capacity to represent Context-Free Languages (CFLs). CFLs are characterized by recursive, hierarchical structures, such as nested parentheses in mathematical expressions or the syntax of programming languages. Despite this theoretical equivalence, Transformers consistently outperform LSTMs in practical applications involving these structures. This research investigates the underlying causes of this performance gap, moving beyond common explanations like numerical precision or memory constraints to explore the internal organizational mechanics of these models.

Methodology: Simulating Pushdown Automata

The researchers evaluated model performance by training them to simulate Pushdown Automata (PDA). A PDA is a theoretical machine that utilizes a stack (a first-in, last-out memory) to recognize CFLs. To analyze the internal representations of the models, two novel training configurations were introduced:

  1. Oracle Training: Models are supervised to predict not only the next token but also the PDA's internal state and the entire stack contents at every time step.
  2. Forced vs. Latent Decomposition: This approach tests whether a model's failure is due to a lack of raw capacity or a failure in information organization.
Figure 4: The forced decomposition architecture where the hidden state vector is explicitly partitioned into state and stack components.

In the Forced Decomposition setup (illustrated in Figure 4), the model's hidden vector is manually segmented, with specific portions dedicated to the PDA state and individual stack positions. In the Latent Decomposition setup, the model is provided with the same information but must autonomously determine how to organize it within its hidden vector.

Datasets and Tasks

The study utilized synthetic datasets representing four canonical context-free languages, each corresponding to a specific PDA structure:

  • Dyck: Balanced parentheses (e.g., (())).
  • $a^nb^n$: Equal counts of 'a's followed by 'b's.
  • Parity: Bitstrings with an even number of zeros.
  • $wcw^r$: Palindromic strings separated by a center marker.
Figure 1: Canonical Pushdown Automata (PDA) representations for the four classic languages used in the study.

Additionally, the models were tested on the SCAN Dataset, a benchmark for semantic parsing that requires translating natural language commands into action sequences, testing the models' ability to handle more complex, "real-world" hierarchical mappings.

Key Insights: The Organization Gap

The core finding of the study is the "Organization Gap." When LSTMs are forced to organize their memory (Forced Decomposition), their performance improves significantly, reaching levels comparable to Transformers. This demonstrates that LSTMs possess the necessary capacity to solve these problems but lack the inherent ability to factorize their latent space. Without explicit guidance, LSTMs tend to conflate state and stack information, making accurate retrieval impossible.

In contrast, Transformers are remarkably robust. Their performance remains high (~99% accuracy) regardless of whether decomposition is forced or latent. The attention mechanism appears naturally predisposed to keeping distinct pieces of hierarchical information separate and accessible, a property the authors term "latent space decomposition."

Results and Analysis

  • SCAN Accuracy: Standard LSTMs (Latent) achieved only 16.6% to 35% accuracy on the SCAN task. However, when Forced Decomposition was applied, accuracy surged to 91.3%.
  • Structural Limitations: Increasing the depth (e.g., to 4 layers) or width of LSTMs did not resolve the decomposition failure. This suggests the issue is architectural rather than a simple lack of parameters.
  • Visualization: t-SNE visualizations confirmed that LSTMs with forced decomposition maintain clean, distinct clusters for different stack states, whereas standard LSTMs produce a disorganized "mixed-color" representation, indicating a failure to track the stack.

Conclusion

The performance disparity between LSTMs and Transformers on hierarchical tasks is rooted in how they organize internal memory. While LSTMs struggle to factorize their latent space without explicit supervision, Transformers naturally excel at this task. These findings suggest that "Oracle Training" and forced decomposition could serve as valuable tools for pre-training recurrent models on formal grammars, potentially bridging the gap in structural learning for natural language processing tasks.

Summary updated

BibTeX
@inproceedings{shi2022learning,
  author = {Hui Shi and Sicun Gao and Yuandong Tian and Xinyun Chen and Jishen Zhao},
  title = {{Learning Bounded Context-Free-Grammar via LSTM and the Transformer: Difference and the Explanations}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  url = {https://openreview.net/forum?id=NNO_0A4O4EE},
}
Figure