Efficient Prompt Optimization Through the Lens of Best Arm Identification
Authors: Chengshuai Shi
Kun Yang
Zihan Chen
Jundong Li
Jing Yang
Cong Shen
Venue: NeurIPS 2024 poster (2024)
Keywords: Prompt Optimization; Best-arm Identification; Limited Budget; Large Language Models
Primary area: bandits
TL;DR: This work introduces a framework that harnesses the power of fixed-budget best arm identification to efficiently perform prompt optimization for large language models (LLMs), which achieves outstanding performance across tasks and targeted LLMs.

Abstract: The remarkable instruction-following capability of large language models (LLMs) has sparked a growing interest in automatically finding good prompts, i.e., prompt optimization. Most existing works follow the scheme of selecting from a pre-generated pool of candidate prompts. However, these designs mainly focus on the generation strategy, while limited attention has been paid to the selection method. Especially, the cost incurred during the selection (e.g., accessing LLM and evaluating the responses) is rarely explicitly considered. To overcome this limitation, this work provides a principled framework, TRIPLE, to efficiently perform prompt selection under an explicit budget constraint. TRIPLE is built on a novel connection established between prompt optimization and fixed-budget best arm identification (BAI-FB) in multi-armed bandits (MAB); thus, it is capable of leveraging the rich toolbox from BAI-FB systematically and also incorporating unique characteristics of prompt optimization. Extensive experiments on multiple well-adopted tasks using various LLMs demonstrate the remarkable performance improvement of TRIPLE over baselines while satisfying the limited budget constraints. As an extension, variants of TRIPLE are proposed to efficiently select examples for few-shot prompts, also achieving superior empirical performance.

capability of large language models (LLMs) Efficient Prompt Optimization Through the Lens of Best Arm Identification
Chengshuai Shi" University of Virginia ys7vovvirgi edu
Kun Yang" University of Virginia kyStcovirggiii.. edu
Zihan Chen University of Virginia
brf3rx@virginia. edu
Jundong Li University of Virginia jundong@virginia.eet
Jing Yang
Cong Shen
The Pennsylvania State University yangj inngjing@psu.edd
University of Virginia
cong@virginia.cmm edu
Abstract
The remarkable instruction-folet
has sparked growing interest in automatically finding good prompts, i.e., prompt optimization. Most existing works follow the scheme of selecting from a pre- generated pool of candidate prompts. However, these designs mainly foeus the generation strategy, while limited attention has been paid to the selection method. Especially, the cost incurred during the selection (e.g., accessing LLM and evalu- ating the responses) is rarely explicitly considered. To overcome this limitation, this work provides principled framework, TRIPLE, to efficiently perform prompt selection under an explicit budget constraint. TRIPLE is built on a novel connection established between prompt optimization and fixed-budger best arm identification (BAI-FB) in multi-armed bandits (MAB); thus, it is capable of leveraging the rich toolbox from BAI-FB systematically and also incorporating unique characteristics of prompt optimization. Extensive experiments on multiple well well-adopted tasks using various LLMs demonstrate the remarkable performance improvement of TRIPLE over baselines while satisfying the limited budget constraints. As an exten- sion, variants TRIPLE are proposed efficiently select examples for few-shot prompts, also achieving superior empirical performance.
Introduction
Large language models (LLMs) have rapidly changed technology landscapes our society 20 72 73. (5). Researchers continuously find effective ways unlock their potential various downstream tasks. Among different research directions, the remarkable ability of LLMs to follow instructions has motivated the study of searching for suitable prompts to interact with them (50). This approach is particularly attractive as it does not require updating the inside parameters of an LLM, and is natural in the way of human conversations. Nevertheless, it has also been recognized that the performance of an LLM is sensitive to the selected prompts [87] 52], and manually designing suitable prompts can be labor-intensiv process [54] Thus, there is growing interest to perform automatic
prompt optimization 990 79 21
19
59
58 60
81]
While these studies have proposed different prompt optimization designs, they commonly follow the approach of generating pool of candidate prompts and then selecting from them. With a deeper look, can be recognized that the focus these existing works largely leans towards how generate the candidate pool, while limited attention has been paid towards how to select from the candidates.
indicates equal contributions, random order.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

