Structurally Diverse Sampling for Sample-Efficient Training and Comprehensive Evaluation

Shivanshu Gupta, Sameer Singh, Matt Gardner

Abstract

A growing body of research has demonstrated the inability of NLP models to generalize compositionally and has tried to alleviate it through specialized architectures, training schemes, and data augmentation, among other approaches. In this work, we study a different approach: training on instances with diverse structures. We propose a model-agnostic algorithm for subsampling such sets of instances from a labeled instance pool with structured outputs. Evaluating on both compositional template splits and traditional IID splits of 5 semantic parsing datasets of varying complexity, we show that structurally diverse training using our algorithm leads to comparable or better generalization than prior algorithms in 9 out of 10 dataset-split type pairs. In general, we find structural diversity to consistently improve sample efficiency compared to random train sets. Moreover, we show that structurally diverse sampling yields comprehensive test sets that are a lot more challenging than IID test sets. Finally, we provide two explanations for improved generalization from diverse train sets: 1) improved coverage of output substructures, and 2) a reduction in spurious correlations between these substructures.

Introduction: The Challenge of Compositional Generalization

Modern NLP models, particularly those used for semantic parsing (translating natural language into code or logic), are notorious for failing to generalize compositionally. They might understand "red ball" and "blue square" in training but stumble when asked to process "red square" at test time.

The authors argue that the culprit is often the training data itself. Standard random sampling (IID) tends to over-represent common patterns and ignore the "long tail" of rare structures. This leads to two major issues: spurious correlations, where models learn "shortcuts" (e.g., always associating the word "black" with the concept "dog" because they only ever appeared together in a small sample), and underspecification, where the model doesn't see enough structural variety to learn the underlying "grammar" of the task.

Methods: Structurally Diverse Subsampling

The researchers propose a model-agnostic, greedy, iterative algorithm for Structurally Diverse Subsampling. Instead of picking instances at random, the algorithm picks instances that contain a wide variety of substructures. The key innovation lies in the choice of substructure granularity. Prior work focused on Bigrams (parent-child pairs) which are too granular to capture complex logic, or Templates (entire program skeletons) which are too coarse and often unique to single instances.

Substructure types extracted from an Abstract Syntax Tree (AST), including bigrams, siblings, and subtrees of various sizes.

This paper advocates for Subtrees (specifically of size $\le 4$) as the "Goldilocks" level of detail. Their algorithm alternates between picking a rare substructure and then picking an instance from the pool that contains it. They also experiment with weighting schemes like FREQNEWT, which prioritizes selecting instances with frequent but currently unsampled templates to balance fine-grained and coarse-grained diversity.

Key Insights and Results

The approach was evaluated across five diverse semantic parsing datasets: COVR, ATIS, Overnight, Schema2QA, and SM-CalFlow. These were tested on both standard IID splits and Template splits, where the test set contains entirely new program structures.

Generalization performance on the SM-CalFlow dataset, comparing structurally diverse sampling against random sampling across different budgets.

The results demonstrate that structurally diverse training sets lead to comparable or better generalization than prior methods in 9 out of 10 dataset-split pairs. Notably, the method achieves up to 2x sample efficiency: in many cases, a model trained on a diversely sampled set of size $N$ performed as well as a model trained on a random set of size $2N$. Unlike bigram or template diversity—which sometimes performed worse than random sampling on IID splits—subtree diversity was consistently robust across different data distributions.

Furthermore, the authors found that diversifying based on subtrees allows the model to see how small components (functions, variables) combine into mid-sized logical blocks. By forcing the training set to be diverse, the algorithm mathematically reduces the "Mutual Information" between substructures, preventing the model from relying on coincidental patterns found in smaller, random datasets.

Comprehensive Evaluation and Benchmarking

Beyond training efficiency, the authors found that using their diversity algorithm to select test sets created much harder benchmarks. Randomly sampled test sets are often "too easy" because they mirror the biases of the training set; structurally diverse test sets provide a more "comprehensive" evaluation of a model's true capabilities. This approach ensures that the "long tail" of the distribution is covered without sacrificing performance on common structures.

Limitations and Future Work

The current method relies on having access to the "programs" or logical forms (ASTs) of the data, meaning it cannot be directly applied to tasks with plain text outputs without an intermediate structural representation. Additionally, the algorithm is a greedy heuristic and may not find the theoretically optimal diverse subset for a given budget. Future research could explore "linguistic diversity" in the input (natural language) to further improve efficiency, especially in zero-data or few-shot settings.

Summary updated

Abstract

A growing body of research has demonstrated the inability of NLP models to generalize compositionally and has tried to alleviate it through specialized architectures, training schemes, and data augmentation, among other approaches. In this work, we study a different approach: training on instances with diverse structures. We propose a model-agnostic algorithm for subsampling such sets of instances from a labeled instance pool with structured outputs. Evaluating on both compositional template splits and traditional IID splits of 5 semantic parsing datasets of varying complexity, we show that structurally diverse training using our algorithm leads to comparable or better generalization than prior algorithms in 9 out of 10 dataset-split type pairs. In general, we find structural diversity to consistently improve sample efficiency compared to random train sets. Moreover, we show that structurally diverse sampling yields comprehensive test sets that are a lot more challenging than IID test sets. Finally, we provide two explanations for improved generalization from diverse train sets: 1) improved coverage of output substructures, and 2) a reduction in spurious correlations between these substructures.
BibTeX
@inproceedings{gupta2022structurally,
  author = {Shivanshu Gupta and Sameer Singh and Matt Gardner},
  title = {{Structurally Diverse Sampling for Sample-Efficient Training and Comprehensive Evaluation}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2022},
  doi = {10.18653/v1/2022.findings-emnlp.365},
}
Figure