Hyperband-based Bayesian Optimization for Black-box Prompt Selection
Authors: Lennart Schneider
Martin Wistuba
Aaron Klein
Jacek Golebiowski
Giovanni Zappella
Felice Antonio Merra
Venue: ICML 2025 poster (2025)
Keywords: Black-box prompt selection
large language models
Bayesian optimization
Hyperband
query efficiency
sample efficiency
structural-aware modeling
multi-fidelity
surrogate modeling
deep kernel
Gaussian Process
in-context learning
Primary area: deep_learning->large_language_models
TL;DR: A novel Hyperband-based Bayesian Optimization method that performs sample- and query-efficient structural-aware prompt selection for large language models, outperforming state-of-the-art methods across multiple benchmarks.

Abstract: Optimal prompt selection is crucial for maximizing large language model (LLM) performance on downstream tasks, especially in black-box settings where models are only accessible via APIs.
Black-box prompt selection is challenging due to potentially large, combinatorial search spaces, absence of gradient information, and high evaluation cost of prompts on a validation set.
We propose HbBoPs, a novel method that combines a structural-aware deep kernel Gaussian Process with Hyperband as a multi-fidelity scheduler to efficiently select prompts.
HbBoPs uses embeddings of instructions and few-shot exemplars, treating them as modular components within prompts.
This enhances the surrogate model's ability to predict which prompt to evaluate next in a sample-efficient manner.
Hyperband improves query-efficiency by adaptively allocating resources across different fidelity levels, reducing the number of validation instances required for evaluating prompts.
Extensive experiments across ten diverse benchmarks and three LLMs demonstrate that HbBoPs outperforms state-of-the-art methods in both performance and efficiency.

Hyperband-based Bayesian Optimization for Black-box Prompt Selection
Lennart Schneider! Martin 2istuba Aaron Klein Jacek Golebiowski Giovanni Zappella
Felice Antonio Merra 5
Abstract
tion (Hendrycks et al., 2021), and mathematical problem- solving (Hendrycks et al., 2021; Cobbe al., 2021). As LLMs are highly sensitive to their input (Zhou et al., 2023; Honovich et al., 2023; Lu et al., 2022; Liu et al., 2023; Ye et al., 2023; Wu et al., 2024), performance on these tasks relies on prompt engineering, where the input is formatted within a carefully designed prompt that may include an in- struction, a few-shol exemplar, and additional information.
Optimal prompt selection is crucial for maximiz- ing large language model (LLM) performance on downstream tasks, especially in black-box set- tings where models are only accessible via APIs. Black-box prompt selection is challenging due to potentially large, combinatorial search spaces, absence of gradient information, and high eval- uation cost of prompts on a validation set. We propose HbBoPs, a novel method that combines a structural-awaat deep kernel Gaussian Process with Hyperband multi-fidelity scheduler efficiently select prompts. HbBoPs uses em- heddings of instructions and few-shot exemplars, treating them as modular components within prompts. This enhances the surrogate model's s ability to predict which prompt to evaluate next in a sample-efficient manner. Hyperband im- proves query-efficiency by adaptively allocating resources across different fidelity levels, reducing the number of validation instances required for evaluating prompts. Extensive experiments across ten diverse benchmarks and three LLMs demon- strate that НbBоPs outperforms statc-of-the methods in both performance and efficiency.
The goal of static black-box prompt optimization and se- lection (Sun et al., 2022b; Chen et al., 2024; Lin al., 2024; Wu et al., 2024; Shi et al., 2024) is construct identify a single prompt for a black-box LLM that, in expec- tation, performs well across all instances of a downstream task. This process involves evaluating different prompts on a validation set and using derivative-free techniques to guide optimization or selection. The static black-box setting allows for offiine optimization, with the resulting optimal prompt being used for the downstream task.
While much research has focused on automatically generat- ing new prompts (Sun et al., 2022b; Xu et al., 2022; Zhou et al., 2023; Chen et al., 2024; Fernando et al., 2024; Lin et al., 2024), there is growing interest in efficiently selecting prompts from a predefined pool of candidates (Shi et al., 2024). This is because many prompt optimization tech- niques involve generating a large candidate pool priori before identifying the best prompt (Xu et al., 2022; Zhou et al., 2023; Fernando et al., 2024; Prasad et al., 2023). Moreover, recent empirical findings indicate that few-shot exemplars often contribute more strongly to prompt perfor- mance than the instruction of a prompt itself, with the best results typically achieved through the optimal selection of both components (Wan et al., 2024).
1. Introduction
In recent years, pre-trained auto-regressive large language models (LLMs) have demonstrated remarkable capabilities in addressing a wide range of machine learning tasks in- volving natural language (Brown et al., 2020; Liu et al., 2023), such as Q&A (Joshi et al., 2017; Clark et al., 2018), text summarization (Koupaee & Wang, 2018), text genera-
The task of black-box prompt selection is challenging. First, the search space can be extensive, as instructions and few- shot exemplars form a combinatorial set of candidates. Sec- ond, black-box L.MSs make impossible to directly opti- mize based on gradient information. Third, evaluating a prompt is time-consuming and costly, as each evaluation in- volves querying the LLM on multiple validation instances of task. This calls for the development of selection methods that can efficiently explore the space of candidate prompts while keeping the total number of LLM calls low.
Work done during an internship at Amazon Web Services, Berlin, Germany. "Amazon Web Services, Berlin, Germany. ASL University of Leipzig. Germany; work done while Amazon. *distil labs, Berlin, Germany: work done while at Amazon. CCognism, Remote, Italy; work done while at Amazon. Correspondence to: Lennart Schneider <lennart.sche @ web.de>.
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

syggerband-bssee Bayesian Optimization for Black-box Prompt Selection
Existing methods for prompt selection in this setting in- clude MIPROV2 (Opsahl-Ong al., 2024), EASE (Wu et al., 2024), TRIPLE-SHE and TRIPLE GSE (Shi et al., 2024). We identify the following limitations among these approaches: (1) Except for MIPROv2, these methods are not explicitly designed to address the problem of jointly selecting instructions and few-shot exemplars. Specifi- cally, EASE primarily focuses on exemplar selection, while TRIPLE-SH and TRIPLE-GSE focus on instruction se- lection. Although EASE can be applied to joint selection by treating the entire prompt as an unstructured block of text, it does not exploit the compositional structure of prompts. (2) No method is both sample-efficiens (allowing for evaluating fewer prompts by relying on a surrogate model) and query- efficient (reducing the total number of LLM calls by not evaluating prompts on all available validation instances).
A prompt p E P is instantiated by combining it with given task input query x X' for which the LLM,, h (P x X) + y, h(p(( + g. produces an output ø E V. We will use (a(r) to denote h([p,=]] as a shorthand.
We make no assumptions regarding the nature of the LLM and treat it as a black-box. The LLM returns output given imput without any additional information, i.e., no access to model parameters, gradients, or token probabilities.
Having access to validation set {(ri, Di) K= evaluating prompt is performed by comparing the ground truth output yi to the output d. = (z4) generated by the LLM based on a pointwise loss function I: y x y - IR, (y. 0) + Iy. D). This loss function quantifies how close the output generated by the LLM is to the ground truth. For example, loss function based on the widely used exact match (Chang et al.. 2024) scoring function is given by:
In this work, we propose HbBoPs (Hyperband-bassee based Bayesian optimization for black-box Prompt selection) ad- dressing these limitations. Our main contributions are the following: (I) We introduce a structural-aware deep ker- nel Gaussian Process (GP) that learns a low-dimensional prompt representation from separate embeddings of instruc- tions and few-shot exemplars in an end-to-end fashion to predict prompt performance. (2) We adopt Hyperband (Li et al., 2018) as a mulri-fidelity scheduler for prompt selection that governs the number of validation instances prompts are evaluated on. (3) We introduce a novel method, HbBoPs, that relies on our structural-awe aware deep kernel GP to make a Bayesian Optimization (BO) proposal within Hyperband and result is both sample- and query-efficient. (4) We compare HbBoPs against four baselines and four state-of- the-art methods across ten benchmarks and three LLMs, demonstrating that HbBoPs performs best in identifying a well-performing prompt after a given budget of total LLM calls but also exhibits strongest anytime performance during the selection process. (5) We perform an ablation study of the components of HbBoPs s gaining insight into their inner workings and further demonstrate its robustness to the choice of the encoder model used to obtain embeddings.
1(y. 1) =
if 9
otherwise.
Our task is identify a single prompt p E P that is optimal with respect to the loss in expectation:
arg min B(z.y) My, (x)]]. PCP
(2)
Here, the expectation is taken over all input-output instances (x, v). In practice, however, Equation (2) can only be ap- proximated based on the validation instances available:
1
Phyylidd
f(p)
hx
Tiyalid
We refer to this setting as the static setting, as we are search- ing offline for single optimal prompt on the target down- stream task. Note that due to the non-deterministic nature of LLMs (depending on temperature), f itself can in general only be observed with noise.
We will denote by
2. Problem Statement
V v= f(p) + E (0
(4)
Let I = (i1,..., in) denote a finite set of instructions (task descriptions) and E em, finite set of few-shot exemplars. Note that by exemplar we refer to an ordered tuple of a given number of ouput-output examples of a task. Let P = I x & be the set of prompts that are generated by combining each i E I with each E E.
the observed validation error of the LLM configured to use prompt ' f is black-box as the LLM is a black-box and no analytic description or gradient information is available.
The core challenge of static black-box prompt selection is balancing exploration (searching the prompt space P) and efficiency (minimizing costly LLM evaluations). Our goal is to identify the best prompt using as few LLM calls for evaluation as possible.
Instructions can be generated either manually by experts or automatically by L.LM-based methods, e.g., Automatic Prompt Engineering (APE; Zhou et al. 2023). Few-shot exemplars can be generated by selecting different input- output instances from a training set of the task.
We model the observation noise homoscedastic Gaussian for analytical convenience.
2

---

Hyperband-base -based Bayesian Optimization for Black-box Prompt Selection
3. Method
In short, this can be written as
We want to learn a surrogate model of the black-box func- tion f in Equation (3) that predicts the validation error of prompts on a downstream task based on observed data col- lected during optimization. This surrogate is used to predict the validation error of the unevaluated prompts during the optimization process. We first describe how GPs can serve as surrogate models in black-box prompt selection (Sec- tion 3.1). but highlight the limitations of vanilla GPs on raw, high-dimensional prompt embeddings. To address this, we introduce structural-awaad deep kernel GP (Section 3.2) that relies on structural information of prompts via separate embeddings of their building blocks. We then adopt Hy- perband (Li et al., 2018) for query-efficient multi aulti-fidelity prompt selection (Section 3.3) and integrate our structural- aware deep kernel GP via BO proposal, which results in our final HbBoPs algorithm (Section 3.4).
v
Kr K. ~ N (( ml m(z)),
1),
[.
K K+t,
where K, = (ZZ22/0) + o²1, K.
k(Z, Z, 10), and
K.. = iZ. Z. are the kemee matrices.
The posterior predictive distribution under the (zero mean) GP is obtained as
F Z, V. Z.] = KI(KK) cov [f. |2 Z.] = K., - (K,,,
(5)
where common choices for the kernel function & are given by the squared exponential kernel or variations of the Matérn kemel (see, e.g., Williams & Rasmussen, 2006, Chapter 4).
At this point, we could proceed and train a vanilla GP as outlined above on the d-dimensional space of embedded prompts. However, as stated in many previous works on BO (Kandasamy et al., 2015; Wang et al., 2016; Gardner et al., 2017; Eriksson et al., 2019; Eriksson & Jankowiak, 2021), GPs struggle with high-dimensional input such as that found in our design data Dr, e.g., the dimensionality of BERT's (Devlin et al., 2019) [CLS] token embedding is al- ready 768. In general, dimensionality reduction techniques such as principal component analysis (PCA) or random projections could be used. However, such techniques are repre-
3.1. Gaussian Process as Surrogate Model
To learn a surrogate model, we collect, at each optimization step I, a set of design data D.- == {(P): my)]i=r where each tuple consists of prompt p E P and its corresponding val- idation error Vy. as defined in Equation (4), recorded at the j-th previous step. This design data captures the history of prompts evaluated and their observed performance through- out the sequential optimization process. To learn a model that maps prompts to their validation errors, we embed each prompt into a d-dimensional numeric space, making use of pre-trained language encoders. Let enc: P - Rd , + z be the encoding function. We then augment the design data, D.- = {(pj.z), Zj "=) where z, is the embedding of prompt Pj. Since we are concerned with black-box prompt selection, it is natural to use embeddings as feature repre- sentations of prompts. Notably, recent work (Tang et al., 2024) has shown that (LLM) embeddings can in general serve as effective features for high- digenniimesional regression tasks, even in domains where the input data is not textual.
unsupervised and will not yield a lower-dimension sentation that is aligned with the downstream performance of prompts (see also Figure 3 in Appendix A for an illustra- tion). Additionally, using a single embedding of the whole prompt treated as a block of text ignores that the prompt is composed of different building blocks with distinct struc- tural information. Below, we present our solution.
3.2. Structural-aware Deep Kernel
To learn a lower-dimensional representation of the embed- ded prompts aligned with the downstream task, we pro- pose to use a deep kernel (Wilson et al., 2016) within the GP. We design feature extractor, & : Rd TRP, p < d to learn flexible kernel transformation function k(o(z, w), o(z', w)))), where 0 and w are the parameters of the kernel and respectively the extractor.
We want to use GP surrogate model since it allows for flexible probabilistic modeling of black-box functions by re- turning a point estimate and well-calibrated uncertainty esti- mates in the form of a Gaussian posterior predictive distribu- tion (Williams & Rasmussen, 2006). In the following, we as- sume GP prior over f in the d-dimensional space of embed- ded prompts. fz) ~ GP,m, k): f ~ (m,(Z), kZ, Z)0)). where is the prior mean function, usually set to zero, le is the covariance function depending on kernel parameters 0, and Z is a matrix of prompt embeddings.
Given that prompts consist of two distinct components (in- structions and few-shot exemplars), we hypothesize that embedding these components separately can improve the deep kernel GP's (DK-GP) ability to use both structural and semantic differences effectively. Instructions typically ex- hibit consistent patterns across prompts, whereas few-shot exemplars are more variable due to diverse input-output pairs and flexible ordering. To address this, we propose learning a structural-aware latent representation of prompts. Our approach involves embedding the instructions E
Given the design data D. and new prompts P. with their embeddings Z.,, the function f, is modeled as a random vari- able that jointly Gaussian distributed with all previously observed validation errors v (Ul,..., v.).
3

---

Flyperband-basee Bayesian Optimization for Black-box Prompt Selection
and few-shot exemplars E & separately. Each component embedding is processed through distinct feed-forward neu- ral networks, each consisting of two fully connected layers with ReLU activations, as defined below:
of calls for the remaining prompts in the next stage, until a single prompt remains.
This strategy is affected by the "budget vs, number of config- urations" dilemma (Li et al., 2018), since, at the beginning of the algorithm, it is not clear if we should evaluate many (by default all) prompts on few instances (good exploration but noisy performance estimates) or few prompts on many instances (less exploration but accurate performance esti- mates). When many prompts need to be evaluated with a limited total budget, SH's initial budget is low, which risks discarding prompt based on noisy performance estimation. HB in contrast hedges against a poor choice of the number of starting prompts and their budget by repeatedly running SH in different brackets with different numbers of starting prompts and starting budgets. This results in HB being ro- bust under various scenarios without knowing the optimal resource a allocation, making it ideal for prompt selection.
(enc() Lin (d, 64) + Re O- + Lin (64, 32) + ReLU ()
After processing the instructions and exemplars inddpen- dently, we concatenate their outputs and input the combined representation into another ferd-forward neural network to learn a joint latent representation:
( (Paatt)) Lin (32 2, 32) + ReLU () + Lin (32, 10)
During training the GP, we obtain both the optimal kernel parameters and the parameters of the neural network fea- ture extractor é by optimizing the log marginal likelihood criterion (up to constants):
To tailor HB to prompt selection, we make the following design decisions (for an ablation study, see Appendix E): (1) We extend previous evaluations when advancing stages within a bracket, ensuring validation instances of higher stages subsume those of lower stages, and (2) return the prompt with the lowest validation error among those evalu- ated on the entire validation set.
0, w= = arg max- -V (K, (O) -v - log (K, w)l (6)
0,w
An additional advantage of using deep kernel GP is its ability to model non-stationary functions, as the feature ex- tractor learns input-dependent transformations that allow the surrogate to capture varying levels of smoothness across the input space, which standard stationary kernels in vanilla GPs cannot accomplish (Li et al., 2024). Before illustrating how we use our structural-aware DK-GP during optimiza- tion to achieve sample-efficiency via BO proposal, we explain how we ensure query -feyyeeffic via Hyperband.
Finally, we combine HB with our structural-aware DK-GP by employing a sequential BO proposal mechanism for candidate prompts in each bracket, which we outline next.
3.4. HbBoPs
HbBoPs combines HB with our structural-aware DK-GP. While the vanilla HB algorithm for prompt selection sam- ples prompts uniformly at random, HbBoPs replaces the random proposal mechanism of HB with a sequential BO proposal (highlighted in gray in Algorithm 1). This is sim- ilar to the approach proposed by Falkner et al. (2018) for hyperparameter optimization. During the execution of HB, HbBoPs s trains the GP on a subset of the design data Drjo for a given fidelity-level b. We use the highest fidelity b for which "enough" observations are available. This design decision stems from the observation that validation errors are estimated more accurately with more instances (see Ap- pendices B and C). Importantly, we train the GP entirely online during the selection process and are not relying on a pre-trained surrogate model.
3.3. Hyperband for Multi- Fulti-Fidelity Scheduling
To improve query-efficiency identified as one of the key limitations of existing works, we want to terminate the eval- uation of poor-performing prompts early, saving cost during the evaluation process. Similarly to TRIPLE (Shi et al., 2024), we model the number of validation instances prompts evaluated on fidelity parameter. Full-fidelity meth- ods evaluate prompts on all validation instances, while multi- fidelity methods adaptively schedule evaluations on varying numbers of instances. TRIPLE implements Successive Halving (SH; Karnin et al. 2013) as a multi-fidelity sched- uler. In contrast, we use Hyperband (HB; Li et al. 2018) as it will generally evaluate fewer prompts and hedges against a poorly configured SH as explained below.
A After training the GP on Drjp, we select the next candidate prompt Pi+1 by maximizing the Expected Improvement (EI; Kushner 1964; Mockus et al. 1978; Jones et al. 1998) acquisition function:
Given a total budget of B LLM calls to evaluate prompts on validation instances, SH allocates budget of b = B/((P] log, (IPI)) to each prompt (see details in Ap- pendix C). After having evaluated the prompts on b vali- dation instances, the lower half of bad performing prompts discarded, and the process repeats, doubling the number
(pI(p)Dev) = E
- f(z)), 0.0
(7)
Pi+1 = arg max (p(j))) pEP
4

