Lower Bounds on the Expressivity of Recurrent Neural Language Models

Anej Svete, Franz Nowak, Anisha Mohamed Sahabdeen, Ryan Cotterell

Presented at NAACL 2024, this research establishes a rigorous theoretical foundation for the expressivity of Recurrent Neural Networks (RNNs) as probabilistic models. While RNNs are widely recognized for their sequence processing capabilities, this work quantifies their ability to capture "regular" languages when treated as probability distributions rather than simple classifiers.

The Challenge of Probabilistic Expressivity

In formal language theory, models are often evaluated on their ability to recognize a language—determining if a string is grammatically correct. However, modern Large Language Models (LLMs) operate by assigning probabilities to strings. A critical distinction exists in the probabilistic domain: unlike classical automata where non-deterministic machines can always be converted to deterministic ones, non-deterministic probabilistic models are strictly more expressive.

Non-deterministic vs. deterministic probabilistic finite-state automata and their probability calculations.

Prior research successfully linked RNNs to deterministic probabilistic automata. This paper bridges the remaining gap, proving that standard Elman RNNs can represent the more complex distributions generated by non-deterministic probabilistic finite-state automata (PFSAs).

Constructive Proof: A Roadmap to Simulation

The authors employ a constructive approach, providing a "blueprint" for an RNN that mimics a PFSA. The core of this construction is a state-tracking mechanism where the RNN's hidden state vector maintains a probability distribution over all possible states of the PFSA, updating this "belief" in parallel as it processes input symbols.

The theoretical roadmap from exact simulation in idealized settings to approximate simulation using standard MLP components.

The proof progresses through four increasingly realistic scenarios, as illustrated in the roadmap above:

  1. Exact Simulation (Idealized): Utilizing "sparsemax" and $L_1$ normalization.
  2. Exact Simulation (Standard): Using standard "softmax" with a "log" activation and the inclusion of $-\infty$.
  3. Approximate Simulation: Demonstrating that the target distribution can be approached arbitrarily closely even without $-\infty$.
  4. The MLP Final Form: Leveraging the Universal Approximation Theorem to show that a standard Multi-Layer Perceptron (MLP) output layer can approximate the necessary log-transformations.

Key Theoretical Results

The primary contribution is Theorem 4.2, which states that for any regular language model (PFSA) and any error margin $\epsilon > 0$, there exists a ReLU-activated, softmax-normalized deep output Elman RNN that approximates that model within $\epsilon$ (measured by Total Variation Distance).

Furthermore, the authors establish that "linearly bounded precision"—where the number of bits required grows linearly with input length—is sufficient for this simulation. This is a significant finding as it moves away from the unrealistic assumption of infinite precision often found in Turing-completeness proofs for RNNs. The space complexity for such a simulation is shown to be $O(|Q||\Sigma|)$, where $|Q|$ is the number of states and $|\Sigma|$ is the alphabet size.

Discussion and Limitations

While this work establishes a new lower bound for RNN expressivity, several questions remain:

  • Upper Bounds: The research defines what RNNs can do, but the upper limit of their expressivity remains undefined. They may be capable of representing languages beyond the regular class.
  • Learnability: The proof demonstrates the existence of weight configurations that represent these languages. It does not guarantee that standard training algorithms, such as gradient descent, will successfully converge to these solutions.
  • Hierarchical Structures: Human language often involves context-free structures (e.g., nested parentheses). Proving that RNNs with linear precision can fully capture this class of languages is a subject for future investigation.

By proving that RNNs can handle non-determinism and establishing the sufficiency of linear precision, this paper provides a tighter lower bound on the expressivity of recurrent architectures in modern NLP.

Summary updated

Abstract

The recent successes and spread of large neural language models (LMs) call for a thorough understanding of their abilities. Describing their abilities through LMs’ representational capacity is a lively area of research. Investigations of the representational capacity of neural LMs have predominantly focused on their ability to recognize formal languages. For example, recurrent neural networks (RNNs) as classifiers are tightly linked to regular languages, i.e., languages defined by finite-state automata (FSAs). Such results, however, fall short of describing the capabilities of RNN language models (LMs), which are definitionally distributions over strings. We take a fresh look at the represen- tational capacity of RNN LMs by connecting them to probabilistic FSAs and demonstrate that RNN LMs with linearly bounded precision can express arbitrary regular LMs.
BibTeX
@inproceedings{svete2024lower,
  author = {Anej Svete and Franz Nowak and Anisha Mohamed Sahabdeen and Ryan Cotterell},
  title = {{Lower Bounds on the Expressivity of Recurrent Neural Language Models}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2024},
  url = {https://openreview.net/forum?id=2G4xja7GLT},
}
Figure