Prompt Optimization with EASE? Efficient Ordering-aware Automated Selection of Exemplars
Authors: Zhaoxuan Wu
Xiaoqiang Lin
Zhongxiang Dai
Wenyang Hu
Yao Shu
See-Kiong Ng
Patrick Jaillet
Bryan Kian Hsiang Low
Venue: NeurIPS 2024 poster (2024)
Keywords: Exemplar selection
Prompt optimization
In-context learning
LLMs
Data selection
Primary area: natural_language_processing
TL;DR: We propose an efficient automated exemplar selection method that uses a neural bandit algorithm to optimize the set of exemplars for in-context learning while accounting for exemplar ordering.

Abstract: Large language models (LLMs) have shown impressive capabilities in real-world applications. The capability of *in-context learning* (ICL) allows us to adapt an LLM to downstream tasks by including input-label exemplars in the prompt without model fine-tuning. However, the quality of these exemplars in the prompt greatly impacts performance, highlighting the need for an effective automated exemplar selection method. Recent studies have explored retrieval-based approaches to select exemplars tailored to individual test queries, which can be undesirable due to extra test-time computation and an increased risk of data exposure. Moreover, existing methods fail to adequately account for the impact of exemplar ordering on the performance. On the other hand, the impact of the *instruction*, another essential component in the prompt given to the LLM, is often overlooked in existing exemplar selection methods. To address these challenges, we propose a novel method named $\texttt{EASE}$, which leverages the hidden embedding from a pre-trained language model to represent ordered sets of exemplars and uses a neural bandit algorithm to optimize the sets of exemplars *while accounting for exemplar ordering*. Our  $\texttt{EASE}$ can efficiently find an ordered set of exemplars that *performs well for all test queries* from a given task, thereby eliminating test-time computation. Importantly,  $\texttt{EASE}$ can be readily extended to *jointly optimize both the exemplars and the instruction*. Through extensive empirical evaluations (including novel tasks), we demonstrate the superiority of  $\texttt{EASE}$ over existing methods, and reveal practical insights about the impact of exemplar selection on ICL, which may be of independent interest. Our code is available at https://github.com/ZhaoxuanWu/EASE-Prompt-Optimization.

