--- kind: concept slug: prompt-optimization title: Prompt optimization (LLM as black-box optimizer) summary: >- Searching for a better prompt by scoring candidates on labelled data. OPRO uses a language model as the proposer and feeds the scored history back; its best GSM8K instruction scores 80.2 vs 71.8 for "Let's think step by step." (test, author-reported). A 2023 survey maps other methods (textual gradients, rewriters, tree search, RL) but runs no experiments of its own. tags: [prompting, optimization, black-box-optimization, meta-prompting, inference, evaluation] papers: ["2309.03409", "2310.14735"] related: [prompt-engineering, chain-of-thought-prompting, in-context-learning, self-refinement, self-consistency, bayesian-optimization, llm-evaluation, soft-prompt-tuning] status: draft updated_at: 2026-10-31 --- ## Overview Prompt optimization is a search over the text a model is conditioned on, where each candidate is judged by a score and the search runs for several rounds. Two cards cover it. OPRO is the full method and the source of every number on this page [arxiv:2309.03409 §2]. It uses a language model as the proposal step: the model sees the task, the candidates tried so far with their scores, and writes new candidates that should score higher. Each new candidate is evaluated on the labelled task, and its score is added to the history for the next round [arxiv:2309.03409 §2]. The survey covers the same problem as one section among many. It lists several automatic prompt optimizers and describes each in a sentence or two, without results of its own [arxiv:2310.14735 §3.10]. Treat those entries as pointers to the original papers, not as evidence about them. The invariant the instruction-search variants keep is that the model is a black box: only its outputs and the scores are used, and no gradients flow back [arxiv:2309.03409 §1]. The survey's textual-gradient method uses written critiques as its update signal [arxiv:2310.14735 §3.10.1]. The survey does not say how that compares with OPRO's score-only feedback. ## Variants ### Instruction search (OPRO for prompts) The optimizer writes an instruction. The instruction is placed before the question, after it, or before the scorer's answer [arxiv:2309.03409 §4.1] [arxiv:2309.03409 app. B]. The score is the scorer's accuracy at temperature 0 on one fixed subset of training questions, reused at every step [arxiv:2309.03409 §5.1]. The default run is 200 steps, with 8 candidates per step and 3 random training examples shown each time [arxiv:2309.03409 §5.1] [arxiv:2309.03409 §4.2]. Card: [Large Language Models as Optimizers](/papers/2309.03409). On GSM8K, with a PaLM 2-L scorer and instructions placed before the answer, the best instruction found by a PaLM 2-L-IT optimizer scored 80.2 on the test set. "Let's think step by step." scored 71.8 under the same scorer [arxiv:2309.03409 tab. 4]. The paper reports the headline gap as "up to 8%" over human-designed prompts on GSM8K [arxiv:2309.03409 §1]. The GSM8K instructions were also scored on MultiArith and AQuA. For both scorers, the ones found on GSM8K were the highest in the table on both sets, with the single-set results reported as-is [arxiv:2309.03409 tab. 6]. On BBH, with the PaLM 2-L-IT optimizer and the PaLM 2-L scorer, the found instructions beat "Let's think step by step." by more than 5 points on 19 of 23 tasks. With text-bison as the scorer, they did so on 15 of 23 tasks [arxiv:2309.03409 §5.2.2] [arxiv:2309.03409 app. E]. ### Solution search for small numeric and combinatorial problems Here the candidate is a solution, not a prompt. For linear regression, the candidate is a pair (w, b) and the score is the objective value. The analytic formula is kept out of the prompt, so the search stays black-box [arxiv:2309.03409 §3.1]. The table reports the steps taken to reach the global optimum for seven (w_true, b_true) cases, for each of three optimizers [arxiv:2309.03409 tab. 2]. For the travelling salesman problem, the candidate is a route, and it is kept only if it visits every node once and starts at node 0 [arxiv:2309.03409 §3.2]. At 10 nodes, all three optimizers reached a gap of 0.0% [arxiv:2309.03409 tab. 3]. At 50 nodes, the best LLM gap was 11.0% (gpt-4), while the farthest-insertion heuristic (FI) reached 9.8% [arxiv:2309.03409 tab. 3]. This variant is a test of the optimizer, not a recipe for routing in production. ### One-shot generation (baseline, not an optimizer) Generating many candidates once and keeping the best one is the simplest alternative. On GSM8K, the best of 50 one-step candidates was "Let's solve the problem." (train 64.4, test 60.8). The iterative run found "Let's do the math!" (train 78.2, test 76.3) [arxiv:2309.03409 §5.3]. The comparison is one ablation with one scorer, so treat it as a direction, not a size. ### Survey-listed methods (no results here) The survey names these optimizers in its prompt-optimization section [arxiv:2310.14735 §3.10]. Each entry below is the survey's own one-line description. None has been checked against its original paper on this page. - **Textual gradients with beam search (ProTeGi).** Critiques written by the model are used to edit the prompt, with beam search and bandit selection among candidates [arxiv:2310.14735 §3.10.1]. The survey reports gains of up to 31% over the initial prompt on sentiment, fake-news and jailbreak detection, citing the original work [arxiv:2310.14735 §3.10.1] (results table of the survey, author-reported in the cited work). - **Black-box rewriter.** A trained model rewrites the prompt [arxiv:2310.14735 §3.10.2]. - **Model-adaptive optimization.** A warm-up set, then supervised fine-tuning and reinforcement learning of the optimizer [arxiv:2310.14735 §3.10.3]. - **Monte Carlo tree search (PromptAgent).** The search is a tree over prompt edits [arxiv:2310.14735 §3.10.4]. - **Reinforcement-learning prompt search.** A learned policy proposes prompts [arxiv:2310.14735 §3.10.5]. - **GPT-store prompt helpers.** Prompt-writing helpers from a model marketplace [arxiv:2310.14735 §3.10.6]. The survey gives no cost, budget or head-to-head comparison for these, so this page cannot rank them against OPRO. Card: [Unleashing the potential of prompt engineering for large language models](/papers/2310.14735). ## When to use which | Situation | Use | Why | |---|---|---| | You can call the model but cannot read its gradients | Instruction search (OPRO) | The method needs only the scored outputs [arxiv:2309.03409 §1] | | You have a labelled set of a few hundred items for the task | Instruction search (OPRO) | The paper used about 3.5% of GSM8K's training set and 20% of each BBH task [arxiv:2309.03409 §5.1] [§5.2.2] | | No labelled data, or the score is hard to compute automatically | One-shot generation, or a hand-written prompt | The method assumes a labelled training set whose accuracy is the objective [arxiv:2309.03409 §5.1] | | Budget is tight | Fewer steps, or a smaller candidate count | Each step scores up to 8 candidates on the full training subset. For GSM8K that is up to about 418,000 scorer calls at 200 steps (derived from [arxiv:2309.03409 §5.1]) | | The prompt will run on a different task or model | Re-check the score | Transfer across tasks was mixed [arxiv:2309.03409 tab. 6], and wording sensitivity is large [arxiv:2309.03409 §5.2.3] | | The problem is small and has a known optimum | Solution search | The paper's optimizers reached optima on small cases [arxiv:2309.03409 tab. 2] [tab. 3] | | The problem is large, such as 50-node routing | A classical heuristic | At 50 nodes, the paper's LLM gaps were above the heuristic's [arxiv:2309.03409 tab. 3] | | You want the optimizer to act on error feedback, not only on scores | Textual-gradient search (ProTeGi) | The survey describes critique-based editing [arxiv:2310.14735 §3.10.1]. It gives no cost comparison | | You can afford to train a rewriter or a policy | Rewriter or RL search | The survey lists both [arxiv:2310.14735 §3.10.2] [§3.10.5]. It reports no numbers that compare them | Sensitivity to the search settings is also reported. Optimizer temperature 1.0 gave the best curves, lower values stalled, and higher values ignored the history [arxiv:2309.03409 §5.3]. Eight candidates per step beat one, two, four and sixteen in the paper's ablation [arxiv:2309.03409 §5.3]. ## Implementation sketch Only the OPRO loop is sketched. The survey does not give enough steps for the other variants to write a sketch without inventing details. The loop below is the common core of OPRO-style search. Variants differ in the candidate format, the meta-prompt layout and the score function. ```pseudocode # Black-box prompt search, OPRO style [arxiv:2309.03409 §2] [§5.1] def optimize_prompt(optimizer, scorer, train, seeds, steps=200): # Score the starting instructions once [§5.2] history = [(p, accuracy(scorer, p, train)) for p in seeds] for step in range(steps): # Show only the best instructions, lowest score first [§4.2] top = sorted(history, key=score_of)[-20:] # Three random examples per step, to show the task [§4.2] shots = sample(train, 3, seed=step) meta = build_meta_prompt(top, shots) # Eight candidates at temperature 1.0 [§2.3] [§5.3] for _ in range(8): candidate = parse(optimizer(meta, temperature=1.0)) if candidate and candidate not in seen(history): history.append((candidate, accuracy(scorer, candidate, train))) # Choose by training accuracy, not test accuracy [§5.4] return max(history, key=score_of) ``` Notes on the sketch: - The score uses greedy decoding from the scorer [arxiv:2309.03409 §5.1]. - Parsing matters. Tag-delimited output is parsed for one model family, and for the text-bison family the first bracketed span is taken, or an empty string if there is none [arxiv:2309.03409 app. C.2] [code: opro/optimization/opt_utils.py#L33-L38]. Filter empty candidates before scoring. The released code also drops candidates over 500 characters and candidates containing a fixed substring, and it dedupes against earlier candidates [code: opro/optimization/opt_utils.py#L785-L822]. The paper does not describe these filters. - The paper's stopping rule is "no better candidate or a step limit" [arxiv:2309.03409 §2]. The released code runs only to the step limit [code: opro/optimization/opt_utils.py#L568]. Use the step limit. ## Contradictions No numerical disagreement between the two cards. The survey's §3.10 list does not include OPRO, so the survey makes no claim about its results. Within the sources: - **"Up to 50%" on BBH.** The abstract's headline is "up to 50%" [arxiv:2309.03409 abstract]. Reading the test column of the per-task table, the largest gap over the best human-designed baseline is 45 points, on word_sorting (derived from [arxiv:2309.03409 app. E]). The largest gap over the empty starting string is 52 points, but that string is not a human-designed prompt. - **Step number of one finding.** "Let's do the math!" is placed at step 6 in one section [arxiv:2309.03409 §5.2.1] and at "the 5th step" in another [arxiv:2309.03409 §5.3]. Check the indexing before comparing curves. - **Selection in the headline table.** The GSM8K table reports the instruction with the highest test accuracy per optimizer and scorer [arxiv:2309.03409 tab. 4]. The paper suggests picking by training accuracy for a deployed prompt [arxiv:2309.03409 §5.4]. The table's figures are therefore selected on test and read higher than a deployed prompt would score. - **Survey figures are second-hand.** The survey says its numbers come from cited work and should be checked against it [arxiv:2310.14735 TL;DR]. The ProTeGi gain above is one such number and is not verified here. ## Papers - [Large Language Models as Optimizers](/papers/2309.03409): introduces OPRO, which uses an LLM as the proposal step of a black-box search; reports instruction search on GSM8K and BBH, and small linear-regression and TSP tests. - [Unleashing the potential of prompt engineering for large language models](/papers/2310.14735): a survey whose prompt-optimization section names ProTeGi, a black-box rewriter, model-adaptive, PromptAgent, RL-based and GPT-store methods; presents no new experiments.