---

sapperband-basce Bayesian Optimization for Black-box Prompt Selection
Algorithm 1 HbBoPs
4.2. Methods
input Avalid, Imin (lower limit to evalidation asstances), 17 (nalving parametes)
We compare HbBoPs s against full-fidelity and multi-fidelity methods described in Table 1. Additional details on the methods reported in Section 6 and Appendix D. RS is simple random search. All methods that rely on embeddings of prompts use BERT's [CLS] token embedding to ensure fair comparison. All full-fidelll -idelity BO methods (vanilla BO, HDBO, BOPCA) use an ARD Matérn 5/2 kernel and Expected Improvement as acquisition function and normalize inputs to the unit eube and standardize outputs have zero mean and unit variance. HD3O is simple but well pell-performing high- high-dimensional BO algorithm using adjusted priors on GP kernel and likelihood parameters, as described in Hvarfner et al. (2024). BOPCA uses a ten component PCA inspired by Zhang et al. (2024). We run MIPROV2, NUCB (Zhou et al., 2020) as used by EASE (v = 0.1), TRIPLE-SH and TRIPLE-GSE as implemented in their publicty available code bases. All full-fidelity methods use the same initial de- sign of ten prompts sampled uniformly at random. HbБoPs uses an ARD Matérn 5/2 kernel, normalizes inputs to the unit cube and standardizes outputs. We always train the DK-GP on the highest fidelity level for which at least four observations are available. To optimize the log marginal likelihood in Equation (6), we use Adam (Loshchilov Hutter, 2019) with learning rate 0.01, maximum number of epochs = 3000, and early termination with a patience = 10. Within the HB schedule, we use a lower limit on the number of validation instances bmin 10 and halving parameter = 2.0.
Rvalid/ /mia
Smax = 1log, (r)]
B- = (8max + 1yvalddd
for $ E { mmax Smax
1,...,0) 0} do
n nevaid (++1)
b R
P (). V 0
for E (0,. , do
p = get pro__pr
e get waliivaatooeeerrrrreeeoo b))
P Pt- PU (p), Vu (v)
end for
P
= top_k(P, V, [n/nl)
for E [L.....s] sf do
n; inn
4. = bnj
V {get_ seet_validation_eee Settaatiiooeroo(pppppp bi) :p E P}
P = top Vo,, (m//nl)
end for end for output Prompt with the lowest validation error evaluated on the whole validation set
In words, given the incumbent (the best-performing prompt evaluated at the highest fidelity level so far) and its vali- dation error umin,d at fidelity level b, the EI quantifies the expected improvement of candidate prompt over the in- cumbent (considering only actual improvement due to the max operator), based on the GP's posterior predictive dis- tribution (Equation (5)). Since our search space is given by a finite set of candidate prompts, we can evaluate the EI exhaustively for all candidate prompts.
4.3. Experimental Protocol
For each task, we generate a search space P of candidate prompts by combining five task-specific instructions with 50 few-shot exemplars. Instructions are generated using APE's forward mode (Zhou et al., 2023), where Claude 3 Sonnet (Anthropic, 2024) generates instructions based ten input- output samples from each task's training set. For exemplars, we sample 25 sets of five input-output instances from the training set of each task, then permute each set twice to create 50 exemplar tuples, allowing assessment of example ordering effects. We fix the five-shot setting throughout our experiments to ensure consistency with prior work (Wu et al., 2024). The final [P] 250 prompts are formed by the Cartesian product of instructions and exemplars.
4. Experimental Setup
4.1. Benchmark Tasks
We benchmark HbBoPs on ten tasks commonly used for LLM evaluation (Zhou et al., 2023; Lin et al., 2024; Chen et al., 2024; Wu et al., 2024; Shi et al., 2024). A12's 's Reason- ing Challenge (ARC) (Clark et al., 2018): multiple-choice Q&A problems; Grade School Math 8K (Cobbe et al., 2021): math problems taking between two and eight steps to solve; Eight Tasks from the BBII subset of the BIG-bench and instruction induction benchmarks (Srivastava et al., 2023; Honovich et al., 2023) used in Zhou et al. (2023); Wu et al. (2024); Shi et al. (2024): antonyms, larger animal, negation, second word letter, sentiment, object counting, orthogra- phy starts with, and word unscrambling. Task statistics are reported in Table 5 in Appendix D.
For LLMs, we use Claude 3 Haiku (Anthropic, 2024), LLAMA3 8B Instruct (Llama Team, Al @ Meta, 2024), and Mistral 7B Instruct (Jiang et al., 2023).
For each benchmark scenario (a given task and LLM), we run each method for a total budget of 25 full-fidelity evalua- tions (i.c., being allowed many LLM calls as 25 prompts evaluated on all validation instances require for given task) to mimic a constricon scenario. We use the number
5

---

Flyperband-basee Bayesian Optimization for Black-box Prompt Selection
Table 1. Overview of baselines, competitors and our HbHoPs in the static black-box prompt selection setting.
Method
Fidelity
Efficiency
Surrogate Model
Bandit
Prompt Representation
Level
Algorithm
sample
query
Full
P cne(p) enc (p)
Vanilla BO
Full
vanilla
IIBO
Full
GP (Hvarfner et al., 2024)
BOPCA
Full
/
vanilla GP
PCA(cno(p)) (Zhang et al., 2024)
EASE (Wu et al., 2024)
Full
V
NN TPE
NUCB
ene(p) ID, IDe
MTPROv2 (Opsahl-Ong et al., 2024)
Full
V
TRIFLE-SE (Shi et al., 2024)
Multi
SH
P cnd(p)
TRIPLE-GSE (Shi et al., 2024)
Multi
LM/GLM
GSE
RIBBPPs (ours)
Multi
structura--wware DK-GP
HB
ene(i), ene(e)
LLM calls as our cost metric, rather than actual monetary cost, since LLM calls are directly interpretable and model- agnostic measure of cost that allows for aggregating over different benchmark scenarios. We repeat each method run 30 times on each benchmark scenario. We evaluate prompts using the loss function described in Equation (1) which is based on the exact match scoring function.
Table 2. Median relative validation and test improvement of HbBoPs over TRIPLE-SS across ten benchmarks per LLM at different fractions of total LLM calls. IQR in parentheses.
Fraction of Total LLM Calls
0.25
0.50
1.00
Claude 3 Haiku
Valid
0.121 (0.145)
0.059 (0.093)
0.018 (0.066)
Test
0.066 (0.105)
0.027 (0.045)
-0.006 (0.035)
Valid
0,120 (0,100)
0.042 (0.086)
0.001 (0.010)
LLAMA3 Instruct
Test
0.036 (0.088)
0.010 (0.036)
0.000 (0.024)
5. Results
Valid
0.068 (0.079)
0,036 (0.036)
0.003 (0.044)
Mistral7B Instruct
Teat 0.039 (0.022)
0.016 (0.033)
-0.001 (0.047)
We report the validation and test errors computed for the best prompt identified by each method given specific budget. For instance, given GSM8k with a validation set of 1319 instances, a budget of 0.25 means that we report the results of the methods after performing [0.25 25 1311] 8244 LLM calls. Therefore, full-fidelity methods always start after having executed fraction of 1/25 total LLM calls.
in-class full-fidelity counterpart, i.e., HDBO (0. 185), they on average have identified prompts that yield error values higher than the ones obtained for HbBoPs's prompts.
Looking at the anytime performance with more lim- ited budget, c.g., a fraction of 0.25 LLM calls, we can confirm HbBoPs's improvements over the baselines. In- deed, HbBoPs s on average outperforms HDBO, the best full- fidelity method, by approximately 35% and TRIPLE-SH, the best multi-fidelity method, by 24%. For additional sta- tistical analyses, we refer Appendix E.
5.1. Analysis of Overall Performance
We start by analyzing the overall performance of the meth- ods averaged across all benchmark tasks and LLMs. To allow for averaging results, we normalize validation and test errors for each benchmark scenario by the performance of the worst and best prompt. Figure 1 visualizes the re- sults. We observe that НbВоPs outperforms all full-fidelity and multi muntii-iidelity methods, particularly terms of anytime performance on both the validation and test set.
5.2. Analysis of the Performance for each LLM
As shown in Section 5.1, TRIPLE- SH emerges as the strongest competitor. To assess whether HbBoPs's im- provements over TRIPLE-SE are consistent across dif- ferent LLMs, we present in Table 2 the median relative improvement over the ten benchmark tasks for each LLM.
Beginning with an analysis of test error at full budget (i.e.,
fraction of LLM calls equal to 1.0), we can see that our НbВоPs on average outperforms all full-fidelity and multi-fidelity approaches with an average normalized test error of 0.1 In detail, we observe that all full-fidelity methods surpass the RS bascline (0.214) with the follow- ing errors: Vanilla BO (0.211), MIPROv2 (0.198), EASE (0.195), BOPCA (0.192), and HDBO (0.185). However, they all have higher enror values than HbBoPs s (50) Addition- ally, HbBoPs also outperforms all multi-fidelity methods. Although both TRIPLE-CSE (0.158) and TRIP LE-PLE (0.159) exhibit superior performance compared to their best-
The table reveals that HbBoPs consistently outperforms TRIPLE-SH in terms of both anytime validation and test error. For instance, when using Claude 3 Haiku, the average test error is reduced by a median factor of 0.066 and 0.027 at 0.25 and 0.50 of the total budget, respectively. While we further observe positive improvements over TRIPLE-SH on the validation set with a full budget, these gains are less pronounced on the test set. One possible reason for this discrepancy is that both methods, when given a sufficient budget, successfully identify prompts that have low or opti- mal validation error. However, optimal validation error does
6

---

Hyperband-bane based Bayesian Optimization for Black-box Prompt Selection
Poaa Nor mallad Toxk EootErer of Mollaaan Bost Pronss
Averaged Benchmark Scenarios iTasks Models)
Averaged Benchmark Scenarias (Tasks and Models)
Mean Nermalzc sacio Bust
pluen 2004
Matted
1098
60
Metted
5000
Pori Aepaaiiing as 2014
Minoye Mapuin ung ae 201e
3x
10:1
2x
0.0
0.2
0.6
0.5
0.0
0.2
04
2.8
1.
Traction offitel LL Call 11.0 25 tu fiddellly Frompe Eowiaatoned
Trast on of TOOAELLN Cate (1.5 fal-fow Prompt Dosluetond)
(a) Validation
(b) Test
Figure 1. Normalized error (log scale) of the best prompt per method, averaged over benchmarks. Lower is better. Ribbons represent SE,
DK-GP)) in full-fidelity setting improves vanilla BO by 11% and 38% at 0.5 and 1.0 budget with respect to the average normalized validation error. This highlights the importance of handling the high-dimensional embedded space properly. The structural-aware deep kernel (BoPs s DK-GP)) further enhances per- formance by 9% and 13% 0.5 and 1.0 budget, demonstrat- ing the value of directly incorporating structural information into the GP which answers (RQ1). Note that the structural- aware DK-GP improves over HDBO by 19% and 8% with respect to final average normalized validation and test error.
Table Normalized validation and test error of HbBoPs with different encoders at different fractions of total LLM calls averaged over all 30 henchmarks. SE in parentheses.
Fraction of Total LLM Calls
0.25
0.50
1.00
Valid
0:081
(0.004)
0.048 (0.003)
0.029 (0.002)
(structural-awa
BERT
Test
0.190 (0.006)
0.170 (0.006)
0.150 (0.005)
Valid
0:083 (0.004)
0.049 (0.003)
0.031 (0.002)
MPNet
Test
0.193 (0.006)
0.173 (0.006)
0.158 (0.006)
Valid
0 (0.003)
0.045 (0.002)
0.026 (0.002)
DistilRRBERRT
Test
0.185 (0.006)
0.166 (0.006) 0.150 (0.005)
The integration of HB for multi-fidelity scheduling (HB using random proposal mechanism) provides orthogonal boosts to both anytime and final performance. We observe improvements of 47% and 11% at 0.5 and 1.0 budget over the full-fidelity BoPs estructural-awaae DK-GP) answering (RQ2).
not necessarily guarantee optimal test error. We provide fur- ther analysis of the generalization gap between validation and test performance that is influenced by the size of the validation set in Appendix B.
5.3. Ablation Study
Our complete HbBoPs further increases performance, achieving a 21% improvement over HB at 0.5 budget and 31 % 1.0 budget, answering (RQ3). Compared to our start- ing point of vanilla BO, HbBoPs demonstrates substantial 66% improvement at 0.5 budget and 67% at 1.0 budget. For additional statistical analyses, we refer to Appendix F.
To better understand the contributions of the individual com- ponents of HbRoPs, we conduct comprehensive ablation study. Our ablation focuses on four key aspects: the use of a GP with deep kernel (DK-GP), the incorporation of a structural-aware DK-GP, the integration of HB for multi- fidelity scheduling, and the final HbBoPs. We aim to an- swer the following main research questions: (RQ1) Does structural-awar DK-GP improve over -tu-structural- aware DK-GP and vanilla GP? (RQ2) Does multi-fidelity scheduling with HB improve over full-fidelity methods? (RQ3) Does combining our structural-awwe aware DK-GP with HB improve over HB with a random proposal?
5.4. Analysis of Varying the Encoder
As HbBoPs relies embeddings of prompts, we conduct a sensitivity analysis to evaluate the effect of different encoder models on the performance of HoBoPs. While our primary results were obtained using BERT's (Devlin et al., 2019) [CLS] token embedding, we extend our analysis to include two more encoder models that are MPNet (Song et al., 2020) and Bostil (Liu et al., 2019). For each encoder model, rerun the entire set of benchmarks.
Figure 2 presents the average anytime normalized validation and test errors of the best prompt found by systematically removing specific components of our HbBoPs such that we can quantify their importance and answer above research questions. We focus on the validation error as shown in Fig- ure 2a to describe results, as improvement of the validation error is a direct consequence of the change of components.
We report in Table 3 the average normalized validation and test error for each encoder when used within HbBoPs for different fractions of total LLM calls over all 30 benchmark scenarios. Results show that HbRoPs s maintains consistent validation and test error across all encoder models, indicat-
First, we observe that using a DK-GP on prompts embedded as a block of text (BoPs s (non struucuural cetttuuralwwwarr l-aware
7

---

Hyperband-base based Bayesian Optimization for Black-box Prompt Selection
Poaa Nor mallad Tox Erie of Malliaan Bost Pranss
Nermaozc sotio Eroo of Bust Bostharres
Averaged Benchmark Scenarios iTasks Models)
Averaged Benchmark Scenarfas (Tasks and Models)
Hethos
Heihed
our cruburtbuan ot-an
3x
20-1
2x
0.0
0.2
0.6
0.6
0.0
0.2
04
2.8
1.3
Traction of offttel LL Caln 11.0 25 tu fiddellly Frompe Eowiaatone)
Trast on of TOOKELLN Cate (1.5- (1DD 25 fal-fow Prompt Easluetond)
(a) Validation
(b) Test
Figure 2. Normalized error (log scale) of the best prompt per HbBoPs ablation variant, RS, and vanilla BO, averaged over benchmarks. Lower is better. Ribbons represent SE.
ing robustness to the choice of encoder. This is expected, as none were specifically fine-tuned for predicting prompt per- formance. HbBoPs's 's effectiveness stems from its ability to learn mapping from prompts to performance through the structuralawware DK-GP, provided the embeddings capture meaningful distinctions between prompts.
MIPROv2 (Opsahl-Ong et al., 2024) is DSPy's (Khattab et al., 2024) state-of-the-art teleprompter for joint instruc- tion and few-shot exemplar selection. It searches over fi- nite set of candidate prompts by combining instructions with few-shot exemplars (which DSPy first constructs automati- cally). The method is a variant of BO using a -rresstructred Parzen Estimator (TPE; Bergstra et al. 201 1) based on the categorical indices of instructions and exemplars (ID, and ID.) that compose a prompt. A downside is that learning a surrogate model based on indices does not use any semantic information of prompts, which may result in suboptimal pre- dictive performance. Moreover, MIPROv2 does not directly address query-efficiency. While DSPy can be configured to use a smaller random subset of the validation set to eval- uate prompts, this risks suboptimal selection due to noisy performance estimates (see also Appendix B).
6. Related Work
Automating Prompt Engineering. Recent work has been concerned with the general topic of automating prompt en- gineering. This work can be classified into prompt optimiza- tion, i.e., automating the creation of prompts (Prasad et al., 2023; Sun et al.. 2022a; Zhou et al., 2023; Xu et al., 2022: Diao et al., 2023; Chen et al., 2024; Lin et al., 2024; Fer-
nando et al., 2024; Pryzant et al., 2023; Guo et al., 2024; Pan et al., 2024; Schnabel & Neville, 2024; Shen et al., 2023; Hu et al., 2024), and prompt selection, i.e., finding the best prompt within a finite candidate set (Wu et al., 2024; Shi et al., 2024; Opsahl-Ong et al., 2024; Do et al., 2024).
EASE proposed by Wu et al. (2024) mainly focuses on few- shot exemplar selection. It uses NeuralUCB (NUCB; Zhou et al. 2020) with embeddings of prompts blocks of text as features, allowing for sequential evaluation of promising prompts based on the UCB criteria. EASE's main contri- bution is to make the combinatorial problem of selecting examples to build the few-shot exemplar from an extensive training set computationally feasible. It prunes the candidate space using an optimal transport inspired heuristic before applying UCB. EASE is affected by query-inefiin -nefy-inefficiencyy since it evaluates prompts on all validation instances (or random subset, again risking suboptimal selection).
Another dimension to categorize the related literature is given by the white-box vs. black-box setting. The white-box setting assumes access to the LLM, so that gradient- gradient-based methods for prompt optimization or selection are applicable (Shin et al., 2020). The black-box setting assumes no access to the LLM which only returns output given input (Sun et al., 2022b; Diao et al., 2023).
Finally, another differentiation is given by the static vs. dynamic setting. The goal of the static setting (Wu et al., 2024; Shi et al., 2024; Khattab et al., 2024) is to obtain a single prompt offline that in expectation performs well for all instances during test time. In contrast, the goal of the dynamic setting (Zhang et al., 2023; Do et al., 2024; Luo et al., 2024) is to select prompt for each test instance (Rubin et al., 2022) in an online fashion.
TRIPLE proposed by Shi et al. (2024) is a class of query- efficient algorithms for static black-box prompt selection us- ing multi-armed bandit approach. It makes use of Succes- sive Halving (Karnin et al., 2013) or Generalized Successive Elimination (Azizi al., 2022) to accelerate prompt evalua- tion by discarding poor- noor-performing prompts early, reducing the need to evaluate all prompts on all validation instances. However, TRIPLE-SE SH is sensitive to the initial evaluation budget and may prematurely discard promising prompts due to noisy performance estimates. TRIPLE-GSE tries to mitigate this by (non-linear) modeling of expected prompt
Static blx Prompt Selection. Our work falls into the category of static black-box box prompt selection. We sum- marize existing works below.
8

---

Flyperband-basee Bayesian Optimization for Black-box Prompt Selection
performance using embeddings of prompts as blocks of text projected to lower-dimensional space. While this approach introduces flexibility, the Generalized Successive Elimina- tion algorithm has been formally analyzed only in the gen- eralized linear setting (A (Azizi et al., 2022). Moreover, both TRIPLE-SE and TRIPLE- GSE begin by evaluating all prompts, whereas our HbBoPs s employs a sample-efficient BO proposal to select candidate prompts for evaluation.
Future work could extend HbBoPs s to multiple objectives. Selecting more examples include in a prompt may en- hance performance but also increases response latency. Bal- ancing the number and composition of examples in few- shot exemplar introduces a trade-off between performance and efficiency, giving rise to a multi-objective optimization problem.
Impact Statement
7. Conclusion
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
We introduced HbBoPs, a method for static black-box prompt selection in which prompts are composed of in- structions and few-shot exemplars. HbBoPs s employs a structural-aware deep kernel Gaussian Process to model the downstream performance of prompts based on separate embeddings of instructions and exemplars. This enables the identification of promising, unevaluated prompts dur- ing the selection process, making HbBoPs s highly sample- efficient. Furthermore, HoBoPs integrates Hyperband as a multi-fidelity scheduler that governs the number of valida- tion instances used for prompt evaluation, ensuring query- efficiency. In extensive experiments, we have demonstrated that HbBoPs s improves upon baselines and state-of-the-art competitors in the limited budget regime while showing strong performance at any stage of the selection process.
References
Anthropic. Claude model card, 2024. URL https: 7 ccbabfoo33800011b6613887778/8// rd [1_claude_20 pdf.
/ www.:ccc...nttrrii.ccoc. com wttp://cccccccoccee.eeceeee dewba 9b01clbb
Azizi, M. J., Kveton, B., and Ghavamzadeh, M. Fixed- budget best-arm identification in structured bandits. In de Raedt, L. (ed.), Proceedings of the Thirty- Fiirty-First Inter- national Joint Conference on Artificial Intelligence, pp. 2022.
While НbBoPs s demonstrates strong performance, some limitations remain. Our method depends on embeddings from pre- pre-trained encoders. Although we have demonstrated that HbBoPs is largely robust to the concrete choice of en- coder model, obtaining embeddings induces some minor computational overhead. Additionally, our analysis focused on prompts composed of instructions and few-shot exem- plars. While these components are highly relevant in prac- tice, prompts may also include additional elements such as output guidance, formatting constraints, or other structural cues, which remain unexplored in this work. Nevertheless, the use of deep kernel Gaussian Process as a surrogate model makes our framework, in principle, flexible enough to incorporate such additional prompt parameters by, for ex- ample, including categorical variables for formatting styles (e.g., JSON, Markdown).
Balandat, M., Karrer, B., Jiang, D., Daulton, S., Letham, B., Wilson, A. G., and Bakshy, E. BoTorch: A frame- work for efficient monte-carlo Bayesian optimization. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M. F,, and Lin, H. (eds.), Advances in Neural Information Pro- cessing Systems, volume 33, pp. 21524-21538, 2020.
Bergstra, J., Bardenet, R., Bengio, Y., and Kégl, B. Al- gorithms for hyper-parameter optimization. In Shawe- Taylor, J., Zemel, R., Bartlett, P., Pereira, F,, and Wein- berger, K. Q. (eds.), Advances in Neural Information Processing Systems, volume 24, pp. 2546-2554, 2011.
Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert- Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D.,, Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Sutskever, I., and Amodei, D. Language models are few-shot learners. In Larochelle, H., Ran- zato, M., Hadsell, R., Balcan, M. F, and Lin, H. (eds.), Advances in Neural Information Processing Systems, vol- ume 33, pp. 1877-1901, 2020.
In our experiments, we evaluated HbooPs s in a static setting with a fixed set of candidate prompts generated a priori. This enabled fair comparisons across baselines and methods operating in the static black-box prompt selection setting. However, we emphasize that HbBoPs 3 can also be applied in more flexible prompt optimization settings where the candidate pool evolves over time. For example, it could be integrated with mutation-based prompt generation strategies (Fernando et al., 2024), where new prompts are generated iteratively, or with similar end-to-end prompt optimization pipelines (Pryzant et al., 2023; Yang et al., 2024).
Chang, Y., Wang, X., Wang, J., Wu, Y., Yang, L., Zhu, K., Chen, H., Yi, X., Wang, C., Wang, Y., Ye, W., Zhang, Y., Chang, Y., Yu, P. S., Yang, Q., and Xie, X. A survey on

---

Hlypebband-basee Bayesian Optimization for Black-box Prompt Selection
evaluation of large language models. ACM Transactions Intelligent Systems and Technology, 15(3):1-45, 2024.
and Krause, A. (eds.), Proceedings of the 35th Interna- tional Conference on Machine Learning, volume 80, pp. 1437-1446, 2018.
Chen, L.,, Chen, J., Goldstein, T., Huang, H., and Zhou, T. InstructZero: Efficient instruction optimization for black-box large language models. In Salakhutdinov, R., Kolter, Z., Heller, K., Weller, A., Oliver, N., Scarlett, J., and Berkenkamp, F. (eds.), Proceedings of the 41st International Conference on Machine Learning, volume 235. pp. 6503-6518, 2024.
Fernando, C., Banarse, D., Michalewski, H., Osindero, S., and Rocktäschel, T. Promptbreeder: Self-referential self- improvement via prompt evolution. In Salakhutdinov, R., Kolter, Z., Heller, K.. Weller, A., Oliver, N., Scarlett, J., and Berkenkamp, F. (eds.), Proceedings of the 41st International Conference on Machine Learning, volume 235, pp. 13481-13544, 2024.
Clark, P., Cowhey, I., Etzioni, O., Khot, T., Sabharwal, A., Schoenick, C., and Tafjord, O. Think you have solved question answering? Try ARC, the A12 Reasoning Chal- lenge, 2018. https / /tt//aaxvvvvv..////v///ee///a.va org/ abs/ 05457.
Gardner, J., Guo, C., Weinberger, K., Garnett, R., and Grosse, R. Discovering and exploiting additive struc- ture for Bayesian optimization. In Singh, A. and Zhu, J. (eds.). Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54, pp. 131 1311-1319, 2017.
Cobbe, K., Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, L.,, Plappert, M., Tworek, J., Hilton, J., Nakano, R., Hesse, C., and Schulman, J. Training verifiers to solve math word problems, 2021. URL https:tt///settt.. //arxiv. org/abs/222 /aa.///110 14168.
Gardner, J., Pleiss, G., Weinberger, K. Q., Bindel, D., and Wilson, A. G. GPyTorch: Blackbox matrix-matrix Gaus- sian Process inference with GPU acceleration. In Ben- gio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa- Bianchi, N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 31, pp. 7576- 7586. 2018
Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. BERT: Pre-training of deep bidirectional transformers for lan- guage understanding. In Burstein, J., Doran, C., and Solorio, T. (eds.), Proceedings of the 2019 Conference of the North American Chapter of the Association for Com- putational Linguistics: Human Language Technologies, Volume (Long and Short Papers), pp. 4171-418 2019.
Guo, Q., Wang. R., Guo, J., Li, B., Song, K., Tan, X., Liu, G., Bian, J., and Yang. Y. Connecting large language mod- els with evolutionary algorithms yields powerful prompt optimizers. In The Twelfth International Conference Learning Representations, 2024.
Diao, S., Huang, Z., Xu, R., Li, X., Lin, Y., Zhou, X., and Zhang, Black-box prompt learning for pre-trained language models. Transactions on Machine Learning Research, 2023.
Hendrycks, D., Burns, C., Basart, S., Zou, A., Mazeika, M., Song, D., and Steinhardt, J. Measuring massive multi- task language understanding. In The Ninth International Conference on Learning Representations, 2021.
Do, V.-T., Hoang, V.KK., Nguyen, D.-H., Sabahi, S., Yang. J., Hotta, H., Nguyen, M.-T,, and Le. H. Automatic prompt selection for large language models, 2024. URL httts://arxiv aarivv.vvvv org/ abs/ 4...0.4.00 02717.
Honovich, O., Shaham, U., Bowman, S. R., and Levy, O. Instruction induction: From few examples to natural lan- guage task descriptions. In 61st Annual Meeting of the Association for Computational Linguistics, ACI. 2023, pp. 1955-1952, 2023.
Eriksson, D. and Jankowiak, M. High-dimensione Bayesian optimization with sparse axis-alignns aligned subspaces. In de Campos, and Maathuis, M. H. (eds.), Proceed- ings of the Thirty-Sevent Conference on Uncertainty in Artificial Intelligence, volume 161, pp. 493-503, 2021.
Hu, W. Shu, Y., Yu, Z., Wu, Z., Lin, X., Dai, Z. Ng. S.-K.. and Low, B. K. H. Localized zeroth-order prompt opti- mization. In Globerson, A., Mackey, L., Belgrave, D., Fan, A., Paquet, U., Tomezak, J., and Zhang, C. (eds.), Advances in Neural Information Processing Systems, vol- ume 37, pp. 86309-86345, 2024.
Eriksson, D., Pearce, M., Gardner, J., Turner, R. D., and Poloczek, M. Scalable global optimization via local Bayesian optimization. In Wallach, H., Larochelle, H., Beygelzimer, A., d' d'Alché-Ba Aaché-BBcc F., Fox, E., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 32, 2019.
Hvarfner, C., Hellsten, E. O., and Nardi, L. Vanilla Bayesian optimization performs great in high dimensions. In Salakhutdinov, R., Kolter, Z., Heller, K., Weller, A., Oliver, N., Scarlett, J., and Berkenkamp. F. (eds.), Pro- ceedings of the 41st International Conference on Machine Learning, volume 235, pp. 20793-20811 2024.
Falkner, S., Klein, A., and Hutter, F. BOHB: Robust and efficient hyperparameter optimization at scale. In Dy,
10

---

Hyperband-basee Bayesian Optimization for Black-box Prompt Selection
Jamieson, K. and Talwalkar, A. Non-stochastic best identification and hyperparameter optimization. In Gret- ton, A. and Robert, C. C. (eds.), Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, volume 51, pp. 240-248, 2016.
Li, L.,, Jamieson, K., Rostamizadeh, A., Gonina, E., Ben- tzur, J., Hardt, M., Recht, B., and Talwalkar, A. A system for massively parallel hyperparameter tuning. In Dhillon, I., Papailiopoulos, D.. and Sze, V. (eds.), Proceedings of Machine Learning and Systems, volume 2, pp. 230-246, 2020.
Jiang, A. Q., Sablayrolles, A., Mensch, A., Bamford, C.,, Chaplot, D. S., de las Casas, D., Bressand, F., Lengyel, G., Lample, G., Saulnier, I.., Lavaud, I.. R., Lachaux, M.- A., Stock, P., Le Scao, T., Lavril, T., Wang, T., Lacroix, T., and El Sayed, W. Mistral 7B, 2023. URL https:
Li, Y. L., Rudner. T. G. J., and Wilson, A. G. A study of Bayesian neural network surrogates for Bayesian opti- mization. In The Twelfth International Conference on Learning Representations, 2024.
//arxiv. //arxiv.org/ abs/ / 221 0. 6625..
Lin, X., Wu, Z., Dai, Z., Hu, W., Shu, Y., Ng. S.-K., Jaillet, P., and Low, B. K. H. Use your INSTINCT: INSTruction optimization using Neural bandits Coupled with Trans- formers. In Salakhutdinov, R., Kolter, Z., Heller, K., Weller, A., Oliver, N., Scarlett, J., and Berkenkamp, F. (eds.). Proceedings of the 41st International Conference on Machine Learning, pp.
Jones, D. R., Schonlau, M., and Welch, J. Efficient global optimization of expensive black-box functions. Journal of Global Optimization, 13:455-492 1998.
Joshi, M., Choi, E., Weld, D., and Zettlemoyer, L. TriviaQA: A large scale distantly supervised challenge dataset for reading comprehension. In Barzilay, R. and Kan, M.-Y. (eds.), Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp. 1601-1611, 2017.
2024.
Liu, P., Yuan, W., Fu, J., Jiang, Z., Hayashi, H., and Neubig, G. Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing. ACM Computing Surveys, 55(9):1-35, 2023.
Kandasamy, K., Schneider, J., and Poczos, B. High di- mensional Bayesian optimisation and bandits via additive models. In Bach, F. and Blei, D. (eds.), Proceedings of the 32nd International Conference on Machine Learning, volume 37, pp. 295-304, 2015.
Liu, Y., Ott, M., Goyal, N., Du, J., Joshi, M., Chen, D., Levy, O., Lewis, M., Zettlemoyer, L.,, and Stoyanov, V. RoBERTa: robustly optimized BERT pretraining ap- proach, 2019. URL Uttpttts: /ttpss///axxvv.e/a httstt/://aaiii.crr http://///axw..r/////////// 07.11692.
Karnin, Z., Koren, T., and Somekh, O. Almost optimal exploration in multi-armed bandits. In Dasgupta, S. and McAllester, D. (eds.), Proceedings of the 30th Interna- tional Conference on Machine Learning, volume 28, pp. 1238-1246, 2013.
Llama Team, Al @ Meta. The Llama 3 Herd of Models, 2024. URL http:////xxvv..o/aaabbee 1783.
Loshchilov, I. and Hutter, F. Decoupled weight decay regu- larization. In The Seventh International Conference on Learning Representations, 2019.
Khattab, O., Singhvi, A., Maheshwari, P., Zhang, Z., San- thanam, K., Vardhamanan, S., Haq, S., Sharma, A., Joshi, T. T., Moazam, H., Miller, H., Zaharia, M., and Potts, C. DSPy: Compiling declarative language model calls into self-improving pipelines. In The Twelfth International Conference on Learning Representations, 2024.
Lu, Y., Bartolo, M., Moore, A., Riedel, S., and Stenetorp. P. Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity. In Mure- san, S., Nakov, P., and Villavicencio, A. (eds.), Proceed- ings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pp. 8086-8099 2022.
Koupaee, M. and Wang, WikiHow: A large scale text summarization dataset, 2018. URL https: arxiv. brg/abs/188 09305.
Kushner, H. A new method of locating the maximum point of an arbitrary multipeak curve in the presence of noise. Journal of Basic Engineering. 86(1):97-106, 1964.
Luo, M., Xu, X., Liu, Y., Pasupat, P., and Kazemi, M. In- context learning with retrieved demonstrations for lan- guage models: survey. Transactions on Machine Learn- ing Research, 2024.
Li, L., Jamieson, K., DeSalvo, G., Rostamizadeh, A., and based approach
Talwalkar, A. Hyperband: A novel bandit-based to hyperparameter optimization. Journal of Machine Learning Research, 18(185):1552, 2018.
Mockus, J., Tiesis, V., and Zilinskas, A. The application of Bayesian methods for secking the extremum. Towards Global Optimization, 2(2):117-129, 1978.

---

Hlypebaand-base Bayesian Optimization for Black-box Prompt Selection
Opsahl-Ong, K., Ryan, M.J., Purtell, J., Broman, D., Potts, C., Zaharia, M., and Khattab, O. Optimizing instrue- tions and demonstrations for multi-stage language model programs. In Al-Onaizan, Y., Bansal, M., and Chen, Y.NN (eds.), Proceedings of the 2024 Conference on Em- pirical Methods in Natural Language Processing, pp. 9340-9366, 2024.
Shin, T., Razeghi, Y., Logan IV, R. L.,, Wallace, E., and Singh, S. AutoPrompt: Eliciting knowledge from lan- guage models with automatically generated prompts. In Webber, B., Cohn, T., He, Y., and Liu, Y. (eds.), Proceed- ings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 4222-4235, 2020.
Pan, R., Xing. S., Diao, S., Sun, W., Liu, X., Shum, K., Zhang, J., Pi, R., and Zhang, T. Plum: Prompt learn- ing using metaheuristics. In Ku, L.-W.nd Martins, A. and Srikumar, V. (eds.). Findings of the Association for Computational Linguistics: ACI. 2024, pp. 2177-2197, 2024.
Song, K., Tan, X., Qin, T., Lu, J., and Liu, T.-Y. MPNet: Masked and permuted pre-training for language under- standing. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M. E,, and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 16857- 16867. 2020.
Prasad, A., Hase, P., Zhou, X., and Bansal, M. GrIPS: Gradient-free, edit-based instruction search for prompt- ing large language models. In Vlachos, A. and Augen- stein, I. (eds.), Proceedings of the 17th Conference of the European Chapter of the Association for Computational Linguistics (EACL), pp. 3845-3864, 2023.
Srivastava, A., Rastogi, A., Rao, A., Shoeb, A. A. M., Abid, A., Fisch, A., Brown, A. R., Santoro, A., Gupta, A., Garriga-Alonso, A., Kluska, A., Lewkowycz, A., Agar- wal, A., Power, A.. Ray, A.. Warstadt, A., Kocurek, A. W., Safaya, A., Tazarv, A., Xiang, A., Parrish, A., Nie, A., Hussain, A., Askell, A., Dsouza, A., Slone, A., Rahane, A., Iyer, A. S., Andreassen, A. J., Madotto, A., Santilli, A., Stuhlmüller, A., Dai, M., La, A., Lampinen, A. K., Zou, A., Jiang, A., Chen, A., Vuong, A., Gupta, A., Got- tardi, A., Norelli, A., Venkatesh, A., Gholamidavoodi, A., Tabassum, A., Menezes, A., Kirubarajan, A., Mullokan- dov, A., Sabharwal, A., Herrick, A., Efrat, A., Erdem, A., Karakaş, A., Roberts, B. R., Loe, B. S., Zoph, B., Bojanowski, B., Özyurt, B., Hedayatnia, B., Neyshabur, B., Inden, B., Stein, B., Ekmekci, B., Lin, B. Y., Howald, B., Orinion, B., Diao, C., Dour, C., Stinson, C., Argueta, C., Ferri, C., Singh. C., Rathkopf. C., Meng, C., Baral, C., Wu, C., Callison- C., Waites, C., Voigt, C., Man- ning, C. D., Potts, C., Ramirez, C., Rivera, C. E., Siro, C., Raffel, C., Asheraft, C.,, Garbacea, C., Sileo, D., Gar- rette, D.,. Hendrycks, D., Kilman, D., Roth, D., Freeman, C. D., Khashabi, D., Levy, D., González, D. M., Per- szyk, D., Hernandez, D., Chen, D., Ippolito, D., Gilboa, D... Dohan, D.,, Drakard, D.,, Jurgens, D., Datta, D., Gan- guli, D., Emelin, D., Kleyko, D., Yuret, D., Chen, D., Tam, D.,, Hupkes, D.,, Misra, D., Buzan, D., Mollo, D. C., Yang, D., Lee, D.HH Schrader, D., Shutova, E., Cubuk, E. D., Segal, E., Hagerman, E., Barnes, E., Donoway, E., Pavlick, E., Rodolà, E., Lam, E., Chu, E., Tang. E., Erdem, E., Chang. E., Chi, E. A., Dyer, E.,, Jerzak, E., Kim, E., Manyasi, E. E.,, Zheltonozhskii, E., Xia, F., Siar, F, Martinez-Plumed, F,, Happé, F,, Chollet, F., Rong, F,, Mishra, G., Winata, G. I., de Melo, G., Kruszewski, G., Parascandolo. G., Mariani, G., Wang, G. X., Jaimovitch- Lopez, G., Betz, G., Gur-Ari, G., Galijasevic, H., Kim, H., Rashkin, H., Hajishirzi, H., Mehta, H., Bogar, H., Shevlin, H. F. A., Schuetze, H., Yakura, H., Zhang, H., Wong, H. M., Ng, I., Noble, I., Jumelet, J., Geissinger, J., Kernion, J., Hilton, J., Lee, J., Fisac. J. F., Simon, J. B., Koppel, J., Zheng, J., Zou, J., Kocon, J., Thompson, J.,
Pryzant, R., Iter, D., Li, J., Lee, Y., Zhu, C., and Zeng, M. Automatic prompt optimization with "gradient de- scent" and beam search. In Bouamor, H., Pino, J., and Bali, K. (eds.), Proceedings of the 2023 Conference Empirical Methods in Natural Language Processing, pp. 7957-7968, 2023.
Rubin, O., Herzig, J., and Berant, J. Learning to retrieve prompts for in-context learning. In Carpuat, M., de Mamn effe, M.-C., and Meza Ruiz, I. V. (eds.), Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT), pp. 2655-2671, 2022.
Schnabel, T. and Neville, J. Symbolic prompt program search: A structure-aware approach to efficient compile- time prompt optimization. In Al-Onaizan, Y., Bansal, M., and Chen, Y-N. (eds.), Findings of the Association for Computational Linguistics: EMNLP 2024, pp. 670-686, 2024.
Shen, M., Ghosh, S., Sattigeri, P., Das, S., Bu, Y., and Wor- nell, G. Reliable gradient-fred and likelihood-fre prompt tuning. In Vlachos, A. and Augenstein, I. (eds.), Findings of the Association for Computational Linguistics: EACL 2023, pp. 2416-2429, 2023.
Shi, C., Yang, K., Chen, Z., Li, J., Yang. J., and Shen, C. Efficient prompt optimization through the lens of best arm identification. In Globerson, A., Mackey, L., Belgrave, D., Fan, A., Paquet, U., Tomezak, J., and Zhang, C. (eds.), Advances in Neural Information Processing Systems, volume 37, pp. 99646 99646-996855 2024.
12

---

Hlyperband-basee Bayesian Optimization for Black-box Prompt Selection
Wingfield, J., Kaplan, J., Radom, J., Sohl-Dickstein, J., Phang. J., Wei, J., Yosinski, J., Novikova, J., Bosscher, J., Marsh, J., Kim, J., Taal, J., Engel, J., Alabi, J., Xu, J.. Song. J., Tang, J., Waweru, J., Burden, J., Miller, J., Balis, J. U., Batchelder, J., Berant, J., Frohberg, J., Rozen, J., Hernandez-Orallo, J., Boudeman, J., Guerr, J., Jones, J. Tenenbaum, J. B., Rule, S., Chua, J., Kanclerz, K., Livescu, K., Krauth, K.. Gopalakrishnan. K., Ignatyeva, K. Markert, K. Dhole, K., Gimpel, K., Omondi, K., Mathewson, K. W., Chiafullo, K., Shkaruta, K., Shridhar, K. McDonell, K., Richardson, K., Reynolds, I.., Gao, L., Zhang, L., Dugan, L., Qin, L., Contreras-Ochande L., Morency, L..P.. Moschella, L., Lam, L., Noble, L.,, Schmidt, L., He, L., Udiveros-Colón L.., Metz, L.., Senel, L. K., Bosma, M.. Sap, M., Hoeve, M. T., Farooqi, M., Faruqui, M. Mazeika, M., Baturan, M., Marelli, M., Maru, M., Sammirez-Quntanne M. J., Tolkiehn, M., Giu- lianelli, M., Lewis, M., Potthast, M., Leavitt, M. I.,, Ha- gen, M., Schubert, M., Baitemirova, M. O., Arnaud, M., McElrath, M., Yee, M. A., Cohen, M., Gu, M., Ivanitskiy, M.. Starritt, M., Strube, M., Swędrowski, M., Bevilac- qua, M., Yasunaga, M., Kale, M., Cain, M., Xu, M., Suzgun, M., Walker, M., Tiwari, M., Bansal, M., Amin- naseri, M., Geva, M., Gheini, M., T, M. V., Peng, N., Chi, N. Lee, N., Krakover, N. G.-A,, Cameron, N., Roberts, N., Doiron, N., Martinez, N., Nangia, N., Deckers, N., Muennighoff, N., Keskar, N. S., Iyer, N. S., Constant, N., Fiedel, N., Wen, N., Zhang, O., Agha, O.,, Elbagh- dadi, O., Levy, O.,, Evans, O., Casares, A. M., Doshi, P. Fung, P., Liang, P. P., Vicol, P., Alipoormolabushi, P., Liao, P., Liang, P., Chang, P. W., Eckersley, P., Htut, P. M., Hwang, P., Milkowski, P., Patil, P., Pezeshkpour, P., Oli, P.. Mei, Q. Lyu, Q. Chen, Q., Banjade. R., Rudolph, R. F., Gabriel, R., Habacker, R., Risco, R., Millière, R., Garg, R., Barnes, R., Saurous, R. A., Arakawa, R., Ray- maekers, R., Frank, R. Sikand, R., Novak, R., Sitelew, R., Bras, R. L.. Liu, R., Jacobs, R., Zhang, R., Salakhut- dinov, R., Chi, R. A., Lee, S. R., Stovall, R., Teehan R., Yang, R., Singh, S., Mohammad, S. M., Anand, S., Dillavou, S., Shleifer, S., Wiseman, S., Gruetter, S., Bow- man, S. R., Schoenholz, S. S., Han, S., Kwatra, S., Rous, S. A., Ghazarian, S., Ghosh, S., Casey, S., Bischoff, S., Gehrmann, S., Schuster, S., Sadeghi, S., Hamdan, S., Zhou, S., Srivastava, S.. Shi, S., Singh. S., Asaadi, S., Gu, S., Pachchigar, S., Toshniwal, S., Upadhyay, S., Debnath, S. S., Shakeri, S., Thormeyer, S., Melzi. S., Reddy, S., Makini, S. P., Lee, S.-H., Torene, S., Hatwar, S., Dehaene, S., Divic, S., Ermon, S., Biderman, S., Lin, S., Prasad, S., Piantadosi, S., Shieber, S., Misherghi, S., Kiritchenko, S., Mishra, S., Linzen, T., Schuster, T., Li, T., Yu, T., Ali, T., Hashimoto, T., Wu, T.-L., Deshordes, T., Rothschild, T., Phan, T., Wang, T., Nkinyili, T., Schick, T., Kornev, T., Tunduny, T., Gerstenberg, T., Chang, T., Neeraj. T. Khot, T., Shultz, T., Shaham, U., Misra, V.,
Demberg, V., Nyamai, V., Raunak, V., Ramasesh, V. V., vinay uday prabhu, Padmakumar, V., Srikumar, V. Fe- dus, W., Saunders, W. Zhang, W., Vossen, W., Ren, X., Tong, X., Zhao, X., Wu, X., Shen, X., Yaghoobzadeh, Y., Lakretz, Y., Song, Y., Bahri, Y., Choi, Y., Yang. Y., Hao, S., Chen, Y., Belinkov, Y., Hou, Y., Hou, Y., Bai, Y., Seid, Z., Zhao, Z., Wang, Z., Wang. Z. J., Wang, Z., and Wu, Z. Beyond the imitation game: Quantifying and extrapolat- ing the capabilities of language models. Transactions on Machine Learning Research, 2023.
Sun, T., He, Z., Qian, H., Zhou, Y., Huang, X., and Qiu, X. BBTv2: Towards gradient-free free future with large language models. In Goldberg, Y., Kozareva, Z., and Zhang, Y. (eds.), Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. 2022a.
Sun, T., Shao, Y., Qian, H., Huang, X., and Qiu, X. Black- box tuning for manduage-model-ss-- service.. In Chaud- huri, K., Jegelka, S., Song, L.., Szepesvari, C.,, Niu, G., and Sabato, S. (eds.), Proceedings of the 39th Interna- tional Conference on Machine Learning, volume 162. pp. 20841-20855, 2022b.
Tang, E.,, Yang. B., and Song, X. Understanding LLM embeddings for regression. Transactions Machine Learning Research, 2024.
van der Maaten, L. and Hinton, G. Visualizing data using t-SNE. Journal of Machine Learning Research, 9(6)): 2579-2605, 2008.
Wan, X., Sun, R., Nakhost, H., and An k, S. O. Teach better or show smarter? On instructions and exemplars in automatic prompt optimization. In Globerson, A., Mackey, L., Belgrave, D., Fan, A., Paquet, U., Tomozak, J., and Zhang, C. (eds.), Advances in Neural Information Processing Systems, volume 37, pp. 58 58174-58244, 2024.
Wang, Z., Hutter, F., Zoghi. M., Matheson, D., and de Fre- itas. N. Bayesian optimization in a billion dimensions via random embeddings. Journal of Artificial Intelligence Research, 55(1):361-387, 2016.
Williams, C. K. I. and Rasmussen, C. E. Gaussian Processes for Machine Learning. MIT press Cambridge, MA, 2 edition, 2006.
Wilson, A. G., Hu, Z., Salakhutdinov, R., and Xing, E. P. Deep kernel learning. In Gretton, A. and Robert, C. C. (eds.), Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, volume 51, pp. 370-378, 2016
Wu, Z., Lin, X., Dai, Z., Hu, W., Shu, Y. Ng. S.-K., Jaillet, P., and Low, B. K. H. Prompt optimization with EASE? ef- ficient ordering- aware automated selection of exemplars.
13

