Teach Better or Show Smarter? On Instructions and Exemplars in Automatic Prompt Optimization

Authors: xingchen  wan
ruoxi  sun
hootan  nakhost
sercan ö arık
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 19:15:07

Abstract: Large language models have demonstrated remarkable capabilities but their performance is heavily reliant on effective prompt engineering. Automatic prompt optimization (APO) methods are designed to automate this and can be broadly categorized into those targeting instructions (instruction optimization, IO) vs. those targeting exemplars (exemplar optimization, EO). Despite their shared objective, these have evolved rather independently, with IO receiving more research attention recently. This paper seeks to bridge this gap by comprehensively comparing the performance of representative IO and EO techniques both isolation and combination on a diverse set of challenging tasks. Our findings reveal that intelligently reusing model-generated input-output pairs obtained from evaluating prompts on the validation set as exemplars, consistently improves performance on top of IO methods but is currently under-investigated. We also find that despite the recent focus on IO, how we select exemplars can outweigh how we optimize instructions, with EO strategies as simple as random search outperforming state-of-the-art IO methods with seed instructions without any optimization. Moreover, we observe a synergy between EO and IO, with optimal combinations surpassing the individual contributions. We conclude that studying exemplar optimization both as a standalone method and its optimal combination with instruction optimization remain a crucial aspect of APO and deserve greater consideration in future research, even in the era of highly capable instruction-following models.

Main paper: 
 claims: 
 Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes] Justification: The abstract and instroduction accurately reflect our contributions and scope. 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. 
