Efficient Multi-objective Prompt Optimization via Pure-exploration Bandits

• URL: http://arxiv.org/abs/2605.14553v1
• Date: Thu, 14 May 2026 08:31:17 GMT
• Title: Efficient Multi-objective Prompt Optimization via Pure-exploration Bandits
• Abstract summary: We study the multi-objective prompt selection problem under two practical settings.<n>We adapt provably efficient algorithms from multi-objective bandits.<n>We introduce a novel design for best feasible arm identification in structured bandits.
• Score: 17.812798971915218
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Generative Universal Multimodal Retrieval with Dual-role Identifiers [1.0981910170846492]
  We propose DrIG, a novel Generative framework for universal multimodal retrieval featuring Dual-role Identifiers.<n>DrIG consistently outperforms state-of-the-art generative multimodal baselines across diverse tasks, while hybrid reranking achieves a favorable efficiency-effectiveness trade-off against strong dense retrievers.
  arXiv  Detail & Related papers  (2026-08-13T09:10:09Z)
• Before Thinking, Learn to Decide: Proactive Routing for Efficient Visual Reasoning [87.18590662029432]
  We propose PRP, a Proactive Routing Paradigm that enables early decision-making by jointly evaluating the competence of both the draft and target models.<n>Our draft Rating Learning (DRL) equips the draft model with an internal confidence estimator, while Joint Rating Learning (JRL) predicts how well the target model can handle a given query.<n>These ratings enable fine-grained, instance-level textbfProactive Routing and substantially accelerate inference without compromising overall performance.
  arXiv  Detail & Related papers  (2026-06-29T12:30:24Z)
• Prompt Optimization via Retrieved Reasoning Assets and Multi-Agent Analysis [5.935239028627343]
  We introduce MA-SAPO, a Multi-Agent framework for Score-Aware Prompt Optimization.<n>Compared to prior methods, MA-SAPO explicitly couples evaluation outcomes with structured reasoning to guide systematic edits.<n>By turning evaluation signals into interpretable reasoning chains, MA-SAPO produces prompt refinements that are more transparent, auditable, and controllable.
  arXiv  Detail & Related papers  (2025-10-18T20:21:09Z)
• TETRIS: Optimal Draft Token Selection for Batch Speculative Decoding [76.23719557942917]
  TETRIS actively selects the most promising draft tokens (for every request in a batch) to be accepted when verified in parallel.<n>We show theoretically and empirically that TETRIS outperforms baseline speculative decoding and existing methods that dynamically select draft tokens.
  arXiv  Detail & Related papers  (2025-02-21T04:19:24Z)
• Progressive Multimodal Reasoning via Active Retrieval [64.74746997923967]
  Multi-step multimodal reasoning tasks pose significant challenges for large language models (MLLMs)<n>We propose AR-MCTS, a universal framework designed to progressively improve the reasoning capabilities of MLLMs.<n>We show that AR-MCTS can optimize sampling diversity and accuracy, yielding reliable multimodal reasoning.
  arXiv  Detail & Related papers  (2024-12-19T13:25:39Z)
• Hyperband-based Bayesian Optimization for Black-box Prompt Selection [15.756224286651237]
  Black-box prompt selection is challenging due to potentially large, search spaces, absence of gradient information, and high evaluation cost of prompts on a validation set.<n>We propose HbBoPs, a novel method that combines a structural-aware deep kernel Gaussian Process with Hyperband as a multi-fidelity scheduler.<n>HbBoPs outperforms state-of-the-art methods in both performance and efficiency.
  arXiv  Detail & Related papers  (2024-12-10T14:42:51Z)
• QPO: Query-dependent Prompt Optimization via Multi-Loop Offline Reinforcement Learning [58.767866109043055]
  We introduce Query-dependent Prompt Optimization (QPO), which iteratively fine-tune a small pretrained language model to generate optimal prompts tailored to the input queries.<n>We derive insights from offline prompting demonstration data, which already exists in large quantities as a by-product of benchmarking diverse prompts on open-sourced tasks.<n> Experiments on various LLM scales and diverse NLP and math tasks demonstrate the efficacy and cost-efficiency of our method in both zero-shot and few-shot scenarios.
  arXiv  Detail & Related papers  (2024-08-20T03:06:48Z)
• DynaThink: Fast or Slow? A Dynamic Decision-Making Framework for Large Language Models [42.95876831743256]
  Large language models (LLMs) have demonstrated emergent capabilities across diverse reasoning tasks via Chains-of-Thought prompting. This paper addresses the challenge of enabling LLMs to autonomously select between fast and slow inference methods. We introduce a dynamic decision-making framework that categorizes tasks into two distinct pathways: 'Fast', designated for tasks where the LLM quickly identifies a high-confidence solution, and 'Slow', allocated for tasks that the LLM perceives as complex.
  arXiv  Detail & Related papers  (2024-07-01T06:45:13Z)
• Efficient Prompt Optimization Through the Lens of Best Arm Identification [50.56113809171805]
  This work provides a principled framework, TRIPLE, to efficiently perform prompt selection under an explicit budget constraint. It is built on a novel connection established between prompt optimization and fixed-budget best arm identification (BAI-FB) in multi-armed bandits (MAB)
  arXiv  Detail & Related papers  (2024-02-15T05:31:13Z)
• Query-Dependent Prompt Evaluation and Optimization with Offline Inverse RL [62.824464372594576]
  We aim to enhance arithmetic reasoning ability of Large Language Models (LLMs) through zero-shot prompt optimization. We identify a previously overlooked objective of query dependency in such optimization. We introduce Prompt-OIRL, which harnesses offline inverse reinforcement learning to draw insights from offline prompting demonstration data.
  arXiv  Detail & Related papers  (2023-09-13T01:12:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.