acceptodds
Under review as a conference paper at ICLR 2027

EvoSampler: Utility-Guided Experience Sampling for Prompt Evolution

Abstract

Prompt evolution allows LLM agents to accumulate experience across rounds of revision and evaluation without updating model weights. Under a limited budget, an optimizer must choose which training instances to expose to the revision process, and this choice determines what experience can shape the next prompt. We argue for a relational view of training-instance value, contingent on whether the revisions it tends to induce address the failures the current prompt still exhibits. This view motivates an objective that scores candidates by their expected contribution to the validation gain of the post-revision prompt. We introduce EvoSampler, a utility-guided experience sampler that resolves this problem by learning from the history of past accept/reject outcomes and re-evaluating that history against the errors the current prompt still exhibits. EvoSampler estimates each training instance's reparability (its reliability in producing revisions that survive evaluation) and the validation failures its accepted revisions tend to resolve. These effects are captured by two complementary components: a Repairability Vector, which estimates each training instance's ability to induce successful revisions, and a Transfer Matrix, which characterizes the training-validation attribution between training instances and validation failures. An upper-confidence-bound rule further supplies exploration when evidence is sparse. Across five benchmarks spanning mathematical reasoning, interactive decision-making, and instruction following, EvoSampler achieves the highest average held-out score among the compared optimizers under both model configurations. With DeepSeek V4 Flash as the target LLM, it improves the HMMT and ALFWorld scores by 28.33 and 42 percentage points, respectively, over the unoptimized prompt. The implementation is available at [https://anonymous.4open.science/r/EvoSampler](https://anonymous.4open.science/r/EvoSampler).

Primary area:
foundation or frontier models, including LLMs
Keywords:
Automatic prompt optimization, data-efficient optimization, training-data selection, training–validation attribution

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_ZBEMOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

EvoSampler is an adaptive experience sampler for prompt evolution. It combines historical candidate-retention probabilities with training-to-validation transfer estimates, conditions selection on the parent prompt’s unresolved validation instances, and adds an exploration bonus. Implemented within GEPA, it achieves the highest average held-out score across five benchmarks under two model configurations. Component and masking ablations provide additional validation.

Critical strengths
  1. The method is clearly formulated and reasonably complete. Combining historical revision outcomes with the current prompt’s remaining failures provides a sensible criterion for selecting reflection experiences.

  2. Experiments span multiple task types and two model configurations. The DeepSeek gains are encouraging, and the component ablations provide evidence supporting the design.

Critical weaknesses
  1. Limited significance and conceptual novelty. The paper provides an incremental improvement to sampling within an existing prompt optimizer. The theoretical results primarily formalize the credit-assignment rule and conditional-probability decomposition, offering limited additional understanding of when or why particular experiences produce transferable improvements.

  2. Incomplete comparisons with simpler alternatives. The component ablations support the design, but do not establish whether the Transfer Matrix provides advantages over directly tracking historical repair gains or sampling by estimated success rate. The exploration bonus is also not separately ablated, leaving its contribution unclear.

Questions for authors
  1. How does EvoSampler compare with directly averaging historical retained repair counts under the same exploration rule? This comparison would help establish the value of the proposed decomposition.

  2. Can the authors provide representative optimized prompts and explain how instance-specific answer memorization and near-duplicate examples across splits are checked?

6 comments
AuthorsOpenReview ↗

W1: Limited significance and conceptual novelty

Thank you for the thoughtful assessment and constructive suggestions. We have clarified the scope of our contribution and added controlled comparisons and analyses addressing the reviewer’s concerns.

W1: Limited significance and conceptual novelty

To our knowledge, EvoSampler is among the very first plug-and-play dynamic experience samplers for black-box prompt optimization that explicitly models both repairability and prompt-conditioned transferability. It is broadly compatible with existing prompt optimization frameworks and improves upon state-of-the-art methods without requiring additional model calls or evaluation overhead.

Theoretically, Theorem 1 formalizes utility attribution under batch-level shared credit, and Theorem 2 derives the expected-utility decomposition into two quantities: the probability that an instance participates in a retained revision (Repairability) and the conditional probability that such a revision resolves a currently unresolved validation failure (Transferability). This decomposition provides a principled basis for the utility optimized by EvoSampler.

Methodologically, EvoSampler translates the theoretical utility decomposition into a practical, plug-and-play sampling strategy for black-box prompt optimization. By leveraging feedback already available during optimization, it dynamically estimates the value of training instances according to their repairability and their potential to resolve the current prompt's remaining validation failures, without introducing additional evaluation overhead. Theorems 1 and 2 provide the theoretical foundation for this process, connecting batch-level optimization feedback to instance-level utility estimation and enabling principled, prompt-conditioned experience selection.

AuthorsOpenReview ↗

W2&Q1: Incomplete comparisons with simpler alternatives

Thank you for suggesting a comparison with historical success-rate sampling. The existing w/o Transfer Matrix ablation provides this comparison: it uses only the Repairability Vector, which estimates the probability that a batch containing instance tit_i yields a retained revision. The estimate uses a Beta(1,1) prior, and the ablation retains initial coverage and the same UCB exploration rule. Thus, it tests whether the Transfer Matrix adds value beyond a smoothed historical retention rate.

Beta smoothing avoids extreme estimates from very few observations: an unsmoothed empirical rate can become 0 or 1 after a single outcome. The prior instead stabilizes estimates in the sparse-observation setting.

The existing Table 2 reports the following results:

MethodHMMTScienceWorldIFBenchAverage
EvoSampler76.6797.0076.6783.45
w/o Transfer Matrix70.0097.0075.5680.85

The Transfer Matrix improves the average score in these experiments, with task-dependent effects: EvoSampler performs better on HMMT, ties on ScienceWorld, and performs better on IFBench.

We also add Beam Search (Uniform Sampling), Failure-based Sampling, and Historical Failure Pool Sampling as supplementary baselines. Their results are reported below.

Table R1: Supplementary sampling baselines (mean ± standard deviation over three runs with seed 42).

MethodHMMTALFWorldIFBenchAverage
GEPA71.67 ± 1.6776.33 ± 3.2174.82 ± 1.2974.27
Beam Search (Uniform Sampling)72.22 ± 1.9276.67 ± 2.3172.96 ± 1.7073.95
Failure-based Sampling70.56 ± 1.9366.67 ± 3.7972.59 ± 1.7069.94
Historical Failure Pool Sampling72.78 ± 0.9672.00 ± 1.0073.70 ± 3.4072.83
EvoSampler73.89 ± 1.9279.33 ± 4.5178.52 ± 3.3977.25

We further add a w/o UCB ablation that retains the learned components and initial coverage but removes the exploration bonus. The results are reported in Table R4.

Table R4: Component and exploration ablations (mean ± standard deviation over three runs with seed 42).

MethodHMMTALFWorldIFBenchAverage
EvoSampler73.89 ± 1.9279.33 ± 4.5178.52 ± 3.3977.25
w/o Transfer Matrix73.33 ± 1.6775.00 ± 4.3675.19 ± 2.8074.51
w/o Repairability Vector70.56 ± 3.4775.00 ± 1.0071.85 ± 1.2872.47
w/o both71.11 ± 2.5573.00 ± 1.7374.45 ± 2.9472.85
Unmask72.78 ± 2.5574.00 ± 3.6175.19 ± 3.5773.99
w/o UCB71.67 ± 2.8972.33 ± 1.5373.70 ± 3.5772.57
AuthorsOpenReview ↗

Q2: Representative prompts and cross-split memorization

We provide the complete prompt optimized by EvoSampler on ALFWorld.

You are an agent interacting with a simulated household (AlfWorld) over multiple turns. Complete the task described in the first observation. Each turn you are shown AVAILABLE ACTIONS; choose exactly one available action and emit it as:
<call name="step">{"action": "..."}</call>
Do not output anything else. The call body must be valid JSON with a single string field "action". Use exact action strings from AVAILABLE ACTIONS.

Plan efficiently and minimize turns. Before moving, identify:
1. The target object(s) and any required state (e.g., clean, hot, cool).
2. The destination or tool needed.
3. The shortest route to find and manipulate the object.

Strategy:
- Check likely locations first. If the task is to put an object in/on a location, check that destination first because the object may already be there.
- For tasks like "put a clean egg in diningtable", check diningtable first; if the egg is there, take it, clean it, then put it back.
- For tasks like "put two bowls in dresser", locate bowls, take one, put it in the dresser, then go get the next bowl. If the "take" action for a second item is not available while holding something, put the held item at the destination first.
- For examine/use tasks like "examine the mug with the desklamp", take the mug if needed, locate the desklamp, go to it, then use it while holding the mug.
- For state-change tasks (clean, heat, cool), first locate the object, then go to the appropriate tool/location (sinkbasin for clean; stoveburner or microwave for heat; fridge for cool), perform the state change, then go to the final destination and put the object.

Search efficiency (important):
- After checking the destination, prefer open surfaces/receptacles over closed containers. Inspect visible items on countertops, tables, sinks, bathtubs, toilets, stoveburners, etc., before opening drawers, cabinets, fridges, or microwaves.
- In bathrooms, common open locations include countertop(s), sinkbasin, bathtubbasin, toilet(s), towelholders, and handtowelholder. Check toilet early for small objects like candles, soap, and spraybottles.
- In kitchens, common open locations include countertop(s), sinkbasin, stoveburners, coffeemachine, toaster, and microwave top. Check these before many cabinets/drawers.
- Do not open more than one or two likely closed containers if open surfaces remain unchecked. If you open a container and it is empty or irrelevant, move to the next unchecked open location rather than exhaustively opening every drawer/cabinet.
- Once you have the target object, go directly to the required destination/tool and perform the next necessary action. Avoid extra examining or detours.
- Each exploratory action costs a turn. Assume a limited turn budget and avoid long exhaustive searches.

Open closed containers only when needed. Prefer known or likely containers over exhaustive searching.

If an action you want is not listed in AVAILABLE ACTIONS, do not repeat it. Reconsider prerequisites: open the container, go to the correct location, or put down a held item. If you receive "Nothing happens", your previous action was invalid; choose only from the current AVAILABLE ACTIONS.

Keep the next action simple and directly advancing the task. When the environment reports the task is complete, stop.

It includes general planning and search guidance, such as prioritizing likely locations, sequencing object-state changes, and avoiding unnecessary exploration.

Importantly, seemingly instance-specific modifications can capture reusable insights that improve performance on similar tasks, consistent with the fundamental motivation of memory-based learning: leveraging past experiences to guide future decisions. The objective of prompt evolution is not to memorize individual training instances, but to improve overall performance across the task distribution. EvoSampler further evaluates candidate revisions on a separate validation set and demonstrates their generalization through performance improvements on an independent, held-out test set.

We use the benchmark’s prescribed train, validation, and test splits: training instances drive prompt revisions, validation outcomes guide candidate selection and utility estimation, and test instances are reserved for final evaluation. We manually inspected examples across splits and found no evidence of substantial near-duplicate overlap. We will clarify that this was a manual inspection and describe its scope in the revised paper.

Reviewer_CFmqOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how to select training examples for prompt evolution under a limited optimization budget. EvoSampler uses past revision outcomes to estimate how often examples lead to retained candidates and which unresolved validation problems those candidates tend to solve. It combines these estimates with a UCB-style exploration rule to select revision batches. Experiments cover five benchmarks and two model configurations. The method achieves the highest average test score in both configurations, with ablations and trace analyses examining its components.

Critical strengths
  1. The paper addresses a useful question: which experiences should an optimizer use to revise a prompt? Using previous evaluation outcomes to guide this choice is a practical idea, particularly when generating and evaluating revisions is expensive.
  2. The experiments cover several task types and two model configurations. The improvements over GEPA are encouraging, and the component ablations provide some evidence that both repairability estimation and validation-error masking are useful.
Critical weaknesses
  1. The use of historical outcomes needs stronger justification. All examples in a batch receive the same credit, and observations are pooled across changing prompts. The paper does not examine whether these estimates remain reliable as the prompt and batch composition change.

  2. The predictive evaluation is underspecified. Section 4.4 does not clearly explain whether predictions are computed before observing their corresponding outcomes. The prediction units and aggregation procedures in Tables 3 and 4 also need clarification.

  3. The contribution of exploration is not isolated. Despite the introduction’s claim, Table 2 contains no explicit ablation removing UCB while retaining the learned utility. It is also unclear whether “w/o both” preserves the same exploration and initial-coverage rules.

Questions for authors
  1. Clarification: What labels and prediction units are used in Tables 3 and 4? Are the predictions always computed before observing the outcomes? Why is repairability evaluated against training-example improvement rather than candidate retention?
  2. Clarification: How is one evaluation counted, and what budget does each baseline receive? How are training executions, validation executions, and reflection calls included in the comparison?
  3. Evidence that could change my assessment: Do the gains hold across independent optimization seeds under matched budgets? Does “w/o both” retain UCB and initial coverage, and how does the full method perform without UCB?
5 comments
AuthorsOpenReview ↗

W1: Reliability of historical estimates under shared credit and changing prompts

Thank you for the thoughtful comments and questions. We clarify the interpretation of our historical estimates, the supplementary predictive-evaluation protocol, the ablation settings, and the evaluation-budget accounting.

W1: Reliability of historical estimates under shared credit and changing prompts

We agree that a revision is generated from the joint feedback of a training batch, so its outcome cannot be directly attributed causally to any single instance. As revisions are generated and evaluated across different parent prompts and training batches, accumulating diverse observations progressively improves the reliability of these shared-credit estimates.

The estimates pool observations across the optimization trajectory. At each round, however, EvoSampler recomputes utility using the current parent prompt’s unresolved validation set. Thus, historical transfer estimates are applied to the failures that remain at that round.

To assess predictive validity beyond the trajectory from which the estimates were learned, we freeze the final Repairability Vector and Transfer Matrix learned by EvoSampler and evaluate them on independently collected GEPA trajectories with uniform training-instance sampling. The estimates are scored without using outcomes from the corresponding branches. Results are reported in Tables R2–R3 below.

AuthorsOpenReview ↗

W2&Q1: Prediction targets, units, and evaluation timing

We will specify the prediction units, labels, and aggregation procedures in Appendix D.4. Let a revision branch be b=(P,B,P~)b=(P,B,\widetilde P), where PP is the parent prompt, BB is the training batch, and P~\widetilde P is the candidate revision.

For training-batch improvement, each branch is one prediction unit. The binary label for AUC indicates whether P~\widetilde P scores higher than PP on BB; AUC is computed by pooling branches across three GEPA trajectories. For Spearman correlation, predicted scores and observed score changes are centered within groups sharing the same run, iteration, and parent prompt, then pooled to compute the correlation.

For validation-gap repair, each eligible pair (b,j)(b,j), where validation instance jj is unresolved by PP and sufficient historical observations are available, is one prediction unit. Its label indicates whether the retained revision resolves jj. AUC and Spearman correlation are computed separately for each GEPA trajectory and averaged across three trajectories. The estimates are frozen before evaluation, and outcomes from the corresponding GEPA trajectories are used only for evaluation.

Candidate retention is the direct Bernoulli outcome used to update the Repairability Vector. Training-batch improvement is an additional downstream target: it tests whether the learned estimates predict improvement on a sampled batch, beyond the retention signal used to learn Repairability.

Table R2: Prediction of training-batch improvement on GEPA trajectories.

(a) AUC

PredictorHMMTALFWorldIFBench
Repairability Vector0.62370.62590.6889
Utility Score0.69640.65210.6954
Transfer Matrix0.69000.55310.5199
Random (expected)0.5000.5000.500

(b) Spearman correlation

PredictorHMMTALFWorldIFBench
Repairability Vector+0.0858+0.1995+0.1173
Utility Score+0.1133+0.2075+0.0853
Transfer Matrix−0.0872−0.1518−0.1585
Random (expected)0.0000.0000.000

Table R3: Prediction of validation-gap repair on GEPA trajectories.

(a) AUC

PredictorHMMTALFWorldIFBench
Transfer Matrix0.88650.65800.8567
Utility Score0.86920.72210.7984
Repairability Vector0.70290.61710.5910
Random (expected)0.5000.5000.500

(b) Spearman correlation

PredictorHMMTALFWorldIFBench
Transfer Matrix+0.3796+0.1784+0.2510
Utility Score+0.3617+0.2469+0.2129
Repairability Vector+0.2013+0.1357+0.0615
Random (expected)0.0000.0000.000
AuthorsOpenReview ↗

W3&Q3: Exploration ablation, w/o both, and repeated runs

The w/o both variant removes the learned Repairability and Transferability components while retaining mandatory initial coverage and count-based UCB exploration. With identical learned utilities, selection is driven by the count-based exploration bonus, yielding round-robin-style coverage.

The w/o UCB variant retains both learned components, masking, and initial coverage, but sets λ=0\lambda=0, removing the exploration bonus. We report this ablation alongside the component ablations in Table R4.

The supplementary baselines and ablations are each run three times using the same data splits, and method-specific budgets. These runs characterize variability across repeated executions under stochastic model responses.

Our method significantly outperforms the other baselines, and the ablation results are consistent with our expectations.

Table R1: Supplementary sampling baselines (mean ± standard deviation over three fixed-seed runs).

MethodHMMTALFWorldIFBenchAVG
GEPA71.67 ± 1.6776.33 ± 3.2174.82 ± 1.2974.27
Beam Search (Uniform Sampling)72.22 ± 1.9276.67 ± 2.3172.96 ± 1.7073.95
Failure-based Sampling70.56 ± 1.9366.67 ± 3.7972.59 ± 1.7069.94
Historical Failure Pool Sampling72.78 ± 0.9672.00 ± 1.0073.70 ± 3.4072.83
EvoSampler73.89 ± 1.9279.33 ± 4.5178.52 ± 3.3977.25

Table R4: Component and exploration ablations (mean ± standard deviation over three fixed-seed runs).

MethodHMMTALFWorldIFBenchAVG
EvoSampler73.89 ± 1.9279.33 ± 4.5178.52 ± 3.3977.25
w/o Transfer Matrix73.33 ± 1.6775.00 ± 4.3675.19 ± 2.8074.51
w/o Repairability Vector70.56 ± 3.4775.00 ± 1.0071.85 ± 1.2872.47
w/o both71.11 ± 2.5573.00 ± 1.7374.45 ± 2.9472.85
Unmask72.78 ± 2.5574.00 ± 3.6175.19 ± 3.5773.99
w/o UCB71.67 ± 2.8972.33 ± 1.5373.70 ± 3.5772.57
Reviewer_kkHkOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies training-instance selection ("experience sampling") during black-box prompt evolution (specifically built on top of GEPA). Instead of sampling small revision batches uniformly at random from Dtrain\mathcal{D}_{\text{train}}, the authors propose EvoSampler, which scores each training instance tit_i by its expected contribution to resolving validation failures of the current parent prompt PP. EvoSampler decomposes this utility into: (1) a Repairability Vector ρ^i\widehat{\rho}_i, tracking the Beta–Bernoulli posterior probability that batches containing tit_i yield a retained prompt revision; and (2) a Transfer Matrix M^∈[0,1]K×N\widehat{\mathbf{M}} \in [0,1]^{K \times N}, tracking the Beta–Bernoulli posterior probability that a retained revision induced by tit_i solves each validation instance vjv_j, masked by the current prompt's unresolved validation indicator r(P)\mathbf{r}(P). Selection combines this utility with a UCB bonus. Across five benchmarks (subsets of MATH-500, HMMT, ScienceWorld, ALFWorld, IFBench) and two LLM configurations, EvoSampler outperforms GEPA, APEX, TextGrad, and MIPRO.

Critical strengths
  1. Well-motivated problem. Focusing on which training experiences feed into reflection—rather than only how prompt mutations are generated—identifies a practical bottleneck in evolutionary prompt optimization under tight evaluation budgets.
  2. Plug-and-play modular design. Conditioning sample selection on the current prompt's unresolved validation mask r(P)\mathbf{r}(P) is intuitive, requires zero extra LLM calls, and integrates cleanly into existing Pareto/evolutionary prompt optimizers like GEPA.
  3. Broad task coverage. Experiments span math reasoning, multi-step interactive agents, and verifiable instruction following across two frontier model pairs.
Critical weaknesses

W1. Severe observation sparsity vs. parameterization of the K×NK \times N Transfer Matrix.

  • Under the 1,000-evaluation budget (Appendix C.3) with ∣Dval∣∈{30,45}|\mathcal{D}_{\text{val}}| \in \{30, 45\} and batch size k=3k=3, full validation of each candidate allows only ~20–30 revision rounds in total. Simply completing the mandatory initial coverage of K=40K=40 training instances (⌈40/3⌉=14\lceil 40/3 \rceil = 14 rounds, Eq. 50) already consumes roughly half of the optimization budget.
  • Crucially, Transfer Matrix entries μij\mu_{ij} (40×45=1,80040 \times 45 = 1,800 parameters) only receive an update when tit_i is sampled and the resulting candidate is retained (A(ℓ)=1A^{(\ell)} = 1, Eqs. 18–19). Over ~20–30 rounds, most training instances participate in 0 to 2 retained revisions total—far too few to meaningfully estimate instance-to-instance transfer probabilities beyond the Beta(1,1)\text{Beta}(1,1) prior and batch-level shared-credit noise.
  • This sparsity is reflected in the weak predictive correlations (Tables 7–8): e.g., Spearman ρ\rho is 0.0750.075 on ScienceWorld for training improvement, and Utility Score gets −0.051-0.051 Spearman correlation (AUC 0.470<0.50.470 < 0.5) on IFBench for predicting validation resolution. W2. Scale mismatch in the UCB rule and stationarity of repairability.
  • Appendix B.5 motivates the exploration bonus bi(q)=2log⁡T/nib_i^{(q)} = \sqrt{2\log T / n_i} via Hoeffding's inequality for rewards in [0,1][0, 1]. However, U^i(P)=ρ^i∑j=1Nμ^ijrj(P)\widehat{U}_i(P) = \widehat{\rho}_i \sum_{j=1}^N \widehat{\mu}_{ij} r_j(P) is an unnormalized sum over NN validation items (up to N=45N=45). Early in optimization when many validation items are unresolved, U^i(P)\widehat{U}_i(P) is on the order of 55–1515, completely dominating λbi(q)\lambda b_i^{(q)} with fixed λ=0.2\lambda = 0.2, whereas late in optimization U^i(P)\widehat{U}_i(P) shrinks by an order of magnitude.
  • Furthermore, pooling ρi\rho_i as stationary across the entire trajectory (Eqs. 14–15) ignores diminishing returns: once a retained revision fixes the flaw exposed by tit_i, resampling tit_i in later rounds will likely show tit_i already solved and yield no further useful edits, yet its historical ρ^i\widehat{\rho}_i remains high.
  • Minor presentation issue: "Theorem 1" and "Theorem 2" are elementary definitions and a one-line application of the probability chain rule, which should be stated as definitions/observations rather than formal theorems. W3. Missing simple baselines (e.g., failure-only / round-robin sampling).
  • Section 2.2 motivates EvoSampler by noting that uniform sampling wastes budget on training instances the current prompt already solves. Yet the experiments omit the most natural, zero-parameter baseline: sampling uniformly among training instances that the parent prompt PP currently fails on (or round-robin sampling without replacement across rounds).
  • Notably, in Table 2, w/o both (which reduces to deterministic round-robin coverage via UCB counts) yields 63.33 / 95 / 74.44, matching GEPA identically on all three tasks—suggesting that enforce-coverage behavior and small-sample variance need to be carefully disentangled from learned transfer estimates. W4. Single-seed evaluation (seed=42) on small subsampled test splits at high temperature.
  • All experiments are run with a single random seed (42) (Appendix C.3), despite using temperature = 1.0 for reflection models and for interactive environments (ALFWorld, ScienceWorld), where trajectory variance is substantial.
  • Test splits are subsampled to just 60–100 examples per task (e.g., 60 for HMMT, 100 out of 500 for MATH-500, 90 for IFBench). On 60 problems, a 2-problem swing is 3.333.33 percentage points. Without multi-seed means and standard errors, it is difficult to assess statistical significance, especially on the Gemini 3 Flash + Claude Opus 4.6 setup where the average gain over GEPA is only +1.60+1.60 points (87.6087.60 vs. 86.0086.00, Table 6) and EvoSampler underperforms TextGrad/MIPRO on HMMT.
  • Relying heavily on Dval\mathcal{D}_{\text{val}} both to retain candidates and to actively steer training-batch selection toward unresolved validation items also raises potential validation-overfitting concerns when ∣Dval∣=30–45|\mathcal{D}_{\text{val}}| = 30\text{–}45.
Questions for authors
  1. Effective number of updates per (ti,vj)(t_i, v_j): Under the 1,000-evaluation budget, how many total revision rounds occur on average per benchmark, how many times is a typical tit_i sampled, and what is the average number of retained updates (BℓiA(ℓ)=1B_{\ell i} A^{(\ell)} = 1) per tit_i? With so few observations, how much of M^\widehat{\mathbf{M}} deviates from the Beta(1,1)\text{Beta}(1,1) prior?
  2. Comparison to Failure-Only Sampling: How does GEPA perform if revision batches B\mathcal{B} are simply sampled uniformly (or via UCB/round-robin) from training instances in Dtrain\mathcal{D}_{\text{train}} that the parent prompt PP currently fails to solve?
  3. Multi-seed variance: Can you report mean and standard deviation across at least 3–5 optimization seeds (at minimum for EvoSampler vs. GEPA on HMMT, ALFWorld, and IFBench)?
  4. UCB normalization: Why is U^i(P)\widehat{U}_i(P) summed rather than averaged over unresolved validation instances (or normalized to [0,1][0,1]) before adding λbi(q)\lambda b_i^{(q)}? Also, why does Utility Score perform worse than random (AUC=0.470\text{AUC} = 0.470, Spearman =−0.051= -0.051) on IFBench in Tables 4 and 8?
  5. Budget accounting across baselines: How is the 1,000-evaluation budget counted for multi-step interactive tasks (per episode vs. per environment step) and matched across TextGrad, MIPRO, APEX, and GEPA?
6 comments
AuthorsOpenReview ↗

W1&Q1: Observation sparsity in the Transfer Matrix

Thank you for the detailed review and constructive questions. We have clarified the evaluation protocol and added analyses and baselines to address the concerns about observation sparsity, exploration, and evaluation fairness.

W1: Observation sparsity in the Transfer Matrix

Full validation is performed only when a candidate improves its training-batch score, rather than after every proposed revision. In our logs, each training instance participates in an average of 5.61 revision attempts and 1.22 full validations, while 63.74% of Transfer Matrix entries receive observation-driven updates. This sparsity partly reflects that many proposed revisions fail even the training-batch improvement check and therefore never reach full validation. Such failures are informative: when an instance repeatedly fails to induce improvements on its training batch, there is little reason to expect its feedback to produce generalizable revisions.

This motivates the Repairability Vector. It learns from frequent, relatively inexpensive retention signals, including rejections before full validation, to identify training instances more likely to yield useful revisions. This directs subsequent sampling toward promising instances, concentrating expensive validation evaluations on candidates with greater potential and allowing transfer evidence to accumulate where it is most informative. Moreover, EvoSampler's Top-k selection requires relative rankings of training-instance utility, rather than precise calibration of every Transfer Matrix entry. Beta(1,1) smoothing and UCB exploration further address sparse observations, while both estimators reuse existing optimization feedback without additional model-evaluation calls.

The most direct evidence of estimation quality comes from independent-trajectory prediction, rather than observation counts. On independently collected GEPA trajectories, we evaluate frozen estimates without using outcomes from the corresponding branches (Appendix D.4). The Repairability Vector predicts training-batch improvement above chance on all three benchmarks, while Utility Score achieves the highest AUC on each (Table R2). For validation-gap repair, the Transfer Matrix achieves AUCs of 0.8865, 0.6580, and 0.8567 on HMMT, ALFWorld, and IFBench, respectively, all exceeding the random baseline of 0.5 (Table R3). Together with the held-out results and ablations in Tables R1 and R4, these findings support effective utility-based selection under limited observations.

Table R2: Prediction of training-batch improvement on GEPA trajectories.

(a) AUC

PredictorHMMTALFWorldIFBench
Repairability Vector0.62370.62590.6889
Utility Score0.69640.65210.6954
Transfer Matrix0.69000.55310.5199
Random (expected)0.5000.5000.500

(b) Spearman correlation

PredictorHMMTALFWorldIFBench
Repairability Vector+0.0858+0.1995+0.1173
Utility Score+0.1133+0.2075+0.0853
Transfer Matrix−0.0872−0.1518−0.1585
Random (expected)0.0000.0000.000

Table R3: Prediction of validation-gap repair on GEPA trajectories.

(a) AUC

PredictorHMMTALFWorldIFBench
Transfer Matrix0.88650.65800.8567
Utility Score0.86920.72210.7984
Repairability Vector0.70290.61710.5910
Random (expected)0.5000.5000.500

(b) Spearman correlation

PredictorHMMTALFWorldIFBench
Transfer Matrix+0.3796+0.1784+0.2510
Utility Score+0.3617+0.2469+0.2129
Repairability Vector+0.2013+0.1357+0.0615
Random (expected)0.0000.0000.000
AuthorsOpenReview ↗

W2&Q4: UCB scale and stationarity

The summed utility directly aligns with our optimization objective: maximizing the expected total number of newly solved validation instances, as captured by U^i(P)=ρ^i∑jμ^ijrj(P)\widehat{U}_i(P)=\widehat{\rho}_i\sum_j\widehat{\mu}_{ij}r_j(P) . While averaging preserves the relative exploitation rankings for a fixed parent prompt, direct normalization without adjusting the exploration bonus can distort the exploration–exploitation balance. For example, consider 10,000 unresolved validation instances, where two training instances are expected to resolve 100 and 200, respectively. Their expected total gains differ by 100, but their normalized utilities differ by only 0.01. Keeping the exploration bonus unchanged would disproportionately amplify exploration, potentially obscuring substantial differences in expected validation gain. We therefore retain the summed utility to preserve the scale of our optimization objective.

We adopt a UCB-style exploration bonus to balance utility-based exploitation with the exploration of under-observed training instances. To assess its empirical contribution, we conduct a w/o UCB ablation that retains both learned components and mandatory initial coverage while removing the exploration bonus. EvoSampler outperforms this variant on all three benchmarks, improving the macro average from 72.57 to 77.25 (+4.68 percentage points, Table R4).

The Repairability Vector aggregates historical retention outcomes and is continuously updated with new observations, allowing subsequent sampling decisions to incorporate changes in an instance's ability to induce successful revisions.

The previous IFBench predictive result (AUC 0.470 and Spearman −0.051) is re-examined using the revised independent-trajectory protocol. The corresponding results under the independent-trajectory protocol are reported in Tables R2–R3.

Theorems 1 and 2 formalize the shared-credit attribution of realized utility and its expected-utility decomposition, respectively, with concise theoretical derivations provided in Appendices B.2 and B.3.

AuthorsOpenReview ↗

W3: Simple sampling baselines

We add three supplementary sampling baselines:

  • Beam Search (Uniform Sampling): uniform selection of training instances within a beam-search optimizer.
  • Failure-based Sampling: uniform sampling from training instances the current parent prompt fails to solve.
  • Historical Failure Pool Sampling: uniform sampling from a historical pool of failed instances, removing instances once solved.

The original w/o both ablation also provides count-based exploration with mandatory initial coverage. Supplementary results are reported in Table R1.

Table R1: Supplementary sampling baselines (mean ± standard deviation over three fixed-seed runs).

MethodHMMTALFWorldIFBenchAVG
GEPA71.67 ± 1.6776.33 ± 3.2174.82 ± 1.2974.27
Beam Search (Uniform Sampling)72.22 ± 1.9276.67 ± 2.3172.96 ± 1.7073.95
Failure-based Sampling70.56 ± 1.9366.67 ± 3.7972.59 ± 1.7069.94
Historical Failure Pool Sampling72.78 ± 0.9672.00 ± 1.0073.70 ± 3.4072.83
EvoSampler73.89 ± 1.9279.33 ± 4.5178.52 ± 3.3977.25

Comments on the paper

1 comment
AuthorsOpenReview ↗

Global Response

We sincerely thank the AC for handling our submission and all reviewers for their valuable feedback. To facilitate the AC's assessment, we summarize our key contributions, positive reviewer comments, and major rebuttal additions and responses.

Key Contributions and Significance

  • An important, underexplored problem with practical value. Dynamic data sampling is widely used to improve the efficiency of parameter fine-tuning, but extending it to black-box textual optimization remains challenging due to sparse feedback and expensive evaluations. To our knowledge, dynamic training-experience sampling remains largely unexplored in open-source black-box prompt optimization. EvoSampler advances prompt optimization from a new dimension—experience selection, achieving higher held-out performance than all compared state-of-the-art methods under both model configurations, without additional LLM evaluation calls.

  • Principled utility modeling and core insight. Our key insight is that historical repair experiences contain transferable signals: an experience that previously helped resolve a validation failure may remain valuable when that failure is unresolved by the current prompt. We formalize this through the Repairability Vector and Transfer Matrix, modeling revision success and training-to-validation repair relationships, and combine them with prompt-dependent utility estimation and UCB exploration.

Overview of Positive Reviewer Comments

  • Problem significance and practicality (kkHk, CFmq). kkHk recognized experience selection as "a practical bottleneck" and highlighted the "zero extra LLM calls" design. CFmq described using historical evaluation outcomes as "a practical idea."
  • Methodological design (ZBEM). ZBEM recognized that combining historical revision outcomes with current failures provides "a sensible criterion" for selecting reflection experiences.
  • Experimental evidence (CFmq, ZBEM). CFmq found the improvements over GEPA "encouraging," while ZBEM acknowledged that the component ablations support the method's design.

Summary of Reviewer Suggestions and Our Revisions

  • Additional sampling baselines (kkHk, ZBEM). We added uniform beam-search sampling, current-failure sampling, and historical-failure-pool sampling. EvoSampler ranks first on all three benchmarks, with macro-average gains of 3.30, 7.31, and 4.42 percentage points, respectively (Table 7).
  • Component effectiveness and UCB exploration ablation (CFmq, ZBEM). We added a dedicated UCB ablation and conducted three repeated runs for the full method and all component ablations. EvoSampler achieves the highest mean score on all three benchmarks among the ablation variants, providing further evidence of component effectiveness and robustness. In particular, UCB exploration improves the macro average from 72.57 to 77.25 (Table 8).
  • Statistical analysis and independent-trajectory validation (kkHk, CFmq). We evaluated both estimators on independent GEPA trajectories. The Transfer Matrix achieves an average AUC of 0.8004 and Spearman correlation of 0.2697 for predicting validation-gap repair (Tables 9–10), while the Repairability Vector achieves an average AUC of 0.6462 and Spearman correlation of 0.1342 for predicting training-batch improvements (Tables 11–12). These results provide strong quantitative evidence supporting our core hypothesis and the effectiveness of both components.

Summary of Responses to Reviewers

  • Reviewer kkHk. We provided detailed analyses of observation coverage and utility estimation under sparse feedback, supplemented by independent-trajectory predictive validation. We also clarified the UCB exploration design and evaluation-budget protocol, providing comprehensive theoretical explanations and empirical evidence.
  • Reviewer CFmq. We clarified historical feedback modeling, shared-credit attribution, and predictive evaluation procedures. Independent-trajectory validation, the dedicated UCB ablation, and repeated experiments provide stronger evidence for the reliability and effectiveness of our method.
  • Reviewer ZBEM. We elaborated on the significance of dynamic experience selection and the theoretical foundation of utility decomposition. Additional sampling baselines, historical-success-rate comparisons, a complete optimized prompt example, and cross-split inspection further substantiate our methodological contribution and generalization capability.

We sincerely appreciate the reviewers' constructive suggestions. We hope our additional experiments and analyses address the reviewers' concerns and provide further support for EvoSampler's methodological novelty, empirical reliability, and practical value.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.