Structurally Diverse Sampling for Sample-Efficient Training and Comprehensive Evaluation

Shivanshu Gupta, Sameer Singh, Matt Gardner

Introduction

Semantic parsing—the task of translating natural language utterances into formal machine-executable programs—is a cornerstone of modern human-computer interaction. However, state-of-the-art models often struggle with "compositional generalization," failing to correctly combine known primitives into novel structures. This paper argues that the standard practice of random data sampling is a primary driver of this failure. By introducing Structurally Diverse Subsampling (SDS), the authors demonstrate that prioritizing the structural variety of training examples can lead to more robust models and more rigorous evaluation metrics.

The Challenge of Random Sampling

Standard random sampling often results in a training distribution that is heavily skewed toward common patterns, leaving a "long tail" of rare but important structures underrepresented. This imbalance leads to two major issues:

  1. Underspecification: Models are not exposed to enough variety to learn the true boundaries of a program's logic.
  2. Spurious Correlations: Models may learn accidental statistical shortcuts (e.g., always associating a specific verb with a specific entity type) rather than the underlying compositional rules.

Methodology: Structurally Diverse Subsampling

The core of the proposed approach is an iterative, model-agnostic algorithm designed to maximize the variety of substructures in the training set. The researchers identify subtrees of the program's Abstract Syntax Tree (AST) as the optimal unit of diversity.

An illustration of how a natural language input and its corresponding program are decomposed into an Abstract Syntax Tree (AST) and further into bigrams, siblings, and subtrees.

As shown in the figure above, subtrees provide a "Goldilocks" level of granularity. While "templates" (the entire program shape) are often too unique and "bigrams" (parent-child pairs) are too common, subtrees of size 3 or 4 effectively capture the meaningful reasoning patterns within a program. The SDS algorithm greedily selects instances that contain the most frequent unseen subtrees, ensuring the training set is both diverse and representative.

Experimental Evaluation

The authors evaluated SDS across five diverse datasets, including ATIS (flight queries) and SM-CalFlow (complex calendar tasks). They tested performance on two types of data splits:

  • IID Splits: Standard random test sets.
  • Subtree Splits: Challenging test sets containing structural patterns not seen during training.

Key Results and Sample Efficiency

The results consistently show that structurally diverse training matches or outperforms random sampling in 9 out of 10 dataset-split combinations. One of the most significant findings is the improvement in sample efficiency. In many instances, models trained on diverse data achieved the same accuracy as those trained on random data while requiring only half the total training budget.

Performance comparison on SM-CalFlow across different training budgets. Subtree-based sampling (blue) consistently outperforms random sampling (orange), especially on the more difficult Subtree split (dashed lines).

Furthermore, the authors used Mutual Information (MI) analysis to confirm that SDS effectively breaks spurious correlations. By forcing the model to encounter primitives in a wide variety of contexts, the model is compelled to learn the true semantic logic rather than relying on statistical "cheating."

Conclusion

This research highlights that the quality and structural composition of training data are just as critical as the quantity. By focusing on subtree diversity, researchers can build semantic parsers that generalize better to complex, real-world inputs with significantly less data. Additionally, the paper advocates for using diverse sampling to create more rigorous "Subtree-sampled" test sets, providing a more honest assessment of a model's true compositional capabilities.

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