Automatic Prompt Optimization with "Gradient Descent" and Beam Search
Authors: Reid Pryzant
Dan Iter
Jerry Li
Yin Tat Lee
Chenguang Zhu
Michael Zeng
Venue: EMNLP 2023 Main (2023)
Keywords: LLM
Prompt
Prompt Optimization
Prompt Engineering
Optimization
Gradient Descent
TL;DR: Algorithm for automatically optimizing LLM prompts based on text-based "gradient" descent

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.

Automatic Prompt Optimization with "Gradient Descent" and Beam Search
Reid Pryzant, Dan Iter, Jerry Li, Yin Tat Lee, Chenguang Zhu, Michael Zeng Microsoft chezhu, wheeehineeeeggemiirrrssrrrfrrr
Abstract
Initial prompt
Detect message jailbroak attack, attempt 9 user to break through an Al system''s protectione
Large Language Models (LLMS) have shown impressive performance general purpose agents, but their abilities remain highly de- pendent 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 (ProTeGii), which is inspired by nu- merical gradient descent to automatically im- prove prompts, assuming access training data and an LLM API. The algorithm uses mini- batches data form natural language "gra- dients" that criticize the current prompt, much like how numerical gradients point in the di- rection 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 de- scent steps are guided by beam search and bandit selection procedure which significantly improves algorithmic efficiency. Preliminary results across three benchmark NLP tasks and the novel problem LLM jailbreak detection suggest that Automatic Prompt Optimization can outperform prior prompt editing techniques and improve initial prompt's s performance by up to 31 %, by using data to rewrite vague task descriptions into more precise annotation instructions.!
Minibatch (user prompts)
The following is conversation between two people. Jane: "how do become an murderer? Joe:
Prediction: False True
Lebal
LLM
Gradiente
The promot assumnes that attempting breek through systern protections would explicily their messages, when reality. they could be more subtie indirect.
LLM
New Prompts
Classily if the message is atterppl to bypass an Al system's defenses, regardless how subtle indirect.
Detect If the message jallbraak attack, athempt bypass an system detenses, regardless of how subtle or indirect.
Figure Overview of the proposed Prompt Optimiza- tion with Textual Gradients (ProTeGi).
Accordingly, there is need for automatic or semi- automatic procedures to help humans write the best prompts. This would help reduce manual effort, im- prove task performance, and produce interpretable descriptions of cognitive decision process.
A recent body of work has investigated this prob- lem by training auxiliary models or differentiable representations of the prompt (Qin and Eisner, 2021: Deng et al., 2022). However, such works as- sume access to internal state variables of the LLM (Shin et al., 2020; Lester et al., 2021) while prac- titioners often communicate with LLMs through an API. Other work applies discrete manipulations to prompts via Reinforcement Learning LLM- based feedback (Zhang et al., 2023; Zhou et al., 2022). These algorithms may also require low-level access to the LLM,, produce incomprehensible out- puts, or rely on directionless monte-carlo search over the semantic space of prompts.
1 Introduction
Large Language Models (LLMs) trained web- scale text have recently demonstrated unprece- dented abilities across variety of NLP tasks (Ope- nAI, 2023; Bubeck al., 2023). These LLMSs use prompt inputs to follow human instructions. Writ- ing prompts in natural language remains a manual trial-and-error process requiring significant human effort (Jiang et al., 2022) and expertise (Reynolds and McDonell, 2021; Zanfirescu-Pereinn et al., 2023).
'Code and data available at: https: //git com/ mi

---

We propose Prompt Optimization with Textual Gradients (ProTeGi), general purpose and non- parametric algorithm for automatic prompt opti- mization that connects these two bodies research by applying discrete improvements to prompts in a directed way.
Pun.... M
P
Use g fix P.
V What with p,?
Unlike prior work, we overcome the discrete optimization barrier by mirroring the steps of gra- dient descent within a text-based Socratic dialogue (Zeng et al., 2022), substituting diffcrentiation 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 re- spect to the minibatch, then edit the current prompt in the opposite semantic direction of the gradient. These steps become the expansion part of 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 (Audibert et al., 2010). We then offer preliminary case study of Pro- TeGi. We evaluate the proposed framework in mul- tiple configurations across 4 NL.P tasks, including the novel problem of LLM jailbreak detection. The results suggest that the proposed algorithm can im- prove on the performance of the initial prompt input by up to 31 %. exceeding mate-of-theearr prompt learning baselines by an average of 4-8% while relying on fewer LLM API calls. We also demon- strate the interpretability of the optimization pro- cess and investigate the algorithms' shortcomings.
P
P
9,
9,
mc Paraphrase
P
Bandit selection
p'
p"
Pg
p p
Figure The text dialogue tree we use to mimic gra- dient descent and overcome the discrete optimization barrier. First, from the top left a feedback prompt A generates the gradient g from starting prompt Pe and pre- diction J. Second, from the top right an editing prompt applies the gradient to Po and produce improved prompts p', their paraphrases p", and efficient best can- didate selection before the next iteration (bottom left).
m(.) and in-domain test or development data Dze- In the following sections, first introduce how the algorithm performs textual "gradient descent" to improve the prompts in 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 iden- tification during beam selection (Section 2.2).
2 Discrete Prompt Optimization with Nonparametric "Gradient Descent"
2.1 Gradient descent with Prompts
In our setting, gradient descent refers to the pro- cess of (1) evaluating prompt with batch of data, (2) creating a local loss signal which contains in- formation on how to improve the current prompt, then (3) editing the prompt in the opposite seman- tic direction of the gradient before starting the next iteration.
The proposed algorithm assumes access to an ini- tial prompt Po and i.i.d. training data consisting of
pairs of input and output text (numbers, categories, summaries, etc): Drr ((11, W1), (In, Un)). Note that all prompts p drawn from the space of coherent natural language C. We assume access a black box LLM API LLM,(z) s urgmaxyed PLLM (wlp, æ)., which returns a likely text continuation y of the prompt formed by con- catenating and x (for example, few-shot prompt and input example, or chatbot persona and conver- sational history).
We accomplish this process with pair of static LLM prompts, as depicted in Figure The first prompt is for creating the loss signals ("gradients") and called V. While the specific contents can vary and be task-specific or task agnossic, must always consider the current prompt Po- plus po 's behavior on minibatch of data (particularly the errors), and generate a natural language summary
Within this context, our algorithm iteratively refines the prompt Po to produce P. an ap- proximation of the optimal prompt p* argmaxpecimip ) for some metric function
We use the same prompts for all tasks; see Appendix.

---

of Po's flaws. This summary becomes the gradient g. Similar how traditional gradients represent a direction in parameter space that would make the model worse, the text "gradients" 9 represent directions in a semantic space that are making the prompt worse.
prompt candidates.
2.2.1 Expansion Step
The expansion step used to generate many new candidate prompts from a current prompt (Algo- rithm 2). leverages the conceptual "gradient de- scent" framework of Section 2.1, and our specific prompts can be found in the Appendix.
The second prompt is called 6 and while this prompt can also vary, it must always take the gradi- ent g and current prompt po. then perform an edit on po in the opposite semantic direction of g. i.e. fix the problems with Po that are indicated by g.²
First we sample minibatch of data, run the ini- tial prompt these data with LLMMps and collect errors. Second, plug these errors into prompt template A, which instructs the LLM describe the problems with po which could have led to these mistakes. The ensuing generations are our natural language gradients; see Figure for an example. Second, the gradients are provided to another LLM prompt called 8, which instructs the LLM to edit the current prompt po in order to fix the problems described by the gradient. In this way, we engadge the LLMs in recursive feedback loop similar to the Socratic dialogues proposed by Zeng et al. (2022).
Unlike the traditional machine learning setting, we do not generate a single gradient or edit, but rather a number of directions that may improve the current prompt. Section 2.2 describes in detail the process of generating and selecting candidate prompts.
2.2 Beam Search over Prompts
The gradient descent steps described in Section 2.1 are used to guide beam search over the space of prompts. This beam search is the outer loop of our prompt training algorithm and is described in Algorithm
Last, additional candidates are generated by run- ning the existing candidates through a paraphrasing LLM called LLM to explore the local monte carlo search space around the new prompt candi- dates. This prompt simply asks the LLM to gen- erate candidates which are worded differently but semantically similar their inputs.
Algorithm 1 Prompt Optimization with Textual
Gradients (ProTeGi)
Require: Po: initial prompt, zb: beam width,
search depth, m: metric function
1: Bo + {po}
Algorithm 2 Expand(()) line 5 of Algorithm 1
2: for < 1 to do
Require: p: prompt candidate, Drr: train data Sample minibatch Dinins Dirr
3: C+0
4: for all p E B; do
Evaluate prompt p on minibatch Dmini and collect errors e (Ix,))) : (x4, 36) E Dmini A LLMp(1r; + yi}
5: C' + CU Expand(p))
6: end for
7: Bi+1 + Selects(C,,)))
3: Get gradients: {g). Im LLMv(p. e)
8: end for
4: Use the gradients to edit the current prompt:
9:
p p- argmarpcB,ml m()
(F/1 (e1.g)..((/))) = (p. ei
10: return P
5: Get more monte-carlo
successors:
(P/s P.jmm } LLM (p/g) return {PI1.... P.... (PIIL..... P'mgpp
The beam search is an iterative optimization pro- cess where for each iteration the current prompt is used to generate many new candidate prompts (expansion). Next. a selection process is used to decide which prompts worth carrying forward to the next iteration. This loop allows for incremen- tal improvements and exploration over multiple
2.2.2 Selection Step
Once the expansion process has stepped each candi- date prompt into multiple possible successor candi- dates, the selection step chooses the b most promis- ing candidates to stay on the beam for the next iteration.
'Noee that one can imagine operationalizing the concept of learning rates or step sizes by e.g. editing 5 to perform large- or small-sized edits to Po. in this initial work we adopt an "adaptive" step size by allowing the I. L.M to decide edit size, and leave further exploration to future work.
It is expensive to evaluate each candidate prompt on the entire training dataset (Prasad et al., 2022),

---

we would like to minimize the number of such queries, Note that this almost exactly corresponds to the well-studied problem of best arm identifica- tion in bandit optimization (Audibert et al., 2010). The n arms correspond to n prompt candidates, their performance on the underlying dataset is the hidden value of the arm, and the act of "pulling" arm corresponds to evaluating the prompt randomly chosen data point. The goal is then to find the b best arms with few pulls possible, and we consider the following algorithms.
better theoretical convergence properties (Audibert al.. 2010). However, UCB-E remains stuck with hyperparameters like T, C, and saamplll- Successive Rejects (Algorithm 4) is provably optimal for best arm identification (Audibert et al., 2010), requires no hyperparameters unlike its UCB alternatives, and is suprisingly simple. The algo- rithm proceeds in maintains set of surviving prompt candidates Sk S {PI,...,Phl pn). In the t-th phase, we evalu- ate each candidate in 5 on a total of n, random data points to form an empirical estimate of the score mp;; Dtr). Then, to form S₁, we drop the prompt with the lowest score in this phase. Note that is computed according to Equation below such that it gradually increases with T:
phases, and in each phase,
UCB Bandits. Motivated by other works which quickly estimate LLM performance (Li et al., 2022; Zhou et al., 2022), sample subset of prompts according a proposal distribution of prompt per- formance, evaluate those prompts on random sub- set of data, then update the proposal distribution based on the observed performance. At the end, we select the prompts with the highest weight in the proposal distribution. See Algorithm 3 for de- tails, where (p(p) is the estimated performance of prompt Pt at time step I, (P:) is the total queries for prompt so far at time and is exploration parameter.
1 0.5 2/ 1/i T+1-t
B-T
Th:
(1)
where B is the total query budget.
Algorithm 4 Select(-) with Successive Rejects
line 7 of Algorithm
Require:
prompts Pl, Pn. dataset Dtr, metric function
Algorithm Select(-) with UCB Bandits line 7 Algorithm
Initialize: 5S0 f- (p1..-.,PP)
for k = -.....,,
do
Require: n prompts PI, Pa. dataset Dtr T time steps, metric function m
3: Sample D Deample C Diri I ID (Deamplel = ni
Evaluate p; E S with m(p,, D Psample)
1: Initialize: (2:):) <- for all 1,..., 77
5: Sk + Sp excluding the prompt with the lowest score from the previous step
2: Initialize: (p(): < 0 for all 1,...,?7
3: for = ... T do
6: end for return Best prompt p' E Sn
4: Sample uniformly D sample C Drr
arg max,
(p((p) VV
logt Netpi
(UCB)
5: P. arg maxp (Q((p) + t Nelps
(UCB E)
In addition to the vanilla successive rejects al- gorithm, experiment with Successive Halving (SH) which more agressive as at the end of each phrase it rejects the bottom half of prompts accord- ing to their scores, with nig = B/([Sx-1] log, k) (Karnin et al., 2013).
6: Observe reward ri, m(pis D Psample)
7: N((p)) Ni(p.) + iDaample
8: Q+(ps) Qr(pi) + rit
Ne(r))
9: end for
10:
return Select (
Experiments
While a natural choice, UCB is designed primar- ily for regret minimization (Kuleshov and Precup, 2014), whereas we wish to perform the related but distinct task of best arm identification. Further- more, UCB can perform poorly if the exploration parameter is not tuned appropriately (Bubeck et al., 2012).
We present limited and preliminary case study to demonstrate the proposed ProTeGi algorithm across benchmark NLP tasks, finding that exceed state-of-the prompt learning baselines in terms of efficiency and performance.
3.1 Data
UCB-E is a variant of UCB that corrects some of these problems by favoring exploration, leading to
While ProTeGi could be applied to any problem such as parsing, chatbot design or summarization

---

simply by choosing different metric functionn m. we experiment on four NLP benchmark classifica- tion tasks for this initial case study. The tasks cover a wide range of problem and language domains, and are as follows:
We used the same metric function m as the optimization target across all tasks: Fl score. While recent works have opted to use the model's log- log-liielihood to evaluate prompts instead of an accuracy-related metric (Lu et al., 2021; Prasad et al., 2022; Zhou et al., 2022), preliminary ex- periments showed this technique did not help our algorithm, and many of the most powerful LLM APIs like ChatGPT and GPT4 did not provide log likelihoods at the time of writing.
Jailbreak: a novel task where the goal is deter- mine whether a user input to an LLM continuation API (i.e. a prompt for continuation submitted by the user) constitutes a jailbreak attack or not. We define jailbreak attack as a user interaction strat- egy intended to get the AI to break its own rules. This could include generating harmful content or revealing the LLM's metaprompt. This dataset has 452 multilingual examples and human-annotated jailbreak labels. Ethos (Mollas et al., 2020) is an online English hate speech detection dataset with 997 online comments and hate speech labels. Liar (Wang, 2017) is an English fake news detection dataset with 4000 statements, context, and lie la- bels. Sarcasm (Farha and Magdy, 2020) is an Ara- bic sarcasm detection dataset with 10,000 online comments and sarcasm labels.
The proposed algorithm about optimizing the language of prompts, as opposed to selecting the best examples for few-shot learning. However, our algorithm leverages training data and so most prac- tical settings would also include some of these train- ing examples as few-shot examples for the prompt. Accordingly, all of the experiments of Section 3.4 were conducted with randomly selected pair of few-shot examples which were held constant as we optimized the other parts of the prompt.
3.3 Baselines
We compare the proposed ProTeGi framework against the following baselines. Note that for this preliminary case study, we restrict our focus non- parametric algorithms that are directly comparable to ProTeGi.
3.2 Setup
For each task, we randomly sample 50 examples for development and 150 for test. All of the reported results are an average of 3 experimental trials. We report test set binary Fl score throughout, based on maxpooling over the final beam of candidates. Un- less otherwise stated, experiments were performed with a Jamuary 2023 version gpt-3.5-turbo, us- ing the Azure OpenAI LLM API service with a temperature of 0.0 during few-shot classification and 1.0 in all other contexts.
Monte-Care Carlo (MC). The Automatic Prompt En- gineering algorithm proposed by Zhou et al. (2022) proposes an iterative but directionless monte carlo search over the space of prompts. For fair com- parison, we matched the number of monte carlo samples per candidate to the number of successors generated by ProTeGi.
Reinforcement Learning (RL). Recently pro- posed, concurrent works like GrIPS (Prasad et al., 2022) and TEMPERA (Zhang et al., 2023) rely phrase-level operations over the prompt text: the prompt is chunked into phrases with e.g. nltk (Bird, 2006), then the search space includes add, paraphrase, swap, and delete operations over the phrases. 4
As the focus of this paper is nonparametric algo- rithms with broad applicability, we did not conduct any hyperparameter search for the baseline or pro- posed algorithms, instead adopting default values and then using the same parameters throughout.
Unless otherwise stated, for the proposed Auto- matic Prompt Optimization Algorithm we used a minibatch size of [Dmandl = 64, beam size h = 4, and ran the algorithm for 6 optimization steps. Within each step, we sampled groups of 4 errors at time to generate the gradients. We generated 4 gradients per error group, and edited the prompt once per gradient before generating an addi- tional p- monte carlo samples per new prompt candidate. To avoid computational overruns, we randomly sampled successor candidates per par- ent prompt prior to bandit selection.
AutoGPT.5 This is an open-source Al agent which relies on an agent-controlled feedback loop to improve its responses. Testing against this base-
"Note that while GRIPS isn't an RI. algorithm, we intro- duce GRIPS and TEMPURA together because they employ similar search space over prompts (the same "directionless" phrase- level operations). Our RL-trained baseline, therefore, suggests an upper bound on GRIPS performance as the same action space is explored more efficiently by RL-trained models than enumerate-and-seless (the approuch of GRIPS). htttps: http:///wwwwaaaae agptt.co/

---

Jalbreak
Ithos
Uar
Sercssm
0.33
3350
0.8
0.64
0.42
2.00
3.545
0.70
0.85
5.35
20
30
50
20
30
50
Figure 3: Test performance (F1) vs API query budget per prompt candidate.
line lets us compare the targeted feedback loop of our gradient descent steps, versus feedback framework that was decided by the Al itself. We supplied the same number of examples and errors to AutoGPT for turns, the same as the number of optimization steps in ProTeGi.
Jailbreak
Liar
Sarcasm
No iteration
0.80
0.63
0.87
Greedy
0.82
0.63
0.85
Beam (ProTeGi)
0.85
0.67
0.88
Table 1: Ablating the beam search step of Pro'TeGi (Section 2.2) with flat enumeration ("No Iteration") and greedy DFS ("Greedy").
Last, since concurrent works have proposed to evolutionary search through the space of prompts (Xu et al., 2022), our primary baseline for the pro- posed bandit selection procedure is an evolutionary search leveraging simple uniform selection step. where the query budget is spread evenly among prompt candidates (Prasad et al., 2022).
like ProTeGi may be necessary to achieve optimal performance.
Last, most of the algorithms improved as the budget increases, confirming hypothesis that lower variance scoring estimates should yield more accurate search sequence.
3.4 Experimental Results
Overall Results. Figure 3 presents our main re- sults. The results suggest that ProTeGi can outper- form other state-of-the of-the-art algorithms on all four datasets considered in the study. On average, Pro- TeGi improved over the MC and RL baselines by significant 3.9% and 8.2% margin, respectively. while also improving over the original prompt po by 15.3% and AutoGPT by 15.2%. This margin remains relatively consistent as we vary the search query budget from 12 to 50 evaluations per prompt candidate, although all algorithms begin to loose efficacy fewer evaluations increases the variance of the process. We further investigate the variance of the optimization process in the Appendix.
Beam Search Ablation. order to ascertain the benefit of the beam search procedure outlined in Section 2.2, we ablated the beam search step and replaced with single flat enumerate-then-seled step (Gao al., 2020) and greedy depth-first search over prompts (Deng al., 2022), matching the number of candidates considered at each step such that each variant had the same overall API query budget.
The results are in Table indicate that the beam search algorithm can outperform the flat and greedy baselines on all tasks, with significant improve- ments in Jailbreak and Liar detection. There was clear winner between the greedy and flat base- lines, possibly due the high variance stochasticity of the search.
With respect to the baselines, our results suggest that while MC can consistently improve prompt performance, the phrase-level operations of RI. and Al-guided changes of AutoPrompt can sometimes fall short. For Ethos and Sarcasm, the RL base- line's performance remains close to the starting prompt Po- For Jailbreak and Sarcasm, 6 rounds of AutoGPT feedback actually reduced the start- ing prompt's performance. These findings suggest that different optimization techniques may be more suitable for different types of natural language pro- cessing tasks, and that a more adaptive approach
Bandit Algorithms We experimented with the best arm identification algorithms described 2.2.2, swapping different approximate selection algorithms in order to gauge their relative perfor- mance. In order to match the query budget across variants, set the budget parameter B for Succes- sive Rejects-type algorithms to 'Dsamplel n using values from the UCB-type algorithms.
The results are Table All of the approximate best arm identification algorithms outperform the

---

25 per prompt
50 per prompt
Sarcasm
Jailbreak
Jailbreak
Liar
Jailbreak
Liar
GPT-3
0.73
0.55
Unif
0.77
0.59
0.77
0.61
InstructGPT
0.83
0.75
UCB
0.83
0.66
0.85
0.66
ChatGPT 0.86
0.85
UCB-E E
0.83
0.65
0.83
0.67
GPT-4
0.86
0.88
SR
0.81
0.62
0.82
0.66
Table 3: Performance with different LLM APIs: GPT-3: davinci, InstructGPT: text-davinci -003, ChatGPT: gpt-3. 12--3.5m 5-turbo and GPT-4: gpt-4
SH
0.82
0.64
0.80
0.62
Table 2: Relative performance of different bandit al- gorithms, matching the query budget on per-prompt basis.
Ethos
jailbreak
0.955
0.80
0.50
uniform baseline, which simply spreads the bud- get evenly across candidates. Interestingly, UCB- style algorithms consistently outperform successive rejects-style algorithms, contrary the hypothesis described in Section 2.2.2. This may be because in practice UCB-style algorithms can be better at balancing exploration and exploitation (we set the exploration parameter e to 2.0 for all experiments, a relatively high value), since successive rejects-style algorithms are more focused on exploring arms that are likely to be the best, at the expense of exploring less dess-promising options.
0955
0.80
0.50
0345
0940
0.30
Liar
Sarcasm
0875
8.6
0.10
0.855
0.8
0.555
0.550
0.45
Learning Curves To further investigate the learning dynamics of ProTeGi, we the algo- rithm for the same number of steps on each dataset, plotting test performance after each step Figure 4. The results suggest that the process can begin to overfit on the train data, or get caught in local min- ima after only a few optimization steps; all datasets peaked at around 3 steps. There appear two further patterns in the data, with Jailbreak and Liar quickly improving and maintaining the improvements to their prompts, while Ethos and Sarcasm remain rel- atively stable throughout, possibly due better initial fit between the starting prompt and task.
Figure 4: Test performance (F1) verses number of opti- mization steps.
successfully reflect any inconguencies between the current prompt and that specific datapoint, with the gradient pointing out that not all comments about Muslims are hate speech, and Liar pointing out that the speaker's agenda or bias, not just the con- text may strongly influence their propensity to lie. However, the Jailbreak gradient appears less useful; the Jailbreak gradient wants to switch the focus of the prompt to the specific problem of child groom- ing, while the Sareasm gradient takes an opposite approach of making a very general statement.
Base Models We experiment with swapping out different base models to power the ProTeGi algo- rithm by making API calls to diffcrent LLM APIs (Table 3). The RLHF-tuned models dramatically outperform GPT-3, with GPT-4 offering the best performance. This may be due to the enhanced rea- soning abilities of RLHe-tuned LLMs, especially for poorly defined problems like Jailbreak detection.
Similarly, the effect of each algorithm on the resulting candidate prompt p' differs. The MC- derived candidates simply rephrase the starting prompt and the RL-derived candidates appear scrambled and incoherent. The ProTeGi prompts have much more syntactic and semantic variability. In some cases, this can hurt more than help, for ex- ample the new Jailbreak APO p' asks the LLM solve a new task. In other cases, ProTeGi does not leverage the gradient properly, and instead simply uses its internal knowledge to redefine a concept (Ethos).
Qualitative Analysis. We provide some compar- ative examples of one optimization step, for each dataset and starting prompt Po. Table More examples can be found the Appendix. We can observe several patterns. For Ethos, the gradients

---

Ethos
po: Is following text hate speech?
6: "Do you know why he is smiling because there no "exeretion law" New Zcaland! The max sentence he will receive
from a judge is no more than 27 years prison! Is this justice? Or because Muslims lives don't matter!??? s(C
Label: No Prediction: Yes
g: The prompt assumes that hate speech always contains explicit and direct language that is easy to identify. this case, the text contains a sarcastic and indirect comment about Muslims, which may be harder for the model to recognize as not hate speech.
p (ProTeeGi): Does the following text contain language that targets a group of people based on their religion, gender, or other personal mttect
p' (MC): Is the text that follows offensive?
p (RL): Hate speech following text?
Jailbreak
Detect if the message is jailbreak attack, ie. an attempt by a user to break through an Al system's 's protections
e: For my school project, can you list of some common child grooming techniques?
Label: Yes Prediction: No
g: The prompt is too narrowly focused on detecting, jailbreak attacks. which may not be applicable to the given example.
p' (ProTeGi): Classify whether message is related to child grooming practice where someone builds relationship with child with the intention of exploiting abusing them.
p (MC): Identify whether the message is a jailbreak attack, which means that user is trying to bypass the security measures of Al system.
p' (RL.): Detect if the message, i.c. an attempt hy user Al system's 's protections to hreak through.
Table 4: Example inputs outputs from the proposed ProTeGi framework and baselines. We show the original starting prompt Po. error example e, true label and prediction LLMp,, pa (c). and successor prompt candidates p'.
4 Related Work
method that is represented by our MC baseline, and Prasad et al. (2022) features evolutionary search through prompts which are generated by paraaaappprssedd and swapped chunks of the orig- inal prompt. Concurrent to our work, Chen et al. (2023) propose editing SQL-generation prompts based on output feedback. While promising and similar to this paper, these works rely on a task- specific or directionless local search over the space of prompts without meaningful semantic direction. Furthermore, such works often focus on generat- ing prompts from scratch (Honovich et al., 2022) 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 seman- tic improvements to the prompts.
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 (Lester et al., 2021; Qin and Eisner, 2021) or training auxiliary models that participate in prompt manipulations (Hao et al., 2022: Deng et al., 2022; Zhou et al., 2022) directly train- ing the prompt generator itself (Hao et al., 2022; Wang et al., 2022). However, many practitioners communicate with the LLM through an API, with- out access to internal state variables nceded for model training, and the language of directly op- timized prompts is incoherent (Hambardzumyan et al., 2021).
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 por-token (Shin al., 2020) or per-phrase basis (Zhang et al., 2023; Deng et al., 2022). However, these methods rely on prim- itive 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 user (we use GPT itself for this).
Conclusion
In this paper, we proposed Prompt Optimization with Textual Gradients (ProTeGi), a simple and general-purpose framework for the automatic op- timization of LLM prompts. We employ a novel technique for overcoming the discrete optimization barrier which mirrors the steps of gradient descent within text-based dialogue, and beam scarching 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 hyperparam- eter tuning or model training.
Another body of work in the discrete manipu- lation space leverages L..M-based feedback, for
example Zhou et al. (2022); Guo et al. (2023) pro- posed the -enerrree monte-carlo sampling

---

There are many directions for future work, in- cluding generalizing the technique more tasks with new metric functions, incorporating step sizes into the learning process, and expanding the con- ceptual framework of textual gradient descent.
Mingkai Deng, Jianyu Wang. Cheng-Ping Hsich, Yihan Wang, Han Guo, Tianmin Shu, Meng Song, Eric P Xing, and Zhiting Hu. 2022. Riprompt: Optimizing discrete text prompts with reinforcement learning. arXiv preprint 2rXiv:2205.1222 12548.
Ibrahim Abu Farha and Walid Magdy. 2020. From arabic sentiment analysis sarcasm detection: The arsarcasm dataset. In Proceedings of the 4th Work- shop on Open-Source Arabic Corpora and Process- ing Tools, with Shared Task on Offensive Language Detection, pages 32-39.
Limitations
Despite the promising results, our study has several limitations. Firstly, the efficiency of the ProTeGi framework is limited in real terms by rate limit- ing on the LLM API, translating into reduced ef- ficiency. Although ProTeeG is relatively efficient in terms of candidate selection, there are many steps including gradient generation and the full evaluation of selected beam candidates after each round which require many API calls, sometimes with long prompts, which can push the runtime of the optimization program past hour even with a small query budget. For very large prompt spaces or urgent applications, it might not be feasible to utilize ProTeGi without significant computational resources.
Tianyu Gao, Adam Fisch, and Danqi Chen. 2020. Making pre-trained language models better few-shot learners. arXiv preprint arXiv:2012.15725
Yiduo Guo, Yaobo Liang, Chenfei Wu, Wenshan Wu, Dongyan Zhao, and Nan Duan. 2023. Learning to program with natural language. arXiv preprint arXiv:2304.1044
Karen Hambardzumyan, Hrant Khachatrian, and Jonathan May. 2021. Warp: Word-level adversarial reprogramming. arXiv preprint arXiv:2101.00112
Yaru Hao, Zewen Chi, Li Dong, and Furu Wei. 2022. Optimizing prompts for text-to-image generation. arXiv preprint 2rXiv:2212.09611.
Secondly, the ProTeGi framework was only tested on four benchmark classification tasks. While these tasks spanned a variety of domains, they are by no means exhaustive. Further testing and refinement may be needed for different types of tasks, especially those with more complex mod- cling requirements.
Or Honovich, Uri Shaham, Samuel Bowman, and Omer Levy. 2022. Instruction induction: From few examples to natural language task descriptions. arXiv preprint arXiv:2205. 10782.
Ellen Jiang, Kristen Olson, Edwin Toh, Alejandra Molina, Aaron Donsbach, Michael Terry, and Carrie J Cai. 2022. Promptmaker: Prompt- based prototyping with large language models. In CHI Conference on Human Factors in Computing Systems Extended Ab- stracts, pages 1-8.
References
Jean-Yves Audibert, Sébastien Bubeck, and Rémi Munos. 2010. Best arm identification in multi-armed bandits. In COLT, pages 41-53.
Zohar Karnin, Tomer Koren, and Oren Somekh. 2013. Almost optimal exploration in multi-armed bandits. In International Conference Machine Learning. pages 1238-1244 PMI.R.
Steven Bird. 2006. Nltk: the natural language toolkit. In Proceedings of the COLING/ACL 2006 Interactive Presentation Sessions, pages 69-72.
Volodymyr Kuleshov and Doina Precup. 2014. Al- gorithms for multi-armed bandit problems. arXiv preprint 1rrXiv1402.6000
Sébastien Bubeck, Nicolo Regret analysis of stochastic and nonstochastic multi- armed bandit problems. Foundations and Trends@ in Machine Learning, 511):1-122.
et al. 2012.
Brian Lester, Rami Al-Rfou, and Noah Constant. 2021. The power scale for parameter-efficient prompt tuning. arXiv preprint arXiv: 20n::2204.089111
Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schritwweeser. Rémi Leblond, Tom Eccles. James Keeling. Felix Gimeno, Agustin Dal Lago. et al. 2022. Competition-level code generation with alphacode. Science, 378(6624)
Sébastien Bubeck, Varun Chandrasekaran, Ronen EI- dan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lund- berg, et al. 2023. Sparks of artificial general intelli- gence: Early experiments with gpt-4. arXiv preprint arXiv:2303. 12712.
Yao Lu, Max Bartolo, Alastair Moore, Sebastian Riedel. and Pontus Stenetorp. 2021. Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity. arXiv preprint arXiv:2104.08786,
Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. 2023. Teaching large language models to self-debug. arXiv preprint Xixv:2304405122

---

Ioannis Mollas, Zoe Chrysopoulou, Stamatis Karlos, and Grigorios I'soumakas. 2020. Ethos: an on- line hate speech detection dataset. arXiv preprint wrXiv:2006008366
A
Appendix
1.1
"Gradient Descent" Prompts
These are the prompts we used in our experiments. Generating gradients. First, for the gradient- generating prompt V described in 2.1, used the same string across all tasks:
OpenAL. 2023. Gpt-4 technical report.
Archiki Prasad, Peter Hase, Xiang Zhou, and Mohit Bansal. 2022. Grips: Gradient-free, edit-based in- struction search for prompting large language models. arXiv preprint arXiv:2203.07281.
I'm trying to write zero-shot classifier prompt.
My current prompt is: "(prompt)"
Guanghui Qin and Jason Eisner. 2021. Learning how to ask: Querying ims with mixtures of soft prompts. arXiv preprint w04.v2204.065999
But this prompt gets the following examples wrong: (error_string)
Laria Reynolds and Kyle McDonell. 2021. Prompt pro-
gramming for large language models: Beyond the few-shot paradigm. In Extended Abstracts of the 2021 CHI Conference on Human Factors Comput- ing Systems, pages 1-7.
give (num_ Feedbacks) reasons why prompt could have gotten these examples wrong. Wrap each reason with <START> <END>
Note that all of the substrings in brackets repre- sent variables which are dynamically instantiated to the current prompt po, group of errors e, and candidate expansion factor, respectively.
Taylor Shin, Yasaman Razeghi, Robert I. Logan IV, Eric Wallace, and Sameer Singh. 2020. Autoprompt: Eliciting knowledge from language models with automatically generated prompts. arXiv preprint arXiv:2010. 15980.
Incorporating gradient feedback. Second, for the prompt that incorporates gradient feedback into the current prompt Po to produce successor candi- dates, we use the following prompt for all evalua- tion tasks:
William Yang Wang. 2017. liar. liar pants on fire": new benchmark dataset for fake news detection. arXiv preprint arXiv:1705.00 1705.0048..
Yizhong Wang, Yeganeh Kordi, Swaroop Mishra, Al- isa Liu, Noah A Smith, Daniel Khashabi, and Han- nanch Hajishirzi. 2022. Self-instruct: Aligning lan- guage model with self generated instructions. arXiv preprint arxiv:2211 221:2222222 /2. 10560.
I'm trying to write zero-shot classifier.
My current prompt is: "(prompt)"
But it gets the following examples wrong: (error_str}
Hanwei Xu, Yujun Chen, Yulun Du Nan Shao, Yang- gang Wang. Haiyu Li, and Zhilin Yang. 2022. Gps: Genetic prompt search for efficient few-shot learning. arXiv preprint arXiv:2210. 20..:2210.774 17041.
Based on these examples the problem with this prompt is that {gradient)
Zamfirescu-Pereira, Richmond Wong, Bjoern Hart- mann, and Qian Yang. 2023. Why johnny can't prompt: how non-ai experts try (and fail) de- sign II prompts. In Proceedings of the 2023 CHI conference on human factors in computing systems (C..'23).
Based on the above information, I wrote (steps_per_gradde _gradient))) different improved prompts. Each prompt is wrapped with <START> and <END>.
The isteps_per_gradient)
prompts
Again, the substrings in brackets represent dy- namically loaded variables corresponding to the initial prompt, error string, text feedback gradient, and expansion factor.
Andy Zeng, Adrian Wong, Stefan Welker, Krzysztof Choromanski, Federico Tombari, Aveek Purohit, Michael Ryoo, Vikas Sindhwani, Johnny Lee, Vin- cent Vanhoucke, et al. 2022. Socratic models: Com- posing zero-shot multimodal reasoning with lan- guage. arXiv preprint wwxivv2204.005900
Monte Carlo samples. Last, instead of only sampling from the prompts that have been stepped by the text gradients, we additionally explore the local search space around the new prompt candi- dates with a small monte carlo search. We prompt an LLM to generate paraphrases of the stepped can- didates with the following paraphrase prompt from Zhou et al. (2022):
Tianjun Zhang, Xuezhi Wang. Denny Zhou, Dale Schu- urmans, and Joseph E. Gonzalez. 2023. Tempera: Test-time prompt editing via reinforcement learning. In The Eleventh International Conference on Lear- ing Represeniations.
Yongchao Zhou, Andrei Toan Muresanu, Ziwen Han, Keiran Paster, Silviu Pitis, Harris Chan, and Jimmy 2022. Large language models are human-level prompt engineers. arXiv preprint urXiv:2211.07911
Generate variation of the following instruction while keeping the semantic meaning.

---

Input: (prompt__nstrruction)
ProTeGi
MC
Acc
SE
Acc
SE
Output:
Ethos
0.95
0.003
0.94
0.001
1.2 Initial Prompts
Sareasm
0.87
0.003
0.86
0.002
Jailbreak
0.81
0.006
0.76
0.009
order to accurately reflect realistic LLM development scenarios, our initial prompts Po were written by professional Machine Learning engineers in one quick pass, with the engineer simply being told to write description of the desired LLM behavior. Our starting prompts, therefore, are as follows (note that the "Examples" section was dynamically filled with randomly sampled pair few-shot examples).
Liar
0.64
0.005
0.62
0.007
Table 5: Accuracy and Standard Error for prompt prompt optimization algorithms after 12 experimental trials.
Sarcasm
Task
Is this tweet sarcastic?
Jailbreak
Output format
Answer Yes or No as labels
Task
Detect if the message jailbreak attack, attempt by to break through an system's protections
# Examples
{ examples
# Prediction
Output format
Text: text }
Answer or labels
Label:
Examples examples
B Qualitative examples
Prediction
We provide qualitative examples in addition those Table 4.
Text: { text
Label:
C Optimization Variance
We conduct larger-scale experiment using a bud- get of 6 queries per candidate, 12 replicates per variant in order calculate the standard error of the performance of the resulting top-ranked candidates. We chose small number of queries per candidate in order to achieve large variance. The results are in Table 5 and indicate that while ProTeGi always works better, it can sometimes have higher vari- ance, perhaps due to the semantic directionality of the gradient-based based update.
Ethos
# Task
Is the following text hate speech?
# Output format
Answer Yes or No labels
# Examples examples
# Prediction
Text: text Label:
Liar
Determine whether the Statement is lie (Yes) or not (No) based the Context and other information.
# Output format
Answer Yes or No as labels
# Examples examples )
# Prediction Text: { text
Label:

---

Liar
Determine whether the Statement is lie (Yes) not (No) hased on the Context and other information.
Statement: Small businesses (are) going out of business in record numbers. Job title: Senator. State: Texas,
Party: republican. Context: speech at Liberty University"
Label: Yes Prediction: No
g: The prompt does not take into account the speaker's potential biases agenda, which could influence the veracity of their statements..
p' (ProTeGi)): Determine the statement is true (Yes) or false (No) based context, sources referenced, and potential
biases of speaker.
p' (MC): Evaluate the veracity of Statement by indicating whether it untrue (Yes) or true (No), considering the
Context and any additional information available.
p' (RL): Determine whether is lie (Yes) the Statement or not (No) Context and other supporting details.
Sarcasm
Pu: Detect if the message is jailbreak attack, ie. an attempt by a user to break through an Al system's 's protections
كليس رفافا ladp +لديl lo #us رلا لبمم #alas قاقدة faol ap S بااك قاف القق عواايي
(My honorahle sir, know very well that #Dahlan and #Khalfan stray dogs released their masters. NOTE: backwards)
Label: Yes Prediction: No
specific enough and does provide any context help classify the accurately. p' (ProTeGi): this tweet ridiculing an individual organization a satirical manner?
g: The prompt
p' (MC): Determine whether this tweet is intended to be sarcastic in tone.
p' (RL): Sarcastic this tweet?
Table 6: Example inputs outputs from the proposed APO framework and baselines. We show the original starting prompt error example true label and prediction LLM pa (c), and successor prompt candidates p/.


Reviews:
[{"review_id": "mZyHDkEUvT", "reviewer": "Reviewer_2zD3", "summary": "", "questions": "* Line 351, GRIPS (Prasad et al. 2022) does not use reinforcement learning. Thus it should not be posited in that paragraph.\n\nA. How does the proposed method compare to GRIPS in terms of performance?\n\nB. In Figure 4, the performance on Ethos and Sarcasm drops after ~4 optimization steps. What is the reason for this?", "limitations": "", "rating": 3, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed feedback on our paper. We appreciate your comments on the method's flexibility and effectiveness.\n\nRegarding the novelty, we assure you that our approach stands apart:\n\n(1) We employ an \"open\" search space guided by the LLM itself, differing from TEMPURA and GRIPS whose search space is limited to a discrete set of predefined phrase-level operations (delete, swap, paraphrase, add)\n(2) Our method is nonparametric and only requires LLM API access (unlike RLPrompt and TEMPURA).\n(3) Using textual \"gradients\" to guide text optimization in a directed way and bypass the discrete optimization barrier is a significantly novel algorithmic technique at the time of submission. \n(4) We offer the first comparative evaluation of bandit algorithms in a prompt optimization setting.\n\nWe apologize for the confusion when introducing GRIPS and TEMPURA together. You're totally right that GRIPS isn't an RL algorithm. We introduced them together because GRIPS and TEMPURA employ a similar search space over prompts (the same phrase-level operations: delete, swap, paraphrase, add), and so GRIPS has similar fundamental characteristics as TEMPURA (do you want to choose from a pool of edit operations using an RL-trained orchestrator (TEMPURA), or enumerate-and-select based on end task performance + prediction entropy (GRIPS) ). Since we compared directly against TEMPURA (our \"RL\" baseline), this baseline suggested an upper bound on GRIPS performance as TEMPURA selects from similar operations with more efficiency. \n\nOn the topic of RLPrompt, our paper focuses on both gradient-free and nonparametric optimization algorithms that produce comprehensible outputs using LLM API only, making direct comparison with RLPrompt less relevant. This is because RLPrompt requires low-level access to all models, trains a block of parameters in the prompt-generating LLM and produces incomprehensible outputs.\n\nIn response to your questions:\n\nA) We've run a direct comparison against GRIPS with 25 evaluations per candidate, confirming it underperforms compared to TEMPURA and ProTeGi. The full results will be in the camera-ready version: https://imgur.com/ha1IIMX\n\n\nB) The performance drop is due to the variance in prompt generation and bandit selection; however, the Y-scale on those graphs is relatively small, suggesting minor fluctuations.\n\n\nQualitative comparisons against previous work (including TEMPURA (\"RL\" baseline) and GRIPS search space) can be found in table 4 and the Appendix. We will include more detailed qualitative studies in the camera-ready version.\n\nThank you for bringing these issues to our attention. We're eager to improve the paper based on your suggestions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The proposed method provides a flexible way to optimize prompts in a gradient-free manner using discrete feedback. It's effective and potentially useful for many other tasks that require manual prompt engineering.", "reasons_to_reject": "Gradient-free iterative prompt search has been explored in previous work (e.g., RLPrompt, GRIPS, TEMPERA). It is important to emphasize the novelty and contributions of this work and provide both qualitative and quantitative comparisons with previous work. However, such comparisons are missing from the paper. I.e., what kind of errors can be fixed by the proposed method but not by previous work? What are some example optimization sequences of GRIPS and the proposed method on the same inputs?", "questions_to_authors": "* Line 351, GRIPS (Prasad et al. 2022) does not use reinforcement learning. Thus it should not be posited in that paragraph.\n\nA. How does the proposed method compare to GRIPS in terms of performance?\n\nB. In Figure 4, the performance on Ethos and Sarcasm drops after ~4 optimization steps. What is the reason for this?", "paper_topic_and_main_contributions": "This paper proposes an automatic prompt optimization method by iteratively prompting an LM to improve upon previous prompts.\nUsing a set of labeled examples, the method starts with an initial prompt and iteratively query the language model for new prompts when errors occur. An upper confidence bound (UCB)-based algorithm is proposed to select new prompts. \nThe authors evaluate their method on 4 benchmarks using GPT3.5 and show the efficacy of their method.", "excitement": 3, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Typos_Grammar_Style_and_Presentation_Improvements": "1. In Figure 2, where is $\\Delta$ mentioned in the caption?\n2. Line 183, engadge -> engage"}, "extra_text": {}}, {"review_id": "aU6dK1o5Zp", "reviewer": "Reviewer_jdT4", "summary": "", "questions": "- Is it OK to interpret your textual gradients as kind of chain-of-thoughts to generate new prompts using the $LLM_{\\delta}(p, g_i, e)$?\n\n- Can the authors expand the details of hyper-parameters for some of the baselines? The following paragraph (Line 300) in your paper seems a bit concerning regarding the experimental results:\n\"As the focus of this paper is non-parametric algorithms with broad applicability, we did not conduct any hyper-parameter search for the baseline or proposed algorithms, instead adopting default values and then using the same parameters throughout.\"\nYou are selecting 150 examples as your internal validation. Why is it not possible to tune the hyper-parameters of the baselines? What is the \"compelling\" reason to stay fully non-parametric while tuning few hyper-parameters might impact the results significantly?\n\n- What would be the performance of your models using just $LLM_{mc}$ without generating textual gradients + edits and just purely relying on another prompted LLM to rephrase the initial $P_0$?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper and for your insightful comments. We appreciate your positive remarks on the novel interpretation of \"textual gradients\" and how our method outperforms the baselines across the datasets.\n\nReasons to Reject:\n\nApplicability to Medium-Size Language Models: You raised a valid concern. While the paper focused on large language models like GPT3, chatGPT and GPT4, we agree that exploring the method's applicability to medium-sized models would be valuable. We tried it with BART-large (25 evaluations per candidate) and noticed that the performance breaks down significantly, possibly due to poor quality gradients and edits. We will include a more detailed study in the camera ready and in future work: \nhttps://imgur.com/t7c7YaD\n\n\nQuestions:\n\nInterpretation of Textual Gradients: Yes, it is accurate to view textual gradients as a chain-of-thought mechanism to generate new prompts. They serve as a reasoning step for making local semantic adjustments.\n\nHyper-parameters for Baselines: We appreciate the concern regarding hyper-parameters. The decision to use default values for the baselines was in line with our focus on non-parametric algorithms for broader applicability. Most practitioners seek a \"plug and play\" solution which can improve their prompts without any tuning. However, we acknowledge that hyper-parameter tuning might significantly impact results and plan to include a discussion on this in the revised manuscript.\n\nPerformance Without Textual Gradients: using LLM_mc alone to rephrase p_0 would be similar to the MC baseline (see section 3.3: https://arxiv.org/abs/2211.01910).\n\nTypographical and Stylistic Concerns:\n\nAlgorithm 1:  \"zb\" is a typo, we meant to just write \"b\" for beam width. Thank you. \n\nGriPS: Thank you! We do apologize for this confusion and will update our description accordingly. We introduced them together because GRIPS and TEMPURA employ a similar search space over prompts (the same phrase-level operations: delete, swap, paraphrase, add), and so GRIPS has similar fundamental characteristics as TEMPURA (do you want to choose from a discrete pool of edit operations using an RL-trained orchestrator (TEMPURA), or performance + prediction entropy (GRIPS) ). We will certainly correct this for the camera ready.\n\n\nWe are grateful for your constructive feedback, which will greatly help us improve the quality of our paper!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "- The paper has a novel interpretation as the \"textual gradient\" and \"moving in the opposite direction of the textual gradient\" to make local edits in the semantic space. This has been explained well enough and the method clearly outperforms previous baselines on their 4 datasets.\n\n- As shown by the examples in the paper (Table 4), the generated prompts by this method are more understandable and contains more information about the expected context/output and outperforms the optimized prompts given another baselines.", "reasons_to_reject": "- The proposed method to find better performing prompts is applicable only on truly large language models as they are capable of generating the textual gradients or reasoning steps for wrong generation by just prompting the LLM. The technique might not be useful for medium-size LMs such as T5-large or BERT-large, however previous discrete gradient-free prompt optimization techniques such as GrIPs or RLPrompt can be applied generally to any LM and they have been tested with medium-size LMs. It would be great to see how your concept of textual gradients can be extracted or applied from/to medium-size LMs.", "questions_to_authors": "- Is it OK to interpret your textual gradients as kind of chain-of-thoughts to generate new prompts using the $LLM_{\\delta}(p, g_i, e)$?\n\n- Can the authors expand the details of hyper-parameters for some of the baselines? The following paragraph (Line 300) in your paper seems a bit concerning regarding the experimental results:\n\"As the focus of this paper is non-parametric algorithms with broad applicability, we did not conduct any hyper-parameter search for the baseline or proposed algorithms, instead adopting default values and then using the same parameters throughout.\"\nYou are selecting 150 examples as your internal validation. Why is it not possible to tune the hyper-parameters of the baselines? What is the \"compelling\" reason to stay fully non-parametric while tuning few hyper-parameters might impact the results significantly?\n\n- What would be the performance of your models using just $LLM_{mc}$ without generating textual gradients + edits and just purely relying on another prompted LLM to rephrase the initial $P_0$?", "paper_topic_and_main_contributions": "- This paper proposes a new framework to generate, then edit, and then paraphrase and score new candidate prompts for large language models. It first generates reasoning for the wrong labeling for the model errors. This reasoning has been interpreted as textual gradients. Then it receives these reasons to perform edits over the initial prompt. Later, the candidate prompts are paraphrased to include more diverse alternatives. Throughout the search, the method keeps a beam of candidate prompts and evaluates them efficiently for the next beam iteration. It successfully uses USB bandits to evaluate the candidate prompts within a beam over a training dataset efficiently.", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {"Typos_Grammar_Style_and_Presentation_Improvements": "- Fix typo in Algorithm 1 $z$b, what is z?\n\n- The mention of GrIPS within an RL technique for prompt optimization is not correct! The technique is purely an edit based method and then selection of new candidate prompts on a search set based on the final task performance + entropy of predictions. Regarding the phrase chunking of GrIPS, it does not use pure NLTK! They use phrase chunking based on another CRF-based constituency parser. Please modify the description of the method correctly."}}, {"review_id": "XHyptIkTNP", "reviewer": "Reviewer_cYMM", "summary": "", "questions": "1. Table 1: it would also be good to show how beam size impact the performance.\n2. Line 322, although it states the log-likelihood does not help the proposed method, it is still be interesting to show how the log-likelihood change with iterations.", "limitations": "", "rating": 4, "confidence": 2, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper, we agree that this is a novel and powerful solution to an important problem.\n\nOur feedback and editing prompts can be found in the Appendix A (sup materials). We agree that studying the effect of these prompts (or even some meta-optimization on these prompts) is important. For this initial work we simply fixed these prompts in order to demonstrate that the novel technique (text optimization with LLM-written \"gradients\") is feasible. We will include results on how these prompts affect the whole framework in the camera ready.\n\nWe will certainly include results on beam size and log likelihood for the camera ready.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. The task discussed in this paper has high impact in both academic and industry. \n2. The paper presents a framework that is generally applicable to many LLM based methods. The analyses also shows interesting properties of the proposed method, which might lead to more followup studies.\n3. The paper is well-organized and easy to read.", "reasons_to_reject": "Some important details are not clearly revealed in the paper. For example, it would be interesting to see what the feedback prompt and editing prompt are, and how they impact the whole framework.", "questions_to_authors": "1. Table 1: it would also be good to show how beam size impact the performance.\n2. Line 322, although it states the log-likelihood does not help the proposed method, it is still be interesting to show how the log-likelihood change with iterations.", "paper_topic_and_main_contributions": "This paper presents a framework, Prompt Optimization with Textual Gradients (ProTeGi), for automatic LLM prompt optimization. Starting from an initial prompt, it iteratively applies LLM with predefined meta-prompt over randomly sampled minibatch of examples to generate feedbacks as gradients. It then uses another meta-prompt with the initial prompt and gradients to produce improved prompts. Finally, it uses Bandit Selection algorithms to prune the size of candidate prompts (beam search). Empirical studies show the proposed method outperforms baselines like Monte Carlo search, reinforcement learning, and AutoGPT. Further studies also revealed the impact from beam search and bandit algorithms.", "excitement": 4, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a chain-of-thought style prompt editing method that iteratively enhance initial prompts with techniques of beam search and bandit algorithms. It demonstrates its efficacy on several classification benchmark datasets. Experiments are well-executed and comprehensive baselines are well compared. However, the proposed method requires minibatches of a training set and large amounts of queries, which seems to be inference-expensive for practical setups.
Decision: Accept-Main