Large Language Models as Optimizers

In plain words

Most optimizers are a piece of code with a formula for the next step, such as a gradient. OPRO replaces that formula with a language model. You describe the goal in plain words, list the attempts made so far with their scores (sorted, best last), and ask the model for new attempts that should score higher. Each new attempt is then actually tested, and its score goes back into the list for the next round.

The paper uses this on two kinds of problem: small numeric tasks with a known answer, and the wording of an instruction given to a language model. For instructions, the score is how often the model answers training questions correctly when it sees that instruction. The authors report that the best instructions found this way beat hand-written ones on math word problems and reasoning tasks. No gradients are needed, only a way to score each attempt.

TL;DR

• OPRO (Optimization by PROmpting) uses an LLM as the optimizer for black-box problems. The task is described in natural language, and the model proposes new candidates from a meta-prompt that holds earlier candidates and scores §2.
• Each candidate is scored by running it, and the result is added to the meta-prompt for the next step §2.
• On linear regression and small TSP instances, the optimizer LLMs reach the optimum on some problems and fail more often as problems grow §3.
• For prompt optimization, the author-reported best instructions beat human-designed prompts by up to 8% on GSM8K and up to 50% on BBH (abstract). See Pitfalls for what the tables do and do not support.

Problem

• Many problems offer no gradient. Derivative-free methods usually need an algorithm customized for each task §1.
• For prompts, the search space is large and discrete. When the model is only reachable through an API, gradient-based prompt tuning does not apply §1.
• Accuracy is sensitive to small wording changes. On GSM8K test, with the same scorer, "Let's think step by step." reaches 71.8 and "Let's work together to solve this problem step by step." reaches 49.4 §5.2.3.
• The method assumes a labelled training set. Its accuracy is the objective, and a small subset is enough: 3.5% of the GSM8K training set and 20% of each BBH task §4.1 §5.1.

Method

Loop §2 fig. 2. In each step, the optimizer LLM reads a meta-prompt and writes candidate solutions. The candidates are scored, then appended to the meta-prompt for the next step. The paper says the loop stops when the LLM can no longer propose better candidates, or when a maximum step count is reached §2. The released code only uses the step count (see Paper vs code).

Meta-prompt contents §2.2 §4.2 fig. 3.

• Problem description. Natural-language objective and constraints. For prompt optimization this is a meta-instruction such as "generate a new instruction that achieves a higher accuracy". Extra meta-instructions can add informal constraints, such as conciseness §2.2.
• Optimization trajectory. Past solutions and their scores, sorted in ascending order so the best come last. Only the highest-scoring ones are kept, because of the context-length limit §4.2.
• Exemplars (prompt optimization only). Three training input-output pairs, drawn at random each step. They show the task and where the instruction goes §4.2 §5.3.
• Output format. Instructions on how to use the trajectory and how to format the answer, so it can be parsed §4.2.

Candidate generation §2.3 §5.1 §5.3.

• Eight candidates per step, to reduce the variance from one bad trajectory §2.3.
• Optimizer temperature 1.0 by default. Lower values stay near known solutions and stall. Higher values ignore the trajectory §5.3.

Prompt optimization §4.1 §5.1.

