The Surprising Computational Power of Nondeterministic Stack RNNs

Brian DuSell, David Chiang

Abstract

Traditional recurrent neural networks (RNNs) have a fixed, finite number of memory cells, which limits their formal language recognition power to regular languages. In practice, RNNs struggle to learn many context-free languages (CFLs). To expand their capabilities, prior work has augmented RNNs with nondeterministic stack data structures. This paper demonstrates that nondeterminism and the neural controller interact to produce two unexpected abilities: recognizing non-context-free languages and handling large alphabet sizes with minimal internal symbols. We also propose the Vector RNS-RNN, which simulates stacks of vectors to increase information capacity, showing improvements on the Penn Treebank benchmark.

Introduction

Recurrent Neural Networks (RNNs) like LSTMs and GRUs are fundamental to sequential data processing but face a theoretical "memory ceiling." Due to their fixed-size hidden state, they are mathematically equivalent to finite automata, making it difficult for them to learn hierarchical or recursive structures found in formal languages and natural language syntax.

To address this, researchers previously introduced "stacks" to RNNs, transforming them into neural versions of Pushdown Automata (PDAs). While deterministic stacks are useful, they cannot represent the ambiguity inherent in language. Nondeterministic stacks (NS-RNNs) were introduced to simulate all possible stack paths simultaneously. This paper investigates whether the interaction between a neural controller and a nondeterministic stack unlocks computational "superpowers" beyond the expected context-free language (CFL) completeness.

Architecture and Methods

The core of this research is the Renormalizing Nondeterministic Stack RNN (RNS-RNN). Unlike a standard PDA that follows a single path, the RNS-RNN utilizes dynamic programming to maintain a distribution over all possible stack configurations.

Architecture of the RNS-RNN showing the interaction between the controller, stack, and input/output layers.

The authors introduce several key innovations:

  1. Theoretical Proofs: They demonstrate that RNS-RNNs can recognize the intersection of multiple CFLs, placing them in a higher complexity class than standard PDAs.
  2. Vector RNS-RNN (VRNS-RNN): This model augments discrete stack symbols with high-dimensional vectors (e.g., word embeddings). This allows the model to combine the structural rigor of nondeterministic logic with the representational power of continuous vectors.
  3. Efficiency: An optimized algorithm reduces the time complexity of stack operations, facilitating the training of larger models.

Experimental Evaluation

The models were evaluated on three types of challenges: synthetic non-context-free languages (like $w\#w$ and $w\#w^R\#w$), large alphabet tasks (Dyck language with up to 200 bracket types), and natural language modeling using the Penn Treebank (PTB) benchmark.

Performance of RNS-RNN (purple) compared to baselines across various synthetic tasks, showing cross-entropy difference over training epochs and sequence lengths.

Key Results

  • Beyond CFLs: The RNS-RNN was the only model capable of learning the $w\#w$ and $ww'$ languages without explicit input hints, outperforming deterministic multi-stack models.
  • Alphabet Capacity: On the $w\#w^R$ task with an alphabet size of 200, the RNS-RNN with only 3 internal symbols achieved near-perfect performance. It achieves this by encoding symbols as specific probability distributions (points on a simplex) over its internal alphabet.
  • Natural Language Modeling: The VRNS-RNN achieved a test perplexity of 120.12 on PTB, a significant improvement over the baseline LSTM (125.90) and previous stack-augmented models.

Discussion and Conclusion

This work reveals that nondeterminism in neural networks is more than a path-finding mechanism; the neural controller can use the entire distribution of paths as a rich, multi-dimensional state. This allows a single stack to coordinate different nondeterministic branches, effectively acting like multiple stacks.

While the RNS-RNN faces challenges with $O(n^2)$ or $O(n^3)$ time complexity relative to sequence length, it successfully bridges the gap between discrete structural logic and continuous vector representations. Future work may focus on linearizing these computational costs for broader industrial applications and exploring more complex linguistic dependencies.

Summary updated

Abstract

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.
BibTeX
@inproceedings{dusell2023surprising,
  author = {Brian DuSell and David Chiang},
  title = {{The Surprising Computational Power of Nondeterministic Stack RNNs}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=o58JtGDs6y},
}
Figure