---

Hyperband-basee Bayesian Optimization for Black-box Prompt Selection
In Globerson, A., Mackey, L., Belgrave, D., Fan, A., Pa- quet, U., Tomezak, J., and Zhang, C. (eds.), Advances in Neural Information Processing Systems, volume 37, pp. 122706-122768 2024.
Xu, H., Chen, Y., Du, Y., Shao, N., Yanggang, W., Li, H., and Yang, Z. GPS: Genetic prompt search for efficient few-shot learning. In Goldberg, Y., Kozareva, Z., and Zhang, Y. (eds.), Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 8162-811 8171, 2022.
Yang. C., Wang. X., Lu, Y., Liu, H., Le, Q. V., Zhou, D., and Chen, X. Large language models as optimizers. In The Twelfth International Conference on Learning Repre- sentations, 2024.
Ye. J., Wu, Z., Feng, J., Yu, T., and Kong, L. Compo- sitional exemplars for in-context learning. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), Proceedings of the 40th Interna- tional Conference on Machine Learning, volume 202, pp. 09818-39333, 2023.
Zhang, H., He, J., Righter, R., and Zheng, Z. Language model prompt selection via simulation optimization, 2024. URL https:://// / /arxiv..vvvvv.////////a///aaaavv org/ abs 2404. 08164.
Zhang, T., Wang, X., Zhou, D., Schuurmans, D., and Gon- zalez, J. E. TEMPERA: Test-time prompt editing via reinforcement learning. In The Eleventh International Conference on Learning Representations, 2023.
Zhou, D., Li, L., and Gu, Q. Neural contextual bandits with (CB-based exploration. In III, H. D. and Singh, A. (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119, pp. 1 11592-11502, 2020.
Zhou, Y., Muresanu, A. I., Han, Z., Paster, K., Pitis, S., Chan, H., and Ba, J. Large language models are human- level prompt engineers. In The Eleventh International Conference on Learning Representations, 2023.
14

---

Hyperband-basee Bayesian Optimization for Black-box Prompt Selection
A. On the Latent Space of the Structural-Aware Deep Kernel Gaussian Process
As described in Section 3.1, unsupervised dimensionality reduction techniques such as PCA or random projections will not result in lower-dimensional latent representation of prompt embeddings that is aligned with the downstream performance of prompts. To illustrate this, we perform the following experiment: We collect the validation error of 250 prompts on GSM8K (according to the splits described in Table 5) using LLAMA3 8B Instruct LLM. We embed each prompt using the [CLS] token embedding of BERT (d = 768). We then split the prompts p.....: P250 and their corresponding validation errors Vi...., 2250 in a train (80%) and test set (20%). Using the train split, we perform a PCA and retain 10 principal components as features. Moreover, we train our structural-aware DK-GP introduced in Section 3.2 on the training split and extract the 10 latent features from the output of the feature extractor (( We visualize the raw 768 dimensional embedding features of prompts, the 10 dimensional PCA features and the 10 dimensional deep kernel features for the training split using a two component t-SNE (van der Maaten & Hinton, 2008) in the top of Figure 3. The x-- and y-axis represent the two t-SNE components, whereas color indicates the validation error of prompts (lighter color indicates better performance). We can see that for both the raw embedding features and the PCA features, it is difficult to visually discern any meaningful clusters or structure how closeness in feature space relates to closeness in performance space. For the deep kernel features, however, we can see that the feature space is well aligned with the performance space (well- werl--peroomiin prompts being closer together with a continuous transition into poorer performing prompts) of course, this is on the training split on which the GP has been trained on, and therefore these results are not surprising. However, when looking at the test split (that was neither used to perform the PCA nor to train the GP) in the bottom row of Figure 3, we can see that similar conclusions as for the train split hold: The latent representation the feature extractor of the deep kernel has learned during training does generalize to the test split, and it has effectively learned a low-dimensional embedding of prompts aligned with the downstream task.
Raw Embedding Features- Train Split
PCA Features Train Split
Deep Kernel Latent Features Train Split
20
15-
10
1:NE2
1:SkVE
10-
10
15-
-20
-15
-10
15
-10
10
-20
-10
10
1-SNE
1-SNE
t-SNE
1
Raw Embedding Features Test Split
PCA Features Test Split
Deep Kernel Latent Features Test Split
15
10
10
2
:SME 2
U:SME2 2
-10
-4-
-15
15
-10
-5
0
10
13
-10
-3
10
-20 -10
0
10
20
1.SNE
b.SNE
Figure 3. Visualization of the 768 dimensional BERT [CLS] token embeddings of prompts via a two component t-SNE, Left: Raw, unprocessed features. Middle: Features of 10 component PCA solution. Right: Latent features (10 dimensional) from the feature extractor of our structural-aware DK-GP. Top row: Train split. Bottom row: Test split. Color indicates the performance of prompts for LLAMA3 8B Instruct on GSMSK.
15

---

Hyperband-basee Bayesian Optimization for Black-box Prompt Selection
B. On the Generalization from Validation to Test
When performing black-box prompt selection, we evaluate prompts on a validation set and iteratively improve over the current best prompt (the incumbent), trying to identify a better one. While progress on the validation set is expected (i.e., if we perform full-fidelity evaluations using the same validation instances for each prompt, the validation error of the incumbent will be monotonically decreasing as optimization progresses), it must not necessarily be the case that also improve performance on held-out test set of instances, i.e., the prompt identified as being validation optimal might not necessarily be optimal on the test set.
In this section, we provide additional insights regarding generalization gaps from validation to test performance. Recall that existing methods for black-box prompt selection (e.g., EASE and MIPROv2) are by design not query-efficient but evaluate all prompts on all validation instances or random subset (e.g. Wu et al. 2024 used sub-sampled validation sets with as few as 20 instances). We now empirically demonstrate that using small random subsets during optimization is not sensible choice, because this will result in increased variance of the estimate of the validation error, which prevents from making correct decisions on the validation set. This can result in generalization issues when moving from the validation set to the test set.
We perform the following experiment: We collect the validation and test error (according to the splits described in Table 5) of 250 prompts on the GSM8K task using LLAMA3 8B Instruct as L.M.. We vary the number of validation instances used to evaluate the performance of prompts via bootstrapping, using k = 10, 50, 100, 500 instead of the original Vivaldd 1319 validation instances. Note that compute the test error, always use the full test set. In Figure 4, we provide scatter plots of the validation and test errors of the prompts with mean validation errors obtained via bootstrapping using k = 10, 50, 100, 500 validation instances vs. validation errors obtained on the full validation set of 1319 instances. We perform 1000 bootstrap replicates.
0.7-
0.7-
0.7
9.7-
0.7
Tes Enerr
0.6
0.6
0.5
0.5
04-
0.4
04 Beostropped
0.8
0.2 Brostrapped
0.6
0.2 Boostrapped
0.6
0.8
0.4
mppped
(a) l- 10.
(b) A 50.
(c) l 100.
(d) l: 500.
(c) Full validation set.
Figure 4. Scatter plots of the validation and test errors of 250 prompts evaluated with LLAMA3 8B Instruct on GSM8K using differently sized (k- 10, 50, 100, 500) bootstrap samples of validation instances (a) to (d) or the full validation set (c).
We can observe that if we use too few validation instances (k = 10 but also k = 50 and k = 100 to some extent) even if we select the validation optimal prompt, its test error can be far from optimal, because noise dominates the estimate of the validation error.
In Figure 5, we provide box plots of the bootstrapped variance estimates of the mean validation error over prompts when using smaller validation sets. As expected, the variance of the mean validation error can be substantial when using few validation instances. Note that the bootstrap results align with theoretical expectations under the assumption that the point- wise loss (based on exact match) is a binary random variable following a Bernoulli distribution with success probability p (corresponding to a loss of O). In this case, the average validation error over nealid instances follows a Binomial distribution, and the variance of the estimated validation error is given by p(1-p)/nvvtie For example, if prompt has a true "success probability" of = 0.5, then using Rvalid = 10 validation instances yields an expected variance of 0.5*/10 = 0.025.
This has serious practical implications, depending on the variation in the performance of prompts on downstream task. If the true performance of many prompts is similar, cannot tell them apart based on their estimated validation error, noise dominates the signal when using too few validation instances. Moreover, for benchmarking methods for black-box prompt selection this is highly relevant as when using too few validation instances, we cannot determine whether a generalization gap from the validation set to the test set results solely from noisy performance estimates or from internal method mechanisms (such as the optimal transport inspired heuristic employed by EASE to only consider examples that are similar to the validation set) which may further result in overfitting to the validation set.
16

---

Hyperband-basee based Bayesian Optimization for Black-box Prompt Selection
Booktrane Weraete of Nean WMldatoon Eree
0.023
0.315
0.010
0.005
0.002
10
50
103
500
No. Velidation Instances
Figure 5. Box plots of the bootstrapped variance estimates of the mean validation error of 250 prompts evaluated with LLAMA3 8B Instruct on GSM8K varying the number of validation instances used to estimate the mean validation error.
The empirical results we have presented here further provide justification for using a multi- multi-fidelity scheduler over the validation instances during prompt selection, such as Hyperband. Poor-perfone poor-performing prompts can be differentiated using few validation instances, however, pelfforrrnmmn prompts need to be evaluated on larger sets so that one can effectively tell their validation errors apart.
C. Multi-Fidelity over Validation Instances
In this section, we discuss how one can define a multi-fidelity schedule for prompt selection, in which the fidelity parameter the number of validation instances. Let Dvalid = {( y/) ) denote the validation set containing Tivald input-output instances in natural language on which the LLM h, configured to use a given prompt p E P is evaluated. Recall our goal of identifying the optimal prompt: arg min B(x,y)~P., [[ h (x))]. Here, the expectation is taken over all input output instances from data- generating distribution Pzy and l is the pointwise loss function used to compare the LLM's output (x) to the ground truth y. We want to identify the best performing prompt while minimizing the number of LLM calls for evaluation, given the significant costs in both time, but especially query expenses associated with LLM black-box APIs.
In practice, we can only approximate this expectation by the full-fidelity evaluation on the whole validation set given by Roaali Iyye, (x:)))
The idea of multi-fidelity techniques is speed up and reduce the cost of the evaluation of prompts by using fewer validation instances during evaluation. Let V {l,.... ) denote the index set corresponding to the indices of validation instances. A simple way to reduce cost of evaluation is to use a random subset, S V of validation instances:
Ss Eies h (x:)). This was for example done in the evaluation protocol of the benchmark study in Wu et al. (2024), However, it comes with the following downsides: (1) It is a priori not clear how many instances are needed to obtain an accurate estimate of the validation error of prompts as this depends on the concrete LLM, downstream task, and variation of the true performance over prompts. (2) Using fixed gub-))sample is inefficient because all prompts are evaluated on the same number of validation instances. However, poor-performing prompts can be identified using few validation instances, whereas well-performing prompts should be evaluated on many validation instances differentiate between them and not risk suboptimal selection.
Shi et al. (2024) made the connection between multi-fidelity prompt selection and best arm identification from the multi- armed bandit literature. In this setting, "pulling an arm" refers to evaluating a prompt on a validation instance. The goal is to identify the best arm within limited budget of evaluations. A well-known algorithm from the bandit literature is given by Successive Halving (SH, Karnin al. 2013; Jamieson & Talwalkar 2016). In our setting of prompt selection, the idea of SH to efficiintly identify the best performing prompt (arm) under given budget constraint of total LLM calls (pulls). Given total budget B of LLM calls and n = |P] prompts, SH starts by allocating a budget of b = B B/(n log2(n)) LLM calls to each prompt. After having evaluated each prompt on à instances, the lower half of bad performing prompts are discarded and the process repeats, doubling the number of LLM calls for the remaining prompts in the next stage. This process in general repeats until a single prompt remains. SH can be employed in both a stochastic and non-stochastic setting. The stochastic setting (Karnin et al., 2013) is formally characterized by the following: (1) Losses are i.id. samples from a probability distribution. (2) Each arm has fixed expected loss Hpp (3) The goal is to identify the arm with the lowest expected loss.
17

