Research map / Large language models / Language, safety and interpretability

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

NeurIPS 2026 · Large language models › Language, safety and interpretability · approach: In-context learning analysis · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes POES, an online, prompt-aware evaluation-subset scheduler for automatic prompt optimization that combines IRT-based discrimination, facility-location coverage, and switching-cost-aware warm-start swaps under a monotone submodular objective.

Problem

Automatic prompt optimization scores candidates on small evaluation subsets, but existing subset selection is either static and prompt-agnostic or heuristic and unstable; the paper asks how the evaluation subset should evolve during optimization.

Approach

Casts APO evaluation as online adaptive testing: select training examples that best discriminate the top two prompts (IRT 1PL-based KL utility), add facility-location coverage, and update the subset by bounded warm-start swaps under an adaptive controller, with a submodularity-based guarantee.

Key results

• POES achieves the highest overall average accuracy (0.882 across 36 tasks, +6.2% over best baseline) and the most rank-1 results (14 of 36 tasks).
• At k=20, POES matches or exceeds naive evaluation at k=30-50 while reducing token consumption by 35-60%.
• At k=10, POES (478K tokens) matches mean accuracy of baselines at k=20 (727K tokens), a 34% token reduction.

Surprising findings

• Naive evaluation at larger subset size does not improve accuracy; k=30 is only marginally better than k=20 while costing substantially more tokens.
• The simpler 1PL IRT model outperforms 2PL by 2.3pp on average, attributed to overfitting with limited observations.

Limitations

• Theoretical analysis covers only the scheduling layer; no end-to-end APO convergence guarantee.
• Evaluated on binary-scored tasks with about 200 training examples; scaling to larger pools and non-binary generation tasks is untested.
• Gains are smaller when all prompts already perform similarly.

Experimental setup

Datasets: BBH BigBench-IPOMP MMLU GSM8K GSM-Hard MATH MultiArith

Benchmarks: BBH BigBench-IPOMP MMLU GSM8K GSM-Hard MATH MultiArith

Metrics: accuracy mean rank token consumption wall-clock time

Baselines: Random SESS IPOMP Anchor Prediction

Builds on: OPRO EvoPrompt IPOMP SESS

Closest papers by meaning

• Teach Better or Show Smarter? On Instructions and Exemplars in Automatic Prompt Optimization (NeurIPS 2024 · similarity 0.88)
• Efficient multi-prompt evaluation of LLMs (NeurIPS 2024 · similarity 0.86)
• Revisiting Prefix-tuning: Statistical Benefits of Reparameterization among Prompts (ICLR 2025 · similarity 0.85)
• DynaPrompt: Dynamic Test-Time Prompt Tuning (ICLR 2025 · similarity 0.85)
• GReaTer: Gradients Over Reasoning Makes Smaller Language Models Strong Prompt Optimizers (ICLR 2025 · similarity 0.85)
• SePO: Self-Evolving Prompt Agent for System Prompt Optimization (NeurIPS 2026 · similarity 0.85)