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_cc_2024_Conference
Published: 2024-05-15 04:27:06

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.

Main paper: 
 introduction: 
 Large language models (LLMs) have rapidly changed technology landscapes in our society [20, 72, 73, 11, 55] . Researchers continuously find effective ways to unlock their potential on 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 a labor-intensive process [54] . Thus, there is a growing interest to perform automatic prompt optimization [90, 79, 21, 19, 59, 84, 28, 58, 60, 81] .While these studies have proposed different prompt optimization designs, they commonly follow the approach of generating a pool of candidate prompts and then selecting from them. With a deeper look, it can be recognized that the focus in these existing works largely leans towards how to generate the candidate pool, while limited attention has been paid towards how to select from the candidates.For example, many works [35, 79, 28, 59] directly evaluate all the generated prompts on the entire development dataset. However, this less-emphasized selection process typically requires accesses to LLMs, which are often (1) financially costly (e.g., each OpenAI 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., OpenAI 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 an unaffordable cost without a 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 a 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 LEarning), by establishing a novel connection between prompt optimization and multi-armed bandits (MAB) [41] . In particular, we focus on harnessing the power of fixed-budget best arm identification (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 baselines. In particular, on GPT3.5 and Llama2, compared with baseline methods also not using prompt embeddings, the basic TRIPLE-SH and TRIPLE-CR achieves performance improvements by (on average) 3% to 16%. When leveraging prompt embeddings, the enhanced TRIPLE-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 [60] , with end-to-end performances significantly improved over their original implementations.• This work extends broadly to providing a 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 to 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 [14, 12] . Experimental results illustrate that the extensions of TRIPLE achieve superior performance, demonstrating its rich potential. Key Related Works. We discuss a 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 a naive filtering strategy without theoretical 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 to 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, as 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. 5, the TRIPLE solution outperforms the previously adopted methods empirically. 
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 a distribution ∆ V over the language space V. The answer Ŷ ∈ V given by the LLM is assumed to be sampled from f (X) as Ŷ ∼ f (X). Note that instead of treating f (•) as a deterministic function providing a specific output answer, we generally consider the practical setting where the answers of LLM exhibit a certain level of randomness.For prompt optimization, we aim to find a prompt p such that when concatenated with inputs X of a certain task (i.e, as [p; X]), it provides good performance in expectation with respect to the input distribution I X and the inherent randomness of LLM f (•). The performance is measured asµ(p) := E X∼I X E Ŷ ∼f ([p;X]) [s(X, Ŷ )],where s(X, Ŷ ) denotes a score function that measures the quality of the output Ŷ 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 to black-box LLMs, i.e., only have access to an API f (•) and no access to the intermediate structure or 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 a good prompt requires interactions with the LLM (i.e., sample Ŷ ∼ f ([p; X]) and evaluating its responses (i.e., obtain score s(X, Ŷ )). However, as mentioned in Sec. 1, 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 * ) under constraints of black-box, discrete, interpretable, and a limited budget.Directly tackling this prompt optimization problem has been widely recognized as challenging even without the constraint of a limited budget [50] . As highlighted in Pryzant et al. [60] , Chen et al. [13] , it essentially requires performing a black-box discrete optimization. Instead, many proposed methods rely on the pipeline of first generating a pool of candidate prompts and then selecting from it [35, 90, 79, 59, 28] . The prompt generation can either be performed manually or follow designed 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:p * := arg max p∈P µ(p). While many efforts have been devoted along this line, we recognize that they are largely focused on how to generate prompts, while limited attention has been paid to how to select from the already generated prompts (as mentioned in Sec. 1 and further discussed in Appendix A).Naive treatments, such as uniformly evaluating all prompts, are understandable since budget limitations are not considered previously, i.e., unlimited 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 at 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. 1 .Different score functions s(•, •), i.e., metrics for evaluation, are used for diverse tasks in the Instruction-Induction and BigBench-ii datasets, namely "Exact match", "F1-score", "Multiple choice within", and "Multiple choice f1-score". 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 1 for outputs exactly matching the label, and 0 otherwise. • f1-score: Applied to tasks with complex targets like long sentences (e.g., "informal to formal", "negation", "sentence similarity"), this metric (defined in Definition E.1), evaluates the overlap between the LLM response and the label.• Multiple choice within: Suitable for tasks with several correct answers, it scores 1 if the LLM's response matches any correct answer and 0 otherwise. We utilized this metric for tasks "rhymes", "translation-en-de", "translation-en-es", "translation-en-fr" and "word in context".• Multiple choice f1-score: Employed for tasks with multiple, lengthy correct answers ("common concept" task), it calculates the highest f1-score across all potential correct answers.Definition E.1 (f1-score). Suppose the question has a labeled answer T and the response of the LLM is A, then the f1-score for this answer is defined as:S f 1 = 2 × P × R P + R ,where P = l m /l A stands for the precision of the response and R = l m /l T the recall of the response.Here we use l A and l T to denote the length of the response and label while l m is adopted to represent the number of matching words between A and T .For the specific score function adopted for the BigBench-ii dataset, we advise referring to the "metric" label for each task therein. This label indicates the appropriate metric ("Exact match" or "Multiple choice within") for the optimal evaluation.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: We included a 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 no 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 (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency 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 fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
connecting prompt optimization with best arm identification: 
 We provide a new perspective of prompt optimization through the lens of tools in multi-armed bandits (MAB) [41, 40] . 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) is established. Based on this connection, we propose to fully leverage the rich toolbox from BAI-FB to perform efficient prompt optimization.The research of multi-armed bandits (MAB) has a long and rich history; see representative surveys of Lattimore and Szepesvári [41] , Bubeck et al. [10] . The most basic form of MAB, i.e., the finite-armed stochastic bandits, considers a system with a set K finite arms (i.e., actions) that provide stochastic rewards when pulled. When interacting with the system, the agent can select one arm k ∈ K to pull at each time, and she receives a stochastic reward:r k ∼ dist k (ν k ), where dist k (ν k ) denotes the action k's reward distribution with an unknown expectation ν 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 max k∈K ν k [4, 27, 32] . 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 as it only focuses on obtaining information to find the best arm. We here particularly note that although the designs targeting regret minimization often can converge to the optimal arm k * given a sufficient period of time, they are known to be inefficient for the objective of best arm identification in the MAB studies.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 K;• Using a prompt p to interact with LLM can be viewed as selecting a bandit arm k to pull in MAB;• The feedback of the score function, i.e., s(X, Ŷ ), provides the reward signal r k , where dist k (ν k ) characterizes the randomness of X ∼ I X and Ŷ ∼ f ([p; X]). The expected performance µ(p) is the counterpart of the expected reward ν k 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 a 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 optimization and BAI established, we further consider the constraint of learning under a limited budget. We argue that this aligns with one of the main research directions in BAI called fixed-budget best arm identification (BAI-FB) [37, 75, 22] . BAI-FB particularly considers the problem of maximizing the probability of correctly identifying the best arm k * while not pulling arms more than T times. It can be observed that this formulation matches the goal of prompt optimization under a limited budget; thus BAI-FB provides 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 1 . To avoid confusion, in the remainder of this paper, we will adopt the notation of prompt optimization as introduced in Sec. 2.As mentioned, we recognize that prompt optimization under a limited budget is a matching application scenario for BAI-FB. In this paper, we propose a 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. 2 and 3 of Appendix C.. SH is one of the first provably efficient BAI-FB designs [37] and remains popular after a decade of its proposal. It follows a protocol that divides the total budget N into ⌈log 2 (|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 is more adaptive than SH (and SR), which makes it appealing both theoretically and practically.While MAB has found broad applications in recommender systems [44] , healthcare [63] , wireless communications [24] , and beyond [8] , a systematical connection between MAB and prompt optimization has not been established before to 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 et al. [38] , Atsidakou et al. [2] Remark 3.1. As mentioned in Sec. 1, Pryzant et al. [60] , Lin et al. [48] leverage specific MAB designs to perform prompt selection without a comprehensive discussion as above on their connection. Moreover, Pryzant et al. [60] argues that UCB [5] is suitable, while Lin et al. [48] also uses a UCBvariant, NeuralUCB [89] , as 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.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
