- 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
-
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.
-
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
-
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.
-
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
-
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.
-
Can the authors provide representative optimized prompts and explain how instance-specific answer memorization and near-duplicate examples across splits are checked?
6 comments
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 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:
| Method | HMMT | ScienceWorld | IFBench | Average |
|---|---|---|---|---|
| EvoSampler | 76.67 | 97.00 | 76.67 | 83.45 |
| w/o Transfer Matrix | 70.00 | 97.00 | 75.56 | 80.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).
| Method | HMMT | ALFWorld | IFBench | Average |
|---|---|---|---|---|
| GEPA | 71.67 ± 1.67 | 76.33 ± 3.21 | 74.82 ± 1.29 | 74.27 |
| Beam Search (Uniform Sampling) | 72.22 ± 1.92 | 76.67 ± 2.31 | 72.96 ± 1.70 | 73.95 |
| Failure-based Sampling | 70.56 ± 1.93 | 66.67 ± 3.79 | 72.59 ± 1.70 | 69.94 |
| Historical Failure Pool Sampling | 72.78 ± 0.96 | 72.00 ± 1.00 | 73.70 ± 3.40 | 72.83 |
| EvoSampler | 73.89 ± 1.92 | 79.33 ± 4.51 | 78.52 ± 3.39 | 77.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).
| Method | HMMT | ALFWorld | IFBench | Average |
|---|---|---|---|---|
| EvoSampler | 73.89 ± 1.92 | 79.33 ± 4.51 | 78.52 ± 3.39 | 77.25 |
| w/o Transfer Matrix | 73.33 ± 1.67 | 75.00 ± 4.36 | 75.19 ± 2.80 | 74.51 |
| w/o Repairability Vector | 70.56 ± 3.47 | 75.00 ± 1.00 | 71.85 ± 1.28 | 72.47 |
| w/o both | 71.11 ± 2.55 | 73.00 ± 1.73 | 74.45 ± 2.94 | 72.85 |
| Unmask | 72.78 ± 2.55 | 74.00 ± 3.61 | 75.19 ± 3.57 | 73.99 |
| w/o UCB | 71.67 ± 2.89 | 72.33 ± 1.53 | 73.70 ± 3.57 | 72.57 |
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.
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.