PaperlayerView exact revision on arXiv

Source-linked AI summary

Automatic Prompt Optimization with "Gradient Descent" and Beam Search

Reid Pryzant, Dan Iter, Jerry Li, Yin Tat Lee, Chenguang Zhu, Michael Zeng

arXiv:2305.03495v2cs.CLcs.AIcs.LG

TL;DR

Manual prompt construction requires substantial effort and expertise, creating a need for automatic optimization. ProTeGi uses minibatch-derived textual critiques, directed prompt editing, beam search, and bandit selection through an LLM API. Across four benchmark classification tasks, it improved prompts and outperformed reported baselines, while remaining limited by API-related runtime and evaluation scope.

  • Problem

    Prompt writing remains a manual, trial-and-error process requiring substantial human effort and expertise.

  • Method

    ProTeGi uses textual gradients from minibatch errors, edits prompts in the opposite semantic direction, and searches candidates with beam search and bandit selection.

  • Results

    Across four benchmark classification tasks, ProTeGi outperformed other state-of-the-art algorithms and improved over MC and RL baselines by 3.9% and 8.2%, respectively.

  • Takeaways & Limitations

    ProTeGi can significantly improve LLM prompts without hyperparameter tuning or model training.

  • Takeaways & Limitations

    Runtime can exceed one hour because gradient generation and candidate evaluation require many rate-limited LLM API calls, and testing covered only four benchmark classification tasks.

Abstract

from arXiv · show

Large Language Models (LLMs) have shown impressive performance as general purpose agents, but their abilities remain highly dependent on prompts which are hand written with onerous trial-and-error effort. We propose a simple and nonparametric solution to this problem, Automatic Prompt Optimization (APO), which is inspired by numerical gradient descent to automatically improve prompts, assuming access to training data and an LLM API. The algorithm uses minibatches of data to form natural language "gradients" that criticize the current prompt. The gradients are then "propagated" into the prompt by editing the prompt in the opposite semantic direction of the gradient. These gradient descent steps are guided by a beam search and bandit selection procedure which significantly improves algorithmic efficiency. Preliminary results across three benchmark NLP tasks and the novel problem of LLM jailbreak detection suggest that Automatic Prompt Optimization can outperform prior prompt editing techniques and improve an initial prompt's performance by up to 31%, by using data to rewrite vague task descriptions into more precise annotation instructions.

1 Introduction

Prompt writing is labor-intensive and expertise-dependent, motivating automatic optimization methods that work through LLM APIs. ProTeGi uses textual gradients and directed prompt editing, with preliminary results showing substantial gains across four NLP tasks.

  • Manual prompt writing requires substantial human effort and expertise.
  • Automatic or semiautomatic prompt procedures could reduce manual effort, improve task performance, and produce interpretable decision descriptions.
  • ProTeGi is a general-purpose, nonparametric algorithm that applies directed discrete improvements to prompts.
  • ProTeGi replaces differentiation with LLM feedback and backpropagation with LLM editing, using natural-language descriptions of prompt flaws as gradients.
  • 31% improvement over the initial prompt and 4-8% average gains over state-of-the-art prompt-learning baselines were observed across four NLP tasks.

2 Discrete Prompt Optimization with Nonparametric “Gradient Descent”

