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 (2200 models, 16 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 led to any non-trivial generalization, despite models having sufficient capacity to perfectly fit the training data. 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.
Introduction: The Generalization Gap
While neural networks are often celebrated as "universal function approximators," they frequently fail to generalize to out-of-distribution (OOD) data. A classic example is length generalization: a model trained to reverse strings of length 40 might completely fail when asked to reverse a string of length 500. Standard statistical learning theory struggles to explain this because it assumes training and test data are independent and identically distributed (i.i.d.).
This paper bridges the gap between theoretical computer science and modern AI by showing that the Chomsky hierarchy—a 70-year-old framework for classifying formal languages—accurately predicts the generalization limits of neural networks. By testing over 20,000 models, researchers demonstrate that an architecture's ability to handle complex, long-sequence data depends fundamentally on its internal memory structure rather than just its size or training data.
Mapping Architectures to Computational Theory
The authors conducted a massive empirical study involving 20,910 models across 15 different tasks. They evaluated a spectrum of models, each corresponding to a level of computational power within the hierarchy:
- RNNs: Theoretically equivalent to Finite State Automata (Regular languages).
- LSTMs: Often functioning as "counter machines," capable of handling regular and some counter-language tasks.
- Transformers: Evaluated with various positional encodings (None, Sin/Cos, RoPE, ALiBi, etc.).
- Memory-Augmented Networks: RNNs equipped with differentiable data structures, specifically a Stack-RNN (for Context-Free tasks) and a Tape-RNN (for Context-Sensitive tasks).
Instead of simple recognition, the study focused on transduction—mapping an input sequence to a specific output sequence (e.g., binary addition). This provides a more rigorous test of a model's algorithmic understanding. The benchmark included 15 synthetic tasks categorized by the hierarchy: Regular (e.g., Parity Check), Deterministic Context-Free (e.g., Reverse String), and Context-Sensitive (e.g., Binary Addition). Models were trained on sequences of length $L \le 40$ and tested on sequences up to length 500 to measure true algorithmic generalization.
Key Results: The Architectural Ceiling
The study defined "successful generalization" as achieving $\ge 90\%$ accuracy on unseen lengths. The results confirm that an architecture's internal memory structure is the primary determinant of its generalization limits.
- Inductive Bias Trumps Scale: For tasks higher up the hierarchy, simply adding more data or training time never led to generalization. The "ceiling" is architectural.
- The Transformer's Position Problem: Transformers generally failed to generalize to longer sequences on non-permutation-invariant tasks. Their reliance on positional encodings makes them vulnerable when sequence lengths exceed those seen during training.
- LSTMs as Counters: LSTMs outperformed standard RNNs on "counter-language" tasks (like Bucket Sort) because their gated memory allows them to track counts effectively.
- Memory is the Key: Only networks augmented with structured memory (stacks or tapes) successfully generalized on context-free and context-sensitive tasks.
Discussion and Future Directions
The findings highlight a critical distinction between theoretical capacity and practical optimization. While an architecture might be theoretically capable of solving a task (e.g., RNNs are technically Turing complete with infinite precision), gradient-based training (SGD) often fails to find the necessary weight configuration.
The results suggest that instead of just scaling up Transformers, the path to more intelligent and generalizable AI may lie in developing better differentiable data structures and memory-augmented controllers. Future work will need to address the large action spaces of models like the Tape-RNN, which currently makes the correct algorithmic trajectory difficult to find via standard gradient descent.
Summary updated