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

Haoyue Liu; Zhichao Wang; Huanyu Yan; Xiaoying Tang

cs.AIOct 5, 2026

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

Authors: Haoyue Liu, Zhichao Wang, Huanyu Yan, Xiaoying Tang

Organizations: 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)

Abstract

Automatic prompt optimization (APO) has been widely employed to adapt large language models without updating their weights, yielding promising results. However, existing methods such as GEPA and OPRO assume hundreds to thousands of subject-model calls, far more than is practical behind paid, rate-limited APIs. Under tight budgets they fail in two ways: multi-stage pipelines can exhaust the budget and return the seed prompt unchanged, while single-stage methods compare candidates on fixed-size minibatches, regardless of each task's noise. As a remedy, we introduce BudgetAPO, a single-stage optimizer for the tight-budget regime. BudgetAPO incorporates (1) a noise-adaptive rule that sizes the evaluation slice to each task's noise, measured by a short probe; (2) a fixed slice that turns every accept/reject decision into a paired comparison; and (3) a reflective operator that rewrites reasoning strategy and output format jointly. Extensive results across seven benchmarks and five subject models demonstrate that BudgetAPO ranks first on every subject and beats every baseline under Holm-corrected paired tests, while returning the seed in 13% of runs at 250 calls against 86% for GEPA. On GPT-OSS-20B, GEPA needs 4.5 times as many calls to match BudgetAPO's 100-call score.

Figures & tables

Figure 1: (a) Test score against budget, GPT-OSS-20B; bands: standard error over seeds. (b) Seed-return rate at a 250-call cap, 105 runs per method.

Figure 2: One BudgetAPO run. Calibration spends 16 calls to read $\hat{\sigma}$ , which fixes a slice of $s$ rows; each refinement round spends $k\,s$ calls (Equation 5 ) and keeps a candidate only if it beats the incumbent (Equation 7 ).

Figure 3: (a) How a 250-call cap divides at each benchmark’s mean slice size (Equation 5 ): a larger slice buys fewer rounds. (b) Probe standard deviation

\hat{\sigma}

against the chosen slice, one point per run; the tasks of (a) in color.

Figure 4: Analysis at a 250-call cap, except (a). (a) Seed returns against budget, primary subject. (b) Rewrite rate against the share of rewrites more than one point below the seed. (c) Candidate scores and running best in one HotpotQA and one StackEval run. (d) Gain as a share of the headroom to 100. (e) Reply length and share truncated at the token cap. (f) Place over the 35 cells, darkest = first. (g) Gain over the seed per run; whiskers: 10th–90th percentiles. (h) Share of the final slice gain reached against budget spent (91 runs); band: standard error. (b), (d), (e), (g) pool 105 runs per method.

Figure 5: Prompt transfer on five of the seven tasks. Change against the seed prompt when the prompt optimized on the row’s task is scored on the column’s test pool (GPT-OSS-20B, budget 250). Boxed: the source task.

Figure 6: Hyper-parameter sensitivity , primary subject: change in the seven-benchmark mean against the default (

\star

), paired by seed; bars: seed standard deviation. (c, d): a separate batch, read against its own Full (Appendix L ).

Benchmark	Full	$-$ Adapt.	$-$ Fixed	$-$ Strat.	$-$ Fail.
HotpotQA	74.3	66.1	65.9	68.8	73.2
CollIE	74.2	70.8	72.7	69.8	70.0
IFBench	62.7	62.7	65.2	61.2	63.6
SuperGPQA	60.5	61.2	61.5	62.5	62.5
StackEval	78.7	78.7	78.6	77.7	77.5
MBPP+	81.3	81.1	79.3	81.1	80.2

Table 2: Ablations, primary subject (%, budget 250); each column removes one component against the shaded Full entry.

-

Adapt.: fixed

s{=}20

, probe still spent.

-

Fixed: slice redrawn every step, incumbent re-scored on it.

-

Strat.: plain “raise the score” request, no failing rows.

-

Fail.: strategy and format kept, no failing rows.

	Opt.: GLM-5-FP8			Opt.: Qwen-3.5-27B
Benchmark	Ours	GEPA	OPRO	Ours	GEPA	OPRO
HotpotQA	68.9	50.2	49.7	69.8	50.9	48.6
CollIE	76.5	68.3	71.5	70.5	69.5	74.0
IFBench	64.5	57.5	64.0	65.0	59.5	63.3
SuperGPQA	63.0	61.5	61.5	62.5	61.0	65.0
StackEval	78.3	78.0	77.5	78.4	77.6	75.8

Table 3: Optimizer swap, primary subject (%, seed 0, budget 250); Ours is BudgetAPO .

Appendix figures & tables14 assets

