# The Surprising Computational Power of Nondeterministic Stack RNNs

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 34 references that are in the map.
- First posted on arXiv 4 Oct 2022.

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

- [On the Properties of Neural Machine Translation: Encoder-Decoder Approaches](https://mlsanity.com/paper/1409.1259/) (2014)
- [Neural Turing Machines](https://mlsanity.com/paper/1410.5401/) (2014)
- [On the Practical Computational Power of Finite Precision RNNs for Language Recognition](https://mlsanity.com/paper/1805.04908/) (2018)
- [Inferring Algorithmic Patterns with Stack-Augmented Recurrent Nets](https://mlsanity.com/paper/1503.01007/) (2015)
- [Learning to Transduce with Unbounded Memory](https://mlsanity.com/paper/1506.02516/) (2015)
- [Recurrent Neural Networks as Weighted Language Recognizers](https://mlsanity.com/paper/1711.05408/) (2017)
- [Rational Recurrences](https://mlsanity.com/paper/1808.09357/) (2018)
- [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 Neural Network Pushdown Automaton: Model, Stack and Learning Simulations](https://mlsanity.com/paper/1711.05738/) (2017)
- [SoPa: Bridging CNNs, RNNs, and Weighted Finite-State Machines](https://mlsanity.com/paper/1805.06061/) (2018)

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

- [Training Neural Networks as Recognizers of Formal Languages](https://mlsanity.com/paper/2411.07107/) (2024)
- [Stack Attention: Improving the Ability of Transformers to Model Hierarchical Patterns](https://mlsanity.com/paper/2310.01749/) (2023)
- [On Efficiently Representing Regular Languages as RNNs](https://mlsanity.com/paper/2402.15814/) (2024)
- [Bearing Syntactic Fruit with Stack-Augmented Neural Networks](https://mlsanity.com/paper/2511.03547/) (2025)
- [Exploring Learnability in Memory-Augmented Recurrent Neural Networks: Precision, Stability, and Empirical Insights](https://mlsanity.com/paper/2410.03154/) (2024)
- [Typological Alignment of Stack-Based Language Models on Mildly Context-Sensitive Artificial Languages](https://mlsanity.com/paper/2610.02040/) (2026)

## Abstract (arXiv)

Traditional recurrent neural networks (RNNs) have a fixed, finite number of memory cells. In theory (assuming bounded range and precision), this limits their formal language recognition power to regular languages, and in practice, RNNs have been shown to be unable to learn many context-free languages (CFLs). In order to expand the class of languages RNNs recognize, prior work has augmented RNNs with a nondeterministic stack data structure, putting them on par with pushdown automata and increasing their language recognition power to CFLs. Nondeterminism is needed for recognizing all CFLs (not just deterministic CFLs), but in this paper, we show that nondeterminism and the neural controller interact to produce two more unexpected abilities. First, the nondeterministic stack RNN can recognize not only CFLs, but also many non-context-free languages. Second, it can recognize languages with much larger alphabet sizes than one might expect given the size of its stack alphabet. Finally, to increase the information capacity in the stack and allow it to solve more complicated tasks with large alphabet sizes, we propose a new version of the nondeterministic stack that simulates stacks of vectors rather than discrete symbols. We demonstrate perplexity improvements with this new model on the Penn Treebank language modeling benchmark.