Coverage-based Example Selection for In-Context Learning
Authors: Shivanshu Gupta
Matt Gardner
Sameer Singh
Venue: EMNLP 2023 Findings (2023)
Keywords: In-Context Learning
Demonstration Selection
Large Language Models
Prompting
Compositional Generalization
Semantic Parsing
TL;DR: A novel training-free method for selecting maximally informative sets of examples for In-context Learning

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.

Coverage-based Example Selection for In-Context Learning
Shivanshu Gupta'
Matt Gardner
Sameer Singh'
'University of California Irvine Scaled Cognition
[shivag5, Jeame. m wwwpe/ooonniiiiii...oooo com
Abstract
with his for Homoron
(a) Test Input
In-context learning (ICI.), the ability of large language models to perform novel tasks by con- ditioning on prompt with 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. this work, show that BERTSScore Recclll (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 metries, giving still better coverage of those salient aspects. On 15 datasets spanning 6 tasks and with 7 diverse L.Mss, 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--pecificc training.'
meeting lomorrsw
CreatoSvent bwich stsondoo1" "),atazto at (foroccoo(1333
Q: appoietment Ji for fomanrow
CreateSvenn withh stsendos1" Jix "/,atazto at (103
9: a mosting with and manager famovrioi
A: Creatallient (AND (with, attendoo Jim ") with attendee hio manages "I, "|,atarts (1mmorrow 2))
(b) Similarity
Independent Selectiion
Q: Schoolule a mosting with Doug ana'Ns boss for noxt wook to rewlow Al Createsiven: LAXD biich 2tsendo21" Doug *I,
wesh tn attendes (F daanaaaaace saaae 1* cous "1), sobt uct. zeviev wtwrtssee (Wour Weeeeeeee M (100
Q: Add an sppoknmment with Jin for tomorrow
A: Conatelvents (AND tea th, sttendan 1" Jin "), "taata (1o30rroN))31
Q: Add a mediing with A' and his managor for Jomorra
Creatativent (ASI (withh atttnndaw'" !" dim with attenndae FindManager ")).otarte
(c) Coverage-based Set Selection
Figure I: (a) Test input with salient aspects highlighted. (a) Independently selecting similar examples leads to redundancy and failure to demonstrate all salient as- pects, in this case, the need identify the manager. (b) Coverage-based selection using SET-BSR mitigates this by selecting less similar example that contains the missing information. Blue indicates LLM generation.
1 Introduction
2021),, as the LLM relies on them for understanding and solving the test instance.
Large language models (LLMs) (Devlin et al., 2019; Brown et al., 2020) are capable of gener- alizing to novel tasks (Brown et al., 2020) by con- ditioning on textual prompts consisting of a few task examples. This training-free paradigm of few- shot inference, known as in-context learning (ICL), reduces the cost of modeling new tasks while also providing an interpretable and customizable in- terface (Liu et al., 2022: Wei et al., 2023) and improving generalization (Anil et al., 2022; Qiu et al., 2022b; Drozdov et al., 2023) and reasoning skills (Wei et al., 2023). However, ICL perfor- mance is critically sensitive to the choice of demon- strations (Zhao et al., 2021; Liu et al., 2022; Lu et al., 2022; Rubin et al., 2022; Schick and Schütze,
The standard approach to selecting ICL exam- ples or demonstrations from pool of candidates is to independently score them using relevance met- ric and choose the top-ranked ones. However, co- sine similarity and BM25, the two commonly used metrics, are sub-optimal for selecting demonstra- tions due to their reliance on a single dense embed- ding and unigram overlap, respectively. Moreover, since it selects examples independently. this ap- proach ignores their utility as set. It is particularly inadequate for complex compositional tasks like mantic parsing (Levy al., 2022) where single candidate might contain all reasoning patterns, and an independent selection would select multiple re- dundant examples with the same reasoning patterns but fail to demonstrate the others. Figure shows a
'https://iithbb. htw.ithub.cooaat00 wwwpShhiwivvanast.asaa Gupta/ icl-coverage

---

failure case where similarity-based selection picks paraphrased examples that fail to demonstrate how to find a manager. Prior work on selecting demon- strations as a set (Ye et al., 2023; Levy et al., 2022) required task and/or LLM-specific training, limit- ing their utility. For this reason, simple yet widely applicable training-free free methods like BM25 and co- sine similarity remain the most popular approaches for ICL example selection.
need for expensive supervised fine-tuning. In addi- tion to reduced cost, has several other advantages over supervised fine-tuning: it provides a more interpretable and customizable interface to using LLMs (Liu et al., 2022; Wei et al., 2023); and re- tention of linguistic understanding and knowledge from pretraining leading to improved generaliza- tion (Anil et al., 2022; Qiu et al., 2022b; Drozdov et al., 2023) and reasoning skills (Wei et al., 2023). However, the performance of ICL is critically sensitive to the choice of demonstrations (Zhao et al., 2021; Liu al., 2022). This has led to growing interest in techniques for selecting good demonstrations. Prior work can be roughly classi- fied into (1) independently scoring and retrieving examples (Liu et al., 2022; Rubin et al., 2022). (2) selecting diverse examples to reduce redundancy among them (Su et al., 2022; Levy et al., 2022; Agrawal et al., 2022: Ye et al., 2022), and (3) se- lecting examples that minimize the entropy of the LLM's output distribution for the test input (Lu et al., 2022; Wu al., 2023). Recent work has also trained RL agents (Lu et al., 2023) and used Bayesian inference (Wang et al., 2023).
In this work, we propose a novel framework for selecting sets of maximally informative demon- strations for the salient aspects of the test input, e.g., reasoning patterns, entities, etc. Examples se- lected 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, in- cluding syntactic structures like dependency parse subtrees and contextual token embeddings, while using BM25 and BERTScore (Zhang et al., 2020) to measure their coverage, respectively. To select the demonstrations as set, we extend the coverage metries to measure the overall informativeness of set of demonstrations. We show that these set-level metries are submodular and can be efficiently op- timized to find demonstration sets that maximally cover the salient aspects.
The most similar studies to ours are Levy et al. (2022) and Ye et al. (2023). Levy et al. (2022) select diverse demonstrations that cover substruc- tures of the target output predicted by task-specific classifiers but are limited in applicability to few semantic parsing tasks. Ye et al. (2023) use Deter- minantal Point Processes (Kulesza, 2012) to select 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..
We evaluate our ICL example selection meth- ods 15 diverse datasets, including 6 semantic parsing, 2 numerical reasoning, and 7 classification datasets, and with LLMs of varying sizes and pre- training. Among instance-level metrics, BSR, the recall version of BERTScore, consistently outper- forms standard retrieval metrics on all datasets and LLMs, beating cosine similarity by up to 8 points on average in semantic parsing datasets and 15 set
points in the rest. Selecting demonstrations using BSR, the set-extension of BSR, leads to further gains semantic parsing and is particularly effective in compositional settings where the gains grow with LLM size. With Codex, a 175B parame- ter LLM, SET-BSR outperforms cosine similarity by 17% on average with up to 49% improvement in some splits, and, despite being training-free, outper- forms even trained methods like those from Rubin et al. (2022), Levy et al. (2022), and Ye et al. (2023) that require task and/or LLM--ceccffic training.
3 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,, 3)) and the test input Wisst involves using textual templates to linearize instance inputs and outputs into sequences of tokens from the LLM vocabulary, x = I(x) - (z)... 2xxi) and =
O (1) ... .yy)> The linearizations are then concatenated to form prompt and fed to the LLM for conditional generation of the test output:
2 Related Work
In- in-context learning for feo-shot inference facili- tates the use of LLMs for novel tasks without the
Yiest ~ PIM (: X1,Y1,.... XK. YK: Xiest (1)

---

The interpretable and training-free nature of ICL makes it an attractive alternative to supervised fine- tuning. However, its performance highly sensi- tive to the choice and order of demonstrations.
and the next, we describe our approach select- ing 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.
Demonstration Selection identifies which exam- ples to include in the prompt for any test instance. Formally, given test input Fiest and pool of can- N
didates T { i=1 = (1r vi) m the goal is to select subset of l < N demonstrations that when included in the context make Ylest 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 un- related to the test input. Instead, the standard ap- proach to selecting demonstrations that are informa- tive about the test input is to independently assign each candidate a score score(Ftest 2) using a rel- evance metric and then select the top candidates.
Informativeness Demonstrations should demon- strate the salient aspects, e.g., reasoning patterns, entities, etc., of the test input. Formally, denoting Saws as the set of salient aspects of the test input, we measure the informativeness of a demonstration in terms of the coverage of such salient aspects,
cover (Frest 2)
Σ SESEiel
c(s, 2)
(3)
where c(s, 2) measures the coverage (or recall) of single salient aspect s by z.
Relevance Metrics The two most commonly used relevance metrics for scoring demonstration are cosine similarity and BM25. Cosine similar- ity uses a representation function R to indepen- dently map the textual linearizations of inputs to unit-norm embeddings rg = RRx)) in a common vector space and then scores the candidate using the dot product, cosine (Frest 2) Iu rzz BM25, the other hand, is sparse information retrieval algorithm belonging
Salient Aspects Both cosine similarity and BM25 are special cases of Eq. 3 for different notions of salient aspects. For BM25, Sans West the set of unigrams in I, and c(s, 2) idf (s) Tz). And cosine similarity, although not explicitly call metric, can also be interpreted as evaluating coverage the dimensions of the test input embed- ding by defining Spm. = [1. d]. the dimensions of the dense embedding as the salient aspects, i.e.,
class of TF-IDF measures that view the test input and the candidates as bags of terms and measures relevance as a weighted re- call or coverage of these terms:
cosine(Trest 2) = T [s]
[s[s]
(4)
The above interpretations reveal why neither co- sine 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 embed- ding. And, unigrams, the commonly used terms with BM25, are too small capture most salient aspects. A good measure of informativeness ne- cessitates 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 syn- tactic 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 (Zhang et al., 2020) metric.
tf idi (Frest z) = Σ (df(s)tf(s,T:) (2) TETrus
Here T, and T2 are the set of terms in x and re- spectively, and tf (f, T2) and (s) are the term frequency and inverse document frequency statis- ties that measure the coverage of particular term and the relative importance of terms respectively. We use tf and idf as per the Okapi variant of BM25 (Robertson et al., 1993; Jones et al., 2000).
4 Informative Demonstrations
The limitation of the standard demonstration se- lection approach that by independently scoring the demonstrations, it ignores their utility as a set. For ICI. to work, the demonstrations included in the context need to be informative about how to understand and solve the test input. In this section

---

BERTScooe was originally proposed as a metric for evaluating the quality of muucinn--genrraee text (e.g., machine translation) by comparing to a reference text. It leverages pre-trained con-
Algorithm 1 Greedy Optimization of Set Coverage
Require: Instance pool T: test input fust desired number of demonstrations k; coverage scoring function setcov > Selected Demonstrations
1: Z f- ()
2: Zem + B
> Current Set Cover
textual embeddings to match words in the candi-
3: curr _ +- inf
date and reference sentences by cosine similarity and compute precision, recall, and Fl measures, Formally, given the sequences of contextual em- beddings (2,,X2,... ........ X|x)) and (Z1, :.,; 24/1 of tokens in x
4:
while / do
5:
x", next_cov argmax setcov (Tres Zeun U 2)
=ET 2
6:
if next_cov >> curr_cov then
D Pick x*
7:
curr Ourr_cov- <- next_cov
( #2,.......... F/a)) and
8:
Z s 2 = Zour Zemn U
9:
(21, 22; ................................ )/1) respectively, the recall measure, BERTScore- Recall (BSR), defined as:
10: else
Or start new cover Yec + 0, curr inf
11:
12: end if
13: end while
BSR( =) = Σ w(x;) maxx!" 2j (5)
14: return Z
E,E2
Intuitively, this measures the coverage of each salient aspect as the best coverage it receives from
Here, w(r;) is weight assigned to token ay and can be defined as la if treating each token as equally important or 1df(#;) Ex,e= idf( downweight- ing rare words. The precision measure is defined analogously, while the Fl measure is the harmonic mean of the two. BSR is also a special case of Eg. 3 with contextualized tokens salient aspects, i.e., S. = -x1; x....., ( and can be used to select examples by treating them candidates and the test input as the reference. The following table sum- marizes the informativeness measures and salient aspects in this work.
any example in the set. In other words, maximizing it requires that every salient aspect appears at least once in some demonstration without considering which how many. Since cosine similarity, BM25, and BSR are all special cases of Eq. 3, they can be extended to set measures using Eq. 6.
Submodularity Given the combinatorial space of sets of demonstrations, for a measure on sets to be practical, it needs to be efficiently optimizable. Fortunately, the set-level metric, as defined above. is also submodular for any definition of c(s, 2). We prove this in Appendix A. Intuitively, this follows from the facts that (1) for any given test instance, (ss, 2) assigns a scalar weight to each demonstra- tion Z E Z, (2) the maximum weights across set elements is submodular, and (3) the sum of sub- modular functions is also submodular. This means that the set-level metric can be optimized using a greedy algorithm with a constant factor approxima- tion guarantee (Nemhauser al., 1978).
Metric
Salient Aspects
Cosine
embedding dimensions
BM25
unigrams, n-grams. dependency parse subtrees contextual token embeddings
BERTScore
5 Set-level Information Coverage
So far, we have focused on measuring the infor- mativeness of 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 pro- vide 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 set.
Algorithm The greedy algorithm we use to select the optimal set shown in Algorithm 1. ev- cry iteration, it seleets the example that maximally increases the coverage of the current set of demon- strations (lines 5-9). If no such example exists, it resets (lines 11) 1). Using the following identity when computing the score for candidate sets (line 5),
setcov (Frest ZU
Set Metrie To evaluate the informativeness a set of examples Z, we propose to extend the coverage measure in Eq. 3 to measure for sets as follows:
Σ max (c(s, Z), c(s,22))
(7)
SCS
setcov (Jiest Z)
max c(s,2) zE%
and assuming constant time for computing cach c(s, the time complexity of algorithm is

---

(kNN)), where L |S For BSR, the com- plexity of computing c(x, 2) for all 2 E Z is (Td), where T is the total number of tokens in Z and d is the token embedding size. Thus, the time complexity of both instance and set-level BSR is dominated by the computation of c(r, z), and is dLTd)). While slower than cosine and BM25, we found it to be small overhead to in-context learning for most datasets considered in this work. We discuss this further in App.
use a random subsample of 1000 instance of the validation set if available, and the test otherwise. We use Exact Match (EM) accuracy for all datasets except BREAK where we use LF-EM (Hasson and Berant, 2021), which is preferred over EM for se- mantic equivalence.
6.2 Models
We experiment with the following LLMs: GPT-
Neo-2.7B (Black et al., 2021): A 2.7B 2.7B-paramette LM trained The Pile (Gao al., 2020),
6 Experimental Setup
825 GB text corpus. LLaMA (Touvron al., 2023): A collection of LMs ranging from 7B to 65B parameters pretrained on CommonCrawl, GitHub, Arxiv, etc. We experiment with L-aMA- 7B and LLaMA-13B. StarCoder (Li et al.. 2023); A 15.5B parameter model trained on 80+ program- ming languages (Kocetkov et al., 2022). GPT- 3.5- 3.5-Turbo²: 175B LM trained with RL to fol- low instructions and optimized for chat. Cush- man, Codex² (Chen al., 2021): 12B and 175B parameter code-pretrained LMs. GPT-Neo-2.7B. LLaMA-7B, LLaMA- LLaMA--- 13B, and Cushman have con- text window lengths of 2048, GPT-3.5- --rbo of 4096, Codex of 8001, and StarCoder of 8192.
6.1 Datasets
We experiment with total of 15 datasets including six diverse semantic parsing datasets viz. Geo- Query (Zelle and Mooney, 1996), ATIS (Hemphill et al., 1990; Dahl et al., 1994), Overnight (Wang et al., 2015), SMCalFlow (Andreas et al., 2020), BREAK (Wolfson et al., 2020), and MTOP (Li et al.. 2021); a math-word problems (GSMSK (Cobbe et al., 2021)) and machine reading com- prehension (DROP (Dua et al., 2019)) dataset re- quiring multi-step numeric reasoning; and seven classification datasets spanning natural language inference, paraphrase detection and sentiment clas- sification viz. QNLI (Wang et al., 2018), MNLI (Williams et al., 2018), RTE (Bentivogli et al., 2009), MRPC (Dolan and Brockett, 2005), PAWS (Zhang et al., 2019), QQP (Wang et al., 2018), and SST2 (Socher et al., 2013). We refer the reader to App. B for detailed descriptions of each dataset along with sample instances and prompt templates. In addition to the standard IID splits, we also evaluate compositional generalization using com- positional splits wherever available. For GeoQuery we use three types of compositional splits: Tem- plate (Finegan-Dollae Dollak et al., 2018), TMCD (Key- sers et al., 2020), and Length. Following Levy al. (2022), we use the compositional splits- three Template, three TMCD, and one Length- generated by Qiu al. (2022a) and average results across the TMCD and Template splits. For ATTS and Overiight, we experiment with Template splits (Finegan-Dollak et al., 2018) generated by Gupta et al. (2022). For SMCalFlow, we experiment with splits in SMCalFlow-CS (Yin et al., 2021): I): IID split (8-S) and compositional split (32-C). For all the splits, following prior work (Ye et al.. 2023; Rubin et al., 2022) we randomly subsample 44,000 instances from the train set to use as pool to select demonstrations from. For evaluation, we
6.3 Methods
6.3.1 Training-Free Methods
We compare the following training-fre free metrics:
Cosine similarity (COSINE) We use the Sentence- Bert library (Reimers and Gurevych, 2019) with the all 1al1-mpeet-ae -baeeeet-baaevv.. model. For independent selection, we use FAISS (Johnson et al., 2019) retrieve the most similar examples.
BM25 (BM25) We use the Okapi variant (Robert- son et al., 1993; Jones et al., 2000) of BM25 from the rank_bm25* library with three syntactic struc- tures as terms: unigrams, size-4 or smaller n-grams, and size-4 or smaller subtrees of the input depen- dency parse (obtained using the spaCy").
BERTScore We use the bert_score" library (Zhang et al., 2020) with deberta-large-mn.. and deber babberta-basemm11 models which are De- BERTa models (He et al., 2021) finetuned on the MNLI dataset ( (Williams et al., 2018). We will refer
hnttps://opeaai.i http:///ppeaai.cooob///o//////// hoom///o//chaatt///////o We use the gpt-3. 5- 5-turbo-0301 snapshot from March 2023.
We use code-davinci--e and gode-cushman--ee
/https://githhii http://ggthubb.oom... www
"https://spacy.ia hhttps://githan

---

Selector
GPT-Neo
LLaMA-7B LLaMA-13B
Cushman
StarCoder
GPT-3.5-Turbo
Codex
Training Free
RANDOM
5.5 (23.3)
(12.7)
(.2.9)
12.0 (32.9)
(33.5)
13.0 (:3199)
20.7 (:326)
COSINE
28.8
34,4
38.7
44.9
47.1
44.9
53.4
BM25
31.2 (+2.4)
36.7 (+2.3)
42.8 (+4.0
49.7 (+4.)
52.9 (+5.7)
50.3 (+5.4)
60.9 (+7.5)
EPR
38.3 (+9.5)
43.7 (+9.3)
48.1 (49.4)
51.8 (+7.0)
53,5 (4644)
47.4 (+2.5)
58.5 (+5.1)
Trained
CEIL
38.1 (+9.3)
44.5 (+10.1)
49.9 (+11.2
54,8 (+9.9)
57.3 (+10.)
51.2 (+6.3)
64.0 (+10.7)
BSR
34.1 (45.3)
40.1 (45.8)
46.5 (47.8)
(2.7
54.8 (47.7)
52.7 (47.8
61.2 (47.9)
Ours
SET-BSR
35.8 (+7.0)
43.8 (+9.4)
51.4 (+12.7)
59.5 (+14.6)
61.6 (+14.5)
60.1 (+15.2)
70.3 (+16.9
Table I: Average 8-shot ICL performance across all splits of semantic parsing datasets using different LLMs and demonstration-selcciin methods with absolute improvement over COSINE in brackets. Both BSR and SET-BSR outperform prior training- -rre methods, with the latter outperforming even trained methods with larger LLMs.
to the recall, precision, and Fl variants BSR, BSP, and BSFI, respectively. Unless specified otherwise, we do not apply importance weighting (IDF) and use deberta-large-mit Additionally, we experiment with (1) a ran- dom baseline (RANDOM) that randomly selects demonstrations from the pool, and (2) with the set-extensions of COSINE, BM25 and BSR de- scribed in $5 which will be referred to SET- COSINE, SET-BM25, and BET respectively.
Selector
8_$
32_C
Training
RANDOM
31.9 (-22.)
7.4 (-155)
COSINE
54.7
11.9
Free
BM25
(-107)
29.4 (+17.5)
EPR
76.3 (+21.6)
21.7 (+9.8)
Trained
CEIL
77.5 (x22.8)
40.1 (+28.2)
LFCOV
66.3 (=11.6)
45.9 (433.9)
BSR
72.5 (+17.8)
31.5 (+19.6)
Ours
SET-BSR
75.7 (+21.0)
61.2 (449.3)
Table 2: 8-shot ICL accuracy on SMCalFlow-CC us- ing Codex with absolute improvement over COSINE brackets. SET- BSR is competitive with trained methods on the IID split while dramatically outperforming them on the compositional split.
6.3.2 Trained Methods
We also compare with methods that require task or LLM-specific training. EPR (Rubin al.. 2022) uses LLM perplexity train dense retriever for each dataset. CEIL (Ye al., 2023) uses EPR and an LLM to train Determinantal Point Pro- cess (Kulesza, 2012) for each dataset and then uses it to select examples. We use Ye et al. (2023)'s implementation of EPR and CEIL and use GPT- Neo-2.7B LLM. We also compare with LFCov (Levy al., 2022), method for semantic pars- ing, specifically SMCalFlow-CS and GeoQuery. It trains a classifier to predict logical form substruc- tures and then selects diverse examples containing them. We use the shots provided by the authors.
dered by their corresponding instance-level score. For the trained baselines, we use orderings recom- mended by the corresponding authors.
7 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 demon- strations ($ 7.2) and the impact of coverage-base set selection using our set extension ($ 7.3).
6.4 Prompt Construction
7.1 Main Results
For k-shot (we use k unless specified other- wise) ICL with any given dataset ($ 6.1), demon- stration selection method ($ 6.3) and LLM ($ 6.2), we construct the prompt as follows: (1) select up to l demonstrations depending on the context win- dow of the LLM; (2) order the demonstrations in increasing order of relevance that the most relc- vant demonstrations appear closest to the test input; and (3) lincarize the ordered demonstrations and the test input using the dataset's prompt template in Table 5 and concatenate to form the prompt. For set-selection methods, the demonstrations are or-
Table compares average performance across all semantic parsing splits for seven LLMs of varying sizes. See Table 2 for comparison with LFCov, which only works with GeoQuery and SMCalFlow- CS and Table 1 for results on individual splits. While BSR consistently outperforms COSINE and BM25 for all LLMs, set-selection using SET-BSR leads further dramatic gains with upto 17% im- provement over COSINE with Codex, beating even state-of-the-ar trained methods like EPR and CEIL by 12 and 6 points, respectively. Further, from

---

Selector
GSM8K
DROP
MNLI
PAWS
SST2
Selector
ALL
IID
CОMP
Random
60.6
62.7
41.9
48
86.9
BSF1
60.6
71.0
50.1
Training Free
Cosine
64
65.4
44.0
$2.5
81.9
BSP
54.3 63.5
43.2
BM25
64.8
66.9
42.2
55.2
82.6
BSR
61.2 71.5
50.9
EPR
61.7
66.11
BM25
60.9
68.9
52.8
Trained
CEIL
63.1
71.71
+ Coverage
56.4
63.4
49.5
BM25[4-gram]
59.1
67.1
51.0
Ours
BSR
90.9
+ Coverage
64.5
68.9
60.2
Set-BSR
67.4
66.4
74.9
61.5
BM25[4-depst]
57.8
65.5
50.0
Coverage
64.9
68.6
61.2
Table 3: 8-shot ICL performance for tasks other than semantic parsing (using GPT-Neo-2.7B for the classi- fication tasks and Codex for the harder GSMSK and DROP). BSR is competitive with prior methods, how- ever, as these are IID splits, EER- doesn't lead to further gains. i 50-shot results from Ye al. (2023).
Table 4: Average 8-shot ICL performance with Codex on IID, COMPositional, and ALL semantic parsing splits. Top compares different variants of BERTSccore white Bottom compares the different variants of BM25.
vantage of larger, more powerful LLMs, becoming less effective on IID splits (Fig. 2), and failing on GSM8K (Table 3). The latter is likely because GPT- Neo-2.7B itself fails on GSM8K (Table 13), which requires Chain-of- Chain-of-Thought reasoning, an emergent ability of larger LLMs (Wei et al., 2022). As train- ing with increasingly large LLMs is prohibitively expensive and impractical, these results demon- strate serious limitations of trained methods.
15.0
Type
CEIL
BM25
BAR
Selesnt
7.2 Measure of Informativeness
Contextual embeddings capture salient aspects From Tables and 3, is clear that BSR consis- tently outperforms COSINE and BM25. This is true even when using the same encoder (see App. D), is seen in both IID and compositional splits (see Fig. 2), and with varying number of demonstrations (see Fig. 4). Larger syntactic substructures did not improve BM25 as seen in Table 4 (Bottom). These results show that contextual embeddings indeed better capturing salient aspects.
LLaM6-138
Gain in average ICL accuracy compared COSINE on IID and COMPositional splits in semantic parsing. Trained methods (EPR and CEIL) become less effective with larger LLMs IID splits. This is unlike SET-BSR, which, on compositional splits, even becomes more effective with larger LLMs.
Figure 2:
Table 3, we see that, unlike SET-BSR. BSR is effective even for non-semantic parsing datasets outperforming COSINE by 15 points on average with GPT-Nco-2.7B (see Table 12), and often even EPR and CEIL (see Table 13). All the above im- provements were statistically significant (p < 0.05) under paired permutation-tests.
Recall outperforms other measures Comparing the variants of BERTScore, for Codex in Table 4 (Top), and other LLMs in Fig. 7 in App. D, is evident that recall on par with, or better than, the Fl metric. This supports our hypothesis that recall or coverage (of salient aspects) is a useful metric for informativeness. We include additional ablations in App. D, analyzing the effeet of using importance weighting (IDF) and using a larger LM to compute token embeddings for BSR.
SET-BSR is more effective with larger LLMs The effectiveness of SET-BSR monotonically im- powerful. The trend proves LLMs become compositional splits, is particularly pronounced in
where it gets 25% absolute improvement v/s Co- SINE on average (see Fig. 2) and 49% improvement on the 32-C split SMCalFlow-CS (see Table 2).
7.3 Coverage-based Set Selection
Impact on performance From Fig. 3, we see that coverage- based set selection is most effective in compositional splits where it improves the aver- age performance of all metrics, including COSINE.
Trained methods do not leverage larger LIMMs As EPR and CEIL are trained using GPT-Nco-2.7B, they have difficulty generalizing to and taking ad-

---

Split Type = IID
Split Type COMP
Split Type = ALL
15.0
Costne
BM23 gram]
Test Accuuacy
DM2516-depal
10.0
B5R
7.5
5.0
2.5
0.0
GPrRee
LLMMA-78
(LMMA-138
Custman
SarCodar
Coder
GPrNeo
HaMAA-7B
LLMMA-138
Custman
StarCoder
Codeer
GPFNee
LLANA 78
LLMMA-138
Custman
StarCoder
Coder
LM
LM
Figure 3: Change in average performance on different types of splits of semantic parsing datasets from set-selection using our set metrics v/s the corresponding instance-level metric. Coverage-han set selection most useful compositional splits and when covering larger syntactic structures (BM25) or contextual embeddings (BSR).
Split Type =
Split Type COMP
Test Instance:
highest point of the sute with smallest population density
70-
Selected by COSINE
Test Accurag
65-
what state has the smallest population dousity
which mate has smallest population density
what the state with the lowest population deasity
Set-B5R
what is the area of the state with the smalless populotion deasity Selected by SET-BSR
BSR
BM25
Cosine
what the state with the lowest population density what is the lowest point of the state with the largest urea highes point of the state with the largest area what the the with the smallest populotion density
16
24
24
shots
#sshtt
Figure 4: Average performance on IID and COMP semantic parsing splits with Codex. SET-BSR consis- tently outperforms independent selection.
Figure S: Demonstrations selected for GeoQuery input (outputs omitted for clarity). COSINE demonstrations are redundant (repeated operations) and limited (only cover "population" " aspect). SET-BSR, instead, selects demonstrations that are similarly complex the test instance and, together, cover all required operations.
This shows the importance of selecting demonstra- tions set in compositional settings where exam- ples demonstrating all the salient aspects of the test input are even less likely to exist. The extension is less effective in IID splits and even hurts per- formance for COSINE and vanilla unigram BM25. Overall, BSR and M25 with larger substructures benefit the most from the set extension. We pro- vided further analyses of improvements from set selection and the impact of reordering in App. D.
the relevance of individual demonstrations to pri- oritize coverage of all aspects with the set (see Table 9 for an example from GSM8K). Addition- ally, even contextual token embeddings can only capture salient aspects that are explicitly expressed in the input text and thus may not be suitable for tasks where the salient aspects more abstract and require reasoning themselves (see Table 10 for an example from QNLI). We leave it to future work to explore better measures of informativeness, in- cluding better characterizations of salient aspects.
Illustrative Example We present GeoQuery test input in Fig 5 along with demonstrations (only the inputs) selected by COSINE and SET-BSR (more examples in Appendix E). COSINE selections tend to be redundant, with repeated operations, and are somewhat restrictive, mostly limited to the min operation. Contrastingly, SET- BSR exhibits more balanced selection, opting for demonstrations of comparable complexity to the test instance and collectively encapsulating all necessary operations.
Conclusion
This paper presents novel framework for select- ing informative sets of demonstrations that cover salient aspects of the test input to aid the lan- guage model (LLM) in solving it. We explore different ways to characterize these aspects and quantify their coverage. Evaluation on a wide
Failure Cases There are a few limitations of coverage-basedd set-selection using SET-BSR. First, by only considering uncovered aspects, it sacrifices

---

range of tasks and LLMS validates the effective- ness of BERTaSore-Recall as a measure of in- formativeness of individual demonstrations. Fur- ther, our results demonstrate the superiority of SET-BSR in selecting informative sets of demon- strations compositional tasks like semantic pars- ing and highlight the ability of coverage-based based demonstration selection, unlike trained methods, to leverage increasingly powerful larger LLMs. Our code base is available at https: //git/b...ttbb....// com/ Shi aatiaaahu--uuaatccclloeeeerreeee
Task-oriented dialogue as dataflow synthesis. Trans- actions of the Association for Computational Linguis- rics, 8:556-571.
Cem Anil, Yuhuai Wu, Anders Johan Andreassen, Aitor Lewkowycz. Vedant Misra, Vinay Venkatesh Ra- masesh, Ambrose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur. 2022. Exploring length gen- eralization in large language models. In Advances in Neural Information Processing Systems.
Luisa Bentivogli, Bernardo Magnini, Ido Dagan, Hoa Trang Dang, and Danilo Giampiccolo. 2009, The fifth PASCAL recognizing textual entailment challenge. In Proceedings of the Second Text Analy- sis Conference, TAC 2009, Gaithersburg Maryland, USA, November 16-17, 2009, NIST.
A Acknowledgements
We would like to thank the anonymous reviewers for their feedback. This work was sponsored in part by the DARPA MCS program under Contract No.
Sid Black, Leo Gao, Phil Wang, Connor Leahy, and Stella Biderman. 2021. GPT-Neo: Large scale autore- gressive language modeling with meshtensorflow.
N66001 1924033 with the United States Office Of Naval Research and in part by the NSF award #IIS- 2046873. The views expressed are those of the authors and do not reflect the policy of the funding agencies.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah. Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020. Language models are few-shot learners. In Ad- vances in Neural Information Processing Systems 33: Annual Conference on Neural Information Process- ing Systems 2020, NeurlPS 2020, December 6-12, 2020, viriual.
Limitations
Contextual token embeddings require the salient as- pects to be expressed in text and hence may not be able to capture them for all tasks. Moreover, since it requires computing dot product for every pair of test and candidate instance tokens, this causes it to scale quadratically with the average number of tokens making it computationally infeasible for tasks with very long textual linearizations. Future work can thus explore more general characteriza- tions of salient aspects and more efficient methods for selecting demonstrations covering them.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Ka- plan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger. Michael Petrov, Heidy Khlaaf, Girish Sas- try, Pamela Mishknn, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cum- mings, Matthias Plappert, Fotios Chantzis, Eliza- beth Barnes, Ariel Herbert- Voss. William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Carr, Jan Leike, Josh Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojciech Zaremba. 2021. Evaluating large language models trained code.
References
Sweta Agrawal, Chunting Zhou, Mike Lewis. Luke Zettlemoyer, and Marjan Ghazvininejad. 2022. In- context examples selection for machine translation.
Jacob Andreas, John Bufe, David Burkett, Charles Chen, Josh Clausman, Jean Crawford, Kate Crim, Jordan DeLoach, Leah Dorner, Jason Eisner, Hao Fang, Alan Guo, David Hall, Kristin Hayes, Kellie Hill. Diana Ho, Wendy Iwaszuk, Smriti Jha, Dan Klein, Jayant Krishnamurthy, Theo Lanman, Percy Liang, Christopher H. Lin, Ilya Lintsbakh, Andy Mc- Govern, Aleksandr Nisnevich, Adam Pauls, Dmitrij Petters, Brent Read, Dan Roth, Subhro Roy, Jesse Rusak, Beth Short, Div Slomin, Ben Snyder, Stephon Striplin, Yu Su, Zachary Tellman, Sam Thomson, An- drei Vorobev, Izabela Witoszko, Jason Wolfe, Abby Wray, Yuchen Zhang, and Alexander Zotov. 2020.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Rejichiro Nakano, Christopher Hesse, and John Schulman. 2021. Training verifiers to solve math word prob- lems.

---

Deborah A. Dahl, Madeleine Bates, Michael Brown, William Fisher, Kate Hunicke-Smitte David Pallett, Christine Pao, Alexander Rudnicky, and Elizabeth Shriberg. 1994. Expanding the scope of the ATIS task: The ATIS-3 corpus. In Human Language Tech- nology: Proceedings of a Workshop held at Plains- boro, New Jersey, March 8-11, 1994.
Pengcheng He, Xiaodong Liu, Jianfeng Gao, and Weizhu Chen. 2021. Deberta: decoding-enhanced bert with disentangled attention. In 9th International Conference on Learning Representations, ICLR I021, Virtual Event. Austria, May 3-7, 2021. OpenRe- view.net.
Charles T. Hemphill, John Godfrey, and George R. Doddington. 1990. The ATIS spoken language sys- tems pilot corpus. In Speech and Natural Language: Proceedings of Workshop Held at Hidden Valley, Pennsylvania, June 24-27,1990.
Jacob Devlin, Ming-Wei Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: Pre-training of deep bidirectional transformers for language under- standing. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Tech- nologies, Volume I (Long and Short Papers), pages 4171-4186, Minneapolis, Minnesota. Association for Computational Linguistics.
Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2019. Billion-scale similarity search with GPUs. IEEE Transactions on Big Data, 7(3):535-547.
Karen Spärck Jones, Steve Walker, and Stephen E. Robertson. 2000. A probabilistic model of informa- tion retrieval: development and comparative experi- ments part 2. hnf. Process. Manag., 36:809-844 -400.
William B. Dolan and Chris Brockett. 2005. Automati- cally constructing corpus of sentential paraphrases. In Proceedings of the Third International Workshop on Paraphrasing (IWP2005).
Daniel Keysers, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashubin, Nikola Momchev, Danila Sinopalnikov. Lukasz Stafiniak, Tibor Tihon, Dmitry Tsarkov, Xiao Wang. Marc van Zee, and Olivier Bousquet. 2020. Measur- ing compositional generalization: A comprehensive method on realistic data. In 8th International Confer- ence on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net.
Andrew Drozdov, Nathanael Schärli, Ekin Akyürek, Nathan Scales, Xinying Song, Xinyun Chen, Olivier Bousquet, and Denny Zhou. 2023. Compositional semantic parsing with large language models. In The Eleventh International Conference on Learning Representations.
Dheeru Dua, Yizhong Wang, Pradeep Dasigi, Gabriel Stanovsky, Sameer Singh, and Matt Gardner. 2019. DROP: A reading comprehension benchmark requir- ing discrete reasoning over paragraphs. In Proceed- ings of the 2019 Conference of the North American Chapter of the Association for Computational Lin- guistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 2368-2378, Min- neapolis, Minnesota. Association for Computational Linguistics.
Denis Kocetkov, Raymond Li, Loubna Ben Allal, Jia Li, Chenghao Mou, Carlos Muñoz Ferrandis, Yacine Jernite, Margaret Mitchell, Sean Hughes, Thomas Wolf, Dzmitry Bahdanau, Leandro von Werra, and Harm de Vries. 2022. The stack: 3 tb of permissively licensed source code.
Alex Kulesza. 2012. Determinantal point processes for machine learning. Foundations and Trends@ in Machine Learning, 5(2-3):123-288
Catherine Finegan-Dollak, Jonathan K. Kummerfeld,
Li Zhang, Karthik Ramanathan, Sesh Sadasivam, Rui Zhang, and Dragomir Radev. 2018. Improving text- to-SQL evaluation methodology. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pages 351-360, Melbourne, Australia, Association for Computational Linguistics.
Itay Levy, Ben Bogin, and Jonathan Berant. 2022. Di- verse demonstrations improve in-context composi- tional generalization.
Haoran Li, Abhinav Arora, Shuohui Chen, Anchit Gupta, Sonal Gupta, and Yashar Mehdad. 2021. MTOP: A comprehensive multilingual task-oriented semantic parsing benchmark. In Proceedings of the 16th Conference of the European Chapter of the Asso- ciation for Computational Linguistics: Main Volume, pages 2950-2962, Online, Association for Computa- tional Linguisties.
Leo Gao, Stella Biderman, Sid Black, Laurence Gold- ing. Travis Hoppe. Charles Foster, Jason Phang. Horace He, Anish Thite, Noa Nabeshima, Shawn Presser, and Connor Leahy. 2020. The pile: An 800gb dataset of diverse text for language modeling.
Shivanshu Gupta, Sameer Singh, and Matt Gardner. 2022. Structurally diverse sampling for sample- efficient training and comprehensive evaluation. In Findings of the Association for Computational Lin- guistics: EMNLP 2022, pages 4966-4979, Abu Dhahi, United Arab Emirates. Association for Com- putational Linguistics.
Raymond Li, Loubna Ben Allal, Yangtian Zi, Niklas Muennighoff. Denis Kocetkov, Chenghao Mou, Marc Marone, Christopher Akiki, Jia Li, Jenny Chim, Qian Liu, Evgeni Zheltonozhskii. Terry Yue Zhuo, Thomas Wang. Olivier Dehaene, Mishig Davaadorj. Joel Lamy-Poirier, João Monteiro, Oleh Shliazhko, Nicolas Gontier, Nicholas Meade, Armel Zebaze, Ming-Ho Ho Yee, Logesh Kumar Umapathi, Jian Zhu, Benjamin Lipkin, Muhtasham Oblokulov, Zhiruo
Matan Hasson and Jonathan Berant. 2021. Question decomposition with dependency graphs.

---

Wang, Rudra Murthy, Jason Stillerman, Siva Sankalp Patel, Dmitry Abulkhanov, Marco Zocca, Manan Dey, Zhihan Zhang, Nour Fahmy, Urvashi Bhattacharyya, Wenhao Yu, Swayam Singh, Sasha Luccioni, Paulo Villegas, Maxim Kunakov, Fedor Zhdanov, Manuel Romero, Tony Lee, Nadav Timor, Jennifer Ding. Claire Schlesinger, Hailey Schoelkopf, Jan lieer,, Tri Dao, Mayank Mishra, Alex Gu, Jennifer Robinson, Carolyn Jane Anderson, Brendan Dolan-Gavitt Dan- ish Contractor, Siva Reddy, Daniel Fried, Dzmitry Bahdanau, Yacine Jernite, Carlos Muñoz Ferrandis, Sean Hughes, Thomas Wolf, Arjun Guha, Leandro von Werra, and Harm de Vries. 2023. Starcoder: may the source be with you!
Empirical Methods in Natural Language Processing, pages 9157 9179, Abu Dhabi, United Arab Emirates. Association for Computational Linguisties.
Nils Reimers and Iryna Gurevych. 2019. Sentence- BERT: Sentence embeddings using Siamese BERT- networks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natu- ral Language Processing (EMNLP-IJCNLL)) pages 3982-3992, Hong Kong, China. Association for Com- putational Linguistics.
Stephen Robertson, Steve Walker, Susan Jones, Miche- line Hancock-Bcaulicu, and Mike Gatford. 1993, Okapi at trec. 500207, pages 109-123. National Institute of Standards and Technology.
Jiachang Liu, Dinghan Shen, Yizhe Zhang. Bill Dolan, Lawrence Carin, and Weizhu Chen. 2022. What makes good in-context examples for GPT-3? In Proceedings of Deep Learning Inside Out (DeelJO 2022): The 3rd Workshop on Knowledge Extrac- tion and Integration for Deep Learning Architectures, pages 100-114, 14, Dublin, Ireland and Online. Associa- tion for Computational Linguistics.
Ohad Rubin, Jonathan Herzig, and Jonathan Berant, 2022. Learning to retrieve prompts for in-context learning. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Tech- nologies, pages 2655-2671, Scattle, United States. Association for Computational Linguisties.
Pan Lu, Liang Qiu, Kai-Wei Chang, Ying Nian Wu, Song-Chun Zhu, Tanmay Rajpurohit, Peter Clark, and Ashwin Kalyan, 2023. Dynamic prompt learning via policy gradient for semi-structured mathematical reasoning.
Timo Schick and Hinrich Schütze. 2021. Exploiting cloze-questions for few-shot text classification and natural language inference. In Proceedings of the 16th Conference of the European Chapter of the Asso- ciation for Computational Linguistics: Main Volume, pages 255-269. Online. Association for Computa- tional Linguistics.
Yao Lu, Max Bartolo, Alastair Moore, Sebastian Riedel, and Pontus Stenetorp. 2022. Fantastically ordered prompts and where find them: Overcoming few- shot prompt order sensitivity. In Proceedings of the 60th Annual Meeting of the Association for Compu- tational Linguistics (Volume 1: Long Papers), pages 8086-8098, Dublin, Ireland. Association for Compu- tational Linguistics.
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang. Christopher D. Manning, Andrew Ng. and Christopher Potts. 2013, Recursive deep models for semantic compositionality over sentiment treebank. In Proceedings of the 2013 Conference on Empiri- cal Methods in Natural Language Processing, pages 1631-1642. Seattle, Washington, USA. Association for Computational Linguistics.
Joram Meron. 2022. Simplifying semantic annotations of SMCalFlow. Proceedings of the 18th Joint ACL- ISO Workshop on Interoperable Semantic An- notation within LREC2022, pages 81-85, Marseille, France. European Language Resources Association.
Hongjin Su, Jungo Kasai, Chen Henry Wu, Weijia Shi, Tianlu Wang. Jiayi Xin, Rui Zhang, Mari Ostendorf, Luke Zettlemoyer. Noah A. Smith, and Tao Yu. 2022. Selective annotation makes language models better few-shot leameer.
George L. Nemhauser, Laurence A. Wolsey, and Mar- shall L. Fisher. 1978. An analysis of approximations for maximizing submodular set functions-2 -i. Mathe- matical Programming, 14:265-294.
Linlu Qiu, Peter Shaw, Panupong Pasupat, Pawel Nowak, Tal Linzen, Fei Sha, and Kristina Toutanova. 2022a. Improving compositional generalization with latent structure and data augmentation. In Proceed- ings of the 2022 Conference of the North Ameri- can Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 4341-4361 Seattle, United States. Association for Computational Linguistics.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. 2023. Llama: Open and efficient foundation language models.
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. 2018. GLUB: A mulli-taskk benchmark and analysis platform for nat- ural language understanding. In Proceedings of the 2018 EMNLP Workshop BlackboxNI.P: Analyzing and Interpreting Neural Networks for NLP, pages 353-355, Brussels, Belgium. Association for Com- putational Linguistics.
Linlu Qiu, Peter Shaw, Panupong Pasupat, Tianze Shi, Jonathan Herzig, Emiiy Pitler, Fei Sha, and Kristina Toutanova. 2022b. Evaluating the impact of model scale for compositional generalization in semantic parsing. In Proceedings of the 2022 Conference on

---

Xinyi Wang, Wanrong Zhu, Michael Saxon, Mark Steyvers, and William Yang Wang. 2023. Large lan- guage models are implicitly topic models; Explain- ing and finding good demonstrations for in-context learning.
John M. Zelle and Raymond J. Mooney. 1996. Learn- ing to parse database queries using inductive logic programming. In Proceedings of the Thirteenth Na- rional Conference on Artificial Intelligence Volume 2, 9AAI',,, pages 1050-1055. AAAI Press.
Yushi Wang. Jonathan Berant, and Percy Liang. 2015. Building semantic parser overnight. in Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume I: Long Papers), pages 1332-1342, Beijing, China, Association for Computational Linguistics.
Tianyi Zhang, Varsha Kishore, Felix Wu, Kilian Q- Weinherger, and Yoav Artzi. 2020. Bertscore: Evalu- ating text generation with BERT. In 8th International Conference on Learning Representations. ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenRe- view.net.
Yuan Zhang, Jason Baldridge, and Luheng He. 2019. PAWS: Paraphrase adversaries from word scrambling. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computa- tional Linguistics: Human Language Technologies, Volume I (Long and Short Papers), pages Minneapolis, Minnesota. Association for Computa- tional Linguistics.
Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, Ed H. Chi, Tatsunori Hashimoto, Oriol Vinyals, Percy Liang, Jeff Dean, and William Fedus. 2022. Emer- gent abilities of large language models.
Jason Wei, Xuezhi Wang. Dale Schuurmans, Maarten Bosma, Brian Ichter. Fei Xia, Ed Chi, Quoe Le, and Denny Zhou. 2023. Chain-of-thought prompting elic- its reasoning in large language models.
Zihao Zhao, Eric Wallace, Shi Feng, Dan Klein, and Sameer Singh. 2021. Calibrate before use: Improv- ing few-shot performance
language models. Priceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Vir- tual Event, volume 139 of Proceedings of Machine Learning Research, pages 12697-12706. PMLR.
Adina Williams, Nikita Nangia, and Samuel Bowman. 2018. A cover-coverage challenge corpus for sen- tence understanding through inference. In Proceed- ings of the 2018 Conference of the North American Chapter of the Association for Computational Lin- guistics: Human Language Technologies, Volume 1 (Long Papers), pages 1112-1122 122, New Orleans, Louisiana. Association for Computational Linguis- tics.
Tomer Wolfson, Mor Geva, Ankit Gupta, Matt Gard- ner. Yoav Goldberg. Daniel Deutch, and Jonathan Berant. 2020. Break it down: A question understand- ing benchmark. Transactions of the Association for Computational Linguistics, 8: 183-198.
Zhiyong Wu, Yaoxiang Wang, Jiacheng Ye, and Ling- peng Kong. 2023. Self-adaptive in-context learn- ing: An information compression perspective for in- context example selection and ordering.
Jiacheng Ye, Zhiyong Wu, Jiangtao Feng. Tao Yu, and Lingpeng Kong, 2023, Compositional exemplars for in-context learning.
Xi Ye, Srinivasan Iyer, Asli Celikyilmaz, Ves Stoy- anov, Greg Durrett, and Ramakanth Pasunuru. 2022. Complementary explanations for effective in-context learning.
Pengcheng Yin, Hao Fang, Graham Neubig, Adam Pauls, Emmanouil Antonios Platanios, Yu Su, Sam Thomson, and Jacob Andreas. 2021. Compositional generalization for neural semantic parsing via span- level supervised attention. Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 28 2810-2823, Online. Association for Computational Linguistics.

---

A Submodularity
Proof. From Theorem A.I, the function fs (z) de- fined as fz(Z) max c(s, 2) is submodular for =EZ
Definition A.1 (Submodular Function). If Ω is finite set, submodular function is set function f 2 + R, where 2 denotes the power set of Ω. which satisfies one of the following equivalent conditions.
any definition of c(s, 2). Further, since from Theo-
rem A.2, the sum of submodular functions is also submodular, setcov (Irest Z)
Σ
fz(Z) is
.ESrga
submodular.
1. For every X,Y C Ω with X C Y and every E Y we have that ((XU(x)) f(x)
B Datasets
U U(UU()) f(Y).
We use 15 diverse datasets, including 6 semantic parsing, numerical reasoning, and classification datasets.
2. For every S,T _ Ω we have that f(S) +
f(T) 2
B.1 Semantic Parsing
3. For every X S Q and 21,42 2 such
We use 6 semantic parsing datasets with ITD and compositional splits for our experiments. Table 5 shows sample instances from each dataset we experiment with along with the textual template to linearize the instances. The ICL prompt is constructed by concatenating the templatized demonstrations and the test instance using \n the separator.
that xı # 22 have that f (X U (a1])
(XX (x2)) (XU (31, x2)) + (XX..
Theorem A.1. The function faa (X) = max Wy =EX is submodular for any assignment of weights Wa to the elements E Ω
Proof. The following are clearly true for any x E Ω and any I1, 72 E Ω such that Wzy > Was:
GeoQuery (Zelle and Mooncy, 1996): dataset containing 880 natural language questions about US geography paired with Prolog programs. In addition to the standard (IID) split, we experiment with three types of compositional splits: (1) Tem- plate split where the training and test sets have disjoint program templates (Finegan-Dollak al., 201 8); (2) TMCD split which creates train and test sets with maximal compound divergence and min- imal atom divergence (Keysers et al., 2020); and (3) Length split which evaluates for length gener- alization by testing on sequences longer than ones in training. Following Levy et al. (2022), we use the compositional splits three Template, threc TMCD, and one Length generated by Qiu al. (2022a) and average results across the TMCD and Template splits.
1. fmaxw (XU 2 f(x)
2. fmaxw (x(((1)) = fmaxw {x1,
Adding these two inequalities together, we get the third definition of submodularity and thus fmaxw is submodular.
Theorem A.2. If (ft) all submodular func-
tions, then Σ Ji is also submodular.
Proof. We show this for 2:
(/1 + +
= (X) f2(2))
ATIS (Hemphill et al., 1990; Dahl et al., 1994): dataset of natural language queries about avi- ation paired with X-calculus programs. We ex- periment with an IID split and Template split FFinega-Doolak et al., 2018) for evaluating com- positional generalization, both taken from (Gupta et al., 2022).
< +
(8)
Therefore, f1 + f2 is submodular using the second definition of submodularity. By induction, this is true for any number of functions.
Overnight (Wang al., 2015): dataset contain- ing both synthetic and natural language utterances from domains (e.g. socialnetwork, restaurants, etc.) paired with Lambda-DGe logical forns. We experiment with an IID and a Template split of
Theorem A.3. The set-level coverage metric setcov (Irest Z) as defined in Eq. 6 is submodu- lar for any definition of c(s,2).

---

the socialnetwork domain taken from (Gupta et al., 2022).
Classification: For this category, we experiment
with three Natural Language Inference (NLI) datasests (QNLI (Wang et al., 2018), MNLI (Williams et al., 2018), and RTE (Bentivogli et al., 2009)), three Paraphrase Detection datasets (MRPC (Dolan and Brockett, 2005), PAWS (Zhang et al., 2019), and QQP (Wang et al., 2018)) and one Sentiment Classification dataset (SST2 (Socher et al., 2013)).
SMCalFlow (Andreas et al., 2020): A dataset of task-oriented natural language dialogs about calen- dars, weather, places, and people paired with exe- cutable dataflow programs. SMCalFlow-CS (Yin et al., 2021) is subset of SMCalFlow containing single-turn dialogs involving two domains (organi- zation structure and calendar event creation), each having its own set of program symbols with two types of test sets: a cross domain (C) test set con- taining only instances where both domains appear and meant to test for compositional generalization, and single-domain (S) test set contains instances with only single-domain for in-distribution evalu- ation. For compositional evaluation, we use the 32-C split which is few-shot cross-domain split where the training set includes 32 cross-domain examples. For our IID evaluation, following Levy al. (2022), we use the 8-S split. Additionally, we use the programs with the simplified syntax provided by (Meron, 2022).
C Selection Time
cross-domain
Despite their (LTd) time complexity, we found example selection using both BSR and SET-BSR to be fast enough to not be a bottleneck to in- context learning for most datasets considered this work. By using a GPU to compute c(x, z)s, we could get both to work in the order tens of milliseconds per test input on average which was significantly faster than the LLM inference time itself. The exceptions were DROP, PAWS, QQP, MNLI and QNLI for which the selection took >1 second due much longer instances and/or larger instance pool. We leave it to future work to explore more efficient ways to measure informativeness.
BREAK (Wolfson et al., 2020) is a dataset that maps complex natural language questions into a language- based meaning representation (QDMR)
D Additional A Analyses
comprising ordered list of atomic steps neces- sary to answer the question. Following (Rubin al., 2022), we use the low-level Break subset where the targets are logical forms comprising lists of operators with their arguments based on the cor- responding QDMR.
BM25 From Fig. 6 we can see that coverage-based selection using BM25 with larger substructures out- performs vanilla unigram BM25 in compositional splits.
HERTScorr-Reeate Recall Examining the impact of im- portance weighting in Fig. 8 which compares the performance change with using importance weight- ing (IDF) in BSR, we can see that its effect is not consistent across different LLMs. We also did not see any consistent improvement from using larger Saberta-large-mee for computing token embeddings for instance- level BSR (see Fig. 9). However, it did help with set-level selection using SET-BSR.
MTOP (Li et al., 2021): multilingual task- oriented semantic parsing dataset spanning six lan- guages and 11 domains. The target commands are complex queries featuring nested intent-slot pre- diction. We use the English subset of MTOP from (Rubin al., 2022).
B.2 Non-Semantic Parsing
We additionally experiment with the standard IID splits non-semantic parsing datasets from the following categories:
Reordering We found the reordering of demonstra- tions according to the corresponding instance-level metric to only be necessary for smaller LLMs (see Fig. 10), with it even hurting the performance of larger LLMs. We believe this is because larger and unde-pretrained LLMs more capable at com- posing the salient aspects in the different demon- strations and taking advantage of the full context.
Numerical Reasoning: For this category, we experiment with GSM8K (Cobbe et al., 2021), a cfain-of-thought reasoning (Wei et al., 2023) dataset of grade school-level arithmetic reasoning problems expressed in natural language and DROP (Dua et al., 2019), dataset of question-answa pairs where the questions are about paragraphs con- taining numerical information and the answers are spans in the paragraph.
BSR outperforms Cosine even with the same encoder In $ 7.2, we showed that BSR with

---

Dataset
Example Template
Sample Instance
Ovemight
(source))t(tareet)
employees who finish after alices birthday
target: (call listvalue (call getProperty ((lambda (call filter (var
(string employmentt_end_datee (string (call ensureNumericEntitty (call getProperty en. person.sonnoo alice (string
(call InsureNumericProperre
birthdate))))) (call domain (string employee))) (string employee)))
ATIS
(source)\t(target)
source: give the flights from pittsburgh los angeles thursday evening
target: Lambda
during. day 50 evening and flight los_angeles pd ) from pittsburgh
day
thursday
GeoQuery
source: which river traverses most states
target: answer { most rriver, traverse_2 state )
SMCalFlow (source)\t(target)
source: Please put a c'clock on my schedule where I'm meeting with boss Daniel. Daniel
target:
CreateEvent (AND (with_attendeee
") staarts_at (tteeeeeme(eeeeeeeeeee((
BREAK
(sturce))t(targett source: there another cube that is the same size as the cyan cube; what color is it?
target: return the cyan cube ;return size of #1 ;return cubes besides rrturrn sizes of ;return #3 where #4 the same as ;return color of #55
МТOP
(source)[t(target)
from target: [IN:GET BONOEE_STRIESSSSSSEE NEWS [SL: DATE, TIME latest [SL:NEWS_TYP news J NEWWSSORRREE washington times ]
source: latest news from washington times please
Table 5: Semantic Parsing Datasets with corresponding sample instances and example templates used in for ICL.
deberta-large-min outperforms Cosine with all pll-mpnet-base-ee Tables 15, 16, 17, and 18 show that the same trend holds even when using the same encoder, bert bert-base-uncased, for both metries confirming that contextual embeddings indeed better capturing salient aspects.
for all the semantic parsing datasets. For numeri- cal reasoning and classification datasets, Tables 12 and 13 compare 8-shot ICL performance with prior training- faneeng-free and trained methods, respectively. Ta- ble 14 provides average performances across all datasets.
Additionally, Tables 15, 16, 17, 18, 20, and 21 contain results on semantic parsing datasets of all ablations learning- free selection methods we ran, with GPT-Neo-2.715 LLaMA-7B, LLaMA- 13B, StarCoder, Cushman, and Codex, respectively, We did not run ablations on GPT-3.5-Turbe due to its cost.
Recall of Syntactic Structures The improvements from set-based selection may be explained by Fig. 11 where we see that set-extensions COSINE and unigram BM25 reduce the recall of substruc- tures of the test input whereas the recalls increase with set-extensions of both AM25[4-GRAA and BM25(4-DEPSTJ, and even BSR, which does not explicity consider these substructures.
E Qualitative Analysis of Prompts
Tables 7, 8 show demonstrations selected using COSINE and SET-BSR for instances from MTOP and SMCalFlow-CS respectively. In each case, Co- SINE find demonstrations that are all very similar to the test input but fails to demonstrate some salient aspect, whereas BSR selects less similar instances but ensures complete coverage of all salient aspects. Tables 9 and 10 additionally illustrate limitations of set-selection and of token-cnn -aeeneembediings in capturing salient aspects.
All Results
Tables Il contains 8-shot ICL results for our pro- posed methods and prior learning- free and learning- based demonstration selection on all the LLMs

---

Spitt Type -
SpiP Type COMP
Spli Type ALL
30-
2-
gram)
30
-15
40-
HAM6678
Cuttoan
PlarCadd
Coden
SPrwe
HAMM77
Caahesk
Copeer
Gatmaa
StarCadio
Coden
4.
Figure 6: Absolute improvement in average 8-shot ICL performance on different types of semantic parsing splits from using the set extensions SET- B----M255 with larger substructures over vanilla BM25.
Syoe
Spik Type
Spitt Type
apmates
Llama 78
Oabman
SaeCodet
Codes
oPrate
13 136
Curman
Starbaaer
Codlet
arr nes
UaMM-7
Chahnan
SarCode
Coler
Figure 7: Comparison of 8-shot ICL performance of different variants of BERTScore with token embeddings computed using deberta-base-mm11 i. For easier visualization, since we found BERTScore- Pecec---eeiiinnn to consistently perform worst, we show absolute improvement in average performance on different types of splits from the recall and Fl metrics over the precision metric.
UM Nov
UK L3M
Ui Custman
StarCoder
Un
color
1400 1p0
Sp6t Tyae
S2. Spm
Sp41 Tyae
S0.1 Mp
S1.
Figure 8: Impact on average 8-shot ICL performance on semantic parsing splits from using importance weighting (IDF) BSR.
Split Type = IID
Split Type COMP
Split Type ALL
2.0
1.5
1.0-
1.0
0.5
0.
esRjarge) Set-aSt(arge))
-05
0.0
-0.5
-05
OPE/Ne
Lastee LLMM6778
L38
Custonan
StarCader
Coder
LLaMM
13M
Coliman
SaeCodee
Coleer
LLAM4-78
Labhle 138
Galoman
StaCodee
Codeee
M
Figure 9: Impact on average 8-shot ICL performance on semantic parsing splits from using larger in BSR
Siteerta-lrre-mmee mnrge LLM for computing contextual token embeddings v/s using and SET-BSR.

---

Datasct
Example Template
Sample Instance
GSM8K Question: (question)
question: Natalia sold clips 48 of her friends April, and then she sold half as many clips in May. How many clips did Natalia sell altogether April and May?
Solution: (solution)
solution: Natalia sold 48/2 #48/=22422 clips in May. Natalia sold 48+24
448+24772-72 clips altogether in April and May. #688
DROP
Passage: {passage)
passage: To start season, Lions traveled south Tampa, Florida take on the Tampa Bay Buccaneers. The Lions scored first the first quarter with a 23-yard field goal by Jason Hanson, The Buccaneers tied it up with 38-yard field goal by Connor Barth, then took the lead when Aqib Talib intercepted a pass from Matthe Stafford and ran in 28 yards. The Lions responded with 28-yard field goal. In the second quarter, Detroit took the lead with 36-yard touchdown catch by Calvin Johnson, and later added more points when Tony Scheffler caught an 1l-yar TD pass. Tampa Bay responded with a 31 31-yard field goal just before halftime. The second half was relatively quiet, with each team only scoring one touchdown, First, Detroit's 's Calvin Johnson caught a I-yard pass in the third quarter. The game's 's fonal points came when Mike Williams of Tampa Bay caught 5-yard pass. The Lions won their regular season opener for the first time since 2007
Question: (question)
Answer: (answer)
question: How many points did the buccaneers need to tie in the first?
answer: 3
QNLI
Question: {question)
sentence: Unlike the two seasons before it and most of the seasons that followed, Digimon Tamers takes a dorker and more realistic approach to its story featuring Digimon who do not reincarnate after their deaths and more complex character development in the original Japanese.
Sentence: (sentence)
Answer: (label}
question: When did the third Diginon series begin?
label: No
MNLI
Premise: (premise)
premise: The new rights are nice enough
Hypothesis: (hypothesis}
hypothesis: Everyone really likes the newest benefits
Answer: (label}
label: Maybe
RTF
Premise: (premise)
premise: Dana Reeve, the widow of the actor Christopher Reeve, has died of lung cancer at age 44, according the Christopher Reeve Foundation.
Hypothesis: (hypothesis)
Answer: (label}
hypothesis: Christopher Reeve had accident.
label: Yes
MRPC
Sentence 1: (sentence1)
sentencel: He said the foodservice pie business doesn 't the company 's long -eemm growth strategy.
Sentence (sentence2)
Answer: (label)
sentence2: " "hhe foodservice pie business does not fit long-term growth strategy
label: Yes
PAW'S
Sentence (sentence1) Sentence (sentence2)
sentencel: Bradd Crellin represented BARLA Cumbria on tour of Australia with other players representing Britain. also a of Australia. sentence2: "Bradd Crellin also represented BARLA Great Britain tour through Australia a tour through Australia with other players representing Cumbria. label: No
Answer: {label}
QQP
Question (question1)
questionl: Why are African- Americans so beautiful?
Question 2: [question2)
question2: "Why are hispanics so beautiful?
Answer: (label} Review: (sentence)
label:
SST2
sentence: it charming and often affecting jofeettennooureey.. label: Positive
Answer: (label)
Table 6: Non-Semantic Parsing Datasets with corresponding sample instances and example templates used for ICL.
US OeTiNoo
LV- LLAM6-77 75
LM 130
JI Culhrer
LI SarCookr
UN Coder
S4 5000nii-ggmm
colon hyo
Tane
Figure 10: Impact average 8-shot ICI. performance on semantic parsing splits from reordering the demonstrations selected by the different set-level metric using the corresponding instance- metric as absolute gain v/s the unreordered version.

---

Selector
Prompt
Ell1 "),starts_at (Tt.rrrtetttrrrrrrr)))..).._._ Sentence: Easy vegan,
Logical Form: (IN:GET [SL ALLBBECIPES_ATTRIBUTEE Easy RECTPESSS__ vagan 1
Sentence: Yegetarian recipes
Logical Form: GET_EIEES REEE Vegetarian ]
COSINE
Sentence: Please rind nе vegan recipes
Logical Form: [IN:GEL_RECIPES [SL:RECIPES_TTP
Sentence: Give
Logical Form: CEN RYCTPES___VE vegan
Sentence: I have a nut ellergy. Find ne dessert recipe nut RECTPEECES dessert
Logtcal Form: (ECIGET
Sentence:
nessage
plan options
fanily
week
SET-BSR
Logicol Form: SEND_MESESSSAGE [SPNNEET_ video RECIPECNN Victoria ]
Sentence: what are some na-bake dessart ideas
Logical CENECEESS RECIPPS_CCCKTNECCC no RECIPES_NEAL
]]
Sentence: Vegan birthday cakes
Logicel Form: RECCIECS [SL:RECIPES_THE Vegan
[SL: RECIPERS birthday cakes
Table 7: Demonstrations selected for the MTOP input: Vegan desert options with target output (IN:GETREECIPES [SL:RECIPES_TYPE Vegan ] [SL:RECIPES_DIS birthday cakes J. COSINE's re- liance on single dense embedding means unable to account for fact that "options" could mean dishes and not just recipes.
Selector
Prompt
Sentence: need necting with Elli tоnоrrои Legicel Forn: (MaieEeeeetMDDiiiii.ttteeeee Elli ").sterts_ast (Tonorrow starts_at (NunberPM (11))))
Sentence: Set meeting with Elli for tonorrow 2 pn through the end of the day and call it Logical Form: CreateEvent (Ait (andds_ata (DateTine Tooaro= (im==Nubbbrrwxx EndOFMorkday "ith_attendce(" Elli ") hubbsssueeeet Recap ((oerrts starts_at (Nunerra(())))))P
COSINE
Sentence: Schedule necting with
тологгeи pm through tha (ANDeess (AND (E Toooro=))))))) (4)) EndO/Mork0ay
workday
Legical Form:
Sentence: Schedule neeting with Elli from 4 PM until the end of the tоnorroи Logical Form: CreatoEvent (Attatteeen (F (daatssTooorrow) (), (in--)) EndoFWorkday ())) with)).kthhhhhheeeeeeeeee Elli stattttssatt (Tamrrrww()) atarts_ (4)))
Sentence: I need doctor 's apsvintment Nednesday norning
Logical Form: CreateEvent
(AND(has_Subjer) (ANDhhEs starts_at(Nexttow WEDNESDAY "}}})
dactor appointment "), 2,stertts.at
Sentence: I need to see Alice and har boss next Honday at 3 Alice witth__tteedeee( attendee(Findaaaggee Alice ")),
Logical Form: CreateEvent (Mi((iih_attenee (tarts_at(NextDDWC HONDAY (ttortssatt(unnbeeMM31))
SET-BSR
Sentence: Schedule neating with Jake Ells Jesse Friday pm (MD(Citth Logical Form: attrtts FRIDAY Jesse "ittth_attendee" Jake "t.htth__ttendee""
Sentence: I need schedule neeting with Jeff 's superviser Lynne for tonorrow at 18
Logical Forn: CreateEvent (MMiieeeeeenDDiiiittttttteeee Lynne (estrrtsst(TTeerrroo))))))) NunberAH(18)))
Table 8: Demonstrations selected for the SMCalFlow -S input: Schedule meeting with Elli and her manager 's boss tomorrow morning. SET-BSR is able to find demonstrations covering all fragments of the test input while COSINE fails include anything which involves finding someones manager.

---

Selector
Prompt
Question: Justin has
height. length height and 4 tines its width. what is the velune of the box? The is 26 inchas
is
COSINE
question: John builds inch thick on each side. How nuch is the internal volune in cubic feet?
inches by 14 inches. The walls
Question: A window is nade up of 8 glass panes. Each pane has a langth of 12 inchas and a the window?
BSR
width inches. what
Question: John builds a bex. The box is 26 inches by inches by 14 inches. The walls are Inch thick on each side. How nuch the internal volure in cubic feet?
Question: Jazel has sticks. stick centineters
The second stick twice long while the third stick is centineter shorter than the second stick. What is the together?
SET-BSR
total length of Jazel's 's sticks when they box.
Question: John
i8 inches by inches by inches- walls inch thick on each side. How nuch is the internal volune in cubic feet?
Table 9: Demonstrations selected by different methods for the GSM8K input: John has boxes. Each box is 5 inches by 6 inches by inches. The walls are inch thick. What is the total inner volume of all boxes? We only show the inputs for clarity. Only BSR solves this input (2-shot ICL with Codex). All three methods select one example that demonstrates most of the aspects of the test input, i.e., computing the volume a box after subtracting wall thickness. The remaining aspect computing the total quantity computed for 3 identical items. COSINE fails to do so, selecting yet another example that requires computing single box's volume. Since SET-BSR prioritizes coverage of the remaining aspect, it selects an example that has exactly three items whose total length has be computed but overall to find example that demonstrates all aspects by itself and happens to find one that partially demonstrates the remaining aspect as well.
very similar in reasoning. BSR on the other hand tries
Selector Prompt
Begun in 1950 and opened to traffic in 1968, the bridge is txa-tiered read and rail design spanning 4,608 river itself. Can we
upper deck, approxinately 1,560 spanning
know "What type of design is the bridge?"? Yes
The BBC also Introduced Ceefax, the first teletext service, starting 1974, Can know "What was Leefax?"? Yes
BSR
Sanitation and Hygtene (NSH) progran of the Foundation launched 22e5 as "Learning Initiative," " and becane full-fledged progran under the Global Developnent Division early 2818. Can know "What the MSH program launched in 2005 Yes
Television broadcasting Hyderabad began Government of India's 's public service broadcaster. which transnits two free-to- terrestrial television channelsand satallite channel. know "Mhat Boordarshan ?n Yes
Doordarshan, the
Table 10: Top four demonstrations selected by different methods for the QNLI input: Telenet was incorporated 1973 and started operations 1975. Can we know "What was telenet Since BSR doesn't 't have access the labels and also cannot reason about the inputs themselves, it cannot account for the fact that the context in the test input does not contain the answer for the question and selects demonstrations that are all answered "Yes" even though the answer the test input is "No".

---

Dataset
ATIS IDDTempl.
Overnight IDD/empl.
Break
MТОP
GeoQuery IDD/eepp/TTMCDI.en.
SMCalFlow-C5 8_8/32_C
AVERAGE
Split
IID
IID
AIVIID/Comp.
LM
Selector
EPR
66.1/12.
5.93/0.9
29.9
62.2
714/33.6/43.//23
54.5/3.6
38.3 56.1 20.5
GPT-Nco-2.7B
CEIL
68.8/18.7
$0.7/2.1
29.9
60.5
65.4 /43.6/25.2
59.1/3.8
38.1/55.6 20.6
Random
1..4/000
3.6/0.0
1.9
1.3
17.5/ 11.0/14.0/0/
14.0/0.9
3.0/0.0
6.5/ 6.666.64.44. 4.3
Cosine
46.1/6.5
38.3/0.4
22.3
43.9
/
/2.4
25.2/1.2
28.8 17.0
BM25
49.5/7.4
33.7/3.0
26.5
47.7
63.6/ /2.1.//2..//..5
32.0/3.2
31.2/42.2/ 20.3
BSR
48.3/7.8
40.1/266
29.1
54.5
67.1 47.1/4077/47.7//
39.7/3.5
34.1 46.. /
Set-BSR
54.6/134 13.2
43.2/49
28.6
4../45.3/454//222
41.5/48
35.8 48./48.4//1
EPR
73.0/2100
57.7/188
33.2
65.2
75.4 /
45.8 30.3
64.0/8.0
43.7/614/ 26.0
LLaMA-7B
CEIL
74.0/30.5
55.8/4.4
36.1
66.8
66.8 50.5 /4.2
67.4/119
44.5/6L.1
Random
9.0
4.2/0.5
8.8
2.8
13.3//9/.444
6./00.0
5.7/68 /4.6
Cosine
16.7/11.5
48.7/0.0
26.1
49.8
42.6/
37.13322
34.4/48.8/ 20.0
BM25
61.0/12.5
45.1
30.1
53.6
67.9 39.5 /
43,419.5
50.2
BSR
60.9 14.3
51.2/3.0
32.5
33.3 /
54.1
40.1 55.0 25.2
Set-BSR
64.2
5..5/6.3
33.7
61.9
76.1 52.3/ /
54.5/19.3
43.8/57.0/ 30.6
EPR
28.3/28.2
6..6/0.7
37.2
68.3
80.4 57.5
/
66.5/119
48.1 /5//550/312
LLaMA-13B
CEIL
76.1/36.7
59.1/4.9
38.8
71.2
75.7 / 59.3 55.55
68.3/2100
49.9 64.9/ 34.9
Random
19.5/5.1
3.4/2.6
9.0
4.8
23.9 19.8
1.5
14.0/0.0
9.8 12.4 7.2
Cosine
57.8/20.5
48.6/3.0
29.4
54.0
77.1 44.8 48.5
42.915.4
38.7 25,8
BM25
65.6/22.6
50.3/58
34.6
58.7
76.4 49.33/ /
50.3/
48.2/13.6
42.8 29.9
BSR
64.0/22.8
55.7/5.8
37.7
64.4
79.6 / 60.1 38..
60.1
46.5 / 60.3 32.8
Set-BSR
63.6
5..6/8.6
39.2
66.1
81.8 64.1/ 60.2
/1.4/6.11/39 62.5
EPR
75.8/42.9
6..2
41.5
72.6
85.4 64.6//////////
69.8/
/3.5 38.5
StarCoder
CEIL
79.2
64.6 17.6
42.5
73.7
85.0/ 7..0/00./1.3. / 39.7
71,0//18
/ /
Random
22.2/12.0
10.8/3.
8.8
4.7
20.1/0.0
13.6 15.4 11.8
Cosine
68.9/31.9
63.8/11.1
31.5
62.1
$144/579/544///
48.8/
47.1 59.4 34.8
BM25
40.4/40.4
62.3 17.6
37.0
66.8
6..//449//0.///4
57.7/24.3
52.9 42.4
BSR 72.1/38.3
63.5 16.4
39.4
69.2
66.3/27.5
$4.8 66.0 43.7
Set-BSR
58.6
27.1
39.7
73.4
86.8 76.1 / 64.8/ 54.5
50.7
61.6 53.9
EPR 75.1/41.1
/3.
37.5
70.8
85.0/ /3///////77/////// 40.3
68.7/16.0
/ 36.9
CEIL
76.8/49.
63.0/114
36.2
70.9
82.5 66.4 60.6 40,3
69.9/30.0
$4.8 43.0
Cushman
Random
16.9/11.1
5.1/2.8
13.0
6.8
22.1 24.1/24./15777
20.1/0.0
12.0 14.0 10.0
Cosine
64.6/32.5
6..7/6.2
30.6
59.7
/6.1/5.11/2 / 42.1
46.7/8.0
/ 32.5
BM25
67.1/35.1
58.3 11.8
34.5
64.4
61.4//1.//6.////
56,2/210
49.7 60.3 39.0
BSR
69.4/36.3
61.0 10.9
38.3
68.4
83.9/ /../67///14///66
62.4/24.7
/ 41.2
Set-BSR
46.9
63.9 19.9
40.2
71.5
88.6 /4.1
68.7/47.8
/9.5/68.33 50.7
EPR
74.5/4188
56.8 10.6
0.0
64.8
82.1 54.6 56.3 39.4
66.9/2100
47.4/ 37.3
Tuubbo--Turbo
CEIL
79.2/53.4
/6.9 26.9
0.0
68.2
75.4 56.9 55.8 33.0
72.8/77.6
51.2/ 43.9
Random
19.8/1411
8.4
14.5
4.8
26,8/ 27.2 17.8/3.
17.1/0.0
15.0/15.2/ 10.8
Cosine
64.2/32.8
58.1/12.0 12.0
30.2
54.6
76. / 56.5
48.8/11.2
44.9 34.4
BM25
71.6/39.5
$2.5 16.9
36.3
60.5
78.9 63.3/63.33/ /8.9/63.3558.14// /
59.8/24.6
50.3 59.9
/5.9/ /9.9/999000 40.6
BSR
55.6 73.2/39.3
17.6
38.6
63.2
82.1 / /6.3/
66.5/
52.7 /3.22/ /2.11
Set-BSR
78.6/53.3
58.2/25.9 25.9
39.5
66.9
83.9 74.1 /
75.6/
60.1 /61/66.5//55 53.7
EPR
49.0
69.6 12.1
45.5
76.6
87.9 70.9 64.6
76.3/21.7
58.5 44.3
CEIL
60..
69.8 / 29.6
46.5
79.7
85.4 / 76.6 68.8 /
77.5/40.1
64.0/73.7 54.3
Codex
Random
24.3
1..1/6.5
26.7
9.3
36.4 28.3 19,1
31.977.4
20.7 /246 16.9
Cosine
74.1
67.7 17.1
41.0
69.1
86.8 / 68.4 / 61.5 48.55
54.7/11.9
53.4/65.6 41.1
BM25
76.9/467
/3.1
45.2
72.3
87.1 /7.2 / 62,1
65,4/29.4
60.9/68.9/ 52.8
BSR
79.3 48.11
68.1 22.4
44.0
76.8
88.2 / 78.8 6 53.0
72.5/31.5
61.2 67.2/71.5/ 50.9
Set-BSR
8 62.4
69.5 /414
46.0
79.6
91.1 86.6 76.0 69.4
75.7/61.2
70.3 / /
Table 11: Comparison of various methods 8-shot ICL for semantic parsing datasets. Right-most column shows
average performances on AL.L, only IID, and only COMPositional splits. BSR consistently outperforms COSINE and B22 and BET-BSR yields further gains surpassing even trained methods.

---

LM
Selector GSMSK DROP
QNLI
MNLI
RTE
MRPC
PAWS
QQP
SST2 AVERAGE
Random
1.5
6.4
51.2
41.9
53.4
51
48
65,9
86.9
45.1
Cosine
1.9
12.3
56
44
54.2
52.5
52.5
75
81.9
47.8
GPT-Nco-2.77
BM25
3.7
12.6
58.1
42.2
50.9
57.6
55.2
71.3
82.6
48.2
BSR
2.9
13.9
81.1
76.7
67.9
70.1
75
86.4
90.9
62.8
Set-BSR
2.9
13.2
78.6
61.5
60.6
68.4
74.9
84.4
89.8
59.4
Random
11.3
23.4
54.2
54.3
70
33.8
59.1
66.2
94.2
51.8
Cosine
12.3
26.7
58
58
67.9
46.6
56.6
76.1
92
54.9
LLaMA-7B
HM25
11.9
26.8
57.3
56.1
68.2
48.3
$7.2
73.2
93.2
54.7
BSR
14.5
27.2
82.9
76.3
70.8
59.8
74
80.4
95.8
64.6
Set-BSR
15
29.1
74.7
70.2
67.5
53.7
72
80.3
94.2
61.9
Random
15.3
29.9
56.3
51.3
75.5
72.3
60.1
67.3
93.1
$7.9
Cosine
16.7
32.6
61.8
62.9
75.1
57.1
58.9
78.7
92.7
59.6
LLMMA-13B
BM25
16.3
31.7
63.3
62.8
73.6
62.5
58.8
76.9
92.7
59.8
BSR
19.2
34.3
85.6
82
76.5
72.8
77.5
85.2
95.2
69.8
Set-BSR
20.6
33.3
82
73.3
76.2
67.2
77.2
81.9
93.8
67.3
Table 12: Comparison of various methods on 8-shot ICL for reasoning and classification datasets. BSR outperforms all prior training free methods though SET-BSR doesn't yield additional improvement.

---

Set-Cosine
Set-BM25
Selector
depst]
Set-85R
unigram
4-gram
4-depst
Substructure
Coverage of aspects of the test instance: Change in recall of unigrams, 4-grams, and depen- dency parse subtrees (size 4) in the test input with set-selection of demonstrations, compared to their non- set version, averaged across all datasets.
Figure 11:
LM
Selector
GSM8K
DROP
QNLI
EPR
0.0
13.8
74.9
CEIL
0.0
84.2
GPT-Neo-2.7B
BSR
2.9
13.9
81.1
Set-BSR
2.9
13.2
78.6
EPR
80.9
CEIL
84.1
LLaMA-7B
BSR
14.5
27.2
82.9
Set-BSR
15.0
29.1
74.7
EPR
81.9
CEIL
84.2
LLaMA-13B
BSR
19.2
34.3
85.6
Set-BSR
20.6
33.3
82.0
EPR
81.7
CEIL
84.8
StarCoder
BSR
26.6
84.7
Set-BSR
17.5
80.3
EPR
10.0
78.9
CEIL
8.3
83.8
Cushman
BSR
12.1
23.6
84.7
Set-BSR
11.1
23.7
74.4
EPR
61.7
83.8
CEIL
63.1
84.9
Codex
BSR
68.1
68.1
88.7
BSR
67.4
66.4
84.6
Table 13: Additional non-semantic parsing 8-shot ICL
results for comparison with trained methods and larger LLMs. BSR is competitive with EPR and CEIL, even outperforming them with larger L.M.s. We could get CEIL to work for DROP.
GPT-Neo-2.7B LLaMA-7B LLaMA-13B
Random
22.5
25.5
30.4
Cosine
36.9
43.2
47.7
BM225
38.5
44.4
50.1
BSR
46.4
50.6
56.5
Set-BSR
45.9
51.6
58.2
Table 14: Average 8-shot ICL performance across all datasets and splits.

---

Dataset
ATIS ITD IID/ Tpl.
Overnight ID HDD/TM
Break
МТОР
GeoQuery
SMCalFlow-CS 8_S/32_C
AVERAGE All IID/ Comp.
Split
IID
IID
ITD Tpp. /MMD//MCD// Len.
Selector
Random
1..4/000
3.6/0.0
1.9
1.3
17.5/ /4.0/
3.0
6.6/ 4,3
Cosine[bert-base]
4..6/3.4
31.8/0.
22.4
44.1
0.9/37.9/41.4//
24.3/0.9
/ 18.3
Cosine[mpnet-basel
6.5
38.3/0.4
22.3
43.9
25.2/1.2
28.8/ 17.0
Coverage
45.9/4.2
32.6/0.4
19.2
39.2
59.6/32.6/44
/4.6//440//1 18.8
27.2/1.4
27.1/ 16.9
rrcorder
6.5
32.3/0.5
19.4
37.8
/2.3332//331///// 20.6
27.2/1.1
27.2 17.4
BM25
49.5/7.4
33.7/3.0
26.5
47.7
63.6 46./44.6/400
32.0/3.2
31.2/42.2/
+Coverage
8.1
25.8/0.4
21.1
41.5
20.9
22.1/1.5
25.8 35.3 16.3
reorder
4..9/7.4
24.1/0.4
20.7
40.6
39.3/ 20.0
23.0/2.3
25.4 34.5 16.3
BM25[4-gram]
5.5
33.4/2.1
27.3
48.9
/ / 27.3
28.4/3.5
30.5 41.54 19.6
Coverage
8.5
27.2/223
23.8
47.1
63.2/362 / 24.2
26.6/3.9
/9.5/39.41 19.6
reorder
4..1/8.1
27.1/18
20.9
46.1
23./3008/39.20 24.5
25.7
17.9
BM25[4-depst]
45.1/9.0
31.8/1.9
26.2
47.4
67.1 / 38.7 / 24.2
27.5/1.7
30.1 19.9
Coverage
48.5/12.0
28.7/0.9
22.8
44.7
58.6 38.8/ 3 41. 24.2
26.6/2.4
39.2/38.3/20
reorder
47.1/9.3
28.7/1.1
21.9
46.1
/9.6 34.1 34.77
25.5/2.0
28.3/38.2/ 18.4
BSR[bert-base]
5..1/8.5
36.9/1.9
27.9
51.5
35.8/2.4
33.5/45.0/21.
Coverage
53.6/12.2
38.4/2.3
28.3
52.1
70.0 46.9/ 27.6
39.7
/5.3/47.0//3.
JSFlleehert
47.2/6.0
39.4/1.4
30.6
54.8
/4.4/ /
41,4/1.8
33.7 33.7 /6.66 20.7
BSPideherta--asee
45.2/7.2
39.4/1.9
31.1
46.5
64.6/38.1/4144/77.
27.5/0.9
/ 19.5
BSR[deherta-basel
47.5/9.0
37.2/2.5
30.2
53.5
40.6/4.1
34.1 441//6.//22
IDF
48.2/9.3
40.0/2.1
28.2
53.7
68.9 42.77//2..773
39.1/4.1
34.0/ 46.4/21.7
Coverage
53.8/
40.1/2.6
28.5
55.4
44.6/445.3/4544//4
40.3/4.1
35.8 48.8//8 4
+ IDF
12.1
40.6/3.3
28.3
53.9
72.1 /6.1////.41.//99
/
25.1/49.8/22.
-rcorder
50.0/
/2.1
26.9
53.0
66.8 /4.//44.//2.///
39.0/4.7
33.7/45.6/215
BSR[deberta--arge]
48.3/7.8
29.1
54.5
/7.1
39.7
34.1/46.5/21.7
IDF
48.8/9.7
41.5/2.6
27.8
54.0
69.3/36.6/45 4 26.4
40.3/3.8
33.8 /7.0
+ Coverage
54.6/
44.2
28.6
55.1
/ 45.4 26.4
41.5/4.8
35.8
48.4 23.3
nan / nan
nam nan
29.0
nan
/4..8 46.8 25.8
40.9/5.1
37.6 47.4
reerder
52.0/ 12.0
37.6/ 4.8
29.2
53.5
63.9 / 39.9 44.4 24.2
39.0/5.1
33.8 45.9 21.7
Table 15: 8-shot ICL results with GPT-Neo-22 Ne7- for all ablations of learning free methods semantic parsing datasets and splits.

---

Dataset
ATIS ITD IID/ Tpl.
Overnight ID HID/Tp Tpl.
Break МТОР IID
GeoQuery
SMCalFlow-CS 8_$/32_C
AVERAGE All IID/ /ompp
Split
IID
ITD /Tl. /TCCD/MCD/// Len.
Selector
Random
9.5
4.2/0.5
8.8
2.8
9.3
13.3
/9.23/9////4
6.2/0.0
5.7 / 6.8 / 4.6
Cosine[bert-base]
72,9/7.2
38.5/2.8
24.9
49.0
69.6/ 40.7
42.42///12 29.4
35.2/
42.9/45.0/ 20.7
Cosine[mpnet-basel
51.7
48.7
26.1
49.8
42.6 29.4
37.3/3.2
34.4 48.8 20.0
Coverage
55.0/
42.5/0.9
24.7
43.0
63.9
43.7 29.7
35.2/3.3
32.8/44.1 21.5
reoorder
56.0/14.3
41.8/1.2
25.5
43.6
/5.8/ /3.6/ 35.2
35.2/3.5
33.4/44.6/2.55
BM25
61.5/
45.1
30.1
53.6
67.9 39.5 44.9/
43,4/9.5
50.2
&Coverage
12.7
34.9/2.6
25.5
48.5
63.6 30.5 4
35.3/6.2
31.8/43.9/ 19.7
reorder
55.0/
34.4/288
25.1
48.3
60.4 31.4/319/418///2
36.3/6.0
314/43.2/ 19.6
BM25[4-gram]
55.5/
42.4/5.6
31.9
52.2
44.7444.7/11.7//3
41,4/9.5
/ 23,9
Coverage
56.7/
39.6/5.8
29.4
53.5
/2.6/42.9/
45.8/13.6
37.4 25.9
reorder
17.3/
37.0/4.9
28.0
51.4
08.9/41.04441///3
44.9/13.4
36,9/47.9 47.9 25.9
BM25[4-depst]
11.2
42.3/3.3
29.7
52.2
/8.9/419/434////
39.9/5.4
35.1/47.9/225
Coverage
59.7/17.8
41.1/5.6
29.2
52.4
/3.6/ 40.9/
45.6/
37.0 4
reorder
59.6/15.3
39.9/4.6
28.1
51.2
66.4/ /4.2//44//
44.1/10.7
36.8 48.22/222.
BSR[bert-base]
63.0/15.0
48.5/2.6
32.7
57.4
/ 45.8 30.0
50.9/8.4
39.9 /4.4
Coverage
64.3/17.8
48.3/5.8
34.1
59.2
76.8/ 48.7 /3.8
34.8
50.2/17.6
/5.5//5.5
JSeeleehert
58.8/13.1
49.7
33.4
59.5
75.7 32.7
55.7/8.4
/5.7
BSs]deherta-base]
53.5/999
49.2/3.7
32.2
47.9
/7.1/424//4.8//5
41.7/229
30.3/503/220
BSR[deherta-basel
61.2/15.2
50.3/2.6
33.4
59.1
74.3/5502/45.9/55
51.2/11.6
/
IDF
60.8/15.3
$1.4/4.
5844
70.7/47:5/420//52
50.3/12.1
40.0 26.0/
Coverage
18.3
52.5
34.3
60.0
75.4/44.5/48.4/3..00
53.0/
42.5 56.3 28.7
+ IDF
63.2/19.4
$1.1/6.2
32.8
60.2
74.6/45.3/4..1/339
53.3/17.5
41.7 /7.9
-rcorder
63.7/2006
49.6/6.2
35.3
61.7
73.9/41.3/48.4//4
52.4/17.5
42.6 56.1
BSR[deberta-Large]
60.9/14.
$1.2/3.0
32.5
59.1
/2.5/47.2/46.9/
54.1/9.8
40.1 /5.0//52
IDF
61.6/15.0
51.4/4.6
33.2
59.1
73.2/53.2/4.5111 /6.5
52.0/10.7
41.0/ 55.1 27.0
+ Coverage
64.3/21.2
6..
33.7
61.9
76.1/52.3/ 48.5
14.5
43.8 57.0 30.6
IDF
65.6/21.9
5..5/6.2
32.9
61.5
/ 50.0 35.8
58.6/18.6
44.1 57.4 30.9
rearder
65.4/
51.6/7.0
33.5
61.9
76.1
511.2/ 48.6 35.5
54.57 19.6
43.7 57.2 30.2
Table 16: 8-shot ICL results with LLaMA-7B for all ablations of learning free methods semantic parsing datasets and splits.

---

Dataset
ATIS ITD IDD/Tpl
Overnight ID HDD/T Tpl.
Break МТОР IID
GeoQuery
SMCalFlow-CS 8_$/32_C
AVERAGE All IID/ Comp-
Split
IID
ITD Tpl. /TMDD/MCD/// Len.
Selector
Random
5.1
3.4/2.6
9.0
4.8
23.9/
19.8 14.2 /
1..0/0.0
9.87 12.4/7.2
Cosine[bert-base]
55.8/ 17.8
45.
30.7
52.7
75.7 53.1 /
42,7/3.0
50.4 26.6 26.6
Cosine[mpnet-basel
37.8/20.5
48.6/3.0
29.4
54.0
7 48.5 32.7
42.9/5.4
3 25.8
Coverage
27.8
42.2/5.8
28.0
50.2
/8.6/51.//1.0// 30.0
41.8/5.7
38.0/48.1 28.0 28.0
reoorder
56.8/21.9
4..6/6.0
27.6
49.9
08.9/44./51.0/
39.6/5.4
BM25
62.6/
50.3/5.8
34.6
58.7
76.4/49.3/5.33 50.3/ / 49.1
48.2/13.6
55.66/
&Coverage
59.3/21.2
37.5/3.7
29.3
52.7
40.6/8.6
37.6/47.8/27,
reorder
57.2/
37.5/3.3
28.5
53.5
67.1 /3.6/ 29.7
40.3/8.7
36.5/47,4//55 25.6
BM25[4-gram]
58.6/20.3
49.7/7.0
33.9
58.1
77.9 55.5 34.8
50.6/13.0
Coverage
26.4/26.5
4..6/6.7
31.8
57.5
73.6 55.6555./515///// 40.6
/
43.5/5333/33.
reorder
60.8/
44.8/6.5
32.4
56.7
76.1/564/51.//000
19,6/
53.6/33.//335
BM25[4-depst]
584/23.8
48.6/6.2
32.9
59.2
46.4/6.3
42.2//3.5/31.0
Coverage
63.7/28.4
45.8/7.2
32.1
58.8
75.7/55.3/50.6/11
50.5
44.1/444/33.
reorder
64.5/28.9
43.9/6.7
31.2
58.5
77.1/568/528//85.
51.5/20.11
44.2/54.5/340
BSR[bert-base]
65.0/27.5
S3.3/5.8
35.0
63.8
77.9/59.5/540//35 39.4
53.6/13.6
45.9 38.4/3333
Coverage
69.4/33.3
56.9/8.8
37.1
64.4
60.4/64./55../
57.3/23.7
49.7
60.9/88.
JSFeleehert
62.2/23.3
55.5
35.8
59.4
80.7/59./52.0/
59.8/
45.6 /
BSPideherta-base]
56.5/16.9
55.0/4.9
34.1
49.4
80.7 50.7/5..7/000/ 33.6
46.1/5.1
40.6 23.6
BSR[deherta-basel
63.3/26.1
56.4/6.7
36.3
64.3
80.0/61.9/44./
59.5/
60.0/
IDF
63.8/28.0
53.8/5.6
64.3
57.5/5..254.7/
55.3/
45.9 33.5/333.
Coverage
69.5/32.6
58.4/9.7
36.6
66.6
80.7/61.5/56.4/433
66.0/
60.4/225/388
+ IDF
68.6/35.4
$6.8995
66.6
79.6/59.4/
nan
/8.6/615//7..
-rcorder
68.9/33.0
56.5
36.7
67.5
79.6/ /
30.9
61.2/619// /
BSR[deberta-Large]
64.0/22.8
55.7
37.7
64.4
79.6 60.1 55.2
60.1
60.3/6..3/33
IDF
65.5/25.6
35.9
65.0
79.6 59.6 55.1 34.2
58.8/17.6
46.41
+ Coverage
69.6/33.5
5..6/8.6
39.2
66.1
81.8 64.1 60.2 44.8
26.5/
51.4 /
69.2/349
57.0/7.7
38.2
66.3
80.4 58.1 58.0
nan
49.2 62.2
reerder
71.1/33.5
59.2/9.2
37.3
67.6
81.8 60.1 55.5 39.7
60.6 29.1
50.4 62.6 38.2
Table 17: 8-shot ICL results with LLaMA-133 13B for all ablations of learning-free methods semantic parsing datasets and splits.

---

Dataset
ATIS IID Tpl.
Overmight IID/Tpl. Tpl.
Break
MTOP
GeoQuery
SMCalFlow-C CS
AVERAGE
Split
IID
IID
IID Tpl. /TMC Len.
8_S/32_C
All/ Comp.
Selector
Random
12.2/12.0
10.8/3.3
8.8
4.7
25.7
20.1
15.4/
Cosine[bert-base]
57.9 61.9/27.0
16,4
32.1
57.6
8 58.6/41.8
48.9/844
36.2/77.2/ 36.0
Cosine[mpnet-
68.9/31.
63.8/11.1
31.5
81.4/ 44.4577./444/42)
48.8/10.7
47.1/ 34.8
Coverage
65.0/33.7
55.1/17.4
31.1
57.9
22./67..2/440///
46.2/11.5
47.9/55.5/
reooddrr
65.2/36.0
15.4
30.4
58.8
78.6/714/65. 63.3//99.
45.6/12.1
48.4/ 1.5.7/411
70.9/40.4
62.3/
37.0
66.8
85.0/ 60.1
57.7/24.3
52.9 1.9//66 63.3
+ Coverage
66.5/37.6
11.8/
31.6
58.8
(5./57///554/411
48.3/17.9
46.8 55.6/
reorder
66.8/37.6
50.7
32.7
58.8
78.2 53.8/412
47.3/17.9
47.0/ 55.7 38.3
BM25[4-gram]
64.4/34.6
62.2/22.0
37.7
63.3
83.9 / 59.3 49.4
57.3/
/
+ Coverage
72.6/45.0
60.7
35.4
62.9
81.4 61.8 4
60.3/34.4
55.0/62.2/47.
reorder
72.2/45.5
59.4/30.3
35.7
63.9
82.9/716 58,9 49.77
60.6/35.6
55.5
BM25[4-depst]
63.5/
60.6/20.1
36.3
64.3
8 61.0 52.7
51.7/10.1
50.5 /4.4
+ Coverage
72.1 72.1/45.1
60.2/26.2
33.8
63.8
84.6 68.5 61.7 49.7
58.5135.0
54.9/
reorder
74.0/45.7
/2.3
34.0
65.0
82.1 / 59.9 48.2
59.43345
55.3/ 48.0
BSR[bert-base]
71.8/4..6
63.4/19.9
38.9
69.6
87.1 / 73.9 63.3 44.2
61.9/2.77
55.3 / 44..1
Coverage
51,6
66.0/27.5
39.9
72.7
/
59.0/
61.2/ 68.7 53.6
BSF JSFeldeberta-basel
/9.7/33.3
65.6/ 18.1
39.3
67.0
/ 60.4 47.0
66.9/23.2
53.8 44.9
BSPIdeberta-basel
60.6/24.5
65.7/15.0
38.0
53.7
85.0 57.4 45.8
$2.07788
57.65590// 36.3
BSR[deberta-base)
38.6/38.3
64.7/15.1
39.7
68.2
35.0/72.22 60.4 / 44.8
66,9/28.1
/4.5/65.9/43..
IDF
79.2/
18.1
38.0
68.1
83.6/7166/ /4.5 44.5
63.1/318
54.5 64.5/64.7/44 /4.2
Coverage
77.3/
65.9/25.9
40.0
71.7
75./75.5/336///
69.3/53.7
61.0 6../68.7//34
+ IDF
71.0/519
26.5
41.1
70.7
/7.1/ /2.27
nan/ 53.5
54.5
rrcorder
/2.9
29.7
39.5
72.2
87.5 62.9/
68.6/54.1
62.1 281/66.7/55.
BSR[deberta-large
72.1
63.5/ 16.4
39.4
69.2
85.4/ 62.6 / 45.5
66.3/
54.8 2.8/66.0/33.
IDF
72.2/40.7
16.2
39.5
69.2
/ 61.7 44.5
63.9/33.2
55.3 65.7 44,9
Coverage
50.6
27.3
39.7
73.4
86.8 76. 64.8 / 54.5
/0.7
61.6 69.3 53.9
IDF
7 52.0
27.6
38.4
72.5
87.1 / 77.5 64.9 51.5
nan / 49.3
60.4 68.3 53.8
-reorder
79.0 52.4 68.2 29.8
39.3
73.1
87.9 / 76.0 64.2 $7.3
70.2 49.9
62.3 69.6 54.9
Table 18: 8-shot ICL results with StarCoder for all ablations of learning-free methods on semantic parsing datasets and splits.
Dataset
ATIS IID /Tll.
Overnight IID / /ppl.
Break
MTOP
GeoQuery
SMCalFlow-CS 8 8.S/32.C
AVERAGE All IID /ompp
Split
IID
IID
IID /pl. / /TCCD Len.
Selector
Random
19.8 14.1
8.4/
14.5
4.8
26.8 26.8/27.2 17.
17.1/0.0
13.0/ 15.2 / 10.8
Cosine[bert-bann
49.5 29.3
16.4
33.4
54.8
77.1 77.1/57.3/44./ 38.2
49.7/9.2
44.4 54.6 34.2
Cusine(mpnet-basee
64.2/32.8
58.1/12.0
30.2
54.6
39.1 76.1/56.5/555
48.8/11.2
55.3 34.4
BM25
79.6
16.9
36.3
60.5
/41.2
59.8/24.6
50.3/59.9 40.6
+ Coverage
72.1
47.9/254
35.5
61.3
77.1/6..2/5.2
61.5/38.5
$3.2/59.2/475
BSR[bert-base]
72.3
19.2
37.9
63.7
85.4 65.0//8./99.11 / 39.1
63.1/26.8
52.5 42.0
Coverage
78.2/51.5
58.4/25.9
38.8
65.1
66.5/51.4
58.7 65.0/65.0//5 52.3
BSR[deberta-large
73.2/39.3
55.6/17.6
38.6
63.2
82.1 69,7/ 56.3//
66.5/
52.7 63.2 2 /
Coverage
53.3
58.2/25.9
39.5
66.9
83.9 /2.3
71.67
60.1 66.55 53.7
Table 19: 8-shot ICL results with GPT-3.5-Turbo
ablations of learning-free methods on semantic parsing
datasets and splits.

---

Dataset
ATIS
Overnight /pI.
Break
MTOP
GeoQuery
SMCalFlow-CS 8_8/32_C
AVERAGE All /ID/ Comp.
Split
IID Tpl.
IID
IID
ITD ID/Tpl. /TTpp//TMDD Lee.
Selector
Random
16.9/11.1
5.1/288
13.0
6.8
22.1 / /2..9//5..755
20.1/00
12.0/ 14.0/ 10.0
Cosine[mpnet-base)
64.6/32.5
6.27/6.2
30.6
59.7
81.1 /1.1/ /0..//2.1
46.7
44.9 57.2 32.5
Coverage
59.0/31.6
52.7/12. 12.0
27.8
53.3
/61/55.6/663/3/4
46.1/8.1
44.0 52.5 35.5
reorder
59.4/34.7
53.1/11.1
27.8
54.7
45.3/8.7
44.2/ 35.9
BM25
67.1/35.1
11.8
34.5
64.4
(6.661//666//777
56.22110
/9.7/ 39.0
Coverage
61.3/33.9
48.4/10.9
29.6
58.5
33./554//6..2/11
48.3/12.4
43.7/53.3/34
reorder
62.4/32.8
48.1/
29.5
58.2
75.4/51.7/51.2//
46.2/12.8
43.1/53.3/22.
BM25[4-gram]
62.8/31.6
15.7
36.5
60.6
81.4/634/55.1//4
57.3/17.9
4 59.359.//33
Coverage
68.0/40.2
56.2/
33.7
61.3
80.0/61.960.3/
57.3/28.1
50.9 59.4
reorder
68.6/41.6
54.9
35.1
80.0/64.//7..9
56.8/28.1
/
BM25[4-depst]
60.7/31.7
17.4/144
35.0
62.7
/2.1/61.5/5..9/
50.5
47.6/58.11
Coverage
69.8/40.0
55.3/
32,9
63.0
81.1/61.7/633
55.6/32.0
50.6/ 59.6/
reorder
39.4/99.
16.6/16.5
33.6
82.1/644/37.5/44
56,8/33.5
$2.0 60.5
BSFIdebberta-base]
67.3/28.9
61.9/10.2
37.9
65.2
86.4/684/51.9
65.9/22.6
50.9 /4.164..337
BSPideberta-base
58.1//2.2
61.2/10.4
36.9
83.2/655/52.88
48.5/6.2
45.3/ 56.9//.9333.7
[SR(dcherta-baae]
67.2/34.7
61.7/888
39.5
67.4
83.9/67.1/6.6//
61.8/2499
51.8/636/
IDF
69.0/37.4
61.5/977
36.1
67.7
82.5/66.7 58.9/ 58.9/42.
60.6/ 28.8
51.8/ 62.9/229/400
Coverage
74.7/47.3
63.0/18.1
38.4
70.1
83.2/718 61.8//499/9
66.6/ 46.2
57.6 66.2 49.1
+ IDF
76.0/48.1
63.5//00
37.5
69.0
84.3/719 58.2
nan 48.3
56.7 46.1/
reoorder
78.2/48.7
62.5 18.8
37.7
69.8
84.6/70.3 64,6/47.3
67.8/49.6
58.1 66.3
[
69.4/66.
61.0/ 10.9
38.3
68.4
/
62.4/24.7
22.6/68.9/114
+ IDF
70.1/37.4
02.2/10.2
38.9
68.8
/ /
62.4/30.9
53.3 64.4/42.2
+ Coverage
76.7
63.9/19.9
40.2
71.5
64.1 50.3
68.7/47.8
59.5 68.3 50.7
+ IDF
77.8/46.9
64.0/
19.7
38.5
70.5
85.0/ 64,9 53.3
nan 50.2
58.6 67.2 51.5
-reorder
76.6/ 48.0
63.2 / 18.7
39.0
70.1
85.0/ 74.4 63.3 55.5
67.7/48..1
59.1 / 66.9 51.3
Table 20: 8-shot ICL results with Cushman for all ablations of learning- frren methods on semantic parsing datasets and splits.
Dataset Split
ATIS IID / Tpl.
Overnight IID /pl..
Break IID
MТOP IID
GeoQuery IID Tpl. TMCD//CDD//// / Len.
SMCalFlow-CS 8_S/32_C
AVERAGE All/ IID Comp.
Selector
Random
27.3/ 14.3
16.1/6.5
26.7
9.3
36.4/2.3/25.7/191
31.977.4
20.7/24 16.9
Cosine|mpnet-base]
/
67.7 17.1
41.0
69.1
86.8/68../61.5//
54.7/11.9
53.4/656//1,
Coverage
71.3/4488
62.8/3155
37.9
68.2
85.4/765/719/600
54.7/26.1
57.6/634/51.
reorder
71.7/45.1
62.6/29.8
36.4
67.5
53.8/25.9
57.3/628/51.
BM25
76.9/46.7
66.5/30.1
45.2
72.3
87.1/722/7122/2)
65.4/29.4
60.9/68.9/22.
+ Coverage
44.9
61.2/29.9
38.9
66.7
83.6 7
55.7/29.9
56.4/63.4/495
-reorder
44.2/46.7
62.1
39.6
65.3
/9.9 66.6/5422
55.7/29.0
56.2/63.1/99
BM25[4-gram]
73.0/
65.7/33.8
43.7
70.4
86.8 / 70,6 60.6
63.1/22.8
59.1/67.1/5.0
+ Coverage
/ 55.2 65.4/33.0
42.2
70.4
68.6/46.8
64.5/ 68.9 60.2
reorder
79.7 54,9 65.9/42.4
41.8
71.1
87.9/ /3.1//../.../6 /6.8
67.7/44.2
64.2/69.0/55 59.4
BM25[4-depst]
70.7/41.1 65.5/31.2
42.6
70.4
85.4 7 69.0
58.2/11.9
/7.8/ 50.0
Coverage
80.0/ 56.4 64.1/40.3
40.9
70.3
79.99/3/733/////
67.2/49.0
64.9/68.6/6/
reorder
56.5 64.7/41.0
39.7
69.4
87.9/ 80.2 /3.02/7344/0
67.7/49.3
64.7/68.3/1..
BSFiseeberta-base]
39,2
66.9/28.2
45.2
73.0
86.1 / / 62.6
72.1/27.1
/9.5 /9.8/49.2 49.2
BSP(deberta-buse)
68.5//993
67.6/26.2
43.7
60.2
86.1 /3.00///333///3
55.0/
/.3/63.5/434
Baae
47.7 67.4/2222
45.6
75.7
88.6 79.7 /52.4
72.1/32.0
60.7 70.8 50.6
IDF
76.7 67.1/
44.1
76.3
87.5 / 8..081.0/00 /9.5// /5.5
70.8
61.7 70.4/
Coverage
83.0/61.7
70.4/41.7
45.1
78.7
91.1 201/854/7788 76.8/
76.0/ 60.8
69.9/ 65.77
IDF
83.0/61.7
70.5/419
45.6
78.4
90.7 85.6 67.6
nan /2.00
69.4/73.6/ 65.9
-reorder
63.5
69.5/42.8
45.1
79.1
91.8/85.9 78.5
76.1/
70.2/74.2/ 66.3
BSFI[eeberta--arge]
77.4144.3
68.9/29.6
45.9
73.8
68.1/
72.1/29.6
60.6/710/500
BSPideberta-large]
70.1/32.5
69.0/22.
44.7
58.9
87.1 / 75.6 50.6
63.0/15.7
54.3/65.55 /
BSR/deberta-large
79.3/48.1
68.1/22.4
44.0
76.8
88.2 / 78.8 53.0
72.5/31.5
61.2/715
IDF
50.8
68.7/21.3
44.9
75.5
88.9 82.0 71.7
70.5
62.//1L4/53.4
Coverage
84.7/
69.5/41.4
86.6 76.0 /6.6 69.4
75.7/61.2
74.4 7 66.2 70.3
IDF
83.8 62.6
39.4
46.5
78.7
91.1 86.6 78.6 68.8
nan 59.0
69.5 / 65.9
-reorder
84.0 64.6 69.6 39.6
46.4
79.0
90.0 86.3 78.0 70.6
60.5
70.5 74.4 66.5
Table 21: 8-shot ICL results with Codex for all ablations of learning- free methods on semantic parsing datasets and splits.


Reviews:
[{"review_id": "EUqqGyoump", "reviewer": "Reviewer_YWop", "summary": "", "questions": "Question A: I wonder if authors conduct some analysis in terms of computational efficiency in the experiments.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review. \n\n**Reasons To Reject**\n1. We have not violated the anonymity policy - our public manuscript was submitted before the arxiv deadline, and we did not publicize the paper or code during the anonymity period.\n2. Missing significance tests: For the results in Table 1 with Codex as the inference LLM, we found that the difference between Set-BSR and all prior baselines, including CEIL, the strongest prior method, was significant with p-values < 0.001 according to paired permutation tests. We’ll add this and other significance test results to the final paper.\n3. Missing evaluation of efficiency: We discuss the computational efficiency of bertscore-based selection through a time complexity analysis in lines 311-323. Further, as stated in the paper, in practice, it runs in tens of milliseconds for nearly all datasets we consider, adding a negligible overhead compared to the time for ICL inference itself while also not requiring any training, unlike for most prior work. As an example, with Starcoder as the inference LLM, the selection time for all datasets and splits except DROP and QNLI was less than one-hundredth of the time for ICL with the selected examples. We will add additional runtime numbers to compare the selection time using the various methods and LLM ICL latency in the final paper.\n\n**Questions For The Authors**\n\nQuestion A: answered above", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "* Interesting idea on ICL measures in recall and set-level coverage.\n* Extensive experiments with various LLMs and tasks.\n* Concreate examples show how the proposed method improves from the cosine method.", "reasons_to_reject": "* Violation of the anonymity policy\n* Missing significance tests.\n* Missing evaluation of efficiency.", "questions_to_authors": "Question A: I wonder if authors conduct some analysis in terms of computational efficiency in the experiments.", "paper_topic_and_main_contributions": "In this paper, the authors propose to optimize set-level metrics for in-context learning to achieve better coverage of salient aspects. Experiments with several conventional large language models and generation tasks show that the proposed metric can result in better in-context learning performance by extending BERTScore.", "excitement": 3, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "rPLZnfewj4", "reviewer": "Reviewer_bmFi", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review and vote for acceptance! For reproducibility, we will make all our code and all the datasets and splits used in this paper available publicly upon acceptance.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "Various results show nice improvements over LLMs in general, and the paper is nicely explained.", "reasons_to_reject": "I vote for acceptance.", "questions_to_authors": "", "paper_topic_and_main_contributions": "The authors have proposed a novel in-context learning method and experimented complex compositional generation tasks and with diverse LLMs.", "excitement": 4, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ZyDIrjJWy1", "reviewer": "Reviewer_t4QT", "summary": "", "questions": "Question A: What is the definition of salient aspect for cosine in Section 5? How to calculate c(s, z) if z is just a dimension?\n\nQuestion B: Why do you use different sentence encoders for BERTScore and Cosine? If both use the same sentence encoders what would be the results?\n\nQuestion C: Can one achieve similar improvement by simply switching to a stronger embedding (e.g., openai's embedding or other encoders with higher dimensions)?", "limitations": "", "rating": 3, "confidence": 3, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We’d like to thank the reviewer for their review. \n\n**Reasons To Reject**\n\n- We’d first like to clarify that in addition to bertscore for ICL example selection and set-selection, our primary technical contribution is the idea of salient aspects of a test instance and the framework for measuring informativeness of demonstrations in terms of how well they demonstrate (or cover) those salient aspects.\n  Eq. 4 shows a way to interpret Cosine as a coverage measure (of the form of Eq. 3) so we can apply our set extension in Eq. 6 to it. It corresponds to the assumption that every dimension of the embedding vector space encodes a salient aspect and the product  $c(s, z) = r_x[s] *  r_z[s]$ measures the coverage of the dimension $s$ by example $z$. With this, cosine can be interpreted as the sum of coverage of every dimension. Set-cosine is obtained by plugging in the above $c(s ,z)$ into Eq. 6:\n\n  $$\\operatorname{setcosine}(x, Z) = \\sum_{s=1}^d \\max_{z \\in Z} c(s, z) = \\sum_{s=1}^d \\max_{z \\in Z} r_x[s] * r_z[s]$$\n\n  The max inside sum might seem odd at first glance, but it is intended. Analogous to other set-metrics, set-cosine is the sum of maximum coverage every dimension (salient aspect) receives from any example $z \\in Z$ and as our results show, this does improve performance of Cosine in compositional settings. Hope this clarifies everything about Cosine. We are happy to answer any follow-up questions. \n\n- Thank you, we’ll consider the suggestion for the final version. Currently, we use Table 1  to highlight a comparison between our best method (Set-BSR) and prior methods and dedicate an entire figure (Figure 3) to examining the influence of set-based metrics. We additionally include Tables 10-17 in the appendix with complete set of results for all methods.\n\n**Questions For The Authors**\n\n*Question A: What is the definition of salient aspect for cosine in Section 5? How to calculate c(s, z) if z is just a dimension?*\n\nAs explained above, for cosine similarity, s is a dimension index and $c(s, z) = r_{x_{test}}[s] .  r_{z}[s]$ i.e. the scalar product of the values at that dimension for the test input and candidate $z$’s embeddings. \n\n\n*Question B: Why do you use different sentence encoders for BERTScore and Cosine? If both use the same sentence encoders what would be the results?*\n\nWe experimented with different encoders for both Cosine and BertScore and found it to have little impact on the performance compared to the difference between them. For Cosine we initially experimented with bert-base and for BertScore, deberta-base and large. The results for the latter are also included in the paper (Figure 9). This is also in line with the results of https://arxiv.org/abs/2302.05698 which additionally tried better sentence embedding models for Cosine. Finally, the specific choice of different encoders for Cosine and BertScore was to ensure a comparison where both are used in their best possible setting. For Cosine, all-mpnet-base-v2 is the best available and recommended encoder model in [SentenceBert](https://www.sbert.net/docs/pretrained_models.html#model-overview). For bertscore, deberta-large and base are the [best models](https://docs.google.com/spreadsheets/d/1RKOVpselB98Nnh_EOC4A2BYn8_201tmPODpNWu4w7xI/edit#gid=0) of their size. Nevertheless, we are happy to add additional results using the same encoder for both.\n\n\n*Question C: Can one achieve similar improvement by simply switching to a stronger embedding (e.g., openai's embedding or other encoders with higher dimensions)?*\n\nWhile it’s true that better underlying models can lead to better performance -- our own experiments showed that for BERTScore (in e.g. Fig. 9 and Tables 12-17) deberta-large improved upon deberta-base (albeit marginally) -- for similarly powerful encoders, bertscore (BSR) would continue to outperform cosine as it is not bottelenecked by the use of a single embedding. Moreover, as shown in Fig. 3, set-extension works best for contextualized embeddings and BSR than for cosine similarity.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "- Research problem studied in this paper is interesting and important\n- The exploration of using BERTScore-Recall in exemplar selection is novel\n- Overall clear presentation\n\nIn sum, I believe that the research problems investigated in this paper are both interesting and important. The proposed method is also simple and does not require any training, which is a positive attribute.", "reasons_to_reject": "- The definition of salient aspect for cosine is confusing, especially when it is applied in Equation (6).\n- Comparisons to other set-coverage-enhanced methods like Set-BM25 / Set-cosine are not illustrated in Table 1\n\nMy biggest concern is the definition of “salient aspect” for cosine. In Equation (4), and the end of Section 4 (Line 272), the table seems to suggest that each embedding dimension is defined as the salient aspect for cosine similarity. If this definition remains the same in Section 5, it would undermine the capability of cosine in the calculation of set-coverage metric defined in Equation (6), where the max dimension will be used instead of the cosine similarity of the whole vector. The authors can probably clarify how salient aspect is defined for cosine in Section 5 and how Equation (6) is calculated for cosine. \n\nI also think the authors can make Table 1 easier to read if they include results for Set-BM25 and Set-cosine into Table 1. This can provide clearer comparison to quantify the improvement of BSR and the set-coverage metric respectively.", "questions_to_authors": "Question A: What is the definition of salient aspect for cosine in Section 5? How to calculate c(s, z) if z is just a dimension?\n\nQuestion B: Why do you use different sentence encoders for BERTScore and Cosine? If both use the same sentence encoders what would be the results?\n\nQuestion C: Can one achieve similar improvement by simply switching to a stronger embedding (e.g., openai's embedding or other encoders with higher dimensions)?", "paper_topic_and_main_contributions": "The authors propose a method for selecting informative examples for in-context learning using BERTScore, which measures the similarity between two pieces of text, derived from the contextual embeddings of each token from BERT. The main contribution of this paper is the proposed BERTScore-based set metric to and the proof of its submodularity. The authors conduct experiments on multiple data sets with multiple LLMs.", "excitement": 3, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "dxlKJb3tUj", "reviewer": "Reviewer_cBG5", "summary": "", "questions": "1) The paper uses all-mpnet-base as a base for cosine similarity but deberta-large-mnli for BERTScore. What is the impact on evaluations if different base embeddings are used for these two metrics? What are the justifications for utilizing these embeddings as the base models?", "limitations": "", "rating": 3, "confidence": 4, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review. \n\nWe’d first like to clarify that in addition to bertscore for ICL example selection and set-selection, our primary technical contribution is the idea of salient aspects of a test instance and the framework for measuring informativeness of demonstrations in terms of how well they demonstrate (or cover) those salient aspects.\n\n**Reasons to Reject**\n\n1. You say that set-based selection did not perform well for cosine and BM25, but this is not what figure 3 shows. Set selection with BM25 improves over vanilla BM25 in almost all cases, and more so as the underlying LLM improves. Even with Cosine, our set-extension is significantly better in compositional splits where set-selection would be necessary. Compositional generalization is commonly required in real data settings, especially when limited training data is available. If a large amount of IID training data is available, you would likely be using some kind of fine-tuning instead of ICL.\n2. In Line 320, we state that we found both BSR and Set-BSR to run in tens of milliseconds for nearly all datasets considered in this work—significantly faster than the LLM inference time itself. As an example, with Starcoder as the inference LLM, the selection time for all datasets and splits except DROP and QNLI was less than one-hundredth of the time for ICL with the selected examples. We will add additional runtime numbers to compare the selection time using the various methods and LLM ICL latency in the final paper.\n\n**Questions For The Authors**\n\n1. We experimented with different encoders for both Cosine and BertScore and found it to have little impact on the performance compared to the difference between them. For Cosine we initially experimented with bert-base and for BertScore, deberta-base and large. The results for the latter are also included in the paper (Figure 9). This is also in line with the results of https://arxiv.org/abs/2302.05698 which additionally tried better sentence embedding models for Cosine. Finally, the specific choice of different encoders for Cosine and BertScore was to ensure a comparison where both are used in their best possible setting. For Cosine, all-mpnet-base-v2 is the best available and recommended encoder model in [SentenceBert](https://www.sbert.net/docs/pretrained_models.html#model-overview). For bertscore, deberta-large and base are the [best models](https://docs.google.com/spreadsheets/d/1RKOVpselB98Nnh_EOC4A2BYn8_201tmPODpNWu4w7xI/edit#gid=0) of their size. Nevertheless, we are happy to add additional results using the same encoder for both.\n\n**Missing References**\n\n1. Thank you for the suggestion. We can add a discussion on such related work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1) Proposal of  a set-based (batch mode) sample selection strategy\n\n2) Adaption of BERTScore [1] for demonstration selection in in-context learning\n\n3) Thorough evaluation of multiple methods, especially pointers to the failure scenarios (due to bias [1]) and scalability issues (all pair similarity computation) \n\n\nReference\n\n[1] BERTSCORE: EVALUATING TEXT GENERATION WITH BERT", "reasons_to_reject": "1) The performance of the proposed method is highly dependent on the scoring mechanism [1]. The proposed set-based method did not perform well using the setup in the paper for cosine and bm25 metric. \n\n2) The paper discusses scalability issues but provides no experimental results (other than time complexity) on comparing time in their 8-shot setup. This would help readers understand performance gain compared to the computation resources requirement.\n\n\n\nReference\n\n[1] BERTSCORE: EVALUATING TEXT GENERATION WITH BERT", "questions_to_authors": "1) The paper uses all-mpnet-base as a base for cosine similarity but deberta-large-mnli for BERTScore. What is the impact on evaluations if different base embeddings are used for these two metrics? What are the justifications for utilizing these embeddings as the base models?", "paper_topic_and_main_contributions": "Demonstration selection is a challenging task in-context learning. The general approach to example selection is to select top-k based on a metric. The paper proposes a set-based method that helps maximize the salient aspects to select examples for demonstration and show that their methodology improves over many tasks.", "excitement": 3, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Missing_References": "1) The idea of the paper is similar to [1]. Would like to have some discussions around different batch-mode selection strategies in another domain.\n\n\nReference\n[1] Batch Active Learning at Scale", "Justification_for_Ethical_Concerns": "N/A"}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, the authors propose to optimize set-level metrics for in-context learning to achieve better coverage of salient aspects. It proposed a BERTScore-based set metric and provides the proof of its submodularity. Experiments with several conventional LLMs and generation tasks show that the proposed metric can result in better in-context learning performance.

Strength:
1. The research problem studied in this paper (demonstration selection) is very important.
2. The proposed method is also simple and does not require any training
3. Extensive experiments with various LLMs and tasks.
4. Overall clear presentation with concrete examples.

Weakness:
1. Would be good to provide significance tests and evaluation of efficiency.
2. Lack of comparison to related area such as active learning [Batch Active Learning at Scale]
Decision: Accept-Findings