---

saperband-basce Bayesian Optimization for Black-box Prompt Selection
Jamieson & Talwalkar (2016) introduced SH in the non-stochastic setting when applying it the problem of hyperparameter optimization, where the budget can, for example, be the size of the training used to train algorithm the number of epochs used to train neural network. This non-stochastic setting formally is characterized by the following: (1) Losses are real numbers chosen by an oblivious adversary. (2) Each arm has a limit Vp of its loss sequence as the number of evaluations go to infinity. (3) The goal to identify the arm with the lowest loss limit.
Within the non-stochastic setting, Li et al. (2018) introduced Hyperband (HB) although in general also applicable to the stochastic setting. Recall that SH requires the overall budget and the number of prompts n as input parameters. These determine the starting budget (number of validation instances) prompts are evaluated on. However, for given overall budget B it is priori not clear whether one should evaluate many prompts using average few validation instances (resulting in better exploration of the search space at the risk of noisy validation error estimates) whether one should consider a smaller number of prompts using on average more validation instances (focusing on fewer prompts but obtaining more accurate validation error estimates).
Our proposal to use HB as a multi-fidelity scheduler for prompt selection improves over SH by addressing this trade-off between the number of prompts to explore and the amount of resources to allocate to each configuration. It does so by running multiple SH brackets, each with a different initial number of prompts and initial per-prompt budget. This allows HB to efficiently explore the search space, quickly discarding poor prompts while allocating more resources promising ones, therefore hedging against poor choice of the number of prompts and per-prompt budget.
We present pseudocode for HB adapted to the problem of black-box prompt selection in Algorithm (as explained in Section 3.4, HbBoPs s replaces the random proposal mechanism of HB by a BO proposal) and in Table 4, we present an exemplary schedule describing how the number of prompts used in each stage of each bracket of the algorithm relates to the number of validation instances used evaluate the prompts. Regarding the output of the algorithm, we note that there is critical design decision: The vanilla HB (Li et al., 2018) algorithm would output the configuration with the smallest validation error observed so far. However, in the context of prompt selection, validation errors determined based on different numbers of validation instances varying between stages of brackets (fSmax Smax .. 0}). To allow for robust selection of the optimal prompt, we always return the prompt with the lowest validation error among all prompts that were evaluated on the full validation set?. This is crucial for robust performance of HB in the context of prompt selection, which we demonstrate in Appendix E.4.
Table 4, Exemplary HB schedule for black-box prompt selection assuming a minimum budget of bmin 10 validation instances, maximum number of Realid 80 validation instances being available in total, and a halving parameter of ry = 2.0.
Bracket (s)
Stage (i)
#Instances (b) #Prompts (n)
3
0
10
8
3
1
20
3
2
40
2
3
3
80
2
0
20
2
1
40
2
2
80
1
0
40
1
80
0 0
80
4
Our HB adapted to black-box prompt selection has three inputs: Rlyalid the total number of validation instances available (depending on the task), dmin a lower bound on the number of validation instances used for prompt evaluation, and 17 the halving parameter of the SH subroutine. HB makes use of three functions:
(1) get__ cet_prropt() returns a candidate prompt from the search space P. In vanilla HB, we would sample uniformly at random.
In our HbBoPs we obtain the next candidate prompt via BO proposal (Section 3.4).
(2) veeddaaiition error(p, 6i) evaluates prompt p using b, validation instances. We further discuss this below.
(3) top (P, V, [m//n]) reduces the n, prompts in the active set P by only keeping the [n./n] best performing ones.
"Or evaluated on the largest subset used so when assessing the anytime performance of the algorithm.
18

---

Hyperband-base -aasbe Bayesian Optimization for Black-box Prompt Selection
As mentioned above, there is another critical detail when adapting HB to the problem of prompt selection, selectin,,, which is concerned with the selection of validation instances for given stage of bracket but also when moving from given stage to the next stage within a bracket. In principle, the validation instances in prompt (sampled uniformly at random from the set of validation instances). However, to allow for a fairer comparison of the performance of prompts, we decided to use the same, fixed subset of validation instances for each prompt evaluated at a given stage of a bracket. This ensures that we perform a paired comparison of the performance of prompts when discarding the worst performing half. We ablate this design decision in Appendix E.4.
peplidattionerrrr/// b,) could be different for each
Moreover, when moving from one stage to another stage, there are two possibilities how to construct the subset of validation instances used in the next stage: (1) Simply draw sample. (2) Keep the already used validation instances of the previous stage and only sample the remaining number of additional validation instances needed to fill the current stage from the remaining yet not used validation instances. The second option is highly desirable to reduce the total number of LLM calls we cache the evaluation of prompts. The validity of this modeling choice naturally depends on the degree of stochasticity in the LLM's output for a given prompt-instanee pair, which in turn is influenced by the sampling temperature. However, if we assume reasonably deterministic outcomes, we can reduce the total number of L.LM calls used in HB drastically (i.e., roughly by a factor of 1)), In HbBoPs we cache the output for a given prompt and validation instance and reuse the already used validation instances of the previous stage and only sample the remaining needed validation instances. We ablate this design decision in Appendix E.4.
We want to note that HbBoPs employs a fully sequential HB schedule, i.e., prompts are proposed sequentially, and we evaluate brackets and their stages in their given order (e.g., as described in Table 4). While plenty possibilities exist to parallelize SH or HB in the context of hyperparameter optimization where evaluating a configuration involves a training step, we argue that in the context of prompt selection, there is little gain made by performing a batch proposal of prompts and evaluating batch-parallel (as in vanilla HB for hyperparameter optimization) or using asynchronous multi-fidelity schedulers (Li et al., 2020). This is because parallelization can be directly performed on the lowest level of evaluating a prompt on the validation set, i.e., in get_ validation -eriioop__rrrrpp_____ b,) by parallelizing LLM calls when evaluating prompt on the b, validation instances. As a final comment on overhead, note that it may initially seem that training the structural-aware DK-GP in each iteration of a BO proposal within HbBoPs s leads to computational costs that increase proportionally as optimization progresses. However, the GP is trained only on the subset of the highest fidelity design data for which enough observations are available. This approach not only ensures that the design data used to train the GP has accurately estimated validation errors but also keeps the subset size manageable, mitigating scaling issues of the GP even when HbBoPs is executed repeatedly.
D. Details on the Experimental Setup
D.1. Tasks
Table 5 reports characteristics on the benchmark tasks used in our experiments. For A12 ARC, we use the official train, validation and test splits from A12's Reasoning Challenge. However, during inspection we noticed that for some reason, A12's s Reasoning Challenge includes few instances with choices named "1", "2", "3", "4" instead of "A", "B", "C", "D" and few instances with five choices instead of four which we excluded from the splits for consistency. GSM8K officially only contains train and test split. We sampled 1319 instances from the train split uniformly at random create validation set of comparable size to the test set. For all other tasks from the BBII subset of the BIG-bench and instruction induction benchmarks, we use the splits as proposed by Wu et al. (2024). Unlike Wu et al. (2024), who used only 20 validation instances by further sub-sampling the validation splits, we retain larger validation splits to reduce noise and improve the reliability of performance estimates. For each task, the training split was used to generate instructions for the prompts via APE's (Zhou et al., 2023) forward mode and to select instances for few-shot exemplars. Instructions are generated using APE's forward mode, where Claude Sonnet (Anthropic, 2024), configured with temperature of 1.0 and default settings otherwise (as in the main paper for Claude 3 Haiku), produces 100 candidate instructions from ten input-output examples per task; these are then embedded using BERT's s [CLS] token representation, and five representative instructions are selected via 5-medoid clustering. The validation split was used during optimization and the test split was used to assess unbiased performance. We perform standard sanitization of LLM outputs to be able to employ the loss function in Equation (1) based on the exact match as a scoring function. For GSMSK, we determine the prediction for the exact match loss function by selecting the last number contained in the LLM's output. This approach aligns with the Cf Thought prompting and the typical output behavior of LLMs for this task.
19

---

Hlperbanddbasee Bayesian Optimization for Black-box Prompt Selection
Table 5. Characteristics of tasks used in the experiments.
Task
Setting
Parain
Avalid
Rttest
A12 ARC
multiple choice question answering
1094
291
1144
GSM8K
grade school math questions
6154
1319
1319
antonyms
find antonym of word
2073
519
100
larger animal
select larger of two animals
2422
606
100
negation
negate sentence
723
181
100
object counting
count number of objects
560
140
100
orthography starts with
output all words starting with a given letter
2400
600
100
second word letter sentiment word unscrambling
output the second letter of a word sentiment analysis of movie rating build a word from scrambled letters
2644
662
100
933
234
100
5627
1407
100
D.2. LLMS
We use Claude 3 Haiku (Anthropic, 2024), LLAMA3 8B Instruct (Llama Team, Al @ Meta, 2024), and Mistral 7B Instruct (Jiang et al., 2023) with default hyperparameters (Claude 3 Haiku: max tokens = 200, temperature = 0.5, top 1.0, 8B Instruct: max tokens = 512, temperature 0.3, top p = 0.9; Mistral 7B Instruct: max tokens 512, temperature 0.5, top p = 0.9, top k 50). For GSM8K we increase max tokens for all LLMs to 1024.
top k = 250; LLAMA3
D.3. Methods
We run all methods as described in Section All full-fidelity BO methods are implemented within BoTorch (Balandat et al., 2020). We include HDBO (Hvarfner et al., 2024) to have a simple yet well well-performing "high- "high-dimensional"" BO baseline. Hvarfner et al. (2024) recently challenged the general belief that vanilla BO does not perform well for high-dimensional functions by training GP via MAP with priors kernel and likelihood parameters adjusted reflect the dimensionality of the problem which resulted in strong BO performance in the official code base?, MIPROv2 as implemented in DSPy* and TRIPLE-SS and TRIPLE- as implemented in we noticed that Shi et al. (2024) did not provide detailed descriptions of
nigh-dimensional functions. We run EASE as implemented
the official code base Regarding the model used to predict expected prompt performance (in the main paper, they state that one can use a linear model or MLP). In their implementation, however, they use an ensemble of a Bayesian ridge regression model, a gradient boosting regression model, and an MLP where weights for the ensemble are determined based on each model's R performance on separate validation set. We did not change this modeling approach when running TRIPLE-GSE. We implement our НbBoPs in GPyTorch (Gardner et al., 2018) and run it as described in Section 4. Moreover, to hedge against poor model-based proposals, we perform random interleaving as described in Falkner et al. (2018) for each proposal with a probability of 0.1. Since a single SH or HB schedule may require less budget than the total pre-defined LLM call budget per task, we repeatedly run all methods that use SH or HB as multi-fidelity schedulers until their total LLM call usage reaches this pre-defined budget.
E. Additional Results
E.1. Main Results
Here, we provide additional analyses of the main results reported in Section 5. To test whether HbBoPs outperforms all other methods with respect to validation and test еттоr for different fractions of budget, we conduct linear mixed effects model analysis. We model the unaggregated performance as a function involving random intercepts for each benchmark scenario (benchmark task and LLM combination). This approach is sensible as each method has been run repeatedly on the
481 wtt.:///////eeeee///aaaaaaaooaaa
/tel hte.l/grropppp/mmpooooommeeeee/r vandit/conteetual/gee..p
/
20

---

Hyperband- -basd Bayesian Optimization for Black-box Prompt Selection
same benchmark scenario with different random seeds that affect, for example, initial designs. To test the global hypothesis that there is an effect of the method on performance, we test intercept model against model including effect of the factor method. If we reject the null hypothesis, we proceed with a Tukey post hoc test (corrected for multiple testing) to test each method against ssBoPs. We test at the conservative a = 0.01 level.
For the validation error at a fraction of 1.00, we reject the global null hypothesis of no effect of methods (x²(8) 672.95. < 1e-4). The pairwise results are:
RB vs. abBoPs, = = 18.52, < 1e-4
vanilla BC vs. HbltoPs, 15.40.p <. 1
HDRD v. WofooPs, 7.65,p p 16-4
ROPDA vs, libooPs, 9.95, In-4
RASE v. WafooPe, 17.29, p < In-4
HIPROv2 lifooPs 13.18, < 1e-4
TREPLR SE liRRoPs 1.87, 0.236
TRCELE-GSE vs. HbBoFs, 6.26. 1e-4
We conclude that HbBoPs outperforms all methods significantly with respect final performance, except for TRIPLE-SH. While the effect is positive, i.e., HbBoPs improves over TRIPLE-SH. it is not strong enough to be considered statistically significant at the a- 0.01 level. For brevity, we do not include results for fractions of 0.25 or 0.50 here, where we observed similar results but HbBoPs s more strongly outperforming the other methods.
Table 6. Normalized validation error of each methad on each benchmark for Claude Haiku. Averaged over repetitions. Standard errors in parentheses. For visual analysis, we highlight all methods that have mean error that less or equal to the mean error of the hest method plus two times its standard error.
Benchmark
ARC
GSMBK
astonyms
larger animal
nepition
object counting
orthugraphy starts with
secced word lotier
senciment
wonl inserambling
RS
0,053 (0.007)
0.067 (0.010)
0.018 (0.002)
0.011 (0.002)
0.000 (0.000)
0.093 (0.01
(0.055
0.076 (0.011)
0.021 (0.003)
0:085 (0.000)
vanilla BO
0,046 (0.907)
0.084 (0.010)
0.020 (0.002)
0.012 (0.002)
0,000 (0,000)
0,075 (0.010)
0,113 (0.005)
0,092 (0.011)
0.021 (0.004)
0,084 (0.009)
HDBO
0.139 (0.807)
0.050 (0.00))
0.014 (0.002)
0.004 (0.801)
0.000 (0.000)
0,840 (0.009)
0.022 (0.004)
0,029 (0.008)
0.014 (0.0L3)
(0.008)
BORCA
0.847 (0.008)
6.041 (6.007)
0.914 (0.002)
0,005 (0.001)
0.000 (1.000)
0.062 (0.011)
(0.00)
0.044 (0.010)
0.015 (0.003)
0.081 (0) (0.009)
EASE
(0.010)
0.063 (0.003)
0.024 (0.002)
(0.07)
0,000 (0.000)
3.099 (0.010)
0,059 (0.005)
0,070 (0.010)
0.027 (0.085)
0.103 (B.007)
MIPROv2
(0.908)
(0.004)
0.016 (0.001)
0,011 (0.002)
(0.000)
0.050 (0.009)
0.019
(0.009)
0.025 (0.003)
0:059 (0.007)
TRIPLE-SH
0,109 (0.014)
0,043 (0.008)
0,029 (0.0133
0.005 (0.002)
0.003 (0.002)
0,043 (8.010)
0,155 (0.006)
0.006 (0.002)
0.051 (0.007)
0.025 (0.096)
TRIPLE-GIE
0,175 (0.014)
0.002 (0.010)
0.031 (0.005)
0,021 (0.001)
0.000 (0.000)
0.087 (0.014)
0:349 (0.008)
1.007 (0.002)
0.060 (0.019)
0.016 (0.606)
RoBcPe
(6.005)
(0.002)
0.005 (0.001)
(0.000)
0.855 (6.011)
(0,0320
(0.002)
0.023 (0.003)
0.026
Table Normalized validation error each method on each benchmark for LLAMA3 8B Instruct. Averaged over repetitions. Standard errors in parentheses. For visual analysis, we highlight all methods that have mean error that is less or equal to the mean error of the best method plus two times its standard error.
Benehmark object counting
AIL ARC
GSMBK
antonyus
larger
negation
orthograply
sccoud word
unscrambling
RS
0J178 (0.010)
(0.066)
0.093 (0.010)
0.025 (0.004)
(0.001)
0.156 (0.015)
1.250 (0.001)
0.275 (0.02))
0.022 (0.005)
0.271 (B.037)
vonilla BO
0.051 (0.005)
0.061 (0.00)
0.079 (0.009)
(0.0600
(0.00)
0.115 (0.017)
0.184 (0.004)
0.226 (0.023)
0.024000000 (0.005)
0.248,0.000)
IDDO
0,042 (0.00)
0.019 (0.006)
0.073 (0.009
0.015(0.002)
0,065 (0.001)
0,066 (9.008)
0.148 (0.02))
0.186 (0.020)
0.010 (0.003)
(0.02()
BOPCA
0.049 (0.006)
(00007)
0.074 (0.010)
0.014 (0.902)
(0.001)
0.074 (0.015)
0.225 (0.028)
0.160 (0.02))
0.013 (0.004)
0.149 (B:022)
FASE
0.059 (0.006)
0.060 (0.05)
0.115 (0.012)
0.032.00.005 (0.005)
0.000(00.00)
8J076 (0.015)
0.129 (0.022)
0.271 (0.015)
0,23 (0.004)
0.357 (0.033)
MIPROV2
0.063 (0.007)
0,056 (0.067)
0.062 (0.008)
0.017 (0.002)
0,005 (1.001)
3,022 (0.011)
0.183 (0.0266
0.218 (0.022)
0,023 (0.0844
0:265 (0.033)
TRIPLE-SH
(0.056
(0.002)
(0.005)
0.008 (0.982)
0.012
0.068 (6.008)
0,034 (0.008)
(0.014)
0.025 (0.005)
(0.09))
TRIPLE-GSE GSE
0.022 (0.006)
0,092 (0.001)
0.026 (0.006)
0.020 (0.003)
0.015 (0.001)
0.050 (8.005)
0,074 (0.011)
0 (0.016)
0.035 (0.004)
0.184 (0.003)
EbBoP's
0.019 (0.905)
0.006 (0.002)
0.024 (0.004)
0.005 (0.902)
0.008 (0.001)
0.092 (0.018)
0,041 (0.009)
0,043 (0.014) 0.020 (0.084)
0,048 (0.014)
In Tables 6, 7 and 8 we report the average normalized validation error of the best prompt found by each method after having used a fraction of 1.00 LLM calls, separately for each benchmark task, separately for each LLM.
We perform the same analysis for the test error at a fraction of 1.00 and reject the global null hypothesis of no effect of methods (x2 (8) = 288.36, p- < 4). The pairwise results are:
RS vs. libPoPs = = 1 < 4
vanilla BG vs. HiltoPs, & = 11.03. < 16-4
21

---

Hyperband-base based Bayesian Optimization for Black-box Prompt Selection
Table 8. Normalized validation error of each method on each henchmark for Mistral 7B Instruct. Averaged over repetitions. Standard errors in parentheses. For visual analysis, we highlight all methods that have mean error that is less or equal to the mean error of the best method plus two times its standard error.
Benchmark
A12 ARC
GSMBK
antonyus
larger
negation
object countingg
octhagraply
sccced word
unscrambling
RS
0.529 (0,035)
0.160 (0.02))
0.020 (0.002)
0.045 (0:005)
0.00% (3.0033)
0,040 (0.004)
0:164 (0.018)
9.171 (0.01))
0.05% (0:013)
0:234 (B.017)
vanilla BO
0.359 (0.038)
0.166 (0.021)
0.077 (0.002)
0.040 (0.000)
0.005 (0.003)
0J033 (0.005)
0.117 (0.030)
0.136 (0.01)
0.885 (0.016)
0.161 (0.019)
IDBO
0.217 (0.045)
0.105 (0.019)
0.013 (0,002)
0.021 (0.005)
0.009 (0.000)
0.028 (9.005)
(0,2010.018)
0.085 (0.017)
0.042 (0.013)
(0.016))
BOPCA
(0,06))
0.015 (0011)
0.021 (0.005)
(0.004)
0.632 (0,006)
(0.02
0.125
0.048
0:136 (0.000)))))
EASE
0,384 (0.03)
0.133 (0.014)
0.022 (0.002)
(0.000)
0.000 (0,000)
0,035 (0.005)
0.147 (0.023)
0.183 (0.014)
0.110 (0.014)
0,095 (0:021)
MIPROV2
0.323 (0.041)
0.122 (0.017)
0.013 (0.002)
(0.005)
0.011 (0.004)
[.632 (0,015)
0.125 (0.014)
0.158 (0.016)
0.068 (0.014)
0.163 (0:017)
TRIPLE-SH
(0.011)
(0.003)
0,041 (0.005)
0.012 (0.003)
0.044 (0.008)
0.057
0.005
0.055 (0.010)
(0.018)
TRISI
(,838 (0.816)
0.001 (0.000)
0.042 (0.005)
0.022 (0.005)
0.055 (0.010)
0.067 (0.010)
0.002 (0.000)
0,022 (0.05))
0.084 (0.017)
0:145 (0.022)
EoBcPe
0,107 (0.036)
0.000 (8.000)
0.011 (0.001)
0.012 (0.003)
0.012 (0.005)
0,025 (0.005)
0,024 (0.010)
0.067 (0.0133
0.930 (0.011)
0 (0.014)
HD30 vs. HbBoPs, x G.19. < 10-4
BCPCI vs, abBoPs, 2 = T.58, p < 1e-d
RASE WofooPe, 7.98. 1e-4
MIPROV2 vs WbBoPPe = 8.61, < 16-4
TRIPLE-SH
SE vs. HbBoPs. a p. 1.000
TRIFLE-GSE vs. Hb 1.34, = 1.000
Conclusions are largely consistent with the analysis with respect to validation error, however, while HoBoPs improves over TRIPLE-SE SH and TRIPLE- CASPEEE-SEEEE also with respect to test enror, the effects are not strong enough to be considered statistically significant at the = 0.01 level. For brevity, we do not include results for fractions of 0.25 or 0.50 here, where we observed similar results but HbBoPs a again more strongly outperforming the other methods.
Table Normalized test eиror of each method on each benchmark for Claude Haiku, Averaged over repetitions. Standard errors in parentheses, For visual analysis, we highlight all methods that have a mean error that is less or equal to the mean error of the best method plus two times its standard error.
Benchmark object counting
AI2 ARC
GSM8K
antonyms
larger
negation
octhograpby starts
sccond word
unscramblig
RS
0.234 (0.823)
(0.012)
0,074 (0.013)
0,096 (0.304)
0.134 (8.007)
0.340 (0.014)
0.277 (0,011)
0,058 (0.010)
0.244 (0.019)
0.163 (0:011)
Vanilla BO
(0.821)
0.092 (0.01))
0.084 (0.014)
0,113 (0.010)
0.134 (0.007)
0.147 (0.019)
0.256 (0.011)
0.063 (0.008)
0.207 (0.016)
0.156
IDBO
0.203 (0.820)
0.087 (0.010)
0.078 (0.003)
0,105 (0.008)
0,124 (0.007)
0,063 (0.015)
0.294 (0.011)
0.000 (0.00)
0.237 (0.014)
0,133 (0.000)
BOPCA
0.209 (0.018)
(0.009)
0.078 (0.0113
0.105 (0.309)
0.134 (0.007)
0.129 (0.019)
0.502 (0.012)
0,009 (0.009)
0.230 (0.014)
0:150 (0.011)
EASE
0.243 (0.023)
0,036 (0.006)
0.070 (0.084)
0.108 (0.007)
0.134 (0.007)
0.135 (0.015)
0.282 (1.018)
3,058 (0.009)
0.263 (0.016)
0.135 (B:010)
MIPROV2
0,200 (0.820)
0.088 (0.006)
0.877 (0.0013
0,099 (0.0045)
0.124 (1.007)
0,100 (0.017)
112711 (0.011)
3,09 (0.088)
0.219 (0.116)
0,125 (0:0035
TRIPLF-SH
0.256 (0.004)
(0.009)
(0.006)
0.176 (0.006)
0.664 (0.012)
0.272 (0.015)
0.088 (0,085)
0.348 (0.019)
0.116 (0.085)
TRIPLE-GSE
0,307 (0.024)
0.080 (0.010)
0.082 (0.005)
0.115 (0.010)
0.106 (0.009)
0.130 (0.019)
0.299 (0.0144)
0.009 (0.005)
0.322 (0.022)
0.122 (0.095)
EbBoPa
0,182 (0.826)
0,083 (0000)
0.080 (0.0055
0,089 (0,307)
0,118 (0.008)
0.317 (0.021)
0,262 (0.010)
0 (0J007)
0.219 (0.016)
0.125 (0.094)
Table 10. Normalized test error of each method on each benchmark for LLAMA3 8B Instruct. Averaged over repetitions. Standard errors in parentheses. For visual analysis, we highlight all methods that have a mean error that is less or equal to the mean error of the best method plus two times its standard error.
Benchmark
AIC
GSMBK
amaatyus
larger
negation
object countinn
orihagraply
sccoed word
unscrambling
RS
0.066 (0.010)
(.112(00001)
0.147 (0.012) 0.085 (0:011)
0.104 (0.010)
0.238 (0.021)
0.29% (0.041)
(0.09)
0.356 (0:013)
0.633 (B.054)
vonilla BO
0,058 (0.009)
0.009 (0.012)
0.145 (0.015)
0,075 (0.007)
0.129
0.236 (0.023)
02:8400004)
0.202 (0.031)
0.356(0.013
(0.054)
IDDO
(0.008)
0.028 (0.009)
0.133 (0.014)
0.085 (0.007)
0.138 (0.007)
0.165 (0.019)
0.184 (0.025)
0.248 (0.027)
0.321 (0.010)
0,767 (0.056)
BOPCA
0.033 (0.004)
(0.011)
0.124 (0.014)
(0.007)
0.126 (0.009)
0.216 (0.014)
0.263
0.344 (0.010)
0.667 (0.045)
EASE
0.847 (0.007)
0.94 (00009)
0.181 (0.015)
0,076 (0.009)
0.112 (0.008)
0,014 (0.009)
0.171 (0.037)
0.248 (0.027)
0.274 (0.013)
0.622 (0.055)
MIPROV2
[.344 (0.008)
0.088 (0.012)
0.114 (0.015)
0,076 (0.006)
0.135 (0.000)
0.160 (0.019)
01239 (0.045)
0.248 (0.024)
0.356 (0.014)
8,700
TRIPLE-SH
(0.00)
(0.003)
0.070
0.075 (0.005)
0.125 (0.011)
0.177 (0.017)
0,037 (0.009)
(0001)
0.362 (0.014)
0.67% (0.05))
TRIPLE-GST GSE
0.017 (0.004)
0.003 (0.002)
0,052 (0.012)
0.059 (0.008)
0.110 (0.009)
0.167 (0.019)
0,078 (0.019)
0.140 (0.016)
0.369 (0.014)
0.544 (0.059)
EbBcPe
0.016 (0.906)
0.009 (0.003)
0.093 (0.015)
0.064 (0.607)
0.152 (0.010)
0:207 (0.027)
0.075(0.019)
0.120 (0.01) 0.341 (0.012)
0.489 (0.044)
In Tables 9, 10 and 11 we report the average normalized test error of the best prompt found by each method after having used a fraction of 1.00 LLM calls, separately for each benchmark task, separately for each L.I.M.
22

---

Hyperband-basee -basd Bayesian Optimization for Black-box Prompt Selection
Table 11. Normalized test error of each method on each benchmark for Mistral 7B Instruct. Averaged over repetitions. Standard errors in parentheses, For visual analysis, we highlight all methods that have a mean error that is less or equal to the mean error of the best method plus two times its standard error.
Benchmark
AI2 ARC
GSMBK
anbanyus
larger
negation
object countinn
octhagraply
sccoed word
unscrambling
RS
0.277 (0.087)
(0.021)
0.099 (0.036)
0:259 (0:133)
(0.005)
0.188 (8.015)
0.293 (0.026)
0.194 (0.015)
0.156 (0:019)
(8:099)
vanilla BO
0.366 (0.042)
0.300 (0.022)
0.992 (0.006)
0.201 (0.025)
0.531 (0.0255
0.199 (0.013)
0.229 (0,00))
0.172 (0.018)
0.125(0.017)
0.445
IDBO
0.215 (0.045)
0.112 (0.020)
0.056 (0.005)
0.140 (0.009)
0.451 (0.027)
0.226 (0.013)
0.257 (0.001)
0.112 (0.021)
0.059 (0.018)
(0:02()
BOPCA
0.266 (0.047)
(0001)
(0,007)
0.162 (0.019)
0.500
0.232 (0.013)
(0226:
0.140 (0.02)
0.063
(0.034)
EASE
0.356 (9.036)
(0.04))
0.076 (0.008)
0.181 (0.021)
0.633 (0.022)
0,209 (8.013))
0.257 (0.029)
0.211 (0.018)
0.15% (0.019)
0.290 (0,025)
MIPROV2
0.327 (0.043)
0.165 (0.01))
0.054 (0.0044)
(0.720
0.519 (1.026)
0.195 (0.013)
0.248 (0.025)
0.193 (0.018
0.115 (0.022)
0:429 (0:029)
TRIPLE-SH
(0.06().008)
(0.010
(0.007)
0.140 (0.009)
0.536 (0.016)
0.230 (0.014)
(0.014)
(0.016)
0.116 (0.019)
(0.05()
TRIPI
0.028 (0.012)
0,050 (0.01))
0,055 (0.006)
0:169 (0.011)
0.421 (0.038)
0.226 (0.013)
0.06] (0.011)
0 (8.015)
0.104 (0.027)
(0.029)
EoBcPe
0,096 (0.002)
0.011 (8.006)
0.063 (0,005)
0.162 (0.013)
0.462 (0.028)
0.238 (0.011)
0,053 (0.023)
0.083 (0.017)
0.088 (0.021)
0,367 (0.030)
E.2. Ablation Study
Here, we provide additional analyses of the ablation results reported in Section 5.3, To test the significance of each component on the validation and test error of HbBoPs, we again conduct a linear mixed effects model analysis. We model the unaggregated performance as function of the fraction of LLM calls (i.e., over time; starting after the initial design of full-fidelity methods, i.e., after fraction of 0.40) and include random intercepts for each benchmark scenario (benchmark task and LLM combination). To test the global hypothesis that there is an effect of the components on performance, we test an intercept model against model including an effect of the factor method (corresponding to an ablation variant). If we reject the null hypothesis, we proceed with a Tukey post hoc test (corrected for multiple testing) to perform pairwise comparisons. We test at the conservative a = 0.01 level.
Examining the validation error, we reject the global null hypothesis of no effect of the method on the anytime performance (x) = 35184.28. p < 4)-4). The relevant pairwise comparison results state as follows:
BO BaPs tcon scructural- -waro D 48.80, 1e-4
RoPa Inon structora avare DK-GP) (struocural--oe axere EX-GPI, 16.07,p < 16-4
RoPs rectural raeee (K--PP 52.92, p < 1n-4
BB abBoFs, 24.00, p 1e-4
We can conclude that using a DK-GP significantly improves over vanilla BO, that a structural-aware DK-GH improves over the non struetural-aware DK-GP, that HB improves over the structural-aware DK-GP and that HbBoPs further improves over HB.
We perform the same analysis for the test error and reject the global hypothesis of no effect (x) 14578.73, p < 11c-4).
The relevant pairwise comparison results state as follows:
vamilla BC Bape Icon resuctora--awarr DK-GF), s 39,35, lo-4
BcPe Inon structora..aoe DK-GF: vs, Boze (etruccural-wvere EX-CPI, 6.51, < 1o-4
Ba7s (siructural aaass DX-GD) 31.59. p < 1e-4
HB a 18.85, 1e-4
Conclusions are the same as for the validation error.
E.3. Encoder Sensitivity
Here, we provide additional analyses of the encoder sensitivity results reported in Section 5.4. To test whether the choice of encoder model affects the final performance of НbВoPs, s, we again conduct a linear mixed effects model analysis. We model the unaggregated performance a fraction of 1.00 total LLM calls involving random intercepts for each benchmark scenario (benchmark task and LLM combination). To test the global hypothesis that there is an effect of the encoder on performance, we test an intercept model against a model including an effect of the factor encoder. We test at the conservative a = 0.01 level. For both the validation and test error, we cannot reject the null hypothesis of the encoder making no difference, x²(2)= = 4.69, p = 0.096 and x (2) = 3.85, p = 0.146 respectively. We therefore conclude that HbBoPs s is robust to the choice of encoder model.
23

---

Hyperband-basee Bayesian Optimization for Black-box Prompt Selection
E.4. Hyperband Design Choices
As mentioned in Section 3 and Appendix C, adapting HB to prompt selection involves several design decisions. Here, we provide an ablation of these decisions. While vanilla HB for hyperparameter optimization would return the configuration with the lowest validation error as the (anytime) incumbent, this is not sensible for prompt selection as the fidelity directly influences the noise of the validation error. We therefore always return the prompt with the lowest validation error among all prompts that have been evaluated on the (current) highest fidelity level. To analyze the effect of this design decision, we run HB for prompt selection with this incumbent selection mechanism and compare to the incumbent selection mechanism that simply selects the prompt with the lowest validation error. The experimental setup is exactly the same as for the results reported in the main paper. We visualize the (oracle) normalized validation and test error of the best prompt found by HB under each incumbent selection scheme in Figure 6. As before, for visualization purposes the validation error of the incumbent is computed here in an oracle setting (i.e., using all validation instances), whereas during the selection process the anytime incumbent itself was selected based on its validation error computed on fewer validation instances. Examining the validation error (Figure 6a) of HB as used by us (selecting the incumbent as the prompt with the lowest validation error among all prompts evaluated on the highest fidelity level), we observe that the validation error of the incumbent keeps decreasing as optimization progresses. In contrast, we would perform the incumbent selection simply by choosing the prompt with the lowest validation error (ignoring the fidelity level), as in HB (incumbent lowest val validation error), we observe that optimization progress stagnates quickly. This occurs because the incumbent is no longer updated, since, at lower fidelity levels, noisy performance estimates can result in artificially low validation errors. Similar conclusions hold for the test error (Figure 6b).
Mua Nomm Tast Erer of Natiiadio Bost Woree
Moan Narnalad Valeidion Enor honge
Averaged over Benchmark Scenarios (Tasks Models)
Averaged Denchmark Scenarios (Tasks Models)
Nethod
10
Melnod
1x
30
20-1
21
0.0
0.2
0.6
0.0
1.0
0.0
044 Frazzoon of LUN calli (1.0 25 fullfide Prompt Evaladiona)
022
1.5
Fraciion of Tatal cass 11.0 25 fudeliy Evalsatrr)
(a) Validation
(b) Test
Figure 6. Normalized error (log scale) of the best prompt found by cach HB incumbent selection mechanism, averaged over benchmarks.
Lower is better. Ribbons represent SE.
To test whether the choice of selection mechanism does make a difference for the final performance of HB, we again conduct a linear mixed effects model analysis. We model the unaggregated performance at a fraction of 1.00 total LLM calls involving random intercepts for each benchmark scenario (benchmark task and LLM combination). To test the global hypothesis that there is an effect of the incumbent selection mechanism on performance, we test an intercept model against a model including an effect of the factor selection mechanism. We test at the conservative a = 0.01 level. For both validation and test error we reject the null hypothesis of no effect of the selection mechanism x²(1)= = 448.05 13.8.05, p 1e-4 and x² 164.17, p < le respectively. We therefore conclude that our incumbent selection mechanism is superior.
Another design decision for adapting HB to prompt selection is concerned with whether prompts should be evaluated on the same random validation instances within a stage or on their own random samples. The final related design decision involves whether validation instances of higher stages for a given bracket are constructed to be supersets of the validation instances used lower stages (as described in Appendix C) which allows for further speed-ups due to caching.
To investigate the effect of using the same random vs. truly random instances for each prompt and the effect of validation instances used in higher stages of a bracket being supersets of the validation instances used in lower stages, we run HB for prompt selection varying these two components. The experimental setup is exactly the same as for the results reported in the main paper. We visualize the (oracle) normalized validation and test error of the best prompt found by HB under each incumbent selection scheme in Figure 7. As before, for visualization purposes the validation error of the incumbent is computed here in an oracle setting (i.c., using all validation instances), whereas during the selection process the anytime incumbent itself was selected based on its validation error computed on fewer validation instances. Examining the
24

---

Flyperband-basee Bayesian Optimization for Black-box Prompt Selection
validation error (Figure 7a) of our proposed HB (same random instances and supersets), we can see that this variant performs best. If we truly random instances (but keep the superset structure) as in HB (random instances for each prompt), ) performance is slightly worse. Giving up the superset structure (HB (no supersets, same instances for each prompt) ) and HB (no supersets, random instances for each prompt) ) we can see that performance is substantially worse, even more so when using truly random instances for each prompt. In general, we can conclude that the effect of using supersets for higher stages within a given bracket boosts the performance of HB. Moreover, using truly random validation instances for each prompt instead of using the same random validation instances for all prompt evaluations in a stage (i.e., the paired setting) generally worsens performance. Examining the test performance, we observe that these conclusions generalize (Figure 7b).
Mean Nomma and Rost Seron Noriaatti Bhst thongg
Averaged Benchmark Scenarios
Averaged Benchmark Scenarios
60
Method
Nomallzed Valeaaiin End
40
3x
20-1
2x
0.0
0.
0.6
5.0
0.2
2.0
1,5
Raction of LLM Cals 11.0 25 Tddellyy Promet Promoc Evaluators
Frazion To calls (1.0 25 fullffiee Prompi Evalandons
(a) Validation
(b) Test
Figure 7. Normalized error (log scale) of the best prompt found by each HB validation instances sampling variant, averaged over henchmarks. Lower is better. Ribbons represent SE.
To test whether the design decisions of using supersets and using the same random validation instances for each prompt evaluation within a stage make a difference for the final performance of HB, we again conduct a linear mixed effeets model analysis. We model the unaggregated performance at a fraction of 1.00 total LLM calls involving random intercepts for each benchmark scenario (benchmark task and LLM combination). To test the global hypothesis that there is an effect of the design choices on performance, we test intercept model against model including an effect of the factor method (corresponding to ablation variant). We test at the conservative 0.01 level.
For the validation error at a fraction of 1.00, we reject the global null hypothesis of no effect of methods (x²(3) = 730.85, < 1e-4). The pairwise results are:
BB trandon instances for each prompt) HB, 1.13p p 0.259
BB Ino supersets, same instances for each prompt) HB. 10.12, le-4
BB Ino aupersets, randon. instances for each pronot) vs. HB, 22.03, 1om4
BB supersets, some instances for each promot) vs. BB ixandon instances for each prompt). 17.99. < le-4
BB Ino supersets, randon instances
prorgt) (randen instances
prompti. 20.90, 1e-4
BB Ino aupersets, randon. instances for each promot) vs, HB (nc superssts, same instances for each prompt). = 2.91, 0.007
Examining test error at a fraction of 1.00 we also reject the global null hypothesis of no effect of methods (x²(3) = 207.12, < 1e-4). The pairwise results are:
BB tsandon instances for each pronpt) HB, 1.39, p 0.328
BB Ino supersets, same instances for each prompt) HB. 10.92, le-4
RB Ino supersets, randon instances for each prompt) vs. li,, 11.02, 1n-4
EB supersets, same instances for each promot) vs. BB Izandon instances for each prompti, 9.553, 1e-4
HB Ino supersets, randon instances
prorgt) (randen instances prompti. 9.63, p < Ie-4
RB Ino supersets, random. instances for each pronpt) vs. Hif (nc sugerietts, zane instances for each prompt). = 0.1 0.916
25