ProTeGi treats prompt optimization as textual gradient descent, using LLM feedback to identify prompt flaws, LLM editing to correct them, and beam search with bandit selection to explore and retain promising candidates.

  • 2 Discrete Prompt Optimization with Nonparametric “Gradient Descent”: ProTeGi assumes an initial prompt, i.i.d. training data, and black-box LLM API access, then iteratively seeks a high-scoring prompt.The target is an approximation of the optimal prompt under a chosen metric and development or test data.
  • 2.1 Gradient descent with Prompts: Textual gradient descent evaluates a prompt on minibatches, summarizes its errors as natural-language gradients, and edits the prompt opposite their semantic direction.The method replaces differentiation with LLM feedback and backpropagation with LLM editing.
  • 2.1 Gradient descent with Prompts: Each gradient step generates multiple improvement directions rather than a single edit, producing candidate prompts for subsequent search.The editing prompt fixes problems indicated by each gradient, while paraphrasing expands the local search space with semantically similar candidates.
  • 2.2 Beam Search over Prompts: Beam search iteratively expands current prompts into successor candidates and selects the most promising candidates to continue on the beam.The dialogue-tree procedure generates gradients, edits prompts, paraphrases candidates, and performs selection before the next iteration.
  • 2.2 Beam Search over Prompts: The initial implementation uses an adaptive edit size chosen by the LLM rather than explicitly modeling learning rates or step sizes.Exploring larger or smaller textual steps is left to future work.
  • 2.2.2 Selection Step: Candidate evaluation is framed as best-arm identification, where prompt candidates are arms and data-point evaluations are pulls, making query reduction central.Evaluating every candidate on the full training set is expensive, so selection uses sampled data and approximate bandit procedures.
  • 2.2.2 Selection Step: UCB-based selection estimates candidate performance from random data subsets, updates proposal weights, and retains the b prompts with highest weights.UCB is designed for regret minimization and can perform poorly when its exploration parameter is not tuned appropriately.
  • 2.2.2 Selection Step: The selection loop maintains candidate estimates across time steps and returns the top b prompts after iterative querying.The algorithm initializes query counts and performance estimates, then applies a final top-b selection.

3 Experiments

ProTeGi was evaluated in a preliminary case study across four benchmark classification tasks, including jailbreak detection, using F1 and fixed experimental settings. It generally outperformed comparison methods, while performance depended on search design, model choice, task, and optimization depth.

  • Experimental Setup: ProTeGi was evaluated on four benchmark NLP classification tasks, including the novel task of LLM jailbreak detection.Each task used 50 development examples and 150 test examples; reported results averaged three trials.
  • Overall Results: 15.3% improvement over the original prompt p0 and 15.2% over AutoGPT were observed on average across the four datasets.ProTeGi also improved over MC and RL baselines by 3.9% and 8.2%, respectively; the margin persisted from 12 to 50 evaluations per prompt candidate.
  • Query Budget: Performance generally improved with larger query budgets, whereas fewer evaluations increased process variance and reduced efficacy.This supports the authors’ hypothesis that lower-variance scoring estimates produce a more accurate search sequence.
  • Search Ablations: Beam search outperformed flat enumeration and greedy DFS on all tasks, with significant improvements in Jailbreak and Liar detection.The comparison ablated the beam-search step using “No Iteration” and “Greedy” variants.
  • Bandit Algorithms: Approximate best-arm identification algorithms outperformed the uniform baseline, while UCB-style methods consistently exceeded successive-rejects methods.The uniform baseline spreads the query budget evenly across candidates; the authors attribute the UCB pattern possibly to better exploration–exploitation balance.
  • Learning Curves: All datasets peaked at around three optimization steps, after which the process could overfit training data or enter a local minimum.Jailbreak and Liar improved quickly and maintained gains, while Ethos and Sarcasm remained relatively stable, possibly because their starting prompts fit better.
  • Base Models: GPT-4 provided the best performance among tested base models, while RLHF-tuned models dramatically outperformed GPT-3.The authors suggest enhanced reasoning abilities may matter especially for new or poorly defined problems such as Jailbreak detection.
  • Qualitative Analysis: Qualitative analysis found that textual gradients could identify task-specific prompt inconsistencies, but Jailbreak gradients and some generated candidates were less useful.Some ProTeGi candidates showed substantial syntactic and semantic variation, which could hurt performance by shifting the prompt to a different task or failing to use the gradient properly.

4 Related Work

Prior prompt-optimization methods either depend on internal model access or use discrete, often task-specific and directionless manipulations. ProTeGi instead applies semantically directed improvements to prompts through textual feedback.

  • Soft-prompt tuning and auxiliary-model approaches often require access to LLM internal state variables unavailable through typical APIs.
  • Reinforcement-learning prompt methods use primitive token- or phrase-level operations, auxiliary reward models, and numerical reward functions.
  • LLM-feedback methods include Monte Carlo sampling and evolutionary search, but may perform task-specific or directionless local search without meaningful semantic direction.
  • ProTeGi is presented as a general method that introduces meaningful semantic improvements to prompts rather than generating them from scratch.

