Introduction
State-of-the-art language models frequently fail to generalize to new combinations of known concepts, a challenge known as compositional generalization. In semantic parsing—the task of mapping natural language (e.g., "Which flights leave from NYC to Miami?") into executable code—models often struggle when the test distribution shifts from the training data. This research identifies the "unit of failure" in these models: unobserved local structures ($n$-LS). By analyzing specific small patterns in output programs, we can accurately predict which test examples will cause a model to fail.
The $n$-LS Framework
The core hypothesis is that a program's difficulty is determined by its local structural components. Programs are represented as graphs where nodes are functions or entities, and edges represent parent-child or sibling relationships.
- Defining Local Structures: An $n$-LS is a connected sub-graph of size $n$ (typically 2 to 4 nodes).
- The Decision Rule: A test instance is predicted to be "hard" if it contains at least one local structure never seen during training.
- Similarity Relaxation: Not all unseen structures are equally difficult. If a model has seen
all(find(dog))but notexists(find(dog)), it may still generalize ifexistsandallappear in similar contexts. The authors use a distributional similarity metric to quantify this "logical analogy" capability.
Key Insights
- Model Agnosticism: Different architectures like T5, BART, and LSTMs consistently succeed or fail on the same instances. This suggests that hardness is an inherent property of the data and the logical task rather than a specific model flaw.
- Local vs. Global Complexity: Models do not fail because a program is long or complex in its entirety; they fail at specific, tiny "junctions" (2-node or 3-node sub-graphs) that were absent from training.
- Structure Over Sequence: Predicting difficulty based on graph-based local structures is significantly more accurate than using simple token $n$-grams, highlighting that the logical hierarchy matters more than token order.
Experimental Results
The $n$-LS decision rule demonstrated high predictive power, achieving an AUC between 78.4 and 93.3 across five benchmarks (COVR, Overnight, Schema2QA, and ATIS). To further validate the theory, the researchers created adversarial "Grammar Splits" by holding out specific local structures. On the COVR dataset, model accuracy plummeted from 94.6% on standard splits to just 19.7% on these adversarial splits.
Beyond predicting failure, the $n$-LS framework enables Efficient Sampling. By selecting training examples that cover the widest variety of local structures, models can achieve superior generalization with a significantly smaller training budget.
Conclusion and Future Work
This research pinpoints unobserved local structures as the primary driver of failure in compositional generalization. While the current metric focuses on the output program, future work could incorporate the natural language utterance to account for linguistic ambiguity. These findings suggest that "structural data augmentation"—generating training data to fill specific structural gaps—could be a powerful path toward more robust semantic parsers.
Summary updated