Neural Networks and the Chomsky Hierarchy

Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, Pedro A. Ortega

TL;DR

Modern neural networks aren't just "black boxes"—they are computational engines constrained by their underlying architecture. This paper demonstrates that the classical Chomsky hierarchy of formal languages accurately predicts the generalization limits of models like Transformers and LSTMs, proving that scaling data and parameters cannot overcome fundamental architectural deficiencies in handling complex logic.

What Problem Does This Paper Address?

In machine learning, we often assume that training and test data come from the same distribution (i.i.d.). However, true intelligence requires length generalization: the ability to learn a rule on short sequences (e.g., length $N=40$) and apply it to much longer ones (e.g., length $M=500$).

While many architectures are theoretically "Turing complete," they often fail to generalize in practice when trained with gradient descent. The authors ask: Can the theory of computation—specifically the Chomsky hierarchy—predict these failures? By mapping neural architectures to formal language classes (Regular, Context-Free, Context-Sensitive), they aim to provide a roadmap for designing models that can actually "reason" through algorithmic tasks.

Methods

The researchers conducted a massive empirical study involving 20,910 models across 15 tasks. They moved beyond simple language "recognition" (yes/no) to transduction, where a model must map an input sequence to a specific output sequence (e.g., reversing a string or solving a modular arithmetic equation).

They evaluated a diverse set of architectures:

  • Standard Recurrent Models: Vanilla RNNs and LSTMs.
  • Transformers: Testing various positional encodings (ALiBi, RoPE, etc.) to see if they could handle unseen sequence lengths.
  • Memory-Augmented Networks: RNNs equipped with differentiable external memory structures, specifically a Stack (for context-free tasks) and a Tape (for context-sensitive tasks).

The core of their analysis involved "reverse-engineering" the learned models using PCA to visualize internal state transitions and memory access patterns.

Datasets

The authors introduced a comprehensive length generalization benchmark spanning the Chomsky hierarchy:

  • Regular (R): Even Pairs, Parity Check, Cycle Navigation.
  • Deterministic Context-Free (DCF): Reverse String, Stack Manipulation, Modular Arithmetic (with brackets).
  • Context-Sensitive (CS): Duplicate String ($ww$), Binary Addition, Bucket Sort, and Compute Sqrt.

The benchmark is designed so that tasks at higher levels of the hierarchy require more sophisticated memory access (e.g., a stack vs. a simple counter).

Key Insights and Ideas

  • Architecture is Destiny: A model’s ability to generalize is largely determined by its memory structure. As shown in Figure 1, there is a clear correspondence between neural architectures and the hierarchy of formal languages. Formal language classes and their correspondence with neural network architectures.

  • The Transformer's "Positional" Ceiling: Transformers are excellent at identifying fixed-length patterns but struggle with length generalization. Because their positional encodings take on new, unseen values for longer sequences, the model's activations go out-of-distribution, causing performance to collapse.

  • LSTMs as Counter Machines: LSTMs are more powerful than vanilla RNNs not just because of "long-term memory," but because their gating mechanism allows them to act as counter machines. This enables them to solve tasks like Bucket Sort that are technically context-sensitive but rely on counting.
  • Scaling Laws Have Limits: The authors found that for tasks higher up the hierarchy, simply adding more layers or training data did not lead to generalization. If the architecture lacks the right inductive bias (like a stack for reversing strings), it will never "click" into the correct algorithm.
Figure 1: Formal language classes and their correspondence with neural network architectures. Left: Our empirical evaluation locates the architectures on the hierarchy of formal language classes. Right: Each formal language class is associated with a minimal computational model (automaton) to recognize or generate the language (see Section 3). All automata have a finite-state controller at their core, in addition to increasingly restrictive memory access as we descend the hierarchy.

Key Results

The study's quantitative results confirm the theoretical mapping:

  • RNNs solve Regular tasks but fail almost everything else.
  • Stack-RNNs achieved near 100% accuracy on DCF tasks like Reverse String, while standard RNNs and Transformers hovered around chance.
  • Tape-RNNs were the only models able to solve complex CS tasks like Duplicate String ($ww$).
  • Generalization Cliffs: Figure 2 illustrates how models that haven't learned the "correct" algorithm perform perfectly within the training range (left of the red line) but fail immediately when sequence length increases. Performance curves on three tasks showing the generalization cliff.
Figure 2: Performance curves on three tasks. The dashed vertical red line is the training range, mean- ing that sequences to the right have not been seen during training and thus measure generalization.

Qualitatively, the researchers showed that Stack-RNNs actually learned to use their stack as intended—pushing symbols until a trigger and then popping them—mirroring the behavior of a classical Pushdown Automaton.

Limitations and Future Work

  • Training Difficulty: Even when an architecture can represent a solution (like Tape-RNNs for Binary Multiplication), gradient descent often fails to find it because the required action trajectory is too complex.
  • Finite Bounds: The study is limited to tasks that can be tested in finite time, leaving the "Recursively Enumerable" (Turing Machine) level largely unexplored.
  • Nondeterminism: Some tasks (like Solve Equation) require nondeterministic controllers, which remain a challenge for standard differentiable architectures.

The authors suggest that the path to more capable AI isn't just "more data," but rather architectural innovations that incorporate structured, differentiable memory.

Summary updated

Abstract

Reliable generalization lies at the heart of safe ML and AI. However, understanding when and how neural networks generalize remains one of the most important unsolved problems in the field. In this work, we conduct an extensive empirical study (20'910 models, 15 tasks) to investigate whether insights from the theory of computation can predict the limits of neural network generalization in practice. We demonstrate that grouping tasks according to the Chomsky hierarchy allows us to forecast whether certain architectures will be able to generalize to out-of-distribution inputs. This includes negative results where even extensive amounts of data and training time never lead to any non-trivial generalization, despite models having sufficient capacity to fit the training data perfectly. Our results show that, for our subset of tasks, RNNs and Transformers fail to generalize on non-regular tasks, LSTMs can solve regular and counter-language tasks, and only networks augmented with structured memory (such as a stack or memory tape) can successfully generalize on context-free and context-sensitive tasks.
BibTeX
@inproceedings{deletang2023neural,
  author = {Grégoire Delétang and Anian Ruoss and Jordi Grau-Moya and Tim Genewein and Li Kevin Wenliang and Elliot Catt and Chris Cundy and Marcus Hutter and Shane Legg and Joel Veness and Pedro A. Ortega},
  title = {{Neural Networks and the Chomsky Hierarchy}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=WbxHAzkeQcn},
}
Figure