Submodular Evaluation Subset Selection in Automatic Prompt Optimization

• URL: http://arxiv.org/abs/2601.03493v1
• Date: Wed, 07 Jan 2026 01:12:45 GMT
• Title: Submodular Evaluation Subset Selection in Automatic Prompt Optimization
• Abstract summary: 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.
• Score: 10.54347571741568
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Automatic prompt optimization reduces manual prompt engineering, but relies on task performance measured on a small, often randomly sampled evaluation subset as its main source of feedback signal. Despite this, how to select that evaluation subset is usually treated as an implementation detail. We study evaluation subset selection for prompt optimization from a principled perspective and propose SESS, a submodular evaluation subset selection method. We frame selection as maximizing an objective set function and show that, under mild conditions, it is monotone and submodular, enabling greedy selection with theoretical guarantees. Across GSM8K, MATH, and GPQA-Diamond, submodularly selected evaluation subsets can yield better optimized prompts than random or heuristic baselines.

Related papers

• Coresets Before Score Sets: Evaluation-Unsupervised Prompt Subset Selection for LLM Benchmarks [31.891185002244146]
  In evaluation-unsupervised benchmark coreset selection, the selection algorithm uses no model evaluation outcomes.<n>We develop and evaluate many different submodular functions for this purpose, including determinantal point process (DPP) based approaches.<n>We show our proposed objective is not limited to the evaluation-unsupervised regime: in the setting where only a handful of whole benchmarks must be selected, the same objective matches or outperforms state-of-the-art baselines.
  arXiv  Detail & Related papers  (2026-07-02T18:37:18Z)
• Embedding by Elicitation: Dynamic Representations for Bayesian Optimization of System Prompts [22.060204303535187]
  System prompts are a central control mechanism in modern AI systems, shaping behavior across conversations, tasks, and user populations.<n>We study this aggregate feedback setting as sample-constrained black-box optimization over discrete, variable-length text.<n>We introduce ReElicit, a Bayesian optimization framework based on emphembedding by elicitation.
  arXiv  Detail & Related papers  (2026-05-18T20:28:17Z)
• 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)
• Select Smarter, Not More: Prompt-Aware Evaluation Scheduling with Submodular Guarantees [28.54776477263591]
  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.
  arXiv  Detail & Related papers  (2026-04-13T11:31:04Z)
• Multinoulli Extension: A Lossless Continuous Relaxation for Partition-Constrained Subset Selection [60.07018090570548]
  We introduce a novel algorithm titled MultinoulliSCG, which is parameterfree and can achieve the same approximation guarantees as the distorted local-search methods.<n>We also present two novel online algorithms, namely, Multinoulli-CG and Multinoulli-GAGA, for the unexplored online subset selection problems over partition constraints.
  arXiv  Detail & Related papers  (2026-03-23T02:30:01Z)
• Automatic Rank Determination for Low-Rank Adaptation via Submodular Function Maximization [56.78271181959529]
  SubLoRA is a rank determination method for Low-Rank Adaptation (LoRA) based on submodular function.<n>Our method combines solid theoretical foundations, second-order accuracy, and practical computational efficiency.
  arXiv  Detail & Related papers  (2025-07-02T15:56:40Z)
• An incremental preference elicitation-based approach to learning potentially non-monotonic preferences in multi-criteria sorting [53.36437745983783]
  We first construct a max-margin optimization-based model to model potentially non-monotonic preferences. We devise information amount measurement methods and question selection strategies to pinpoint the most informative alternative in each iteration. Two incremental preference elicitation-based algorithms are developed to learn potentially non-monotonic preferences.
  arXiv  Detail & Related papers  (2024-09-04T14:36:20Z)
• Sub-SA: Strengthen In-context Learning via Submodular Selective Annotation [4.846839863393725]
  We propose Sub-SA (Submodular Selective ), a sub-module-based selective annotation method. The aim of Sub-SA is to reduce annotation costs while improving the quality of in-context examples. We also propose RPR (Reward and Penalty Regularization) to better balance the diversity and representativeness of the unlabeled dataset.
  arXiv  Detail & Related papers  (2024-07-08T07:47:30Z)