For example, many works [35 79, 28 [9] directly evaluate all the generated prompts on the entire development dataset. However, this less- ress-emphasized selection process typically requires accesses to L.Ms,, which are often (1) financially costly (e.g., each OpenAl API access incurs a cost); (2) time-wise consuming (e.g., even a locally hosted LLM would typically require seconds to respond); (3) under total usage limits (e.g., OpenAl has hard per-day and per-month limits on API accesses). Furthermore, it is often overlooked that evaluating the responses of an LLM for different candidate prompts can be costly as many tasks (e.g.. writing improvement, mathematical reasoning, etc.) would require human (and sometimes domain expert) opinions. As a result, the prompt optimization process can incur unaffordable cost without proper selection method.
To make the learning process more accessible, this work proposes to study prompt optimization under an explicitly imposed budget constraint when interacting with the targeted LLM, in addition to the previously considered requirements (e.g., discrete, interpretable, and black-box). To the best of our knowledge, budget constraints are only briefly mentioned in Zhou et al. [90]. Pryzant et al. [60], and there are no systematic or principled investigations of how to address the limited budget constraint in prompt optimization. The main contributions of this work are summarized as follows.
The constraint of limited budget is explicitly introduced into prompt optimization, which has been largely ignored before. As most of the prompt optimization methods rely on selecting from a pre-generated candidate prompt pool, we focus our study on how to carefully allocate budgets to test each candidate prompt so that the optimal one can be learned efficiently and effectively.
We propose a general solution framework, termed TRIPLE (besT aRm Identification for Prompt LErriing). by establishing a novel connection between prompt optimization and multi-armed bandits (MAB) 41) In particular,
focus on harnessing the power of fixed-budget best arm identifica- tion (BAI-FB) [4] 37) to address prompt optimization (especially, selection) with a limited budget constraint. Two representative designs TRIPLE-SH and TRIPLE-CR, inspired by celebrated BAI- FB algorithms, are presented. To improve scalability, two enhanced methods, TRIPLE-CLST and TRIPLE-GSE, are further proposed, where prompt embeddings are leveraged by exploiting the ideas of clustering and function approximation to accelerate the learning process.
Extensive experimental results are reported using well-adopted prompt tasks and varying LLMs to demonstrate the superiority of TRIPLE over previous haselines. In particular, on GPT3.5 and I. Llama2, compared with baseline methods also not using prompt embeddings, the basic TRIPLE-SH and TRIPLE-CR CR achieves performance improvements by (on average) 3% to 16%. When leveraging prompt embeddings, the enhanced ERIPLE-CLST and TRIPLE-GSE also outperform corresponding baselines by (on average) 10% to 56% with fewer prompts than budget and (on average) 16% to 45% with more prompts than budget. The gains are further evidenced on other LLMs, i.e., Gemma and Mistral. Moreover, the proposed methods can be directly plugged into two popular prompt optimization pipelines, APE (90) and APO 660, with end-to-end performances significantly improved over their original implementations.
This work extends broadly to providing new perspective of prompt optimization from MAB, and also a new application scenario of MAB in prompt optimization. This established connection may spark further innovations in both fields. As one concrete example, we extend the study optimizing the selection of examples in few-shot prompts (9, which can be recognized as a BAI-FB problem in the setup of combinatorial bandits [2). Experimental results illustrate that the extensions of TRIPLE achieve superior performance, demonstrating its rich potential.
Key Related Works. We discuss few works that explicitly or implicitly touch upon the selection efficiency in prompt optimization, and a complete literature review can be found in Appendix [A] First, Zhou et al. [90] discusses naive filtering strategy without thcoretical or empirical justifications. Chen et al. 13 leverages Bayesian optimization (BO) with expected improvement (EI) as the acquisition function to select continuous soft prompts. BO can be viewed as similar BAI while mostly focusing on infinite-arm cases (62). Moreover, Pryzant et al. (60), Lin et al. (48) use specific MAB methods targeting regret minimization to perform prompt selection, which, further illustrated in Sec. 3.3 are not well-suited as they optimize the cumulative selection performance over a period instead of the final selection output. Thus, compared with this work, existing investigations either lack a comprehensive discussion of the connection between prompt optimization and MAB or choose unsuitable MAB techniques to tackle prompt optimization. Moreover, as illustrated in Sec. S the TRIPLE solution outperforms the previously adopted methods empirically.
2

---

2 Prompt Optimization under a Limited Budget
Following Zhou et al. [90]. Chen et al. 13. we present a concrete formulation of the problem of prompt optimization. Consider that we are using an LLM f(-), which provides a mapping from any input X V to distribution Ay over the language space V. The answer Y E V given by the LLM is assumed to be sampled from f(X) as Y f(X). Note that instead of treating f()) deterministic function providing a specific output answer, we generally consider the practical setting where the answers of LLM exhibit certain level of randomness.
For prompt optimization, we aim to find a prompt p such that when concatenated with inputs of a certain task (i.e, as (p; XJ), it provides good performance in expectation with respect to the input distribution Zx and the inherent randomness of LLM f(-). The performance is measured as
ppp) == Ex-rx -(xx)
where s(X,Y) denotes score function that measures the quality of the output Y for the input X.
Motivated by the common usage scenario of LLMs,, recent studies have imposed several constraints on this learning problem [90] 58 13 28 where the three key ones are (I) black-box: the method can be applied black-box LLMs, i.e., only have access to an API f()) and no access to the intermediate structure parameters inside (including gradients, output likelihood, etc.); (II) discrete: the learned prompt must be discrete characters, instead of continuous values (i.e., soft prompts); and (III) interpretable: the learned prompt must be understandable by humans, instead of gibberish words.
Intuitively, the process of learning good prompt requires interactions with the LLM (i.e., sample Y ~ [[p: X]) and evaluating its responses (i.e., obtain score s(X XX, Y)). However, as mentioned in Sec. [ such interactions and evaluations are costly. Thus, besides the aforementioned constraints, we further explicitly take into account that the prompt optimization process should have (IV) a limited budget: the total number of trials with the LLM that happen during the learning is at most N. Finally, the prompt optimization problem considered in this work can be formulated as:
finding p" with high performance p(p") ) under constraints of black-box, discrete, interpretable, and a limited budget.
Directly tackling this prompt optimization problem has been widely recognized challenging even without the constraint of a limited budget [50]. As highlighted in Pryzant et al. [60], Chen et al. it essentially requires performing black-box discrete optimization. Instead, many proposed methods rely on the pipeline of first generating a pool of candidate prompts and then selecting from
13
35 90,
59 28 The prompt generation can either be performed manually or follow designed 79
automatic protocols. For example, the famous APE design [90] selects from prompts generated by an LLM using demonstrations. From a unified perspective, we can simplify the problem into generating a pool of prompts P and finding the optimal prompt in it:
pz = arg max pep u(p).
While many efforts have been devoted along this line, we recognize that they are largely fo-
Generate Pool Prompts (the focus of previous works)
Select a Good Prompt from P (the focus of this work)
cused on how generate prompts, while limited attention has been paid to how to select from the already generated prompts (as mentioned in
Improve the provided umail
Previously: ignore
This work: an explicit budget
Help polibh the following enai.
Interact
Evaluate
Sec. [ and further discussed in Appendix AA). Naive treatments, such as uniformly evaluating all prompts, are understandable since budget lim- itations are not considered previously, i.e., un- limited evaluations can be performed. With an explicit budget limitation, however, we need to carefully allocate the budgets to each prompt so that the optimal prompt (or least a sufficiently good one) can be correctly learned, which is the main focus of this work. An overview of the considered prompt optimization pipeline and our focus is illustrated in Fig.
Recomntructngg this email for ma.
Output Prompt
GrPS: phrose level editions
LUMs
APE: demonstrating LLMs
Potenttal Iterative Loop
The commonly adopted prompt optimization pipeline. Previous works mostly investigate the genera- tion component and ignore costs during selection. where GrIPS and APE are proposed in Prasad et al. (59), Zhou al. [90). This work. instead, focuses the selection component under explicit budget constraint.
Figure 1:
3

---

3 Connecting Prompt Optimization with Best Arm Identification
We provide new perspective of prompt optimization through the lens of tools in multi-armed bandits (MAB) [41 [4]. In particular, prompt optimization under a limited budget is shown to be intrinsically aligned with the problem of fixed-budget best-arm identification (BAI-FB) 4 37 In the following. a brief introduction to MAB is first provided. Then, the connection between prompt optimization (especially selection) and MAB (especially BAI-FB) established. Based on this connection, we propose to fully leverage the rich toolbox from BAI-FB to perform efficient prompt optimization.
3.1 Multi-armed Bandits
The research of multi-armed bandits (MAB) has long and rich history; see representative surveys of Lattimore and Szepesvári [41], Bubeck et al. [10]. The most basic form of MAB, i... the finite-armed stochastic bandits, considers a system with set K. finite arms (i.e., actions) that provide stochastic rewards when pulled. When interacting with the system, the agent can select one arm & E K. to pull at each time, and she receives stochastic reward: rh dist; (vx), where (istx(v)) denotes the action k 's reward distribution with an unknown expectation 1/k-
The learning objective of the agent in MAB can be roughly divided into two categories: (1) regret
minimization, which maximizes the expected cumulative rewards collected by the agent 5 3 26
:
(2) best arm identification, which targets at outputting the best arm k- = arg mаx 's These two objectives often require different learning strategies. Regret minimization typically relies on a carefully designed balance between exploration (i.e., obtaining new information) and exploitation (i.e., collecting higher rewards based on the previous information). Best arm identification, on the other hand, is also called pure exploration best arm. We here particularly note that although the designs targeting regret minimization often can converge to the optimal arm k- given sufficient period of time, they are known to be inefficient for the objective of best arm identification in the MAB studies.
4 27 32
it only focuses obtaining information to find the
3.2 A Bandit View of Prompt Optimization
Based on the above introduction, it can be intuitively understood that the prompt optimization (especially, selection) problem can be mapped into an MAB setting:
The pool of candidate prompts P is equivalent to the set of arms KC:
Using prompt p interact with LLM can be viewed selecting bandit arm pull in MAB;
The feedback of the score function, i.c., s(X, Y), provides the reward signal rk, where dista (P%) characterizes the randomness of X ~ Ix and Y ~ f(p; X)). The expected performance p(p) is the counterpart of the expected reward 14 in MAB.
It can be further recognized that the target of prompt optimization is more suitable to be captured as the best arm identification (BAI) problem, instead of regret minimization one, as it only cares about finding the optimal prompt p" instead of the cumulative performance of interactions performed during the learning process.
With the relationship between prompt optimiza- tion and BAI established, we further consider the constraint of learning under limited budget. We argue that this aligns with one of the main research directions in BAI called best arm identification (BAI-FB) (37 75 22]
Table 1:
Prompt Optimization and MAB.
Prompt Optimization
Multi-armed Bandits
The pool of prompts P
The arm set K. Pull arm
Interact LLM via prompt p
Score s(X, Y)
Reward ri
BAI-FB particularly considers the problem of maximizing the probability of correctly identify- ing the best arm k" while not pulling arms more than T times. It can be observed that this formu- lation matches the goal of prompt optimization under limited budget; thus BAI-FB provides
Randomness in X and Performance p(p)
Randomness in dists
Expected reward 1/2
Learn the optimal prompt under limited budget
Fixed-budger best arm identification (BAI-FB)
a perfect toolbox to enhance the commonly required prompt selection process. The connection between prompt optimization and MAB, in particular, BAI-FB, is further illustrated in Table [] To avoid confusion, the remainder of this paper, we will adopt the notation of prompt optimization as introduced in Sec. 2

---

3.3 Harnessing the Power of BAI-FB
As mentioned, we recognize that prompt optimization under a limited budget is a matching appli- cation scenario for BAI-FB. In this paper, we propose general framework called TRIPLE (besT aRm Identification for Prompt LEarning) to harness the power of BAI-FB in solving the prompt optimization problem. This is possible because BAI-FB has witnessed significant development over the years, with several efficient designs being proposed. As a first step, we choose two popular and successful BAI-FB schemes and implement them for prompt optimization, which are briefly described below. Their complete descriptions are provided in Algs. and of Appendix C
Sequential Halving (SH). SH is one of the first provably efficient BAI-FB designs [37 and remains popular after a decade of its proposal. It follows protocol that divides the total budget N into ((P)) equal-length phases. In each phase, SH uniformly tries all active prompts (initialized as P) and eliminates half of them with the lower sample means for the next phase. The final active arm is output as the identified optimal prompt.
Continuously Reject (CR). CR is a recently proposed method [75], which can be viewed as an extension of the classical Successively Reject (SR) design [4] It uniformly explores active prompts (initialized as P) and performs potential elimination of poorly-performed prompts after each pull. The elimination is based on carefully designed criteria using the Large Deviation Principle. It can be observed that, without the phased structure, CR more adaptive than SH (and SR), which makes appealing both theoretically and practically.
While MAB has found broad applications in recommender systems 44 healthcare 633, wireless communications [24], and beyond [8] a systematical connection between MAB and prompt op- timization has not been established before the best of our knowledge. which may spark new research activities (see discussions in Sec. 7 In addition, although SH and CR are selected as the representatives, the connection between prompt optimization and MAB is fundamental. Any existing or forthcoming BAI-FB designs can be flexibly incorporated into TRIPLE, e.g., the Bayesian perspective provided in Komiyama al. 388 Atsidakou al. 2
Remark 3.1. As mentioned in Sec. [ Pryzant et al. [60], Lin et al. 48 leverage specific MAB designs to perform prompt selection without comprehensive discussion above their connection. Moreover, Pryzant et al. (6) argues that UCB (5) is suitable, while Lin et al. [48) also uses a UCB- variant, NeuralUCB [89] the core method. However, both of UCB and NeuralUCB are designed for regret minimization (i.e., optimizing the cumulative interaction performance during learning). As illustrated in Sec. 3.1 designs for regret minimization cannot achieve optimal performance for the goal of identifying the optimal arm (i.e., BAI), which thus are not well-suited for prompt optimization.
4 Handling Large Candidate Pools via Prompt Embeddings
The connection built in the last section provides us with the core idea of leveraging BAII-BB designs to tackle prompt optimization. As having been theoretically established [4], solving BAI-FB without additional structures, however, will unavoidably incur an identification error that is positively related to the number of candidate prompts (P|. In other words, given a larger pool of prompts, it becomes harder find the optimal prompt with the basic BAI-FB designs, which restricts their applicability to practical prompt optimization problems (where possibly the number of prompts exceeds the budget).
The key reason behind this is that each candidate prompt is treated independently in the basic BAI-FB. Thus, budgets need to be assigned to all the prompts and no information can shared among them, which is often not the case in prompt optimization. For prompt optimization problem, the underlying task is often stable, c.g., rewriting emails, constructing TLDR, etc. The candidate prompts, regardless of their generation methods, should all reflect the purpose of the underlying task and thus share similaritics. For example, the candidate prompts generated via demonstrating LLMs (90) often share similar structures and differ only in few words word orders.
With the above observation, we target sharing information among prompts during learning. To achieve this, we propose to leverage an embedding model, denoted as embed V + Rd, to obtain the sentence embedding the prompts: e(p) := embed(p) E Rd & == (e(p) p E P). where refers to the embedding dimension. In the experiments, the OpenAl embedding API is adopted while, in general, any sufficiently expressive models can be incorporated. Also, due to this flexibility, using embedding models is fundamentally different from requiring white-box LLM B 48). With the
5

---

obtained prompt embeddings, we propose two useful enhancements to further improve the learning effectiveness when the pool of candidate prompts is large.
4.1 Leveraging Similarities via Clustering
Since the key challenge is a large pool of candi- date prompts, an intuitive idea is to effectively decrease the size of the pool. We thus propose
Algorithm TRIPLE-CLST
1: Input: the pool of candidate prompts P and their
embeddings &, overall budget N, Phase I budget
two-phased BAI-FB scheme for prompt opti- mization, In Phase I, the entire pool of candidate
N1. number of clusters L
2: Cluster P into clusters C = {C), (Ct...., ,C'} based on embeddings & (e.g., via k-means)
prompts is clustered into several groups based on their embeddings, and BAI-FB is performed on
3: Obtain C* + BAI-FB(C, Ni)
{Phase I)
the clusters with an initial target of finding the optimal cluster (or the few good clusters). Then, in Phase II, BAI-FB is performed on the prompts in the optimal cluster with the target of identifying one final prompt. For both phases, different BAI- be incorporated, e.g., SH and CR. The entire procedure, referred to TRIPLE-CLST,
4: Obtain 5" BAI-FB Ni) (Phase II)
5: Output: prompt p
FB designs is described in Alg. [
The effectiveness of TRIPLE-CLST relies on the clustering results produced in Phase I. Ideally, prompts with similar performances should be clustered together. Then, Phase can quickly eliminate the prompts with poor performances, leaving small pool of good prompts for Phase II to process. In the experiments, this intuitive phenomenon is indeed observed. In particular, in Fig. 2 as expected, prompts in the same clus- ter share similar performances. In particular, it can be observed that the prompts in the same cluster (i.e., the same color and shape) share sim- ilar performance (i.e., similar sizes). Especially, the optimal prompt (marked by the red star) is
400
Prodeted
Figure 2: Clusters for 30 prompts for "movic rec- ommendation" (left) (69] and "rhymes" (right) (30] Prompts
same cluster are labeled by the same color and shape. The performance
each prompt is represented by the size of its shape (the larger the better). The embeddings are projected using T-SNE 29
clustered together with few prompts with comparably near-optimal performances.
4.2 Sharing Information via Function Approximation
Besides clustering, another idea to incorporate the prompt embeddings to learn common function (e.g., an MI.P) to predict the prompt performances based on their embeddings. Similar ideas of function approximation have also been widely adopted MAB literature to share information among
large action spaces, with functions ranging from linear ones [1 (2) to neural networks [9]] [89. In
the setting considered in this work, we adopt a recently developed BAI-FB scheme as described in the following as TRIPLE-GSE. with details provided in Alg. of Appendix C
GSE. The general phased elimination flow of SH described
3.3 inherited. The major difference is that SH uses sample means to perform eliminations. GSE 66. on the other hand, leverages collected samples from previous phases to train reward function go Rd E that maps prompt embeddings to the predicted performance, which is further used to eliminate prompts.
Experiments
In this section, extensive experimental results are reported evaluate the efficiency of TRIPLE across diverse prompting tasks from two standard datasets: DnstructionIInduction (30) and BigBench [69] The results reported in this section are mainly collected from GPT-3.5, Llama2, Gemma, and Mistral (see the specific model numbers listed in Appendix E.I. Full experimental details can be found in Appendix The complete results of 47 tasks are reported Appendix F while here we particularly focus on 12 representative tasks, which are not too hard (i.e., all generated prompts achieve near- zero performances) or too easy (i.e., all generated prompts achieve near-one performances). The experimental codes can be found at authtps:// : h/tp:::////hhtttt www hhtp/ShhnnGruu/TRRPLLEE

---

5.1 Evaluating TRIPLE with Fixed Prompt Pools
As TRIPLE main focuses on the prompt selection component, we perform initial evaluations in an isolated fashion of selecting from fixed pools of candidate prompts. For this experiment, candidate pools of prompts are generated following the well-established APE design [90] with a high LLM temperature to ensure randomness. Then, under a limited budget, the performances of TRIPLE algorithms are compared with the following four baselines, where the latter two (i.e., BO and NeuralUCB) leverage prompt embeddings:
Uniform. Many previous designs choose to evaluate the entire candidate pool all development data 228 59 which corresponds to uniformly dividing the total budget to test all prompts.
UCB. The upper confidence bound (UCB) method is famous design for regret minimization in
MAB. We evaluate UCB using its vanilla version from Auer et al. [5], which is reported to have good performance in Pryzant al. [60]
BO. Bayesian optimization (BO) with expected improvement (EI) acquisition function is adopted Chen al. 13 which assumes a Gaussian process prior specified by prompt embeddings to perform posterior updates and makes selection to maximize EI. To further examine the performance
BO, another acquisition function, i.c. probability of improvement (PI), is also adopted.
NeuralUCB, Lin et al. [48) uses NeuralUCB [89] to perform prompt selection, which extends
UCB by training a reward function to predict prompt performances based on embeddings.
(a) [P| 30 candidates and budget N = 150: GPT-3.5 (top) and Llama2 (bottom). The reported results (y-axis) are test accuracies of cach method normalized to the mean performance of "Uniform" on that task.
25
(b) [P] 150 candidates and budget = 100: GPT-3.5 (top) and Llama2 (bottom). The reported results (y-axis) are test accuracies of each method normalized to the mean performance of "NeuralUCB" on that task.
Figure 3: Performance comparisons of various prompt selection methods on the selected tasks. The red dashed lines label the performances normalized over (i.e.. 1 on the y-axi)) and the red stars mark the best methods. The reported results aggregated 20 independent runs. The full results on 47 tasks reported in Appendix
Performance with fewer prompts than budget. We first test candidate pools with 30 prompts per task. Results reported Fig. ((a) reflect the selection performance with an overall budget of 150. It can be observed that TRIPLE-SS SH and TRIPLE-CH achieve better performance than Uniform (15% and 12% improvements on average for GPT-3.5; 15% and 16% for Llama2) and UCB (5% and 3% improvements average for GPT-3.5; 6% and 7% for Llama2). Moreover, for methods using
7

---

Table 2: Averaged performance ranks baselines and TRIPLE on the selected tasks using GPT-3.5, which are computed separately for methods using embeddings or not. The rank of BO is computed with the highest performance from BO-EI and BO-PI. The highest ranked methods are marked bold.
Setup
Without embeedlings
With embeddings
[P]. N, LLM
Uniform
UCB
SH
CR
BO
NeuralUCB
CLST
GSE
30, 150, 3.5
3.28
2,50
2,04
2.29
2.75
3.38
2.00
1,91 0.2
30, 150, Llama2
3,08 +0079
2,66 + 102
2,00 = 1.27
2.25 1.13
2.75 = 1.01
3.25 00.9
1.75 0.77
2.25 + 1,16
30, 150, Mistral
3,00 095
2,50 # 039
2.41 = 131
2,08 = 1.36
3,00 = 1.04
2.58 = 1,08
2.00 = 0.85
2.41 # 1.57
30. 130, Gemma
3.21
2,46
2.04.
2.29
2.91 1,96
3.16
2.04
1,87
150, 100, GPT 3.5
N/A
2.75 009
3.93 #0,31
1.92 = 0.49
1,53 : 0.74
150, 100, Llama2
N/A
2.68 = 1,03
3.41 2.66
1.5 + 0.64
2.25 + 1.11
150, 100, Gemma
N/A
2.75
3.16
2.33
1.75 0.75
prompt embeddings, the enhanced TRIPLE- CLST and TRIPLE-GSE also demonstrate remarkable improvements over BO-EI (11% and 10% average for GPT-3.5; 56% and 52% for Llama2) and NeuralUCB (17% and 17% improvements on average for GPT-3.5; 26% and 27% for Llama2). These results empirically evidence the superiority of TRIPLE with or without prompt embeddings.
Performance with more prompts than budget. In the above test, the budget is larger than the number of candidate prompts. We further perform experiments in more difficult setting, i.e., there are more prompts than the budget. In particular, candidate pools with 150 prompts per task are generated, and the overall budget is set as 100. In this scenario, only the methods that can leverage embeddings (i.c.. BO, NeuralUCB, TRIPLE-CKE CLST, TRIPLE-GSE) can be used, as otherwise the total budget is not sufficient to provide even one evaluation to initiate the performance estimation of each candidate prompt. Results are reported in Fig. 3(b] In particular, it can be observed that TRIPLE-CLST and TRIPLE-GSE significantly improve over BO-EI (21% and 28% on average for GPT-3.5; 31% and 42% for Llama2) and NeuralUCB (38% and 45% on average for GPT-3.5; 26% and 16% for Llama2).
summary of the averaged performance ranks of the baselines and TRIPLE is listed in Table 2 which contains results on four LLMs (i.e., GPT-3.55, Llama2, Mistral, Gemma). It can be observed that in varying setups and with different L.L,s, the proposed TRIPLE methods consistently obtain better performances than the previous baselines, remarking its efficiency and broad applicability.
Impact of the total budget. For a more comprehensive understanding, using candidate pools with 30 prompts, we further examine the impact of budgets, starting with 5 evaluations per prompt on average (i.e., 150 overall as adopted in Fig. }. and then gradually increasing to 30 (i.e., 900 overall, which is the same as the experiments in Zhou et al. (90). From the results shown in Fig. 4 we see that the improvements of TRIPLE over baselines are more pronounced with lower budgets. In particular, with budget of 10 evaluations per prompt on average (i.e., 300 overall), TRIPLE-CR, TRIPLE-CLST and TRIPLE-GSE maintain notable 9.7%, 13.5% and 17.4% improvement over Uniform, respectively: when the budget escalates to 20 evaluations per prompt on average, TRIPLE-CLST and TRIPLE-GST still achieve an approximate 8% improvement. Once the budget reaches 30 evaluations per prompt on average (i.c., 900 overall), all methods provide approximately the same performance they can all identify the optimal prompts under this generous budget.
Impact of the prompt pool size. Moreover, we investigate the prompt selection performance under prompt pools with different sizes. First, while Figs. (3a]] ((b) and Table 2 has demonstrated the superiority of TRIPLE with 30 and 150 prompts. we further enlarge the size of prompt pool size to 1000 and consider an overall budget of 500. The results reported Fig. 5 further illustrate that the improvement of TRIPLE over the baselines is consistent across the sizes of prompt pools. Also, to benefit empirical usage, we take a deep look into whether larger prompt pools are necessary to provide better candidates. From Fig. 6 it can be observed that actually the prompt performance distributions do not vary much with the pool size increased from 100 to 1000, indicating that generating a sufficiently large prompt pool (c.g., 100) is enough to further perform the selection and find the final prompt candidate to use.
5.2 Integrating TRIPLE into End-to-End Pipelines
We now explore whether TRIPLE can provide performance improvements when plugged into end-to- end prompt optimization pipelines that include both prompt generation and selection. To this end,
8

---

USB
T10 2.
Ludpe Figure 4: Gains over Uniform under different budgets on GPT-3.5.
Figure 5: |P| 1000
Figure Performance distributions on GPT-3.5 of
prompts and N = 500
prompt pools with varying sizes: "movie recommendation" (left) and "larger animal" (right).
budget on GPT-3.5.
Table 3: Performances of integrating TRIPLE in the end-to-end pipelines using GPT-3.5. The baseline methods reported in the original implementations labeled as (b). For each task, the best score across pipelines is marked as red, and the best score the remaining pipeline highlighted as yellow. TRIPLE- are selected over TRIPLE-SH due better performance observed in the previous experiments. FRILE-CLST is ignored
the tests with APO, as it is ineffective to cluster only 10 prompts.
APE 30
APO 60
Tisks
Uniform (b)
(#1) Cause and effect
0.65
0.74 0.06
0.75
0.78 1
0.78
0.80
0.80 1 0.0
(#2) Common concept
0.09 1 0.0
0.12 0.06
0.10 1 0.04
0.14 000
0.12 0.04
0.12 1 0.05
0.14 0.11
(#3) Disambiguation qa
0.83 + 0.4
0.88 0.10
0.97 + 0.00
0.96 0.00
0.95 0.04
0.98 4: 0.00
0.96 : 0.02
(#4) Gender inc. DE
1 0.17
0.10
0.12
0.84 0.144
0.69 0.22
0.80 1. 0.17
0.88 0.005
(45) Hyperhaton
0.78
0.83
0.84 40122
0.84
0.59 0.24
0.74 + 0:31
0.79 0.18
(H6) Larger unimal
0,56 + 0.24
0.64 1 0:35
0.79 0.066
0.84 :: 0.02
0.66 0.13
0.73 4 0.18
0.85 4:0.0 0.15
(#7) Movie recommnendation
0.61 1.112
0.65 1 0.18
0.76 1 0.06
0.74 0.144
0.67 0.111
0.65 1 0.15
0.71 1 0.15
(MS) Object counting
+
+ 0.08
+ 0.0
+
0.44 0.08
0.50
+ 0.00
Orthography
with
0.41 1:
0.65 0.16
0.67 1:
0,66
0.58 0.13
0.64 1:
0.67
(H10) Question selection
0.90 + 0.04
0.91 + 0.03
0.95 + 0.01
0.93 = 0.03
0.93 + 0.06
0.92 + 0.06
0.93 + 0.03
(#11) Rhymes
0.66 + 0.30
0.68 + 0.36
0.75 0.200
0.78 = 0.16
0.78 +
0.83 + 0.08
0.85 + 0:13
Snarks
1: 0.10
0.52 1 0.19
0.57 0.10
:: 0.21
0.49 1:
1: 0.15
1: 0.00
Avg. Performance Rank
4,00
2,92 + 0.38
1,58
1,50
2.75 0.44
2.00 + 0.71
1,25 0.48
two end-to-end designs are considered, aiming to assess the performance of TRIPLE in more fluid and iterative settings, which are discussed in the following with our implementation details.
APE. Proposed by Zhou et al. [90]. the APE pipeline lets LLMs generate prompt candidates and then selects from them. In our experiments, for each task, following original templates, 30 prompts are generated, followed by different methods to perform selection with a budget of 5 evaluations per prompt average (i.e., 150 LLM accesses overall). Zhou al. [90] suggest non-iterative version with uniform evaluations of prompts, which is taken as the bascline here.
APO. The APO pipeline (60] is iterative one, letting LLMs criticize the previous prompts. Here, following the original templates, three iterations are performed and 10 prompts are generated per iteration. Different selection methods are then tested with budget of 50 per iteration so that an overall budget of 150 is used, aligning with that of APE. Pryzant et al. [60] have reported UCB as the most effective prompt selection method, which adopted as the baseline here. We note that OPRO [8]] shares similar iterative scheme APO while using different component to improve prompts. Due to their similarity, the experiments are mainly focused on APO here, while TRIPLE can also be flexibly integrated with OPRO.
The end-to-end experiment results are reported in Table 3 which reveal the consistently better performance of TRIPLE over the originally adopted baseline methods. This observation highlights the applicability and flexibility the TRIPLE framework, i.e., it can benefit any prompt optimization pipelines requiring a selection component.
Extension: Selections of Examples for Few-shot Prompts
Based on the general connection between prompt optimization and BAI-FB, the power of TRIPLE can be further extended beyond finding one good instructional prompt. In the following, we provide discussions how to leverage TRIPLE to efficiently select examples for few-shot prompts.

---

As noticed in Brown et al. 19, LLMs can perform varying tasks when prompted with several related examples, i... few-shot prompting. has been widely recognized that a good choice of examples in few-shot prompts is important to obtain good downstream performances [49 52 Using the terminol- ogy introduced in Sec. | we can formulate the problem of example selection as follows. From set of examples 9, we target at selecting M examples (01, .9M) to form few-shot prompt, whose performance is measured as plg11.... .9M) == Ex~Ix B "ath:: x))x (xX, Y)). The optimal selection of examples can be defined as ( ... .hs) == arg max S1." ar (1( ... .9M)
From the MAB perspective, the learning target can be interpreted as finding the optimal combination of M arms from the overall arm set G, which the focus of the study on combinatorial MAB (CMAB) [6 15 18) Then, TRIPLE can be further extended to incorporate BAI-FB designs from CMAB to perform the desired example selection. In particular, based on some heuristics on the performance p(g1. ... : .gM). TRIPLE-SAN and TRIPLE- RRALE-CSARR are proposed, extending Chen et al. [14, Gabillon et al. [23], which are further discussed in Appendix [ The performances of these extensions are presented in Table with more details and results provided in Appendix E.6 and
Table 4: Performance comparisons of various example selection methods on different tasks using GPT-3.5
with
50 candidate examples, budget = 100, and length M 4. The tasks are numbered according to For each task, the best score across is marked as red, and the second best as yellow.
Table
Tusks
Random
Uniform
SAR
CSAR
Tasks
Random
Uniform
SAR
CSAR
#1
0.65+ 0:07
0.63 0.13
0.67=am7 0.07
0.66: om
#7
0.98 0.03
L.0+ 0.00
100+ 0:00
1,00 0.00
W2
0,264 0.05
0.244 0.07
0.27 0.07
0.35+ 0.02
0.40# 0.8
0.38+ 0.05
0.42
#3
0.83+
0.904
0.934 0.07
0.53+
0.64+ 0.12
0.65+ 0.12
0.63+ 014
#4
0.96+ 0.02
0.964
0.97+ 0.01
0.97
#10
0.844
0,91 0.05
0.95+ 0.01
0.94 o.s
#5
0.734 0.11
0.804 0.05
0.734 0,85
0.84 0.10
#11
0.41
0.824 0.20
0.6841 0.13
0.87+ 0.20
#6
0.78+ 0.10
0.794 0.11
0.844 0.04
0.82+ 0.44
#12
0.65+ 0.08
0.564 0.07
0.62+ 0.12
0,70+ 0.09
Avg. Performance Rank
3.75
2.831 0.69
2.08 0.86
1.33 0.47
7
Conclusions
Prompt optimization is an important problem for large language models (LLMs), but prior research has not considered the potential cost during prompt selection. We have explicitly incorporated budget constraint to prompt optimization, and studied the problem of how to efficiently select prompts with the given budget. A systematical connection between multi-armed bandits (MAB) and prompt optimization was established. Through this lens, we proposed a general framework, termed TRIPLE, to fully harness the power of fixed-budget best arm identification (BAI-FB) to perform prompt optimization. Besides standard BAI-FB designs, two embedding- based enhancements were proposed to accelerate learning. Extensive experimental results demonstrated the superiority of TRIPLE over multiple representative tasks and various targeted LLMs. Furthermore, we showed that TRIPLE could be plugged into popular end-to-end prompt optimization pipelines, with better performance than previous implementations, demonstrating its effectiveness and flexibility.
In addition to the technical contributions, we believe that the connection between prompt optimization and MAB may be of broader interest. It not only provides a rich set of tools from MAB to advance prompt optimization but also introduces new application scenario for MAB (especially BAI) research. In particular, the discussed extension to the selection of examples for few-shot prompts demonstrates the rich potential of TRIPLE. As future steps, the research on contextual bandits [44 may provide insights into selecting input-dependent prompts (78). Also, the application of prompt optimization may spark new research efforts in MAB, e.g., efficient BAI methods for correlated arms.
10

---

Acknowledgments and Disclosure of Funding
The work of CSs, KY, and ZC was supported part by the US National Science Foundation (NSF) under awards CNS-2002902. ECCS- 2029978, ECCS-2143559, and CNS-2313110 and the Bloomberg Data Science Ph.D. Fellowship. The work of JY was supported part by the US NSF under awards CNS-1956276 and CNS-2114542.
References
[1] Abbasi-Yadkori, Y., Pál, D.,, and Szepesvári, C. (2011). Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24.
[2] Atsidakou, A., Katariya, S., Sanghavi, S., and Kveton, B. (2022). Bayesian fixed-budget best-arm identification. arXiv preprint arXiv:2211.0877..
[3] Audibert, J.-Y., Bubeck, S., al. (2009). Minimax policies for adversarial and stochastic bandits. COLT, volume 7, pages 1-122.
[4] Audibert, J.-Y., Bubeck, S., and Munos, R. (2010). Best arm identification in multi nulti-armed bandits. COLT, pages 41-53.
[5] Auer, P., Cesa- Dosaa-Binnchi, N., and Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine learning, 47:235 256.
[6] Azizi, J. Kveton, B., and Ghavamzadeh, M. (2023). Fixed-budget best-arm identification in structured bandits. arXiv preprint vrXiv:2106.04763
[7] Bergstra, J., Bardenet, R., Bengio, Y., and Kégl, B. (2011). Algorithms for hyper-parameter optimization. Advances in neural information processing systems, 24.
[8] Bouneffouf, D. and Rish, I. (2019). A survey on practical applications of multi-armed and contextual bandits. arXiv preprint 1904
[9] Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. (2020). Language models are few-shot learners. Advances neural information processing systems, 33:1877-1901.
[10] Bubeck, S., Cesa-Bianchi, N., et al. (2012). Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends@ in Machine Learning, 5(1):1-122.
[11] Bubeck, S., Chandrasekaran, V., Eldan, R., Gehrke, J., Horvitz, E., Kamar, E., Lee, P., Lee, Y. T., Li, Y., Lundberg. S., et al. (2023). Sparks of artificial general intelligence: Early experiments with gpt-4. arXiv preprint 2rXiv:2303.12111
[12] Bubeck, S., Wang, T., and Viswanathan, N. (2013). Multiple identifications in multi-armed bandits. In International Conference on Machine Learning, pages 258 268-265.77 PMLR.
[13] Chen, L., Chen, J., Goldstein, T., Huang, H., and Zhou, T. (2023). Instructzero: Efficient instruction optimization for blx large language models. arXiv preprint arXiv:2306.03082.
[14] Chen, S., Lin, T., King, I., Lyu, M. R., and Chen, W. (2014). Combinatorial pure exploration of multi-armed bandits. Advances in neural information processing systems, 27.
[15] Chen, W., Hu, W., Li, F., Li, J., Liu, Y., and Lu, P. (2016). Combinatorial multi-armed bandit with general reward functions. Advances in Neural Information Processing Systems, 29.
[16] Chen, W., Wang, Y., and Yuan, Y. (2013). Combinatorial multi-armed bandit: General frame- work and applications. In International conference on machine learning, pages 151-159. PMLR.
[17] Cobbe, K., Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, L., Plappert, M., Tworek, J., Hilton, J., Nakano, R., Hesse, C., and Schulman, (2021). Training verifiers to solve math word problems, arXiv preprint arXiv:2110.14163

---

[18] Combes, R., Talebi Mazraeh Shahi, M. S., Proutiere, A., et al. (2015). Combinatorial bandits revisited, Advances neural information processing systems, 28.
[19] Deng, M., Wang, J., Hsieh, C.-P., Wang, Y., Guo, H., Shu, T., Song, M., Xing, E. P., and Hu, Z. (2022). Riprompt: Optimizing discrete text prompts with reinforcement learning. arXiv preprint arXiv:2205.122 12548.
[20] Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. (2018). Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805.
[21] Diao, S., Huang. Z., Xu, R., Li, X., Lin, Y., Zhou, X., and Zhang, (2022). Black-box prompt learning for pre-trained language models, arXiv preprint arXiv:2201.08533
[22] Gabillon, V., Ghavamzadeh, M., and Lazaric, A. (2012). Best arm identification: A unified approach to fixed budget and fixed confidence. Advances in Neural Information Processing Systems, 25.
[23] Gabillon, V., Ghavamzadeh, M., Lazaric, A., and Bubeck, S. (2011). Multi-bandit best arm identification. Advances in Neural Information Processing Systems, 24.
[24] Gai, Y., Krishnamachari, B., and Jain, R. (2012). Combinatorial network optimization with un- known variables: Multi-armed bandits with linear rewards and individual observations. JEEE/ACM Transactions on Networking. (416))1466-1788
[25] Gao, T., Fisch, A., and Chen, D. (2020). Making pre-trained language models better few-shot learners. arXiv preprint arXiv:2012.15723.
[26] Garivier, A. and Cappé, O. 1). The kl-ucb algorithm for bounded stochastic bandits and beyond. In Proceedings of the 24th annual conference on learning theory, pages 359-376. JMLR Workshop and Conference Proceedings.
[27] Garivier, A. and Kaufmann, E. (2016). Optimal best arm identification with fixed confidence. Conference on Learning Theory, pages
PMLR.
[28] Guo, Q., Wang, R., Guo, J., Li, B., Song, K. Tan, X., Liu, G., Bian, J., and Yang, Y. (2023). Connecting large language models with evolutionary algorithms yields powerful prompt optimizers. arXiv preprint 230..22300.08533.
[29] Hinton, G. E. and Roweis. S. (2002). Stochastic neighbor embedding, In Becker, S., Thrun, S., and Obermayer, K., editors, Advances in Neural Information Processing Systems, volume 15. MIT Press.
[30] Honovich, O., Shaham, U., Bowman, S. R., and Levy, O. (2022). Instruction induction: From few examples to natural language task descriptions, arXiv preprint arXiv:2205.10782
[31] Hu, W., Shu, Y., Yu, Z., Wu, Z., Lin, X., Dai, Z., Ng. S.-K., and Low, B. K. H. (2024), Localized zrdee prompt optimization. arXiv preprint arXiv:2403.02990 02993..
[32] Jamieson, K. and Nowak, R. (2014). Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting. In 2014 48th Annual Conference on Information Sciences and Systems (CISS), pages 1-6. IEEE.
[33] Jedra, Y. and Proutiere, A. (2020). Optimal best-arm identification in linear bandits. Advances Neural Information Processing Systems, 33:10007-10017.
[34] Jiang, A. Q., Sablayrolles, A., Mensch, A., Bamford, C., Chaplot, D. S., de las Casas, D., Bressand, F., Lengyel, G., Lample, G., Saulnier, L., Lavaud, L. R., Lachaux, M.-A., Stock, P., Scao, T. L., Lavril, T., Wang, T., Lacroix, T., and Sayed, W. E. (2023). Mistral 7b.
[35] Jiang, Z., Xu, F. F., Araki, J., and Neubig, G. (2020). How can we know what language models know? Transactions of the Association for Computational Linguistics, 8:423-433.
[36] Kanarios, K., Zhang, Q., and Ying, (2024). Cost aware best arm identification. arXiv preprint 17X1122402.16710
12

---

[37] Karnin, Z., Koren, T., and Somekh, O. (2013). Almost optimal exploration in multi- aumti-armed bandits. In International conference on machine learning, pages 1236. PMLR.
[38] Komiyama, J., Ariu, K., Kato, M., and Qin, C. (2023). Rate-optimal bayesian simple regret in best arm identification. Mathematics of Operations Research.
[39] Kone, C., Kaufmann, E., and Richert, L. (2024). Bandit pareto identification: the fixed budget setting. In International Conference on Artificial Intelligence and Statistics, pages 2548-2556. PMLR.
[40] Lai, L.. and Robbins, H. (1985). Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22.
[41]
Lattimore, T. and Szepesvári, C. (2020). Bandit algorithms. Cambridge University Press.
[42] Lester, B., Al-Rfou, R., and Constant, N. (2021). The power of scale for parameter-efine efffiietr-efficientt prompt tuning. arXiv preprint arXiv:2104.08691,
[43] Levy, I., Bogin, B., and Berant, J. (2023). Diverse demonstrations improve in-context com- positional generalization. Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1401-1422.
[44] Li, L.. Chu, W. Langford, J., and Schapire, R. E. (2010). A contextual- approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 661-670
[45] Li, Lv, K., Yan, H., Lin, T., Zhu, W., Ni, Y., Xie, G., Wang. X., and Qiu, X. (2023). Unified demonstration retriever for in-context learning. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Pupers), pages 4644-4668
[46] Li, X. L. and Liang, P. (2021). Prefix-tuning: Optimizing continuous prompts for generation. arXiv preprint arXiv:2101.001 00000000
[47] Lin, X., Dai, Z., Verma, A., Ng. S.-K., Jaillet, and Low, K. H. (2024). Prompt optimization with human feedback. arXiv preprint arXiv:2405.17344
[48] Lin, X., Wu, Z., Dai. Z., Hu, W., Shu, Y., Ng. S.-K., Jaillet, P., and Low, B. K. H. (2023). Use your instinct: Instruction optimization using neural bandits coupled with transformers. arXiv preprint
[49] Liu, J., Shen, D., Zhang, Y., Dolan, B., Carin, L., and Chen, W. (2021a). What makes good in-context examples for gpt-3? arXiv preprint 000:21011.6804
[50] Liu, P., Yuan, W., Fu, J., Jiang, Z., Hayashi, H., and Neubig, G. (2023). Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing. ACM Computing Surveys, 1-35):
[51] Liu, X., Ji, K., Fu, Y., Tam, W. L., Du, Z., Yang, Z., and Tang, J. (2021b). P-tuning v2: Prompt tuning can be comparable to fine-tuning universally across scales and tasks. arXiv preprins 2Xiv:2/10.07660
[52] Lu, Y., Bartolo, M., Moore, A., Riedel, S., and Stenetorp, P. (2021). Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity. arXiv preprint arXiv:2104.0877 00400886.
[53] Min, S., Lyu, X., Holtzman, A., Artetxe, M., Lewis, M., Hajishirzi, H., and Zettlemoyer, L. (2022). Rethinking the role of demonstrations: What makes in-context learning work? arXiv preprint 12837
[54] Mishra, S., Khashabi, D., Baral, C., Choi, Y., and Hajishirzi, H. (2021). Reframing instructional prompts to gptk's language. arXiv preprint arXiv:2109.08800.
[55] OpenAl (2023a). Gpt-3.5-turbo.
https://platfores openai. www/docssmooelll.. htt.://c..oppaaa..cooo//////ooeo
gpt-3-5 3-5 Accessed: 2024-01-29.
13

---

[56] OpenAl (2023b). sext-emmeeddngg-dd--0000 models/embedding: Accessed: 2024-01-29.
https://platform.. opw.aa...aaaaaaaaaeeeoeoooo
[57] Opsahl-Ong, K., Ryan, M. J., Purtell, J., Broman, D., Potts, C., Zaharia, M., and Khattab, O. (2024). Optimizing instructions and demonstrations for multi-stage language model programs. arXiv preprint urXiv:2406. 1695.
[58] Pan, R., Xing, S., Diao, S., Liu, X., Shum, K., Zhang, J., and Zhang, T. (2023). Plum: Prompt learning using metaheuristic. arXiv preprint arXiv:2311.0836.
[59] Prasad, A., Hase, P., Zhou, X., and Bansal, M. (2022). Grips: Gradient-free edit- bdst-based instruction search for prompting large language models, arXiv preprint arXiv:2203.07286
[60] Pryzant, R., Iter, D., Li, J., Lee, Y. T., Zhu, C., and Zeng, M. (2023). Automatic prompt optimization with "gradient descent" and beam search. arXiv preprini arXiv:2305.08 00445.
[61] Rubin, O.. Herzig, J., and Berant, J. (2022). Learning to retrieve prompts for in-context learning. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 2655 1675-2671.
[62] Shahriari, B., Swersky, K., Wang, Z., Adams, R. P., and De Freitas, N. (2015). Taking the human out the loop: A review of bayesian optimization. Proceedings of the IEEE, 104(1); (04(1):148-177) 145-175.
[63] Shen, C., Wang. Z., Villar, S., and Van Der Schaar, M. (2020), Learning for dose allocation in adaptive clinical trials with safety constraints. In International Conference on Machine Learning. pages 8730-877 8740. PMLR.
[64] Shi, W. Han, X., Gonen, H., Holtzman, A., Tsvetkov, Y., and Zettlemoyer, L. (2022). Toward human readable prompt tuning: Kubrick's 's the shining is a good movie, and a good prompt too? arXiv preprint arXiv:2212.10532
[65] Shin, T., Razeghi, Y. Logan IV, R. L., Wallace, E., and Singh, S. (2020). Autoprompt: Eliciting knowledge from language models with automatically generated prompts. arXiv preprint 20li::0010.199000
[66] Soare, M. Lazaric, A., and Munos, R. (2014). Best-arm identification in linear bandits. Advances Neural Information Processing Systems, 27.
[67] Su, H., Kasai, J., Wu, C. H., Shi. W., Wang, T. Xin, J., Zhang, R., Ostendorf, M., Zettlemoyer, L., Smith, N. A., al. (2022). Selective annotation makes language models better few-shot learners. arXiv preprint arXiv:2209.01975
[68] Sun, H., Hüyük, A., and van der Schaar, M. (2023). Query-dependent prompt evaluation and optimization with offline inverse rl. arXiv e-prints, pages arXiv-2309.
[69] Suzgun, M., Scales, N., Schärli, N., Gehrmann, S., Tay, Y., Chung, H. W., Chowdhery, A., Le, Q. V., Chi, E. H., Zhou, D., et al. (2022). Challenging big-bench tasks and whether chain-of- thought can solve them. arXiv preprint arXiv:2210.09261
[70] Team, G., Mesnard, T., Hardin, C., Dadashi, R., Bhupatiraju, S., Pathak, S., Sifre. L., Rivière, M., Kale, M. S., Love, J., et al. (2024). Gemma: Open models based on gemini research and technology. arXiv preprint arXiv:2403.088
[71] Thompson, W. R. (1933). On the likelihood that one unknown probability exceeds another in view of the evidence of samples. Biometrika, 25(3/4):285-294
[72] Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F., al. (2023a). Llama: Open and efficient foundation language models. arXiv preprint or Xiv: 13971.
[73] Touvron, H., Martin, L., Stone, K., Albert, P., Almahairi, A., Babaei, Y., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., et al. (2023b). Ilama 2: Open foundation and fine-tuned chat models. arXiv preprint a7Xiv:2307.09288.
14

---

[74] Wang, A., Singh, A., Michael, J., Hill, F., Levy, O., and Bowman, S. R. (2019). GLUE: A multi- task benchmark and analysis platform for natural language understanding. In the Proceedings of ICLR.
[75] Wang, P.-.., Tzeng, R.-C., and Proutiere, A. (2023). Best arm identification with fixed budget: A large deviation perspective. arXiv preprint arXiv:2312.12137.
[76] Wei, J., Wang. X., Schuurmans, D., Bosma, M., Xia, F., Chi, E.,, Le, Q. V., Zhou, D., et al. (2022). Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-24837.
[77] Wen, Y., Jain, N., Kirchenbauer, J.. Goldblum, M., Geiping, J. and Goldstein, T. (2023). Hard prompts made easy: Gradient-based discrete optimization for prompt tuning and discovery. arXiv preprint arXiv: 230.v2230..0366.
[78] Wu, Z.., Wang, S., Gu, J., Hou, R., Dong, Y., Vydiswaran, V., and Ma, H. (2022). Idpg: An instance-dependent prompt generation method. arXiv preprint arXiv:2204. 044997.
[79] Xu, H., Chen, Y., Du, Y., Shao, N., Wang, Y., Li, H., and Yang, Z. (2022). Gps: Genetic prompt search for efficient few-shot learning. arXiv preprint arXiv:2210.17041.
[80] Xu, S. and Zhang, C. (2024). Misconfidenne--aseed demonstration selection for Ilm in-context learning. arXiv preprint arXiv:2401.0630)
[81] Yang, C., Wang, X., Lu, Y., Liu, H., Le, Q. V., Zhou, D., and Chen, X. (2023). Large language models as optimizers. arXiv preprint urXiv:2309.33409
[82] Yang. J. and Tan, (2022). Minimax optimal fixed-budget best arm identification in linear bandits. Advances in Neural Information Processing Systems, 15:12253-12266
[83] Yavas, R. C. and Tan, V. Y. (2023). Fixed-budget best-arm identification in sparse linear bandits. arXiv preprint arXiv:2311.0044
[84] Zhang, T., Wang. X., Zhou, D., Schuurmans, D., and Gonzalez, J. E. (2023a). Tempera: Test- time prompt editing via reinforcement learning. In The Eleventh International Conference on Learning Representations.
[85] Zhang, Z., Wang, S., Yu, W., Xu, Y., Iter, D., Zeng, Q., Liu, Y., Zhu, C., and Jiang, M. (2023b). Auto-instruct: Automatic instruction generation and ranking for black-box language models. arXiv preprint ar arXiv:2310.13127.
[86] Zhang, Z., Zhang, A., Li, M., and Smola, A. (2022). Automatic chain of thought prompting in large language models. arXiv preprint arXiv:2210.0349.
[87] Zhao, Z., Wallace, E., Feng, S., Klein, D., and Singh, S. (2021). Calibrate before use: Improving few-shot performance of language models. In International Conference Machine Learning, pages 12697-12706. PMLR.
[88] Zhong, 7., Friedman, D., and Chen, D. (2021). Factual probing is [mask]: Learning vs. learning recall. arXiv preprint arXiv:2104.05240.
[89] Zhou, D., Li, L., and Gu, Q. (2020). Neural contextual bandits with ucb-based exploration. In International Conference on Machine Learning, pages 1 11492-11 1502.. PMLR.
[90] Zhou, Y., Muresanu, A. I., Han, Z., Paster, K., Pitis, S., Chan, H., and Ba, J. (2022). Large language models are human-level prompt engineers. arXiv preprint 11X11:2211.01910.
[91] Zhu, Y., Zhou, D., Jiang, R., Gu, Q., Willett, R., and Nowak, R. (2021). Pure exploration in kernel and neural bandits. Advances in neural information processing systems, 34:1 14:11618-11160.
15

---

A Related Works
The study of prompt optimization (also known as instruction learning) focuses on automatically learning suitable prompts, which is more scalable compared with manual
Prompt Optimization.
prompt engineering. Many efforts have been devoted to this direction [25] 77
68
86
85 which
is summarized in recent survey of Liu et al.
[50]. The early studies mostly consider optimizing
soft prompts (i.c., continuous vectors) [42 46
51 78 or discrete but not interpretable prompts 665 [4] for white-box LLMs, where different gradient-guiedd optimization techniques are leveraged.
88
The recent research efforts, instead, are more focused on considering the more practical setting of
learning interpretable prompts for black-box LLMs [59 900 60 79 28
58
[3], where the generating-
then-selecting pipeline in Fig. Dis often adopted.
Compared with previous investigations, this work additionally considers limited budget in an explicit fashion, which we believe a practical but under-investigated concern. Most of the previous
methods perform selection based on evaluating prompts on all development data R5 79 28 [59].
which is unavoidably costly. APE [90] briefly touched on the cost issue by proposing a naive iterative
top filtering strategy (which however is suggested to have only marginal benefits). APO [60] tested
few MAB methods, including two classical BAI-FB designs, i.e., SH [37 and SR [3], and reported that the performance of UCB is the more favorable. However, it neither formally introduces the budget constraint nor provides a systematical connection to BAI-FB as in this work. Also, this work goes much deeper in incorporating the state-of-the thrt art BAI-FB designs (i.e., CR (75 and GSE (6) and proposing embedding- baseed enhancements. It is worth noting that INSTINCT 48] also incorporates one MAB method, i.e., NeuralUCB [89] prompt optimization. However, as mentioned in Sec. [
NCuralUCB is designed for regret minimization (instead of best arm identification), which is not suitable for learning the optimal prompt.
There are a few interesting concurrent works on topics that are worth further exploration. With the observation that finding a local optima is sufficient for many prompting tasks, Hu et al. (31) performs zeroth order optimization with an NTK-based derived Gaussian process. Opsahl-Ong et al. (57] studies the problem of prompt optimization in multi-stage LLM pipelines, where a Tree-structured Parzen Estimator 77] is adopted for selection. Lin et al. extends the prompt optimization framework to consider preference feedback.
Multi-armed Bandits. Here we briefly discuss the representative studies of MAB, with compre- hensive surveys available in Bubeck et al. [10], Lattimore and Szepesvári 41.. As mentioned in Sec. S.T. the target of learning MAB system can be roughly categorized as regret minimization and best arm identification. The regret minimization designs target achieving desired balance be- tween exploration and exploitation so that the cumulative rewards are maximized, e.g., UCB (5) and Thompson sampling [71]. The best arm identification (BAI) designs are fully focused on exploration and can be further divided into two classes: fixed-budget (BAI-FB) and fixed-confidence (BAI-FC). The BAI-FB setting maximizes the probability of finding the best arm with a limited number of pulls 4. 37 75 6 2, 82) J. The BAI-FC setting is a dual one which focuses on minimizing the overall number of pulls while guaranteeing that the probability of finding the best arm is higher than threshold 27 32 66
33 Besides leveraging BAI-FB as in this work, it is imaginable that BAI-FC designs also find applications in prompt optimization, especially when valuing identification accuracy over incurred costs. While MAB has found wide success in different applications, this work marks the first time that systematical connection between MAB and prompt optimization has been established to the best of our knowledge.
B Discussions
B.1
Broader Impacts
This work introduces TRIPLE, a framework that can perform efficient prompt optimization for large language models (LLMs) under limited budgets. By optimizing resource usage in prompt optimization for LLMs, we believe the proposed approach could make advanced Al tools and research more accessible to institutions and individuals with limited budgets, promoting a more equitable and democratized field of study. While acknowledging the need for responsible usage of the proposed method, we do not foresee major negative socictal impacts.
16

---

B.2 Limitations and Future Works
This work opens an interesting direction on the connection between MAB and prompt optimization. In the following, we discuss few aspects that are currently lacking in this work and particularly worth future explorations.
Prompt-specific costs. This work considers an abstract model where the cost during learning is measured by the number of L.M accesses. This model provides important starting point to initialize the investigation. To make the study more practical, more refined considerations on costs can be incorporated. For example, the OpenAI API charge the interactions based on the number of input tokens, which means longer prompts incur higher costs. The cost-aware BAI studied in Kanarios et al. [36 can provide some insights further consider prompt-specific costs.
Other BAI designs. Based on the connection between prompt optimization and BAL, this work has incorporated several BAI designs. However, the research on MAB has long and rich history. where many other BAI designs can also be leveraged. For example, the Bayesian perspective provided in 38 Atsidakou al. [2] and the function approximation scheme adopted in Yavas g3 Yang and Tan 882 are all worth investigation. Moreover, the multi-objective designs developed in Kone et al. (39 can be valuable extensions. This work important in delivering the
Komiyama al.
and Tan
message that (both existing and forthcoming) BAI methods can benefit prompt optimization, which may inspire future explorations.
Structured prompls. Sec. 6 we discuss how to extend TRIPLE to select examples for few- shot prompts. Based the insights obtained in this work, believe this direction is work further exploration. Moreover, other forms of structured prompting methods, such as Chain-of-Thern Thoughts (76), also interesting topics, which may further require multi-step techniques such reinforcement learning.
C Details of TRIPLE Designs
The details of TRIPLE-SH (inspired by Karnin et al. [37 TRIPLE-CR (inspired by Wang et al. 75 and TRIPLE-GSE (inspired by Azizi et al. (6) can be found in Algs. 2 and respectively.
Algorithm 2 TRIPLE-SE
1: Input: the pool of candidate prompts P, budget N
2: Initialization: set p(p) 0 for all p E P: set the active prompt set A t
3: for phase 1,... [log2 (IPl) do
4: Interact with the targeted LLM using each prompt A for [N/([A] (Pg2( times
5: Update the sample means (f(p) p E A} using the collected samples
6: Update the active prompt set as the set of [A/2] prompts in the original A with the highest
((p)
7: end for
8: Output: the remaining active prompt /*
D Details of TRIPLE's Extensions to Example Selection
In this section, we provide additional discussions on extension to example selection mentioned in Sec. [ It is first noted that the properties of good combinations of examples for few-shot prompts are a complicated topic and an active research problem [52 49 53 80), which still lacks conclusive answers. The proposed designs are based heuristics that are rell-recogd and widely evidenced. With deeper understanding of the few-shot prompt developed in later research, the perspective provided by TRIPLE and these designs would still be beneficial guide corresponding modifications and extensions.
CSAR. First, we incorporate the intuitive heuristic that if one example leads to better performance as a one-shot prompt, contributes positively to overall few-shot performance 61 45) Based on this heuristic, we adapt the CSAR design [14 I2 to perform example selection, which can identify M prompts from G with the highest individual performances, i.e., ((mm). The details are provided in Alg. 5
17

---

Algorithm 3 TRIPLE-CR
1: Input: the pool of candidate prompts P, budget N
2: Initialization:
n(p) 0, jo(p) + 0 for all p E P; set the active prompt A t-
3: for time 7 1, , , do
4: Receive input 20r
5: Select prompt Pr + arg min PEAA (p(p)
6: Sample output 0r ~ [(Pr. Fr7) from the targeted LLM
7:
Obtain score 8, t- ((T 1))
Update j((+>) t A(p- m(pp)+* and n(pr) ) + n(p+) +1
8:
n(p,)+
9:
Compute p' arg min Pe (pp) and 8, minpedM(r" {p(p) fa(''))
N- N- Epen p(p)
10:
EPEA m(p) log( - 1 1 6, then
11:
Eliminate prompt p', i.e., A AMp)
12:
end if
end for
14:
Output: prompt 6' + arg max PE (p()
Algorithm 4 TRIPLE-GSE
1: Input: the pool of candidate prompts P and their embeddings &, budget
2: Initialization: p(p) 0 for all p P:; the active prompt A
3: for phase 1, flog2 [P] do
4: Interact with the targeted LLM using each prompt in A for [N/ AA] 1og2((P)))) times
5: Use the collected samples to train a function ge(-) parameterized by 0, e.g., a linear function
an MLP
6: Compute {A(p) = ge(e(p) p E A}
7: Update the active prompt set as the set of [A/2] prompts in the original A with the highest
((p)
8: end for
9: Output: the remaining active prompt ~*
SAR. It is also noticed in previous studies that selecting diverse set of examples is vital in achieving good few-shot performances [67 [43] Leveraging this heuristic, we propose to first divide the example set G into M clusters, denoted as {g for each cluster GTh, we find one example Im in it with the highest one-shot performance (()m)) To perform such selection process efficiently, the SAR design [12] is leveraged. In this way, the diversity and quality the selected examples are both guaranteed. The details are provided in Alg 6
G ). based on the embeddings of the examples. Then,
E Full Experimental Details
In this section, include full details of our experiments, while the complete codes are also uploaded the supplementary materials.
E.1
LLM Models and System Instructions
Before further details, we first list the LLM models that we adopted for experiments:
GPT-3.5: gpt-3.5-turbo-111
55
Llama2: Llama2-7b
73
Gemma: Gemma-77 7b
70
Mistral: Mistral-7B-v0.2
As we use chat-based L.MMs, initial system instructions are needed, where the officially recommended system instructions are adopted in experiments, shown in Fig
18

---

Algorithm 5 TRIPLE-CSA
1: Input: the set of available examples G. the size of the combination M, budget N
2: Initialization: set j(g)) +- for all g E G; set the active example set < 9; To + 0: Jace + 0;
Gejj + 0; log( - Σ El|| 1/i
3: for phase p 1, | do
4: Tp < [(N G)) (I) - + 1))1
5: Interact with the targeted LLM using each example g E A one-shot prompt for T - p-1
times
6: Update the sample means (j(()) g E A) using the collected samples
7: Obtain order such that ((go(1)) ((go(2))
((())(AA))
8: Compute gaps
Do(r) - ((go()) M(9(MM- (M90((M-1mn)) (()o())
if S M 19acc
Vr E [|A|]]
if 2 M 19ncc +1,
9:
Compute g' +- arg max m Ag
10: Update Guve + Sux U (g') } if jug') A(go(M smalt1)); Grg + Poce U (g'} otherwise
11: Update A G/(Cnce U Gmi)
12: end for
13: Output: the set Gose
Algorithm 6 TRIPLE-SAR
1: Input: the set available examples G and their embedding ε, the size of the combination M, budget N
2: Cluster G into clusters [g),... ,GM based on embeddings & (e.g., via k-means)
3: Initialization: set jı(g) <- for all g G; set the active example set for cluster A g
set the overall active example set < G; set the active cluster M [M]; To + 0:
log((9)) < Eie[jn] 1/i
4: for phase
1,..
| do
5: Tμ + [[N - 9 / (lo
1))1
6: Interact with the targeted LLM using each example g E A as one-shot prompt for Tú - T
times
7:
Update the sample means (p(g) g E A) using the collected samples
8:
if 3m E M such that [ = then
9:
Update M + M/ {m}
10:
Update Fmm <- the remaining example in A
11:
else
12:
Vm E .M, compute Am < max gm am (max, M(mm) - M(gm)) and I'm t
arg max, Em {maxgm EAm ji(mm) - p(gm)}
Compute m arg MeMM Am
Update Am" +- And Hgm end if
14:
15:
16:
end for
17:
Output: the set (gr. 99M1
E.2 Score Functions
Different score functions s(-, -), i.e., metries for evaluation, are used for diverse tasks in the Instruction- Induction and BigBench-ii datasets, namely "Exact match", "Fl-score", "Multiple choice within", and "Multiple choice -loscore". These score functions are adopted according to the specific output requirements of different tasks:
Exact match: Used for most tasks unless otherwise specified, this metric scores for outputs exactly matching the label, and 0 otherwise.
19

---

System instruction Llama2,
Gemma, Mistral

 

System gpt-3.5
You are an intelligent assistant. Please enswer finish the given task, answer with the output only and reply nothing else.
"role": "system",
"content": "You are an intelligent assistant."


"role""usar""
<prompt>
"content"; sprompt>

]
Figure 7: The adopted system instructions: GPT-3.5 (left) and Llama2/Gemm//Mittaal (right)
Applied to tasks with complex targets like long sentences (e.g.. "informal to formal", "negation", "sentence similarity"), this metric (defined in Definition E. evaluates the overlap between the LLM response and the label.
fl-score:
Multiple choice within: Suitable for tasks with several correct answers, it scores 1 if the LLM'' response matches any correct answer and otherwise. We utilized this metric for tasks "rhymes", "translation-en-de"" "raaslaaion-ennes"" "translation-en-Ff and "word in context".
Employed for tasks with multiple, lengthy correct answers ("common concept" task), it calculates the highest fl-score across all potential correct
Multiple choice fl-score:
answers.
Definition E.1 (fl-score). Suppose the question has a labeled answer T and the response of the LLM is A, then the fl-score for this answer is defined as:
2 P R
Sn = P+R
where P P= 1m. stands for the precision of the response and R lm/lr the recall of the response. Here we use lA and lr to denote the length of the response and label while Im is adopted to represent the number of matching words between and T.
For the specific score function adopted for the BigBench-ii ii dataset, we advise referring to the "metric" label for each task therein. This label indicates the appropriate metric ("Exact match" "Multiple choice within"" for the optimal evaluation.
E.3 Experiments with Fixed Prompt Pools and APE
The prompt generation process to obtain the fixed prompt pools largely follows the one in APE 90), i.e., demonstrating L.MSs with examples. In particular, in the generation of each prompt, we sample 10 examples from the training set demonstrate LLMS with two types of generation templates: 'forward' and 'backward', which are illustrated in Fig. The same setups are also adopted in the end-to-end experiments with APE in Sec. 5.2
A side observation is that we find that in general. GPT-3.5 can handle both templates, resulting in reasonable prompts. However, LLMs with fewer parameter numbers, like Llama2-7b, Gemma- 7b, or Mistral-7b-vO. we use exhibit difficulties in generating useful prompts from the 'backward' template, possibly due its more simplified structure.
E.4 Experiments with APO
The APO framework (60] iteratively refines prompts based on feedback generated by LLMs. In particular, for each iteration, the system is set to identify (num_feedback) fault reasons (i.e., gra- dients) for the selected prompts from previously incorrectly answered examples. Then, with the selected prompts and the identified fault reasons, the L.M instructed create [oam_prompts] new prompts for further selection. The adopted templates in experiments are shown in Fig.
20

---

Forward Generation Template
gave friend an instruction. Hased the instruction they produced the following (impus,
output) pairs:
Imput: [2,]
Output: [4,]
Backward Generation Template
Imput: [0a] Output: (4g]
Input: [4
Output: I4,1
Input: [0g]
Output: [Ag]
What was instruction' Provide only the instruction and NOTHING else.
The instraction was to?
Figure 8: The adopted prompt generation templates for experiments with APE: forward (left) and backward (right)
where we set thum_feedbade to 2 and [oomp_sompps] to 5. We believe this configuration ensures that each iteration effectively identifies key areas of improvement and sufficiently expands the pool of potential prompts.
New prompt prompt generation template
'Gradient' 'eemlltee
I'm trying to wille a zero-shos classifeer My current peocapi is:
irying to classifier prompt.
(prompe)
My current prompt is:
Bur gets follewing examples wrong [emor exp)
(prompp]
cxamples problem peompt
But this prompt gets the following examples
wrong: (error string) give tmum foedbacks) reasons why the prompt could have gotten these examples wrong.
[gmadienx]
Based the above information, wnote (num prompts) differrnt improved prompts.
Wrap each reason with <START> and <END>
Each prompe is wrapped with <START and <ENDS The [nums prompts) new prompts (new prompts)
Figure 9: The adopted templates for experiments with APO 60 fault identification (i.e., "gradient") (left) and new prompt generation (right).
E.5 Implementions of TRIPLE-CLST and TRIPLE-GSE
Obtaining Embedding. critical component both TRIPLE-CLST and TRIPLE-GSE is the ex- traction of sentence embeddings for the candidate prompts. In experiments, the prompts first tokenized using the cl1 base tokenizer. Then, the tokenized prompts are input into the lext-embedding-ada--00 model (56), converting them into continuous vectors.
PP] TRIPLE-CLST In experiments with TRIPLE-CLSS the number of clusters is set as L [VP]] and third of our total budget allocated for the initial phase, i.e., N₁ N/3. The k-means algorithm employed the clustering method. For more stable performance, Phase I is configured to find the top 1/2 clusters, instead the optimal one, which safeguards against situation that the optimal prompt is not located in the optimal cluster. Also, for the BAI-FB designs in both phases, the CR algorithm 75 is adopted due to its flexibility.
The OpenAl embedding API returns embeddings of 1536 dimensions, which can be challenging for learning with limited samples. To overcome this issue, in the implementation of TRIPLE-GSE, we first employ projection to 64 dimensions using matrix with random elements from the standard normal distribution. This technique also incorporated in Chen al. [13] and is particularly beneficial given our limited budget constraints. Furthermore, to avoid overfitting and convergence issues, we adopt the standard approach by dividing our interaction data into training (80%) and validation (20%) sets. The prompt elimination process on line 7 in Alg. 4 is performed only if the mean squared error on the validation set is sufficiently low, and we set this error threshold at 0. in our experiments.
TRIPLE-GSE.
21

---

E.6 Experiments of Example Selection
In the results reported in Table 4 the task is to select 4 examples from set of overall 50 candidate examples within 100 interactions with the targeted LLM. For tasks with a training dataset larger than 50 examples, 50 examples across experiments. There are also few tasks with a training dataset smaller than 50 examples. which are thus entirely used as the candidate set. The same prompt template, as illustrated in Fig. [T is used for all tasks to maintain consistency.
first sampled to construct the candidate set, which is used consistently
Few-shot template
Instruction: Complate the problem.
Examples:
Input: [Q:] Output: [4,]
Input: [Q.] Output: [4g]
Input: (2x)
Output: [44]
Input: (Q4) Output: [4,]
Task: Input: (Q) Output: (output)
Provide only one answer NOTHING else.
Figure 10: The adopted few-shot templates for experiments of example selection.
Further details regarding the adopted baselines are provided the following.
To validate the benefits of interactions with the targeted LLM during the selection, commonly adopted baseline is to randomly select the required number of examples from the candidate pool.
Random.
Uniform. Similar the uniform baseline adopted in Sec. the overall budget can be uniformly divided to evaluate the one-shot performance of each prompt. Then, the examples with the highest estimated one-shot performances are selected.
Also, for TRIPLE-SAF SARR, the same process of obtaining embeddings as described in Appendix E.5 with also k-means as the algorithm to perform clustering.
E.7 Computing Resources and Costs
We use a workstation with two Nv0dia-A6000 Ada GPUs for all experiments using white-box LLMs (i.e., Llama2, Mistral, and Gemma). To reproduce our result, any GPU with over 30 GB of memory should be sufficient. With our equipment, each interaction with the white-box LLMs typically takes around 1.3 2.0 seconds. For experiments using GPT-3.5, the whole execution is light regarding local computational resources, while access to the OpenAl API is needed to perform learning. Under our network condition, one API call typically takes around second.
F Additional Experimental Results
Additional experimental results are provided to supplement observations in the main paper.
F1
Selection of Budgets
To further guide practical implementation, we additionally investigate how to select reasonable budget. In particular, we focus on the efficiency of various prompt selection algorithms in identifying "good" prompt either the optimal prompt in the pool or achieving 95% or better of the optimal prompt's performance. Fig. illustrates that initial increases in budgets significantly improve the probability of identifying good prompt, but this benefit tapers off with further budget expansion. This finding suggests that starting with a modest budget and incrementally increasing is the more effective approach, stopping when additional investment no longer translates into significant returns.
22

---

RatalBudget
Un Borm
0.0
Farc/gor's
0.8
0.4
25
15
20
25
Figure 11: Probability for different algorithms to select good prompt under different budgets (right), collected with GPT-3.5 and averaged over 5 runs.
F22 Performances on Gemma and Mistral
For the experiments on the selected tasks with [P] 30 prompts and budget N 150, additional results with Gemma and Mistral are reported in Fig. 12(a] and 12(b) The superiority of TRIPLE can still be observed, demonstrating its flexibility over different LLMs.
F.3 Performances on Additional Datasets
The experiments are further extended to more diagnostic tasks (GLUE (74] and math problem datasets (GSM8K (7)). More specifically, TRIPLE methods are deployed to select prompts for the task "Cola" in GLUE (on distinguishing linguistic acceptability) and also cfain-of-thought prompts for GSM8K (on mathematical reasoning). The results are presented Table 5 where it can be observed that the superiority of TRIPLE still prominent.
Table 5: Averaged scores of baselines and TRIPLE on the task "Cola" (from the GLUE dataset) and the GSM8K dataset using GPT-3.5, with [P] 30 candidates and budget N 150, where the highest ranked methods are marked bold.
Setup
Without emheddings
With embeddings
Dutaset
Uniform
LCB
SIT
CR
BO-EI
NeuralUCB
CLST
GSE
Cola (GLUE)
0.728 = 0:66
0.753
0.01
0.768 648
0.766 = 0002
0.618 = 0.22
0.673 = 0.04
0,763 2P
0.757 = Eus
GSMBK
0.706
0000
0.720
0,713
0.733 0006
0.710 2000
0.716
0.730
0.710 08t
F,4 Complete Evaluations 47 Tasks
In the main paper, we provide experimental results of 12 representative tasks from the overall 47 available tasks in Sec. In the following, the complete results discussed.
P
30, N 150: results on the 24 available tasks in the Instruction-IIductioo dataset 30 are illustrated in Fig. (3(a) GPT-3355,, and 13(b (Llama2);
PI = 30, 150: results on the available tasks in the BigBench-ii dataset are illustrated in Fig. 14(a) (GPT-3.5) and 14(b) (Ilama2).
P 150, N 100: results on the 24 available tasks in the Instruction-Induattoon dataset 30 are illustrated in Fig. [5(a) (GPT-3.5), and (5b) (Llama2);
IP| 1500 100: results on the 23 available tasks the BigBench-ii dataset 69 are
illustrated in Fig. [6(a) (GPT-3.5), and 16(b) (Llama2).
23

---

Also, the complete performances of example selection for few-shot prompts discussed in Sec. 6 are presented in Fig.
iestrruction-nducctiinn and [8 (BigBench-il)
Besides the average return, another key aspect of prompt selection is the frequency of selecting good prompt. In Table 8 we further demonstrate the best prompt identification frequency of different algorithms across 20 selected tasks from 5 independent runs.
24

---

Table Clusters for "movie selection": best prompt overall is marked red, and the best prompt in each
cluster in yellow.
Prompts
The instruction was to select the movie tile that appeared the mast frequestiy amang the given choices. choose the
The instruction
the given inputs and cloicees, movie the given choices based the impui tides. task
select option thet matched given genre The instruction was to choose the move till from the given choiees that correspoud the movie tillss un the input.
The instruction was to select the movie from the given choaces.
of choices instruction was select the movie that received most number
instruction
should watch based the inpumed given choices.
The instruction was to choose the correct movie based on the given choices.
The instruction was to provide the from the choices. given
movie based the given choices.
instruction
choese
instruction was to select
ssovic
The instruction was to provide the outpur movie choice for each given input movie titles and their correspoading choices.
The instruction was to recornmend one movie out of the given choices.
novies, based chelees their coressanning movic choice based on givess imput movies. There muttppe choices for inpur, and the selected chooce was the ooe with value of 1. The chosen movie the output.
instruction
detenti the choice
instruction was
Choose the cornect
based on choices.
choices.
In each case, provide ourgut responding to the relitive place of these Nos amoug Fraver best shope singers thes, the relative here is taken negatively greater- wasse place's s id fails in the tranchise with counseling distriburina) Crush Orders Miscellancons similaty depending continuity concestaatinn
confirmed kid nook campaign Hadson stafter reinforeemess Paris Concestraze' theater! stinket made water Vectar Vancouver British infuity company merchant
Ferdinand mates Schaup an Koyalty fracture PSA Coay drafts navigate Parse Site name CrosiRef SC CoooaeesSCKKapppeeeeeeaea -ppentill MP Ref lighweight winds Hurricanc winds login Joint GetString Paramoters disparitios Orrhh Rocket Vanting MPI resemble are Met Lav anc-etr sand crosion colernel Hophobic Inbox sshes shoping Ogen whitesqace subsidizing Uppot Mouthhly-Sugg NZ archivetiles coastine-commeree Stetch Trihural exposing Directoes reveal HA corp Sew pro
excevation bokers
subsddary amended
Signing Un subritle Rui Metican commentary Ribad uplosding grow encryrion reading Unil clavses Teaching Altemative indent worklowddSNN fileputh Strings kisty Samplefice testile Purser clam pract OakWhen modes Up representatives Knoxville ODEM repositories BP fixed role Renighhoors EIP Recall Copy Destruction gears
baaned
FussonRih stomgeSettinge metaValldateFalllee
The instrutionn was to desermine the conrect ourput based un a given input and its correspouding choices. The instruction was to determine the ouiput choice based on the given inputs and options.
instruction
select the choice with
point
and provide The instruction was to select the correct choice from each input sequence.
instruction was select one
output.
R.Selctt the correct
film titl from the given list input films. options.
Choose
ticle
Sclect one movie from the given choices based on the input movies.
Desermine the correct movie choice based on the given options for each input.
Given list movie tides. need to chouse the currect movie from the given choices that matches closely with the given litles.
Find conrect cutput mavic the grovided choices. Solect the movie from the given choices.
25

---

Table Clusters "rhymes": the best prompt overall marked red, the best prompt in cluster
yellow.
Prompts
The instruction was identily homophones the given inguss.
Identify the words from the given inpuis,
The instuction was
nearest thyming word for euch given word.
Find the shyming word for the given word.
Replace the provided word with a similer werd that rhymes with and has different menning
Find
given
instrccioon was to provide outpur
rhymes given inpui
The instraction was idemity any work that are siil the same aher cestoviing the letters "in", "re", "peo", "ex", and "anii" Trom the beginiing muddle of word.
pronounced Iduntdy the incourect word within cach pair.
Identiy the
meanings thomophonees.
Ideutiyy any words that are one letter away from real weed that makes sense.
ideutify the
created by changing
time from given word.
Find the rhyming word for each imput wunt
The instruction was to find the rhyming word for each input word.
Find rhyming word each input Identify chyming word for each input word.
Find shyming
given inputs.
Find shyming word each input wond.
Generate thyming words with the given inpu: words.
Find rhyming word for each
wond.
Replace word ppooee'
Iduutiy the woods that thyme with phose".
idzutiy the weeds that chyme with "phone".
Meniify
rhyme
suggost the alternative word that rhymes with ench inpamed weed. rhyoee "yloone..
anstuutioon was
Provide the correct spelling for the given words.
Conrect the spelling of the weed if misspelied, otherwise. Identily
word 35.5.
spelling
Replace the letter with the letter in each word.
The instruction was correct any misspelled words in the given imputs.
26

---

2009
(a) Gemma
4
14.00
(b) Mistral
Figure 12: Performances using Gemma and Mistral on selected tasks with [P] 30 prompts and budget N 150.
27

---

ans
corcapt
ward
on mal
Tat
Regadan
Ninbow
A/T pasove
5-gg JAV pkrral
Myymes
Seciad
Semterce
JCB
TRPIE-SH
TRPLE-CR
50
NevrOlUC
PAPL--GSE
Sensmmett
Starts wi
Sum
Tarrsation
Warsladin
Trans-af
Word
content
(a) GPT-3.5
Fi
corcept
werd
an mra
Tecsromy
Negator
Number varbal
Act.vv pasuve
Sing-ler skural
Shymme
Secopa losist
Senterce
TRPLE-SH
TREPEECR
50-E)
Vem.
MeUONTIC
PRIPE-SSE
Word
rover
(b) Llama2
Figure 13: Complete results on the Instruction- Instruction-Inductionn Induction dataset with [P] = 30 prompts and budget
N 150.
28

---

namres
judgmmntt
undoralansing
Sourt rg
reasoring
Timedal
Sradks
Wer
HycerSation
Wert Migg
Pullacy
JCB
TR
TR TRPLE-CR
50
NevrOlUC
TR-LE-GSE
Diammbiguue 42
Tenns
Presucpooi 1015
Gonder DE
Opentos
ang.ages
(a) GPT-3.5
names
judyment
understanding
daunting
reasoring
Timedal
Smarks
Were
Hypersaton
LINDU 91iCh
Queetion
Wert
Lecical dutediin
Sal
TR TRPLE-SH
TRELEECR
50-E)
MeUOVTICA
PRIPE-SSE
Tinne
ang--ages
(b) Llama2
Figure 14: Complete results on the Big dataset with |P| = =30 prompts and budget N 150.
29

---

ard
cencept
word
sninal
let
mnnal
temall
80.2
Naurat.C
nord
01-30
01-53
C1-11
(a) GPT-3.5
and
concept
word
animal
lnt
animal
smiliily
exde
e1155
eh/ll
(h) Llama2
Figure 15: Complete results on the Instruction-Inducet dataset with [P] = 150 prompts and budget
N 100.
30

---

Run
Vevigate
Crusa
Spart
Osjec
Spstemk
W meAPy
Timddl
Smarte
Word
Hyperbaron
Lings mihe
Queetion
Veen
Logenl pedeciion
3t -8 on
Presuppectine
Sender TX.
Opera0o15
(a) GPT-3.5
rames
lufgree
indesttandig
Suurking
reaseiigg
stntiig
808 TRULL--2E
Puicees
selection
unsrambiing
Siacy
injuages
60
incommendatonn
DE
(b) Llama2
Figure 16: Complete results on the BigBench-ii ii dataset with [P| 150 prompts and budget
100.
31

---

Ugg
carcar
farma
21m
Unibrm
TRENEESA
sland
Inttr
cantoot
Figure 17: Complete few-shot results on the Instruction-Induction dataset using GPT-3.5 with 50 examples, budget N 100, and prompt length M 4.
[
0.2
Clieet
Ipeless
543955
3.3
TRPPLE SAR
TRALE-25A
0.2
Wing
Last-
Dourtay A7
Vast:
krot
Mospoooaatnneeee DE
Figure 18: Complete sho-shot results on the Big-Bende dataset using GPT-3.5 with [ examples, budget N = 100, and prompt length M = 4.
50
32

---

Table 8: The ratios of different methods outputting good prompt with GPT-3.5 from large prompt
pools [P] = 30.
Task
Budget
Uniform (%)
UCB (%6
SH (96
CR (%6
CLST (%)
GSE (%)
5
20
20
20
30
60
30
and effect
20
40
80
40
20
60
60
80
80
100
80
5
20
40
Common concept
10
20
20
20
20
00
40
20
40
40
80
80
80
80
80
100
100
100
Larger animal
10
100
100
100
100
100
100
20
100
100
100
100
100
100
Informal to formal
10
20
20
20
60
40
40
20
60
80
100
100
100
100
100
100
100
100
Negation
10
100
100
100
100
100
100
100
100
100
100
10
10
30
20
40
30
Rhymes
40
60
60
80
80
20
100
100
100
100
100
5
30
40
40
20
40
40
Orthography starts with
60
80
80
80
20
100
100
100
100
100
100
5
25
30
40
25
53
45
Sentence similarity
40
60
80
20
60
60
80
80
80
100
5
55
70
60
70
70
Word context
10
100
100
100
100
100
20
100
100
100
100
100
100
90
100
90
100
Disambiguation
10
100
100
100
100
100
100
20
100
100
100
100
100
100
60
70
100
80
Gender Inc. DE
10
60
80
100
100
100
100
100
100
100
100
70
70
70
90
80
Hyperbaton
10
80
80
80
80
100
100
100
100
100
100
20
20
25
45
50
40
Movic recommcodation
40
40
40
60
60
60
20
60
80
80
80
80
5
10
20
25
30
35
35
Object counting
40
40
60
60
20
80
100
100
100
100
100
5
0
10
20
15
Question selection
10
20
20
20
20
40
20
20
40
40
40
60
80
60
5
20
10
25
25
20
Snarks
10
20
40
40
60
60
60
20
80
100
100
100
100
100
Word sorting
10
100
100
100
100
100
100
20
100
100
100
100
100
100
55
70
70
80
Ruin names
10
60
80
100
100
100
100
100
100
100
75
80
80
80
80
90
Sporting undorstanding
10
100
100
100
100
100
100
100
100
100
80
85
90
50
83
90
Word unscrambling
10
100
100
100
100
100
100
20
100
100
100
100
100
100
33

---

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: Our claims in the abstract and introduction faithfully point out the main idea we proposed, the major contribution we made, and the technique challenges we have solved.
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 long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We included discussion of our paper's limitations and potential future directions in Sec. B.2. please see the referred section for more information.
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 a 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 (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn 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 on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on 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-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of 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 faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a 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 an 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 set of assumptions and complete (and correct) proof?
34

---

Answer: [NA]
Justification:
This paper's work is mainly practical, we did not claim any theoretical results and thus did not include any proof accordingly.
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 to 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 affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
The methods proposed in this work have been described with full details (see the pscudocodes in Algs.
Justification:
S and (6. The complete experimental setups are presented in Appendix [., and the experiment codes can found at https::/gii thub com/ Shwnnhhennrrrr/// TRIPLE. With these efforts, we are confident that the main results of the paper are reproducible.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, 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.
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 a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require 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 reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.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 reproducibility may be tricky in some cases, in which case authors are welcome describe the partieular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
35

---

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
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
The experiment codes (together with detailed instructions) available at attpp://githhut com htt///Senroouu/TTTTe /TRPPTRILEE The adopted datasets are all open-source ones. This should be sufficient to make anyone who wants to reproduce experiment results capable of easily executing the experiments.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, "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 reproduce the results. See the NeurIPS code and data submission guidelines (https //nips.ccpput wwtpcccccppccccceee conollicggiieee www.deeeeeeeebmmmeeeeeee iobbmisssiins ssioncolccy for more details.
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 new proposed method and baselines. If 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/eetails
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 understand the results?
Answer: [Yes]
we have included all the experimental details used for our experiment execution and how the asper-parameters are chosen.
Justification: Appendix E
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of 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, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We did include the error bars and the standard deviation in all the experimental results that need this information.
Guidelines:
36

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars 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).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma error bars, but 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 show in tables figures symmetric error bars that would yield results that are out of range (c.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have included the necessary computing/other resources, as well as the experimental times we have used to finish all our experiments. Please refer to Appendix E.7 for this information.
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 as 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 NeurlPS Code of Ethics
Answer: [Yes]
Justification: Our research conducted in the paper follows the NeurIPS Code of Ethics in every respect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there 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 socictal impacts of the work performed?
37

---

Answer: [Yes]
Justification:
We have discussed the broader impact of our work in Appendix B.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact 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), fairness considerations (e.g., deploymeet 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 a 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 conrectly, 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.
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: Our paper does not pose such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We have properly credited all code sources, data sources, and open-source models in paper following their license and terms.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
38

---

The authors should state which version of the asset is used and, if possible, include 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.
If assets released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
Answer: [NA]
Justification: In this current version, we do not plan to release any new assets to the public.
Guidelines:
The answer NA means that the paper does not release new 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 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. Crowdsourcing 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 as details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not include any crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing 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 as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or 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 equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
39

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on 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.
We recognize that the procedures for this may vary significantly between institutions and locations, and 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.
40


Reviews:
[{"review_id": "HF6AsIUITG", "reviewer": "Reviewer_55GB", "summary": "The authors study prompt optimization, with a focus on finding the best prompt from a pool of proposed prompts under highly limited budgets. They establish a connection to fixed-budget best arm identification in multi-armed bandits (MAB) and explore several algorithms from that problem, applied to prompt selection for evaluation. They then make additional improvements by observing that prompts are not independent and that information, through embedding the prompts, can be shared to make the exploration more effective. They test methods based on clustering and DNN reward functions, based off of off-the-shelf embeddings of the prompts.", "questions": "Do TRIPLE-SAR and CSAR take ordering into account?", "limitations": "n/a", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper is well-argued and well-presented. The authors argue that existing work on exploring prompt candidates under limited budgets apply a regret minimization framework, which is less well-suited than best arm identification, and then go on to explore highly-effective simple extensions that share information across prompts.\n\n2. The results are compelling: the methods are compared against a convincing set of baselines, from UCB to Bayesian optimization (BO) with expected improvement. The outcomes consistently show the value of the author's selection of framework (BAI) and their information sharing.", "weaknesses": "1. The authors evaluate on tasks that to my understanding are extremely limited in scope. Most are narrow reasoning puzzles and may not reflect the type or complexity of typical prompts people use in the increasingly elaborate open-ended LM systems out there. How would such open-endedness interact with the findings?\n\n2. The results are somewhat hard to parse from the tables and especially so from the figures, though it is clear that they are overall quite positive. The budgets considered for evaluation are perhaps very strict, which is worth calling out, e.g. <1 evaluation per prompt, 5 evaluations per prompt. The method does show gains over baselines up to 30 evalutions per prompt, so it is very compelling nonetheless.\n\n3. The claims at the start of the paper that existing work just rarely considers budget of optimization is a bit overblown and overlL unnecessary for the claims of the paper, which are compelling on their own. The authors compare with several baselines that *do* consider budget, just not as effectively or thoughtfully as the authors do.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing this paper and providing the helpful suggestions. We are glad to hear your recognition that this paper is well-presented and well-argued with compelling results. In the meantime, we would like to provide the following point-to-point responses, which hopefully can address your raised questions.\n\n---\n\n\n>**Weakness 1.** The authors evaluate on tasks that to my understanding are extremely limited in scope. Most are narrow reasoning puzzles and may not reflect the type or complexity of typical prompts people use in the increasingly elaborate open-ended LM systems out there. How would such open-endedness interact with the findings?\n\n**Response 1.** We would like to answer your question in two aspects:\n\n- First, the studies on prompt optimization are focused on finding good prompts for certain downstream tasks, which contain a broad scope of applications (e.g., translate languages, generate TL;DR, summarize news, etc.). This work strictly follows this established research line, thus sharing this broad scope in terms of applications. \n\n    - Two standard datasets, Instruction-Induction and BigBench, are adopted to provide representative tasks, e.g., recommend movies based on browse histories (i.e., task \"movie_recommendation\" in BigBench), and translate English to German (i.e., task \"translation_en-de\" in Instruction-Induction). \n  \n    - During the rebuttal, we have further performed experiments (see the Table 1 in the uploaded PDF) on two additional datasets, GLUE (in particular, task \"Cola\" on distinguishing linguistic acceptability) and GSM8K (on mathematical reasoning), to further demonstrate the broad applicability of this work. These tasks also align with other research papers on prompt optimization. We believe that our findings are convincing with these representative datasets.\n\n- Second, the line of research on prompt optimization (including our paper) can still contribute to the more open-ended interactions with LLMs mentioned by the reviewer. In particular, the identified prompts on various downstream tasks can be used to summarize general prompting strategies (e.g., use positive tongues or imperative sentences), which can be further released to guide users. \n\n  - Moreover, we note that during this summarization process, efficiency is still a major concern as good prompts on a large pool of different tasks should be identified to find the general strategies. Thus, this work contributes to providing a well-tested framework to guarantee both performance and efficiency. We will add discussions on this further extension into the revised paper.\n\nOverall, we believe this work has a sufficiently broad scope to benefit both task-specific and open-ended interactions with LLMs.\n\n---\n>**Weakness 2.** The results are somewhat hard to parse from the tables and especially so from the figures, though it is clear that they are overall quite positive. The budgets considered for evaluation are perhaps very strict, which is worth calling out, e.g. $< 1$ evaluation per prompt, 5 evaluations per prompt. The method does show gains over baselines up to 30 evaluations per prompt, so it is very compelling nonetheless.\n\n**Response 2.** Thank you for this great suggestion on highlighting the results. We have further refined the figures and tables to facilitate understanding, emphasizing the superiority of the proposed methods. A part of the revised Figure 2(a) is contained in the uploaded PDF as Figure 1 to serve as one demonstration.\n\n- One horizontal line at 1 is added to label the baseline of Uniform, over which the performance of other methods are normalized. \n- A star is positioned on the best-performing method of each task. \n- The size of the candidate prompt pool and the stringent budget are also highlighted in the top left corner. \n\nSimilar enhancements will also be applied towards other figures and tables. We believe they will better illustrate the superiority of the proposed TRIPLE framework. It would be our pleasure to further take any suggestions that you may have. \n\n---\n\n>**Weakness 3.** The claims at the start of the paper that existing work just rarely considers budget of optimization is a bit overblown and overly unnecessary for the claims of the paper, which are compelling on their own. The authors compare with several baselines that do consider budget, just not as effectively or thoughtfully as the authors do.\n\n\n**Response 3.** Thank you for this constructive suggestion on the presentation of this work. As suggested, in the revised paper, we will put more emphasis on the obtained compelling results, especially under the strict budgets noted by the reviewer. At the meantime, a reduced while clear claim will be made that previous works did not particularly optimize performances under specific budgets, while this work introduced a systematical and empirically superior approach.\n\n--- \n\n>**Question 1.** Do TRIPLE-SAR and CSAR take ordering into account?\n\n**Response 4.** While already achieving remarkable performance, the current version of TRIPLE-SAR and CSAR do not optimize over different orderings. The main reason is that there currently lacks a comprehensive understanding on the impact of example ordering on the final performance. Directly examining all the permutations, on the other hand, would lead to an unaffordable, exponentially-large action space.  \n\nIf a better understanding of the impact of ordering can be established in the future (which essentially is a property of function $\\mu$ defined in Line 363), it is conceivable that the TRIPLE framework can incorporate ordering by leveraging corresponding investigations on fixed-budget best arm identification, following the spirits of the pioneering TRIPLE-SAR and CSAR. We will provide further discussions on this point in the revised paper to encourage further investigations.\n\n---", "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": "ITyw1vuMiH", "reviewer": "Reviewer_7VZU", "summary": "This work proposes an algorithm that adopts the fixed-budget best arm (BAI-FB) identification to search for the best prompt. The authors have considered two variants of BAI-FB including sequential halving (SH) and continuously reject (CR). They then utilize prompt embeddings to enhance the BAI-FB methods via clustering and function approximation.", "questions": "- Some literature adopts the deterministic function $f(\\cdot)$ for prompt optimization and this is practical as some LLMs use greedy sampling. Will your method still work under the deterministic function $f(\\cdot)$?\n\nSee other weaknesses above.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "- The idea of using BAI-FB other than naive online MAB is interesting in prompt optimization.\n\n- The empirical results suggest TRIPLE is an effective method to identify good prompts.", "weaknesses": "- The presentation could be substantially improved. For example, Section 3 seems redundant as most of its content is not critical and can be covered by Section 2. Besides, the empirical results show TRIPLE-CLST/GSE are generally better but their justifications and descriptions (including the clustering property which is critical for TRIPLE-CLST and the embedding in function approximation) are not enough in the main text. I strongly suggest authors to reduce Section 3 and extend Section 4 by adding explanations and moving some materials from the appendix into the main text.\n\n- The evaluation setting is not described in detail. For example, are the evaluation budgets per prompt the same for all considered baselines? If so, the exact amount of evaluation budgets per prompt only means how accurate this estimation is.\n\n- The considered prompt candidates for search are very limited only containing 150 at the maximum. However, in the literature (e.g., Lin et al. [43]), they have considered over 10k candidates. Generally, it is reasonable to consider a large prompt space for the search method to really find the optimal prompt. Otherwise, the result could be biased.\n\n- Although the paper emphasizes efficiency, it is very hard to see if the method is efficient in the empirical section, where only the performances under the specific budget setting are considered.\n\n- Recent baselines with/without embeddings like ZOPO and, OPRO should also be considered.\n\n- The tasks evaluated in this paper are mostly instruction induction tasks. It would be great to show that the method can work on GLUE tasks and reasoning tasks (e.g., GSM8K, MATH).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing this work! The following point-by-point response is provided, where the reviewer's comments are compressed due to the length limit.\n\n---\n>**W1.** The presentation could be substantially improved...\n\n**R1.** Thank you for this helpful suggestion! In the revised paper, we will shrink Section 3, making a reduced but clear claim on the systematical connection between BAI-FB and prompt optimization. More descriptions will be added to Section 4 to highlight the empirically remarkable TRIPLE-CLST/GSE, especially the clustering property and the utilization of function approximation.\n\n---\n>**W2.** The evaluation setting ... are the evaluation budgets per prompt the same for all considered baselines? ... evaluation budgets per prompt ...\n\n**R2.** We would like to clarify the notation of \"evaluation budgets per prompt\" here and in the revised paper to avoid misunderstanding.\n\n- First, as mentioned in Line 109, this work imposes an overall budget on the total interactions with LLM during training, referred to as the \"(overall) budget\" and denoted as $N$. The experiments always control **the overall budget as the same across methods**, ensuring fair comparisons.\n\n- The notion \"evaluation budgets per prompt\" is an expression denoting the value of the overall budget divided by the number of candidate prompts, i.e., $N/P$ with $P$ being the number of candidates. It just means that **on average**, each prompt is evaluated $N/P$ times, while the algorithm still can flexibly allocate the overall budget $N$. For example, in Lines 322-323, the overall budget is $N = 150$ and $P=30$ prompts are considered (thus $N/P = 5$ evaluations per prompt on average), which means the algorithm can flexibly allocate the overall $150$ evaluations on the $30$ prompts. Line 333 indicates $30$ evaluations per prompt on average, which with $P = 30$ prompts, means the overall budget is $30 \\times 30 = 900$.\n\n---\n>**W3.** The considered prompt candidates ... only containing 150 at the maximum...\n\n**R3.** During the rebuttal, we have scaled up the number of candidate prompts to $1000$, with results on two tasks reported in Figure 2 in the uploaded PDF. It can be observed that TRIPLE still exhibits better performances than others. We will add complete results to the revised paper.\n\nAlso, Figure 3 demonstrates that the performance distributions of prompt pools with sizes ranging from $100$ to $1000$ are similar to each other. Thus, we believe the obtained results can faithfully represent the comparison between TRIPLE and baselines.\n\n---\n>**W4.** ... hard to see if the method is efficient in the empirical section, where only the performances under the specific budget setting are considered.\n\n**R4.** This work refers to one method as more \"efficient\" than another if, under a specific (and likely stringent) budget, the former can find a better-performing prompt. We use this definition of efficiency because many previous works do not explicitly limit the LLM interactions during training, which may lead to large costs. In the empirical section, we compare the performance of the identified prompts among different methods **under the same budget** to determine which one is more efficient. We will clarify this in the revised paper.\n\n---\n>**W5.** Recent baselines ... like ZOPO and, OPRO ...\n\n**R5.** Thank you for providing these two baselines!\n\n- [ZOPO] As the [ZOPO paper](https://arxiv.org/abs/2403.02993) is posted on arXiv on May 5th, 2024, which is very close to the NeurIPS submission deadline (full paper on May 22), we did not include it as a baseline in the initial submission. According to [NeurIPS 2024 Call For Papers](https://neurips.cc/Conferences/2024/CallForPapers#:~:text=Contemporaneous)  *\"For the purpose of the reviewing process, papers that appeared online within two months of a submission will generally be considered 'contemporaneous' in the sense that the submission will not be rejected on the basis of the comparison to contemporaneous work.\"*, we believe our work can be considered contemporaneous with ZOPO.\n\n  Following the reviewer's helpful suggestion and [NeurIPS 2024 Call For Papers](https://neurips.cc/Conferences/2024/CallForPapers#:~:text=Contemporaneous) *\"Authors are still expected to cite and discuss contemporaneous work and perform empirical comparisons to the degree feasible.\"*, during this rebuttal period, we have been trying our best to implement ZOPO. However, as ZOPO does not have released codes (to the best of our search) and we have encountered several clarity questions, we have not been able to re-implement it during the limited rebuttal phase. Currently, we are getting in touch with the authors to clarify our encountered issues. We will properly cite ZOPO in the revised paper and continue to do our best to add the comparisons.\n\n- [ORPO] The [ORPO paper](https://arxiv.org/abs/2309.03409), cited as [74] in our work, proposes to prompt LLMs as an optimizer to perform optimization tasks. This philosophy is very similar to that of APO [54], adopted as one pipeline in Section 5.2. Due to such a similarity, we mainly perform experiments with APO, with Table 3 demonstrating the superiority of TRIPLE.\n\n---\n>**W6.** ... It would be great to show ... on GLUE tasks and reasoning tasks (e.g., GSM8K, MATH).\n\n**R6.** As suggested, during the rebuttal period, we have tested the performance of TRIPLE on CoLA (one of GLUE tasks) and GSM8K. Results are provided as Table 1 in the attached PDF, where TRIPLE still performs better than the baselines. We will include these and more results in the revised paper.\n\n---\n>**Q1.** ... Will your method still work under the deterministic function $f(\\cdot)$?\n\n**R7.** Yes, our solutions still work under the deterministic function, as it is one special case of the general stochastic function considered in this paper. In this case, as captured in the definition of $\\mu$ in Line 97, the randomness would only come from the input $X$ but not $f(\\cdot)$.\n\n---", "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": "xIYhWMPa0D", "reviewer": "Reviewer_cpR6", "summary": "This paper studies prompt optimization using BAI-FB. There are several contributions:\n1. Draw a connection between prompt optimization with the BAI-FB\n2. Benchmark different acquisition function for prompt optimization\n3. Extensive experiments are done to show the effectiveness of the proposed prompt optimization and extend the setting to example selection.", "questions": "What's the hyper-parameter used to run the regret minimization algorithm? e.g., UCB and NeuralUCB? Since these algorithm are highly sensitive to the selection of hyper-parameters.", "limitations": "See my weakness", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The presentation of this work is clear\n2. The formulation of prompt optimization with limited budget as BAI-FB is clean with strong justification\n3. The experiments are extensive with a good coverage of baselines, LLMs, and datasets", "weaknesses": "1. The novelty of this work is limited, since there are already a lot of prompt optimization work using bandits as the authors have discussed in the paper\n2. A larger domain of prompts need to be considered where exploration vs exploitation is more important. For example in [43], the domain of prompt is 10k and the experiments in [43] shows that NeuralUCB is a SOTA selection strategy in this case. A comparison of MAB-FB methods and regret minimization methods in a larger domain of prompt optimization can be more helpful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing this work and providing helpful comments. It is our pleasure to hear that you found the presentation is clear, the connection with BAI-FB is clean, and the experiments are extensive. To further address the raised questions and concerns, the following point-by-point response is provided.\n\n---\n\n>**Weakness 1.** The novelty of this work is limited, since there are already a lot of prompt optimization work using bandits as the authors have discussed in the paper.\n\n**Response 1.** We would like to provide the following discussions to highlight the novelties of this work.\n\n- First and foremost, while some previous papers have touched upon leveraging bandit techniques in prompt optimization, as we have discussed in Lines 80-86, they mostly focus on using algorithms designed for **regret minimization**. As the reviewer recognized, this work makes a clean and well-justified connection between **fixed-budget best arm identification (BAI-FB)** and prompt optimization, highlighting this is a more suitable way to incorporate bandit techniques. We believe it is of great importance to clearly deliver this message. \n\n- Also, the contribution of this work goes beyond identifying the connection between BAI-FB and prompt optimization. Two enhancements, i.e., TRILE-CLST and TRIPLE-GSE, are proposed in Section 4 to leverage prompt embeddings together with BAI-FB to handle large candidate pools. Furthermore, TRIPLE-SAR and TRIPLE-CSAR are designed in Section 6 to further incorporate techniques from combinatorial bandits to efficiently perform example selection for few-shot prompts. None of these designs have been proposed in the literature of prompt optimization, and they have demonstrated superior empirical performance in the extensive experiments in Sections 5 and 6.\n\nWe believe both the introduction of BAI-FB and the proposed designs contribute novel ideas to the study of prompt optimization.\n\n---\n>**Weakness 2.** A larger domain of prompts need to be considered where exploration vs exploitation is more important. For example in [43], the domain of prompt is 10k and the experiments in [43] shows that NeuralUCB is a SOTA selection strategy in this case. A comparison of MAB-FB methods and regret minimization methods in a larger domain of prompt optimization can be more helpful.\n\n**Response 2.** During the rebuttal period, we have scaled the number of candidate prompts to $1000$. The performances on two tasks are represented as Figure 2 in the uploaded PDF. It can be observed that the proposed TRIPLE framework still achieves improved performances with this larger number of candidate prompts, further corroborating its superiority. We will add these and more results to the revised paper.\n\nAlso, Figure 3 presents the performance distributions of prompt pools with sizes ranging from $100$ to $1000$. It can be observed that the distributions do not vary much with the size of the prompt pool. Thus, we believe the current experiments with $150$ and $1000$ prompts are sufficiently representative to faithfully demonstrate the compelling performance of TRIPLE.\n\n---\n>**Question 1.** What's the hyper-parameter used to run the regret minimization algorithm? e.g., UCB and NeuralUCB? Since these algorithm are highly sensitive to the selection of hyper-parameters.\n\n**Response 3.** We used the vanilla form of UCB from [R1] where it was first proposed. For NeuralUCB, the same parameterization as the Github repo of [R2] is used. We believe this can result in a reasonable performance comparison.\n\n\n[R1] Auer, P., Cesa-Bianchi, N., and Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem.\n\n[R2] Lin, X., Wu, Z., Dai, et al. (2023). Use your instinct: Instruction optimization using neural bandits coupled with transformers.\n\n---", "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": "DbG9fkIyVQ", "reviewer": "Reviewer_gchr", "summary": "This study focuses on the efficient prompt design under budget constraints, where effective prompts may have to be designed without excessive evaluation of a very large number of candidate prompts.\nThe paper aims to present a principled framework - called  TRIPLE - for tackling this problem, which is achieved by making connections between the prompt optimization problem and the fixed-budget best arm identification problem (BAI-FB), thereby drawing from the rich literature on the multi-armed bandits (MAB) problems and methods. Based on prompt design experiments for various design tasks using various LLMs, the paper shows that TRIPLE can meaningfully improve the prompt design results when there are budget constraints.", "questions": "- Please provide some discussion on how TRIPLE may be used when the prompt optimization task has multiple objectives. How can connections to best-arm identification be leveraged in case of multi-objective prompt optimization?", "limitations": "The paper discusses the limitations of the proposed approach in the Appendix (section B.2) as well as some future research directions to address these limitations.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- It is a good and meaningful attempt to formulate the prompt optimization problem as a multi-armed bandit (MAB) problem. As shown in the paper, making connections between prompt optimization and best-arm identification in MAB allows one to draw from the rich MAB literature to devise effective prompt design methods. This is clearly demonstrated in the budget constrained case, which is the main focus of the current study, as one can leverage fixed-budget best-arm identification methods to improve prompt design under a limited budget for evaluating the (possibly large) prompt candidate pool. However, the benefits of the proposed framework are likely to go beyond the current problem setting, as MAB is an actively investigated field with rich outcomes and existing tools in MAB may be utilized for enhancing prompt optimization methods in the future.\n\n- The results (e.g., in Figure 2 and Tables 2-4) clearly demonstrate the efficacy of the proposed TRIPLE framework for prompt evaluation & selection and how it may also improve end-to-end prompt optimization by integrating the framework with popular prompt generation schemes. According to the results shown, the gains turn out to be fairly significant and also consistent across different tasks/settings.", "weaknesses": "- As the main contribution of this paper seems to lie in making systematic connections between prompt optimization and best arm identification in MAB, after establishing these connections, the improvements achieved in prompt optimization are direct outcomes of adopting existing FB-BAI algorithms in the MAB literature. As a result, novel methodological contributions that go beyond the utilization of existing FB-BAI methods proposed and well-studied in MAB for prompt optimization purpose are somewhat limited.\n\n- While the paper discusses the issues that arise when the prompt pool is huge (hence a large number of arms) and also proposes practical schemes to address these issues, there is no in-depth discussion of how the pool size affects the overall prompt optimization performance. There should be further discussion on this issue and the paper should include at least some empirical results (e.g., similar to Figure 3) that shows how the gain may be affected by the prompt pool size.\n\n- In Figure 2, it is unclear when the \"normalized evaluation score\" exceeds 1 (i.e., outperforming the uniform scheme\"). Please add a horizontal line to show which bars are above/below 1.\n\n- The comparison with BO-EI is interesting but as BO performance tends to vary widely depending on the acquisition function used, it would be meaningful to provide additional comparison based on at least one or two additional acquisition functions. Especially, using BO acquisition functions aimed at different aspects (e.g., uncertainty vs diversity) may be helpful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing this work! We are excited to hear your recognition on the potential of the proposed framework and the compelling results. For the raised concerns and questions, we would like to provide the following point-to-point responses.\n\n---\n>**Weakness 1.** As the main contribution of this paper seems to lie in making systematic connections between prompt optimization and best arm identification in MAB ... novel methodological contributions that go beyond the utilization of existing FB-BAI methods proposed and well-studied in MAB for prompt optimization purpose are somewhat limited.\n\n**Response 1.** We would like to first thank the reviewer for recognizing the contribution of this work in identifying the connection between prompt optimization and fixed-budget best arm identification (BAI-FB). Indeed, as the reviewer noted in the strength section, this connection allows us to not only leverage existing tools from BAI, but also flexibly utilize future developments.\n\nFor the question about additional methodological contributions, we would like to emphasize the following aspects. (1) The designs proposed in Section 4 for handling large prompt pools introduce new methods to leverage prompt embeddings. Especially, TRIPLE-CLST effectively integrates the clustering structure with BAI-FB techniques, leading to a novel two-phase design. (2) Moreover, the extensions in Section 6 to example selections are original approaches that carefully built upon the unique characteristics of in-context prompts, e.g., the importance of both quality and diversity as detailed in Appendix D. The superior performance of these proposed methods has been demonstrated with the experimental results in Sections 5 and 6. We believe these designs provide novel methodologies to benefit existing applications and guide future investigations in this direction.\n\n---\n>**Weakness 2.** While the paper discusses the issues that arise when the prompt pool is huge (hence a large number of arms) and also proposes practical schemes to address these issues, there is no in-depth discussion of how the pool size affects the overall prompt optimization performance...\n\n**Response 2.** During the rebuttal period, we have scaled the number of candidate prompts to $1000$. The performances on two tasks are presented in Figure 2 of the attached PDF. It can be observed that the proposed TRIPLE framework still achieves improved performances with this larger number of candidate prompts. We will add these and more results with other sizes of prompt pools to the revised paper.\n\n\n---\n>**Weakness 3.** In Figure 2, it is unclear when the \"normalized evaluation score\" exceeds 1 (i.e., outperforming the uniform scheme\"). Please add a horizontal line to show which bars are above/below 1.\n\n**Response 3.**  Thank you for this helpful suggestion! We have revised the original Figure 2 (and other similar figures) to include the suggested horizontal line. In addition, a star is added to mark the best-performing method on each task, facilitating the visualization. A part of the revised Figure 2(a) is contained in the uploaded PDF as Figure 1 to serve as one demonstration. The superiority of TRIPLE can be clearly evidenced there. We are happy to incorporate any further advices to make this work more accessible.\n\n\n---\n>**Weakness 4.** The comparison with BO-EI is interesting but as BO performance tends to vary widely depending on the acquisition function used, it would be meaningful to provide additional comparison based on at least one or two additional acquisition functions. Especially, using BO acquisition functions aimed at different aspects (e.g., uncertainty vs diversity) may be helpful.\n\n**Response 4.** Thank you for providing this helpful suggestion! During the rebuttal period, we have conducted further experiments on Bayesian optimization (BO) with another acquisition function--probability of improvement. The results, labeld as BO-PI, on two demonstrating tasks are reported in Figure 2 of the attached PDF. It can be observed that TRIPLE is still superior to the performance of BO with different acquisition functions. The complete results will be added to the revised paper.\n\n---\n\n>**Question 1.** Please provide some discussion on how TRIPLE may be used when the prompt optimization task has multiple objectives. How can connections to best-arm identification be leveraged in case of multi-objective prompt optimization?}\n\n**Response 5.**  Thank you for raising this interesting question on multi-objective prompt optimization. The proposed TRIPLE framework provides many possibilities to leverage the rich studies on multi-armed bandits (MAB) in prompt optimization, building upon the identified connection. As one demonstrating example, we have discussed the extension to perform example selection for in-context prompts in Section 6.\n\nSimilarly, to perform multi-objective prompt optimization, TRIPLE should incorporate suitable techniques from the studies on multi-objective fixed-budget best arm identification in MAB, which itself is an interesting topic in the bandit research community that has attracted much recent attention. In particular, we believe the following two approaches could be ideal candidates to begin with: under a fixed budget, [R1] has proposed an algorithm to identify the Pareto-optimal arm sets, and [R2] investigates how to find the arm maximizing one attribute while ensuring other attributes are larger than given thresholds.\n\nWe will include the discussions on this interesting direction in the revised paper. It is indeed the flexibility and rich potential of TRIPLE fascinate us, and we sincerely hope this work can contribute to research communities of both prompt optimization and bandits.\n\n[R1] Kone, C., Kaufmann, E., and Richert, L. (2024). Bandit Pareto Set Identification: the Fixed Budget Setting.\n\n[R2] Faizal, F. Z., and Nair, J. (2022). Constrained pure exploration multi-armed bandits with a fixed budget.\n\n---", "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:
Dear Reviewers,

Thank you for reviewing this work and giving the helpful comments! We have provided point-by-point responses, which hopefully can address the raised questions and concerns. It will be our pleasure to have further discussions and incorporate any suggestions you may have.

Together with this response, a PDF containing multiple new experimental results are uploaded, detailed in the following. We will add the complete versions of these results to the revised paper. 

- [Table 1] The performance comparisons between the proposed TRIPLE framework and baselines on two new datasets, GLUE and GSM8K. The superiority of TRIPLE is further evidenced.

- [Figure 1] A sample of the improved presentation of the original Figure 2(a). We will make similar enhancements on all the figures. Let us know if you have further suggestions to improve the presentation of results.
  - One horizontal line is added to label the performance of the Uniform baseline, over which the other performances are normalized.
  - A star is added to remark the best method in each task.
  - The number of prompts and the budget in this experiment are labeled in the top left corner to facilitate references.

- [Figures 2 and 3] Further investigations on the impact of the size of the prompt pools and a new baseline BO-PI. Figure 2 demonstrates that with a large prompt pool (i.e., $1000$ prompts), TRIPLE still improves over other baselines (including the new BO-PI), illustrating its broad applicability. Figure 3 further shows that the size of the prompt pool does not have major impact on the performance distributions of its contained prompts, evidencing that the obtained results are sufficiently representative.

Thank you again and looking forward to further discussions!

Best regards,
Authors of Submission 13481

Meta-review: This paper introduces TRIPLE, a framework for efficient prompt selection in large language models that optimizes performance within budget constraints by leveraging techniques from multi-armed bandit theory, demonstrating significant improvements over existing methods.

All reviewers appreciate that connecting prompt optimization to best arm identification under fixed budget is an interesting and worthwhile exploration, and is well-justified theoretically. The reviewers also appreciate the promising empirical results, supporting the authors' claim that better search algorithms are needed (and somewhat overlooked in the literature so far). On the flip side, there are questions raised on the comprehensiveness of the tasks, the performance of the algorithm with an expanded candidate prompt pool size, comparison against additional baselines, and some clarity issues that the authors were largely able to address satisfactorily during the rebuttal. 

After rebuttal, all reviewers unanimously recommended the acceptance of the paper, and the AC also concurs with this recommendation after reading through reviews and subsequent author-reviewer discussions. Having said that, the AC agrees that there are several valuable suggestions from the reviewers that the authors should consider when preparing the camera-ready version, such as the discussions on more complicated and realistic tasks and toning down some rather hyperbolic claims (both made by Reviewer 55GB).
Decision: Accept (poster)