Supplementary material from the paper’s appendix.

Appendix

Benchmark	$\|\mathcal{R}_{\text{cal}}\|$	$\|\mathcal{R}_{\text{opt}}\|$	$\|\mathcal{R}_{\text{test}}\|$
HotpotQA	150	300	200
CollIE	150	300	200
IFBench	150	300	200
SuperGPQA	150	300	200
StackEval	150	300	200
MBPP+	78	150	150

Appendix

Table 4: Benchmark data splits (number of rows). Identical for all five subject models.

Benchmark	Spread (pt)	BudgetAPO $\Delta$
MBPP+	6.77	$-0.11$
IFBench	6.73	$-0.85$
HotpotQA	5.19	$+3.51$
CollIE	5.18	$+1.40$
StackEval	2.68	$+1.15$
SuperGPQA	2.11	$+1.15$

Appendix

Table 5: Baseline spread per benchmark (Table 1 b): best minus worst of the five baselines over five subjects and three seeds, BudgetAPO excluded.

\Delta

: BudgetAPO ’s margin over the best baseline. Last row: both quantities on the seven-task mean scores.

Subject	Method	Hotpot	CollIE	IFBench	SuperGPQA	Stack	MBPP+	LB-IF	Avg
Subject = Gemma-4-31B
	No optimization	50.56	67.50	57.75	61.00	77.41	77.33	67.37	65.56
	GEPA	54.31 $\pm$ 3.91	69.45 $\pm$ 1.78	57.83 $\pm$ 1.53	61.83 $\pm$ 0.58	77.79 $\pm$ 0.32	80.44 $\pm$ 1.39	68.10 $\pm$ 1.42	67.11
	OPRO	52.00 $\pm$ 3.00	71.67 $\pm$ 1.26	63.92 $\pm$ 1.13	60.50 $\pm$ 1.73	77.96 $\pm$ 1.02	79.33 $\pm$ 2.00	67.64 $\pm$ 0.72	67.58
	MIPROv2	49.79 $\pm$ 4.45	70.67 $\pm$ 0.76	64.33 $\pm$ 1.88	61.50 $\pm$ 0.50	73.38 $\pm$ 4.66	79.33 $\pm$ 2.67	67.37 $\pm$ 0.05	66.62
	GrIPS	57.12 $\pm$ 1.98	68.11 $\pm$ 0.20	56.92 $\pm$ 1.84	61.33 $\pm$ 1.26	77.46 $\pm$ 0.73	80.89 $\pm$ 1.02	66.92 $\pm$ 0.48	66.97

Appendix

Table 6: Main result per cell. Test score (%) at a 250-call cap, mean

{}_{\pm\text{std}}

over seeds 0/1/2 (sample standard deviation); all methods share optimizer, budget, decoding and seed prompt. No optimization : the seed prompt at seed 0. Bold : within each subject, each task column’s best and every entry within one standard error of it; significance is in Table 7 . Shaded: BudgetAPO , with its margin over the best baseline in green .

Baseline	$\Delta$ (pt)	Cohen $d_{z}$	Wins	$p_{\text{Holm}}$
GrIPS	+3.75	0.819	29/35	$4.5\!\times\!10^{-5}$
GEPA	+3.59	0.682	26/35	$3.9\!\times\!10^{-4}$
OPRO	+1.98	0.480	25/35	$1.2\!\times\!10^{-3}$
aPSF	+2.37	0.577	24/35	$3.1\!\times\!10^{-3}$
MIPROv2	+2.49	0.472	23/35	$5.9\!\times\!10^{-3}$

Appendix

Table 7: Paired Wilcoxon tests against each baseline over the 35 (subject, benchmark) cells, seeds averaged.

\Delta

: mean margin in points. Wins : cells where BudgetAPO scores higher.

p

: Holm-corrected.

Method	100	150	200	250	300	350	400	450	500
BudgetAPO	64.9	67.0	65.7	65.2	66.2	66.4	65.6	64.4	65.1
GEPA	59.2	59.3	59.9	60.1	60.0	64.3	64.3	65.0	65.2
OPRO	61.2	61.9	62.7	63.2	63.0	62.6	63.0	64.3	63.3
MIPROv2	62.9	62.9	61.9	63.8	64.4	63.8	63.8	62.6	64.9
GrIPS	58.5	58.7	59.4	59.4	59.5	59.6	59.0	58.9	59.3
aPSF	65.0	63.5	65.2	62.4	65.4	65.0	63.7	64.1	65.0

Appendix

Table 8: Budget curve, full range. Mean test score (%) over the seven benchmarks and three seeds, GPT-OSS-20B. Figure 1 (a) draws 100–400; 450 and 500 are here. GEPA needs 450 calls to reach BudgetAPO ’s 100-call score.

