Making Transformers Solve Compositional Tasks

Motivation

• Transformers show limited compositional generalization despite strong performance on many natural-language tasks.Compositional generalization requires combining learned primitives in ways not seen during training.Source: §1 · p. 1

Approach

• The study evaluates how position encodings, decoder type, weight sharing, model hyperparameters, and target-task formulation affect compositional learning biases.The empirical evaluation uses twelve datasets designed to measure compositional generalization.Source: §1 · p. 1

Contributions

• The paper examines which Transformer configurations improve compositional generalization across a diverse collection of tasks.The results are presented as a study of design choices rather than a single architectural modification.Source: §1 · p. 1
• The paper reports a COGS accuracy of 0.784 using a sequence-tagging intermediate representation, versus 0.35 for the best previously reported model (Kim and Linzen, 2020).It also reports state-of-the-art results on the productivity and systematicity splits of PCFG.Source: §1 · p. 1

2.1 Compositional Generalization

• Systematicity recombines known parts and rules in novel ways, whereas productivity extrapolates to sequences or structures longer than those seen during training.The paper also identifies substitutivity, localism, and overgeneralization, but focuses mainly on systematicity and productivity.Source: §2.1 · p. 2
• Compositional generalization is framed as out-of-distribution generalization in which models should discover domain symmetries rather than rely on training-distribution shortcuts.This connects compositionality to primitive operations and other regularities that generalize beyond observed examples.Source: §2.1 · p. 2
• Prior work reports poor compositional generalization in deep-learning models and introduced benchmarks including SCAN, PCFG, Arithmetic language, and CFQ.Liška et al. (2018) found that only about 2% of 50,000 training runs exceeded 80% compositional accuracy despite near-perfect training performance.Source: §2.1 · p. 2
• Proposed improvements include syntactic attention, pretraining, data augmentation, intermediate representations, structure annotations, and specialized architectures.Concurrent work also reported gains from relative attention and highlighted end-of-sequence detection as a challenge.Source: §2.1 · p. 2

2.2 Transformer Models

• A Transformer uses encoder and decoder stacks with attention and feed-forward sublayers, producing output tokens autoregressively from token embeddings.Position encodings provide information about token order; the paper denotes layers, embedding dimension, feed-forward dimension, and attention heads by l, d, f, and h.Source: §2.2 · pp. 2–3
• The experiments use smaller-than-original Transformer configurations because the evaluated datasets are relatively small.The original base configuration is l = 6, d = 512, f = 2048, and h = 8.Source: §2.2 · p. 3

Dataset Suite

• The benchmark suite contains twelve datasets: six algorithmic tasks and six standard compositional-generalization datasets.The algorithmic tasks mostly test productivity, while the other datasets also involve systematicity or synonymity.Source: §3 · p. 3

Algorithmic Tasks

• Addition tests summing digit sequences with up to 8 training digits and 9- or 10-digit test numbers, while AdditionNegatives adds negative inputs.Numbers are padded to length 12.Source: §3 · p. 3
• Reversing and Duplication test sequence transformations beyond training lengths, while Cartesian and Intersection test operations over symbol sequences or sets.Cartesian training uses up to 6 symbols and testing uses 7 or 8; Intersection tests set sizes 17 to 24 after training sizes 1 to 16.Source: §3 · p. 3

Standard Benchmarks

• The suite includes SCAN length and add-jump, PCFG productivity and systematicity, COGS generalization, and CFQ MCD1 splits.These datasets represent standard compositional-generalization benchmarks alongside the algorithmic tasks.Source: §3 · p. 3

Model Variations

• Figure 2 summarizes the Transformer components varied in the evaluation: position encodings, copy decoder, model size, weight sharing, and intermediate representations.The experiments systematically compare these architectural dimensions using small Transformers trained from scratch.Source: Figure 2 · p. 4

Evaluation Design

• The splits place harder or longer structures in testing so models must generalize compositionally rather than exploit shortcuts from the training distribution.Most tasks are trivial under identically distributed train and test data, where Transformers can approach 100% accuracy.Source: §3 · pp. 3–4

Position Encodings

