🤖 machine learning

Efficient Multi-objective Prompt Optimization via Pure-exploration Bandits

This paper addresses the multi-faceted nature of prompt performance by framing prompt selection as a multi-objective pure-exploration bandit problem, proposing novel algorithms for Pareto set recovery and best feasible prompt identification that are theoretically guaranteed and empirically validated to outperform existing baselines across multiple large language models.

Original authors: Donghao Li, Chengshuai Shi, Weijuan Ou, Cong Shen, Jing Yang

Published 2026-05-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Donghao Li, Chengshuai Shi, Weijuan Ou, Cong Shen, Jing Yang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a chef trying to find the perfect recipe for a new dish. You have a massive cookbook with thousands of potential recipes (prompts), but you only have a limited amount of time and ingredients (a "budget") to test them.

In the world of Large Language Models (LLMs), these "recipes" are the instructions we give the AI. The problem is that a "good" recipe isn't just about taste (accuracy); it also needs to be quick to cook (brevity), healthy (safety), and cheap to make (cost). Most previous methods tried to find the best recipe by looking at just one thing, like taste. But in real life, you often have to balance trade-offs: the tastiest dish might take too long to cook, or the fastest one might taste bland.

This paper, titled "Efficient Multi-Objective Prompt Optimization via Pure-Exploration Bandits," proposes a smarter way to find the best instructions for AI when you have to juggle multiple goals at once, all while running out of time.

Here is the breakdown of their approach using simple analogies:

1. The Problem: The "Taste vs. Speed" Dilemma

The authors point out that evaluating an AI prompt is like judging a car. You can't just look at how fast it goes (accuracy); you also need to check how much gas it uses (brevity) or if it's safe (constraints).

The Old Way: Previous methods tried to combine all these factors into a single score (like saying "Speed minus Gas Cost"). This often misses the nuance. Sometimes you want the fastest car, even if it drinks gas, as long as it doesn't explode (safety constraint).
The New Goal: The paper wants to find two specific things:
1. The Best Feasible Prompt: The absolute best recipe that still meets a strict safety or speed limit (e.g., "Find the tastiest dish that takes under 10 minutes").
2. The Pareto Set: A menu of "best possible trade-offs." These are recipes where you can't improve one thing (taste) without making another thing worse (speed). It's a list of the top contenders that represent the best balance.

2. The Solution: The "Tasting Menu" Strategy (Bandits)

The authors treat this problem like a game show called a "Multi-Armed Bandit." Imagine a row of slot machines (the prompts). You have a limited number of coins (the budget) to pull the levers. You want to find the best machine without wasting all your coins on the losers.

They introduce two new algorithms to manage this game:

A. GENSEC: The "Elimination Game" for Constraints

Think of this as a tournament bracket for finding the Best Feasible Prompt.

How it works: You start with all 100 recipes. You taste a few of each.
The Twist: In every round, you immediately throw away the recipes that are clearly too slow (violating the constraint) or clearly taste worse than the current leader.
The Magic: Instead of treating every recipe as a totally unique, unrelated item, this algorithm notices that recipes often share "ingredients" (features). If Recipe A and Recipe B both use "garlic," and you learn something about garlic from Recipe A, you can guess something about Recipe B. This lets them learn faster, like a chef who knows that if one garlic-heavy dish is too salty, another garlic-heavy dish probably will be too.
Result: They found that this method recovers 80–90% of the potential "perfect" score, whereas old methods (just tasting randomly) only got 20–50%.

B. GENPSI: The "Map Maker" for Trade-offs

This algorithm is designed to find the Pareto Set (the menu of best trade-offs).

How it works: Instead of looking for one winner, it tries to map out the "frontier" of possibilities. It asks: "Which recipes are so good that you can't improve one metric without hurting another?"
The Strategy: It uses a similar elimination process but looks at the "gap" between recipes. If a recipe is clearly dominated by another (worse in every way), it gets cut. If it's a unique trade-off (great speed, okay taste), it stays.
Result: This method recovered over 90% of the "hypervolume" (a fancy way of saying the total area of good trade-offs) compared to the ground truth, while baselines only managed about 80%.

3. The "Secret Sauce": Learning from Connections

A key part of their success is realizing that prompts aren't random; they are related.

The Analogy: Imagine you are testing 100 different cars. If you test a red sports car and find it's fast, you don't need to test every red sports car from scratch. You know they share an engine type.
The Paper's Approach: They use a "feature map" (like a fingerprint for the prompt) to see these connections. By using a neural network (MLP) to understand these shared patterns, their algorithms learn much faster than methods that treat every prompt as an isolated island.

4. The Proof: The Kitchen Test

The authors tested this in a real kitchen (using real AI models like Llama-3 and Gemma) with real recipes (summarizing news articles).

The Setup: They had to summarize news (Accuracy) while keeping the summary short (Brevity).
The Outcome: Their "Bandit" chefs (GENSEC and GENPSI) consistently found better, safer, and more balanced prompts than the "Random Taster" (Uniform) or other standard methods, especially when they had very little time (budget) to test.

Summary

In short, this paper says: "Stop guessing randomly and stop looking at just one number."

By treating prompt selection as a strategic game where you eliminate bad options early and learn from the similarities between different prompts, you can find the perfect balance between accuracy, speed, and safety much faster and with fewer tries. It's like having a smart sous-chef who knows that if one dish is too salty, the next one probably will be too, saving you from tasting every single dish in the cookbook.

Technical Summary: Efficient Multi-Objective Prompt Optimization via Pure-Exploration Bandits

Problem Formulation

Prompt engineering is central to leveraging Large Language Models (LLMs), yet existing methods predominantly focus on optimizing a single objective (e.g., task accuracy). In real-world applications, prompt performance is inherently multi-faceted, involving trade-offs between competing metrics such as coherence, faithfulness, fluency, and safety. A single prompt rarely dominates across all dimensions. Furthermore, prompt evaluation is costly, requiring a limited budget of queries to an LLM.