handling large candidate pools via prompt embeddings: 
 The connection built in the last section provides us with the core idea of leveraging BAI-FB 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 to 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 be shared among them, which is often not the case in prompt optimization. For a prompt optimization problem, the underlying task is often stable, e.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 similarities. For example, the candidate prompts generated via demonstrating LLMs [90] often share similar structures and differ only in a few words or 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 → R d , to obtain the sentence embedding of the prompts: e(p) := embed(p) ∈ R d , E := {e(p) : p ∈ P}, where d refers to the embedding dimension. In the experiments, the OpenAI 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 a white-box LLM [13, 48] . With the obtained prompt embeddings, we propose two useful enhancements to further improve the learning effectiveness when the pool of candidate prompts is large.Algorithm 1 TRIPLE-CLST Since the key challenge is a large pool of candidate prompts, an intuitive idea is to effectively decrease the size of the pool. We thus propose a two-phased BAI-FB scheme for prompt optimization. In Phase I, the entire pool of candidate prompts is clustered into several groups based on their embeddings, and BAI-FB is performed on 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-FB designs can be incorporated, e.g., SH and CR. The entire procedure, referred to as TRIPLE-CLST, is described in Alg. 1.Figure 2 : Clusters for 30 prompts for "movie recommendation" (left) [69] and "rhymes" (right) [30] . Prompts in the same cluster are labeled by the same color and shape. The performance of each prompt is represented by the size of its shape (the larger the better). The embeddings are projected using T-SNE [29] .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 I can quickly eliminate the prompts with poor performances, leaving a 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 cluster share similar performances. In particular, it can be observed that the prompts in the same cluster (i.e., the same color and shape) share similar performance (i.e., similar sizes). Especially, the optimal prompt (marked by the red star) is clustered together with a few prompts with comparably near-optimal performances.Besides clustering, another idea to incorporate the prompt embeddings is to learn a common function (e.g., an MLP) to predict the prompt performances based on their embeddings. Similar ideas of function approximation have also been widely adopted in MAB literature to share information among large action spaces, with functions ranging from linear ones [1, 82] to neural networks [91, 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. 4 of Appendix C.The general phased elimination flow of SH described in 3.3 is inherited. The major difference is that SH uses sample means to perform eliminations. GSE [6] , on the other hand, leverages collected samples from previous phases to train a reward function g θ (•) : R d → R that maps prompt embeddings to the predicted performance, which is further used to eliminate prompts. 
experiments: 
 In this section, extensive experimental results are reported to evaluate the efficiency of TRIPLE across diverse prompting tasks from two standard datasets: Instruction-Induction [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.1). Full experimental details can be found in Appendix E. The complete results of 47 tasks are reported in Appendix F, while here we particularly focus on 12 representative tasks, which are not too hard (i.e., all generated prompts achieve nearzero performances) or too easy (i.e., all generated prompts achieve near-one performances). The experimental codes can be found at https://github.com/ShenGroup/TRIPLE.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 on all development data [28, 59] which corresponds to uniformly dividing the total budget to test all prompts. • UCB. The upper confidence bound (UCB) method is a 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 et al. [60] . • BO. Bayesian optimization (BO) with expected improvement (EI) acquisition function is adopted in Chen et 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 of BO, another acquisition function, i.e., probability of improvement (PI), is also adopted. • NeuralUCB. Lin et al. [48] uses NeuralUCB [89] Performance with fewer prompts than budget. We first test candidate pools with 30 prompts per task. Results reported in Fig. 3 (a) reflect the selection performance with an overall budget of 150. It can be observed that TRIPLE-SH and TRIPLE-CR 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 on average for GPT-3.5; 6% and 7% for Llama2). Moreover, for methods using Table 2 : Averaged performance ranks of 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. prompt embeddings, the enhanced TRIPLE-CLST and TRIPLE-GSE also demonstrate remarkable improvements over BO-EI (11% and 10% on 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 a 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.e., BO, NeuralUCB, TRIPLE-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).A 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.5, Llama2, Mistral, Gemma). It can be observed that in varying setups and with different LLMs, 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. 3 (a)), 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 a 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-GSE still achieve an approximate 8% improvement. Once the budget reaches 30 evaluations per prompt on average (i.e., 900 overall), all methods provide approximately the same performance as 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. 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 in 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 (e.g., 100) is enough to further perform the selection and find the final prompt candidate to use.We now explore whether TRIPLE can provide performance improvements when plugged into end-toend prompt optimization pipelines that include both prompt generation and selection. To this end, Table 3 : Performances of integrating TRIPLE in the end-to-end pipelines using GPT-3.5. The baseline methods reported in the original implementations are labeled as (b). For each task, the best score across two pipelines is marked as red, and the best score in the remaining pipeline is highlighted as yellow. TRIPLE-CR are selected over TRIPLE-SH due to its better performance observed in the previous experiments. TRILE-CLST is ignored in the tests with APO, as it is ineffective to cluster only 10 prompts. APE [90] APO [ 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 on average (i.e., 150 LLM accesses overall). Zhou et al. [90] suggest a non-iterative version with uniform evaluations of prompts, which is taken as the baseline here. • APO. The APO pipeline [60] is an 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 a 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 is adopted as the baseline here. We note that OPRO [81] shares a similar iterative scheme as APO while using a 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 of the TRIPLE framework, i.e., it can benefit any prompt optimization pipelines requiring a selection component.As noticed in Brown et al. [9] , LLMs can perform varying tasks when prompted with several related examples, i.e., few-shot prompting. It 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 terminology introduced in Sec. µ(g 1 , • • • , g M ) := E X∼I X E Ŷ ∼f ([g1,••• ,g M ;X]) [s(X, Ŷ )].The optimal selection of examples can be defined as(g * 1 , • • • , g * M ) := arg max g1,••• ,g M ∈G µ(g 1 , • • • , g M ).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 is the focus of the study on combinatorial MAB (CMAB) [16, 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 µ(g 1 , • • • , g M ), TRIPLE-SAR and TRIPLE-CSAR are proposed, extending Chen et al. [14] , Gabillon et al. [23] , which are further discussed in Appendix D. The performances of these extensions are presented in Table 4 , with more details and results provided in Appendix E.6 and F. Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes]Justification: The experiment codes (together with detailed instructions) are available at https://github.com/ShenGroup/TRIPLE. The adopted datasets are all open-source ones. This should be sufficient to make anyone who wants to reproduce our experiment results capable of easily executing the experiments.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: In Appendix E, we have included all the experimental details used for our experiment execution and how the hyper-parameters are chosen.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 a 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. 
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 a 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 a 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.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes]Justification: We did include the error bars and the standard deviation in all the experimental results that need this information.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence 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 are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not 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 as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Our paper does not pose such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes]Justification: We have properly credited all the code sources, data sources, and open-source models in our 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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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. 
 
 Appendix: Prompt Optimization. The study of prompt optimization (also known as instruction learning) focuses on automatically learning suitable prompts, which is more scalable compared with manual prompt engineering. Many efforts have been devoted to this direction [25, 77, 68, 86, 85] , which is summarized in a recent survey of Liu et al. [50] . The early studies mostly consider optimizing soft prompts (i.e., continuous vectors) [42, 46, 88, 51, 78] or discrete but not interpretable prompts [65, 64] for white-box LLMs, where different gradient-guided optimization techniques are leveraged. The recent research efforts, instead, are more focused on considering the more practical setting of learning interpretable prompts for black-box LLMs [59, 90, 60, 79, 28, 58, 13] , where the generatingthen-selecting pipeline in Fig. 1 is often adopted.Compared with previous investigations, this work additionally considers a limited budget in an explicit fashion, which we believe is a practical but under-investigated concern. Most of the previous methods perform selection based on evaluating prompts on all development data [35, 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 a 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-art BAI-FB designs (i.e., CR [75] and GSE [6] ) and proposing embedding-based enhancements. It is worth noting that INSTINCT [48] also incorporates one MAB method, i.e., NeuralUCB [89] , to prompt optimization. However, as mentioned in Sec. 1, NeuralUCB 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 [7] is adopted for selection. Lin et al. [47] extends the prompt optimization framework to consider preference feedback.Multi-armed Bandits. Here we briefly discuss the representative studies of MAB, with comprehensive surveys available in Bubeck et al. [10] , Lattimore and Szepesvári [41] . As mentioned in Sec. 3.1, the target of learning in a MAB system can be roughly categorized as regret minimization and best arm identification. The regret minimization designs target achieving a desired balance between 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] . 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 a threshold [27, 32, 66, 33] . Besides leveraging BAI-FB as in this work, it is imaginable that BAI-FC designs can 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 a systematical connection between MAB and prompt optimization has been established to the best of our knowledge.B.1 Broader ImpactsThis work opens an interesting direction on the connection between MAB and prompt optimization.In the following, we discuss a 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 LLM accesses. This model provides an 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 to further consider prompt-specific costs.• Other BAI designs. Based on the connection between prompt optimization and BAI, this work has incorporated several BAI designs. However, the research on MAB has a long and rich history, where many other BAI designs can also be leveraged. For example, the Bayesian perspective provided in Komiyama et al. [38] , Atsidakou et al. [2] and the function approximation scheme adopted in Yavas and Tan [83] , Yang and Tan [82] are all worth investigation. Moreover, the multi-objective designs developed in Kone et al. [39] can be valuable extensions. This work is important in delivering the message that (both existing and forthcoming) BAI methods can benefit prompt optimization, which may inspire future explorations.• Structured prompts. In Sec. 6, we discuss how to extend TRIPLE to select examples for fewshot prompts. Based on the insights obtained in this work, we believe this direction is work further exploration. Moreover, other forms of structured prompting methods, such as Chain-of-Thoughts [76] , are also interesting topics, which may further require multi-step techniques such as reinforcement learning.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, 3, and 4, respectively.Algorithm 2 TRIPLE-SH In this section, we provide additional discussions on the extension to example selection mentioned in Sec. 6. 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 on heuristics that are well-recognized and widely evidenced. With a deeper understanding of the few-shot prompt developed in later research, the perspective provided by TRIPLE and these designs would still be beneficial to 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, it contributes positively to the overall few-shot performance [61, 45] . Based on this heuristic, we adapt the CSAR design [14, 12] to perform example selection, which can identify M prompts from G with the highest individual performances, i.e., µ(g m ). The details are provided in Alg. 5.1: Input: the pool of candidate prompts P, budget N 2: Initialization: set n(p) ← 0, μ(p) ← 0 for all p ∈ P; set the active prompt set A ← P 3: for time τ = 1, • • • , N do Obtain score s τ ← s(x τ , ŷτ ) Update the active prompt set A as the set of ⌈A/2⌉ prompts in the original A with the highest μ(p) 8: end for 9: Output: the remaining active prompt p * SAR. It is also noticed in previous studies that selecting a 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 1 , • • • , G M }, based on the embeddings of the examples. Then, for each cluster G m , we find one example g m in it with the highest one-shot performance µ(g m ).To perform such a selection process efficiently, the SAR design [12] is leveraged. In this way, the diversity and quality of the selected examples are both guaranteed. The details are provided in Alg. 6.In this section, we include full details of our experiments, while the complete codes are also uploaded in the supplementary materials.Before further details, we first list the LLM models that we adopted for experiments:• GPT-3.5: gpt-3.5-turbo-1106 [55] ,• Llama2: Llama2-7b [73] ,• Gemma: Gemma-7b [70] • Mistral: Mistral-7B-v0.2 [34] As we use chat-based LLMs, initial system instructions are needed, where the officially recommended system instructions are adopted in experiments, as shown in Fig 7 . Interact with the targeted LLM using each example g ∈ A as a one-shot prompt for Tp -Tp-1 times 6:Update the sample means {μ(g) : g ∈ A} using the collected samples 7:Obtain order σ such that μ(g σ( 1)) ≥ μ(g σ(2) ) ≥ • • • ≥ μ(g σ(|A|) ) 8:Compute gaps∆ σ(r) ← μ(g σ(r) ) -μ(g σ(M -|Gacc|+1) ) if r ≤ M -|G acc | μ(g σ(M -|Gacc|) ) -μ(g σ(r) ) if r ≥ M -|G acc | + 1, ∀r ∈ [|A|] 9:Compute g ′ ← arg max g∈A ∆ g 10:Update Interact with the targeted LLM using each example g ∈ A as a one-shot prompt for Tp -Tp-1 times 7:G acc ← G acc ∪ {g ′ } if μ(g ′ ) ≥ μ(g σ(M -|Gacc|+1) ); G rej ← G acc ∪ {g ′ } otherwise 11: Update A ← G/(G acc ∪ G rejUpdate the sample means {μ(g) : g ∈ A} using the collected samples 8:if ∃m ∈ M such that |A m | = 1 then 9:Update M ← M/{m} ∀m ∈ M, compute ∆ m ← max gm∈A m {max ḡm∈A m μ(ḡ m ) -μ(g m )} and g ′ m ← arg max gm∈A m {max ḡm∈A m μ(ḡ m ) -μ(g m )} 13: Compute m ′ ← arg max m∈M ∆ m 14: Update A m ′ ← A m ′ /{g ′ m ′ } 15:end if 16: end for 17: Output:the set {g * 1 , • • • , g * M } E.The prompt generation process to obtain the fixed prompt pools largely follows the one in APE [90] , i.e., demonstrating LLMs with examples. In particular, in the generation of each prompt, we sample 10 examples from the training set to demonstrate LLMs with two types of generation templates: 'forward' and 'backward', which are illustrated in Fig. 8 . 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-v0.2 we use exhibit difficulties in generating useful prompts from the 'backward' template, possibly due to its more simplified structure.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., gradients) for the selected prompts from previously incorrectly answered examples. Then, with the selected prompts and the identified fault reasons, the LLM is instructed to create {num_prompts} new prompts for further selection. The adopted templates in our experiments are shown in Fig. 9 , where we set {num_feedback} to 2 and {num_prompts} to 5. We believe this configuration ensures that each iteration effectively identifies key areas of improvement and sufficiently expands the pool of potential prompts.Figure 9 : The adopted templates for experiments with APO [60] : fault identification (i.e., "gradient") (left) and new prompt generation (right).Obtaining Embedding. A critical component of both TRIPLE-CLST and TRIPLE-GSE is the extraction of sentence embeddings for the candidate prompts. In our experiments, the prompts are first tokenized using the cl100k_base tokenizer. Then, the tokenized prompts are input into the text-embedding-ada-002 model [56] , converting them into continuous vectors.In experiments with TRIPLE-CLST, the number of clusters is set as L = ⌈ |P|⌉ and a third of our total budget is allocated for the initial phase, i.e., N 1 = N/3. The k-means algorithm is employed as the clustering method. For more stable performance, Phase I is configured to find the top L/2 clusters, instead of the optimal one, which safeguards against the 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 OpenAI 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 a projection to 64 dimensions using a matrix with random elements from the standard normal distribution. This technique is also incorporated in Chen et 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.1 in our experiments.In the results reported in Further details regarding the adopted baselines are provided in the following.• Random. To validate the benefits of interactions with the targeted LLM during the selection, one commonly adopted baseline is to randomly select the required number of examples from the candidate pool. • Uniform. Similar to the uniform baseline adopted in Sec. 5, 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-SAR, the same process of obtaining embeddings as described in Appendix E.5 with also k-means as the algorithm to perform clustering.We use a workstation with two Nvidia-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 OpenAI API is needed to perform learning. Under our network condition, one API call typically takes around 1 second.Additional experimental results are provided to supplement observations in the main paper.To further guide practical implementation, we additionally investigate how to select a reasonable budget. In particular, we focus on the efficiency of various prompt selection algorithms in identifying a "good" prompt -either the optimal prompt in the pool or achieving 95% or better of the optimal prompt's performance. Fig. 11 illustrates that initial increases in budgets significantly improve the probability of identifying a good prompt, but this benefit tapers off with further budget expansion. This finding suggests that starting with a modest budget and incrementally increasing it is the more effective approach, stopping when additional investment no longer translates into significant returns. 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.The experiments are further extended to more diagnostic tasks (GLUE [74] ) and math problem datasets (GSM8K [17] ). More specifically, TRIPLE methods are deployed to select prompts for the task "Cola" in GLUE (on distinguishing linguistic acceptability) and also chain-of-thought prompts for GSM8K (on mathematical reasoning). The results are presented in Table 5 , where it can be observed that the superiority of TRIPLE is 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. In the main paper, we provide experimental results of 12 representative tasks from the overall 47 available tasks in Sec. 5. In the following, the complete results are discussed.• |P| = 30, N = 150: results on the 24 available tasks in the Instruction-Induction dataset [30] are illustrated in Fig. 13 (a) (GPT-3.5), and 13(b) (Llama2);• |P| = 30, N = 150: results on the 23 available tasks in the BigBench-ii dataset [69] are illustrated in Fig. 14 (a) (GPT-3.5), and 14(b) (Llama2).• |P| = 150, N = 100: results on the 24 available tasks in the Instruction-Induction dataset [30] are illustrated in Fig. 15 (a) (GPT-3.5), and 15(b) (Llama2);• |P| = 150, N = 100: results on the 23 available tasks in the BigBench-ii dataset [69] are illustrated in Fig. 16 (a) (GPT-3.5), and 16(b) (Llama2).Also, the complete performances of example selection for few-shot prompts discussed in Sec. 6 are presented in Fig. 17 (Instruction-Induction) and 18 (BigBench-ii).Besides the average return, another key aspect of prompt selection is the frequency of selecting a good prompt. In Table 8 , we further demonstrate the best prompt identification frequency of different algorithms across 20 selected tasks from 5 independent runs. Table 6 : Clusters for "movie selection": the best prompt overall is marked in red, and the best prompt in each cluster in yellow.Cluster Prompts 0The instruction was to select the movie title that appeared the most frequently among the given choices.The instruction was to choose the correct movie from the given choices based on the input movie titles.Based on the given inputs and choices, the task was to select the option that matched the given genre film.The instruction was to choose the movie title from the given choices that correspond to the movie titles in the input.The instruction was to select the movie from the given choices. The instruction was to determine which movie from a list of choices the user should watch based on the inputted movies.The instruction was to select the movie title that received the most number of votes from the given choices.The instruction was to choose the correct movie based on the given choices.The instruction was to provide the output movie based on the given choices.The instruction was to choose one movie from the given choices.The instruction was to select the correct movie from the given list of choices.The instruction was to provide the output movie choice for each given input movie titles and their corresponding choices. The instruction was to recommend one movie out of the given choices.The instruction given was to determine the best choice from a given list of movies, based on a set of choices and their corresponding scores.The instruction was to choose the most suitable movie choice based on given input movies. There were multiple choices for each input, and the selected choice was the one with a value of 1. The chosen movie is the output.1Choose the correct answer based on the given choices.Choose the correct answer from the given choices. 2In each case, provide output responding to the relative place of these Nos among Fraser beat shape singers then, the relative here is taken negatively ( greater-worse place's id it falls in the franchise with counseling distribution) The instruction was to determine the correct output based on a given input and its corresponding choices.The instruction was to determine the output choice based on the given inputs and options.The instruction was to select the choice with the highest point value.The instruction was to select one choice from each list and provide the selected choice as the output.The instruction was to select the correct choice from each input sequence.RSelect the correct output film title from the given list of input films.Choose the correct title from a list of options.Select one movie from the given choices based on the input movies. Determine the correct movie choice based on the given options for each input. Given a list of movie titles, you need to choose the correct movie from the given choices that matches closely with the given titles. Find the correct output movie from the provided choices. Select the movie from the given choices. 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 in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.Extension: Selections of Examples for Few-shot PromptsBased 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 on how to leverage TRIPLE to efficiently select examples for few-shot prompts.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 AI 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 societal impacts. 