• 0.354 average accuracy was obtained with relative position embeddings and decoder-to-encoder relative positions, versus 0.137 with absolute encodings.Relative embeddings were necessary for the benefit; relative biases alone were insufficient, and decoder-to-encoder positional information particularly helped productivity and positional tasks.Source: §4.1 · pp. 4–5

Decoder Type

• Copy decoders consistently outperformed their non-copy counterparts, with the largest benefits appearing on PCFG and COGS but not on every task.The comparison used matched models with and without the copy-decoder suffix.Source: §4.2 · p. 5

Model Size

• Model size helped PCFG but generally did not help algorithmic tasks, where larger models could overfit.Lowering the learning rate improved larger-model performance on Duplication, preventing the observed degradation.Source: §4.3 · p. 6

Weight Sharing

• Weight sharing significantly boosted compositional-generalization accuracy, including 0.982 on AdditionNegatives and PCFG scores of 0.634 and 0.828 for the large-6s model.Most weight-shared models achieved higher average accuracy than their corresponding models without sharing.Source: §4.4 · p. 6

Intermediate Representations

• 0.784 COGS accuracy was achieved with sequence tagging, exceeding the previously reported 0.35 and yielding the best reported COGS performance.The result suggests that the encoder can parse inputs correctly, while the full Transformer decoder may struggle to generate the required output sequence.Source: §4.5.1 · pp. 7–8

5 Discussion

• Algorithmic tasks generally reached close to 0.8 accuracy or higher with at least one configuration, except Cartesian product.Cartesian product remains challenging because outputs grow quadratically with input size and can be much longer than training outputs.Source: §5 · p. 8
• SC​​AN-aj showed little improvement because the models struggled to interpret a symbol seen very few times, a challenge none of the tested variations solved.The same obstacle also appeared in some COGS generalization types.Source: §5 · p. 8
• Relative position encodings, copy decoders, model size, weight sharing, and intermediate representations produced distinct compositional learning biases across tasks.Relative positions were generally beneficial, while other choices had task-dependent effects.Source: §5 · pp. 8–9
• Increasing embedding dimensions generally helped, two layers to four gave a slight benefit, and six layers hurt unless larger models used smaller learning rates.The smaller-learning-rate result came from additional preliminary experiments, while systematic exploration remained future work.Source: §5 · p. 9
• Weight sharing helped tasks with clear primitives or algorithmic structure, especially PCFG, but hurt COGS and therefore lacked general benefits.Its effect was more task-specific than the broader gains from other modifications.Source: §5 · p. 9
• Intermediate representations significantly helped when they could be defined, but their usefulness was dataset-specific.This benefit was reported as expected when an appropriate intermediate representation was available.Source: §5 · p. 9

6 Conclusions

• Average sequence-level accuracy increased from 0.137 for the baseline Transformer to up to 0.527 with design changes.Up to 0.493 accuracy was achieved without increasing the baseline model's parameter count.Source: §6 · p. 9
• The models achieved state-of-the-art results on COGS with 0.784 generalization accuracy and on two PCFG splits with accuracies of 0.634 and 0.828.These results were reported as state of the art at the time of submission.Source: §6 · p. 9
• The results identify appropriate inductive biases as a key factor in training models that generalize compositionally.The study evaluated Transformer configurations on language and algorithmic compositional-generalization benchmarks.Source: §6 · p. 9
• Future work will examine pre-training, optimizer parameters, and compositional generalization in large models on real-world tasks.These directions extend the design-space study beyond its current scope.Source: §6 · p. 9

A Implementation Details

• The experiments used a standard Transformer implementation with proposed variations added on top, running on one CPU and one Tesla V100 GPU.Parameters retained the original implementation's default values, including its learning-rate schedule.Source: A Implementation Details · p. 11
• The experiments prioritized comparing inductive biases rather than optimizing for state-of-the-art results.The authors note that the learning-rate schedule could likely have been further tuned.Source: A Implementation Details · p. 11
• Layer-normalization placement and initializer choices affected reproducibility across implementations.Matching the Keras implementation's post-sublayer normalization and initialization details was necessary to reproduce some results in Flax.Source: A Implementation Details · p. 11
• The low-level implementation details altered the model's learning bias, not merely its engineering behavior.The authors were unable to reproduce some results with different defaults until these details were matched.Source: A Implementation Details · p. 11

