Evaluating Compositional Generalization in Transformers: The Role of Composition Equivalence and Module Coverage

Purva Pruthi, Andrew Yuan, Alexander D'Amour, David Jensen

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:

  1. Composition Equivalence: Identifying classes of different module sequences that reduce to the same end-to-end function.
  2. 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.
Figure 1: (a) A sequential composition task combines “atomic” functions (e.g., sort, mode, filter). Task-based compositional generalization is the ability to generalize to unseen sequences after training on a subset. (b) Composition equivalence: Different sequences are composition equivalent if they reduce to the same end-to-end function. For example, one equivalence class consisting of the first four sequences reduces to returning the most frequently occurring vowel in a set of strings; direct models succeed on the test sequence (mode ◦filter ◦sort) from this class but fail on the remaining two test sequences from a different composition equivalence class. (c) Module coverage: Examples of coverage failures include position-wise (e.g., function 2 never appearing in the first position, shown with dashed lines) and pair-wise (e.g., missing pair (2,1) in the training set, shown with solid lines).

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

Abstract

Compositional generalization is an important form of out-of-distribution generalization, defined as the ability to train on some combinations of modules (e.g., functions such as sort, filter) and then generalize to unseen combinations. Despite substantial empirical work evaluating compositional generalization in transformers, findings have been inconsistent because evaluations were often conducted on a limited set of train-test splits, defined in an ad hoc manner. Through a systematic evaluation, we identify two key aspects of the train-test distribution that strongly affect performance: composition equivalence and module coverage. We show that the apparent performance of direct models (trained only on final outputs) results primarily from exploiting composition equivalences, meaning different sequences of modules that reduce to identical end-to-end functions. When benchmarks eliminate these equivalences, performance drops significantly, showing their inability to generalize to compositions of known modules that produce novel end-to-end functions. We further demonstrate that performance degrades monotonically as module coverage shifts increase (when modules appear in different contexts between train and test), affecting both direct and step-by-step models (trained on intermediate and final outputs). These findings have concrete implications for benchmark design: benchmarks that include compositional equivalences can lead to significant overestimation of the generalization abilities of direct models, and benchmarks that include both module coverage violations and compositional equivalences can exacerbate shortcut learning. As a case study, we demonstrate the role of compositional equivalence on the generalization performance of the pre-trained model Llama3-8B on the code-output prediction task in the coding benchmark LiveCodeBench.
BibTeX
@misc{pruthi2026evaluating,
  author = {Purva Pruthi and Andrew Yuan and Alexander D'Amour and David Jensen},
  title = {{Evaluating Compositional Generalization in Transformers: The Role of Composition Equivalence and Module Coverage}},
  year = {2026},
  eprint = {2611.13498},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.13498},
}
Figure