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.
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).
Algorithmic Variants
TRIPLE introduces several strategies to navigate the selection process:
- 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.
- TRIPLE-CR (Continuously Reject): A fluid version that eliminates poorly performing prompts based on statistical confidence intervals after any single evaluation.
- 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