Diverse Demonstrations Improve In-context Compositional Generalization (2023)

Abstract: 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.

## introduction despite strong performance of pretrained language models (lms) across many tasks, they have been shown to struggle in a compositional generalization setting (lake and @xcite @xcite , when tested on their ability to process and generate novel combinations of previously observed elements. for example, a model might fail to interpret the request "book a meeting with jake's supervisor" even when "book a meeting with jake" and "who is jake's supervisor?" were observed during training. in semantic parsing, the task of mapping natural language utterances to formal queries, such generalization is important (especially in a real-world setting), since models are required to interpret new combinations that are not covered by the annotated training data @xcite . recently, large lms have shown impressive performance on downstream tasks by conditioning on a text-based prompt that contains a few training examples. this type of few-shot inference is known as in-context learning (icl, @xcite . a core component of in-context learning is the set of examples in the prompt, often termed task demonstrations. with the right demonstrations, icl can be an effective approach to improving lms' compositional generalization abilities @xcite . selecting a relevant set of demonstrations is crucial for generalization. however, most past work only considered the relevance of each example in isolation, ignoring the quality of the entire set of examples @xcite . for instance, a retriever can be used to select the examples most similar to the input @xcite . a set of demonstra- diverse examples selection 1. predict local structures: @xmath0. select demonstrations that cover predicted local structures: state(next_to_2(largest_one(population_1(state(all))))) state(most(state(loc_1(river(all))))) count(major(city(all))) cover-ls inference with prompts state(next_to_2(state ... count(state(next_to_2( … state(next_to_2(stateid ... retrieve similar training examples question: what states border the state with the most major cities? state(next_to_2( most(state(loc_1( major(city(all)) ))))) predicted target (1) (2) (3) finetuned model (optional) finetuning with prompts prompt (45) …(most(state(loc_1( … (63) count(major(city(all… tions that are all highly relevant but highly similar to one another may not be as effective as a more diverse set. in compositional splits, where no single demonstration is sufficiently similar to the input, choosing diverse demonstrations can be especially beneficial since it leads to better coverage of structures in the target program (fig. 1 ). in this paper, we study how to leverage icl to improve compositional generalization for semantic parsing, by optimizing the entire set of demonstrations and increasing the diversity of examples in this set. we investigate two approaches for increasing diversity: (a) a coverage-based approach, where we define a set of elements conditioned on the input utterance, and select examples that cover those elements (e.g., covering potential substructures in the output program), and (b) a second approach, where we select a subset of examples that are most dissimilar from one another, such that diversity is independent of the input utterance. empirically, we find that coverage-based diversity results in better performance. our method can be used in the "pure" in-context learning setup without finetuning, which leverages the ability of large lms, such as codex @xcite , to generalize from the selected diverse demonstrations. furthermore, it can be combined with finetuning by training a model with demonstrations as part of the input. this can be viewed as meta-learning, where the model learns to use demonstrations during training and build new structures based on them during inference @xcite @xcite @xcite . it can, however, lead to an over-reliance on demonstrations, especially in compositional splits. we address this by using "noisy" demonstrations during training. we empirically test our method on three compositional generalization semantic parsing datasets. we show that diverse demonstrations, both with and without finetuning, improve performance by up to 23 absolute points (e.g., 50.3 → 73.5 on smcalflow-cs) compared to a baseline that retrieves demonstrations according to similarity alone, and lead to state-of-the-art results in multiple compositional setups. finally, we show that our method reduces the number of demonstrations needed for generalization and improves test performance on hard examples. ## diversity for compositional generalization in semantic parsing, we define compositional splits of datasets as splits where train and test programs do not overlap @xcite . recent work has shown that increasing the number of different program structures a model sees during training improves performance on compositional splits. this can be done by augmenting the training set @xcite or through efficient sampling of diverse examples @xcite @xcite . while past work focused on increasing structure diversity in the training set, we focus on diversity in the demonstration set within an icl setup. increasing diversity is important as we want the demonstrations to cover all structures of the expected output program. in the few-shot setting, where the model is unfamiliar with the formal language of the output programs, increasing coverage also improves generalization simply since otherwise the model will be unaware of the required program symbols (predicates and logical operators). however, selecting demonstrations that cover larger structures (sub-trees of the program tree) are potentially more beneficial, for two reasons: (1) it reduces the amount of new structures that the model needs to produce, making demonstration fusion easier, and (2) it exposes the model to structure compositions in different contexts, providing the model with valuable information about how structures can be composed in the data. ## diverse demonstrations selection problem setup given a training set @xmath1, y i )} n @xmath2, our objective is to select a subset of training examples @xmath3, y j )} k @xmath4, where k ≪ n, termed demonstrations. those demonstrations are then formatted as a text-based prompt p . when feeding the concatenation of the prompt and the test utterance ([p ; x test ]) to the model, the desired output is y test . overview fig. 2 provides an overview of our framework for obtaining and leveraging diverse demonstrations for better compositional generalization. given an input utterance, x test , we propose two approaches for selecting demonstrations. in the first ( §3.1), we optimize coverage: we define a set of elements that we want our demonstrations to cover (either structures in the program or utterance words), and then iteratively select examples that contain these elements. the second approach ( §3.2) increases diversity by selecting a subset of examples with minimal similarity. fig. 2 shows an example of the former approach (cover-ls), where we predict and then attempt to cover local structures (ls), i.e., sub-trees of the output program. local structures were shown to be key for compositional generalization in @xcite . having selected demonstrations, we use them to construct a prompt ( §3.3). we show that our method can be combined with finetuning to metatrain the model to learn in-context ( §3.4). @xcite have recently shown, in the context of finetuning semantic parsers, that models fail to generalize to programs with local structures that were not observed at training time, where local structures of a program are defined to be a set of its sub-trees. inspired by this observation, we propose cover-ls, an algorithm that given the test utterance x test , attempts to choose examples that collectively cover as many local structures as pos-sible from the set s ytest of local structures of the program y test . since we have no access to y test at test time, we predict what local structures are likely using an auxiliary model, assuming that predicting local structures is easier than predicting the entire program. then, we iteratively select examples that cover the predicted local structures. ## experiments we present our experimental setup and results on different compositional semantic parsing tasks, with finetuning (ft) and without (noft). ## related work example selection one of the central issues in incontext learning is the selection of examples, which can either be based on parameter-free retrievers @xcite or neural-based retrievers @xcite @xcite . these studies consider each example separately, which often leads to a lack of coverage and diversity. our approach is similar to the retrieval procedure in @xcite , which makes a preliminary prediction and retrieves demonstrations with similar programs. however, while they use classic tf-idf with predicted tokens, we use predicted local structures and aim to cover them. some studies encourage diverse example selection regardless of prompting. to address multianswer retrieval, @xcite employ dpp, and min et al. (2021) autoregressively select instances based on previous selections. other works include su et al. (2022), which selects instances with varying confidence scores for annotation and (concurrent work) ye et al. (2022) who propose a mmr-based selection strategy. in-context learning for compositional generalization there have been previous attempts to address compositional generalization problems using llms equipped with demonstrations. when selecting demonstrations, some also consider target coverage or structure similarity, but only in oracle setups @xcite . @xcite try to cover the syntactic parse tree constituents with demonstrations but rely heavily on manually-picked examples. ## conclusion in this paper, we studied how to leverage icl to improve compositional generalization in semantic parsing, by increasing diversity among demonstrations. we found that choosing demonstrations that cover the structures required in the output program substantially improves performance across three compositional semantic parsing datasets in the pure in-context learning setup and when combined with finetuning. we further demonstrated that by aiming for structural coverage, we can reduce the number of demonstrations needed for generalization, and improve test performance on hard examples. our approach can be applied to a wide range of nlp tasks where demonstrations should cover complementary aspects of the task, and we hope it will encourage further exploration of our method to improve generalization across diverse applications.