Decision: 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).

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_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?

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 evalutions per prompt, so it is very compelling nonetheless.

3. 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.
questions: questions: Do TRIPLE-SAR and CSAR take ordering into account?
limitations: limitations: n/a
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.

- 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.

- 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.

- 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.

- Recent baselines with/without embeddings like ZOPO and, OPRO should also be considered.

- 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).
questions: 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)$?

See other weaknesses above.
limitations: limitations: Yes.
paper_summary: paper_summary: This paper studies prompt optimization using BAI-FB. There are several contributions:
1. Draw a connection between prompt optimization with the BAI-FB
2. Benchmark different acquisition function for prompt optimization
3. Extensive experiments are done to show the effectiveness of the proposed prompt optimization and extend the setting to example selection.
strength_weakness: strength_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
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.
questions: 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: limitations: See my weakness
paper_summary: paper_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.
The 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.
strength_weakness: strength_weakness: - 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.

- 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.

- 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.

- 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.
questions: 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: 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.

Comments: title: Looking forward to Discussions
Thanks for your response
Thank you
Thank you
Response to authors
comment: We are glad to hear that the responses are helpful in addressing your concerns. Thank you for providing further valuable suggestions on the clarity and comparisons! We will carefully incorporate them into the revised paper, in particular additional illustrations on TRIPLE-CLST/GSE and empirical comparisons with OPRO.
Thanks for the additional results and some clarifications. 

