Type Diversity Enables Transformers to Generalise Compositionally

1 Introduction

• Type diversity counts the constructor functions that build trees of a linguistic type, and the paper proposes it as an explanation for poor structural generalisation.For noun phrases, simple determiner–noun phrases and phrases containing a prepositional phrase use different constructors.Source: §1 · p. 2
• The experiments add linguistic diversity to COGS and SLOG and generate more than a hundred SCAN variants with differing type diversity.The COGS and SLOG variants include adjectives, plural nouns, and verb tenses.Source: §1 · p. 2
• The paper also examines other dataset properties, including semantic-term order, and notes that diversity findings contradict the claim that compound divergence correlates negatively with Transformer performance.It describes distribution-based compositionality assessment (DBCA) as comparing distributions of atomic units and their combinations.Source: §1 · p. 2

2 Grammatical Framework: concrete & abstract syntax and interpretation

• Grammatical Framework separates abstract syntax, which specifies categories and how functions combine them, from concrete syntax, which specifies their string realization.Its rules can also interpret syntax trees in logical semantics.Source: §2 · pp. 3–5

3 Defining compositionality and assessing compositional generalisation

• Compositionality requires a homomorphism from syntax to semantics, with a corresponding semantic rule for each syntactic rule.The section also notes that compositional generalisation is often used more broadly than learning mappings from syntax trees to logical semantics.Source: §3 · pp. 5–6
• DBCA measures atom and compound divergence between training and test distributions, with low atom divergence and high compound divergence defining a highly compositional split.The measure can use input sequences or output sequences and does not itself assess the input-output mapping.Source: §3 · p. 6
• SCAN tests generalisation by withholding parts of command-translation data, while COGS includes lexical cases and structural cases involving novel phrase positions.The COGS PP-in-Obj→PP-in-Subj task trains on PP-containing noun phrases as objects and tests them as subjects.Source: §3 · pp. 6–7

4 Why are structural generalisation tasks hard for seq2seq models?

• Earlier studies report that lexical generalisation is easier than structural generalisation, but the authors argue type diversity explains much of this gap.They frame three proposed explanations: architectural limits, unfair or ill-posed tasks, and dataset surface properties.Source: §4 · p. 7

4.1 An architecture hypothesis: Structural generalisation is hard for Transformers

• Evidence that Transformers are inherently poor at structural generalisation remains limited because the issue has been studied in few works and mostly with COGS and its variants.The authors argue it is premature to blame the architecture without results across multiple datasets and task types or evidence of an internal deficiency.Source: §4.1 · p. 8

4.2 A perspective: Structural generalisation is not a fair task

• The authors consider Geiger et al.’s fairness requirement too strict as a necessary condition, while agreeing it would be sufficient for fairness.They argue that processing a novel structure in a new role is a reasonable expectation for models intended to exhibit human-like compositional generalisation.Source: §4.2 · p. 9

4.3 A concrete syntax hypothesis: Difficulty is on the surface

• Filler words and preposing raise reported accuracy from 0% to 20.5%, but accuracy remains below many lexical cases, so these changes do not account for all the difficulty.The cited work identifies constraints on variable numbers and token order as a source of difficulty.Source: §4.3 · p. 10
• Adding participial phrases with nmod semantics raises accuracy from 0% to 82.7% by reducing the test to lexical generalisation; using acl raises it from 0% to 24.7%.The authors note that acl adds a new structure and meaning, while the nmod setup introduces a phrase with semantics identical to prepositional phrases.Source: §4.3 · pp. 10–11

5.1 A preliminary experiment

• Removing object participial phrases while retaining them in subjects brought PP-in-Subj accuracy back close to 0%, contrary to the surface-order explanation tested.The comparison tests whether subject-only PAPs would help as much as PAPs in both subject and object positions if word order explained the gain.Source: §5.1 · p. 11, Table 1 · p. 11

5.2 Type diversity

• Type diversity (TD) counts constructors of a particular type, covering both lexemes and multiword structures in GF’s abstract syntax.The relevant structural additions are new structures of the same type, not familiar structures populated with new words; the measure depends on the grammar used.Source: §5.2 · pp. 12–13

5.3 Previous work on the effects of dataset properties on compositional generalisation

• Unlike data-augmentation research aimed at improving results, this work seeks to understand how training-data properties affect compositional generalisation.The experiments keep training-set sizes approximately equal and exclude test cases from training.Source: §5.3 · p. 13

5.3.1 Data augmentation

