Recurrent Neural Language Models as Probabilistic Finite-state Automata

Anej Svete, Ryan Cotterell

Introduction

Recurrent Neural Networks (RNNs) are foundational to modern natural language processing, yet they are often treated as "black boxes" with poorly understood theoretical limits. While classical automata theory provides a robust framework for understanding formal languages, most prior research has focused on "unweighted" or non-probabilistic languages—for instance, whether a network can recognize balanced parentheses. However, real-world language models are inherently probabilistic, defining distributions over sequences of tokens. This paper bridges the gap by establishing a formal equivalence between a specific class of RNNs and Deterministic Probabilistic Finite-state Automata (DPFSAs).

Theoretical Framework: From RNNs to DPFSAs

The authors focus on the Heaviside Elman RNN (HRNN), a standard Elman architecture where the activation function is the Heaviside step function ($H(x) = 1$ if $x > 0$, else $0$). This choice allows for a discrete state space, which is necessary for mapping to finite automata.

A central concept in this work is the Deterministic Probabilistic Finite-state Automaton (DPFSA). Unlike general probabilistic automata, a DPFSA is deterministic in its state transitions: given a current state and an input symbol, there is exactly one possible next state. However, it remains probabilistic because each transition and the termination of a sequence are associated with specific probabilities.

Example of a Deterministic Probabilistic Finite-state Automaton (DPFSA) defining probabilities for strings like $ab^n ab^m$.

Methods: Establishing Equivalence

The paper proves the equivalence of HRNNs and DPFSAs through a two-way simulation:

  1. RNN to DPFSA: Since an HRNN with $D$ neurons has at most $2^D$ possible hidden states, its behavior over any input sequence can be mapped to a finite state machine.
  2. DPFSA to RNN: The authors extend the classic 1954 Minsky construction. While Minsky originally showed how to encode unweighted automata into neural networks, this paper introduces a Weighted Minsky’s Construction. This allows the RNN to track state transitions while simultaneously outputting the correct transition probabilities via a Softmax or Sparsemax layer.

Complexity and the Hierarchy of Languages

A key contribution of this research is the establishment of lower bounds on the size of the hidden layer required to represent a given language. A common assumption in deep learning is that neural networks can achieve exponential compression of state spaces. The authors demonstrate that for general language modeling, this is not the case.

To faithfully represent a DPFSA with $N$ states over an alphabet $\Sigma$, an RNN requires a hidden layer size of $\Omega(N|\Sigma|)$ neurons. This linear scaling suggests a significant "space complexity bottleneck." Logarithmic compression (scaling with $\log |\Sigma|$) is only possible for specific, simpler classes of languages, such as n-gram models.

Hierarchy of complexity for various language models and their corresponding computational classes.

Key Insights

  • The Determinism Constraint: HRNNs are inherently deterministic in their state updates. Consequently, they are strictly less expressive than non-deterministic PFSAs and cannot represent distributions that require summing over multiple internal paths for a single string.
  • Heaviside as a Proxy: Although Heaviside functions are rarely used in practice, they serve as a theoretical lower bound for more common activation functions like ReLU.
  • Representability vs. Learnability: The proofs establish what an RNN can represent with optimal weights, but they do not guarantee that standard training algorithms like Gradient Descent will converge to these configurations.

Conclusion and Future Work

This work provides a rigorous theoretical foundation for understanding the representational capacity of recurrent architectures. By placing RNNs within the hierarchy of classical automata, the authors clarify the limits of these models. Future research may extend these findings to continuous activation functions (like Sigmoid or Tanh) and more complex architectures, including LSTMs, GRUs, and Transformers, to see how different gating mechanisms affect state compression and language representability.

Summary updated

Abstract

Understanding neural network architectures with formal models of computation promises to spark a better understanding of the network's capabilities and limitations. A long line of work has described recurrent neural networks (RNN) in terms of their connection to the well-understood finite-state automata (FSAs), whose sequential nature provides a useful analogy to how RNNs function. Minsky's [1954] construction first showed how RNNs can simulate FSAs and provided a way of understanding RNNs as FSAs. This paper presents a comprehensive review of this construction along with two additional classical results showcasing the relationship between RNNs and FSAs: The constructions due to Dewdney [1977] and Indyk [1995]. We are not only interested in \emph{whether} an RNN can simulate an FSA, but also in the space requirements to do so: Whereas Minsky [1954] shows that an RNN can simulate an FSA with $N$ states using $\mathcal{O}\left(N\right)$ neurons, Dewdney [1977] improved this to $\mathcal{O}\left(N^\frac{3}{4}\right)$ and Indyk [1995] further to $\mathcal{O}\left(\sqrt{N}\right)$, which he also showed to be optimal. We discuss the constructions, emphasizing their commonalities, and put them into the context of more modern research, focusing on the representational capacity of neural language models.
BibTeX
@inproceedings{svete2023recurrent,
  author = {Anej Svete and Ryan Cotterell},
  title = {{Recurrent Neural Language Models as Probabilistic Finite-state Automata}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2023},
  url = {https://openreview.net/forum?id=7Qv7nTwDS2Y},
}
Figure