REVIEW 8 cited by
Neural Networks and the Chomsky Hierarchy
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original 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.
Forward citations
Cited by 8 Pith papers
-
Auditing Discovery Claims: A Two-Sided Criterion for Agentic Science, with the Negative Side Decidable
A two-sided audit with a formally decidable negative side shows a single-oracle RNA design claim collapses from 43/60 to 1/60 under a three-predictor panel, while two AI-written operators survive a held-out judge.
-
When Does Reward Teach State? A Hidden-Automaton Instrument and the Group-Language Boundary
High reward in sparse RL does not imply latent-state recovery; a hidden-DFA instrument separates perception from planning gaps and flags group-language structure as a pre-training warning.
-
Learning State-Tracking from Code Using Linear RNNs
Linear RNNs with negative eigenvalues track permutation state from REPL traces under next-token prediction, but probabilistic state-tracking with partial reveals forces exponential belief decay without nonlinear renor...
-
(How) Can Transformers Predict Pseudo-Random Numbers?
Transformers predict LCG sequences in-context for fixed moduli up to 2^32 and unseen moduli up to 2^16 by learning the modulus factorization and digit-wise periodic structure.
-
Rethinking Memorization Measures and their Implications in Large Language Models
Contextual memorization, defined by comparing a string's training loss against the best loss without training on that string, is stricter than counterfactual memorization and suggests that zero-memorization optimal le...
-
Hierarchical Solomonoff Induction: An Unbounded Machine Learning Model
HSI, a hyperprior over all Solomonoff priors, is shown equivalent to Solomonoff Induction while enabling dataset-conditioned prediction and a training-set error bound.
-
Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformers
The paper claims pause tokens strictly increase constant-precision, constant-depth Transformer expressivity from a subset of AC0 to AC0 (and log-precision to TC0), but the constant-precision proof is not sound as written.
-
Tokenization Constraints in LLMs: A Study of Symbolic and Arithmetic Reasoning Limits
Matching token boundaries to the atomic units of a task, such as one letter per token, can improve LLM accuracy on symbolic reasoning by tens of percentage points and may matter more than model size.
Discussion (0). Sign in to comment.