preliminaries: 
 Prompts are natural language inputs to LLMs. Denoting an input task query as x, a few-shot prompt P (x) may be represented as P (x) = [I, e 1 , ..., e k , x] where I denotes an instruction and {e 1 , ..., e k } denote k exemplars (or interchangeably, demonstrations), each of which is a concatenation of other queries and their outputs (including both the final answer and any possible intermediate outputs) which resemble the current query x or may otherwise guide the LLM to better handle the current task, and we show a common prompt template organizing these components in Fig. 2 -note that not all components are required: e.g., zero-shot prompts feature no exemplars.Solve the following math problems by following the steps: 1. When multiplying or dividing two negative numbers, the result will be positive.2. When multiplying or dividing a positive and a negative number, the result will be negative.3. When adding or subtracting a negative number, it is the same as adding or subtracting its positive counterpart.( Automatic prompt optimization (APO) aims to automatically design P (x) via optimization. We broadly consider black-box API-only LLMs 2 . The proposed framework assumes a validation dataset D val := {(x i , y i )} n val i=1 , where x i and y i represent validation inputs and targets, a performance metric (e.g., accuracy) g(•, •), and aims to find the optimal prompt P * (x) to be used at test time, which is empirically the maximizer on D val : P * (x) = arg max P (•)∼P E (x,y)∼D val g fLLM P (x) , y ,where f LLM (•) denotes a textual LLM output given input and P denotes the search space, whose definition allows a broad categorization of APO methods into instruction optimization methods targeting instructions in Fig. 2 , exemplar optimization methods targeting exemplars in Fig. 2 and approaches that tackle both.Exemplar optimization (EO). Efforts to optimize exemplars started soon after the discovery of in-context learning (ICL) [6] via retrieval-based approaches to identify the closest labeled examples [28, 61, 51, 64] , influences and sensitivity [31, 8] , and learning-based approaches [58, 55] . Toolkits like DSPy [21] adopt EO as the main APO paradigm. Works [45, 46, 60, 22, 41, 59] have also extended EO to model-generated exemplars in LLMs and multimodal models. Lastly, by framing EO from an active learning angle, Margatina et al. [29] provide a comprehensive understanding and comparative analyses. These works, however, principally analyze different EO strategies only, nor do they analyze from the angle of APO. Many of these works also primarily focus on and draw findings from earlier and simpler tasks that are arguably less challenging to SoTA LLMs.Instruction optimization (IO). On black-box LLMs, the origin of IO may be traced to discrete prompt search [12, 40, 53, 62, 34] which prepend optimized tokens, which can be viewed as a form of "instructions", to inputs. However, these approaches do not necessarily yield interpretable prompts and most of them require output signals (such as logits) beyond strictly black-box access. Thus, recent advances have shifted towards utilizing an LLM itself to generate natural language instructions for iterative optimization on D val in Eq. 1. The seminal works is APE [66] , which employs the LLM to iteratively cull top-performing instructions on D val and paraphrase them until convergence. Similar evolutionary frameworks are widely used in follow-up works [16, 19, 63] and alternative formulations like Bayesian optimization (BO) [7] and neural bandits [25] were also used. Another line of works [35, 48, 56, 42] employ reflection, directing an LLM to articulate reasons for errors to iteratively improve instructions. Other approaches like OPRO and its variants [54, 27] , treat the LLM as a black-box optimizer, tasking it with generating new instructions based on the trajectory of previously evaluated instructions and their performances without explicit meta-instructions.Combining EO and IO. As discussed in §1, there is a relative dearth of work combining EO and IO despite their shared objective. Specifically, even when the labeled dataset D val is a prerequisite of virtually all IO methods, it is primarily used to estimate the expectation in Eq. 1 only rather than to construct exemplars in a principled way: For instance, ProTeGi [35] randomly samples exemplars from D val , while OPRO [54] uses them only for instruction induction [18] . Other works [16, 66, 48] either use no exemplars or fix exemplars and only optimize the instructions -for challenging reasoning tasks, these methods require human-annotated chain-of-thought (CoT) exemplars [50] in addition to D val , which arguably runs counter to the goal of automatically designing prompts without human intervention in APO. A few exceptions exist: PromptBreeder [14] employs "context shuffling" to co-evolve exemplars and instructions, while Mixture-of-Prompts (MoP) [47] aligns exemplars with multiple prompting "experts" for joint optimization. However, these works still focus their optimization effort on instructions: PromptBreeder emphasizes complex mutation operators for IO while providing only basic EO frameworks, whereas MoP chiefly focuses on IO with the bulk of its contribution being assigning optimized instructions to different exemplar groups, rather than optimizing the exemplars themselves. Other works [13, 57] also include both exemplars and instructions in the search space, but they require information beyond strictly black-box outputs to some extent. Lastly, several works have analyzed the interplay between ICL and instructions [30] or prompt templates [39] , but they mainly characterize the performance variation as an issue deserving attention. We, however, consider the APO setup specifically, and argue that such an interdependence presents an opportunity through holistically considering instructions and exemplars. Concurrent to our work, Agarwal et al. [2] and Opsahl-Ong et al. [32] also study the joint optimization of instructions and exemplars, and in many cases reached conclusions corroborating our findings, demonstrating the community's growing awareness on the importance of the subject of focal interest to this paper.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: We clearly discuss our limitations in the Conclusion. 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. 
understanding instruction optimization and exemplar optimization: 
 While studying IO and EO independently has academic value, the practical goal ultimately for both is to optimize the performance of LLMs. Hence, IO and EO, as two dominant genres of APO methods, present practitioners with the challenge of selecting or combining them to maximize cost-performance benefits. We aim to meet this by evaluating EO and IO in the context of APO by answering the following: 1) What is the relative importance and performance impact of EO and IO, both in isolation and when combined together? 2) How do we make the optimal use of the limited data and computational budget under the current APO framework?We perform thorough experiments employing various EO and IO methods individually and in combination. We use the PaLM 2 text-bison-002 [4] and Gemini 1.0 Pro/1.5 Flash [15, 36] as the target models, but we will also validate key findings on GPT-3.5. Modern IO methods often employ another, usually more potent optimizer model for to generate and/or critique instructions; we use PaLM 2 text-unicorn-001 (for text-bison target model), Gemini 1.0 Ultra (for Gemini 1.0 Pro target model) or Gemini 1.5 Pro (for Gemini 1.5 Flash target model). We evaluate on tasks selected from BIG-Bench Hard (BBH) [43] , a collection of diverse tasks considered to be challenging to LLMs -the suite itself and datasets of similar task types are frequently used in many recent APO works [48, 54, 19, 14, inter alia]: the tasks include numerical reasoning, commonsense problemsolving, logical deduction, linguistic manipulation, machine translation, and tabular reasoning, among others. For all tasks, we use 20% of data as validation set and the remaining 80% for testing, the latter of which is held-out and unavailable to the LLM at search time (see App. A for implementation details). We also test some of our key findings on the MMLU benchmark [17] , a set of 57 tasks frequently used to gauge the general problem-solving abilities of LLMs -we use the official val and test splits for validation and testing, respectively. We consider the following IO strategies:1. No IO: we use the seed instruction I 0 "Let's think step by step." [23] without any optimization. 2. APE [66] is the seminal work for LLM-as-an-instruction-optimizer and uses an evolutionary algorithm design: at each iteration, we evaluate a population of instructions on the validation set and the optimizer is asked to generate a new population by paraphrasing the top-performing instructions. This process iterates until convergence. 3. ProTeGi [35] collects samples that the target LLM answers incorrectly on D val under the current instruction and directs the optimizer LLM to reflect and critique it. The optimizer model is then asked to update the instruction by summarizing and abstracting the feedback. Additionally, at each iteration, ProTeGi also paraphrases instructions similar to APE (referred to as "Monte Carlo sampling") and uses beam search to identify the most promising instructions. 4. PromptAgent [48] is similar to ProTeGi but it features a more advanced planning agent using Monte Carlo tree search [10] . 5. OPRO [54] implicitly optimizes instructions. Starting from the seed instruction, at each iteration, OPRO provides the optimizer model a concatenation of previously evaluated instructions and their validation scores. Instead of explicitly requesting paraphrasing or reflection, OPRO treats the optimizer LLM as a black-box optimizer and simply asks the optimizer model to "come up with a better instruction" given these information.The above methods are selected as each of them represents the state of the art of a genre of approaches as outlined in §2 and collectively represents IO techniques as a whole. We initialize each method at the seed instruction and ensure they consume the same amount of compute measured by the number of prompt evaluations on D val m (we cap m = 32 except for "No IO" which requires no iteration). We also compare against PromptBreeder [14] in a later section, as it features a much more expansive search space and requires significantly more than 32 iterations before convergence. After obtaining the optimized instruction I * (or I 0 if no IO is performed), we perform EO. At this point, we emphasize that our setup should not be confused with the "few-shot" setup considered by some prior works [66, 16] which require additional human-annotated exemplars with reasoning traces to elicit CoT behavior. We perform EO only from the exemplars self-generated by the target model (also referred to as "bootstrapped few-shot" in DSPy [21] and "reinforced ICL" in concurrent works like Agarwal et al. [3] ) and do not assume exemplars are given at the start of APO (i.e., we do not assume the presence of initial {e 1 , ..., e k } in P (x)). We consider the following EO strategies:1. No EO: no exemplars are used; this is typically referred to as "zero-shot" in the APO literature. The above heuristic-based EO strategies do not use D val , whereas optimization-based EO can utilize it similarly to IO. Instead of generating instructions, we select the exemplar combinations with the highest validation accuracy for testing [33, 20, 21] . Unlike IO, which creates new instructions via an optimizer model, EO selects from pre-generated outputs and does not require an optimizer model. Formally, we focus on optimizing exemplars conditional on I * from IO (or I 0 if no IO is involved) 3 :EQUATIONWe include the following optimization-based EO methods that differ in search strategy:6. Random search: Following the EO procedure in DSPy [21] , we randomly sample m combinations of k exemplars: {E 1 , ..., E m } where each E = {e j } k j=1 ∀ ∈ {1, ..., m}. We evaluate each combination on the validation set and use the best for testing. 7. Mutation: We also implement a mutation-based baseline, initiating with a population of Q combinations for T = m/Q generations, where Q = 8. Each generation starts with a randomly For all EO methods except for "All exemplars", we use m = 32, k = 3 for all main experiments, but we also test with k = {1, 3, 5, 10, 20} in App. B.4. Given the IO and EO strategies, we experiment on each of the IO-EO combinations.On BBH, we aggregate the results in Table 1 for PaLM 2 models. We also experiment on Gemini models with no IO and with ProTeGi (best overall IO technique from the PaLM 2 results) in Table 2 (Gemini 1.0) and Table 4 (Gemini 1.5). We also validate key findings in representative datasets on GPT-3.5 (Table 13 , App B). On MMLU, we present results in Table 3 (PaLM 2) and App. B.1 (Gemini) . Below, we highlight and discuss the key insights.Insight 1: We should almost always perform EO whenever we perform APO.One of the immediate findings from the tables is that comparing the first column against others, any EO consistently improves test performance, with any or no instruction optimization. In Fig. 3 , we further show that the EO not only benefits at an aggregated level but also leads to significant and almost unanimous improvements across diverse tasks.While exemplars improving performance may not seem surprising, it is worth noting that as mentioned, in this case they are side-products of evaluating instructions on D val with no additional data costs. Thus, we argue that for practical purposes under the framework of Eq. 1, barring unusual constraints like extreme restrictions in context length, which This might restrict applicability of IO methods too as many SoTA IO methods also generate long prompts, and/or extreme long-context tasks where it is not possible to fit exemplars in the context window, there is little incentive to consider the "zero-shot" setup without exemplars and little incentive not to perform EO, given that current APO setup requires D val anyway, regardless of whether we use them as exemplars. Thus, it is by definition, not "zero-shot" and is not directly comparable to true zero-shot methods requiring no labeled data. Furthermore, there is also the risk that "zero-shot" results neither reflect nor accurately predict the full potential of the LLM, as what performs well under zero-shot does not necessarily performs well when a better EO strategy (e.g., PromptAgent in Table 1 and ProTeGi in Table 3 ) is used. Lastly, since obtaining labeled data can be costly, intelligently reusing them as exemplars also represents a more judicious use of scarce resources compared to only using them to evaluate a metric for optimization.Insight 2: How we select exemplars may outweigh how we optimize instructions, and selecting exemplars via iterative optimization consistently outperforms alternative strategies.Exemplar optimization outweighs instruction optimization. Despite the recent focus the community places on IO, we find that how we select exemplars outweighs how we optimize instructions in the model-task combinations we investigate. With reference to Tables 1 2 3 4 (and task-specific breakdown in Fig. 5 ), we find that if we optimize instructions or exemplars (i.e., the blue cells) under a roughly compute-matched budget, prompts without instruction optimization but with optimized exemplars (e.g., the "No IO + Mutation" combination) outperform prompts with SoTA instruction optimization but without optimized exemplars (e.g., the "ProTeGi + Random" combinations) in an overwhelming majority of cases. In fact, on a separate set of experiments performed on the PaLM 2 models, we find this to be true even after halving the evaluation budget of EO (see App. B.6), and optimization on exemplars as naïve as random search can outperform IO methods that are significantly more complicated and expensive. Further substantiating this argument are that:1) In isolation, EO boosts performance more effectively than IO: for example, with reference to Table 2 , compared to the seed prompt, using the best EO strategy (Mutation, first row) alone increases the average performance by >11%, compared to approximately 8% using the best IO strategy (ProTeGi, first column); 2) When combined, benefits of EO and IO stack up but are largely attributable to EO: under "Mutation" (last column), the best EO strategy, the performance gap between the best and worst IO strategies shrinks to less than 4%, suggesting that instructions might be less critical if the LLM is provided with good exemplars after all.We observe similar conclusions for different models and task combinations. In fact, on MMLU (Table 3 ) featuring much smaller validation splits, we observe that judicious exemplar optimization completely eliminates the performance gap caused by IO under zero-shot, with No IO even surpassing SoTA IO. Interestingly, as we show in Fig. 4 where we further consider the difference between validation accuracy, which is the empirical objective function in Eq. 1, and the test accuracy, which is the reported metric that represents the generalization power of the optimized prompt, optimized exemplars generalize better than optimized instructions under all model-task combinations considered. On MMLU tasks (two rightmost plots in Fig. 4 ), IO even improves validation performance comparable to or better than EO, but the validation improvement does not generalize to the test set. These imply that the superior test performance of EO cannot be solely attributed to a more effective search space P or optimization strategy in Eq. 1, and the performance gap might not be completely closed by advancing optimization only. exemplars outperforms random exemplars, which is the default design in Pryzant et al. [35] , by more than 6% in both Table 1 and 2 and more than 2% in Table 4 . Interestingly, as shown by the "All" column in Table 4 for Gemini 1.5 and App. B.4 for Gemini 1.0, naïvely scaling the number of exemplars may not be the most effective -the fact using the entire D c underperforms 3 optimized exemplars, which are a subset of D c , highlights the relevance of EO even for modern LLMs capable of handling long context windows. On the other hand, heuristic-based selection like Diversity and Nearest do not consistently outperform simple random baseline, echoing previous findings [33] .Imitation of task-dependent winning patterns outweighs elaborate descriptions. We further present representative prompts in Fig 6 and how LLM responds to them in App. B.9: Generally, we find that even detailed and task-specific instructions do not regulate the LLM's behavior as effectively as exemplars, which enable imitation. For example, for challenging tasks like tracking_shuffled_objects and web_of_lies, optimization-based EO discover "winning" templates that, when followed, improve performance massively. Even when SoTA IO methods may often state the answer steps equivalently in words, we find LLMs to simply respond better to exemplars from which they can copy behaviors. On the other hand, for tasks where CoT-style answering are known to be unhelpful (e.g., snarks) [43] , the optimized exemplars are invariably those giving direct answers; when prepended to the test queries, LLMs tend to prioritize exemplar imitation over instruction following to answer directly despite triggers like "We should move forward in stages". These highly task-dependent "winning" patterns that vary from elaborate step-to-step reasoning to direct answering may also explain why heuristic-based EO fares worse to data-driven approaches, since there might not be a single heuristic universally useful for all tasks.Concluding remarks. We argue that the findings are highly significant for the future of APO. equally crucial and should not be relegated to an afterthought. Second, we note that the EO strategies studied are in no way exhaustive. In fact, in contrast to the sophisticated search and instruction generation approaches adopted by IO methods, they can even be considered elementary. Yet, they deliver comparable or more significant improvements. Thus, we anticipate advanced methods that more effectively optimize exemplars would yield even greater enhancements: some techniques in IO may be adapted to EO with little-to-no modifications. For example, many recent advances in IO adopt an evolutionary search framework -while our "Mutation" baseline can be seen as an elementary version of it in EO, it should be also straightforward to use more advanced search strategies and operators or use techniques like LLM-generated paraphrasing on top of selected exemplars. Other search techniques, such as sample-efficient combinatorial BO [5, 44, 11, 65] , can be uniquely suitable for the EO setup, which is itself a combinatorial optimization problem 4 . Furthermore, while we used a fixed set of exemplars (i.e., task-wise selection), it might also be fruitful to further explore in the direction of instance-wise selection [51, 37] . Lastly, as discussed, the presence of (often large) generalization gap also suggests the importance to consider generalization alongside optimization, which seems to be the chief focus thus far; it might be promising to investigate analogies of well-tested in classical machine learning like regularization and cross-validation in APO.Insight 3: Optimizing both instructions and exemplars is greater than the sum of its parts, even under a comparable computational budget.For most of the results obtained, we note that iteratively optimizing both instructions and exemplars led to the best performance. This naturally leads us to answer the second research question: whereas experiments in Tables 1 and 2 expend additional cost by optimizing exemplars on top of the optimized instructions, we show that 1) such a combinable benefit does not simply root from the additional compute and 2) optimally mixing-and-matching IO and EO leads to significant performance improvement with negligible additional overhead.Concretely, we budget a total m = 32 prompt evaluations on D val where we use first m IO ={0,8,16,24,32} iterations optimizing instructions and the remaining m EO optimizing exemplars. We summarize the results in Fig. 7 , where we find that 1) any mix-and-match outperforms IO or EO only (i.e., m IO =0 or 32), and 2) the best allocation bridges the gap or almost bridges the gap compared to the combination that uses twice as many prompt evaluations (last column) -interestingly, in this case the optimal allocation also roughly reflects the relative contribution of IO and EO to the overall performance improvement in Table 1 . We show in App. B.7 that the above findings hold for other target models and instruction optimizers, and we also give detailed examples and explanations of the mechanism leading to this synergy. Additionally, in App. B.10, we compare this simple routine against PromptBreeder [14] , which is one of the few existing IO methods that supports EO via an optional "context shuffling" routine. It, however, mutates the exemplars purely stochastically rather than optimizing from the validation metric. We show that despite the simplicity, our algorithm converges to comparable or better solutions while incurring a fraction of the PromptBreeder cost, which often requires hundreds of evaluations before convergence. Finally, we note that the presented way to combine optimization-based IO and EO is a proof of concept and room for future improvement can be vast and we experiment several other alternative ways to combine them in App. B.8, but we defer thorough investigations to a future work.Insight 4: SoTA IO methods may be inadvertently relying on exemplars already.Beyond inspecting performance metrics only, we also examine the actual instructions and exemplars discovered. While detailed prompts are available in App. C, we highlight a key observation that adds a new dimension to our discussion: SoTA IO strategies may inadvertently utilize exemplars already. Despite IO methods not typically explicitly focusing on exemplars, we find them to frequently generate texts resembling exemplars within instructions through feedback and reflection processes. For instance, PromptBreeder employs "Lamarckian mutation" to reconstruct instructions from inputoutput pairs, while ProTeGi prompts the optimizer model to analyze target model errors. These operators, though varied, all involve taking actual validation exemplars as inputs to optimizer models. As exemplified by Fig. 8 , while the original intention may have been to abstract task-level instructions, the model occasionally incorporates these exemplars verbatim in the instructions. Whereas these "quasi-exemplars" may seem unintentional, we observe that they are surprisingly common in highperforming instructions and often contribute more to the performance than the actual instructions themselves.Let's address this systematically. To determine the correct order of adjectives in a sentence, we need to follow a speci c order. The general order of adjectives is as follows:1. Opinion adjectives 2. Size adjectives ...Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [NA]Justification: The paper does not include theoretical results. Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced.• All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
