Search and optimization basics

Why you need this

Every prompt optimizer in this cluster is a search: it tries versions of a program, scores them, and keeps the good ones. The vocabulary on this page (objective, search space, budget, local optimum, exploration) is the vocabulary the optimizer pages use without stopping to define. The one twist for language-model programs is that each score costs real model calls and wobbles from run to run, which changes which strategies make sense.

The idea

Three things define any search problem.

Term	Meaning	In prompt optimization
Objective function	A function $f(x)$ that gives a number for each candidate $x$; higher is better.	The average metric score $\bar{s}(p)$ of program $p$ on a validation set.
Search space	The set of all candidates you are allowed to try.	Every possible instruction and set of worked examples.
Budget	How many times you can afford to compute $f$.	A number of metric calls, each one a run of the program on one example.

A strategy decides which candidate to try next, given what you have seen so far. Two simple ones:

• Random search picks candidates at random and remembers the best. It never gets stuck, but it learns nothing from what it has seen.
• Hill climbing starts somewhere, looks at the neighbors (the candidates one small change away), and moves to the best neighbor if it is better. It stops when no neighbor is better.

A point where no neighbor is better is a local optimum (a local peak). The best point anywhere is the global optimum. Hill climbing always reaches a local peak, but which one depends on where it started. The standard fix is random restarts: climb several times from random starting points and keep the best peak.

Behind every strategy is a trade. Exploitation means spending budget near the best candidate found so far, hoping to polish it. Exploration means spending budget on unfamiliar candidates, hoping to find a better region. Pure exploitation gets stuck on the first peak; pure exploration never polishes anything.

Worked example

The search space is ten cells, numbered 0 to 9. The objective is a table of scores. Each cell's neighbors are the cells directly left and right of it.

Cell	0	1	2	3	4	5	6	7	8	9
Score	3	5	6	4	2	4	7	9	8	5

There are two peaks: cell 2 (score 6, a local peak) and cell 7 (score 9, the global peak).

One climb from cell 1. Cell 1 scores 5. Its neighbors are cell 0 (3) and cell 2 (6). Cell 2 is better, so move there. Cell 2's neighbors are cell 1 (5) and cell 3 (4). Neither beats 6, so the climb stops at cell 2 with score 6. It used 4 evaluations (cells 0, 1, 2, 3) and never learned that cell 7 exists.

Three restarts from cells 1, 6, and 3 (three starts drawn at random):

Start	Path	Stops at	Score
1	1, 2	cell 2	6
6	6, 7	cell 7	9
3	3, 2	cell 2	6

The restart from cell 6 lands in the other hill and finds the global peak. Two of the three climbs wasted their effort on the same local peak, which is normal.

This Python program does the same thing. It needs no libraries; it ran on Python 3.14, and 3.12 and newer behave the same.

score = [3, 5, 6, 4, 2, 4, 7, 9, 8, 5]   # objective value of cells 0..9

def hill_climb(start, evaluated):
    x = start
    evaluated.add(x)
    path = [x]
    while True:
        neighbors = [n for n in (x - 1, x + 1) if 0 <= n < len(score)]
        evaluated.update(neighbors)
        best = max(neighbors, key=lambda n: score[n])
        if score[best] <= score[x]:          # no neighbor is better: a peak
            return x, path
        x = best
        path.append(x)

for starts in ([1], [1, 6, 3]):
    evaluated = set()
    results = [hill_climb(s, evaluated) for s in starts]
    for s, (peak, path) in zip(starts, results):
        print(f"start {s}: path {path}, stops at cell {peak} with score {score[peak]}")
    best_peak = max((peak for peak, _ in results), key=lambda c: score[c])
    print(f"  best found: cell {best_peak}, score {score[best_peak]}; cells evaluated: {len(evaluated)}")

Run it with python hill.py. It printed:

start 1: path [1, 2], stops at cell 2 with score 6
  best found: cell 2, score 6; cells evaluated: 4
start 1: path [1, 2], stops at cell 2 with score 6
start 6: path [6, 7], stops at cell 7 with score 9
start 3: path [3, 2], stops at cell 2 with score 6
  best found: cell 7, score 9; cells evaluated: 9

The restarts cost 9 distinct evaluations to find the global peak, against 4 for the single climb that missed it. For comparison, random search with six random picks (cells 1, 6, 3, 6, 5, 4 from a seeded generator) evaluates 5 distinct cells and its best is cell 6 with score 7: it found the right hill but, unlike a climb, never stepped up it.

In an optimization pipeline

In stage 3, the candidates are versions of a program's instructions and examples, and "evaluate a cell" means running the program on many examples and averaging the metric. Two facts change the picture compared with the table above.

Evaluation is expensive. One score on a 50-example valset is 50 rollouts, each one or more model calls. An optimizer's budget is counted in these calls, so a strategy that wastes evaluations (like the two climbs that found cell 2 again) wastes real time and money.

Evaluation is noisy. The same program can score 62% on one set of 50 examples and 70% on another, and a model at nonzero temperature can answer differently on a rerun. A hill climber that trusts a noisy score will "climb" onto a candidate that only got lucky. Noisy scores and sample size quantifies this.

The optimizers respond in different ways. MIPROv2 searches combinations of instructions and examples with a model of which choices tend to score well. GEPA keeps a population of candidates rather than a single climber, which Evolutionary algorithms explains, and keeps candidates that are best on different examples, which Pareto fronts explains. Both are ways to keep exploring without giving up on exploitation.

Common mistakes

• Stopping at the first peak. Symptom: every optimization run ends at nearly the same score, and a hand-written alternative beats it easily.
• Too few evaluations per candidate. Symptom: the "best" candidate drops several points when you rerun it, because it won on luck.
• Comparing candidates on different examples. Symptom: the winner changes depending on which examples happened to be drawn, not on the candidates.
• Spending the whole budget exploring. Symptom: many different candidates, none refined, all mediocre.

Cost

With $N$ candidates in the search space, exhaustive search costs $N$ evaluations, which is impossible when the space is "every instruction someone could write". One hill climb costs about $d \times L$ evaluations, where $d$ is the number of neighbors per candidate and $L$ the number of steps taken; $R$ random restarts multiply that by $R$. For prompt optimization each evaluation is itself $n$ rollouts on an $n$-example set, so the total in model calls is roughly $R \times d \times L \times n$ times the number of predictors in the program. This is why real optimizers reuse evaluations, evaluate on small minibatches first, and spend full evaluations only on candidates that look promising.

Going further

• Evolutionary algorithms: a population of climbers that share good ideas.
• Pareto fronts: what to keep when no single candidate is best everywhere.
• Simulated annealing, a hill climber that sometimes accepts a worse move on purpose to escape local peaks.
• The multi-armed bandit problem, the cleanest statement of the explore-exploit trade.