• Several augmentation methods increase lexical or subtree diversity, but their experiments often recover test samples rather than test generalisation beyond training.The authors argue that prior methods do not specifically target type diversity as they define it.Source: §5.3.1 · p. 14

5.3.2 Understanding the effects of data properties

• Type diversity is linguistically defined and language-specific, whereas density is intended to apply across machine-learning tasks.The authors distinguish this focus on linguistic categories from metrics that aggregate diversity more generally.Source: §5.3.2 · p. 15

6 Using GF to generate and extend the SCAN, COGS, and SLOG datasets

• GF’s Resource Grammar Library supplies English syntax, while higher-order abstract syntax supports compositional variable binding and interpretation in generated semantic-parsing data.Unlike QCFG-based COGS generation, GF can handle variable binding without the described brittle word-order-based post-processing.Source: §6 · pp. 15–16

7 Experiments on structural generalisation and type diversity in COGS

• Two other COGS structural-generalisation cases are excluded because their test sets introduce variable names that pose an out-of-vocabulary problem for seq2seq models.Source: §7 · p. 16
• Changing the logical-semantics output format raised accuracy from 0.0% in original COGS to 2.1% in the authors’ format.The authors note that this comparison means their results are not directly the original-format result.Source: §7 · pp. 16–17
• Increasing the original training set by 60% to match the largest variant’s word count changed accuracy from 2.1% to 1.7%, providing no size-related gain.The authors use this control to argue that dataset size does not confound the reported diversity results.Source: §7 · p. 17
• Adding PAPs in both roles, adjectives, and relative clauses raised accuracy to 55.4%; adding plural forms then raised it from 55.4% to 69.3%.PAPs only in subjects improved accuracy from 1.7% to 6.2%, while adding PAPs in objects yielded a larger improvement.Source: §7 · pp. 17–18
• 73.3% mean accuracy with added verb tenses versus 69.3% without them was less than half the standard deviation across random seeds.The added tenses did not increase NP diversity, and the authors describe the difference as not significant.Source: §7 · p. 18
• 92.4% accuracy followed additions of two artificial NP structures, extending the reported type-diversity–performance correlation beyond the earlier results.The artificial structures differed from the test case, so the authors characterize the task as structural rather than lexical generalisation.Source: Table 2 · p. 17, §7 · p. 18
• The highest-diversity dataset used five NP or CN structures, which the authors say do not exhaust English noun-phrase structures.They argue that improvement with each added constructor supports their account of the previously reported lexical–structural gap, while noting that concrete properties also affect results.Source: §7 · pp. 18–19

8.1.1 Experimental setup

• SCAN variants hold out one constructor at each level of a V→VP→Imp hierarchy, varying constructors to compare lexical and structural generalisation separately.The structural constructors here use one indicator token, unlike COGS PPs, and the held-out constructor appears in only one role; this is a controlled comparison, not a replication of COGS.Source: §8.1.1 · pp. 19, 22
• Training sets were approximately equal in size, but the zero-added-diversity base set was an outlier, so the authors draw no conclusions from it alone.Average output lengths were 17.1–18.0 tokens except for the base set at 15.2; training-set lengths ranged from 440,520 to 467,840 tokens, with the base set at 388,263.Source: §8.1.1 · p. 22

8.1.2 Transformer training details

• Across 120 training sets, models were trained with 14 random seeds each; roughly 1M-parameter Transformers ran for 15,000 steps without warmup and with dropout rate 0.1.The same test set was used throughout, divided into three parts testing generalisation to a new constructor of each of three types.Source: §8.1.2 · p. 23

8.1.3 Results

• At V diversity 10, greater VP diversity accompanies higher lexical accuracy, but at V diversity 90 the relationship reverses; Imp diversity shows a similar, smaller reversal.At V=10 and Imp diversity=0, lexical accuracy rises from 3% to 14% as VP diversity goes from 0 to 90; at V=90 and Imp diversity=0, it falls from 93% to 76%. Across Imp-diversity levels, Spearman’s ρ for VP diversity is 0.86 at V=10 and -0.67 at V=90; for Imp diversity it is 0.28 and -0.75, respectively.Source: §8.1.3 · pp. 23, 25
• From around 0–3% to 60–90% accuracy as type diversity rises across lexical and both structural SCAN tests; their diversity-accuracy correlations do not differ significantly.The study contrasts this with prior findings that structural generalisation is harder, noting that its lexical and structural types have roughly equal diversity.Source: §8.1.3 · p. 23, Figure 1 · p. 24
• VP generalisation is associated with VP diversity, while second-order structural generalisation also varies with subtree diversity, whose effects can change direction as Imp diversity rises.VP diversity’s relationship with VP accuracy plateaus or may reverse after 60 added constructors. For Imp generalisation, VP diversity correlates at Imp diversity=4 (ρ=0.58), while at Imp diversity=16 the correlations for V and VP diversity are -0.44 and -0.65.Source: §8.1.3 · p. 25

