Budgeted Prompt-Set Expansion and Refinement for Language Models via Simulation Optimization

Haoting Zhang; Jinghai He; Rhonda Righter; Zeyu Zheng

stat.MLApr 12, 2024

Budgeted Prompt-Set Expansion and Refinement for Language Models via Simulation Optimization

Authors: Haoting Zhang, Jinghai He, Rhonda Righter, Zeyu Zheng

Organizations: Department of Industrial Engineering and Operations Research, University of California Berkeley

Abstract

A prompt is an instruction or description provided by the user to guide a generative language model toward outputs that meet application requirements. When these requirements change, existing prompts may need to be adapted and improved. Evaluating candidate prompts requires time and computational resources. We therefore study how to expand and refine an initial set of prompts under a limited evaluation budget through simulation optimization, aiming to maximize a pre-defined task score for a fixed language model. Specifically, we propose a two-stage framework. In the first stage, we expand the initial set of prompts into a finite candidate set, where each prompt is represented by a moderate-dimensional vector. In the subsequent stage of evaluation and selection, we construct a surrogate model of the score for moderate-dimensional vectors representing the prompts. We propose sequentially selecting prompts for evaluation using the constructed surrogate model. We prove the consistency of the sequential evaluation procedure in our framework. We further introduce a refinement procedure that uses the collected scores to search beyond the initial candidate set. We also conduct numerical experiments to demonstrate the advantages of our method over baseline prompt selection methods, with higher prompt scores, especially when the budget for calling language models to evaluate prompts is limited.

Figures & tables

Figure 1. An illustration of different prompts leading to different outputs on a common subject. Two prompt-and-response examples about late-night snacks. Adding the requirement that snacks should not affect sleep changes the three food recommendations.

Figure 2. Framework for budgeted prompt-set expansion and refinement. Flowchart of the two-stage framework. Initial text prompts are encoded, perturbed, and projected into prompt representations. Sequential evaluation alternates surrogate updating, acquisition maximization, decoding, language-model evaluation, and score collection. The refinement procedure uses collected scores to adjust the projection and generate further candidates.

z^{(t+1)}\in\arg\max_{z_{n}\in\mathcal{Z}}\alpha_{t}\left(z_{n}\right).

Algorithm 1 General Procedure of the Evaluation and Selection Stage with M-UCB

Panel of Figure 3 — Figure 3. Experimental results for comparing M-UCB with R&S algorithms on time series anomaly detection. The employed LLM is Claude 3.5 Sonnet with $N=100$ prompt representations. The left figure is for credit card fraud detection, and the right figure is for water-pump system failure detection. The solid lines represent the mean values of the F1 score while the shadows are standard deviations. Two line charts compare mean F1 scores against evaluation budget for M-UCB, OCBA, EVI, and KG on credit-card fraud detection and water-pump status prediction. M-UCB has the highest mean across the plotted budgets. Shaded bands show one standard deviation.

$(N,T)$	M-UCB		OCBA		EVI		KG
(20, 50)	$0.57$	(0.031)	$0.58$	(0.025)	$0.53$	(0.022)	$0.56$	(0.024)
(20, 100)	$0.60$	(0.032)	$0.61$	(0.026)	$0.56$	(0.022)	$0.59$	(0.020)
(20, 150)	$0.61$	(0.029)	$0.62$	(0.022)	$0.59$	(0.020)	$0.61$	(0.022)
(20, 250)	$0.62$	(0.027)	$0.63$	(0.021)	$0.60$	(0.019)	$0.62$	(0.018)
(100, 50)	$0.64$	(0.040)	$0.60$	(0.027)	$0.58$	(0.027)	$0.55$	(0.020)
(100, 100)	$0.69$	(0.036)	$0.66$	(0.026)	$0.61$	(0.025)	$0.60$	(0.022)

