Efficient Multi-objective Prompt Optimization via Pure-exploration Bandits
Authors: Donghao Li
Chengshuai Shi
Weijuan Ou
Cong Shen
Jing Yang
Venue: ICLR 2026 Poster (2026)
Keywords: Multi-objective prompt optimization; multi-objective bandits; best feasible arm identification; fixed-budget pure exploration
Primary area: foundation or frontier models, including LLMs

Abstract: Prompt engineering has become central to eliciting the capabilities of large language models (LLMs). At its core lies prompt selection - efficiently identifying the most effective prompts. However, most prior investigations overlook a key challenge: the inherently multi-faceted nature of prompt performance, which cannot be captured by a single metric. To fill this gap, we study the multi-objective prompt selection problem under two practical settings: Pareto prompt set recovery and best feasible prompt identification. Casting the problem into the pure-exploration bandits framework, we adapt provably efficient algorithms from multi-objective bandits and further introduce a novel design for best feasible arm identification in structured bandits, with theoretical guarantees on the identification error in the linear case. Extensive experiments across multiple LLMs show that the bandit-based approaches yield significant improvements over baselines, establishing a principled and efficient framework for multi-objective prompt optimization.

Published as a conference paper at ICLR 2026
EFFICIENT MULTI-OBJECTIVE PROMPT OPTIMIZATION VIA PURE-EXPLORATION BANDITS
Donghao Li"
Chengshuai Shi Weijuan Ou Cong Shen" Jing Yang"
University of Virginia, Charlottesville. VA 22904, USA
Princeton University, Princeton, NJ 08544, USA
o Southern University of Science and Technology, Shenzhen, Guangdong 518055, China
ABSTRACT
Prompt engineering has become central to eliciting the capabilities of large lan- guage models (LLMs). At its core lies prompi selection efficiently identifying the most effective prompts. However, most prior investigations overlook key challenge: the inherently multi-faceted nature of prompt performance, which can- not be captured by a single metric. To fill this gap, we study the multi-objective prompt selection problem under two practical settings: Pareto prompt set recov- ery and best feasible prompt identification. Casting the problem into the pure- exploration bandits framework, we adapt provably efficient algorithms from multi- objective bandits and further introduce a novel design for best feasible arm identi- fication in structured bandits, with theoretical guarantees on the identification er- ror in the linear case. Extensive experiments across multiple LLMs show that the bandit-based based approaches yield significant improvements over baselines, establish- ing principled and efficient framework for multi-objective prompt optimization.
INTRODUCTION
Prompt engineering has become practical way to leverage large language models (LLMs) without expensive, cone-conu fine-tuning (Sahoo et al.] 2024] Schulhoff al.) (024). Early results
show that zero-shot (Radford et al. 2019) and few-shot prompting (Brown et al. 2020) with a small
number of examples can elicit strong performance from frozen models. More recently, chain-of- thought (CoT)) prompting (Wei et al., 2022, Kojima et al. 2022; Zhang et al.] 2023) has further unlocked step-by-step reasoning, matching or even surpassing task-specific fine-tuning on several complex benchmarks. Prompting has also become foundational across adjacent areas, including aurreval-augmmented generation (RAG) (Kang et al. 2024), text-to-image generation (Brade et al, 2023 Mo et al. 2024), and jaibbreak analysis and defenses Yan et al. 2024 Mehrotra et al. 2024
Xu & Parhi] 2025).
Generally speaking, prompt engineering comprises manual prompt design, in which experts craft prompts through intuition and iteration, and automatic prompt optimization, in which algorithms search the prompt space systematically. Examples of the latter include evolutionary search for high- performing prompts (Guo et al.); gradient-based methods such as AutoPrompt and APO (Shin et al.) 2020 Pryzant al., 2023); reinforcement learning approaches that cast prompt construction as sequential decision making (Deng et al. 2022); and methods that use an LLM itself as the opti- mizer (Cheng et al. 2024 Tang et al. (2025). Despite their algorithmic differences, these methods share a core challenge: prompt selection, i.e., given finite candidate prompt set X and limited evaluation budget B, how should one allocate queries identify the prompts that maximize task
performance?
Prior work on prompt selection spans Bayesian optimization (Chen et al. 2024, Sabbatella et al., 2024). discrete search (Hu et al.) 2024). and bandit formulations (Shi et al. 22244 Lin al.) 2024| Lin et al. Kong et al. 2025). Despite these advances, existing methods predominantly optimize a sin- gle objective (e.g.. task accuracy), leaving broader trade-offss among multiple objectives largely ad- dressed. However, in many real-world applications, prompt performance is inherently factie-acetedd involving multiple objectives rather than a single metric. For example, in text summarization tasks,

---

Published as a conference paper at ICLR 2026
human and benchmark assessments consider coherence, faithfulness, fluency, and relevance, and no single metric captures all dimensions (Fabbri et al., 2021). In text style transfer tasks, outputs must satisfy both content preservation and style adherence (c.g., modem-to-SSaee -osak-ttt--Saaasearreen transla- tion (Caldas et al., 2018) and politeness transfer (Madaan et al. 2020).. In these multi-objective settings, a single prompt usually cannot be universally superior across all metrics. The trade-offs among these objectives require moving beyond scalarized prompt selection to procedures that pre-
serve multiple criteria throughout the evaluation.
Meanwhile, research on multi-objective bandits offers principled tools for trade-off exploration un- der fixed evaluation budgets, including algorithms that learn with multiple criteria and handle ex- plicit metric constraints with
guarantees (Auer et al. [016)] Kone et al.) [024] 2025 Faizal & Nair, 2022). Yet this toolkit has not been systematically applied to multi-objective prompt selection.
In this work, we aim to bridge these areas by formulating multi-objective prompt selection within bandit framework and developing a principled, bandit-based approach for efficient prompt selection under stringent prompt evaluation budget constraint. Our major contributions are three-fold:
First, we bridge prompt selection under multiple evaluation criteria with the framework of multi- objective bandits. To the best of our knowledge, this is the first attempt to formalize multi-criteria prompt selection as a multi-objective bandit problem. This connection allows to move beyond or single-metrie prompt selection strategies and instead leverage the rich toolbox of multi- objective bandit algorithms. By doing so, we obtain principled and efficient framework for balancing diverse evaluation criteria, leading to more robust and systematic prompt selection.
Secondly, within this framework, we investigate two fundamental problems: best feasible prompt identification and Pareto prompt set identification. For the former, we introduce general algo- rithm, GENSEC, and provide theoretical characterization of its error rate under the linear reward setting. For the latter, we propose another general algorithm, GENPSI, which unifies and gen- eralizes existing bandit algorithms for both the standard and linear settings. Importantly, both GENSEC and GENPSI are designed accommodate general shared structures among prompts, thereby enhancing learning efficiency, particularly when the evaluation budget is limited.
We evaluate the performance of GENSEC and GENPSI on two summarization benchmarks: XSum and Mail. For best feasible prompt identification, GENSEC based algorithms recover over 80% and 90% of the utility of the optimal constrained prompt the two tasks, respec- tively, whereas the baseline methods achieve only 20-50%. For Pareto prompt set identification, GENPSI based algorithms recover more than 90% of the hypervolume of the ground-truth Pareto set, while the baselines remain in the low-to-mid 80% range.
2 RELATED WORKS
Single-objective prompt selection. InstructZero (Chen et al.] 2024) applics Bayesian optimization in the continuous space of soft prompts, while (Sbbatelal et al. (2024) uses Bayesian optimization
over hard prompts by modeling prompts as n-gram phrases. ZOPO (uu et al. 2024) specializes in selection from a fixed candidate set and argues that a locally optimal prompt can outperform generation-base algorithms. Bandit-based methods improve sample efficiency via adaptive alloca-
2025); TRIPLE (Shi tion and elimination (Shi et al. 2024 Lin al. 2024 Lin al. Kong al.
et al. 2024) casts selection as fixed- budget best-arm arm identification; INSTINC (Lin et al. 2024)
leverages NeuralUCB with transformer features optimize instructions: APOHF (Lin al.)) frames
human-in-the-loog selection as a dueling bandit over pairwise preferences; and EXPO (Kong et al.) 2025) addresses -tatioaatinariity in agentic settings with adversarial bandits.
Multi-objective prompt engineering. Multi-criteria prompt optimization has been receiving in- creasing attention due to its practical impact across various domains. Evolutionary approaches, such as EMO-Prompts (Baumann & Kramer 2024), InstOptima (Yang & Li 2023), and MOPO (Re- sendiz & Klinger, 2025) use LLM--riven mutation and crossover to generate candidate prompts with high-quality trade-offs. Beyond evolutionary search, MORL-Prome (Jafari et al. 2024) adapts multi-objective RL with Pareto-aware policy gradient, and GEPA (Agrawal et al.) 2025) combines natural-language reflection with Pareto-guided evolution. While those work aim achieve trade-
2

---

Published as a conference paper at ICLR 2026
offs among different metrics in prompt optimization, they mostly focus on prompt generation while adopting uniform sampling as the selection method.
For constrained prompt optimization, CAPO (Zehle et al. 2025 adds cost awareness by combining evolutionary search with length penalty, yielding prompts that balance task accuracy against token usage. Co-Pri Co-Prompt (Cho al., 2023) focuses token-wise prompt generation optimization, and uses another discriminator model to evaluate the generated token. To the best of our knowledge, there are currently no prompt optimization studies that consider hard constraints, which is key focus of our work.
Multi-objective bandits. Pareto identification in multi-armed bandits was first studied in the confideeee setting (Auer et al. 2016). In the fixed fixed-budget regime, Kone et al. (2024) intro- duced Empirical Gap Elimination (EGE), and showed that the misidentiifiattion probability decays exponentially with the budget, achieving the optimal rate up to constants, Kone et al. (2025) further investigated the linear bandits setting, while ZZuluaga et al. (2013) 2016) investigate the problem from Bayesian perspective. In the constrained bandits setting, regret minimization was investi- gated Kagrecha et al. (023);; Pacchiano et al. (202T), while pure exploration strategies have been studied in Faizal & Nair (2022); Bian & Tan (2025) recently. In summary, there has been active research on multi objectiveee bandits, providing a rich set of tools for principled prompt optimiza- tion. However, existing work primarily focuses on bandits with simple structures, which limits their applicability in practical scenarios. Our work builds on the bandit framework and extends it with ioplication-inspiree designs to address these gaps.
MULTI-OBJECTIVE PROMPT SELECTION
We first introduce the basic notations used in the prompt-assisted interactions with LLMs (Zhou ctt al. 2022. Chen et al. 2024 Shi et al. 2024). Let æ be prompt, D = {(q, a}} task dataset consisting of inputs q and reference answers a, and M black-box LLM that maps the prompt together with an input q to distribution over the output language space y. Given (z, q). the LLM generates outputs according y M(g; x)), where y y.
Due to the multi-criteria nature of prompt performance (Baumann Kramer 2024 Yang & Li 2023
Agrawal al. 2025). consider m objectives represented by evaluation functions
f - I, j -. m,
where each fj assigns numerical score to an LLM output E ) given a reference answer E y. For each prompt X, its expected performance vector
μ(x) E (g.a)>> By--(g=z)
fm a)) E RT.
(2)
Here, the inner expectation averages the stochasticity of the LLM given fixed input, while the outer expectation averages over the dataset. Thus yuzz summarizes how prompt x performs across all objectives average. In addition, assume that all metrics defined such that larger values indicate better performance.
Motivating example. Figure illustrates the evaluation of prompts on the XSum dataset using the Ilama3 model, where each point corresponds to a prompt's ' ROUGE score (x-axis) and brevity score (y-axis). These two metrics exhibit inherent trade- offs, motivating joint consideration for prompt optimization.
0.95
Breiiy Score
In this work, we focus on the problem of mulli-criteria prompt selection: given set of candidate prompts X' and evaluation metrics Jj. the objective is to identify a subset of prompts from X' that achieves the desired trade-offs. We consider this prob- lem under the following two settings: (i) best feasible prompt identification. and (ii) Pareto prompt set identification.
0.85
Dominated
0.75
0.08
0.10
0.12
0.14
0.16
ROUGE Score
Best feasible prompt identification. The first target arises when one objective designated as the primary performance metric (e.g., task accuracy), while the remaining objectives act
Figure ROUGE and Brevity.
Trade-offs hetween
3

