Source-linked AI summary
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Daniel Keysers, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashubin, Nikola Momchev, Danila Sinopalnikov, Lukasz Stafiniak, Tibor Tihon, Dmitry Tsarkov, Xiao Wang, Marc van Zee, Olivier Bousquet
TL;DR
Machine learning systems often fail at compositional generalization, while realistic benchmarks for measuring it remain scarce. The paper introduces DBCA, constructs the CFQ benchmark, and applies the approach to CFQ and SCAN. Three architectures fail compositionally, and accuracy is strongly negatively correlated with compound divergence.
Problem
State-of-the-art machine learning methods exhibit limited compositional generalization, and realistic benchmarks that comprehensively measure this ability are lacking.
Method
The paper introduces DBCA, constructs the realistic CFQ dataset with it, and creates divergence-based compositionality experiments for CFQ and SCAN.
Results
Three baseline architectures fail to generalize compositionally, and mean accuracy is strongly negatively correlated with compound divergence.
Takeaways & Limitations
CFQ and DBCA provide a benchmark and yardstick for evaluating progress in compositional generalization.
Takeaways & Limitations
The authors identify broader language-understanding coverage and end-to-end natural-language question answering as directions for extension.
Abstract
from arXiv · showhide
State-of-the-art machine learning methods exhibit limited compositional generalization. At the same time, there is a lack of realistic benchmarks that comprehensively measure this ability, which makes it challenging to find and evaluate improvements. We introduce a novel method to systematically construct such benchmarks by maximizing compound divergence while guaranteeing a small atom divergence between train and test sets, and we quantitatively compare this method to other approaches for creating compositional generalization benchmarks. We present a large and realistic natural language question answering dataset that is constructed according to this method, and we use it to analyze the compositional generalization ability of three machine learning architectures. We find that they fail to generalize compositionally and that there is a surprisingly strong negative correlation between compound divergence and accuracy. We also demonstrate how our method can be used to create new compositionality benchmarks on top of the existing SCAN dataset, which confirms these findings.
1 INTRODUCTION
The paper addresses machine learning systems’ weak compositional generalization and the shortage of realistic benchmarks for measuring it. It introduces DBCA, CFQ, and experiments analyzing compositionality across CFQ and SCAN.
- Compositional generalization is the ability to systematically generalize to composed test examples after learning their necessary components on a different distribution.
- State-of-the-art machine learning methods often fail to capture underlying compositional structure and therefore fail to generalize compositionally.
- Existing benchmark approaches split examples using observable properties such as output patterns, output length, or rarely observed primitives.
- DBCA quantitatively assesses dataset-split adequacy for compositional generalization and constructs splits designed for this purpose.
- CFQ is a large, realistic natural-language-understanding dataset specifically designed to measure compositional generalization using DBCA.
- Experiments on CFQ and SCAN compare DBCA-based splits with other compositionality experiments and evaluate three baseline architectures.
- The three architectures fail to generalize compositionally, while compound divergence strongly predicts test accuracy.
2 DISTRIBUTION-BASED COMPOSITIONALITY ASSESSMENT (DBCA)
DBCA evaluates compositionality through train-test splits with similar atom distributions but maximally different compound distributions. It formalizes these divergences using weighted compound frequencies and Chernoff-coefficient-based measures.
- Compositional generalization is tested by exposing learners to similarly represented atoms but novel compounds in the test distribution.
- In CFQ and SCAN, atoms are individual rules, while compounds are subgraphs of rule-application DAGs.
- A compositionality experiment is a train-test split intended to measure compositional generalization.
- Ideal splits keep atom distributions similar while making compound distributions as different as possible.
- Similar atom distributions isolate differences in composition, while different compound distributions make the experiment compositionally challenging.
- Compound distributions use weighted frequencies of selected rule-DAG subgraphs to reduce double-counting highly correlated super-compounds.
- Chernoff coefficients quantify distribution similarity, using α = 0.5 for atom distributions and α = 0.1 for compound distributions.
- DBCA defines compound divergence as DC(V ∥W) = 1 − C0.1(FC(V) ∥FC(W)) and atom divergence as DA(V ∥W) = 1 − C0.5(FA(V) ∥FA(W)).
3 THE CFQ DATASET
CFQ is a large, realistic dataset generated with tracked compositional rules to support compositional-generalization assessment. It maps natural-language questions to SPARQL queries, while controlling ambiguity, scope, complexity, and entity grounding.
- Dataset and task: CFQ is a large dataset of natural-language questions and answers paired with SPARQL queries for Freebase semantic parsing.It contains 239,357 English question-answer pairs answerable using public Freebase data.
- Automatic generation: Rule-based generation tracks atoms and compounds through rule-application sequences, enabling controlled measurement of compositional structure.The generator produces question, logical-form, and SPARQL triples together with a normalized DAG of rule applications.
- Automatic generation: The generation rules use four categories: grammar, inference, resolution, and knowledge rules.Grammar and inference rules construct questions and logical forms; resolution rules map logical forms to SPARQL, while knowledge rules provide reusable logical-form expressions.
- Dataset construction: CFQ controls complexity and diversity by sampling generated questions, subsampling across complexity levels, and maximizing diversity of rule combinations.Complexity is measured by the number of rule applications, while rule-combination diversity is measured using empirical entropy of weighted rule-application DAGs.
- Dataset design: The dataset covers selected compositional language and knowledge-base features while largely avoiding ambiguity through unique entity references and constrained interpretations.Its scope includes question types, subordinate clauses, voice, conjunctions, possessives, adjectives, and type restrictions.
- Dataset statistics: CFQ contains the most query patterns by an order of magnitude and substantially more queries and questions than the compared semantic-parsing datasets.The comparison anonymizes entities and properties to determine query patterns; CFQ uses at most one entity substitution per question pattern.
4 COMPOSITIONALITY EXPERIMENTS FOR CFQ AND SCAN
The experiments construct divergence-controlled train/test splits for CFQ and SCAN using a greedy method, emphasizing maximum compound divergence under low atom divergence. MCD splits are more comprehensive than single-criterion alternatives and achieve substantially higher compound divergence at similar atom divergence.
- Split construction: The greedy split algorithm alternates examples between train and test while maintaining the target ratio and selecting examples to approach desired atom and compound divergences.Randomized choices allow multiple distinct splits to satisfy the same divergence targets.
- MCD experiments: MCD splits target maximum compound divergence while keeping atom divergence at or below 0.02.They are compared with random splits and previously proposed length- and pattern-based experiments on CFQ and SCAN.
- Experimental setup: All experiments use 40% of the data for training and 10% for validation and testing, with roughly 96k training and 12k validation/test examples for CFQ.For SCAN, the corresponding counts are approximately 8k training and 1k validation/test examples.
- Results: MCD splits achieve significantly higher compound divergence at similar atom divergence than the other evaluated experiments.They optimize divergence across all compounds rather than focusing on one arbitrary aspect of compositional generalization.
- Results: MCD splits correlate with targeted properties such as shorter training examples and limited coverage of test input and output patterns, but less strongly than specialized experiments.These correlations vary across splits.
- Interpretation: Across multiple MCD splits, compositionality is assessed comprehensively rather than through a single immediately observable criterion such as length.Consequently, train and test examples generally look fairly similar.
5 EXPERIMENTAL RESULTS AND ANALYSIS
Experiments on CFQ and SCAN evaluate three encoder-decoder baselines across divergence-controlled and comparison splits. The models perform well on random or low-divergence settings but fail on compositional splits, with compound divergence strongly predicting accuracy.
- Experiment setup: The study evaluates LSTM+attention, Transformer, and Universal Transformer baselines, training fresh models for each experiment and replicating each five times.Hyperparameters are tuned on a CFQ random split and fixed across CFQ and SCAN; results report mean accuracy with 95% confidence intervals.
- Experiment setup: Compound divergence is varied from zero to the maximum achievable in 0.1 increments while keeping atom divergence at or below 0.02.At least three randomized splits are produced for each target divergence, alongside accuracies on other comparison splits.
- CFQ results: All models exceed 95% accuracy on random splits, whereas mean accuracy on MCD splits remains below 20% despite roughly 96k training instances.The similar atom distributions between train and test therefore do not ensure strong performance on novel compounds.
- CFQ results: Compound divergence has a strong negative correlation with mean accuracy for all architectures, suggesting failure to capture compositional rather than superficial structure.Varying compound divergence gives direct control of mean accuracy even when train and test examples look similar.
- Split analysis: Splits based on output length perform worse than expected from compound divergence because they also change output length and slightly increase atom divergence.Comparisons with prior experiments indicate that differing atom distributions generally lower accuracy without breaking the accuracy–compound-divergence correlation.
- Error analysis: On the analyzed MCD1 split, accuracies range from 29% to 37%, and 68% of errors occur on the same samples across systems.The most common error is clause omission, appearing in 43%-49% of test samples; errors also occur more often for longer sequences.
- SCAN results: On SCAN, compound divergence again predicts mean accuracy, with systems reaching nearly 100% accuracy up to approximately 0.2 divergence.CFQ appears more complex than SCAN, using 443 construction rules compared with SCAN’s 38.
6 RELATED WORK
Related work studies compositional generalization across semantic parsing, SCAN, mathematics, visual reasoning, and learned representations. This paper extends these directions with CFQ’s rule-tree annotations and a formal analysis based on atom and compound divergences.
- Semantic parsing and SCAN: Finegan-Dollak et al. use query-pattern splits for semantic parsing, while Lake and Baroni introduce SCAN for compositional navigation commands.Prior work confirms that query-pattern splits are harder than conventional splits, and SCAN has supported analyses of compositional generalization.
- Related datasets: The mathematics dataset shares the goal of testing generalization but focuses on mathematical reasoning, whereas this work performs finer-grained analysis through generation rules.Its 112M samples are organized into 56 separate subtasks.
- Related datasets: ComplexWebQuestions is related to CFQ but was not considered suitable for thorough compositionality analysis because consistent compositional annotations would be difficult to obtain.Its complex questions are generated from simpler WebQuestionsSP sub-questions and then manually reworded.
- Visual reasoning: CLEVR uses functional programs to study visual reasoning and generalization to new combinations of visual attributes, counts, and program depths.Subsequent work includes neural-symbolic and compositional-attention architectures for CLEVR.
- Contribution relative to prior work: CFQ adds exact rule-tree annotations that enable analyses beyond accuracy on particular holdouts, including formal measurement through atom and compound divergences.This distinguishes the approach from many prior discussions of compositionality.
- Architectures and representations: Other related work addresses semantic parsing architectures, combinatorial generalization, and compositionality of learned representations.Examples include memory networks, multi-hop reasoning systems, representation tree-reconstruction error, and arguments for prioritizing combinatorial generalization.
7 CONCLUSION AND OUTLOOK
The paper presents a large realistic benchmark and DBCA-based dataset construction for measuring compositional generalization. Baseline results show failures despite abundant training data and a strong relationship between accuracy and compound divergence.
- The benchmark is described as the largest and most comprehensive evaluation of compositional generalization on a realistic NLU task.
- Its dataset uses a principled rule-based generation process and splits train and test data by optimizing atom and compound distribution divergences.
- Three baseline systems fail to generalize compositionally even when trained on large amounts of data.
- Mean accuracy is strongly correlated with compound divergence in the reported baseline experiments.
- The authors propose using the benchmark as a yardstick and suggest pretraining, targeted architectures, and applying DBCA to visual reasoning as future directions.
- The authors are also interested in evaluating end-to-end natural-language question answering and extending the approach to broader language-understanding phenomena.
A EXAMPLE DATASET ITEM
The example item illustrates how CFQ represents a question, its answer, multiple normalized forms, the corresponding SPARQL query, and the rules used to generate them.
- A CFQ item records the question, answer, SPARQL query, normalized patterns, complexity measures, and generation rules.
- The example asks whether Agustin Almodovar executive produced Deadfall and gives the expected answer as “No.”
- The question and query are represented with entity-specific and abstracted forms, including placeholders M0 and M1.
- Generation metadata includes SPARQL-generation operations such as entity identification and truth-set retrieval.
- The item links grammar rules and Freebase property mappings to the generated query.
- The rule tree records the grammar and query-generation steps used to construct the example.
B DATA QUALITY ANALYSIS
The quality analysis combines manual inspection, generated examples, answer-frequency statistics, and discussion of artifacts caused by Freebase data and modeling choices.
- Manual checking of a random sample of 50 final CFQ examples found semantically correct SPARQL queries, while identifying three debatable questions.
- The inspected examples include questions requiring multiple roles, entities, relations, and coordinated actions.
- Other examples combine nested relations, shared entities, possessives, and several interacting film or organization properties.
- Some generated questions contain highly complex combinations of roles, influences, employment, founding, and film-related relations.
- Freebase errors produce implausible role combinations such as entities being both spouses and parents, or both parents and children.
- After “Yes” and “No,” movie-related entities are the most frequent answers in CFQ.
- Freebase modeling choices can create unnatural phrasing by representing a country and its government, or a person and a film character, with the same entity.
C DATA DISTRIBUTION ANALYSIS
The distribution analysis examines answer frequencies and how subsampling changes question, rule, and rule-combination distributions.
- Movie-related entities have the highest answer frequencies in CFQ after the answers “Yes” and “No.”
- Subsampling makes the distribution of questions across complexity levels more even.
- Subsampling increases the frequency of rarely used rules and rule combinations while reducing the frequency of commonly used ones.
- Figure 4 compares rule occurrence ratios before and after subsampling, while Figure 5 makes the same comparison for rule combinations.
D.1 QUALITATIVE ANALYSIS OF MCD1
MCD1 examples look similar across training and test despite substantial differences in how compounds are distributed. The analysis contrasts aligned atom frequencies with highly divergent compound frequencies.
- Qualitative properties: MCD1 train and test examples are not easily distinguished by observable surface properties.Divergence-based splits make examples look fairly similar rather than separating them by an immediately visible criterion such as length.
- Atom and compound distributions: Atom frequencies are closely aligned between train and test, and every test atom also appears in training.Figure 6 indexes atoms by train frequency and then test frequency.
- Atom and compound distributions: Compound frequencies are highly misaligned: most compounds occur exclusively in either the training or test set.Some compounds occur in both sets, but their frequencies often differ substantially.
- Interpretation: The examples illustrate that MCD1 changes compound combinations while preserving the component atoms needed to form them.The split’s intended distinction is between similar atom distributions and different compound distributions.
- Analysis materials: The section documents the MCD1 qualitative analysis alongside figures, hyperparameters, and error-type summaries.Table 6 summarizes non-default hyperparameters, while Table 7 categorizes CFQ errors into clause, filter, and malformed-query types.
F.2 QUALITATIVE ERROR ANALYSIS
The error analysis examines cases where systems fail despite training exposure to relevant subqueries and compositional patterns. Failures include incorrect relation composition and omitted relations in generated SPARQL.
- Scope: About 5k instances were selected where all machine learning systems failed in every replicated run.These cases were drawn from a total test set of about 12k instances.
- Query 1: In one example, the inferred query misinterprets “What sibling of M0 was M1’s parent?” as asking about a sibling of M1’s parent.The analysis states that the generated query’s meaning is incorrect.
- Query 1: The relevant subqueries appeared frequently during training even though the exact combined query did not.“Sibling of Mx” and “Mx’s parent” occurred 2,331 and 1,222 times, respectively.
- Query 2: In another example, the system omitted the relation connecting the director to movie M1.Its inferred query asks whether a male director edited M0 and directed M0 and M1, rather than preserving the intended structure.
- Query 2: Separate conjunction patterns occurred often in training, but their required combination never occurred together.The two component patterns occurred 1,432 and 909 times, respectively.
G ADDITIONAL EXPERIMENTAL RESULTS ON SCAN
Additional SCAN experiments confirm that accuracy depends strongly on compound divergence, while different split designs produce distinct performance patterns. Training exposure to a primitive’s combinations is especially consequential.
- Divergence relationship: Accuracy shows a strong dependency on compound divergence across the existing SCAN splits.The analysis reports that accuracy drops faster with increasing compound divergence in these targeted experiments.
- Primitive splits: The “primitive<jump>” experiment gives systems the jump command alone in training but tests it in arbitrary combinations.All three systems achieve very low accuracy on this experiment.
- Primitive splits: The “primitive<jump>” split has atom divergence 0.08, whereas “primitive<turn left>” has atom divergence 0.07.The turn-left experiment also has lower compound divergence and covers 94% rather than 63% of the data in training.
- Split-specific results: All three systems reach 100% accuracy on the fewshot task with one example, while both transformer models reach 0% on the length split.The LSTM reaches around 14% on the length split.
- Comparison with prior work: The primitive-task results largely match earlier reports, but the fewshot and length results differ from previously reported architecture-specific outcomes.The comparison is made with Lake & Baroni (2018) and Loula et al. (2018).
H ANALYSIS OF RELATIONS BETWEEN ACCURACY, COMPOUND DIVERGENCE, AND TRAINING SIZE
Accuracy is strongly related to compound divergence across CFQ and SCAN and across training sizes, although larger training sets generally improve accuracy. The gains flatten at larger dataset sizes.
- Accuracy and divergence: Accuracy and compound divergence show a strong correlation for all baseline systems at 96k CFQ samples and 8k SCAN samples.The relationship also holds at smaller training sizes, where accuracy is generally lower.
- Accuracy and divergence: The correlation between accuracy and compound divergence persists when training sizes are reduced.Figures 8 and 9 examine CFQ and SCAN across different training sizes.
- Training size: Accuracy gains from increasing training size flatten around 80k samples for CFQ and 6k samples for SCAN.The difference between accuracies at various training sizes also becomes smaller as training size increases.
- Logical-form representation: The dataset represents logical forms using concepts and roles, including conjunction, existential restriction, and specialized constructors.Roles are represented in the form RolePair(C1, C2).
- Grammar representation: CFQ uses recursive unification-based grammar rules to generate question–logical-form pairs and their corresponding queries.The grammar supports feature-based rewriting with logical forms attached to rule components.