Automatic Prompt Optimization with “Gradient Descent” and Beam Search (2023)

Abstract: 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, Prompt Optimization with Textual Gradients (ProTeGi), 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, much like how numerical gradients point in the direction of error ascent. The natural language 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.

## introduction large language models (llms) trained on webscale text have recently demonstrated unprecedented abilities across a variety of nlp tasks @xcite . these llms use prompt inputs to follow human instructions. writing prompts in natural language remains a manual trial-and-error process requiring significant human effort @xcite and expertise @xcite . 1 code and data available at: https://github.com/ microsoft/lmops/tree/main/prompt_optimization . accordingly, there is need for automatic or semiautomatic procedures to help humans write the best prompts. this would help reduce manual effort, improve task performance, and produce interpretable descriptions of a cognitive decision process. a recent body of work has investigated this problem by training auxiliary models or differentiable representations of the prompt @xcite . however, such works assume access to internal state variables of the llm @xcite while practitioners often communicate with llms through an api. other work applies discrete manipulations to prompts via reinforcement learning or llmbased feedback @xcite . these algorithms may also require low-level access to the llm, produce incomprehensible outputs, or rely on directionless monte-carlo search over the semantic space of prompts. we propose prompt optimization with textual gradients (protegi), a general purpose and nonparametric algorithm for automatic prompt optimization that connects these two bodies of research by applying discrete improvements to prompts in a directed way. unlike prior work, we overcome the discrete optimization barrier by mirroring the steps of gradient descent within a text-based socratic dialogue @xcite , substituting differentiation with llm feedback and backpropagation with llm editing. in detail, we use minibatches of training data to produce "gradients" in natural language, i.e., descriptions of the current prompts' flaws with respect to the minibatch, then edit the current prompt in the opposite semantic direction of the gradient. these steps become the expansion part of a wider beam search over the space of prompts, increasing algorithmic efficiency by treating the problem of beam candidate selection as an instance of the best arm identification problem @xcite . we then offer a preliminary case study of pro-tegi. we evaluate the proposed framework in multiple configurations across 4 nlp tasks, including the novel problem of llm jailbreak detection. the results suggest that the proposed algorithm can improve on the performance of the initial prompt input by up to 31%, exceeding state-of-the-art prompt learning baselines by an average of 4-8% while relying on fewer llm api calls. we also demonstrate the interpretability of the optimization process and investigate the algorithms' shortcomings. ## discrete prompt optimization with the proposed algorithm assumes access to an initial prompt p 0 and i.i.d. training data consisting of pairs of input and output text (numbers, categories, summaries, etc): note that all prompts p are drawn from the space of coherent natural language l. we assume access to a black box llm api llm p (x) ≈ argmax @xmath0, x), which returns a likely text continuation y of the prompt formed by concatenating p and x (for example, few-shot prompt and input example, or chatbot persona and conversational history). within this context, our algorithm iteratively refines the prompt p 0 to produce p, an approximation of the optimal prompt p * = argmax @xmath1, d te )} for some metric function m(•) and in-domain test or development data d te . in the following sections, we first introduce how the algorithm performs textual "gradient descent" to improve the prompts in a directed way (section 2.1). then the algorithm leverages these gradient descent steps to beam search through the space of coherent language l, guided by the gradients during beam expansion, and efficient best arm identification during beam selection (section 2.2). ## experiments we present a limited and preliminary case study to demonstrate the proposed protegi algorithm across 4 benchmark nlp tasks, finding that it can exceed state-of-the-art prompt learning baselines in terms of efficiency and performance. ## related work our work draws from a number of related areas of research on llm prompts. the majority of works attempt to improve llm prompts through the differentiable tuning of soft prompts @xcite or training auxiliary models that participate in prompt manipulations @xcite @xcite or directly training the prompt generator itself @xcite . however, many practitioners communicate with the llm through an api, without access to internal state variables needed for model training, and the language of directly optimized prompts is incoherent @xcite . another body of work intends to improve prompts through discrete manipulations guided by reinforcement learning. research in this space builds up the prompt on a per-token @xcite or per-phrase basis @xcite . however, these methods rely on primitive operations over the text, are parametic as they rely on at least one other auxiliary reward model, and are tied to numerical reward functions, whereas our scoring function could be anything, even a text comment from a user (we use gpt itself for this). another body of work in the discrete manipulation space leverages llm-based feedback, for example @xcite ; @xcite proposed the llm-generated monte-carlo sampling method that is represented by our mc baseline, and @xcite features an evolutionary search through prompts which are generated by llm-paraphrased and swapped chunks of the original prompt. concurrent to our work, @xcite propose editing sql-generation prompts based on output feedback. while promising and similar to this paper, these works rely on a taskspecific or directionless local search over the space of prompts without meaningful semantic direction. furthermore, such works often focus on generating prompts from scratch @xcite while it is trivial for humans to write a quick first draft (with e.g. a vague description of the desired behavior). ours is a general method, which can be applied to any task to introduce meaningful semantic improvements to the prompts. ## conclusion in this paper, we proposed prompt optimization with textual gradients (protegi), a simple and general-purpose framework for the automatic optimization of llm prompts. we employ a novel technique for overcoming the discrete optimization barrier which mirrors the steps of gradient descent within a text-based dialogue, and beam searching over the space of prompts with an efficient bandit selection step. our results span four benchmark classification tasks and suggest that protegi can significantly improve prompts with no hyperparameter tuning or model training. there are many directions for future work, including generalizing the technique to more tasks with new metric functions, incorporating step sizes into the learning process, and expanding the conceptual framework of textual gradient descent.