PaperlayerView exact revision on arXiv

Source-linked AI summary

Large Language Models as Optimizers

Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V. Le, Denny Zhou, Xinyun Chen

arXiv:2309.03409v3cs.LGcs.AIcs.CL

TL;DR

OPRO addresses the challenge of optimizing without gradients by using LLMs to iteratively generate solutions from natural-language descriptions and prior evaluated solutions. Applied to prompt optimization, OPRO-produced prompts outperform human-designed prompts on GSM8K and Big-Bench Hard, sometimes by over 50%.

  • Problem

    Prompt optimization is difficult because the large, discrete prompt space and sensitivity to subtle instruction changes make high-performing prompts challenging to find.

  • Method

    OPRO describes optimization tasks in natural language and iteratively has an LLM generate new solutions using previously generated solutions and their objective values.

  • Results

    OPRO-optimized prompts outperform human-designed prompts on GSM8K and Big-Bench Hard, with gains sometimes exceeding 50%.

  • Takeaways & Limitations

    LLMs can progressively improve solutions from past optimization trajectories and optimize different objective functions through prompting.

  • Takeaways & Limitations

    OPRO is not designed to outperform state-of-the-art gradient-based methods or specialized solvers, and context-window limits constrain large-scale optimization problem descriptions.

Abstract

from arXiv · show

Optimization is ubiquitous. While derivative-based algorithms have been powerful tools for various problems, the absence of gradient imposes challenges on many real-world applications. In this work, we propose Optimization by PROmpting (OPRO), a simple and effective approach to leverage large language models (LLMs) as optimizers, where the optimization task is described in natural language. In each optimization step, the LLM generates new solutions from the prompt that contains previously generated solutions with their values, then the new solutions are evaluated and added to the prompt for the next optimization step. We first showcase OPRO on linear regression and traveling salesman problems, then move on to our main application in prompt optimization, where the goal is to find instructions that maximize the task accuracy. With a variety of LLMs, we demonstrate that the best prompts optimized by OPRO outperform human-designed prompts by up to 8% on GSM8K, and by up to 50% on Big-Bench Hard tasks. Code at https://github.com/google-deepmind/opro.

1 INTRODUCTION

OPRO uses LLMs as optimizers by describing optimization tasks in natural language and iteratively generating solutions from prior evaluated solutions. It is demonstrated on classical optimization problems and prompt optimization, where optimized instructions improve benchmark performance.

  • Motivation and approach: OPRO describes an optimization problem in natural language and instructs an LLM to iteratively generate new solutions from previously found solutions.Changing the problem description or adding instructions customizes the optimization process for different tasks.
  • Optimization case studies: LLMs find good-quality solutions on small-scale linear regression and traveling salesman problems, sometimes matching or surpassing hand-designed heuristics.These case studies demonstrate LLM-based optimization on classic problems.
  • Prompt optimization: Prompt optimization targets instructions that maximize task accuracy, but large discrete prompt spaces and sensitivity to prompt format make this challenging.Semantically similar prompts can have drastically different performance, and optimal formats may depend on the model and task.
  • Prompt optimization: The meta-prompt combines prior prompts with training accuracies, a natural-language task description, and randomly selected task exemplars.OPRO generates new prompts from the full optimization trajectory rather than editing one prompt from natural-language feedback.
  • Results: 8% is the maximum GSM8K improvement over human-designed zero-shot prompts reported for OPRO-optimized instructions.With zero-shot prompting, the best generated instructions also match few-shot chain-of-thought performance when applied to PaLM 2-L.

2 OPRO: LLM AS THE OPTIMIZER

