PaperlayerView exact revision on arXiv

Source-linked AI summary

Diverse Demonstrations Improve In-context Compositional Generalization

Itay Levy, Ben Bogin, Jonathan Berant

arXiv:2212.06800v3cs.CL

TL;DR

Similarity-based demonstrations are often insufficient for semantic parsing under compositional generalization, where test programs contain structures absent from training. The paper selects diverse demonstrations to cover target-program structures and finds improvements across three datasets, both with and without finetuning.

  • Problem

    Similarity-based demonstration retrieval is insufficient when compositional test programs contain structures absent from training data.

  • Method

    The paper selects diverse demonstrations using coverage of predicted program structures or utterance words, and also evaluates selecting mutually dissimilar examples.

  • Results

    Diverse demonstrations improve performance by up to 23 absolute points, including 50.3 →73.5 on SMCalFlow-CS, across pure in-context learning and finetuning setups.

  • Takeaways & Limitations

    Choosing demonstrations for structural coverage improves compositional generalization, reduces the demonstrations needed, and improves performance on hard examples.

  • Takeaways & Limitations

    The approach assumes diversity is obtained through program structures and does not consider more complex utterance features for broader language-understanding tasks.

Abstract

from arXiv · show

In-context learning has shown great success in i.i.d semantic parsing splits, where the training and test sets are drawn from the same distribution. In this setup, models are typically prompted with demonstrations that are similar to the input utterance. However, in the setup of compositional generalization, where models are tested on outputs with structures that are absent from the training set, selecting similar demonstrations is insufficient, as often no example will be similar enough to the input. In this work, we propose a method to select diverse demonstrations that aims to collectively cover all of the structures required in the output program, in order to encourage the model to generalize to new structures from these demonstrations. We empirically show that combining diverse demonstrations with in-context learning substantially improves performance across three compositional generalization semantic parsing datasets in the pure in-context learning setup and when combined with finetuning.

1 Introduction

The paper argues that similarity-based demonstration retrieval is insufficient for compositional generalization and proposes selecting diverse demonstrations that collectively cover target-program structures. Across pure in-context learning and finetuning setups, this approach improves semantic parsing performance.

  • Motivation: Compositional generalization requires models to process novel combinations of previously observed elements, which similarity-based demonstrations may not adequately support.In semantic parsing, these combinations can form formal queries absent from annotated training data.
  • Approach: The paper optimizes the entire demonstration set by increasing example diversity through coverage-based selection or input-independent dissimilarity.Coverage-based selection targets elements such as potential output-program substructures.
  • Approach: The framework supports pure in-context learning and finetuning, using demonstrations as part of the model input in the latter setup.The finetuning formulation is described as meta-learning because the model learns to use demonstrations during training and inference.
  • Results: Diverse demonstrations improve performance by up to 23 absolute points, from 50.3 to 73.5 on SMCalFlow-CS, versus similarity-only retrieval.The improvements hold with and without finetuning and produce state-of-the-art results in multiple compositional setups.

2 Diversity for Compositional Generalization

The paper frames compositional generalization as requiring demonstrations that cover structures in expected output programs. It motivates covering larger structures because this can reduce novel structure production and expose compositions across contexts.

  • Setting: Compositional splits are dataset splits where training and test programs do not overlap.Prior work increased training-set structure diversity through augmentation or diverse sampling, whereas this paper targets demonstration-set diversity during in-context learning.
  • Why coverage matters: Demonstrations should cover all structures of the expected output program, including required predicates and logical operators.This is especially relevant when few-shot models are unfamiliar with the output programs’ formal language.
  • Why coverage matters: Covering larger program subtrees may reduce new structures the model must produce and expose structure compositions in different data contexts.These effects are presented as reasons larger structures may be more beneficial than smaller ones.

3 Diverse Demonstrations Selection

The framework selects a small prompt set of demonstrations that balances relevance with structural coverage or explicit diversity, then uses those demonstrations for in-context semantic parsing. It supports coverage-based selection, dissimilarity-based selection, prompt construction, and finetuning integration, while addressing over-copying during meta-learning.

  • Problem setup: The setup selects k ≪ n training utterance-program pairs as demonstrations, formats them into a prompt, and concatenates that prompt with the test utterance.The model receives [P; xtest] and produces ytest.
  • Selection framework: The framework offers coverage-based selection and minimal-similarity selection to obtain diverse demonstrations for compositional generalization.Coverage may target predicted program local structures or input-utterance words; the alternative selects mutually dissimilar examples.
  • Coverage-based selection: Cover-LS predicts likely local structures with an auxiliary model, then retrieves examples that collectively cover those structures while remaining similar to the test utterance.Local structures are subtrees or connected subgraphs of the program tree, and larger structures are prioritized during selection.
  • Coverage-based selection: Cover-LS iteratively updates the uncovered-structure pool, removes examples sharing a chosen template, and continues until the desired number of demonstrations is reached.The retriever can be BM25 or SBERT, and the implementation removes examples with the same anonymized program template as selected examples.
  • Coverage-based selection: Cover-Utt uses the same coverage algorithm to cover words in the input utterance without an auxiliary local-structure prediction model.This variant is beneficial when the auxiliary model produces low-quality local-structure predictions.
  • Diversity without coverage: DPP selects relevant and diverse demonstrations using retriever relevance scores and cosine similarity between tf-idf representations of extracted local structures.Chosen demonstrations are ordered by retriever score for prompting, and the framework can be combined with finetuning for meta-learning.

