# Learning Hierarchical Structures with Differentiable Nondeterministic Stacks

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 33 references that are in the map.
- First posted on arXiv 5 Sep 2021.

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

- [Regularizing and Optimizing LSTM Language Models](https://mlsanity.com/paper/1708.02182/) (2017)
- [A Systematic Assessment of Syntactic Generalization in Neural Language Models](https://mlsanity.com/paper/2005.03692/) (2020)
- [ListOps: A Diagnostic Dataset for Latent Tree Learning](https://mlsanity.com/paper/1804.06028/) (2018)
- [Recurrent Neural Network Grammars](https://mlsanity.com/paper/1602.07776/) (2016)
- [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)
- [Compound Probabilistic Context-Free Grammars for Grammar Induction](https://mlsanity.com/paper/1906.10225/) (2019)
- [Does syntax need to grow on trees? Sources of hierarchical inductive bias in sequence-to-sequence networks](https://mlsanity.com/paper/2001.03632/) (2020)
- [Learning to Transduce with Unbounded Memory](https://mlsanity.com/paper/1506.02516/) (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)
- [Quantity doesn't buy quality syntax with neural language models](https://mlsanity.com/paper/1909.00111/) (2019)
- [Tree-structured composition in neural networks without tree-structured architectures](https://mlsanity.com/paper/1506.04834/) (2015)
- [Recurrent Dropout without Memory Loss](https://mlsanity.com/paper/1603.05118/) (2016)
- [Ordered Memory](https://mlsanity.com/paper/1910.13466/) (2019)
- [Learning Context-Free Languages with Nondeterministic Stack RNNs](https://mlsanity.com/paper/2010.04674/) (2020)
- [Context-Free Transductions with Neural Stacks](https://mlsanity.com/paper/1809.02836/) (2018)
- [The Neural Network Pushdown Automaton: Model, Stack and Learning Simulations](https://mlsanity.com/paper/1711.05738/) (2017)
- [Hierarchical Representation in Neural Language Models: Suppression and Recovery of Expectations](https://mlsanity.com/paper/1906.04068/) (2019)
- [Finding Syntactic Representations in Neural Stacks](https://mlsanity.com/paper/1906.01594/) (2019)

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

- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Physics of Language Models: Part 1, Learning Hierarchical Language Structures](https://mlsanity.com/paper/2305.13673/) (2023)
- [Training Neural Networks as Recognizers of Formal Languages](https://mlsanity.com/paper/2411.07107/) (2024)
- [Can Language Models Learn Typologically Implausible Languages?](https://mlsanity.com/paper/2502.12317/) (2025)
- [Pushdown Layers: Encoding Recursive Structure in Transformer Language Models](https://mlsanity.com/paper/2310.19089/) (2023)
- [Stack Attention: Improving the Ability of Transformers to Model Hierarchical Patterns](https://mlsanity.com/paper/2310.01749/) (2023)
- [Dependency Transformer Grammars: Integrating Dependency Structures into Transformer Language Models](https://mlsanity.com/paper/2407.17406/) (2024)
- [The Surprising Computational Power of Nondeterministic Stack RNNs](https://mlsanity.com/paper/2210.01343/) (2022)
- [Beam Tree Recursive Cells](https://mlsanity.com/paper/2305.19999/) (2023)
- [Recursion in Recursion: Two-Level Nested Recursion for Length Generalization with Scalability](https://mlsanity.com/paper/2311.04449/) (2023)
- [Efficient Beam Tree Recursion](https://mlsanity.com/paper/2307.10779/) (2023)
- [A Transformer with Stack Attention](https://mlsanity.com/paper/2405.04515/) (2024)
- [A Constructive Framework for Nondeterministic Automata via Time-Shared, Depth-Unrolled Feedforward Networks](https://mlsanity.com/paper/2505.24110/) (2025)
- [Algorithms for Weighted Pushdown Automata](https://mlsanity.com/paper/2210.06884/) (2022)
- [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)

## Abstract (arXiv)

Learning hierarchical structures in sequential data -- from simple algorithmic patterns to natural language -- in a reliable, generalizable way remains a challenging problem for neural language models. Past work has shown that recurrent neural networks (RNNs) struggle to generalize on held-out algorithmic or syntactic patterns without supervision or some inductive bias. To remedy this, many papers have explored augmenting RNNs with various differentiable stacks, by analogy with finite automata and pushdown automata (PDAs). In this paper, we improve the performance of our recently proposed Nondeterministic Stack RNN (NS-RNN), which uses a differentiable data structure that simulates a nondeterministic PDA, with two important changes. First, the model now assigns unnormalized positive weights instead of probabilities to stack actions, and we provide an analysis of why this improves training. Second, the model can directly observe the state of the underlying PDA. Our model achieves lower cross-entropy than all previous stack RNNs on five context-free language modeling tasks (within 0.05 nats of the information-theoretic lower bound), including a task on which the NS-RNN previously failed to outperform a deterministic stack RNN baseline. Finally, we propose a restricted version of the NS-RNN that incrementally processes infinitely long sequences, and we present language modeling results on the Penn Treebank.