Method	Gemma	GPT-OSS	Qwen	Nemo.	Minis.	All
BudgetAPO	5	10	24	14	14	13
GEPA	71	81	90	90	95	86
OPRO	33	5	43	19	19	24
GrIPS	14	10	19	19	19	16
MIPROv2	0	0	0	0	0	0
aPSF	0	0	0	0	0	0

Appendix

Table 9: Seed return (%) by subject under a 250-call cap; 21 runs per cell, 105 per method. MIPROv2 and aPSF always rewrite.

	Benchmark	Seeds	Full	Variant	$\Delta$
Replace	CollIE	0–2	74.17	71.83	$-2.33$
	HotpotQA	0–2	74.34	53.76	$-20.58$
	IFBench	0–2	62.75	59.25	$-3.50$
	nine cells				$-8.80$
Add	IFBench	0–1	64.88	59.75	$-5.13$

Appendix

Table 10: Failure-histogram feedback, primary subject (test score in %, budget 250). Replace : the histogram replaces one of the three failing rows; Add : it is added to all three. Full is the main-table run at the same seeds;

\Delta

is the variant minus Full.

Benchmark	Full	$\tau{=}.05$	$\tau{=}.15$	$\tau{=}.20$	$k{=}1$	$k{=}3$
HotpotQA	74.3	65.0	61.5	60.9	74.9	68.9
CollIE	74.2	72.8	70.2	71.2	71.8	73.0
IFBench	62.7	62.8	63.1	61.8	63.9	62.7
SuperGPQA	60.5	63.0	62.3	62.0	60.0	61.0
StackEval	78.7	78.1	78.3	78.5	77.8	77.7
MBPP+	81.3	81.8	80.4	81.6	80.2	80.9

Appendix

Table 11: Hyper-parameter sweeps per benchmark, primary subject (test score in %, budget 250, mean over three seeds). Top: main runs, read against Full. Bottom: the separate batch for probe rows

n

(

n_{\mathrm{probe}}

) and lower clamp

s

(

s_{\min}

, upper clamp 30), read against its own Full † . Figure 6 plots the paired differences.

$\tau$	Range	At $s_{\min}$	At $s_{\max}$	Adaptive
0.05	15–30	0/21	15/21	6/21
0.10 (default)	10–25	29/61	0/61	32/61
0.15	10–11	17/21	0/21	4/21
0.20	10	21/21	0/21	0/21

Appendix

Table 12: Slice sizes chosen by Equation 4 under each target SE, primary subject, 21 runs per setting (61 for the default, which includes the main-table runs).

Method	Mean	Std.
BudgetAPO	71.57	0.50
GrIPS	66.97	0.48
MIPROv2	66.62	0.50
OPRO	67.58	0.91
GEPA	67.11	1.38
aPSF	68.85	1.86

Appendix

Table 13: Seven-benchmark mean test score (%) and its standard deviation across three seeds (points), budget 250, primary subject (Gemma-4-31B).

Figure 7: Every candidate of one run on HotpotQA and on StackEval (Gemma-4-31B, seed 0, budget 250): grey dots rejected, diamonds accepted, step line the incumbent.

Figure 8: Slice fitness against test-half-B score over 35 (subject, benchmark) cells, one seed-0 BudgetAPO run per panel. Spearman

\rho

: green

\geq 0.3

, red

\leq-0.3

, gray otherwise, n/a for a constant slice score; dashed lines are least-squares fits.

Benchmark	Rows	Total	$\Delta$	$\Delta$ enlarged
HotpotQA	200	1000	$+11.63$	$+9.92$
CollIE	200	731	$+2.50$	$+1.46$
SuperGPQA	200	1000	$-1.83$	$-1.44$
StackEval	200	1000	$+0.70$	$+0.64$

Appendix

Table 14: Shipped prompts re-scored on an enlarged test set (primary subject, three seeds, no re-optimization); scores pool the original and the added rows, which are shared by all methods.

\Delta

: BudgetAPO ’s margin over the strongest baseline.

	GEPA		BudgetAPO
Benchmark	Words	Calls	Words	Calls
HotpotQA	5	250	220	246
CollIE	5	250	417	223
IFBench	5	250	249	246
SuperGPQA	5	250	126	223
StackEval	5	250	162	246

Appendix

Table 15: What each method shipped on the primary subject at seed 0, budget 250. Words is the length of the returned prompt; a five-word prompt is the unchanged seed. Calls is the budget actually spent.

Explore similar work

May 15, 2026cs.LG

MO-CAPO: Multi-Objective Cost-Aware Prompt Optimization

Large language models (LLMs) achieve strong performance across a wide range of tasks but are highly sensitive to prompt design, motivating the need for automatic prompt optimization. Existing methods predominantly focus on performance alone, ignoring competing objectives such as inference cost or latency. At the same time, existing work on multi-objective prompt optimization relies on off-the-shelf NSGA-II, ignoring optimization efficiency. As a remedy, we introduce MO-CAPO, a novel multi-objective prompt optimization algorithm that jointly optimizes performance and inference cost while leveraging budget allocation for cost-efficient optimization. We further propose a deployment-oriented cost objective that captures the full computational profile of LLM inference. We evaluate our approach across four tasks and three LLMs and compare it to an NSGA-II-based multi-objective method and state-of-the-art single-objective prompt optimizers. Results show that MO-CAPO consistently identifies strong, robust, and diverse Pareto front approximations while maintaining cost-efficiency. It outperforms the NSGA-II baseline on 8 out of 12 cases in terms of the noisy R2 metric and achieves competitive performances often already at a considerably lower budget. The discovered solution sets span diverse performance-cost trade-offs that are omitted by single-objective optimizers, yet the top-performance candidates remain competitive with single-objective solutions. Additionally, we conduct the first evaluation of multi-objective machine learning experiments that considers generalization and robustness through noisy R2 and approximation gap, enabling a more realistic assessment of solution quality. MO-CAPO enables practitioners to select from an efficiently discovered set of multiple prompts offering different trade-offs between performance and cost.

Jan Büssing, Moritz Schlager, Timo Heiß +2

LMU Munich, Germany · Technical University of Munich (TUM), Munich Center for Machine Learning (MCML), Germany · LMU Munich, Munich Center for Machine Learning (MCML), Germany +2

Inference Cost Prompt Engineering

Ask PDF

Jul 21, 2026cs.AI

From Monolithic to Modular: Segment-level Automatic Prompt Optimization

Automatic Prompt Optimization (APO) often rewrites prompts monolithically, which can improve one behavior while degrading others. We present SAPO, a segment-level APO method that decomposes prompts into role, context, tasks, and output format, then applies targeted improvements based on top-5 and bottom-5 examples. The optimization loop uses one LLM with static meta-prompts and structured outputs for segmentation, weakness analysis, and candidate generation. We describe a train/validation protocol and a two-stage generation process: (1) segment-level diagnosis and recommendation extraction, (2) candidate synthesis constrained by weak/strong segment signals. Using the evaluation setup across SQuADv2, TweetEval, XSUM, CommonGen, and GSM8K on GPT-3.5-Turbo and GPT-4o-mini, SAPO achieves the best average score against Zero-shot and strong APO baselines including APE, OPRO, EvoPrompt, GEPA, and StraGO.

Nikita Kulin, Viktor Zhuravlev, Artur Khairullin +4

ITMO University · HSE · AXXX

Prior Prompt Optimization Techniques Automatic Prompt Optimization Prompt Engineering Modular Framework

Ask PDF

Sep 3, 2026cs.CL

ESPO: Error-Structured Prompt Optimization via Diagnose, Diversify, and Stabilize

Evolutionary prompt optimizers such as GEPA suffer from prompt bloat: each iteration appends rules and caveats, producing prompts up to 3

\times

longer yet no more accurate. We trace this to three deficiencies - incomplete error observation, limited search diversity, and unreliable selection - and propose ESPO (Error-Structured Prompt Optimization), which decomposes prompt optimization into three phases: Diagnose clusters all training errors into structural patterns in one round; Propose generates candidates via four complementary strategies with independent biases; Select applies bootstrap stability selection. On seven public NLP benchmarks - Tweet, MMLU, GSM8K, HotpotQA, ScoNe, HoVer, and PUPA - ESPO improves average accuracy by

+

3.76 pp over the state-of-the-art (74.67% vs 70.91% for GEPA), matching or exceeding GEPA on every dataset while producing prompts 47% shorter (1,004 vs 1,878 chars) and faster at inference. Cross-model experiments across four additional student models (Gemma 3 12B, Mistral 14B, Qwen3 32B, Claude Haiku 4.5) show ESPO yields the best average accuracy on every model tested, with the largest gap on Qwen3 GSM8K (15.00%

\to

91.40%). A generalization bound (Appendix) grounds each phase in a corresponding term of the test-time gap, and the ablation confirms a key prediction: adding diversity without bootstrap selection actually hurts performance (

-

1.20%).

Lihao Liu, Peng Tang, Kunwar Yashraj Singh +1

AWS Agentic AI

Automatic Prompt Optimization Instruction-Tuned Models Prompt Optimization Natural Language Processing Model Selection Diagnosis

Ask PDF