Search and Evolution
The previous three chapters established who changes what and which execution results guide the change. The next problem is deciding which candidates to try first and what to try next after observing their results. Small edits to prompts, workflows, and code can change behavior sharply, while evaluation is costly and noisy. This chapter organizes search methods by the order in which they evaluate candidates, the history they retain, and how they allocate the budget.
Best-of-\(N\) as the Baseline
The simplest optimizer independently generates \(N\) candidates and selects the one with the highest development score.
This baseline is important. Even if a complex search algorithm wins, it may simply have used more candidates or tokens. Comparisons should match the following quantities.
- Number of candidates
- Proposal tokens per candidate
- Number of cases used to run each candidate
- Target model and optimizer model
- Number of validation queries
- Wall time with parallel execution
When scores are noisy, simply increasing \(N\) makes it more likely that a candidate with an accidentally high score will be selected. Improvements from Best-of-\(N\) include both artifact quality and selection noise.
Search with History in the Prompt
APE generates instruction candidates from task examples, scores them on a subset, and reselects them (Zhou et al. 2023). OPRO lists past candidates and scores in a meta-prompt and asks an optimizer large language model (LLM) to generate the next candidate (Yang et al. 2024). Rather than using numerical gradients, the LLM reads patterns in the history.
In this approach, the meta-prompt is the search state. Including every past candidate expands the context, while retaining only the top candidates discards the exploration history. Moreover, OPRO’s reported tables include an analysis that presents the instruction with the highest test accuracy under each setting. The method’s search mechanism must be distinguished from its effect size under clean held-out selection.
An LLM that merely generates candidates is not necessarily itself the optimizer. The outer loop that records, evaluates, selects, and stops candidates is the optimizer.
Local Search and Beam Search
Local search edits the neighborhood of the incumbent. Given prompt \(p_t\) and an edit operator \(M\),
\[ \mathcal{C}_t = \{M(p_t,z_j)\}_{j=1}^{m} \]
constructs a set of neighboring candidates. Here, \(z_j\) can be an incorrect answer, critique, or mutation instruction.
ProTeGi creates textual gradients from minibatch errors and adds prompt paraphrases and edits to a beam. It also uses bandit selection to allocate evaluation budget among candidates in the beam (Pryzant et al. 2023). This makes use of the direction indicated by failures rather than relying on scalar-only search, but if the local critique is wrong, the entire beam can move in the same direction.
The primary ProTeGi paper also includes an example in which training performance rises over successive iterations while test performance deteriorates. Some of its main results max-pool multiple prompts from the final beam at test time. Comparisons should therefore separate persistent improvement to a single prompt, search-time selection, and test-time ensembling.
TextGrad propagates natural-language feedback to text variables in a computation graph and repeatedly applies local edits (Yuksekgonul et al. 2025). When the graph is fixed, this is local parameter search and differs from methods that search the workflow topology itself.
Tree Search
Tree search branches the history by treating candidates as nodes and edits as edges. AFlow represents workflows as code nodes and uses Monte Carlo tree search to generate and evaluate new workflows (Jiayi Zhang et al. 2025).
In MCTS, exploring only branches with high known scores biases the search toward local optima. A selection rule must balance exploration of unknown branches with exploitation of known ones. However, when workflow evaluation has high variance, it is difficult to determine whether differences in node values reflect differences between artifacts or sampling noise.
Comparisons across methods should include the search cost of the entire tree, not just the inference cost of the final workflow. AFlow’s results from searching separately for each benchmark do not demonstrate that the same workflow transfers to another environment.
Reducing Evaluation with Predictors
When every candidate cannot be evaluated with a full rollout, a surrogate can predict performance from a small number of evaluations.
MIPRO selects combinations of multi-stage LM programs with Bayesian optimization, while AgentSquare narrows workflow candidates using an in-context performance predictor (Opsahl-Ong et al. 2024; Shang et al. 2025). Selecting solely from predicted values biases search toward the surrogate’s blind spots. Evaluate finalists and high-uncertainty candidates with actual rollouts, and report prediction error as well.
Evolving Candidate Populations
Evolutionary search maintains multiple candidates as a population and repeatedly applies selection, mutation, and crossover.
EvoPrompt uses an LLM as the operator in a genetic algorithm or differential evolution to evolve natural-language instructions (Guo et al. 2024). Promptbreeder coevolves not only task prompts but also the mutation prompts that mutate them (Fernando et al. 2024). This is not general “self-improvement,” but a specific form of prompt evolution based on fixed-task fitness.
The advantage of a population is that exploration is not tied to a single incumbent. On the other hand, repeatedly measuring fitness on the same development set adapts the entire population to that set. Population diversity does not guarantee held-out generalization.
Preserving Multiple Strengths in the History
A single average score can prematurely discard candidates that perform well on specific instances. GEPA retains the union of candidates that perform best on individual validation instances in a Pareto archive and creates reflective mutations from those candidates (Agrawal et al. 2026).
A Pareto archive is not the same as multi-objective acceptance. GEPA’s archive primarily preserves strengths on different instance-level scores. Promoting a candidate that jointly satisfies quality, cost, and safety requires separate evaluation records and an acceptance rule.
Code Archives and Open-Ended Search
The Meta Agent Search method in ADAS gives an archive of evaluated agent code to a coding agent as in-context examples and generates new agent systems (Hu et al. 2025). DGM goes further by modifying the codebases of different parents in the archive and retaining even candidates whose scores do not improve immediately as stepping stones in separate lineages (Jenny Zhang et al. 2026).
Because DGM’s archive selection repeatedly evaluates the same coding benchmark, the search campaign itself is transductive. Read it separately from transfer results on other benchmarks.
“Open-ended” does not mean proceeding in arbitrary directions without evaluation. DGM runs candidate code and adds it to the archive based on benchmark scores. A broad search space that does not require monotonic improvement is different from the absence of an evaluation objective.
Measuring Selection Bias
When many candidates are compared using development scores, the maximum is biased upward because a candidate with an accidentally favorable noise term is increasingly likely to be selected. Selection bias from repeatedly reusing the same data for model selection has long been recognized (Cawley and Talbot 2010).
The remedy is not simply to use more seeds.
- Create proposals on development data
- Select the promotion candidate on validation data and record the number of queries
- Finalize the finalists before evaluating the sealed test once
- Reevaluate the incumbent with the same seeds and case runs
- Compare against a Best-of-\(N\) baseline under the same budget
- Report the distribution of candidate scores, not only the average
If a public leaderboard is used repeatedly as validation, its score is search feedback. It cannot be called the final test.
Stopping Rules
When search ends “once improvement stops,” the relevant question is which set defines improvement. Repeatedly checking a validation plateau adapts the stopping point itself to validation.
Fix one of the following in advance.
- Number of candidate evaluations
- Number of case runs
- Target / optimizer token budget
- Wall-clock budget
- Number of validation queries
- Improvement threshold and patience
- Reaching a safety or cost limit
If no significant candidate emerges before the budget is exhausted, retain the incumbent. “Always adopt the best candidate” is not a stopping rule.
Key Points
Search methods differ not in whether they use an LLM, but in their search state, proposal operator, evaluation budget, selection, and archive. Compare Best-of-\(N\), local/beam, tree, surrogate, population, Pareto, and code-archive methods under the same budget and held-out protocol. Populations and archives preserve diversity during search, but do not automatically guarantee generalization or regression-free promotion.