Prompt optimization (LLM as black-box optimizer)

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 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 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 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 2309.03409 §1. The survey's textual-gradient method uses written critiques as its update signal 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 2309.03409 §4.1 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 2309.03409 §5.1. The default run is 200 steps, with 8 candidates per step and 3 random training examples shown each time 2309.03409 §5.1 2309.03409 §4.2. Card: Large Language Models as Optimizers.

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 2309.03409 tab. 4. The paper reports the headline gap as "up to 8%" over human-designed prompts on GSM8K 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 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 2309.03409 §5.2.2 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 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 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 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% 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) 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 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 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 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 2310.14735 §3.10.2.
• Model-adaptive optimization. A warm-up set, then supervised fine-tuning and reinforcement learning of the optimizer 2310.14735 §3.10.3.
• Monte Carlo tree search (PromptAgent). The search is a tree over prompt edits 2310.14735 §3.10.4.
• Reinforcement-learning prompt search. A learned policy proposes prompts 2310.14735 §3.10.5.
• GPT-store prompt helpers. Prompt-writing helpers from a model marketplace 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.

When to use which

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 2309.03409 §5.3. Eight candidates per step beat one, two, four and sixteen in the paper's ablation 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.

# 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 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 2309.03409 app. C.2 opt_utils.py. 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 opt_utils.py. The paper does not describe these filters.
• The paper's stopping rule is "no better candidate or a step limit" 2309.03409 §2. The released code runs only to the step limit opt_utils.py. 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%" 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 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 2309.03409 §5.2.1 and at "the 5th step" in another 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 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 2310.14735 TL;DR. The ProTeGi gain above is one such number and is not verified here.

Papers

• Large Language Models as Optimizers: 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: 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.