PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2207.02098v3cs.LGcs.AIcs.CLcs.FL

TL;DR

The paper asks when neural networks generalize reliably beyond the training distribution, especially on sequence tasks where standard i.i.d. assumptions fail. It conducts a large empirical study organized by the Chomsky hierarchy and finds an architecture-dependent generalization pattern, with structured external memory supporting higher-level tasks.

  • Problem

    The paper asks how neural networks generalize on out-of-distribution sequences when training and test lengths differ, a setting not covered by standard i.i.d. assumptions.

  • Method

    The authors evaluate 20'910 models across 15 sequence-prediction tasks spanning the Chomsky hierarchy, comparing standard and memory-augmented architectures.

  • Results

    RNNs generalize up to regular tasks, Stack-RNNs up to deterministic context-free tasks, and Tape-RNNs up to context-sensitive tasks in the evaluated benchmark.

  • Takeaways & Limitations

    The results indicate a model hierarchy on the investigated tasks, with external stack or tape memory enabling architectures to climb the Chomsky hierarchy.

  • Takeaways & Limitations

    The claims are limited to the empirical study and finite maximum test lengths, so they do not guarantee arbitrary-length generalization or universal task-level boundaries.

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper examines whether computational theory can predict practical neural-network generalization on sequence tasks outside the training distribution. It argues that architecture and training constraints matter, and studies this question empirically through the Chomsky hierarchy.

  • Motivation: Non-i.i.d. length generalization tests models trained on sequences of length ℓ≤N against arbitrarily longer sequences ℓ≫N.This setting directly probes inductive inference beyond observed examples.
  • Motivation: Gradient-based training can make theoretically universal or Turing-complete architectures practically non-universal by failing to find suitable parameters.The paper therefore treats architecture and optimization as joint practical constraints.
  • Motivation: The Chomsky hierarchy links increasing task complexity to computational models with increasingly capable or differently constrained memory access.The paper uses this correspondence to organize sequence-prediction tasks and architectures.
  • This work: 20'910 models and 15 tasks span the Chomsky hierarchy to evaluate how neural architectures generalize on sequence-prediction problems.The study includes RNNs, LSTMs, Transformers, and memory-augmented networks.
  • This work: The benchmark is designed to identify failure modes and test whether more training data enables higher-level generalization when training data are fit perfectly.The authors report negative results for some architectures despite sufficient capacity and increased data.

2 RELATED WORK

Prior work finds that common neural architectures learn some simple formal languages but struggle with more advanced languages without external memory. Theoretical claims of computational completeness are often impractical under finite computation and finite numerical precision.

  • Learning formal languages: RNNs and LSTMs can learn simple counting languages and Dyck-1, but advanced languages may require exponential memory in input length.Their limited external-memory access constrains extrapolation to longer sequences.
  • Learning formal languages: RNNs and LSTMs can learn some context-sensitive languages, but prior studies report generalization only to lengths close to those used during training.This distinguishes learning a training-range pattern from robust length generalization.
  • Neural networks and the Chomsky hierarchy: Although RNNs and Transformers have been shown theoretically to be Turing complete, those results rely on unbounded recurrent steps and arbitrary numerical precision.The related analyses motivate evaluating practical rather than purely idealized computational power.
  • Memory-augmented networks: Memory-augmented networks add differentiable read and write access to structures including stacks, random-access memory, and memory matrices.These designs provide architectural mechanisms for handling dependencies beyond hidden-state computation.

3 BACKGROUND

The paper recasts sequence prediction as transduction between formal languages and uses formal grammars and automata to characterize task complexity. This preserves the Chomsky hierarchy’s computational models while allowing outputs at each transition.

  • Formal languages: Infinite formal languages provide arbitrarily long sequences with shared structure for testing generalization to unseen lengths.A grammar generates the sequences used to probe extrapolation.
  • Formal languages: A formal language is a set of finite strings over a finite alphabet, and grammars generate such languages through production rules.The background gives binary examples including counting, palindromes, duplication, and Turing-machine descriptions.
  • Recognizing a language: An automaton recognizes a language by accepting every string in the language and rejecting all others.A deterministic finite-state automaton uses states, an alphabet, transitions, an initial state, and accepting states.
  • Transduction vs. recognition: Language transduction learns a deterministic mapping from an input word in one formal language to an output word in another.This avoids the need to construct a finite set of negative examples for recognition.
  • Transduction vs. recognition: The transduction hierarchy retains FSAs, PDAs, LBAs, and TMs, with memory augmentations unchanged while machines additionally output values at transitions.Thus the hierarchy applies to sequence mappings rather than only language acceptance.

