The Surprising Computational Power of Nondeterministic Stack RNNs

Brian DuSell, David Chiang

TL;DR

This paper demonstrates that augmenting Recurrent Neural Networks (RNNs) with a nondeterministic stack (RNS-RNN) grants them computational powers far beyond standard context-free languages. This includes the ability to recognize cross-serial dependencies and encode massive alphabets into tiny discrete stacks. The authors also introduce the Vector RNS-RNN (VRNS-RNN), which combines nondeterminism with vector embeddings to achieve state-of-the-art results on the Penn Treebank language modeling benchmark.

What Problem Does This Paper Address?

Standard RNNs, like LSTMs and GRUs, are theoretically limited to recognizing "regular languages" because they rely on a fixed, finite number of memory cells. To move beyond this limitation, researchers previously added stacks to RNNs, effectively turning them into neural versions of Pushdown Automata (PDAs). This allowed them to handle Context-Free Languages (CFLs), such as nested parentheses.

However, two major hurdles remained:

  1. Beyond Context-Free: Human language contains "cross-serial dependencies" (e.g., in Swiss German or Bambara) that are non-context-free. Most stack RNNs are deterministic and struggle to process these structures.
  2. The Vocabulary Bottleneck: Discrete stacks require a stack alphabet. If your input vocabulary is 10,000 words, a discrete stack usually needs a similarly sized alphabet, which becomes computationally expensive ($O(|\Gamma|^3)$ or worse).

Methods

The authors build upon the Renormalizing Nondeterministic Stack RNN (RNS-RNN). Unlike deterministic stacks that follow a single path, the RNS-RNN simulates all possible stack operations in parallel using a dynamic programming algorithm (similar to the CYK algorithm for parsing), running in $O(n^3)$ time.

Architecture of the stack RNN model

The Innovation: Vector RNS-RNN (VRNS-RNN) To solve the capacity problem, the authors propose the VRNS-RNN. Instead of the stack containing only discrete symbols (like 'A' or 'B'), each stack element is a pair of a discrete symbol and a continuous vector.

  • Push: The controller pushes a discrete symbol $y$ and a vector $v_t$ (derived from the hidden state).
  • Pop: The model uncovers the symbol and vector that were underneath.
  • Reading: The "read" operation becomes a weighted interpolation of vectors across all nondeterministic branches.

Datasets

The models were evaluated on three distinct types of challenges:

  1. Non-Context-Free Languages: Synthetic tasks like $w\#w$ (copying a string) and $w\#w^R\#w$, which require tracking multiple dependencies simultaneously.
  2. Capacity Benchmarks: The $w\#w^R$ (palindrome) and Dyck language (nested brackets) tasks, where the input alphabet size ($k$) was scaled up to 200 to test how much information the stack could hold.
  3. Natural Language: The Penn Treebank (PTB), a standard benchmark for word-level language modeling.

Key Insights and Ideas

  • Intersections of CFLs: The authors prove that RNS-RNNs can recognize the intersection of multiple context-free languages. This makes them strictly more powerful than standard PDAs and allows them to handle complex linguistic phenomena like cross-serial dependencies.
  • The "Alphabet Trick": In a shocking finding, the authors showed that an RNS-RNN with a discrete stack alphabet of only 3 symbols could successfully learn a language with an input alphabet of 200 symbols.
  • How? The model uses nondeterminism to "orchestrate" weights. It encodes the 200 different symbols as distinct points in the high-dimensional simplex of the distribution over its 3 stack symbols.
  • Nondeterminism vs. Determinism: While deterministic multi-stack models can solve some non-CFLs if given "hints" (like explicit boundaries), only the nondeterministic RNS-RNN could learn them when those hints were removed.

Key Results

  • Formal Languages: The RNS 3-3 (3 states, 3 stack symbols) was the only model able to learn $w\#w$ and $ww'$ effectively without extra computational timesteps.
Training and generalization performance on formal language tasks
  • Scaling: On the $w\#w^R$ task with an alphabet of $k=200$, the RNS 2-3 model achieved near-zero cross-entropy, while deterministic vector-stack models (like Superposition Stacks) struggled as $k$ increased.
  • Penn Treebank: The new VRNS 3-3-5 (3 states, 3 symbols, vector size 5) achieved a test perplexity of 120.12, outperforming the standard LSTM (125.90) and previous deterministic stack models. This proves that even a tiny amount of nondeterminism and a small vector can significantly boost a large LSTM's performance.

Limitations and Future Work

  • Computational Cost: The $O(n^3)$ complexity of the RNS-RNN is a bottleneck for very long sequences. While the authors used a "windowing" technique to keep it manageable, it remains more expensive than a standard LSTM.
  • Unmarked Copying: As seen in the performance charts, no model in the study successfully learned the "unmarked" copying task ($ww$) without a middle delimiter, suggesting that even more advanced nondeterministic structures might be needed for truly "blind" search/copy tasks.
  • Generalization: While the models performed well on lengths seen during training, generalization to much longer strings remains a challenge for some non-CFL tasks.

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