OPRO uses a meta-prompt to generate, evaluate, and iteratively refine solutions, combining task descriptions with an optimization trajectory. Its design addresses how LLMs interpret task constraints, exploit prior high-scoring solutions, maintain stability, and balance exploration with exploitation.

  • Optimization procedure: In each optimization step, the LLM generates candidate solutions from the meta-prompt, evaluates them, and adds them for subsequent optimization.The process stops when no better solutions are proposed or when the maximum number of steps is reached.
  • Meta-prompt design: The meta-prompt describes the optimization problem, including the objective function and solution constraints.For prompt optimization, it can request a new instruction that achieves higher accuracy and impose properties such as concision or general applicability.
  • Meta-prompt design: The optimization trajectory contains past solutions and scores, enabling the LLM to identify patterns among high-scoring solutions and build on them.Scores are sorted in ascending order in the trajectory.
  • Solution generation challenges: Optimization stability is threatened because low-quality solutions in the trajectory can drastically affect LLM outputs and create large variance.This problem is especially pronounced early, before the solution space has been adequately explored.
  • Solution generation challenges: Sampling temperature controls exploration and exploitation: lower values favor small adaptations near known solutions, while higher values encourage more distinct solutions.The design treats this balance as a fundamental optimization challenge.

3 MOTIVATING EXAMPLE: MATHEMATICAL OPTIMIZATION

OPRO applies LLM prompting to mathematical optimization by using prior solutions and objective values to propose improved candidates. On small problems, it can find strong solutions, but performance degrades as problem size or optimization difficulty increases.

  • Mathematical optimization: LLMs use past optimization trajectories to infer descent directions in small linear regression and TSP problems.The studies cover continuous linear regression and discrete traveling-salesman optimization.
  • 3.1 LINEAR REGRESSION: Fewer than exhaustive-search numbers of explored (w, b) pairs indicate black-box optimization through comparison and descent-direction proposals.Text-bison and gpt-4 also converge faster than gpt-3.5-turbo.
  • 3.2 TRAVELING SALESMAN PROBLEM (TSP): 4× faster convergence: gpt-4 reaches the TSP global optimum about four times faster than other LLMs on smaller-scale problems.On larger problems, gpt-4 remains comparable to heuristic algorithms while other LLMs can have up to 20× worse optimality gaps.
  • 3.2 TRAVELING SALESMAN PROBLEM (TSP): OPRO performance degrades dramatically as TSP size increases, and farthest insertion eventually outperforms all LLMs in optimality gap.All LLMs find optimal solutions at n = 10, but optimality gaps increase quickly for larger instances.
  • Limitations: OPRO is not designed to outperform state-of-the-art gradient-based continuous optimizers or specialized classical combinatorial solvers.Its stated goal is to show that prompting can optimize different objectives and reach global optima on some small-scale problems.

4 APPLICATION: PROMPT OPTIMIZATION

OPRO optimizes natural-language prompts by having an optimizer LLM generate instructions from task descriptions, exemplars, and previously scored instructions. The generated instruction is inserted into scorer prompts, evaluated on training accuracy, and iteratively refined.

  • 4 APPLICATION: PROMPT OPTIMIZATION: OPRO's prompt-optimization objective is to find instructions that maximize accuracy on natural-language tasks with text inputs and outputs.Training accuracy is the optimization objective, while test accuracy is computed after optimization.
  • 4.1 PROBLEM SETUP: The prompt-optimization dataset uses training and test splits, with training accuracy as the objective value and test accuracy as the post-optimization evaluation.Small training subsets can suffice, including 3.5% of GSM8K and 20% of Big-Bench Hard.
  • 4.1 PROBLEM SETUP: The GSM8K meta-prompt places the generated instruction at <INS> and combines scored solutions, task and output-format descriptions, and meta-instructions.The figure's color coding distinguishes solution-score pairs, optimization-task instructions, and meta-instructions.
  • 4.1 PROBLEM SETUP: The optimizer LLM generates an instruction that is concatenated with each exemplar's question before prompting the scorer LLM.The scorer LLM evaluates the resulting prompts, and the optimizer and scorer may be the same or different models.
  • 4.1 PROBLEM SETUP: Instructions may be inserted at Q_begin before the question, Q_end after the question, or A_begin at the beginning of the scorer output.A_begin applies to pretrained LLMs without instruction tuning using QA-sequence formatting.
  • 4.2 META-PROMPT DESIGN: Optimization-problem exemplars are sampled from training data to demonstrate the task and the position where generated instructions will be inserted.These examples help the optimizer produce instructions in the required style.
  • 4.2 META-PROMPT DESIGN: The optimization trajectory contains past instructions and scores sorted in ascending order, retaining only the highest-scoring instructions under the context-length limit.In prompt optimization, the scores are training accuracies.
  • 4.2 META-PROMPT DESIGN: Meta-instructions explain the optimization goal, how to use the supplied information, and sometimes the desired output format for parsing.They complement the task exemplars and scored instruction history in the meta-prompt.

