We thank the reviewer for taking the time to review our paper. We are glad to know that our paper has provided insights into the impact of exemplar selection through a wide range of baseline comparisons.

We would like to address the specific concerns and questions raised by the reviewer below:

[W1] Performance on II is very close to random search baseline

You are right that the random baseline performs well in Tab. 1 of Instruction Induction (II) tasks. It is not unexpected that random is a strong baseline: In particular, we highlight in second para. of Sec. 4.1 that such tasks might not be suitable for evaluation of the exemplar selection's effectiveness. This is likely due to data contamination where the benchmark data have been extensively used to train the target model (i.e., GPT-3.5 in our paper). Therefore, the target model easily identifies the task through exemplars (including those selected by the random baseline) and utilizes its expert knowledge on the task to answer. This explains why the choice of in-context exemplars has minimal impact on the performance in contaminated tasks. To better evaluate the effectiveness of exemplar selection, we propose three classes of tasks in Sec. 4.3 and see the significant advantages of EASE in them. We attribute the performance gain to the fact that EASE balances exploration and exploitation to be more effective under budget constraints. The above observation aligns with our insights from progressive finetuning (Sec. 4.2): As the model knows more about the task, the effect of in-context exemplars diminishes.

[W2] Validate on open-weight models for reproducibility

As suggested by the reviewer, we conduct additional experiments with open-weight models. Due to the limited time during rebuttal, we use a representative (Meta's newest) model Llama-3.1-8B-Instruct as the target model. We present the results in Tab. A5 of rebuttal PDF. Importantly, the results are consistent with the original conclusions we drew for the black-box models in the paper. The model is also much smaller than GPT-3.5, hence making it easier for others to deploy and reproduce the results. We hope this further improves the reproducibility of our results.

That said, we still advise practitioners to use the black-box models for comparison, which can be more affordable especially in academic settings (pay-as-you-go APIs vs. hosting a model on servers). We note that the black-box model is also fair for comparison because all baseline methods essentially undergo the same pre- and post-processing.

[Q1] “Out-of-distribution” tasks selection

We agree with the reviewer that we cannot confirm whether a task is already well-trained without access to the training data. We clarify that "out-of-distribution" tasks are defined loosely here (hence in inverted commas as mentioned in Lines 276-277 of our paper). If this is not a suitable name, we will gladly adopt another name that the reviewer deems fit; let us know!

We select these tasks with the following practical intuitions:

(1) If a task contains novel rules such that the model has to extract the underlying relationships among the provided in-context exemplars and directly use the relationship for test-time inferences, it is unlikely that these tasks appear in the training dataset (Rule-based tasks in Lines 281-303).

(2) If a task is constructed through random label remapping to be against the model's existing knowledge (e.g., "good" sentiments are mapped to "bad" sentiments), it is unlikely such tasks appear in the training dataset (Remapped label tasks in Lines 304-314).

(3) If excessive noises are added to existing real datasets, it is likely to present a distributional shift from the original real distribution to one that the model has not seen before (Noisy tasks in Lines 315-322).

To provide more empirical evidence, we refer the reviewer to Tab. A6 & A7 of rebuttal PDF. We performed random exemplar in-context prompting and discovered that it achieved an average performance of 17.6% for "out-of-distribution" tasks, which contrasts with the average performance of 64.7% for II benchmark tasks. This demonstrates that the model is likely to have less knowledge about our defined "out-of-distribution" tasks. Additionally, we can also see that the performance gain of EASE is higher for "out-of-distribution" tasks.

[Q2] Using a range instead of a fixed value of $k$ as in D.5

If we understand correctly, you refer to the setting of allowing a range instead of a fixed value of $k$ to be selected. That is, if $k=50$, we allow the number of exemplars in the prompt to be any integer from 1 to 50. We present the additional results in Tab. A6 of rebuttal PDF. Firstly, EASE continues to consistently outperform the strongest baseline Best-of-N. Secondly, we also observe that the prompts with the best performance typically have a large number of exemplars, i.e., close to the max $k$ allowed. Thirdly, using $k=50$ gives better performance than $k=5$. Therefore, including more exemplars in the prompt usually gives a higher performance. However, this comes at the expense of a higher query cost at test time because more tokens are used in the prompt.

We thank the reviewer for pointing us to this interesting insight which we will add to the revised paper.

Minor issues: Related works and presentation

We thank the reviewer for pointing out ways to improve the presentation of the paper. With the additional page upon acceptance, we can certainly move the dedicated related work section (now in App. A) back to the main paper to ensure a better flow. We also welcome other ways to improve the structure of presentation in our paper.

We hope our clarifications above have helped to improve your opinion of our work.

We thank the reviewer for taking the time to review our paper and acknowledging that we address a significant problem with a well-founded and novel method.

We would like to address your specific questions below:

[W1] Similar to [1]

In EASE, we face the challenge of an exploding permutational search space of exemplars that is distinct from [1]. A direct application of NeuralUCB would not work in practice for exemplar selection without our search space reduction technique through OT. It is also new to formulate the problem as one of optimization in the space of exemplar sequence embedding, which entirely removes the reliance on a white-box LLM as in [1]. The new formulation also enables the natural incorporation of instructions and hence the joint optimization of instructions and exemplars. Thus, the distinct solutions of EASE come from the unique challenges in exemplar selection. We also refer to the explanation of our distinction from [1] in Lines 159-165.

[W2] The literature review is inadequate

To clarify, we have a more extensive related works section in App. A, which expands on the ones discussed in Introduction. We will add references to RLPrompt, TEMPERA & GrIPS in our revised paper. We will have an additional page to include related works in the main paper upon acceptance.

[W3] Other related works

We thank the reviewer for the references. As long as the instruction optimization method can handle permutational search space of exemplars, they can serve as a baseline. While they are valuable references to add in our related works (we will do so for the revised paper), it is non-trivial to adapt these works to our problem setting, as discussed below.

LLMs: APE [5] and OPRO [6] rely on LLM's generation for the instruction search space and hence are not designed for exemplar selection. It is non-trivial to adapt them for exemplar selection. Nevertheless, we did a workaround and adopted the same spirit of asking the LLMs to directly select exemplars for us by explicitly telling LLM the search space. In App. D.9, we demonstrated that EASE performs much better than asking LLMs to select exemplars.

RL: The discrete optimization of a fixed-length prompt (i.e., no exemplars) in RLPrompt cannot be easily extended to our setting of exemplar optimization. TEMPERA focuses on query-dependent (vs. our query-agnostic) prompts which we argue to carry privacy risks of data exposure in Introduction paragraph 2. The formulation of TEMPERA also only supports classification tasks. So, we cannot adapt these methods to compare with EASE.

GA: GrIPS only focuses on iteratively editing the instruction and does not optimize for exemplars. Specifically, it either uses a fixed set of exemplars or performs a simple heuristic random search (Sec. 5.2 & 5.8 of GrIPS). In our paper, we have in fact demonstrated the superior performance of EASE against random search in Best-of-N.

[W4] Efficiency

To clarify, EASE excels in query efficiency instead of time efficiency (Lines 85-90). While EASE can take longer to perform the optimization, the saving in the LLM API calls or black-box LLM queries can be substantial. So, we perform a fair comparison with the baselines in all tables using a fixed target LLM call/query budget.

To address the question of the performance for a large $N$, we perform additional experiments with $N$=500. The results are shown in Tab. A1 of rebuttal PDF. Compared to the original Tab. 2 of the paper, we see that the performance gain of EASE is still significant even though all baselines (Evo, Best-of-N, and EASE) improve with a larger budget $N$.

[W5][Q4] More real datasets

We highlight that EASE also works better than baselines in real datasets: In Tab. 1, EASE achieves top performance for 17 tasks while Best-of-N tops only 11.

To make the case more convincing, we conducted experiments on a number of additional real benchmarks. We present results on the benchmarks used in the TEMPERA paper in Tab. A4 of rebuttal PDF, including MR, Yelp P., CR, MNLI & MRPC. Note that these tasks are overly simple to distinguish the effectiveness of EASE because all of them achieve above 80% accuracy and are hard to improve further using mere in-context examples.

So, we refer the reviewer to more complicated benchmarks on real tasks with reasoning chains in Tab. A2 of rebuttal PDF, which we just experimented with during the rebuttal period. We hope that the good performance of EASE on MATH, GSM8K & AQuA-RAT with CoT reasoning chains makes the baseline comparisons in our paper more convincing.

Questions

[Q1] Brute-force search

We note that the search space grows exponentially with the size of $D$. We use $|D| = 100$ in most experiments. However, even when $|D| = 10$, a brute-force approach is still not feasible because permuting 5 exemplars with 10 candidates yields $10^5$ possibilities. It can incur a considerable monetary cost to query the black-box API and obtain the best exemplar sequence.

[Q2] Uncertainty for NN

Due to length restrictions, we will answer this separately in an official comment below.

[Q3] NeuralUCB hypers

In order to show the robustness and generalizability to all possible tasks, the same set of hyperparameters should perform well on all tasks. So, we fix the architecture of the NN, learning rate, weight decay, and training iterations and do not tune them. We also used the extent of exploration $\nu=0.01$ throughout all experiments after searching from four values $[0, 0.01, 0.1, 1]$.

We hope our clarifications above have helped to improve your opinion of our work.

We thank the reviewer for taking the time to review our paper. We are glad to hear that our approach is unique, the empirical evaluations are extensive on comprehensive baselines, and our explanations are clear.

For the specific concerns and questions raised, we will address them below:

[W1] On-the-fly computation of embeddings as a potential computational bottleneck

[Q1] Insights or potential solutions to mitigate the computational bottleneck

In addition to the optimal transport (OT) introduced in EASE to reduce the on-the-fly computation of embeddings required, we can potentially eliminate the on-the-fly embedding entirely by adopting the average embedding (AvgEmb) of individual exemplars. However, there is no free lunch: Such computational simplification comes at the cost of performance due to the loss of order information. We performed ablation studies in App. D.6 to demonstrate that simply averaging the embeddings of all exemplars using AvgEmb results in worse performance. Though not as good, note that AvgEmb still achieves a decent and competitive performance. The practitioners can balance the trade-off and select the most suitable method.

While the above approaches either use pre-trained models for on-the-fly sequence embedding or discard order information altogether, there is a potential alternative: One can try concatenating the individual exemplar embedding as the NN input such that the order information is captured in the concatenated embedding. However, this method may require more training data to fit the NN due to a more complex mapping (from the higher dimensional input space). Also, this method may not scale well when selecting a large number $k$ of exemplars.

[W2] EASE's reliance on the availability of a suitable validation set as a limitation

[L1] Especially in contexts where validation data is scarce or difficult to obtain

We clarify using a validation set is a common practice as in [4, 43, 14]. The validation dataset can be as small as 20 data samples to provide meaningful evaluations of the prompts to guide the optimization process. We used 20 validation samples for all experiments. The manual creation of a small validation set should not be very difficult or expensive.

Moreover, in situations where a suitable validation set is simply not possible to obtain, it is possible to revert to human feedback/responses, thanks to the recent work of Lin et al. (2024). We can replace the numerical validation score with binary human feedback (i.e., asking a human to select a preferred prompt according to the responses/outputs of two prompt candidates). This greatly relaxes the requirement of a labeled validation set and only requires preference feedback from an interactive human user.

[W3] More detailed guidance on effectively implementing this joint optimization in practice.

Sure! We will elaborate more details of the joint optimization in the revised paper. We will provide some rough explanations here:

According to Line 5 of Algorithm 1, the instructions augment the search space by the size $|P|$. In practice, the most straightforward implementation without increasing the computational complexity is to reduce $|Q'_t|$ from $q'$ to $q'/|P|$. More generally, one can randomly sample $r\times |P|$ instructions to pair with $q'/(r\times |P|)$ exemplar sequences. This implementation is simple yet effective, where $r$ controls the trade-off of focusing more on instructions vs. exemplars.

[Q2] While combining EASE with retrieval-based methods for large exemplar sets has shown better performance, could you elaborate on any potential limitations or challenges of this approach?

We thank the reviewer for recognizing our effort in using retrieval-based methods to tackle large exemplar sets. We would like to elaborate on some limitations:

(1) The filtering through retrieval-based methods completely eliminates the consideration of a large subset of exemplars in the later optimization stage. This may result in important exemplars being left out and never explored again in our automatic optimization.

(2) The cosine similarity retrieval places a strong bias on preferring exemplars that are similar (in the embedding space) to the validation set, which may not yield the best performance in practice. This bias is dependent on the retrieval model and the retrieval metric used which therefore need to be carefully selected.

These limitations come with the simplification of the search space for practical efficiency reasons. We will add a section to discuss the above limitations and challenges for future research and improvements.

[L2] The selection of exemplars could inadvertently reinforce biases present in the training data. The authors could address how EASE mitigates bias and ensures fairness in exemplar selection, especially in sensitive applications.

Fairness is an important aspect to consider as the reviewer pointed out. We would like to refer the reviewer to App. B where we emphasize the responsible deployment of our method, including integrating safety measures and ethical constraints in the objective metric. In sensitive applications, we suggest integrating the performance objective metric with fairness such as demographic parity, equal opportunity, equalized odds, etc. to mitigate bias in exemplar selection. The integration can be done with an adjustable hyperparameter controlling the extent of fairness to be enforced, which depends on the critical and sensitive nature of the application.

We hope our clarifications above have helped to improve your opinion of our work.

References

(Lin et al., 2024) Prompt Optimization with Human Feedback. arXiv.

Dear Reviewer FzJo,

Thank you for taking the time to review our paper!

As the discussion period is concluding in less than a day, we hope to hear from you whether our rebuttal has sufficiently addressed your questions and concerns. We have provided additional insights and proposed potential solutions to the computational bottleneck. We also justified the use of our validation dataset, while offering an alternative approach to remove the validation dataset in future works. We also hope that our detailed guidance on joint optimization, along with our discussion of the limitations helped to improve the quality of the paper.

We are more than happy to answer any further questions during the remaining discussion period.

Best regards,

Authors of Paper 16009

We thank the reviewer for taking the time to review our paper and acknowledging the strong results, valuable insights, and possibility of future extension.

We will address your concerns below:

[W1] About "off-the-shelf embeddings"

We justify in the paper that off-the-shelf encoders are "commonly used for downstream clustering, semantic search, and classification". We regard prompt optimization as a similar downstream application that can leverage the advantages of such pre-trained encoders.

As for order sensitivity, we have a dedicated section that discusses the benefit of the ordering-aware embedding through ablation studies in App. D.6. Therefore, the sensitivity to ordering is leveraged effectively in EASE to produce better performance as compared to the order-agnostic AvgEmb.

However, we do observe differences for different encodings: see Tab. 16 in App. D.8. According to the reviewer's comments, it is worth investigating as a future direction to develop or finetune embedding models specifically for the purpose of prompt optimization, such that it captures important aspects of the prompt in the latent space.

[W2] Retrieval is fast

We thank the reviewer for pointing out the comparatively negligible computational overhead for retrieval. Considering the fast retrieval in practice, we would instead comment that test time computation is not needed for our method. We also wish to highlight that the decreased privacy risks and the enhanced empirical effectiveness continue to be the advantages of our method.

[W3] Experimental details

We refer the reviewer to App. C for all implementation details. We reproduce them here for ease of reference.

LM choice: Default is gpt-3.5-turbo-1106. In App. D.7, we also show that EASE is generally useful for different black-box models, including GPT-4-V, GPT-4-Turbo, and Gemini Pro.

Budget size: Default is 165 rounds of validation evaluation (same as [14]). We conduct additional experiments by increasing the budget to 500 and show the results in Tab. A1 of rebuttal PDF. Increasing the budget improves performance.

Training set size: Default is 100 data points. In App. D.5, we increase to $n$=1000 and show that EASE is able to select a large number of exemplars from a larger training data pool.

Validation data: Default is 20 validation data exemplars. Using a larger size may reduce performance variance and reduce "overfitting" (i.e., finding exemplars and instructions that work well only on the validation set), while having a higher cost.

[W4] Reasoning chains or open-ended generation

Reasoning chains: As suggested by the reviewer, we conduct additional experiments for tasks with reasoning chains, including MATH (Hendrycks et al., 2021), GSM8K (Cobbe et al., 2021), and AQuA-RAT (Ling et al., 2017). From Tab. A2 of rebuttal PDF, EASE works well for these tasks.

Open-ended generation: Tasks like auto_categorization, word_sorting, LR, and LP-variant are beyond simple direct classification-type labels. For example, auto_categorization requires outputting an open-ended sentence that categorizes the inputs well; LP-variant does open-ended sentence translation following a set of nontrivial rules.

Therefore, these tasks demonstrate the generalizability of EASE on various tasks of different levels of difficulty and response types.

[W5] Reference for Evo and Best-of-N

We thank the reviewer for suggesting references for Evo and Best-of-N. We will add connections to PhaseEvo for our Evo baseline, and connections to RandomSearch implemented in DSPy for our Best-of-N baseline. These references will serve as stronger support for the validity of the baselines that we compare with, and hence demonstrate the effectiveness of EASE.

Questions

[Q1] Insight on OT

Intuitively, OT selects exemplar candidates such that they are on average close to the embeddings of validation exemplars in $D_V$, as measured by cosine similarity. This intuition is derived from the specific definitions of the embedding space, the cost function, and the discrete measure in Lines 179-188.

The advantages of OT are two-fold: (1) OT allows efficient filtering of less useful exemplars due to its computationally efficiency and (2) OT operates entirely on exemplar samples and their embeddings without needing to query the target LLM.

If the reviewer is referring to using Best-of-N in place of OT in our EASE, it will incur much more API calls to the target LLM. Alternatively, completely removing OT also degrades performance, as suggested in the ablation study in Tab. 7 (NeuralUCB vs. EASE).

[Q2] Tables 7 and 8

Tab. 7 presents the validation performance and Tab. 8 presents the test performance. We add experiments for real tasks that involve open-ended sentence answers and present the results in Tab. A3 of rebuttal PDF. The results are consistent with the original paper in that using both NeuralUCB and OT together contribute to the success of EASE.

[Q3] Retrieval formulation

Query: Validation data exemplars $D_V$

Corpus: Training set exemplars in $D$

Relevance: An embedding model with a cosine-similarity metric

Procedure: For each validation data exemplar in $D_V$, we retrieve the most similar/relevant training set exemplars from $D$. Combine them to form a smaller set of exemplars (than $D$).

Therefore, we have retrieved a small subset of exemplars from $D$ that are similar (i.e., relevant) to the validation set. Then, we proceed with EASE using this reduced subset for efficiency. We will make this clearer in the revised paper.

We hope our clarifications above have helped to improve your opinion of our work.

References

(Hendrycks et al., 2021) Measuring mathematical problem solving with the math dataset. NeurIPS.

(Cobbe et al., 2021) Training verifiers to solve math word problems. arXiv.

(Ling et al., 2017) Program induction by rationale generation: Learning to solve and explain algebraic word problems. ACL.