Abstract
NLP is deeply intertwined with the formal study of language, both conceptually and historically. Arguably, this connection goes all the way back to Chomsky's Syntactic Structures in 1957. It also still holds true today, with a strand of recent works building formal analysis of modern neural networks methods in terms of formal languages. In this document, I aim to explain background about formal languages as they relate to this recent work. I will by necessity ignore large parts of the rich history of this field, instead focusing on concepts connecting to modern deep learning-based NLP.
Introduction
This work provides a comprehensive bridge between classical formal language theory and modern NLP, offering a rigorous framework to understand the "black box" of neural networks. By treating architectures like LSTMs and Transformers as types of automata, we can reveal their fundamental computational limits and explain why certain models are better suited for specific linguistic tasks than others.
Problem Statement: The Expressive Power of Neural Architectures
In modern NLP, we often know that a model works, but we struggle to define exactly what it is capable of representing or why it fails on certain edge cases. While neural networks are continuous, high-dimensional systems, human language often follows discrete, structural rules (grammars).
The central question addressed is: What is the expressive power of a neural architecture? For example, can a vanilla RNN learn to count? Can an LSTM understand nested parenthetical structures? By mapping neural networks onto the Chomsky Hierarchy—a classical ranking of computational power—we can establish a mathematical "ruler" to measure the intelligence of our models.
Methods: The Saturated Network Framework
The core theoretical contribution is the discussion of the Saturated Network framework. To analyze a continuous neural network using discrete logic, we consider the "saturated" limit: as the weights of a network grow toward infinity, smooth activation functions (like sigmoid or tanh) sharpen into discrete step functions. This transformation turns a neural network into a formal automaton (a discrete machine).
Using this lens, architectures can be categorized based on their computational equivalence:
- RNNs/GRUs: Mapped to Finite-State Automata (FSA).
- LSTMs: Mapped to Counter Automata (capable of counting but not full recursion).
- Stack-augmented RNNs: Mapped to Pushdown Automata.
- Transformers: Analyzed through the lens of circuit complexity and "hard attention" mechanisms.
Synthetic Formal Language Benchmarks
As a theoretical survey, this analysis synthesizes results from various experimental papers that use synthetic formal language benchmarks, such as:
- $a^n b^n$: Testing the ability to count and match sequences.
- Dyck languages ($D_k$): Testing the ability to handle nested, well-balanced parentheses (a proxy for hierarchical syntax).
- Parity: Testing the ability to compute whether a bitstring has an even or odd number of ones.
Key Insights and Ideas
- The "Counting" Advantage of LSTMs: LSTMs consistently outperform vanilla RNNs on counting tasks because, in the saturated limit, an LSTM’s gating mechanism acts as a counter. This gives it a space complexity of $O(\log n)$, whereas a standard RNN is limited to $O(1)$ (finite memory).
- The Hierarchical Wall: Despite their power, LSTMs (and counter machines) cannot recognize Dyck languages with more than one type of bracket ($k > 1$). They can count, but they cannot remember the order of elements. This explains why "Stack RNNs" are theoretically necessary for true hierarchical processing.
- Transformers and Position: Without positional encodings, Transformers are "position-blind" and computationally weak. Even with encodings, "hard" attention Transformers face limitations from circuit complexity theory, struggling with tasks like calculating parity or recognizing certain nested structures.
- Inductive Bias via Norm Growth: Gradient Descent has an inductive bias toward "saturated" solutions. As a model trains and its weights grow, it naturally drifts toward the discrete, algorithmic behavior described by formal language theory.
Key Results
The field has established several foundational proofs:
- Turing Completeness: Rational-weighted RNNs are Turing-complete if given unbounded time and precision, though this doesn't reflect standard "real-time" usage.
- Space Complexity Hierarchy: Saturated architectures show a clear hierarchy:
- sCNN/sRNN/sGRU: $O(1)$ bits of memory.
- sLSTM: $O(\log n)$ bits (enough to count).
- Stack sRNN: $O(n)$ bits (enough for full hierarchy).
- WFA Equivalence: Certain "rational recurrences" (like QRNNs) are shown to be equivalent to Weighted Finite-State Automata, allowing for more efficient "compiled" versions of these models.
Limitations and Future Work
The "saturated" model is an approximation; real-world neural networks use finite weights and floating-point precision, which may allow for "hypercomputation" or introduce noise. Furthermore, just because a network can represent a grammar doesn't mean Gradient Descent will find it. The formal analysis of Transformers is still in its infancy compared to RNNs, and there is a growing need for a "non-trivial theory of complexity" for bounded-length strings, which more closely resembles human language use.
Summary updated