conclusion: 
 We present comprehensive evaluations on the SoTA IO and EO methods, both individually and combined. We demonstrate that EO can be a potentially more crucial element in APO, revealing a beneficial synergy through joint optimization with IO. We also find that the high performance of SoTA IO methods can themselves be driven by implicit yet spontaneous exemplar discovery. Overall, we advocate for further research into EO, both as an independent approach and in conjunction with IO, even for highly-capable instruction-following modern models. One limitation is that although the tasks we consider are fairly diverse and findings on it are already of value given the widespread interest just on these tasks only, they are not exhaustive, omitting tasks like open-ended longer-form generation and metrics like safety & harmfulness which are important for responsible use of LLMs. As is the case for any inductive study deriving insights from experiments, there is also a possibility that the findings may not fully generalize to other tasks and/or models. Expanding to include these aspects would be important for future work.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [Yes] Justification: We fully disclose the datasets (all datasets are publicly accessible) and the models used (all models have public API). We include all discussions about the implementation details in Appendix. A. Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
open access to data and code: 
 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: [No] Justification: While we aim to open-source our experimental code in the future, we cannot open source the codebase at the time of submission. However, many of our experiments derive from existing methods, which can be reproduced by running the respective, opensourced codebase which we outline in Appendix A. 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: We fully disclose the datasets (all datasets are publicly accessible) and the models used (all models have public API). We include all discussions about the implementation details in Appendix. A. 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. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [No] Justification: While we do not repeat each experiments more than once due to the computational constraints, we perform experiments on a large set of tasks, and insights are largely drawn from the aggregated results averaged over 70+ different tasks to improve the reliability of our results. 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). 
