# Pushdown Layers: Encoding Recursive Structure in Transformer Language Models

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 46 references that are in the map.
- First posted on arXiv 29 Oct 2023.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding](https://mlsanity.com/paper/1804.07461/) (2018)
- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [What Does BERT Look At? An Analysis of BERT's Attention](https://mlsanity.com/paper/1906.04341/) (2019)
- [BLiMP: The Benchmark of Linguistic Minimal Pairs for English](https://mlsanity.com/paper/1912.00582/) (2019)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Targeted Syntactic Evaluation of Language Models](https://mlsanity.com/paper/1808.09031/) (2018)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [A Systematic Assessment of Syntactic Generalization in Neural Language Models](https://mlsanity.com/paper/2005.03692/) (2020)
- [Multilingual Constituency Parsing with Self-Attention and Pre-Training](https://mlsanity.com/paper/1812.11760/) (2018)
- [Overcoming a Theoretical Limitation of Self-Attention](https://mlsanity.com/paper/2202.12172/) (2022)
- [Recurrent Neural Network Grammars](https://mlsanity.com/paper/1602.07776/) (2016)
- [Self-Attention Networks Can Process Bounded Hierarchical Languages](https://mlsanity.com/paper/2105.11115/) (2021)
- [Ordered Neurons: Integrating Tree Structures into Recurrent Neural Networks](https://mlsanity.com/paper/1810.09536/) (2018)
- [Inferring Algorithmic Patterns with Stack-Augmented Recurrent Nets](https://mlsanity.com/paper/1503.01007/) (2015)
- [Linguistically-Informed Self-Attention for Semantic Role Labeling](https://mlsanity.com/paper/1804.08199/) (2018)
- [Grammar as a Foreign Language](https://mlsanity.com/paper/1412.7449/) (2014)
- [Tree Transformer: Integrating Tree Structures into Self-Attention](https://mlsanity.com/paper/1909.06639/) (2019)
- [Unsupervised Latent Tree Induction with Deep Inside-Outside Recursive Autoencoders](https://mlsanity.com/paper/1904.02142/) (2019)
- [Learning to Transduce with Unbounded Memory](https://mlsanity.com/paper/1506.02516/) (2015)
- [Unsupervised Recurrent Neural Network Grammars](https://mlsanity.com/paper/1904.03746/) (2019)
- [Transformer Grammars: Augmenting Transformer Language Models with Syntactic Inductive Biases at Scale](https://mlsanity.com/paper/2203.00633/) (2022)
- [Characterizing Intrinsic Compositionality in Transformers with Tree Projections](https://mlsanity.com/paper/2211.01288/) (2022)
- [Neural Random-Access Machines](https://mlsanity.com/paper/1511.06392/) (2015)
- [A Fast Unified Model for Parsing and Sentence Understanding](https://mlsanity.com/paper/1603.06021/) (2016)
- [Memory-Augmented Recurrent Neural Networks Can Learn Generalized Dyck Languages](https://mlsanity.com/paper/1911.03329/) (2019)
- [Effective Inference for Generative Neural Parsing](https://mlsanity.com/paper/1707.08976/) (2017)
- [Structural Guidance for Transformer Language Models](https://mlsanity.com/paper/2108.00104/) (2021)
- [Learning Hierarchical Structures with Differentiable Nondeterministic Stacks](https://mlsanity.com/paper/2109.01982/) (2021)
- [Guiding Attention for Self-Supervised Learning with Transformers](https://mlsanity.com/paper/2010.02399/) (2020)

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

- [SynCode: LLM Generation with Grammar Augmentation](https://mlsanity.com/paper/2403.01632/) (2024)
- [Mission: Impossible Language Models](https://mlsanity.com/paper/2401.06416/) (2024)
- [A Survey on Compositional Learning of AI Models: Theoretical and Experimental Practices](https://mlsanity.com/paper/2406.08787/) (2024)
- [Generative Pretrained Structured Transformers: Unsupervised Syntactic Language Models at Scale](https://mlsanity.com/paper/2403.08293/) (2024)
- [Dependency Transformer Grammars: Integrating Dependency Structures into Transformer Language Models](https://mlsanity.com/paper/2407.17406/) (2024)
- [Tree-Planted Transformers: Unidirectional Transformer Language Models with Implicit Syntactic Supervision](https://mlsanity.com/paper/2402.12691/) (2024)
- [Banyan: Improved Representation Learning with Explicit Structure](https://mlsanity.com/paper/2407.17771/) (2024)
- [Tree Transformers are an Ineffective Model of Syntactic Constituency](https://mlsanity.com/paper/2411.16993/) (2024)
- [CARMA: Enhanced Compositionality in LLMs via Advanced Regularisation and Mutual Information Alignment](https://mlsanity.com/paper/2502.11066/) (2025)
- [A Transformer with Stack Attention](https://mlsanity.com/paper/2405.04515/) (2024)
- [Inducing Systematicity in Transformers by Attending to Structurally Quantized Embeddings](https://mlsanity.com/paper/2402.06492/) (2024)
- [A Systematic Study of Compositional Syntactic Transformer Language Models](https://mlsanity.com/paper/2506.22978/) (2025)
- [Referring Expressions as a Lens into Spatial Language Grounding in Vision-Language Models](https://mlsanity.com/paper/2511.06146/) (2025)
- [GiLT: Augmenting Transformer Language Models with Dependency Graphs](https://mlsanity.com/paper/2605.15562/) (2026)
- [Learning Model Successors](https://mlsanity.com/paper/2502.00197/) (2025)
- [Filling in the Mechanisms: How do LMs Learn Filler-Gap Dependencies under Developmental Constraints?](https://mlsanity.com/paper/2604.14459/) (2026)
- [Transcript-Managed Transformers: Monotone Multi-Agent Collapse and Universality with Two Pop-Enabled Transcripts](https://mlsanity.com/paper/2607.29496/) (2026)
- [Beyond Sequence Order: Syntax-Informed Positional Embeddings for Transformers](https://mlsanity.com/paper/2608.06111/) (2026)
- [A Scaled-Up Empirical Study of Syntactic Language Models](https://mlsanity.com/paper/2610.16837/) (2026)

## Abstract (arXiv)

Recursion is a prominent feature of human language, and fundamentally challenging for self-attention due to the lack of an explicit recursive-state tracking mechanism. Consequently, Transformer language models poorly capture long-tail recursive structure and exhibit sample-inefficient syntactic generalization. This work introduces Pushdown Layers, a new self-attention layer that models recursive state via a stack tape that tracks estimated depths of every token in an incremental parse of the observed prefix. Transformer LMs with Pushdown Layers are syntactic language models that autoregressively and synchronously update this stack tape as they predict new tokens, in turn using the stack tape to softly modulate attention over tokens -- for instance, learning to "skip" over closed constituents. When trained on a corpus of strings annotated with silver constituency parses, Transformers equipped with Pushdown Layers achieve dramatically better and 3-5x more sample-efficient syntactic generalization, while maintaining similar perplexities. Pushdown Layers are a drop-in replacement for standard self-attention. We illustrate this by finetuning GPT2-medium with Pushdown Layers on an automatically parsed WikiText-103, leading to improvements on several GLUE text classification tasks.