---

Hyperband-bane baarbd Bayesian Optimization for Black-box Prompt Selection
Summarizing, our results confirm that the design decisions made to adapt HB prompt selection effective: (1) The incumbent should be selected the prompt with the lowest validation error among all prompts evaluated the highest fidelity level. (2) Validation instances used to evaluate prompts in higher stages of given bracket should be supersets of the validation instances used in lower stages. (3) Using the same (random) validation instances to evaluate prompts in each stage in general is beneficial compared to using truly random validation instances for each prompt, albeit this effect is comparably small.
26


Reviews:
[{"review_id": "GHq6hOtHVo", "reviewer": "Reviewer_vVkq", "summary": "The paper uses hyperband, combined with a Gaussian process surrogate model with deep kernel learning, to optimize the prompt for black-box LLMs. The method optimizes both the instruction and exemplars, and specifically aims to optimize the efficiency in terms of the total number of LLM calls. Extensive experiments and comparisons with previous baseline methods demonstrate the efficacy of the proposed method.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive review.\nWe 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.\nMoreover, we are happy to hear that they find the structural-aware deep kernel to be elegant.\nWe are also pleased that the design and insightfulness of our ablation studies were positively noted.\nLastly, 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.\nBelow, we respond to weaknesses, feedback and questions raised by the reviewer:\n\n`1. Limited instruction search space`\n\nWhile 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.\nThis 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)](https://proceedings.neurips.cc/paper_files/paper/2024/hash/b46bc1449205888e1883f692aff1a252-Abstract-Conference.html).\n\nFrom a methodological standpoint, our approach is expected to scale effectively with larger instruction spaces.\nThis is due to the structural-aware surrogate model, which encodes instructions and exemplars separately.\nThus, increasing the instruction set size would likely further amplify the benefits of our modeling choices rather than hinder them.\n\n`2. Interesting optional experiments on the most powerful LLMs, such as DeepSeeks R1`\n\nWhile 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.\nIn 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.\nThe 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.\n\n\n\nWe thank the reviewer again for their feedback and we remain happy to clarify any follow-up questions.", "claims_and_evidence": "The claims made in the paper are supported by clear and convincing empirical evidence. Extensive experiments and comparisons with previous baseline methods demonstrate the efficacy of the proposed method. The experimental results clearly show that the proposed method performs better than previous full-fidelity and multi-fidelity methods. Additionally, the ablation studies are well-designed and reveal the importance of different components of the proposed method, further supporting the claims.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are reasonable for the studied problem. Applying hyperband to prompt optimization is a natural and suitable idea. The paper specifically considers minimizing the total number of LLM calls on the validation set, which is an important yet often overlooked aspect in previous works on prompt optimization. This focus on efficiency (in terms of LLM calls) is commendable and aligns well with the goal in practice. The structural-aware deep kernel design is very interesting. It separately embeds the instruction and exemplars before combining them via another MLP.", "theoretical_claims": "The paper does not have theoretical claims.", "experimental_designs_or_analyses": "The experimental designs and analyses appear sound and valid. The experimental results are a strength of the paper, showing the superiority of the proposed method over previous approaches. The ablation studies are well-designed, revealing the importance of different components such as the structural-aware deep kernel design. One potential drawback is that the search space in the experiments may be a little too small, as the space contains only 5 instructions (although the entire space has 250 input prompts).", "relation_to_broader_scientific_literature": "The paper contributes to the existing broader scientific literature, particularly in the areas of prompt optimization for black-box LLMs. The use of hyperband for prompt optimization is a natural and effective idea.", "essential_references_not_discussed": "I'm not aware of any essential missing reference.", "other_strengths_and_weaknesses": "Strengths:\n- The design of the structural-aware deep kernel is elegant and innovative.\n- The experimental results are strong and clearly demonstrate the efficacy of the proposed method.\n- The focus on minimizing the number of LLM calls on the validation set is a commendable and practical aspect.\n\nWeaknesses:\n- The search space in the experiments may be a little too small, as it only contains five instructions.", "other_comments_or_suggestions": "An interesting (but optional) further experiment to explore is to optimize the prompt for the most powerful LLMs nowaways (such as those reasoning models like DeepSeek R1), to see whether the proposed method can improve the performance of these strong models.", "questions_for_authors": "Please see my individual comments above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "un2kFc0Ux3", "reviewer": "Reviewer_rbkb", "summary": "The paper introduces HbBoPs, a novel method for optimizing prompt selection in large language models (LLMs) in black-box settings. The method combines a structural-aware deep kernel Gaussian Process with Hyperband, a multi-fidelity scheduler, to efficiently select prompts. The approach is designed to handle large, combinatorial search spaces and high evaluation costs associated with black-box LLMs. Extensive experiments demonstrate that HbBoPs outperforms state-of-the-art methods in both performance and efficiency.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive feedback and for recognizing the novelty and efficiency of our proposed method.\nWhile we appreciate the reviewer’s feedback, we note that some contributions of the paper may not have been fully recognized.\nBelow, we respond to the two concerns raised in the review.\n\n`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.`\n\nEASE can be used for joint instruction and few-shot exemplar selection by treating the prompt as a single block of text.\nWe ran EASE in exactly this way, as intended by the authors.\nHowever, in contrast to our method, EASE does not make use of the structural information of the prompt being composed of different building blocks.\nTherefore, compared to our method, EASE is \"not explicitly designed for the problem\" which is what we stated in line 51.\nIn our experiments, we observed that this structural unawareness leads to lower optimization performance compared to our approach.\nStill, 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\".\n\n`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?`\n\nTo 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.\nThese experiments were carried out across all benchmark tasks and LLMs, and the results are reported in Section 5.2 of the paper.\nAs 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.\nWe further confirm this observation with a statistical analysis provided in Appendix E.3.\nThis evidence supports our claim that the overall effectiveness of our method is not sensitive to the particular encoder.\nWe note that this robustness was also recognized as a positive aspect by reviewer Nvhi.\n\nWe hope that our responses above have adequately addressed the two concerns raised by the reviewer responsible for the comparably low rating.\n\nThe reviewer further had the following question:\n\n`Can the method be extended to handle other components of prompts, such as output guidance or formatting constraints?`\n\nHbBoPs is sufficiently flexible to be extended to handle additional prompt components, such as output guidance or formatting constraints.\nOne 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).\nThis would expand the search space beyond instructions and few-shot exemplars along these dimensions.\nIncorporating these into our framework involves augmenting the input representation to the deep kernel GP.\nSpecifically, the additional parameters, after suitable encoding, can be concatenated with the learned representations of the instructions and few-shot exemplars.\nFor 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.\nThe surrogate model will then jointly learn to predict performance based on the prompt structure including these new components.\nWe view this as a promising direction for future work.\n\nFinally, 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.\n\nWe thank the reviewer again and are happy to clarify any further questions.", "claims_and_evidence": "Claim: HbBoPs improves query-efficiency by adaptively allocating resources across different fidelity levels.\nEvidence: The paper presents experimental results across ten benchmarks and three LLMs, showing that HbBoPs outperforms existing methods in terms of both performance and efficiency.\nClaim: The structural-aware deep kernel GP enhances the surrogate model’s ability to predict prompt performance.\nEvidence: The paper includes an ablation study demonstrating the effectiveness of the structural-aware deep kernel GP compared to non-structural-aware models.", "methods_and_evaluation_criteria": "The paper uses a combination of Gaussian Processes and Hyperband for prompt selection. The structural-aware deep kernel GP is used to learn a low-dimensional prompt representation, while Hyperband governs the number of validation instances for prompt evaluation.\n\nThe methods are evaluated based on their ability to identify well-performing prompts with a limited number of LLM calls. The performance is measured using validation and test errors across various tasks and LLMs.", "theoretical_claims": "The paper claims that the structural-aware deep kernel GP can effectively use structural and semantic differences in prompts to improve prediction accuracy.\nIt also claims that Hyperband can efficiently explore the search space by terminating poor-performing prompts early.", "experimental_designs_or_analyses": "The experiments are conducted on ten tasks commonly used for LLM evaluation, using three different LLMs.\nThe paper compares HbBoPs against several baselines and state-of-the-art methods, using a total budget of 25 full-fidelity evaluations for each task.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "n/a", "other_strengths_and_weaknesses": "The method is highly efficient in terms of both sample and query efficiency. The integration of Hyperband with a structural-aware GP is novel and well-justified.\n\nThe method's performance depends on the choice of encoder model for embeddings, although the paper claims robustness to this choice.", "other_comments_or_suggestions": "In line 51, the authors claim that EASE does not consider the joint optimization of instruction and exeamplers, which is not true. Please check the EASE paper carefully again.", "questions_for_authors": "How does the choice of encoder model affect the performance of HbBoPs in practice?\nCan the method be extended to handle other components of prompts, such as output guidance or formatting constraints?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SMcgfE6fc2", "reviewer": "Reviewer_Nvhi", "summary": "This paper contributes in two main ways for prompt optimization in the context of maximizing total scores over datasets (e.g. GSM8K):\n  * Introducing a deep kernel GP, i.e. project high-dimensional prompt embeddings into a lower dimension before sending vectors to kernel\n  * Introducing standard Hyperband technique for multi-fidelity scheduling (i.e. avoid evaluating using the full validation set in GSM8K).\n\nExperiments show this method outperforms previous prompt optimization methods (TRIPLE-GSE, TRIPLE-SH, MIPROv2, EASE), and ablations are done to analyze the effects when using different base methods (Claude, LLAMA, Mistral) and different embedders (BERT, MPNet, DistillRoBERTa). \n\nAdditionally Appendix A contains important ablations on understanding the behavior of the projected embeddings (i.e. if they match with the objective function).", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive review.\nWe 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.\nWe also appreciate their acknowledgment of the comprehensiveness of our experiments and ablation studies.\nBelow, we respond to weaknesses, feedback and questions raised by the reviewer:\n\n`1. Possibility of Overfitting in Deep Kernel GP`\n\nIndeed, prior work, such as [Ober et al. (2021, UAI)](https://proceedings.mlr.press/v161/ober21a.html) has highlighted scenarios where deep kernel models may overfit.\nHowever, in our setting, this risk is mitigated.\nThe encoder component (e.g., BERT) is a large, frozen, pre-trained language model.\nThe 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.\nThis is significantly smaller than typical deep kernel learning applications, where models with 5-10x more trainable parameters are used.\nAdditionally, 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.\n\n`2. EI as acquisition function`\n\nWe chose EI as our acquisition function since it is widely regarded as the de facto standard in BO.\nWhile 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.\nThe reviewer is correct in referring to [Ament et al. (2024, NeurIPS)](https://proceedings.neurips.cc/paper_files/paper/2023/hash/419f72cbd568ad62183f8132a3605a2a-Abstract-Conference.html), who discuss challenges associated with optimizing EI using gradient-based methods.\nThese difficulties are primarily due to EI being flat in large regions of the input space and often numerically close to zero.\nThis 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).\nHowever, these challenges do not arise in our setting.\nIn particular, we do not rely on gradient-based optimization of the acquisition function.\nInstead, since our candidate set of prompts is discrete, we evaluate the EI exhaustively over all candidates and select the argmax directly.\nAs such, issues of flatness, vanishing gradients, or numerical instability in gradient-based optimization are not applicable in our case.\n\n`3. Is the deep kernel GP trained only on the current task’s trials or pre-trained on offline data?`\n\nThe deep kernel GP is trained entirely online, using only the observations collected during the current optimization run.\nWe do not pre-train the deep kernel feature extractor on offline data before the task.\nThat 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!\n\n`4. Related Work`\n\nWe 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.\nWe appreciate these suggestions and will ensure that these works are included and appropriately discussed in the camera-ready version of the paper.\nConcerning the directly related work of [Falkner et al. (2018, ICML)](https://proceedings.mlr.press/v80/falkner18a.html) 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.\n\nWe thank the reviewer again for their feedback and we remain happy to clarify any follow-up questions.", "claims_and_evidence": "Yes, the experiments are fairly comprehensive. I was most interested in making sure the projected embeddings on validation settings made sense (i.e. new objective landscape is smooth). It's possible that the high parameter-count of the embedding projector could've led to overfitting when performing GP logprob maximization, but apparently not.", "methods_and_evaluation_criteria": "Yes, the method makes complete intuitive sense and matches standard intuitions from Bayesian Optimization (e.g. making sure the Gaussian Process works well for regression) + using Hyperband for multifidelity optimization.", "theoretical_claims": "N/A - no theoretical claims.", "experimental_designs_or_analyses": "As mentioned earlier, I just wanted to make sure that the new deep kernel-GP provided accurate regression results, and according to Appendix A's visualizations, this confirmed it.\n\nEverything else (i.e. optimization performance) follows directly.", "relation_to_broader_scientific_literature": "The deep kernel GP idea using LLM embeddings might be much more broadly applicable than just prompt optimization. For example, since inputs are strings, one can also perhaps use such techniques to speed up evolutionary code searches (e.g. [1]) as well, or even generally, any optimization problem involving mapping a string to a score. Recently, it has been discovered [2] that even embedding tabular inputs leads to embeddings which have good objective landscape properties.\n\n[1] (Romera-Paredes, 2023) Mathematical discoveries from program search with large language models.\n\n[2] (Tang, 2024) Understanding LLM Embeddings for Regression", "essential_references_not_discussed": "Since prompt optimization is a form of bandit optimization, there have also been other works involving combining embedding, GPs and Hyperband for regression (in more other optimization settings however), that the authors should consider citing:\n\n[1] (Rankovic, 2023) BoChemian: Large language model embeddings for Bayesian optimization of chemical reactions.\n\n[2] (Falkner, 2017) Combining Hyperband and Bayesian Optimization.\n\n[3] (Kristiadi, 2024) A Sober Look at LLMs for Material Discovery: Are They Actually Good for Bayesian Optimization Over Molecules?\n\n[4] (Tang, 2024): Understanding LLM Embeddings for Regression.\n\n[5] (Nguyen, 2024): Predicting from Strings: Language Model Embeddings for Bayesian Optimization", "other_strengths_and_weaknesses": "As mentioned before, I suspect this deep kernel GP idea using LLM embeddings will be much more broadly applicable to many different problems (any objective mapping a string to a score) than just prompt optimization. It would be worth investigating this in future work.\n\nThis is especially true if one can pretrain the GP over a massive amount of offline data first for better warm-starting.", "other_comments_or_suggestions": "* Just making sure (forgive me if I missed it) - in terms of amount of data, is the deep kernel GP retrained online at every optimization iteration only on the current optimization task's trials, or is it pretrained from offline data before the start of optimization? \n* Why EI for acquisition, as opposed to UCB? EI can be quite flat, making acquisition optimization difficult sometimes, unless you use tricks like log-EI [1].\n\n[1] (Ament, 2023) Unexpected Improvements to Expected Improvement for Bayesian Optimization.", "questions_for_authors": "N/A - paper is overall solid.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qnup0nQfP0", "reviewer": "Reviewer_Su6X", "summary": "This paper assumes a candidate instruction set and a candidate example set and aims to optimize prompts by automatically selecting the best instruction + example combination. The method combines Bayesian Optimization with Hyperband, where the main contribution compared to previous work is using Hyperband to discard poor-performing prompts early, reducing computational cost.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive review.\nWe are pleased that the reviewer finds our method efficient, acknowledges the strength of our experimental results, and appreciates the clarity of the paper.\nBelow, we respond to the concerns raised in the review.\n\n`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.`\n\nOur method is designed for the static black-box prompt selection setting, as discussed in Section 6, which is distinct from iterative prompt optimization frameworks.\nThat said, while our experiments use a fixed candidate set to ensure fair comparison across methods, our approach does not require a fixed candidate set.\nIt can be readily integrated into dynamic or iterative pipelines, where new prompts are generated - e.g., via evolutionary strategies ([Fernando et al., 2024, ICML](https://proceedings.mlr.press/v235/fernando24a.html)) - which update the candidate set.\n\n`2. This application scenario feels somewhat limited because if a human were writing prompts, the number of candidates wouldn't be that large.`\n\nIn 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.\n\n`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.`\n\nWe 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.\n\n`4. LLM calls used as cost metric`\n\nOverall 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.\nIn the case of black-box LLMs accessed via APIs, cost is naturally tied to the actual monetary API cost.\nWhile 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.\nAggregating results across different models using token-based cost introduces additional complexity.\nIn 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. \n\n`5. Cost of feature extractor`\n\nWe 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.\nThis is similar to overhead induced by EASE or TRIPLE-GSE.\nWe consider this overhead minimal in practice relative to the latency and monetary cost incurred by multiple LLM queries required for prompt evaluation.\nMoreover, the overhead of the encoder is small, since encoders have parameters in the range of millions.\n\n`6. Fixed 5-shot setting`\n\nWe conducted preliminary investigations into the effect of the number of few-shot examples.\nResults indicated that increasing the number of examples improves the performance of prompts - similar to [Wan et al. (2024, NeurIPS)](https://proceedings.neurips.cc/paper_files/paper/2024/hash/6b031defd145b02bed031093d8797bb3-Abstract-Conference.html).\nEASE [(Wu et al., 2024, NeurIPS)](https://proceedings.neurips.cc/paper_files/paper/2024/hash/dd8e7dae18cecd7c9137840161e1bf62-Abstract-Conference.html), a competitor, uses $k=5$ in the experiments which we mimicked.\nFrom a methodological standpoint, we expect that increasing the number of few-shot examples further amplifies the benefits of our method.\nCompetitors, in contrast, are not designed to disentangle the contributions of the instructions and few-shot exemplars.\n\n`7. Hyperparameters of the deep kernel`\n\nThe 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.\nWith 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.\n\nWe hope that our responses have adequately addressed the concerns raised by the reviewer, and we remain happy to clarify any follow-up questions.", "claims_and_evidence": "The paper makes two main claims:  \n\n1. Modeling the structural information of instructions and examples separately and using Gaussian Process for prompt selection optimisation (they call it structural-aware deep kernel GP) is better.\n->The paper provides dimensionality reduction comparison experiments (t-SNE visualization), showing that DK-GP aligns the prompt performance better in the low-dimensional space. They also did ablation experiments, demonstrating that structural-aware deep kernel GP outperforms a GP that does not model the structure.  \n\n2. HbBoPs improves efficiency by reducing computational cost through Hyperband’s early stopping mechanism. \n->The experimental results are solid, and the fact that Hyperband improves efficiency is also expected.", "methods_and_evaluation_criteria": "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. Then, BO is used for efficiency to find the best combination. This application scenario feels somewhat limited because if a human were writing prompts, the number of candidates wouldn't be that large. Essentially, we would first need some method to generate a large set of instructions and examples to choose from, but the quality of this set itself is unknown. In 3.2 Structural-aware Deep Kernel, 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\n\nWhen running the experiments, HbBoPs does achieve a lower error rate with fewer LLM calls, but I am curious why the metric here is calls. Typically, we measure time and tokens instead. Also, it seems like the cost does not include the feature extractor’s computation overhead, but generally, comparison methods should consider the total cost.", "theoretical_claims": "No theoretical claims.", "experimental_designs_or_analyses": "The experiments corresponding to the main claims of the paper are conducted clearly, and the results are well-presented.\n\nHowever, the paper does not explicitly compare different n-shot settings and instead fixes 5-shot throughout the experiments. I am curious about how factors such as candidate set size, quality, and n-shot choices affect the method’s performance and convergence. As mentioned earlier, this method seems to be designed specifically for scenarios where we already have a large, high-quality candidate set, since the candidate set is fixed and cannot be updated in the current framework. This raises concerns about its applicability to situations where prompt refinement is iterative. Additionally, the dimensionality reduction step does not explain why 10 dimensions were chosen, and many hyperparameters feel somewhat arbitrarily set without justification.", "relation_to_broader_scientific_literature": "Overall, this work feels somewhat narrow in scope, focusing on a specific setup where a high-quality, fixed candidate set is assumed, without addressing broader prompt optimisation techniques that involve iterative refinement or generation of new candidates.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "The paper is easy to follow.", "other_comments_or_suggestions": "It would be useful to discuss whether and how the approach could handle updates to the candidate set. Maybe compare with baselines that can handle updates, to make this work more convincing.", "questions_for_authors": "As I discussed above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "No"}}]

Author rebuttal:

Meta-review: This paper tackles the challenge of selecting optimal prompts (combinations of instructions and few-shot examples) for LLMs in black-box settings. The authors propose HbBoPs which combines 1) a structural-aware deep kernel Gaussian Process (GP) that handles instructions and exemplars separately and 2) hyperband, a multifidelity optimization strategy to allocate evaluation resources. 

Overall, the reviewers are positive about the work. All reviewers agree that 1) the claims are well-supported by clear and convincing empirical evidence and the gain in performance/efficiency is significant; 2) sound and intuitive methodology and 3) comprehensive evaluation. On the flip side, there are some concerns on the rather small search space (e.g., fixed number of examples) and the fact that the performance can be dependent on the encoder model for embeddings. Overall, either the authors were able to address them satisfactorily, or (in my opinion) the concerns are relatively minor when weighed against the contributions of the paper. I therefore concur with the reviewers and recommend acceptance of this paper.
Decision: Accept (poster)