5 PROMPT OPTIMIZATION EXPERIMENTS

OPRO iteratively optimizes natural-language instructions using LLMs as optimizers and scorers, producing substantial gains across GSM8K and Big-Bench Hard. Results also show sensitivity to initialization and wording, while ablations clarify the roles of iterative search and task exemplars.

  • OPRO brings significant performance gains across prompt-optimization experiments with different combinations of optimizer and scorer LLMs.
  • 5.2.1 GSM8K: On GSM8K, optimization curves generally trend upward while the variance among generated-instruction accuracies decreases.This pattern appears with both the pre-trained PaLM 2-L scorer and the text-bison scorer.
  • 5.2.1 GSM8K: 78.2 training accuracy was reached by “Let’s do the math!” at Step 6, nearly matching 80.2 from “Take a deep breath and work on this problem step-by-step.” at Step 107.Large curve leaps can reflect simultaneous qualitative improvement across all eight instructions rather than discovery of one much better instruction.
  • 5.2.1 GSM8K: Pre-trained PaLM 2-L can optimize its own prediction performance, but performs better with few-shot formatting and different initialization instructions.The experiment begins with the empty instruction at 32.2 training accuracy and “The answer is” at 33.3.
  • 5.2.2 BBH: On BBH, OPRO improves over “Let’s think step by step.” by over 5% on 19/23 tasks with PaLM 2-L and 15/23 with text-bison.It also improves over the empty starting point by over 5% on 20/23 and 15/23 tasks, respectively.
  • 5.2.2 BBH: On ruin_names, semantically similar instructions improve from 72.0 at Step 1 to 80.0 at Step 18 and 82.0 at Step 38 training accuracy.The results emphasize that optimizer-generated paraphrases can produce notable accuracy improvements.
  • 5.2.3 SEMANTICALLY SIMILAR INSTRUCTIONS MAY ACHIEVE DRASTICALLY DIFFERENT ACCURACIES: Small wording changes can cause large GSM8K accuracy differences, including 71.8 for “Let’s think step by step.” versus 49.4 for a semantic combination of related instructions.
  • 5.3 ABLATION STUDIES: Ablations show that iterative optimization outperforms one-step instruction generation, while task exemplars are critical but adding more exemplars can distract the optimizer.Starting instructions also affect early performance and convergence, with stronger initializations producing better instructions sooner.

6 RELATED WORK

The paper positions OPRO among approaches that use language models for optimization, emphasizing its use of optimization trajectories rather than explicit feedback or evolutionary operators.

  • Prior prompt-optimization methods include continuous soft prompts, gradient-guided discrete search, and reinforcement learning.
  • Related work also uses natural language feedback to revise outputs and improve model behavior or reasoning.
  • OPRO uses the optimization trajectory in its prompt, requiring the optimizer LLM to infer common characteristics of similarly scored solutions.
  • Other work tunes or prompts language models as mutation and crossover operators within evolutionary algorithms.

7 CONCLUSION