8.2 Type diversity and the atom/compound divergences of Keysers et al.

• Accuracy correlates positively with atom and compound divergence in all three SCAN tests, contradicting a general claim that compound divergence captures compositional-generalisation difficulty.The authors qualify the comparison: here, divergence rises by broadening the training set while the test set stays fixed, so compound divergence can indicate broader training support rather than a more dissimilar test case.Source: Figure 2 · p. 26, §8.2 · pp. 27–28, Figure 3 · p. 27

9.1 The SLOG dataset

• SLOG test cases target NP, slashed-VP, or clause constructors in novel roles, with four cases excluded for out-of-vocabulary depth or near-ceiling accuracy.Three excluded cases involve deeper nesting; the fourth is active-voice wh-questions, where Transformers were already near 100% accurate.Source: §9.1 · pp. 29–30

9.2.1 Separating events, renaming variables, removing explicit lambdas

• Separating event predicates from thematic-role predicates mostly had little effect, but could help on 3-place direct-object wh-questions with systematic role-omission errors.The separated format was described as more compositional because thematic-role predicates no longer had to repeat the verb.Source: §9.2.1 · p. 32

9.2.2 Morphological segmentation

• Morphological segmentation made little difference with only past tenses, but its effect became large after additional verb tenses were added.For example, “painted” was segmented as “paint ed.”Source: §9.2.2 · p. 33

9.2.3 Adding number and tense predicates

• Adding number and tense predicates had little impact by itself, and served as a prerequisite for adding plural forms and new tenses.Their negligible effect means these changes do not confound the results attributed to adding tenses and plural forms.Source: §9.2.3 · p. 33

9.2.4 Changing the order of semantic terms

• Duplicate question marks occurred in 63.2% of samples with aligned-order models versus 18.1% with GF-order models on indirect-object wh-questions.Aligned-order models often placed the interrogative variable in Theme before correctly placing it in Recipient; GF order outputs the noun semantics first.Source: §9.2.4 · p. 34

9.2.5 NP diversity

• PP-in-subject-NP accuracy rose from nearly zero to about 35%, while shallower centre embedding rose from near zero to around 80%.RC-in-subject-NP accuracy increased from 0.0 (+-0.0) to 1.8 (+-1.7)%; changing semantic-term order could erase the non-zero result in that case.Source: §9.2.5 · p. 35

9.2.6 Clause diversity

• New tenses improved CC wh-questions but not shallower tail CC recursion, and combining tenses with NP diversity had the largest positive effect in the wh-question case.Pooled variable-binding errors fell from 22.9% without tenses to 2.6% with tenses; new tenses made time and anteriority variable binding relevant.Source: §9.2.6 · pp. 35–36

9.3 Conclusions from the SLOG experiments

• Average accuracy increased from 27.7% to 47.7%, mostly due to increased NP diversity.Other properties, including output sequence order and separating event predicates from thematic-role predicates, also had large effects in some cases.Source: §9.3 · p. 36

10 Discussion on compositional generalisation benchmarking methods

• Diagnostic datasets control for many natural-language properties, but benchmark results can still reflect factors beyond systematic compositional structure.The authors note that natural language includes synonymy, polysemy, idioms, irregular inflections, and constructions that can obscure systematicity.Source: §10 · p. 36
• COGS may misrepresent Transformers’ structural generalisation because the tested noun-phrase structure has unnaturally low type diversity.The authors argue that other dataset properties cannot simply be removed; their effects must instead be mapped and controlled when comparing models.Source: §10 · p. 37
• Different compositional-generalisation benchmarks have ranked models differently, raising concerns about their construct validity.Prior work cited in the discussion also reports that SCAN’s limited target-side dependencies can let models perform well without interesting composition, and that adding verbs improved performance on its “add jump” split.Source: §10 · p. 37
• The results do not establish that enough type diversity would give Transformers perfect or human-level compositional generalisation.Accuracy typically plateaus below 100%, consistent with previous lexical-diversity studies.Source: §10 · p. 37

11 Summary and Conclusions