Table 1. Joint effects of number of prompt representations (

N

) and total budget (

T

) on the selected prompt performance for M-UCB and R&S algorithms based on the credit card fraud detection dataset. Values show the mean F1 score with standard deviation in parentheses. The employed LLM is Claude 3.5 Sonnet.

Figure 4. Best attainable F1 score within candidate sets of different sizes on the two anomaly detection datasets, using Claude 3.5 Sonnet. The smaller sets are fully included in the larger sets. Each prompt’s F1 score is estimated using all data points in the dataset; the plotted value is the highest score within the set. Two line charts show the best attainable F1 score as the candidate set grows for credit-card fraud detection and water-pump status prediction. Results are compared across nested sets of prompt representations.

Table 2. Prompt improvement and refinement-budget allocation on IndustryOR under a fixed total budget of

T=1000

API calls. Reported accuracy is mean

\pm

std over 3 repetitions. The last 100, 200, or 400 calls are reserved for refinement.

Method	Score @ 2M Tokens	Score @ 5M Tokens	Score @ 10M Tokens
M-UCB	$1.42$	$1.73$	$2.11$
APE	$1.17$	$1.38$	$2.07$
OPRO	$1.08$	$1.35$	$1.96$

Table 3. Preference-judging scores under total token budgets covering both prompt generation and evaluation. Higher scores indicate stronger preference for the human-preferred response.

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

$(N,T)$	M-UCB		OCBA		EVI		KG
(20, 50)	$0.59$	(0.038)	$0.57$	(0.029)	$0.56$	(0.034)	$0.55$	(0.023)
(20, 100)	$0.60$	(0.031)	$0.60$	(0.032)	$0.57$	(0.030)	$0.57$	(0.022)
(20, 150)	$0.60$	(0.027)	$0.61$	(0.022)	$0.57$	(0.025)	$0.61$	(0.020)
(20, 250)	$0.62$	(0.013)	$0.65$	(0.019)	$0.60$	(0.021)	$0.61$	(0.022)
(100, 50)	$0.60$	(0.034)	$0.58$	(0.037)	$0.54$	(0.039)	$0.56$	(0.032)
(100, 100)	$0.62$	(0.033)	$0.60$	(0.034)	$0.61$	(0.037)	$0.58$	(0.030)

Appendix

Table 4. Joint effects of number of prompt representations (

N

) and total budget (

T

) on the selected prompt performance for M-UCB and R&S algorithms based on the water pump system failure dataset. Values show the mean F1 score with standard deviation in parentheses. The employed LLM is Claude 3.5 Sonnet.

Figure 5. The F1 scores of M-UCB and OCBA based on the credit card fraud detection with $N=500$ prompt representations and $T=250$ evaluation calls. The employed LLMs include 1) Claude 3.5 Sonnet, 2) Gemini 2.0 Flash, 3) GPT-4o, and 4) Qwen2.5 32B. Grouped bars compare mean F1 scores of M-UCB and OCBA for credit-card fraud detection across Claude 3.5 Sonnet, Gemini 2.0 Flash, GPT-4o, and Qwen 2.5 32B. M-UCB has the higher mean for each model.

Figure 6. The F1 scores of M-UCB and OCBA based on the water-pump system failure dataset with $N=500$ prompt representations and $T=250$ evaluation calls. The employed LLMs include 1) Claude 3.5 Sonnet, 2) Gemini 2.0 Flash, 3) GPT-4o, and 4) Qwen2.5 32B. Grouped bars compare mean F1 scores of M-UCB and OCBA for water-pump status prediction across Claude 3.5 Sonnet, Gemini 2.0 Flash, GPT-4o, and Qwen 2.5 32B. M-UCB has the higher mean for each model.

Figure 7. The score trajectories of the compared token-space black-box optimization methods. The solid line is the mean value of the prompt score calculated using the held-out test dataset, and the shadow represents the standard deviation. Line chart of accuracy against the number of API calls for the IndustryOR task with Claude 4 Sonnet. The curves compare RLPrompt, BDPL, and M-UCB-r, with shaded variability bands. M-UCB-r has the highest mean accuracy at the plotted budgets.