Prompt Optimization with EASE? Efficient Ordering-aware Automated Selection of Exemplars
Zhaoxuan Wu Xiaoqiang Lin#", Zhongxiang Dais, Wenyang Hu Yao Shu See-Kiong Ngšt, Patrick Jaillet', Bryan Kian Hsiang Low Institute of Data Science, National University of Singapore, Republic of Singapore Singapore-MIT Alliance for Research and Technology, Republic of Singapore Dept. of Computer Science, National University of Singapore, Republic of Singapore! School of Data Science, The Chinese University of Hong Kong, Shenzhen
LIDS and EECS, Massachusetts Institute of Technology, USA
Guangdong Lab of AI and Digital Economy (SZ)ll
{wu. zhaoxuan, xiaoqiang lin, wenyang hu mus m daizhongxianggcuuhe edu. cnS, seekiongênus edu. sg lowkh@comp. mus mus. edu.sg",
jaille jaillet@mit. edu',, shuyao@gml.an acc.gmml........ cn
Abstract
Large language models (LLMs) have shown impressive capabilities in real-world applications. The capability of in-context learning (ICI.) allows to adapt an LLM to downstream tasks by including input-label exemplars in the prompt without model fine-tuning. However, the quality of these exemplars in the prompt greatly impacts performance, highlighting the need for an effective automated exemplar selection method. Recent studies have explored retrieval-based approaches select exemplars tailored to individual test queries, which can be undesirable due extra test-time computation and an increased risk of data exposure. Moreover, existing methods fail to adequately account for the impact of exemplar ordering on the performance. On the other hand, the impact of the instruction, another essential component in the prompt given to the L.M,, is often overlooked in existing exemplar selection methods. To address these challenges, we propose a novel method named EASE, which leverages the hidden embedding from pre- trained language model to represent ordered sets of exemplars and uses a neural bandit algorithm to optimize the sets of exemplars while accounting for exemplar ordering. Our EASE can efficiently find an ordered set exemplars that performs well all test queries from given task, thereby eliminating test-time computation. Importantly, EASE can be readily extended to jointly optimize both the exemplars and the instruction. Through extensive empirical evaluations (including novel tasks), we demonstrate the superiority of EASE over existing methods, and reveal practical insights about the impact of exemplar selection ICL performance, which may be of independent interest. Our code available at htttps://gitti com/ http///aaxxxuu////aaaaaa EASEE Preset-rrmpt--oe Ppromptttptimmzzaiion
Introduction
Large language models (LLMs) have recently drawn significant attention and have been widely
deployed in various real-world scenarios 226 28 51 due to their strong capabilities. Of note, particularly impressive capability of LLMs is in-context learning (ICL): LLMs can learn from
Equal contribution. Correspondence to: Zhongxiang Dai claizhonggiang@@ehkk.ccccco
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

handful of input-label demonstrations (i.e., data exemplars) included in its prompt to perform a ICL allows us to adapt an LLM a downstream task without fine-tuning
downstream task [ 23
However, the ICL performance is heavily dependent on the data Therefore, to maximize the ICI. performance, it of paramount importance to carefully select the set of exemplars [6]. Unfortunately, exemplar selection for ICL is challenging because the mechanism of ICL is complicated and unknown, and this difficulty is further aggravated for black-box LLMs to which we only have API access (e.g., GPT-4 (32), Gemini
the model parameters 20
29
exemplars in the prompt
23 38
Ultra
A large number of existing works on exemplar selection for ICL have considered sirievall-bsed methods [ 23 [8). Specifically, they aim to develop a retriever model such that for every test query, the retriever model retrieves the corresponding best set of exemplars tailored to this particular query 48]. Such approaches require test-time retrieval for every query which might hinder their ease of adoption 22 while test-time computation is not needed for our method. Moreover, another drawback of these retrieval- based methods is that they may lead to increased privacy risks. Compared to using a fixed set of exemplars for all test queries submitted to the LLM provider (e.g.. via an API), using a different set of exemplars for every test query may lead to greater data exposure, i.e., more data exemplars being exposed to the LLM provider. Privacy issues have become increasingly prominent in discussions surrounding LLMs 30]. with evidence of user data being output by these models [45). Therefore, retrieval -assdd methods are undesirable in scenarios where such privacy concerns are important considerations. Given these two important shortcomings of retrieval- based methods, it is imperative to develop exemplar selection methods that generalize to test queries and are capable of choosing a fixed set of exemplars that perform well for all test queries for a task.
Another major limitation of existing exemplar selection methods (including retrieval -bssed and other methods) is their inability to account for the impact of the ordering of the exemplars within subset [24 33 52). Specifically, to select a subset of k exemplars, previous works have either relied on simple heuristics (e.g., selecting the top-k exemplars based on the score from a retriever (25) or used subset selection techniques which are able to account for the inter-relationships among the exemplars within a subset [4. 14 18
19 48). Due to the computational complexity caused by the combinatorial search space, these works based subset selection have often employed an iterative greedy strategy to sequentially select the subset of exemplars. It is also non-trivial to extend these existing works to consider exemplar ordering. However, it has been repeatedly verified that the ordering of the exemplars has a significant impact on the performance of ICL [24 33 52).
To the best of our knowledge, the impact of the exemplar ordering during the selection process remains inadequately addressed by these previous works that relied on simple heuristics (e.g., random ordering) and approximations (e.g., greedy strategy).
In addition, when optimizing the set of exemplars to improve the performance of the LLM, existing methods have often ignored the impact of the instruction, which is another essential component in the prompt given to the LLM (21). Specifically, previous works on exemplar selection often use a fixed pre-determined instruction or do not include any instruction at all in the prompt 4
19
23 38)
Meanwhile, existing works on instruction optimization for LLMs typically include a fixed manually selected set of exemplars in the prompt
10 16,
47 or simply adopt the zero-shot setting (i.e.,
without using any exemplar) [S) [3]. However, these two lines of work have separately demonstrated that both the exemplars and the instruction have significant impacts on the performance of the LLM. Therefore, the existing works that optimize these two components separately are unable to account for their interactions, which may be crucial for further boosting the performance of LLMs. This leaves considerable untapped potential in enhancing the performance of the LLM through ICL, which can be achieved by jointly optimizing the instruction and the exemplars.
In this work, we propose a novel exemplar selection algorithm that addresses the above-mentioned challenges faced by existing works (with detailed discussions of related work in App. 5) We formulate exemplar selection as a black-box optimization problem, in which every input in the domain corresponds to sequence of l exemplars and its corresponding output represents the ICL performance achieved by including this sequence in the prompt for the LLM. Given this formulation, for every sequence of At exemplars in the domain, we adopt the embedding from a powerful pre- trained language model as its continuous representation, and train a neural network (NN) to predict its ICL performance. Based on the trained NN, we use a neural bandit algorithm to find the optimal exemplar sequence in a query-efficiiet manner. Our Efficient ordering-aware Automated Selection of Exemplars (EASE) algorithm offers several significant benefits:
2

---

Our EASE can find an efficacious sequence of k exemplars (which performs well for all test queries from a task) in a query-efficiens manner (i.e., it only needs test a small number of exemplar sequences). This can mainly be attributed to our algorithmic design, which allows us to use neural bandits to balance the exploration of the space of exemplar sequences and the exploitation of the predicted performance from the NN in a principled way. Importantly, in contrast to retrieval-based methods, our EASE requires no test-time computation to select test query-specific exemplars.
Our EASE naturally takes into account the ordering of the exemplars when maximizing the ICL performance. This is because, for the same subset of exemplars, a different ordering leads to different pre-trained embedding. which allows the trained NN (that takes the embedding as input) to predict the performances of different orderings of these exemplars. We have made our EASE computationally feasible for large search spaces of exemplar sequences using a technique based on optimal transport (OT), which reduces the computational cost of EASE while preserving its strong performance by imposing an implicit preference towards exemplars that are more relevant to the task (Sec. (.2))
Our EASE is readily extended to jointly optimize the exemplars and instruction in the prompt. This is achieved by augmenting the domain of exemplar sequences with the instruction (Sec. 3.3
These advantages of our EASE algorithm allow it to significantly boost the performance of ICI. To empirically validate this, we compare our EASE algorithm with comprehensive suite of baselines in variety of tasks. To begin with, we show that our EASE consistently outperforms previous baselines in large number of benchmark tasks (Sec. (Sec.4..I) Next, by using our EASE algorithm in a novel experiment, we unveil an interesting insight about ICL: The selection of exemplars is more important when the LLM has less knowledge about the task (Sec. 4.2). Based on this insight, we design set of novel experiments in which the selection of exemplars has an important impact on the ICL performance, and use these experiments to further demonstrate the superiority of our EASE (Sec. 4.3 Furthermore, we showcase the ability of our EASE to jointly optimize the exemplars and the instruction to enhance extension of
the performance of the LLM even further (See. 4.4). We also included a retrieval- EASE to deal with large exemplar set sizes (Sec. 44.5). Of note, our novel experimental designs, as well as the insights from them, may be of independent interest for future works on ICI. and beyond.
2 Problem setting
We are given a set of data exemplars D = fe; = (x;; v:)): of size where I; and yi correspond to the input and output text, respectively. The data exemplars describe a downstream task, and we aim to select is of them to form the optimal in-context exemplars sequence E for accurate output generation when prompting a black-box LLM f()). Due to the sequential nature of the natural language input, the exemplar sequence is ordered such that E = (e1, (e1,0,,-.. ,ex) where e, denotes the i-th exemplar chosen. For every input v, we prepend with sequence of exemplars E to generate a response ò from the black-box LLM (e.g., through calling the API), following
Ú [(ei, e2, ,.,, a!) f((E,x))
contexl
Here, the number of exemplar & in the context can be determined by the future budget of inference in practice. A larger & corresponds to a longer sequence of context tokens to be prepended to the test input æ during inference, which leads to higher query costs (e.g., associated with the API calls). Alternatively, it is common to decide & depending on the context window size of the target LLM f()).
Since the model architecture and the internal working of the black- box LLM f(-) is unattainable, we formulate the exemplar selection as a black-box optimization problem over the space of permutations Ω A F:: | k) of size n (i.e., having n choices for each of the l positions the sequence),
max F(E) _ E(,.g)ED (E, Eeft
where s(..-) is score function for the output against the ground truth, Dy is the held-out validation set and [E] = i denotes that the number of exemplars E is k. Therefore, the exemplar sequence E found represents a fixed ordered set of exemplars that apply to every data point in the validation set. Note that our formulation considers exemplars jointly as ordered text the sequence E. This space of permutation Ω is also a lot larger than the (unordered) combinatorial search space considered We show the superior performance of our method against subset selection methods in our experiments (Sec. 4..
in the subset selection formulation of exemplar selections in 4 14
19 48
3

---

3 Automated selection of exemplars
3.1 NeuralUCB for query-efficient optimization of exemplar sequences
We propose to use neural bandits to iteratively maximize the black-box objective function (T) At each iteration i, the neural bandits algorithm selects the next input query based the belief of the objective given all past ( observations 0,-1 _ {(E,, sy sy(E) } where E, and sv sv (E;) are the exemplar sequence and corresponding validation score at iteration i, respectively. Here, the validation score is realization of the objective function so sv (E) = Dv E(..)) s (([(E, (E,*), x), y).
Inspired by Lin et al. [21] who have shown impressive performances of the neural upper confidence bound (NeuralUCB) acquisition function [53] on instruction optimization, we adopt the NeuralUCB approach to novel black-box exemplar selection formulation in (Ip. We propose to neural network (NN) to directly learn the mapping from a general-pure purposs hidden embedding of input exemplar sequences to the validation score. Specifically, we propose to use embedding model h(-) and train a network mmh( E); 0z) at iteration such that
0,- = arg ming (E,,vv E (mn(h(E); 0), sv (V))
where é the mean squared error (MSE) loss function. The embedding model can be pre-trained on a large corpus of text and hence provides powerful latent representation of the input sentence. For example, pre-trained centence-transfommer models like MPNet [40] and black-box APIs like OpenAl text embedding are both commonly used for downstream clustering, semantic search and classification. Importantly, even for the same subset of exemplars, a different ordering leads to different embedding, hence h(E) captures both the content and the ordering of the exemplars in E.
Then, the trained NN can be used iteratively select the next exemplar sequence E, query:
F2 arg max gen Ben NeuralUCB.
(F) _ mmh(m)))))) (F); 0,) + ()o)=1(((F))))))
where m(h(E);; 0,) is the predicted score, a (k(E); 0.) is the NN's uncertainty about the score of h(E) and 1/2 is a hyperparameter that balances the two terms. Using NeuralUCB, our EASE balances the exploration of the space of exemplar sequences E and the exploitation of the predicted score from the NN in principled way.
This application of NeuralUCB in our work differs from that of Lin al. 21 in three main aspects. Firstly, the input to our NN is the embedding of exemplar sequences rather than the latent representation of the instructions from 21]] Secondly, we relax the requirement of separate white-box LLM from (21] and only need black-box access to the embedding model h(-). Thirdly, our application to exemplar selection dramatically increases the search space from finite candidate instructions 21 to the space of exemplar sequences. Particularly, the explosion of the size of the search space poses significant difficulties to optimization, which we will address in the next section.
3.2 Reducing computational cost through optimal transport (OT)
Directly applying NeuralUCB to exemplar selection is challenging due to the enormous search space of all permutations of exemplars on which the acquisition values (3) have to be evaluated. For example, selecting 5 exemplars out of 100 requires 100" evaluations which is far from being practical. is natural to search over a domain space Q = {EG.0)y_ with a smaller number q of exemplar sequences in each iteration t. However. uniformly sampling such a reduced space Qe from Ω could be sub-optimal, because small q. which is required to make our algorithm computationally feasible, highly likely to discard important exemplar sequences (we verify this in ablation experiments in S.c. and App. C33). To this end, we make large q feasible by introducing a novel technique
Sec. 4.5 based on optimal transport (OT) to further select from Q, a subset Q/ of q' < relevant exemplar sequences. This technique can simultancously (a) reduce the computational cost (since g' << {2) and (b) preserve our performance (since we can now search over a large domain space Qt) by imposing an implicit preference towards exemplars in Q2 that are more relevant to the task.
Given probability measures pa and Hy over space Z. the OT distance between μt and μy is defined as
min J c(z, 2'
OT(Ms
xell(pe
4

---

where I[(,e = f E P(Z x 2)1 T(2, Ms. 12 (22, 2')22'= = myy J is a collection of couplings between two the distributions its and Me, and c 2 x 2 + R is some symmetric positive
cost function. In our problem, we propose to use the space of embedding from i(-) as 2 because the embedding captures the semantics of the exemplars with similarity is usually used to train embedding models such as MPNet [40] and sentence-BERT (36), 1 sémtoos (h(e), h(ee)) where
exed-dimensiones vector. As cosine
we propose to use the following cost function ((((e)))(ee)) sime (h(e), h((e)) measures the cosine similarity between the embedding of two exemplars e and
e'. Given a sampled subset S = {e we define a discrete measure μ., = E 8(h(e;) where 8 is the Dirac function. Likewise, we define jr for the validation set Dv
Intuitively, a smaller value of (4) indicates that the subset of exemplars is more similar to the validation set and is hence more relevant the task. This allows sequences from Q, to form the smaller subset Qú, on which the acquisition values (3) are evaluated. Consequently, we can increase the size q of Q, by hundreds of folds while being computationally feasible since the most expensive computation (i.e.. computing embeddings for all exemplar sequences in Q+) is not needed. Note that the extra computation incurred by OT is minimal since the embedding of every data exemplar in D and Dy can be pre-computed and reused. Therefore, OT helps us examine a large number of permutations among the space of all permutations without significantly increasing the computation, which helps mitigate the problem of the exploding search space.
select the relevant exemplar
3.3 Natural extension to jointly optimize instructions and exemplars
Our algorithm can further boost the performance of ICL for LLMs by jointly optimizing the exemplars and the instruction. A natural extension of our formulation in Sec. Bellows the instruction, being another essential component of the LLM prompt, to be simultaneously optimized with exemplars. This ensures the optimal matching between instructions and exemplars to achieve fully automated pipeline with superior performance. Specifically, our formulation naturally extends to E (p, 61, e ex) where p E P is an instruction from candidate space/set P, i.e., Q < P x Q¹-- Subsequently, p can be intuitively treated as another type of "exemplar" from a new space P and optimized in conjunction with the exemplars. In practice, the fixed set P of candidate instructions can be generated by the black-box model through techniques such as APE (54), Promp(Breeder [10], etc. This extension is not only simple in its implementation but also proven to be effective in our experiments in Sec. 4.4
3.4 Our EASE algorithm
In iteration of EASE, we first use the historical observations of the exemplar sequence and score pairs {(Fg, sv (v.(svvF))) [= to train the score prediction NN. Then, we perform sampling to obtain the domain space Q., which will be further refined to a set Q' of top-q' candidates based on OT distances. The space of exemplar sequence can be optionally augmented with instructions p E P from a set P of instruction candidates. Subsequently, we find the optimal E that maximizes the NeuralUCB acquisition function. The selected exemplar sequence E is then evaluated against the black-box LLM f(+) using the validation dataset Dy, obtaining new observed pair of (E, sv (E)). This process is repeated until the query budget T is exhausted. An overview of the algorithm is presented in Alg.
Algorithm 1: EASE
Require: Data exemplars set D, validation set Dv, length of exemplars kt total budget T, number of initial rounds Tinit sampling size q'. black-box target model f(-), embedding model (t(-), neural network m(-;0), (optional) instruction set P.
Initialize {(E,, sy (E.))] with Thit randomly sampled (E,)
Tun from D;
for /. t= TTmm to T do
Following (2. use observations {(E,, sv (E.)) to train the NN ml(:0,) 0,) parameter 0;;
Sample sequences Q and select top-q' sequences Qi with smallest OT distances; (Optional) Augment each E E Q/ with instructions E P.e. Q2 + I-P. x Q/:
Following 3 select the next query E, arg ra (E)) Evaluate E, on the black-box model to obtain the validation score sv (E,);
7
return E
arg max (1,... Sy (F.)
5

---

Table 1: Average accuracy + standard error achieved by the best exemplar sequence discovered by different algorithms over 3 independent trials. For better distinguishability, we do not include easy
tasks here (i.e., with 100% accuracy across baselines) and show full results in Tab. of App. C.T
DPP
MMD
OT
Cosine
BM25
Active
Inf
Evo
Best-of-N
EASE
antonyms
70.Daor
80.0-aa
81.7au7
85.0gaa
85.0gno
80.0g0o
86.7a1
88.3
90.0.00
90.0
auto categorization
3,3
8.3
0.0gm
25.0aaa
16.7217
10.0gh
21.72
21.7
20.0gn
30.0
diff'
0.0aot
0.0
0.0gm0
0.0gea
0.0g00
0.0g00
100.0.4a
100.0.44
100.0.u
100.0..*
larger_ann animal
70.0ase
91.7a17
100.0.0e
100.0.aa
100.0.a>
66.7214
100.0..x
100.0.>a
100.0.s
100.0:.*
negation
95.0aaa
95.0.aa
95.0.m0
95.0
95.0gmm
95.0
95.0.saa
95.0.ma
95.0gmm
95.0:aa
objoct counting
55.0azs
56.7-17
287
61.7.11
66. 2a17
S1.7
63.3244
70.0
70.0
73.3
orthogruphy. _stastssssss with
20.Dar
35.0=a1
61.7g17
78.3
70.0gm
43.3gtc
70.0
75.0gm
78.3g11
80.0
rhymes
60.0anz
51.7
0.0
100.0:aa
80.0
65.0pxa
70.0am
100.0.aa
100.0.a0
100.0:
second word letter
10.0ars
30.0 30.0
28.3
50.0at4
50.0gm
26.7ass
40.0aas
46 2217
50.0am
53.3
sentenes_ similariy
20.0aoz
21.7:33
40.0:29
46.7
53.3
5.0
18.3
45.0
51.7
56.7:17
sentiment
90.0.am
85.0gm
9677
100.0
85 0gst
91.7a11
100.0.aa
100.0
100.0..a
sum
0.Daoz
0.0-aa
0.0
0,0
0.0
0.0
100.0
100.0
100.0:00
100.0
synonyms
10.0aos
25.0.aa
20.0gn0
35.0
30.0g0n
3.3g14
26.7413
30.0.a0
30.0goo
30.0at
laxonoeny_smie snimal
43.3
40.0-27 22
46.7
85.0
80.0..p
45.01az
70.0
80.0
80.0
13.
translation, en-de
90.0ses
80.0=aa
80.0gm0
90.0
85.0gmn
56.72:s
90.0
90,0
90.0
90.0:aa
translation en-es
100.0
96.7
100.0
100.0:00
96.7
98.3
100.0
irnssatioo, en-fr word sontig word unserambling
76.7211
76.7217
81.7
85.0gra
85.0gmo
81.7gic
85.0aa:
8677
85.0gee
88.3
26.7a11
88.3-13
88.3a17
90.0aaa
71.7a17
80.0
88.3413
93.3-12
91.7ai7
90.0ata
68.3g11
56.7gz
71.7gm
75.0gsa
76.7217
63.3g
66.7
75.0gm
75.0gn
78.3
# bost best-perfomning tasks
2
5
17
4 Experiments
We compare EASE with the following comprehensive suite of baselines. They include subset selection methods with (a) a determinantal point process (DPP) metric adapted from [48], and (b) maximum mean discrepancy (MMD) (9), (c) optimal transport (OT) 42) metries. We also adapt retrieval- based methods to our setting using a new retrieve-then-samlee strategy based on the validation set (details in App. [B.2] and Sec. 4.5), specifically with the classical (d) Cosine similarity and (e) BM25 (37] retrievers. We also compare with existing exemplar selection baselines using (f) an active selection policy learned using reinforcement learning (Active) (50), and (g) an exemplar influence metric (Inf) B1. Additionally, we propose two more new strong baselines: (h) Evo which mutates exemplars through evolutionary strategies and (i) Best-of-N which explores the exemplar space uniformly until the query budget is exhausted. Evo is similar to PhaseEvo proposed by Cui et al. [8. Best-of-N shares similarity with DSPy's 's BootstrapFewShot with RandomSearch (17). More implementation details are found in App. B.2 The number of exemplars in the in-context prompt set to ie The black-box query budget is 165 evaluations following Lin et (21) Since the effectiveness of the optimization is directly reflected by the value of the objective function in { we report the validation accuracy in the following experiments unless otherwise specified. The test accuracy tables are presented in App. C.15
4.1 Empirical study of performance gains on various benchmark tasks
To study the effectivvnees of EASE, we conduct empirical comparisons with baseline methods using the Instruction Induction (II) benchmark tasks (5). We test on tasks that contain more than 100 training examples for selection. The results are shown in Tab. [ Our EASE achieves the best performance in 17 out of 19 language tasks. We observe that the subset selection methods such as DPP, MMD and OT are ineffective in practice. implying that choosing subsets alone without considering the order information is inadequate. While the retrieval-based methods Cosine and BM25 have demonstrated success in retrieving test- satt--mmlle-assee exemplars 38, it is not as effective in finding the best exemplars that generalize to the entire task. This is because the exemplars retrieved at the instance level may not work well for the entire validation set. The Active bascline requires training an active exemplar selection policy through the data-intensive reinforcement lcarning process, which explains its ineffectiveness under our budget-constrained setting. The Inf baseline is not efficient in subset sampling and disregards exemplar ordering, leading to worse results. Our proposed Evo and Best-of-N are the most competitive baselines both with best performance in 9 tasks.
We discover that while EASE consistently outperforms or matches the baselines across tasks, for some tasks, most baselines achieve good performances. We hypothesize that the effect of exemplar selection diminishes as the model gains more knowledge about the task. This explains the instances where the choice in-context exemplars has minimal impact on the performance, as the black-box model (i.e.. GPT-3.5 Turbo) has been pre- pre-trained on these publicly available language tasks. As

---

suggested by Brown et al. [3, it is highly likely that GPT-3 has been trained on common benchmark datasets potentially contained in Common Crawl due to data contamination. Hence, further providing high-quality in-context exemplars could hardly improve the performance of the model on these well- trained tasks. Another possibility could be that the exemplars mostly serve as the context for adapting to the new formatting rules of the specific task, i.e., the L.M is not utilizing the semantic contents of the exemplars to learn the underlying input-output relations. This aligns with the discoveries of Min et al. [27] and provides potential explanation for the surprising behavior of LLMs. Therefore, the II dataset might not be the most suitable one to test EASE. Next, we verify the above hypothesis that the effect of exemplar selection diminishes as the model gains more knowledge about the task in Sec. 4.2 and propose more suitable families of datasets for exemplar selection in Sec.
4.2 Empirical validation of the hypothesis through progressive finetuning
We hypothesize that the effect of exemplar selection diminishes as the model gains more knowledge about the task. To gain insights on this hypothesis, we study an open-source white-box Vicuna model instead of the black-box GPT-3.5 model that is only accessible through API. We progressively finetune the while-box language model, and examine whether the extent of finetuning on a specific task diminishes the importance of in-context exemplars when prompted.
Our results are in Fig. I Compared to the most competitive baseline, Best-of-N, the gain from exemplar selection using our EASE diminishes as the model is finetumed on the dataset of the respective tasks for more epochs. Across the three tasks shown in Fig. [ using EASE originally has a performance gain of about 30-10% and this gain slowly diminishes to 0 as finetuning progresses. This verifies our hypothesis and calls for further investigation of the exemplar selection performance of our EASE on tasks that have not been seen by the model, which we conduct in Sec.
1.00
0.6
Gap in sccurecy Accuracy
00/55
Accuracy
Accuracy
0.50
0.5
0.6
Best-of-N CASC
Best-af-N
Rest-of-N
0.25
EASE
0.5-
EASE
Gap accuracy
Gap accuracy
0.03
0.10
0.02
0.02
0.05
0.00
0.00
0.00
5
11
12
20
28
36
10
30
50
70
90
Finetuning epochs
Finetuning epochs
Finetuning ng epochs
Figure I: From left to right, the tasks are taxonomy animal, sentence similarity and object counting. The performance gaps between EASE and the Best-of-N baseline diminish as the LLM is finetuned.
4.3 New families of "outtof-distributtonn tasks that emphasize in-context reasoning
We propose three new families of "outtof-disttibuttin" tasks (i.c., loosely referred to as tasks on which the LLM not already well trained) that highlight the importance of high-quality exemplars, which could also be of independent interest. The new tasks require the LLM to learn the underlying sunction/relationship in the input prompt in order to perform reasoning during inference, and are hence more sensitive to the quality of the exemplars.
Rule-hased tasks. Given our insight the impact of the model's existing knowledge about the task (.2). we propose rule-based tasks that contain novel rules that the I.I.M has not learned before. key characteristic of these tasks is that the model has to extract the underlying relationships among the provided in-context exemplars and directly use the relationship for test-time inferences. For example, we construct the linear regression (LR) task where the input takes the form demonstrated in Example
2 (see App. B.I. The underlying relationship in this example is y = az + b, with a -4 and b in this specific Example 2 Without further instructions, the model is supposed to rely on the provided in-context exemplars to implicitly infer the regression task, recover the coefficients a, b for linear regression, and then directly apply it to the test sample (e.g., for test input 117, compute -4 117 + 6- = -462 and output- -462). The results are in Tab. 2 For the clean dataset (i.e., 0% noise), EASE outperforms the most competitive baseline by 8.3% absolute accuracy. Note that EASE has greater advantages in settings with noisy data, which will be discussed later in this section.
7

---

Another example of our proposed rule-based tasks is constructed by changing the rules for language puzzles (LP). prominent example is "pig Latin" which follows two simple rules: (a) For words that begin with a vowel, one just adds "yay" to the end; (b) for words that begin with consonants, the initial consonants are moved to the end of the word, then "ay" added. For example, translating "Hello, how are you today?" to pig Latin gives "Ellohay, owhay areyay ouyay odaytay?". Note that this task also requires the model to reason about the language translation rules (i.e., rules (a) and (b)) before predicting for the test sample. The rules can be frrely modified (e.g.. by changing the suffix word "yay" to others) to create diverse tasks that require in-context reasoning from the LLM. Hence, we create a new variant of the LP task, named LP-variant, by using the "ay" suffix for both rules (a) and (b). An example of the task query is given in Example 3 (see App. B. As shown in Tab. 2 in this task, our EASE also demonstrates competitive results and outperforms all baselines.
Remapped label tasks. By remapping the labels of existing classification tasks to new ones, we construct novel tasks that are against the model's existing knowledge. In the commonly used AG News dataset, the news articles are classified into four categories: "World", "Sports", "Business" and "Sci/Tech". We construct a remapped dataset AG News Remap such that "World" news is now labeled as "Sports" news, "Sports" " is now labeled as "Business", etc. This is against the LLM's knowledge since the output now does not correspond to the context descriptions of the input (i.e., news articles). So, the LLM has to learn these remapping rules from the in-context exemplars. Similarly, construct another dataset SST5 Reversed by reversing the labels of the sentiment analysis dataset SSTS, such that "very negative" labels are swapped with "very positive" labels, and "negative" labels swapped with "positive" labels. The results for these novel remapped label tasks are also in Tab. 2 which shows superior performances of EASE over baselines by 6.7%-10%% in absolute accuracy.
Noisy tasks. Exemplar selection is even more important to achieve good ICL performances when the dataset is potentially noisy, since using noisy or mislabeled data as exemplars could have detrimental effects performance. Noisy datasets also better resemble practical scenarios because clean data is expensive and difficult to obtain. We construct noisy datasets by injecting various ratios of noisy outputs into the task datasets, ranging from having 10% noisy data samples (i.e., the remaining 90% are clean) to having 90% noisy data samples (i.e., the remaining 10% are clean). We show in Tab. 2 that EASE is the best-performing method across different noise ratios and generally exhibits lower decrease in accuracy as the tasks become more difficult with increasing noise ratios.
Note that the conclusions on test accuracy results (in App. C.15) are consistent with the main text. These tasks above represent new families of tasks that contain novel knowledge for LLMs. We show through comprehensive experiments that exemplar selection is important and useful in practice, especially for novel downstream task adaptations. Also, the noisy datasets considered here align with real-world scenarios, which typically contain noises from observation, labeling error, corruption, etc.
4.4 Jointly optimizing instruction and exemplars
To the best of our knowledge. no prior work can can jointly optimize instruction and exemplars. For fair comparison, we do not include an instruction when comparing with other exemplar selection baselines in earlier sections. As EASE is readily extended to find the optimal combination of instruction and exemplars (Sec. (3.3), we show the benefits of joint optimization in this section. According to Tab. jointly optimizing these two essential components of a prompt significantly improves the performance for most tasks (marked with red arrows 1). This improvement is attributed to the ability of the optimized instruction to significantly reinforce the information captured in the corresponding exemplars. For example, an automatically optimized instruction "identify and list the animals from the given words" complements the exemplars in the taxonomy animal task. Therefore, our joint optimization of instruction and exemplars presents a fully automated pipeline for prompt optimization and achieves impressive practical performances.
4.5 Ablation studies
Combination with retrieval-based methods to handle larger sets of exemplars. Applying EASE to scenarios where the size n of the set of exemplars D is very large may lead to performance degradation. This is because the space Ω of exemplar sequences becomes excessively large, which cannot be sufficiently explored without significantly increasing the computation (i.e., with the size of Q. being fixed). To resolve this issue, natural idea is to first filter the large pool of data exemplars to eliminate
8

---

Table 2: Average accuracy + standard error over 3 independent trials achieved by different algorithms on the new families of out-of-distribution tasks.
Type
Task
Noise
DPP
MMD
OT
Cosine
BM25
Active
Inf
Evo
Best-of-N
EASE
31.7
38.3
50.0.a>
71.7.11
70.0.0e
36.7,14
56.7ana
61.7a17
66.7g1
a0
10%
8.3
36.7217
48.3g11
61.7g11
61.7215
0.0g00
58.3
60.0gm
65.0g
10.0
28.3
46.7.11
63.3.11
60.0.0o
40.0aa4
35.0,39
53.3
50.0
76.7
Rule-based bleebbsed tasks
LR
50%
0.0
38,3g17
45.0gas
65.0ge0
53.3g11
0.0.00
51.3g1
46.7g10
45.0gma
-8
55.0gaa
38.3,33
65.00..
50.0.00
26.7as4
30.0asa
33.3
33.3g11
66.7.11
90%
0.0gmn
21.7
26.7g11
46.7g
3.3g15
0.0gen
6.7
8.3g
15.0ga3
g3.
0%
48, 38.3+55
40.0=2>
41.7=1>
65.0=ee
58.3
30.0
61.7a17
75.0ez>
71.7
25
10%
0.0gna
36.7a17
40.0.s3
63,3
60.0.0o
36.7
65.0129
70.0
73.3
80.0
LP-
30%
0.0
48,3+33
40.0-21
60.0
55.0
40.0
53.3
65.0e2>
65.0eaa
15
variant
50%
0.0
65.0
35.0
63.3
60.0.00
38.3
48.3
61.7at7
65.0
78.3
70%
0.0gen
46.7g33
35.0gas
70.0gee
60.0gee
25.0gaa
60.0g5e
56.7217
56.7gi1
21
90%
0.0an0
35.0s2>
50.0
65.0
0.0g00
30.0
50.0129
38.3
55.0g31
66.7
0%
20.0+29
15.0eaa
26,7=1>
43.3-11
43.3+13
5.0+2A
25 15.00sn
40.0soa
40.0ea:
50.0
10%
5.0aso
15.0em
15.0=as
41.7a1
38.3
3.3+1A
26.7a33
36.7au7
40.0saa
=1.7=1>
Re-mapped label tasks
AG
30%
10.0
5.Deaa
5.0=as
40.0=so
36.7a17
1.7
10.0
40.0xoa
43.3
55.0
News
50%
5.0
10.0em
5.0=as
43.3=m
35.0zm
3.3
20.0san
35.0sm
35.0saa
55.0
Remap
70%
5.0
25.0eaa
8,3
50.0=so
35.0
1.701A
11.7a67
38.3
46.7e1.
33
90%
5.0am
18.3
5.0=as
40.0=ma
10.0su
15.0eea
35.0am
35,0sm
41.7st>
53.3-13
0%
20 Oano
10,0
13.3
40.0ge0
40.0zm
15.0
33.3
35 0.:0
40.0
50.0
10%
16.7
10.0ga0
15.0ga
48.3
40.0gee
13.3
23.3
33.3g
40.0ga0
_8
SST5
30%
23 2313
6,72t
25.0az>
40.0gae
40.0zm
21.723e
26.7
30.0
31.7au
46.7=
Reverse
50%
21.7
15.0eaa
15.0-as
43.3-11
33.3-1
21.7+14
23.3
28.3
30.0sa:
46.7-13
70%
25 Oawi
23.3
23.3
40.0gee
30.0zm
20.0az4
25.0am
36.7au
36.7au
45.0.sa
90%
20.0
15.0ez>
20.0-as
30.0=ao
30.0
13.3+27
21.7au
30.0saa
30.0sa:
31.7-11
Table 3: Average accuracy + s.e. for EASE with and with- out jointly optimized instructions. We removed tasks with 100% accuracy. The full results are in App. Tab. 6
Table 4: Average accuracy + s.e.
achieved by EASE and EASE with re- trieval for larger exemplar set sizes.
AG News Remap (10% noise)
EASE with instructions
Improve -ment
EASE
EASE with retrieval
Size n
EASE
antonyms
90.0 Lea
85.0
55.0
auto calegorization
30,0+0a
56.7=17
26.7
1000
50.0s29
60.0
negation
95.0
100.0
5.0
10000
55.0sao
63.3=11
Dojjct_counting
73.
75.0=
1.7
orthography. starts with
80.0
81.7
1.7
50000
48.3
63.3
second_ word letter
53,3+117
100.0:0a
46.7
100000
50.0
65.0
sentence sentence_similarrty synonyms
56.7
58.3
1.7
30.0ss0
31.7=17
1.7
taxonomy_anm _animal
88.3
100.0
11.7
SST5 Reverse (10% % noise)
translation _nn-ee
90.0ssa
90.0=sa
0.0
translation_ce en-ft
88.3
85.0=ap
-3.31
Size
EASE
EASE with retrieval
word_soo sorting
90.01ma
93.3.11
3.31
word unscrambling
78.3+1.7
80,0=aa
1.71
LR (10% noise)
73.3
45.0a150
-28.3
1000
43.3
48.3
LP-variant (10% noise)
80.0429
86.7=17
6.7
3000
48.3+44
48.3-11
AG News Remap (10% noise)
51.7
65.0:az
13.3
5000
43.3+t1
50.0:aa
SSTS Reverse (10% noise)
48.3
53,3-17
5.01
7000
45.0aae
48.3=17
those that are less relevant to the task. This independent step to pre-filter candidates serves as a promising extension of our EASE to handle large set of exemplars. To this end, we propose to first use eetrivval-based methods to select the exemplars that are more relevant to the task, and then run our EASE using this refined smaller set of exemplars. Specifically, we use a cosine similarity retriever on exemplar embedding and perform exemplar selection on D with a size n as large as 100000. The query involves validation data exemplars Dy and we retrieve from the corpus of training set exemplars D. For each validation data exemplar in Dy, we retrieve the most similar/relevant training set exemplars from D. Then, we combine them to form smaller set of exemplars than D and proceed with EASE using this reduced subset for efficiency. As shown in Tab, 4 when the size n of the exemplar set is large, combining EASE with retrieval gives better performances than directly running EASE
Effectiveness of components of EASE. Here we show the necessity of both of the main components to the success of EASE: OT and NeuralUCB. As shown Tab. of App. C.3 EASE significantly outperforms methods employing OT or NeuralUCB alone. Overall, pure subset selection algorithm based on OT performs badly on its own, especially when the dataset's 's noise ratio is high. However, when used together with NeuralUCB, OT significantly improves the performance of our EASE.

---

Further ablations. We defer further ablation studies to App. including those exploring (a) speedups from OT, (b) larger l or a range of k. (c) a larger query budget T. (d) benefits of using an ordering-aware embedding, (e) different black-box LLMs, (f) other embedding models, (g) degree of exploration v. (h) asking GPT to directly select exemplars, and (i) additional experiments on more datasets including reasoning chains.
5 Related work
Retrieval-based methods. This approach utilizes trainable exemplar retrievers to select exemplars depending the text sequence of each individual test sample [144). Liu et al. [23] first proposed a similarity-basee (e.g., negative Euclidean distance or cosine similarity) retrieval strategy on the sentence embeddings of the exemplars for ICL. Gao et al. []]] further enhanced the above by emphasizing on exemplars with top-2 labels that the LLM is most uncertain about. Adapting retrievers to specific tasks, Rubin et al. [38] learned retrieval model from evaluating individual exemplars by their I-shot ICL performance on validation data. Improving on the limitation of the above methods that exemplars are considered in isolation (i.e., independently). Ye et al. 48 proposed to retrieve a set of exemplars jointly by examining their joint probability to capture inter-relationships. Likewise, Levy et al. (18] retrieved set by selecting diverse exemplars that collectively cover all of the output structures. Gupta et al. [4] instead generalized the individual metrics to a set-level metric through a submodular function, which is well-suited for optimization via greedy algorithms. However, retrieval-baa -based methods are characterized by varying exemplars for each test sample, which do not align with our practical setting of maintaining fixed set of exemplars for the entire task. Also, another common drawback is that heuristics are typically required to order the exemplars in the retrieved set.
Selection of a fixed set of exemplars. Having a fixed set of exemplars offers practical and privacy- related advantages, such the ease of implementation and reduced data exposure [25 30 Wang et al. proposed to train a small L.LM as a latent variable model using output token logits from independent exemplars, then forming fixed exemplar set directly transfer to target models. Similarly, Chang and Jia 4 developed a data model for each validation sample and introduced an aggregate metric select subsets. Li and Qiu [19] proposed to filter and search for best exemplars using an informativeness metric derived from LLM output logits on classification tasks. However, these works restricted classification tasks. The closest to our work is that of Zhang al. (50), which used reinforcement learning to actively select exemplars. In a similar setting to ours, Nguyen and Wong (31] used influence select the most influential exemplars and order them arbitrarily to form the subset. However, both methods perform worse than our algorithm in our experiments.
Instruction optimization. Another related direction for enhancing the performance of LLMs is instruction optimization. Focusing on instructions within the prompt, evolutionary algorithms and seroth-order optimization algorithms are gaining popularity in refining the prompts for black-box
LLMs (5] 10 [3 16 21 [47). Specifically, some studies [10 16 21 47] maintained a constant set of
exemplars throughout the process of prompt optimization, whereas others (5 9 13 [4] ignored the consideration of exemplars altogether by adopting a zero-shot setting. It is therefore imperative to develop an effective exemplar selection method for black-box LLMs.
Conclusion and limitation
We propose EASE, an algorithm that selects the optimal ordered set of exemplars for in-context learning of black-box LLMs in an automated fashion. EASE is query-efficient due to the adoption of the NeuralUCB algorithm and is further made computationally feasible for large spaces of exemplar sequences through technique based on optimal transport. Additionally, our EASE has been extended to fully automated prompt optimization pipeline that jointly optimizes exemplars and instruction for the best in-context learning performance. Furthermore, we provide practical insights indicating that exemplar selection in in-contes learning is more crucial for downstream tasks that the LLM has limited knowledge about. However, the on-the-fly computation of embedding for the ordered exemplar sequences is the computational bottleneck of our method, which could be potentially improved in future work for more efficient optimization. Also, a potential limitation of EASE the requirement for a suitable validation set, which may not be readily available in some scenarios.
10

---

Acknowledgments and Disclosure of Funding
This research is supported by the National Research Foundation Singapore and the Singapore Ministry of Digital Development and Innovation, National AI Group under the AI Visiting Professorship Programme (award number AIVP-2024-001). This research is supported by the National Research Foundation (NRF), Prime Minister's ' Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme. The Mens, Manus, and Machina (M3S) an interdisciplinary research group (IRG) of the Singapore MIT Alliance for Research and Technology (SMART) centre.
References
[1] Alon Albalak, Yanai Elazar, Sang Michael Xie, Shayne Longpre, Nathan Lambert, Xinyi Wang. Niklas Muennighoff, Bairu Hou, Liangming Pan, Haewon Jeong, Colin Raffel, Shiyu Chang, Tatsunori Hashimoto, and William Yang Wang. survey on data selection for language models. arXiv:2402. /627, 2024.
[2] Hamsa Bastani, Mohsen Bayati, and Khashayar Khosravi. Mostly exploration-fre algorithms for contextual bandits. Management Science,
2021.
[3] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, llya Sutskever, and Dario Amodei. Language models are few-shot learners. In Proc. NeurlPS, pages 1877-1901, 2020.
[4] Ting- Tun Chang and Robin Jia. Data curation alone stabilize in-context learning. In Proc. ACL, pages 9123-8144, 2023.
[5] Lichang Chen, Jiuhai Chen, Tom Goldstein, Heng Huang, and Tianyi Zhou. InstructZero: Efficient instruction optimization for black-box large language models. 0300022306.03082, 2023.
[6] Lingjiao Chen, Matei Zaharia, and James Zou. How is ChatGPT's behavior changing over time? 20X0003077.0009, 2023.
[7] Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Hcewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems. arXiv:2110.14168. 2021.
[8] Wendi Cui, Jiaxin Zhang, Zhuohang Li, Hao Sun, Damien Lopez, Kamalika Das, Bradley Malin, and Sricharan Kumar. Phaseevo: Towards unified in-context prompt optimization for large language models. arXiv:2402. 1347, 2024.
[9] Mingkai Deng, Jianyu Wang. Cheng-Ping Hsieh, Yihan Wang, Han Guo, Tianmin Shu, Meng Song, Eric Xing, and Zhiting Hu. RlPrompt: Optimizing discrete text prompts with reinforce- ment learning. In Proc. EMNLP, pages 3369-3391, 2022.
[10] Chrisantha Fernando, Dylan Banarse, Henryk Michalewski, Simon Osindero, and Tim Rocktäschel. Promptbreeder: Self-referential self-improvement via prompt evolution. 2309::2309. 16797, 2023.
[11] Lingyu Gao, Aditi Chaudhary, Krishna Srinivasan, Kazuma Hashimoto, Karthik Raman, and Michael Bendersky, Ambiguity-awee in-context learning with large language models. arXiv:2309.07900 2024.
[12] Dirk Groeneveld, Beltagy, Evan Walsh, Akshita Bhagia, Rodney Kinney, Oyvind Tafjord, Ananya Jha, Hamish Ivison, Ian Magnusson, Yizhong Wang, Shane Arora, David Atkinson, Russell Authur, Khyathi Chandu, Arman Cohan, Jennifer Dumas, Yanai Elazar, Yuling Gu, Jack Hessel, Tushar Khot, William Merrill, Jacob Morrison, Niklas Muennighoff, Aakanksha Naik,
11

---

Crystal Nam, Matthew Peters, Valentina Pyatkin, Abhilasha Ravichander, Dustin Schwenk, Saurabh Shah, William Smith, Emma Strubell, Nishant Subramani, Mitchell Wortsman, Pradeep Dasigi, Nathan Lambert, Kyle Richardson, Luke Zettlemoyer, Jesse Dodge, Kyle Lo, Luca Soldaini, Noah Smith, and Hannaneh Hajishirzi. OI.Mo: Accelerating the science of language models. In Proc. ACI, pages 15789, 2024.
[13] Qingyan Guo, Rui Wang, Junliang Guo, Bei Li, Kaitao Song, Xu Tan, Guoqing Liu, Jiang Bian, and Yujuu Yang. Connecting large language models with evolutionary algorithms yields powerful prompt optimizers. In Proc. ICI.R, 2024.
[14] Shivanshu Gupta, Matt Gardner, and Sameer Singh. Coverage-based example selection for in-context learning. In Pruc. EMNLP, pages 13924-13950, 2023.
[15] Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the MATH dataset. In Proc. NeurIPS (Track on Datasets and Benchmarks), 2021.
[16] Wenyang Hu, Yao Shu, Zongmin Yu, Zhaoxuan Wu, Xiangqiang Lin, Zhongxiang Dai, See- Bee-Kiong Ng. and Bryan Kian Hsiang Low. Localized zeroth-order prompt optimization. arXiv:2403.02993 2024.
[17] Omar Khattab, Arnav Singhvi, Paridhi Maheshwari. Zhiyuan Zhang, Keshav Santhanam, Sri Vardhamanan A, Saiful Haq, Ashutosh Sharma. Thomas T. Joshi, Hanna Moazam, Heather Miller, Matei Zaharia, and Christopher Potts. DSPy: Compiling declarative language model calls into state-of-the-art pipelines. In Proc. ICLR, 2024.
[18] Itay Levy, Ben Bogin, and Jonathan Berant. Diverse demonstrations improve in-context compositional generalization. In Proc. ACI. pages 1401-1422, 2023.
[19] Xiaonan Li and Xipeng Qiu. Finding support examples for in-context learning. In Proc. EMNLP, pages 6219-6235, 2023.
[20] Xiaonan Li, Kai Lv, Hang Yan, Tianyang Lin, Wei Zhu, Yuan Ni, Guotong Xie, Xiaoling Wang, and Xipeng Qiu. Unifted demonstration retriever for in-context learning. In Proc. ACL., pages 4644-4668, 2023.
[21] Xiaoqiang Lin, Zhaoxuan Wu, Zhongxiang Dai, Wenyang Hu, Yao Shu, See-Kiong Ng, Patrick Jaillet, and Bryan Kian Hsiang Low. Use your INSTINCT: Instruction optimization using neural bandits coupled with transformers. In NeurIPS Workshop on Instruction Tuning and Instruction Following, 2023.
[22] Wang Ling, Dani Yogatama, Chris Dyer, and Phil Blunsom. Program induction by rationale generation: Learning to solve and explain algebraic word problems. In Proc. ACL. pages 158-167, 2017.
[23] Jiachang Liu, Dinghan Shen, Yizhe Zhang, Bill Dolan, Lawrence Carin, and Weizhu Chen. What makes good context examples for GPT-3? In Proc. DeeLIO: Deep Learning Inside Out, pages (00, 2022.
[24] Yao Lu, Max Bartolo, Alastair Moore, Sebastian Riedel, and Pontus Stenetorp. Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity. In Proc. ACL, pages 8086-8008 8098, 2022.
[25] Man Luo, Xin Xu, Yue Liu, Panupong Pasupat, and Mehran Kazemi. In-context learning with retrieved demonstrations for language models: survey. arXiv:2401. 2024.
[26] Nestor Maslej, Loredana Fattorini, Raymond Perrault, Vanessa Parli, Anka Reuel, Erik Bryn- jolfsson, John Etchemendy, Katrina Ligett, Terah Lyons, James Manyika, Juan Carlos Niebles, Yoav Shoham, Russell Wald, and Jack Clark. The Al index 2024 annual report. Technical report, Al Index Steering Committee, Institute for Centered AI, Stanford University, 2024.
[27] Sewon Min, Xinxi Lyu, Ari Holtzman, Mikel Artetxe, Mike Lewis, Hannaneh Hajishirzi, and Luke Zettlemoyer. Rethinking the role of demonstrations: What makes in-context learning work? In Proc. EMNLP, pages 11048-11064 1064, 2022.
12

---

[28] Shervin Minaee, Tomas Mikolov, Narjes Nikzad, Meysam Chenaghlu, Richard Socher, Xavier Amatriain, and Jianfeng Gao. Large language models: survey, arXiv:2402.06116. 2024.
[29] Marius Mosbach, Tiago Pimentel, Shauli Ravfogel, Dietrich Klakow, and Yanai Elazar. Few- shot fine-tuning vs. in-context learning: fair comparison and evaluation. In Proc. ACL. Findings, pages 12284-12314, 2023.
[30] Seth Neel and Peter Chang. arXiv:2312.06717, 2024.
Privacy issues in large language models:
survey.
[31] Tai Nguyen and Eric Wong. In-context example selection with influences. arXiv:230.111042. 2023.
[32] OpenAI, Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Floren- cia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, and Sam Altman et al. GPT-4 technical report. arXiv:2303.0877,, 2024.
[33] Ethan Perez, Douwe Kiela, and Kyunghyun Cho. True few-shot learning with language models. In Proc. NeurlPS, pages 1054-11070, 2021.
[34] Archiki Prasad, Peter Hase, Xiang Zhou, and Mohit Bansal. GrIPS: Gradient-free, edit-based instruction search for prompting large language models. In Proc. EACL, pages 3845-3864, 2023.
[35] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In Proc. ICML, pages 8748-8763, 2021.
[36] Nils Reimers and Iryna Gurevych. Centence-BERT Sentence embeddings using siamese bert-networks. In Proc. EMNLP, pages 3982-39999 2019.
[37] Stephen Robertson and Hugo Zaragoza. The probabilistic relevance framework: BM25 and beyond. Found. Trends Inf. Retr. 344)3333-3,, 2009.
[38] Ohad Rubin, Jonathan Herzig, and Jonathan Berant. Learning to retrieve prompts for in-context learning. In Proc. NAACL, pages 2655-2671, 2022.
[39] Dino Sejdinovic, Bharath Sriperumbudur, Arthur Gretton, and Kenji Fukumizu. Equivalence of distance-based and RKHS-based statistics in hypothesis testing. Annals of Statistics, 41(5): 2263 2291,2291,222 2013.
[40] Kaitao Song, Xu Tan, Tao Qin, Jianfeng Lu, and Yan Liu. MPNet: masked and permuted pre-training for language understanding. In Proc. NeurIPS, pages 16857-16867, 2020.
[41] Gemini Team, Rohan Anil, Sebastian Borgeaud, Jean Jean-Bapaneeeeeeeeeee Baptiste Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M. Dai, Anja Hauth, and Katie Millican et al. Gemini: A family of highly capable multimodal models. arXiv:2312. 1805, 2024.
[42] Cédric Villani. Topics in optimal transportation, volume 58. American Mathematical Soc., 2021.
[43] Wenhui Wang, Furu Wei, Li Dong, Hangbo Bao, Nan Yang, and Ming Zhou. MiniLM: Deep self-attention distillation for agnostic compression of pre-trained transformers. In Proc. NeurlPS, pages 5776-5788 2020.
[44] Xinyi Wang. Wanrong Zhu, Michael Saxon, Mark Steyvers, and William Yang Wang. Large language models are latent variable models: Explaining and finding good demonstrations for in-context learning. In Proc. NeurIPS, pages 15614-15638, 2023.
[45] Jeremy White. How strangers got email address from ChaiGPT's model. The New York Times, 2023. URL htttttt/p:/:/ww http://wwww.ttiiissss.. http::/wwww........t/tteraaaaaaa cwt.m///mmeeraaatae////////22222
rechmollogy/openiiccccaaggee hhtp:ppppnnniiccaat-t------e explyit.epppptpeoeo html
13

---

[46] Xinyi Xu, Zhaoxuan Wu, Rui Qiao, Arun Verma, Yao Shu, Jingtan Wang, Xinyuan Niu, Zhenfeng He, Jiangwei Chen, Zijian Zhou, Gregory Kang Ruey Lau, Hieu Dao, Lucas Agussurja. Rachael Hwee Ling Sim, Xiaoqiang Lin, Wenyang Hu, Zhongxiang Dai, Pang Wei Koh, and Bryan Kian Hsiang Low. Data-centric ai in the age of large language models. In Proc. EMNLP Findings, 2024.
[47] Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V. Le. Denny Zhou, and Xinyun Chen. Large language models as optimizers. In Proc. ICLR, 2024.
[48] Jiacheng Ye, Zhiyong Wu, Jiangtao Feng, Tao Yu, and Lingpeng Kong. Compositional exem- plars for in-context learning. In Proc. ICML, pages 39818-39833, 2023.
[49] Tianjun Zhang, Xuezhi Wang, Denny Zhou, Dale Schuurmans, and Joseph E. Gonzalez, Tem- pera: Test-time prompting via reinforcement learning. In Proc. ICLR, 2023.
[50] Yiming Zhang, Shi Feng, and Chenhao Tan. Active example selection for in-context learning. In Proc. EMNLP, pages 9134-9148, 2022.
[51] Wayne Xin Zhao, Kun Zhou, Junyi Li. Tianyi Tang. Xiaolei Wang. Yupeng Hou, Yingqian Min, Beichen 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. A survey of large language models. arXiv:2303. 18223, 2023.
[52] Zihao Zhao, Eric Wallace, Shi Feng, Dan Klein, and Sameer Singh. Calibrate before use: Improving few-shot performance of language models. In Proc. ICML, pages 12697-12706, 2021.
[53] Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with UCB-based exploration. In Proc. ICML, pages 1492-11 11522, 2020.
[54] Yongchao Zhou, Andrei loan Muresanu, Ziwen Han, Keiran Paster, Silviu Pitis, Harris Chan, and Jimmy Ba. Large language models are human-level prompt engineers. Proc. ICLR, 2023.
14

---

A Broader impacts
As LLMs continue to gain popularity and are increasingly used by a broad user base (e.g., evidenced by OpenAl's over million active users), carefully handling the ethical considerations associated with LLMs' diverse applications becomes crucial. Such a work like ours which focuses on automatically optimizing the performance of LLMs offers valuable applications and ease of usage. However, is both challenging and essential to address the potential for malicious usage. When applied to tasks specially designed with malicious adversarial intent, method could be exploited to produce harmful instructions and exemplars. In such cases, responsible usage of the tool is important. There may be need for user-friendly platform (which integrates safety measures, instead of providing the raw code) to add an extra layer of protection. Additionally, we urge the community to focus more on potential ethical and safety issues related the usage of LLMs and associated technologies, which should also account for additional objectives and constraints (e.g., harmfulness).
B Implementation details
In this section, we provide details for the implementation of the data processing (see App. B.1 and the baseline methods employed in this paper (see App. B.2) All experiments are conducted on server with Intel(R) Xeon(R) CPU and NVIDIA H100 GPUs. Unless otherwise stated, we use "gpt-3.5-turbo-111
the target black-box model, and MPNet as the embedding model.
B.1 Details for data processing
We follow the query template proposed by APE [54 for querying LLM models. Example T below shows the general query template for in-context learning (ICL) used in the paper, and the LLM will generate outputs corresponding to the query. In the template, the placeholders (i.c., [INSTRUCTION] [INPUT], [OUTPUT] and [TEST INPUT]) are replaced by raw text in the datasets. The placeholder "<More exemplars...>" represents any additional exemplars written the same input-output format depending on the number of in in-context exemplars k in the prompt. The "instruction" is optional in the query and we only include the instruction when jointly optimizing for both the exemplars and the instruction (Sec. 3.3 and Sec. 4.4).
Example Query 1: A General Template
(optional) Instruction: [INSTRUCTION]
Input: [INPUT]
Output: [OUTPUT]
<More exemplars...
Input: [INPUT]
Output: [OUTPUT]
Input:
[TEST INPUT]
Output:
Next, we present the details for the new families of out-of-distributiio tasks that we proposed in Sec. 43
Linear regression (LR). The LR task is generated with an underlying linear regression function y b, where a, are the coefficients to be defined. In specific example of the LR task presented in the paper, we arbitrarily choose a = -4 and = 6. We let x be the input and be the output. Note that to make the task difficult, no information about the function structure (i.e., y = az + b) is passed to the LLM the query. A concrete example shown in Example 2
Language puzzle variant (L.-variant). We change the rules for the classic language game "pig Latin". The original pig Latin follows rules: (a) For words that begin with vowel, one just adds "yay" to the end: (b) For words that begin with consonants, the initial consonants moved to the end
15

---

of the word, then "ay" is added. We create variant, LP-variant, using the "ay" suffix for both rules (a) and (b). An example of the task query is given in Example Note that one could freely modify the rules, by changing the suffix word "yay" to something else for example, and create diverse tasks that require in-context reasoning from the model.
Example Query 3: LP-variant
Example Query 2: LR
Input: quick brown fox The jumps Over the Lazy dog Output: uickqay ownbray oxfay Ethay umpsjay Overyay ethay Azylay ogday
Input: 172
Output: -682
<More exemplars...
<More exemplars...>
Input: 47 Output: -182
Tom never walks to school Output: Omtay evernay alksway otay oolschay
Input:
Input: 117 Output:
Input:
We never talk
Output:
AG News Remap. For the commonly-used AG News dataset, the news articles classified into four categories: "World", "Sports", "Business" and "Sci/Tech". We constructed re-mapped dataset by "shifting" the label mapping, such that
"World" news is now labeled as "Sports" news,
"Sports" news is now labeled as "Business" news,
"Business" news is now labeled as "Sci/Tech" news,
"Sci/Tech" news is now labeled as "World" news.
Note that the remapping rule above is chosen arbitrarily. Therefore, one could create a variety of tasks by changing the remapping rule, or even directly changing the labels completely, For the above rule that we adopted, an example of the AG News Remap task query given in Example
Example Query 4: AG News Remap
Yahoo, Adobe join hands Adobe Systems, the digital imaging, design and document technology platform provider and Internet service provider Yahoo will announce this week the launch of a co- co-branded Yahoo Toolbar. Output: World
Input:
<More exemplars...>
Input:
Schumacher Sets Mark Michael Schumacher won the Hungarian Grand Prix Sunday in Budapest, setting yet another record by becoming the first Formula One driver with 12 victories in a season.
Output: Business
LeapFrog Warns 3Q, Year Profit View LeapFrog Enterprises Inc., devel- oper of Sahnoloogy-based educational products, on Monday lowered third-quarter and full-year profit expectations, citing difficult market conditions. Output:
Input:
SST5 Reverse. SST5 is another commonly used 5-way sentiment classification dataset, with labels being "very positive", "positive", "neutral". "negative" and "very negative". make the task novel and unseen by the LLM before, we reverse the labels to be against the sentiment expressed in the input, such that
"very positive" sentences now labeled "very negative",
"positive" sentences are now labeled as "negative",
16

---

Table 5: Average accuracy + standard error achieved by the best exemplar sequence discovered by different algorithms for different tasks over independent trials.
DPP
MMD
OT
Cosine
BM25
Active
Evo
Best-of-N
ZASE
active_to po_pasivve
100.0.1a
100.0.sa
100.0.sa
100.0.00
100.0.
100,0
100.0
100.0.1a
100.0..a
100.0
antonyms
70.0ace
80.0gaa
$1.7
85.0goo
85.0g0
80.0.am
26.7
88.3
auto Calegorization
3,3
8,3
0.0
25.0tao
16.7
10.0 24
21.7
21.7a17
20.0
.0.0
diff
0.0gce
0.0g00
0.0g00
0.0g00
0.0000
0.0ma0
100.0
100.0:44
100.0.23
100.0..a
first word letter
100.0.a.
100.
100.0.0e
100.0gee
100.0
100.0
100.0.am
100.0:aa
100.0..1
100.0...
larger_ uanimal
70.0
91.7s17
100.0.ca
100.0.00
100.0:00 cmp
66.7-14
100.0
100.0:11
100.0:.1
100.0..a
letters list
100.0.aa
100.0.aa
100.0:0a
100.0.oe
100.0.m
100.0
100.0.am
100.0:4a
100.0.a3
100.0..a
negation
95.0 cc
95.0
v5.0.oz
95.0 ao
95.0 ao
95.0.aa
95.0
95.0 c..
num, to, verbal
100.0.1a
100.0:aa
100.0.a4
100.0soe
100.0.a0
100.0-am
100.0.aa
100.0:33
100.0:a1
100.0:.a
object_ counting
55.0a2s
26.7213
48.
61.7211
66.721
51.7
63.3g44
20.0asa
33.3
orthography starts with
20.0g>
35.0ac4
61.7g
78.3
70.0ge
43.3
70.0ga
75.0g30
78.3
20.0
fhymes
60.0ate
51,7213
0.0gme
100.0.oe
80.0gmm
65.0zxz
70.0am52
100.0:aa
100.0.a1
100,0.ea
second_ weoodd_orrdllie word_
28.3
50.0
40.0.a0
46.7
53.3
sentence
eentencesimillarty similarity
20.0ace
21.7
40.0gas
46.7
53.3g11
5.0ga1
18.3
45 45.0g3a
51.7
56.7
sentiment
85.011a
90.0.oa
85.0
96.7a13
100.0.
85.0
91.7-12
100.0
100.0..a
100.0
singular_ to to_pluma
100.0.4a
100.0.aa
100.0.4a
100.0.am
100.0
100.0.aa
100.0:aa
100.0.a.
100.0..a
sum
0.0ace
0.0ans
0.0ge0
0.0
0.0gmm
0.0gao
100.0
100.0:.a
100.0..1
100.0.aa
synonymns
10.0
25.0.0a
20.0
35.0
30.0.op
3.3
26.7
30.0asa
30.0
30.0
taxonomy aninal
43.
40.0a1s
46.7.1
85.0
80.0am
0.00
20.0.so
80.0asa
80.0
38.
translation en-de
90.0
80.Dioa
80.0
90.0
85.0
56.7.1s
90.0
90.0
90.0
90.0
translaiion
90.0gts
100.0.ca
96.7a11
100.0.00
100.0.am
96.7-1
98. 98.3213
100.0
100.0.aa
100.0:4a
transtation en-fr
76.2a:
76.7211
81.7
85 02m0
85.0amm
81.7
86.7
65.0
38.3
word, sorting unserambling
26.7a
88.3g11
88.3gm
90.0gmo
71.7gi1
80.0gm
88.3
93.
91.7
90.0ac
68.3a17
71.7am
75.0zm
76.7a17
63.3
66.7at7
75.0ase
75.0asa
78.3
# best- best-perfarming tasks
7
7
9
6
10
14
22
"neutral" sentences are still labeled as "neutral""
"negative" sentences are now labeled "positive",
"very negative" sentences are now labeled as "very positive".
This makes the task difficult as the LLM has to now output sentiments that are against the pre-trained knowledge about sentiments, which is obtained from the large corpus of pre-training data that the LLM has been trained on.
An example of the SST5 Reverse task query is given in Example 5
Example Query S: SST5 Reverse
Input:
extremely bad. Output: very positive
<More exemplars...>
Input:
bright, intelligent, and humanly funny film.
Output: very negative
Input:
really dumb but occasionally really funny
Output:
Injecting noises into datasets. construct noisy datasets with different noise ratios, we mainly modify the labels of data points. Specifically, to construct dataset with r% noisy data, sample r% data and replace their labels with the labels of other randomly sampled data points the dataset. We also design specific noise structures for LR and LP- to simulate noises due to systematic error. For LR, the noisy data instead follows = 5x 8. For LP-variant, the noisy data simply repeats the input sentence in the label.
B.2 Details for implementation of the methods and baselines
For all methods, we use a consistent exemplar selection set D, validation set Dy and test set for evaluating one task. We also implement all exemplar selection without replacement for all methods.
17

---

DDP. We follow Ye et al. [8] to use the DPP metric combined with relevance scores as the subset selection criterion. We do train the embedding model and directly use cosine similarity to measure the relevance term. However, the original metric by Ye et al. [48] is dependent on the test input Thest so we adapted the method average the metric over the validation dataset. The exemplar set with the maximum values on the metric is chosen and evaluated on the black-box LLM.
MMD. We use the MMD metric in Sejdinovic et al. [39] measure the distance between the exemplars set and the validation set. The exemplar set with the maximum values on the MMD metric chosen and evaluated on the black-box LLM.
OT. We use the OT metric in (4) to measure the distance between the exemplars set and the validation set. Similarly, the exemplar set with the maximum values on the OT metrie is chosen and evaluated on the black-box L.M.M
Cosine. Retrieval- based methods are not suitable for finding fixed set of exemplars for the entire test set in its original form. Hence, we propose the following adaptation. We first retrieve top- R candidates with the lowest distance to all validation samples on average. Then, sample T permutations of exemplars from the candidates to test on the black-box LLM, where is the black-box query budget. In the above, the retriever calculates the cosine similarity between the embeddings of samples obtained from an embedding model h(.). In this paper, we use R = 10 and use MPNet as h(-)-
BM25. This retrieval-basee baseline works similarly to Cosine. The only difference is that this baseline uses the classic BM25 (37 as the retriever.
Active. We use the official implementation of Zhang et al. (50] For a fair comparison using the same query budget T for the black-box LLM,, we limit the number of episodes that can be used according to T, and then train the exemplar selection policy through reinforcement learning.
Inf. For Inf, we first sample random permutations of exemplar sequences to be evaluated on the black-box LLM to obtain the scores. Then, we follow the influence metric proposed by Nguyen and Wong [31 to select k individual exemplars to form the best exemplar sequence. The best exemplar sequence is then finally evaluated on the black-bor box LLM.
Evo. We propose a new baseline using evolutionary strategies. For each iteration, the mutation operator changes one exemplar in the current best exemplar sequence to another random exemplar. Then, we evaluate the exemplars on the black-box LLM. In this way, we exploit the current knowledge about the best exemplars and perform local mutations.
Best-of-N. This is a straightforward baseline that explores the whole space of all exemplar permuta- tions uniformly by sampling random permutations until the T query budget is exhausted.
EASE. The details for our proposed method EASE are described thoroughly in Sec. 3 We use a sampling size of q 50000 exemplar permutations per iteration after OT is introduced.
C More experiment results
C.1 Full results table for the 24 tasks
Tab. is the full table containing all 24 tasks (with more than 100 training data samples) from the Instruction Induction dataset (compared to Tab. which drops tasks with 100% accuracy across baselines). Our EASE outperforms all baselines.
C.2 Full results table for EASE with instructions
We present the full table of results for EASE with joint optimization of exemplars and instructions in Tab. (compared to Tab. which drops tasks with 100% accuracy both with and without instructions). The conclusion is still consistent with the main text that incorporating instructions jointly optimized to best match the chosen exemplars could improve the ICL performance, especially for difficult tasks (e.g., auto categorization, taxonomy animal, etc.).
We also provide some details on the efficient implementation of the joint optimization practice. According to Line 5 of Algorithm [] the instructions augment the search space by the size PP] This will gain us much benefit if additional computation available. Otherwise, in practice, the most straightforward implementation without increasing the computational complexity is to reduce
18

---

Table 6: Average accuracy + standard error comparison for EASE with and without jointly optimized instructions.
EASE
EASE with instructions
improvement
antonyms
90.0=ea
85.0=aa
-5.0 +
auto_ coooceegroizationn
30.0=ao
56.7=17
26.7
diff larger_aninea
100.0
100.0
0.0
100.0
100.01..0
0.0
negation
95.0zoo
100.0
5.0
73.3
75.0
1.7 0
orthography_stoee tttpppyy_sttt__tiiii
80.01o.
81.7
1.7 f
rhymes
100.0...0
100.0
0.0
second word letter
53.3
100.0
46.7 f
sentence_singg sentence_similarity
56.7=17
58.3
1.7 f
sentiment
100.0
100.0
0.0 o
sum synonyms laxonomy _nnimal translation_ent en-de translation en-es translation. en-fr word sorting
100.0
100.0
0.0
30.0
31.7
1.7 f
88.3211
100.0
11.7
90.0=ea
90.0=a.0
0.0 o
en-ees
100.0:...
100.0
0.0
88.3
85.0
-3.3 L
90.0=oou
93.3
3,3
word word__nncrammling
1..
80.0
1.7
LR (10% noise)
73.3
45.02150
-8.33
L--viriant (10% noise)
80.0#29
86.7
6.7
AG News Remap (10% noise)
51.7+1.7
65.0
13.3
SST5 Reverse (10% noise)
48.3217
53.3
5.0 f
|Q from q' to P/l More generally, one can randomly sample r x PP| instructions to pair with (r PP)) exemplar sequences. This implementation is simple yet effective, where controls the trade-off of focusing more on instructions versus exemplars.
C.3 Ablation studies the NeuralUCB and OT components
The following Tab. 7 and Tab. 8 show the necessity of both of the main components. NeuralUCB and OT, in the success of the proposed EASE algorithm. A pure subset selection algorithm based on OT performs badly on its own, especially when the noise ratio is high in the datasets. However, greatly improves the performance of NeuralUCB when used together with NeuralUCB in our EASE, This is attributed the ability to examine more permutations of the exemplars without increasing the computational cost, since only selected permutations through OT (which places an implicit bias towards more relevant exemplars) will be evaluated for the acquisition values in NeuralUCB.
C.4 Ablation studies for the speedups from OT
Carrying from the previous section about the necessity of both the NeuralUCB and OT components, we can quantify through experiments the amount speedups brought by OT. Specifically, we measure the wall clock time speedups for different sizes of the domain space Q: that sample. We experiment on one of the tasks with the longest input, AG News Remap. As shown in Tab. 9 the larger the domain space [Qrl, the greater the relative gain in the speedups. This mitigates the computational issues of applying NeuralUCB to the problem of exemplar selection and contributes positively to the success of EASE.
C.5 Ablation studies for other numbers of l:
We validate that EASE is able to select larger set of exemplars (i.e., larger k) and also from larger exemplar set of size n. We conduct comparisons EASE to the two most competitive baselines, Evo and Best-of-N, the AG News Remap and SST5 Reverse datasets of size 1000 with 10% noise.
19

---

Table Average aceuracy = standard error for ablation studies of the OT and NeuralUCB com- ponents EASE.
Table 8: Average test accuracy + standard error for ablation studies of the OT and NeuralUCB components in EASE.
Task
Noise
OT
NeuralUCB
EASE
Task
Noisc
OT
NeuralUCB
EASE
0%
50.0+ao
71.7+17
80.0+29
0%
34.0
50.7
58.0
10%
48.3117
66.7ass
13
10%
29.3+03
41,0+29
42.3+aa
LR
50%
30%
45.0100
1777
61.7g17
66.7=17
76.7
78.3::44
LR
50%
30%
23.0
30.0
49.3gt:
47.7
47.7
50.7::12
70%
38.3+13
55.0+50
66.7+17
70%
28. 7
44.0=21
47.0+32
90%
26.7+11
28.3+33
13.3+11
90%
32.0
14.7
39.0
0%
41.7
78.3
75.0zn0
0%
34. 7
56.3:41
53.0a13
10%
40.0+a0
75.0=no
80.0=29
10%
34.0
55.7
48.0114
LP-
30%
40.0+19
70.0=ao
75.0=a0
I.P-
30%
36.0gmi
48.7
50..1114
variant
50%
35.0aa9
71.7-17
78.3
variant
50%
31.0+06
49.3+26
56.7+*9
70%
35.0
70.0
:177
70%
30.3
50.3
52.0
90%
50.01s0
61.7217
66.7
90%
38.3
44.3
0%
26.7
48.3
50.0gmn
0%
12.3
29.7.n9
30.3
10%
15.0+00
51.7=33
51.7
10%
13.0
32.0:45
30.3
AG
30%
5,0
55.0:29
55.0:a0
30%
4. 7,00
32.0=a1
40.0
News
News
50%
5,0+00
41.7=33
55.0=29
50%
3.7 1oo
30.7
40.0
Remap
Remap
70%
8.31
45.0ga9
58.3
70%
7. 7,0+00
34,3+19
45.0+2a
90%
5.0ano
45.0a58
53.3
90%
2. 2.0000
26.3aa4
36.7
0%
13.3+1.
41.7=33
50,0=29
0%
9.7+a9
31.3es2
34.0
10%
15.0100
48.3144
18.
10%
9.3
37.0
31.3
SST5
30%
25.0g39
36.7244
46.7
SSTS Reverse
30%
11.7
21.3+20
24.3
Reverse
50%
15.0
38.3
46.7
50%
12. 0.00
22.3+a3
28.7=114
70%
23.3+177
53,3=33
45.0=50
70%
14.3
33.7
33.3
90%
20.0+a0
33,3=33
31.7+17
90%
16.0+06
14.3+29
19.0+6
Table 9: Wall clock time speedups of using OT. The time in the table measures the wall clock time for each iteration of the algorithms.
Domain size [Qcl
Time without OT (Sec)
Time with OT (Sec)
Speedup
5000
21,45 22
5.62
3.8x
10000
44. 162267
6.
6.4x
20000
91.39 1106
8.82
10.4x
50000
216.61
15.32=0m4
14.1x
According to Tab. 10 and Tab. II EASE performs much better than the two baselines. Therefore, EASE is able to work in other general setups with a larger & and n.
We could potentially choose more exemplars to maximize the context window, but this will incur a very high future cost of inference (i.e., the cost of actually using the exemplars for inference during production). For example, maximize the GPT-3.5-Turbo's context window of 16385 tokens (which OpenAl charges US$0.5 per 1M tokens), each inference will cost USS000081999 00819255200 and each run of the algorithm costs USS27.04 (assuming 165 iterations of query budget and 20 validation data samples). Similarly for GPT-4-Turbo with a context window of 128000 tokens (which OpenAl charges US$10 per 1M tokens), each inference of the algorithm now costs US$1.25 1.28 and each run of the algorithm costs US$4224. Therefore, while it is theoretically possible to even larger & which exhausts the context window, is not economically viable to conduct experiments or adopt such an approach in practice.
Another alternative is to allow range instead of a fixed value of be selected. That is, if 50, we can allow the number of exemplars in the prompt to be any integer from I to 50. We present additional results in Tab. 12 Firstly, EASE continues to consistently outperform the strongest baseline Best-of-N. Secondly, we also observe that the prompts with the best performance typically have large number of exemplars, i.e., close to the max & allowed. Thirdly, using à = 50 gives better performance than & = 5. Therefore, including more exemplars in the prompt usually gives higher
20

---

Table 10: Average accuracy standard error for k = 50 and n = 1000.
Table 11: Average test accuracy + standard error for k 50 and π 1000.
Evo
Best-of-N
EASE
Evo
Best-of-N
EASE
AG News Remap
50.0gss
55.0229
68.3
AG News Remap
12.7
26.3209
38.7 40.0
SST5 Reverse
58.3
56.7217
63.3
SST5 Reverse
39.0s0m
38.7
Table 12:
Results for the setting that allows different number exemplars to be selected (i.e., allowing range instead of fixed k. EASE outperforms Best-of-N. We also observe high-performing prompts usually consist of more exemplars (i.c., larger average k).
Best-of-N
EASE
Tasks
Max k
Avg. best
Acc
Avg. best
LR P.P-variant
100
60.0
5.01n0
76.7.11
4.71aa
100
600.ggn
2.7an7
71.7.11
4.3gas
AG News Remap
100
31.7237
3.0
46.7
5.0gan
SST5 Reverse
100
31.7
4.3
48.3
4.7,0s
News Remap
1000
45.0gaM
25.0
50.0
45.02t
SSTS Reverse
60.01sm
38.3
61.7.11
36.0.x
performance. However, this comes at the expense of higher query cost test time because more tokens are used in the prompt as well.
C.6 Ablation studies for the query budget
In the main text of the paper, we follow Lin 21 and set the black-box query budget to 165 evaluations. Here, we increase the query budget to 500 iterations to study the effect of the query budget on performance. We show Tab. [3 that increasing the budget generally improves performance.
Table 13: Average performance when the query budget is increased to 500 iterations. The performance increased compared to Tab. 2f of the original paper. The gaps between EASE and baselines are still significant.
Tasks (10% noise)
Evo
Best-of-N
EASE
LR
70.0
70.0
76.7
LP- Larvintt
73.3
66.7+1.
80.0
AG News Remap
40.0200
50.0400
56.7
SSTS Reverse
40.0200
41.7a1
51.7
C.7 Ablation studies for the benefit of having an ordering-aware embedding in EASE
Note that even for the same subset of exemplars, different ordering leads to different pre-trained embedding from embedding model l(.). this section, we investigate the impact capturing the ordering of the exemplars in the exemplar sequence F. To contrast the adopted approach, we propose new embedding that simply averages the embeddings of all individual exemplars in the chosen subset. So, this embedding will be invariant with regard the ordering of exemplars and call it AmgEmb, As demonstrated in Tab. 14 and Tab. [5] adopting an ordering- embedding in EASE results in better overall performance compared AvgEmd which disregards exemplar ordering.
Notably, AvgEmd presents trade-off between efficiency and effectiveness. AvgEmd is advantageous terms of efficiency as eliminates the on-the-fly embedding entirely. However, there is no free lunch: Such computational simplification comes at the cost of performance due to the loss of order information. Though not as good, note that AvgEmb still achieves decent and competitive performance. The practitioners balance the trade-off and select the most suitable method.
21

---

Table 14: Average accuracy standard error for ablation studies of using embedding without considering order.
Table 15: Average test accuracy = standard er- ror for ablation studies of using an embedding without considering order.
Task
Noise
AvgEmb
EASE
Task
Noise
AvgEmb
EASE
76.7
80.0239
0%
48.7 48.7
58.0221
10%
73.3+44
73.3
10%
48.7=1a
42.3+00
30%
70.0+a0
76.7+17
30%
53.0=4a
47.7+58
I.R
L.R
50%
68. 68.3+44
78.3+-44
50%
46.0
50.7+12
70%
66.7.1x7
66.7
70%
14.3
17.0
90%
51.7+aa
53.3+177
90%
28.7+27
39,0+1a
76.7 1m.7
75.0
0%
47.7 k33
53.0
10%
75.0+a0
80.0=22
10%
48.0
48. 18.0+25
LP-
30%
70.0+aa
75.0+am
LP-
30%
49.3+14
50.7+11
variant
50%
78.3
78.3
variant
50%
48.0
56.7
70%
75.0
71.7 1.177
70%
54.3 jna
52.01m
90%
61.7
66.7.1. 1.17
90%
38 3,.3
44.3
0%
53.3 1..7
50.0
0%
33.3 1:3
30.3
10%
50.0.s.
51.7 1.x7
10%
32.0 Lea
30.3
AG
AG
30%
51.7+aa
55.0+em
30%
29.7
40.0=1a
News
News
50%
50.0
55.0
50%
28.
40.0
Remap
Remap
70%
58.3
58.3
70%
40.0
45.0
90%
53.3aso
53.3
90%
36.32.1
36.7
0%
46.7
50.0
0%
31.0
34.0
10%
50.0
48.3
10%
31.3
31.312a
SSTS
30%
45.0a39
46.7
SSTS
30%
27.7
24.3211
Reverse
50%
48.3
46.7
Reverse
50%
33.7 114
28.7
70%
41.7144
45.0
70%
25.7
33.3
90%
31.7117
31.7
90%
13.7
19.0261
best-performing tasks
18
best-performing tasks
16
Table 16: Average accuracy + standard error when using our EASE to select exemplars for different target black-box models.
Table 17: Average test accuracy + standard error when using our EASE select exemplars for different target black-hox models.
GPT-4-
Gemini Pro
GPT-4- Turbo
Gemini Pro
Task (with 10% noise)
GPT-4-V
Task (with 10% noise)
GPT-4-V
Turbo
LR LP-variant
1.7
3.3_
83.3
0.0
0.0,u>
51.3
90.0+ao
90.0=a
31.7+1
LP-variant
83.7+13
77.7+19
14.3+14
AG News Remap
50.0
35.0az9
53.3
AG News Remap
25.7
25.7
32.7494
SST5 Reverse
21.7+17
41.7+u
36.7+u
SST5 Revense
13.3+14
28.3e1a
24.0aao
C.8 Ablation studies for optimizing exemplars for different black-box LLMs in EASE
We perform exemplar selection for other target black-box models that are GPT-3.5 which we used for all other experiments previously. We use GPT-4-V (i.e.. "gpt-4-urboo20024-04--99 with vision capability), GPT-4-Turbo (i.e., 'gpt-4-1 106-prrveee without vision capability) and Gemini Pro 41] (i.e., "gemini- 1. 1.0-prro' ") for our experiments. Tab. [6 and Tab. 17 show that our EASE is able to select effective exemplars for different black-box models. Note that the performance of GPT-4-V and GPT-4-Turbo is comparable to or worse than that of GPT-3.5 5 in some tasks. This may be attributed to significant variations in performance across different versions (i.e., checkpoints) of the GPT models. For example, existing work by Chen et al. (6] has shown that GPT-4''s mathematical ability varies lot across different checkpoints, with some exhibiting poor performance on mathematical problems. This variability partially explains the suboptimal performance of GPT-4-V and HPPT-4-Turbo on the task of LR. Additionally, worth investigating, future work, significance of exemplar selection as the LLMs continue to become increasingly powerful.
C.9 Ablation studies for using different embedding models in EASE
For our main experiments, we use MPNet as the embedding model for our EASE. Here, we use MiniLM 43 and CLIP 335 to obtain the embedding for EASE, respectively. Tab. 18 and Tab. 19
22

---

Table 18: Average accuracy standard error when using different embedding models for our EASE.
Table 19; Average test accuracy + standard error when using different embedding models for our EASE.
Task (with 10% noise)
MiniLM
CLIP
Task (with 10% noise)
MiniLM
CLIP
LR I.P-variant
73.3=17
68.3
LR I.P-variant
51.3-13
50.3+5s
76.7211
70.0229
56.3209
49.7a14
AG News Remap
43.3+11
46.7 4637
AG News Remap
29.3-22
29.3+0a
SSTS Reverse
43.3=a1
45.0+00
SSTS Reverse
29.7=64
33.3a48
Table 20: Average accuracy + standard error for ablation studies of the exploration parameter v.
Table 21: Average test accuracy + standard error
for ablation studies of the exploration parameter u.
Noise
Task
Noise
0%
75.0=so
75.0gma
71.7as
70.0aaa
0%
49.3
$3.0=sa
52.0=t
50.0es>
10%
75.0=29
80.0+1>
71.7
73.3+t
10%
46.0gi
48.0a35
51.3.3a
49.3214
LP-
30%
73.3
75.0
68.3
71.7a1
30%
49. 49.3
50.7
43.7
52.3:24
variant
50%
76.7
78.3
75.0
71.7117
variant
50%
54.3=za
56.7
50.3+21
47.0et:
70%
75.0-eo
71.7ax7
73.3
70.0saz
70%
52.0
46.0:ax
47.011
90%
63.3
66.7.11
63.3
63.311
90%
41,3gaa
44.3
36.7276
40.3211
show that our EASE achieves competitive performance using different embedding models. Therefore, EASE is general in the sense that different embedding models be used. It might be worth investigating as a future direction to develop or finetune embedding models specifically for the purpose of prompt optimization, such that it captures important aspects of the prompt in the latent space.
C.10 Ablation studies for the degree of exploration
One important hyperparameter the NeuralUCB algorithm utilized the paper is P (see (3), which controls the degree of exploration performed during the optimization process. Our finding indicates that a small v in EASE results in better exemplar selection performance. As demonstrated in Tab. 20 and Tab. 21 having our sub- samplann of the domain space Ω which is motivated by practically reducing computational complexities, and at the same time inherently serves form of exploration. Given the enormous size of the Ω sub-sampling to Q, likely generates a different exemplar sequences space within each iteration of the algorithm. This observation further supported by Bastani et al. 2 who found that a greedy algorithm can be rate optimal given sufficient randomness in the observed contexts of the bandits algorithm. Therefore, only small extent of exploration is required for EASE.
(i.e., 0.01) exploration is the best. This may be attributed to
To further support the above observation empirically, we conduct additional experiments with the domain space Q: fixed throughout. When [Qrl 1000 and fixed, observe results in Tab. 22 and Tab. 23 that a larger value of y performs better. Thus, exploration is essential when there is no randomness in the context (i.e., the domain space Q.). However, given sufficient randomness in EASE algorithm from sampling, we adopt a small v = 0.01 for optimal performance.
Table 22: Average accuracy + standard error for ablation studies of exploration in fixed domain.
Table 23: Average test accuracy + standard error for ablation studies of the exploration in fixed domain.
Noise
0%
60.0=ao
66.7417
68.3-11
66.741o
38.3
51.0as2
$3.7=xa
45.0et
10%
60.0-mm
61.7a17
66.7-17
65.0+27
10%
41.7
42.7+1a
47.0-12
49.0
LP.
30%
58.3
58.3
65.0...
65.01aa
39.3133
variant
50%
60.0g
65.0gm0
61.7ga7
66.711
variant
50%
43.3gm
47.7
41.7gM
48.7122
70%
50.0
51.7
58.3
61.7
70%
a9.7
42.0xx:
39.7
90%
36.7217
36.7
45.0as0
48.311
90%
20.72m1
22.3an
29.0g36
29.0.u
23

---

Table 24: Average accuracy standard error when asking GPT to directly output the best ex- emplars.
Table 25: Average test accuracy + standard er- when asking GPT to directly output the best exemplars.
GPT Select
GPT Select
Task (with 10% noise)
EASE
Task (with 10% noise)
EASE
LR I.P-variant
35,0+74
73.3=17
LR
29.0=no
42.3
58.3
80.0.2
LP-variant
44.0=1a
48.0+15
AG News Remap SST5 Reverse
10.0gn0
51.7
AG News Remap SST5 Reverse
12.7
30,
10.0
48.3=17
10.0.ue
31.3
Table 26: Average performance for tasks involving reasoning chains.
Tasks
Evo
Best-of-N
EASE
MATH 13
61.7a17
60.0gam
65.0
GSM8K 7
70.0
68.3
75.0=4.0
AQuA-RAT
22
46.7
43.3
48.3
C.11
Ablation studies: Asking GPT to directly select exemplars
One may wonder whether ChatGPT can directly help us select the exemplars for in-context learning. To test the possibility of directly utilizing ChatGPT, we the following prompt to query the GPT:
"You are asked to perform a task that is described by the examples below, the goal is to correctly give output based on the imput. Given the numbered list of examples below, pick 5 of them that will best serve examples for in-context learning for this task. Only output the list of numbers."
We provide all the exemplars in D in the form of numbered list to GPT together with the prompt above, and obtain the GPT-selected exemplars. We call this method GPT Select. As shown in Tab. 24 and Tab. 25 the exemplars directly selected by GPT perform worse than EASE for ICL.
C.12 Additional experiments tasks with reasoning chains open-ended generation
Note that the tasks included in the main experiments of the paper already include open-ended generation tasks. Tasks like Auto Categorization, Word Sorting, LR, and LP-variant are beyond simple direct classification-tyae type labels. For example, Auto Categorization requires outputting an open-ended sentence that categorizes the inputs well; P--vvariatt does open-ended sentence translation following a set of nontrivial rules. Therefore, our EASE demonstrates effectiveness in challenging open-ended generation tasks.
We conduct additional experiments for tasks with reasoning chains, including MATH [5 GSM8K [7]. and AQuA-RAT (22). These tasks are typically harder and involve longer responses. From Tab. 26 EASE works well for these tasks and the advantages are significant.
C.13
Additional experiments on more datasets
We conduct experiments benchmarks used in the TEMPERA 49 paper in Tab. 27 including MR, Yelp P., CR, MNLI & MRPC. Note that these tasks overly simple to distinguish the effectiveness of EASE because all of them achieve above 80% accuracy and are hard to improve further using mere in-context examples.
number of additional real benchmarks. We present results the
Therefore, we refer the reviewer to more complicated benchmarks in the main paper. Additionally, real tasks in Sec. C..22also demonstrated good performance of EASE on MATH, GSM8K & AQuA-RAT with Chain-of-Though reasoning, making the baseline comparisons in paper convincing.

---

Table 27: Average performance on benchmarks used in TEMPERA 49
Tasks
Evo
Best-of-N
EASE
MR
95.0:na
95.0:
95.0
Yelp
95.0=aa
95.0=saa
95.0=ao
CR
100.0.aa
100.0.aa
100.0..m
MNLI
81.7=13
80.0=e0
81.7+17
MRPC
81.7=17
81.7=117
81.7=17
Table 28: Average performance on Meta's 's newest open-weight model Llama-3. 3.1-8B-Instruct
Tasks (with 50% noise)
Evo
Best-of-N
EASE
LR
11.7a1
15.0=29
35.0
LP-variant
11.7.1
15.0
25.0
AG News Remap
31.7+17
31.7+17
33,3+17
SSTS Reverse
31.7=33
30.0=an
28.3+aa
C.14 Open-weight models for reproducibility
For reproducibility's sake, we conduct additional experiments with open-weight models. We use representative (Meta's newest) model Llama-3.1-4 3.--BBB1BB---. 188--nnrttutt as the target model. We present the results in Tab. 28 Importantly, the results are consistent with the original conclusions we drew for the black-box models in the paper. The model is also much smaller than GPT-3.5, hence making easier for others to deploy and reproduce the results.
C.15
Test accuracies for all tables
Tab. 30 Tab. 31 and Tab. 32 present the test accuracies for all tables presented in the main paper. Note that we report validation accuracies in the main tables because the effectiveness of the optimization strategy is directly reflected by the maximized value of the objective function in ( at the end of all iterations. Nevertheless, we show all test accuracies here for reference and completeness. The accuracy can be affected by the difference in the distribution the validation and test data, which is out of our control. This difference in distribution is significant in our case because the validation set only contains
In Tab. 29
data points (limited by the fact that querying the GPT-3.5 API expensive). This setup is disadvantageous for EASE because the optimized exemplar is "overfitted" to the validation set. This test performance is expected to improve much if we use a larger validation set (e.g., with 100 validation samples).
D Other discussions
D.1 Further validations of "onttoffddistribttion" tasks benchmarks
In Sec. we propose new families of couttof-distribution tasks that highlight the importance of high-quality exemplars. We note that nuut-of-distribution" tasks are defined loosely here as tasks which the LLM are not already well trained.
However, we cannot confirm whether a task already well-trained without access the training data. We instead perform empirical validation to show that tout-of-distrbbuiii tasks are less likely to be well-trained, and hence suitable dataset benchmarks to access the performance of algorithms. As shown in Tab. 333 and Tab. 34 we performed random exemplar in-context prompting and discovered that it achieved an average performance 17.6% for -futtof-distribution" tasks, which contrasts with the average performance of 64.7% for Instruction Induction benchmark tasks. This demonstrates that the model is likely to have less knowledge about our defined diatr----ittrbuuiinn tasks. Additionally, tasks.
can also that the performance gain of EASE is higher for
25

---

Table 29: Test accuracies counterpart of Tab. 1 over 3 independent trials.
DPP
MMD
OT
Cosine
BM25
Active
Inf
Evo
Best-of-N
EASE
active_lo to_ lo_passive
100.0...
100.0.ca
100.0 ce
100.0100
100.0.00
100.0 ao
100.0 so
100,0:.>
100.0...
100.0
antonyms
75,7
S6.0.aa
85.3
77.7
80,7
80.0g25
82.3
82.0gaa
84.3
84.7aca
auto categorization
28.7at1
25.7am0
24.0a0e
39.3
27.0gt
3277
35 0.ts
1733
30.7
34,0am1
diff
2.0
2,0
2.0ge0
2.0gn0
2.0
100.0
100.0-4m
100.0:4
100.0:a*
100.0..a
first word word_leteer
100.0.aa
100.0asa
100
100.0.0e
100.0.0m
100.0.am
100.0:3m
100.0:aa
100.0.a1
100,0
larger animal
69.0
78.7
83.7
77.7
84.0
61.0.17
84.7.a3
90.0
18.0
letters, list
100.0.4a
100.0:.a
100.0.ca
100.0
100.0
100.0
100.0-4m
100.0.4a
100.0:44
100.0:aa
negation
85,7
S7.3
1603
87.7
k3.3
85.7
83.7
86.3
85.0
19.
num, to, verbal
97.3
98.7
99.0..a
99.0.um
9600g0
-7.7-a?
98.0.an
96.7
26.7
96.
object_ counting
48.3
48, 48.3
40.7
21.0az
31.3
48 0:20
48.0
42.3
$2,3
52.0a21
orthography_Htann Sttpphy___tt_silllll with
30.3
42.0sos
65.7
65.7
710
40.3
69.3
47.0s1a
63.3
fhymes
58.0a:
42,0ana
11.3
99.0
64.3
47.3 -7
19,3
98. 3313
96.aa1
97, 2:13
second_ word letter
17.3
31,0i
42.0
42.3
27.0
45.7
40,3
38.7
48.3
sentence similarity
19.0
13.7a0
38.3
41.0zox
33.7
19.0
20.0g50
18.0g39
31,322
32.7
sentiment
91.3
87.02
90.3gm0
90.7gmt
91.7
89 89.0gam
8937
89,3
89.0
singular to plunal
100.0:4a
100.0:ea
100.D.e4
100,0
100.0:00
100.0:am
100.0-3a
100.0::4
100.0:41
100.0:4a
sum
2.0ate
2.0ats
2.0gm0
2.0
34.7
100.0.aa
100,0:4a
100.0:aa
synonyms
14.0
14.3
11.0
14.0
13.7
13.0 as
14.7.mp
13.3
18.3
13.7
taxonomy junimal
47.7
44.7
71.3
73.3
67.3g
46.3
62.3g49
32.7
73.7
78.7
translation
83.7
83.3
83.0sas
83.3
80.3-19
85.0
83.3
82.3
83.3
translation en-es
83.7
89.7.aa
88.3g0
87.3g1a
87.3
88 0gas
86.7214
84.3
84.3
84,7
translation en-ft
83.0ate
87,7am
87,3
87.0zm
87.0am
83.3
87.7
86,7
88,3
85.0a1
word_sorting
8.7
65.01sa
66.7a12
66.0ssi
43.7
14
69.3
61.3
63.3
69.7
word unserambling
61.3at3
58.7at0
63.3
$7.0ata
61.3au7
60.7-17
58.3
53.7
60,3a13
62.0a2a
e best performing tucks
6
5
7
Table 30: Test accuracies counterpart of Tab. 2 over 3 independent trials.
Type
Task
Noise
DPP
MMD
OT
Cosine
BM25
Active
Inf
Evo
Best-of-N
EASE
0%
36. 7
38.0a1a
34,0=1a
48.0au
40,7
32.0zma
43.3
38.0 38.0
47.7
58.0
10%
7,3
33.3
29.3
40.3+55
41,0-2>
0.0
46.3
38.3
47.7
42.3+aa
Rule-based basebd tasks
LR
50%
30%
12.0
3,0=10
33.7-us
23.0-as
30.0ase
45.7
43.7+zs
29.7.2x
33.3
9.0ass
0.0
35.0
47.0ea:
38.3
32.7=ms
30.3
43.0
47.7
20.7
70%
0.0
38.7
28.7
44.013s
34.0a11
1.7
31.7a3a
30.3
26.3
:2
90%
0.0gne
32.721a
32.0_aa
37.3214
2.3gas
0.0ge0
7.7g1
5.0ger
14.0gms
39.0
0%
39.3
35.0zma
34.7=s3
47.3+tu
36.3e14
34.0=sa
53.3
38.3
51.7
53.0=21
10%
0,0
37.0:as
34.0
49.0
39.3:22
39.0:oa
52.3
37.7
48.0
48.0
L.P
0.0
44.3
36.0_11
38.7143
34.3
36.7
48.0gm1
35.7
49.3
50.7
variant
50%
0,0
S3.3
31.0-ta
47.010a
34,3113
12.7as2
42.7
34.0
56.7 as
70%
0.0gn0
39.011s
30.3
46.7111
36.32a7
4.3.1s
51.021
13.3
31.3100
90%
0.0g00
35.02ns
39.7
35.3219
0.0gas
0.0gm0
41.0g10
16.7ass
28.0
24
0%
7,0
7.0
12,3=43
30.3+14
28.3e13
4.3-u
9.0e2s
11.3
30 19.3
10%
2.0
7,0,00
13.0g11
17.0140
19.0
6.0.is
13,0
12.0.az
30.0
34
Re- Re-mapped labe] tusks
News
AG
50%
30%
4.7
3.7
3.0
1.0gm0
3.7
4.7.41
27.3123
28.0100
22.3
21.3g27
8.7
7.7
13.0
5.0gns
12.3
6.7am0
21.7
28.0g50
40
40.0
Remap
70%
2. 2.0
23.3gm
7.0
20.0210
16.0aas
15.7
5.0gm1
4,7gm
36.0gns
25
90%
8.0aus
21.0at1
2.0=ae
22.7am
2.0
11.7a1
23.0sta
6.3amr
27.3
36.7
0%
137
11.7
9,7
22.0134
18.3
10.3
21.7
11.3
23.7
34.0
10%
13.3
11.3
9.3_41
20.013a
18.0
11.721
27.0gu
12.0gec
23.01ma
31.3
SSTS
30%
15.7
13.3
11.724
19.3
23.72a1
9.7gms
21.3g07
11.0ge
13.0215
24
Reverse
50%
13.0g06
12.31a3
12.0_a0
28.3139
14.0aas
12.7_a7
14.3g0
9,3201
14.0
28.7
70%
12.0g00
12.02ns
14.3
24.7am0
12.0g
11.7
18.7g
15.7
33.0210
33.3
90%
16.0zue
9.3
16.0=zx
12.7aus
13.3
12.7am
14.0
11.7am
10.7
19.0
# best-performing tasks
2
0
21
D.2 Further validations of the practical insight using OLMo
We hypothesize that the effect of exemplar selection diminishes as the model gains more knowledge about the task and is validated with progressive fine-tuning of Vicuna models in the main paper. In this section, we further supplement the experiments above with empirical evidence using the OLMo models checkpoints [2].
Upon checking the published data sources, named Dolma, of OLMo, it is likely that Instruction Induction (II) data has been included in the training source (via Common Crawl, or The Stack), Therefore, we perform additional experiments across different checkpoints (at 41k, 130k and 410k training steps) of the recent -B-0------42--f model, which released checkpoints over more than 400k steps of training. The results are presented below in Tab. 35
26

---

Table 31: Test accuracies counterpart of Tab. over independent trials.
EASE with instructions
improvement
antonyms
84.7=0.
82.0=as
-2.7 |
auto_cate cateocategorizttion
34.0a31
48.027a
14.0
diff
100,0:0a
100.0=ea
0.0
larger_animal
88.0
59.3
28.7 L
negation
89.0
88.0.aa
-1.0
52.0ga.
5.3
orthography sttrrt starts with
69.3
72.7=112
3,3 t
rhymes
97.7
68.0285
29.7
second word letter
48. 14
100.0 8.0
51.7 f
sentence similarity
32.7
32.7=227
0.0
sentiment
89 Oáo0
93.7
4.7 f
sum
100.0:0a
100.0
0.0
synonyms
13.7
14.0
0,3
taxonomy_anm _nniall
78.7
78.3
003
translationeen-de
83.3290
84.7
1.3
translation en-es
84.7=0a
89.3
4.7
translation_enee
85. $5.0210
88.0
3.0
word sorting
69.7=03
73.3
3.7
word unscrambling
62.0=2.1
62.0=115
0.0
LR (10% noise)
42.3
24.0a14a
-8.33 |
PP-variant (10% noise)
48.020.5
55.0
7.0
AG News Remap (10% noise)
30.3
51.3
21.0
SST5 Reverse (10% noise)
31.3=26
34.0
2.7
Table 32: Test accuracies counterpart of Tab. 4 over independent trials.
AG News Remap (10% noise)
SSTS Reverse (10% noise)
EASE with retrieval
EASE with retrieval
Size
EASE
Size n
EASE
1000
35.3
40.7
1000
33.0az9
35.3
10000
39.3.x4
31.3255
3000
29.0
31.7a26
50000
32.0=10
36.0=10
5000
36.7+09
37.0
100000
29.0azs
37.3
7000
23.0am.
37.3
The conclusions are consistent with Fig. of the main paper.
When the training just started (i.e., at 41k steps), the model might not be capable enough to carry out effective in-context learning.
As the training progresses (i.e., at 130k steps), we observe the best exemplar selection effectiveness. At this point, the model is capable of learning underlying relationships among the in-context exemplans, and yet to well-trained on the specific task.
As the model converges (i.e., 410k steps), the gain from exemplar selection using our EASE diminishes as the model becomes well-trained on the dataset of the respective tasks.
We also tried the rule-based tasks and remapped label tasks on OLMM-7BB-0224hh However, the in-context learning performances are always at 0% for these more difficult tasks, so comparisons are meaningful. We also look forward similar efforts as OLMo in the community open-source larger and more capable models with checkpoints in the future.
D.3 Potential limitations of the extension
we described an extension EASE using retrieval-based methods to tackle large exemplar sets. Despite the practical effectiveness and efficiency, we elaborate on some limitations here. (1) The filtering through retrieval-basee methods completely eliminates the consideration of large subset of exemplars in the later optimization stage. This may result in important exemplars being left out and
In Sec. 4.5
27

---

Table 33: The average performance of ran- dom exemplar in-context prompting in "out-of- distribution" tasks, It only achieves 17.6% accu- racy on average, indicating that the model has little knowledge about the task. The performance gain from EASE relatively large.
Table 34: The average performance of random exemplar in-context prompting in Instruction In- duction (II) tasks. achieves 64.7% accuracy average, indicating that the model has much knowledge about the task. The performance gain from EASE is relatively small.
Task
Noise
Random
EASE
Gup
Task
Random
EASE
Gap
0%
34.4
81.7
47.3
active_ _o___t_____ co_passive
100.01
100.0
0.0
10%
28.0
73.3
45.3
antonyms aulo _aalegorization
79.3
90.0gme
10.7
30%
18.2+a
78.3+14
60.1
5,4g01
30.0
24.6
50%
10.8ga1
71.7
60.9
diff
6,5
100.0
93.5
70%
4.2
66.7
62.5
first first_word, word__eetter letter
100.0gao
100.0ame
0.0
90%
0.5
53.3+an
52.8
laggrranimal
83.3
100.0
16.7
0%
46.3=s
75.0sae
28.7
letters list
100.0+00
100,0=00
0.0
10%
44.1 gen
75.0g>4
30,9
negation
94.71m0
95.0zue
0.3
30%
36.02o2
73.3
37.3
num_lo_verbal
100.0g00
100.0
0.0
50%
27.51.8
76.7137
abject_counting
52.9
73.3
20.4
70%
16.8=sa
75.0=am
58.2
authography_stare sttthh__sstttstthhhhhh with
50.7
78.3
27.6
90%
3.6eaI
63.3
59.7
rhymes
56.7
100.0ame
0%
9.2.a1
53.3216
44.1
second_ second_word__ wwrdwwwrreeeeeee
23.8
50.0=oo
26.2
10%
8.6181
56.7137
48.1
sentence siaeenccssimilaitty
20.5
56.7114
36.2
AG
30%
8.1
51.7=1A
43.6
sentiment
89.8
100.0.ae
10.2
News
50%
7.5200
56.7
49.2
singular_to _p__luralllll
100.0
100.0=ao
0.0
Remup
70%
7.0.a1
51.7
sum
12.5 100
100.0
87.5
90%
6.8esu
55.0
48.2
synonyms laxonomy annimal translation en-de translation seeeeestioneen-s _en-es trans lationtionn.. lation_en-frr en-fr word sorting
21.3
30.0ane
8.7
0%
18.8=a0
50.0=sm
31.2
51,5
88.3
36.8
10%
18.2.a1
50.0gae
31.8
84.4
90.0
5.6
SSTS
30%
17.51s1
41.7136
94.1 ins
100.0
5.9
Reverse
50%
16.9=sa
43.3+14
26.4
78. 7200
88.3
9.6
70%
16.8
45.0az2
28.2
84,5
91.7.11
7.2
90%
31.7
14.4
word unscrambling
61.5
78.3
16.8
Mean
17.6
60.4
42.8
Mean
64.7
85.0
20.3
Table 35: Average performance gap between Best-of-N and EASE on different training-step check- points of OLMo.
OLMo_4k _lk
OLMo, 130k EASE
OLMo _40k
Best-of-N
EASE
Gap
Best-of-N
Gap
Best-of-N
EASE
Gap
Object_countingg sentence siciiilrttiliitttyy
20.0a3a
31.7=17
11.7
25.0=29
35.0=29
10.0
45.0a29
46.7+17
1.7
25.01
25.0
0.0
30.0
35.0129
5.0
41.7
45.0100
3.3
orthography. starts with wrnsllttoo en-fr
21.7
26.7217
5.0
21.7am7
26.7217
5.0
26.7217
31.7217
5.0
21.7
21.7a1
38.3
43.3
5.0
35.0zu
40.0zeo
5.0
explored again in automatic optimization. (2) The cosine similarity retrieval places strong bias on preferring exemplars that are similar (in the embedding space) to the validation set, which may not yield the best performance in practice. This bias is dependent on the retrieval model and the retrieval metric used which therefore need to be carefully selected. Nevertheless, these limitations come with the simplification of the search space for practical efficiency reasons.
28

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction accurately reflect the paper's contribution and scope, with bulleted points of contributions nearing the end of the introduction (Sec. T
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The limitations of the work have been discussed in the conclusion and lim- itations (Sec. 6). The computational efficiency of the proposed algorithm discussed in
Sec. 3.2 and App. C.4
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
29

---

Answer:
[NA]
Justification:
The paper does not include theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The code is included in the supplementary materials. In the paper, the main experiment section (Sec. 4 and the section about implementation details (App. B provide all information needed to reproduce the results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
30

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Our code is available https://gtthub..cm//hbaaaag EASE MASS-PPromp-OOppimmzatioo
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://mips.cc.
aublic//uudees/Codeetubiis
www.ssssinooiiiylllooooo for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
wtweeee//ooSSSeissss.ee.e ssissssliccyy for more details. / wttps/cccppplccguui.eeaeaecccuea
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All details necessary to understand the results are provided in the main experiment section (Sec. T and the section about implementation details (App. B).
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Error bars (that indicates the standard error of the mean) are reported for all results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
31

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The computer resources utilized to produce the results in the paper are stated in App. B
The amount of compute is compared App. C.4
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpu://neurips.. http://p....ppullltcccctccccaaaa
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., s if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Broader societal impacts are discussed in App.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
32

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: No model will be released for this work and all datasets involve no risk for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging. and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
The sources of the datasets are cited in the paper.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
33

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, batasets.papersstt paperswi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The datasets are well documented in Sec. and App. B The code is well documented as well.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
34

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
35


Reviews:
[{"review_id": "y77NnaeYr3", "reviewer": "Reviewer_u1fC", "summary": "The authors propose EASE, a method for optimizing the selection of few-shot examples for prompting black-box LLMs. EASE is an iterative algorithm that combines NeuralUCB and Optimal Transport. In iteration t, EASE trains a neural network to map embeddings of strings (of few-shot examples) to their average score on a validation set. Then, they sample a subset of possible combinations of few-shot examples, filter them with optimal transport, and use NeuralUCB to select a set that maximizes their acquisition function. The selected set is evaluated and added to the pool of embedding -> score list. The authors evaluate on a set of existing tasks and a few synthetic tasks they created. Overall, the proposed method outperforms the baselines nearly across the board.", "questions": "1) The authors simultaneously find best-of-N to be highly effective as a baseline and yet argue for the importance of Optimal Transport in their method. Can we gain more insight on what OT ultimately selects under the hood? Intuition is lacking.\n\n2) What's the difference between Tables 7 and 8? What about ablations on real tasks?\n\n3) The authors say:\n> filter the large pool of data exemplars to eliminate those that are less relevant to the task. To this end, we propose to first use retrieval-based methods to select the exemplars that are more relevant to the task, and then run our EASE using this refined smaller set of exemplars. Specifically, we use a cosine similarity retriever and perform exemplar selection on D with a size n as large as 100000.\n\nWhat does this mean? What are examples that are \"more relevant\" to a task? What's the precise retrieval formulation here, i.e. what's the query and what is the corpus of documents.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) The paper overall is easy to follow.\n2) The results are very strong and the range of baselines is satisfactory.\n3) The hypothesis and synthetic task evaluation is quite valuable and insightful.\n4) The method underlying EASE is likely to spur future approaches in this space.", "weaknesses": "1) The method does not really justify why we should expect off-the-shelf embeddings (into a single unlearned vector no less) of few-shot example strings to encode enough information for NeuralUCB to work effectively. In general, off-the-shelf encoders may or may not highlight the important aspects of the prompt; they're not trained to do that. The authors discuss that embeddings will be sensitive to the ordering. This is true, but in what way do we know that such sensitivity could be leveraged effectively from a frozen task-misaligned sematic encoder?\n\n2) A lot of the discussions regarding \"retrieval-based methods\" are just forced and the paper doesn't even need them. The work shows that it's empirically more effective. That's sufficient. You don't need to argue that retrieval-based methods will \"significant additional computational overheads especially when the number of test queries is large\". That's plainly false: retrieval in the way discussed in this paper (e.g., cosine similarity) can standardly be done from billion-scale collections in 2-3 milliseconds in practice, far faster than the LLM invocation.\n\n3) Many experimental details don't seem to have been controlled for: what's the effect of the LM choice? what's the effect of the precise budget? of the training set size? of the validation set size? How large are these currently in the first place?\n\n4) The tasks selected are arguably overly simplistic and generally this means that the few-shot examples considered are all rather trivial. To my understanding, there are no reasoning chains or open-ended generation in any of the labels. There's no argument on why we should expect a method that works for simple direct classification-type labels to generalize to far more open-ended tasks. Such tasks exist plentifully; it's unclear why the authors do not consider any of them.\n\n5) The authors say: \"Our proposed Evo and Best-of-N are the most competitive baselines with best performance in 9 and 11 tasks, respectively.\" This seems to suggest that the authors believe they are the first to consider such approaches. While I think the current baselines are satisfactory, both Evo and Best-of-N approaches are components in numerous existing methods (which may involve other components), e.g. see PhaseEvo \"Unified In-Context Prompt Optimization\" for the former and DSPy's BootstrapFewShot with RandomSearch for the latter.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to review our paper and acknowledging the strong results, valuable insights, and possibility of future extension.\n\nWe will address your concerns below:\n\n> [W1] About \"off-the-shelf embeddings\"\n\nWe justify in the paper that off-the-shelf encoders are \"commonly used for downstream clustering, semantic search, and classification\". We regard **prompt optimization as a similar downstream application** that can leverage the advantages of such pre-trained encoders.\n\nAs for order sensitivity, we have a dedicated section that discusses the benefit of the ordering-aware embedding through ablation studies in App. D.6. Therefore, the sensitivity to ordering is leveraged effectively in EASE to produce better performance as compared to the order-agnostic AvgEmb.\n\nHowever, we do observe differences for different encodings: see Tab. 16 in App. D.8. According to the reviewer's comments, it is worth investigating as a future direction to develop or finetune embedding models specifically for the purpose of prompt optimization, such that it captures important aspects of the prompt in the latent space.\n\n> [W2] Retrieval is fast\n\nWe thank the reviewer for pointing out the comparatively negligible computational overhead for retrieval. **Considering the fast retrieval in practice, we would instead comment that test time computation is not needed for our method**. We also wish to highlight that the decreased privacy risks and the enhanced empirical effectiveness continue to be the advantages of our method.\n\n> [W3] Experimental details\n\nWe refer the reviewer to **App. C for all implementation details**. We reproduce them here for ease of reference.\n\nLM choice: Default is gpt-3.5-turbo-1106. In App. D.7, we also show that EASE is generally useful for different black-box models, including GPT-4-V, GPT-4-Turbo, and Gemini Pro.\n\nBudget size: Default is 165 rounds of validation evaluation (same as [14]). We conduct additional experiments by increasing the budget to 500 and show the results in Tab. A1 of rebuttal PDF. Increasing the budget improves performance.\n\nTraining set size: Default is 100 data points. In App. D.5, we increase to $n$=1000 and show that EASE is able to select a large number of exemplars from a larger training data pool.\n\nValidation data: Default is 20 validation data exemplars. Using a larger size may reduce performance variance and reduce \"overfitting\" (i.e., finding exemplars and instructions that work well only on the validation set), while having a higher cost.\n\n> [W4] Reasoning chains or open-ended generation\n\nReasoning chains: As suggested by the reviewer, we conduct **additional experiments for tasks with reasoning chains, including MATH (Hendrycks et al., 2021), GSM8K (Cobbe et al., 2021), and AQuA-RAT (Ling et al., 2017)**. From Tab. A2 of rebuttal PDF, EASE works well for these tasks.\n\nOpen-ended generation: Tasks like auto_categorization, word_sorting, LR, and LP-variant are beyond simple direct classification-type labels. For example, auto_categorization requires outputting an open-ended sentence that categorizes the inputs well; LP-variant does open-ended sentence translation following a set of nontrivial rules.\n\nTherefore, these tasks demonstrate the generalizability of EASE on various tasks of different levels of difficulty and response types.\n\n> [W5] Reference for Evo and Best-of-N\n\nWe thank the reviewer for suggesting references for Evo and Best-of-N. We will **add connections to PhaseEvo for our Evo baseline, and connections to RandomSearch implemented in DSPy for our Best-of-N baseline**. These references will serve as **stronger support** for the validity of the baselines that we compare with, and hence demonstrate the effectiveness of EASE.\n\n### Questions\n\n> [Q1] Insight on OT\n\nIntuitively, OT selects exemplar candidates such that they are on average close to the embeddings of validation exemplars in $D_V$, as measured by cosine similarity. This intuition is derived from the specific definitions of the embedding space, the cost function, and the discrete measure in Lines 179-188.\n\nThe advantages of OT are two-fold: (1) OT allows **efficient filtering of less useful exemplars** due to its computationally efficiency and (2) OT operates entirely on exemplar samples and their embeddings **without needing to query the target LLM**.\n\nIf the reviewer is referring to using Best-of-N in place of OT in our EASE, it will incur much more API calls to the target LLM. Alternatively, completely removing OT also degrades performance, as suggested in the ablation study in Tab. 7 (NeuralUCB vs. EASE).\n\n> [Q2] Tables 7 and 8\n\nTab. 7 presents the validation performance and Tab. 8 presents the test performance. We add experiments for real tasks that involve open-ended sentence answers and present the results in Tab. A3 of rebuttal PDF. The results are consistent with the original paper in that using both NeuralUCB and OT together contribute to the success of EASE.\n\n> [Q3] Retrieval formulation\n\nQuery: Validation data exemplars $D_V$\n\nCorpus: Training set exemplars in $D$\n\nRelevance: An embedding model with a cosine-similarity metric\n\nProcedure: For each validation data exemplar in $D_V$, we retrieve the most similar/relevant training set exemplars from $D$. Combine them to form a smaller set of exemplars (than $D$).\n\nTherefore, we have retrieved a small subset of exemplars from $D$ that are similar (i.e., relevant) to the validation set. Then, we proceed with EASE using this reduced subset for efficiency. We will make this clearer in the revised paper.\n\nWe hope our clarifications above have helped to improve your opinion of our work.\n\n**References**\n\n(Hendrycks et al., 2021) Measuring mathematical problem solving with the math dataset. NeurIPS.\n\n(Cobbe et al., 2021) Training verifiers to solve math word problems. arXiv.\n\n(Ling et al., 2017) Program induction by rationale generation: Learning to solve and explain algebraic word problems. ACL.", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0poeNhCISN", "reviewer": "Reviewer_FzJo", "summary": "The paper introduces EASE, a method for optimizing ICL in LLMs by selecting and ordering exemplars efficiently. Unlike retrieval-based methods that incur extra computation and privacy risks, EASE uses a neural bandit algorithm and optimal transport techniques to find high-quality ordered exemplars without test-time computation. It also extends to jointly optimize exemplars and instructions for improved performance. Empirical evaluations demonstrate EASE's superiority over existing methods across various tasks, especially where the LLM lacks task-specific knowledge. EASE proves robust in noisy data scenarios, offering a comprehensive solution for enhancing ICL in practical applications.", "questions": "- Can you provide more insights or potential solutions to mitigate the computational bottleneck caused by the on-the-fly computation of embeddings for ordered exemplar sequences?\n- While combining EASE with retrieval-based methods for large exemplar sets has shown better performance, could you elaborate on any potential limitations or challenges of this approach?", "limitations": "- The need for a suitable validation set is recognized as a limitation, as such sets may not always be readily available. This could restrict the method's applicability in certain contexts where validation data is scarce or difficult to obtain.\n- The selection of exemplars could inadvertently reinforce biases present in the training data. The authors could address how EASE mitigates bias and ensures fairness in exemplar selection, especially in sensitive applications.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The introduction of the EASE algorithm, which combines neural bandit optimization and optimal transport, is a unique approach to exemplar selection.\n- The paper includes extensive empirical evaluations, comparing EASE with a comprehensive suite of baseline methods across various tasks. The consistent outperformance of EASE underscores its effectiveness. \n- The paper provides clear explanations of the methodology, including the use of neural bandit algorithms and optimal transport, making the complex concepts accessible.", "weaknesses": "- The requirement for on-the-fly computation of embeddings for ordered exemplar sequences is identified as a potential computational bottleneck.\n- EASE relies on the availability of a suitable validation set, which may not always be readily available in certain scenarios. This requirement could limit the method's applicability in some contexts.\n- The joint optimization of exemplars and instructions, while beneficial, adds complexity to the method. The paper could provide more detailed guidance on effectively implementing this joint optimization in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to review our paper. We are glad to hear that our approach is unique, the empirical evaluations are extensive on comprehensive baselines, and our explanations are clear.\n\nFor the specific concerns and questions raised, we will address them below:\n\n> [W1] On-the-fly computation of embeddings as a potential computational bottleneck\n\n> [Q1] Insights or potential solutions to mitigate the computational bottleneck\n\nIn addition to the optimal transport (OT) introduced in EASE to reduce the on-the-fly computation of embeddings required, we can potentially eliminate the on-the-fly embedding entirely by **adopting the average embedding (AvgEmb) of individual exemplars**. However, there is no free lunch: Such computational simplification comes at the cost of performance due to the **loss of order information**. We performed ablation studies in App. D.6 to demonstrate that simply averaging the embeddings of all exemplars using AvgEmb results in worse performance. Though not as good, note that AvgEmb still achieves a decent and competitive performance. The practitioners can balance the trade-off and select the most suitable method.\n\nWhile the above approaches either use pre-trained models for on-the-fly sequence embedding or discard order information altogether, there is a potential alternative: One can try **concatenating the individual exemplar embedding** as the NN input such that the order information is captured in the concatenated embedding. However, this method may require more training data to fit the NN due to a more complex mapping (from the higher dimensional input space). Also, this method **may not scale** well when selecting a large number $k$ of exemplars.\n\n> [W2] EASE's reliance on the availability of a suitable validation set as a limitation\n\n> [L1] Especially in contexts where validation data is scarce or difficult to obtain\n\nWe clarify using a validation set is a common practice as in [4, 43, 14]. The validation dataset can be as small as 20 data samples to provide meaningful evaluations of the prompts to guide the optimization process. We used 20 validation samples for all experiments. The manual creation of a small validation set should not be very difficult or expensive.\n\nMoreover, in situations where a suitable validation set is simply not possible to obtain, it is **possible to revert to human feedback/responses**, thanks to the recent work of Lin et al. (2024). We can replace the numerical validation score with binary human feedback (i.e., asking a human to select a preferred prompt according to the responses/outputs of two prompt candidates). This greatly relaxes the requirement of a labeled validation set and only requires preference feedback from an interactive human user.\n\n> [W3] More detailed guidance on effectively implementing this joint optimization in practice.\n\nSure! We will elaborate more details of the joint optimization in the revised paper. We will provide some rough explanations here:\n\nAccording to Line 5 of Algorithm 1, the instructions augment the search space by the size $|P|$. In practice, the most straightforward implementation without increasing the computational complexity is to reduce $|Q'_t|$ from $q'$ to $q'/|P|$. More generally, one can randomly sample $r\\times |P|$ instructions to pair with $q'/(r\\times |P|)$ exemplar sequences. This implementation is simple yet effective, where $r$ controls the trade-off of focusing more on instructions vs. exemplars.\n\n> [Q2] While combining EASE with retrieval-based methods for large exemplar sets has shown better performance, could you elaborate on any potential limitations or challenges of this approach?\n\nWe thank the reviewer for recognizing our effort in using retrieval-based methods to tackle large exemplar sets. We would like to elaborate on some limitations:\n\n(1) The filtering through retrieval-based methods completely eliminates the consideration of a large subset of exemplars in the later optimization stage. This may result in important exemplars being **left out and never explored again** in our automatic optimization.\n\n(2) The cosine similarity retrieval places **a strong bias** on preferring exemplars that are similar (in the embedding space) to the validation set, which may not yield the best performance in practice. This bias is dependent on the retrieval model and the retrieval metric used which therefore **need to be carefully selected**.\n\nThese limitations come with the **simplification of the search space for practical efficiency reasons**. We will add a section to discuss the above limitations and challenges for future research and improvements.\n\n> [L2] The selection of exemplars could inadvertently reinforce biases present in the training data. The authors could address how EASE mitigates bias and ensures fairness in exemplar selection, especially in sensitive applications.\n\nFairness is an important aspect to consider as the reviewer pointed out. We would like to refer the reviewer to App. B where we emphasize the responsible deployment of our method, including integrating safety measures and ethical constraints in the objective metric. In sensitive applications, we suggest **integrating the performance objective metric with fairness** such as demographic parity, equal opportunity, equalized odds, etc. to mitigate bias in exemplar selection. The integration can be done with an adjustable hyperparameter controlling the extent of fairness to be enforced, which depends on the critical and sensitive nature of the application.\n\n\nWe hope our clarifications above have helped to improve your opinion of our work.\n\n\n**References**\n\n(Lin et al., 2024) Prompt Optimization with Human Feedback. arXiv.", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gPTnBEDi9p", "reviewer": "Reviewer_NbA9", "summary": "The paper introduces EASE (Efficient ordering-aware Automated Selection of Exemplars), a new approach to boost in-context learning (ICL) in large language models (LLMs). EASE optimizes the selection and ordering of input-label exemplars without needing model fine-tuning or test-time retrieval. EASE trains a neural network to predict the prompt performance using hidden embeddings from a pre-trained language model. Using the network as the scorer, it then employs a bandit algorithm to search for the best order exemplars for improved performance efficiently. Additionally, EASE can jointly optimize exemplars and instructions. In Instruction Induction (II) benchmark tasks and four novel out-of-distribution tasks, EASE outperforms several basic baselines, especially when the LLM has limited knowledge of the task.", "questions": "- What is the size of the dataset D? If D is small, a brute-force search could be feasible. Typically, LLMs are most beneficial when there is little to no data for downstream tasks, so a small D would be more realistic.\n- How was the NN’s uncertainty computed?\n- What method was used to tune the hyperparameters of NeuralUCB?\n- Please consider more real data such as those in the Tempera paper [3].", "limitations": "The authors could also mention the cost of hyperparameter tuning", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The problem addressed is significant, as finding a fixed set of examples and instructions that generalize well to testing time could be a valuable technique.\n- The proposed method is well-founded, incorporating a novel component that uses optimal transport to reduce the search space.\n- The performance improvement in the out-of-distribution (OOD) setting is clear.", "weaknesses": "- The main framework is quite similar to prior work [1], with only minor differences in details.\n- The literature review is inadequate, failing to cover other prompt optimization approaches, including instructions and/or example ordering (see below). Including a comprehensive related work section is crucial to highlight the novelty of the approach and justify its preference over others.\n- Due to the lack of discussion on prominent related works, it is unclear why the authors did not include them in the baseline set. The current baseline set is weak, relying only on heuristic methods. It would be better to incorporate proper optimization-based methods using RL[2,3], GA [4], or even LLM [5,6] as optimizers.\n- The current presentation of the results is unconvincing. For instance, there is no comparison in terms of running time or efficiency, areas where the paper claims to excel. The second-best baseline, Best-of-N, shows competitive results in real benchmarks. If N increases, its performance might surpass EASE. Without efficiency comparison between methods, it is hard to determine if EASE is useful.\n- Another major concern is the method seems to only work well with synthetic OOD settings. More experiments with real datasets are preferred. \n\n[1] Xiaoqiang Lin, Zhaoxuan Wu, Zhongxiang Dai, Wenyang Hu, Yao Shu, See-Kiong Ng, Patrick Jaillet, and Bryan Kian Hsiang Low. Use your INSTINCT: Instruction optimization using neural bandits coupled with transformers. In NeurIPS Workshop on Instruction Tuning and Instruction Following, 2023.\n\n[2] Mingkai Deng, Jianyu Wang, Cheng-Ping Hsieh, Yihan Wang, Han Guo, Tianmin Shu, Meng Song, Eric Xing, and Zhiting Hu. 2022. Rlprompt: Optimizing discrete text prompts with reinforcement learning. In Proceedings of the 2022 Conference on Empirical Methods in\nNatural Language Processing, pages 3369–3391.\n\n[3] Tianjun Zhang, Xuezhi Wang, Denny Zhou, Dale Schuurmans, and Joseph E Gonzalez. 2022. Tempera: Test-time prompt editing via reinforcement learning. In The Eleventh International Conference on Learning Representations\n\n[4] Archiki Prasad, Peter Hase, Xiang Zhou, and Mohit Bansal. 2023. Grips: Gradient-free, editbased instruction search for prompting large language models. In Proceedings of the 17th Conference of the European Chapter of the Association for Computational Linguistics, pages 3827–3846.\n\n[5] Yongchao Zhou, Andrei Ioan Muresanu, Ziwen Han, Keiran Paster, Silviu Pitis, Harris Chan, and Jimmy Ba. 2022. Large language models are human-level prompt engineers. In The Eleventh International Conference on Learning Representations.\n\n[6] Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V Le, Denny Zhou, and Xinyun\nChen. 2023. Large language models as optimizers. arXiv preprint arXiv:2309.03409.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to review our paper and acknowledging that we address a significant problem with a well-founded and novel method.\n\nWe would like to address your specific questions below:\n\n>[W1] Similar to [1]\n\nIn EASE, we face the challenge of an exploding permutational search space of exemplars that is distinct from [1]. A direct application of NeuralUCB would not work in practice for exemplar selection without our search space reduction technique through OT. It is also new to formulate the problem as one of optimization in the space of exemplar sequence embedding, which entirely removes the reliance on a white-box LLM as in [1]. The new formulation also enables the natural incorporation of instructions and hence the joint optimization of instructions and exemplars. Thus, the **distinct solutions of EASE come from the unique challenges in exemplar selection**. We also refer to the explanation of our distinction from [1] in Lines 159-165.\n\n> [W2] The literature review is inadequate\n\nTo clarify, we have a more extensive related works section in App. A, which expands on the ones discussed in Introduction. We will add references to RLPrompt, TEMPERA & GrIPS in our revised paper. We will have an additional page to include related works in the main paper upon acceptance.\n\n> [W3] Other related works\n\nWe thank the reviewer for the references. As long as the instruction optimization method can handle permutational search space of exemplars, they can serve as a baseline. While they are valuable references to add in our related works (we will do so for the revised paper), it is **non-trivial to adapt these works to our problem setting**, as discussed below.\n\nLLMs: APE [5] and OPRO [6] rely on LLM's generation for the instruction search space and hence are not designed for exemplar selection. It is non-trivial to adapt them for exemplar selection. Nevertheless, we **did a workaround** and adopted the same spirit of **asking the LLMs to directly select exemplars** for us by explicitly telling LLM the search space. In App. D.9, we demonstrated that EASE performs much better than asking LLMs to select exemplars.\n\nRL: The discrete optimization of a fixed-length prompt (i.e., no exemplars) in RLPrompt cannot be easily extended to our setting of exemplar optimization. TEMPERA focuses on query-dependent (vs. our query-agnostic) prompts which we argue to carry privacy risks of data exposure in Introduction paragraph 2. The formulation of TEMPERA also only supports classification tasks. So, we cannot adapt these methods to compare with EASE.\n\nGA: GrIPS only focuses on iteratively editing the instruction and does not optimize for exemplars. Specifically, it either uses a fixed set of exemplars or performs a simple heuristic random search (Sec. 5.2 & 5.8 of GrIPS). In our paper, we have in fact demonstrated the superior performance of EASE against random search in Best-of-N.\n\n> [W4] Efficiency\n\nTo clarify, EASE excels in **query efficiency instead of time efficiency** (Lines 85-90). While EASE can take longer to perform the optimization, the saving in the LLM API calls or black-box LLM queries can be substantial. So, we perform a fair comparison with the baselines in all tables using a fixed target LLM call/query budget.\n\nTo address the question of the performance for a large $N$, we perform additional experiments with $N$=500. The results are shown in Tab. A1 of rebuttal PDF. Compared to the original Tab. 2 of the paper, we see that the performance gain of EASE is still significant even though all baselines (Evo, Best-of-N, and EASE) improve with a larger budget $N$.\n\n\n> [W5][Q4] More real datasets\n\nWe highlight that EASE also works better than baselines in real datasets: In Tab. 1, EASE achieves top performance for 17 tasks while Best-of-N tops only 11.\n\nTo make the case more convincing, we conducted experiments on a number of additional real benchmarks. We present results on the benchmarks used in the TEMPERA paper in Tab. A4 of rebuttal PDF, including **MR, Yelp P., CR, MNLI & MRPC**. Note that these tasks are overly simple to distinguish the effectiveness of EASE because all of them achieve above 80\\% accuracy and are hard to improve further using mere in-context examples.\n\nSo, we refer the reviewer to **more complicated benchmarks on real tasks with reasoning chains** in Tab. A2 of rebuttal PDF, which we just experimented with during the rebuttal period. We hope that the good performance of EASE on **MATH, GSM8K & AQuA-RAT with CoT reasoning chains** makes the baseline comparisons in our paper more convincing.\n\n#### Questions\n> [Q1] Brute-force search\n\nWe note that the search space grows exponentially with the size of $D$. We use $|D| = 100$ in most experiments. However, even when $|D| = 10$, a brute-force approach is still not feasible because permuting 5 exemplars with 10 candidates yields $10^5$ possibilities. It can incur a considerable monetary cost to query the black-box API and obtain the best exemplar sequence.\n\n> [Q2] Uncertainty for NN\n\nDue to length restrictions, we will answer this separately in an official comment below.\n\n> [Q3] NeuralUCB hypers\n\nIn order to show the **robustness and generalizability to all possible tasks**, the same set of hyperparameters should perform well on all tasks. So, we fix the architecture of the NN, learning rate, weight decay, and training iterations and do not tune them. We also used the extent of exploration $\\nu=0.01$ throughout all experiments after searching from four values $[0, 0.01, 0.1, 1]$.\n\nWe hope our clarifications above have helped to improve your opinion of our work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cHvU4I51Mt", "reviewer": "Reviewer_1tAm", "summary": "The paper proposes EASE, an exemplar selection algorithm  for in-context learning of large language models (LLMs). It takes into account the order of the exemplars and offers the possibility to jointly optimize the instruction and the exemplars. A neural network is iteratively trained on the embeddings of the current exemplar sequence to predict the score of the next exemplar. The search space is reduced using a  technique based on optimal transport. The paper also empirically shows that the effect of exemplar selection is not the same for all tasks.", "questions": "- “out-of-distribution” tasks is defined as  as tasks on which the LLM is not already well trained. How are these tasks selected without access to the training data?\n- what is the effect of the length of exemplars k on performance (using a range instead of a fixed value as in D.5)?", "limitations": "There is a section on limitations in the main paper and a section on broader social impact in the appendix.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- A wide range of baseline methods and tasks are covered in the experiments.\n- The paper provides insights on the impact of exemplar selection on some specific tasks.", "weaknesses": "- The performance of EASE, which requires training a model for each task, on Instruction Induction (II) is very close to the random search baseline for most tasks.  \n- Experiments are mainly conducted on gpt-3.5-turbo-1106, an API that might include unknown pre- and post-processing. Moreover, the availability and behaviour of these APIs is not guaranteed hindering reproducibility. Consequently, the algorithm should also be validated on open-weight models (not just when doing progressive finetuning) in addition to models only available through APIs.\n\nMinor issues:\nConcerning the presentation, although the main contribution is clearly stated, the paper is structured in a way that makes it a bit hard to read. For example, the main paper lacks a dedicated related work section that would better contextualize the proposed algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to review our paper. We are glad to know that our paper has provided insights into the impact of exemplar selection through a wide range of baseline comparisons.\n\nWe would like to address the specific concerns and questions raised by the reviewer below:\n\n> [W1] Performance on II is very close to random search baseline\n\nYou are right that the random baseline performs well in Tab. 1 of Instruction Induction (II) tasks. It is not unexpected that random is a strong baseline: In particular, we highlight in second para. of Sec. 4.1 that such tasks might not be suitable for evaluation of the exemplar selection's effectiveness. This is likely **due to data contamination** where the benchmark data have been extensively used to train the target model (i.e., GPT-3.5 in our paper). Therefore, the target model easily identifies the task through exemplars (including those selected by the random baseline) and utilizes its expert knowledge on the task to answer. This explains why the choice of in-context exemplars has minimal impact on the performance in contaminated tasks. To better evaluate the effectiveness of exemplar selection, we propose three classes of tasks in Sec. 4.3 and see the significant advantages of EASE in them. We attribute the performance gain to the fact that EASE balances exploration and exploitation to be more effective under budget constraints. The above observation aligns with our insights from progressive finetuning (Sec. 4.2): As the model knows more about the task, the effect of in-context exemplars diminishes.\n\n> [W2] Validate on open-weight models for reproducibility\n\nAs suggested by the reviewer, we conduct additional experiments with open-weight models. Due to the limited time during rebuttal, we use a representative **(Meta's newest) model Llama-3.1-8B-Instruct** as the target model. We present the results in Tab. A5 of rebuttal PDF. Importantly, the results are **consistent with the original conclusions** we drew for the black-box models in the paper. The model is also much smaller than GPT-3.5, hence making it easier for others to deploy and reproduce the results. We hope this further improves the reproducibility of our results.\n\nThat said, we still advise practitioners to use the black-box models for comparison, which can be more affordable especially in academic settings (pay-as-you-go APIs vs. hosting a model on servers). We note that the black-box model is also fair for comparison because all baseline methods essentially undergo the same pre- and post-processing.\n\n> [Q1] “Out-of-distribution” tasks selection\n\nWe agree with the reviewer that we cannot confirm whether a task is already well-trained without access to the training data. We clarify that \"out-of-distribution\" tasks are **defined loosely here** (hence in **inverted commas** as mentioned in Lines 276-277 of our paper). If this is not a suitable name, we will gladly adopt another name that the reviewer deems fit; let us know!\n\nWe select these tasks with the following practical intuitions:\n\n(1) If a task contains novel rules such that the model has to extract the underlying relationships among the provided in-context exemplars and directly use the relationship for test-time inferences, it is unlikely that these tasks appear in the training dataset (Rule-based tasks in Lines 281-303).\n\n(2) If a task is constructed through random label remapping to be against the model's existing knowledge (e.g., \"good\" sentiments are mapped to \"bad\" sentiments), it is unlikely such tasks appear in the training dataset (Remapped label tasks in Lines 304-314).\n\n(3) If excessive noises are added to existing real datasets, it is likely to present a distributional shift from the original real distribution to one that the model has not seen before (Noisy tasks in Lines 315-322).\n\nTo provide more empirical evidence, we refer the reviewer to Tab. A6 & A7 of rebuttal PDF. We performed random exemplar in-context prompting and discovered that it achieved an average performance of 17.6\\% for \"out-of-distribution\" tasks, which contrasts with the average performance of 64.7\\% for II benchmark tasks. This demonstrates that the model is **likely to have less knowledge** about our defined \"out-of-distribution\" tasks. Additionally, we can also see that the performance gain of EASE is higher for \"out-of-distribution\" tasks.\n\n\n> [Q2] Using a range instead of a fixed value of $k$ as in D.5\n\nIf we understand correctly, you refer to the setting of allowing a range instead of a fixed value of $k$ to be selected. That is, if $k=50$, we allow the number of exemplars in the prompt to be any integer from 1 to 50. We present the additional results in Tab. A6 of rebuttal PDF. Firstly, EASE continues to consistently outperform the strongest baseline Best-of-N. Secondly, we also observe that the prompts with the **best performance typically have a large number of exemplars**, i.e., close to the max $k$ allowed. Thirdly, using $k=50$ gives better performance than $k=5$. Therefore, including more exemplars in the prompt usually gives a higher performance. However, this comes at the expense of a higher query cost at test time because more tokens are used in the prompt.\n\nWe thank the reviewer for pointing us to this interesting insight which we will add to the revised paper.\n\n> Minor issues: Related works and presentation\n\nWe thank the reviewer for pointing out ways to improve the presentation of the paper. With the additional page upon acceptance, we can certainly move the dedicated related work section (now in App. A) back to the main paper to ensure a better flow. We also welcome other ways to improve the structure of presentation in our paper.\n\nWe hope our clarifications above have helped to improve your opinion of our work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
# Global response

We sincerely appreciate the efforts of all our dedicated reviewers. The constructive feedback in the reviews significantly enhanced the quality of our paper. We are very grateful!

In response to the specific questions raised by the reviewers and to address potential weaknesses, we have provided a detailed reply to each of the reviewers. In these responses, we use short forms such as **"[Q1]"** to denote the first Question, **"[W1]"** to refer to the first Weakness, and  **"[L1]"** to refer to the first limitation.

In this global response to all reviewers, we have attached a PDF file with tables containing additional results to support our paper. Please refer to the individual responses for detailed explanations, and we provide a summary here:

- [*Reviewer u1fC* and *Reviewer NbA9*] We increased the query budget to 500 iterations to study the effect of the query budget on performance.
- [*Reviewer u1fC* and *Reviewer NbA9*] We showed the effectiveness of EASE on real-world open-ended generation tasks with reasoning chains.
- [*Reviewer u1fC*] We extended the ablation studies on the necessity of both OT and NeuralUCB done in App. D.3 to additional open-ended real tasks.
- [*Reviewer NbA9*] We performed experiments on additional benchmarks used in the TEMPERA paper.
- [*Reviewer 1tAm*] We provided additional results on Meta's newest open-weight model Llama-3.1-8B-Instruct to ensure better reproducibility.
- [*Reviewer 1tAm*] We adopted the new experimental setting suggested by *Reviewer 1tAm* to allow different number of exemplars to be selected. The experiments demonstrated the superiority of EASE and showed insights into the number of exemplars to be included in the prompt.

This work advances research on automatic prompt optimization in two ways: (1) As highlighted by *Reviewer FzJo* and *Reviewer NbA9*, our "EASE algorithm, which combines neural bandit optimization and optimal transport, is a **unique approach to exemplar selection**". This ensures not only query efficiency through neural bandits, but also computational efficiency by "incorporating a **novel component** that uses optimal transport to reduce the search space"; (2) As pointed out by *Reviewer FzJo*, *Reviewer NbA9*, and *Reviewer 1tAm*, our EASE "**takes into account the order of the exemplars**" and "**jointly** optimizes exemplars and instructions for improved performance", which provides researchers and practitioners a **fully automated pipeline for prompt optimization**.

Our work can significantly impact the field of prompt optimization by **bringing principled optimization and search methods** to **complement the existing** heuristic and retrieval-based approaches. We also hope to draw researchers' attention to the **ordered nature of exemplars** in the input sequence and the **joint effect** from the interactions between exemplars and instructions in the prompt. We share similar thoughts with *Reviewer u1fC* that "the method underlying EASE is **likely to spur future approaches** in this space".

Again, we would like to extend our thanks to the reviewers for their constructive feedback and valuable insights.


Best regards,

Authors of Paper 16009

Meta-review: The reviewers agreed that this is a well-written ("easy to follow", "clear explanations") paper addressing a "significant" problem with an "insightful" and "unique approach". The "extensive empirical evaluations" cover a "wide range of baseline methods and tasks" to make the performance improvement "clear". Given the unanimous agreement, I recommend this paper for acceptance.
Decision: Accept (poster)