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

Introduction: The Dilemma of Evaluating Compositional Generalization

Compositional generalization is an important form of out-of-distribution generalization, referring to whether a model, having seen certain module combinations during training (such as sorting, filtering, and other functions), can generalize to unseen combinations at test time. Although there has been extensive empirical research on compositional generalization in Transformers, the conclusions often contradict one another—because evaluations tend to rely on limited and ad-hoc training-test splits. A systematic evaluation reveals that two key properties of the training-test distribution strongly influence performance: composition equivalence and module coverage.

Compositional generalization is the ability to measure whether a model can combine previously learned simple functions or modules in new ways and correctly execute unseen combinations. It is closely related to out-of-distribution generalization but emphasizes reorganization at the structural level: the model must not only cope with input distribution shifts but also handle changes in how modules are combined. In tasks such as program synthesis, semantic parsing, and instruction following, compositional generalization is regarded as a key indicator of whether a model truly understands language or code structure. However, because the composition space is enormous, researchers can usually only sample a limited set of combinations to construct training-test splits. Differences in how the splits are made directly lead to differences in evaluation conclusions, which is one of the root causes of the difficulty in reproducing and comparing empirical results in this field.

Composition Equivalence: The Main Source of Inflated Performance

The study finds that the seemingly decent performance of direct models (trained only on final outputs) mainly comes from exploiting composition equivalence—that is, different module sequences reduce to the same end-to-end function. When benchmarks eliminate these equivalences, performance drops significantly, indicating that such models cannot generalize to new end-to-end functions produced by known module combinations. In other words, the model may simply be memorizing shortcuts in the input-output mapping rather than truly learning composition rules.

This finding has direct implications for benchmark design: benchmarks that contain composition equivalence will significantly overestimate the generalization ability of direct models.

Composition equivalence refers to the phenomenon in which different module sequences produce the same function in end-to-end semantics. For example, "filter then sort" and "sort then filter" may yield the same output under certain data distributions, or two different function compositions may happen to reduce to the same mapping. When such equivalence exists between the training set and the test set, a model may perform well on the test set by memorizing input-output mappings even if it has not truly learned composition rules. This "shortcut" inflates benchmark scores and masks the model's failure on genuinely unseen combinations. Eliminating composition equivalence means that each end-to-end function in the test set cannot be directly obtained by equivalence from existing combinations in the training set, thereby testing the model's compositional ability more rigorously.

Module Coverage: Performance Declines Monotonically with Shift

In addition to equivalence, module coverage is equally critical. When the context in which modules appear shifts between training and testing (i.e., module coverage shift increases), performance declines monotonically, and this effect applies to both direct models and step-by-step models (trained on intermediate and final outputs). This means that even if a model has learned individual modules, its performance deteriorates when these modules are combined in new contexts.

More seriously, if a benchmark contains both module coverage violations and composition equivalence, it exacerbates shortcut learning—the model tends to exploit surface patterns rather than truly understanding compositional structure.

Module coverage measures the contextual diversity in which each module appears in the training set. If a module appears only in a few fixed contexts during training but is required to combine with other modules in entirely new contexts at test time, the model may fail to invoke that module correctly. A larger module coverage shift means a greater difference between test combinations and training combinations in terms of module co-occurrence patterns. Research shows that this shift monotonically degrades performance, and this holds for both direct models and step-by-step models. Although step-by-step models are trained on intermediate outputs, providing denser supervision signals, they still cannot fully offset the negative impact of coverage shift. Therefore, benchmark design needs to explicitly control the distribution of module coverage to avoid test sets deviating excessively from the contexts in which modules appear in the training set.

Implications for Benchmark Design

The above findings impose clear requirements on the design of compositional generalization benchmarks:

• Avoid test sets that contain composition equivalence, otherwise the generalization ability of direct models will be overestimated;
• Control module coverage shift to more realistically measure the model's adaptability to unseen combinations;
• Consider both factors simultaneously to prevent shortcut learning from being masked.

As a case study, the authors demonstrate the impact of composition equivalence on the generalization performance of the pretrained model Llama3-8B in code output prediction tasks on the coding benchmark LiveCodeBench. This shows that even for large pretrained models, compositional generalization evaluation can be disturbed by equivalence.

Conclusion

Evaluating compositional generalization is not simply a matter of training-test splitting. Composition equivalence and module coverage are two core factors affecting performance, and ignoring them can lead to incorrect judgments of model capabilities. Future benchmark design needs to control these variables more systematically in order to drive the development of models that truly possess compositional generalization ability.

One-line Summary

Composition equivalence and module coverage are the two key factors that distort compositional generalization evaluations.

Paragraph Summary

The article systematically evaluates the reasons behind contradictory conclusions in Transformer compositional generalization research, pointing out that two properties of the training-test distribution—composition equivalence and module coverage—strongly influence performance. Composition equivalence allows direct models to obtain inflated scores through memorization shortcuts, and performance drops significantly when it is eliminated; increasing module coverage shift causes monotonic performance decline for both direct and step-by-step models. If a benchmark contains both factors, it exacerbates shortcut learning. Using Llama3-8B's code prediction on LiveCodeBench as an example, the authors confirm the interference of equivalence in evaluating pretrained models. Finally, they propose that benchmark design should avoid composition equivalence, control module coverage shift, and consider both factors simultaneously to promote the development of models with genuine compositional generalization ability.