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:
- 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.
- 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.
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:
- Non-Context-Free Languages: Synthetic tasks like $w\#w$ (copying a string) and $w\#w^R\#w$, which require tracking multiple dependencies simultaneously.
- 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.
- 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.
- 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