purpose adjectives: 
 In case of any confusion, you can utilize the ROYAL mnemonic as a memory aid: R -Relative size (big, small); O -Opinion (beautiful, ugly); Y -Age (young, old); A -Shape (square, round); L -Color (red, blue) By applying this rule, we can ascertain the correct order of adjectives in a sentence.Text: "Which sentence has the correct adjective order: Options: (A) small archaic square leather sock (B) archaic small leather square sock" Label: a Prediction: b The correct answer is (A). The adjectives in this sentence are "small," "archaic," "square," and "leather." Referring to the ROYAL mnemonic, the correct order of adjectives is"size, opinion, shape, material." Therefore, the appropriate order in this sentence is "small, archaic, square, leather."..Full prompt: 84.5% Quasi-exemplars only: 80.5% (-4.5%) Removing quasi-exemplars: 71.0% (-13.5%)The best instructions might actually be exemplars: Best instruction discovered by ProTeGi on hyperbaton where spontaneously discovered "quasi-exemplars" are highlighted. We also edit the instructions to either remove or retain the higlighted parts and find these quasi-exemplars, rather than the rest of the instruction, drive the performance. See App. B.11 for more examples.We argue that the findings here provide further evidence corroborating our insights obtained so far and our suggestions advocating explicit EO. Indeed, in contrast to explicit optimization of the exemplars, the aforementioned mechanism of exemplar discovery via IO is entirely opportunistic and, depending on interpretation, an unintentional artifact. For example, the quasi-exemplars in Fig. 8 almost certainly originate from the optimizer model in ProTeGi taking a convenient shortcut by incorporating a critique into the instruction verbatim (note the presence of traces like "Label: a Prediction: b" which suggests a previous mistake by the target model), which should not happen if the optimizer model perfectly executes the intended task of abstracting these critiques. Thus, we argue that instead of relying on the opportunistic exemplar generation via IO, explicitly optimizing for exemplars can be more preferable, as shown throughout this study. 
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: This paper does not release new generative models or scraped datasets but rather derive from existing models and datasets. Therefore, we do not anticipate 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 list the license and terms of use in Appendix A. Original creators/owners of all assets used in the paper are properly credited with citations. 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. • 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.In the template above, QUERY_TEXT denotes the input text; INSTRUCTION denotes the instruction to be added, which is the principal optimizable component of IO methods; llm() denotes the location where LLM is prompted to generate an output. ANSWER_INSTRUCTION is a special, taskspecific sentence to ensure the LLM generates the final answer in a format that can be easily parsed.Specifically, for all multiple-choice questions-style tasks, it has the following content:Show your final answer option bracketed between < answer > and <\ answer >.For all other tasks, the content is:Show your final answer {{ T A S K _ S P E C I F I C _ C O N S T R A I N T }} bracketed between < answer > and <\ answer >.where the content of TASK_SPECIFIC_CONSTRAINT depends on the task:• boolean_expressions: (True or False only)• formal_fallacies: (valid or invalid only)• navigate, sports_understanding, causal_judgement, web_of_lies: (yes or no only)• word_sorting: (sorted words separated by spaces only)• all other tasks: None (empty string).At test time, the final answer is extracted with the capturing pattern <answer>...<\answer>. When exemplars are added, we use the following template:Q : {{ D E M O _ 1 _ Q U E R Y _ T E X T }} {{ AN S W E R _ I N S T R U C T I O N }} A : {{ INSTRUCTION }} {{ DEMO_1_OUTPUT }} == Q : {{ D E M O _ 2 _ Q U E R Y _ T E X T }} {{ AN S W E R _ I N S T R U C T I O N }} A : {{ INSTRUCTION }} {{ DEMO_2_OUTPUT }} == ... Q : {{ QUERY_TEXT }} {{ AN S W E R _ I N S T R U C T I O N }} A : {{ INSTRUCTION }} {{ llm () }}where DEMO_{i}_OUTPUT contains the entire response from the LLM to the corresponding input (not the final answer only). For ProTeGi and PromptAgent, we follow the templates used in the respective original papers with the format that puts the instruction and answer instruction in front of the test query:{{ INSTRUCTION }} {{ A N S W E R _ I N S T R U C T I O N }} {{ QUERY_TEXT }} {{ llm () }}Accordingly, we modify the template with exemplars to:{{ INSTRUCTION }} {{ D E M O _ 1 _ Q U E R Y _ T E X T }} {{ A N S W E R _ I N S T R U C T I O N }} {{ DEMO_1_OUTPUT }} == {{ D E M O _ 2 _ Q U E R Y _ T E X T }} {{ A N S W E R _ I N S T R U C T I O N }} {{ DEMO_2_OUTPUT }} == ... {{ QUERY_TEXT }} {{ A N S W E R _ I N S T R U C T I O N }} {{ llm () }}Noting that instruction is stated once at the beginning only rather than repeated at each exemplar, in consistency to the original styles adopted by these papers.Implementation details of IO methods. In this section, we describe the implementation details of the IO and EO methods adopted. For all methods, we use greedy decoding (temperature = 0) for the PaLM 2 (text-bison-002) or Gemini target models. Whenever an optimizer model is used, we use temperature = 1.0, top_k = 40 and top_p = 0.8. For both PaLM 2 and Gemini models, we use the Google Cloud Vertex AI API available at https://cloud.google.com/vertex-ai.• APE: We adapt the official implementation available at https://github.com/keirp/ automatic_prompt_engineer. Instead of using "instruction induction" [18] from exemplars which is the primary initialization method introduced in the original paper in §3.1, Forward Mode Generation or Reverse Mode Generation, we opt for the third option, Customized Prompts where we initialize APE at the seed prompt "Let's think step by step" because 1) this ensures fairness in comparison with other methods and 2) we find initializing at the seed prompt actually leads to much better performance because it is well-known to induce step-by-step, CoT-style reasoning from the LLM. On the other hand, while the LLM induced initial instructions may describe the task better, the model often tends to utter the final answer without intermediate steps which we observe lead to much worse performance: on the BBH tasks selected for experimentation in this work, instruction induction using the meta-prompt provided by the APE paper only led to an average test accuracy of 56.7% on PaLM 2 (text-bison-002), which is even worse than using the seed prompt with no additional optimization. For APE, we use a population size of 8 and allow for 4 generations. • OPRO: we adapt the official implementation available at https://github.com/ google-deepmind/opro. At each optimization step, we follow the authors by asking the optimizer model to generate 8 candidate prompts and we budget for 4 steps. • ProTeGi: We use the official implementation available at https://github.com/microsoft/ LMOps. We set the initial prompt to the seed prompt, and we always use the entire validation set to generate the "gradients" (i.e., we use no mini-batching). We set the number of newly proposed instructions per optimization step to 8, where half of them come from "gradients" (i.e., new instructions generated by using the optimizer model to critique past mistakes made by the target model) and the other half come from "Monte Carlo samples" which are paraphrased/rewritten variants of the past prompts by the optimizer model. We again allow for 4 generations of mutations. • PromptAgent: We use the official implementation at https://github.com/XinyuanWangCS/ PromptAgent. We set the initial prompt to the seed prompt and use the default Monte Carlo Tree Search algorithm and set the number of maximum iterations to 32 to be consistent with the other methods described above.Computational Resources. All experiments conducted in this work are accessible via public APIs where the underlying LLMs are hosted from the server side. There is no computational resource requirement on the client machine except that one can access Google Colab and run Python 3.10.Datasets. As discussed briefly in §3.  
: 
 Significant advancements in large language models (LLMs) have revolutionized various natural language processing tasks [9, 4, 1, 15] . One notable aspect of LLMs, however, is their sensitivity to the input "prompts," which has given rise to the burgeoning field of prompt engineering [26, 38] . On black-box LLMs where we can neither modify or access internal parameters, prompt engineering involves crafting input prompts that effectively guide LLMs to generate desired outputs. Starting from manual processes requiring human expertise, the complexity and volume of prompts have necessitated the development of automatic prompt optimization (APO) methods aiming to streamline and automate prompt generation, thereby alleviating the burden of manual intervention. Broadly, since prompts consist of instructions and exemplars, we may roughly categorize APO into instruction optimization (IO) and exemplar optimization (EO) approaches. IO focuses on refining the textual instructions provided to LLMs that contain task-specific information (i.e., to teach), whereas EO emphasizes the selection of relevant examples to guide model behavior (i.e., to show). Partially driven by the improved instruction-following ability of LLMs, the research attention has increasingly shifted towards IO, especially using LLMs themselves as optimizers [66, 35, 48] .While EO and IO approaches address the similar overarching problem, they have evolved somewhat independently, with a few exceptions [14, 47] . Indeed, as we elaborate in §2, EO approaches are often based on simple, handcrafted templates without explicit instruction optimization [21, 45] , while IO methods seldom optimize exemplars and often rely on random validation set samples [35] , require additional fixed exemplars on top of the validation set [66, 16] , or consider the "zero-shot" setup with no exemplars at all [48] . Whereas the lack of IO in EO methods is somewhat understandable as many EO approaches predate instruction finetuning [49] and, subsequently, instruction-following models that are sensitive to instructions, the inverse is much less so: concretely, almost all existing IO approaches already require a labeled dataset as the validation set, and are therefore, by definition, not "zero-shot". With the inputs, labels, and, if applicable, model-generated intermediate outputs (e.g., reasoning steps) on the subset of the validation set that the model has answered correctly, we already have a set of exemplars as a free side-product whenever we perform IO, independent from and on top to any additionally provided, human-annotated exemplars. A common argument for not focusing on EO, such as mentioned in Pryzant et al. [35] , is the goal to focus on one objective at a time 1 . However, given the common practical goal of and the interplay between EO and IO [30] , we argue they should not be treated separately -it is instead critical to understand their relative importance and combined impact, and, where necessary, optimize them jointly for the best performance-cost balance. This is, to our knowledge, where there is a gap in the literature that we aim to bridge. To do so, on a diverse suite of challenging BIG-Bench and MMLU tasks, we compare the performance gain brought by various representative, state-of-the-art (SoTA) IO and EO methods on the fairground with PaLM 2, Gemini (1.0/1.5) and GPT models to foster better scientific understanding of different APO techniques. While IO comfortably improves the baseline prompts before any instruction or exemplar optimization, this, at best, portrays an incomplete picture. Under the same setup, with simple yet effective EO methods on the model-generated exemplars on the validation set, we show:• Intelligently incorporating exemplars generated by the target model itself on the validation set significantly and consistently improves performance on top of recently proposed IO methods; • The performance gains realized by choosing appropriate exemplars via methods as simple as random search can eclipse the improvements brought by SoTA instruction optimization. As a concrete example, as shown in Fig. 1 , with a simple optimization routine on exemplars, seed instructions before any optimization outperform optimized instructions obtained with complex IO but with random exemplars most commonly used. • There exists a synergy between EO and IO, and optimally mixing-and-matching IO and EO is greater than the sum of its parts under a comparable computational budget. • SoTA IO might be itself implicitly generating exemplars, and these exemplars, while somewhat unintentional, contribute more to the performance than the rest of the instruction that IO methods are meant to optimize. • While arguably receiving less research attention recently, exemplar optimization remains a crucial design consideration in APO. Even in an era of highly capable instruction-following LLMs, the significance of exemplar optimization should not be relegated to an afterthought, and better exemplar optimization both as a standalone tool and as a combinable component with IO is crucial for APO. 
 
 Appendix: In Tables 5 to 10, we show the per-task performance breakdown using the PaLM 2 (text-bison-002) target model whose aggregated results are presented in Table 1 . In Table 11 and Table 12 , we show the results using the Gemini 1.0 Pro and Gemini 1.5 Flash target models whose aggregated results are presented in Table 2 and Table 4 , respectively. The aggregated and task-specific breakdown results on the GPT-3.5 (gpt-3.5-turbo-0125) model are shown in Tables 13 and 14 , respectively. In Table 15 , we show the per-task performance breakdown using the PaLM 2 (text-bison-002) target model whose aggregated results are presented in Table 3 . In Table 16 , we show the MMLU results using the Gemini 1.0 Pro target model. Complementary to Fig. 3 in the main text, in PaLM 2 model, we show the per-task change of test accuracy before and after applying EO for APE and OPRO in Fig. 9 (comparison between optimized exemplars vs. no exemplars) and Fig. 10 (comparison between optimized exemplars vs random exemplars). We also include a visualization on the effect of IO (comparing optimized instructions and initial instructions) in Fig. 11 . We also visualize the Gemini 1.0 Pro results in Fig. 12 . Complementary to Fig. 5 in the main text, we visualize the additional BBH tasks on PaLM 2 in Fig. 13 (a), Gemini 1.0 Pro in Fig. 13 (b) and Gemini 1.5 Flash in Fig. 13 . We also test key findings on a representative subset of 11 tasks in GPT-3.5 (Fig. 14 . We visualize the MMLU results in Fig. 15 . 25With the advent of LLMs that support longer context windows, an alternative approach to performing exemplar optimization is to scale the number of exemplars. Taking into the context of our setup, instead of selecting k exemplars from D c where k is a small value, we can scale k to a larger value or even use the entire D c as exemplars. In this section, we perform experiments on the relative merits of the two approaches.We show the aggregated results in Table 17 and task-specific results for both models in Fig. 16 and Fig. 17 . While we find increasing the number of exemplars generally leads to improved test performance up to k = 10, further increase leads to performance deterioration. The increase in performance, however, does not diminish the importance of exemplar optimization as we show that using optimized exemplars outperform many more random exemplars, both at an aggregated level and on a task-specific level (the instances where optimized exemplars outperform random exemplars of any k, which are marked by magenta lines in Figs. 16 & 17 , are more than 50% in both target models) -we argue that this suggests that exemplar optimization remains relevant even in modern LLMs with long contexts. In fact, we believe that novel exemplar search strategy in such many-shot setup can be an important next step, given that the number of possible combinations and permutations of exemplars explodes exponentially for a higher k, necessitating more advanced search strategies that would navigate this optimization landscape more effectively and efficiently. We defer a thorough investigation of this direction to a future work. In the main experiments, we used 20%-80% validation-test split for all BBH tasks. In this section, we investigate the sensitivity of the various methods to changing validation data sizes, especially under very data-constrained setups such as very small validation data sizes. To do so, we vary the validation split to be {2, 4, 10, 20}% and we investigate on the combination of ProTeGi and Mutation, the bestperforming IO and EO methods, respectively. We summarize the average test accuracy against the size of validation data split (as a fraction of the total data available) in Fig. 18 .We find that optimization-based EO is remarkably robust towards the size of the validation size, with the smallest performance drop even with an extremely small validation set (i.e., 2% or 4%, which correspond to 5 or 10 validation samples). On the other hand, ProTeGi dropped to a performance no better than un-optimized seed instruction under such an extremely data-constrained setup, and even the performance of ProTeGi + Mutation, which performs the best overall in the main text dropped significantly with a small validation data size.In this section, we show the results of EO with search budget approximately halved (from m = 32 to m = 16) in Table 18 on top of the seed instructions without instruction optimization. We find that even after halving the budget (i.e., the EO strategies are now half as expensive), seed instruction and optimized exemplars still outperform optimized instruction and random exemplars both in terms of average test accuracy and average rank. Other choices of instruction optimizers and/or target models. We show results from mixingand-matching IO and EO in a similar manner to Fig. 7 but use ProTeGi (instead of APE in Fig. 7 ) on both PaLM 2 (text-bison-002) and Gemini 1.0 Pro target models in Table 19 , where we see that two key findings (that any mix-and-match outperforms IO and EO only and that optimal allocation completely bridges the gap compared to a more expensive routine) we made still hold, except on Gemini model, the optimal allocation occurs at 16/16 instead of 8/24. This confirms that the phenomenon we see in Fig. 7 in the main text is not specific to the choice of the target models and/or instruction optimizers but is instead generally applicable. Mechanism of synergy between IO and EO. In this section, we give an example of why combined IO and EO outperform its constituting building blocks in Fig. 19 : performing IO only (Fig. 19a ) generates step-by-step text instructions, but without exemplars, the model is prone to making arithmetic errors. Performing EO only (Fig. 19b ), on the other hand, subjects the model to the shortcomings of the un-optimized seed prompt, which, in this case, generates arithmetic operations-only outputs without textual reasoning. Combined IO and EO (Fig. 19c ) addresses both issues, leading to vastly improved performance from both textual reasoning and exemplars.As discussed in §3.2, we conducted EO after IO in the main text: in our setup, the exemplars are bootstrapped from the model's own predictions, which in turn depend on the instructions given. As such, we performed instruction optimization first on the zero-shot setup and search for the optimal exemplar(s) amongst the predictions induced by the optimal instruction. While we believe this order is the most natural, it is also important to ensure that any findings derived in this paper are not biased by the particular order we chose. Thus, in this section, we also experiment with two alternatives:1. Inverted order. We first optimize the exemplars based on the seed instruction ("Let's think step by step." for most cases), and then freeze the exemplars and optimize the instruction on both Gemini 1.0 Pro and Gemini 1.5 Flash models. We used APE to optimize the instructions and random search to optimize exemplars wiht a total budget of m = 32, which is identical to the setup presented in Fig. 7 in the main text. 2. Interleaved. Instead of framing the exemplar and instruction optimization as a two-staged approach, a better approach in principle is to optimize them jointly. Here, we propose an interleaved approach with the intention of conditioning instructions to the best exemplars discovered so far and vice versa given their inter-dependence. The pseudocode representation of the algorithm in shown in Algorithm 1.Algorithm 1 Interleaved instructions and exemplars optimization. Exemplar optimization steps marked in blue. We present the comparison between the original and inverted orders in Table 20 , where we found that the findings (in particular, Insights 2 and 3) are not affected by the optimization order. For the interleaved approach, we find it to achieve a test accuracy of 74.6% on 26 BBH tasks on PaLM 2, which is broadly on par with the two-staged approach with m IO = 16, m EO = 16 -we thus primarily focused on the two-staged approach for its simplicity, and defer a detailed exploration on better ways to exploit the interdependence of exemplars and instructions to future work.Table 20 : Effect of ordering between IO and EO on selected BBH tasks of (left) Gemini 1.0 Pro and (right) Gemini 1.5 Flash. Original refers to the IO before EO order used in the main text and Inverted refers to the IO-after-EO optimization order. In this section, we compare the two-stage EO-IO combined search mentioned in §3.2 against PromptBreeder [14] , the SoTA method that has the option of optimizing both instructions and exemplars. In contrast to our method which is a simple combination of APE (for instruction optimization) and mutation (for exemplar optimization), PromptBreeder features a much expansive search space introduced by its different mutation operators on the instruction and the meta-prompts (referred to as hyper-mutation in Fernando et al. [14] ). As such, the algorithm requires many more iterations before convergence -for our experiment, we use a population size of 40 and allow for 10 generations. Since PromptBreeder uses binary tournament evolution for each generation which will result in half of its population being replaced with new prompts requiring evaluations D val , there are total 40 + 10 × (40/2) = 240 traversals on the validation set D val , which is approximately an order-of-magnitude larger than the budget used in this paper and the discovered prompts can be deemed as an approximation of the performance "upper bound" when a SoTA optimizing agent is left to freely explore an expansive search space with ample search budget. As a comparison, we run our two-staged EO and IO algorithm for 100 iterations, with first 25 iterations used for IO and the remaining 75 for EO. Due to the much larger computational costs, we run the comparison on four selected tasks: movie_recommendation, multistep_arithmetic_two, object_counting and ruin_names. We summarize the results in Table 23 and Fig. 20 . It is worth noting that our simple two-stage search performs on par or better than PromptBreeder in 3/4 tasks in terms of both validation and test metrics while using less than half of the budget and using a much simpler instruction optimization heuristic.Given that the chief difference between our algorithm and PromptBreeder is the explicit iterative optimization for exemplars (noting that the "context shuffling" routine used in PromptBreeder, which permutes the exemplars in the prompt, relies purely on stochasticity), this again suggests that the importance of exemplar optimization may actually outweigh complicated instruction optimization as we highlighted in Insight 2 in §3.2 -in fact, even the the PromptBreeder authors themselves remarked in App. J that "... We find that in the few-shot evolution case, the contexts dominate, and often the task-prompts drift into nonsense. They are less critically determining of fitness than the evolved contexts.".Complementary to Insight 4 in §3.2 of the main text, in this section, we show additional examples illustrating how SoTA IO techniques may spontaneously and opportunistically use quasi-exemplars.For selected examples, we also perform ablation experiments similar to the experiment in Fig. 8 where we either retain or remove the identified quasi-exemplars to study the effect of their presence on the final performance and we show the results in Table 24 -it is further worth noting that in multiple cases, the instruction optimizers discovered instructions that consist of quasi-exemplars only (e.g., multi_arithmetic_two and movie_recommendation in Table 24 ), which further corroborates our point made in Insight 4. 1. First, we need to understand the problem. We have a collection of possessions that a person has along with their quantities. We need to determine the number of a certain object/item class.2. Next, we need to identify the object/item class for which we want to determine the number.3. Once we have identified the object/item class, we need to find all the possessions that belong to that class. 4. We then need to sum up the quantities of all the possessions that belong to the object/item class. 5. The sum of the quantities will give us the total number of possessions that belong to the object/item class. Let's take an example to understand this better. Suppose we have the following collection of possessions: "' { "car": 1, "house": 1, "bicycle": 2, "dog": 1, "cat": 2 } "' We want to determine the number of pets that the person has. In this case, the object/item class is "pets". The possessions that belong to this class are "dog" and "cat". The quantities of these possessions are 1 and 2, respectively. The sum of these quantities is 3. Therefore, the person has 3 pets. We can use the same approach to determine the number of any other object/item class in the collection. Step 2: Identify the cheapest fruit . The plums are the cheapest .Step 3: Determine the order of the fruits from most expensive to least expensive . The most expensive fruit is either the cantaloupes or the kiwis . The watermelons are the second -most expensive . The apples are less expensive than the cantaloupes . The loquats are less expensive than the kiwis . The apples are more expensive than the loquats . The loquats are the third -cheapest .Step 4: Identify the cheapest fruit . The plums are the cheapest .< answer >A </ answer > == Q : The following paragraphs each describe a set of seven objects arranged in a fixed order . The statements are logically consistent within each paragraph . On a shelf , there are seven books : a purple book , a brown book , a red book , a blue book , a gray book , a black book , and a green book . The brown book is to the left of the green book . The gray book is the second from the left . The black book is to the left of the gray book . The blue book is to the left of the red book . The blue book is the second from the right . The green book is to the left of the purple book . Options :While the genres of the movies vary , they are all considered to be classic films that have stood the test of time .Out of the options provided , the movie that is most similar to the given movies in terms of its popularity and well -knownness is Goodfellas .< answer >( C ) Goodfellas </ answer > == Find a movie similar to Batman , The Usual Suspects , The Silence of the Lambs , Jurassic Park : Options : ( A ) The End of the Tour ( B ) Forrest Gump ( C ) Lust ( D ) Caution ( E ) Shelter Show your final answer option bracketed between < answer > and </ answer > at the end .The common theme among the given movies is that they are all critically acclaimed and popular films from the 1990 s .Out of the options , the movie that is most similar to the given movies in terms of its popularity and well -knownness is Forrest Gump .< answer >( B ) Forrest Gump </ answer > == Listing 11: movie_recommendation: PromptAgent + Mutation. Test accuracy = 95.0%Solve the following math problems by following the steps in the order of operations :1. When multiplying or dividing two negative numbers , the result will be positive . 2. When multiplying or dividing a positive and a negative number , the result will be negative . 3. When adding or subtracting a negative number , it is the same as adding or subtracting its positive counterpart . ((6 -0 * 5 + -3) * (6 --7 + -2 --7) ) = Show your final answer bracketed between < answer > and </ answer >.((6 -0 * 5 + -3) * (6 --7 + -2 --7) ) = (6 -0 + -3) * (6 --7 + -2 --7) (6 + -3) * (6 --7 + -2 --7) 3 * (6 --7 + -2 --7) 3 * (6 + 7 + -2 + 7) 3 * (13 + -2 + 7) 3 * (11 + 7) 3 * 18 < answer >54 </ answer > == 1. When multiplying or dividing two negative numbers , the result will be positive . 2. When multiplying or dividing a positive and a negative number , the result will be negative . 3. When adding or subtracting a negative number , it is the same as adding or subtracting its positive counterpart . ((8 * 9 * 0 --1) -( -9 --7 + -4 -8) ) = Show your final answer bracketed between < answer > and </ answer >.((8 * 9 * 0 --1) -( -9 --7 + -4 -8) ) = 1. 8 * 9 * 0 --1 = 0 + 1 = 1 2. -9 --7 + -4 -8 = -9 + 7 -4 -8 = -14 3. 1 -( -14) = 1 + 14 = 15 < answer >15 </ answer > == 1. When multiplying or dividing two negative numbers , the result will be positive . 2. When multiplying or dividing a positive and a negative number , the result will be negative . < answer >C </ answer > == Side -step three is a move in basketball . Studs up is a term in football . Blocking foul is a penalty in football .Initially , we will define what it means for a sentence to be plausible in the context of sports . It is logical and consistent with the facts about sports when a sentence is plausible .Now , we will look into the given four examples . For example 1 , " Travis Konecny did a maradona on the defender ," we can infer that this sentence is not plausible since maradona is a move in football , not hockey . Similarly , for example 2 , " Bryce Harper hit the back shoulder fade ," we can also infer that this sentence is not plausible because back shoulder fade is a move in football , not baseball . For example 3 , " Tuukka Rask killed the powerplay ," we can conclude that this sentence is plausible because powerplay is a term in hockey . Likewise , for example 4 , " Giorgio Chiellini committed a handball in the FA Cup ," we can also conclude that this sentence is plausible because handball is a penalty in football and the FA Cup is a football competition .Based on the above analysis , the correct answers are : Handball is an illegal move in football , where a player touches the ball with their hand during a match . Side -step three is a move in basketball . Studs up is a term in football . Blocking foul is a penalty in football .Initially , we will define what it means for a sentence to be plausible in the context of sports . It is logical and consistent with the facts about sports when a sentence is plausible .Now , we will look into the given four examples . For example 1 , " Travis Konecny did a maradona on the defender ," we can infer that this sentence is not plausible since maradona is a move in football , not hockey . Similarly , for example 2 , " Bryce Harper hit the back shoulder fade ," we can also infer that this sentence is not plausible because back shoulder fade is a move in football , not baseball . For example 3 , " Tuukka Rask killed the powerplay ," we can conclude that this sentence is plausible because powerplay is a term in hockey . Likewise , for example 4 , " Giorgio Chiellini committed a handball in the FA Cup ," we can also conclude that this sentence is plausible because handball is a penalty in football and the FA Cup is a football competition .Based on the above analysis , the correct answers are : Handball is an illegal move in football , where a player touches the ball with their hand during a match . Side -step three is a move in basketball . Studs up is a term in football . Blocking foul is a penalty in football .Initially , we will define what it means for a sentence to be plausible in the context of sports . It is logical and consistent with the facts about sports when a sentence is plausible .Now , we will look into the given four examples . For example 1 , " Travis Konecny did a maradona on the defender ," we can infer that this sentence is not plausible since maradona is a move in football , not hockey . Similarly , for example 2 , " Bryce Harper hit the back shoulder fade ," we can also infer that this sentence is not plausible because back shoulder fade is a move in football , not baseball . For example 3 , " Tuukka Rask killed the powerplay ," we can conclude that this sentence is plausible because powerplay is a term in hockey . Likewise , for example 4 , " Giorgio Chiellini committed a handball in the FA Cup ," we can also conclude that this sentence is plausible because handball is a penalty in football and the FA Cup is a football competition .Based on the above analysis , the correct answers are : Example 1: no Example 2: no Example 3: yes Example 4: yes Now , we will examine the two new examples . For example 1 , " Dejounte Murray took a sidestep three ," we can conclude that this sentence is plausible since side -step three is a move in basketball . Similarly , for example 2 , " Luka Modric went in studs up in the FA Cup ," we can also conclude that this sentence is plausible because studs up is a term in football and the FA Cup is a football competition . To solve this problem , we can break it down into smaller steps . The first step is to find the time when the person woke up . Once we have that information , we can then proceed to the next step , which is to identify the earliest time slot that has not been accounted for .Today , James went to the swimming pool . Between what times could they have gone ? We know that : James woke up at 5 am . Ashley saw James sitting on a rooftop from 7 am to 9 am . Hannah saw James taking photos near the Eiffel Tower from 9 am to 7 pm . William saw James buying cookies at a bakery from 7 pm to 8 pm . 38th Conference on Neural Information Processing Systems (NeurIPS 2024)."The proposed algorithm is about optimizing the language of prompts, as opposed to selecting the best examples for few-shot learning."We performed EO after IO to optimize the exemplars generated by the best instruction; we also tested the inverted order (i.e., EO before IO) and interleaved optimization (detailed in App. B.8) and found the results to be largely robust to these design choices.Wu et al. [52], a concurrent work, precisely explored a combinatorial BO solution. 


Decision: Following the author rebuttal, all six reviewers have expressed positive ratings for this paper. I appreciate the efforts made by the authors; their work demonstrates novelty and potential impact, making it suitable for NeurIPS. However, the authors should consider the necessary revisions in the final version, particularly those highlighted by the reviewers.

Reviews: review: paper_summary: paper_summary: This work studies automatic prompt optimization, seeking to compare and to connect the literatures on instruction optimization and on example selection. They find that existing approaches for using LMs to self-generate examples and selecting between them can outperform the best existing instruction optimizers, but that combining the two is effective. They use this to recommend larger emphasis on few-shot examples in future prompt optimization work.
strength_weakness: strength_weakness: 1. The authors evaluate on BIG-Bench and MMLU tasks, which to my knowledge are extremely limited in scope. Most are narrow reasoning puzzles or manipulation tasks, e.g. multiple choice, and may not reflect the type or complexity of typical prompts people use in the increasingly elaborate open-ended LM systems out there. This has an effect on the extent of "self-generated" examples, which in this work are reduced to just chain of thought reasoning if I understand correctly, where all "inputs" and "labels" (in this case final answers) are known in advance, rather than trajectories of actual input/output labels for prompts per example. How would such open-endedness interact with the findings?

2. The authors already find very compelling results with ES, but the scope of existing example-based optimizers in the cited work like DSPy seem wider in terms of the search/optimization method and in the generation approach. For the latter, the authors employ a large LM to optimize the instructions for smaller LMs, but related work permits similarly a large LM (or the same LM but in already example-optimized form) to generate the examples for small LMs. As a result of this asymmetry, the effect of the source of instruction or example optimization is not explored or isolated. This seems unlikely to affect the results direction, but it may affect their magnitude substantially, perhaps making IO+ES less attractive than just ES.
questions: questions: 1. This is not a weakness of the present paper, but in the manner described here APE and OPRO are presented rather similarly in Sec 3.1. Overall, this raises the question of how the authors ensured their implementations are faithful to the original algorithms while being fair to all methods within a new test environment.

2. I appreciate the note in lines 199-201 about self-generation. The way this is presented suggests the authors thing it's important, but it's rather buried now and hard to concretely understand without an example or further elaboration, especially because the tasks considered in this work are rather "simple", e.g. not clearly multi-step. In addition, the term Example Selection (ES), which is not particularly universal in the literature, is perhaps setting this up for confusion, since selection directly assumes the presence of a set from which to select.
limitations: limitations: n/a
paper_summary: paper_summary: This work focus on evalution and comparison study of automatic prompt optimization (APO) methods. These methods are broadly categorized into instruction optimization (IO) and exemplar selection (ES). This paper seeks to bridge the gap between these two methods by comprehensively comparing the performance of representative IO and ES techniques both isolation and combination. This work found that how to select examplars can outweigh how to optimize instructions.
strength_weakness: strength_weakness: 1. In the experimental study part, this work only use two kinds of LLMs, PaLM 2 and Gemini, which is not quite adequate.
2. The evaluation criteria are a bit simple, only considering the acc rate. For engneering requirements, how many efforts (e.g. number of tokens; expense of the APO process; how much level of ) will be required during the prompt optimization is also important. Other reasonable metrics maybe also of help.
questions: questions: 1. What's the difference between methods from IO and ES in terms of the cost. Are there any differences in statistical characteristics between these two categories?
limitations: limitations: See weakness and question part.
paper_summary: paper_summary: This paper profoundly discusses how the deisgn of Automatic Prompt Optimization (APO) methods influence the performance of current instruction-following pre-trained large language models (LLMs). Concretely, the authors first systematically summarize and compartmentalize current APO methods into two lines: instruction optimziation (IO) and exempler sleection (ES), with their mathematical definitions. Then a series thorough and incremental experiments are carried out, of which primary discoveries includes: 1) reusing model-generated data (obtained from validation phase) as exempler shows performance improvement against standalone IO methods, with better efficiency. 2) combining IO and ES together would bring "1+1>2" performance improvement. Under these experimental results, the authors claim that studying ES methods should be put as top priority of APO studies.
strength_weakness: strength_weakness: After reading this paper from top to the bottom, I found my concerns revolve around limited evaluation: I would appreciate the authors if they could at least conduct an additional experiment on GPT-3.5 Turbo to reinforce the convincingness of all findings, since GPT models hold quite some users. To summarize, although I fully understand that ideally comprehensive evaluation experiment is never easy, the above aspects deserve to be investigated, at least. Besides, the contribution of this paper mainly involves benchmarking and concluding meaningful findings, which in my view, should be more suitable for Benchmark Track of NeurIPS.
questions: questions: see Weaknesses.
limitations: limitations: The authors have summarized the limitations of this work in Conclusion of the paper, which are objective. I strongly suggest the authors include more datasets (e.g., multimodal tasks) and models (e.g., GPT series) in their future works as they promised.
paper_summary: paper_summary: This paper provides a comprehensive investigation of instruction optimization and exemplar selection.
strength_weakness: strength_weakness: - The performances achieved by the different combinations of algorithms are indeed good, however, in terms of the relative comparison of the importance of IO and ES, I think it is possible that an unfair advantage is given to ES. First of all, in all methods studied in this paper, IO is performed first followed by ES, this allows ES to adapt to an already optimized IO, while IO is not able to adapt to exemplars since it is performed first before any ES. In addition, only those exemplars on which the optimized instruction predicts correctly are used for ES, this also gives an advantage to ES since it uses information from an already optimized instruction, whereas IO is not able to exploit information from already optimized exemplars since IO is performed first. Therefore, it puts into question the reliability of a major conclusion drawn from the paper, i.e., ES is much more important than IO.
- As mentioned in the last paragraph of Section 2, to the best of my knowledge, there is indeed a general lack of works on joint IO and ES. I'd like to point the authors to two concurrent works along this line: https://arxiv.org/abs/2405.18369, https://arxiv.org/abs/2405.16122. The second work may be of more interest, because it is exactly using something similar to the combinatorial BO approach which is alluded to on lines 295-296.
questions: questions: - The total number of prompt evaluations is selected as $m=32$. In my impression, this is in general a small number compared to the other related works on IO or ES. For example, OPRO uses more than 100 evaluations in most of its experiments. I wonder will the conclusions change if a larger $m$ is used?
- It has been widely reported that the ordering of the exemplars matters a lot. I wonder how do you determine the ordering?
limitations: limitations: A limitation is discussed in the Conclusion section.
paper_summary: paper_summary: The paper studies the instruction optimization and exemplar selection in auto prompt optimization. It has the following contributions:
1) Showing that optimizing ES improves significantly over IO and the importance of ES
2) Showing the synergy effect between ES and IO
3) Extensive experiments are conducted to validate the conclusions
strength_weakness: strength_weakness: 1. The authors have made a significant effort in summarizing the existing works, however, there are still some of the SOTA IO methods not mentioned:
- Connecting Large Language Models with Evolutionary Algorithms Yields Powerful Prompt Optimizers: https://arxiv.org/abs/2309.08532
- Use Your INSTINCT: INSTruction optimization for LLMs usIng Neural bandits Coupled with Transformers: https://arxiv.org/abs/2310.02905
2. Some of the baselines are mentioned in related work, however, the author did not compare with them (e.g., InstructZero). This can be important since these methods are SOTA methods of IO and may potentially produce much better results than the methods compared in this paper. It is true that the authors use simple methods for ES, however, do note that exemplars are natural data points (good data) while instructions are usually generated differently by different methods and hence a more careful design is needed. 
3. The no IO is based on a very good instruction “let’s think step by step” while no ES is just no examplar at all. Therefore for fair comparison /drawing insights from the experiments, the improvement on ES needs to be compared to random (or at least nearest) to say which optimization is more important.
4. As the author mentioned in mix-matching section, the improvement of the R.S., Mutation in Table 1, 2 can be because of the extra computation/queires to LLM used in the search phase. How much does the delta in these tables are from this factor? And how would this affect the conclusion of comparing the importance of ES and IO? These are unclear from the current experiments.
questions: questions: 1. The experiments are all conducted on PaLM and Gemini which are from the same company and hence some similar underlying designs. Can the results generalize to other major LLMs, e.g., GPT-4, Claude, Llama.
2. How does the author implement Nearest? Is it finding the nearest for each test input? or for a whole validation dataset?
3. ES after IO is used to run the result in Table 1 and 2, have the authors tried IO after ES, will the result change?
limitations: limitations: The limitations are stated in the weakness. It mainly lies in the mismatch between experimental settings and the insights.
paper_summary: paper_summary: This paper aims to study the performance impact of instruction optimization (IO) and exemplar selection (ES) both isolation and combination, as the automatic prompt optimization literature mostly only focuses on either IO or ES. Its empirical results on a wide range of tasks (e.g., BBH and MMLU) show that optimizing ES may bring more performance gain than IO, and highlight the importance of studying ES and its combination with IO.
strength_weakness: strength_weakness: 1. The paper only considers PaLM 2 and Gemini Pro (which are from the same source) as the target models. It is meaningful to see if the conclusion (i.e., ES outweighs IO) still holds for different target models (e.g., ChatGPT/GPT-4).