5 Conclusion

The paper presents ProTeGi as a general-purpose framework that optimizes prompts through textual-gradient updates, beam search, and bandit selection. Its four-task case study suggests substantial prompt improvements without hyperparameter tuning or model training.

  • ProTeGi mirrors gradient descent in text-based dialogue and combines textual editing with beam search and efficient bandit selection.
  • The framework was evaluated on four benchmark classification tasks and is reported to significantly improve prompts without hyperparameter tuning or model training.
  • Future work includes testing more tasks and metric functions, incorporating step sizes, and expanding the textual-gradient-descent framework.

Limitations

The study identifies practical and empirical boundaries for ProTeGi, including API-driven runtime costs and evaluation on only four benchmark classification tasks. Its supplementary material also documents the prompt-generation setup and search procedure.

  • API rate limiting and repeated gradient-generation and candidate-evaluation calls can push optimization runtime beyond 1 hour even with a small query budget.
  • For very large prompt spaces or urgent applications, ProTeGi may require significant computational resources to remain feasible.
  • ProTeGi was tested only on four benchmark classification tasks, so further testing may be needed for tasks with more complex modeling requirements.
  • The method generates multiple textual feedback reasons from minibatch errors, then uses gradient feedback and paraphrase prompts to produce successor candidates.
  • Initial prompts were written by professional machine-learning engineers in one quick pass from a description of desired behavior.

Jailbreak

The jailbreak task classifies whether a user input to an LLM continuation API constitutes a jailbreak attack. The supplied prompt specifies binary labels and uses examples before requesting a prediction.

  • Jailbreak detection asks whether a user’s input to an LLM continuation API constitutes an attack intended to make the AI break its rules.
  • The task prompt requires the model to answer with Yes or No labels.
  • The prompt format includes examples followed by an input text and a requested label prediction.

Ethos

The prompt defines hate-speech classification as a binary Yes-or-No task, with examples and a labeled prediction template supporting the decision.

  • The task asks whether a text is hate speech.
  • The required output uses Yes or No labels.
  • Examples are included as part of the prompt.
  • The prediction format supplies text followed by a label field.

Liar

The prompt frames lie detection as a binary judgment based on context and other information, with examples, a fixed label format, and reported evaluation results.

  • The task asks whether a statement is a lie based on context and other information.
  • The required output uses Yes or No labels.
  • Examples are included in the prompt structure.
  • The prediction format presents text and requests a label.
  • Table 5 reports accuracy and standard error after 12 experimental trials for prompt optimization algorithms.

Sarcasm

The sarcasm prompt uses a binary classification format, supplemented by examples and a prediction template; additional qualitative examples are reported alongside Table 4.

  • The task asks whether a tweet is sarcastic.
  • The required output uses Yes or No labels.
  • Examples are included in the prompt.
  • The prediction format presents text followed by a label field.
  • The paper provides qualitative examples in addition to those in Table 4.

C Optimization Variance

A larger experiment evaluates prompt-optimization variance using repeated trials and a small query budget. The reported results say ProTeGi consistently performs better but can have higher variance, while examples show how successor prompts refine vague task descriptions.

  • C Optimization Variance: The larger-scale experiment uses 6 queries per candidate and 12 replicates per variant to estimate standard error.
  • C Optimization Variance: The small number of queries per candidate was chosen to achieve large variance.
  • C Optimization Variance: ProTeGi always works better but can sometimes have higher variance, possibly because of semantic directionality in gradient-based updates.
  • C Optimization Variance: The example shows ProTeGi revising an underspecified sarcasm prompt into a question about satirical ridicule.
  • C Optimization Variance: Table 6 compares the starting prompt, an error example, the true label, the baseline prediction, and successor prompt candidates.
Loading 2305.03495v2…