B Detailed Results

• Table 8 reports average sequence-level accuracy for all evaluated models, including duplicate rows for equivalent model names.The table consolidates the paper's model-level average results.Source: B Detailed Results · p. 11
• Table 9 reports each model's maximum dataset accuracy across three to ten repetitions, with repetition counts varying by dataset.Inters received ten repetitions because it exhibited more extreme results.Source: B Detailed Results · p. 11
• Inters models typically achieved either random accuracy around 0.5 or perfect accuracy of 1.0, rarely intermediate values.This pattern supports a low-probability compositional-solution interpretation and indicates that some architectures increased the chance of finding it.Source: B Detailed Results · p. 11
• Algorithmic tasks showed much larger standard deviations, with Add and Inters often producing near-zero or near-perfect accuracy.Table 10 summarizes the observed standard deviation in sequence-level accuracy.Source: B Detailed Results · p. 11

• The best overall model, large-4s, used only about 0.5 million parameters yet significantly outperformed larger models.Parameter counts vary across datasets because token vocabularies change embedding and output-layer sizes.Source: C Parameter Counts · p. 11, Table 7 · p. 11
• The paper therefore finds that increasing parameter count by itself is insufficient to improve compositional generalization.Source: C Parameter Counts · pp. 11–12
• Models with shared layer parameters outperformed their non-shared counterparts despite naturally having fewer parameters.Source: C Parameter Counts · p. 12

• 0.784 versus 0.278: the best tagging model substantially outperforms the base seq2seq model on COGS generalization.The COGS generalization set reports overall performance alongside task-specific subsets.Source: D Detailed Results in COGS · p. 12, Table 9 · p. 13
• 0.681 to 0.819: increasing model depth from 2 to 6 layers improves Depth generalization for prepositional-phrase modifiers.The result suggests that the deeper model handles deeper recursion better on this task.Source: D Detailed Results in COGS · p. 12
• Increasing encoder depth simultaneously lowers performance on Verb Argument Structure Alternation tasks.Source: D Detailed Results in COGS · p. 12
• Sequence tagging underperforms seq2seq on Prim verb →Infinitival argument because the isolated-verb example omits the relations that the verb allows.Source: D Detailed Results in COGS · p. 12
• Some tagging errors are structurally reasonable: models can recover the complete parsing tree while mislabeling a subject–predicate relation.Source: D Detailed Results in COGS · p. 12
• The best tagging model reaches only 0.233 on Sentential complements, where long chains and relative-attention limits cause frequent incorrect long-distance parent predictions.Incorrect parents are often more than 16 positions away, exceeding the relative attention offset limit.Source: D Detailed Results in COGS · pp. 12–13

• The algorithmic tasks cover addition, reversing, duplication, Cartesian products, and intersection, with several requiring extrapolation beyond training lengths.Cartesian products require two nested loops over the input sets, while duplication primarily challenges deciding when to stop output.Source: E Dataset Details · pp. 13–14
• Cartesian products remain especially challenging because output length grows quadratically with input size, making much longer test outputs necessary.Source: E Dataset Details · p. 14
• SCAN-length tests productivity by placing the longest instruction sequences in the test set, whereas SCAN-add-jump tests systematicity by combining a primitive learned only in isolation with other constructs.Source: E Dataset Details · pp. 14–15
• PCFG-productivity requires applying string operations such as reversing, duplicating, or selecting elements to longer compositions, while PCFG-systematicity recombines operations in unseen ways.Source: E Dataset Details · p. 15
• COGS tests unseen combinations in semantic parsing, including systematic changes in grammatical roles and deeper prepositional-phrase nesting.The deeper-nesting productivity cases are where sequence tagging significantly outperforms previous approaches.Source: E Dataset Details · p. 15, Table 12 · p. 17
• CFQ-MCD1 tests systematicity while also requiring Cartesian-product expansion and alphabetical sorting of SPARQL clauses.A question mentioning three relations and three movies can require nine clauses.Source: E Dataset Details · pp. 15–16