# Efficient Multi-objective Prompt Optimization via Pure-exploration Bandits

arXiv: https://arxiv.org/abs/2605.14553 · HTML: https://mlsanity.com/paper/2605.14553/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 42 of its 55 references that are in the map.
- First posted on arXiv 14 May 2026.

## Builds on (most cited first, 30 of 42)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Don't Give Me the Details, Just the Summary! Topic-Aware Convolutional Neural Networks for Extreme Summarization](https://mlsanity.com/paper/1808.08745/) (2018)
- [Teaching Machines to Read and Comprehend](https://mlsanity.com/paper/1506.03340/) (2015)
- [Large Language Models Are Human-Level Prompt Engineers](https://mlsanity.com/paper/2211.01910/) (2022)
- [Gemma: Open Models Based on Gemini Research and Technology](https://mlsanity.com/paper/2403.08295/) (2024)
- [LEAF: A Benchmark for Federated Settings](https://mlsanity.com/paper/1812.01097/) (2018)
- [Automatic Chain of Thought Prompting in Large Language Models](https://mlsanity.com/paper/2210.03493/) (2022)
- [SummEval: Re-evaluating Summarization Evaluation](https://mlsanity.com/paper/2007.12626/) (2020)
- [Tree of Attacks: Jailbreaking Black-Box LLMs Automatically](https://mlsanity.com/paper/2312.02119/) (2023)
- [Automatic Prompt Optimization with "Gradient Descent" and Beam Search](https://mlsanity.com/paper/2305.03495/) (2023)
- [GEPA: Reflective Prompt Evolution Can Outperform Reinforcement Learning](https://mlsanity.com/paper/2507.19457/) (2025)
- [A Systematic Survey of Prompt Engineering in Large Language Models: Techniques and Applications](https://mlsanity.com/paper/2402.07927/) (2024)
- [RLPrompt: Optimizing Discrete Text Prompts with Reinforcement Learning](https://mlsanity.com/paper/2205.12548/) (2022)
- [Backdooring Instruction-Tuned Large Language Models with Virtual Prompt Injection](https://mlsanity.com/paper/2307.16888/) (2023)
- [Black-Box Prompt Optimization: Aligning Large Language Models without Model Training](https://mlsanity.com/paper/2311.04155/) (2023)
- [The Prompt Report: A Systematic Survey of Prompt Engineering Techniques](https://mlsanity.com/paper/2406.06608/) (2024)
- [Politeness Transfer: A Tag and Generate Approach](https://mlsanity.com/paper/2004.14257/) (2020)
- [Stochastic Bandits with Linear Constraints](https://mlsanity.com/paper/2006.10185/) (2020)
- [InstructZero: Efficient Instruction Optimization for Black-Box Large Language Models](https://mlsanity.com/paper/2306.03082/) (2023)
- [Promptify: Text-to-Image Generation through Interactive Prompt Exploration with Large Language Models](https://mlsanity.com/paper/2304.09337/) (2023)
- [Dynamic Prompt Optimizing for Text-to-Image Generation](https://mlsanity.com/paper/2404.04095/) (2024)
- [Efficient Prompt Optimization Through the Lens of Best Arm Identification](https://mlsanity.com/paper/2402.09723/) (2024)
- [Unleashing the Potential of Large Language Models as Prompt Optimizers: Analogical Analysis with Gradient-based Model Optimizers](https://mlsanity.com/paper/2402.17564/) (2024)
- [Prompt Optimization with Human Feedback](https://mlsanity.com/paper/2405.17346/) (2024)
- [Use Your INSTINCT: INSTruction optimization for LLMs usIng Neural bandits Coupled with Transformers](https://mlsanity.com/paper/2310.02905/) (2023)
- [Localized Zeroth-Order Prompt Optimization](https://mlsanity.com/paper/2403.02993/) (2024)
- [Discrete Prompt Optimization via Constrained Generation for Zero-shot Re-ranker](https://mlsanity.com/paper/2305.13729/) (2023)

## Built on by (most cited first, 2 of 2)

- [The Optimizer Is the Agent: Reasoning-Driven Search across Prompts, Programs, and ML Workflows](https://mlsanity.com/paper/2608.06714/) (2026)
- [Do Prompt Optimizers Break Requirements They Are Not Scored On? A Preregistered Study](https://mlsanity.com/paper/2610.13287/) (2026)

## Abstract (arXiv)

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.