Best Arm Identification for Prompt Learning under a Limited Budget

Chengshuai Shi, Kun Yang, Jing Yang, Cong Shen

Abstract

The instruction-following capability of large language models (LLMs) has driven significant interest in prompt optimization—the process of automatically finding effective prompts. Most existing methods focus on generating candidate prompts but treat the selection of the best prompt as a secondary, often expensive, step. This work introduces TRIPLE, a principled framework designed to perform prompt selection efficiently under explicit budget constraints. By establishing a novel connection between prompt optimization and fixed-budget best arm identification (BAI-FB) in multi-armed bandits (MAB), TRIPLE leverages established bandit theory to identify high-performing prompts while minimizing LLM API calls and evaluation costs. Extensive experiments across 47 tasks demonstrate that TRIPLE significantly outperforms standard selection methods, particularly when evaluation budgets are tight.

Introduction: The Selection Bottleneck

As LLMs become more integrated into production workflows, the sensitivity of these models to prompt wording remains a challenge. While researchers have developed sophisticated ways to generate candidate prompts, the process of selecting the "best" one is often a naive afterthought. Typically, every candidate prompt is tested against a large development dataset, which incurs substantial financial costs (API fees), time overhead, and evaluation complexity.

The prompt optimization pipeline, highlighting the focus on efficient selection under budget constraints.

This paper argues that prompt optimization must be treated as a resource-constrained search. We need to identify the optimal instruction from a pool of candidates using the fewest possible interactions with the LLM.

The TRIPLE Framework

The core innovation of this work is the formal mapping of prompt selection to the Fixed-Budget Best Arm Identification (BAI-FB) problem within Multi-Armed Bandit (MAB) theory. In this framework, each candidate prompt is viewed as an "arm" of a bandit, and the goal is to find the single best arm within a pre-defined number of "pulls" (evaluations).

Mapping the components of prompt optimization to the multi-armed bandit framework.

Algorithmic Variants

TRIPLE introduces several strategies to navigate the selection process:

  1. TRIPLE-SH (Sequential Halving): The budget is divided into phases. In each phase, all active prompts are tested, and the bottom-performing half is discarded, concentrating the remaining budget on the most promising candidates.
  2. TRIPLE-CR (Continuously Reject): A fluid version that eliminates poorly performing prompts based on statistical confidence intervals after any single evaluation.
  3. Embedding-Aware Variants (TRIPLE-CLST & TRIPLE-GSE): These versions leverage the semantic similarity between prompts. CLST clusters similar prompts to share performance data, while GSE uses a neural network to predict the performance of untested prompts based on their vector embeddings. This allows the system to identify high-quality prompts even when the budget is too small to test every candidate individually.

Experimental Evaluation

The framework was evaluated across 47 tasks from two major benchmarks: Instruction-Induction (e.g., sentiment analysis, antonym identification) and BigBench-II (e.g., logical fallacies, mathematical reasoning). Testing involved a variety of LLMs, including GPT-3.5, Llama2-7b, Gemma-7b, and Mistral-7B.

Key Insights

  • BAI vs. Regret Minimization: Traditional bandit approaches often focus on "regret minimization" (maximizing total score during the search). However, in prompt engineering, the performance of the model during the search is irrelevant; only the quality of the final selected prompt matters. BAI-FB is the mathematically appropriate tool for this objective.
  • Leveraging Prompt Correlation: Unlike standard bandit arms, prompts are semantically related. By using embeddings, TRIPLE can infer the quality of a "neighborhood" of prompts, making the search significantly more efficient than uniform sampling.
  • Budget Resilience: TRIPLE-GSE proved particularly effective in "impossible" scenarios—where the number of candidate prompts exceeds the total evaluation budget. By leveraging semantic priors, it can still identify top-tier prompts.

Results and Impact

Empirical results show that TRIPLE provides substantial gains over baseline selection methods:

  • Accuracy Improvements: On GPT-3.5 and Llama2, TRIPLE improved prompt accuracy by 3% to 16% over uniform sampling.
  • Efficiency Gains: When using embedding-aware variants, performance improvements reached 10% to 56% compared to non-embedding baselines under tight budgets.
  • Plug-and-Play Integration: TRIPLE was successfully integrated into existing pipelines like APE (Automatic Prompt Engineer) and APO (Automatic Prompt Optimization), boosting their final output quality without increasing computational costs.

Conclusion

TRIPLE provides a principled, budget-aware foundation for the selection phase of prompt optimization. By treating prompts as arms in a bandit problem, researchers can systematically navigate the trade-off between evaluation cost and prompt quality. Future work includes extending this framework to account for token-based costs (where longer prompts are more expensive) and exploring contextual bandits to select prompts tailored to specific input types.

Summary updated

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. As an extension, variants of TRIPLE are proposed to efficiently select examples for few-shot prompts, also achieving superior empirical performance.
BibTeX
@inproceedings{shi2024best,
  author = {Chengshuai Shi and Kun Yang and Jing Yang and Cong Shen},
  title = {{Best Arm Identification for Prompt Learning under a Limited Budget}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=FLNnlfBGMo},
}
Figure