2. Some important settings are not explained. For example, in line 199, why ES is only performed from the exemplars self-generated by the target model, instead of choosing from $\mathcal{D}_{val}$. For $\mathcal{D}_c(I^*)$, only selecting the correctly predicted samples may not bring the highest performance, as some works show that wrong exemplars in ICL may be more valuable. In many IO works, they typically use more than 100 query evaluation budgets, instead of choosing $m=32$ naively in this paper.

3. The authors have the following objective in their paper:
>We aim to meet this by evaluating ES and IO in the context of APO by answering the following ... 2) How do we make the **optimal use** of the limited data and computational budget under the current APO framework?

Because of the synergy between ES and IO, the optimal use of ES and IO should exist at the *joint optimization* of ES and IO. However, the authors have only shown the performances of combining independently optimized instruction and optimized exemplars conditioned on that instruction. The optimality should be found when the exemplars and instructions are optimized together and the corresponding combinatorial optimization problem should cater to the space $\mathcal{I}\times\mathcal{E}^k$ rigorously. Intuitively, the optimized instruction should also depend on the given exemplars at each iteration. So, if the authors want to completely study how the effect of combining IO and ES, they should consider this joint optimization problem. Unfortunately, to the best extent, this paper only empirically shows (through brute force) that there may exist an optimal allocation of budgets $m_{IO}$ and $m_{ES}$ used for running the 'mixing-and-matching' strategy of ES and IO, which is far from the so-called **optimal use**.
questions: questions: 1. How did you choose the seed instruction? Do different seed instructions have different outcomes?