• Localized Distributional Robustness in Submodular Multi-Task Subset Selection [5.116582735311639]
  We propose a regularization term which makes use of the relative entropy to the standard multi-task objective. We show that this novel formulation is equivalent to a monotone increasing function composed with a submodular function. We conclude that our novel formulation produces a solution that is locally distributional robust, and computationally inexpensive.
  arXiv  Detail & Related papers  (2024-04-04T19:06:29Z)
• Localized Zeroth-Order Prompt Optimization [54.964765668688806]
  We propose a novel algorithm, namely localized zeroth-order prompt optimization (ZOPO) ZOPO incorporates a Neural Tangent Kernel-based derived Gaussian process into standard zeroth-order optimization for an efficient search of well-performing local optima in prompt optimization. Remarkably, ZOPO outperforms existing baselines in terms of both the optimization performance and the query efficiency.
  arXiv  Detail & Related papers  (2024-03-05T14:18:15Z)
• Submodular Reinforcement Learning [38.40138241424851]
  In reinforcement learning (RL), rewards of states are typically considered additive, and following the Markov assumption, they are $textitindependent$ states visited previously. In many important applications, such as coverage control, experiment design and informative path planning, rewards naturally have diminishing returns, i.e., their value decreases in light of similar states visited previously. We propose $textitsubmodular RL$ (SubRL), a paradigm which seeks to optimize more general, non-additive (and history-dependent) rewards modelled via submodular set functions which capture diminishing returns
  arXiv  Detail & Related papers  (2023-07-25T09:46:02Z)
• Towards Automated Imbalanced Learning with Deep Hierarchical Reinforcement Learning [57.163525407022966]
  Imbalanced learning is a fundamental challenge in data mining, where there is a disproportionate ratio of training samples in each class. Over-sampling is an effective technique to tackle imbalanced learning through generating synthetic samples for the minority class. We propose AutoSMOTE, an automated over-sampling algorithm that can jointly optimize different levels of decisions.
  arXiv  Detail & Related papers  (2022-08-26T04:28:01Z)
• Streaming Adaptive Submodular Maximization [19.29174615532181]
  We introduce a new class of utility functions, semi-policywise submodular functions. We develop a series of effective algorithms to maximize a semi-policywise submodular function under the stream-based setting.
  arXiv  Detail & Related papers  (2022-08-17T02:05:10Z)
• Learning Interpretable Decision Rule Sets: A Submodular Optimization Approach [12.710158664288784]
  We consider a submodular optimization based approach for learning rule sets. We employ an objective function that exhibits submodularity and thus is amenable to submodular optimization techniques.
  arXiv  Detail & Related papers  (2022-06-08T07:41:47Z)
• Local policy search with Bayesian optimization [73.0364959221845]
  Reinforcement learning aims to find an optimal policy by interaction with an environment. Policy gradients for local search are often obtained from random perturbations. We develop an algorithm utilizing a probabilistic model of the objective function and its gradient.
  arXiv  Detail & Related papers  (2021-06-22T16:07:02Z)
• The Power of Subsampling in Submodular Maximization [51.629656762796564]
  We show that this approach leads to optimal/state-of-the-art results despite being much simpler than existing methods. We empirically demonstrate the effectiveness of our algorithms on video summarization, location summarization, and movie recommendation tasks.
  arXiv  Detail & Related papers  (2021-04-06T20:25:57Z)
• Fast Greedy Subset Selection from Large Candidate Solution Sets in Evolutionary Multi-objective Optimization [11.110675371854988]
  We discuss the efficiency of greedy subset selection for the hypervolume, IGD and IGD+ indicators. Our idea is to use the submodular property, which is known for the hypervolume indicator, to improve their efficiency.
  arXiv  Detail & Related papers  (2021-02-01T16:14:15Z)

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.