💬 NLP

Bandit-Based Prompt Design Strategy Selection Improves Prompt Optimizers

This paper introduces OPTS, a prompt optimization framework that enhances the performance of existing optimizers like EvoPrompt by implementing explicit, bandit-based mechanisms (specifically Thompson sampling) to effectively select and apply prompt design strategies, thereby outperforming methods that rely on implicit strategy selection.

Original authors: Rin Ashizawa, Yoichi Hirose, Nozomu Yoshinari, Kento Uchida, Shinichi Shirakawa

Published 2026-06-18

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Rin Ashizawa, Yoichi Hirose, Nozomu Yoshinari, Kento Uchida, Shinichi Shirakawa

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a very smart but sometimes stubborn robot (a Large Language Model) how to solve a difficult puzzle. You give the robot instructions, called a "prompt." If the instructions are vague, the robot gets confused. If they are perfect, the robot solves the puzzle instantly.

For a long time, humans have tried to write these perfect instructions by hand, or they've used computer programs to automatically tweak the instructions until they work better. This is called Prompt Optimization.

However, there's a problem: these automatic programs often create instructions that are functional but lack the "secret sauce" that human experts use. They miss out on proven tricks like "think step-by-step" or "act like an expert."

The Problem: The Robot's Bad Guessing Game

Recently, a tool called APET tried to fix this. It gave the robot a menu of "design strategies" (like a menu of cooking techniques: add salt, chop finely, simmer slowly). The robot was supposed to look at the menu and decide which tricks to use for the specific puzzle.

But the paper argues that asking the robot to make this choice is like asking a tired chef to guess which spice will save a burnt soup. The robot often guesses wrong, picking strategies that actually make the instructions worse. It's an implicit choice (the robot just "feels" like it should use a trick), and it's not very good at it.

The Solution: OPTS (The Smart Sommelier)

The authors of this paper introduce a new method called OPTS (Optimizing Prompts with sTrategy Selection).

Instead of letting the robot guess, OPTS acts like a smart sommelier (a wine expert) or a casino manager running a game of chance. Here is how it works using a simple analogy:

Imagine you have a row of slot machines (the researchers call these "arms").

Machine 1: Adds "Think Step-by-Step" to the instructions.
Machine 2: Tells the robot to "Read the question again."
Machine 3: Tells the robot to "Act like a math expert."
Machine K+1: Does nothing (keeps the instructions exactly as they are).

In the old method (APET), the robot would just pull a lever randomly or based on a hunch.

In the new OPTS method, the system uses a mathematical strategy called Thompson Sampling. Think of this as a smart gambler who keeps a scorecard:

It tries a machine (a strategy).
If the robot solves the puzzle better, the system gives that machine a "thumbs up" and makes it more likely to be picked next time.
If the robot fails, the system gives that machine a "thumbs down" and stops picking it.
Crucially, it also keeps a "Do Nothing" machine. If all the tricks are making things worse, the system learns to just leave the instructions alone.

What They Found

The researchers tested this on two different robots (LLMs) using a set of very hard logic and reasoning puzzles (called BIG-Bench Hard).

The Result: By using this "smart gambler" approach to pick the right strategy, the system created much better instructions than the robots could do on their own.
The Champion: The Thompson Sampling method (the smart gambler) was the clear winner. It improved the performance of the prompt optimizer by up to 50% on some tasks.
The Comparison: The old method (APET), where the robot guessed, actually performed worse than just picking strategies randomly. This proves that the robot is bad at guessing which tricks to use, but it is great at following instructions if we tell it which trick to use.

The Takeaway

This paper doesn't claim to have solved all AI problems or to be ready for medical diagnosis yet. It simply shows that when we are trying to teach AI how to talk better, we shouldn't let the AI guess which teaching method to use. Instead, we should use a smart, data-driven system (like Thompson Sampling) to explicitly choose the best teaching tricks, just like a coach choosing the right play for a specific game situation.

The code for this "smart coach" is now available for others to use.

Technical Summary: Bandit-Based Prompt Design Strategy Selection

Problem Statement

Prompt optimization aims to automatically search for effective prompts that enhance the performance of Large Language Models (LLMs). While existing discrete prompt optimization methods (e.g., evolutionary algorithms) have successfully discovered effective prompts, these often differ from the sophisticated, carefully crafted prompts designed by human experts. A critical gap exists in leveraging established "prompt design strategies" (best practices like Chain-of-Thought or Role Prompting) within automated optimization.

Recent approaches, such as the Autonomous Prompt Engineering Toolbox (APET), attempt to incorporate these strategies by feeding all available strategy descriptions into an LLM, which then implicitly selects and applies them. However, this implicit selection is prone to suboptimal performance because LLMs may not effectively optimize the selection process, and inappropriate strategies can negatively impact performance depending on the specific task and target LLM. The core problem addressed is the lack of an explicit, robust mechanism to select the most appropriate prompt design strategies during the optimization process.

Methodology