2. In Table 3, why ProTeGi is worse than (NO IO) if its optimization starts from the same seed instruction?

3. If you revert the process, that means you start ES first and run IO conditioned on the best ES you found, will this make the $\Delta IO$ greater than  $\Delta ES$?
limitations: limitations: Yes

Comments: title: Thanks for your response
Thank you
We'd love to hear your opinion on the rebuttal
We'd love to hear your opinion on the rebuttal
We'd love to hear your opinion on the rebuttal
Response to Authors
Detailed tables of the overall response
Continuation of rebuttal to Reviewer dxC3 (2/2)
Continuation of rebuttal to Reviewer dxC3 (1/2)
Continuation of rebuttal to Reviewer 1T7N
Continuation of rebuttal to Reviewer uqie
comment: Thanks for the response and additional results. Many of my concerns have been addressed. But for joint optimization, I think the author at least should propose a naive method to consider jointly optimizing prompts and exemplars (e.g., use a Bayesian optimization approach to model the prompt and exemplar together in a finite set and search for the promising combinations). As the evaluation and clarity of this paper remain an issue, I will increase my score to 5.
We'd like to thank the reviewer for engaging in the author feedback process and their valuable suggestions. As promised, we'll make sure to include additional results and discussions into the final version of the paper.
Thanks for your additional results. Most of my concerns are addressed by your response. Therefore, I will increase my score. Please add these additional results to your revision.
We'd like to thank the reviewer again for engaging in the rebuttal and appreciating our contributions -- we'll make sure to incorporate the reviewer's suggestions into the final version of the paper. As we are approaching the end of author discussion period, we are more than happy to answer any further questions or discuss any additional improvements that would potentially make the reviewer evaluate our work even more positively.
We thank the reviewer again for their time and effort engaging in the rebuttal, and we will make sure to incorporate the reviewer's suggestions into the final version of our paper.
Thank you for your constructive feedback and positive assessment of our work! We will make sure to incorporate the reviewer's suggestions into the final version of the paper.
Dear reviewer dxC3,