The conclusion presents OPRO as an approach that progressively generates better solutions, demonstrated on classical optimization problems and prompt optimization. It reports parity with some hand-crafted heuristics on small traveling-salesman problems and substantial gains over human-designed prompts.

  • OPRO progressively generates new solutions to optimize an objective function using LLMs.
  • On small-scale traveling-salesman problems, OPRO performs on par with some hand-crafted heuristic algorithms.
  • Optimized prompts outperform human-designed prompts on GSM8K and Big-Bench Hard by a significant margin, sometimes over 50%.
  • Reducing sensitivity to initialization and balancing exploitation with exploration remain unresolved questions for LLM-based optimization.
  • The current prompt optimizer does not effectively use error cases to infer promising directions for improving generated instructions.

ETHICS STATEMENT

The ethics statement identifies the datasets used in the experiments and flags safeguarding model behavior against harmful information as future work.

  • The experiments use synthetic math problems for linear regression and traveling-salesman problems and public datasets including GSM8K and Big-Bench Hard.
  • Safeguarding model behavior against harmful information remains valuable future work.

REPRODUCIBILITY STATEMENT

The reproducibility statement identifies the public evaluation benchmarks, model APIs, and specific GPT model versions used in the work.

  • The evaluation uses public benchmarks.
  • The study uses the text-bison API and GPT model APIs, specifically gpt-3.5-turbo-0613 and gpt-4-0613.

A SOME FAILURE CASES

OPRO has several failure modes in black-box optimization, including unreliable novelty, numerical hallucination, stagnation, and difficulty navigating complex landscapes. Prompting-format examples also illustrate that scorer-model formatting is task- and model-dependent.

  • Optimizer LLMs can hallucinate mathematically incorrect function values unless reliable external calculation tools are triggered.The paper leaves when and how to trigger such tool use as an open question.
  • Optimizer LLMs do not reliably generate solutions distinct from those already in context, even when explicitly instructed to do so.Comparing the new solution with all previous ones makes novelty almost guaranteed, but may affect instruction following elsewhere.
  • Black-box optimization can become stuck away from both global and local optima when exemplars share misleading coordinates or point in quantitatively opposite directions.The paper notes that including more past solutions can help avoid one linear-regression failure case.
  • The optimizer LLM struggles to navigate the narrow valley of the Rosenbrock landscape toward the global optimum at (20, 400).The illustrated landscape has a narrow valley between (0, 0) and (20, 400).
  • Q_begin, Q_end, and A_begin are distinct prompting formats, with the QA pattern removed for Q_begin and Q_end when using instruction-tuned scorer models such as text-bison.The appendix figures provide examples with and without the QA pattern.

C META-PROMPTS

OPRO’s meta-prompts combine previously evaluated solutions or instructions with a natural-language optimization task and output requirements. The appendix instantiates this format for mathematical optimization and prompt optimization across model settings.

  • C.1 META-PROMPT FOR MATH OPTIMIZATION: The math-optimization meta-prompt asks the LLM to minimize a two-variable function using previously evaluated (w, b) pairs.The pairs are ordered by function value, with lower values better.
  • C.1 META-PROMPT FOR MATH OPTIMIZATION: The linear-regression meta-prompt displays solution-score pairs alongside orange meta-instructions.The figure identifies the blue text as solution-score pairs and the orange text as meta-instructions.
  • C.1 META-PROMPT FOR MATH OPTIMIZATION: The appendix shows a malformed or unrelated trace-and-length fragment in the mathematical-optimization meta-prompt materials.The passage presents coordinates followed by trace lengths and states that lower lengths are better.
  • C.1 META-PROMPT FOR MATH OPTIMIZATION: The traveling-salesman meta-prompt similarly presents solution-score pairs for a problem of size n = 20 with accompanying meta-instructions.The figure uses the same color distinction between solution-score pairs and meta-instructions.
  • C.2 META-PROMPT FOR PROMPT OPTIMIZATION: For PaLM 2-L prompt optimization, the generated instruction is prepended to the scorer LLM output in the A_begin format.The appendix figure gives this meta-prompt format for GSM8K with pre-trained PaLM 2-L as scorer.
  • C.2 META-PROMPT FOR PROMPT OPTIMIZATION: A prompt-optimization meta-prompt asks the LLM to generate an instruction from previously scored instructions on a 0-to-100 scale.The generated instruction is represented as <INS>.
  • C.2 META-PROMPT FOR PROMPT OPTIMIZATION: For GPT models, the prompt-optimization meta-prompt includes solution-score pairs, task and output-format descriptions, and meta-instructions.The generated instruction is likewise prepended in the A_begin format.

