Abstract: 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.
Introduction
Standard Recurrent Neural Networks (RNNs) and LSTMs often struggle to capture deep hierarchical structures, such as nested parentheses in code or long-distance dependencies in natural language. Their primary limitation is a fixed-size hidden state; to remember the first half of a very long palindrome to predict the second half, an RNN eventually exhausts its memory capacity.
To address this, researchers have augmented RNNs with differentiable stacks. However, prior attempts often relied on deterministic stacks, which struggle with the syntactic ambiguity of human language, or nondeterministic stacks that were notoriously difficult to train. In the latter, the probability of a long sequence of correct stack actions becomes vanishingly small, leading to severe vanishing gradient problems.
The Renormalizing Nondeterministic Stack RNN (RNS-RNN)
This work introduces the Renormalizing Nondeterministic Stack RNN (RNS-RNN), which builds upon the Nondeterministic Stack RNN (NS-RNN) by simulating a nondeterministic pushdown automaton (PDA) using a weighted finite automaton (WFA). Three key innovations drive its improved performance:
- Unnormalized Transition Weights: Instead of forcing stack actions (push, pop, replace) to sum to a probability of 1.0 at every step, the model uses unnormalized positive weights. The distribution is only renormalized when the controller "reads" from the stack. This allows the model to "amplify" successful paths, preventing gradients from vanishing over long sequences.
- PDA State Visibility: The RNS-RNN allows the controller to see a joint distribution of both the top symbols and the internal states of the underlying PDA simulation, providing a richer representation of the stack's history.
- Memory-Limited Execution: To handle natural language, the authors introduced a constraint where stack transitions only span a fixed distance $D$. This reduces computational complexity from $O(n^3)$ to $O(n)$, making it feasible for standard training techniques like truncated Backpropagation Through Time (BPTT).
Experimental Evaluation
The model was evaluated on two fronts: five formal Context-Free Languages (CFLs) designed to test specific algorithmic capabilities (Marked Reversal, Unmarked Reversal, Padded Reversal, Dyck Language, and the Hardest CFL) and the Penn Treebank (PTB) for natural language modeling.
Key Results and Insights
The RNS-RNN achieved near-optimal performance on all five CFL tasks, reaching cross-entropy within 0.05 nats of the information-theoretic lower bound. A significant breakthrough was solving the "Padded Reversal" task, where the previous NS-RNN failed to outperform deterministic baselines. This success underscores the importance of allowing the controller to observe internal PDA states.
Furthermore, the model demonstrates strong generalization to longer sequences. Unlike standard RNNs that degrade as sequence length increases, the RNS-RNN maintains low cross-entropy across varying lengths for complex tasks like Dyck and the Hardest CFL.
In natural language experiments on the Penn Treebank, the memory-limited RNS-RNN successfully scaled to real-world text. While it did not significantly outperform LSTMs in raw perplexity, it proved that nondeterministic stacks can be efficiently integrated into large-scale language modeling. The authors also noted a "Perplexity-Syntax Gap," where a model's ability to predict the next word (perplexity) does not always correlate with its understanding of deep nested structures (Syntactic Generalization).
Conclusion and Future Work
The RNS-RNN represents a significant step forward in neural hierarchical learning. By utilizing unnormalized weights and PDA state visibility, it overcomes previous training hurdles for nondeterministic stacks. Future work will explore continuous or vector-based stack symbols to increase the "bandwidth" of information the stack can hold, potentially closing the gap in natural language performance.
Summary updated