---

Published as a conference paper at ICLR 2026
constraints (e.g., safety above threshold). Formally, let objective j be the primary objective
to maximize, and denote the constraints on the other objectives as (T, b= A prompt æ is feasible if
My (z)z) 2 TJ
Vj
(3)
The best feasible prompt is then defined as
arg max (1()) s.t. ZEX
[5(z) Vj
(4)
This formulation is especially relevant for safe or regulated domains where utility must be achieved under explicit constraints.
Pareto prompt set identification. The second target is to recover the Pareto prompt set, which is the set of prompts that is not strictly dominated by any other prompt, as defined in the following. Definition (Pareto Optimality). A prompt x E X is Pareto optimal if there does not exist another prompt x' X such that Py (x') 2 p2(()) for all {1,...,m) m) and pı522)) > (1(22) for at least one j.
The set of Pareto-optimal prompts is denoted X", and {u(x) : x E X*) the Pureto front. In the absence of explicit constraints, Pareto set identification is the most general target for multi-objective optimization, which captures the best achievable trade-offs among objectives.
Fixed budget constraint. In practice, prompt evaluations are costly because each trial requires querying LLM multiple data examples and metrics. Therefore, in this work, we consider fixed budget setting, where the total number of evaluations the optimization procedure is upper bounded by B. Then, given fixed budget constraint B, the learner's goal is to identify (i) the optimal feasible prompt x", or (ii) the Pareto set of prompts X²,, as accurate as possible.
4 PROMPT OPTIMIZATION VIA PURE-EXPLORATION BANDITS
Recent work (Shi et al. 2024 shows that prompt optimization can be formulated as a best arm identification (BAI) problem and solved efficiently by leveraging the rich toolbox from BAI multi- armed bandits. While extensive experiments demonstrate the remarkable performance improvement of such an approach over baselines for a single performance metric, to the best of our knowledge, leveraging bandits algorithms to solve the more general multi-objective prompt optimization has not been studied previously. To fill this gap, in the following, we formulate the multi-objective prompt optimization problem under fixed budget constraint as pure-exploration multi-objective bandits.
Specifically, we model the prompt set X' as the set of arms in a multi-armed bandits, and pulling an arm corresponds to evaluating a prompt X a randomly sampled input (q, a) E D. which produces an output ~ M(g; The evaluation metrics (ʃi (y, a), f2 a), fm (y, a)) then serve the stochastic reward vector observed for that pull. Thus, the expected reward of each arm is denoted as p(z), which captures the mean performance of prompt æ across all objectives.
Under the given budget constraint B, our objective is to leverage the algorithms from pure- exploration bandits to efficiently identify the optimal feasible prompt and the Pareto set of prompts (arms), respectively.
In practice, the candidate prompt set could be very large. Treating each prompt independently may not be very cost efficient, especially when the total budget limited. On the hand other, the candidate prompts may inherently have certain correlations, and exploiting such correlation can potentially speed up the learning process and improve the learning accuracy. Motivated by those observations, we introduce general bandits model to capture such inherent dependency among prompts.
Specifically, let Φ X Rd be known feature map that embeds given prompt æ to d-dimensional feature vector Φ(x). The expected reward of x, denoted as μ(x), is then equal to go ()))))). where ge Ed + th is function parameterized by an unknown parameter Ó. Since ge is shared across all prompts, the observations obtained by evaluating any of the prompts will contribute to the estimation of 0, potentially speeding up the learning process.
4

---

