Abstract
While recent work has convincingly showed that sequence-to-sequence models struggle to generalize to new compositions (termed compositional generalization), little is known on what makes compositional generalization hard on a particular test instance. In this work, we investigate what are the factors that make generalization to certain test instances challenging. We first substantiate that indeed some examples are more difficult than others by showing that different models consistently fail or succeed on the same test instances. Then, we propose a criterion for the difficulty of an example: a test instance is hard if it contains a local structure that was not observed at training time. We formulate a simple decision rule based on this criterion and empirically show it predicts instance-level generalization well across 5 different semantic parsing datasets, substantially better than alternative decision rules. Last, we show local structures can be leveraged for creating difficult adversarial compositional splits and also to improve compositional generalization under limited training budgets by strategically selecting examples for the training set.
Introduction
In semantic parsing, AI models translate natural language into executable code. While these models often achieve high performance on data similar to their training sets, they frequently fail when encountering new combinations of known concepts—a phenomenon known as the "compositional generalization" gap. This research investigates the fundamental drivers of instance-level difficulty, moving beyond dataset-wide metrics to explain why specific test examples trigger model failure.
The Local Structure Hypothesis
The core proposal is that programs should be viewed as graphs where nodes represent functions or values, and edges represent their logical relationships. The researchers define n-LS (Local Structures) as small connected sub-graphs of size $n$ (typically 2, 3, or 4).
A test instance is hypothesized to be "easy" if all its local structures were either observed during training or are highly similar to observed ones. Similarity is determined via a distributional metric; for instance, if a model has seen all -> filter but not exists -> filter, it may still succeed if exists and all appear in similar logical contexts. Conversely, the presence of even a single completely "unobserved" local building block often leads to failure, regardless of the sentence length or the model's architecture.
Experimental Methodology
The study evaluated five diverse semantic parsing datasets to ensure domain-agnostic findings:
- COVR: Synthetic visual question answering.
- Overnight: A mix of synthetic and natural language paraphrases.
- Schema2QA: Synthetic queries using the ThingTalk language.
- ATIS: Real-world natural language questions about flight information.
Experiments involved testing multiple architectures, including T5, BART, and LSTMs, to determine if difficulty is a property of the model or the data split.
Results and Discussion
Model Agreement and Predictive Power
A striking finding is that different models tend to succeed or fail on the same examples. The proposed $n$-LS decision rule predicted instance-level difficulty with an AUC between 78.4 and 93.3 across all datasets, significantly outperforming traditional text-based metrics like n-grams.
Adversarial Hardness and Strategic Training
By intentionally creating splits that maximize unobserved local structures, the researchers could drop model accuracy on the COVR dataset from ~94% to as low as ~20%. However, this insight also provides a path toward more efficient training. By strategically selecting training examples that cover the maximum number of unique local structures, models can achieve superior generalization even with a limited training budget.
Conclusion
This work demonstrates that unobserved local structures are a primary driver of difficulty in compositional generalization. While current models are sensitive to these missing building blocks, identifying them allows for better performance prediction and more robust dataset design. Future research may focus on incorporating these structural insights directly into model architectures to handle novel compositions more effectively.
Summary updated