Do transformers actually learn systematic compositional reasoning?
Explores whether transformers solve compositional tasks through genuine systematic reasoning or by pattern-matching against training data. This matters because it determines whether scaling alone can achieve robust generalization.
"Faith and Fate: Limits of Transformers on Compositionality" (Dziri et al., 2023) provides the clearest empirical decomposition of how transformers actually handle compositional tasks — and why they fail.
The test bed is three representative tasks: multi-digit multiplication, logic grid puzzles (Einstein's puzzle), and a classic dynamic programming problem. Each is formulated as a computation graph with measurable complexity. The results are devastating for systematic reasoning claims: training on task-specific data leads to near-perfect performance on in-distribution instances at low compositional complexity, but "fails drastically on instances outside of this region."
The mechanism: transformers solve compositional tasks by reducing multi-step reasoning into linearized path matching. When a test problem's computation subgraph was seen during training (or closely resembles one), the model succeeds. When the composition is novel — requiring the model to apply computational rules to unseen combinations — it fails. This is shortcut learning: "may yield fast correct answers when similar compositional patterns are available during training but does not allow for robust generalization to uncommon or complex examples."
The error analysis is particularly revealing. While models can memorize single-step operations, they fail to compose them into correct reasoning paths. The failure is not random — it is systematic, suggesting "predictions based on shallow, rote learning rather than a deep, holistic task understanding." Error propagation makes this worse: errors in early stages compound in subsequent steps, creating an inherent ceiling on complex compositional tasks.
This provides the task-specific mechanism for what Do foundation models learn world models or task-specific shortcuts? describes at a higher level. The heuristic IS linearized subgraph matching — and it works well enough within the training distribution to create the illusion of systematic reasoning. Since Can neural networks learn compositional skills without symbolic mechanisms?, the Faith and Fate finding adds the critical qualifier: scaling helps only insofar as it increases training coverage of computation subgraphs. Novel compositions remain unsolved.
The implication for chain-of-thought: since Does logical validity actually drive chain-of-thought gains?, CoT may work not because it enables systematic reasoning but because it decomposes problems into subgraphs the model has already seen. CoT as subgraph decomposition rather than logical inference.
Inquiring lines that read this note 81
This note is a source for these research framings, grouped by the broader line of inquiry each explores. Scan the bold lines of inquiry; follow any specific question forward.
What structural biases does transformer attention create in language model outputs?- What is selective resonance and why do transformers not perform it?
- Why do transformer attention patterns show positional and sequential bias across tasks?
- Do transformer architectures structurally bias models toward short-term optimization?
- How do transformers perform multi-hop reasoning across distant training documents?
- Do transformers learn generalizable algorithms or instance-based patterns?
- How does error propagation limit transformer performance on complex tasks?
- Can symbolic mechanisms improve transformer compositional abilities?
- Can explicit stack mechanisms extend what formal languages transformers can learn?
- How does circuit complexity limit which grammatical structures transformers can acquire?
- Can neural networks implement genuine algorithms or only statistical pattern matching?
- Why do standard transformers fail on problems requiring serial algorithmic reasoning?
- Could graph neural networks fundamentally outperform transformers on structured reasoning?
- What hidden computations happen inside transformer layers during reasoning?
- What formal language complexity level matches transformer computational limits best?
- How does explicit stack tracking solve the composition sub-problem in binding?
- Why do standard transformers fail to encode recursive structure in their hidden states?
- Can transformers reason beyond fixed architectural depth limits?
- Can bounded-depth transformers solve inherently sequential problems?
- What limits the effectiveness of formal language pretraining on transformer architectures?
- What data properties enable transformers to learn sequential decision-making in context?
- Can energy-based transformers achieve deep reasoning without supervision?
- Why does looping computation outperform adding more transformer layers?
- Can recurrent transformers learn genuinely new computations beyond inference stages?
- Why does reapplying the same transformer block work better than computing new layers?
- Can looping enable reasoning capabilities that fixed-depth transformers fundamentally cannot achieve?
- Can recurrent transformers track state more efficiently than feedforward models?
- How stable are the fixed points in recurrent transformer blocks?
- Can recurrent blocks learn genuinely novel computation beyond repetition?
- Why does explicit chain-of-thought work as a workaround for feedforward transformers?
- Can latent recurrence achieve the depth that standard transformers cannot?
- Can transformers abstract relational structure without explicit symbolic machinery?
- How does program synthesis relate to transformers computing general algorithms?
- Can common-mode rejection be applied to other transformer operations?
- Can neural networks represent symbolic structures without explicit mechanisms?
- What makes linear decodability a reliable signal of compositionality?
- Can fractured representations explain why models fail at systematic generalization?
- Can representation analysis methods detect complex features models compute with?
- Why do text-to-image models fail at composing multiple concepts together?
- Does scaling model size solve compositional generalization problems?
- Does compositional generalization emerge suddenly or improve smoothly with scale?
- Why does comparison reasoning generalize better than composition reasoning?
- Does scaling data automatically produce compositional reasoning or just better feature encoding?
- What test distinguishes genuine compositionality from fractured feature presence?
- What makes recursive structure different from other forms of compositional generalization?
- Can scaling alone create compositional generalization without explicit binding mechanisms?
- Can granular function calling tasks learn composition from graph-sampled data?
- Can learned verifiers over token similarity replace dense compositional training?
- What role does query-level exposure play in enabling compositional generalization?
- Why does scaling data and model size improve compositional generalization?
- Does sparsity enforce compositional structure or merely amplify existing modularity?
- Why does gradient descent discover compositional structure without explicit pressure?
- What architectural alternatives can capture compositional structure beyond pooled cosine?
- What makes recurrent depth enable compositional generalization across tasks?
- How does scaling and training data enable compositional behavior without symbolic mechanisms?
- Where do neural networks still fail at compositional generalization despite scaling?
- Can recursion alone drive generalization better than model scale?
- Why does compositional reasoning fail to explain cross-domain transfer?
- How does evidence retrieval affect compositional reasoning in language models?
- Why do energy-based models generalize better on out-of-distribution data than standard transformers?
- Why do task-specific heuristics fail at generalizing to sparse data regions?
- How do transformers generate harder solutions when mostly trained on easier problems?
- Can neural networks learn that A implies B in reverse?
- What explains the contextual variability of knowledge in transformers?
- Can long-context models handle compositional reasoning requiring structured logic?
- Why do long-context language models struggle with compositional reasoning tasks?
- How do neural networks decompose complex tasks into modular subnetworks?
- Does training on granular tasks beat training on the full function calling problem?
- How do gradients flowing through both branches simultaneously reshape each component's role?
- How do transformers stitch together learned behaviors when adapting to new tasks?
- How do neural networks decompose tasks into modular subnetworks that transfer?
- Why is a combinatorial framework better than family resemblance classification?
- What makes modernized N-gram embeddings composable with transformer architectures?
Related concepts in this collection 4
This note in its neighbourhood — explore the map, then jump to a related concept in the list below.
Click a node to walk · click center to open · click Open in graph to see this note in the full knowledge graph
-
Do foundation models learn world models or task-specific shortcuts?
When transformer models predict sequences accurately, are they building genuine world models that capture underlying physics and logic? Or are they exploiting narrow patterns that fail under distribution shift?
subgraph matching is the specific heuristic for compositional tasks
-
Can neural networks learn compositional skills without symbolic mechanisms?
Do neural networks need explicit symbolic architecture to compose learned concepts, or can scaling alone enable compositional generalization? This asks whether compositionality is an architectural feature or an emergent property of scale.
scaling helps by covering more subgraphs, not by creating systematic reasoning
-
Why do neural networks fail at compositional generalization?
Exploring whether the binding problem from neuroscience explains neural networks' inability to systematically generalize. The binding problem has three aspects—segregation, representation, and composition—each creating distinct failure modes in how networks handle structured information.
theoretical explanation for why linearized matching fails on novel compositions
-
Does logical validity actually drive chain-of-thought gains?
What if invalid reasoning in CoT exemplars still improves performance? Testing whether logical correctness or structural format is the real driver of CoT's effectiveness.
CoT may succeed via subgraph decomposition, not logical validity
Related papers in this collection 8
Papers most semantically related to this note, ranked by cosine similarity in the embedding space.
- Faith and Fate: Limits of Transformers on Compositionality
- Scaling can lead to compositional generalization
- Compositional Reasoning with Transformers, RNNs, and Chain of Thought
- Grokked Transformers are Implicit Reasoners: A Mechanistic Journey to the Edge of Generalization
- Break It Down: Evidence for Structural Compositionality in Neural Networks
- Loop, Think, & Generalize: Implicit Reasoning in Recurrent-Depth Transformers
- Pushing the Limits of Rule Reasoning in Transformers through Natural Language Satisfiability
- How do Transformers Learn Implicit Reasoning?
Original note title
compositional reasoning in transformers reduces to linearized subgraph matching — success depends on training exposure to similar computation subgraphs not systematic problem-solving