The authors propose OPTS (Optimizing Prompts with sTrategy Selection), a framework that introduces explicit selection mechanisms for prompt design strategies. OPTS is integrated into EvoPrompt, a well-known prompt optimizer that emulates evolutionary algorithms (specifically Genetic Algorithms and Differential Evolution).

Core Components

Strategy Arms: The system defines $K$ arms, each corresponding to a specific prompt design strategy (e.g., Chain-of-Thought, Emotion Prompting, Re-Reading). An additional $(K+1)$ -th "inaction arm" is included, representing the option to apply no strategy modification.
Selection Mechanisms: The paper proposes and evaluates three distinct selection methods:
- OPTS(TS): Uses Thompson Sampling, a multi-armed bandit algorithm. It maintains a probability distribution (Beta distribution priors) for each arm's expected reward. After evaluating a modified prompt, the reward (based on task-solving LLM accuracy) updates the distribution, allowing the system to balance exploration and exploitation of strategies.
- OPTS(US): Uses Uniform Sampling, where each arm (including the inaction arm) is selected with equal probability, serving as a baseline for random strategy application.
- OPTS(APET): Based on the APET method, where an LLM implicitly selects strategies from a list. This version includes an explicit 50% probability of choosing the "inaction arm" to mimic APET's behavior while adding a control for non-modification.
Integration Workflow:
- EvoPrompt generates a new candidate prompt via crossover and mutation.
- The OPTS module selects a strategy (or inaction) based on the chosen mechanism.
- If a strategy is selected, its description is passed to a "Prompt-designing LLM" along with a meta-prompt and the candidate prompt.
- The Prompt-designing LLM modifies the prompt to incorporate the selected strategy.
- The modified prompt is evaluated by the "Task-solving LLM," and the resulting score is used to update the selection distribution (in the case of TS) and determine the next generation's population.

Key Contributions

Explicit Strategy Selection: The paper introduces the first explicit selection mechanisms for prompt design strategies within prompt optimization, moving away from the implicit selection used in prior works like APET.
Thompson Sampling Integration: The authors propose a Thompson sampling-based approach (OPTS(TS)) that empirically demonstrates superior performance in selecting appropriate strategies for specific tasks and LLMs.
Performance Enhancement: The study demonstrates that integrating explicit strategy selection significantly improves the performance of the EvoPrompt optimizer.
Comprehensive Evaluation: The methods are evaluated across 27 challenging tasks from BIG-Bench Hard (BBH) using two different task-solving LLMs (Llama-3-8B-Instruct and GPT-4o mini) and two different evolutionary algorithms (GA and DE).

Experimental Results

Experiments were conducted using BIG-Bench Hard tasks. The task-solving LLMs were Llama-3-8B-Instruct (all 27 tasks) and GPT-4o mini (3 tasks).

Overall Improvement: All three OPTS variants (TS, US, APET) improved the average performance of the baseline EvoPrompt(DE) by approximately 4.5% to 7.5%.
Superiority of Thompson Sampling: OPTS(TS) achieved the best overall results. When using GPT-4o mini for both prompt generation and task solving, OPTS(TS) improved EvoPrompt's performance by up to 50% on specific tasks (e.g., "logical deduction five objects"). On average across BBH tasks with Llama-3-8B-Instruct, OPTS(TS) outperformed OPTS(US) by ~1.7% and OPTS(APET) by ~2.7%.
Comparison with APET: OPTS(APET) performed worse than OPTS(US), suggesting that LLMs have biases that lead to incorrect implicit strategy selection.
Task Variability: The improvement varied by task. For tasks like "ruin names," OPTS(TS) improved performance by ~40% over the baseline. In some cases, performance slightly degraded, but the "inaction arm" ensured that degradation was minimal compared to the gains.
Cost Efficiency: Under a fixed constraint of 500 API calls, OPTS(TS) still outperformed the baseline EvoPrompt, indicating higher cost-effectiveness.

Significance and Claims

The paper claims that the explicit selection of prompt design strategies is a crucial step in advancing prompt optimization. By leveraging existing knowledge of prompt engineering (strategies like Chain-of-Thought) through a bandit-based selection process, OPTS allows optimizers to discover prompts that are not only effective but also structurally aligned with human best practices.

The authors highlight that:

Explicit selection is superior to implicit selection: The LLM's ability to implicitly choose strategies (as in APET) is suboptimal compared to the data-driven selection of Thompson Sampling.
Strategies can be combined: While OPTS(TS) selects one strategy at a time, the resulting optimized prompts often exhibit a combination of strategies (e.g., Chain-of-Thought incorporating Re-Reading), suggesting the optimizer effectively learns to layer these techniques.
Generalizability: The approach is effective regardless of the specific task-solving LLM (Llama-3 or GPT-4o) or the underlying evolutionary algorithm (GA or DE).

The authors maintain a modest stance, noting limitations such as the formulation of OPTS(TS) as a Bernoulli bandit (which could be refined), the lack of testing on other optimizers beyond EvoPrompt, and the potential variability of results based on the specific set of prepared strategies. They conclude that their work underscores the importance of explicitly leveraging and selecting existing prompt design knowledge to enhance LLM performance.