This paper investigates why Transformers often show inconsistent results when tasked with compositional generalization—the ability to learn individual "atomic" modules (like sort or filter) and then correctly apply them in novel, unseen combinations.
TL;DR
Transformers often appear to generalize by exploiting "compositional equivalences"—different sequences of functions that happen to produce the same output—rather than learning true modular reasoning. By systematically controlling for these functional shortcuts and "module coverage" (where functions appear in a sequence), the authors show that current benchmarks significantly overestimate how well models actually understand composition.
What Problem Does This Paper Address?
Compositional reasoning is fundamental to human intelligence and critical for AI tasks like coding, planning, and mathematical proof. However, research on whether Transformers can do this is a mess of contradictions: some studies show perfect generalization, while others show total failure.
The authors argue that this inconsistency stems from a lack of control over the training data. Most benchmarks define "unseen" compositions syntactically (e.g., the model hasn't seen the specific string of tokens sort -> filter). But if the model has seen filter -> sort and those two sequences are functionally identical, the model isn't generalizing to a new task—it’s just recognizing a familiar one. The paper aims to untangle these "shortcuts" from true generalization.
Methods
The researchers conducted a systematic evaluation using both small, controlled models (nanoGPT) and large-scale pre-trained models (Gemma-3-1B, Llama3-8B). They focused on sequential composition tasks, where a model receives an input and a sequence of functions to apply.
They introduced two primary metrics to analyze the train-test distribution:
- Composition Equivalence: Identifying classes of different module sequences that reduce to the same end-to-end function.
- Module Coverage: Measuring how often each atomic module appears in specific positions (e.g., first, second) or contexts (e.g., following a specific other module) during training versus testing.
They compared two training regimes:
- Direct Models: Trained only on the final output of a sequence.
- Step-by-Step Models: Trained on both intermediate and final outputs (similar to Chain-of-Thought).
Datasets
The study utilized three distinct data environments:
- Uniform Benchmark: A "control" dataset using six random bijections (one-to-one mappings). By design, no two sequences are equivalent, making it a pure test of compositional ability.
- Diverse Benchmark: A more realistic dataset of string-manipulation functions (sort, mode, filter, shift, etc.) that naturally contains many functional equivalences.
- LiveCodeBench: A real-world coding benchmark used to validate their findings on Llama3-8B, specifically looking at how "leaking" functionally equivalent code implementations into training affects test performance.
Key Insights and Ideas
- Functional vs. Syntactic Novelty: The authors argue that a test composition is only truly "out-of-distribution" if it produces a novel end-to-end mapping. If the model has seen a functionally equivalent sequence in training, it can succeed by memorizing the mapping rather than reasoning through the steps.
- The Illusion of Generalization: Direct models (those without intermediate steps) fail completely on benchmarks that eliminate functional equivalences. Their apparent success in prior literature is largely an artifact of benchmarks that inadvertently included these shortcuts.
- The Identity Padding Trap: Common evaluation practices, like padding sequences with "identity" functions to keep lengths consistent, actually introduce massive amounts of composition equivalence, leading to inflated performance scores.
- Monotonic Degradation: Generalization performance drops predictably and monotonically as the "coverage shift" increases. If a module is never seen in the first position during training, the model is highly likely to fail when that module appears first at test time.
Key Results
- Zero Generalization without Shortcuts: On the Uniform benchmark (no equivalences), direct models achieved 0% accuracy on unseen sequences, regardless of their length.
- Equivalence Predicts Success: In the Diverse benchmark, accuracy for direct models rose from near-zero to ~80% as the proportion of shared equivalence classes between train and test increased.
- Step-by-Step Robustness: Models trained on intermediate steps are significantly more robust to these shifts, but they still suffer when module coverage is poor.
- Real-World Validation: Fine-tuning Llama3-8B on LiveCodeBench confirmed that "leaking" functional equivalences into the training set (even with different function names) significantly boosts performance on "unseen" test cases, proving this isn't just a synthetic phenomenon.
Limitations and Future Work
The study primarily focuses on sequential tasks. Real-world reasoning often involves hierarchical or graph-based compositions (like nested loops or complex logic), which this paper does not address. Furthermore, in real-world datasets like LiveCodeBench, it is difficult to perfectly isolate module coverage from other factors like library usage or code style.
The authors suggest that future benchmark design must move beyond simple syntactic splits and account for functional equivalence to truly measure the reasoning capabilities of LLMs.
Summary updated