We thank you again for your time and discussion. Our impression with your original review is that you were concerned about 1) experiments on additional LLMs 2) some clarification about experimental setup (why exemplars are generated and the choice of evaluation budget) and 3) better joint optimization between IO and ES.

To address your concerns, on 1), we conducted experiments on two new LLMs; on 2), we clarified that the setup we adopt is consistent to that of several existing works, and we have already included experiments of our algorithm under a higher budget in App. B.10 and 3) we pointed out that we have, in fact, already considered the joint optimization in App B.8. We hope our response has alleviated your concerns — as we are approaching the end of the discussion period, we’d be grateful if you could read our response and let us know if you have additional questions. Your insights and replies are highly appreciated. We’d also be grateful if you could reconsider the rejection rating if you feel the concerns have been sufficiently addressed.

Thank you.

Best,

Authors
Dear reviewer 1T7N,

We’d like to thank you once again for your review. From your original review, we believe that your concerns were about 1) additional IO techniques 2) concerns on baseline selection and 3) additional LLMs. 

To address your concerns, 1) we clarified the rationale for our IO selection. Furthermore, we observe that on challenging tasks requiring chain of thoughts, none of the additional related works (EvoPrompt*, INSTINCT and InstructZero) compared against ProTeGi, which from our experiments is a very strong baseline because it additionally utilizes self-reflection on top of better evolution-like paraphrasing that these works focused on; we showed that the benefit of ES persists even with ProTeGi – after all, we do not aim to propose a new instruction optimizer but rather to derive generalizable insights from representative methods. 2) We clarified that we are following prior works, and also that changing the ES reference to “random exemplars” does not materially affect the conclusion. On 3) we added experiments on two additional LLMs. 

As the discussion period ends, we would greatly appreciate it if you could review our response and share any further questions. Your insights are highly valued, and we look forward to your feedback. We’d also be grateful if you could consider increasing the score if you feel the concerns have been sufficiently addressed.

Thank you!

Best,

Authors

*EvoPrompt compared against ProTeGi on simple text classification tasks like SST-2 and AGNews only, which arguably aren’t commensurate with the caliber of modern LLMs (e.g., [1] achieved similar performance using the much older 355M RoBERTa with prompting, with differences of at most a few percentage points compared to EvoPrompt results with a 7B Alpaca [1]). On more challenging tasks, EvoPrompt, however, only compared against manual instruction (“Let’s think step by step”; referred to as “No IO” in our paper) and APE (App C.3, with ~3% improvement, which is smaller than the margin we showed with ES across all models (PaLM 2, Gemini 1.0 + 1.5, GPT-3.5) considered). The other works did not compare against ProTeGi in all experiments.

[1] TEMPERA: Test-Time Prompting via Reinforcement Learning, ICLR 2023
Dear reviewer uqie,

We thank you once again for your time. From your original review, your main concern was about the fairness of comparison between IO and ES. 

To address your concerns, we 1) clarified that we first conducted IO and ES separately over the same reference and 2) conducted additional experiments in a swapped order (i.e., ES before IO). As we are approaching the end of the discussion period, we’d be grateful if you could read our response and let us know if you have additional questions? Your comments have been tremendously helpful in improving our paper, and we’d like to hear your opinion on the rebuttal. We’d also be grateful if you could consider increasing the score if you feel the concerns have been sufficiently addressed.

Thank you!

Best,

Authors
Thanks for your reponse and all of my questions have been addressed. Good work and I will maintain my score.
Thank you for the response. All my concerns are addressed more or less. I still insist that this paper serves more as a benchmark track paper but also agree with the authors that the contributions are also suitable for main track. I raise my score to 5.
Thank you for the detailed response. It helps me maintain my high score of this work.
**Table S1**: Effect of different IO/ES order on gemini-1.0-pro-002
|        gemini-1.0-pro-002       | IO only | ES only | Combined, *IO first* | Combined, *ES First* |
|:-------------------------------:|---------|---------|:------------------:|-------------------:|
|             boolean_expressions |  79.50% |  91.00% |             90.50% |             90.50% |
|                causal_judgement |  54.67% |  59.33% |             66.00% |             66.00% |
|              date_understanding |  73.50% |  78.50% |             79.50% |             74.50% |
|                geometric_shapes |  33.00% |  71.00% |             67.50% |             84.50% |
| logical_deduction_seven_objects |  31.00% |  50.00% |             47.50% |             51.00% |
| logical_deduction_three_objects |  49.00% |  76.50% |             78.00% |             79.00% |
|        multistep_arithmetic_two |  77.50% |  84.00% |             79.50% |             81.00% |
|                        navigate |  58.00% |  85.50% |             89.50% |             89.00% |
|                 object_counting |  78.50% |  95.50% |             94.50% |             94.00% |
|             penguins_in_a_table |  78.63% |  84.62% |             93.16% |             84.62% |
|              temporal_sequences |  79.50% |  84.00% |             77.50% |             82.50% |
| (Average)                       |  62.98% |  78.18% |             78.47% |             79.69% |

**Table S2**: Effect of different IO/ES order on gemini-1.5-flash-001
| gemini-1.5-flash-001            | IO only | ES only | Combined, *IO first* | Combined, *ES First* |
|---------------------------------|---------|---------|:------------------:|-------------------:|
|             boolean_expressions |  90.50% |  99.50% |             96.00% |             99.00% |
|                causal_judgement |  68.00% |  67.33% |             67.33% |             63.33% |
|              date_understanding |  80.00% |  84.50% |             84.00% |             83.00% |
|                geometric_shapes |  54.50% |  82.00% |             90.50% |             81.00% |
| logical_deduction_seven_objects |  50.00% |  70.00% |             80.50% |             72.00% |
| logical_deduction_three_objects |  91.00% |  89.50% |             92.50% |             93.50% |
|        multistep_arithmetic_two |  91.50% |  91.50% |             92.50% |             91.50% |
|                        navigate |  66.00% |  69.00% |             74.00% |             85.00% |
|                 object_counting |  86.50% |  95.50% |             93.50% |             93.50% |
|             penguins_in_a_table |  95.73% |  94.87% |             95.73% |             94.87% |
|              temporal_sequences |  97.50% |  99.50% |             99.50% |            100.00% |
| (Average)                       |  79.20% |  85.75% |             87.82% |             86.97% |

**Table S3**: detailed per-task breakdown of interleaved optimization presented in Appendix B.8 with PaLM 2
|                                    Task | Test accuracy |
|----------------------------------------:|:-------------:|
|                     boolean_expressions |        88.50% |
|                        causal_judgement |        70.00% |
|                      date_understanding |        75.50% |
|                       disambiguation_qa |        72.00% |
|                        formal_fallacies |        58.50% |
|                        geometric_shapes |        69.50% |
|                              hyperbaton |        93.50% |
|          logical_deduction_five_objects |        41.50% |
|         logical_deduction_seven_objects |        55.50% |
|         logical_deduction_three_objects |        91.00% |
|                    movie_recommendation |        79.50% |
|                multistep_arithmetic_two |        75.50% |
|                                navigate |        65.00% |
|                         object_counting |        85.50% |
|                     penguins_in_a_table |        89.74% |
|         reasoning_about_colored_objects |        74.00% |
|                              ruin_names |        86.00% |
|     salient_translation_error_detection |        58.00% |
|                                  snarks |        81.12% |
|                    sports_understanding |        82.00% |
|                      temporal_sequences |       100.00% |
|  tracking_shuffled_objects_five_objects |        52.00% |
| tracking_shuffled_objects_seven_objects |        63.00% |
| tracking_shuffled_objects_three_objects |        64.50% |
|                             web_of_lies |        89.00% |
|                            word_sorting |        80.00% |
|                               (Average) |        74.63% |
Secondly, while we fully agree that ways to better integrate the joint optimization are important (we acknowledged this towards the end of Page 8 — “*we note that the presented way to combine optimization-based IO and ES is a proof of concept and room for future improvement can be vast: e.g., instead of two-stage optimization, it is also possible to optimize them jointly, interleavedly, or otherwise better exploit the inter-dependence between instructions and exemplars*”), **it is still an open research question**. Furthermore, **recognizing the importance of this joint optimization *problem* is the premise and the prerequisite to how to derive better *solutions***, the latter of which is where the reviewer’s concerns focused on. However, as argued in the paper and concurred by the other reviewers, we believe that the importance of the problem itself is under-appreciated, and exposing its benefit is a core contribution of ours. As discussed, most existing works only focus on either aspect but not both, and **our two-stage approach**, while simple and straightforward, has already led to significant improvement and is certainly **more optimal than instruction OR exemplar optimization only**. Thus, while we agree that there is always room for algorithmic improvement, and we will make this point even clearer in the paper, we also argue that our contributions should be assessed relative to the status quo in the literature.

> In Table 3, why ProTeGi is worse than (NO IO) if its optimization starts from the same seed instruction?

We followed the standard validation-test split and the test set is only evaluated once after selecting the instruction that led to the best validation accuracy. However, better validation performance does not always generalize to the test set (overfitting), and in this case the optimized instruction actually led to worse test performance.

> If you revert the process, that means you start ES first and run IO conditioned on the best ES you found, will this make $\Delta IO$ larger than $\Delta ES$

Firstly, we’d like to point out that the relative importance of ES and IO ($\Delta ES$ vs $\Delta IO$) has been studied both *in isolation* and *when combined* -- the ordering is only relevant when we combine them, but **the relative importance was first studied when each is performed separately**. With reference to Table 1-3, the results on the first row (“No IO”) are all obtained **without any instruction optimization**, and as we highlighted in bold on Page 6, optimized exemplars on top of seed instructions still outperform optimized instructions but with unoptimized exemplars, relative to the common reference point (i.e., seed instruction without exemplars).

