Abstract
Studying language models (LMs) in terms of well-understood formalisms allows us to precisely characterize their abilities and limitations. Previous work has investigated the representational capacity of recurrent neural network (RNN) LMs in terms of their capacity to recognize unweighted formal languages. However, LMs do not describe unweighted formal languages—rather, they define probability distributions over strings. In this work, we study what classes of such probability distributions RNN LMs can represent, which allows us to make more direct statements about their capabilities. We show that simple RNNs are equivalent to a subclass of probabilistic finite-state automata, and can thus model a strict subset of probability distributions expressible by finite-state models. Furthermore, we study the space complexity of representing finite-state LMs with RNNs. We show that, to represent an arbitrary deterministic finite-state LM with $N$ states over an alphabet $\Sigma$, an RNN requires $\Omega(N |\Sigma|)$ neurons. These results present a first step towards characterizing the classes of distributions RNN LMs can represent and thus help us understand their capabilities and limitations.
Introduction
For decades, researchers have sought to map the computational boundaries of Recurrent Neural Networks (RNNs). Historically, this investigation focused on unweighted formal languages—asking whether a network could distinguish between "grammatical" and "ungrammatical" strings. However, modern language modeling is fundamentally probabilistic; models assign likelihoods to sequences rather than binary labels.
This paper addresses the formal gap between neural architectures and probabilistic language theory. By focusing on the probability distributions RNNs can represent, the authors provide a more rigorous framework for understanding the reliability and capacity of these models. Specifically, they bridge the gap between simple RNNs and Probabilistic Finite-State Automata (PFSAs), revealing both the equivalence of these systems and the significant "price of admission" required to simulate them.
The Equivalence of HRNNs and DPFSAs
The study focuses 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$). While simpler than the continuous Sigmoid or ReLU functions used in modern engineering, the HRNN provides a mathematically tractable proxy for studying discrete state transitions.
The authors establish a core equivalence through an extension of Minsky’s Construction. In 1954, Marvin Minsky demonstrated how RNNs could simulate unweighted automata. This paper extends that logic to the probabilistic domain by showing how the RNN's weight matrices ($U, V$) and bias ($b$) can be configured to perform logical operations that track state transitions while the output layer generates the corresponding probability distributions.
The result is Theorem 4.1, which proves that HRNN language models are mathematically equivalent to Deterministic Probabilistic Finite-State Automata (DPFSAs). This means that for every HRNN, there exists a weakly equivalent DPFSA, and vice versa. However, this equivalence comes with a major caveat: HRNNs are strictly less expressive than non-deterministic PFSAs. Distributions that a non-deterministic automaton can represent compactly might require an exponentially larger HRNN to simulate.
The Space Complexity Bottleneck
One of the most significant contributions of this work is the analysis of space complexity. Previous research in unweighted languages suggested that RNNs could "compress" automata, potentially representing $N$ states using only $\sqrt{N}$ or even $\log N$ neurons.
This paper proves that such compression generally fails for weighted models. Because a language model must store independent probability distributions for every state-symbol pair in its output matrix, the RNN requires a hidden layer size $D$ that scales linearly with both the number of states and the size of the alphabet. Specifically, the authors show that representing a minimal DPFSA with $N$ states over alphabet $\Sigma$ requires $\Omega(N |\Sigma|)$ neurons.
There is, however, a niche exception: $\log |\Sigma|$-separability. The authors identify that only models possessing this specific property—such as standard n-gram models—can achieve efficient logarithmic scaling relative to the alphabet size. For general deterministic FSAs, the authors provide an algorithm to transform them into a log-separable version, though this process increases the state count by a factor of $|\Sigma|$, effectively moving the complexity from the neuron count to the state count.
Discussion and Implications
These findings have profound implications for how we view neural architecture:
- The Determinism Bottleneck: The fact that HRNNs are limited to deterministic distributions suggests they may struggle with certain types of ambiguity that non-deterministic models handle easily.
- Finite Precision Reality: Since all physical computers operate with finite-precision arithmetic, every deployed RNN is technically a finite-state machine. Therefore, the theoretical bounds established here are not just mathematical abstractions but represent real constraints on the engineering of reliable AI systems.
- Limits of Compression: The proof that neural compression is harder than previously thought for probabilistic models suggests that simply increasing the number of neurons may be a less efficient way to capture complex state-based logic than previously assumed.
Future Work
While this study provides a rigorous foundation using Heaviside activations, the behavior of "soft" activations like Sigmoid, Tanh, or ReLU remains an open frontier. These continuous functions allow for infinite state spaces in theory, though finite precision often collapses them back into finite-state behavior in practice. Additionally, extending this analysis to more complex architectures like LSTMs or Transformers—and investigating whether they can more efficiently represent linguistically motivated phenomena—remains a critical next step in formal language theory.
Summary updated