Submodular Evaluation Subset Selection in Automatic Prompt Optimization Jinming Nian, Zhiyuan Peng, Hongwei Shang, Dae Hoon Park, Yi Fang 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 1 1 1 https://github.com/jmnian/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. 1 Introduction Large language models (LLMs) are highly sensitive to how a task is described in natural language, which makes instruction prompts crucial for real deployments 17 . Small changes to wording or formatting can lead to large swings in accuracy and behavior 18 ; 3 , while the right prompting pattern can unlock capabilities such as multi-step reasoning 22 ; 8 . In practice, however, prompt engineering is often a slow trial-and-error process. To reduce manual effort, a growing line of work studies automatic prompt optimization (APO) . As illustrated in Figure 1 , a typical pipeline alternates between an LLM-based optimizer that proposes one or more candidate prompts, and an evaluator, which provide feedback in the form of evaluation scores or textual critiques. This feedback is then used to guide the next round of candidate prompt generation. For example, OPRO 23 stores each evaluated prompt together with its score and uses the top-scoring prompts as in-context examples for subsequent optimization rounds. ProTeGi 14 and TextGrad 25 use gradient-inspired methods that treat LLM-generated natural language critiques as a proxy feedback for prompt optimization. More broadly, evolutionary search methods have also been used to iteratively improve algorithms using both evaluation score and critiques as feedback 12 ; 10 . Across methods, the shared pattern is: the optimizer proposes candidates, and evaluation feedback determines which candidates are retained for further optimization. Figure 1: The general framework of APO. SESS replaces random or heuristic subset selection with a principled submodular evaluation subset selection module. Evaluating every candidate prompt on the full evaluation dataset is often infeasible; most APO methods score prompts on a randomly sampled evaluation subset 23 ; 14 . Because the optimizer only sees scores computed on the evaluation subset, this choice controls the noise of the feedback signal, how easily the optimizer overfits a few examples, and how stable prompt comparisons are across runs. This motivates a core yet underexplored budgeted evaluation subset selection problem : Given a fixed budget, how can we select an evaluation subset that best supports prompt optimization and leads to high-performing prompts on the target distribution? Recent work has started to explore this direction. For instance, IPOMP 2 selects evaluation data using a two-stage procedure based on semantic clustering and boundary analysis, followed by refinement using real-time model performance. Still, principled objectives with clear guarantees for evaluation subset selection specifically for prompt optimization remain limited. To address this issue, we propose SESS , a submodular evaluation subset selection method for prompt optimization. We evaluate SESS on GSM8K 1 , MATH 5 , and GPQA-Diamond 16 , where prompts optimized using submodularly selected evaluation subsets can outperform random and heuristic baselines. Our key contributions include: (1) we introduce SESS , a principled method to selecting evaluation subsets for APO, formulated as a budgeted set maximization problem; (2) we show that the proposed objectives are monotone and submodular under mild conditions, which allows greedy selection with approximation guarantees; (3) we present a unified framework that generalizes multiple subset selection strategies through different objective definitions, making optimization feedback an explicit modeling choice rather than an implementation detail; and (4) we show gains on GSM8K, MATH, and GPQA-Diamond, where SESS yields better optimized prompts than random or heuristic baselines. 2 Related Work Subset Selection. Recent work on benchmark compression and coreset selection 24 ; 20 ; 7 ; 21 focus on preserving full-benchmark scores or model ranking using a small subset. In contrast, we study evaluation subset selection for APO, where the goal is to maximize the target distribution performance of the optimized prompt. A subset that closely matches the full evaluation set is therefore not necessarily optimal for this goal. IPOMP 2 addresses this problem using a heuristic two-stage procedure based on semantic clustering, boundary analysis, and model performance. While effective, IPOMP does not provide an explicit optimization objective or theoretical guarantees. Our approach complements this line of work by formulating evaluation subset selection as a budgeted set maximization problem with monotone submodular objectives, enabling greedy selection with approximation guarantees. 3 Methodology 3.1 Evaluation subset selection Let D=\{x_{1},\dots,x_{N}\} be a pool of candidate evaluation examples. Automatic prompt optimization such as OPRO iteratively proposes prompts and keeps those that score well on an evaluation set. Since scoring each prompt on the full pool D is often infeasible, we select a budgeted subset S\subseteq D with |S|\leq k to serve as the optimization feedback. We frame evaluation subset selection as the following budgeted set maximization problem: S^{*}\in\arg\max_{S\subseteq D,\;|S|\leq k}\mathcal{F}(S), (1) where \mathcal{F}:2^{D}\to\mathbb{R}_{\geq 0} measures how suitable S is for guiding prompt optimization. Exact maximization is NP-hard for many natural choices of \mathcal{F} , but when \mathcal{F} is non-negative, monotone, and submodular 4 , the greedy algorithm achieves a (1-1/e) approximation under the cardinality constraint 11 . Our goal is therefore to design useful evaluation objectives \mathcal{F} that match the needs of prompt optimization and belong to this monotone submodular family. We solve Eq. 1 once prior to optimization (static selection). We hypothesize that optimization feedback is primarily determined by intrinsic instance properties (e.g., representativeness or difficulty), allowing a fixed subset to provide a stable and efficient signal without the overhead of dynamic re-selection. 3.2 Submodular Evaluation Objectives We consider two goals for evaluation subsets: (1) representativeness : cover the diversity of the pool so the feedback reflects the full task distribution; (2) difficulty awareness : emphasize examples that the scorer model finds hard, since these are often the most informative for comparing prompts. We propose three subset selection objectives: representative, least confident, and confidence-weighted representative. In the remainder of the paper, we refer to the greedy solution of each objective as a specific instance of SESS : SESS-rep for the representative objective \mathcal{F}_{\mathrm{rep}} , SESS-lc for least-confidence selection using likelihood-based confidence, SESS-vlc for least-confidence selection using verbalized confidence, both described by \mathcal{F}_{\mathrm{lc}} , and SESS-wrep for the confidence-weighted representative objective \mathcal{F}_{\mathrm{wrep}} . Each method selects a subset S of size k using the greedy procedure described in Section 3.3 . Representative subset. We cast each example into a vector representation and define \mathrm{sim}(i,j) by cosine similarity. To satisfy the non-negativity assumptions required by our analysis, we normalize cosine similarity as \mathrm{sim}(i,j)=(1+\cos(i,j))/2\in[0,1] . We then use a facility-location style objective to quantify how well a subset S covers the full pool: \mathcal{F}_{\mathrm{rep}}(S)\;:=\;\sum_{j\in D}\max_{i\in S}\mathrm{sim}(i,j). (2) Intuitively, each example j contributes its similarity to its nearest neighbor in the selected subset S , so larger \mathcal{F}_{\mathrm{rep}}(S) indicates that S contains good representatives for many regions of the pool. Under \mathrm{sim}\geq 0 , \mathcal{F}_{\mathrm{rep}} is monotone and submodular 6 . Proofs are provided in Appendix C . Least confident subset. Let c(j) be a scalar confidence score for example j computed by a fixed scorer model. We select the k examples with smallest c(j) . This can be written as a modular objective \mathcal{F}_{\mathrm{lc}}(S)\;:=\;\sum_{j\in S}(1-\tilde{c}(j)), (3) where \tilde{c}(j)\in[0,1] is a normalized confidence score of c(j) . We provide two variants: likelihood-based confidence and verbal confidence 19 . These objectives capture difficulty but could cause redundancy among selected examples. Because the objective is modular and nonnegative, it is monotone and submodular. Confidence-weighted representative subset. To combine representativeness and difficulty awareness, we weight coverage to favor hard examples: \mathcal{F}_{\mathrm{wrep}}(S)\;:=\;\sum_{j\in D}w(j)\cdot\max_{i\in S}\mathrm{sim}(i,j), (4) where w(j)\geq 0 is an importance weight computed from the scorer model’s likelihood-based confidence. In our implementation, w(j)\;=\;(1-\lambda)\;+\;\lambda\cdot\bigl(1-\tilde{c}(j)\bigr),\ \lambda\in[0,1], (5) so \lambda=0 gives us \mathcal{F}_{\mathrm{rep}}(S) which recovers pure representativeness, while larger \lambda increasingly concentrates coverage on low-confidence (hard) examples. Since \mathcal{F}_{\mathrm{wrep}} is a nonnegative weighted sum of facility-location terms, it remains monotone submodular when \mathrm{sim}\geq 0 and w(j)\geq 0 ; we prove this in Appendix C . 3.3 Greedy selection For any monotone submodular objective \mathcal{F} above (in particular \mathcal{F}_{\mathrm{rep}} and \mathcal{F}_{\mathrm{wrep}} ), we apply the standard greedy algorithm starting from S=\emptyset : x^{*}\leftarrow\arg\max_{x\in D\setminus S}\left[\mathcal{F}(S\cup\{x\})-\mathcal{F}(S)\right], (6) followed by the update S\leftarrow S\cup\{x^{*}\} , repeated until |S|=k . For monotone submodular \mathcal{F} under the cardinality constraint, the resulting subset S_{\mathrm{greedy}} enjoys the guarantee \mathcal{F}(S_{\mathrm{greedy}})\;\geq\;(1-1/e)\,\mathcal{F}(S^{*}) where S^{*} is an optimal solution to Eq. ( 1 ) 11 . For modular objectives such as \mathcal{F}_{\mathrm{lc}} , S_{\mathrm{greedy}} is obtained by sorting examples by uncertainty (1-\tilde{c}(j)) in descending order and selecting the top- k . Method GSM8K (EM) MATH (EM) GPQA-D (Acc) Avg Small Large Small Large Small Large Small Large All Base 82.9 82.9 73.2 73.2 29.9 29.9 62.0 62.0 62.0 Random 88.7 89.6 74.1 73.3 34.3 35.9 65.7 66.3 66.0 IPOMP 88.6 91.8 73.7 74.7 33.8 33.8 65.4 66.8 66.1 Anchor-Points 87.9 90.4 75.1 76.1 33.8 37.4 65.6 68.0 66.8 SESS-rep 91.9 89.9 73.2 70.3 32.3 29.8 65.8 63.3 64.6 SESS-lc 90.8 90.8 73.9 75.3 34.3 32.8 66.3 66.3 66.3 SESS-vlc 91.8 91.0 75.7 75.7 34.3 36.9 67.3 67.9 67.6 SESS-wrep 90.0 90.8 76.1 73.6 37.4 34.8 67.8 66.4 67.1 Table 1: OPRO performance under different evaluation subset selection methods. We report Exact Match (EM) on GSM8K and MATH, and accuracy on GPQA-Diamond. Small and Large denote averages over small-budget (1%, 1%, 10%) and large-budget (3.5%, 3.5%, 20%) settings, respectively; All averages all six settings. Bold and underline denote the best and second-best results in each column, respectively. 4 Experiment Setup We evaluate how evaluation-subset selection in OPRO 23 affect the final optimized prompt’s test performance. OPRO iteratively proposes new instruction prompts using an optimizer LLM conditioned on previously tried prompts and their scores. Each candidate prompt is scored by running a scorer LLM on a fixed evaluation subset S , and the resulting score is the only feedback that guides optimization. We isolate the effect of subset selection by running the same OPRO procedure while varying how S is chosen. After optimization, we select the highest-scoring candidate prompt on the evaluation subset and report its performance on the full test set. Datasets. We report Exact Match (EM) on GSM8K and MATH and accuracy on GPQA-Diamond. The evaluation budget is documented in Appendix A . Subset selection methods. We compare Base (“Let’s solve the problem.”, no OPRO optimization), Random (OPRO default), IPOMP 2 , Anchor-Points 20 , and our variants from Section 3 : SESS-rep, SESS-lc (likelihood), SESS-vlc (verbal), and SESS-wrep. The implementation details of SESS can be found in Appendix A . Anchor-Points is designed to approximate full-benchmark evaluation with fewer examples, not specifically for prompt optimization. Although it is not proposed for prompt optimization, it serves as a strong baseline for selecting a coreset. 5 Results and Discussion Table 1 reports the test performance on OPRO-optimized prompts when the evaluation subset is constructed by different selection methods. This directly tests our main claim that evaluation subset selection should not merely be an implementation detail, and that SESS provides a principled and effective way to shape the optimization signal and materially affect prompt optimization outcomes. Overall, SESS variants are competitive with or outperform strong baselines, with the clearest gains under small evaluation budgets. Among all methods, SESS-vlc achieves the best Avg(All) (67.6) and remains strong across datasets and budgets, while SESS-wrep achieves the best Avg(Small) (67.8). In contrast, Random and IPOMP perform notably worse under small budgets (65.7 and 65.4 Avg(Small)), indicating that careful subset construction matters most when evaluation resources are limited. Different objectives excel in different regimes, validating our unified objective family. SESS-rep performs best on GSM8K at 1% (91.9), suggesting that coverage-based objectives provide a strong signal on large, relatively homogeneous pools. SESS-wrep performs best on the most challenging small-budget setting, GPQA-Diamond 10% (37.4). SESS-vlc is consistently strong across tasks and budgets, yielding the best Avg(All) and near-best Avg(Large). Notably, well-chosen small evaluation subsets can match or outperform larger budgets at a fraction of the compute. For example, on GPQA-Diamond, SESS-wrep with a 10% subset (20 questions) achieves 37.4% accuracy, matching or exceeding several 20% settings. Similar effects appear on GSM8K, where 1% subsets already provide strong optimization signals. This suggests that increasing evaluation budget without improving subset quality yields diminishing returns: larger subsets often add redundant or low-signal examples, while carefully selected subsets concentrate feedback on representative yet hard cases, improving the signal-to-noise ratio seen by the optimizer. Among baselines, Anchor-Points is the strongest competitor, achieving the best Avg(Large) (68.0) due to strong performance on MATH and GPQA-Diamond at large budgets. Random remains stable with Avg(All) of 66.0, while IPOMP performs well on GSM8K at 3.5% (91.8) but does not generalize across datasets or budgets. Overall, SESS variants remain competitive across settings while offering explicit control over how optimization feedback is constructed. 6 Conclusion Across three benchmarks of varying difficulty and multiple evaluation budgets, SESS can yield stronger optimized prompts than random sampling and competitive heuristic baselines. This supports our core argument that evaluation subset selection is a core component of automatic prompt optimization, and framing it as monotone submodular set maximization provides both theoretical structure and practical gains. 7 Limitations Our experiments focus on a single prompt optimization pipeline OPRO with one optimizer LLM and one scorer LLM. While this setting allows controlled comparisons between subset selection methods, broader experiments across additional optimizer and scorer models would help clarify how sensitive the conclusions are to these settings. We also primarily report final test performance. A more detailed study of optimization dynamics, such as convergence speed and how quickly strong prompts are discovered, would provide a fuller picture of how subset selection shapes the optimization process. 8