Lower Bounds on the Expressivity of Recurrent Neural Language Models

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

Abstract

The recent successes and spread of large neural language models (LMs) call for a thorough understanding of their computational ability. Describing their computational abilities through LMs' representational capacity is a lively area of research. However, investigation into the representational capacity of neural LMs has predominantly focused on their ability to recognize formal languages. For example, recurrent neural networks (RNNs) with Heaviside activations 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 LMs, which are definitionally distributions over strings. We take a fresh look at the representational capacity of RNN LMs by connecting them to probabilistic FSAs and demonstrate that RNN LMs with linearly bounded precision can express arbitrary regular LMs.

Introduction

In formal language theory, models are typically categorized by their ability to "recognize" strings—determining whether a given input belongs to a specific set. However, modern neural language models (LMs) perform a more complex task: they assign probability distributions over sequences of strings. While previous research established strong links between Recurrent Neural Networks (RNNs) and "acceptors" like Finite State Automata (FSAs), a significant gap remained in understanding RNNs as probabilistic models.

In the probabilistic domain, non-deterministic Probabilistic Finite State Automata (PFSAs) are strictly more expressive than their deterministic counterparts. Until now, it was not formally proven that standard RNN architectures could capture the full range of distributions defined by these non-deterministic regular languages. This research addresses this gap, proving that simple RNNs are, at a minimum, as powerful as any regular probabilistic language.

Methodology: From Exact to Approximate Simulation

The authors focus on the Elman RNN, the most fundamental recurrent architecture. Their proof strategy is constructive, building specific RNN configurations to simulate PFSAs through a hierarchy of increasing realism. This progression is summarized in the figure below:

The progression of proofs from exact simulation with specialized activations to approximate simulation with standard MLP layers.

This constructive approach relies on three pillars:

  1. Linearly Bounded Precision: The authors assume that numerical precision (the number of bits for hidden states) grows linearly with input length. This allows the RNN to maintain cumulative probability products without losing information to rounding.
  2. Exact Simulation: They demonstrate that RNNs using sparsemax (which allows exact zeros) or softmax (with extended reals including $-\infty$) can perfectly simulate a PFSA.
  3. Approximate Simulation: By applying the Universal Approximation Theorem, they show that standard RNNs with MLP output layers and softmax projections can approximate any regular LM to an arbitrarily small error (Total Variation Distance).

The Power of Non-Determinism

A critical insight of this work is the handling of non-determinism. In standard automata theory, non-deterministic FSAs can always be converted into deterministic ones. However, in the probabilistic realm, some distributions can only be represented by non-deterministic PFSAs.

Comparison between determinizable and non-determinizable PFSAs. Non-determinism in probabilistic models provides a level of expressivity that deterministic models cannot match.

By allowing precision to scale with string length, the RNN can effectively "remember" the branching paths of these non-deterministic processes, proving that RNNs are not limited to the simpler deterministic subset of regular languages.

Key Results

  • Theorem 3.1: Establishes that an Elman RNN can track the state-string distributions of any PFSA within its hidden state.
  • Corollaries 3.1 & 3.2: Prove that RNNs can exactly simulate any regular LM using either sparsemax or a log-transformed softmax.
  • Theorem 4.2: The primary impact result, proving that for any regular language model and any error tolerance $\epsilon > 0$, there exists a standard ReLU-activated RNN with an MLP output that is $\epsilon$-close to that language model.
  • Space Complexity: The proofs indicate that a hidden state size of $O(|Q||\Sigma|)$ (where $Q$ is the number of states and $\Sigma$ is the alphabet) is sufficient for these simulations.

Limitations and Future Work

While this paper establishes a robust "lower bound" for RNN expressivity, it does not define the "upper bound" or the ceiling of their abilities. RNNs may be capable of representing languages far more complex than regular ones, such as context-free structures (e.g., nested parentheses).

Furthermore, there is a distinction between representational capacity and learnability. While the authors prove that an RNN can represent these languages, it does not guarantee that standard optimization algorithms like Adam will successfully find the necessary weights during training. Expanding this rigorous probabilistic analysis to higher levels of the Chomsky hierarchy remains a vital next step for theoretical NLP.

Summary updated

Abstract

The recent successes and spread of large neural language models (LMs) call for a thorough understanding of their computational ability. Describing their computational abilities through LMs' \emph{representational capacity} is a lively area of research. However, investigation into the representational capacity of neural LMs has predominantly focused on their ability to \emph{recognize} formal languages. For example, recurrent neural networks (RNNs) with Heaviside activations 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 \emph{language models} (LMs), which are definitionally \emph{distributions} over strings. We take a fresh look at the representational capacity of RNN LMs by connecting them to \emph{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