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 Gt , and (5) an adaptive controller that adjusts (τt,Bt,λt) . The selected subset St feeds back to the evaluation module, closing the optimization loop.
Figure 3: Per-task accuracy comparison on rank-1 tasks (OPRO × 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.
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 × 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 × 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
Δ
s
Δ
(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
± 0%
1,200
± 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, ± 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
∼ 200
Total training examples (80% split)
Test set size
–
∼ 50
Held-out test examples (20% split)
Appendix
Table 4: Complete hyperparameter settings for POES . All values fixed across all tasks.
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. ≤ 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)
Δ 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 × 3 values × 3 tasks × 2+ seeds).
Statistic
Value
Mean subset shift per round
0.287±0.043
Median subset shift per round
0.280
Min / Max subset shift
0.195 / 0.395
Mean attempted swaps (cumulative)
228.5±21.8
Mean accepted swaps (cumulative)
221.2±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’ → R ← R ⋅ [[0, -1],[1, 0]], ‘Turn right’ → R ← R ⋅ [[0, 1],[-1, 0]], ‘Turn around’ → R ← R ⋅ [[-1, 0],[0, -1]], ‘Take N steps’ → position ← position + N ⋅ (R ⋅ [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 ( ≤ 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 (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.
Haoyue Liu, Zhichao Wang, Huanyu Yan +1
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)
Current Large Language Model (LLM) evaluation frameworks utilize the same static prompt template across all models under evaluation. This differs from the common industry practice of using prompt optimization (PO) techniques to optimize the prompt for each model to maximize application performance. In this paper, we investigate the effect of PO towards LLM evaluations. Our results on public academic and internal industry benchmarks show that PO greatly affects the final ranking of models. This highlights the importance of practitioners performing PO per model when conducting evaluations to choose the best model for a given task.
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.
Haoting Zhang, Jinghai He, Rhonda Righter +1
Department of Industrial Engineering and Operations Research, University of California Berkeley