# Stack Attention: Improving the Ability of Transformers to Model Hierarchical Patterns

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 52 references that are in the map.
- First posted on arXiv 3 Oct 2023.

## Builds on (most cited first, 28 of 28)

- [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)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing](https://mlsanity.com/paper/1808.06226/) (2018)
- [Learning Deep Transformer Models for Machine Translation](https://mlsanity.com/paper/1906.01787/) (2019)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Transformers without Tears: Improving the Normalization of Self-Attention](https://mlsanity.com/paper/1910.05895/) (2019)
- [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)
- [When Do You Need Billions of Words of Pretraining Data?](https://mlsanity.com/paper/2011.04946/) (2020)
- [Structured Attention Networks](https://mlsanity.com/paper/1702.00887/) (2017)
- [Inferring Algorithmic Patterns with Stack-Augmented Recurrent Nets](https://mlsanity.com/paper/1503.01007/) (2015)
- [Tree Transformer: Integrating Tree Structures into Self-Attention](https://mlsanity.com/paper/1909.06639/) (2019)
- [Learning to Transduce with Unbounded Memory](https://mlsanity.com/paper/1506.02516/) (2015)
- [Grokking of Hierarchical Structure in Vanilla Transformers](https://mlsanity.com/paper/2305.18741/) (2023)
- [SG-Net: Syntax-Guided Machine Reading Comprehension](https://mlsanity.com/paper/1908.05147/) (2019)
- [Transformer Grammars: Augmenting Transformer Language Models with Syntactic Inductive Biases at Scale](https://mlsanity.com/paper/2203.00633/) (2022)
- [Describing Multimedia Content using Attention-based Encoder--Decoder Networks](https://mlsanity.com/paper/1507.01053/) (2015)
- [Coloring the Blank Slate: Pre-training Imparts a Hierarchical Inductive Bias to Sequence-to-sequence Models](https://mlsanity.com/paper/2203.09397/) (2022)
- [Quantity doesn't buy quality syntax with neural language models](https://mlsanity.com/paper/1909.00111/) (2019)
- [Structural Guidance for Transformer Language Models](https://mlsanity.com/paper/2108.00104/) (2021)
- [Transformers Generalize Linearly](https://mlsanity.com/paper/2109.12036/) (2021)
- [Learning Hierarchical Structures with Differentiable Nondeterministic Stacks](https://mlsanity.com/paper/2109.01982/) (2021)
- [Learning Context-Free Languages with Nondeterministic Stack RNNs](https://mlsanity.com/paper/2010.04674/) (2020)
- [The Surprising Computational Power of Nondeterministic Stack RNNs](https://mlsanity.com/paper/2210.01343/) (2022)

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

- [Training Neural Networks as Recognizers of Formal Languages](https://mlsanity.com/paper/2411.07107/) (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)
- [Investigating Recurrent Transformers with Dynamic Halt](https://mlsanity.com/paper/2402.00976/) (2024)
- [Compositional Generalization Across Distributional Shifts with Sparse Tree Operations](https://mlsanity.com/paper/2412.14076/) (2024)
- [A Transformer with Stack Attention](https://mlsanity.com/paper/2405.04515/) (2024)
- [Emergent Stack Representations in Modeling Counter Languages Using Transformers](https://mlsanity.com/paper/2502.01432/) (2025)
- [TRA: Better Length Generalisation with Threshold Relative Attention](https://mlsanity.com/paper/2503.23174/) (2025)
- [A Systematic Study of Compositional Syntactic Transformer Language Models](https://mlsanity.com/paper/2506.22978/) (2025)
- [Bearing Syntactic Fruit with Stack-Augmented Neural Networks](https://mlsanity.com/paper/2511.03547/) (2025)
- [Rational Transductors](https://mlsanity.com/paper/2602.07599/) (2026)
- [Grokking as Structural Inference: Transformers Need Bayesian Lottery Tickets](https://mlsanity.com/paper/2605.15787/) (2026)
- [Finding path and cycle counting formulae in graphs with Deep Reinforcement Learning](https://mlsanity.com/paper/2410.01661/) (2024)
- [Efficient transformer with reinforced position embedding for language models](https://mlsanity.com/paper/2410.04731/) (2024)
- [StackTrans: From Large Language Model to Large Pushdown Automata Model](https://mlsanity.com/paper/2507.15343/) (2025)
- [Transcript-Managed Transformers: Monotone Multi-Agent Collapse and Universality with Two Pop-Enabled Transcripts](https://mlsanity.com/paper/2607.29496/) (2026)
- [Typological Alignment of Stack-Based Language Models on Mildly Context-Sensitive Artificial Languages](https://mlsanity.com/paper/2610.02040/) (2026)

## Abstract (arXiv)

Attention, specifically scaled dot-product attention, has proven effective for natural language, but it does not have a mechanism for handling hierarchical patterns of arbitrary nesting depth, which limits its ability to recognize certain syntactic structures. To address this shortcoming, we propose stack attention: an attention operator that incorporates stacks, inspired by their theoretical connections to context-free languages (CFLs). We show that stack attention is analogous to standard attention, but with a latent model of syntax that requires no syntactic supervision. We propose two variants: one related to deterministic pushdown automata (PDAs) and one based on nondeterministic PDAs, which allows transformers to recognize arbitrary CFLs. We show that transformers with stack attention are very effective at learning CFLs that standard transformers struggle on, achieving strong results on a CFL with theoretically maximal parsing difficulty. We also show that stack attention is more effective at natural language modeling under a constrained parameter budget, and we include results on machine translation.