Learning Hierarchical Structures with Differentiable Nondeterministic Stacks

Brian DuSell, David Chiang

Introduction

Standard Recurrent Neural Networks (RNNs) excel at processing sequential data, but they inherently rely on a "flat" memory structure. When tasked with remembering a long sentence containing multiple nested clauses, an RNN must compress all that structural information into a single, fixed-size vector. This architectural limitation makes it notoriously difficult for them to generalize to unseen hierarchical patterns, such as matching brackets in computer code or parsing complex natural language grammar.

To address this, researchers have previously augmented RNNs with "differentiable stacks," effectively providing the neural network with a scratchpad analogous to a Pushdown Automaton (PDA). However, earlier iterations of these models struggled during training: the probability of executing a long, correct sequence of stack operations would become infinitesimally small, leading to vanishing gradients and stalled learning.

In this paper, researchers introduce the Renormalizing Nondeterministic Stack RNN (RNS-RNN). By allowing the model to utilize unnormalized weights for stack actions and observe its own internal state, the RNS-RNN achieves near-optimal performance on difficult algorithmic tasks and scales to process long, real-world text sequences incrementally.

The RNS-RNN Architecture

The authors supercharge the previous Nondeterministic Stack RNN (NS-RNN) with three major methodological upgrades:

  1. Unnormalized Transition Weights: Instead of forcing stack actions (push, pop, replace) to be probabilities that sum to one at every single step, the new model uses unnormalized positive weights. It only renormalizes when it explicitly needs to "read" the stack. This crucial change allows the model to "amplify" certain paths, preventing the gradient from disappearing during long sequences of operations.
  2. PDA State Visibility: In older versions, the controller could only observe the top symbol of the stack. The RNS-RNN is now equipped to see a joint distribution of the top symbol and the internal state of the underlying nondeterministic PDA. This provides much-needed context about its current position within a hierarchical structure (e.g., distinguishing between a "pushing" phase and a "matching/popping" phase).
  3. Memory-Limited Incremental Execution: To handle infinitely long sequences—such as a book or a large codebase—the authors introduce a restricted version that limits how far back a "pop" operation can reach. This optimization reduces the computational complexity from $O(n^3)$ to $O(n)$, making the model practical for standard natural language processing tasks.

Experiments and Key Insights

The model was evaluated across two primary domains: Formal Context-Free Languages (CFLs) and Natural Language.

Formal Context-Free Languages

The researchers tested the model on five synthetic tasks designed to rigorously evaluate structural logic. These included Marked Reversal (palindromes with a middle marker), Dyck Language (balanced brackets), and the Hardest CFL (a notoriously difficult language for parsers).

Key Results: * Near-Perfect Logic: On all five formal language tasks, the RNS-RNN achieved cross-entropy scores within 0.05 nats of the theoretical lower bound. * Faster Convergence: The shift to unnormalized weights proved to be a massive advantage. It allowed the model to learn correct actions for all time steps almost immediately, whereas older normalized models had to slowly learn from the "middle" of a sequence outwards.

Difference in cross-entropy during training on the Dyck language task.
  • Surpassing Baselines: The RNS-RNN successfully solved the "padded reversal" task, a benchmark where the previous state-of-the-art NS-RNN had failed to beat simpler deterministic models.
Difference in cross-entropy during training on the Hardest CFL task.

Natural Language Processing

To test real-world applicability, the model was evaluated on the Penn Treebank (PTB), a standard benchmark for language modeling.

On the PTB, the $O(n)$ RNS-RNN performed comparably to a well-tuned LSTM. While it didn't drastically outperform the LSTM on standard metrics, it successfully demonstrated that a complex $O(n^3)$ data structure can be scaled down to linear time for real-world text processing without breaking.

Why It Works: Nondeterminism as Parallelism

A core insight from the paper is that forcing local probabilities on stack actions actually bottlenecks global learning. By letting weights grow unnormalized, the model can more easily orchestrate the long-range dependencies required to solve deep hierarchies. Because the stack is nondeterministic, the model effectively explores an exponential number of possible "parses" or stack-operation sequences in parallel, weighted by their learned importance.

Limitations and Future Work

Despite these significant improvements, the RNS-RNN still faces an information bottleneck. Because the stack relies on a small, discrete alphabet of symbols, it struggles to store specific lexical information (like exact vocabulary words) on the stack.

Future work may involve expanding the stack's "bandwidth" so it can store more complex, continuous representations. This could potentially allow stack-augmented models to truly surpass LSTMs and Transformers in understanding the deep, nested nuances of human language. Additionally, while the $O(n)$ version is much faster, the constant computational factors involved in simulating a nondeterministic PDA remain high compared to simpler, standard architectures.

Summary updated

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.
BibTeX
@inproceedings{dusell2022learning,
  author = {Brian DuSell and David Chiang},
  title = {{Learning Hierarchical Structures with Differentiable Nondeterministic Stacks}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=KYuCwT_HMk4},
}

Loading related content...

Figure