4 METHODS

The experiments define sequence-transduction tasks across the Chomsky hierarchy, train multiple neural architectures on sampled sequences, and measure accuracy on longer unseen sequences. Models use dummy output tokens and are evaluated across task-specific computational demands.

  • Problem setup: The model predicts output continuations from input sequences, with |y| empty dummy tokens appended so it knows when the input ends.Per-sequence accuracy is the percentage of correctly predicted output tokens.
  • Tasks: Tasks range from modular arithmetic at the regular level to binary addition at the context-sensitive level, emphasizing counting, repetition, long-distance dependencies, and hierarchy.Context-sensitive tasks receive particular emphasis because they are challenging for state-of-the-art models.
  • Architectures: Architectures combine an RNN controller with either a deterministic stack or a bounded tape to cover different hierarchy levels.The stack and tape are differentiable memory structures with elements in R^d for d = 8.
  • Evaluation: Table 2 reports accuracy averaged over unseen lengths and maximized over 10 random seeds, with scores of at least 90% counted as successful generalization.Random accuracy is 50% for most tasks and 20% for Cycle Navigation, Bucket Sort, and two modular arithmetic tasks.
  • Data generation: Training samples lengths from U(1, 40), while test samples use U(41, 500) to measure length generalization.The test range contains sequences longer than any training sequence.

5 RESULTS

Across sequence-prediction tasks, architectures generally match the Chomsky hierarchy, while learned internal mechanisms reveal how models implement regular, deterministic context-free, and context-sensitive algorithms. Transformers remain most successful on permutation-invariant tasks but fail to generalize on most others, partly because positional encodings become out-of-distribution at longer lengths.

  • 5.1 MAIN RESULT: RNNs solve tasks up to the regular level, Stack-RNNs up to the deterministic context-free level, and Tape-RNNs up to the context-sensitive level.The match is imperfect: Stack-RNNs fail on Solve Equation (DCF), while Tape-RNNs fail on Binary Multiplication (CS) and Compute Sqrt (CS).
  • 5.2 ANALYSIS OF LEARNED PROGRAM STRUCTURE: RNN internal states form four clusters on Parity Check, consistent with a finite-state solution, while Stack-RNNs solve regular tasks without using their stack.Stack-RNNs use only NO-OP or POP actions, indicating reliance on a finite-state controller rather than stack memory.
  • 5.2 ANALYSIS OF LEARNED PROGRAM STRUCTURE: Stack-RNNs learn expected stack algorithms for Reverse String and Modular Arithmetic by pushing, preserving, and popping intermediate results at bracket boundaries.For Modular Arithmetic, stack operations occur when brackets open or close, while numbers and operators are handled by the internal controller.
  • 5.2 ANALYSIS OF LEARNED PROGRAM STRUCTURE: Tape-RNN mechanisms on Duplicate String are indicative of the task grammar, writing the input to memory, duplicating it, repositioning, and outputting the result.The learned sequence uses WRITE-LEFT, JUMP-RIGHT, WRITE-STAY, and later WRITE-LEFT actions across the input, memory, and output regions.
  • 5.3 LSTMS: LSTMs solve Bucket Sort (CS) almost perfectly, but finding non-regular solutions with counters through gradient descent is harder than using a stack or tape.LSTMs are more powerful than RNNs for counting tasks, yet permissive external memory structures make non-regular computation easier to learn.
  • 5.4 TRANSFORMERS: Transformers generalize best on permutation-invariant tasks, but fail on most others regardless of positional encoding.They solve Bucket Sort (CS), generalize non-trivially on Cycle Navigation (R), and solve Even Pairs (R); positional encodings can produce out-of-distribution activations on longer sequences.

6 DISCUSSION

