Finding Support Examples for In-Context Learning
Authors: Xiaonan Li
Xipeng Qiu
Venue: EMNLP 2023 Findings (2023)
Keywords: In-Context Learning
ICL
Language Model
TL;DR: Finding Support Examples for In-Context Learning

Abstract: In-context learning is a new learning paradigm where a language model observes a few examples and directly outputs the test input's prediction. Previous works have shown that it is sensitive to the provided examples and randomly sampled examples probably cause inferior performance. In this paper, we propose finding ``support examples'' for in-context learning: Given a training dataset, it aims to select one permutation of a few examples, which can well characterize the task for in-context learning and thus lead to superior performance. 
Although for traditional gradient-based training, there are extensive  methods to find a coreset from the entire dataset, they struggle to find important in-context examples, because in-context learning occurs in the language model's forward process without gradients or parameter updates and thus has a significant gap with traditional training. 
Additionally, the strong dependence among in-context examples makes it an NP-hard combinatorial optimization problem and enumerating all permutations is infeasible. Hence we propose **LENS**, a fi**L**ter-th**EN**-**S**earch method to tackle this challenge in two stages:
irst we filter the dataset to obtain individually informative in-context examples. Specifically, we propose a novel metric, InfoScore, to evaluate the example's in-context informativeness based on the language model's feedback, and further propose a progressive filtering process to filter out uninformative examples.
Then we propose diversity-guided example search which iteratively refines and evaluates the selected example permutations, to find examples that fully depict the task. 
The experimental results show that LENS significantly outperforms a wide range of baselines and further analyses show that each component contribute critically to the improvements and shed light on the principles of supporting examples and in-context learning.

