Improving Compositional Generalization in Classification Tasks via Structure Annotations

Juyong Kim, Pradeep Ravikumar, Joshua Ainslie, Santiago Ontañón

Abstract: Compositional generalization is the ability to generalize systematically to a new data distribution by combining known components. Although humans seem to have a great ability to generalize compositionally, state-of-the-art neural models struggle to do so. In this work, we study compositional generalization in classification tasks and present two main contributions. First, we study ways to convert a natural language sequence-to-sequence dataset to a classification dataset that also requires compositional generalization. Second, we show that providing structural hints (specifically, providing parse trees and entity links as attention masks for a Transformer model) helps compositional generalization.

Introduction

Neural networks frequently struggle with "compositional generalization"—the capacity to combine known concepts in novel ways. This research demonstrates that by restricting a Transformer’s attention to follow the logical structure of the input, such as parse trees, performance on difficult reasoning tasks can be dramatically improved. This approach achieves near-perfect results in scenarios where standard models typically fail.

Problem Definition

While humans intuitively understand that if "jump" is an action and "twice" denotes repetition, then "jump twice" implies two actions, modern AI often fails this basic test. This failure is a core challenge in compositional generalization. Historically, research has focused on sequence-to-sequence tasks, such as translating natural language into database queries (e.g., SPARQL). However, these tasks are complex due to the requirement of a decoder for text generation. This paper proposes studying this problem within classification tasks (e.g., "Does this query correctly represent this question?") to determine if structural hints can help models ignore irrelevant patterns and focus on underlying logic.

Methodology

The researchers adopted a "less is more" approach, using structure annotations to prune the model's focus rather than increasing parameter count.

  1. ETC Transformer: The Extended Transformer Construction (ETC) model was utilized for its ability to handle structured inputs and custom attention masks.
  2. Hard Masking: This core innovation restricts self-attention to tokens connected via a parse tree or entity links (e.g., linking a specific word in a question to its counterpart in a query), preventing the model from attending to irrelevant tokens.
  3. Soft Masking: As a baseline, "relative attention" was tested, where the model is informed of relationships (like parent-child nodes) without being strictly forbidden from attending elsewhere.
  4. Negative Sampling: To ensure the classification task remained challenging, the authors avoided simple random negatives. Instead, they used "Model Negatives"—incorrect queries generated by other high-performing models (LSTMs and Transformers) that appear plausible but are logically flawed.

Dataset and Evaluation

The study utilizes the CFQ (Compositional Freebase Questions) dataset, a standard benchmark for compositional learning. The authors converted the original generation task into a binary classification dataset. Evaluation was conducted using Maximum Compound Divergence (MCD) splits, where individual atoms in the test set are seen during training, but their combinations (compounds) are entirely novel.

Comparison of negative sampling strategies: random negatives vs. model-based negatives on MCD splits.

Key Insights

  • The Power of Suppression: Hard Masks significantly outperformed Soft Masks. This suggests that Transformers fail not because they lack structural knowledge, but because they cannot ignore "noisy" non-compositional correlations.
  • Structure as the Primary Driver: Simply adding structure tokens to the input string provided minimal benefit. Significant performance gains only occurred when the attention mechanism was forced to respect the structure.
  • Classification as a Diagnostic Tool: By shifting to classification, the authors demonstrated that compositional failure occurs at the encoding stage; the model's internal representation is flawed before generation even begins.

Experimental Results

Results on the difficult MCD split show a massive gap between standard and structure-aware models:

  • Baseline LSTM: ~0.831 AUC
  • Standard Transformer (6 layers): ~0.874 AUC
  • Transformer + Hard Mask + Entity Links: 0.9656 AUC
  • Transformer + Combined Hard/Soft Masks: 0.9721 AUC

Providing a structural "map" allowed the model to solve nearly all compositional puzzles that stumped baselines.

Conclusion and Future Work

Currently, the model relies on "gold" parse trees and entity links. Future work should focus on models that can automatically induce these structures during training. If a model can learn to mask itself effectively, it may bridge the gap between simple pattern matching and true compositional reasoning.

Summary updated

Abstract

Compositional generalization is the ability to generalize systematically to a new data distribution by combining known components. Although humans seem to have a great ability to generalize compositionally, state-of-the-art neural models struggle to do so. In this work, we study compositional generalization in classification tasks and present two main contributions. First, we study ways to convert a natural language sequence-to-sequence dataset to a classification dataset that also requires compositional generalization. Second, we show that providing structural hints (specifically, providing parse trees and entity links as attention masks for a Transformer model) helps compositional generalization.
BibTeX
@inproceedings{kim2021improving,
  author = {Juyong Kim and Pradeep Ravikumar and Joshua Ainslie and Santiago Ontañón},
  title = {{Improving Compositional Generalization in Classification Tasks via Structure Annotations}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2021},
  url = {https://openreview.net/forum?id=LF2a9hoV8G},
}
Figure