• The optimizer writes an instruction, which is inserted in one of three positions: Q_begin, Q_end, or A_begin (text placed before the scorer's answer) §4.1 app. B. A_begin is used with the pre-trained PaLM 2-L scorer; Q_begin and Q_end are used with the instruction-tuned text-bison scorer §5.1.
• Score = accuracy of the scorer, at temperature 0, on one fixed training subset, reused at every step §5.1.
• The search runs for 200 steps by default §5.1. The reported test accuracy is measured once, on the held-out test set, after the search finishes §5.1.

# OPRO loop for prompt optimization  [§2] [§4.1] [§5.1]
# Scores are training accuracy on one fixed subset  [§5.1]
# Code: opro/optimization/opt_utils.py#L568-L1034

def opro_prompt_optimization(
    optimizer, scorer, train_examples, starting_instructions
):
    # Score each starting instruction once  [§5.2] [code: opt_utils.py#L520]
    trajectory = []
    for instruction in starting_instructions:
        accuracy = training_accuracy(scorer, instruction, train_examples)
        trajectory.append((instruction, accuracy))
    # Default run length is 200 steps  [§5.1]
    # [code: optimize_instructions.py#L708]
    for step in range(200):
        # Keep the 20 best instructions so far, lowest score first
        # [§4.2] [§5.1]
        best_so_far = sorted(trajectory, key=accuracy_of)[-20:]
        # Sample 3 training exemplars; the seed is the step index  [§4.2]
        # [code: opt_utils.py#L681-L688]
        exemplars = random_sample(train_examples, 3, seed=step)
        meta_prompt = build_meta_prompt(best_so_far, exemplars)
        # Ask for 8 candidates at temperature 1.0  [§2.3] [§5.1]
        candidates = []
        for _ in range(8):
            reply = optimizer(meta_prompt, temperature=1.0)
            candidates.append(extract_instruction(reply))
        # Drop duplicates and unusable candidates before scoring
        # [code: opt_utils.py#L785-L822]
        for candidate in admissible_unique(candidates):
            accuracy = training_accuracy(scorer, candidate, train_examples)
            trajectory.append((candidate, accuracy))
    # Final choice by training accuracy, not test (see Pitfalls)  [§5.4]
    return max(trajectory, key=accuracy_of)

# Meta-prompt layout for prompt optimization  [§4.2] [fig. 3] [app. C.2]
# Order: old instructions, then exemplars, then the meta-instruction
# Code: opro/optimization/opt_utils.py#L162-L295

def build_meta_prompt(best_so_far, exemplars):
    # Header describing the list and its ascending sort  [§4.2] [app. C.2]
    parts = [list_description_text()]
    for instruction, accuracy in best_so_far:
        # Accuracy is shown as an integer 0 to 100  [§5.3]
        # [code: opt_utils.py#L47-L49] [code: opt_utils.py#L74-L80]
        score_bucket = round(accuracy * 100)
        parts.append(f"text:\n{instruction}\nscore:\n{score_bucket}")
    # One input-output pair per exemplar, with the instruction slot  [app. B]
    for example in exemplars:
        parts.append(format_exemplar(example))
    # Ask for a new text that differs from the old ones and scores higher
    # [§4.2]
    parts.append(meta_instruction_text())
    return "\n\n".join(parts)

# Parse the optimizer reply  [code: opt_utils.py#L740-L768]

def extract_instruction(reply, optimizer_family):
    # GPT models: text between the start and end tags  [app. C.2]
    # A missing end tag means the rest of the reply is used
    # [code: opt_utils.py#L752-L762]
    if optimizer_family == "gpt":
        return text_between_tags(reply, "<Start>", "</Start>")
    # text-bison: the first text in square brackets, or "" if none
    # [code: opt_utils.py#L33-L38]
    return first_bracketed_text(reply)

Linear regression uses the same loop without exemplars, with the (w, b) pair as the solution and the objective value shown to the model. The analytic form is kept out of the prompt, so the search is black-box §3.1. The TSP variant asks for a route as a list of node indices in tags, and it keeps the candidate only if it visits every node once and starts at node 0 §3.2 optimize_tsp.py.

Hyperparameters

Results

Author-reported throughout. The optimizer and scorer are API models. Hardware is not stated.

Prompt optimization, GSM8K tab. 4. Setup: PaLM 2-L scorer, A_begin, test accuracy on the full test set. The table keeps the best test-accuracy instruction per scorer and optimizer pair (see Pitfalls).

The 80.2 instruction was found at step 107 with a training accuracy of 80.2 §5.2.1. The paper's stated headline is "up to 8%" over human-designed prompts on GSM8K §1. Against "Let's think step by step." (71.8), 80.2 is 8.4 points (derived).

Transfer of GSM8K instructions tab. 6. Same instructions, evaluated on two other math sets. Scores are MultiArith / AQuA.

Prompt optimization, BBH §5.2.2 app. E. With the PaLM 2-L-IT optimizer, the found instructions beat "Let's think step by step." by more than 5 points on 19 of 23 tasks with the PaLM 2-L scorer, and on 15 of 23 with text-bison. They beat the empty start by more than 5 points on 20 of 23 (PaLM 2-L) and 15 of 23 (text-bison). Per-task numbers, including training accuracy, are in app. E. The abstract's "up to 50%" is discussed in Pitfalls.

Linear regression tab. 2. Mean ± standard deviation over 5 runs. Bold marks the best of the three optimizers in each row. The model must reach the global optimum. Steps and unique (w, b) pairs explored are reported.

TSP tab. 3. Five instances per size. Gap = (LLM tour − oracle tour) / oracle tour, in %. The paper computes the oracle with Gurobi. Steps are for successful runs; the number in brackets is how many of the 5 instances reached the optimum. N/A means none did.

Ablations §5.3 (text-bison scorer, PaLM 2-L-IT optimizer, GSM8K and BBH sports_understanding). Sorting ascending beat descending and random. Showing scores beat hiding them. Three exemplars beat none, and ten did not help. Eight candidates per step beat 1, 2, 4 and 16. Temperature 1.0 was best. Starting from a weaker instruction converges more slowly §5.3.

Comparison with one-step generation §5.3. 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).

