Unobserved Local Structures Make Compositional Generalization Hard

Ben Bogin, Shivanshu Gupta, Jonathan Berant

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.

  1. Defining Local Structures: An $n$-LS is a connected sub-graph of size $n$ (typically 2 to 4 nodes).
  2. The Decision Rule: A test instance is predicted to be "hard" if it contains at least one local structure never seen during training.
  3. Similarity Relaxation: Not all unseen structures are equally difficult. If a model has seen all(find(dog)) but not exists(find(dog)), it may still generalize if exists and all appear in similar contexts. The authors use a distributional similarity metric to quantify this "logical analogy" capability.
Figure 1: Models succeed on unobserved structures if they are similar to observed ones (Split 1), but fail when structures are entirely novel (Split 2).

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.

Figure 5: Comparison of test accuracy across different training budgets, showing that $n$-LS based sampling (Ours) outperforms random sampling.

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

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.
BibTeX
@inproceedings{bogin2022unobserved,
  author = {Ben Bogin and Shivanshu Gupta and Jonathan Berant},
  title = {{Unobserved Local Structures Make Compositional Generalization Hard}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2022},
  url = {https://openreview.net/forum?id=Qi0UGaOlbaS},
}
Figure