Why Neural Networks Fail to Generalize Structural Recursion

192 concepts112 papers1 proposal

Human language and logic are fundamentally productive: using a finite set of rules, we can generate and understand infinitely nested structures. Whether parsing a complex sentence with center-embedded clauses ("The rat that the cat chased died") or evaluating nested mathematical operations, our cognitive architecture handles recursion by applying abstract rules regardless of depth.

Early connectionist critiques by Paul Smolensky in Principles for an Integrated Connectionist/Symbolic Theory of Higher Cognition ; CU-CS-600-92 and Jordan B. Pollack in Implications of Recursive Distributed Representations pointed out that distributed neural networks struggle with this exact property of systematic productivity. Decades later, despite the paradigm shifts toward Transformers and Large Language Models, this structural ceiling remains a persistent bottleneck. When modern models encounter recursive depth just one or two levels beyond their training data, their performance frequently collapses to near-chance levels.

Disentangling Depth from Length

A common misconception is that structural generalization failure is simply a symptom of sequence length. It is tempting to assume that as a sentence or program grows longer, it merely exhausts the model's context window or attention capacity. However, systematic benchmarks show that sequence length and structural depth are orthogonal axes of difficulty.

In COGS: A Compositional Generalization Challenge Based on Semantic Interpretation, Najoung Kim et al. demonstrated that standard sequence-to-sequence models fail to extrapolate to deeper recursive structures even when the total sequence length falls well within the distribution observed during training. The models master the base grammatical rules perfectly at shallow depths but cannot apply them to deeper hierarchies.

To isolate this phenomenon, Bingzhi Li introduced the SLOG benchmark in SLOG: A Structural Generalization Benchmark for Semantic Parsing. The author found that vanilla and pretrained Transformers hit a hard performance ceiling driven strictly by nesting depth. Models achieve near-perfect accuracy on shallow patterns but drop to 0% accuracy when faced with highly nested center-embedded clauses. This indicates that instead of learning abstract, generalized hierarchical rules, neural networks rely on fixed-depth surface patterns.

Why Flat Representations Plateau

To understand why these architectures fail to extrapolate depth, we must look at how they process information internally.

The Autoregressive Pass Bottleneck

In standard autoregressive generation, a model must output a sequence linearly, token by token. Yuanhe Tian et al. observed in Large Language Models Are No Longer Shallow Parsers that while human-annotated syntactic structures naturally deepen as sentences grow longer, the structural depth of outputs from large language models plateaus. Because the model generates text in a single flat pass, it struggles to maintain recursive consistency across deep hierarchical trees without an explicit mechanism to pause and compute sub-trees.

The Lack of Explicit Memory Stacks

To parse infinite context-free grammars or nested recursion, a system mathematically requires a mechanism equivalent to a pushdown automaton—an explicit stack memory. Without it, recurrent models must compress hierarchical states into fixed-width vectors. As Michiel Hermans et al. noted in Training and Analysing Deep Recurrent Neural Networks, deep recurrent networks lose information as syntactic trees deepen, failing to maintain long-range nested dependencies when they are infrequent in the training distribution.

Branching vs. Linear Recursion

The problem compounds when moving from linear sequences to branching structures. Marek Suppa et al. introduced FractalBench in FractalBench: Diagnosing Visual-Mathematical Reasoning Through Recursive Program Synthesis to test how models handle exponentially growing computation graphs. They discovered that while models can occasionally manage sequential geometric transformations, they fail catastrophically at representing branching recursion, often defaulting back to simpler iterative loops or single-branch logic.

The Limits of Scaling and Data Augmentation

If the underlying bias of standard architectures is flat, can we resolve it by making models deeper or augmenting the training data? Evidence suggests these approaches only mask the problem rather than solving it.

Jackson Petty investigated the impact of Transformer depth on compositional generalization in The Impact of Depth on Compositional Generalization in Transformer Language Models, decoupling layer count from parameter size. While increasing depth initially helps models combine familiar concepts, this benefit saturates remarkably early—often after just 4 to 6 layers. Crucially, depth scaling fails to bridge the gap between lexical recombination and true structural generalization.

Data augmentation strategies also hit a wall when encountering self-nesting. Ekin Akyürek et al. showed in LexSym: Compositionality as Lexical Symmetry that while symmetry-based data augmentation successfully resolves flat compositional combinations, it does not inherently enable models to generalize across varying depths of self-nested recursive structures.

Ultimately, the evidence across diverse domains—spanning natural language syntax (Konstantinos Kogkalidis et al. in Discontinuous Constituency and BERT: A Case Study of Dutch), logical reasoning (Alessandra Russo et al. in DeepLogic: Towards End-to-End Differentiable Logical Reasoning), and program translation (Xinyun Chen et al. in Tree-to-tree Neural Networks for Program Translation)—points to a shared conclusion: current neural networks simulate hierarchical depth via bounded, shallow heuristics rather than executing true algorithmic recursion.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 118 papers
  2. Version 1 · 2026-10-04 · 138 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_recursive_generalization_5c71b344,
  title = {recursive generalization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/recursive-generalization/rdr_5c71b344c58c40a69983b80ee037b044},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_recursive_generalization_5c71b344_v2,
  title = {recursive generalization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/recursive-generalization/rdr_5c71b344c58c40a69983b80ee037b044/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake