# Bandit-Based Prompt Design Strategy Selection Improves Prompt Optimizers

arXiv: https://arxiv.org/abs/2503.01163 · HTML: https://mlsanity.com/paper/2503.01163/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 33 references that are in the map.
- First posted on arXiv 3 Mar 2025.

## Builds on (most cited first, 15 of 15)

- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Them](https://mlsanity.com/paper/2210.09261/) (2022)
- [Large Language Models as Optimizers](https://mlsanity.com/paper/2309.03409/) (2023)
- [Automatic Prompt Optimization with "Gradient Descent" and Beam Search](https://mlsanity.com/paper/2305.03495/) (2023)
- [Capabilities of GPT-4 on Medical Challenge Problems](https://mlsanity.com/paper/2303.13375/) (2023)
- [Promptbreeder: Self-Referential Self-Improvement Via Prompt Evolution](https://mlsanity.com/paper/2309.16797/) (2023)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [PromptAgent: Strategic Planning with Language Models Enables Expert-level Prompt Optimization](https://mlsanity.com/paper/2310.16427/) (2023)
- [Large Language Models Understand and Can be Enhanced by Emotional Stimuli](https://mlsanity.com/paper/2307.11760/) (2023)
- [ExpertPrompting: Instructing Large Language Models to be Distinguished Experts](https://mlsanity.com/paper/2305.14688/) (2023)
- [Rephrase and Respond: Let Large Language Models Ask Better Questions for Themselves](https://mlsanity.com/paper/2311.04205/) (2023)
- [Principled Instructions Are All You Need for Questioning LLaMA-1/2, GPT-3.5/4](https://mlsanity.com/paper/2312.16171/) (2023)
- [PromptWizard: Task-Aware Prompt Optimization Framework](https://mlsanity.com/paper/2405.18369/) (2024)
- [Prompt Optimization via Adversarial In-Context Learning](https://mlsanity.com/paper/2312.02614/) (2023)
- [Bounding the Capabilities of Large Language Models in Open Text Generation with Prompt Constraints](https://mlsanity.com/paper/2302.09185/) (2023)

## Built on by (most cited first, 9 of 9)

- [LLM Prompt Duel Optimizer: Efficient Label-Free Prompt Optimization](https://mlsanity.com/paper/2510.13907/) (2025)
- [Multimodal Prompt Optimization: Why Not Leverage Multiple Modalities for MLLMs](https://mlsanity.com/paper/2510.09201/) (2025)
- [Towards Reliable LLM Evaluation: Correcting the Winner's Curse in Adaptive Benchmarking](https://mlsanity.com/paper/2605.05973/) (2026)
- [Evolving Skill-Structured Attack Memory Enhances LLM Jailbreaking](https://mlsanity.com/paper/2605.29237/) (2026)
- [Cost-Aware Multi-Objective Bandits: Theory and Application to Budgeted LLM Configuration Evaluation](https://mlsanity.com/paper/2608.04333/) (2026)
- [A Component-Based Survey of Interactions between Large Language Models and Multi-Armed Bandits](https://mlsanity.com/paper/2601.12945/) (2026)
- [Progressive Content Refinement with Decaying Reward Joint LinUCB](https://mlsanity.com/paper/2608.06750/) (2026)
- [StraTune: Adaptive Selection of Revision Operators for Self-Evolving LLM Skills](https://mlsanity.com/paper/2609.32886/) (2026)
- [Fusion is the New Mutation: Bandit-Guided Evolution on Workflow Graphs](https://mlsanity.com/paper/2610.05284/) (2026)

## Abstract (arXiv)

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 .