# Efficient Prompt Optimization Through the Lens of Best Arm Identification

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

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- Builds on 55 of its 91 references that are in the map.
- First posted on arXiv 15 Feb 2024.

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

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding](https://mlsanity.com/paper/1804.07461/) (2018)
- [Prefix-Tuning: Optimizing Continuous Prompts for Generation](https://mlsanity.com/paper/2101.00190/) (2021)
- [The Power of Scale for Parameter-Efficient Prompt Tuning](https://mlsanity.com/paper/2104.08691/) (2021)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [Pre-train, Prompt, and Predict: A Systematic Survey of Prompting Methods in Natural Language Processing](https://mlsanity.com/paper/2107.13586/) (2021)
- [Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Them](https://mlsanity.com/paper/2210.09261/) (2022)
- [Rethinking the Role of Demonstrations: What Makes In-Context Learning Work?](https://mlsanity.com/paper/2202.12837/) (2022)
- [Calibrate Before Use: Improving Few-Shot Performance of Language Models](https://mlsanity.com/paper/2102.09690/) (2021)
- [Making Pre-trained Language Models Better Few-shot Learners](https://mlsanity.com/paper/2012.15723/) (2020)
- [What Makes Good In-Context Examples for GPT-3?](https://mlsanity.com/paper/2101.06804/) (2021)
- [Fantastically Ordered Prompts and Where to Find Them: Overcoming Few-Shot Prompt Order Sensitivity](https://mlsanity.com/paper/2104.08786/) (2021)
- [Large Language Models Are Human-Level Prompt Engineers](https://mlsanity.com/paper/2211.01910/) (2022)
- [How Can We Know What Language Models Know?](https://mlsanity.com/paper/1911.12543/) (2019)
- [Large Language Models as Optimizers](https://mlsanity.com/paper/2309.03409/) (2023)
- [P-Tuning v2: Prompt Tuning Can Be Comparable to Fine-tuning Universally Across Scales and Tasks](https://mlsanity.com/paper/2110.07602/) (2021)
- [Automatic Chain of Thought Prompting in Large Language Models](https://mlsanity.com/paper/2210.03493/) (2022)
- [Automatic Prompt Optimization with "Gradient Descent" and Beam Search](https://mlsanity.com/paper/2305.03495/) (2023)
- [Learning To Retrieve Prompts for In-Context Learning](https://mlsanity.com/paper/2112.08633/) (2021)
- [RLPrompt: Optimizing Discrete Text Prompts with Reinforcement Learning](https://mlsanity.com/paper/2205.12548/) (2022)
- [Hard Prompts Made Easy: Gradient-Based Discrete Optimization for Prompt Tuning and Discovery](https://mlsanity.com/paper/2302.03668/) (2023)
- [Factual Probing Is [MASK]: Learning vs. Learning to Recall](https://mlsanity.com/paper/2104.05240/) (2021)
- [Selective Annotation Makes Language Models Better Few-Shot Learners](https://mlsanity.com/paper/2209.01975/) (2022)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Reframing Instructional Prompts to GPTk's Language](https://mlsanity.com/paper/2109.07830/) (2021)
- [Instruction Induction: From Few Examples to Natural Language Task Descriptions](https://mlsanity.com/paper/2205.10782/) (2022)

## Built on by (most cited first, 30 of 37)

- [Prompt Optimization with Human Feedback](https://mlsanity.com/paper/2405.17346/) (2024)
- [A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits](https://mlsanity.com/paper/2407.13977/) (2024)
- [Online Multi-LLM Selection via Contextual Bandits under Unstructured Context Evolution](https://mlsanity.com/paper/2506.17670/) (2025)
- [Tuning LLM Judge Design Decisions for 1/1000 of the Cost](https://mlsanity.com/paper/2501.17178/) (2025)
- [Hyperband-based Bayesian Optimization for Black-box Prompt Selection](https://mlsanity.com/paper/2412.07820/) (2024)
- [FastGAS: Fast Graph-based Annotation Selection for In-Context Learning](https://mlsanity.com/paper/2406.03730/) (2024)
- [Strategic Scaling of Test-Time Compute: A Bandit Learning Approach](https://mlsanity.com/paper/2506.12721/) (2025)
- [LLM Prompt Duel Optimizer: Efficient Label-Free Prompt Optimization](https://mlsanity.com/paper/2510.13907/) (2025)
- [Survey: Multi-Armed Bandits Meet Large Language Models](https://mlsanity.com/paper/2505.13355/) (2025)
- [What Makes a Good Natural Language Prompt?](https://mlsanity.com/paper/2506.06950/) (2025)
- [Multimodal Prompt Optimization: Why Not Leverage Multiple Modalities for MLLMs](https://mlsanity.com/paper/2510.09201/) (2025)
- [Towards Reliable LLM Evaluation: Correcting the Winner's Curse in Adaptive Benchmarking](https://mlsanity.com/paper/2605.05973/) (2026)
- [A Survey of Automatic Prompt Optimization with Instruction-focused Heuristic-based Search Algorithm](https://mlsanity.com/paper/2502.18746/) (2025)
- [PRESTO: Preimage-Informed Instruction Optimization for Prompting Black-Box LLMs](https://mlsanity.com/paper/2510.25808/) (2025)
- [Multi-Drafter Speculative Decoding with Alignment Feedback](https://mlsanity.com/paper/2604.05417/) (2026)
- [Compute Allocation for Self-Evolving LLMs: From Depth-Breadth to Multi-Armed Bandits](https://mlsanity.com/paper/2605.29268/) (2026)
- [Cost-Aware Multi-Objective Bandits: Theory and Application to Budgeted LLM Configuration Evaluation](https://mlsanity.com/paper/2608.04333/) (2026)
- [Prompt Exploration with Prompt Regression](https://mlsanity.com/paper/2405.11083/) (2024)
- [Bounds of Chain-of-Thought Robustness: Reasoning Steps, Embed Norms, and Beyond](https://mlsanity.com/paper/2509.21284/) (2025)
- [Efficient Multi-objective Prompt Optimization via Pure-exploration Bandits](https://mlsanity.com/paper/2605.14553/) (2026)
- [LPDS: Evaluating LLM Robustness Through Logic-Preserving Difficulty Scaling](https://mlsanity.com/paper/2605.15393/) (2026)
- [Stop Guessing When to Stop Testing: Efficient Model Evaluation with Just Enough Data](https://mlsanity.com/paper/2607.08522/) (2026)
- [LatentPrompt: Optimizing Promts in Latent Space](https://mlsanity.com/paper/2508.02452/) (2025)
- [From Cross-Task Examples to In-Task Prompts: A Graph-Based Pseudo-Labeling Framework for In-context Learning](https://mlsanity.com/paper/2510.24528/) (2025)
- [Beyond Elicitation: Provision-based Prompt Optimization for Knowledge-Intensive Tasks](https://mlsanity.com/paper/2511.10465/) (2025)
- [A Component-Based Survey of Interactions between Large Language Models and Multi-Armed Bandits](https://mlsanity.com/paper/2601.12945/) (2026)
- [BoLT: A Benchmark to Democratize Black-box Optimization Research for Expensive LLM Tasks](https://mlsanity.com/paper/2605.17000/) (2026)
- [The Optimizer Is the Agent: Reasoning-Driven Search across Prompts, Programs, and ML Workflows](https://mlsanity.com/paper/2608.06714/) (2026)
- [Audit, Alignment, and Optimization of LM-Powered Subroutines with Application to Public Comment Processing](https://mlsanity.com/paper/2507.08109/) (2025)
- [Inference-Aware Prompt Optimization for Aligning Black-Box Large Language Models](https://mlsanity.com/paper/2508.10030/) (2025)

## Abstract (arXiv)

The remarkable instruction-following capability of large language models (LLMs) has sparked a growing interest in automatically finding good prompts, i.e., prompt optimization. Most existing works follow the scheme of selecting from a pre-generated pool of candidate prompts. However, these designs mainly focus on the generation strategy, while limited attention has been paid to the selection method. Especially, the cost incurred during the selection (e.g., accessing LLM and evaluating the responses) is rarely explicitly considered. To overcome this limitation, this work provides a principled framework, TRIPLE, to efficiently perform prompt selection under an explicit budget constraint. TRIPLE is built on a novel connection established between prompt optimization and fixed-budget best arm identification (BAI-FB) in multi-armed bandits (MAB); thus, it is capable of leveraging the rich toolbox from BAI-FB systematically and also incorporating unique characteristics of prompt optimization. Extensive experiments on multiple well-adopted tasks using various LLMs demonstrate the remarkable performance improvement of TRIPLE over baselines while satisfying the limited budget constraints. As an extension, variants of TRIPLE are proposed to efficiently select examples for few-shot prompts, also achieving superior empirical performance.