Prompt Optimization
What sentence should accompany a mathematical word problem? In OPRO’s experiments, the pretrained PaLM 2-L achieved 71.8% test accuracy on GSM8K with “Let’s think step by step.” With “Take a deep breath and work on this problem step-by-step.”, found by using PaLM 2-L-IT as the optimizer, it achieved 80.2%. The change was not to the model’s weights but to the instruction supplied at the beginning of its answer. The authors measured this difference with the same task model (Yang et al. 2024, Table 1).
This comparison cannot isolate the effect of the words “deep breath.” The search generated many candidates, had the model actually solve problems, and used the scores to propose further candidates. Suggesting one readable revision is different from selecting a prompt that also works on unseen problems. This chapter compares prompt search in terms of what candidates are constructed, what information guides revisions, and where the evaluation budget is allocated.
Generating Candidates Is Not Enough
Prompt optimization changes the instructions or demonstrations supplied to a fixed task model and selects candidates using evaluation results. Even when a large language model (LLM) rewrites the text, the generator is only one part of the optimizer. Evaluation, a mechanism for retaining search history, and a selection rule for keeping candidates are also required.
OPRO (Optimization by PROmpting) lists previous instructions and scores in an optimization prompt and asks the model to generate new instructions from them. Its standard setting generates 8 candidates per step and presents the top 20 instructions from the history together with 3 randomly selected training problems. On GSM8K, it evaluates candidates on a fixed 3.5% of the training set and finally measures performance on the full test set. Generation encourages diversity, whereas candidate scoring uses greedy decoding. The opening instruction emerged from this history-based search (Yang et al. 2024, secs. 4–5).
Figure 1 separates the instruction–score history from task examples, showing how past evaluations inform the next proposal.
The few problems shown to the generator and the problem set used to score candidates have different roles. The former communicate the task, while the latter estimate differences between candidates. Returning training scores to the history must also be distinguished from optimizing on test scores. More powerful search creates more opportunities to select instructions adapted to a repeatedly consulted evaluation set.
APE (Automatic Prompt Engineer) works backward from input–correct-output pairs to generate instructions that explain the transformation. It scores candidates by execution accuracy or the likelihood of correct outputs and adds paraphrases of promising candidates. Whereas OPRO directly uses a history of instructions and numerical scores for its next proposal, APE centers on inferring instructions from examples and narrowing the candidate set. For reasoning-prompt search, APE collects reasoning processes that led to correct answers and selects an answer prefix that increases their likelihood. Here, the selection criterion is not final-answer accuracy itself (Zhou et al. 2023, secs. 3, 4.3).
Figure 2 separates generation from scoring on the left and shows how promising candidates lead to further paraphrases.
The same wording is not equally effective across models. In the OPRO table discussed above, a longer step-by-step reasoning instruction found by APE under different conditions achieved 58.8% on PaLM 2-L. This is not a verdict on APE as a whole. It illustrates that the effectiveness of a discovered instruction depends on the task model and evaluation conditions. Read the generating model, task model, and scoring metric separately, not just the search method’s name.
Error-Based Revision and Multi-Step Search
A low score does not explain what to fix. Methods that use incorrect answers address this lack of information through natural-language diagnosis. ProTeGi collects a minibatch of errors under the current instruction and requests a written critique of the errors and the instruction’s weaknesses. It revises the instruction in the direction opposite to that critique and generates further paraphrases. Combining beam search, which retains multiple candidates, with evaluation-budget allocation preserves alternatives when the first revision fails (Pryzant et al. 2023, sec. 2).
The paper’s use of “gradient” for this critique is metaphorical. Rather than differentiating a loss through embeddings, the method describes the inputs on which the prompt failed and uses that description to produce different text. A plausible critique does not guarantee higher accuracy after revision. A proposed revision direction and execution-based candidate selection are both necessary.
PromptAgent incorporates error analysis into Monte Carlo tree search (MCTS) rather than limiting it to a single revision. Prompts are nodes and error-informed revisions are edges. Search selects promising nodes, expands child candidates, tries subsequent revisions, and backpropagates rewards. Decisions reflect not only a candidate’s current score but also the improvements reachable from it. Whereas ProTeGi’s beam retains promising candidates at each step, PromptAgent uses branch visits and rewards to allocate evaluation across multi-step revision paths (X. Wang et al. 2024, sec. 3).
Figure 4 shows how an error-informed revision becomes an edge in a multi-step search tree.
The ability to create those edges is not fixed either. PE2 (Prompt Engineering a Prompt Engineer) improves the meta-prompt requesting revisions, not just the search algorithm. It provides a two-stage task description that asks for error analysis before instruction revision, context about where the instruction is inserted, and a reasoning template for the analysis. Rather than merely requesting improvement, it specifies what to inspect and what to change (Ye et al. 2024, sec. 3).
Such analysis does not guarantee discovery of the correct rule. In counterfactual arithmetic tasks, PE2 also produces instructions that insert numerical corrections fitting the examples, creating shortcuts that differ from the task’s actual calculation rule. Explaining errors is not the same as finding a rule that survives distribution changes (Ye et al. 2024, sec. 5.3).
LPO (Local Prompt Optimization) approaches the problem by restricting the edit region. It first asks the model to tag a short phrase needing revision and then to revise primarily that region. It can augment existing candidate-generation methods and avoids losing effective text whenever the entire prompt is rewritten. However, an LLM chooses the edit location. The method does not measure phrase importance with numerical gradients (Jain and Chowdhary 2025, sec. 2.2).
<edit> tags. The LLM decides the location (paper Figure 2). Source: (Jain and Chowdhary 2025)
Population Search and Changing Edit Rules
Following only one improvement direction can constrain search to the initial instruction’s wording. Population-based methods retain different instructions simultaneously and generate candidates through mutation and combination. What matters is not the label “evolution,” but what constitutes an individual, what mutates, and which evaluation determines replacement.
EvoPrompt implements genetic algorithms and differential evolution over natural-language prompts. For the former, it asks an LLM to cross over and mutate parent candidates. For the latter, it extracts and changes the differing parts of two instructions, incorporates them into another instruction, and performs crossover. It translates differential-evolution operations into text-editing procedures rather than computing differences between numerical vectors. An initial population combines human-written and generated instructions, and execution results on a development set determine which candidates survive (Guo et al. 2024, sec. 3).
Figure 7 shows how differences between instructions replace numerical vector differences and become text-editing operations.
Promptbreeder gives each individual both a task instruction and an instruction for mutating that instruction. It changes mutation prompts as well as task prompts and combines operations that use the population or a history of strong candidates with operations that derive instructions from the model’s solution processes. EvoPrompt largely fixes the meta-prompts describing edit operations, whereas Promptbreeder also searches the text specifying those operations. Evaluation uses random batches of training problems, unlike a design that fully scores a fixed set each time (Fernando et al. 2024, sec. 3, Figure 1).
In Figure 8, the top shows population initialization, the lower left shows mutation operations, and the lower right shows an individual pairing task and mutation prompts. Updating the population includes both revising task instructions and revising the text specifying how to revise them.
PromptQuine searches by deleting tokens from existing instructions or demonstrations rather than writing more elaborate text. Candidates are subsequences that preserve the original order, and binary keep-or-delete masks serve as genomes. Individuals replicate, undergo deletion mutations, and survive according to task fitness. Since it does not exclude subsequences that look unnatural to humans, its reachable candidates differ from those of a search restricted to readable paraphrases (J. Wang et al. 2025, secs. 2–3).
Self-replication here does not mean that an LLM writes arbitrary self-modifying programs. PromptQuine centers on subsequence search under defined masks and selection rules. It also differs from changing Promptbreeder’s mutation prompts. Figure 9 separates replication and deletion of instructions or demonstrations from the resulting population changes over repeated steps. Its classification experiments also use output probabilities in the fitness function. Not using numerical gradients must not be equated with being able to run every experiment using output text alone.
Table 1 compares how these methods generate subsequent candidates and what they retain during search.
| Method | Main Information for the Next Candidate | Retained Search Information |
|---|---|---|
| APE | Instructions inferred from input–output examples, paraphrases of top candidates | Scored candidates |
| OPRO | Previous instructions and numerical scores | History of top instructions |
| ProTeGi / PromptAgent | Critiques of errors and revisions | Beam / search tree with visits and rewards |
| EvoPrompt | Crossover, mutation, and textual differences between parent instructions | Instruction population |
| Promptbreeder | Task prompts and mutation prompts | Population of individuals containing both |
| PromptQuine | Replication and token deletion from initial prompts | Population of subsequence masks |
Refining Instructions or Reselecting Demonstrations
Changing only instruction wording overlooks a major degree of freedom in prompts. A few input–output demonstrations in context communicate not only answer format but also solution procedures and task boundaries. Even with the same instruction, behavior changes with the examples and combinations shown.
Wan et al. compare instruction optimization with demonstration optimization and their combination. Demonstration candidates are not additional human-written reasoning data. They are correctly answered input–output pairs generated by the task model while solving the evaluation set, with intermediate reasoning included in the outputs. Beyond random selection, the methods use random search over combinations and mutations that replace one example (Wan et al. 2024, sec. 3.1).
In the following comparison, the task model is PaLM 2 text-bison-002 and the instruction-optimization model is text-unicorn-001. Each BIG-Bench Hard (BBH) task is split into 20% for evaluation and 80% for testing, with 3 demonstrations. Instruction-only and demonstration-only search each receive 32 candidate evaluations on the evaluation set. The combined setting spends a budget on each, so the last row is not a comparison with standalone search under the same total budget (Wan et al. 2024, Table 1).
| Instruction Search | Demonstration Search | Mean BBH Test Accuracy |
|---|---|---|
| None | None | 60.30% |
| ProTeGi | None | 68.13% |
| None | Random search | 71.16% |
| None | Mutation-based search | 72.92% |
| ProTeGi | Mutation-based search | 77.29% |
The important finding is that selecting demonstrations without changing the instruction outperformed instruction-only optimization. Changing both achieved a higher result still. This supports neither “instructions are unnecessary if examples are selected” nor “select the strongest instruction and then fix the examples.” In the paper’s Massive Multitask Language Understanding (MMLU) comparison, adding ProTeGi instructions to randomly searched demonstrations sometimes failed to improve performance. The interaction depends on the task (Wan et al. 2024, Table 3).
PromptWizard incorporates this interaction into its optimization procedure. It progressively combines generating diverse instruction candidates, critiquing their execution results, and consolidating instructions with demonstration selection and synthesis. It synthesizes missing examples from errors and aligns their reasoning and task intent with the instruction. This is not simply paraphrasing an entire prompt with fixed examples attached. The search still targets readable prompts, but improves their components in sequence (Agarwal et al. 2025, secs. 3.1–3.4).
Allocating Evaluation Budget Among Candidates
Adding a candidate need not require solving every evaluation problem. When the product of candidate count and evaluation-set size is large, scoring can cost more than generation. Eliminating clearly inferior candidates with a few problems and investigating differences among the survivors may yield a better final choice under the same budget.
TRIPLE formulates selection from a prepared candidate set as fixed-budget best-arm identification. An arm is a prompt, and pulling it means supplying one input and observing a reward. The aim is not to maximize cumulative scores during search but to return one good candidate when the budget is exhausted. The paper proposes TRIPLE-SH, which progressively halves the candidate set, TRIPLE-CR, which rejects candidates sequentially, and variants using embedding-based clustering or reward-function approximation (Shi et al. 2024, secs. 3–4).
Figure 12 shows why the relation between candidate count and budget matters for selection. The upper and lower groups also use different normalization baselines, so their bar heights should not be compared directly.
This distinction prioritizes selecting a candidate for future unseen inputs over producing many good answers on evaluation inputs during search. TRIPLE does not replace the generator itself. It can replace the selection component for candidates produced by APE or another generator.
HbBoPs predicts which unevaluated candidates to measure as well as how thoroughly to measure them. It embeds instructions and demonstrations separately and estimates evaluation error using a Gaussian process with a deep kernel that exploits their structure. It combines Bayesian optimization using these predictions with Hyperband, which promotes promising candidates from evaluations on small problem subsets. The former reduces the number of candidates tried, while the latter reduces the queries per candidate (Schneider et al. 2025, sec. 3).
HbBoPs uses continuous embeddings to predict performance, not to differentiate through the task model and rewrite instructions. Treating instruction–demonstration combinations as candidates also makes component reuse easier to represent than in a surrogate that compares entire prompts as indivisible text. It nevertheless depends on relative performance on small subsets approximating final performance and on the predictive structure being useful.
Figure 13 reports experiments on 10 tasks with Claude 3 Haiku, Llama 3 8B Instruct, and Mistral 7B Instruct. Each condition is repeated 30 times, measuring exact-match error. The total budget equals the queries needed to evaluate 25 candidates on the full validation set. The horizontal axis shows the fraction consumed. Errors are normalized using the minimum and maximum error within each condition and then averaged. Looking at test error on the right as well as validation error on the left distinguishes performance on search data from performance on unseen inputs.
MutantPrompt adds candidates during search instead of restricting itself to a fixed set. Thompson sampling updates beta distributions from success and failure counts to select candidates for small-batch evaluation. At the same time, it mutates currently strong instructions with a probability that decreases as search progresses. Targeting low-resource Indic languages and relatively small models, it balances exploring new candidates and reevaluating existing ones within a limited evaluation budget. Whereas TRIPLE centers on final selection from a fixed set, here the set itself grows (Nag et al. 2025, Algorithm 1).
Search Without Correct Labels or a Single Instruction
For text generation without a unique correct answer, even constructing an error set is difficult. SPO (Self-Supervised Prompt Optimization) asks an LLM to compare outputs from different instructions pairwise and select the output better aligned with task requirements. The optimizer revises the instruction using the better output as evidence. The key change is replacing comparisons against labeled answers with comparisons between outputs (Xiang et al. 2025, secs. 2–3).
This is not optimization without evaluation. It transfers the evaluation burden to an LLM’s relative judgments, so instructions may adapt to the evaluator’s preferred style or explanation length. Not using reference answers during search also does not eliminate the need to verify final quality against external criteria.
The requirement to use the same instruction for every input can also be relaxed. ToP (Tree-of-Prompts) constructs a tree with shared instructions at parent nodes and specialized cases at child nodes. Rather than clustering training examples only by their input text, it generates and clusters “solution prompts” for solving them. For example, in function-calling tasks, similarly worded questions may require different treatment when no available function can answer one of them. At inference time, search prompts describing when each instruction applies guide instruction selection (Kim et al. 2025, sec. 3).
PromptAgent’s tree represents revision paths during optimization, whereas ToP’s tree also determines which instruction an input receives. Comparisons with improving one static instruction must therefore account for the changed inference-time selection process.
Other methods do not reduce “best” to a single score. Pareto Prompt Optimization uses dominance: one candidate is at least as good on every objective and better on at least one. For style transfer with both stylistic fit and content preservation, for example, incomparable candidates need not be forced into one ranking. ParetoPrompt constructs a preference loss from input-dependent dominance between candidate pairs and updates the prompt-generation policy’s parameters. This differs from fixing a weighted sum of objectives in advance (G. Zhao et al. 2025, sec. 3).
Figure 17 routes updates back to the instruction-generating policy rather than the task model, making the learned component explicit.
This is not black-box search that merely asks a fixed LLM to edit text. The updated component is the instruction-generating policy, not the task model. Learned Optimizers examines this boundary through RLPrompt and MePO.
The Boundary with Numerical-Gradient Prompt Updates
Methods calling textual critiques “gradients” differ from methods that actually differentiate a loss, both in required access and in what an update means. Even the latter may produce discrete instructions, so discrete prompts do not necessarily imply gradient-free optimization.
GReaTer generates a reasoning process under the current instruction, extracts a final answer, and computes cross-entropy loss against the correct answer. Here, cross-entropy aggregates the negative log probabilities assigned to correct answer tokens, increasing when the model assigns them low probability. Using gradients of that loss with respect to instruction tokens, it chooses updates from candidate tokens filtered by the model’s own generation probabilities. Unlike natural-language error critiques, it obtains a numerical signal from final answers even on reasoning tasks. The loss is conditioned on already generated reasoning. This does not mean exactly differentiating through the entire discrete reasoning-generation process (Das et al. 2025, sec. 4).
Figure 18 traces the numerical signal from answer loss conditioned on generated reasoning back to instruction tokens.
GMPO (Gradient-guided Multi-judge Prompt Optimization) uses a first-order approximation of the loss change from moving instruction spans toward mask embeddings to identify important spans from gradients. It asks a generator to revise those spans and selects candidates by aggregating cross-entropy losses across multiple lightweight evaluator models. The generator may be a closed API, but importance estimation requires backpropagation through evaluator models. Its aim of restricting the edit region resembles LPO’s, but the signal selecting the location differs (C. Zhao et al. 2026, sec. 3).
SGCG represents discrete-token selection distributions and sampling continuously, combining gradient updates with greedy candidate selection. The forward pass makes discrete choices, while the backward pass uses surrogate gradients. A surrogate gradient approximates an otherwise nondifferentiable discrete choice with a differentiable continuous representation during backpropagation. It is not an exact derivative of the discrete operation itself. A moving window of recent losses also determines whether to accept updates. The experiments address classification and text attacks, differing in both representation and tasks from search in which an LLM writes readable critiques and revises instructions (Y. Wang et al. 2025, sec. 3).
These three methods require internal access to models that provide numerical gradients. They nevertheless update instruction tokens or their search representations rather than fine-tuning model weights. In programs containing multiple model calls, one must also choose demonstrations and account for interactions between stages. Multi-Module Optimization covers this extension through DSPy, MIPRO, and GEPA.
Prompt-search methods differ in more than their ability to generate fluent revisions. Candidate scope, error-derived signals, demonstration combinations, and evaluation-budget allocation all affect the selected instruction. The open question is which mechanisms most reliably improve performance on unseen problems when compared under the same task model and total budget.
Figure Credits
Figure 2: (Pryzant et al. 2023). Original figure: published version, Figure 2. CC BY 4.0. Original figure cropped and rasterized.
Figure 3: (Ye et al. 2024). Original figure: published version, Figure 3. CC BY 4.0. Original figure cropped and rasterized.
Figure 2: (Jain and Chowdhary 2025). Original figure: published version, Figure 2. CC BY 4.0. Original figure cropped and rasterized.
Figure 1: (Fernando et al. 2024). Original figure: published version, Figure 1. CC BY 4.0. Figure region cropped from the original.
Figure 2: (J. Wang et al. 2025). Original figure: published version, Figure 2. CC BY 4.0. Figure region cropped from the original.
Figure 3: (Wan et al. 2024). Original figure: published version, Figure 3. CC BY 4.0. Original figure cropped and rasterized.
Figure 4: (Agarwal et al. 2025). Original figure: published version, Figure 4. CC BY 4.0. Original figure cropped and rasterized.
Figure 1: (Schneider et al. 2025). Original figure: published version, Figure 1. CC BY 4.0. Figure region cropped from the original.
Figure 1: (Nag et al. 2025). Original figure: published version, Figure 1. CC BY 4.0. Original figure cropped and rasterized.
Figure 4: (Xiang et al. 2025). Original figure: published version, Figure 4. CC BY 4.0. Original figure cropped and rasterized.
Figure 2: (Kim et al. 2025). Original figure: published version, Figure 2. CC BY 4.0. Original figure cropped and rasterized.
Figure 2: (C. Zhao et al. 2026). Original figure: published version, Figure 2. CC BY 4.0. Original figure cropped and rasterized.
Figure 1: (Y. Wang et al. 2025). Original figure: published version, Figure 1. CC BY 4.0. Original figure cropped and rasterized.
Figure 3: (Yang et al. 2024). Source: paper PDF, Figure 3. Original figure region cropped and rasterized to PNG.
Figure 1: (Zhou et al. 2023). Source: paper PDF, Figure 1. Original figure region cropped and rasterized to PNG.
Figure 3: (X. Wang et al. 2024). Source: paper PDF, Figure 3. Original figure region cropped and rasterized to PNG.
Figure 2: (Guo et al. 2024). Source: paper PDF, Figure 2. Original figure region cropped and rasterized to PNG.
Figure 3: (Shi et al. 2024). Source: paper PDF, Figure 3. Original figure region cropped and rasterized to PNG.
Figure 1: (G. Zhao et al. 2025). Source: paper PDF, Figure 1. Original figure region cropped and rasterized to PNG.
Figure 2: (Das et al. 2025). Source: paper PDF, Figure 2. Original figure region cropped and rasterized to PNG.