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
In semantic parsing—the task of translating natural language into machine-executable code or logical forms—models frequently struggle with compositional generalization. While they may learn individual components, they often fail when these components are combined in novel ways. The authors argue that standard random sampling is a primary culprit, as it often results in "skewed distributions" where certain structures appear together frequently by coincidence. Models then learn these spurious correlations rather than the underlying logic, leading to high variance and poor performance on out-of-distribution (OOD) data.
Methodology: Structurally Diverse Subsampling
The core contribution is a model-agnostic, greedy iterative algorithm for Structurally Diverse Subsampling. The method focuses on the granularity of program substructures to find a "Goldilocks" zone of structural information.
- Substructure Granularity: While previous work focused on "bigrams" (too fine-grained) or "templates" (too coarse), this paper utilizes subtrees of the program’s Abstract Syntax Tree (AST) up to a depth of $d=4$.
- The Algorithm: The algorithm alternates between identifying a frequent substructure in the overall pool that hasn't been sampled yet and selecting a specific instance from the pool that contains that substructure.
- Weighting Schemes: The researchers experimented with schemes like
FREQNEWT, which prioritizes examples with the most frequent unsampled templates to ensure both fine-grained and coarse-grained diversity.
Experimental Evaluation
The method was evaluated across five diverse semantic parsing datasets: COVR (visually grounded queries), ATIS (flight information), Overnight (multi-domain Lambda-DCS), Schema2QA (ThingTalk web queries), and SM-CalFlow (large-scale task-oriented dialogues).
Results and Discussion
The results demonstrate that structurally diverse training significantly improves sample efficiency and model robustness.
- Superior Sample Efficiency: Structurally diverse training outperformed random sampling in 9 out of 10 dataset-split combinations. In many scenarios, diverse training sets achieved the same accuracy as random sets while using only half the data.
- Reducing Spurious Correlations: By measuring Average Mutual Information (AMI), the authors proved that diverse sampling weakens accidental bonds between substructures, forcing the model to learn true compositional rules.
- Comprehensive Evaluation: Using the algorithm to create test sets resulted in benchmarks that were significantly more challenging than standard IID tests, providing a more rigorous assessment of true model capabilities.
Conclusion
Structurally diverse sampling offers a powerful, model-agnostic way to improve the sample efficiency and generalization of semantic parsers. While the current method requires a pool of labeled programs and relies on a greedy heuristic, it highlights the importance of output structure in training data selection. Future work may explore simultaneous diversification of natural language inputs to further enhance linguistic robustness.
Summary updated