Hyperband-based Bayesian Optimization for Black-box Prompt Selection

We thank the reviewer for their constructive review. We are pleased that the reviewer finds our method efficient, acknowledges the strength of our experimental results, and appreciates the clarity of the paper. Below, we respond to the concerns raised in the review.

1. The setup assumes that we have a large candidate instruction set and candidate example set, which already includes the high-quality choices we are looking for.

Our method is designed for the static black-box prompt selection setting, as discussed in Section 6, which is distinct from iterative prompt optimization frameworks. That said, while our experiments use a fixed candidate set to ensure fair comparison across methods, our approach does not require a fixed candidate set. It can be readily integrated into dynamic or iterative pipelines, where new prompts are generated - e.g., via evolutionary strategies (Fernando et al., 2024, ICML) - which update the candidate set.

2. This application scenario feels somewhat limited because if a human were writing prompts, the number of candidates wouldn't be that large.

In human-in-the-loop scenarios, combining a small number of candidate instructions with few-shot exemplars of different examples and permutations quickly leads to a combinatorially large search space. Therefore, moderately sized initial sets can produce rich candidate pools that benefit from principled selection.

3. The feature extractor is trained separately for the instruction set and example set. If we later realize that both sets are of poor quality and want to update them, then the previous training becomes wasted and difficult to adjust.

We acknowledge that changing the candidate set mid-optimization requires embedding new prompts. However, prior evaluations are not wasted. We retain all prior evaluations and use them to learn the relationship between latent prompt representation and performance. If newly added candidates are drawn from a different distribution and improve upon earlier ones, the GP will reflect this in its updated posterior enabling our method to adapt.

4. LLM calls used as cost metric

Overall wall clock time for the entire pipeline is less informative in the context of prompt selection, as prompt evaluations can be parallelized via asynchronous API calls. In the case of black-box LLMs accessed via APIs, cost is naturally tied to the actual monetary API cost. While token count could be used, API pricing distinguishes between input and output tokens (e.g., cost per 1000 input/output tokens), and these rates vary across LLMs. Aggregating results across different models using token-based cost introduces additional complexity. In contrast, the number of LLM calls offers a clean, model-agnostic measure of cost and it was positively noted by reviewers vVkq, rbkb and NvHi that our method reduces this cost.

5. Cost of feature extractor

We observe an overhead (on an M1 processor) of approximately 1-4 seconds per BO proposal, including training the deep kernel GP and selecting the next candidate prompt. This is similar to overhead induced by EASE or TRIPLE-GSE. We consider this overhead minimal in practice relative to the latency and monetary cost incurred by multiple LLM queries required for prompt evaluation. Moreover, the overhead of the encoder is small, since encoders have parameters in the range of millions.

6. Fixed 5-shot setting

We conducted preliminary investigations into the effect of the number of few-shot examples. Results indicated that increasing the number of examples improves the performance of prompts - similar to Wan et al. (2024, NeurIPS). EASE (Wu et al., 2024, NeurIPS), a competitor, uses $k=5$ in the experiments which we mimicked. From a methodological standpoint, we expect that increasing the number of few-shot examples further amplifies the benefits of our method. Competitors, in contrast, are not designed to disentangle the contributions of the instructions and few-shot exemplars.

7. Hyperparameters of the deep kernel

The latent dimensionality $d=10$ was motivated by widely observed limitations in the BO literature, where vanilla GPs tend to perform poorly in moderate to high-dimensional input spaces. Therefore, we selected $d=10$ as a conservative upper bound. With respect to the architecture and hyperparameters of the feature extractor, we acknowledge that these choices were not exhaustively tuned. However, we adopted widely accepted defaults: feedforward MLPs with ReLU activations, trained using AdamW with common hyperparameters.

We hope that our responses have adequately addressed the concerns raised by the reviewer, and we remain happy to clarify any follow-up questions.

We thank the reviewer for their constructive review. We are pleased that the reviewer recognizes our structure-aware deep kernel GP as a novel and meaningful contribution and that the integration with Hyperband is viewed as sound and well-justified. We also appreciate their acknowledgment of the comprehensiveness of our experiments and ablation studies. Below, we respond to weaknesses, feedback and questions raised by the reviewer:

