Bandit-Based Prompt Design Strategy Selection Improves Prompt Optimizers (2025)

Abstract: Prompt optimization aims to search for effective prompts that enhance the performance of large language models (LLMs). Although existing prompt optimization methods have discovered effective prompts, they often differ from sophisticated prompts carefully designed by human experts. Prompt design strategies, representing best practices for improving prompt performance, can be key to improving prompt optimization. Recently, a method termed the Autonomous Prompt Engineering Toolbox (APET) has incorporated various prompt design strategies into the prompt optimization process. In APET, the LLM is needed to implicitly select and apply the appropriate strategies because prompt design strategies can have negative effects. This implicit selection may be suboptimal due to the limited optimization capabilities of LLMs. This paper introduces Optimizing Prompts with sTrategy Selection (OPTS), which implements explicit selection mechanisms for prompt design. We propose three mechanisms, including a Thompson sampling-based approach, and integrate them into EvoPrompt, a well-known prompt optimizer. Experiments optimizing prompts for two LLMs, Llama-3-8B-Instruct and GPT-4o mini, were conducted using BIG-Bench Hard. Our results show that the selection of prompt design strategies improves the performance of EvoPrompt, and the Thompson sampling-based mechanism achieves the best overall results. Our experimental code is provided at https://github.com/shiralab/OPTS.

## introduction large language models (llms) such as @xcite , gemini @xcite , and llama 3 @xcite have demonstrated superior abilities in a variety of domains, including medicine @xcite , law @xcite , and code generation @xcite . since well-crafted prompts improve the performance of llms, prompt engineering (i.e., designing better prompts) plays a key role in the area @xcite . despite its importance, prompt engineering is laborious as it requires a lot of time for refinement and sufficient knowledge of the tasks. to design effective prompts with less effort, research on prompt optimization has been actively conducted. in particular, discrete prompt optimization, which optimizes prompts within the natural language space, has attracted attention. this approach is valuable as it typically allows for the optimization of prompts for black-box llms, such as gpt-4, while also providing interpretable results @xcite . to explore effective prompts within the large natural language space, several methods have been proposed, which include emulating evolutionary algorithms using llms @xcite @xcite . these methods have discovered effective prompts, but they often differ from sophisticated prompts carefully designed by human experts. prompt design strategies, which provide guidelines for creating effective prompts, can be key to boosting the performance of prompt optimizers. in fact, chain-of-thought (cot; @xcite and role prompting @xcite have been employed in prompt optimization, leading to better prompts @xcite . recently, @xcite proposed a method termed the autonomous prompt engineering toolbox (apet), which incorporated various prompt design strategies into the optimization process. apet fed all prepared strategies into an llm to generate a new prompt that incorporates the strategies. however, not all strategies should be incorporated because prompt design strategies can have negative effects depending on both the llm and the task @xcite . in apet, an llm that generates prompts if one of the first k arms is selected, the description of the prompt design strategy corresponding to the selected arm is passed to the prompt-designing llm. if the (k + 1)-th arm is selected, the prompt is not modified in any way. in this paper, we introduce explicit selection mechanisms for prompt design strategies for the first time. we also propose three selection methods, including one based on thompson sampling @xcite @xcite . by integrating them with the existing prompt optimizer, evoprompt @xcite , we show that explicit strategy selection effectively leverages existing knowledge of prompt design and enhances the performance of prompt optimizers. moreover, the optimizer with the ts-based selection mechanism outperforms other existing methods. in summary, our contributions are as follows: ## proposed methods in this section, we describe our proposed methods for selecting prompt design strategies. we then introduce prompt optimization algorithms that combine evoprompt @xcite with the strategy selection methods. we term our methods optimizing prompts with strategy selection (opts). terminology task-solving llm is an llm that is applied to and solves downstream tasks, while prompt-designing llm is another llm that produces helpful prompts for task-solving llms. in contrast to prompt, which represents an instruction for a task-solving llm, meta-prompt refers to an instruction for a prompt-designing llm. ## experiments we experimentally evaluate three strategy selection methods we introduce: opts(ts), opts(us), and opts(apet). combined with evoprompt, these methods are applied to various tasks and compared with the existing baseline methods. ## analysis in this section, we analyze opts(ts) from two perspectives: the analyses of the discovered task descriptions and the case where a strategy was applied more than once. further analyses, including comparison under the same number of api calls, analysis of prompts generated during and after optimization, and analysis of score variance, can be found in the appendices e to g. before or after opts description before let's think step-by-step. identify a humorous variation that spoofs the title of a film or music artist, inventing a funny alteration while preserving its original essence. before providing your answer, ensure full clarity and understanding. ## conclusion and discussion we introduced explicit selection mechanisms into prompt optimization to effectively leverage existing knowledge of prompt design. experiments have demonstrated that the three methods we introduced improve the performance of the prompt optimizers. in particular, the method based on thompson sampling is the best among those we compared. the prompts discovered by our methods effectively incorporate several prompt design strategies, which evoprompt alone was unable to discover. our results highlight the importance of leveraging existing knowledge and selecting it explicitly.