Neural Networks and the Chomsky Hierarchy

2022/07/05 by Grégoire Delétang, Anian Ruoss, Delétang, Grégoire +20 · 2 voices · 55 citations
Computer Science · Engineering · Mathematics · #Algorithm #Artificial intelligence #Artificial neural network #Computation #Computer science #Context (archaeology) #Deep neural networks #Ferroelectric and Negative Capacitance Devices #Field (mathematics) #Generalization #Hierarchy #Machine learning #Mathematics #Models of neural computation #Natural Language Processing Techniques #Theoretical computer science #Topic Modeling #Transformer #cs.AI #cs.CL #cs.FL #cs.LG

paper · pdf · doi:10.48550/arxiv.2207.02098

published in arXiv (Cornell University) (Cornell University)

openalex publication_date 2022/07/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04

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.

Cited by

• Relative Positions Generalize, Absolute Positions Memorize: An Implicit-Bias Account of Length Generalization in Attention
• The Information Shadow: Measuring Structural Limits on What Language Models Can Learn
• Is In-Context Learning Learning?
• Fast weight programming and linear transformers: from machine learning to neurobiology
• Beyond Statistical Learning: Exact Learning Is Essential for General Intelligence
• Reflection Pretraining Enables Token-Level Self-Correction in Biological Sequence Models
• From Isolation to Entanglement: When Do Interpretability Methods Identify and Disentangle Known Concepts?
• Sequential Enumeration in Large Language Models
• Exact Learning of Arithmetic with Differentiable Agents
• Vibe Learning: Education in the age of AI
• Probability Distributions Computed by Hard-Attention Transformers
• Transformers Can Learn Rules They've Never Seen: Proof of Computation Beyond Interpolation
• Education Paradigm Shift To Maintain Human Competitive Advantage Over AI
• To Infinity and Beyond: Tool-Use Unlocks Length Generalization in State Space Models
• Unraveling Syntax: Language Modeling and the Substructure of Grammars
• Which Word Orders Facilitate Length Generalization in LMs? An Investigation with GCG-Based Artificial Languages
• GramTrans: A Better Code Representation Approach in Code Generation
• Black-box Context-free Grammar Inference for Readable & Natural Grammars
• An empirical study on the limitation of Transformers in program trace generation
• Structured Sparse Transition Matrices to Enable State Tracking in State-Space Models
• Bridging Kolmogorov Complexity and Deep Learning: Asymptotically Optimal Description Length Objectives for Transformers
• Exploring Major Transitions in the Evolution of Biological Cognition With Artificial Neural Networks
• Beyond Memorization: Extending Reasoning Depth with Recurrence, Memory and Test-Time Compute Scaling
• RNN Generalization to Omega-Regular Languages
• Parity Requires Unified Input Dependence and Negative Eigenvalues in SSMs
• Small transformer architectures for task switching
• StackTrans: From Large Language Model to Large Pushdown Automata Model
• Rethinking Memorization Measures and their Implications in Large Language Models
• Learning State-Tracking from Code Using Linear RNNs
• The Imitation Game: Turing Machine Imitator is Length Generalizable Reasoner
• Transcript-Managed Transformers: Monotone Multi-Agent Collapse and Universality with Two Pop-Enabled Transcripts
• On the Existence of Universal Simulators of Attention
• Long-Short Alignment for Effective Long-Context Modeling in LLMs
• RELIC: Evaluating Complex Reasoning via the Recognition of Languages In-Context
• Fodor and Pylyshyn's Legacy: Still No Human-like Systematic Compositionality in Neural Networks
• Weight-Space Linear Recurrent Neural Networks
• Position as Probability: Self-Supervised Transformers that Think Past Their Training for Length Extrapolation
• Characterizing the Expressivity of Fixed-Precision Transformer Language Models
• TiRex: Zero-Shot Forecasting Across Long and Short Horizons with Enhanced In-Context Learning
• Born a Transformer -- Always a Transformer? On the Effect of Pretraining on Architectural Abilities
• Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformers
• Revisiting Bi-Linear State Transitions in Recurrent Neural Networks
• Recursive Decomposition with Dependencies for Generic Divide-and-Conquer Reasoning
• Structured Linear CDEs: Maximally Expressive and Parallel-in-Time Sequence Models
• Bottlenecked Transformers: Periodic KV Cache Consolidation for Generalised Reasoning
• Advancing the Scientific Method with Large Language Models: From Hypothesis to Discovery
• Tokenization Constraints in LLMs: A Study of Symbolic and Arithmetic Reasoning Limits
• The Counting Power of Transformers
• How Transformers Learn Regular Language Recognition: A Theoretical Study on Training Dynamics and Implicit Bias
• When Does Tool Use Increase the Expressive Power of Finite-Precision Recurrent Models?
• On Subquadratic Architectures: From Applications to Principles
• Length Generalization Bounds for Transformers
• Characterizing the Expressivity of Local Attention in Transformers
• What Formal Languages Can Transformers Express? A Survey
• The Optimal Choice of Hypothesis Is the Weakest, Not the Shortest

Discussions

• Neural Networks and the Chomsky Hierarchy [hn, 164 points, 79 comments]
• Neural Networks and the Chomsky Hierarchy by DeepMind [hn, 5 points, 1 comments]

Related

• Decoding Generalization from Memorization in Deep Neural Networks
• Generalization Error in Deep Learning
• Generalizing in the Real World with Representation Learning
• Rethinking generalization requires revisiting old ideas: statistical mechanics approaches and complex learning behavior
• Generalization Through the Lens of Learning Dynamics