(i) Budget allocation. each round r starts from the active set A,-1 and a planned budget n,, The step determines which arms to be pulled for the given budget nt, Denote (x.(").... (( as the list of arms to pull. The budget allocation for the active arms can be flexible as long as sufficient Published as a conference paper at ICLR 2026
For ease of exposition, in the following, we assume 2, ie.., there two metrics for the prompt performance, denoted as Yl and 1/2, respectively. The algorithm design and analysis can be extended for general m.
BEST FEASIBLE PROMPT IDENTIFICATION
For best feasible prompt identification, the learner seeks prompt that maximizes primary objec- tive while satisfying feasibility conditions on a secondary criteria, under a fixed budget constraint. Under the corresponding bandits formulation, bandits algorithm Constrained Successive Rejects (CSR) (Faizal & Nair 2022) is shown to be able to obtain the optimal feasible arm with an expo- nentially decaying error probability for stochastic bandits.
5.1 GENERAL FRAMEWORK
Under the general bandits formulation, propose round based elimination framework. The process consists of R rounds, each having n, pulls. In total, has Σ 74 B. Each round begins with an active arm set A,-1, and at the end of each round, only L, arms will be kept. are determined beforehand through a SCHEDULER, such as Successive Re- jection (Audibert & Bubeck 2010) or Sequential Halving (Karnin et al. 2013). We set IR 1, which corresponds to the estimated best feasible prompt. As the process proceeds, the major tasks in each round are as follows.
(R, H 16 }
exploration on the active arms is performed (e.g.. uniformly sampling each arm, or adopting G- optimal design cover the feature space).
(ii) Arm pulling and evaluation. For each t E [n,]. sample (4t, ax) ~ D. query the LLM to generate y ~ M(q;x x.)), evaluate Y/ and obtain f(() = (f1(1,, at), f2(Ve, a,)). The new observations (,(2l9, will be included in the collected datasets X,, and Y,..
(iii) Reward estimation. An estimator will then utilize (Xx,, Y,) to estimate the unknown parameter 0, based on which the estimated performance ((x) can be obtained for each x E Ay-1- The esti- mation also be performed in flexible ways. In the simplest approach, sample means be used without accounting for prompt features. More efficient alternatives can developed based on the considered parameterization function go, e.g., (regularized) least squares.
(iv) Arm elimination. Due to the multi-objective setting, the arm elimination step should jointly consider the optimality and feasibility of the active arms. For that purpose, first forms the empirical feasible arm set F, by checking wether (2) > T and then selects an empirical best feasible arm a based on Pr, (x) from F,,. A key component for this step is to estimate the constrained gap for all active arms as follows
(x) min {max {T (2), (,,()))) - (2)r ,,2,, T}.
(5)
where x; the empirical best feasible arm in round The gap design comes from Faizal Nair (222),, which characterizes the empirical difficulty of classifying an arm as either infeasible or suboptimal.
Based on the estimated constrained gap, the learner then eliminates the arms that are determined to be infeasible or suboptimal, and keeps the 4, arms with the smallest (i) to form A,. It then proceeds to the next round. The algorithm is presented in Algorithm [ We note that all arms are treated independently, the round schedule follows Successive Rejects, and the evaluation budgets are allocated uniformly, then GENSEC recovers the Constrained Successive Rejection algorithm (CSR) (Faizal & Nair 2022).
5

---

Published as a conference paper at ICLR 2026
Algorithm 1 GENeralized Successive Elimination under Constraints (GENSEC)
1: Input: budget B, constraint threshold т, prompt set X, feature map o(.), dataset D
2: Initialization: Au + X: (R, (n, { (4-)-)) & SCHEDULER K B); Xo < 0, Yo +
3: for-=1 1==1: do
x._,) 4: (I:(2) (.(1),...,,,(a)))) )) <- ALLOOCATOR (T: 1
5: At each step & E {1...., ny }, pull arm x01) with feature o(x(0), collect evaluation f() and
update observations as X, + X u (o(x(0)) Yr t- Y (
6: Obtain estimator (x) ESTIMATOR(I; Xr. Yr), Vo E Ar-1
7:
Update empirical feasible arm set and empirical best feasible arm
F E A (2)(2)) > T} o t arg max (x) zef,
8:
Estimate constrained gap
(x) + min { {max - (1), (1,(),)) - (x) 12. -T},
Vo E Ar-1
9: Perform arm elimination: A, t ELIMINATOR (Ap-1: 4: (r()))
10: end for
11:
Output: Ar
5.2 THEORETICAL ANALYSIS WITH LINEAR REWARD FUNCTIONS
We instantiate the general framework special where the reward function (o(((=)) is linear both ((x) and 0, i.e., μπ() = ((x) 0, where Φ(x) E IR and 0 E Rdxm This recovers the classical linear bandits setting. The following theoretical guarantee can be obtained.
Theorem (Informal version Theorem 2 ). Assume total budget B 2 45d [log, d].
With SCHEDULER being Sequential Halving, ALLOCATOR using the G-optimal design (Sec- tion A.3.I. and ESTIMATOR based on least squares, the probability that Algorithm ! fails
to return x² satisfies Pr [x- & Ar] S 36 [log2 10 -expexp//1 positive constant, H max A and D; is the constrained gap defined as A. min fmax (T (22()) - un (t)) (2 T}.
H[ogg, RT where e₁ is
Compared to the existing upper bounds the stochastic bandit problem Faizal & Nair 2022), our result makes significant improvement in the dependency on K. Specifically, while the existing results exhibit a dependence of K33 in the leading coefficient, our upper bound only depends on loga K, greatly reducing the impact of K the eтror probability. Furthermore, although we adopt a different definition for H, both results show similar influence of the budget and the constrained gap the error upper bound.
Proof sketch of Theorem 1 At high level, the proof shows that the algorithm rarely eliminates the optimal feasible arm =" consists of the following major steps. Step 1: establish uniform con- centration bounds for the empirical estimates, which is derived from nelf-normalized concentration inequality for linear models as shown in Lemma] [ Step 2: use the uniform concentration bounds to show that any suboptimal or infeasible arm appears better than x² only with exponentially small probability (see Lemma 2 During this process, three types of arms are carefully considered: fea- sible but suboptimal arms, deceiver arms (infeasible but better than the optimal feasible arm on the primary objective), and infeasible sub-optimal arms, which brings more complicated failure modes compared with previous single-objectio analyses. Step 3: Lemma 3 argues that x" can only be eliminated if many such arms simultaneously misleading, which very unlikely. Finally, Step combines the error probabilities across all rounds via a union bound. This yields an error bound that decays exponentially in the budget B, up to logarithmic factors.

---

Published as a conference paper at ICLR 2026
6 PARETO PROMPT SET IDENTIFICATION
In this section, we investigate the Pareto set identification problem and propose an algorithm named Generalized Pareto Set Identification (GENPSI), which can be found in Section [ Compared with Algorithm [ GENPSI shares the same components such as budget allocation, arm pulling and eval- uation, and reward estimation. The major difference lies in the last component, i.e., arm elimination. Due to the different objectives between best feasible arm identification and Pareto set identification, we use the empirical Pareto gap (Kone et al. 2024) as the metric for arm elimination.
We denote the empirical Pareto set as X², and employ the following notations
(( v) min (v) (x)) iE =m]m)
M( u) = max (i(()) - Pe(()), =E[m)
8 (x) min min (M (z, v), M (y.x)), v=)+\(()
8 (2) min v
max (M, x), + max mvv.))) VEE
Then, the empirical Pareto gap is defined as
max m(x,y), min 8+ (x), (1)}, x x
x x z 8r,
(xx)
The Pareto gap measures the difficulty of classifying amm to be Pareto or sub optiomli
We note that GENPSI recovers the Empirical Gap Elimination (EGE) (Kone et al. (2024) for stochas- tic bandits and G-optimal Empirical Gap Elimination (GEGE) (Kone et al.) 2025) for linear bandits when the corresponding ALLOCATOR and ESTIMATOR are set in the same form.
7 EXPERIMENTS
Datasets. We evaluate the prompt selection algorithms on two standard summarization bench- marks: XSum (Narayan et al., 2018) and Mall (Hermann et al.) (0015). The XSum dataset contains approximately 227,000 documents paired with concise one-sentence summaries, whereas the CNN/DailyMail dataset comprises roughly 311,000 article-summary pairs with multi- sentence outputs.
Candidate prompt generation. We generate candidate prompts X' using LLaMA-3. For each dataset, 200 prompts are generated based on randomly sampled examples from the dataset (Zhou al. 2022). The generated prompts are then manually filtered to remove some completely irrelevant prompts and down-sampled to form the final prompt pool of size 100. Within the prompt pool, we further sample 50 and 30 prompts to form smaller candidate prompt sets. sets.
Models. We evaluate the performance of candidate prompts two LLMs: instruction-tuned LLaMA-3-8B 1--MA-3-BB-instruc and Gemma-7B-it. Given a prompt x and a query the LLM generates an output using greedy decoding with maximum of 512 new tokens, which will then be evaluated according the metrics below.
Metrics.
We evaluate LLM generated responses on two metrics: ROUGE-L Lin 2004), mea- suring the overlap with the reference summary, and Brevity score, measuring the token lengths. The details of the reward definition can be found in Section
Feature extraction. To facilitate the general bandits formulation, we use GPT-3.5-turbee to extract the embeddings of the prompts. Let e(x) R2 be the extracted embedding for prompt x X. We then perform principle component analysis (PCA) to obtain reduced feature representation. Let Ua E R denote the matrix of the top-d eigenvectors of the sample covariance of (e(x) The
reduced feature of is then ((x)
Ug (e(x) é) E Rdd where R Exex

---

Published as a conference paper at ICLR 2026
XSum Gemma-70 (K-100)
CRNIDM Uemma-800 3-88 IK=100)
XSum Uamm3 00 (K=100)
CNN/DM Gemma 70 (K=106)
102
40-
10
10
10
Budget (b)
Dudgect (s)
Budget 16)
Budget (D)
Figure 2: Average soft constrained reward vs. per-arm budget. Error bars denote 95% confidence intervals over 20 random seeds.
Table 1: Average soft constrained reward on XSum Gemma.
K
Method
b b=a
b 5
b
b 10
Uniform
0.015 0.010
0.000
0.000
0.030 + 0.013
0.037 0.014
30
CSR
0.117 0.013
0.137 = 0.007
0.144 + 0.000
0.143 + 0.000
MLP-CSR
0.123 + 0.010
0.139 = 0.002
0.140 + 0.002
0.142 + 0.001
Uniform
0.021 0.011
0.021 + 0.011
0.037 +.014
0.036 0.014
50
CSR
0.122 + 0.012
0.143 + 0.001
0.141 + 0.002
0.140 + 0.002
MLP-CSR
0.143 0.002
0.142 + 0.002
0.147 + 0.001
0.142 + 0.002
Uniform
0.021 + 0.011
0.066 0.016
0.037 0.014
0.044 + 0.015
100
CSR
0.134 + 0.007
0.141 = 0.002
0.142
0.143 + 0.002
MLP-CSR
0.139 0.002
0.142 + 0.002
0.145 0.001
0.147 0.001
7.1 BEST FEASIBLE PROMPT IDENTIFICATION
In this subsection, we evaluate our constrained prompt selection algorithm, GENSEC, where the objective is to maximize task utility under a prescribed brevity constraint. We instantiate GENSEC into two variants, namely, CSR and MLP-CSR.
CSR. We first treat prompts independently, and adopt Successive Rejection, uniform pulling and sample averaging as the Scheduler, Allocator and Estimator, respectively, under which GENSEC reduces to CSR.
MLP-CSR. For the general bandits setting, we use an MLP consisting of a ReLU neural network with one hidden layer of 30 hidden states to model the reward function go(-). We set the Scheduler to be Sequential Halving to reduce the training rounds.
Denote the final output of the algorithms å.. Then, define soft constrained reward of the à as un (+) if (2())= 2 0.9r; otherwise, it equals zero. We use this definition to tolerate slight violation of the constraint. In Figure we report the average soft constrained reward as function of the average budget per arm with K 100 prompts. We normalize the value by Pi (x"), where x" is the best feasible arm. We note that the proposed bandits based algorithms outperform the uniform baseline in almost all settings. The advantage is more significant when performing task CNN Dailymail on Llama3 (denoted as "CNN Dailymail Llama3') and performing task XSUM on Gemma (denoted as 'XSum- Gemma'), For both cases, when the average budget each arm b is sufficiently large, the proposed bandits based algorithms recover more than 80% and 90% of the utility of subject to the relaxed constraint, while the baseline only reaches 20% to 50% of that, respectively.
In Table 1 we present the soft constrained reward results by performing task XSum on Gemma. Across different prompt set sizes K, and per-arm budget b, both CSR and MLP-CSR consistently outperform the uniform pulling baseline. The uniform pulling baseline rarely finds a feasible near- optimal prompt, while algorithms can reliably find close-optimal prompt. Notably, MLP- CSR yields slightly higher average soft rewards than CSR, demonstrating the advantage of shared structure in reward functions.
8

---

Published as a conference paper at ICLR 2026
XSum GGmmma-78 (K=100)
XSum | Liama3-88 (K=100)
CNNDDM Gemmo-77 (K-100)
CNN/OM Liama3-88 (K=100)
TV Recwooed
05
85
Budge
Budget
EGE
+
MLPEEGE
+
Unifomm
Figure 3: Hypervolume recovery per-arm budget. Error bars denote 95% confidence intervals
over 20 random seeds.
Table 2: Hypervolume (HV) on CNN/DaillMail Llamma
K
Method
b 3
b
b
10
Uniform
0.1577 + 0.0039
0.1534 + 0.0051
0.1685
0.0028
0.1661
0.0037
30
EGE
0.1603 + 0.0049
0.1680 0.0028
0.1753
0. 0.0033
0.1744
0.0043
MLP-EGE
0.1632 + 0.0034
0.1688 + 0.0039
0.1803 = 0.0022
0.1727 + 0.0030
Uniform
0.1559 + 0.0029
0.1543 + 0.0031
0.1618
0.0023
0.1646 0.0031
50
EGE
0.1651 + 0.0023
0.1647 + 0.0022
0.1706
0.0032
0.1720 + 0.0023
MLP-EGE
0.1618 + 0.0033
0.1628 + 0.0027
0.1661 + 0.0028
0.1673 + 0.0026
Uniform
0.1519 = 0.0024
0.1579 + 0.0022
0.1624 = 0.0019
0.1631 + 0.0023
100
EGE
0.1503 = 0.0028
0.1639 + 0.0024
0. = 0.0020
0.1754 + 0.0022
MLP-EGE
0.1628 + 0.0024
0.1684 + 0.0020
0.1699 = 0.0023
0.1716 0.0023
7.2
PARETO PROMPT SET IDENTIFICATION
The proposed GENPSI framework for Pareto prompt set identification is also instantiated into two variants.
EGE. We first treat prompts independently, and adopt Successive Rejection, uniform pulling and sample averaging as the Scheduler, Allocator and Estimator, respectively, under which GENPSI reduces EGE.
MLP-EGE.
Following the same configuration of Scheduler and reward function as in MLP-CSR, instantiate GENPSI MLP-EGE.
To evaluate the performance of the algorithms on Pareto prompt set identification, we introduce metric called hypervolume (HV) (Knowles al. 2003). HV measures the Lebesgue volume of objective space dominated by the obtained Pareto set, which is a scaler indicator of the quality and diversity of trade-offs of the estimated Pareto set. HV is computed with respect to a reference point, which we set to the origin for both metrics. We also present the recovered HV as percentage of the ground-truth Pareto-set HV, which is obtained by exhaustively evaluating all prompts in the candidate pool.
In Figure 3 we report the results when prompt set size K 100. We note that both bandits based algorithms consistently outperform the bascline. When per-arm budget b low, MLP-EGE achieves the highest performance on average, indicating the advantage of exploiting shared parameters under GENPSI. When per-arm budget 8, 10, both elimination approaches recover about 90% HV of the ground-truth Pareto set, whereas the baseline recovers around the low-to-mid 80% range.
Table presents the average hypervolume XSum dataset with Gemma for varying K and b. Bandits based algorithms consistently outperform the baseline, indicating robustness of the proposed GENPSI framework. More comprehensive evaluation results can be found in Section C.4

---

Published as a conference paper at ICLR 2026
8 CONCLUSION
In this work, we established a principled connection between multi-objectivv prompt selection and the framework of multi-objective pure-exploration bandits, representing (to the best of our knowl- edge) the first formalization this problem in such setting. Within this framework, we addressed two fundamental problems: best feasible prompt identification and Pareto prompt set identification. To this end, we proposed two general algorithms, GENSEC and GENPSI, which were theoretically grounded and designed to exploit shared structures among prompts to improve sample efficiency un- der limited evaluation budgets. Extensive experiments on XSum and CNN/Dailyyaun Mail demonstrated the effectiveness of our approach. Our framework opened new opportunities for principled and scal- able prompt optimization under complex evaluation criteria. Future directions include extending our methods more diverse tasks and models, incorporating richer evaluation metrics such as fairness and efficiency, and exploring strategies for real-world, large-scale deployment.
REFERENCES
Lakshya A Agrawal, Shangyin Tan, Dilara Soylu, Noah Ziems, Rishi Khare, Krista Opsahl-Ong, Arnav Singhvi, Herumb Shandilya, Michael J Ryan, Meng Jiang, et al. Gepa: Reflective prompt evolution can outperform reinforcement learning. In NeurIPS 2025 Workshop on Foundations of Reasoning in Language Models, 2025.
Zeyuan Allen-Zhue Yuanzhi Li, Aarti Singh, and Yining Wang. Near-optimal design of experiments via regret minimization. In International Conference on Machine Learning, pp. 126-135. PMLR,
2017.
Jean-Y Audibert and Sébastien Bubeck. Best arm identification in multi-armed bandits. In COLT-23th Conference on learning theory-2010, pp. 13-p, 2010.
Peter Auer, Chao-Kai Kai Chiang, Ronald Ortner, and Madalina Drugan. Pareto front identification from stochastic bandit feedback. In Artificial intelligence and statistics, pp. 939-947, PMLR, 2016.
Jill Baumann and Oliver Kramer. Evolutionary multi-objective optimization of large language model prompts for balancing sentiments. In International conference the applications of evolutionary computation (part of evoStar), pp. 212-224. Springer, 2024.
Jie Bian and Vincent YF Tan. Asymptotically optimal linear best feasible arm identification with fixed budget. In Conference on Uncertainty in Artificial Intelligence, pp. 296-331. PMLR, 2025.
Stephen Brade, Bryan Wang, Mauricio Sousa, Sageev Oore, and Tovi Grossman. Promptify: Text- to-image generation through interactive prompt exploration with large language models. In Pro- ceedings of the 36th Annual ACM Symposium on User Interface Software and Technology, pp. 1-14, 2023.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
Sebastian Caldas, Peter Wu, Tian Li, Jakub Konečný, H. Brendan McMahan, Virginia Smith, and Ameet Talwalkar. LEAF: A benchmark for federated settings. CoRR, abs/1812.01097, 2018. URL
wwtgg/////////..//////// 01097
Lichang Chen, Jiuhai Chen, Tom Goldstein, Heng Huang, and Tianyi Zhou, Instructzero: efficient instruction optimization for black-box large language models6518. In Proceedings of the 41st International Conference on Machine Learning, pp. 2503-6518, 2024.
Jiale Cheng, Xiao Liu, Kehan Zheng, Pei Ke, Hongning Wang, Yuxiao Dong, Jie Tang, and Minlie Huang. Black-box prompt optimization: Aligning large language models without model training. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp. 3201-3219, 2024.
Sukmin Cho, Soyeong Jeong, Jeong yeon Seo, and Jong C Park. Discrete prompt optimization via constrained generation for zero-shot re-ranker. In Findings of the Association for Computational Linguistics: ACI. 2023, pp. 960-971, 2023.
10

---

Published as a conference paper at ICLR 2026
Mingkai Deng, Jianyu Wang. Cheng- Ping Hsich, Yihan Wang, Han Guo, Tianmin Shu, Meng Song, Eric Xing, and Zhiting Hu. Riprompt: Optimizing discrete text prompts with reinforcement learning. In Proceedings of the 2022 Conference Empirical Methods in Natural Language Processing, pp. 3369-3391, 2022.
Alexander R Fabbri, Wojciech Kryšcińiski, Bryan McCann, Caiming Xiong, Richard Socher, and Dragomir Radev. Summeval: Re-evaluating summarization evaluation. Transactions of the Asso- ciation for Computational Linguistics, 9:391-409, 2021.
Fathima Zarin Faizal and Jayakrishnan Nair. Constrained pure exploration multi-armed bandits with fixed budget. arXiv preprint ar Xiv:22211.1466. 2022.
Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, et al. The llama 3 herd of models. In Neural Information Processing Systems. Curran Associates, 2024.
Qingyan Guo, Rui Wang. Junliang Guo, Bei Li, Kaitao Song, Xu Tan, Guoqing Liu, Jiang Bian, and Yujiu Yang. Connecting large language models with evolutionary algorithms yields powerful prompt optimizers. The Twelfth International Conference on Learning Representations.
Karl Moritz Hermann, Tomas Kocisky, Edward Grefenstette, Lasse Espeholt, Will Kay, Mustafa Suleyman, and Phil Blunsom. Teaching machines to read and comprehend. Advances in neural information processing systems, 28, 2015.
Wenyang Hu, Yao Shu, Zongmin Yu, Zhaoxuan Wu, Xiaoqiang Lin, Zhongxiang Dai, See-Kiong Ng. and Bryan Kian Hsiang Low. Localized zeroth-order prompt optimization. Advances in Neural Information Processing Systems, 97:86309-86335, 2024.
Yasaman Jafari, Dheeraj Mekala, Rose Yu, and Taylor
Morl-prompt: An em- pirical analysis of multi-objective reinforcement learning for discrete prompt optimization. In Findings of the Association for Computational Linguistics: EMNLP 2024, pp. 9878-9889, 2024.
Anmol Kagrecha, Jayakrishnan Nair, and Krishna Jagannathan. Constrained regret minimization for multi-criterion multi-armed bandits. Machine Learning, (12(2)431-455) 2023.
Bongsu Kang, Jundong Kim, Tae-Rim Yun, and Chang-Fop Kim. Prompt-rag: Pioneering vec- tor embedding-free retrieval-augmented generation in niche domains, exemplified by korean medicine. arXiv preprint arXiv:2401. 11246, 2024.
Zohar Karnin, Tomer Koren, and Oren Somekh. Almost optimal exploration in aalti-armed bandits. In International conference machine learning, pp. 1238-1246. PMLR, 2013.
Joshua D Knowles, David W Corne, and Mark Fleischer. Bounded archiving using the lebesgue measure. In The 2003 Congress on Evolutionary Computation, 2003. CEC'03, volume 4, pp. 2490-2497. IEEE, 2003.
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. Advances in neural information processing systems, 35:22199 222113.. 2022.
Cyrille Kone, Emilie Kaufimann and Laura Richert. Bandit Pareto set identification: the fixed budget setting. In International Conference on Artificial Intelligence and Statistics, pp. 2548- 2556. PMLR, 2024.
Cyrille Kone, Emilie Kaufmann, and Laura Richert. Bandit Pareto set identification in multi- output linear model. In AISTATS 2025-8th International Conference on Artificial Intelligence and Statistics, 2025.
Mingze Kong, Zhiyong Wang, Yao Shu, and Zhongxiang Dai. Meta-prompt optimization for LLM- based sequential decision making. In ICLR 2025 Workshop Reasoning and Planning for Large Language Models, 2025.
Chin-Yers Lin. Rouge: A package for automatic evaluation of summaries. In Text summarization branches out, pp. 74-81, 2004.
11

---

Published as a conference paper at ICLR 2026
Xiaoqiang Lin, Zhongxiang Dai, Arun Verma, See-Kionge Ng. Patrick Jaillet, and Bryan Kian Hsiang Low. Prompt optimization with human feedback. In ICML 2024 Workshop on Models of Human Feedback for Al Alignment.
Xiaoqiang Lin, Zhaoxuan Wu, Zhongxiang Dai, Wenyang Hu, Yao Shu, See-Kiong Ng. Patrick Jail- let, and Bryan Kian Hsiang Low. Use your INSTINCT: Instruction optimization for LLMs using neural bandits coupled with transformers. In International Conference Machine Learning, pp- 30317-30345. PMLR, 2024.
Aman Madaan, Amrith Setlur, Tanmay Parekh, Barnabas Poczos, Graham Neubig, Yiming Yang, Ruslan Salakhutdinov, Alan W Black, and Shrimai Prabhumoye. Politeness transfer: A tag and generate approach. In Proceedings of the 58th Annual Meeting of the Association for Computa- tional Linguistics, pp. 1869-1881 2020.
Anay Mehrotra, Manolis Zampetakis, Paul Kassianik, Blaine Nelson, Hyrum Anderson, Yaron Singer, and Amin Karbasi. Tree of attacks: Jailbreaking black-box llms automatically. Advances in Neural Information Processing Systems, 37:61065-66 105, 2024.
Wenyi Mo. Tianyu Zhang, Yalong Bai, Bing Su, Ji-Rong Wen, and Qing Yang. Dynamic prompt op- timizing for text-to-image generation. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 16627-266333 2024.
Shashi Narayan, Shay B. Cohen, and Mirella Lapata. Don't give me the details, just the summary! topic-aware convolutional neural networks for extreme summarization. ArXiv, abs/1808. 087.08745, 2018.
Aldo Pacchiano, Mohammad Ghavamzadeh, Peter Bartlett, and Heinrich Jiang. Stochastic bandits with linear constraints. In International conference on artificial intelligence and statistics, pp- 2827-2835. PMLR, 2021.
Reid Pryzant, Dan Iter, Jerry Li, Yin Lee, Chenguang Zhu, and Michael Zeng. Automatic prompt optimization with "gradient descent" and beam search. In Proceedings of the 2023 conference on empirical methods in natural language processing, pp. 7957-7968, 2023.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, llya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 20199
2019.
Yarik Menchaca Resendiz and Roman Klinger. Mopo: Multi-objective prompt optimization for affective text generation. In Proceedings of the 31st International Conference on Computational Linguistics, pp-
2025.
Antonio Sabbatella, Andrea Ponti, Ilaria Giordani, Antonio Candelieri, and Francesco Archetti. Prompt optimization in large language models. Mathematics, 12(6))929, 2024.
Pranab Sahoo, Ayush Kumar Singh, Sriparn Saha, Vinija Jain, Samrat Mondal, and Aman Chadha. A systematic survey of prompt engineering in large language models: Techniques and applica- tions. arXiv preprini arXiv:2402.07927, 2024.
Sander Schulhoff, Michael Ilie, Nishant Balepur, Konstantine Kahadze, Amanda Liu, Chenglei Si, Yinheng Li, Aayush Gupta, HyoJung Han, Sevien Schulhoff, al. The prompt report: system- atic survey of prompt engineering techniques. arXiv preprint Xrxiv:2406.000 06608, 2024.
Chengshuai Shi, Kun Yang, Zihan Chen, Jundong Li, Jing Yang, and Cong Shen. Efficient prompt optimization through the lens of best arm identification. Advances in Neural Information Pro- cessing Systems, 111999446996888 2024.
Taylor Shin, Yasaman Razeghi, Robert Logan IV, Eric Wallace, and Sameer Singh. Autoprompt: Eliciting knowledge from language models with automatically generated prompts. In Proceedings of the 2020 conference on empirical methods in natural language processing (EMNLP), pp. 4222- 4235, 2020.
12

---

Published as a conference paper at ICLR 2026
Xinyu Tang, Xiaolei Wang, Wayne Xin Zhao, Siyuan Lu, Yaliang Li, and Ji-Rong Wen. Unleashing the potential of large language models as prompt optimizers: Analogical analysis with gradient- based model optimizers. In Proceedings of the AAAI Conference on Artificial Intelligence, vol- ume 39, pp. 18264425227 2025.
Chao Tao, Saúl Blanco, and Yuan Zhou. Best arm identification in linear bandits with linear di- mension dependency. International Conference on Machine Learning. pp. 4877-4886. PMLR, 2018.
Gemma Team, Thomas Mesnard, Cassidy Hardin, Robert Dadashi, Surya Bhupatiraju, Shreya Pathak, Laurent Sifre, Morgane Rivière, Mihir Sanjay Kale, Juliette Love, et al. Gemma: Open models based gemini research and technology. arXiv preprint arXiv:4403.08295 2024.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoe V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-24837 2022.
Wenrui Xu and Keshab K Parhi. A survey of attacks on large language models. arXiv preprint arXiv:2505.12567, 2025.
Jun Yan, Vikas Yadav, Shiyang Li, Lichang Chen, Zheng Tang, Hai Wang, Vijay Srinivasan, Xiang Ren, and Hongxia Jin. Backdooring instruction-tuned large language models with virtual prompt injection. In Proceedings of the 2024 Conference of the North American Chapter of the Associ- ation for Computational Linguistics: Human Language Technologies (Volume Long Papers), pp. 6065-6086, 2024.
Heng Yang and Ke Li. Instoptima: Evolutionary multi-objective instruction optimization via large language model-base instruction operators. In Findings of the Association for Computational Linguistics: EMNLP 2023, pp. 13593 13602, 2023.
Tom Zehle, Moritz Schlager, Timo HeiB, and Matthias Feurer. Capo: Cost-aware prompt optimiza- tion. In International Conference on Automated Machine Learning, pp. 18-1. PMLR, 2025.
Zhuosheng Zhang, Aston Zhang, Mu Li, and Alex Smola. Automatic chain of thought prompting in large language models. In The Eleventh International Conference on Learning Representations, 2023.
Yongchao Zhou, Andrei Ioan Muresanu, Ziwen Han, Keiran Paster, Silviu Pitis, Harris Chan, and Jimmy Ba. Large language models are human-level prompt engineers. In The eleventh interna- tional conference on learning representations, 2022.
Marcela Zuluaga, Guillaume Sergent, Andreas Krause, and Markus Püschel. Active learning for multi-objective optimization. In International conference on machine learning, pp. 462-470. PMLR, R, 2013.
Marcela Zuluaga, Andreas Krause, and Markus Püschel. e-PAL: An active learning approach to the multi- objectivee optimization problem. Journal of Machine Learning Research, 17(104):1-2,, 2016.
13

---

Published as a conference paper at ICLR 2026
APPENDIX
A BEST FEASIBLE PROMPT IDENTIFICATION
A.I SETTINGS AND NOTATIONS
In this section, we formally present the Linear Constrained Sequential Halving in Algorithm 2 We first recap the linear constrained bandit setting and notations. For the multi-objective bandit setting, we have the prompt arm set X' with | K, and the expected performance reward vector u(z), x E X. For each arm, there an associated feature ((x) R the linear constrained bandit setting, assume the number of reward dimensions is only two for simplicity and the expected rewards satisfy the linear structure,
#i (z) )(x) T((),
P2(x) = ((z)
(6)
where E Rd unknown. Moreover, for the theoretical results, further assume that the one-time evaluation results satisfy,
( = ( (12 uo(x()) + (m -12
(2(x()))
where (() is the evaluation reward of one pull of the arm (1) and f/i 7/2 are the independent g-sub-Gaussian noise.
(t) (8)
Definition -uuus-Gas A random variable X is
for all X E R.
E xx S exp ( (0²12)
A.2 CONSTRAINED GAP
Given constrained threshold the feasible set is denoted as F == {x E X p2(x) 2 r). The goal of the constrained bandit algorithm is to identify the optimal arm x",
arg maxzer (x)x), F 2,
arg maxxex #2(x), F Ø.
With the notations, we follow Faizal Nair (2022) to define the violation gap and sub-optimal gap as follows
viol(x) == max(T - u2(x), 0), subopt(x) == ui (1(")))))))))))) (I(x), where the latter is used only when F # Ø.
They characterize the difficulty to distinguish a prompt as infeasible or suboptimal. Then, the gap used classify an arm as infeasible or suboptimal is denoted
[max( viio(x)), subopt(x)), F Ø
8(x)
[x( p2(x),
F= 2.
Finally, note that the probability of failing to identify the optimal arm also includes the case where the optimal arm estimated as infeasible. Therefore, we define the constrained gap as
(xx min (0(z), (z(1) -7).
(8)
We also assume that the arms are indexed in ascending order of their constrained gaps, with the first arm corresponding to the optimal feasible arm, such that ((1) < A S ... ...SA A(K).
A.3 ALGORITHM DESIGN
We present the Linear Constrained Sequential Halving Algorithm for the linear reward setting in Algorithm 2 The algorithm is instantiated from GENSEC Algorithm [ by using the Sequential Halving (SH) scheduler, the G-optimal design allocator and the linear estimator.
14

---

Published as a conference paper at ICLR 2026
Algorithm 2 LINEAR CONSTRAINED SEQUENTIAL HALVING
1: Input: budget B, threshold prompt set X, feature map Φ(-), tolerance parameter
(0, 1/3
2: Initialization: An X; Xo 0, Yo 0
3: (R, (n, )r (4)))1) < SCHEDULER K B):
Sequential Halving R = [log2 KT, 4, =
K
[
2"
4: for r 1 to R do
5: Allocate nr pulls across active arm Ar-1 based on G-optimal design (Algorithm B):
(z(11, , (*+)) + G-OPTIMAL DESIGN A,
6: Pull the arms and collect the observation data:
X, (o(x())))s YER" (1(0)
7: (x) + ESTIMATOR o()), K,), Va E Ar-1:
4, (6(In,),..... (Ir,)))) B. a maximal linearly independent subset of (Ø(x) A.A.
V,, = X,, = V,,
0. - Y,,,Y, (=) = (x), (x)) <(x)
8:
Construct empirical feasible set and identify empirical optimal arm:
f, - (ar A (x) 7) i arg max Tú, (x) aeF.
9: Obtain empirical constrained gap:
8-( + max T - (i), (1, (1r
(1) = min (1), 02,((17) -T},
vi E Ar
10: Rank arms A,-1 in the increasing order of (,()) and keep the first 1, arms to form 4,
11: end for
12:
Output: Ar
A.3.1 G-OPTIMAL DESIGN
The G-optimal design follows Kone et al. (2025). achieving the same estimation error bound as in Lemma [ for multi-objective bandits. It employs entropic mirror descent solve the continuous relaxation of the G-optimal design problem, followed by an efficient rounding step to produce an approximate integer solution. These procedures adapted from Tao al. (2018) and Allen-Zhu et al. 2017). and are denoted by MD and ROUND, respectively.
The output N; of the rounding procedure indicates the number of pulls allocated for arm The corresponding budget allocation {a((t)) 1 can then be constructed accordingly. We present the subroutine below.
Algorithm G-OPTIMAL DESIGN (KONE AL., 2025)
1: Input: budget N, active set A, feature map o(-), tolerance e, parameter x 1/3)
2: (wsJie <- MD(A, o, e)
3: (N. & ROUND(N, (N, (w: A, A,
4: fort = to N do
(1) <- i, if E
N N₂)
5: end for
6: Output: (x(
15

---

Published as a conference paper at ICLR 2026
A.3.2 LINEAR ESTIMATOR
For the linear case, the estimator only relies on the data collected in the current round estimate 0. In round given the active arm A,-1, the arm pulled at step satisfies x(() E A and yields the observed outcome f(t), We define X, the design matrix obtained by stacking the feature vectors ((x(0) from round and Y, as the vector of the corresponding outcomes f())
)(x(1) ((
f())
f(2)
X, ==
E ERd
;=
E R
(
f(am)
In each round r, define the Gram matrix
V= X X, E Rdxd
Denoting 4, = [ ( A.)) ) Rd as a maximal linearly independent subset selected from (EE,, we can define the pesudo inverse
V = $, (V,
T
E ERddd
(9)
Then, the estimation becomes
0, = vt X,
(x(x) = 6(x) TO.
(10)
A.4 PROOF OF THEOREM
Before we proceed to prove Theorem 2 first introduce several key lemmas.
We first bound the estimation error in each round by following Lemma 2 of Kone et al. 20255).
Lemma (Adapted from Lemma in Kone al. 2025 ). Let k E 10,1/3 and N 2 5d,-1/k²? where d, din(span( (xx) A. A,),, O Rux Then, under Algorithm
2 for all 0 and
x A,-1,
P ( 0) ( 2() S 4exp (- aan.e" 2
(-
dr
where a 2(166K)02
Lemma Iindicates that, by applying the G-optimal allocator and the linear estimator, the estimated rewards concentrate around the true performance mean.
Next, leverage Lemma D to show Lemma 2 which bounds the probability that sub-optimal prompt is empirically better than the optimal arm.
Lemma 2. Assume that the best feasible arm is not eliminated prior to round r. Let my be the total allocated budget in round r. Then, for any arm i E Ar, define Gr(i) as the event that arm i is empirically better than the best feasible arm (i.e., arm 1) the end of round r, ie.,
Gr(1) = (1) < (7)1) or P2(11) <T}-
Then,
anr A2(1) A
((),()) < 12
4d,
Proof. Let (1 denote the event that arm is empirically feasible at the end of round r. Thus, we have
= PGG:)))-P
<))
2 (PGG,()) F+()) + exp (-ama(T- Poar (1)2()))/
16

---

Published as a conference paper at ICLR 2026
(6) x (L)) + 4exp ( (1)/d/
< (P(C)())))) + 4
anl
A (i)
(11)
4dl
where incquality (i) uses Lemma to bound r() (1) < T), and inequality (ii is based on the definition of (i).
The event G,(1) n (1) corresponds the case that arm is empirically feasible the end of round but worse than arm This implies that arm is empirically feasible and outperforms arm on the primary objective, i...
F(G,())) S (P2, (1) < (t))
To bound (1),(t) n (.)1), we further consider three possible cases.
Case 1: Armi is feasible suboptimal arm.
In this case, we have
B,)() $ (f), 2 (1))
= ((((,,)))) -m((i) - (f1, (1) - (1(1)) 2 (wi(1) - (1(1)}
s (L - (1) 2 (1(1) - (1)
+ P (1(11) (1) (i(1) - (1
2
2
where the last step follows from the fact that both (i) rn (i) and p1 (1) cannot be (1) and a subsequent union bounding argument.
greater than 2
Using Lemma we have
P (1) m1(1)= (1(1) (1(
2
(Mi (1) MI (1))²
$4.00 exp
-am,
4d,
Wilrr A 2?(i)
< 4 exp
4d,
and
[ (1(1) - -11,
(1(1) (1(
2
-an, (11(1) - 11 (1))2
$ 4. exee
4d,
anr 1²(i))
$ 4 exp
4d,
Thus, for this case,
an, A2
((G.())FF.1)) < <xpp
exp
(-4d, 4d,
Case 2: Arm is deceiver arm.
17

---

Published as a conference paper at ICLR 2026
This case corresponds to the situation where infeasible arm appears to be empirically feasible. In this case, we have
PP(F n Ba)
- P (1) 2 T)
PP (122,(1) (1) m2(1) 2 T 222(1)
1 exp
(ann (T v2(()))/d,))
(12)
(18)
S 4 4exp
(-am, (i))
- 4 - exp
(-am. 4d,
an,
A
where inequality (i) follows from Lemma and inequality (ii) follows from the definition of (i).
Case 3: Arm+ is an infeasible suboptimal arm.
Since A (i) & max {T - p2(1), (1) (i()), then
i) S F1 (1) μ4 (i) then this case follows from Case 1;
if ( S M2 (t), then this case follows from Case 2.
Put pieces together: Since for all three case, we have P(G,(1) & 8- exep (-an,- Plugging the result into Equation [II). we have
A2
2d,
P(G,()) S P(G. (( +expp {
anr a 2i 4d,
112exp {
an,
4dl
With Lemma we can further bound the probability of eliminating the best feasible arm in round. Lemma 3. The probability that the best feasible arm is eliminated on round satisfies
P(x" & Ar|x* E Ar-1) s 36 eepp {
aB 2
4 [log K] f
where i, arg m A(i).
Proof. In each round, we eliminate arms A,-1 to obtain A,, where |A, A the proof, we further consider A' as the & worst arms in Ar-1 and use N, to denote the number of arms in A'. whose empirical gap is smaller than (1).
K1 For
2"
By Lemma we have
B[N = Σ (()
REA
Ai
12 12-exp exp
0-,
4d,
VEA
B
12 exp
[og K
B
< |
max 12 exp
2
(EA-
Tog2 K
aB minie A, A
|4||
12 exp
[lgg K]
18

---

Published as a conference paper at ICLR 2026
Furthermore, applying Markov's inequality, get
3 B,E]
min A? aB
P
N
A
S 36-3666 - exp (- [logz K
3
x= is rejected at round r: there have to be most 2/Ar-1| arms in AG is empirically worse than the optimal arm. Thus, we have
P(x* & A,1a* E Ar-1)
2 P A -N, 5
=5(A41 A44
aB minic AC A A²
I 18d - exp
4 [log K'
which completes the proof.
With Lemmas to we are now ready to prove Theorem first state formal version of Theorem I as follows.
Theorem 2. Given a fixed set of K arms with the linear reward structure specified in Equa-
tions 6 and 7 under total budget B 2 45d [log2 d), the probability that Algorithm 2 fails to
output the best feasible arm x² is upper bounded by.
{
aB
P(x* Ar) S 36 [log2 KJ exp
{ 4 logg K H
where
1
2(1 + 6k)
H
max KE|K]
A
and A(i) is defined in Equation 8
Proof. By algorithm design, An contains only one arm. Thus, the error rate is equal to the prob- ability that the best arm survives the whole algorithm execution. By Lemma B and union bound, the probability that the best arm is eliminated one of the [log, K" rounds of the algorithm can be upper bounded as below.
P(r + x", Vo E Ar)
[log K1
aB minied, A?
36 exp
4 |loog K
aB Ai
< 36 [log, K
max exp iE[K]
[log K]
aB
36 flog, K] exp
(13)
llog K]
max A7
aB
36 flog, K]
llgg K H exp
(14)
B PARETO SET IDENTIFICATION
B. RESTATE THE GENPSI
For the GENPSI framework, the main difference from GENSEC is the design of gaps. In GENPSI, we use the Pareto gap, following Auer et al. (2016) and Kone et al. (2024). To define the gap, we first introduce the following defintions.
19

---

Published as a conference paper at ICLR 2026
Algorithm 4 GENeralized Pareto Set Identification (GENPSI)
1: Input: budget B, prompt set X' feature map 6(-), dataset D
2: Initialization: Au + X: (R, {n {4, (-)r=1) <- SCHEDULER(K, B); X, < 0, Yo + 0.
3: for =1 do
4: (z:(1)
x..)) (,(1),..,,,11...
<- ALLOCATOR (T: Ar-1).
5: At each step E (1,..., n, pull arm a(1) with feature o(x(1, observe evaluation f(), and
update observations as X, + X,-1 u (o(x(0)) Y, t- Y,-1 U (
6: Obtain estimator (x) ESTIMATOR(E:: (r; X Yr), Vo E Ar-1;
7:
Calculate the empirical dominating set
X = {s A E such that [Vi E [m], (x,) 2 P4. (2)) and E [m]] (,r((")) > (
8:
Calculate the empirical Pareto gap
max m (2, y), x x y min (z), 8- (x)), x R
(x)
where the m, 8+ 8 are all the empirical version based j1 Perform arm elimination: A, f- ELIMINATOR (A,-1, 4. (,)-)
9:
10: end for
Output: Ar
Definition 3 (Pareto Dominance). We say that arm Pareto-dominates y (denoted as u(x) > p(y)) if and only if
Vi, pz(x) 2 (v()) and Bi, px(x)) > p4(())
Definition 4 (Pareto set). For given set of arms X, the Pareto set is defined as
X {
E Hx' E X such that p(x') > ulx))
i.e, the Pareto set consists of all arms that are not dominated by any other arm.
Then, we define m(x, y) and M (x, y) for any prompt pair x, y E X' as follows:
m(a, y) = min (ju(v) - p=(x)), xE(m]
M y) = max (ue(T) - px(y)) sE <E(m)
These terms quantify the level of y dominating x.
a & X the Pareto gap is directly
A(x) max m(x, 8),
yE
which quantifies the greatest dominance from a Pareto prompt.
If & X*, we further denote
(x) =
min min(M((x,)) v), M (v,x)), yE (m)
(x) = min (max(M(v.x).00 + A(w)
x
and define the Pareto gaps for X
A(x) = min (5in()t()), 8 (x)).
In Algorithm 4 we use the empirical estimates of the Pareto gaps for arm elimination.
B.2 EXTENSION TO GENERAL m 2 2
Our framework extends naturally to settings with more than two objectives. The key quantities underlying our algorithms, such as the Pareto gaps and constrained gaps, can be generalized to m-dimensional objective spaces without changing the fundamental structure of the elimination or
20

---

Published as a conference paper at ICLR 2026
selection rules. The computational overhead associated with these extensions is modest: dominance checks and gap computations scale polynomially with m and remain efficient for the small number of objectives typically encountered in practice. Thus, the proposed algorithms retain both conceptual simplicity and computational tractability when applied to m > multi-objective prompt selection problems.
C EXPERIMENTS DETAILS AND RESULTS
C.I MODELS AND TEMPLATE
We uses two target models Gemma-7b-it (Team et al. 2024 and Llama3-88 Llama3-8b-instrus (Grattafirii et al. 2024). For the instruction models, we adopt the recommended system template as Figure
System instruction template
<lbegin_od of serrrin_o__eet/>>>> (exxt//<(start_eeeeee idd >system<| end madd_heder_idd
You are an intelligent assistant. Please finish the given task, answer with the output only and reply nothing else.
<prompt>
hiddderr_rd>
Figure 4: The system prompt template is used for both Gemma and Llama3.
In addition, to generate the prompt sets, we use the generation template as Figure
Prompt Generation Template
Input: [Input
Output: [Output1]
Input: [Input2]
Output: [Output2]
Please provide the instruction now.
Figure 5: Prompt generation with 3-5 examples.
C.2 METRICS USED IN SUMMARIZATION TASKS
In experiments, we mainly consider two metrics for the summarization task, the ROUGE and Brevity score.
ROUGE Score. The ROUGE (Lin) 2004) score is a widely used metric for the summarization task. It captures the token-wise similarity between two texts. We use its variant, ROUGE-Lsum, provided by the Hugging Face evaluate python package. In general, computes the longest com- mon subsequences between the generated text and the reference. and aggregates the results across sentences. captures the similarity between the generated summary from the LLM and the gold reference from the dataset.
21

---

Published as a conference paper at ICLR 2026
Brevity Score. The Brevity score function is artificial score to map the token lengths into the range [0, 1]. a piecewise function
1,
S
Tlow
Thigh
fB(ω)
Now
T
Thighs
Thigh Nlw
Thig
where æ is the token length and Now Thigh-
C.3 IMPLEMENTATION DETAILS WITH GENERAL REWARD STRUCTURE
We now specify the algorithm for general reward functions. We set the SCHEDULER to be Sequential Halving. uniform budget AL.LOCATOR adopted each round for ease of implementation.
For the ESTIMATOR, a neural network with parameter 0 is used to approximate the reward func- tion ga- each round r, we use the observations collected from the pulled arms to optimize 0. Specifically, we let
C, (0; = 1 (00( 2l111K
(15)
where the lg regularization is adopted prevent model overfitting. Then, the estimator obtains the estimates according to
0,- arg min C, (0: (r(x)) 98. (d(x)),
Ve Ar.
C.4 EXPERIMENTAL RSULTS
C.4.1 BEST FEASIBLE PROMPT IDENTIFICATION
We list our main results of best feasible prompt identification in Table 3 and Table
C.4.2 PARETO PROMPT SET IDENTIFICATION
Here, we list our main results of Pareto prompt set identification in Table 5 and Table 0
C.5 ABLATION STUDIES
C.5.1 DISTRIBUTION OF PROMPT OBJECTIVES
We visualize the objective distributions of the generated prompts to highlight the trade-off between the two metrics and validate the reasonableness of our prompt-generation process and experimen- tal design.
Figure 6a| shows the objective distribution of 100 generated prompts used in our main XSum experiments. The trade-off between the two metrics is clearly visible, demonstrating that identify- ing the Pareto-optimal prompts or the optimal feasible prompt is indeed a meaningful task this environment.
We further extend the prompt set to 1000 candidates in Figure 6b For this larger pool, no manual filtering is applied. Comparing the figures, observe that manual filtering primarily removes prompts that perform poorly on both Brevity and ROUGE, while preserving the overall structure of the distribution. Moreover, the Pareto-front shapes in both figures are similar, indicating that manual filtering does not materially alter the key characteristics of the candidate prompt set.
C.5.2 VARYING EVALUATION BUDGET
We next analyze how performance changes as the evaluation budget per seeeptnnnlection run in- creases.
22

---

Published as a conference paper at ICLR 2026
0.18
0.15
ROUGEE Store
0.13
0.10
ROUICE
0.10
0.08
0.05
Other points
Other points
ooretol
Pareto optimal
0.00
Brevity Score
Brevity Score
(a) 100 prompts
(b) 1000 prompts
Figure 6: Distributions of the objectives for generated prompts on Xsum.
Average Hypervolume (K) vs Bueget
Avorage Constroinad Reword (%0 vs Budget
100
20
85
Peni Freee
00
Parce.U Uh
Desttrenol.Ur
va2.con
10
15
20
25
30
Dadget
Dudgge
Figure 7: Average recovered hypervolume (%) and constrained reward on XSum using Llama-3.
23

---

Published as a conference paper at ICLR 2026
Table 3: Average soft constrained reward on XSum.
K
Method
5
b =
10
Gemma-7B
Uniform
0.015 0.010
0.000 = 0.000
0.030 + 0.013
0.037 + 0.014
30
CSR
0.117 0.013
0.137 + 0.007
0.144 + 0.000
0.143 + 0.000
MLP-CSR
0.123 0.010
0.139 + 0.002
0.140 + 0.002
0.142 0.001
Uniform
0.021 + 0.011
0.021 = 0.011
0.037 + 0.014
0.036 + 0.014
50
CSR
0.122 0.012
0.143 = 0.001
0.141 + 0.002
0.140 0.002
MLP-CSR
0.143 0.002
0.142 = 0.002
0.147 0.001
0.142 0.002
Uniform
0.021 0.011
0.066 = 0.016
0.037
0.044 - 0.015
100
CSR
0.134 0.007
0.141 = 0.002
0.143 0.002
MLP-CSR
0.139 + 0.002
0.142 = 0.002
0.145 0.001
0.147 = 0.001
Llama3-8B
Uniform
0.048 + 0.016
0.069 = 0.019
0.080
0.089 + 0.020
30
CSR
0.161 0.003
0.154 = 0.004
0.149 0.003 0.148 0.002
MLP-CSR
0.143 + 0.003
0.126 = 0.010
0.149 = 0.002
Uniform
0.063 0.018
0.045 + 0.017
0.051 0.018
0.078 0.019
50
CSR
0.144 0.011
0.134 = 0.010
0.122
0.157 = 0.002
MLP-CSR
0.141 + 0.008
0.151 = 0.003
0.154
0.156 + 0.002
Uniform
0.113 0.015
0.134 + 0.010
0.123 + 0.012
0.141 0.009
100
CSR
0.141 + 0.003
0.144 + 0.008
0.153 + 0.002
0.154 + 0.002
MLP-CSR
0.124 + 0.001
0.144 + 0.008
0.158 + 0.003
0.157 + 0.002
Figure illustrates how the recovered hypervolume changes increase the evaluation budget for both our methods and the baselines. As expected, all algorithms benefit from larger budgets, but methods consistently outperform the uniform-pulling baseline across all settings. This confirms that increasing the budget does not alter the overall conclusions. In the main experiments, we focus on smaller budgets in order highlight that our algorithms remain effective even in the low-budget regime, which is the setting of primary interest.
C.5.3 EXPERIMENTS WITH AN EXPANDED CANDIDATE PROMPT POOL
We next examine how the algorithms behave when we increase the size of the candidate prompt pool.
Average Hypersotume [N) Buaget
Average Constramed Reward vs Budget
1.03
Carafru
65
Figure 8: Average recovered hypervolume (%) and average constrained reward (%) with 1000 can- didate prompts on XSum using Llama-3.
24

---

Published as a conference paper at ICLR 2026
Table Average soft constrained reward on CNN/DailyMail.
K
Method
b =
b b=8 8
10
Gemma-7B
Uniform
0.021 + 0.014
0.032 = 0.017
0.021 0.014
0.021 = 0.014
30
CSR
0.081 + 0.018
0.134 + 0.020
0.153 0.012
0.166 + 0.010
MLP-CSR
0.138 0.016
0.164 + 0.011
0.164 + 0.005
0.163 0.005
Uniform
0.007 + 0.007
0.020 = 0.013
0.020 = 0.013
0.000 + 0.000
50
CSR
0.091 0.019
0.161 0.013
0.161 + 0.010
0.167 + 0.011
MLP-CSR
0.146 + 0.015
0.162 = 0.008
0.153 = 0.006
Uniform
0.015 0.015
0.045 = 0.022
0.000 0.000
0.015 - 0.015
100
CSR
0.088 0.023
0.015 = 0.015
0.062 0.022
0.032 0.021
MLP-CSR
0.032 = 0.020
0.045 = 0.027
0.032 = 0.020
0.072 0.026
Llama3-8B
Uniform
0.000 0.000
0.000 = 0.000
0.008 0.008
0.000 + 0.000
30
CSR
0.157 0.002
0.136 0.015
0.148 0.011
0.154 0.009
MLP-CSR
0.142 = 0.011
0.126 = 0.015
0.142
0.154 = 0.004
Uniform
0.016 + 0.011
0.008 0.008
0.010 0.010
50
CSR
+1144
0.157 = 0.009
0.155 0.009
0.165 0.003
MLP-CSR
0.144 0.005
0.155 = 0.004
0.160
0.160 = 0.004
Uniform
0.019 + 0.013
0.044 + 0.017
+
0.018 + 0.012
100
CSR
0.123 + 0.014
0.138 + 0.011
0.151 + 0.008
0.160 + 0.003
MLP-CSR
0.134 + 0.011
0.154 + 0.003
0.154 0.003
0.160 + 0.003
Figure reports the recovered hypervolume when scaling the candidate pool to 1000 prompts under different evaluation budgets. We observe that MLP-EGE performs best in this larger-pool setting, and EGE outperforms the uniform baseline when the budget is sufficiently large. These results indicate that our algorithms remain robust the prompt pool grows substantially in size.
C.5.4 VARYING CONSTRAINT
Finally, we vary the constraint threshold and track the feasible average reward under different con- straints in Figure 9 indicates that our proposed algorithms consistently outperform the uniform baseline, and the choice of constraint does not compromise the effectiveness of our algorithms.
Awcrede Deveerdv vo Burtett On Bett
Arpsec Soward Bubiic Iith Encr Zart
Avcuect Senurd Buthact Sart
Teaes coama cond
PLY C1R
00
(a) Constraint = 0.6
(b) Constraint = 0.5
(c) Constraint = 0.4
Figure 9: Feasible average reward vs. per-armed budget on XSum using Llama3 with varying constraints.
C.6 COMPUTING RESOURCES AND COSTS
Our experiments are conducted on a server equipped with an AMD EPYC 9554 CPU, 755 GiB of system memory, and four NVIDIA H100 PCIe GPUs (80 GiB HBM each; driver 550.144.03)
25

---

Published as a conference paper at ICLR 2026
Table 5: Hypervolume (HV) on XSum.
K
Method
b =5 5
b =
b 10
Gemma-7B
Uniform
0.1105 = 0.0019
0.1127 + 0.0021
0.1165 - 0.0013
0.1173 + 0.0012
30
EGE
0.1115 + 0.0020
0.1172 + 0.0014
0.1188 = 0.0015
0.1193 + 0.0013
MLP-EGE
0.1147 + 0.0021
0.1138 + 0.0023
0.1172 + 0.0018
0.1195 + 0.0015
Uniform
0.1105 = 0.0023
0.1169 + 0.0019
0.1181 = 0.0017
0.1192 + 0.0014
50
EGE
0.1126 = 0.0028
0.1180 + 0.0018
0.1207 = 0.0019
0.1212 + 0.0016
MLP-EGE
0.1117 0.0024
0.00225
0.1174 = 0.0018
0.1187 + 0.0012
Uniform
0.1007 = 0.0013
0.1023 = 0.0016
0.1084 = 0.0017
0.1126 = 0.0014
100
EGE
0.1085 = 0.0013
0.1187 = 0.0010
0.1218 = 0.0007
0.1219 = 0.0007
MLP-EGE
0.1138 0.0012
0.1179 0.0013
0.1216 = 0.0009
0.1220 + 0.0009
Llama3-8B
Uniform
0.1433 + 0.0026
0.1481 + 0.0023
0.1472 = 0.0031
0.1493 + 0.0031
30
EGE
0.1614 0.0008
0.1496 = 0.0022
0.1535 = 0.0031
0.1560 = 0.0015
MLP-EGE
0.1488 = 0.0026
0.1496 = 0.0031
0.1577 = 0.0019
0.1548 = 0.0017
Uniform
0.1500 0.0022
0.1557 + 0.0024
0.1586 = 0.0020
0.1585 + 0.0021
50
EGE
0.1626 = 0.0004
0.1587 + 0.0023
0.1596 = 0.0019
0.1604 + 0.0020
MLP-EGE
0.1520 = 0.0020
0.1552 + 0.0022
0.1595 = 0.0013
0.1616 + 0.0021
Uniform
0.1423 + 0.0028
0.1443 + 0.0016
0.1489 = 0.0022
0.1516 + 0.0021
100
EGE
0.1542 + 0.0028
0.1549 + 0.0016
0.1594
0.0019
0.1570 + 0.0021
MLP-EGE
0.1507 + 0.0024
0.1574 + 0.0027
0.1573 = 0.0024
0.1611 + 0.0016
running CUDA 12.4.131. We employ Gemma and Llama-3 in quantized, inference-only settings. Generally, the experiments are expected to be reproduced on a server with over 20G GPU memory.
D LANGUAGE MODEL USAGE IN PAPER WRITING DISCLOSURE
ChatGPT' 5 used during the writing of the paper, mainly for paraphrasing the sentences, improving the grammar, reorganizing the sentences in paragraphs, and generating few paragraphs based human-provide outlines. All the generated texts are reviewed and revised by humans. All technical claims, definitions, algorithms, theorems, and proofs are written by humans.
26

---

Published as a conference paper at ICLR 2026
Table 6: Hypervolume (HV) CNN/Daily.Mail.
K
Method
b 3
b 5
b = 8
b 10
Gemma-7B
Uniform
0.1345 + 0.0036
0.1393 + 0.0029
0,1484 0.0019
0.1459 + 0.0021
EGE
0.1327 = 0.0038
0.1458 + 0.0026
0.1472 = 0.0023
0.1453 + 0.0036
MLP-EGE
0.1441 + 0.0029
0.1499 + 0.0019
0.1505 = 0.0016
0.1505 + 0.0019
Uniform
0,1310 = 0.0038
0,1390 + 0.0023
0.1414 = 0.0021
0.1429 = 0.0020
50
EGE
0.1334 = 0.0032
0.1413 = 0.0020
0.1455 = 0.0024
0.1445 = 0.0019
MLP-EGE
0.1358 = 0.0032
0.1430 + 0.0017
0.1434 = 0.0020
0.1463 + 0.0016
Uniform
0.1280 = 0.0015
0.1305 + 0.0015
0.1325 = 0.0017
0.1342 + 0.0018
100
EGE
0.1279 = 0.0014
0.1342 = 0.0016
0.1343 = 0.0016
0.1411 = 0.0013
MLP-EGE
0.1316 + 0.0016
0.1336 + 0.0019
0.1379 = 0.0021
0.1408 + 0.0015
Llama3-8B
Uniform
0.1577 0.0039
0,1534 + 0.005
0.1685 = 0.0028
0.1661 + 0.0037
30
EGE
0.1603 + 0.0049
0.1680 + 0.0028
0.1753 = 0.0033
0.1744 1: 0.0043
MLP-EGE
0.1632 = 0.0034
0.1688 + 0.0039
0.1803 = 0.0022
0.1727 = 0.0030
Uniform
0.1559 + 0.0029
0.1543 + 0.0031
0.1618 + 0.0023
0.1646 + 0.0031
50
EGE
0.1651 + 0.0023
0.1647 + 0.0022
0.1706 = 0.0032
0.1720 + 0.0023
MLP-EGE
0.1618 + 0.0033
0.1628 + 0.0027
0.1671 = 0.0028
0.1673 + 0.0026
Uniform
0.1519 + 0.0024
0.1579 + 0.0022
0.1624 + 0.0019
0.1631 + 0.0023
100
EGE
0.1503 + 0.0028
0.1639 + 0.0024
0.1690 + 0.0020
0.1754 + 0.0022
MLP-EGE
0.1628 0.0024
0.1684 + 0.0020
0.1699 + 0.0023
0.1716 + 0.0023
27


Reviews:
[{"review_id": "YOlwB3VQMI", "reviewer": "Reviewer_NCGw", "summary": "This paper investigates the multi-objective prompt selection problem under two settings: Pareto prompt set recovery and best feasible prompt identification. The authors treat the prompt selection problem as a bandit problem and develop a multi-objective bandit algorithm. The experimental results demonstrate that the proposed method outperforms baseline methods on two tasks.", "questions": "- How is the performance of the proposed method when the budget and candidate prompt pool size are large?\n- Could you explain the reason that the current experimental settings are chosen (e.g., datasets and baselines)?\n- Please describe a practical use case where the proposed method is more effective than other existing prompt optimization (generation) methods.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- Focusing on multiple evaluation criteria in prompt selection is convincing, as it reflects practical scenarios better than single-objective settings.\n- The experimental evaluation demonstrates that the proposed method outperforms baseline methods on two tasks.", "weaknesses": "- The proposed method requires a pre-defined candidate prompt set, and its performance is limited by the quality of the candidate prompt set. However, how to construct a good candidate prompt set is not discussed in this paper.\n- In the experiment, the candidate prompt pool is up to 100, which seems relatively small. It is unclear whether the proposed method works well when the candidate prompt pool is large.\n- The budget $B$ considered in the experiment is small (up to 10). How is the performance of the proposed method when the budget and candidate prompt pool size are large?\n- The experimental comparison is conducted only with a simple baseline and the variants of the proposed method. Comparison with existing prompt optimization methods may be helpful in clarifying the absolute effectiveness of the proposed method.\n- Only two datasets (XSum and CNN/DailyMail) are considered in the experiment. It would be better to include more datasets to verify the effectiveness of the proposed method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "HiGMXWi42j", "reviewer": "Reviewer_BAtQ", "summary": "The paper frames multi-criteria prompt selection as pure-exploration multi-objective bandits, targeting both best feasible prompt and Pareto set recovery. It proposes two elimination frameworks GENSEC and GENPSI respectively. In the linear case, the paper proves an exponentially decaying misidentification bound with only logarithmic dependency in K. Experiments on XSum and CNN/DailyMail with Llama-3-8B-Instruct and Gemma-7B-IT show consistent gains over a uniform baseline.", "questions": "How exactly is the “ground-truth Pareto set” computed for normalization?\n\nCan you add weighted sum +BAI, and evolutionary multi-objective prompt optimizer as baselines?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper moves beyond single-metric prompt selection to an explicit multi-objective setup, which is well motivated for practical problem. \n\nThe paper provide theoretical error bound for linear rewards.", "weaknesses": "In experiments, comparisons are largely to a uniform allocator,  there is no multi-objective prompt optimization baselines, such as weighted sums with single-objective BAI or recent evolutionary multi-objective prompt optimizers mentioned in sec. 2. \n\nHV is “normalized by the ground-truth Pareto set,” but the procedure to obtain that ground truth is not fully specified. \n\nTypo: in line 128, should be  \"Let $x$ be a prompt\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "gOoiQtPEBr", "reviewer": "Reviewer_pHhY", "summary": "This paper addresses multi-objective prompt optimization for large language models (LLMs) by formulating it as a pure-exploration multi-objective bandits problem. The authors study two fundamental settings: (1) best feasible prompt identification, where one objective is maximized subject to constraints on others, and (2) Pareto prompt set identification, where the goal is to recover all non-dominated prompts. They propose two general algorithms, GENSEC and GENPSI, which can exploit shared structure among prompts via feature representations. For the linear reward case, they provide theoretical guarantees showing exponentially decaying error probability with improved dependency on the number of prompts K (from K³ to log K). Experiments on XSum and CNN/DailyMail summarization benchmarks with LLaMA-3 and Gemma models demonstrate superior performance over uniform baseline methods.", "questions": "1. Can you provide experiments with 1000+ initial prompts to demonstrate the method's effectiveness when exhaustive evaluation is infeasible?\n2. What specific advantages does the bandit formulation provide over off-the-shelf HPO methods like Bayesian optimization for this problem?\n3. Can you demonstrate the method on real safety or fairness constraints?", "limitations": "", "rating": 2, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "1. The paper makes a valuable connection between multi-objective prompt selection and the multi-objective bandits framework, which is the first systematic attempt to leverage bandit algorithms for multi-criteria prompt optimization.\n2. The paper provides theoretical analysis for the linear reward setting, which is a significant theoretical improvement.\n3. The work addresses a real and important problem in prompt engineering where multiple conflicting objectives (e.g., accuracy vs. brevity, coherence vs. faithfulness) need to be balanced.", "weaknesses": "1. Once prompts are mapped to feature vectors (e.g., using GPT-X embeddings), the problem proposed in this paper becomes a standard gradient-free optimization problem (aka hyperparameter optimization - HPO). The authors apply one of gradient free optimization methods (multi-objective bandit) to this vectorized representation and record theoretical and empirical analysis. While such application papers have value, they require much more extensive empirical validation to justify publication.\n2. In empirical evaluation, authors compares against random/uniform pulling. For a fair evaluation, the method must be compared with other prompt optimization engines (e.g., InstructZero, ZOPO, EMO-Prompts, InstOptima) under the same fixed evaluation budget (number of examples per forward pass).\n3. Testing on only 30-100 prompts is very small - one could simply evaluate all prompts exhaustively at this scale. Real-world prompt selection involves choosing from thousands or tens of thousands of candidates and it is important to show the method works in this setting.\n\nMinor weaknesses:\n-  Gap between theoretical linear case and practical MLP implementation not well explained\n- Missing discussion on scalability with number of objectives m > 2\n- Prompt generation via LLM + manual filtering introduces selection bias", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "Th317UA6Lq", "reviewer": "Reviewer_i6FQ", "summary": "The paper frames multi-objective prompt selection as a pure-exploration bandit problem under a fixed evaluation budget, with two tasks: best feasible prompt identification and Pareto prompt set identification. It introduces two round-based frameworks: GENSEC for the constrained task and GENPSI for the Pareto task, and in the linear shared-feature case provides a bound where the misidentification probability decays with budget and the dependence on the number of prompts improves from cubic to logarithmic, given specific choices of scheduler, allocation design, and estimator. Experiments are conducted on summarization tasks (XSum and CNN/DailyMail), using ROUGE-L F1 as utility and a brevity score as the second objective. After generating candidate prompts, filter them and down-sample the remainder into pools of size 100, 50, or 30. In practice the paper evaluates instantiated variants: for the constrained task, CSR and MLP-CSR as reductions of GENSEC; for the Pareto task, EGE and MLP-EGE as reductions of GENPSI. Figures report average soft-constrained reward versus per-arm budget and hypervolume recovery versus per-arm budget.", "questions": "1. Can you add at least one non-summarization task and one additional objective (e.g., safety, factuality, latency or cost)? If not, justify why summarization with two metrics is representative.\n2. Please ablate elimination margin and thresholding: compare variants of the constrained elimination margin; sweep the soft-constraint factor instead of fixing it.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The problem setup shows meaningful originality: framing multi-objective prompt selection under a fixed budget and then applying established bandit-style methods to this setting is practical and likely useful in real evaluation pipelines.\n2. The theoretical analysis is solid, with clearly stated assumptions, a clean proof structure, and a bound that is easy to interpret within the stated setting.\n3. The paper is well written and organized; the problem, algorithms, and evaluation protocol are presented clearly and are easy to follow.", "weaknesses": "1. Experimental scope and objectives are too narrow. All experiments are on summarization only, and every result uses just two objectives: ROUGE-L for utility and a brevity score for length control. There are no tasks beyond summarization (for example QA, dialogue, style transfer, code, safety-critical instruction following), and no additional objectives that typically motivate multi-objective selection in practice (for example safety, factuality, latency, monetary cost). Because both chosen objectives are summary-specific and tightly coupled to output length, the evidence does not establish that the approach generalizes to broader prompt-selection settings or to richer multi-objective trade-offs.\n2. Method-level novelty is limited; evaluated variants are reductions of existing algorithms. In the constrained setting the implementation reduces to CSR; in the Pareto setting it reduces to EGE (and related elimination variants in the linear case). The paper’s contribution is therefore mainly a problem framing and a unifying wrapper, rather than a new selection algorithm. The linear-case theory is helpful but tied to specific design choices and is not shown to drive the practical wins in the non-linear instantiations.\n3. Missing ablation on elimination margin and thresholding. The paper fixes both the constrained elimination margin and the soft-constraint factory. Without a sensitivity study of these choices, it is unclear whether the observed gains are robust or driven by a particular margin/threshold setting.\n4. In the Pareto experiments, hypervolume gains over uniform are small and inconsistent, which weakens the claim that shared structure or the framework provides broad advantage. In the “maximize task utility under a prescribed brevity constraint” experiments, uniform cannot purposefully satisfy the brevity threshold and therefore predictably underperforms any elimination method that can focus on constraint-satisfying prompts; this makes the superiority of CSR unsurprising and less persuasive as evidence of algorithmic merit. These results would be more convincing with strict feasibility curves, violation rates, and comparisons to stronger multi-objective baselines (for example evolutionary multi-objective prompt search) under the same candidate pool and budget.\n5. In the first paragraph of Section 3, the text says “Let a be a prompt,” but throughout the paper prompts are denoted by x, while a denotes the reference answer in input pairs (q, a).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": {}}]

Author rebuttal:

Decision: Accept (Poster)