COGS: A Compositional Generalization Challenge Based on Semantic Interpretation

Najoung Kim; Tal Linzen

Source-linked AI summary

COGS: A Compositional Generalization Challenge Based on Semantic Interpretation

Najoung Kim, Tal Linzen

arXiv:2010.05465v1Oct 12, 2020cs.CL

TL;DR

COGS addresses the limited evaluation of compositional generalization in language models by introducing a semantic parsing dataset with systematic train–evaluation gaps. Using controlled synthetic generation, the paper finds that Transformers and LSTMs are near-perfect in distribution but substantially weaker and seed-sensitive on generalization cases, especially structural ones.

Problem
Existing standard NLP models are not designed to generalize compositionally, motivating a controlled evaluation of whether they can recombine familiar words and structures into new semantic interpretations.
Method
COGS is a rule-based synthetic sentence-to-logical-form dataset whose evaluation cases systematically recombine familiar primitives, structures, grammatical roles, and nesting depths.
Results
96–99% mean accuracy in distribution fell to 16–35% on out-of-distribution generalization, with 6–8% standard deviation across random seeds and structural cases more difficult than lexical cases.
Takeaways & Limitations
The tested Transformers and LSTMs showed limited compositional generalization capacity, while COGS provides a challenge for motivating new computational models.
Takeaways & Limitations
COGS evaluates systematic generalization but not the ability to constrain generalizations, simplifying natural language by including only cases where generalizations apply.

Abstract

from arXiv · show

Natural language is characterized by compositionality: the meaning of a complex expression is constructed from the meanings of its constituent parts. To facilitate the evaluation of the compositional abilities of language processing architectures, we introduce COGS, a semantic parsing dataset based on a fragment of English. The evaluation portion of COGS contains multiple systematic gaps that can only be addressed by compositional generalization; these include new combinations of familiar syntactic structures, or new combinations of familiar words and familiar structures. In experiments with Transformers and LSTMs, we found that in-distribution accuracy on the COGS test set was near-perfect (96--99%), but generalization accuracy was substantially lower (16--35%) and showed high sensitivity to random seed ($\pm$6--8%). These findings indicate that contemporary standard NLP models are limited in their compositional generalization capacity, and position COGS as a good way to measure progress.

1 Introduction

COGS evaluates whether language models can compositionally construct semantic representations when familiar words and structures are recombined in systematically novel ways. Standard neural architectures perform near-perfectly in distribution but generalize poorly out of distribution.

COGS is a semantic parsing challenge in which models map English sentences to semantic representations under systematic train–evaluation distribution shifts.Success requires out-of-distribution generalization consistent with compositional principles.
96–99% mean accuracy was achieved on the in-distribution test set, compared with 16–35% on the out-of-distribution generalization set.The generalization set was substantially more difficult for the evaluated architectures.
6–8% standard deviation in generalization accuracy across random seeds showed strong sensitivity to initialization.Runs differed only in random seed while using the same architecture.
Structural generalization was more difficult than lexical generalization for the evaluated models.The challenge includes novel combinations of syntactic structures, primitives, modified phrases, nesting depths, argument alternations, and verb classes.

2 Compositional Generalization

COGS builds on research examining whether neural networks exhibit human-like systematicity, extending compositional-generalization evaluation beyond narrower synthetic tasks. Its semantic representations cover a broader range of English expressions than SCAN and differ from CFQ’s SQL-focused setting.

Systematicity concerns producing and understanding different sentences by recombining the same primitives with the same rules.John loves Mary and Mary loves John exemplify this combinatorial property.
Earlier connectionist models and later LSTM- and GRU-based sequence-to-sequence models were reported not to display human-like systematicity.The cited studies reached similar conclusions about the limits of those models.
SCAN tests compositional generalization by mapping synthetic-language word sequences to navigation commands, but its semantic representation covers only a small subset of English grammar.COGS is intended to test systematic linguistic abstractions unavailable in SCAN.

3 Overview of COGS

COGS is a synthetic sentence-to-logical-form dataset designed to test multiple compositional generalization gaps in English. Its cases recombine familiar primitives, grammatical roles, modifiers, recursive structures, argument alternations, and verb classes.

COGS uses a rule-based sentence-to-logical-form mapping to control input distributions and cover rare constructions.The dataset is not inherently grounded, though it could potentially be linked to a knowledge base or visual world.
Novel Combination of Familiar Primitives and Grammatical Roles: Training and generalization cases test novel combinations of primitives with grammatical roles, including subject-to-object shifts in simple and embedded clauses.Some lexical items occur in only one grammatical role during training and the opposite role during generalization.
Novel Combination of Modified Phrases and Grammatical Roles: PP-modifier cases train only object-NP modification and evaluate subject-NP modification, testing whether modified phrases retain their grammatical-role flexibility.The paper identifies this setup as a simplification of the generalization problem humans may encounter.
Deeper Recursion: Recursive cases train embedding depths 0–2 and evaluate strictly greater depths of 3–12 for sentential complements and nominal PP modifiers.The dataset therefore tests generalization to deeper nesting rather than merely recombining surface roles.
Verb Class: COGS includes active–passive, transitive–intransitive, and dative alternations, plus verb–NP combinations requiring verb-class-sensitive thematic-role interpretation.For example, interpreting cobra as the theme of freeze cannot be determined from surface syntax alone.

