# Finding needles in a haystack: Sampling Structurally-diverse Training Sets from Synthetic Data for Compositional Generalization

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 48 references that are in the map.
- First posted on arXiv 6 Sep 2021.

## Builds on (most cited first, 30 of 38)

- [BART: Denoising Sequence-to-Sequence Pre-training for Natural Language Generation, Translation, and Comprehension](https://mlsanity.com/paper/1910.13461/) (2019)
- [Green AI](https://mlsanity.com/paper/1907.10597/) (2019)
- [TaBERT: Pretraining for Joint Understanding of Textual and Tabular Data](https://mlsanity.com/paper/2005.08314/) (2020)
- [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)
- [WinoGrande: An Adversarial Winograd Schema Challenge at Scale](https://mlsanity.com/paper/1907.10641/) (2019)
- [GraPPa: Grammar-Augmented Pre-Training for Table Semantic Parsing](https://mlsanity.com/paper/2009.13845/) (2020)
- [Beyond I.I.D.: Three Levels of Generalization for Question Answering on Knowledge Bases](https://mlsanity.com/paper/2011.07743/) (2020)
- [Adversarial Filters of Dataset Biases](https://mlsanity.com/paper/2002.04108/) (2020)
- [Good-Enough Compositional Data Augmentation](https://mlsanity.com/paper/1904.09545/) (2019)
- [REPAIR: Removing Representation Bias by Dataset Resampling](https://mlsanity.com/paper/1904.07911/) (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)
- [Structure-Grounded Pretraining for Text-to-SQL](https://mlsanity.com/paper/2010.12773/) (2020)
- [Data Recombination for Neural Semantic Parsing](https://mlsanity.com/paper/1606.03622/) (2016)
- [Compositional generalization through meta sequence-to-sequence learning](https://mlsanity.com/paper/1906.05381/) (2019)
- [Compositional Generalization in Semantic Parsing: Pre-training vs. Specialized Architectures](https://mlsanity.com/paper/2007.08970/) (2020)
- [Span-based Semantic Parsing for Compositional Generalization](https://mlsanity.com/paper/2009.06040/) (2020)
- [Grounded Adaptation for Zero-shot Executable Semantic Parsing](https://mlsanity.com/paper/2009.07396/) (2020)
- [Sequence-Level Mixed Sample Data Augmentation](https://mlsanity.com/paper/2011.09039/) (2020)
- [Learning to Recombine and Resample Data for Compositional Generalization](https://mlsanity.com/paper/2010.03706/) (2020)
- [Meta-Learning to Compositionally Generalize](https://mlsanity.com/paper/2106.04252/) (2021)
- [Unlocking Compositional Generalization in Pre-trained Models Using Intermediate Representations](https://mlsanity.com/paper/2104.07478/) (2021)
- [Compositional Generalization by Learning Analytical Expressions](https://mlsanity.com/paper/2006.10627/) (2020)
- [Environmental drivers of systematicity and generalization in a situated agent](https://mlsanity.com/paper/1910.00571/) (2019)
- [Compositional Generalization for Primitive Substitutions](https://mlsanity.com/paper/1910.02612/) (2019)
- [Improving Compositional Generalization in Semantic Parsing](https://mlsanity.com/paper/2010.05647/) (2020)
- [Learning to Synthesize Data for Semantic Parsing](https://mlsanity.com/paper/2104.05827/) (2021)
- [Compositional Generalization via Semantic Tagging](https://mlsanity.com/paper/2010.11818/) (2020)
- [AutoQA: From Databases To QA Semantic Parsers With Only Synthetic Training Data](https://mlsanity.com/paper/2010.04806/) (2020)

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

- [Diverse Demonstrations Improve In-context Compositional Generalization](https://mlsanity.com/paper/2212.06800/) (2022)
- [State-of-the-art generalisation research in NLP: A taxonomy and review](https://mlsanity.com/paper/2210.03050/) (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)
- [Improving Compositional Generalization with Latent Structure and Data Augmentation](https://mlsanity.com/paper/2112.07610/) (2021)
- [Unobserved Local Structures Make Compositional Generalization Hard](https://mlsanity.com/paper/2201.05899/) (2022)
- [SPINACH: SPARQL-Based Information Navigation for Challenging Real-World Questions](https://mlsanity.com/paper/2407.11417/) (2024)
- [ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis](https://mlsanity.com/paper/2307.13883/) (2023)
- [Learning to Retrieve Iteratively for In-Context Learning](https://mlsanity.com/paper/2406.14739/) (2024)
- [The Validity of Evaluation Results: Assessing Concurrence Across Compositionality Benchmarks](https://mlsanity.com/paper/2310.17514/) (2023)
- [Leveraging Code to Improve In-context Learning for Semantic Parsing](https://mlsanity.com/paper/2311.09519/) (2023)
- [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)
- [Dyna-bAbI: unlocking bAbI's potential with dynamic synthetic benchmarking](https://mlsanity.com/paper/2112.00086/) (2021)
- [Paraphrasing Techniques for Maritime QA system](https://mlsanity.com/paper/2203.10854/) (2022)
- [Learning to Generalize Compositionally by Transferring Across Semantic Parsing Tasks](https://mlsanity.com/paper/2111.05013/) (2021)
- [Compositional Generalization and Decomposition in Neural Program Synthesis](https://mlsanity.com/paper/2204.03758/) (2022)
- [A Study on Training and Developing Large Language Models for Behavior Tree Generation](https://mlsanity.com/paper/2401.08089/) (2024)
- [Active Learning for Multilingual Semantic Parser](https://mlsanity.com/paper/2301.12920/) (2023)
- [Understanding Compositional Data Augmentation in Typologically Diverse Morphological Inflection](https://mlsanity.com/paper/2305.13658/) (2023)
- [Attribute Diversity Determines the Systematicity Gap in VQA](https://mlsanity.com/paper/2311.08695/) (2023)
- [Layer-wise Representation Fusion for Compositional Generalization](https://mlsanity.com/paper/2307.10799/) (2023)
- [A Taxonomy of Transcendence](https://mlsanity.com/paper/2508.17669/) (2025)
- [Learning to Substitute Components for Compositional Generalization](https://mlsanity.com/paper/2502.20834/) (2025)
- [A Short Survey of Systematic Generalization](https://mlsanity.com/paper/2211.11956/) (2022)
- [Differentially Private Non Parametric Copulas: Generating synthetic data with non parametric copulas under privacy guarantees](https://mlsanity.com/paper/2409.18611/) (2024)
- [A Diversity Diet for a Healthier Model: A Case Study of French ModernBERT](https://mlsanity.com/paper/2602.22014/) (2026)

## Abstract (arXiv)

Modern semantic parsers suffer from two principal limitations. First, training requires expensive collection of utterance-program pairs. Second, semantic parsers fail to generalize at test time to new compositions/structures that have not been observed during training. Recent research has shown that automatic generation of synthetic utterance-program pairs can alleviate the first problem, but its potential for the second has thus far been under-explored. In this work, we investigate automatic generation of synthetic utterance-program pairs for improving compositional generalization in semantic parsing. Given a small training set of annotated examples and an "infinite" pool of synthetic examples, we select a subset of synthetic examples that are structurally-diverse and use them to improve compositional generalization. We evaluate our approach on a new split of the schema2QA dataset, and show that it leads to dramatic improvements in compositional generalization as well as moderate improvements in the traditional i.i.d setup. Moreover, structurally-diverse sampling achieves these improvements with as few as 5K examples, compared to 1M examples when sampling uniformly at random -- a 200x improvement in data efficiency.