• Structural generalisation is not significantly harder than lexical generalisation for Transformers when differences in type diversity are considered.The authors attribute the earlier disparity to lower type diversity among tested structural types than lexical types.Source: §11 · p. 37
• Linguistically diverse variants of the previously published COGS and SLOG datasets were generated using Grammatical Framework.The approach is described as extendable to additional linguistic structures and languages.Source: §11 · p. 37
• Subtree and supertree type diversity can help generalisation when type diversity itself is low.The supplied conclusion presents this as an additional finding beyond diversity of the novel test structure.Source: §11 · pp. 37–38
• Compound and atom divergences can correlate with Transformer generalisation when the divergence comes from increased type diversity.This finding contrasts with the cited observation by Keysers et al. (2020).Source: §11 · p. 38
• The order of semantic terms also affects generalisation results.Source: §11 · p. 38

12 Limitations

• The experiments use only Transformer models, so the results probably do not generalise to all seq2seq models.Prior work reports substantial differences between Transformers and LSTM networks.Source: §12 · p. 38
• Each experiment uses one hyperparameter setup, leaving open whether some conclusions are specific to the chosen Transformer hyperparameters.The authors selected settings from prior work for comparability.Source: §12 · p. 38
• Variance across random seeds is very high in most results, although the authors report standard deviations and rely on findings they judge to persist despite it.Source: §12 · p. 38

A Generating SCAN

• Table 4 presents SCAN’s abstract syntax.The appendix identifies it as the abstract syntax used to define the SCAN grammar.Source: A Generating SCAN · p. 39, Table 4 · p. 39
• Tables 5 and 6 present SCAN’s concrete syntaxes for the source and target domains, respectively.Source: A Generating SCAN · p. 39, Table 5 · p. 40, Table 6 · p. 41
• The listed SCAN categories are assigned the linearisation type Str.The supplied syntax excerpt also includes a `lin` declaration.Source: A Generating SCAN · pp. 39–41

• The semantics uses individuals, events, and propositions, with Exist, ExistEvent, and Unique taking higher-order function arguments.Agent, Theme, and Recipient express propositions about an individual and an event.Source: B Logical semantics · p. 42
• Interpretation functions are defined for each natural-language category, and applying them to a syntax tree computes its logical-semantics interpretation.The functions guarantee compositionality of interpretation.Source: B Logical semantics · p. 42
• A sentence tree such as “a man drinks a coffee” is computed into a logical-semantics proposition that can then be linearised.The example represents the drink event, its agent, and its theme.Source: B Logical semantics · p. 43

C Generating COGS and SLOG

• COGS and SLOG are regenerated with Grammatical Framework using a slightly modified logical form and interpretation functions for their syntactic categories.The functions cover sentence, tense, anteriority, polarity, determiner, verb phrase, noun phrase, and verb.Source: C Generating COGS and SLOG · p. 43
• The generated logical-semantics tree is linearised into a simplified flat format resembling COGS.The example flat form lists noun and number predicates alongside event, agent, theme, anteriority, and time predicates.Source: C Generating COGS and SLOG · p. 45

D Distribution-based compositionality assessment of the SCAN variants

• Atom and compound divergence both correlate with type diversity across SCAN variants.Figures 6 and 7 show the atom and compound divergences, respectively.Source: D Distribution-based compositionality… · p. 46, Figure 6 · p. 47, Figure 7 · p. 48

• Combining a question or relative-clause gap with a double-object construction can produce two possible gap positions and readings.The paper notes that the less common interpretation may sound ungrammatical without semantic support.Source: E Ambiguity in the SLOG dataset · p. 49
• In SLOG, double-object constructions with gaps are not systematically resolved when ditransitive verbs occur in both a relative clause and the main clause.The example permits two parses even though the gap is otherwise placed after the final word.Source: E Ambiguity in the SLOG dataset · p. 49
• Some resulting parses are semantically unlikely, but resolving ambiguity from semantic cues is outside SLOG’s intended challenges.The paper says semantic cues available to Transformers are very limited.Source: E Ambiguity in the SLOG dataset · p. 49

• Active subject questions are excluded from the results because Transformers achieve close to 100% accuracy on that sample group.A few percent of its samples are still systematically misinterpreted.Source: F Additional error analysis of SLOG… · p. 50
• Remaining systematic errors involve unaccusative verbs that appear mostly as two-place verbs in training.Examples include “Who froze?”, “Who floated?”, “What rolled?”, and “What decomposed?”.Source: F Additional error analysis of SLOG… · p. 50
• The error pattern reflects a mismatch between training subjects interpreted as agents and test subjects that should be themes.The analysis describes this as the unergative–unaccusative distinction combined with object alternation.Source: F Additional error analysis of SLOG… · p. 50