The study evaluates generalization on substantially longer out-of-distribution sequences and finds that standard architectures remain limited, despite strong performance on fixed-size patterns. Increasing data and Transformer size may not overcome the absence of extendable memory.

  • Evaluation and interpretation: Testing on sequences significantly longer than training data provides evidence about whether networks learned the intended algorithm.The evaluated languages are finite in practice but share the structure of infinite languages, enabling out-of-distribution length tests.
  • Evaluation and interpretation: Slight accuracy degradation with increasing test length can result from accumulated numerical inaccuracies in neural state transitions or memory updates.The issue arises when finite-state machines and memory dynamics are implemented with SGD-trained neural networks.
  • Architectural limits: RNNs, LSTMs, and Transformers are limited in their ability to generalize to longer inputs.This limitation contrasts with their ability to learn complex patterns for fixed-size inputs or context windows.
  • Architectural limits: Transformers can learn complex structured patterns but cannot overcome the limitation of lacking extendable memory in these evaluations.The memory limitation becomes apparent when models are tested on longer sequences.
  • Scaling implications: Even substantially more training data and a larger Transformer may be insufficient for climbing the Chomsky hierarchy.This is presented as a possible hard limit for scaling laws within the study’s setting.

7 CONCLUSION

The paper uses computation theory to study algorithmic sequence generalization and finds a hierarchy of model capabilities across the investigated tasks. External stack or tape memory enables models to reach higher levels of the Chomsky hierarchy.

  • Conclusion: The experiments demonstrate a model hierarchy across tasks representative of different Chomsky-hierarchy levels.The hierarchy concerns the architectures’ empirical ability to generalize on the investigated algorithmic sequence-prediction tasks.
  • Conclusion: LSTMs and Transformers cannot solve string duplication when tested on sequences significantly longer than those seen during training.The paper characterizes string duplication as a seemingly simple task despite this failure under length extrapolation.
  • Conclusion: Models with external memory structures such as stacks or finite tapes can climb the Chomsky hierarchy.The authors identify structured external memory as a promising direction for architecture design.

8 ETHICS STATEMENT & LIMITATIONS

The paper frames sequence generalization through formal-language complexity and evaluates deterministic transduction with several neural and memory-augmented architectures. Its conclusions are limited by finite test lengths, the exact training setting, and known difficulties in autoregressive evaluation.

  • Limitations: The claims are limited to the empirical study and its precise training protocol, with no guarantee about arbitrary-length generalization or alternative weight configurations.The evaluations use a maximum test length and do not extract the automata implemented by the networks.
  • Evaluation limitations: Autoregressive token probabilities can make unseen-length generalization impossible when the correct probabilities depend on the training strings’ length distribution.The paper gives palindromes of lengths 2 and 3 as an example of conflicting next-token distributions.
  • Evaluation limitations: Predicting sets of possible next tokens avoids length-dependent distributions but is incompatible with standard sequence prediction and less relevant to the wider machine learning community.This motivates the deterministic transduction formulation used by the paper.
  • Scope and task framing: The approach uses language transduction, mapping each input word to an output word through a deterministic function.Only prefixes with a single possible continuation are considered, avoiding the length-dependent probability conflict of autoregressive generation.
  • Architectures: The experiments use RNN, LSTM, Transformer, Stack-RNN, Tape-RNN, and related memory-augmented architectures.The implementation includes differentiable stacks or tapes for selected models and manually enlarges memory sizes for longer tests.

A.3 TASKS

The task suite defines sequence-to-sequence mappings across regular, deterministic context-free, and context-sensitive problems, with varying memory and dependency requirements.

  • Task formulation: The benchmark maps input sequences x ∈ L_I to target sequences y ∈ L_O, using appended empty tokens so models consume the full input before producing outputs.Tasks include both sequence outputs and single-token outputs.
  • Regular tasks: Regular tasks include parity, modular arithmetic, and cycle navigation, each solvable with a finite-state machine.These tasks require only a finite number of states, such as two or five.
  • Context-free tasks: Deterministic context-free tasks include bracketed modular arithmetic, reversal, equation solving, and stack manipulation, which require stack-based processing.Reverse String cannot be solved by a finite-state machine because its possible outputs are unbounded.
  • Context-sensitive tasks: Context-sensitive tasks include binary arithmetic, duplication, missing-duplicate recovery, interleaving, and sorting, involving cross-serial dependencies or multiple counters.Binary Addition and Binary Multiplication are classified as context-sensitive because their operands are presented sequentially.
  • Resource boundary: The NDStack-RNN requires space proportional to (l + m)^3, reaching 33.5Gb for input and output lengths of 40 with batch size 128.The resulting memory demand forces the batch size down to 16 for this architecture.