Finding Support Examples for In-Context Learning
Xiaonan Li, Xipeng Qiu
School of Computer Science, Fudan University Shanghai Key Laboratory of Intelligent Information Processing, Fudan University {lixn20, xpqiu] fudann.cu..cn
Abstract
L( P y
In-context learning is a new learning paradigm where language model observes few exam- ples and then directly outputs the test input's prediction. Previous works have shown that it is sensitive the provided examples and randomly sampled examples probably cause in- ferior performance. this paper, we propose finding "support examples" for in-context learn- ing: Given a training dataset, it aims to select one permutation of few examples, which can well characterize the task for in- in-context learn- ing and thus lead to superior performance. Al- though for traditional pradient-based training, there are extensive methods to find a coresct from the entire dataset, they struggle to iden- tify important in-context examples, because in- context learning occurs in the language model's forward process without gradients or parame- ter updates and thus has significant discrep- ancy with traditional training. Additionally, the strong dependency among in-context exam- ples makes it an NP-hard combinatorial opti- mization problem and enumerating all permuta- tions is infeasible. Hence we propose LENS, L.te--hEN--Sarde method to tackle this chal- lenge two stages: First we filter dataset to obtain informative in-context examples individ- ually. Specifically, we propose a novel metric, InfoScore, evaluate the example's in-context informativeness based on the language model's feedback, and further propose progressive fil- tering process to filter out uninformative exam- ples. Then we propose wversity-guider exam- ple search which iteratively refines and evalu- ates the selected example permutations, to find examples that fully depict the task. The exper- imental results show that LENS significantly outperforms wide range of baselines.
Model
x1 y1 x2 y2
(a) Model Training
(b) In-context learning
Figure I: In-context learning and model training learn in different ways, where and & are forward and backward processes, respectively, and L(---) is the loss function.
ing examples, LM can directly output the predic- tion of given test input without parameter updates. Restricted by LM's max input length, it is typical to randomly sample a small set of examples from the entire dataset for in-context learning (Brown et al., 2020; Zhang et al., 2022a). However, in-context learning sensitive to the provided examples and randomly sampled in-context examples show sig- nificant instability and probably cause inferior per- formance (Lu et al., 2022; Chang and Jia, 2023). this paper, we propose to select a small list of ex- amples that are informative and representative for the entire dataset as in-context examples. Inspired by the traditional machine learning method, Sup- port Vector Machine (SVM) (Cortes and Vapnik, 1995), where few support vectors closest the decision boundary and provide crucial discrimi- native information for SVM, we name the selected examples for ICL as support examples since they provide crucial task information for the LM and their quantity is usually limited, too.
There is a similar problem in traditional gradient- based deep learning like fine-tuning (Devlin et al., 2019), typically called Coreset Selection (Guo et al., 2022), which aims to select a set of rep- resentative training examples for the dataset to ben- efit many downstream scenarios like data-efficient learning (Adadi, 2021), active learning (Ren al., 2022), neural architecture search (Shim al., 2021), etc. However, challenging for these coreset selection methods to select important in-
1 Introduction
In-C un-Context Learning (ICL) a new paradigm using the language model (LM) to perform many NLPP tasks (Brown et al., 2020; Dong et al., 2022: Zhao et al., 2023). ICL, by conditioning on a few train-

---

Examples
Acc
combinations and verify their performance. How- ever, it will lead combinatorial explosion and thus is infeasible.
The casting of Raymond J. Barry the 'assassin'
82.0
gready enhances the quality It was [great]
At some point. all this visual trickery stops being 85.3 clever... It was [terrible]
To tackle these challenges, we propose LENS, a -itee-hhEN-Search that finds support examples in two stages: in the first stage, we filter the dataset to obtain informative in-context examples individu- ally. Specifically, we propose InfoScore to evalu- ate the example's 's in-context informativeness based on the LM's feedback, and further propose a pro- gressive filtering process to filter out uninforma- tive examples; In the second stage, we propose a diversity- guided example search method that itera- tively refines and evaluates the selected examples to find support examples that can fully depict the task. We summarize our contributions as follows:
1. The casting of Raymond ... It was [great] 2. At some point, all this visual trickery... It was [terrible]
56.0
At some point, all this visual trickery ... was 74.4 [great] 2. The casting of Raymond... ... It was [terrilec]
Table 1: The case study of examples' combinatorial dependency on SST-2, where "it was Igreat/terrible" is the template. Although two examples bring good performance separately, combining them instead hurts performance.
context examples because there is a significant dis- crepancy between traditional training and ICI. As shown in Figure 1, the "learning" paradigms of model training and ICL are highly different. Tra- ditional training depends on back-propagation's gradients to update parameters while ICL occurs in LM's forward process without gradients and param- eter updates. Existing coreset selection methods are always coupled with the training procedure, i.c., they usually depend on gradients or run with the training procedure. For example, Paul et al. (2021) select informative examples by their gra- dients' norm. Toneva et al. (2019) evaluate each example's importance by counting how many times it is forgotten, i.e., the example misclassified af- ter being correctly classified in the previous epoch. Additionally, coreset selection methods mainly de- pend on the example's gradients as the feature of example selection (Mirzasoleiman et al., 2020; Kil- lamsetty et al., 2021a.b Guo et al., 2022). However, LM performs ICL through inference, which does not rely on gradients parameter updates. Hence, the gap between gradient-based training and ICL makes these methods struggle to effectively select informative examples for in-context learning. Another challenge is the strong dependency among in-context examples. Previous work (Lu et al., 2022) shows that even the same example set with different orderings can result in drastically different performance from random- guess level to state-of-the arrt Here we also conduct an additional case study to shed light on examples' combinatorial dependency in Table 1. We see that compared with two examples" individual performance, combining them instead significantly hurts the performance. To cope with examples' dependency, a straightfor- ward method is to enumerate all possible examples'
To the best of our knowledge, we are the first to define the support examples selection prob- lem for in-context learning and introduce a novel aiter-then-sear method to tackle it.
We conduct experiments on various text clas- sification datasets and compare our method with a wide range of baselines. Experimental results demonstrate that our method signif- icantly outperforms baselines and previous coreset selection methods bring marginal im- provements over the random baseline, which shows the necessity of ICL-specific designing for finding support examples.
We conduct further analyses on support ex- amples and find that they exhibit different trends from random examples in many as- pects, which can shed light on the principle of them and ICL. We provide the following key takeaways: 1. Support examples are less sensitive to the order compared with random examples (Lu et al., 2022). Ground truth labels matter for support examples, while the previous study (Min et al., 2022b) show that they are not important for randomly sampled examples. 3. One LM's support examples can be well transferred to other LMs with differ- ent sizes and pre-training corpora and keep the superiority over random examples.
We provide comprehensive empirical results of previous coreset selection methods on ICL, which has not been explored. We release the implementation of our method and baselines facilitate future research'.
http:///sshubboomm/LeeSseeenncct Support Example

---

2 Background:In In-Conex Learning
Algorithm 1 Progressive Example Filtering
Input: Training set 'D = { Ye language model G, de- sired candidate size m, progressive factor initial score data size I.
In this section, introduce the definition of in- context learning. We focus text classifica- tion's co-tontext learning using the causal language model (Radford et al., 2018). Given a language model G, n examples {.,, yi 3- and a test input Eiest, the prediction of Trest is generated as:
Output: Individually informative examples D
1: D' <-D
2:
S 4- Randomly sample examples from D.
3: while (D') > v do
4:
D' do s(e,) ((, end for
for
5:
arg max (alyl 1 @ 20 yEy where J' is the label space and @ is the con- catenation operation. To deal with classification tasks, the original label is often mapped to word words in G's vocabulary. For example, the pos- itive/negative label in a binary sentiment classifi- "great"/"terrin""
2 1 yr. @ Fmeat)
(1)
6:
7:
if [D'l/p then
8:
D' +- the top-m of D' using (=(e)))
9:
Break;
10:
else
11:
<- the top using [[
12:
end if
13:
S' Randdomly sample 1 (p 1) examples from D
cation can be mapped simplicity, we omit the verbalizer, special tokens and prompting templates in Eq (1).
For
14:
S 5 S"
15:
end while
16:
return 2
As (1) shows, G receives the task's supervi- sion only from the concatenated {a, yi ) and directly output the prediction of Fiest- Typically, n is limited by the max input length of G, so it is typical for researchers to randomly sample a small set of samples from the entire dataset D (Brown al., 2020; Zhang et al., 2022a). How- ever, ICL is sensitive the provided examples and random in-context examples show significant insta- bility and probably cause inferior performance(Lu et al., 2022; Chen et al., 2022). In this paper, we focus on selecting small list of support examples that are informative for the task and performant for in-context learning, from the entire dataset D.
methods to measure the example's importance for gradient- training, like the example's gradient norm (Paul et al., 2021), loss value in the early train- ing stage or the times of being forgotten (Toneva et al., 2019), etc. However, these methods strug- gle to identify important in-context examples since ICL is based on LM-inference without gradients and parameter updates. Here we propose InfoS- core (Informativeness Score) to measure the indi- vidual in in-context informativeness of one example c == {x. y) for ICL based on LM's feedback as:
I(e, D) = c(e,ee)
CED
c(e, (cc''''=o(s'' (x, v.) pa(s/la)),
3 Method
The strong dependency among in-context exam- ples makes selecting support examples essentially an NP-hard combinatorial optimization problem. Enumerating all combinations and evaluating them is infeasible due to the combinatorial explosion. In this section, we propose LENS, ALter-thEN. Search method to find support examples: we first filter the training dataset to obtain informative examples individually, 2. then we search the ex- ample permutation that fully depicts the task from them. In this paper, we instantiate the two stages as novel example metric with progressive filter- ing and diversity-guides example search, we leave the development of more powerful components as future work. We introduce these two stages below.
where e' = (x' v/). and D is the training dataset. Eq (3) is the gap between the probabilities of the ground truth y' conditioned on (e, x²) and (a'), re- spectively. So evaluates how informative is for the LM to correctly classify x' and thus measures e's contribution for e' in ICL. Hence, [e, D), the sum of Eq (3) over D, can evaluate the example's s lask- in-context informativeness.
However, computing all examples' InfoScores over the entire dataset is quadratic in [D] and thus infeasible. We further propose progressive filter- ing process filter out uninformative examples progressively, where promising examples receive more computation while low-quality examples get less computation, shown in Algorithm
We filter out uninformative examples in a pro- gressive manner. We first sample a small set of examples from D as initial "score set" (line 2) to coarsely evaluate the InfoScore of each example
3.1 Informative Examples Filtering
In the first stage, we aim to find those informa- tive examples individually. There are extensive

---

Algorithm 2 Diversity-Guided Search
alone considering the examples' orders.
Input: Candidate examples D' [e:][= candidates' fea- ture [((e)))._.. small validation set V. iteration num I, beam size B, example substitution size 8
Hence we propose diversity-guided example search iteratively refine the example selection from filtered examples and obtain the support ex- amples, as shown Algorithm 2. starts with a set of initial example permutations. At each itera- tion, we use the diversity of in-context examples to guide the update of the current candidate permuta- tions. Specifically, for each candidate permutation E [ei][=1 we randomly select an example e* in E and update it with the example enew
Output: A performant examples' permutation.
2: for in {EA)==1 initialize B examples' permutations
I: 8
1,2
3:
E" E
4: for in (E,) do
for b 1.2... do
6:
e* Randomly sample an example from K
6.e f- argmax, DE a(c, =x")
8:
- Replace E" with Snew E' E'"
9:
10:
end for
11:
for in 1, .......... B' do
Enew argmaxxee! ale, E*) a(e, ==:==(===ee>)))
(4)
12:
E" - Randomly shuffle E -"-
Σ (m(((())((e)) e'E
(5)
13:
14:
end for E t Evaluate 8" on V and get the top-B
15:
where E e", X is pre-defined hyper- parameter, S = {e is the final score set the filtering stage. The subsequent term of s(c, E") in Eq (5) corresponds to the diversity between e and E', and f(-) is the example's feature vector calculated
16:
end for
17:
end for
18:
return The top-1 of
and filter the entire dataset to 1/p of its original size (line 5). At the following iteration, we pro- portionally expand the size of the score set to p times by randomly sampling more examples from training set (line 13~15) and foScore of the remaining promising examples. As the score set is expanded, the subsequent InfoScore can be calculated a more fine-grained way and better filter informative examples. Meanwhile, the uninformative examples are filtered out in the pre- vious iteration, which helps save the computational cost. We repeat this procedure until small set of examples left.
f(e) ei(e, "leee.. cle,,ess))
(6)
where (ee describes e's contribution on S's each example of in ICL and thus directly encodes e's in-context feature. If two examples' f(-) sim- ilar, their effect on ICL can be redundant and we should avoid selecting both of them in one permuta- tion. Note that [(e, S) and each c(e, et) in fe) are calculated in the filtering stage and can be reused. With s(e, E') and f(e). the updated candidate permutations can be informative and diverse, and help the LM correctly predict various examples, which can better help find the support examples that fully depict the task in ICL. In this paper, we propose and verify simple yet effective example ICL feature. We leave the development of more powerful ones future work.
calculate In-
Thus we achieve filtering examples with high in-context informativeness in the complexity of O(N log, .). where N is the size of training set, experiments, we set p to dà to make it linear complexity, where the size dataset, p is usually set between 3.
constant. According to
Since examples' order significantly influ- ence the performance (Lu et al., 2022; Kumar and Talukdar, 2021), we also update E with different orders by randomly shuffling (line 10~13), which can reduce the risk of missing performant combina- tions of examples due to poor ordering. In order To explore the example search space more comprehen- sively and alleviate risk of the local-optimal exam- ple permutation, consider the beam search (Ju- rafsky and Martin, 2009) here instead of greedy search. Specifically, we update each candidate example permutations by diversity-based exam- ple substitution and random shuffling for B' and B - times, respectively (line 5, 10). Then
3.2 Diversity-Guided Example Search
After filtering, we get individually informative examples D'. Since the in-context examples have high combinatorial dependency (see Table 1), a straightforward method is to enumerate all possible combinations and evaluate them on validataion set. However, although we have reduced the candi- date examples by filtering, it still impossible to evaluate all combinations. For example, there are 50 examples retained after filtering and we want to find a combination examples from them, it can lead to C (about 536 million) combinations, let

---

we leverage a small validation set sampled from DD) evaluate them and keep the top-B per- mutations with best performance as next iteration's candidates. Through these, we can the mitigate issue of local-optimal example permutation, better iteratively refine and evaluate the candidate permu- tations with high informativeness and diversity in turn and obtain the examples that can fully depict the task.
gatina et al., 2021); Error/Loss Based Method: assumes the example that contributes more the error or loss during training is more important and should be included in coreset, including For- getting (Toneva et al., 2019) and GraNd (Paul et al., 2021); Gradient Matching Based Method: Since deep models are usually trained by gradient descent, it tries to find coreset whose gradients can imitate the entire dataset's gradients, including CRAIG (Mirzasoleiman al., 2020) and Grad- Match (Killamsetty al., 2021a); Submodularity- Based Method: Submodular functions (Iyer and Bilmes, 2013) naturally measure a subset's ' informa- tiveness and diversity and can thus be powerful for coreset selection, including Facility Location and Graph Cut (Iyer and Bilmes, 2013); Bilevel Op- timization Based Method: It transforms the core- set selection problem into a bilevel-optimization problem whose outer and inner objectives are sub- set selection and model parameter optimization, respectively: Glister (Killamsetty et al., 202 2021b). Due to the page limit, we introduce these methods and their implementation details in Appendix A and Appendix B. respectively.
To initialize example permutations E with infor- mativeness and diversity, we formulate it discrete optimization that maximizes Eecg s(e, E e). which can be solved by the discrete optimization solver like CPLEX (Cplex, 2009).
4 Experiments
4.1 Experimental Settings
Dataset In this paper, we conduct experiments on eight text classification datasets across three task families, including Sentiment Classification: SST- 2, SST-5 (Socher et al., 2013), Amazon (McAuley and Leskovec, 2013) and MR (Pang and Lee, 2005); Subjectivity Classification: Subj (Pang and Lee, 2004); Topic Classification: TREC (Voorhees and Tice, 2000), AGNews (Zhang et al., 2015) and DB- Pedia (Lehmann et al., 2015).
Implementation Details For the LM, we follow Min al. (2022a) to GPT2-L (Radford et al., 2018). We set the number of retained examples of filtering m, the weight of diversity X, the beam size B and the number of diversity search iterations as 500, 1, 8 and 10 respectively. We show the overall implementation details, analysis details and complexity analysis in Appendix B. For baselines and LENS, we run each method under 4 prompt templates over 10 random seeds (40 in total) and report the average performance with and without calibration (Zhao al., 2021), unless oth- erwise specified. We show the overall templates and dataset statistics in Appendix C and D.
Method Comparison We mainly compare our proposed methods with the following baselines: Random: We randomly select examples from the training set; Random & Validation: We evaluate multiple sets of random examples on the validation set and select the best one. We consider Random & Validation under two settings whose computa- tional cost similar to our method: 1. the size of validation set is the same as ours at stage (100) and the number of random example sets is the same our searched and evaluated example permutations (640). 2. the size of validation set is larger, 1000, and the number of random exam- ple sets is 100. We also consider a wide range of Coreset Selection methods in gradient-based learning scenarios, according to the methodologies, they can be divided into multiple categories includ- ing: Geometry-Bate Based Method: it assumes that data points that are close in the feature space have similar properties, including Herding (Chen et al., 2012) and K-Center Greedy (Sener and Savarese, 2018); Uncertainty-Bart
4.2 Main Results
We show the results in Table 2. We observe that our method significantly outperforms baselines on all datasets with or without calibration mecha- nism, which shows our method's best overall abil- ity to find task-representative support examples across different settings and task familics. Spe- cially, our method shows better performance than the Vaaiiatiinn baseline and this directly demonstrates its non-triviality. Meanwhile, previ- ous methods for gradient- learning have simi- lar performance with the Random baseline, and this
Method: it assumes ex- amples with higher uncertainty can have greater impact on the model and should be contained in coreset, including Least Confidence, Entropy. Margin (Coleman et al., 2020) and CAL (Mar-

---

Method
SST-2
SST-5
Amazon
Subj
TREC
AGNews
DBPedia
Average
zero-shot
63.0/80.3
27.5/33.3
31.2/37.6
61.7/77.4
51.0/52.0
38.7/27.7
59.8/59.9
32.3/37.6
45.6/50.7
Random
57.9/64.4
27.5/23.9
73.7/78.5
59.5/67.1
55.0/60.9
30.3/24.9
33.6/47.8
16.3/64.7
44.2/54.0
Herding
62.0/63.7
24.8/20.5
75,4/71.9
54.1/57.3
56.5/56.7
26.4/22.2
38.7/35.7
7,4/61.7
43.2/48.7
K-Center Greedy
58.6/61.6
25.1/23.0
78.6/76.3
59.0/61.3
59.9/57.0
31.3/26.4
42.3/37.8
32.1/72.1
48.4/51.9
Entropy
62.4/67.4
25.5/26.6
71.4/76.2
54.1/56.2
53.9/51.7
26.2/21.3
30.6/35.3
14.5/46.9
42.3/47.7
1 LeastConfidence
58.4/63.0
26.0/332
73.8/72.1
55.9/57.3
58.0/519
23.5/21.5
31.6/36.7
9.1.59.9
42.0/48.2
Margin
62.4/67.4
26.1/22.6
76,9/76.6
54.1/56.2
53.9/51.7
24.2/21.0
38.1/45.0
7.1/58.4
42.9/49.9
Cal
59.3/66.7
25.3/25.5
75.7/75.4
66.2/67.7
64.6/55.6
31.8/30.7
42.3/46.6
30.3/73.9
49.4/55.3
Forgetting
61.6/68.2
27.7/23.5
77.178.22
56.7/59.4
55.1/53.2
28.7/28.6
33,4/39.8
10.5/64.7
43.9/52.0
GraNd
54.6/56.5
27.8/24.9
75.5/73.4
52.8/55.8
55.7/51.9
28.2/23.9
33.4/53.2
21.2/64.0
43.7/50.5
CRAIG
63.4/72.0
26.4/25.3
75.4/80.6
59.3/66.7
57.0/54.8
32.0/24.8
37.4/55.4
29.5/71.0
47.6/56.3
GradMatch
57.0/61.9
26.3/23.4
75.1/76.0
56.6/62.1
55.8/64.6
25.8/21.4
32.6/39.4
9.7/57.8
42.3/49.6
FacilityLocation
65.5/73.2 23.9/24.3
77.7/7766
61.7/69.6
59.0/54.5
35.7/29.1
42.5/58.6
30.4/74.3
49.6/57.7
GraphCut
65.0/71.4
25.3/24.6
76.5/78.4
66.3/72.3
63. 63.2/56.6
34.7/28.4
41.9/50.8
14.0/47.3
48.4/53.7
Glister
59.0/61.0
25.8/25.2
78.0/77.7
60.1/66.6
60.6/57.0
29.4/23.4
38.6/41.1
24.1/69..
46.7/52.7
Random Valid (100)
70. 1/72.8
33.2/29.6
76.3/78.4
53.2/S7.9
60. 60.7/58.9
30.3/24.9
40. 1/33.6
37.2/56.7
50. 50.1/51.6
Random & Valid (1000)
65.0/62.6
29.0/30.8
78.5/78.6
57.7/62.5
61.9/53.4
32.8/29.4
43.5/56.1
37.8/73.6
49.5/55.9
LENS
86.3/87.6
44.9/42.1 80.2/83.9
83.1/83.9
86.4/81.5
59.0/48.8
77.9/78.1
40.8/80.7
69.8/73.3
Table 2: Results on GPT22LL Each entry shows the ICL accuracy without and with calibration (Zhao al., 2021).
ordering of in-context examples for ICL has a sig- nificant influence on the performance. Specifically, to the same set randomly sampled examples, different orders can result in near state-of-the-art and random-guess performance. In this section, we explore the effect of ordering for our support examples on SST-2, Amazon, MR and Subj. For each task, select four sets of support examples and four sets of random examples and then evalu- their performance with eight randomly sampled orders. We show the performance distribution Figure We see that random examples with dif- ferent orders show highly unstable performance where the worst drops to the random-gued guess level, which is consistent with the conclusion in previous work (Lu et al., 2022). In contrast, the support ex- amples' performance is significantly more stable than random examples. Generally, most orders can still lead to approximately equivalent performance as the searched orders and few orders lead the random-guee -uesss performance. The phenomenon is compatible with the conclusion from the recent work (Chen et al., 2022), which shows strong negative correlation between ICL sensitivity and accuracy. Moreover, our support examples' lower sensitivity the ordering demonstrates that they can more effectively depict and characterize the corresponding task.
Oles
Ranioon
Diss
Ranionn
(a) SST-2
(b) Amazon
Osze
Usp
(c) MR
(d) Subj
Figure 2: The performance distribution of support ex- amples and random examples with multiple orders.
indicates: 1. there is a noglnggli gap between ICL and these methods 2. it is necessary to design to ICL-specific method to find support examples. Additionally, the Random baseline slightly un- derperforms the Zero-Shot, which shows that ran- dom examples are hard to fully characterize the task and the necessity of finding support examples for ICL. In experiments, we obscrve that Random- Validation suffers from the ICL's instability. Specif- ically, we find that considerable example permuta- tions selected by the validation set do not consis- tently yield satisfactory results on the test set and this degrades its performance, whereas our method is more robust and less susceptible to this issue.
4.3 Analysis
Transferablity across Different LMs In the main experiments, we get GPT2-L's support ex- amples and evaluate them using the same LMM And
The Sensitivity of Support Examples to Orders The recent study (Lu et al., 2022) shows that the

---

Examples SST-2 MR TREC AGNews Average
SST-2
Subj
TREC
Average
GPT2-XL
Random
57.9
55.0
30.3
47.7
Random
60.3
66.7
34,4
56,9
54,6
p=1.5
86.6
86.1
59.5
77.4
LENS
73.0
70.7
44.0
60.4
62.0
p=2
86.3
86.4
59.0
77.2
p=3
85.1
86.0
58.7
76.6
GPT2-M
m 50
83.6
84.1
56.2
74.6
Random LENS
65.0
33.4
51.7
52.4
m 500
86.3
86.4
59.0
77.2
82.0
75.5
37.5
75.3
67.6
m 1000
86.1
85.9
59.1
77.0
GPT-Neo-2270
86.3
86.4
59.3
77.3
Random
57.3
55,8
29.4
71.6
53.5
x=
86.5
86.2
58.8
77.2
LENS
62.5
65.2
45.0
80.2
63.2
0
85.9
86.
58.7
76,9
A=
67.5
68.2
37.7
57.8
Table 3: The transfer of GPT2-L's support examples on LMs with different sizes and pre-training corpora: GPT2-M, GPT2-XL and GPT-Neo-2.7B.
B=
83.1
76.2
42.2
67.2
B=4
85.9
86.0
58.5
76.8
==8
86.3
86.4
59.0
77.2
Trals
Talil
Table 4: Impact of different papeer-arrmeters.
performance of support examples and random ex- amples with GT or random labels in Figure 3. We see that the results on random examples are con- sistent with that in the previous paper (Min et al., 2022b). However, we observe a significantly differ- ent trend in support examples. Specifically, after re- moving GT labels, support examples' performance gets strong degradation. We suppose it is because while random examples can not characterize the task well and thus their GT labels are not important, the GT labels of support examples contain crucial task information and input-output correspondence, so their GT labels are important for ICL's perfor- mance. Meanwhile, we find that under random labels, support examples also yield noticeable im- provements over the random examples, which indi- cates that the inputs of support examples are also more informative for the task.
(a) SST-2
(b) Amazon
Cale
Bundon
(c)
Subj (d) AGNews
Figure 3: The results under gold and random labels.
here we explore the transferability these sup- port examples across different LMs with various sizes and pre-training corpora. Specifically, we test the support examples of main experiments on GPT2-M (355M), GPT2-XL (1.5B) and GPT-Neo- 2.7B (Black et al., 2021). The results shown in Table 3. We see that GPT2-L's support exam- ples also show better performance than the Random baseline. Additionally, our support examples also demonstrate the consistent superiority on GPT-Neo- 2.7B which has different pre- pre-training corpus from GPT2-L. Since random examples' performance can not be well transferred to other LMs (Lu et al., 2022), these can show the strong transferability of support examples and the utility of our method when more powerful LMS proposed.
The Impact of paraee-pss In this sec- tion, we evaluate the effect of each hyper-parameter. Specifically, we evaluate the effect of progressive ratio p, the number of stage I's retained examples m, the weight of diversity and the beam size B by separately tuning them and observing per- formance. Table 4 shows the results. When is set to O, i.e., we remove stage 2 and just select those examples with the highest InfoScore, the per- formance gets significantly degraded, and this di- rectly demonstrates the effectiveness and necessity of stage 2. Except when B O, our method leads to consistent performance improvements compared with the Random baseline in general. across var- ious hyper-parameter configurations, which indi- cates our method's robustness to hyper-parameters. Mcanwhile, we observe two slight performance degradations when m = 100 or B = 1. For
Ground Truth Matters for Support Examples Recently, Min et al. (2022b) suggests that ground truth (GT) labels are not important for ICL, which differs from traditional supervised learning. In their experiments, for randomly sampled examples, us- ing ground truth labels or not leads to similar ICL. performance. Here we explore the effect of ground truth labels for support examples. We show the

---

Subj
AGNews
demonstration retriever based on the feedback of the language model for semantic parsing. Wu et al. (2022) use Sentence-BERT (Reimers and Gurevych, 2019) to retrieve relevant examples and introduce an information-theorriiccc to rerank their permutations. Levy et al. (2022); Ye et al. (2023) further consider diversity in exam- ple retrieval. Different from these methods which aim provide example-specific information for the test input, we focus on task-level example selection, which seeks to find examples that are representative for the task and is complementary to them. More- over, because the large language models (Brown et al., 2020; Zhang et al.. 2022a; Black et al., 2021) almost adopt purely causal Transformer (Vaswani et al., 2017) decoder architecture, we can calcu- late task-level in-context examples representation in advance and reuse them for different test inputs. Since these two settings' goals are orthogonal and complementary, we regard the hybrid setting and method as future work. Another line of methods is active learning (Ren et al., 2022) for ICL., It aims to select some examples from large pool of unla- beled data and annotate them for ICL. Zhang et al. (2022b) propose to learn active example selector by off-line reinforcement learning and use to lect examples to annotate for ICL. Su et al. (2022) propose a graph-based annotation method, vote-k, and use Sentence-BEie to retrieve relevant exam- ples from the annotated examples for ICL. In this paper, we explore a different setting for ICL'S ex- ample selection, where we select support examples from the annotated dataset since there are massive annotated datasets for various tasks and the prevail- ing large language model has shown impressive data annotation ability (Efrat and Levy, 2020; Gao et al., 2022: Ye et al., 2022: Meng et al., 2022: Cheng et al., 2023).
Random
55.0
33.6
Filtering (Uninformative)
52.5
27.4
Filtering (Informative)
65.8
47.8
Filtcring+ Scarch
86.4
77.9
criterion
Table 5: The Effect of Progressive Filtering.
the case that m = 100, we suppose that is be- cause there too few examples being retained after stage 1, limiting candidate examples' diversity, When B I, our stage degrades greedy search guided by the diversity, causing it susceptible to the local optimum issue.
InfoScore and Progressive Filtering In this sec- tion, we evaluate the effect of InfoScore and pro- gressive filtering in stage 1. Specifically, we ran- domly sample examples from the retained exam- ples of stage and test their average performance across 4 prompt templates with 10 random orders (40 in total). We compare the Random baseline. our filtering method and another filtering variant that filters uninformative examples, which retains those examples with low InfoScore at each itera- tion. We show the results in Table 5. We observe that just the proposed filtering method also leads to better ICL performance than randomly sampled examples, which directly shows that stage is ef- fective for filtering out the uninformative examples. Meanwhile, the performance points of Filtering (Informative), Random and Filtering (Uninforma- tive) present a descending trend, which demon- strates that the proposed InfoScore can indicate the examples' in-context informativeness. However, compared with our entire method, Filtering (Infor- mative) still shows significant discrepancy. This indicates the necessity of considering in in-context examples' dependency and the effectiveness of the proposed diversity-gun guided search.
5 Related Work
Conclusion
Since we introduce wide range of coreset selec- tion methods in Section 4.1, we omit them here and mainly introduce previous works about ex- ample selection for ICL. Previous works mainly consider example-level retrieval for ICL. Liu et al. (2022) leverage a semantic embedder to retrieve relevant examples for the given test input. Das al. (2021) and Hu et al. (2022) use dense re- trievers trained by task-specific targets' similarities to retrieve in-context examples for question an- swering and dialogue state tracking, respectively. Rubin et al. (2022); Shi et al. (2022) train the
In this paper, we propose a two-stage filter-then- search method to find support examples for in- context learning from the annotated dataset: First we propose InfoScore to select informative exam- ples individually with a progressive filtering pro- cess. Then we propose uiversity-guided example search which iteratively refines and evaluates the selected examples, find the example permuta- tions that fully depict the task. The experimen- tal results show that our method significantly out- performs extensive baselines, and further analyses show that each component contributes critically to

---

the improvements and shed light on the principles of support examples and in-context learning.
Alec Radford, Ilya Sutskever. and Dario Amodei. 2020. Language models are few-shot leareer. In Ad- vances in Neural Information Processing Systems 33: Anmual Conference on Neural Information Process- ing Systems 2020, NeurlPS 2020, December 6-12, 2020, viriual.
Limitations
These are the limitations of this work:
Due to the computation resources limitation, we mainly conduct experiments on GPT2- L (Radford et al., 2018) 8) and analyze the cross- LM transferability of support examples in sec- tion 4.3. We see the exploration more LMs as future work.
Ting- Yun Chang and Robin Jia. 2023. Data curation alone can stabilize in-context learning.
Yanda Chen, Chen Zhao, Zhou Yu, Kathleen R. McKe- own, and He He. 2022. On the relation between sen- sitivity and accuracy in in-context learning. CoRR, abs/2209.07661.
Yutian Chen, Max Welling, and Alexander J. Smola. 2012. Super-samples from kernel herding. CoRR, Abs//100..472.
In this paper, the proposed filter-then-search framework explores how to find support exam- ples of in-context learning. We see exploring and analyzing more principles of in-context learning as future work.
Qinyuan Cheng, Xiaogui Yang. Tianxiang Sun, Linyang Li. and Xipeng Qiu. 2023. Improving contrastive learning of sentence embeddings from Al feedback. In Findings of the Association for Computational Linguistics: ACL 2023. pages 11122-11138, Toronto, Canada. Association for Computational Linguisties.
Language models have exhibited various kinds of bias (Bender et al., 2021), since our filtering stage is based on its feedback, the filtered example might also exhibit these bi- ases. We see language model debiasing as an important future research topic.
Cody Coleman, Christopher Yeh, Stephen Mussmann. Baharan Mirzasoleiman, Peter Bailis, Percy Liang, Jure Leskovec, and Matei Zaharia. 2020. Selection via proxy: Efficient data selection for deep learning. In Sth International Conference on Learning Repre- sentations, ICIR 2020, Addis Abuba, Ethiopia, April 26-30, 2020. OpenReview.net
A Acknowledgements
This work was supported by the National Natural Science Foundation of China (No. 62236004 and No. 62022027).
Corinna Cortes and Vladimir Vapnik. 1995. Support- vector networks. Machine learning, 20(3):273-297.
IBM ILOG Cplex. 2009. V12. 1: User's manual for cplex. International Business Machines Corporation, 46(53):157.
References
Amina Adadi. 2021. A survey on data-efficient algo- rithms in big data era. J. Big Data, 3(1):1-54.
Rajarshi Das, Manzil Zaheer, Dung Thai, Ameya God- bole, Ethan Perez, Jay Yoon Lee, Lizhen Tan. Lazaros Polymenakos, and Andrew McCallum. 2021. Case- based reasoning for natural language queries over knowledge bases. In Proceedings of the 2021 Confer- ence on Empirical Methods in Natural Language Pro- cessing. EMNLP 2021, Virtual Event / Punta Cana, Dominican Republic, 7-11 November, 2021, pages Association for Computational Linguis-
Emily M. Bender, Timnit Gebru, Angelina McMillan- Major, and Shmargaret Shmitchell. 2021. On the dangers of stochastic parrots: Can language models be too big? In FAceT 21: 2021 ACM Conference on Fairness, Accountability and Transparency, Virtual Event/ / Toronto, Canada, March 3-10, 2021, pages 610-66 003-623.44 ACM.
tics.
Sid Black, Leo Gao, Phil Wang, Connor Leahy, and Stella Biderman. 2021. GPT-Neo: Large Scale Autoregressive Language Modeling with Mesh- Tensorflow.
Jacob Devlin, Ming-Was 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 Linguistics: Human Language Tech- nologies, NAACL-HLT 2019, Minneapolis, MN. USA, June 2-7, 2019, Volume (Long and Short Papers), pages 4171-4186 Association for Computational Linguistics.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neclakantan, 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,
Qingxiu Dong, Lei Li, Damai Dai, Ce Zheng, Zhiyong Wu, Baobao Chang, Xu Sun, Jingjing Xu, Lei Li, and Zhifang Sui. 2022. A survey for in-context learning.

---

Avia Efrat and Omer Levy. 2020. The turking test: Can language models understand instructions? CoRR, 1ts/2010.11982
Jens Lehmann, Robert Isele, Max Jakob, Anja Jentzsch, Dimitris Kontokostas, Pablo N. Mendes, Sebastian Hellmann, Mohamed Morsey, Patrick van Kleef, Sören Auer, and Christian Bizer. 2015. Dbpedia- A large-scale, multilingual knowledge base extracted from wikipedia. Semantic Web, 6(2):167-195.
Jiahui Gao, Renjie Pi, Yong Lin, Hang Xu, Jiacheng Ye, Zhiyong Wu, Xiaodan Liang, Zhenguo Li, and Lingpeng Kong. 2022. Zerogen*. : Self-guided high- quality data generation in efficient zero-shot learning. CoRR, abx/2205. 12679.
Itay Levy, Ben Bogin, and Jonathan Berant. 2022. Di- verse demonstrations improve in-context composi- tional generalization. CoRR, abs/2212.06800.
Chengcheng Guo, Bo Zhao, and Yanbing Bai. 2022. Deepcore: A comprehensive library for coreset se- lection in deep learning. In Database and Expert Systems Applications 33rd International Confer- ence, DEXA 2022, Vienna, Austria, August 22-24, 2022, Proceedings, Part I, volume 13426 of Lecture Notes in Computer Science, pages 181-195. Springer.
Jiachang Liu, Dinghan Shen, Yizhe Zhang. Bill Dolan, Lawrence Carin, and Weizhu Chen. 2022. What makes good in-context examples for gpt-3? In Pro- ceedings of Deep Learning Inside Out: The 3rd Work- shop on Knowledge Extraction and Integration for Deep Learning Architectures, DeeLIO@ ACL 2022, Dublin, Ireland and Online, May 27, 2022, pages 100-114, Association for Computational Linguistics.
Yushi Hu, Chia-Hsuan Lee, Tianbao Xie, Tao Yu, Noah A. Smith, and Mari Ostendorf. 2022. In- context learning for few-shot dialogue state tracking. CoRR, abs/2203.08566 088668.
Yao Lu, Max Bartolo, Alastair Moore, Sebastian Riedel, and Pontus Stenetorp. 2022. Fantastically ordered prompts and where to find them: Overcoming few- shot prompt order sensitivity. In Proceedings of the 60th Annual Meeting of the Association for Compu- tational Linguistics (Volume I: Long Papers), pages 8086 8096,-09,, Dublin, Ireland. Association for Compu- tational Linguistics.
Rishabh K. Iyer and Jeff A. Bilmes. 2013. Submodular optimization with submodular cover and submod- ular knapsack constraints. In Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Sys- lems 2013. Proceedings of meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pages 2436-2444.
Katerina Margatina, Giorgos Vernikss, Loie Barrault, and Nikolaos Aletras. 2021. Active learning by ac- quiring contrastive examples. In Proceedingy of the 2021 Conference on Empirical Methods in Natural Language Processing, EMNLP 2021, Virtual Event / Punta Cana, Dominican Republic, 7-11 November, 2021, pages 650-663. Association for Computational Linguistics.
Dan Jurafsky and James H. Martin. 2009. Speech and language processing: an introduction to nat- ural language processing, computational linguistiics, and speech recognition, 2nd Edition. Prentice Hall series in artificial intelligence. Prentice Hall, Pearson Education International.
Julian J. McAuley and Jure Leskovec. 2013. Hidden factors and hidden topics: understanding rating di- mensions with review text. In Seventh ACM Confer- ence on Recommender Systems, RecSys '13, Hong Kong, China, October 12-16, 2013, pages 165-172. ACM.
KrishnaTeja Killamsetty, Durga Sivasubramanian, Ganesh Ramakrishnan, Abir De, and Rishabh K. Tyer. 2021a. GRAD- MATCH: gradient matching based data subset selection for efficient deep model training. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 5464-5474. PMI..
Yu Meng, Martin Michalski. Jiaxin Huang, Yu Zhang, Tarek F. Abdelzaher, and Jiawei Han. 2022. Tun- ing language models training data generators for seanentation-enhaneee few-shot learning. CoRR, abs/2211 1.2211..00 1.0004..
KrishnaTeji Killamsetty, Durga Sivasubramanian. Ganesh Ramakrishnan, and Rishabh K. Iyer. 202 GLISTER: generalization based data subset selection for efficient and robust learning. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Thire Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial In- telligence, EAAI 2021, Virtual Event, February 2-9, 2021, pages 8110-8116 8118.188..88 AAAI Press.
Sewon Min, Mike Lewis. Hannaneh Hajishirzi, and Luke Zeutlemoyer. 2022a. Noisy channel language model prompting for few-shot text classification. In Proceedings of the 60th Annual Meeting of the As- sociation for Computational Linguistics (Volume 1: Long Papers), ACL 2022, Dublin, Ireland, May 22-27, 2022, pages 5316-536 5330- Association for Computa- tional Linguistics.
Sawan Kumar and Partha Talukdar. 2021. Reorder- ing examples helps during priming-basc based few-shot learning. In Findings of the Association for Com- putational Linguistics: ACL-IJCNLP 2021, pages 4507-4518, Online. Association for Computational Linguistics.
Sewon Min, Xinxi Lyu. Ari Holtzman, Mikel Artetxe. Mike Lewis, Hannaneh Hajishirzi, and Luke Zettle- moyer. 2022b. Rethinking the role of demonstrations: What makes in-context learning work? In Proceed- ings of the 2022 Conference on Empirical Methods

---

Natural Language Processing, EMNLP 2022, Abu Dhabi, United Arab Emirates, December 7-11, 2022, pages 11048-1 1064. Association for Computational Linguisties.
Representations, ICLR 2018. Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceed- ings. OpenReview.net
Peng Shi, Rui Zhang, He Bai, and Jimmy Lin. 2022. XRICL: cross-lingual retrieval-augmentee in-context learning for cross-lingual text-to-sa) sol semantic pars- ing. CoRR, abs/2210. 13693.
Baharan Mirzasoleiman, Jeff A. Bilmes, and Jure Leskovec. 2020. Coresets for data-efficient training of machine learning models. In Proceedings of the 37th International Conference on Machine Learning. ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 0950-6960. PMLR.
Jae-hun Shim, Kyeongho Kong, and Suk-Ju Kang. 2021. Core-set sampling for efficient neural architecture search. CoRR, abs/2107.06865
Bo Pang and Lillian Lee. 2004. A sentimental educa- tion: Sentiment analysis using subjectivity summa- rization based on minimum cuts. In Proceedings of the 42nd Annual Meeting of the Association for Com- putational Linguistics, 21-26 July, 2004, Barcelona. Spain, pages 271 271-278. ACL.
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Y. Ng, and Christopher Potts. 2013. Recursive deep mod- els for semantic compositionality over sentiment treebank. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, EMNLP 2013, 18-21 October 2013, Grand Hyatt Seattle, Seattle, Washington. USA, A meeting of SIG- DAT, a Special Interest Group of the ACL, pages 1631-1642. ACL.
Bo Pang and Lillian Lee. 2005. Seeing stars: Exploiting class relationships for sentiment categorization with respect to rating scales. In ACI. 2005, 43rd Annual Meeting of the Association for Computational Lin- guistics, Proceedings of the Conference, 25-30 June 2005, University of Michigan. USA, pages 115-124. The Association for Computer Linguistics.
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 learners. CoRR, abs/2209.01975.
Mansheej Paul, Surya Ganguli, and Gintare Karolina Dziugaite. 2021. Deep learning on a data diet: Find- ing important examples early in training. In Ad- vances in Neurul Information Processing Systems 34: Annual Conference on Neural Information Process- ing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 20596 20607.
Mariya Toneva, Alessandro Sordoni. Remi Tachet des Combes, Adam Trischler, Yoshua Bengio, and Geof- frey J. Gordon. 2019. An empirical study of example forgetting during deep neural network learning- In 7th International Conference on Learning Represen- tations, ICIR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2018. Language models are unsupervised multitask learners.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Advances in Neural Information Pro- cessing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 1998-6008
Nils Reimers and Iryna Gurevych. 2019, Sentence-bert Sentence embeddings using siamese nert-networks. Proceedings of the 2019 Conference on Empiri- cal Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, F.MNLP-ICCNIP 2019, Hong Kong, China, November 3-7, 2019, pages 3980-3990. Association for Computational Linguistics.
Ellen M. Voorhees and Dawn M. Tice. 2000. Building question answering test collection. In SIGIR 2000: Proceedings of the 23rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, July 24-28, 2000, Athens, Greece, pages 200-207. ACM.
Pengzhen Ren, Yun Xiao, Xiaojun Chang, Po-Yao Huang, Zhihui Li. Brij Gupta, Xiaojiang Chen, and Xin Wang. 2022. A survey of deep active learn- ing. ACM Comput. Surv. (809):180:10 11::140.
Ohad Rubin, Jonathan Herzig, and Jonathan Berant. 2022. Learning retrieve prompts for in-context learning. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Tech- nologies, NAACL 2022, Seattle, WA, United States, July 10-15, 2022, pages Computational Linguistics.
Zhiyong Wu, Yaoxiang Wang, Jiacheng Ye, and I. Ling- peng Kong. 2022. Self-adaptive in-context learning. CoRR, abs/2212.103355.
Jiacheng Ye, Jiahui Gao, Zhiyong Wu, Jiangtao Feng- Tao Yu, and Lingpeng Kong. 2022. Progen: Pro- gressive zero-shot dataset generation via in-context feedback. In Findings of the Association for Com- putational Linguistics: EMNLP 2022, Abu Dhabi, United Arab Emirates, December 7-11, 2022, pages 3671-3683, Association for Computational Linguis- ties.
Association for
Ozan Sener and Silvio Savarese. 2018. Active learning for convolutional neural networks: A core-set ap- proach. In 6th International Conference on Learning

---

Jiacheng Ye. Zhiyong Wu, Jiangtao Feng, Tao Yu, and Lingpeng Kong. 2023. Compositional exemplars for in-context learning. CoRR, abs/2302.05698.
Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona T. Diab, Xian Li, Xi Victoria Lin, Todor Mihaylov, Myle Ou, Sam Shleifer, Kurt Shus- ter, Daniel Simig. Punit Singh Koura, Anjali Srid- har, Tianlu Wang, and Luke Zettlemoyer. 2022a. OPT: open pre-trained transformer language mod- cls. CoRR, fts//2205.0008..
Xiang Zhang, Junbo Jake Zhao, and Yann LeCun. 2015. Character-level convolutional networks for text clas- sification. In Advances in Neural Information Pro- cessing Systems 28: Annual Conference Neural In- formation Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 649-657.
Yiming Zhang. Shi Feng. and Chenhao Tan. 20226. Ac- tive example selection for in-context learning. CoRR, abs/2211 .04486.
Wayne Xin Zhao, Kun Zhou, Junyi Li, Tianyi Tang. Xiaolei Wang. Yupeng Hou, Yingqian Min, Be- ichen Zhang, Junjie Zhang, Zican Dong, Yifan Du, Chen Yang, Yushuo Chen, Zhipeng Chen, Jinhao Jiang, Ruiyang Ren, Yifan Li, Xinyu Tang, Zikang Liu, Peiyu Liu, Jian- Yun Nie, and Ji-Rong Wen. 2023. A survey of large language models. CoRR, 1b//2303.18223.
Zihao Zhao, Eric Wallace, Shi Feng. Dan Klein, and Sameer Singh. 2021. Calibrate before use: Improv- ing few-shot performance of language models. In Proceedings of the 38th International Conference Machine Learning. ICML 2021, 18-24 July 2021, Vir- tual Event, volume 139 of Proceedings of Machine Learning Research, pages 12697-12706. PMLR.

---

A Baselines
Since deep models are usually trained by gradient descent, it tries to find a coreset whose gradients can imitate the entire dataset's s gradients. Mirzasoleiman et al. (2020) propose CRAIG to convert the gradient matching problem to the maxi- mization of monotone submodular function and optimize it greedily. Killamsetty et al. (2021a) pro- pose GradMatch based on CRAIG, which adds a regularization term to discourage assigning large weights to individual examples and improves the used greedy algorithm. Submodularity- Method: Submodular functions (lyer and Bilmes, 2013) naturally measure the subset's ' informative- ness and diversity and thus can be powerful for coreset selection. Tyer and Bilmes (2013) leverage Facility Location and Graph Cut as submodu- lar functions to select the coreset. Bilevel Opti- mization Based Method: It transforms the core- selection problem into a hilivcl-ptimmization problem whose outer and inner objectives are sub- set selection and model parameter optimization, respectively. Glister (Killamsetty et al., 202 leverages validation set on the outer optimization and the log-likelihood in the bilevel optimization. To reduce the gap between these methods and ICL, we use the same LM (GPT2-L) with "last pooling" fine-tuned on the whole dataset for 5 epochs to obtain relevant metries, e.g., gradients or forgetting times for these methods. Following Guo al. (2022), we use the gradients of the final fully-connected layer's parameters as these meth- ods' example feature.
Method:
We mainly compare our proposed methods with fol- lowing baselines: Random: We randomly select examples with random orderings from the train- ing set; Random & Validation: We evaluate mul- tiple sets of random examples on the validation set and select the best one. We consider Random & Validation under two settings whose computa- tional cost is similar to our method: 1. the size of validation set is the same as ours at stage 2 (100) and the number of random example sets is the same our searched and evaluated example permutations (640). 2. the size of validation set is larger, 1000, and the number of random example sets is 100. We also consider a wide range of Core- set Selection methods in traditional gradient-based learning scenarios, according to the methodologies, they can be divided into multiple categories includ- ing: Geometry-Be -ased Method: it assumes that data points that are close in the feature space have similar properties. The Herding method (Chen al.. 2012) adds one data point each time into the coreset to greedily minimize the distance be- tween coreset center and the original dataset cen- ter. The K-Center Greedy method (Sener and Savarese, 2018) selects examples to minimize the largest distance between each example in coreset and its closest example in set of examples that Method:
are not in coreset. Uncertainty-Bawe it assumes examples with higher uncertainty can have a greater impact on the model and should be contained in coreset. Coleman et al. (2020) pro- pose Least Confidence (the max probability over all labels), Entropy and Margin (max probabil- ity margin between different labels) to measure the examples' uncertainty scores and build core- set. CAL (Margatina et al., 2021) selects examples whose predictive likelihood exhibits the greatest divergence from their neighbors to build the core- set. Error/Loss Based Method: It assumes the example that contributes more to the error or loss during training is more important and should be added to coreset. Toneva et al. (2019) propose For- getting to evaluate each example's importance by counting how many times it is forgotten, i.e., it is misclassified after begin correctly classified in prc- vious training epochs. Paul al. (2021) propose the GraNd score to select informative examples. GraNd is the gradient norm expectation of the ex- ample. The larger one example's GraNd is, the more important it is. Gradient Matching Based
B Implementation Details
B.1 Baseline Details
For those previous coreset selection methods, reduce the gap between these methods and ICL, we use the same LM (GPT2-L) with "last pool- ing" fine-tuned on the whole dataset for 5 epochs to obtain relevant metrics, e.g., gradients or for- getting times for these methods. Following Guo et al. (2022), we use the gradients of the final fully- connected layer's parameters these methods' ex- ample feature. For baselines that output weighted subset of examples, e.g., CRAIG or GradMatch, we just adopt its examples for simplicity since there are few methods to weighting in-context examples for ICL.

---

B.2 Method Details
Training Size
Test Size
Label Examples
We find each prompting template's corresponding support examples separately in our method and compared methods, i.e., we select examples for each prompting template separately. For simplicity, we calculate Eq (3) without calibration for experi- ments without or with calibration. For the filtering stage, set the progressive factor and the size of initial score set according to the dataset's size. Specifically, we set the progressive factor to make the filter iterations be
SST-2
6921
873
2
SST-5
8544
2210
10
Amazon
30000
2000
MR
8662
2000
Subj
8000
2000
TREC
5452
AGNews
30000
7601
DBPedia
30000
2000
Table 6: Data statistics.
small set of examples is left, the number of iteration is log..N.. Thus the filtering stage's complexity N is O log, N). In experiments, set No make it linear complexity, where C constant. According to the size of dataset, p is usually set between 2 33, shown in Table 7.
We run all experiments under the label balance setting and the total number of in-context examples for most datasets except DBPedia set 8. The number of some datasets' in-context examples is not 8 but close to 8 because 8 can not be divided by the number of its labels, e.g., 5 for SST-5. Since DBPedia has 14 labels and significantly longer in- put sequence,
Diversity-Guider Example Search At each iter- ation, we have candidate permutations and sepa- rately update them B times. And then we evaluate these updated candidate permutations the small validation set sampled from the remaining train- ing set, whose size is fixed. Since updating the candidate permutations reuses the intermediate re- sults of the filtering stage and does not involve the computation of the LLM (see Eq (4) and (5)), we omit for complexity analysis. So the complexity of diversity-guided example search is consistant, B B.
experiments it under the label-unbalance setting and set the total number of examples to In label balance setting, we filter the same number of examples for each label, 2. initialize the example permutation of stage with balanced labels 3. update ex with new whose label is the same as e".
We list the total number examples in Table And we set the size of initial score set to make the times of LM's forwards to be around 10K. We list the progressive factor and the size of initial score set |So in Table 7. For other hyper-parameters, conduct grid search for the number of retained examples of filtering m, the weight of diversity X, the beam size B and the iteration of diversity- guided search over (500, (0.5,1.2), 14,8,16) and (5, 15,10,15) respectively on the SST-2 dataset. And we set them to be 500, 1, 8 and 10 respectively.
C Prompting Templates
We show the prompting verbalizers and templates in Table 8.
D Dataset Split and Statistics
We use the same dataset split in the previous work (Min al., 2022a). Due to computational resource limitations, for Amazon, AGNews and DBPedia, we conduct experiments on randomly sampled subset of it (30000 and 2000 for the train- ing and test set), and we show the overall dataset statistics in Table
B.3 Experimental Details
In section "The Sensitivity of Support Examples Orders", since the performance is sensitive to the prompting templates, we show the performance distribution under a specific prompting template. other analysis experiments, for simplicity, we report the average performance under four different prompting templates without calibration, unless otherwise specified.
B.3.1 The Complexity of Our Method
Progressive Filtering in the filtering stage, need to compute pairwise Eq for N*l=p/p > times, where is size of training set. Since we filter the dataset into 1/p p of its previous size until a

---

p
|
SST-2
2
14
SST-5
2
11
Amazon
3
MR
2
11
Subj
2
12
TREC
2
20
AGNews
3
4
DBPedia
3
4
Table The progressive factor p and the size of initial score set Sn for each dataset.

---

Task Family: Sentiment Classification
Task: SST-2
Prompting Verbalizer: (great, terrible)
Prompting Templates:
"[INPUT] A [VERBALIZER] one.
"[INPUT] It was [VERBALIZER).
"[INPUT] All [VERBALIZER].
"[INPUT] [VERBALIZER] piece."
Example:
Input:
have to admit that am baffied by jason
It was terrible.
If you answered yes, by all means enjoy the new guy. It was great.
Never comes together coherent whole.
It
Output:
terrible.
Task: SST-5
Prompting Verbalizer: (great, good, okay, bad, terrible)
Prompting Templates: Same as SST-2
Task: Amazon
Prompting Verbalizer: (great, good, okay, bad, terrible)
Prompting Templates: Same as SST-2
Task: MR
Prompting Verbalizer: [great, terrible)
Prompting Templates: Same as SST-2
Task Family: Topic Classification
Task: TREC
Prompting Verbalizer: (Description, Entity, Expression, Human, Location, Number] Prompting Templates:
"[INPUT] Topic: [VERBALIZER)."
"[INPUT] Subject: [VERBALIZER]]
"[INPUT] This about [VERBALIZER).
"[INPUT] about [VERBALIZER] piece."
Example:
Input:
How do storms form ?
Topic: Description.
What city Florida is Sea World in?
Topic: Location.
What university fired Angela Davis?
Topic:
Output:
Human
Task: AGNews

---

Prompting Verbalizer: WWold. Sports, Business, Technology)
Prompting Templates: Same TREC
Task: DBPedia
Prompting Verbalizer: [Company, Educational Institution, Artist, Athlete, Office Holder, Mean of Transportation, Building, Natural Place. Village, Animal, Plant, Album, Film, Written Work)
Prompting Templates: Same as AGNNew
Task Family: Subjective Classification
Task: Subj
Prompting Verbalizer: (subjective, objective) Prompting Templates:
"[INPUT] This is [VERBALIZER]. "
"[INPUT] It's all [VERBALIZER].
"[INPUT] It's [VERBALIZER).
"[INPUT] it [VERBALIZERJ!"
Example:
Input:
There are two distince paths in life good vs. evil. It's subjective. Photographed with melancholy richness and eloquently performed yet also decidedly uncinematic. It's objective.
The film is an homage power, strength and individualism.
It's
Output: subjective
Table 8: The prompting verbalizers and templates for each task.


Reviews:
[{"review_id": "af2cRtQW5n", "reviewer": "Reviewer_NXgr", "summary": "", "questions": "1. Can LENS outperform dynamic selection methods (such as [1])?\n\n2. Can LENS help larger models such as GPT-3?", "limitations": "", "rating": 3, "confidence": 5, "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": "Thank you for your comprehensive review and insightful suggestions. Below is our response to the comments and questions.\n\n**Q1**: Can static example selection outperform dynamic example selection? \n\nWe believe that static and dynamic example selection (or example retrieval) serve complementary rather than mutually exclusive roles. Our static example selection is designed to choose instances that are broadly representative of the task at hand, whereas example retrieval aims to provide example-specific information. We consider the hybrid setting as future work. \n\nAdditionally, static example selection offers greater deployment efficiency and lower latency compared to dynamic example retrieval. As noted on lines 593-595 of our paper, static selection allows for the pre-computation of task-level, in-context example representations that can be reused across various test inputs.\n In contrast, dynamic retrieval methods require an additional retrieval step, often relying on dense encoders, and must compute in-context example representations on-the-fly. Therefore, our static approach demands lower computational costs and offers quicker response times.\n\n\nFrom recent work on  example retrieval, we find our proposed static example selection shows competitive performance with example retrieval methods. Take the recent paper \"Self-adaptive In-context Learning (ACL 2023)\"**[1]** as an example (which dynamically retrieves relevant examples and adjusts their permutation according to the test input), the following is the comparison between our method and theirs:\n\n|               | Language Model | SST-2 | SST-5 | Trec  | AgNews | Avg   |\n|---------------|:----------------:|:-------:|:-------:|:-------:|:--------:|:-------:|\n| Self-Adaptive | GPT2-XL        | 91.5  | 40.3 | 42.5 | 87.9  | 65.6 |\n| Ours          | GPT2-L         | 87.6  | 44.9  | 59.0  | 78.1   | **67.4**  |\n\nWe see our method (on GPT2-L 750M) outperforms Self-Adaptive example selection (On GPT2-XL 1.5B) on average and is comparable with it in general, which is the latest competitive method of dynamic example selection.\n\n**Q2**: 1) Discussion about the emergence of ICL in GPT-2; 2) Except GPT2-L, can the proposed method help larger models?\n\nWe agree with you that it is important to test our method on the models > 10B.  We will add the experiments on large language models like Flan-T5, Text-davinci-003 and GPT-3.5-turbo in the next version. \n\nOur choice of GPT2-L as the inference model aligns with prior studies **[2][3][4]**, which have demonstrated that language models of the GPT-2-L scale have emerged the ability of in-context learning. And our experimental results also show that our selected example significantly outperforms randomly selected examples. \n\nIn section 4.3 \"Transferability across Different LMs\" (line 471), we show that the examples selected by our method on GPT2-L can lead to improvements on GPT2-XL and GPT-Neo-2.7B. These can show the strong transferability of our support examples and the utility of our method when more powerful LMs are proposed.\n\n\n\n**[1]** Self-adaptive In-context Learning\n\n**[2]** MetaICL: Learning to Learn In Context\n\n**[3]** Noisy Channel Language Model Prompting for Few-Shot Text Classification\n\n**[4]** Rethinking the Role of Demonstrations: What Makes In-Context Learning Work?\n\nThank you again for your valuable review. If we have misunderstood any aspect of your review, or if you have additional questions, please let us know.", "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. Novel Approach: This work provides a novel approach (LENS) towards improving the performance of in-context learning.\n(LENS) approach to tackle the challenge of finding support examples in two stages, by filtering the dataset and then using diversity-guided example search.\n\n2. Extensive experimental results: The paper provides a comprehensive set of experimental results showing that LENS significantly outperforms a wide range of baselines, demonstrating the effectiveness of the proposed method.", "reasons_to_reject": "The main limitation of this work lies in the nature of static example selection, as it can hugely limit the upper-bound performance of this method.\n\nFor selecting better in-context examples, one standard method is to dynamically select similar examples for different test cases [1].\nSuch a dynamic selection can make better use of the large-scale example bank.\nIn this work, the proposed LENS just chooses one set of prompting examples for each task.\nIt might not be reasonable that all cases in one task consistently prefer the same examples, especially for more complex tasks (such as reasoning tasks) in which the cases have significant diversity.\n\nMoreover, the in-context learning is the emergent capability on models with >10B size.\nHowever, this work mainly experiments with relatively small models, which limit the experimental contribution of this work.\n\n[1] J. Liu, D. Shen, Y. Zhang, B. Dolan, L. Carin, and W. Chen. What makes good in-context examples for GPT-3?", "questions_to_authors": "1. Can LENS outperform dynamic selection methods (such as [1])?\n\n2. Can LENS help larger models such as GPT-3?", "paper_topic_and_main_contributions": "This work tried to address the challenge of selecting support examples that can improve the performance of in-context learning. In-context learning is a new paradigm where a language model observes a few examples and directly predicts the test input, but it is sensitive to the provided examples. The authors propose a two-stage method, LENS (fiLter-thEN-Search), to tackle this challenge. First, the dataset is filtered to obtain informative in-context examples individually using a novel metric called InfoScore. Then, a diversity-guided example search is used to iteratively refine and evaluate selected example permutations. Experimental results show that LENS significantly outperforms various baselines, with further analyses highlighting the importance of each component in the method and providing insights into the principles of support examples and in-context learning.", "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": "TqRKHzANcR", "reviewer": "Reviewer_wMx9", "summary": "", "questions": "A: All experiments are conducted on the fixed shot. The number of shots indeed has a significant impact on ICL performance, and there are several methods that perform well only on certain shots. Would LENS also face such issues? Testing under different shots would provide more convincing results.\n\nB: What is the label distribution of support in-context examples? Balance or not balance?\n\nC: Figure 3 shows the results under gold and random labels. This experiment is motivated by Min et.al (2022b). Actually, Yoo et.al (2022) (Ground-Truth Labels Matter: A Deeper Look into Input-Label Demonstrations, EMNLP2022) shows that golden labels matter in some tasks. Are the test tasks in Figure 3 originally sensitive to the golden labels? Maybe comparison with other examples could answer this question.\n\nD: In Section 3.1, this paper test InfoScore on the score set. What the impact of this score set? Intuitively, the similarity between the score set and the test set is crucial, higher similarity could lead to higher test performance. Do the actual results perform so? This paper randomly sample score set (Line 2 in Algorithm 1), what is the standard deviation?\n", "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": "Thank you for your comprehensive review and insightful suggestions. Below is our response to the comments and questions.\n\n**Q1**: Experiments on LLaMA models\n\nWe agree with you that it is important to verify the method on the latest strong language models and we will add the corresponding experiments (LLaMA2, LLaMA2-chat) in the next version.\n\n**Q2**: About the name of the proposed method\n\nThank you for your detailed opinions on our method name. We will consider renaming in the next version.\n\n**Q3**: More analyses of the selected examples\n\nWe conduct analytic experiments on the sensitivity of support examples to orders, transferability of support examples across different LMs, the effect of ground truth to support examples, hyper-parameter sensitivities and the ablation study about the proposed components. We plan to extend these analyses to cover word distribution and the gradients of support examples in the next version.\n\n**Q4**: The performance of our method under different demonstration quantities\n\nIn the primary experiments, we have standardized the demonstration quantity to ensure consistent inference costs across all evaluated methods. Here are our method's results (without calibration) on three datasets, SST-2, Subj, and Amazon, using varying numbers of demonstrations:\n\n**SST-2**\n\nDemonstration Quantity (per Label) | 1    | 2    | 3    | 4    |\n|----------------------------------------|------|------|------|------|\nAccuracy                               | 85.2 | 86.9 | 86.1 | 86.3 |\n\n**Subj**\n\nDemonstration Quantity (per Label) | 1    | 2    | 3    | 4    |\n|----------------------------------------|------|------|------|------|\nAccuracy                               | 82.0 | 85.9 | 86.2 | 86.4 |\n\n**Amazon**\nDemonstration Quantity (per Label) | 1    | 2    | 3    | 4    |\n|----------------------------------------|------|------|------|------|\nAccuracy                               | 78.1 | 78.7 | 79.3 | 80.2 |\n\nWe see that our method's performance degrades slightly with fewer demonstrations, which shows the stability of our method across different demonstration quantities and superior performance over baseline methods.\n\n\n\n\n\n\n**Q5**: Are support examples label-balanced?\n\nAs mentioned in the section of Implementation details (Appendix B.2), we keep using the label balance setting in all the experiments except DBPedia (The number of some datasets’ in-context examples is not 8 but close to 8 because 8 can not be divided by the number of its labels, e.g., 5 for SST-5. Since DBPedia has 14 labels and significantly longer input sequence, we run experiments on it under the label-unbalance setting and set the total number 1096 of examples to 4.). \n\nOur preliminary investigations reveal two main findings: 1) For datasets with imbalanced labels, like TREC, a balanced selection of examples significantly boosts performance. 2) For relatively label-balanced datasets, the performance remains stable irrespective of label balance. We will add these results in the next version and further analyze the effect of balanced labels.\n\n**Q6**: The comparison in Figure 3 (Ground Truth Matters for Support Examples). Are the test tasks in Figure 3 originally sensitive to the golden labels?\n\nWe agree with you that it is important to compare with the original results and we have the comparison between support examples and randomly selected examples in Figure 3. Compared with random examples, we observe a significantly different trend in support examples. Specifically, after removing GT labels, support examples’ performance significantly degrades, while the performance of random examples remains similar to their original points. We will make the presentation more clear in the next version.\n\n**Q7**: 1. Does the score set influence the final performance? (Does the score set that is similar to the test set lead to better performance?) 2. The random variance of our method\n\n1. Yes, but we cannot get access to information of the test set before the test stage. So we cannot improve the performance according to this.\n\n2. As mentioned in line 407~409, we run our experiments under 4 prompt templates over 10 random seeds (40 in total) and report the average performance with and without calibration (Zhao et al., 2021). For all datasets, the performance of our method fluctuates within three points under the same prompt template, which is significantly more stable than the randomly selected examples and baselines. We will add the detailed standard deviation in the next version.\n\n\nThank you again for your valuable review. If we have misunderstood any aspect of your review, or if you have additional questions, please let us know.", "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": "- Finding in-context examples that could well characterize the task is an important topic and would benefit the future research. And this paper focus on this topic.\n- The paper is well-organized. The proposed two-stage method LENS is described clearly. In the first stage, the defined InfoScore evaluates the informativeness of an example and could help filter the original dataset to obtain informative in-context examples. The second stage further introduces diversity into the selected informative examples, which is also well-motivated. The experiments also show the effectiveness of LENS.\n- The further analyses show the extra characteristic of support in-context examples: less sensitivity to order, ground truth labels matter, and good transferability across LMs.\n", "reasons_to_reject": "- The experiments are all conducted on GPT2-L, which is not enough. More experiments on other LMs are required. Although the authors claims that this is because of the computation resources limitation. Actually, all experiments in this paper only require inference, other small LMs such as GPT2-xl, which could be inferenced on a single 2080Ti/3090Ti. In summary, experiments only on GPT2-L lack persuasiveness, more experiments on other LMs (at least extra one) would improve this paper.\n- The “support in-context examples” seems to be misleading, especially the “support”. The similar idea has been widely studied in interpretability, especially the instance-based explanations ([1][2]). More recently, similar topic is also studied in prompt learning [3] and in-context learning [4]. The coreset selection methods also make connections between training examples and test set and this paper mainly compare with these methods. Actually, this paper mainly focuses on select examples which could characterize the task. In essence, this paper focuses on select examples which could stand for the training set. The only aspect that demonstrates supportiveness is the InfoScore. Therefore, the “support” may be not confusing and not accurate.\n- Although this paper provides some analyses on support in-context examples, it is not enough. It would be more meaningful to examine the characteristics of these in-context examples, such as label distribution, word distribution [4], and so on. These factors can greatly assist in better understanding the in-context learning.\n", "questions_to_authors": "A: All experiments are conducted on the fixed shot. The number of shots indeed has a significant impact on ICL performance, and there are several methods that perform well only on certain shots. Would LENS also face such issues? Testing under different shots would provide more convincing results.\n\nB: What is the label distribution of support in-context examples? Balance or not balance?\n\nC: Figure 3 shows the results under gold and random labels. This experiment is motivated by Min et.al (2022b). Actually, Yoo et.al (2022) (Ground-Truth Labels Matter: A Deeper Look into Input-Label Demonstrations, EMNLP2022) shows that golden labels matter in some tasks. Are the test tasks in Figure 3 originally sensitive to the golden labels? Maybe comparison with other examples could answer this question.\n\nD: In Section 3.1, this paper test InfoScore on the score set. What the impact of this score set? Intuitively, the similarity between the score set and the test set is crucial, higher similarity could lead to higher test performance. Do the actual results perform so? This paper randomly sample score set (Line 2 in Algorithm 1), what is the standard deviation?\n", "paper_topic_and_main_contributions": "This paper proposes a new topic that finding support examples for in-context learning, which could well characterize the task for in-context learning. To select such support examples, this paper proposes a two-stage fiLter-thEN-Search (LENS) method. In the first stage, this paper proposes InfoScore metric, which could help filter the dataset to obtain informative in-context examples. In the second stage, this paper proposes a diversity-guided search method that iteratively refines and selected examples to find support examples. Extensive experiments show that LENS achieve better performance that traditional coreset selection methods.", "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": {"Missing_References": "[1] Understanding Black-box Predictions via Influence Functions, ICML 2017\n\n[2] Estimating Training Data Influence by Tracing Gradient Descent, NIPS 2020\n\n[3] Tracing Knowledge in Language Models Back to the Training Data, Findings of EMNLP2022 \n\n[4] Understanding In-Context Learning via Supportive Pretraining Data, ACL2023\n"}}, {"review_id": "XP09po89gL", "reviewer": "Reviewer_Hn2j", "summary": "", "questions": "A. In algorithm 1, you define 'l'. Which 'l' did you use in the experiments?\nB. Algorithm 1, line 11, did you mean the top |D'|/ρ samples? The current line leads to selecting the top ~1/N^0.5 samples which doesn't make sense.", "limitations": "", "rating": 4, "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": "Thank you for your comprehensive review and insightful suggestions. Below is our response to the comments and questions.\n\n**Q1**: Will we add baselines and experiments on newer language models?\n\nYes, we will add the state-of-the-art related work as baselines and add the experiments on the latest language model (LLaMA2, LLaMA2-chat) in the next version.\n\n**Q2**: The runtime comparison.\n\nThe runtime of our method is comparable with baselines. Our proposed method only depends on the inference of the language model. But baselines depend on finetuning the language model, which requires more strong computational resources and more time. We will add the detailed runtime report in the next version. Meanwhile, the examples selected by our method lead to significant improvements over baselines.\n\n**Q3**: Question for symbols in Algorithm 1:\n\nAbout the \"l\":\n\nWe list the value of \"l\" for each dataset in Appendix B.2 (Table 7).  We will adjust the position of Table 7 and improve the layout to make it more clear.\n\nThe line 11 in Algorithm 1:\nYes, we meant the top |D'|/ρ samples. We will fix the presentation in the next version.\n\n**Q4**: typos and presentation improvements\n\n1) The position of the section \"Related Work\"\n\nThank you for your detailed review and pointing out these issues. We will move the section of related work to the beginning (after introduction).\n\n2) The typo in Table 4:\n\nThe entry 'm=500' in Table 4 is a mistake, which should be \"m=100\", we will fix it in the next version.\n\n**Q5**: Missing References\n\nWe will include citations for the papers you have suggested in the next version.\n\nThank you again for your valuable review. If we have misunderstood any aspect of your review, or if you have additional questions, please let us know.", "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. Simple yet effective solution which outperforms the other task-specific baselines in the paper - the task-specific setup will fit an online system with very low latency inference (to avoid heavy computation for inference sample oriented solutions). Moreover, the linear algorithm to calculate the InfoScore can be beneficial to focusing on informative samples.\n2. Extensive experimental study showing state of the art results in addition to ablation test showing less sensitive to sample order\n3. Paper is easy to follow", "reasons_to_reject": "1. The baselines are classical while there is missing state-of-the-art related work[1,2,3] published last year which can act as better baselines\n2. Unclear how well it generalizes to IFT models - the solution uses GPT2 LMs. However, more advanced solutions such as Instruction Fine-Tuned (IFT) like Flan-T5 are not being evaluated. Thus, it is unclear how well this solution keeps up with the existing IFT solutions.\n3. Missing runtime comparison - the solution seems to be more exhaustive than other baselines. The runtime cost of the algorithm was not reported as part of the paper.\n\n[1] GPS: Genetic Prompt Search for Efficient Few-shot Learning, Shao et al, EMNLP'22 - for constructing task specific prompts\n[2] Fantastically Ordered Prompts and Where to Find Them: Overcoming Few-Shot Prompt Order Sensitivity, Lu et al, ACL'22 - ordering of samples\n[3] Reordering Examples Helps during Priming-based Few-Shot Learning, Kumar et al, ACL findings'21", "questions_to_authors": "A. In algorithm 1, you define 'l'. Which 'l' did you use in the experiments?\nB. Algorithm 1, line 11, did you mean the top |D'|/ρ samples? The current line leads to selecting the top ~1/N^0.5 samples which doesn't make sense.", "paper_topic_and_main_contributions": "The paper addresses the problem of selecting the best prompt for in-context learning with a large labeled dataset. In this paper, they focus on finding the best task specific prompt, independent of the inference sample, without having access to the gradients. The solution is based on a filter-then-search pipeline, which first extracts the most \"informative\" samples from the training set. Then, it reorders the top informative samples to construct the prompt. The paper provides an extensive experimental study on 8 datasets on more classical approaches showing state-of-the-art results on task specific prompt selection. In addition, the paper shows that the selected examples are more robust to ordering and changing the model than the random approach.", "excitement": 4, "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": {"Missing_References": "[1] GPS: Genetic Prompt Search for Efficient Few-shot Learning, Shao et al, EMNLP'22 - for constructing task specific prompts\n[2] Fantastically Ordered Prompts and Where to Find Them: Overcoming Few-Shot Prompt Order Sensitivity, Lu et al, ACL'22 - ordering of samples\n[3] Reordering Examples Helps during Priming-based Few-Shot Learning, Kumar et al, ACL findings'21\n", "Typos_Grammar_Style_and_Presentation_Improvements": "- The related work should be moved to the beginning. In the current format it was hard to follow on the positioning compared to other related work which only made clearer after reading the RW section.\n- In line 533 you mention m=100 and refer to table 4, which doesn't include the m=100 setting.\n\n"}}]

Author rebuttal:

Meta-review: The authors propose a method, LENS (fiLter-thEN-Search), for selecting and ordering 'support' examples used as part of an in-context learning (ICL) prompt in LLMs in an effort to maximize performance. Specifically, LENS, first filters the dataset to obtain informative in-context examples using a newly developed InfoScore metric followed by a diversity-guided example search is used to iteratively refine selected 'support' example permutations. Experimental results on eight widely used text classification datasets show that LENS significantly outperforms several ICL example selection baselines, with additional experiments addressing questions regarding sensitivity to example ordering, selection generalization across LLMs, the value of ground truth quality in support examples, and algorithm hyperparameter sensitivity.

== Quality == 
Overall, the reviewers believe that this submission is of solid quality. Specifically, the method is conceptually well motivated and there are extensive experimental results in terms of baseline methods and additional experiments to better understand the dynamics of the proposed method. However, there were some recommendations regarding stronger experiments including larger foundational models (including instruction-tuned) additional recent applicable baseline methods, and tasks beyond text classification. Overall, the experiments support the stated premises and result in interesting findings to motivate further work.

== Clarity == Overall, the paper is well-organized and easy to understand with the appendices adding clarity. All of the reviewers were confident that they would be able to reproduce the empirical results and though the evidence as presented was convincing. The only conceptual clarification was the use of the term "support examples" (which are specific to learning discriminative functions) vs. "core set" (which align more closely with representing example distributions) -- a technical distinction, but worth considering the precision of the methodological claims. Also, while not a concern of the reviewers, discussion of theoretical implications and contextualization of the algorithmic approximations would increase overall understanding.

== Originality == While there has been work in selecting examples for ICL, the reviewers believed the specific approach to be novel and pragmatic (especially when considering algorithmic simplifications). This is a new area and there is the right balance of good conceptual motivation and heuristics to create a feasible implementation.

== Significance == As stated above, this is a increasingly widely-studied area (example selection in ICL) where small improvements can have large impact. Thus, there is definitely potential for impact, minimally as a baseline for future work. That being said, there were several concerns that the reviewers thought may hinder wide adoption including only using GPT-2 scale models (thus, without instruction-tuning and knowing that these results scale to SotA settings), only performing static selection (which is a natural area for future research with a multi-stage method), and questions regarding computational resources needed to perform this in practice. Thus, while the reviewers concur that the method is likely useful, it isn't clear what the impact will be with stronger LLMs (and if this ends up being a negative result, the impact will clearly be limited).
Decision: Accept-Findings