Large Language Models as Optimizers

Abstract: 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.

Preview

Synopsis

Overview

Keywords: Large Language Models, Optimization, Prompting, OPRO, Natural Language Processing
Objective: To explore the use of large language models (LLMs) as optimizers through a method called Optimization by PROmpting (OPRO).
Hypothesis: LLMs can effectively generate and optimize solutions to various mathematical and natural language tasks by iteratively refining prompts based on previous outputs.
Innovation: Introduction of a novel framework (OPRO) that leverages natural language descriptions for optimization tasks, allowing LLMs to adaptively generate solutions without the need for formal programming.

Background

Preliminary Theories:
- Iterative Optimization: Traditional optimization methods often rely on iterative updates to improve solutions based on objective functions.
- Natural Language Understanding: LLMs possess the ability to interpret and generate human-like text, enabling them to understand complex optimization tasks described in natural language.
- Prompt Engineering: The design of prompts significantly influences the performance of LLMs, making it a critical aspect of their application in various tasks.
- Exploration vs. Exploitation: Balancing the search for new solutions (exploration) with refining known good solutions (exploitation) is essential in optimization.
Prior Research:
- Evolutionary Algorithms: Previous studies have utilized LLMs as mutation and crossover operators in evolutionary algorithms, demonstrating their potential in generating novel solutions.
- Prompt Optimization Techniques: Research has shown that optimizing prompts can lead to significant improvements in task performance, especially in natural language processing tasks.
- Performance Benchmarks: Earlier works established benchmarks like GSM8K and Big-Bench Hard, which serve as evaluation standards for LLM performance in reasoning tasks.

Methodology

Key Ideas:
- OPRO Framework: The OPRO framework allows LLMs to generate candidate solutions based on a meta-prompt that includes past solutions and their scores.
- Meta-Prompt Design: The meta-prompt consists of the optimization problem description and the optimization trajectory, which guides the LLM in generating new solutions.
- Sampling Strategies: Multiple solutions are generated at each step to enhance exploration and mitigate the risk of getting stuck in local optima.
Experiments:
- Case Studies: Evaluations on classic optimization problems like linear regression and the traveling salesman problem demonstrate the effectiveness of LLMs in generating quality solutions.
- Prompt Optimization: The ability of LLMs to optimize prompts for natural language tasks is assessed using benchmarks such as GSM8K and Big-Bench Hard, measuring improvements in task accuracy.
Implications: The design of the OPRO methodology allows for flexible adaptation to various optimization tasks, showcasing the potential of LLMs to serve as general-purpose optimizers.

Findings

Outcomes:
- LLMs successfully generated high-quality solutions for small-scale optimization problems, often matching or exceeding the performance of traditional heuristic algorithms.
- Optimized prompts significantly outperformed human-designed prompts in benchmark tasks, with improvements exceeding 50% in some cases.
- The iterative nature of the OPRO framework allowed LLMs to refine their outputs progressively, demonstrating effective learning from previous optimization steps.
Significance: This research challenges the traditional view of optimization, suggesting that LLMs can serve as versatile tools for generating solutions across various domains without the need for extensive customization.
Future Work: Further research is needed to address limitations such as sensitivity to initialization and the exploration-exploitation trade-off. Incorporating richer feedback mechanisms and exploring larger problem spaces are potential avenues for enhancement.
Potential Impact: Advancements in LLM optimization capabilities could revolutionize fields requiring complex problem-solving, from mathematical optimization to natural language processing, enabling more efficient and adaptable solutions.