>More descriptions will be added to Section 4 to highlight the empirically remarkable TRIPLE-CLST/GSE

As the justification and description of the method are lacking here, I am not convinced by the novelty of this work. I hope the authors can improve this part in their revision.

> 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.

OPRO should be a much stronger baseline than APO. I think the authors should consider the strong and representative works in this area.

---
Some of my concerns are addressed, although the comparison and clarity remain an issue. I will increase my score accordingly based on the additional results provided.
Dear Reviewer 7VZU,

We would like to first thank you again for the valuable comments and suggestions on our work. As the discussion period is concluding, we would be grateful if you could share any further concerns or feedback you might have. If our responses have sufficiently addressed your concerns, we hope that you could consider raising the score of your evaluation. Thank you for your consideration.

Best,

Authors of Submission 13481
It is our pleasure to hear that the responses are helpful in addressing your concerns. We will carefully incorporate your comments in the revised paper. Thank you for recognizing the contributions of this work!
Thanks for your response, some of my concerns are addressed, i will keep my score.
We greatly appreciate your recognition of the contributions of this work! We will revise the paper accordingly to incorporate your suggestions.
Thank you for recognizing the contributions of this work! We will carefully incorporate your suggestions in the revised paper.
I would like to thank the authors for their careful response.
The authors' additional clarifications have addressed many of my previous concerns and I am increasing the rating as a result.
Thank you for the detailed response. It helps me maintain my high score.