1. Possibility of Overfitting in Deep Kernel GP

Indeed, prior work, such as Ober et al. (2021, UAI) has highlighted scenarios where deep kernel models may overfit. However, in our setting, this risk is mitigated. The encoder component (e.g., BERT) is a large, frozen, pre-trained language model. The only trainable component in our deep kernel GP consists of the comparably small feature extractor applied on top of the encoder, with approximately 100k trainable parameters. This is significantly smaller than typical deep kernel learning applications, where models with 5-10x more trainable parameters are used. Additionally, when optimizing the GP marginal likelihood, the log-determinant term in the objective acts as a form of complexity regularization, penalizing overly flexible kernel functions.

2. EI as acquisition function

We chose EI as our acquisition function since it is widely regarded as the de facto standard in BO. While UCB is a popular alternative, it requires the specification or tuning of a mean-variance trade-off parameter, which introduces an additional hyperparameter whose optimal value can be problem-dependent. The reviewer is correct in referring to Ament et al. (2024, NeurIPS), who discuss challenges associated with optimizing EI using gradient-based methods. These difficulties are primarily due to EI being flat in large regions of the input space and often numerically close to zero. This results in first- or second-order methods having serious challenges during optimization, which can be mitigated by optimizing the EI on log scale (and performing other numerical tricks for robust computation of the EI). However, these challenges do not arise in our setting. In particular, we do not rely on gradient-based optimization of the acquisition function. Instead, since our candidate set of prompts is discrete, we evaluate the EI exhaustively over all candidates and select the argmax directly. As such, issues of flatness, vanishing gradients, or numerical instability in gradient-based optimization are not applicable in our case.

3. Is the deep kernel GP trained only on the current task’s trials or pre-trained on offline data?

The deep kernel GP is trained entirely online, using only the observations collected during the current optimization run. We do not pre-train the deep kernel feature extractor on offline data before the task. That said, we agree that exploring pre-training strategies for the deep kernel - particularly leveraging ideas from transfer learning - represents a promising direction for future research!

4. Related Work

We thank the reviewer for pointing us to relevant work that focuses on obtaining meaningful representations of non-standard input to make BO applicable in more complex domains. We appreciate these suggestions and will ensure that these works are included and appropriately discussed in the camera-ready version of the paper. Concerning the directly related work of Falkner et al. (2018, ICML) on combining Hyperband with BO, we would like to clarify that this reference is already cited and discussed in Section 3.4 of our paper.

We thank the reviewer again for their feedback and we remain happy to clarify any follow-up questions.

We thank the reviewer for their constructive feedback and for recognizing the novelty and efficiency of our proposed method. While we appreciate the reviewer’s feedback, we note that some contributions of the paper may not have been fully recognized. Below, we respond to the two concerns raised in the review.

1. In line 51, the authors claim that EASE does not consider the joint optimization of instruction and exemplars, which is not true. Please check the EASE paper carefully again.

EASE can be used for joint instruction and few-shot exemplar selection by treating the prompt as a single block of text. We ran EASE in exactly this way, as intended by the authors. However, in contrast to our method, EASE does not make use of the structural information of the prompt being composed of different building blocks. Therefore, compared to our method, EASE is "not explicitly designed for the problem" which is what we stated in line 51. In our experiments, we observed that this structural unawareness leads to lower optimization performance compared to our approach. Still, to prevent misunderstanding, we will rewrite line 51 as: "EASE can be used for joint instruction and few-shot exemplar selection by treating the composed prompt as a block of text".

2. The method's performance depends on the choice of encoder model for embeddings, although the paper claims robustness to this choice. How does the choice of encoder model affect the performance of HbBoPs in practice?

