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.
Figures & tables
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).
Figure 2: Within- k evaluation: Direct models fail completely (0% accuracy) on uniform bijections without identity tokens (Figure (d)), while step-by-step models maintain near-perfect performance across all conditions. We observe that including identity tokens or diverse function types seems crucial for the generalization performance of direct models.
Figure 3: Cross- k evaluation: For the diverse benchmark (a–b), direct models perform well near training k as equivalences persist across nearby k values. Direct models fail on the uniform benchmark (c–d) regardless of identity tokens, since identity-based equivalences in the uniform benchmark are k -specific. Step-by-step models are more robust but still exhibit significant variability.
Figure 4: Isolating the effect of composition equivalence in the diverse benchmark ( k=6 ): (a) Generalization performance increases with the degree of shared composition equivalence classes between train and test. (b) The direct model generalizes primarily to test sequences that share equivalence classes and fails on classes exhibiting novel end-to-end behavior.
Threshold
Accuracy: 0% shared
Accuracy: 100% shared
0.01
0.04
0.70
0.25
0.08
0.73
0.50
0.28
0.84
0.75
0.68
0.88
0.95
0.84
0.91
Table 1: Sensitivity of direct-model accuracy to the equivalence threshold: We report accuracy on train/test splits with 0% and 100% shared composition equivalences, where equivalence classes are learned at different thresholds. At low thresholds, weak equivalences are captured, so the 0% shared split contains no equivalences of any strength and generalization is poor. At high thresholds, some equivalences go undetected and remain in the 0% shared split, which inflates generalization performance.
Figure 5: Effect of position-wise distribution shift: As the position-wise KL divergence increases, the compositional generalization performance of both direct and step-by-step models decreases.
Figure 6: (a) Code output prediction performance of Llama3-8b on LiveCodeBench benchmark: We show the accuracy of the base model (No LoRA) and three LoRA fine-tuned models on splits with varying ratios of shared equivalence classes (defined by the same function names) (held out h =0, 0.5, 1.0). As splits share composition equivalences, accuracy improves substantially. (b) Performance grouped by equivalence classes: We observe that performance on most functions only improves when equivalences are leaked into the fine-tuning set.
Appendix figures & tables21 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 7: Uniform benchmark (without identity), N_heads = 6, N_layers = 3, Direct (Relative) : We observe that the models learn to predict the outputs of training compositions for both K=2 and for K=6, while the test accuracy on unseen compositions remains 0% throughout. We report two metrics: (1) sharp accuracy , where a prediction scores 1.0 only if the entire output sequence is correct and 0.0 otherwise; and (2) mean token accuracy , average accuracy of predictions in the output sequence, with both metrics averaged across compositions from each split. For reference, 100 epochs correspond to roughly 20k iterations (batch size 512, 100k training samples, 195 iterations per epoch).
Figure 8: Diverse benchmark, N_heads = 6, N_layers = 3, Direct (Relative) : We observe non-trivial compositional generalization, as the models perform well on training and validation compositions, the test performance also increases. We observe better generalization for K=6 than for K=2 due to more training diversity and shared equivalences.
Figure 9: Generalization performance of bigger transformer architecture : We observe that the performance of the bigger architecture shows similar performance trends as seen for the smaller architecture (N_heads = 6, N_layers = 3) in Figures 2 (b) and (d).
Num. strings
0%
20%
50%
60%
70%
100%
10
1.8
4.2
6.4
12.7
12.3
83.4
100
1.1
3.8
8.7
17.4
41.1
75.0
1,000
0.4
6.2
10.0
22.0
44.9
78.2
10,000
1.2
7.9
11.8
20.9
48.0
78.6
Appendix
Table 2: Sensitivity of accuracy to the number of strings N used to estimate composition equivalence. Each column reports results for a given percentage of shared composition equivalences between train and test splits. Accuracy increases with shared equivalence at every value of N .
Figure 10: Equivalence class necessity and training requirements: (a) Generalization performance to unseen sequences is strongly correlated with the degree of shared composition equivalence classes between train and test. (b) Models need to see at least 4–5 composition equivalences (per class) in training to generalize to the corresponding test equivalences.
Figure 11: Visualization of learned equivalence classes for the diverse benchmark (K=6): We show two equivalence classes (out of a total of 14 classes). First, we can note that the degree of equivalence varies significantly within an equivalence class. The test sequences are marked in red, and the training sequences are marked in green, indicating whether an equivalence class is shared. We observe that accuracy is significantly higher for compositions in the shared equivalence class and near zero for those in the non-shared equivalence class.
Figure 12: Size distribution of learned equivalence classes( K = 6)
Figure 13: Leaking test equivalence classes without swapping ( K = 6): (a) Generalization performance to unseen sequences is strongly correlated with the number of shared composition equivalence classes between train and test. (b) The mean accuracy of shared equivalence classes is significantly higher than that of non-shared equivalence classes.
Figure 14: Composition equivalence encourages shortcuts in step-by-step models: We observe that composition equivalences in the diverse benchmark cause discrepancies between final output accuracy and full output (intermediate and final output) accuracy for both within-k evaluation and cross-k evaluation. Final accuracy > full accuracy implies the model is learning shortcuts to reach the final answer. If we eliminate composition equivalences, the performance difference is zero between full and final outputs (see Figures 15 (a), 15 (b))
Figure 15: Eliminating composition equivalences removes shortcut learning in step-by-step models : We observe that the lack of compositional equivalence in the uniform benchmark removes shortcut-learning behavior in step-by-step models. This is shown by the exact same step-by-step accuracy, and the final accuracy is the same for both within-k evaluation ( k = 6) and cross-k evaluation (train- k = 6).
Figure 16: Gemma-1B visualization of per-class distribution for 100% sharing: We observe that most of the equivalence classes are shared and the model has overall high accuracy over test sequences in the shared equivalence classes.
Figure 17: Gemma-1B visualization of test accuracy for the split with no shared equivalences: We observe that none of the equivalence classes are shared, and the model has poor accuracy over test sequences in those classes.
Figure 18: Position-wise and pair-wise KL divergence in Cross- k evaluation
Figure 19: Effect of pairwise-wise distribution shift: (a) As the pairwise-wise KL divergence increases, the compositional generalization performance of both direct and step-by-step models decreases in the diverse benchmark. (b) For the uniform benchmark, the effect of divergence is primarily observed at the extreme right end for support violations.
Figure 20: Combined effect of position-wise shift and reduced diversity: Shows (1- accuracyKL ) to demonstrate accuracy degradation as in Figure 5 , revealing combined effects of coverage shift and reduced compositional diversity due to biased sampling. Here, accuracyKL is the performance with biased sampling.
Figure 21: Isolating position-wise shift by controlling diversity: Shows accuracyzero_shift−accuracyKL , where accuracyzero_shift and accuracyKL are accuracies under random and biased sampling with n unique compositions at each Dpos , respectively. For the diverse benchmark, position-wise shift alone has a reduced but still significant effect compared to Figure 20 , indicating that both coverage shift and reduced diversity contribute to degradation. For the uniform benchmark, the negligible difference confirms that degradation is driven primarily by coverage shift alone.
Figure 22: Effect of number of unique training sequential compositions (randomly sampled, K=6): : We observe that (a) step-by-step models with relative global embedding need fewer training compositions to generalize faster than absolute embedding models, and (b) For the diverse benchmark, as compared to direct models, step-by-step models need fewer unique training compositions due to extra information available using intermediate outputs.
Figure 23: Effect of number of samples per composition (uniform benchmark, direct model): . Number of training compositions N=24 for K=2 , and N=576 for K=6 . We vary the number of input-output samples per training composition in this experiment. We observe that with a small number of training samples, the train/val gap is large, and the model struggles to generalize to training compositions with novel inputs. The train-val gap reduces as the number of samples increases. Test accuracies remain 0%, as expected.
Figure 24: Effect of number of samples per composition (uniform benchmark, step-by-step model): We observe that step-by-step models are more sample efficient than direct models due to access to intermediate outputs providing extra information.
Figure 25: Effect of number of samples per composition (diverse benchmark, direct model): For the diverse benchmark, direct models are less sample efficient than the uniform benchmark to generalize on the validation set, especially for K= 2 . We observe significant compositional generalization behavior, as seen in Figure 2(b) for large samples, especially for K= 6 .
Figure 26: Effect of number of samples per composition (diverse benchmark, step-by-step model): Step-by-step models are more sample efficient than direct models, and a similar difference between uniform and diverse benchmarks for K= 2 is observed as for direct models.
Large language models are able to compose skills in order to perform complex tasks, many of which might not have been seen during training. The details of how exactly this composition occurs remain elusive. In this paper, we study a mechanism for compositional generalization in transformers by considering a simple controlled setting involving variable assignment and modular addition. By partitioning our training data into disjoint sets, we observe that small transformers are able to generalize to previously unseen combinations of variables and numbers. Our mechanistic analysis shows that the same ``modular addition'' MLP module is used whether the inputs are given directly or indirectly through a separate variable assignment mechanism. We also analyze the training dynamics from an empirical lens, which reveals three phases of learning: first, modular addition is learned, then the structure required for variable assignment, and finally a refinement phase where the model generalizes to some hard sequences not seen in training. Finally, we provide a theoretical framework to explain how compositionality emerges from training dynamics. These results suggest that compositional generalization can be a natural consequence of the compositionality of internal mechanisms in~transformers.
Compositional generalization remains a persistent limitation of transformer language models: even when a model learns to combine known facts correctly in-distribution (ID), the same compositional mechanism may fail when applied to out-of-distribution (OOD) knowledge. We investigate this compositionality gap in a controlled two-hop reasoning setting using a GPT-2-like transformer model trained from scratch. Building on prior work identifying a circuit associated with compositional generalization, we test whether the failure of OOD transfer is related to how atomic knowledge is structurally exposed during training. We modify the training distribution by presenting both ID and OOD atomic facts in a format positionally aligned with the second-hop retrieval step of the learned compositional circuit, without modifying the model architecture or adding OOD compositional supervision. Under this intervention, the model successfully transfers the learned ID compositional behaviour to held-out OOD atomic facts, closing the observed compositionality gap in the controlled setting. Our results provide evidence that the observed compositionality gap is not a fundamental architecture limitation and that it can be overcome through mechanistically informed training distribution design.
Davide Venuto, Leonardo Venuto
Technical University of Denmark (DTU), Lyngby, Denmark · Independent Researcher, Heidelberg, Germany
Compositional generalisation has been divided into lexical and structural generalisation. Previous work has found that structural generalisation is harder than lexical for Transformers. We propose that this difference is not inherent to Transformers, but due to the high diversity of lexical types and low diversity of structural types in the specific datasets of these previous works. By type diversity we mean the number of different constructors of that type, instead of, for example, the specific word combinations that might populate the structure. To test this, we vary the amounts of type diversity of lexical and structural types in previously published datasets. We create linguistically diverse variants of the COGS and SLOG datasets using Grammatical Framework. We find that type diversity correlates with compositional generalisation equally in lexical and structural test cases, supporting our hypothesis. We note a contradiction with the proposition in previous work that compound divergence explains the difficulty in compositional generalisation tasks. We further investigate the effects of other dataset properties on compositional generalisation, such as the diversity of types other than the novel test structure, and surface properties of the logical semantics format.