B.1 MAIN RESULT

Across the benchmark, model performance generally follows the computational hierarchy: regular tasks are broadly solvable, while performance declines on harder tasks and varies by architecture.

  • Main result: All networks except Transformers solve all regular tasks perfectly for every random seed.Only a few tasks above regular achieve average scores of at least 90%.
  • Main result: Tape-RNN achieves substantially better average scores on context-sensitive tasks than the other architectures, but still fails on some tasks.The authors identify the limited action set and difficult action trajectories as a possible explanation.
  • Evaluation metric: The results are reported as mean and standard deviation of average test accuracy across architectures and tasks.Table B.1 summarizes the main experiment using scores averaged over test accuracies.
  • Evaluation nuance: Some models fail to achieve perfect accuracy even within the training range on Compute Sqrt.Evaluation samples from a distribution, so unseen sequences can occur within the nominal training range.

B.2 PHASE TRANSITION UNDER INCREASING TRAINING RANGES

Increasing the training range can trigger a phase transition in length generalization, while internal state analysis distinguishes stack use across tasks.

  • Phase transition: Stack-RNNs trained only on Reverse String sequences shorter than 10 fail to learn the data-generating algorithm and do not generalize to longer sequences.For training ranges N < 10, the models memorize the training distribution.
  • Stack usage: On Parity Check, the Stack-RNN does not use its stack and instead exhibits the state structure of a classical RNN.Its states depend on the last result and last input token.
  • Stack usage: On Reverse String, the Stack-RNN uses the stack, while PCA shows states clustered according to the last input token.This contrasts with the stack-ignoring behavior observed on Parity Check.

B.3.1 STACK-RNN PROGRAM ANALYSIS

The Stack-RNN adapts its memory behavior to task structure: it ignores the stack for Parity Check but uses it for Reverse String.

  • Parity Check: On Parity Check, the Stack-RNN applies only NO-OP and POP actions on an unseen sequence of length 100.Its PCA state representation matches that of a simple RNN.
  • Parity Check: The Stack-RNN’s Parity Check states depend only on the last result and last input token.This provides the same state structure as a classical RNN for the regular task.

B.3.2 TRANSFORMER PROGRAM ANALYSIS

The Transformer achieves non-trivial but incomplete generalization on Cycle Navigation (R) by learning token-counting computations through attention. Its frequency-based counting mechanism explains why performance degrades on longer sequences, while broader experiments show that scaling alone does not reliably remove such limitations.

  • Experimental setup: 61.9% with baseline 20% is the Transformer's score on Cycle Navigation (R), below the paper's 90% threshold for solving the task.The score is accuracy averaged over test lengths and maximized over seeds and other hyperparameters.
  • Learned algorithm: The first layer matches the final empty token with tokens 0 and 2, separating token representations for subsequent computation.The task counts 0s and 1s and performs subtraction modulo 5.
  • Learned algorithm: Constant attention weights aggregate token values proportionally to their occurrence counts, enabling the linear layer to compute each token's occurrence.The first-layer activation visualization supports this token-counting interpretation.
  • Failure mode for long sequences: Softmax normalization produces frequencies rather than true counts, so the learned representation becomes less separable as sequence length increases.This explains reasonable but imperfect generalization to longer sequences.
  • Scaling laws and limitations: Under standard training conditions, architectural extensions such as stacks or tapes can overcome systematic limitations that more data, training, or parameters do not overcome.The authors qualify that excessive training, tuning, or delayed grokking cannot be ruled out.
  • Scaling laws and limitations: 1,000,000 and 10,000,000 training steps, together with 5 to 25 layers, generally do not increase the Transformer's score.The scaling experiment maximized accuracy over 10 seeds and 3 learning rates.
Loading 2207.02098v3…