Coverage-based Example Selection for In-Context Learning (2023)

Abstract: In-context learning (ICL), the ability of large language models to perform novel tasks by conditioning on a prompt with a few task examples, requires these examples to be informative about the test instance. The standard approach of independently ranking and selecting the most similar examples selects redundant examples while omitting important information. In this work, we show that BERTScore-Recall (BSR) selects better examples that demonstrate more of the salient aspects, e.g. reasoning patterns, of the test input. We further extend BSR and many standard metrics to easily optimizable set-level metrics, giving still better coverage of those salient aspects. On 15 datasets spanning 6 tasks and with 7 diverse LLMs, we show that (1) BSR is the superior metric for in-context example selection across the board, and (2) for compositional tasks, set selection using Set-BSR outperforms independent ranking by up to 17 points on average and, despite being training-free, surpasses methods that leverage task or LLM-specific training.

## introduction large language models (llms) @xcite are capable of generalizing to novel tasks @xcite ) by conditioning on textual prompts consisting of a few task examples. this training-free paradigm of fewshot inference, known as in-context learning (icl), reduces the cost of modeling new tasks while also providing an interpretable and customizable interface @xcite and improving generalization @xcite @xcite and reasoning skills @xcite . however, icl performance is critically sensitive to the choice of demonstrations @xcite @xcite ; schick and schütze, 2021), as the llm relies on them for understanding and solving the test instance. the standard approach to selecting icl examples or demonstrations from a pool of candidates is to independently score them using a relevance metric and choose the top-ranked ones. however, cosine similarity and bm25, the two commonly used metrics, are sub-optimal for selecting demonstrations due to their reliance on a single dense embedding and unigram overlap, respectively. moreover, since it selects examples independently, this approach ignores their utility as a set. it is particularly inadequate for complex compositional tasks like semantic parsing @xcite where no single candidate might contain all reasoning patterns, and an independent selection would select multiple redundant examples with the same reasoning patterns but fail to demonstrate the others. figure 1 shows a failure case where similarity-based selection picks paraphrased examples that fail to demonstrate how to find a manager. prior work on selecting demonstrations as a set @xcite required task and/or llm-specific training, limiting their utility. for this reason, simple yet widely applicable training-free methods like bm25 and cosine similarity remain the most popular approaches for icl example selection. in this work, we propose a novel framework for selecting sets of maximally informative demonstrations for the salient aspects of the test input, e.g., reasoning patterns, entities, etc. examples selected using this framework are informative about the test input and help the llm understand and perform the task. we use this framework to explore different ways to characterize salient aspects, including syntactic structures like dependency parse subtrees and contextual token embeddings, while using bm25 and bertscore @xcite to measure their coverage, respectively. to select the demonstrations as a set, we extend the coverage metrics to measure the overall informativeness of a set of demonstrations. we show that these set-level metrics are submodular and can be efficiently optimized to find demonstration sets that maximally cover the salient aspects. we evaluate our icl example selection methods on 15 diverse datasets, including 6 semantic parsing, 2 numerical reasoning, and 7 classification datasets, and with 7 llms of varying sizes and pretraining. among instance-level metrics, bsr, the recall version of bertscore, consistently outperforms standard retrieval metrics on all datasets and llms, beating cosine similarity by up to 8 points on average in semantic parsing datasets and 15 points in the rest. selecting demonstrations as a set using set-bsr, the set-extension of bsr, leads to further gains in semantic parsing and is particularly effective in compositional settings where the gains grow with llm size. with codex, a 175b parameter llm, set-bsr outperforms cosine similarity by 17% on average with up to 49% improvement in some splits, and, despite being training-free, outperforms even trained methods like those from @xcite , @xcite , and @xcite that require task and/or llm-specific training. ## related work in-context learning for few-shot inference facilitates the use of llms for novel tasks without the need for expensive supervised fine-tuning. in addition to reduced cost, it has several other advantages over supervised fine-tuning: it provides a more interpretable and customizable interface to using llms @xcite ; and retention of linguistic understanding and knowledge from pretraining leading to improved generalization @xcite @xcite and reasoning skills @xcite . however, the performance of icl is critically sensitive to the choice of demonstrations @xcite . this has led to a growing interest in techniques for selecting good demonstrations. prior work can be roughly classified into (1) independently scoring and retrieving examples @xcite , (2) selecting diverse examples to reduce redundancy among them @xcite @xcite , and (3) selecting examples that minimize the entropy of the llm's output distribution for the test input @xcite . recent work has also trained rl agents @xcite and used bayesian inference @xcite . the most similar studies to ours are @xcite and @xcite . @xcite select diverse demonstrations that cover substructures of the target output predicted by task-specific classifiers but are limited in applicability to a few semantic parsing tasks. @xcite use determinantal point processes (kulesza, 2012) to select a diverse set of demonstrations similar to the test instance but do not optimize for coverage directly and require training with the llm. moreover, both methods require task or llm-specific training that limits their use and effectiveness for larger lms. ## preliminaries in-context learning is the ability of llms to solve novel tasks by merely conditioning on a few task demonstrations. formally, given demonstrations {(x i , y i )} k @xmath0, it involves using textual templates to linearize instance inputs and outputs into sequences of tokens from the llm vocabulary, @xmath1. . . x |x| ⟩ and @xmath2. . . y |y| ⟩. the linearizations are then concatenated to form a prompt and fed to the llm for conditional generation of the test output: the interpretable and training-free nature of icl makes it an attractive alternative to supervised finetuning. however, its performance is highly sensitive to the choice and order of demonstrations. demonstration selection identifies which examples to include in the prompt for any test instance. formally, given a test input x test and a pool of candidates @xmath3, y i )} n @xmath4, the goal is to select a subset of k ≪ n demonstrations that when included in the context make y test the most likely generation. a naive approach is to randomly sample k instances from t , but this is sub-optimal since the demonstrations are often completely unrelated to the test input. instead, the standard approach to selecting demonstrations that are informative about the test input is to independently assign each candidate z a score score(x test , z) using a relevance metric and then select the top k candidates. relevance metrics the two most commonly used relevance metrics for scoring demonstration are cosine similarity and bm25. cosine similarity uses a representation function r to independently map the textual linearizations of inputs to unit-norm embeddings r @xmath5, cosine(x test , z) = r t xtest r z . bm25, on the other hand, is a sparse information retrieval algorithm belonging to a class of tf-idf measures that view the test input and the candidates as bags of terms and measures relevance as a weighted recall or coverage of these terms: here t x and t z are the set of terms in x and z respectively, and tf(s, t z ) and idf(s) are the term frequency and inverse document frequency statistics that measure the coverage of a particular term and the relative importance of terms respectively. we use tf and idf as per the okapi variant of bm25 @xcite . ## informative demonstrations the limitation of the standard demonstration selection approach is that by independently scoring the demonstrations, it ignores their utility as a set. for icl to work, the demonstrations included in the context need to be informative about how to understand and solve the test input. in this section and the next, we describe our approach to selecting informative sets of demonstrations for icl. we begin by defining our notion of informativeness of demonstrations in icl and describing how to measure it. thereafter, in §5, we will discuss how to extend this notion to an algorithm for selecting optimally informative sets of demonstrations. informativeness demonstrations should demonstrate the salient aspects, e.g., reasoning patterns, entities, etc., of the test input. formally, denoting s xtest as the set of salient aspects of the test input, we measure the informativeness of a demonstration z in terms of the coverage of such salient aspects, the above interpretations reveal why neither cosine similarity nor bm25 are good measures of informativeness. while cosine similarity captures some aspects of semantic similarity (depending on the embedding), it is limited to a single embedding. and, unigrams, the commonly used terms with bm25, are too small to capture most salient aspects. a good measure of informativeness necessitates an accurate characterization of salient aspects. one way might be to use larger syntactic substructures of the input as terms with bm25. we experiment with using larger n-grams and subtrees of the dependency parse tree. however, such syntactic structures are constrained to the surface form of the instance and hence may not capture meaning and aspects like reasoning patterns. a better way to capture salient aspects is to use contextualized token embeddings, the idea behind the bertscore @xcite metric. bertscore was originally proposed as a metric for evaluating the quality of machine-generated text (e.g., machine translation) by comparing it to a reference text. it leverages pre-trained contextual embeddings to match words in the candidate and reference sentences by cosine similarity and compute precision, recall, and f1 measures. formally, given the sequences of contextual embeddings ⟨x 1 , x 2 , . . . , x |x| ⟩ and ⟨z 1 , z 2 , . . . , z |z| ⟩ of tokens in @xmath6, x 2 , . . . , x |x| ⟩ and @xmath7, z 2 , . . . , z |z| ⟩ respectively, the recall measure, bertscore-recall (bsr), is defined as: here, w(x i ) is a weight assigned to token x i and can be defined as 1 |x| if treating each token as equally important or idf(x i ) ## set-level information coverage so far, we have focused on measuring the informativeness of a single demonstration to rank and independently select the most informative ones. however, as depicted in fig. 1 , when no single single candidate demonstrates all salient aspects, this approach can fail to cover all of them while also selecting redundant demonstrations that provide no new information. a scenario where this can happen is when the candidate pool contains close paraphrases (or duplicates). this suggests that demonstrations should be selected as a set. ## results we begin by comparing the performance of our proposed methods, bsr and set-bsr, with prior training-free and state-of-the-art trained methods in § 7.1. we then analyze the different metrics for measuring informativeness of individual demonstrations ( § 7.2) and the impact of coverage-based set selection using our set extension ( § 7.3). ## conclusion this paper presents a novel framework for selecting informative sets of demonstrations that cover salient aspects of the test input to aid the language model (llm) in solving it. we explore different ways to characterize these aspects and quantify their coverage. evaluation on a wide range of tasks and llms validates the effectiveness of bertscore-recall as a measure of informativeness of individual demonstrations. further, our results demonstrate the superiority of set-bsr in selecting informative sets of demonstrations compositional tasks like semantic parsing and highlight the ability of coverage-based demonstration selection, unlike trained methods, to leverage increasingly powerful larger llms. our code base is available at https://github.com/ shivanshu-gupta/icl-coverage.