4 Dataset Generation

The dataset is generated with a probabilistic grammar and deterministic semantic annotations, then converted into indexed logical forms and divided into controlled training, development, test, and generalization sets. Additional exposure examples ensure key primitives occur in training contexts needed for evaluation.

A PCFG generates the covered constructions, while annotated rules provide the semantic-class information needed to disambiguate syntactic structures.The semantic interpretation follows deterministically from the PCFG rules.
Sentences are mapped to a simplified logical formalism whose indexed constants represent entities or events associated with phrasal-head positions.The indexing scheme avoids selecting arbitrary constant names as expressions grow.
Primitive exposure examples supply training contexts required for targeted generalizations, such as observing hedgehog as a subject before testing it as an object.The design reflects evidence that children can generalize nonce verbs after limited distinct exposure.
24,000 of 30,000 sampled sentences form the initial training set, with 3,000 each for development and test; the resulting training set contains 24,155 examples.The added examples include primitive meanings for 80 verbs and 60 nouns, plus 15 primitive exposure examples.
The generalization set samples 1,000 examples for each of 21 cases, totaling 21,000 examples.Separate PCFGs generate examples for particular generalization cases such as Subject → Object.

5 Experiments

Experiments evaluated LSTM and Transformer encoder-decoder models on COGS, finding strong in-distribution performance but weak, variable out-of-distribution generalization. Structural and depth generalization were especially difficult, and scaling parameters did not improve Transformer performance.

Experimental setup: COGS experiments trained unidirectional LSTM, bidirectional LSTM, and Transformer encoder-decoder models without pretraining, using five random seeds.The Transformer and LSTMs had comparable parameter counts, while training used cross-entropy loss and early stopping.
Results: In-distribution accuracy was strong and stable, whereas generalization accuracy was low and substantially more variable across runs.The evaluation counted an output as correct only when it exactly matched the gold sequence.
Results: Transformers and unidirectional LSTMs had similar average accuracy, while bidirectional LSTMs performed comparatively worse.This comparison concerns models of comparable size.
Lexical vs. Structural Generalization: Structural generalization was harder than lexical generalization: depth and modifier-role cases had zero or near-zero accuracy, while lexical cases performed better.Lexical generalization combines a familiar primitive with a familiar structure; structural generalization combines familiar structures into a novel structure.
Levels of Embedding: Depth generalization failures reflected both sequence complexity and output-generation errors, not merely difficulty producing novel labels.Only 0.5% of depth-generalization errors had correct structure with incorrect indices, while 90.3% ended prematurely; outputs longer than 95 tokens had 68% LSTM and 13% Transformer accuracy, versus near-zero PP-modifier depth accuracy for both.
Model Size / Number of Exposure Examples: Fivefold larger Transformers did not improve performance, whereas increasing primitive exposure examples from one to 100 improved lexical generalization across all three models.The exposure increase was applicable only to lexical generalization cases.

6 Comparison to Related Work

COGS complements prior compositional-generalization benchmarks by testing semantic parsing over a broader fragment of English. Its results align with reported gaps between in-distribution and out-of-distribution performance, including difficulty with deeper structures and longer sequences.

Neural models show a recurring discrepancy between excellent in-distribution performance and degraded out-of-distribution performance.
Poor generalization to deeper nested structures also relates to difficulty generalizing to longer sequences, paralleling persistent difficulty on SCAN length splits.
COGS differs from CFQ by covering a broader variety of interpreted English expressions than question- and imperative-limited SQL mappings.
COGS directly evaluates the meaning assigned to sentences, unlike syntactic-generalization language-modeling setups that do not evaluate semantic interpretations.

7 Constraints on Generalization

COGS evaluates systematic generalization but deliberately excludes the harder problem of learning when generalizations should be constrained. The dataset therefore simplifies natural-language variation and leaves constraint learning to future work.

COGS does not evaluate whether computational models can constrain systematic generalizations.
The dataset includes only cases where generalizations apply, such as dative verbs that alternate, rather than exceptions requiring learned constraints.
Natural-language generalizations depend on morphophonological, syntactic, and semantic factors, including animacy and definiteness in dative alternation.
COGS leaves constraint evaluation for future work requiring detailed case-specific factors and a formalism that can express them.

8 Conclusion