This paper addresses the Multi-Objective Prompt Selection problem under a fixed evaluation budget $B$ . The authors formalize two specific targets:

Best Feasible Prompt Identification: Identifying a prompt that maximizes a primary objective (e.g., accuracy) while satisfying constraints on other objectives (e.g., safety or brevity thresholds).
Pareto Prompt Set Identification: Recovering the set of non-dominated prompts (the Pareto front) that represent the optimal trade-offs among all objectives.

The problem is cast within the Pure-Exploration Multi-Objective Bandits framework. The candidate prompt set $\mathcal{X}$ is treated as a set of arms. Pulling an arm corresponds to evaluating a prompt on a sampled input, yielding a stochastic reward vector. The challenge lies in efficiently identifying the optimal arm(s) given the high cost of evaluation and the complex structure of multi-objective trade-offs.

Methodology

The authors propose a general framework that leverages the inherent correlations between prompts to improve sample efficiency, moving beyond treating each prompt as an independent arm.

General Framework

The approach utilizes a round-based arm elimination strategy. The process involves $R$ rounds with a total budget $B$ . In each round:

Budget Allocation: Prompts are selected for evaluation based on an allocator (e.g., uniform sampling or G-optimal design).
Evaluation: Prompts are queried against the LLM, and reward vectors are observed.
Reward Estimation: An estimator updates the expected performance vector $\hat{\mu}(x)$ for active prompts. The framework supports general reward functions $g_\theta(\phi(x))$ , where $\phi(x)$ is a feature embedding of the prompt and $\theta$ is an unknown parameter shared across all prompts.
Arm Elimination: Prompts are ranked and eliminated based on specific criteria depending on the target problem.

Algorithms

Two specific algorithms are introduced based on this framework:

GENSEC (Generalized Successive Elimination under Constraints):
- Target: Best Feasible Prompt Identification.
- Mechanism: It constructs an empirical feasible set based on constraint thresholds. Arms are ranked first by feasibility, then by the primary objective estimate. The top $l_r$ arms are retained for the next round.
- Theoretical Guarantee: For linear reward settings ( $\mu(x) = \phi(x)^\top \theta$ ), the authors prove that the probability of failing to identify the optimal feasible prompt decays exponentially with the budget $B$ . Notably, the error bound depends on $\log_2 K$ (where $K$ is the number of prompts) rather than $K^3$ , significantly improving scalability compared to prior stochastic bandit results.
GENPSI (Generalized Pareto Set Identification):
- Target: Pareto Prompt Set Identification.
- Mechanism: It employs the Empirical Pareto Gap as the metric for elimination. This gap measures the difficulty of classifying an arm as Pareto optimal or sub-optimal. The algorithm unifies and generalizes existing bandit algorithms (like EGE and GEGE) for both standard and linear settings.

Feature Utilization

To handle large prompt sets efficiently, the method utilizes a feature map $\phi: \mathcal{X} \to \mathbb{R}^d$ . In the linear setting, this allows the algorithm to learn the shared parameter $\theta$ across all prompts, accelerating convergence. In experiments, prompt embeddings are extracted using GPT-3.5-turbo and reduced via PCA.

Experimental Results

The authors evaluated GENSEC and GENPSI on two summarization benchmarks (XSum and CNN/DailyMail) using LLaMA-3-8B and Gemma-7B. The objectives were ROUGE-L (quality) and Brevity Score (length).

Best Feasible Identification:
- The bandit-based algorithms (CSR and MLP-CSR variants) significantly outperformed uniform sampling baselines.
- Under constrained budgets, the proposed methods recovered 80–90% of the utility of the optimal constrained prompt, whereas baselines achieved only 20–50%.
- The MLP-CSR variant, which leverages shared structure via a neural network estimator, consistently outperformed the independent-arm CSR variant, demonstrating the benefit of exploiting prompt correlations.
Pareto Set Identification:
- Using Hypervolume (HV) as the metric, GENPSI-based algorithms (EGE and MLP-EGE) recovered >90% of the ground-truth Pareto set's hypervolume.
- Baselines remained in the low-to-mid 80% range.
- MLP-EGE showed particular advantage in low-budget regimes, highlighting the efficiency of shared parameter learning.

Key Contributions

Formalization: This work presents the first formalization of multi-criteria prompt selection as a multi-objective pure-exploration bandit problem.
Algorithmic Innovation: The introduction of GENSEC and GENPSI, which generalize existing bandit algorithms to handle constraints and Pareto optimality while exploiting shared structures among prompts.
Theoretical Guarantees: The paper provides theoretical error bounds for GENSEC in the linear setting, showing a significant improvement in dependency on the number of prompts ( $K$ ) compared to prior work.
Empirical Validation: Extensive experiments demonstrate that bandit-based approaches are principled and efficient, offering substantial improvements over baselines in recovering optimal feasible prompts and Pareto fronts under strict evaluation budgets.

Significance and Claims

The paper claims to establish a "principled and efficient framework" for multi-objective prompt optimization. By bridging prompt engineering with multi-objective bandits, the authors argue that it is possible to move beyond ad-hoc or single-metric strategies. The work addresses the practical reality that prompt performance involves inherent trade-offs that cannot be captured by scalarized metrics alone. The authors position their methods as a solution for scenarios where evaluation budgets are limited, such as in regulated domains or when dealing with expensive LLM inference. The paper concludes that this framework opens new opportunities for scalable prompt optimization under complex evaluation criteria, though it acknowledges that future work is needed to extend these methods to more diverse tasks and incorporate richer metrics like fairness and efficiency.