Abstract
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.
Introduction
Prompt optimization—the process of finding the best instruction to trigger a specific behavior in an LLM—is notoriously sensitive. A single word change can swing accuracy wildly. Most current "automatic prompt engineers" work by generating a huge pool of candidate prompts and then testing them.
The primary bottleneck in this process is cost. Evaluating 100 candidate prompts on a large dataset is financially expensive (API fees), time-consuming, and often hits rate limits. Most existing methods either ignore this cost or use naive selection strategies, such as testing every prompt equally. This paper introduces a principled way to allocate a limited budget of $N$ LLM interactions to identify the single best prompt as accurately as possible.
Bridging Prompt Optimization and Bandits
The core innovation of this work is bridging the gap between prompt engineering and Multi-Armed Bandits (MAB). By framing prompt selection as a "Best Arm Identification" (BAI) problem, the researchers can apply rigorous mathematical tools to the trial-and-error process of prompt testing.
In this analogy, the pool of candidate prompts represents the "arms" of the bandit. "Pulling an arm" corresponds to sending a prompt to the LLM and scoring the response, which serves as the "reward." Unlike traditional bandit algorithms like UCB (Upper Confidence Bound), which focus on maximizing cumulative reward during training, TRIPLE focuses on Pure Exploration. The goal is not to avoid "bad" prompts during the search, but to ensure the final prompt selected is the absolute best within the given budget.
The TRIPLE Framework
The proposed TRIPLE (besT aRm Identification for Prompt LEarning) framework features two core selection strategies:
- TRIPLE-SH (Sequential Halving): The budget is split into phases. In each phase, all remaining prompts are tested equally. At the end of the phase, the bottom 50% are discarded, concentrating the remaining budget on the most promising candidates.
- TRIPLE-CR (Continuously Reject): A fluid approach that uses the "Large Deviation Principle" to eliminate poorly performing prompts after each individual trial, rather than waiting for phases to end.
To handle massive prompt pools where the budget is smaller than the number of candidates, TRIPLE incorporates embedding-based enhancements. TRIPLE-CLST groups similar prompts using sentence embeddings to find the best "cluster" first, while TRIPLE-GSE uses a neural network to learn a relationship between a prompt's embedding and its performance, allowing the system to estimate the quality of untested prompts.
Empirical Results
The researchers evaluated TRIPLE across 47 diverse tasks from benchmarks like Instruction-Induction and BigBench-ii, using LLMs including GPT-3.5, Llama2, and Mistral-7B.
Key findings include:
- Significant Accuracy Gains: TRIPLE-SH and CR improved performance by 3% to 16% over uniform testing and standard UCB baselines.
- Efficiency at Low Budgets: TRIPLE’s advantage is most pronounced when the budget is tight. When using embeddings (CLST and GSE), TRIPLE outperformed sophisticated baselines like Bayesian Optimization by up to 56% on Llama2.
- Versatility: TRIPLE can be integrated into existing pipelines like APE (Automatic Prompt Engineer) to improve their selection efficiency without changing their generation logic. It also proved successful in selecting the best examples for few-shot prompting.
Conclusion
TRIPLE provides a mathematically grounded framework for prompt selection that explicitly accounts for the real-world constraints of API costs and computation time. By treating prompts as correlated arms in a bandit problem, it enables researchers to find high-performing instructions with significantly fewer LLM interactions. Future work may address token-specific costs and the iterative generation of prompts within this unified bandit framework.
Summary updated