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:
- Underspecification: Models are not exposed to enough variety to learn the true boundaries of a program's logic.
- 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.
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.
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