Select Smarter, Not More: Prompt-Aware Evaluation Scheduling with Submodular Guarantees

Xiaoyu Ma; Yiwen Li; Haoyue Liu; Zhichao Wang; Ye Chen; Yongxin Guo; Xiaoying Tang

cs.AIApr 13, 2026

Select Smarter, Not More: Prompt-Aware Evaluation Scheduling with Submodular Guarantees

Authors: Xiaoyu Ma, Yiwen Li, Haoyue Liu, Zhichao Wang, Ye Chen, Yongxin Guo, Xiaoying Tang

Organizations: The Chinese University of Hong Kong, Shenzhen · Xi’an Jiaotong University · Taobao and Tmall Group

Abstract

Automatic prompt optimization (APO) hinges on the quality of its evaluation signal, yet scoring every prompt candidate on the full training set is prohibitively expensive. Existing methods either fix a single evaluation subset before optimization begins (principled but prompt-agnostic) or adapt it heuristically during optimization (flexible but unstable and lacking formal guarantees). We observe that APO naturally maps to an online adaptive testing problem: prompts are examinees, training examples are test items, and the scheduler should select items that best discriminate among the strongest candidates. This insight motivates Prompt-Aware Online Evaluation Scheduling (POES), which integrates an IRT-based discrimination utility, a facility-location coverage term, and switching-cost-aware warm-start swaps into a unified objective that is provably monotone submodular, yielding a (1-1/e) greedy guarantee for cold starts and bounded drift for warm-start updates. An adaptive controller modulates the exploration-exploitation balance based on optimization progress. Across 36 tasks spanning three benchmark families, POES achieves the highest overall average accuracy (6.2 percent improvement over the best baseline) with negligible token overhead (approximately 4 percent) at the same evaluation budget. Moreover, principled selection at k = 20 examples matches or exceeds the performance of naive evaluation at k = 30-50, reducing token consumption by 35-60 percent, showing that selecting smarter is more effective than selecting more. Our results demonstrate that evaluation scheduling is a first-class component of APO, not an implementation detail.

Figures & tables

Figure 1: (a) Optimization curves on BBH Navigate: static baselines plateau while POES (red) continues improving via prompt-aware subset adaptation, achieving +8.3% over the best baseline. (b) Accuracy vs. token consumption: POES at

k{=}20

dominates all baselines (high accuracy, moderate cost); at

k{=}10

it stays close to baseline accuracy (0.804 vs. 0.820) with 34% fewer tokens.

Figure 2: Overview of the POES framework. The scheduler (dashed box) integrates five components: (1) auto warmup for noisy early rounds, (2) IRT-based discrimination utility, (3) facility-location coverage, (4) warm-start swap optimization of the composite objective $G_{t}$ , and (5) an adaptive controller that adjusts $(\tau_{t},B_{t},\lambda_{t})$ . The selected subset $S_{t}$ feeds back to the evaluation module, closing the optimization loop.

Figure 3: Per-task accuracy comparison on rank-1 tasks (OPRO

\times

Llama-3.1-8B). Top row: BBH reasoning tasks; bottom row: Math and BigBench tasks. Red annotations show the POES score when it is the best or tied-best method. POES achieves the highest score on all 10 selected tasks.

Panel of Figure 4 — Figure 4: Analysis and ablation. (a) POES outperforms the baseline average on 86% of tasks (30W/1T/5L). (b) Improvement correlates negatively with baseline accuracy ( $r{=}{-}0.40$ , $p{=}0.016$ ): gains are largest on harder tasks. (c) Waterfall decomposes the 12.8pp ablation gain: adaptive (+6.5pp), warmup (+5.5pp), coverage (+0.8pp). (d) Warm-start matches or exceeds cold-start on all 4 tasks ( $+9\%$ BBH Navigate, $+11\%$ BB Navigate), confirming subset stability improves optimization signal quality.

	Reasoning & Knowledge			Mathematics
Method	BBH (27)	BigBench (5)	MMLU (57)	GSM8K	GSM-Hard	MATH	MultiArith	Mean
Panel A: OPRO $\times$ Llama-3.1-8B-Instruct
Random	0.809	0.748	0.440	0.853	0.689	0.775	0.933	0.750
SESS	0.817	0.719	0.435	0.728	0.686	0.720	0.850	0.708
IPOMP	0.833	0.758	0.455	0.907	0.667	0.767	0.892	0.754
Anchor	0.798	0.709	0.442	0.892	0.727	0.735	0.783	0.727

