Select Smarter, Not More: Prompt-Aware Evaluation Scheduling with Submodular Guarantees
This work addresses the efficiency bottleneck in automatic prompt optimization by providing a principled, adaptive evaluation scheduling method with formal guarantees, significantly reducing computational cost while improving performance.
The paper introduces Prompt-Aware Online Evaluation Scheduling (POES) for automatic prompt optimization, which uses submodular optimization to select evaluation examples adaptively. Across 36 tasks, POES achieves 6.2% higher accuracy than baselines with only 4% token overhead, and using 20 examples matches or exceeds naive evaluation with 30-50 examples, reducing token consumption by 35-60%.
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.