Neural Networks and the Chomsky Hierarchy
The DOI matches its DataCite record; 6 of the 6 references it cites were found in a registry or an index.
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Their results show that 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 some context-free and context-sensitive tasks.”
From Looped Transformers for Length Generalization (2024) · cites this paper as Delétang et al. (2022)
In the citing paper
“Their results show that 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 some context-free and context-sensitive tasks.”
From Looped Transformers for Length Generalization (2024) · cites this paper as Delétang et al. (2022)
In the citing paper
“Their results show that 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 some context-free and context-sensitive tasks.”
From Looped Transformers for Length Generalization (2024) · cites this paper as Delétang et al. (2022)
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Elman, J. L. (1990) · Cognitive Science · doi:10.1207/s15516709cog1402_1 · Cited by 11,212
Scaling Laws for Neural Language Models
Kaplan, J., McCandlish, S., Henighan, T., Brown, T. B., Chess, B., Child, R., Gray, S., Radford, A., Wu, J., & Amodei, D. (2020) · arXiv · doi:10.48550/arxiv.2001.08361 · Cited by 9,550 · cited 2×
“This might imply hard limits for scaling laws (Kaplan et al., 2020): Even significantly increasing the amount of training data and the size of a Transformer are insufficient for it to “climb the Chomsky hiearchy”.”
BackgroundTransformer-XL: Attentive language models beyond a fixed-length context
Dai, Z., Yang, Z., Yang, Y., Carbonell, J., Le, Q., & Salakhutdinov, R. (2019) · Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics · doi:10.18653/v1/p19-1285 · Cited by 3,169 · cited 5×
“As described in Section 4, we evaluate five encodings (none, sin / cos , RoPE, ALiBi, and the relative positional encoding from Transformer-XL) and report the best-performing variant.”
BackgroundMethodInfluentialSukhbaatar, S., Szlam, A., Weston, J., & Fergus, R. (2015) · arXiv · doi:10.48550/arxiv.1503.08895 · Cited by 1,345
On the Practical Computational Power of Finite Precision RNNs for Language Recognition
Weiss, G., Goldberg, Y., & Yahav, E. (2018) · Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers) · doi:10.18653/v1/p18-2117 · Cited by 226 · cited 4×
“…Bhattamishra et al., 2020; Hahn, 2020; Hao et al., 2022; Korsky & Berwick, 2019; Merrill, 2019; Merrill et al., 2020; Merrill & Sabharwal, 2022; Weiss et al., 2018) has refined these theoretical analyses by considering linear computation steps and logarithmic precision, showing that: (i) RNNs…”
BackgroundMethodResultInfluentialRecurrent Neural Networks as Weighted Language Recognizers
Chen, Y., Gilroy, S., Maletti, A., May, J., & Knight, K. (2018) · Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers) · doi:10.18653/v1/n18-1205 · Cited by 49 · cited 2×
“Neural networks and the Chomsky hierarchy It was theoretically shown that RNNs and Transformers are Turing complete (Chen et al., 2018; Pérez et al., 2019; 2021; Siegelmann & Sontag, 1994).”
BackgroundMethod
Cited by
xLSTM: Extended Long Short-Term Memory
Beck, M., Pöppel, K., Spanring, M., Auer, A., Prudnikova, O., Kopp, M., Klambauer, G., Brandstetter, J., & Hochreiter, S. (2024) · Advances in Neural Information Processing Systems 37 · doi:10.52202/079017-3417 · Cited by 286
xLSTM: Extended Long Short-Term Memory
Beck, M., Pöppel, K., Spanring, M., Auer, A., Prudnikova, O., Kopp, M., Klambauer, G., Brandstetter, J., & Hochreiter, S. (2024) · arXiv · doi:10.48550/arxiv.2405.04517 · Cited by 299
GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Models
Mirzadeh, I., Alizadeh, K., Shahrokhi, H., Tuzel, O., Bengio, S., & Farajtabar, M. (2024) · arXiv · doi:10.48550/arxiv.2410.05229 · Cited by 714
“Delétang et al. (2023) demonstrated that transformers fail to generalize on non-regular tasks and showed that structured memory (e.g., memory tape) is necessary for handling complex tasks.”
Caution Ahead: Numerical Reasoning and Look‐Ahead Bias in AI Models
LEVY, B. (2026) · Journal of Accounting Research · doi:10.1111/1475-679x.70058 · Cited by 20
What Algorithms can Transformers Learn? A Study in Length Generalization
Zhou, H., Bradley, A., Littwin, E., Razin, N., Saremi, O., Susskind, J., Bengio, S., & Nakkiran, P. (2023) · arXiv · doi:10.48550/arxiv.2310.16028 · Cited by 10
Metadata
- Authors
- Delétang, G., Ruoss, A., Grau-Moya, J., Genewein, T., Wenliang, L. K., Catt, E., Cundy, C., Hutter, M., Legg, S., Veness, J., & Ortega, P. A.
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2022
- arXiv
- 2207.02098
- References
- 6
- Type
- Preprint
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.