To assess the impact of the encoder model on the performance of our method, we conducted an ablation study using three distinct encoder models: BERT, MPNet, and DistillRoBERTa. These experiments were carried out across all benchmark tasks and LLMs, and the results are reported in Section 5.2 of the paper. As shown in Table 3, the anytime validation and test performance remains stable across the different encoders, suggesting that our method is robust to the choice of encoder. We further confirm this observation with a statistical analysis provided in Appendix E.3. This evidence supports our claim that the overall effectiveness of our method is not sensitive to the particular encoder. We note that this robustness was also recognized as a positive aspect by reviewer Nvhi.

We hope that our responses above have adequately addressed the two concerns raised by the reviewer responsible for the comparably low rating.

The reviewer further had the following question:

Can the method be extended to handle other components of prompts, such as output guidance or formatting constraints?

HbBoPs is sufficiently flexible to be extended to handle additional prompt components, such as output guidance or formatting constraints. One natural extension would be to introduce categorical hyperparameters that encode the presence or type of such components - for example, binary indicators for the inclusion of output guidance or formatting constraints or categorical variables specifying formatting styles (e.g., none, JSON, XML, Markdown). This would expand the search space beyond instructions and few-shot exemplars along these dimensions. Incorporating these into our framework involves augmenting the input representation to the deep kernel GP. Specifically, the additional parameters, after suitable encoding, can be concatenated with the learned representations of the instructions and few-shot exemplars. For example, let $\mathbf{\eta} = \phi_{\left(\phi_{\mathrm{enc}}(i), \phi_{\mathrm{enc}}(e)\right)}$ be the $d$ dimensional output of our feature extractor operating on embeddings of instructions $i$ and few-shot exemplars $e$. We can then concatenate additional hyperparameters $\mathbf{\lambda}$ that indicate or encode the inclusion of output guidance or formatting constraints to obtain $[\mathbf{\eta}, \mathbf{\lambda}]$, which make up the features used within the GP. The surrogate model will then jointly learn to predict performance based on the prompt structure including these new components. We view this as a promising direction for future work.

Finally, we observed that the reviewer listed the design of our structural-aware deep kernel GP and the incorporation of Hyperband as a multi-fidelity scheduler under Theoretical Claims. We would like to clarify that our work does not propose novel theoretical contributions related to Hyperband or BO. As such, we believe that any critique in this regard is not applicable.

We thank the reviewer again and are happy to clarify any further questions.

We thank the reviewer for their constructive review. We appreciate the reviewer’s recognition of the extensiveness of our experiments, as well as their assessment that our claims are supported by clear and convincing empirical evidence. Moreover, we are happy to hear that they find the structural-aware deep kernel to be elegant. We are also pleased that the design and insightfulness of our ablation studies were positively noted. Lastly, we thank the reviewer for highlighting that our method is highly efficient in reducing the number of LLM calls required to identify a well-performing prompt - a practical aspect that we believe is crucial, yet was not explicitly recognized by all reviewers. Below, we respond to weaknesses, feedback and questions raised by the reviewer:

1. Limited instruction search space

While our experiments consider a fixed set of 5 instructions, the total prompt search space spans 250 candidates due to the combinatorial selection of instructions and few-shot exemplars. This results in a search space comparable in size to those used in prior work concerned with black-box prompt selection, such as Shi et al. (2024, NeurIPS).

From a methodological standpoint, our approach is expected to scale effectively with larger instruction spaces. This is due to the structural-aware surrogate model, which encodes instructions and exemplars separately. Thus, increasing the instruction set size would likely further amplify the benefits of our modeling choices rather than hinder them.

2. Interesting optional experiments on the most powerful LLMs, such as DeepSeeks R1

While applying our method to cutting-edge models such as DeepSeek R1 is indeed a promising direction for future work, we believe that our current experimental setup already provides strong evidence for the method’s applicability across diverse LLMs. In particular, we evaluate our approach on a representative and heterogeneous set of models, including Claude 3 Haiku, LLaMA 3 8B Instruct, and Mistral 7B Instruct. The consistent improvements achieved by our method across these models suggest that it is robust to model-specific variations and well-suited for deployment in real-world scenarios.

We thank the reviewer again for their feedback and we remain happy to clarify any follow-up questions.