Table 1: Cross-optimizer and cross-model generalization across benchmark families. Panel A shows the full method comparison for OPRO

\times

Llama-3.1-8B; Panels B–F report results under other optimizer–model settings. Bold : best per column; underline: second best.

Task	POES	No-AutoWarmup	No-Coverage	No-Adaptive	Disc+Cov
Dyck Languages	0.900	0.900	0.860	0.750	0.790
Navigate	0.890	0.775	0.797	0.725	0.855
GSM-Hard	0.754	0.750	0.693	0.680	0.722
MATH	0.900	0.775	0.812	0.694	0.739
MultiArith	0.983	0.950	0.946	0.938	0.992

Table 2: Ablation study. Each column removes or replaces one component. Bold : best per task.

		Accuracy					Token		Time
	Method	Dyck	GSM-Hard	MultiArith	Navigate	Mean	K	$\Delta$	s	$\Delta$
(i) Method comparison at $k{=}20$
	Random	0.740	0.723	0.975	0.740	0.795	684	ref	1,195	ref
	SESS	0.900	0.739	0.975	0.860	0.869	752	$+$ 10%	1,252	$+$ 5%
	IPOMP	0.920	0.686	0.975	0.760	0.835	684	$\pm$ 0%	1,200	$\pm$ 0%
	Anchor	0.840	0.765	0.950	0.720	0.819	743	$+$ 9%	1,220	$+$ 2%

Table 3: Budget efficiency analysis of POES . Top : All methods at

k{=}20

— POES achieves rank-1 on all 4 tasks with only 6% more tokens. Middle : POES at reduced budgets—

k{=}20

matches

k{=}30

while saving 33% tokens. Bottom : POES @

k{=}10

stays close to baselines@

k{=}20

while using 34% fewer tokens . Bold : best per column; underline : 2nd best; green : our method. Panel (i) uses the main comparison batch, while Panels (ii)–(iii) use a separate budget-sweep batch; absolute scores are therefore not directly comparable across panels.

Figure 5: Hyperparameter sensitivity. (a) Test accuracy across 8 benchmarks (faded lines) and their average (dark,

\pm

1 SEM) as a function of candidate pool size

k

; performance plateaus beyond

k{=}20

. (b) Optimization token cost scales linearly with

k

; the shaded region marks diminishing returns. (c) IRT model comparison: the 1PL model (blue) outperforms the 2PL model (red) on average (+2.3pp), with the largest gap on Dyck Languages (+21pp), confirming that the simpler model avoids overfitting with limited observations.

Figure 6: Optimization curves on 8 representative tasks. POES (red) reaches the highest final score with steady late-stage improvement; baselines plateau earlier.

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Parameter	Symbol	Default	Description
Prompt Optimizer
Optimization steps	$T$	10	Number of OPRO optimization rounds
Candidates per step	–	8	Prompt candidates generated per round
Evaluation budget	$k$	20	Examples in the evaluation subset
Training pool size	$N$	$\sim$ 200	Total training examples (80% split)
Test set size	–	$\sim$ 50	Held-out test examples (20% split)

Appendix

Table 4: Complete hyperparameter settings for POES . All values fixed across all tasks.

Family	Representative Tasks	# Tasks	$N_{\text{train}}$ / $N_{\text{test}}$	Task Type
BBH	boolean_expr, dyck_lang, navigate, word_sort, logical_ded	27	$\sim$ 200 / 50	Reasoning, Symbolic
BigBench	implicatures, metaphor, navigate, presuppositions, sports	5	$\sim$ 200 / 50	NLU, Reasoning
MMLU	abstract_algebra, formal_logic, anatomy, college_chem	57	$\sim$ 200 / 50	Knowledge QA
Math	GSM8K, GSM-Hard, MultiArith, MATH	4	$\sim$ 200 / 50	Math

Appendix

Table 5: Benchmark summary with task counts and types.

Figure 7: Ablation optimization curves (best seed) on three tasks. POES (red) reaches the highest or tied-highest final subscore on all tasks; No-Adaptive (purple) consistently lags, confirming adaptive control as the most critical component (MATH: 0.95 vs.

\leq

0.90).

Family	Random (K)	IPOMP (K)	POES (K)	Overhead
BBH	498	475	521	+4.6%
BigBench	390	375	398	+2.1%
MMLU	612	601	640	+4.6%
Math	584	571	619	+6.0%
Overall	538	536	560	+4.1%

Appendix

Table 6: Token consumption by task family (thousands of tokens).

		Accuracy (best seed)				Cost (avg)
Param	Value	Dyck Lang.	GSM-Hard	MultiArith	Mean	Tok. (K)	Time (s)	$\Delta$ Tok
$k$	10	0.800	0.799	0.967	0.855	478	2,370	$-$ 64%
	20 ∗	0.900	0.742	0.950	0.864	892	2,884	$-$ 33%
	30	0.980	0.705	0.942	0.876	1,331	3,264	—
$T$	10 ∗	0.820	0.826	0.992	0.879	999	3,091	$-$ 37%
	15	0.980	0.852	0.983	0.938	1,299	4,241	$-$ 18%

Appendix

Table 7: Complete parameter sensitivity with computational cost (POES, best accuracy across seeds; tokens/time averaged across seeds). Default values ( ∗ ) highlighted in blue . Bold : best accuracy per group. 124 runs total (6 params

\times

3 values

\times

3 tasks

\times

2+ seeds).

Statistic	Value
Mean subset shift per round	$0.287\pm 0.043$
Median subset shift per round	0.280
Min / Max subset shift	0.195 / 0.395
Mean attempted swaps (cumulative)	$228.5\pm 21.8$
Mean accepted swaps (cumulative)	$221.2\pm 33.2$
Swap acceptance rate	96.8%

Appendix

Table 8: Comprehensive subset shift statistics for POES.

Statistic	Random	SESS	IPOMP	Anchor	Prediction	Ours
Rank-1 count	8	2	10	5	8	14
Top-2 count	16	12	15	12	13	25
Avg. rank	3.08	3.81	3.14	3.72	3.58	2.56
Median rank	3.0	4.0	3.0	4.0	3.5	2.0
Tasks evaluated	36	36	36	36	36	36

Appendix

Table 9: Rank statistics across all 36 main tasks.

Figure 8: Per-task rank distribution (violin plot) for each scheduling method. Lower rank is better. Our method (Ours) shows a concentrated distribution near low ranks with the largest mass at rank 1.

Task	Method	Score	Best Prompt
BBH Navigate	Random	0.740	“Calculate the final coordinates after executing the given moves and output ‘Yes’ if they equal the starting point (0,0); otherwise output ‘No’.”
	SESS	0.860	“Initialize position = (0, 0) and orientation matrix R = [[0, -1],[1, 0]] (facing north). Process each command sequentially: ‘Turn left’ $\to$ R $\leftarrow$ R $\cdot$ [[0, -1],[1, 0]], ‘Turn right’ $\to$ R $\leftarrow$ R $\cdot$ [[0, 1],[-1, 0]], ‘Turn around’ $\to$ R $\leftarrow$ R $\cdot$ [[-1, 0],[0, -1]], ‘Take N steps’ $\to$ position $\leftarrow$ position + N $\cdot$ (R $\cdot$ [0,1]). After all commands: output ‘Yes’ if position = (0,0), else ‘No’.”
	IPOMP	0.760	“Trace the path step by step, compute the final coordinates relative to the start, and output ‘Yes’ if the coordinates are (0,0); otherwise output ‘No’.”
	POES	0.920	“Interpret the entire command sequence, updating your (x,y) position based on the current facing direction; after processing the last command, respond ‘Yes’ if the final position is (0,0), otherwise respond ‘No’.”
MATH	Random	0.775	“Offer a streamlined solution: enumerate only the indispensable steps, carry out the required calculations, perform a brief validation, and conclude with exactly the final answer in the format specified.”
	IPOMP	0.870	“Give a brief ( $\leq$ 8-word) core insight, then on the next line write the exact answer enclosed in double curly braces {{answer}} with no other text.”

Appendix

Table 10: Best prompts found by each scheduler on three tasks. POES rows are highlighted. Scores are accuracy on the held-out test set.

Round	Phase	Subset Characteristics
1	Warmup	Random subset with broad coverage across difficulty levels. Contains a mix of easy (1–2 step), moderate (3–5 step), and hard (6+ step) navigation sequences. No discrimination signal available yet.
3	Warmup exit	First actively selected subset. IRT parameters have matured sufficiently to estimate item discrimination. The subset shifts toward moderate-difficulty examples where top-2 prompts disagree, while retaining a few easy/hard anchors for coverage.
5	Active	Subset refined via 2–3 swaps from round 3. Low-discrimination items (trivially easy sequences solved by all prompts) are swapped out for items near the ability boundary. Coverage term prevents over-concentration.
10	Active (final)	Subset has stabilized: most items are moderate-complexity navigation sequences (3–5 turns) that maximally separate the current top prompt candidates. Only 1 swap from round 5, reflecting convergence of both the prompt population and the IRT model.

Appendix

Table 11: Qualitative evolution of the POES evaluation subset on BBH Navigate (seed 44). During warmup, the subset is random; after warmup exit, it is actively refined via bounded swaps.

Discrimination	Example Type	Explanation
High	Moderate-complexity navigation (3–5 turns)	Top prompts disagree: one correctly tracks facing direction through multiple turns, while the other loses track after 2–3 direction changes. These examples are near the “ability boundary” in IRT terms.
High	Multi-step arithmetic with carries	Prompt phrasing affects whether the model explicitly shows intermediate work. Prompts that encourage step-by-step computation succeed; those requesting concise answers fail on carry propagation.
Low	Simple 2-step navigation (always correct)	All prompts succeed regardless of phrasing—the task is too easy to reveal quality differences. Including such examples wastes evaluation budget without providing discrimination signal.
Low	10+ step navigation (always wrong)	All prompts fail because the sequence exceeds the model’s reliable tracking capacity. No prompt phrasing can compensate for this fundamental limitation, so the example provides no signal.

Appendix

Table 12: Examples with high vs. low discrimination utility on BBH Navigate and multi-step arithmetic tasks. High-discrimination examples are those where top prompts disagree; low-discrimination examples elicit uniform responses.

Task	Optimizer	Score	Best Prompt
GSM8K	OPRO	0.890	“Read the problem, extract every numeric value and the exact mathematical relationship it implies (including multiplication, division, addition, subtraction, percentages, rates, and any needed unit conversion)…”
	EvoPrompt-GA	0.250	“Let’s tackle the problem together.”
	EvoPrompt-DE	0.258	“Let’s solve the problem.”
MultiArith	OPRO	0.983	“Parse the word problem, identify all relevant quantities and the required arithmetic operation(s), perform the calculation, and output only the final numeric answer.”
	EvoPrompt-GA	0.392	“Let’s work together to solve the problem.”
	EvoPrompt-DE	0.325	“Let’s solve the problem.”

Appendix

Table 13: Optimizer failure analysis: best prompts found by OPRO vs. EvoPrompt (GA/DE) on math tasks. EvoPrompt’s crossover/mutation operators degrade prompts into generic phrases lacking task-specific instructions, bottlenecking all scheduling methods equally.

Automatic Prompt Optimization

Automatic prompt optimization uses model or task feedback to revise instructions for stronger, more reliable language-model performance.

See all 103 papers

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)
Optimization before Evaluation: Evaluation with Unoptimised Prompts Can be Misleading
Apr 30, 2026Nicholas Sadjoli, Tim Siefken, Atin Ghosh +2LLM Evaluation Language Model Generation Evaluation
SAP · Stanford University
Budgeted Prompt-Set Expansion and Refinement for Language Models via Simulation Optimization
Apr 12, 2024Haoting Zhang, Jinghai He, Rhonda Righter +1Prompt Optimization LLM Prompting
Department of Industrial Engineering and Operations Research, University of California Berkeley

Oct 5, 2026J/K move · Enter open · S save

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

Haoyue Liu, Zhichao Wang, Huanyu Yan, Xiaoying Tang

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)

Automatic Prompt Optimization Prompt Optimization

Open paper AskPDF arXiv

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 5 times as many calls to match \method's 100-call score.

Abstract

Automatic Prompt Optimization

Explore similar work

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

Optimization before Evaluation: Evaluation with Unoptimised Prompts Can be Misleading

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