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

• URL: http://arxiv.org/abs/2604.11328v1
• Date: Mon, 13 Apr 2026 11:31:04 GMT
• Title: Select Smarter, Not More: Prompt-Aware Evaluation Scheduling with Submodular Guarantees
• Abstract summary: We present Prompt-Aware Online Evaluation Scheduling (POES)<n>POES integrates an IRT-based discrimination utility, a facility-location coverage term, and switching-cost-aware warm-start swaps into a unified objective.<n>POES achieves the highest overall average accuracy (6.2 percent improvement over the best baseline) with negligible token overhead.
• Score: 28.54776477263591
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Learn What's Left, Not What's Mastered: Saturation Aware Advantage Reweighting for Multi-Reward Policy Optimization [60.89431018071735]
  Reinforcement learning with group-relative advantages has become the de facto standard for post-training language model reasoners.<n>We show that rollouts with distinct reward profiles can receive identical advantages, and all objectives are optimized with fixed relative weights regardless of their current level of saturation.<n>We introduce saturation-aware reweighting, which standardizes each reward objective independently and adaptively discounts its contribution according to a batch-level estimate of objective saturation.
  arXiv  Detail & Related papers  (2026-08-17T04:07:50Z)
• Less Data, Better Alignment: Data-Centric Multi-Evaluator Agreement for Preference Optimization [20.147316178118732]
  DMAPO generates candidate responses from the target policy, evaluates helpfulness, factuality, and conciseness with rubric-specialized evaluators.<n>This procedure accepts 1,871 of 54,236 Mistral-7B candidates (3.45%)<n>KTO trained on this set reaches 7.50 on MT-Bench, 95.5% length-controlled win rate against a text-davinci-003 reference, and 57.3% IFEval prompt accuracy.
  arXiv  Detail & Related papers  (2026-07-27T23:05:12Z)
• Do Agent Optimizers Compound? A Continual-Learning Evaluation on Terminal-Bench 2.0 [53.71882250666667]
  Most reported gains from agent-optimization methods are one-shot.<n>This does not test the setting that matters for deployed agents.<n>We compare three approaches to agent-harness optimization.
  arXiv  Detail & Related papers  (2026-07-15T16:36:04Z)
• MAGE: Understanding Stability-Performance Trade-offs in Multi-component Prompt Optimization [3.7323766833175718]
  MAGE (Memory-Augmented Goal Prompt Evolution) is a controlled analysis framework for studying component interaction in prompt optimization.<n>Our experiments uncover a previously unreported phenomenon, the Prompt Optimization Coupling Effect (POCE), when multiple optimization signals operate within a closed reflective loop.
  arXiv  Detail & Related papers  (2026-07-11T10:05:58Z)
• MASS-DPO: Multi-negative Active Sample Selection for Direct Policy Optimization [66.81594613265833]
  Multi-negative preference optimization under the Plackett--Luce (PL) model extends Direct Preference Optimization (DPO)<n>We introduce MASS-DPO, a multi-negative active sample selection method that derives a PL-specific Fisher-information objective for selecting compact, informative negative subsets within each prompt.<n> MASS-DPO consistently exceeds or matches existing methods in accuracy, improves Recall/NDCG and margin-based optimization dynamics, and delivers stronger alignment with substantially fewer negatives.
  arXiv  Detail & Related papers  (2026-05-11T16:18:08Z)
• Adaptive Prompt Structure Factorization: A Framework for Self-Discovering and Optimizing Compositional Prompt Programs [18.579725648410815]
  We propose Adaptive Prompt Structure Factorization (aPSF), an API-only framework (prompt-in/text-out; no access to model internals)<n>aPSF uses an Architect model to discover task-specific prompt structures as semantic factors.<n>aPSF outperforms strong baselines including principle-awares, improving accuracy by up to +2.16 percentage points on average.
  arXiv  Detail & Related papers  (2026-04-08T05:25:40Z)
• Aligning Multimodal Sequential Recommendations via Robust Direct Preference Optimization with Sparse MoE [7.609008983716641]
  We conduct experiments on multimodal sequential recommendation to compare common negative-selection strategies and their interaction with DPO training.<n>Our central finding is that a simple modification, replacing deterministic hard negatives with sampling from a dynamic top-K candidate pool, consistently improves ranking performance.
  arXiv  Detail & Related papers  (2026-03-31T04:49:32Z)
