Efficient Prompt Optimization Through the Lens of Best Arm Identification

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.

---

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.

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.

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

---

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

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.

---

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.

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.

---

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.

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.

---

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?}

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.

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

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

[R1] Kone, C., Kaufmann, E., and Richert, L. (2024). Bandit Pareto Set Identification: the Fixed Budget Setting.

[R2] Faizal, F. Z., and Nair, J. (2022). Constrained pure exploration multi-armed bandits with a fixed budget.

---

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.

---

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.

Response 1. We would like to provide the following discussions to highlight the novelties of this work.

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

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

We believe both the introduction of BAI-FB and the proposed designs contribute novel ideas to the study of prompt optimization.

---

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.

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.

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

---

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.

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.

[R1] Auer, P., Cesa-Bianchi, N., and Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem.

[R2] Lin, X., Wu, Z., Dai, et al. (2023). Use your instinct: Instruction optimization using neural bandits coupled with transformers.

---

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.

---

W1. The presentation could be substantially improved...

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.

---

W2. The evaluation setting ... are the evaluation budgets per prompt the same for all considered baselines? ... evaluation budgets per prompt ...

R2. We would like to clarify the notation of "evaluation budgets per prompt" here and in the revised paper to avoid misunderstanding.

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

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

---

W3. The considered prompt candidates ... only containing 150 at the maximum...

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.

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

---

W4. ... hard to see if the method is efficient in the empirical section, where only the performances under the specific budget setting are considered.

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.

---

W5. Recent baselines ... like ZOPO and, OPRO ...

R5. Thank you for providing these two baselines!

• [ZOPO] As the ZOPO paper 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 "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.

  Following the reviewer's helpful suggestion and NeurIPS 2024 Call For Papers "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.

• [ORPO] The ORPO paper, 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.

---

W6. ... It would be great to show ... on GLUE tasks and reasoning tasks (e.g., GSM8K, MATH).

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.

---

Q1. ... Will your method still work under the deterministic function $f(\cdot)$?

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

---

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.

---

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?

Response 1. We would like to answer your question in two aspects:

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

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

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

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

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

Overall, we believe this work has a sufficiently broad scope to benefit both task-specific and open-ended interactions with LLMs.

---

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.

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.

• One horizontal line at 1 is added to label the baseline of Uniform, over which the performance of other methods are normalized.
• A star is positioned on the best-performing method of each task.
• The size of the candidate prompt pool and the stringent budget are also highlighted in the top left corner.

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

---

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.

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.

---

Question 1. Do TRIPLE-SAR and CSAR take ordering into account?

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.

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

---