Overfitting §5.4 fig. 11. Training accuracies of found instructions were often 5 to 20 points above test accuracy. Validation accuracy moved with training accuracy, so the highest-training instruction was still a good pick.

EvoPrompt §5.5 fig. 12. Reported only as plots. OPRO improved steadily on GSM8K with generic starts. Both EvoPrompt variants degraded there. With task-specific starts on BBH sports_understanding, EvoPrompt (DE) improved, but its curve was less stable.

Paper vs code

Code paths are relative to the repository at code_commit.

• Stopping rule. The paper stops when no better candidate appears or a step limit is reached §2. The code loops over a fixed num_search_steps with no break opt_utils.py. Only the step limit applies.
• BBH starting point. The paper starts BBH from the empty string §5.2.2. The code default is initial_instructions = ["Let's solve the problem."]; the empty string is commented out optimize_instructions.py.
• Oracle for TSP. The paper uses the Gurobi solver for oracle tours §3.2. The repository has no Gurobi reference. The oracle is an exact search written in the repo optimize_tsp.py.
• include_qa with A_begin. Both scorer branches set include_qa = False optimize_instructions.py optimize_instructions.py. gen_prompt builds an A_begin prompt only when include_qa is True; otherwise it asserts the position is Q_begin or Q_end eval_utils.py eval_utils.py. The default position is A_begin optimize_instructions.py. Reading the code, the default command should fail the assertion. I did not run it: it needs API keys and the Google and OpenAI clients.
• Filters in code, not in the paper. The code drops candidates over 500 characters, drops GSM8K candidates that contain any digit, drops any candidate containing the substring "INS", and dedupes against every earlier candidate by MD5 hash opt_utils.py. It also capitalizes the first letter and strips ** eval_utils.py.
• Display threshold. For GPT scorers, instructions scoring below 0.3 are hidden from the meta-prompt. The top-20 cut happens first, then the threshold filters what is shown. Hidden instructions stay in the stored trajectory opt_utils.py optimize_instructions.py. The paper does not mention this.
• TSP and linear-regression settings. The TSP script keeps 10 pairs in the meta-prompt optimize_tsp.py and defaults to n = 100 optimize_tsp.py. The paper does not state either. The linear-regression script caps runs at 500 steps optimize_linear_regression.py.
• Agreement. The code matches the paper on: optimizer temperature 1.0 and scorer temperature 0.0 optimize_instructions.py optimize_instructions.py; 8 candidates per step optimize_instructions.py; 3 exemplars optimize_instructions.py; top 20 instructions optimize_instructions.py; 100 score buckets optimize_instructions.py; 3.5% and 20% training subsets optimize_instructions.py optimize_instructions.py; the 3-step evaluation interval optimize_instructions.py. No discrepancy in these.