Second, as we detail in the common response, we also performed experiments with the opposite order where in Stage 1, we optimize the exemplars based on the seed instruction, and in Stage 2, we freeze the exemplars and optimize the instruction. We performed experiments on a subset of all tasks using both Gemini 1.0 and 1.5 models, using APE to optimize instructions and random search to optimize exemplars with a total budget of m=32 (the setup presented in Fig 6 of the paper). We find that using the swapped order (ES-IO) led to comparable aggregated results (on Gemini 1.0: IO first: 78.5%; ES first: 79.7%; on Gemini 1.5: IO first: 87.8%, ES first: 87.0%). Relative to ES only (Gemini 1.0: 78.2%; Gemini 1.5: 85.8%), it should be clear that **the bulk of the improvement is still attributable to ES, regardless of the ordering**.

As mentioned above, another alternative is to use multi-stage interleaved optimization, as detailed in our response to the previous question. As we mentioned earlier, we highlighted the simple two-stage framework because, empirically, we found the interleaved algorithm to perform roughly similarly in practice.


[1] Anil et al. (2023). Palm 2 technical report. arXiv preprint arXiv:2305.10403.

[2] Google (2023). Gemini: a family of highly capable multimodal models. arXiv preprint arXiv:2312.11805.

[3] Suzgun et al. (2022). Challenging big-bench tasks and whether chain-of-thought can solve them. arXiv preprint arXiv:2210.09261.

[4] Khattab et al. (2024). DSPy: Compiling declarative language model calls into self-improving pipelines. ICLR.

[5] Agarwal et al. (2024). Many-shot in-context learning. arXiv preprint arXiv:2404.11018.

[6] Gao & Das (2024). Customizing Language Model Responses with Contrastive In-Context Learning. AAAI. 

[7] Wei et al. (2023). Larger language models do in-context learning differently. arXiv preprint arXiv:2303.03846.

[8] Kojima et al. (2022). Large language models are zero-shot reasoners. NeurIPS.

[9] Yang et al (2024). Large language models as optimizers. ICLR.

[10] Wang et al. (2024). PromptAgent: Strategic planning with language models enables expert-level prompt optimization. ICLR.
>  In many IO works, they typically use more than 100 query evaluation budgets, instead of choosing 32 naively in this paper.

While we are aware of works that use >100 query budgets, other works, like DSPy (which used “10-20 trials” – see Page 9 of [4]) also set a query budget similar to us – in this sense, using smaller evaluation budget for the given small amount of labeled data is not more “naive” than a larger budget, since it is just a matter of hyperparameter choice. In fact, we’d argue that performance at a tighter budget is more practically impactful and relevant as a larger evaluation budget leads to worse latency and higher cost; in most real-life setups, we cannot assume that the user can afford a long wait time and/or large budget – a key purported advantage of APO is that it eliminates the need for expensive prompt engineering, and it is important that we do not substitute an expensive process with another. Second, **we’d like to refer the reviewer to Appendix B.10, Page 40 in our paper, where we extend the evaluation budget to 100** and compare the simple two-stage optimization against PromptBreeder, which takes hundreds of iterations to converge. It is evident that the simple algorithm performs on par or better than the much more complicated PromptBreeder in most cases and converges faster.

> How did you choose the seed instruction? Do different seed instructions have different outcomes?

We chose “Let’s think step by step”, a well-known prompt introduced by [8] as the seed instruction. This seed instruction is commonly used at initialization in numerous prior works [9,10, inter alia].

To answer the second part of the reviewer’s question, we run experiments with Gemini 1.0 models using different seed instructions. We run both APE and the two-stage IO-ES on it – please see the results below for aggregated results across 11 tasks. Apart from “Let’s think step by step,” we also tested two other initial prompts presented in previous works “Let’s think logically” also from [8] and “Let’s work this out in a step by step way to be sure we have the right answer,” from [9] – we can see that while IO-only can be significantly affected by the seed (>10% difference between best and worst seeds), two-stage IO-ES effectively shrank the gap to <3%. This should demonstrate our general robustness to initialization. We will include these discussions in the final version of the paper. 

|                                                        Initial instruction (I_0) |  IO-only (APE) | Two-stage IO-ES |
|---------------------------------------------------------------------------------:|-----:|-----------|
|                                              Let's think step by step (original) [8] | 63.0 | 78.5      |
|                                              Let’s think about this logically [8] | 56.0 | 75.8      |
| Let's work this out in a step by step way to be sure we have the right answer [9] | 66.7 | 77.5      |

> Because of the synergy between ES and IO, the optimal use of ES and IO should exist at the joint optimization of ES and IO. However, the authors have only shown the performances of combining independently optimized instruction and optimized exemplars conditioned on that instruction…  Intuitively, the optimized instruction should also depend on the given exemplars at each iteration. So, if the authors want to completely study the effect of combining IO and ES, they should consider this joint optimization problem.

Firstly, we thank the reviewer for their suggestion, and **we’d like to bring their attention to Algorithm 1 in Appendix B.8, which is exactly an example of how one may approach the joint optimization problem by allowing optimized exemplars and instructions to condition on each other and co-evolve**. Since we empirically found Algorithm 1 to achieve a comparable performance to the two-stage algorithm **(please see the common response for details)**, we emphasized the simpler algorithm for the sake of parsimony and ease of implementation. We agree that discussions on this should be made clearer in the main text, and we will amend the paper accordingly.
> Additional LLMs

We thank the reviewer for their suggestions. We have included additional results on GPT and Gemini 1.5 below. With the new experiments added, we believe that our results now cover a comprehensive set of LLMs with a continuum of model caliber, especially with the Gemini 1.5 model family [performing at or very close to the state of the art](https://arena.lmsys.org/) – made possible by the long-context ability, we also included an “All” column in Gemini 1.5 experiments, which includes all valid demonstrations without any selection. The new results are in near unanimous agreement with the key insights in the paper, and we believe this presents clear evidence that the patterns in the paper are not due to artifacts of individual models. We’d like to refer the reviewer to the common response for more details about the new experiments conducted.

### gpt-3.5-turbo-0125*


|         |    No ES | Random | Search | Δ ES      |
|:-------:|---------:|-------:|--------|-----------|
|  No IO  |     59.0 |   68.6 | 76.8   | **+17.8** |
|   APE   |     63.0 |   68.9 | 78.4   | **+15.4** |
| ProTeGi |     68.9 |   72.2 | 80.2   | **+11.3** |
| Δ IO    | **+9.9** | +3.6   | +3.4   |           |

### gemini-1.5-flash-001

|         |    No ES | Random | Nearest | Diversity | All  | Search | Δ ES     |
|:-------:|---------:|-------:|---------|-----------|------|-------:|----------|
|  No IO  |     75.1 |   80.0 | 81.7    | 81.5      | 80.4 |   83.3 | **+8.2** |
|   APE   |     77.5 |   81.2 | 83.7    | 81.6      | 81.2 |   85.0 | **+7.5** |
| ProTeGi |     80.4 |   82.4 | 82.6    | 82.3      | 83.5 |   84.5 | +4.1     |
| Δ IO    | **+5.3** | +2.2   | +2.0    | +0.8      | +3.1 | +1.8   |          |

> Nearest implementation

To implement nearest, we embed each test input using the [Gecko embedding model](https://arxiv.org/pdf/2403.20327) and retrieve the nearest exemplar in D_c based on input similarity, so each test input is likely to receive different exemplars as a result of this.

> ES after IO is used to run the result in Table 1 and 2, have the authors tried IO after ES, will the result change?

We thank the reviewer's suggestion. To answer this question, we also performed experiments with the opposite order where, in Stage 1, we optimize the exemplars based on the seed instruction, and in Stage 2, we freeze the exemplars and optimize the instruction. We performed experiments on a subset of all tasks using both Gemini 1.0 and 1.5 models, using APE to optimize instructions and random search to optimize exemplars with a total budget of m=32 (the setup presented in Fig 6 of the paper). We find that using the swapped order (ES-IO) led to comparable aggregated results (on Gemini 1.0: IO first: 78.5%; ES first: 79.7%; on Gemini 1.5: IO first: 87.8%, ES first: 87.0% – please refer to the common response for task-specific breakdown). We believe these new experiments provide sufficient evidence that the conclusion drawn in the paper is not due to any bias created by a specific ordering — we will incorporate a more comprehensive evaluation of this in the camera-ready copy.
> Additional related works

We thank the reviewer for bringing related works to our attention. We agree the second paper is particularly relevant. As the reviewer aptly pointed out, the method is exactly a “combinatorial Bayesian optimization” approach mentioned by us. The authors also motivated their work with the importance of exemplar selection. They proposed a joint ES-IO algorithm, and we are glad that contemporary research on prompt optimization has put more effort into improving both exemplars and instructions holistically, which is exactly the practice championed in our paper. The key difference is that the key contribution of the mentioned paper is to propose a specific method (EASE). In contrast, we aim to obtain general insights on the best practices for prompt design by drawing upon the literature. We believe the contributions are complementary to each other (for example, we believe it is possible that the improvement brought by EASE over the pure instruction optimization methods shown in the paper could be partly explained by the exemplar optimization it performed). We will incorporate more detailed discussions of these related works in the final version of the paper.

> The choice of m, and whether a larger m will affect the conclusion.

We chose a relatively small m because a tighter budget is more practically impactful and relevant as a larger evaluation budget leads to worse latency and higher cost; in most real-life setups, we cannot assume that the user can afford a long wait time and/or large budget – a key purported advantage of APO is that it eliminates the need for expensive prompt engineering, and it is important that we do not substitute an expensive process with another. Second, **we’d like to refer the reviewer to Appendix B.10, Page 40 in our paper, where we perform some preliminary experiments where we increased the evaluation budget to 100** to compare against PromptBreeder, which takes hundreds of iterations to converge. It is evident that the simple algorithm performs on par or better than the much more complicated PromptBreeder in most cases and converges faster.

> Ordering of exemplars

We thank the reviewer for the suggestion – it is indeed well-known that the ordering of the exemplars can affect downstream performance. However, our high-level impression is that for the frontier models, the effect of ordering seems to be secondary to the choice of exemplars. Secondly, for a data-driven exemplar optimization algorithm, the order is implicitly optimized at the same time – for example, in random search, each iteration draws an *ordered* tuple of demonstrations, and an argmax over all draws is taken for testing – a data-driven optimization method only considers performance metric but is agnostic to what contributed to it, and it is possible that the optimality of the chosen demo set is partly attributable to order.

[1] Khattab et al. (2024). DSPy: Compiling declarative language model calls into self-improving pipelines. ICLR.

[2] Agarwal et al. (2024). Many-shot in-context learning. arXiv preprint arXiv:2404.11018.