Research map / Large language models / Language, safety and interpretability
Efficient Prompt Optimization Through the Lens of Best Arm Identification
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Frames prompt selection as fixed-budget best arm identification and proposes TRIPLE (SH/CR plus embedding-based clustering and GSE variants) to choose prompts under an explicit LLM-call budget, extended to few-shot example selection.
Problem
Prompt optimization's selection stage typically evaluates all candidate prompts on full dev data, incurring large LLM-access and evaluation costs; no principled method allocates a fixed budget across candidate prompts.
Approach
Connects prompt selection to fixed-budget best arm identification in multi-armed bandits, adapting BAI-FB algorithms (Sequential Halving, Continuously Reject, GSE) and adding prompt-embedding clustering and function approximation to share information across large candidate pools.
Key results
- On GPT-3.5 with 30 prompts and budget 150, TRIPLE-SH and TRIPLE-CR improve over Uniform by about 15% and 12% on average, and over UCB by about 5% and 3%.
- With 150 prompts and budget 100, TRIPLE-CLST and TRIPLE-GSE improve over BO-EI by 21% and 28% on average for GPT-3.5, and over NeuralUCB by 38% and 45%.
- Integrated into APE, TRIPLE-CR/GSE achieve the best average performance rank (1.50 for GSE) versus 4.00 for uniform APE across 12 tasks.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use TRIPLE-SH instead of Uniform | Prompt selection without embeddings · 30 prompts, budget 150, GPT-3.5 | performance: 15% | Helped |
| Use TRIPLE-CR instead of Uniform | Prompt selection without embeddings · 30 prompts, budget 150, GPT-3.5 | performance: 12% | Helped |
| Use TRIPLE-CLST instead of BO-EI | Prompt selection with embeddings · 30 prompts, budget 150, GPT-3.5 | performance: 11% | Helped |
| Use TRIPLE-GSE instead of BO-EI | Prompt selection with embeddings · 30 prompts, budget 150, GPT-3.5 | performance: 10% | Helped |
| Use TRIPLE-CLST instead of NeuralUCB | Prompt selection with embeddings · 30 prompts, budget 150, GPT-3.5 | performance: 17% | Helped |
| Use TRIPLE-GSE instead of NeuralUCB | Prompt selection with embeddings · 30 prompts, budget 150, GPT-3.5 | performance: 17% | Helped |
| Use TRIPLE-CLST instead of BO-EI | Prompt selection with embeddings · 150 prompts, budget 100, GPT-3.5 | performance: 21% | Helped |
| Use TRIPLE-GSE instead of BO-EI | Prompt selection with embeddings · 150 prompts, budget 100, GPT-3.5 | performance: 28% | Helped |
| Use TRIPLE-CLST instead of NeuralUCB | Prompt selection with embeddings · 150 prompts, budget 100, GPT-3.5 | performance: 38% | Helped |
| Use TRIPLE-GSE instead of NeuralUCB | Prompt selection with embeddings · 150 prompts, budget 100, GPT-3.5 | performance: 45% | Helped |
| Use TRIPLE-CR rather than Uniform when the budget is 10 evaluations per prompt on average | Prompt selection · 30 prompts, GPT-3.5 | performance: 9.7% | Helped |
| Use TRIPLE-CLST rather than Uniform when the budget is 10 evaluations per prompt on average | Prompt selection · 30 prompts, GPT-3.5 | performance: 13.5% | Helped |
Surprising findings
- Regret-minimization methods such as UCB and NeuralUCB are argued to be ill-suited to the best-arm-identification goal of final prompt selection.
Limitations
- Cost modeled only as number of LLM accesses, ignoring prompt-specific token costs.
- Only a few BAI-FB designs (SH, CR, GSE) are incorporated; other BAI methods left unexplored.
- Example-selection extension relies on heuristics without theoretical guarantees.
Experimental setup
Datasets: Instruction-Induction BigBench
Benchmarks: Instruction-Induction BigBench
Metrics: exact match f1-score multiple choice accuracy average performance rank
Baselines: Uniform UCB BO-EI NeuralUCB Random APE APO
Builds on: APE APO Sequential Halving Continuously Reject GSE
Closest papers by meaning
- Sample Efficient Demonstration Selection for In-Context Learning (ICML 2025 · similarity 0.89)
- On Speeding Up Language Model Evaluation (ICLR 2025 · similarity 0.87)
- Unleashing the Potential of Large Language Models as Prompt Optimizers: Analogical Analysis with Gradient-based Model Optimizers (AAAI 2025 · similarity 0.87)
- PREFER: Prompt Ensemble Learning via Feedback-Reflect-Refine (AAAI 2024 · similarity 0.87)
- GReaTer: Gradients Over Reasoning Makes Smaller Language Models Strong Prompt Optimizers (ICLR 2025 · similarity 0.87)
- Prompt Optimization with EASE? Efficient Ordering-aware Automated Selection of Exemplars (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.