# Unobserved Local Structures Make Compositional Generalization Hard

arXiv: https://arxiv.org/abs/2201.05899 · HTML: https://mlsanity.com/paper/2201.05899/

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 30 references that are in the map.
- First posted on arXiv 15 Jan 2022.

## Builds on (most cited first, 24 of 24)

- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [BART: Denoising Sequence-to-Sequence Pre-training for Natural Language Generation, Translation, and Comprehension](https://mlsanity.com/paper/1910.13461/) (2019)
- [Measuring Compositional Generalization: A Comprehensive Method on Realistic Data](https://mlsanity.com/paper/1912.09713/) (2019)
- [COGS: A Compositional Generalization Challenge Based on Semantic Interpretation](https://mlsanity.com/paper/2010.05465/) (2020)
- [Incorporating Copying Mechanism in Sequence-to-Sequence Learning](https://mlsanity.com/paper/1603.06393/) (2016)
- [Good-Enough Compositional Data Augmentation](https://mlsanity.com/paper/1904.09545/) (2019)
- [Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?](https://mlsanity.com/paper/2010.12725/) (2020)
- [Improving Text-to-SQL Evaluation Methodology](https://mlsanity.com/paper/1806.09029/) (2018)
- [The Devil is in the Detail: Simple Tricks Improve Systematic Generalization of Transformers](https://mlsanity.com/paper/2108.12284/) (2021)
- [A Benchmark for Systematic Generalization in Grounded Language Understanding](https://mlsanity.com/paper/2003.05161/) (2020)
- [Compositional Generalization in Semantic Parsing: Pre-training vs. Specialized Architectures](https://mlsanity.com/paper/2007.08970/) (2020)
- [Compositional Generalization via Neural-Symbolic Stack Machines](https://mlsanity.com/paper/2008.06662/) (2020)
- [Span-based Semantic Parsing for Compositional Generalization](https://mlsanity.com/paper/2009.06040/) (2020)
- [Learning to Recombine and Resample Data for Compositional Generalization](https://mlsanity.com/paper/2010.03706/) (2020)
- [CLOSURE: Assessing Systematic Generalization of CLEVR Models](https://mlsanity.com/paper/1912.05783/) (2019)
- [Unlocking Compositional Generalization in Pre-trained Models Using Intermediate Representations](https://mlsanity.com/paper/2104.07478/) (2021)
- [Improving Compositional Generalization in Semantic Parsing](https://mlsanity.com/paper/2010.05647/) (2020)
- [Jump to better conclusions: SCAN both left and right](https://mlsanity.com/paper/1809.04640/) (2018)
- [Finding needles in a haystack: Sampling Structurally-diverse Training Sets from Synthetic Data for Compositional Generalization](https://mlsanity.com/paper/2109.02575/) (2021)
- [COVR: A test-bed for Visually Grounded Compositional Generalization with real images](https://mlsanity.com/paper/2109.10613/) (2021)
- [Genie: A Generator of Natural Language Semantic Parsers for Virtual Assistant Commands](https://mlsanity.com/paper/1904.09020/) (2019)
- [Revisiting Iterative Back-Translation from the Perspective of Compositional Generalization](https://mlsanity.com/paper/2012.04276/) (2020)
- [Latent Compositional Representations Improve Systematic Generalization in Grounded Question Answering](https://mlsanity.com/paper/2007.00266/) (2020)
- [Schema2QA: High-Quality and Low-Cost Q&A Agents for the Structured Web](https://mlsanity.com/paper/2001.05609/) (2020)

## Built on by (most cited first, 29 of 29)

- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [Prompting GPT-3 To Be Reliable](https://mlsanity.com/paper/2210.09150/) (2022)
- [Diverse Demonstrations Improve In-context Compositional Generalization](https://mlsanity.com/paper/2212.06800/) (2022)
- [UnifiedQA-v2: Stronger Generalization via Broader Cross-Format Training](https://mlsanity.com/paper/2202.12359/) (2022)
- [Don't Generate, Discriminate: A Proposal for Grounding Language Models to Real-World Environments](https://mlsanity.com/paper/2212.09736/) (2022)
- [How Do In-Context Examples Affect Compositional Generalization?](https://mlsanity.com/paper/2305.04835/) (2023)
- [Evaluating the Impact of Model Scale for Compositional Generalization in Semantic Parsing](https://mlsanity.com/paper/2205.12253/) (2022)
- [Entity Tracking in Language Models](https://mlsanity.com/paper/2305.02363/) (2023)
- [Uncontrolled Lexical Exposure Leads to Overestimation of Compositional Generalization in Pretrained Models](https://mlsanity.com/paper/2212.10769/) (2022)
- [Structural generalization is hard for sequence-to-sequence models](https://mlsanity.com/paper/2210.13050/) (2022)
- [What's the Meaning of Superhuman Performance in Today's NLU?](https://mlsanity.com/paper/2305.08414/) (2023)
- [Learning to Retrieve Iteratively for In-Context Learning](https://mlsanity.com/paper/2406.14739/) (2024)
- [Benchmarking Compositionality with Formal Languages](https://mlsanity.com/paper/2208.08195/) (2022)
- [CTL++: Evaluating Generalization on Never-Seen Compositional Patterns of Known Functions, and Compatibility of Neural Representations](https://mlsanity.com/paper/2210.06350/) (2022)
- [Induced Natural Language Rationales and Interleaved Markup Tokens Enable Extrapolation in Large Language Models](https://mlsanity.com/paper/2208.11445/) (2022)
- [Leveraging Code to Improve In-context Learning for Semantic Parsing](https://mlsanity.com/paper/2311.09519/) (2023)
- [What Makes Instruction Learning Hard? An Investigation and a New Challenge in a Synthetic Environment](https://mlsanity.com/paper/2204.09148/) (2022)
- [Structurally Diverse Sampling for Sample-Efficient Training and Comprehensive Evaluation](https://mlsanity.com/paper/2203.08445/) (2022)
- [Learning to Substitute Spans towards Improving Compositional Generalization](https://mlsanity.com/paper/2306.02840/) (2023)
- [Compositional Generalisation with Structured Reordering and Fertility Layers](https://mlsanity.com/paper/2210.03183/) (2022)
- [Recursive Neural Networks with Bottlenecks Diagnose (Non-)Compositionality](https://mlsanity.com/paper/2301.13714/) (2023)
- [Understanding Compositional Data Augmentation in Typologically Diverse Morphological Inflection](https://mlsanity.com/paper/2305.13658/) (2023)
- [Beyond Fertility: Analyzing STRR as a Metric for Multilingual Tokenization Evaluation](https://mlsanity.com/paper/2510.09947/) (2025)
- [Laziness Is a Virtue When It Comes to Compositionality in Neural Semantic Parsing](https://mlsanity.com/paper/2305.04346/) (2023)
- [Meta Operator for Complex Query Answering on Knowledge Graphs](https://mlsanity.com/paper/2403.10110/) (2024)
- [Learning to Substitute Components for Compositional Generalization](https://mlsanity.com/paper/2502.20834/) (2025)
- [Reinforcing Compositional Retrieval: Retrieving Step-by-Step for Composing Informative Contexts](https://mlsanity.com/paper/2504.11420/) (2025)
- [Dataflow Dialogue Generation](https://mlsanity.com/paper/2308.02323/) (2023)
- [SetLexSem Challenge: Using Set Operations to Evaluate the Lexical and Semantic Robustness of Language Models](https://mlsanity.com/paper/2411.07336/) (2024)

## Abstract (arXiv)

While recent work has convincingly showed that sequence-to-sequence models struggle to generalize to new compositions (termed compositional generalization), little is known on what makes compositional generalization hard on a particular test instance. In this work, we investigate what are the factors that make generalization to certain test instances challenging. We first substantiate that indeed some examples are more difficult than others by showing that different models consistently fail or succeed on the same test instances. Then, we propose a criterion for the difficulty of an example: a test instance is hard if it contains a local structure that was not observed at training time. We formulate a simple decision rule based on this criterion and empirically show it predicts instance-level generalization well across 5 different semantic parsing datasets, substantially better than alternative decision rules. Last, we show local structures can be leveraged for creating difficult adversarial compositional splits and also to improve compositional generalization under limited training budgets by strategically selecting examples for the training set.