• Unbiased Dynamic Pruning for Efficient Group-Based Policy Optimization [60.87651283510059]
  Group Relative Policy Optimization (GRPO) effectively scales LLM reasoning but incurs prohibitive computational costs.<n>We propose Dynamic Pruning Policy Optimization (DPPO), a framework that enables dynamic pruning while preserving unbiased gradient estimation.<n>To mitigate the data sparsity induced by pruning, we introduce Dense Prompt Packing, a window-based greedy strategy.
  arXiv  Detail & Related papers  (2026-03-04T14:48:53Z)
• ODAR: Principled Adaptive Routing for LLM Reasoning via Active Inference [60.958331943869126]
  ODAR-Expert is an adaptive routing framework that optimize the accuracy-efficiency trade-off via principled resource allocation.<n>We show strong and consistent gains, including 98.2% accuracy on MATH and 54.8% on Humanity's Last Exam.
  arXiv  Detail & Related papers  (2026-02-27T05:22:01Z)
• Verified Critical Step Optimization for LLM Agents [67.05296684575445]
  Critical Step Optimization focuses preference learning on verified critical steps.<n>Method starts from failed policy trajectories rather than expert demonstrations.<n>Experiments on GAIA-Text-103 and XBench-DeepSearch show that CSO achieves 37% and 26% relative improvement over the SFT baseline.
  arXiv  Detail & Related papers  (2026-02-03T11:41:02Z)
• Submodular Evaluation Subset Selection in Automatic Prompt Optimization [10.54347571741568]
  We study evaluation subset selection for prompt optimization from a principled perspective.<n>We frame selection as maximizing an objective set function and show that, under mild conditions, it is monotone and submodular.<n>Across GSM8K, MATH, and GPQA-Diamond, submodularly selected evaluation subsets can yield better optimized prompts than random or baselines.
  arXiv  Detail & Related papers  (2026-01-07T01:12:45Z)
• OptPO: Optimal Rollout Allocation for Test-time Policy Optimization [11.375209834858135]
  Test-time policy optimization enables large language models to adapt to distribution shifts by leveraging feedback from self-generated rollouts.<n>We propose Optimal Rollout Allocation for Test-time Policy Optimization (OptPO), a principled framework that adaptively allocates inference budgets.
  arXiv  Detail & Related papers  (2025-12-02T15:38:52Z)
• PMPO: Probabilistic Metric Prompt Optimization for Small and Large Language Models [1.6816171955882597]
  PMPO locates low quality prompt segments via a masking based analysis and iteratively rewrites them to propose improved variants.<n>It selects among variants by minimizing loss in a single forward pass, eliminating output sampling and human or judge based scoring for selection.<n>Across model sizes and datasets, PMPO outperforms prior prompts: it achieves the highest average accuracy on BBH, performs strongly on GSM8K and AQUA RAT, and raises AlpacaEval 2.0 win rates by over 19 points.
  arXiv  Detail & Related papers  (2025-05-22T06:59:10Z)
• On the Role of Feedback in Test-Time Scaling of Agentic AI Workflows [71.92083784393418]
  Agentic AI (systems that autonomously plan and act) are becoming widespread, yet their task success rate on complex tasks remains low.<n>Inference-time alignment relies on three components: sampling, evaluation, and feedback.<n>We introduce Iterative Agent Decoding (IAD), a procedure that repeatedly inserts feedback extracted from different forms of critiques.
  arXiv  Detail & Related papers  (2025-04-02T17:40:47Z)
• Self-Play Preference Optimization for Language Model Alignment [75.83359213697854]
  Recent advancements suggest that directly working with preference probabilities can yield a more accurate reflection of human preferences. We propose a self-play-based method for language model alignment, which treats the problem as a constant-sum two-player game. Our approach, dubbed Self-Play Preference Optimization (SPPO), utilizes iterative policy updates to provably approximate the Nash equilibrium.
  arXiv  Detail & Related papers  (2024-05-01T17:59:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.