The paper introduces COGS as a synthetic sentence-to-logical-form challenge for compositional generalization. Transformers and LSTMs perform near-perfectly in-domain but poorly and variably on generalization, especially for structural cases.

8 Conclusion: COGS uses a synthetic sentence-to-logical-form mapping task that approximates English meaning interpretation.
8 Conclusion: Transformers and LSTMs perform poorly on COGS generalization, with high run-to-run variability, while in-domain test performance is consistently near-perfect.
8 Conclusion: Structural generalization is more challenging for the tested models than lexical generalization.
Dataset construction: The PCFG assigns about 5% probability to most frames and about 8% to CP embedding constructions, while post-generation filtering can alter generated proportions.
Dataset construction: The dataset construction simplifies frequency assumptions because not all syntactic categories or subtypes are expected to follow Zipfian distributions.
Logical-form postprocessing: The logical forms use deterministic conjunct ordering by Skolem-constant subscripts and remove event predicates triggered by nominals.

D Training Details

The experiments use standard LSTM and Transformer architectures and examine how Transformer size and primitive exposure affect COGS performance. Larger models do not improve test accuracy reliably, while more exposure examples benefit all models.

Model architectures: The LSTM experiments use 2-layer encoder-decoders with global attention, testing both unidirectional and bidirectional encoders.
Model architectures: The Transformer uses 2 encoder and decoder layers, 4 attention heads, and a feedforward dimension of 512.
Effect of model size: 45M, 9.5M, and 4.5M parameter Transformers all exceed 90% test-set accuracy, so parameter count has little impact on that metric.
Effect of model size: Model size affects generalization, but the 45M model has a lower five-run average than smaller models, with high variance making the result difficult to interpret.
Exposure examples: Increasing primitive exposure examples from one to 100 benefits all models, while cases not requiring exposure examples remain identical across settings.

F Results by Case

Table 7 provides the full model accuracy results for each generalization case.

Table 7 lists full model accuracy for every generalization case.

G.1 Active →Passive: Systematicity of Errors in LSTMs vs. Transformers

LSTMs and Transformers differed not only in accuracy but also in error structure across Active →Passive generalization. LSTM errors were usually structurally correct and systematic, whereas Transformer errors were fewer but often structurally invalid and more variable.

Model comparison: Transformers performed near-perfectly on Active →Passive generalization, whereas LSTMs did not, but LSTM errors were more systematic.The comparison concerns both performance and the organization of errors, not accuracy alone.
LSTM error structure: 0.3% (7/2591) of unidirectional LSTM errors and 0.5% (14/2773) of bidirectional LSTM errors had a different structure from the gold output.Most LSTM errors preserved the correct output structure and token count, despite wrong verbs, thematic roles, or indices.
Transformer error structure: 79.6% of Transformer errors (39/49) in Active →Passive generalization had incorrect structure.Transformer errors included omitted conjuncts, spurious indices, missing outputs, and numbered constants substituted for proper nouns.
Model comparison: Transformer runs with similar Active →Passive accuracy nevertheless differed in error systematicity: some used the wrong verb consistently, while others made mixed, idiosyncratic errors.Random initialization therefore affected the pattern of errors even when aggregate accuracy was similar.
Possible explanation: Equal sampling of passive constructions with and without agent by-phrases may have increased exposure to examples relevant to forming passives.The corresponding logical forms are related by a prefix, with the agent conjunct added in the by-phrase version.

H Linguistic Commentary

The linguistic commentary describes COGS’s semantic representation, tested structural and depth generalizations, and grammar-specific assumptions. It also identifies scope boundaries involving human comparability, attachment ambiguity, and simplified selectional preferences.

Semantic representation: COGS uses a Neo-Davidsonian semantic representation in which verbs introduce event arguments and thematic roles connect non-event arguments to events.Definite descriptions that are not proper names receive asterisks standing for standard ι notation.
Recursive structures: The dataset tests traditionally recursive structures that can nevertheless be implemented by a Finite State Machine, leaving unbounded recursion as a debated assumption.The commentary distinguishes the tested structures from recursion as an intrinsic language mechanism.
Depth generalization: Depth generalization evaluates 3–12 degrees of right-branching embedding, while models already had nearly zero accuracy at depth 3 and were predicted to differ from humans.The prediction was that humans would retain degraded but reasonable understanding at depth 3.
PP attachment: The grammar permits only NP-attachment readings for PP modifiers, although human readers may sometimes favor VP attachment based on lexical content.PP modifications are nested rather than sequential, and VP-modifying PPs are absent from the grammar.
Selectional preference: COGS implements selectional preference as a simplified animacy constraint based on verb type, whereas real selectional preferences are more complex and verb-specific.This simplification limits how fully the dataset represents lexical semantic constraints.
PP modification generalization: Generalizing PP modification from object-position NPs to subject-position NPs may be stronger than human experience, and human performance without cross-position exposure remains untested.The authors identify this question as future work.