4 Experiments

Experiments across three compositional semantic parsing datasets evaluate diverse demonstration selection with and without finetuning. Diversity-based methods generally outperform similarity-only retrieval, improve generalization with fewer demonstrations, and perform better on harder examples.

  • Datasets and setup: Experiments cover three datasets, including SMCalFlow-CS, GeoQuery, and the ten compositional splits of COVR-10, using NoFT and FT settings.SMCalFlow-CS includes cross-domain compositional and i.i.d. splits; GeoQuery includes template and TMCD compositional splits.
  • NoFT results: In the NoFT setup, Cover-Utt, DPP, and Cover-LS outperform similarity-based Top-K in 7 out of 8 compositional splits.The diversity methods also outperform an oracle Top-K in these settings, suggesting similarity-only retrieval is sub-optimal even with oracle access.
  • Comparing diversity methods: Cover-LS and Cover-Utt outperform DPP in 7 out of 10 splits, indicating that covering target input or program elements helps beyond selecting merely dissimilar examples.Cover-LS fails on the 0-C split when the T5 local-structure predictor has zero baseline accuracy; Cover-Utt is presented as a viable alternative when local structures cannot be predicted reliably.
  • Number of demonstrations: Cover-LS achieves roughly the same NoFT results with four demonstrations as Top-K with 24 demonstrations.The comparison also shows that covering local structures is more important than covering only program symbols or utterance words, especially with small prompts.
  • FT results: In the FT setup, training with Cover-LS1 and testing with Cover-LS yields higher performance on all compositional splits than Top-K or random-sampling baselines.Using Top-K at both training and test time performs poorly on compositional splits but well on i.i.d. splits, while Cover-LS1 at both stages is comparable to the main method.
  • Analysis: Cover-LS and DPP produce substantially more unique local structures than Top-K, while Cover-LS outperforms Top-K across retriever settings and helps most on harder examples.The examples where Cover-LS alone succeeds have lower T5 accuracy and more unseen local structures; both methods fail on examples with low T5 accuracy and high unseen-local-structure rates.

5 Related Work

Prior demonstration-selection work often optimized examples individually, while this paper builds on approaches that model diversity, coverage, or structure similarity for compositional generalization.

  • Earlier retrieval studies selected examples independently, which can produce prompts lacking coverage and diversity.
  • The paper's retrieval procedure predicts local structures and retrieves demonstrations covering them, rather than using tf-idf over predicted program tokens.
  • DPP and autoregressive selection methods promoted diversity independently of prompting, alongside confidence-based and maximum-marginal-relevance strategies.
  • Figure 5 compares accuracy across retrievers when demonstrations are selected using Top-K or Cover-LS.
  • Some prior compositional-generalization methods considered target coverage or structure similarity only in oracle settings.

6 Conclusion

The paper finds that structurally covering demonstrations improves compositional generalization in semantic parsing across pure in-context learning and finetuned settings. It also reduces the demonstrations needed for generalization and improves performance on hard examples.

  • Structural coverage substantially improves performance across three compositional semantic parsing datasets in both pure in-context learning and finetuned setups.
  • Aiming for structural coverage reduces the number of demonstrations needed for generalization and improves test performance on hard examples.
  • The approach may apply to NLP tasks where demonstrations should cover complementary aspects of the task.

Limitations

The method relies on assumptions about which features provide useful diversity, prioritizes recall over precision, and uses retrievers selected separately for NoFT and FT settings.

  • The method assumes that diversity can be obtained from different program structures and does not consider more complex utterance features.
  • The Cover-LS algorithm prioritizes recall by covering every predicted local structure without predicting which structures should actually be covered.
  • Increasing gold structure coverage with additional beam candidates could be improved by search methods specifically targeted for diversity.
  • Different retrievers were used for NoFT and FT setups based on development-set performance, leaving the reason for their differing preferences open.

Ethics Statement