D PROMPT OPTIMIZATION CURVES ON THE REMAINING BBH TASKS

Across the remaining BBH tasks, prompt-optimization curves generally rise over optimization steps. The two figures divide these tasks into parts, with most curves trending upward in one and all curves doing so in the other.

  • Most prompt-optimization curves on the first group of 21 remaining BBH tasks have upward trends.The tasks exclude ruin_names and temporal_sequences, which appear in Figure 6.
  • All prompt-optimization curves on the second group of 21 remaining BBH tasks have upward trends.These tasks also exclude ruin_names and temporal_sequences shown in Figure 6.

E PROMPT OPTIMIZATION ON BBH TASKS – TABULATED ACCURACIES AND FOUND INSTRUCTIONS

Tabulated BBH results compare OPRO-found instructions with standard and starting-point baselines across scorer and optimizer configurations. The results generally favor optimized instructions, while instruction style depends on the prompting format and starting point.

  • E.1 PALM 2-L-IT AS OPTIMIZER, OPTIMIZATION STARTING FROM THE EMPTY STRING: The PaLM 2-L-IT experiments report training, test, and overall accuracies for found instructions against baselines across BBH tasks.PaLM 2-L scores use A_begin instructions, while text-bison scores use Q_begin instructions.
  • E.1 PALM 2-L-IT AS OPTIMIZER, OPTIMIZATION STARTING FROM THE EMPTY STRING: The PaLM 2-L-IT optimizer produces task-wise instructions for both PaLM 2-L and text-bison scorers.These results are listed separately in the task-wise instruction tables.
  • E.1 PALM 2-L-IT AS OPTIMIZER, OPTIMIZATION STARTING FROM THE EMPTY STRING: The BBH examples include instructions for temporal_sequences, tracking_shuffled_objects, web_of_lies, and word_sorting.The supplied excerpts show the corresponding task-specific instruction text.
  • E.2 GPT-3.5-TURBO AS OPTIMIZER, OPTIMIZATION STARTING FROM THE EMPTY STRING: Most instructions found from the empty starting point outperform “Let’s think step by step.” and the empty string across the GPT-3.5-turbo experiments.The comparison covers PaLM 2-L and text-bison scorer settings.
  • E.2 GPT-3.5-TURBO AS OPTIMIZER, OPTIMIZATION STARTING FROM THE EMPTY STRING: A_begin optimization with GPT-3.5-turbo often produces imperative or interrogative instructions better suited to Q: than A:.Starting from “Let’s solve the problem.” yields more declarative instructions suited to A_begin.
  • E.2 GPT-3.5-TURBO AS OPTIMIZER, OPTIMIZATION STARTING FROM THE EMPTY STRING: With “Let’s solve the problem.” as the starting point, the study compares found instructions against that phrase, “Let’s think step by step.”, and empty-start instructions.The corresponding accuracy and task-wise instruction tables are Tables 14 and 15.
  • E.2 GPT-3.5-TURBO AS OPTIMIZER, OPTIMIZATION STARTING FROM THE EMPTY STRING: Starting-point wording influences the prevalence of the “Let’s” pattern and the declarative style of generated A_begin instructions.The paper connects this pattern to the fixed “Let’s” template used by Zhou et al. (2022b).
Loading 2309.03409v3…