Table 5. IndustryOR results stratified by difficulty (Easy/Medium/Hard) under a fixed budget of 1000 API calls. The recorded metric is the accuracy of LLMs’ output under the instructions from the selected prompt.

	10 calls		50 calls
Method	Score	Tokens Used	Score	Tokens Used
M-UCB	$1.21$	$\sim 0.6\,\mathrm{M}$	$1.55$	$\sim 3.1\,\mathrm{M}$
APE	$1.13$	$\sim 1.7\,\mathrm{M}$	$1.86$	$\sim 8.6\,\mathrm{M}$
OPRO	$1.10$	$\sim 2.1\,\mathrm{M}$	$2.02$	$\sim 15.5\,\mathrm{M}$

Appendix

Table 6. Comparison of methods when each is allowed a fixed number of LLM calls.

Panel of Figure 8 — Figure 8. Experimental results for approximating the mean score with the prompt representations using different Bayesian parametric models. The task is word sorting and the generative language model is text-davinci-003. Two line charts compare surrogate root mean squared error and coverage ratio as the number of prompt representations increases on the word-sorting task with text-davinci-003. The models are BLR, GP, VAE, and BNN.

Panel of Figure 9 — Figure 9. Experimental results for approximating the mean score with the prompt representations using different Bayesian parametric models. The task is word sorting and the generative language model is GPT-3.5-turbo. Two line charts compare surrogate root mean squared error and coverage ratio as the number of prompt representations increases on the word-sorting task with GPT-3.5-turbo. The models are BLR, GP, VAE, and BNN.

Panel of Figure 10 — Figure 10. Experimental results for comparison between two acquisition functions: M-UCB and PR-M-UCB (number of starting points, number of gradient ascent iterations). The task is finding the largest animals given the names and the generative language model is GPT-3.5-turbo. Two line charts compare the mean score of the selected prompt and optimization time against candidate-set size on the largest-animals task with GPT-3.5-turbo. The curves show M-UCB and three PR-M-UCB configurations.

Panel of Figure 11 — Figure 11. Experimental results for comparison between two acquisition functions: M-UCB and PR-M-UCB (number of starting points, number of gradient ascent iterations). The task is word sorting and the generative language model is text-davinci-003. Two line charts compare the mean score of the selected prompt and optimization time against candidate-set size on the word-sorting task with text-davinci-003. The curves show M-UCB and three PR-M-UCB configurations.

Panel of Figure 12 — Figure 12. Experimental results for comparison between the proposed two-stage framework and the direct search in the latent space with PSK. The pair of task and generative language model includes 1) counting objects with GPT-3.5-turbo (left) and 2) finding the rhymes with text-davinci-003 (right). PR-M-UCB-r uses 20 additional evaluation calls beyond $T$ for refinement. Two line charts compare selected-prompt scores against evaluation budget for PSK-EI, PR-M-UCB, and PR-M-UCB-r. The tasks are counting objects with GPT-3.5-turbo and generating rhymes with text-davinci-003.

Panel of Figure 13 — Figure 13. The mean score of the selected prompts in six tasks. The generative language model used to implement the tasks is GPT-3.5-turbo. The budget before refinement is $T=500$ ; M-UCB-r uses 20 additional evaluation calls. Radar chart comparing M-UCB, PSK-EI, M-UCB-r, and random search on six task axes: word sorting, first letter, counting objects, rhymes, numbers to verbal, and largest animals.