The work evaluates diverse-demonstration methods for compositional generalization on English semantic parsing datasets, while expressing hope for future benefits in underrepresented languages.

  • The methods were evaluated only on semantic parsing datasets in English.
  • The authors hope improved compositional generalization will eventually help systems generalize to languages underrepresented in small training sets.

A Additional Analysis

The analysis characterizes prediction errors across demonstration-selection methods and reports that increased diversity reduces over-copying in SMCalFlow-CS.

  • Error analysis: DPP-based diversity significantly decreases over-copying, particularly in SMCalFlow-CS.Over-copying occurs when the prediction has the same anonymized form as a demonstration.
  • Error analysis: Syntax errors are rare across both evaluated datasets, while nearly all incorrect predictions contain a missing symbol.Top-K predictions are especially prone to missing-symbol errors.
  • Error analysis: GeoQuery produces more out-of-vocabulary hallucinations than SMCalFlow-CS despite having a smaller vocabulary.
  • Retriever comparison: The FT comparison replaces BM25 over predicted program symbols with BM25 over lower-cased utterance words.This experiment is reported in Table 7.

B Local Structures

The paper extends local-structure analysis to arbitrary sizes by representing programs as trees augmented with consecutive-sibling edges, then extracting constrained connected subgraphs.

  • Local-structure construction: Programs are parsed into labeled trees whose nodes represent functions or values and whose edges represent parent-child relations.A special symbol labels the root node.
  • Local-structure construction: Sibling relations are added between consecutive children of each parent, producing a graph that combines parent-child and sibling edges.
  • Local-structure definition: A local structure of size n is a connected subgraph of n nodes satisfying a restriction on sibling edges between leaves.The definition excludes relations such as cousins or uncles, while size-1 structures are individual program symbols.
  • Error analysis: The error analysis categorizes wrong predictions as syntax errors, over-copying, or out-of-vocabulary hallucinations.These statistics are automatically computed for incorrect predictions.
  • Error correction: Syntax-error repair adds or removes closing parentheses according to redundant or missing parentheses at the program end.An auxiliary model enables parsing repaired predictions into ASTs and extracting local structures.

C Dataset Details

The appendix documents datasets, prompting, retrieval, DPP-based demonstration selection, finetuning, evaluation variability, and artifact licensing for the experiments.

  • Datasets: SMCalFlow-CS Simple has fewer training examples than SMCalFlow-CS because of conversion errors, but the missing examples are not cross-domain examples.
  • Datasets: The study uses publicly available datasets without uniquely identifying information or offensive content, including a fully synthetic COVR-10 dataset.GeoQuery contains basic U.S. geography information, while SMCalFlow-CS uses simulated crowd-sourced queries.
  • Prompting: Prompts separate retrieved source-target pairs with line breaks and use source: and target: prefixes.For a cited example, Cover-LS is the only method whose prompt contains all required program symbols and yields the correct prediction.
  • Demonstration selection: DPP selection models example quality with normalized retriever scores and similarity with normalized TF-IDF vectors over local structures.The dot product of TF-IDF vectors measures similarity between training examples.
  • Demonstration selection: A Naive Greedy optimizer maximizes the submodular log det objective to select k training examples, with TF-IDF vectors computed using scikit-learn.
  • Experimental setup: Finetuning uses T5-large with AdamW, a 1e−5 learning rate, polynomial decay to 1e−6, warmup, dataset-specific epochs, and batch size 8.Experiments use AllenNLP for training and evaluation and Rank-BM25 for BM25 retrieval.
  • Evaluation: Standard deviations are computed across 3 random seeds in FT experiments and across 3 seeds on 100-test-example subsets in NoFT experiments.NoFT evaluation uses temperature 0 and one API call per test instance, with approximately 160K calls overall.
  • Evaluation: The number of beam candidates is tuned on 100 development examples using Cover-LS prompts with k = 8 demonstrations.

I GenBench Evaluation Card

The appendix presents the GenBench evaluation card and supplementary tables covering local structures, datasets, prompts, variability, beam candidates, and licenses.

  • GenBench evaluation: The GenBench evaluation card is presented in Figure 6.
  • Supplementary materials: Supplementary tables include local structures for an example program and examples from each SMCalFlow-CS dataset version.
  • Supplementary materials: Dataset sizes are reported in Table 10, while Table 11 presents prompts from different demonstration-selection methods using k = 4 demonstrations.
  • Supplementary results: Tables 12 and 13 report standard-deviation results for NoFT and FT setups, respectively, both using 3 random seeds.The NoFT results use a random subset of 100 test examples.
  • Supplementary results: Table 14 reports how the number of beam candidates B affects NoFT accuracy with Cover-LS prompts and k = 8 demonstrations.Results use 100 randomly selected development examples and one seed.
  • Artifacts: Table 15 provides license information for all artifacts used in the work.
Loading 2212.06800v3…