Pitfalls

• Test-set selection in the headline table. The GSM8K table caption says it shows "the instruction with the highest test accuracy" per pair tab. 4. That picks the best of many candidates on the test set, which inflates the number. For a deployed prompt, pick by training accuracy, as the paper suggests §5.4.
• The "up to 50%" claim on BBH. The abstract says "up to 50%". I read the test column of app. E for the PaLM 2-L-IT optimizer with the PaLM 2-L scorer (derived). The largest gap over the better human-designed baseline is word_sorting, 54.5 vs 9.5, which is 45.0 points. The largest gap over the empty string is multistep_arithmetic_two, 55.5 vs 3.5, which is 52 points, but the empty string is not a human-designed prompt. The same table shows OPRO below the baseline on tracking_shuffled_objects_seven_objects (16.5 vs 61.5).
• Inconsistent step number. The paper says "Let's do the math!" was found at Step 6 §5.2.1, and at "the 5th step" in the one-step comparison §5.3. Check the 0- or 1-based indexing in the source before comparing curves.
• Output parsing is fragile. For GPT models, if the end tag is missing the code keeps the whole reply, prose included opt_utils.py. For text-bison, it takes the first bracketed text, or an empty string if there is none opt_utils.py opt_utils.py. Nothing in the visible loop removes an empty candidate before it is scored opt_utils.py.
• Answer scoring depends on a rule-based parser. GSM8K answers are parsed by a rule-based normaliser that looks for answer-marker phrases and keeps the text after them metrics.py. The paper does not describe this parser. Reimplementing it differently changes the scores.
• Training accuracy overstates test accuracy. The objective uses about 261 GSM8K questions (derived) and reuses them at every step. The exemplars come from that same subset opt_utils.py, so the optimizer has seen those questions. Expect a 5 to 20 point gap §5.4.
• Cost scales with the search. Each step adds 8 candidates, and each candidate is scored on the full training subset opt_utils.py. At 200 steps and 261 questions, that is up to 200 × 8 × 261 ≈ 418,000 scorer calls for GSM8K (derived, before dedupe). Scorer calls are the main cost.
• Sensitivity to wording. Synonym-level changes move accuracy a lot. In the paper, "Let's think step by step." reaches 71.8 and "Let's solve the problem together." reaches 60.5 §5.2.3. Generate several candidates per step; one candidate is not reliable.
• Context length. Linear regression and TSP prompts get hard to fit as problems grow, and bumpy objectives trap the search at local optima §3.2 app. A. The TSP optimality gap grows fast with n, and at n = 50 the paper's own optimizer does worse than the farthest-insertion heuristic §3.2 tab. 3.
• Hallucinated arithmetic. On linear regression the model sometimes claims a function value it did not compute, and sometimes repeats a solution that is already in the prompt app. A.
• Model snapshots. The results depend on the GPT snapshots named in the Reproducibility Statement and on the PaLM 2 text-bison API. Those endpoints change or retire, so re-run before comparing numbers.

Lineage

• Compared against and positioned against: APE (Zhou et al., arXiv:2211.01910), which proposes initial instructions and then paraphrases the top ones; APO (Pryzant et al., arXiv:2305.03495), which edits an instruction using LLM-written feedback; EvoPrompt (Guo et al., arXiv:2309.08532), which uses crossover and mutation prompts §6 §5.5.
• Baselines: "Let's think step by step." from zero-shot chain-of-thought (Kojima et al.) §5.2.1 tab. 4.
• Related approaches the paper cites: soft and discrete prompt tuning §6.