Task	GPT-3.5-turbo	text-davinci-003
word sorting	Sort the following word list in alphabetic order.	Sort the words in alphabet order.
first letter	Return the first letter of the selected word.	Select the initial letter in the word.
counting objects	Count the total number of mentioned products.	Estimate the total quantity for all products.
rhymes	Choose the word with the closest pronunciation.	Select the word with most similar pronunciation.
nums to verbal	Turn number list to word list.	Turn number list to word list.
largest animals	Choose the larger animal from the following animals.	Select the largest animals in size.

Appendix

Table 7. Selected prompts for six tasks using M-UCB-r.

Prompt Optimization

Prompt optimization automates the revision or selection of instructions and other prompt components to improve model behavior for specific tasks.

See all 140 papers

RLMOpt: Adaptive Prompt Optimization via Recursive Language Models
Aug 11, 2026Subhash Bangalore Satheesha, Nirvik Pande, Deepthi Duddempudi +1Large Language Model-Guided Optimization LLM Agents
Autonomize AI · Carnegie Mellon University
How Should a Prompt Optimizer Spend a Tight Budget? BudgetAPO with Noise-Adaptive Evaluation
Oct 5, 2026Haoyue Liu, Zhichao Wang, Huanyu Yan +1Automatic Prompt Optimization Prompt Optimization
School of Science and Engineering, The Chinese University of Hong Kong, Shenzhen · Shenzhen Future Network of Intelligence Institute (FNii-Shenzhen) · Guangdong Provincial Key Laboratory of Future Networks of Intelligence, CUHK(SZ)
$p1$ : Better Prompt Optimization with Fewer Prompts
Apr 9, 2026Zhaolin Gao, Yu, Wang +4Automatic Prompt Optimization Large Language Model-Guided Optimization
Sid · Cornell University · Microsoft +2

Aug 11, 2026J/K move · Enter open · S save

RLMOpt: Adaptive Prompt Optimization via Recursive Language Models

Subhash Bangalore Satheesha, Nirvik Pande, Deepthi Duddempudi, Bharath Dandala

Autonomize AI · Carnegie Mellon University

Large Language Model-Guided Optimization LLM Agents Prompt Optimization Recursive Language Models LLM Input Optimization

Open paper AskPDF arXiv

Prompt optimizers automate the search for prompts that improve language-model performance, but existing methods rely on a predefined optimization procedure: the algorithm determines which candidates to explore and how the search progresses, while the language model generates or refines prompt proposals. We introduce RLMOpt, a prompt optimizer that makes the search policy itself language-model-driven through a recursive language model (RLM). The RLM agent operates over a tool-based environment, inspecting task information, analyzing failures, generating candidates, allocating evaluation budget, and deciding when to stop. A deterministic harness complements the agent by enforcing objective scoring, Pareto-based selection, and regression constraints. We evaluate RLMOpt across four benchmarks spanning structured clinical information extraction (Chia), multi-hop question answering (HotpotQA), verifiable instruction following (IFBench-2025), and multi-turn tool-calling agents (BFCL). In a matched comparison at a single seed, RLMOpt obtains the best held-out score on all four benchmarks and leads the four-task mean (0.610 against 0.589 for GEPA). Repeating each benchmark across seeds yields 11 matched benchmark-seed comparisons, in which RLMOpt outperforms GEPA in 9 cases. Across all 11 runs, it never produced a prompt that underperformed its seed, whereas GEPA fell below its starting point twice. It is also more efficient, achieving these results with fewer search rollouts while producing prompts that are 27-79% the size of those produced by GEPA. Our results further show that optimization gains are determined primarily by the headroom available in the seed prompt, rather than by the search budget. Efficient optimization therefore depends on reaching the available headroom reliably and with minimal search

Abstract

Prompt Optimization

Explore similar work

RLMOpt: Adaptive Prompt Optimization via Recursive Language Models

How Should a Prompt Optimizer Spend a Tight Budget? BudgetAPO with Noise-Adaptive Evaluation

p1p1p1: Better Prompt Optimization with Fewer Prompts

$p1$ : Better Prompt Optimization with Fewer Prompts