Localized Zeroth-Order Prompt Optimization
Authors: Wenyang Hu
Yao Shu
Zongmin Yu
Zhaoxuan Wu
Xiaoqiang Lin
Zhongxiang Dai
See-Kiong Ng
Bryan Kian Hsiang Low
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Prompt Optimization
Large Language Models
LLM
Instruction Optimization
Primary area: natural_language_processing
TL;DR: We propose a principled local optimization method to optimize the discrete prompts for black-box LLMs that outperforms all baseline methods in performance and efficency. .

Abstract: The efficacy of large language models (LLMs) in understanding and generating natural language has aroused a wide interest in developing prompt-based methods to harness the power of black-box LLMs. Existing methodologies usually prioritize a global optimization for finding the global optimum, which however will perform poorly in certain tasks. This thus motivates us to re-think the necessity of finding a global optimum in prompt optimization. To answer this, we conduct a thorough empirical study on prompt optimization and draw two major insights. Contrasting with the rarity of global optimum, local optima are usually prevalent and well-performed, which can be more worthwhile for efficient prompt optimization (**Insight I**). The choice of the input domain, covering both the generation and the representation of prompts, affects the identification of well-performing local optima (**Insight II**). Inspired by these insights, we propose a novel algorithm, namely localized zeroth-order prompt optimization (ZOPO), which incorporates a Neural Tangent Kernel-based derived Gaussian process into standard zeroth-order optimization for an efficient search of well-performing local optima in prompt optimization. Remarkably, ZOPO outperforms existing baselines in terms of both the optimization performance and the query efficiency, which we demonstrate through extensive experiments.

Localized Zeroth-Order Prompt Optimization
Wenyang Hu*t', Yao Shu Zongmin Yut, Zhaoxuan Wu Xiaoqiang Lin", Zhongxiang Dait, See-Kiong Ng Bryan Kian Hsiang Low Dept. of Computer Science. National University of Singapore, Republic of Singapore! Institute of Data Science, National University of Singapore. Republic of Singapore Guangdong Lab of AI and Digital Economy (SZ)
Singapore-MIn Alliance for Research and Technology, Republic of Singapore School of Data Science, The Chinese University of Hong Kong, Shenzhen wenyang hu@u. mus nus. shuyao@gml ac fyuzongmin, wu. zhaoxuan, xiaoqiang. @in]@u... nus edu daizhongzianggeuukk edu, cn, seekiongênus edu. sg, lowkh@comp nus. edu ag
Abstract
The efficacy of large language models (LLMs) in understanding and generating natural language has aroused wide interest developing prompt-based methods to harness the power of black-box LLMs. Existing methodologies usually prioritize a global optimization for finding the global optimum, which however will perform re-think poorly in certain tasks under budget constraints. This thus motivates the necessity of finding a global optimum in prompt optimization. To answer this, we conduct thorough empirical study on prompt optimization and draw two major insights. Contrasting with the rarity of global optimum, local optima are usually prevalent and well-performed which can be more worthwhile for efficient prompt optimization (Insight I). The choice of the input domain, including both the generation and the representation of prompts, affects the identification well-performing local optima (Insight II). Inspired by these insights, we propose novel algorithm, namely localized zeroth-order prompt optimization (ZOPO), which incorporates a Neural Tangent Kernel- -baeed derived Gaussian process into standard peroth-order optimization for an efficient search of well sell-performin local optima in prompt optimization. Remarkably, ZOPO outperforms existing baselines in terms of both the optimization performance and the query efficiency, which we demonstrate through extensive experiments. Our implementation is available at stttps://gis /gttttttthh...../ggg com aammmaaale44747/000
Introduction
Large language models (LLMs)) have demonstrated remarkable capabilities for understanding and generating natural languages (27 41 45). Thanks to the instruction-follwwii abilities of LLMs (28,
coanpting-adding crafted, discrete prompts, namely natural language text, the input emerges as an effective and lightweight approach to direct LLMs to generate specific, desired responses (20 21). Such approach is of particular interest when
interact with state-of-the-ar LLMs like ChatGPT 25 and GPT-4 244. which can only be accessed through black-box APIs (i.e., the interface of black-box L.LMs only accepts discrete texts input). So, prompt optimization becomes critical effort in pursuing the optimal performance of black-box LLMs on downstream tasks.
Although human knowledge may subjectively guide prompt designs 32], this process is commonly time-intensive and its results are not always desirable in practice. To mitigate such human efforts
Equal contribution.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

and achieve better performance in optimizing crafted prompts, random sampling [48] Bayesian optimization B [8], and evolutionary algorithms [TO] have been proposed to generate and select well-performing prompts automatically. However, most of these existing strategies prioritize global optimization, dedicating substantial portions of the query budget to explore the entire search space for the global optima and consequently making it query-inefficient in practice. Meanwhile, these strategics typically implement their prompt optimization across various input domains (i.e., natural texts 110 [8] or hidden embeddings [3 (8), ) resulting in diverse performance outcomes in practice. These results consequently inspire us to re-think the questions about the necessity of finding a global optimum and the essence of the input domain for efficient and effective prompt optimization.
To answer these questions, we provide a thorough empirical study on prompt optimization. Firstly, we visualize the performances of some randomly sampled prompt candidates on various tasks to show that, in contrast to the scarcity of global optima, local optima are commonly prevalent and perform reasonably well, making them more valuable for query-efficie prompt optimization (Insight in our Sec. ). Secondly, we visualize the estimated accuracy distributions for a number of prompt candidates and the corresponding function surfaces using various embeddings their representation. The results demonstrate that the selection of the input domain, including both the generation and representation of prompt candidates, will influence the identification of nigh-perrforing prompts, especially those local optimal ones (Insight II in our Sec. 3.2). These insights consequently highlight the importance of local optima and input domain for efficient and effective prompt optimization.
Inspired by these insights, we novelly propose the Localized Zeroth-Order Prompt Optimization (ZOPO) algorithm for a considerably improved prompt optimization as evidenced by Fig. T Moti- vated by Insight II, we first propose a general domain transformation that utilizes L.MSs for prompt generation and existing embedding models for transforming these generated prompts into their corre- sponding hidden representations, which thereby enjoys not only the remarkable generation ability from any type of LLMs (white/black-box: but also the impressive representation ability from existing embedding models for our prompt optimization (Sec. J. Inspired by Insight we then leverage cutting-edge zeroth-order optimization (ZOO) method enhanced by derived Gaussian process for efficient gradient estimation 33 to underpin our localized prompt optimization, which goes one step further by incorporating the Neural Tangent Kernel (NTK) [12 to handle the complex and high- dimensional prompt optimization tasks [.2). Lastly, we present an uncertainty ievertaitt--iformeed local exploration method designed improve the gradient estimation in our derived NTK-GP framework, thereby augmenting the practical performance of the ZOPO algorithm (Sec.
To summarize, the contributions of our work include:
To the best of our knowledge, we are the first to conduct a thorough empirical study in prompt optimization to underscore the value of local optima and the essence of input domain for efficient and effective prompt optimization (Sec.B)
Drawing on the insights gained from our empirical study, we design the ZOPO algorithm (Sec. 4
which outperforms existing baselines in optimization performance and query efficiency.
We conduct extensive studies to confirm the efficacy of our algorithmic framework and elucidate the underlying principles or insights of our ZOPO algorithm (Sec. 5
2 Problem Setup
Given an NLP task that characterized by a data distribution DD and a black-box LLM f(-), e.g.. ChatGPT 25 discrete prompt optimization aims to generate piece of human-readable text, namely the prompt v, which will then be applied to the black-box LLM f()) along with a test input a such that the queried LLM output [[er; ær]) is able to correctly predict the ground-truth label y for each (x. y) ~ D. This problem is then commonly framed as a black-box maximization problem over the discrete language input domain Ω 18]:
max F(b) A B(aa)EDD [R (f((e: v) eE
(1)
where R (f([v; y) is applied to measure the alignment between the LLM output [(w===) and the groundtruth y. and Dy is the validation set sampled from D. Note that the performance of the optimal instruction found on Dy (i.e., arg max, F())) will be evaluated on a held-out test set Dr.

---

Ieenazlem
tuxonomy animal
cause and effect
informal formal
1.0
0.75
INSTINCT
Deshangt
0.50
OPRO
0.5
70PO (exn)
0.25
0.0
10
20
Figure 1: The performance profile for dif- ferent methods on 20 tasks. A higher p(T) is better. More details in Sec.
Figure 2: The validation accuracy of 300 randomly sampled prompts with the last token representation various tasks.
3 Empirical Study on Prompt Optimization
3.1 Local Optima vs. Global Optimum
In prompt optimization, methods like [3 18) are generally more effective than the others 10 48).
which is usually contributed to their usage of Bayesian optimization, a popular global optimization strategy, that is able to find the global optimum in low-dimensional problems (22). However, these methods will perform poorly in certain prompt optimization tasks, e-g.. cause and_effecd and inf informal_tae soslllttffrrmri formalll from [II, indicating that they typically fail to find the global optimum in these tasks given limited query budget. This likely because substantial portions of the budget are wasted in these methods to explore the entire search space for the global optimum. However, is it really necessary to find the global optimum in query-efficient prompt optimization?
To answer this question, we have employed a 3-dimensional scatter plot to visualize the performance (differentiated by colors) for 300 randomly sampled prompt candidates on various tasks, whose prompt embeddings (i.e., the last token embedding as in (8) are reduced by t-distributed stochastic neighbor embedding (I-SNE) (see more details in our Appx. D.I.I). The results are in Fig. 2 which shows that the global optimum (i.e., the points achieving the highest accuracy) is consistently rare for a range prompt optimization tasks, making it extremely challenging achieve this global optimum in practice. In contrast, prompt optimization often features a number of local optima (e.g.. the points achieving accuracy higher than 80% in taxonomy caxonomy_animan amnimll Fig. 2]. Importantly, these local optima commonly enjoy relatively good performances, suggesting that local optima shall be more worthwhile obtain in prompt optimization, especially for the scenarios of limited query budgets, summarized below.
Insight
In contrast with the rarity of global optimum, local optima are usually prevalent and well-performed, which is more worthwhile for query- prompt optimization.
3.2 Essence of Input Domain
Besides, existing works R 10, 18 typically implement their prompt optimization across various input domains, leading to a wide range of performances in practice. These results thus inspire to ask: How essential is the input domain for finding well-performing prompts, particularly the local optimal ones? Thoroughly exploring this question is fundamental for the design of well-performing prompt optimization algorithm.
To answer this, we first visualize the accuracy distributions of 300 prompt candidates that are randomly generated by Vicuna-I5 13B and ChatGPT for various tasks to study the essence of prompt generation in Fig. (more details in Appx. D.1.2). Fig. reveals that the prompt candidates produced by ChatGPT (a black-box model) generally exhibit better performance than those produced by Vicuna-13B (a white-box model), which has been widely applied in 3 [8 for prompt optimization. Importantly, ChatGPT demonstrates a greater likelihood of generating locally optimal prompts (e.g., the ones of accuracy higher than 0.8 in taxonomy maxonomy_animal
animal of Fig. 3). These results indicate that the ability to
3

---

taacoomy animal
casse and stfect
informal formal
taxonomy animal
cause andde_anddee informal to
0.8
08
0.5
on
bn
64
0.6
Validation Ausunay
Figure 3: The validation accuracy distribution of prompts generated by Vicuna-13B or Chat- GPT on various instruction induction tasks, where the vertical dotted line is the mean per- formance.
SSBER
0.2
0.0
Figure 4: The function surfaces using the last token (Vicuna-13B) or SBERT embedding.
generate well well-performing local optima in prompt optimization usually varies for different models. So, the selection of the prompt generation model is crucial for finding well-performing optima.
We then investigate the function surface (i.e., accuracy landscape) using two different embeddings for prompt candidates in Fig. (more details in Appx. D.1.2) where the embeddings are mapped into a 2-dimensional domain using the t-SNE for better visualization. Interestingly, Fig. 4 unveils that different embeddings will convey varying number of pell-performing local optima in practice. Particularly, the last token emhedding is usually able to produce a larger number of well-performing local optima than the SBERT (i.e., popular sentence embedding transformer (3T) embedding, making it easier to enjoy good prompt optimization performance on this domain, as validated in Tab. 8 This therefore implies that the choice of the prompt embedding model also essential for the finding of well-performing optima. In all, we conclude our aforementioned insights as below.
Insight II
The choice of the input domain, including both the generation and the representation of prompt candidates, affects the identification of well-performing local optima.
4
The ZOPO Algorithm
Given the insights established in our Sec. we then propose Localized Zeroth-Order Prompt Optimization (ZOPO) algorithm (Algo. for better-performing as well as more query-efficient prompt optimization. Specifically. following Insight II. first develop mation for the imput domain of prompt optimization (Sec. 4.J).. which can enjoy both the remarkable generation ability from any type of LLMs (white/black-bork and the impressive representation ability from many NLP models. Subsequent to this transformation, inspired by our Insight I, we propose to use zeroth-order optimization (ZOO) with derived NTK Gaussian process inspired from (36) to find well-performin local optima (Sec. 4.2). Lastly, we introduce an uncertainty-inforoe
general transfor-
local derived NTK Gaussian process, aiming
exploration technique to refine the gradient estimation to enhance the performance of our ZOPO algorithm in practice (Sec. 4.3
4.1 A More General Input Domain Transformation
As introduced in our Sec. 3.2 the choice input domain (including the generation and representation of candidates) significantly influences the ultimate performance in prompt optimization: Black-box LLMs (e.g.. ChatGPT) typically enjoy an advanced generation ability and different embedding models (e.g., SBERT) have varying representative capacity for prompt optimization. This naturally inspires us to develop an improved domain transformation that can utilize not only the remarkable generation ability from whitc/black- box LLMs but also the impressive representation ability from certain NLP models for our prompt optimization. To achieve this, we propose to make use of the prompt v e Ω generated from LLM g(-) and subsequently transform it into continuous hidden representation
E Z C Rd by other sentence embedding model h(-) for the optimization, i.e., h (z), where ①1) can then be re-framed as
F(z) E (x,y)E
[R

---

Algorithm The ZOPO Algorithm
1: Input: the prompt generation model g(),, the prompt embedding model h(-), size of prompt
candidates m, iteration number T, prompt candidate set 0. prompt embedding set Z
2: repeat
3: V + ([Demm))) )
4: 2 < h(v)
5: i & V then V VU(o), - 2U(²}
6: until [V] m
7:
for = to T do
8:
if A (=))
then do uncertainty-informed local exploration in Sec. 4.3
9: 2++1 = Pz(ze + +x))
10: Query 2+11 to yield F(2+1)
end for
12: 2" f arg max F(2)
13:
Return h- (x')
Of note, input domain transformation and (2) enjoy number of major advantages compared with previous works: (a) Different from the direct optimization over the discrete and complex language space 52 [10] where optimization algorithms in the numerical domain can hardly be applied,
our transformed input domain leads to dense numerical space of lower dimension and therefore allows the usage of
optimization algorithms for (2) (e.g., our Algo. [T. (b) Different
from the potential many-to-ons mapping in the previous works [ 18) i.e., the same discrete prompt may be generated by various continuous soft prompts s, we develop one-to-one mapping where one prompt generally has a unique hidden representation which thus can help eliminate the redundant queries during optimization and ultimately lead more query-efficient prompt optimization. (c) Our domain transformation with an independent generation and representation process is capable of enjoying the remarkable generation ability from any type of LLMs (white/black-bor -box) and the impressive representation ability from many embedding models whereas previous works are highly restricted to the LLMs, thus leading to wider application.
Practical Implementations. Before the start of the optimization on 2 we usually generate numerous prompt candidates = {r} and their corresponding representations 2 (=) (line 2-6 of Algo. 1 where can be produced by an embedding model h((.) We store (z, u) in key-value pairs considered here
for constructing the one-to-one inverse mapping h (-). Two practical methods for prompt generation: (a) Feeding randomly sampled soft prompts E Rd and few demonstrations Doemo into a white- box LLM g(-). (b) Sampling the output distribution of a black-box LLM g(-) given generation template filled with Daemo- Specifically, if we consider the generation method in (a), 2 can be chosen as the last token embedding from g(-) [18] or the soft prompt s B when
generating v. Here h(.) then represents mapping function from
4.2 Local Optimization with Derived NTK-GP
As local optima are more prevalent than global optimum and can exhibit compelling performance for prompt optimization tasks (Sec. (.1). propose to apply zeroth-order optimization (ZOO), particu- larly gradient descent using estimated gradients, for a well-performing local prompt optimization on our transformed input domain Z in Sec. 4.1 Unfortunately, existing ZOO algorithms are typically query-inefficient many additional queries are required for gradient estimation in every gradient descent update
23 In light of this, we resort to the most recent ZoRD algorithm [6) where
localized surrogate model will be applied for query-efficient gradient estimations.
According to 36 given well-specified kernel function k(,,)) such that the function F is sampled from Gaussian process F (O k)) alternatively ming-sP(0. max,Ez [F(z) G(z) = and the observed value of function F follows the Gaussian noise (N g²), then conditioned on the history of function queries D, & [(Er, ) of size t, VF follows derived
5

---

Gaussian Process ((;, i...
VF GP
(3)
in which the mean function (-) and the covariance function ()) are defined as
(z) - kx(2) T (K, + +021) + Te,
(4)
>, (2, 2') - k" (z, z') kx(2) (K, + + ko(z').
Here, kx(2)T A [0, 2, 2 - is d x t-dimensional matrix, Ke & [k((rr k(zz) i
dimensional matrix, ri - [r>] is t-dimensional column vector, and k" k" 22) & 0,0g, 2') is d x d-dimensional matrix. As result, (z) can be applied to estimate the gradient of the black-box function F at input
Of note, the underlying black-box function F here is highly related to deep neural networks (DNN), more specifically transformers. naturally inspires us to apply the Neural Tangent Kernel (NTK) [12 theory for better approach to the aforementioned assumption of well-specified kernel function k..,). This is because has been widely proven that NTK is capable of well characterizing the predictions of neural networks [2 34 335 and therefore should be better-specifier kernel in the setting of prompt optimization than the simple kernel (i.e., Matérn kernel) applied in ZoRD [3].. Specifically, given neural network (00, z) parameterized by 0 E RP, we employ the following
empirical NTT as the kernel in (3) and 4
2(2,z') Veń(0,2) Voo(O, (V,0) 2)
(5)
8=60
where dg is the initialized parameter of neural network ø. By incorporating the derived NTK-GP for the gradient estimation in our prompt optimization.
(5) into 44. we realize
Based on this derived NTK-GP, finally apply standard first-order optimization (e.g., stochastic gradient descent) with projected gradients for our local prompt optimization. Specifically, in every iteration of our Algo. the next promising prompt candidate will be selected via:
Ut+1 h (Pz(z (2)4(2))))
(6)
where Pz(=) - arg min || - ='Il is the projection function that projects the updated z Rd into domain 2 and 7/1 is learning rate.
Practical Implementations. Following the localized modeling principle, only the neighbors 2 in the query history D, used to caleulate the gradient (=)=).. As do not know the exact DNN for the underlying black-box function F, we propose to approximate it using a small DNN, which can work well thanks to the theoretically guaranteed universal approximation ability of DNNs [4 33 Our experiments in Sec. 5.3 will further validate the effectiveness of this implementation.
4.3 Eicertaintt-Informeet Local Exploration
Though the derived NTK-GP allows us to estimate the gradient at any 2 according to (6). we introduce the following Prop. D to demonstrate that the error in gradient estimation at a specific input E Z implies considerable variability, which is strongly correlated with the number of historical queries that are effectively relevant for the gradient estimation at the specific input z E Z. This insight, in turn, motivates the creation of our uncertainty -nnfoommd local exploration approach, opposed to the adoption the virtual update mechanism described in [36] for our prompt optimization strategy.
Proposition 1. Assume k(z, 2') S a and [IK"(z, 2)Il S K. for any z, z E Z. Let å E (0, 1) and Nz.9 A {=' E {-y) probability of at least 1 -8.
(0,,((",=))1'' 2 B} for given imput z E 2, the following holds with
w3/d
[mx(2)
) z w |+)| wK a 02 N
where w d 2(Vd 1) In(18)) and (2) A (2)

---

Table I: Average test accuracy with standard error (3 runs) for different methods on 20 instruction induction tasks. We bold the highest accuracy when comparing ZOPO with baselines, and use green cell to highlight the highest accuracy when comparing ZOPOGpT with baselines.
Tisks
APE
InstruciZero
INSTINCT
EvoPrompt
PB
OPRO
ZOPO
ZOPO
antonyms
63.7 63.7
82.7=0.7
84.7
84.020.0
78.0=a.
79.0-2.2
88.2
84.0z14
auto, categurization
25.0+00
25.7
25.0g3.
31.011.
24.0_a.7
24.0_a.6
32.7-1.9
27.0.500
auto dehugging
20.2+1.4
37.5-0.00
20.2+3.4
33.0+1.2
25.0=0.0
37.5-0.0
41.7-15.6
29. 29.2=5.9
cause and effect
57.3g5.
$13311
58.7
84.0.18.9
82.7-100
82.7=1000
94,7-a.1
80.0-142
common, concept
6.
8.611
21.3.97
11.1169
10.9_a.4
8.6137
23.5.a.4
2,8.06
diff
67. 67.3
69.31222
100.010o
27.31422
7133_27
100.0
100,0100
100.0.0.
informal_u formall
57.41oa
58..1
55.
51.6go.
54.2
48.0_n.
61.3g2.7
(1.2229
lotters_ list
100.0
19.0
100.0100
100.0
99.3_
99.7 .0.5
100.0
100.0...
negation
75.3+
77.7=1.4
$1.7=0.a
86.0=a.0
70.7=4.0
73.3
86.3
77.7=2.6
object_counting odd out orthograph__ste __stariss with
36.321.
36.0g9.3
34.0=7.
35.0
20.3=1.2
36.0
52.3
40.3
63.3+1.4
6l.3=s.7
70.0
10.0
-0.7-a.9
47 42.3-2222
32.0+11.5
68.7=23
45.7214.8
50.7
66.722.7
15.0aa.4
59.8
33.5-146
56.5+12.
71.0z00
thymes
15.7
100.01c.0
100.0100
39.723.1
45.0_1077
23.7
100.0100
61
second word letter
74.7 14.7
43.3
10.014.1
21.7108
88,7 88.7_104
86.7 189
25.7
96.7 224
sentence siceneesimilartty
0.D....0
0.0100
14.0
2.0g10
0.0.a0
2.7
T.61933
37 .7.
sum
67.31
100.0
100.0
100.0
98.3 1.T
100.0 100
100.0
10000
synonyms
36.0+74
27.7
30. 30.7
40.3
36.3-3.
40.0-4.8
43.3-n.9
44.7=4.1
taxonomy animal
34.7=28.4
T1.7=8.4
85.7
83.0+4.6
29.7=a5.5
30.0=41.0
90.0-7.1
92.320.5
word_son _orttiningg
33.0+37
31.0:114
613300
48 48.0+21a
46.7-1.7
50.3-6.8
60.0
60.3 60.3=s.1
word unserambling
44.0g18.
55.0e17
63.320,7
51.3
51.026.2
61.3-2.1
59.3g2.
58.321.
The proof is given in Appx. A Here, 22,3 denotes a set of historical input queries that are effectively
relevant for the gradient estimation at z where /3 can be regarded as a measure of effective relevance.
Prop. 1 shows that the gradient estimation error of (3) at specific input E 2 is bounded by the norm of covariance matrix 2 (z), which is related to the query set N2.3 of effective relevance. Specifically, the gradient estimation error at different varies if the effective relevance 3 and the number relevant queries |N varies with z. When 3 or |Naal becomes small during ZOO, the gradient estimation error is likely increased, which will lead to poor performance in practice. This likely will happen in prompt optimization especially considering the sparsity of prompt candidates w.r.t. the continuous domain Rd. That is, both the effective relevance 3 and the number of relevant queries |N2,| can be small due to this sparsity. As a consequence, additional input queries should be conducted to increase both B and [N for better-performing prompt optimization.
To this end, we propose an uncertainty-informe local exploration method that utilizes additional input queries from local searches to reduce predictive uncertainty and hence the gradient estimation error in derived NTK-GP according to Prop. [ informed by the local trajectory:
Specifically, we propose the local exploration condition
A2) - 1 E Ar 2t $ At
where A, = (2.)o()))))) A, Vi E [0,E]] is the condition that incorporates uncertainties and X, the thresholds. If this condition is met (i.e., x (z+) = 1), will query the neighbors of 2; in the local region to update our derived NTK-GP, thus improving its gradient estimation.
Practical Implementations. If define the set of the n nearest neighbors of M, C Z s.t. [ n and Va E 2 We, ||a - 24|l 2 maxbEA, b|b zell. we propose to query each E M, in the local region, whenever A. (2r) = 1.
5 Experiments
In this section, we perform prompt optimization for ChatGPT (i.e., the black-box LLM f(-) with limited query budget of 165. We evaluate the performance of ZOPO against several strong baseline
methods, including APE [8%] InstructZero [3], INSTINCT [8] EvoPrompt [10] PromptBreeder
(PB) [8), and OPRO 46 on 30 instruction induction tasks [ 3 arithmetic reasoning tasks A [9
29,, and the GLUE benchmark [42). The task-specific prompt is optimized for each task independently.
We use the performance profile (7), defined in Appx. C.I the overall evaluation metric that
measures the frequency (i.e., p(T)) of a method within some distance (i.e., 7) from the highest
accuracy achieved by any method. We defer more experimental details to Appx. C
7

---

5.1 Instruction Induction
Instruction induction tasks are commonly used to investigate the prompt optimization performance by assessing LLM's zero-shot in-context learning ability in previous works [3] 18] 48]. Although our ZOPO is a general prompt optimization method given any prompt generation strategy, here we follow the same setting of prompt generation from INSTINCT and InstructZero, only for fair comparison. We also adopt the last token embedding from Vicuna-13h as the prompt embedding (same as INSTINCT). Here Vicuna-133 is used to generate task-specific prompts by feeding random soft prompts. More experimental details are deferred to Appx.
Superior performance of ZOPO. For better distinguishability. we follow the experimental setting from Lin et al. [8] to display the results on 20 challenging tasks reported in Tab. TT, where ZOPO significantly outperforms all baseline methods. Particularly, our ZOPO performs the best in 14 out of the 20 tasks presented, while achieving the best performance profile across different (see Fig. T compared with all baseline methods. For more results on all 30 tasks, refer to Tab. 3 in Appx. D.2 where the ZOPO consistently outperforms existing methods.
Connecting ChatGPT with ZOPO. With our proposed domain transformation, we empirically demonstrate that ZOPO is capable of performing numerical optimization on ChatGPT-generated prompts. Specifically, we use the same generation method as in APE 48 to generate task-specific prompts (i.e.. v) from ChatGPT, and use a popular embedding model SBERT to provide the cor- responding sentence embeddings (i.e., 2) for V. Then we apply ZOPO to perform optimization over the given V and 2, which we name ZOPOspT. The result of ZOPO compared against other baselines is shown in Tab. [] with the corresponding performance profile shown in Fig. in App. D.2 Fig. 9 demonstrates that ZOPOGpT significantly outperforms other baselines, achiev- ing the best performance in 10 out of the 20 tasks as shown in Tab. [ Specifically, ZOPOapT achieves significantly higher accuracy on some challenging tasks such as second_ saaedd_wod__eeeeeeeeeddeeeeeeeee and sentence lincce__sinm www.simmlaa similarity, which we attribute to the high-quality of prompt candidates generated by ChatGPT. This is also consistent with our discussion on the input domain in Sec. 3.2 Here we could not draw direct comparison between ZOPO and ZOPOGPT. as the Vicuna last token embedding is specifically associated with the prompt generation process in ZOPO and cannot be applied to ZOPOGrr- However, using either ZOPO or ZOPOapT is sufficient to outperform baseline methods, which also provides the flexibility of prompt optimization in practice. Future research may consider employing better embeddings to further improve the performance of ZOPO
ZOPO has better query efficiency. To justify that our local optimization method is more query-effiiient, we compare ZOPO against baselines at different query budget scales. The result shown in Fig. Billustrates that ZOPO generally achieves better per- formance with the same number of queries compared with other baseline methods and yields superior performance upon conver- gence. We notice that ZOPO achieves lower validation accuracy yet higher test ac- curacy on the taxonomy _ animal task than INSTINCT, which suggests ZOPO likely has better generalization ability. More re- sults on other tasks in Fig. 10 in Appx. D.2 also indicate that ZOPO has consistent ad- vantages.
taxonomy animal cause_ _nd__effecttttt_eeeeeeeee_e_____ informal formal
Test Acc.
0.75
0.6
0.75
0.50
0.25
0.50
0.4
40
80
120
160200
40 80 160200
40 80 120 200
Val. Acc.
0.75
0.75
0.50
0.5
0.25
0.50
40
80
120
160
40
80 120 160
40
80
120 160 200
# queries
INSTINCT InstructZero
EvoPrumpl
OPRO
PB
ZOPO
Comparison of the query efficiency between ZOPO and baselines. The first and second rows show the test and validation accuracies.
Figure 5:
5.2 Improving Chain-of- -fhouht Prompt
Reasoning prompts, e.g.. "Let's think step by step" (denoted as hand-craft), have been shown effective in improving LLMs' zero-shot multi-step reasoning performance [33 [3]. We show that ZOPO can find better chain-of-thought prompt across different arithmetic reasoning tasks, as evidenced in Tab. 2 Particularly, ZOPO produces better prompt "Let's 'ss find the solution by using the given information." " on GSM8K 4 compared to other baselines, improving the performance from 71.80 (hand-craft) to 75.36. Refer to Appx. C.4 for more experimental details.
8

---

Table 2: The performance of the best zero-shot CoT prompt found by different methods on three
reasoning tasks.
Method
Task
Best prompt
Score
hand-craft
AQUA-RAT
Let's think step by step. Let's break down the problem.
52.36
InstructZero
AQUA-RAI
54.33
INSTINCT
AQUA-RAT
I have new solution.
54.72
EvoPrompt
AQUA-RAT
Let's utilize the substitution method to find solution, then try it out together.
52.76
ZOPO
AQUA-RAT
Let's find the solution by breaking down the problem.
54.72
hand-craft
SVAMP
Let's think step by step.
76.25
InstructZero
SVAMP
Let's use the equation. Let's
79.50
INSTINCT
SVAMP
brains. Let's break down the issue at hand using promptal meth-
81.00
EvoPrompt
SVAMP
79.50
ods gain thorough analysis.
ZOPO
SVAMP
Let's use logic to solve the problem.
81.00
hand-craft
GSM8K
Let's think step by step.
71.80
InstructZero
GSM8K
Let's use the prompt solve the problem.
74.30
INSTINCT
GSM8K
Let's think about it.
74.53
EvoPrompt
GSMSK
Let's attempt to analyze the situation and give it shot.
74.53
ZOPO
GSMSK
Let's find the solution by using the given information.
75.36
5.3 Ablation Study
Verifying the essence of input domain. To fairly validate the importance of input domain on prompt generation, we compare the optimization performances with different prompts generated by Vicuna- 13B and ChatGPT respectively, using the same embedding model SBERT (i.e., h(-)). The result is shown Table. in Appx. [.6] with the performance profile in Fig. IT suggesting that applying ZOPO ChatGP TeGGPP--geereeee prompts is better. We ascribe its better performance to ChatGPT's remarkable prompt generation ability. This confirms the importance the input domain on prompt generation in Insight II.
Besides, different embeddings (i.e., 2) of the same prompt candidates can potentially affect the function landscape as shown in Fig. 4 Thus, we need to study the performance of ZOPO using different embedding representations given the same set of prompts. We consider four different embeddings here: the last token embedding from Vicuna-I 13B, the OpenAl embedding provided through an API [26]. the SBERT embedding, and randomly projected embedding baseline. We observe from Tab. [ in Appx. D.6 that, although last token embedding generally better, there certain tasks that OpenAl and SBERT embeddings perform equally well or better. Besides, random embedding shows distinct lesser performance. This again highlights the importance of using more structured embeddings for prompt optimization and indicates the optimal choice embedding can be task-dependent. We diseuss how might find the best embedding model and further show the generality ZOPO by experimenting with more embedding models in Appx. D.6]
Study of NTK-GP and uncertainty ineertaintyinformeed local exploration. We conducted additional ex- periments to validate the NTK-GP (Sec. (42)) and uncertainty-informe local exploration (Sec. [43)
components of ZOPO. We evaluated the impact of these components by testing two variants of the ZOPO algorithm: (a) replacing the NTK component with Matérn kernel (as in ZoRD), and (b) removing the umcertainty-informee original ZOPO on instruction induction tasks (see Tab. in Appx. D.7 highlight the significant contributions of these components to ZOPO's overall effectiveness.
local exploration. Comparisons of these variants against the
Additional results. The results on the GLUE benchmark in Appx. D.3 consistently validate the superior performance of ZOPO. We also demonstrate that ZOPO can handle prompt optimization the few-shot setting in Appx. D.4] We conduct further experiments to show ZOPO generalize to different combinations of prompt generation models and black-box LLMs in Appx. D.5 We also perform an ablation study to examine the impact of larger size of the generated prompt candidates (i.c.. VD on ZOPO and ZOPOGeT in Appx. D.g. which suggests a relatively small set of strong

---

prompt candidates (e.g., | = 500) is sufficient (compared with size 1000 or 2000), Additionally, we provide more demonstrations of our empirical findings in Sec. on other tasks in Appx. D.I
Related Work
Soft Prompt Tuning. To control LLMs to perform specific downstream tasks (c.g., reasoning), soft prompt tuning [17] is usually used as a lightweight method to fine-tune the LLMs by only optimizing continuous vector prepended to the input tokens using gradient descent, in contrast to fine-tuning millions to billions of model parameters [37 43]. However, when the gradient information of the
model is inaccessible, gradient-free prompt tuning methods [40] 39 6 are developed to alleviate human efforts in prompt design. Still, those efforts to optimize soft prompts have conventionally relied tfate-of-the-ane art LLMs like ChatGPT [25] and GPT-4 [24] that can only be accessed through black-box APIs (i.e., only accept natural language input).
on the white-box access to the embedding layers of LLMs, making it inapplicable
Discrete Prompt Optimization. We refer to the process of optimizing discrete prompts as "prompt optimization", which is also a more practical setting black-box LLMs only accept discrete inputs. Reinforcement lcarning- based methods (5] 47] focus on discrete token optimization but rely on the output distribution of the LLMs, which is not accessible in black-box API LLMs (e.g.. ChatGPT), Zhou et al. [48] instead makes use of LLMS to produce promising candidate prompts through resampling without applying specific optimizations. Some recent works, EvoPrompt [10] and PB (8) further extend this model-free approach to evolutionary algorithms and design meta-prompts that explicitly ask the LLM perform iterative mutation and crossovers of existing prompt candidates. Besides, Pryzant et al. (00 ask the LLM to perform implicit gradient descent on existing prompts; OPRO 46 uses the LLM as an implicit optimizer to perform prompt optimization, where its designed meta-prompl takes in the optimization trajectory and instructs the LLM to output a promising prompt candidate. However, these methods rely on powerful LLMs (e.g.. GPT-3.5) and typically require large number of iterations and queries to perform well. In this regard, InstructZero [3] leverages the induction ability from other boxte-box LLM g()) for generating the task-specific prompt e that is conditioned on a continuous soft prompt & Rd After that, the optimization on can be transformed into an optimization on the soft prompt 8, where BO algorithms are employed for global black-box optimization. INSTINCT [8 further employs neural bandit algorithms and the last token embeddings from the white-box LLM to further improve the prompt optimization performance. However, these works prioritize global optimization approach that emphasizes the exploration of the entire space. With an empirical understanding of the underlying target function (i.e., the black-box API LLMs), we propose localized ZOO method that is in contrast to the global optimization approaches.
7 Conclusion
In this work, we first provide a thorough empirical study to understand the characteristics of the target function, and then propose our ZOPO algorithm for prompt optimization. ZOPO embraces a ZOO approach in pursuit of finding local optima efficiently. Extensive experiments on 30 instruction induction tasks, 3 reasoning tasks, and the GLUE benchmark demonstrate the efficacy of ZOPO. and ablation studies also validate the design principles and the generality of ZOPO. Besides, we propose a domain transformation that connects powerful LLMs with remarkable embedding models, which provides the flexibility of choices of input domains in prompt optimization. A limitation of this paper is the lack of principle to select LLMS and embedding models in our input domain transformation for better-performing prompt optimization, which we aim to explore in future work.
Acknowledgments and Disclosure of Funding
This research is supported by the National Research Foundation Singapore and the Singapore Ministry of Digital Development and Innovation, National AI Group under the AI Visiting Professorship Programme (award number AIVP-2024-001 This research/project is supported by the National Research Foundation Singapore and DSO National Laboratories under the Al Singapore Programme (AISG Award No: NSG2-RP-2020-011
10

---

References
[1] Anil, R., Dai, A. M., Firat, O., Johnson, M., Lepikhin. D., Passos, A., Shakeri, S., Taropa, E., Bailey, P., Chen, Z., et al. Palm 2 technical report. arXiv:2305.10003 2023.
[2] Arora, S., Du, S. S., Hu, W., Li, Z., Salakhutdinov, R., and Wang, R. On exact computation with an infinitely wide neural net. In Proc. NeurlPS, 2019.
[3] Chen, L., Chen, J., Goldstein, T., Huang, H., and Zhou, T. InstructZero: Efficient instruction optimization for black-box large language models. arXiv:2306.0300 2023.
[4] Cobbe, K., Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, L., Plappert, M., Tworek, J., Hilton, J.. Nakano, R., Hesse, C., and Schulman, J. Training verifiers to solve math word problems. vrXi:22110141666 2021.
[5] Deng, M., Wang, J., Hsieh, C.-P., Wang, Y., Guo, H.. Shu, T., Song. M., Xing, E., and Hu, Z. RlPrrmpt: Optimizing discrete text prompts with reinforcement learning. In Proc. EMNLP, 2022.
[6] Diao, S., Huang, Z.,, Xu, R., Li, X., Yong. I.., Zhou, X., and Zhang, T. Black-box prompt learning for pre-trained language models. Transactions on Machine Learning Research, 2023.
[7] Dolan, E. D. and Moré, J. Benchmarking optimization software with performance profiles. Mathematical programming, 91:201-213, 2002.
[8] Fernando, C., Banarse, D., Michalewski, H., Osindero, S., and Rocktäschel, Promptbreeder: Self-referentin self-improvemmnt via prompt evolution. arXiv:2309.16797, 2023.
[9] Flaxman, A., Kalai, A. T., and McMahan, H. B. Online convex optimization in the bandit setting: Gradient descent without a gradient. In Proc. SODA, 2005.
[10] Guo, Q., Wang, R., Guo, J., Li, B., Song, K., Tan, X., Liu, G., Bian, J., and Yang, Y. Connecting large language models with evolutionary algorithms yields powerful prompt optimizers. In Proc. ICLR, 2024.
[11] Honovich, O., Shaham, U., Bowman, S. R., and Levy, O. Instruction induction: From few examples natural language task descriptions. Proc. ACL, 2023.
[12] Jacot, Hongler, C., and Gabriel, Neural Tangent Kernel: Convergence and generalization in neural networks. In Proc. NeurIPS, 2018.
[13] Kojima, T., Gu, S. S., Reid, M., Matsuo, Y., and Iwasawa, Y. Large language models are zero-shot reasoners. Proc. NeurIPS, 2022.
[14] Kratsios, A. and Papon, L. Universal approximation theorems for diffcrentiable geometric deep learning. The Journal of Machine Learning Research, 23(1):8896-8)) 00118899668888888888888888888888 2022.
[15] Lau, G. K. R., Hu, W., Liu, D., Chen, J., Ng, S.-K., and Low. B. K. H. Dipper: Diversity in prompts for producing large language model ensembles in reasoning tasks. NeurIPS 2024 Workshop Foundation Model Interventions, 2024.
[16] Lee, J., Xiao, L., Schoenholz, S. S., Bahri, Y., Novak, R., Schh--Dicsttein, J., and Pennington, J. Wide neural networks of any depth evolve as linear models under gradient descent. In Proc. NeurIPS, 2019.
[17] Li, X. L. and Liang. P. Prefix-tuning: Optimizing continuous prompts for generation. In Proc. ACL, 2021.
[18] Lin. X., Wu, Z., Dai, Z., Hu, W., Shu, Y.. Ng. S.-K., Jaillet, P., and Low, B. K. H. Use Your INSTINCT: INSTruction optimization using Neural bandits Coupled with Transformers. In Proc. ICML, 2024.
[19] Ling, W., Yogatama, D., Dyer, C., and Blunsom, P. Program induction by rationale generation: Learning to solve and explain algebraic word problems. Proc. Annual Meeting of the ACI. 2017.
11

---

[20] Liu, P.. Yuan, W., Fu, J., Jiang, Z., Hayashi, H., and Neubig, G. Pre-train, prompt, and predict: systematic survey of prompting methods in natural language processing, ACM Computing Surveys, 55(9):1-35, 2023.
[21] Mishra, S., Khashabi, D., Baral, C., Choi, Y., and Hajishirzi. H. Reframing instructional prompts to gptk's 's language. In Proc. ACL Findings, pp. 589-612, 2021.
[22] Moriconi, R., Deisenroth, M. P., and Sesh Kumar, K. nigh-dimensional bayesian optimization using cow-dimensional feature spaces, Machine Learning, 109:1925-199 1991999--944,,, 2020.
[23] Nesterov, Y. E. and Spokoiny, V. G. Random gradient-free minimization of convex functions.
Found. Comput. Math., 17(2):527-566, 2017.
[24] OpenAl. GPT-4 technical report. arXiv preprint arXiv:2303.0877: 2023.
[25] OpenAl. ChatGPT. http:///oonai..commloooo//oheeee 2024.
[26]
OpenAI.
Documentation of OpenAI's
text
embeddings.
2024.
Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., [27]
Slama, K., Ray, A., et al. Training language models to follow instructions with human feedback. Proc. NeurIPS, 2022.
[28] Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C. L., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., Schulman, Hilton, J., Kelton, F., Miller, L., Simens, M., Askell, A., Welinder, P., Christiano, P., Leike, J., and Lowe, R. Training language models to follow 2022.
instructions with human feedback. arXiv:2203.02111
[29] Patel, A., Bhattamishra, S., and Goyal, N. Are nlp models really able to solve simple math word problems? In Proc. NAACL, 2021.
[30] Pryzant, R., Iter, D., Li. J., Lee, Y., Zhu, C., and Zeng, M. Automatic prompt optimization with "gradient descent" and beam search. In Proc. EMNLP, 2023.
[31] Reimers, N. and Gurevych. I. Sentence-BERT: Sentence embeddings using siamese bert- networks. Proc. EMNLP- IICNLP, 2019.
[32] Reynolds, L. and McDonell, K. Prompt programming for large language models: Beyond the few-shot paradigm. In Extended Abstracts of the 2021 CHI Conference on Human Factors in Computing Systems, pp. 1-7, 2021.
[33] Shen, Z., Yang, H., and Zhang, S. Optimal approximation rate of relu networks in terms of width and depth. Journal de Mathématiques Pures et Appliquées, 157:101-135, 2022.
[34] Shu, Y., Cai, S., Dai, Z., Ooi, B. C., and Low, B. K. H. NASI: Label- and data-agnostic neural architecture search initialization. In Proc. ICLR, 2022.
[35] Shu, Y., Dai, Z., Wu, Z., and Low, B. K. H. Unifying and boosting gradient-based training-free neural architecture search. In Proc, NeurlPS, 2022.
[36] Shu, Y., Dai, Z., Sng, W., Verma, A., Jaillet, P., and Low, B. K. H. Zeroth-order optimization with irajertor-infoormed derivative estimation. In Proc. ICLR, 2023.
[37] Shu, Y., Hu, W., Ng, S.-K., Low, B. K. H., and Yu, F. R. Ferret: Federated full-parameter tuning at scale for large language models. NeurlPS 2024 Workshop on Federated Foundation Models, 2024.
[38] Shu, Y., Lin, X., Dai, 7.,, and Low, B. K. H. Federated zeroth-order optimization using trajectory- informed surrogate gradients. In ICMI. 2024 Workshop on Differentiable Almost Everything: Differentiable Relaxations, Algorithms, Operators, and Simulators, 2024.
[39] Sun, T., He, Z., Qian, H., Huang, X., and Qiu, Bhtv2: Pure blo optimization can be comparable gradient descent for few-shot learning. arXiv:2205.11200, 2022.
12

---

[40] Sun, T., Shao, Y., Qian, H., Huang, X., and Qiu, X. Black-box tuning for monguage-model-ae as-a- service. In Proc. ICML, 2022.
[41] Touvron, H., Martin, L., Stone, K., Albert, P., Almahairi, A., Babaei, Y., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., Bikel, D., Blecher, L., Ferrer, C. C., Chen, M., Cucurull, G., Esiobu, D., Fernandes, J., Fu, J., Fu, W., Fuller, B., Gao, C., Goswami, V., Goyal, N., Hartshom, A., Hosseini, S., Hou, R.. Inan, H., Kardas, M., Kerkez. V., Khabsa, M., Kloumann. I., Korenev, A., Koura, P. S., Lachaux, M.-A., Lavril, T., Lee, Liskovich, D., Lu, Y., Mao, Y., Martinet, X., Mihaylov, T., Mishra, P.. Molybog, L., Nie, Y., Poulton, A.. Reizenstein, J., Rungta, R., Saladi, K., Schelten, A., Silva, R., Smith, E. M., Subramanian, R., Tan, X. E., Tang, B., Taylor, R., Williams, A., Kuan, X., Xu, P., Yan, Z.., Zarov, I., Zhang, Y., Fan, A., Kambadur, M., Narang, S., Rodriguez, A., Stojnic, R., Edunov, S., and Scialom, T. Llama 2: Open foundation and fine-tuned chat models. arXiv:2307, 09288, 2023.
[42] Wang, A., Singh, A., Michael, J., Hill, F., Levy, O., and Bowman, S. R. GLUE: A multi-task benchmark and analysis platform for natural language understanding. In Proc. ICLR, 2019.
[43] Wei, C.,, Shu, Y., He, Y. T., and Yu, F. R. Flexora: Flexible low-rank adaptation for large language models. In NeurlPS 2024 Workshop on Fine-Tuning Modern Machine Learning: Principles and Scalability, 2024.
[44] Xu, C., Sun, Q.. Zheng, K., Geng, X., Zhao, P., Feng, J., Tao, C., Lin, Q., and Jiang, D. WizardLM: Empowering large pre-trained language models to follow complex instructions. In Proc. ICLR, 2024.
[45] Xu, X., Wu, Z., Qiao, R., Verma, A., Shu, Y., Wang, J., Niu, X., He, Z., Chen, J., Zhou, Z., Lau, G. K. R., Dao, H., Agussurja, L., Sim, R. H. L., Lin, X., Hu, W., Dai, Z., Koh, P. W., and Low,
B. Position paper: Data-centric ai in the age of large language models. In Proc. EMNLP, 2024.
[46] Yang, C., Wang, X., Lu, Y., Liu, H., Le, Q. V., Zhou, D., and Chen, X. Large language models as optimizers. In Proc. ICLR, 2024.
[47] Zhang, T., Wang, X., Zhou, D., Schuurmans, D., and Gonzalez, J. E. TEMPERA: Test-time prompt editing via reinforcement learning. In Proc. ICLR, 2023.
[48] Zhou, Y., Muresanu, A. Han, Z., Paster, K., Pitis, S., Chan, H., and Ba, J. Large language models are huvan-level prompt engineers. In Proc. ICLR, 2023.
13

---

Appendix A Proofs
A.1 Proof of Prop.
We follow the ideas in 36
38 to prove our Prop. ! To begin with, we first introduce the following
lemmas adapted from 36
Lemma A.1 (Thm. in 36)
Let E (0. 1) and w d 2(vā + ln16//)) For any E and any t 2 the following holds with probability of at least - 6.
VF(=) pe(2)]]
S 1 (=)]l
Lemma A.2 (Lemma B.4 in [3]). For any E Z and any t z 1, the following holds
[=)] | (x)
Proof of Prop. M Recall that the covariance function (refer to 44) of our derived NTK-GP conditioned on history of function queries D, _ (()rr size will
(x)) (K, + o²) ke(z).
(7)
For any E IR and 2 E Z, define Ne fz' {2r 1|0,k(2,2'11' 2 3} with |Nz,øl = N, the following then holds on the set N2,9:
(a)
[x(22)
(x(2)) (2)))((((())))
tr (KN((2) (2)
0
tr (KN (2)
(8)
10,k(z, 2
n=1
(4) NB8
d
where (a) comes from the fact the maximum eigenvalue of matrix always larger or equal to its averaged cigenvalues, (b) is based on tr(AB) tr(BA), (c) is from the definition of ky (2), and (d) results from the definition Ne.9.
Meanwhile,
(0)
(2)
k" (2, 2) - k2(2)] (KN + o²²I -1 (2)
kl (Amax (KN) +02) -x((2)) kN((2)
(0)
kN(2) kN(2))
Na
(4)
N3/d
Na Na+a" o²
where (a) comes from Lemma A.2 (b) based on the assumption of (2, 2) S x and the defi-
nition of maximum cigenvalue. In addition, (c) comes from Amax (Kv) ) < N max,,s' k(2,
(i.e., the Gershgorin theorem) and the assumption that k(2,2') I a for any 2, 2' E 2, and (d) is
based on the results in (8).
Finally, by introducing the results above into Lemma A.I we conclude the proof.
14

---

Appendix B Broader Impacts
As LLMs have recently received great popularity in human society and their various applications have significantly affected many aspects of society, it is important to make sure the technology related to LLMs is helpful and harmless. Our work focuses on improving the performance of black-bon -bx LLMs by automatically optimizing the prompts, which can significantly save human efforts in prompt engineering. However, such work can be potentially used for malicious purposes. When an adversarial user defines a harmful objective function, our work could be exploited to output harmful prompts that lead negative societal impacts. Therefore, we urge the black-box LLM API providers to impose security check for the prompt that prevents users from querying for malicious purposes.
Appendix C Details of Experimental Settings
C.1 Evaluation Metrics
Following previous works 48 18
use the F1 score for tasks including common_commee and in-
formal_to farlottto_oororo foromal we use the exact set matching for orthography_sine sitgruphhyttrrtswwwa sissssarrrswlll mitth and laxonomy caxonomy_animal, we use the set containing for synonyms; we use the exact matching metric for the rest of instruction induction tasks; and we use the accuracy metric for the arithmetic reasoning datasets.
As the number of datasets is tremendous, use the performance profile 7 the evaluation metric that measures the frequency (i.e., P(T)) of a method within some distance (i.e., T) from the optimality achieved by any method, defined below
(T( = [ 1 E II - Fn,m S ST)
(10)
where IT is the set of all tasks, fr.m is the accuracy of method m on task π, and r = max max(ra, (Fa,m= Vm M) is the best performance achieved by any method in M task x. Specifically, p(0)
represents the number of tasks where a method achieves the best performance. Accordingly, we use both p(0) and p(5) as the evaluation indicators in our tables report the results.
C.2 Hyperparameters
For all experiments using ZOPO in this work, we set the learning rate to 0.01, the uncertainty thresholds X, E to 0.1 and respectively, and the number n of nearest neighbors to query in local exploration (Section 4.3) to 10. A neural network with fully connected layers of size 32 and ReLU activation functions is used in NTK-GP the kernel. We use 20 nearest neighbors to fit the NTK-GP.
C,3 Instruction induction
In this subsection, we describe the experimental details of the instruction induction tasks.
C.3.1
Experimental Specifications
The same data partition and evaluation process in previous works 48 3 18 is adopted in this work, where, for each task, we optimize the generated prompt on a training set D, and report the best-performing prompt's inference accuracy on a held-out test set Dr. Specifically, 5 examples are sampled from the training set as the demonstrations (i.c., Ddemo) for instruction induction, and another sampled 20 examples from the training set are used as the validation set Dy to evaluate the objective function value as in Equation fixed at 165 for all methods.
I The total query budget for each instruction induction task
C.3.2 Implementation Details
To comprehensively compare with the baseline methods, we use GPT-3.5-turbo-0301 (supported by OpenAl API) as the black-box model for prompt evaluation and Vicuna-13B-vl.. as the white-box LLM (i.e., sf-)) to generate the task-specific prompts by feeding g(.) with randomly sampled soft prompts and Daemo: which the same as InstructZero and INSTINCT. In the experiments, we only generate 500 prompt candidates for ZOPO (i.e., [V] 500). Similarly, also use 40 out of the 165
15

---

queries for random initialization of our optimization method, which could serve as the only global exploration of the function landscape at the beginning of local optimization.
To tackle the high dimensionality of soft prompt (i.e., 5120 for one token embedding as Vicuna- 13B) in optimization, InstructZero and INSTINCT random projection to project the soft prompt into a much smaller intrinsic dimension (e.g., 100). This intrinsic dimension may empirically affect the quality of generated prompts, as shown in Lin [18). Therefore, tuning the intrinsic dimension and the soft token length could lead to better performance. Previous methods (i.e., InstructZero and INSTINCT) perform a grid search over the intrinsic dimension in [50, 100, 200) and the soft token length [3, 5, 10] on the validation set and report the accuracy on held-out test set using the best prompt found using the validation set. We also adopt this technique in ZOPO here for fair comparison. The soft prompt will be concatenated with the tokenized embedding of the prompt generation template to generate aask-specific prompt from Vicuna-13B, The prompt generation template and the prompt evaluation template are shown below in the bounding boxes.
Prompt Generation Template (Soft Prompt)
Input: (INPUT)
Output: (OUTPUT)
Input: (INPUT)
Evaluation Template
Output: (OUTPUT)
Input: (INPUT)
prompt: (prompt (i.e., u)) Input: (TEST INPUT) Output:
Output: (OUTPUT)
Input: (INPUT)
Output: (OUTPUT)
Input: (INPUT)
Output: (OUTPUT)
The prompt was to?
We directly use the reported results of APE, IntructZero, and INSTINCT from Lin et al. [18] for comparison, and report the results of EvoPrompt with our re-implementation. For a fair comparison, we also use Vicuna-13B for generating the initial prompt population (of size 20) for EvoPrompt, and we use GPT-3.5 turbo perform the genetic algorithm in EvoPrompt and generate its new prompts. Using GPT-3.5 turbo to generate new prompts will help improve EvoPrompt's performance, compared with using the relatively smaller model Vicuna-13B.
C.3.3 Experimental Details on Query Efficiency
To facilitate a more comprehensive comparison of different prompt optimization methods at different query budget scales, we the maximum query budget 200, and report the test accuracy of the best prompt found on the validation set with each incremental query budget, as shown in Fig. in the main text. We report the mean accuracy and standard error, using 3 runs with different random seeds. For InstructZero, INSTINCT, and ZOPO, we directly fix the intrinsic dimension for generating the soft prompt as 10 and the number of soft tokens as without using the validation set perform grid search over the intrinsic dimension and the number of soft tokens.
16

---

ChatGPT Prompt Generation Template
I gave a friend an prompt. Based on the prompt they produced the following input-output pairs:
Input: (INPUT)
Output: (OUTPUT)
Input: (INPUT)
Output: (OUTPUT)
Input: (INPUT)
Output: (OUTPUT)
Input: (INPUT)
Output: (OUTPUT)
Input: (INPUT)
Output: (OUTPUT)
The prompt was to
C.3.4 Experimental Details GOPOGrT
For our experiment on ZOPOGpT in the main text, we apply ZOPO on ChatGPT (i.e., GPT-3.5 turbo) generated prompts. We follow the generation template from APE 488) as shown above, to generate task-specific prompts from ChatGPT. To generate various prompts using the APE method, we need to sample different sets of demonstrations (i.e., Demmo) from the training set, and, for each Deemo we also need to randomly sample from the ChatGPT's response by setting a high temperature (e.g.. 0.95). To maintain the same size of prompt candidates as in the previous experimental setting of ZOPO, we also generate 500 prompt candidates for each instruction induction task. harness representation power of existing embedding models, we adopt the sentence transformer model [3] "all-mpnet-base from HuggingFace to generate the high-dimensional sentence embedding for each generated prompt from ChatGPT.
C.4 Improving Chain-of-Thought Prompt
To improve the zero-shot chain-of-thought prompt performance on arithmetic reasoning tasks, make use of the LLM's induction ability and enable LLMs to generate different chain-of-thought prompt candidates by providing some example chain-of-thought prompts. We consider the evaluation of our method on three arithmetic reasoning datasets (i.c., GSMSK AQUARAT SVAMP Similar APE 488, use all data from the test set for GSMSK and AQUARAT, and sample 400 data points from AQUARAT's test set to evaluate the corresponding test accuracy. For all these three datasets, sample 200 data points from their training dataset respectively their individual validation dataset.
We follow the experimental setting of Lin et al. 18 use the soft prompt to generate prompts from Vicuna- 13B with a fixed intrinsic dimension of 1000 and search the soft token length (3, 5, 10) on the validation set. The corresponding prompt generation template is given below.
17

---

Prompt Generation Template for Chain-of-Thoughh Thought
I have some prompt examples for solving school math problems.
prompt: Let's figure it out!
prompt: Let's solve the problem.
prompt:
Let's think step by step.
Write your new prompt that is different from the examples to solve the school math problems.
prompt:
C.5 Details Compute Resources
All experiments are conducted on a server with Intel(R) Xcon(R) CPU and NVIDIA H100 GPUs. We mainly perform the prompt optimization for the GPT-3.5-Turbo model (for which OpenAl charged USD 0.5 per IM tokens for input and USD 1.5 per IM tokens for output). The time of execution of our algorithm on each prompt optimization task (e.g.. any task in the 30 instruction induction tasks) normally takes less than 20 minutes, where the actual time would depend on OpenAl API's response speed.
18

---

Appendix D
Additional Results
D.1 Extended Empirical Study Function Landscape
In Section 3, we have empirically studied the landscape of the target function and incorporated the findings into the design of ZOPO. In the main text, we have demonstrated the results on three in- struction induction datasets, including taxonomy animal, cause eause_and___ effect, and informal to formal. Here we use more datasets to validate our findings. Due to the large size of instruction induction tasks (i.e., 30 tasks in total) and the query budget limit (i.e., incurs monetary costs when query the objective function ChatGPT to evaluate the prompt on the given task), we only experiment with few more randomly chosen tasks here to further validate our findings.
D.1.1 Local Optima vs. Global Optimum
To validate our local optimization design, we study the local optima in the function landscape, by using 3-dimensional (reduced by t-SNE) scatter plot to represent the prompt embeddings (last token embeddings from Vicuna- 13B). Here we provide the empirical results on more instruction induction tasks, shown in Fig. 6 The heatmap color represents the validation accuracy of the corresponding prompt. This allows us interpret the local optima visually, and we conclude that many local optima can already exhibit compelling performance.
word sorting
sentiment
synonyms
singalar to plural
common concept
1.0
0.5
0.0
Figure The validation accuracy of 300 randomly sampled prompts with the last token representation on various tasks.
D.1.2 Essense of Input Domain
Prompt Generation To study the prompt quality of different prompt generation methods, we compare the prompts generated from Vicuna-133 and those generated from ChatGPT (i.e., GPT 3.5 turbo). For (icuma-13B, we use the randomly sampled soft prompts with a fixed intrinsic dimension 200 and a number token length of 10. For ChatGPT, we randomly sample prompts from the ChatGPT's response by using the APE generation template filled with random example demonstrations. For each generation method on each task, we generate 300 random prompts, and we query the target function with all prompts. We show the validation accuracy distribution of prompts generated by the two methods on four more (due to budget constraints) tasks here in Fig. 7 demonstrates that ChatGPT has a larger probability of generating prompts with higher accuracy, also with larger mean. The result shows that ChatGPT-gennrated prompts are generally better, further validating our finding of the importance of the input domain.
auto categorization
negation
singular to 10_plural
synonyms
Probabiiity Density
10
0.0
0.5
0.0
Validation Accuracy
Vicuna-138
ChaiGPT
Figure 7: The estimated accuracy distribution prompts generated by Vieuna- 13B or ChatGPT on various instruction induction tasks, where the vertical dotted line indicates the mean performance.
19

---

Prompt Embedding The complexity of modeling the target function depends on its function landscape defined by the embedding domain. To empirically analyze the black-box target function, we show the accuracy landscape of different tasks, where we reduce the dimension of the prompt embedding (we use the last token embedding of Vicuna-I 13B here) to by using I-SNE. The loss landscape is visualized in the surface plot shown in Fig. X We observe that different optimization methods achieve similar performances on tasks like sentiment and singular _t__t_________olee _t__poo__llll____ea as they have many good local optima. For other challenging tasks with complex function landscapes, the good local optima are less, but our methods can still achieve superior performance. This validates our insight that there are many good local optima in the embedding space.
word sorting
sentiment
synonyms
singular lsr_tt_pppp to_plural
common concept
1.0
0.5
0.0
Figure 8: The function surfaces on various tasks using the last token embedding from Vicuna-133 13B as the representation for prompt candidates that are generated by Vicuna- 13B, with contour plots shown below.
20

---

D.2 Comparison on Instruction Induction Tasks
In Section 5.1 of the main text, we compared our methods with other baselines on 20 challenging instruction induction tasks. Here we provide the full results on 30 instruction induction tasks in Section 5.]
Table 3: Average test accuracy with standard error (3 runs) for the best prompt found by different methods for all 30 instruction induction tasks,
Tasks
APE
InstructZero
INSTINCT
EvoPrompt
PB
OPRO
ZOPO
ZOPOart
to passivee
100.0000
99.7
97.0=25
100.0
99.0.0a
100.0000
100.0
100,0000
antonyms
63.7=142
82.7+0.
84.7=03
81.0g00
78.0236
79.0 79.0.2.2
85,2232
81,0+14
categorization
25.0=0.9
25.7+12
25.0=a.3
31.0+10
24.0=3.
24.0=a.
32.7
27.0=6.0
auto deboggggnn
29.2:a.4
37.52a.
29.2:a.4
33.0gz
25.0.00
37. 37.5
41.7
29.2
cause and effect
57.3
$1.3331.1
38.7
84.0113.
82.7 130.0
82. 1000
94.7 13.7
80.0114.2
common_comme concept diff
6.9.2.1
8.62..0
21.3-002
11.1a69
10.9.34
8.6
23,5
2.840.8
67.3
69.3122
100.010a
27.3
71.3 71.3
100.01a0
100.0.0.0
100.0100
firs__ lert_eetter
100.0.00
100.0.a.
93.0_5.3
100.0g0.
100.0.0.0
100.0.00
100.0.0.0
100.0
informal tn formal
57 57.4g0.3
53. 1
55.3=0.0
51.620.9
54.2=445
48.0=0.8
61.3+2.7
61.9_2.9
larger_ animal
89.7.0.5
90.024.
93.7
87.3
73.3
90.7=4.1
92.3+39
92.7
letters,
100.0000
59.0+16.7
100.020.3
100.0
90.3
00.7
100.0.0.0
100.0:000
negation
75.3=1.1
77.7=11
81.7=0.3
86.0.a.
70.7=4.
73.3-a.a
86.3
77.7=22 #2.0
num, to_ verhal
99.7g0.3
100.0g0.0
100.0g0.
100.0.0.0
98.3=1.7
100.0.00
100.0
100.0:0.0
object counting odd_one_oud out
36.321.9
36.02as
31.027.0
55.0
29.3
36 0.5.
52.3
40.3
63.3
61.3147
70.0
10.0100
66.7
17 22.
32.01113
68.7
orthography. startsstts__stt
45.7=14.
50.7
66.7.27
15.0ga
59.8
33.5
56.5
71.0.0.0
retiodi__elemenn
92.712.2
86.7
92.7-2.7
98.0
95.3125
93.3.00
100.0.0.0
91.7
thymes
15.726.4
100.0.0.0
100.0.00
59.7
45.0g.07
23.0
100.0.0.0
11.0
second_ word letter
74.7=20.3
43.3
10.0-41
24.7
88.7=10.4
86.7=18.9
25.7
96.7-2.4
sentence sentence_similarrty
0.0
0.0.0.0
14.0=0.5
2.0
0.0gn.0
2.7
7,6.n.a
37.3
sentiment
91 91.321.4
87.7+24
89.7=1.
93.0+000
81.7=60
57. 67.2-30.3
93.5
89.3
singular_se foclllr__o___llle _oprra
100.0:0.
98.7=111
100.0
100.0
98.0=0a
100.0:0.0
100.0.0.0
100.0:000
67 :.23
100.0.a.
100.010.
100.0.0.a
98.3
100.01a00
100.0.0.0
100.0
synonyms
27.7
30.7=49
40.3240
36.3=3.
40 40.0
43 43.3+009
=4.7
taxonomy_aam _animal
31.71254
T1.7184
85.7
83.0146
29.7
30.0.a1.
90.017.
92.3.0.3
translation_en en-de
84.0g0.5
82.3ga1
84.020.5
85.0g00
71.3
79.724.
85.3
84.7 10.6
translation
87.020.0
87.340.
88.020.0
82.327
81.7=1.
85.3-2.4
85.3+21
86.3
translation_ents en-ffr
88.720.3
87.7200
8
80.7
76.7
86.0ga.
91.0100
86.7 17.1
word sorting
33.02a.7
31.02114
51.3203
48.0421.
45.7=1.7
50.325.8
60.0+42
60.3_3.1
word unscrambling
44.0=13.9
59.0+5.s
63.3.0.7
51.3
51.0=62
61.3-2.1
59.3+25
58.3+1.9
# best-performing tasks
7
18
performance profile p(5)
0.37
0.43
0.57
0.47
0.27
0.43
0.87
0.73
21

---

The performance profile of GF compared against other baseline methods is shown in Fig. 9 This corresponds the result shown Tab. I
APE
InstrxctZeno
INSTINCT
EvoProcppt
PB
t
0.5 A
OPRO
zorO (ours)
0.0
0
10
20
Figure 9: The performance profile of ZOPOGPT compared against other baseline methods 20 instruction induction tasks.
We also provide additional results on other instruction induction tasks to compare ZOPO against baseline methods in terms of query efficiency. The result is shown Fig. I0
word sorting
auto debugging
synonyms
word unscrambling
common concept
Test Apc.
0.5
0.4
0.4
0.2
0.0
0.2
3
0.25
10000000
40
80
120
160
200
40
80
120
160 200
40
80
120
160 200
40 80 120 160 200
40
80
120
160
200
Val. Acc.
0.75
29999
0.6
9-0.9 9-9
0.50
0.50
0.25
000000000
0.4
900
00000000
0.25
120
160
200
120 160 200
40
80
120 160 200
80 120 160 200
40
80
120 160
# queries
INSTINCT
InstruciZero
EvoPrompt
PB
OPRO
-
ZOPO
Figure 10: Comparison of the query efficiency between ZOPO and other existing baselines on various instruction induction tasks.
22

---

D.3 Results on the GLUE Benchmark
We here follow the same experimental setting previous experiments the instruction induction tasks and apply the prompt optimization on the GLUE benchmark, which consists of several more traditional natural language processing tasks. The result in Tab. 4 shows that our method ZOPO is still able to achieve advanced performance when compared with other baselines.
Table 4: Test accuracy achieved by different methods GLUE tasks.
Tasks
APE
InstructZero
INSTINCT
EvoPrompt
PromptBeeder
OPRO
ZOPO
CoLA
82.0
79.0
72.0
65.0
54.0
0.0
65.0
MNLI-m
72.0
70.0
66.0
72.0
69.0
71.0
70.0
MNL.-mm
71.0
40.0
66.0
64.0
56.0
52.0
73.0
MRPC
66.0
76.0
71.0
71.0
28.0
0.0
76.0
QNLI
80.0
83.0
78.0
77.0
83.0
83.0
QQP
78.0
79.0
83.0
72.0
83.0
RTE
83.0
74.0
76.0
20.0
79.0
$3.0
SST-2
92.0
97.0
93.0
91.0
85.0
92.0
best-performing
performance profile p(5)
0.875
0.875
0.375
0.375
0.25
0.875
D.4 Few-shot Setting
Our algorithm ZOPO is in fact able to handle the few-shot settings as evidenced by the results in Tab. below. Interestingly, the performance our ZOPO even better few-shot setting, which is reasonable since in-context exemplars will help the black-box models better understand the context and the output format of the task, and consequently will be able to lead better performance than the zero-shot setting. In this few-shot experiment, we provide exemplars for prompt evaluation and also report the test accuracy the best prompt with exemplars provided.
Table 5: Test accuracy achieved by ZOPO under zero-shot and few-shot settings on instruction induction tasks.
Tasks
Zero-shot
Few-shot (5)
antonyms
81.0
86.0
auto_categorization
38.0
34.0
auto_ sito_debugging
37.5
50.0
cause_and baaiee_an_eefeeeee effect
92.0
92.0
common_concepp diff
19.6
10.2
97.0
99.0
informal to formal
63.4
46.9
letters_ii list negation
100.0
100.0
86.0
90.0
object_counting
object counting odd _i__ooe__o__ out
57.0
55.0
6.0
36.0
orthography_stane sitoographysstrts_wwiiii with
44.0
67.0
rhymes
98.0
65.0
second_word letter
16.0
65.0
similaty
18.0
27.0
sum
100.0
100.0
synonyms
44.0
25.0
taxonomy_aning animal
97.0
62.0
word sorting
57.0
62.0
word unscrambling
61.0
62.0
best-performing tasks
13
23

---

D.5 Results of Different Combinations of Generation and Evaluation Models
We use further experiments show that our method can generalize different prompt generation models and different black-box API LLMs for prompt evaluation (as f()). Specifically, we here consider two open-sourced models: Vicuna- and WizardLM- 13B 44 for the prompt generation
and we use their corresponding last token embeddings in our algorithm. For the black-box API LLMs, we consider GPT-3.5 (the one considered our main text), Pa D. and GPT-4. total, we have six combinations. Tab. X shows the results of different combinations on the instruction induction tasks. The results show that our ZOPO performs well on all these black-box API models (with GPT-4 performing the best most tasks), which further verifies the generality of our method when different black-box LLM f()) is considered in the objective function Eq. We also notice that the Vicuna model generally performs better than the WizardLM model, which suggests it is more suitable for prompt generation and representation when applying our method ZOPO.
Table 6: Test accuracy instruction induction tasks with different black-box LLMs f(-) considered in the objective function in Eq.
Prompt Generation/Embedding LLM
Vicuna
Vieuna
Vicuna
WizardLM
WizardLM
WizardLM
Black-box LLM (Objective Function)
GPT-3.5
PaLM2
GPT-
GPT-3.5
PaLM2
GPT-4
antonyms
81.0
80.0
85.0
80.0
80.0
88.0
auto auto_cateee categorization
38.0
24.3
37.0
19.0
1.0
3.0
auto dethgdindgging
37.5
33.3
25.0
25.0
cause and effect
92.0
96.0
Common_concee
19.6
diff
97.0
100.0
100.0
100.0
100,0
informal_ formoa letters_lis list
63.4
50.1
51.5
53.1
100.0
100.0
100.0
100.0
negation
86.0
80.7
84.0
73.0
73.0
object_counting
57.0
57.3
57.0
49.0
48.0
59.0
odd one_one
6.0
14.7
68.0
36.0
24.0
26.0
orthography_starre
44.0
60.0
72.0
34.0
30.0
13.0
rhymes
98.0
84.0
86.0
53.0
90.0
100,0
second word letter sentence_similarde
16.0
22.0
99.0
1.0
18.0
93.0
18.0
0.0
5.0
11.0
0.0
0.0
sum synonyms
100.0
72.0
100.0
98.0
100.0
100,0
44.0
35.3
41.0
36.0
16.0
39.0
taxonomy_aning _nnimal word _ort_ssning
97.0
86.3
100.0
95.0
77.0
97.0
57.0
19.3
66.0
0.0
1.0
0.0
word unncrramblin
61.0
12.7
71.0
51.0
14.0
58.0
# best-performing tasks performance proñle p(3)
9
10
0.7
0.2
0.8
0.25
0.25
0.45
24

---

D.6 Verifying the Essence of Input Domain
Prompt Generation To fairly compare the effect of prompts generated by Vicuna-13B and Chat- GPT in terms of the optimization performance by using ZOPO, we adopt the same embedding representations here, that we use the SBERT embedding model for both prompts generated by Vicuna-13B and ChatGPT. For the prompt generation process, we fix the number of prompt candidates for both methods to 500. The result of the comparison on 20 instruction induction tasks is shown in Table. 7 where the corresponding performance profile shown in Fig. [1 suggests that applying ZOPO on ChatGPP-gennrated prompts better than applying on Vieuna-gente Vieuna-generated prompts. This again confirms the importance of the choice of the input domain (i.e., the prompt generation).
Table 7: Fair comparison of the optimization perfor- mance of ZOPO with different generated prompts but the same embedding model (i.e., SBERT). Tasks
Vicuna-13B
ChatGPT
0.9
Vion 138
antonyms
78.3
84,0
ChaceP
auto categorization
29.7
27.0+5.0
auto_ tio_ddcugging
41.7
29. 29.2+5.9
0.8
cause and effect
86.7
80.0
common_coome concept diff
24.9
2.8+0.6
8.0g7.1
100.0.0.0
informal to formal
62.0+3.35
61.9
0.6
letters list negation object_counttee
100,0+0.0
100,0
82.0
77.7
10
20
object counting
45.3
40.3
7
odd_one_ood
20.0
68.7+2.5
orthography starrlyyssttst_teeeee with
51.0
71.0
Figure 11: The corresponding performance profile for results shown in Tab.
rhymes
100,0+0.0
61.0+2.8
second_word war__word__eeee Jetter
24.3
96.7+2.44
gettence_similariy
10.3
37.3
100.0+0.0
100,0
synonyms
40.3
44.7++4.1
taxonomy animal
91.7
92.3
word word_sorting
62.7
60.3
word_unscrambling
53.0
58.3
25

---

Prompt Embedding Here we analyze how different embeddings affect the optimization of ZOPO. We first generate fixed
prompts of size 500 from Vicuma- 13B those Tab. For the same set of prompts, we consider four different embeddings here: (a) the Last Token embedding from Vieuna- 13B (b) the OpenAl emhedding obtained through embedding model ""ext-embedding-adee (c) the SBERT embedding obtained through the sentence transformer ("all-mpnet- base-v2" from HuggingFace), and (d) the Random embedding obtained by randomly projecting the Vicuna embedding into the same dimension. The dimensions of the four embeddings (from (a) to (d)) are 1536, 756, and 5 5120 respectively. We compare the optimization performance of the four embeddings using ZOPO and the results shown in Tab. 8 We observe although last token embedding generally better, there are certain tasks that OpenAl and SBERT embeddings perform equally well better, which indicates the optimal choice of embedding can be task-dependens. Intuitively, random embedding is not representative. Its lesser performance shown in Tab. g again confirms Insight II in Sec. 3.2 which says the choice of embedding/input domain is important in prompt optimization.
002" API. [26].
Table Average test accuracy with standard error (3 runs) for the best prompt found by ZOPO with four different embeddings on 20 instruction induction tasks.
Tasks
Last Token (5120)
OpenAl (1536)
SBERT (756)
Random (5120)
antonyms
85.2
76.7
78.3+4.5
79.3
aulo categorization
32.7 1.9
31.0
29.7
32.3
auto debugging
115.6
29.2#5.9
41.7+15.6
37.5=17.7
cause_ame cause_and__ _effeffectt
94.7 94.7_.3.7
82.7
86.7
68.0
common concept diff'
23.5-3.4
24.4+1.5
24.9
22.4+1.8
100.0 10.0
94.713.11
8.0
15.7
informal to formal
61.3-2.7
59.4 59.4+2.
62.0
58.543.7
letters list negation
100.0 10.0
100.0
100.0 _..0
100.0 10.0
86.3
82.3
82.0
84.0+2.2
object object_ccuntinee
counting
52.3
51.7
15.3
51.7
odd_one _id_onee_uu
32.0+11.3
24.048.6
20.0+3.3
20.0=12.3
orthography_staree stttoysssttttssitttt with
16.5
56.0
51.016.1
46.7
rhymes
100.0
68.7+21.5
100.0
96.3+2.4
second word letter
wott_letter
15.7
24.3
24.3
24.3
moneece_similarie
7.6+9.3
10.3
10.3
6.3+6.4
100.0 10.0
100.0
100.0
100.0 10.0
synonyms
43.3
40.0 40.0
40.3
42.3
taxonomy aioooomy_nnimal animal
90.0
91.7 11.7
91.7
89.3
word_sorting
60.0 60.0_4.2
63.0
62.7
59.7+3.8
word unscrambling
$9.3
56.3
53.0
47.3
# best-performing tasks
15
8
2
To demonstrate the generality of ZOPO, we provide more results below to show we are not focusing on specific combination of LLMs and embedding models. For the same optimization objective (i.e., we still perform prompt optimization for ChatGPT), we further study our ZOPO with more choices of embedding models and pair with different black-bal LLMs for prompt generation (i.e., GPT-4). We consider three more embedding models from HuggingFace and OpenAI, including "Instructor-Large" "Mi-iL.M--6-v2"... and rext-embeddinng---ae 3-saddllnn---mal"" Tab, D beloo, as well another black-box model (i.e., GPT-4) for prompt generation in Tab. below.
Note that, in main text, the fair comparison against baselines (i.c., InstructZero and INSTINCT), and we can tell from Tab, that the Vicuna embedding a good embedding to use in prompt optimization. The result from Tab. 10 suggests choosing better embedding model (i.c., Instructor-Largo for GPT-4 generated prompts can even further improve performance.
the Vicuna-13B model the prompt generation model mainly for
Can we possibly find the best embedding model? As we have shown in our previous experiments, the best choice for the embedding model can be task-dependent. To find the suitable paired embedding model without enumerating every embedding model, we could possibly analyze the variance V. of
26

---

the eigenvalues of the covariance matrix of the embeddings (i.e., 2). The eigenvalues represent the variances along the principal directions (eigenvectors) of the embeddings. If the embeddings are distributed with equal spacing in the high-dimensional space, we would expect the eigenvalues to be approximately equal (i.e., low variance). Intuitively, if the embeddings are such representative space with equal spacing, it could help function modeling.
Therefore, if such variance Ve is small, the optimization performance using such an embedding model is more likely to be better. Based on the test accuracies from Tab. and Tab. TO we show that there exists sufficiently high negative Spearsman's correlation (i.e., the average correlation is -0.47) between Ve and the performance of ZOPO using different embedding models on each task. Therefore, we can check every embedding prior to the experiment, and can be done efficiently. We acknowledge that this approach is not perfect and finding the best embedding model is not the main focus of this work. By finding the best pair of generation and embedding models for prompt optimization, we believe our ZOPO algorithm can be further boosted. We would like to take it as potential future direction.
Table 9: Test accuracy achieved by ZOPO (Vicuna-13B for prompt generation) with different embeddings on GLUE tasks.
Tasks
Vieuna
Instructor-Largg
Minil.M-L.6v22
texteembedding---smaalll
CoLA
65.0
70.0
58.0
60.0
MNLI-m
70.0
67.0
71.0
71.0
MNLI-mm
73.0
62.0
73.0
62.0
MRPC
76.0
73.0
73.0
73.0
QNLI
83.0
78.0
83.0
83.0
QQP
83.0
82.0
82.0
82.0
RTE
83.0
78.0
75.0
82.0
SST-2
92.0
91.0
91.0
91.0
# best-performing tasks
6
3
2
performance profile p(5)
1.00
0.88
0.75
0.75
Table 10: Test accuracy achieved by ZOPOGpT4 (GPT-4 for prompt generation) with different embeddings GLUE tasks
Tasks
SBERT
Instructor-Large
MiniL.M-L.-v22
text-embeedding--smmalll
CoLA
77.0
78.0
79.0
76.0
MNLI-m
73.0
73.0
74.0
69.0
MNLI-mm
72.0
77.0
77.0
69.0
MRPC
68.0
71.0
65.0
71.0
QNLI
83.0
83.0
84.0
83.0
QQP
81.0
76.0
74.0
75.0
RTE
84.0
86.0
81.0
82.0
SST-2
96.0
96.0
93.0
93.0
# best- best-performing tasks
2
performance profile p(5)
1.0
1.0
0.75
0.75
27

---

D.7 Study of NTK-GP and Uncertainty-Informee Local Exploration
To validate the effectiveness the components, namely NTK-GP (in Sec. 4.2) and uncertainty- informed local exploration (in Sec. 4.3) of ZOPO, we perform controlled experiments to replace these components. Specifically, we (a) replace the NTK component with Matérn kernel in the 700 method ZoRD), and (b) remove the uncertainty-informed local exploration feature. We evaluate the two settings on 20 instruction induction tasks. The result shown in Table illustrates these two settings are both significantly worse than the original ZOPO, which validates the effectiveness of NTK-GP and uncertainty-infe informmed local exploration.
Table 11:
Ablation study of the design components in ZOPO showing the average test accuracy reported with standard error (3 runs) on 20 instruction induction tasks.
Tasks
ZOPO
ZOPO w/o NTK
ZOPO w/o Local Exploration
antonyms
85.2
79.719.0
78.7
auto_categorization
32.7
34.7
28.314.9
auto sit__debugging
41.7 1:1.6
29.2
25.011.0
cause_and _ed_effect
93.7
93.3+1.9
85.346.8
common_concee
23.5+3.4
9.2+4.1
22.045.6
diff
100.0
13.7+6.1
13.7
informal_nt ____t__foool formaal
61.3+2.7
63.4
63.4
letters list
100.0
100.040.0
100.0+0.0
negation
86.3
85.7+005
84.7+3.3
object_counting
counting
52.3
39.0+7.1
51.7+6.2
odd_one_out orthography_sine stttptyyyssttt_t_tteee with
32.0 12.03
14.7
32.0 32.0 18.6
56.51112.
49.318.2
46.3
rhymes
100.0
90.7.10.5
93.3
second_ word letter
wotd_letter
25.7
25.7
19.7
sentence_similarity sum
7.6
0.0
0.0
100.0
93.749.0
100.040.0
synonyms
43.3
38.3+0.9
39.7
taxonomy animal word _orting
90.0+7.1
74.7+15.1
91.3
60.0
29.3+12.7
56.3
word gand_unscramblng
59.3
47.340.9
50.0+12
# best-performing tasks
17
performance profile p(5)
1.0
0.35
0.5
28

---

D.8 Study of ZOPO with More Prompt Candidates
Intuitively, generating more prompt candidates offers closer approximation the true function landscape. As our optimization method ZOPO is operated under given set of prompt candidates, we here conduct an ablation study examine the impact of larger size of the generated prompt candidates (i.e., [V]] on the optimization performance. For ZOPO, we use random soft prompts to feed Vicuna- 13B and generate prompts until 500 or 2000. We compare the optimization results of ZOPO using the two different sizes of prompts, and the results are shown in Table [2] We also follow the APE generation template to prompt ChatGPT to generate different sizes of prompt candidates and use SBERT to produce their embeddings. For ChaiGPT-generatee prompts in ZOPOGGT, we also consider two settings, V = 500 or 1000 (due to budget constraint), The corresponding result is shown in Table 13 We observe from the two tables that a larger set of prompt candidates may not necessarily lead to strictly better performance, and generating a relatively small set of strong prompt candidates (e.g., of size 500) is already good enough when aim to find the optimal prompt.
Table 12: Ablation study of different sizes of prompt candidates in ZOPO.
Table 13: Ablation study of different sizes of prompt candidates in ZOPOGPT.
Tasks
[V| 500
[V] 2000
Tasks
[V] 500
|V 1000
antonyms auto categorizaain
85.2
86.3 10.9
antonyms
84.0
80.311.2
32.7
37.3
auto. categgrrriziiinnnn
27.0=5.0
28.3
deeuuggggnngg
41.7
33.3
auto_debuge seio_debggging
29.2.5.9
37.5
cause_and and _effect
13.7
94.71.1.
cause_and effect
80.0
78.713.8
cemmmon_concee
23.5
17 77.06..1
commonn_com cenuonn_concept
2.8+0.6
11.7+66.
diff
100.0=0.0
100.0.0.0
100.0=0.0
100.0.0.0
informal_re formal
61.3.22.7
56.6 6...1
informal formol
61.9
57.2+8.9
letters_list
100.0
100.0.0..
letters_list
100.0_0.0
99.3
negation
86.3
86.3
negation
77.7
75.0+1.6
object_ counting odd_one_owt out orthography_starts___
52.3=6.0
$3.0
object couuting
40.3=0.5
41.3+1.2
11.3
20.7
odd_one_one
08.7=2.5
72.0
56.5 46.5
46.0 46.0
orthography_sstrrss
71.0=u.0
71.3
rhymes
100.0
100.0
rhymes
61.0-2.
100.0
second_wond word letter
25.7+447
35.3
second_wood letter
96.7=2.4
99.7+006
sentence_similas
7.649.3
+6.1
sentence simtnceesimillarity
37.3+0.9
0.0=0.D
sum
100.0
100.0
sum synonyms
100.0=0.0
100.0.0.0
synonyms txxonoyy_om animal
43.3
40.0
44.7=-41
45.3
90.0+7.1
91.3+
taxonomy animal
92.3g..5
89.3+1.9
word_ word_sorting
60.0+4.2
59.0+6.4
word_ sorting
60.3
54.3+7.0
word word_unsee uunscrambling
59.3
54.713.3
word_ word_unscrambling
58.3219
60.3
best-performing tasks
14
best-performing tasks
12
performance profile p(5)
0.9
0.8
performance profile p(5)
0.85
0.9
29

---

D.9
Best Prompts Found
We list the best prompts discovered by our method ZOPO for every instruction induction task here in Table 14 which corresponds to the results in Table 3
Table 14: The best prompts discovered by method ZOPO for every instruction induction task, where **" indicates the best prompt is found by ZOPO for that task.
Task
Best prompt
active_to, saave__t___ssvvee__
The prompt was convert the given sentence into passive voice.
antonyms
The prompt was to rewrite the given words into their opposite meaning. So. "humor- less" becomes "humorous", "ddpressing" becomes "cheerful", "unwrap" becomes "wrap". "consumptive" becomes "generative", "uncoil" becomes "coil".
auto_ nuto_categorization
The prompt was input the given names and output the corresponding apparel. For example, the input "Nature Nanotechnology, Annual Review of Biochemistry, and The Lancet Neurology" would output as "top journals".
auto_ debuggen
The prompt to write program that would take the given input and output the expected output. For example, the first input was simple calculation, and the expected output was "2550". The second input was a class definition with a method, and the expected output was "5".
gouse_and_eeee _ffectt
The prompt was to identify the sentence that is the cause and the sentence that is the effect in each pair of sentences. The input sentences are given, and the output is the cause sentence.
common_commee
The prompt was to create a series of pairs of inputs and outputs. where the outputs are related to the inputs in some way. For example, the inputs "guitars" and "pendulums" are related to the output of "involve oscillations.
diff
The prompt was subtract the second number from the first number. For example, the first input would be 41 and the second input would be 13, so the output would be 28 (41 - 13). The same process would be applied for the other inputs and outputs. The prompt was to create a program that takes single input (a word representing legal concept term) and outputs corresponding letter of the alphabet that represents that concept or term. For example, if the input is "year", the program should output "y". The prompt was to rephrase each input sentence using more formal or polite language.
west_werd_letter
informal to formal*
larger_ aager_animal
The prompt was to create a program that takes two input animals and outputs the animal that is bigger. The program uses the ">=" operator to compare the size of the first animal to the size of the second animal. If the first animal is bigger, the program outputs the first animal.
letters list
The prompt was to create program that takes single word input (e.g. "year") and outputs a concatenated string of letters and spaces that approximates the pronuncia- tion of that word (e.g. "y e ar)).
negation
The prompt was to flip the truth value of the input statements. For example, if the input statement is "Cany Ash and Robert Sakula are both Architects." " the output should be "Cany Ash and Robert Sakula are not Architects.
num to_ verbal
The prompt was to write a program that takes a number as input and outputs the number in words, using the appropriate number formatting. The examples provided in the input show the expected output for each number.
object__comee countiig
The prompts were to provide the output a given input, where the input is list items and the output is a number representing the total count of those items. The examples given in the prompt show how the prompts should be used to generate the desired output.
one_ _od_one_uut"
The prompt was to identify the word that is most different from the others in the group.
30

---

The prompt was to "Identify and return the second letter of the input word". The prompt was create two different sentences that have similar meanings but are orthography_starre sttplpyyy_ttttt__ttteeer with*
The prompt to identify the first word that begins with specific letter in each sentence.
periodic_elenee
The prompts were write program that takes an input value and outputs the corresponding element name based on that value.
For example, if the imput is 24, the program would oulput "chromium.
rhymes
The prompts were to create a program that takes in a word as input and outputs a related word based on a specific set of rules. The rules are as follows: If the input word starts with "tri", the output should be "slip".
second word letter* sentence_similen
not identical. The oulput of each input-oulput pair indicates how closely the sentences match in terms meaning.
Explanation of outputs:
5 perfectly: The two sentences are very similar meaning and can be considered as equivalent.
prohably: The two sentences have some similarities in meaning but there are also some differences, making it less certain that they are equivalent.
- pussibly: The two sentences have some similarities but also significant differences, making it unlikely that they are equivalent.
1 prohably not: The two sentences have very different meanings and are unlikely to be considered as equivalent.
0 -oefinitlly not: The two sentences have no similarity in meaning and cannot be considered as equivalent.
sentiment
The prompt was classily the given reviews as positive negative based on the given input and output. The output is positive when the review is positive, and negative when the review negative.
singular to lo_plural
The prompt was to convert the input words to their plural form by adding "x" to the end of the word. This was done by using the "replace" function in Excel, which allows you to replace a specific text string with another text string.
sum
The prompt was to write a program that takes two numbers as input and outputs their sum as the result. The program uses the 'scanf' function to read the input numbers from the user, and the 'printf" function to display the result.
synonyms*
The prompt was create list of words that synonyms or closely related the given word.
taxonomy_amm *
The prompt was to select the animals in the input and output them in the order they appear.
translation_ena _n-de
The prompts were to input various words and have the model generate the corre- sponding output in German. It appears that the model was successful in generating the desired output for each of the input words provided. If there are any additional prompts or clarification needed, please let me know.
translation en-es
The prompts were to translate a set of words from Spanish to English using the
provided translation table.
translation_ en-Ir
The prompt was to input word and then oulput the corresponding word in French. It appears that the input and output words are heing matched correctly, with the exception of the word "initiative, which should have the outpur "initiative" in French, not "enterprise.
sord_nor word_ word__uncrammling
The prompt was to alphabetize the input list in ascending order and provide the resulting output as a list.
The prompt was to create a program that takes an input word and outputs the corresponding word with the letters rearranged in order. For example, given the input "eccpat". the program should output "uccept".
31

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We have provided extensive experimental results to validate the efficacy of our proposed method. The claims are also empirically supported.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations are mentioned in Sec.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
32

---

Justification:
The assumptions and proofs are included in the Appx.
A
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We have included all the necessary information to implement our algorithm, and the experimental details to conduct the experiments.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
33

---

Answer: [Yes]
Justification: We have included our code in the supplementary materials with exact com- mands. The code will be uploaded to GitHub upon acceptance of the work.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https
ssicnlolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The experimental details are specified in Appx. C
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We report the average accuracy with standard error (3 runs) in our tables, and plot the error bar for the query efficiency experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
34

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: The computing resources needed to reproduce the experiments are stated in Appx. C.5
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
Our research adopts the ethical practices mentioned in the Code of Ethics
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Both potential positive and negative societal impacts are discussed Appx.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
35

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: No new data or models in this work will be released. All data and models involved in this work have no risk for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The sources of the datasets are cited in the paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the batasets.papersstt paperswi thcode. cww/ datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
36

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
37


Reviews:
[{"review_id": "IaEt4T4Clc", "reviewer": "Reviewer_bDUw", "summary": "This paper addresses prompt optimization for a black-box API LLM. This paper empirically investigated the objective function landscape of the prompt optimization problem and derived two insights: (I) local optima are usually prevalent and well-performed, (II) choice of the input domain affects the identification of well-performing local optima. Based on these insights, a novel local prompt optimization algorithm based on NTK-GP is proposed. Empirical comparisons have been conducted to show the performance differences between the proposed and baseline approaches.", "questions": "L 118. “We then investigate the function surface (i.e., accuracy landscape) using two different embeddings for prompt candidates in Fig. 4 (more details in Appx. D.1.2) where the embeddings are mapped into a 2-dimensional domain using the t-SNE for better visualization. “ It is not clear how the local optima in the 2D t-SNE space is related to the local optimality of the objective function in the original space? Because the relation is not clear, I am not sure if the insight derived in this paper is valid or not.\n \nIt is not clear how Section 4.1 is related to Insight (II). What is the novelty of this part? This question is also related to the next question.\n\nL165. “We store (z, v) … for constructing the one-to-one inverse mapping.” Because h is a mapping from a discrete space to a continuous space, there does not exist a bijection theoretically. Therefore, it is not clear what the authors mean by this sentence. It is also not clear how this goal is achieved. Please clarify this point.\n\nL197. “theta_0 is the initialized parameters …“ Is it trained? If so, how and when? \n\nTable 1. I couldn’t find the explanation of ZOPO_{GPT}. What is the difference between ZOPO and ZOPO_{GPT}?\n\nThe performance of the baselines and the proposed approaches are compared only up to 200 queries. It is interesting to see how it will change if more queries are allowed.", "limitations": "A limitation has been addressed in the conclusion.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "* a novel and efficient prompt optimization algorithm targeted for a black-box API LLM\n\n* promising performance over baseline approaches\n\n* analysis and visualization of the objective function landscape using t-SNE", "weaknesses": "* The clarity of the algorithm could be improved (see the question part)\n\n* The validity of the derived insights is not sufficiently high (see the question part)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer bDUw for recognizing that our algorithm is novel and efficient, and its performance is promising. We would like to address your concerns below and hope our response will improve your opinion of our work.\n\n---\n> [Q1] Validity of our insight\n\nThank you for your insightful comment. We address your concern below:\n1. The t-SNE is well-suited for visualizing the landscape because it generally preserves the local structure of original data [R1], including the relative positions of local optima.\n2. To further support this claim, we present an **additional result** in Figure[R] 1 of the rebuttal PDF to show that our derived insight is **indeed valid**. \n    - We first identify the local optima points in the original space by comparing $\\widetilde{F}(z)$ of each point $z$ with those of the k-nearest neighbors (k=10) around $z$.\n    - We then apply the same t-SNE transformation to these identified local optima points and highlight them in red with an \"x\" marker in the 2D space.\n\n    This visualization demonstrates that the local optima identified in the original space generally correspond well with those \"peak values\" in the 2D t-SNE space, confirming that our derived insights are indeed valid.\n\nWe will include this clarification and the updated visualization to enhance our manuscript.\n\n[R1] Van der Maaten, L., & Hinton, G. (2008). Visualizing data using t-SNE. *Journal of machine learning research*, 9(11).\n\n---\n\n> [Q2] Section 4.1 and its novelty\n\nRecall that Insight (II) emphasizes the importance of both the generation and representation of prompt candidates. Motivated by Insight (II), we are the **first** to integrate both the generation and representation of prompts within a **unified** problem formulation (refer to our Eq. 2), which then leads to a more general domain transformation of prompt optimization in our Section 4.1 (as one of the novel contributions of our paper). This is in contrast to previous works such as APE and INSTINCT, which focus solely on either generation or representation, but not both. Our domain transformation instead allows for improved prompt optimization by leveraging not only the remarkable generation ability from any type of LLMs (white/black-box, like ChatGPT) but also the impressive representation ability from existing embedding models (refer to our introduction and Sec. 4.1), which in fact has been widely supported by our empirical results in Sec. 5. For example, as shown in Table 1, our approach, denoted as $\\text{ZOPO}_{\\text{GPT}}$, achieves promising performance on many complex tasks. We believe this contribution can inspire the field and may benefit future research.\n\n> [Q3] One-to-one mapping\n\nTo clarify, the mapping is in fact built on a **finite set**. Specifically, we pre-generate a finite set of **unique** prompt candidates (i.e., $\\mathcal{V}=\\\\{v\\\\}$), that is, each text prompt $v$ in this set will be unique. With these unique prompt candidates, the complex embedding model usually will produce the **corresponding** unique embedding vectors $\\mathcal{Z} = \\\\{z\\\\}$. Our mapping $h$ is then defined on these two finite sets $\\mathcal{V}$ and $\\mathcal{Z}$, i.e., $h:\\mathcal{V}\\rightarrow\\mathcal{Z}$, which therefore leads to the one-to-one mapping. In practice, we only perform the search in the finite set $\\mathcal{Z}$ (as shown in Eq. 2) and all the gradient-updated points are projected back into $\\mathcal{Z}$, which then finds a unique $v \\in \\mathcal{V}$ (as shown in line 201-203).\n\nWe will include a detailed clarification of this point in our revised manuscript.\n\n---\n> [Q4] theta_0\n\nNo, theta_0 is not trained. We use the empirical NTK that is based on random initialization of network parameters to avoid the training process while maintaining a good approximation to the predictions of neural networks and hence preserving the compelling representation ability of neural networks for the GP regression in our ZOPO. Of note, such an effectiveness of the empirical NTK has been widely evidenced from both theoretical and empirical perspectives [2,15,33,34], as well as the compelling performance achieved by our ZOPO in Sec. 5.\n\n> [Q5] ZOPO_{GPT} in Table 1\n\nThe explanation of $\\text{ZOPO}_{\\text{GPT}}$ can be found in the third paragraph of Section 5.1. For your convenience, we summarize it as a more straightforward comparison below:\n- ZOPO: we use the Vicuna-13B model for both prompt generation and representation (specifically, the last token embedding). This choice was made to ensure a fair comparison against existing baselines such as InstructZero [3] and INSTINCT [17].\n- $\\text{ZOPO}_{\\text{GPT}}$: Here, we utilize GPT-3.5 for prompt generation and SBERT for embedding representation inspired by our Insight (II). This approach leverages the superior generation ability of GPT-3.5, resulting in significantly higher accuracy on challenging tasks like `second_word_letter` and `sentence_similarity`. This demonstrates our method is capable of performing numerical optimization on ChatGPT-generated prompts.\n\nWe hope this clarifies the distinctions between the two variants and highlights the strengths of $\\text{ZOPO}_{\\text{GPT}}$.\n\n> [Q6] More queries\n\nWe would like to first clarify that our work follows the same query setting as previous baselines [3, 17, 44] (up to 200 queries) primarily for a fair comparison. For your interest in the results of more queries, we additionally performed experiments on only 4 GLUE tasks due to the limited money budget and time in this rebuttal, extending the number of queries to 1000. The experimental results, presented in Table[R] 1 of the rebuttal PDF, indicate that our proposed method ZOPO continues to achieve better or comparable results even in a query-rich setting compared with 165-queries results in Table 4.\n\n---\nWith our elaboration and additional results, we hope our response has addressed your concerns and increased your opinions of our work. We are happy to provide more clarifications if needed.", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NibcIK6hTf", "reviewer": "Reviewer_GMgT", "summary": "The paper proposes multiple contributions:\n\n1. Establishes a new visualization technique for the objective landscapes of blackbox functions over prompts. This is done by converting the high dimensional embeddings of strings into 2D (via t-SNE), and visualizing the landscape in 3D. Using this, the paper finds several patterns:\n  * There is a correlation between the smoothness of the landscape and the strength of the prompt generator.\n  * Much of the landscape is filled with local minima.\n\n2. Proposes a new Bayesian Optimization-like algorithm, with the following setup:\n* The regressor + uncertainty estimator is a NTK-GP using an MLP\n* The acquisition maximization is a gradient descent in the embedding space, with a projection back into the original prompt space.", "questions": "Please address the main questions in the weaknesses above. \n\nThese are more for clarification:\n1. How does $h^{-1}$ (i.e. mapping an embedding back into some text) work? L165 mentions storing $(z,v)$ for constructing this inverse mapping - does this mean there are already alot of candidate prompts pre-generated forming an embedding set $Z$, and for a new $z$, we simply perform randomized rounding or projection to the nearest legitimate prompt in $Z$? \n\n2.  Eq 6: What happens if we fully attempt to argmax the acquisition (like regular Bayesian Optimization), rather than just move by a gradient step? I understand that this gradient step may be motivated by the landscape being full of local optima, but there may be missed gains here. Is this explained in L220-L230?", "limitations": "Section 7 discusses some limitations, but it may be worth considering the raised weaknesses above.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "* The proposed visualization method is simple yet surprisingly very insightful. I believe this might become a very important tool for any string-based blackbox optimization to assess the landscape.\n\n* The Bayesian optimization-like algorithm makes intuitive sense (bar the weaknesses, see below). This paper is well-written and is straightforward to read.\n\n* The conducted experiments are rigorous and comprehensive over numerous tasks with multiple baselines. Ablation studies are also relevant and insightful.", "weaknesses": "* Section 4.2 is not well-motivated. I understand that the idea is to construct an acquisition function expressing explore/exploit tradeoffs, and the most natural regressor to use is a Gaussian process, leading to the idea of using the NTK kernel. But this may seem overly complicated. For instance, why not use a simpler regressor / uncertainty estimator, like an ensemble of MLPs?\n  * Since the NTK requires computing dot-products of gradients, this makes it tricky to use for larger models (which have much longer gradients as feature vectors).\n\n* (Small) I would tone down the statement that Bayesian Optimization (or more generally, regressor guided search) will do poorly in local-optima situations simply because it was designed to search for global optima. There are several previous works over traditional black-box optimization showing Bayesian Optimization remains competitive even with multiple local optima. Furthermore, one could argue that the paper is essentially a Bayesian Optimization technique given the gradient ascent over essentially an explore-exploit acquisition.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are highly encouraged by Reviewer GMgT's positive and constructive feedback! We appreciate that the reviewer positively recognizes that our visualization method is **insightful** and could be a very **important tool** for studying the black-box prompt optimization landscape, our designed algorithm is **intuitive**, the paper is **well-written** and **straightforward**, and our experiments are **rigorous and comprehensive**. We would like to address the comments as follows.\n\n---\nFirstly, we would like to clarify that our ZOPO is in fact a gradient ascend-like algorithm rather than a Bayesian optimization-like algorithm. More specifically, in standard Bayesian optimization, Gaussian process will be applied to construct its **acquisition function (i.e., a surrogate function to the original objective function with GP mean and covariance)** to trade off exploitation and exploration for its **global optimization**. In contrast, ZOPO will make use of a **derived** Gaussian process (i.e., Eq. 3) from a standard Gaussian process to **estimate the gradient of the original objective function with GP mean** (see line 188) as well as to **measure the uncertainty on this gradient estimation with GP covariance** (which will be later used in our local exploration for more accurate gradient estimation in Sec.4.3) for a **local optimization**, i.e., the gradient ascend in our Eq. 6. We would like to refer you to [35] for detailed comparison between zeroth-order optimization with derived GP and standard Bayesian optimization.\n\n> [W1] Section 4.2 is not well-motivated\n\nThank you for pointing out this interesting question. As we have clarified above, the idea in our ZOPO is in fact to leverage a derived Gaussian process to estimate gradient and then apply gradient ascend to maximize the objective function. However, as mentioned in line 189 of our main paper, the underlying objective $\\widetilde{F}$ is complex and highly related to transformers, i.e., it's computed based on the inference of transformers. As a result, standard kernels may not have a powerful representation ability to approximate this objective function and hence can not provide a good gradient estimation to the underlying objective function (as supported in Table. 11). To leverage the powerful representation ability from deep neural networks for our prompt optimization, we can either train an ensemble of MLPs (the method you mentioned), or apply empirical NTK to avoid this training process while maintaining a good approximation to the predictions of neural networks and hence preserving the compelling representation ability of neural networks. Of note, such an effectiveness of the empirical NTK has in fact been widely evidenced from both theoretical and empirical perspectives [2,15,33,34]. Although empirical NTK requires computing dot-products of gradients, it is still more computationally efficient (as no training is required) than training an ensemble of MLPs, especially when we typically use a small neural network, e.g., 2-layer MLPs in our implementation, to compute this empirical NTK in practice. In light of the effectiveness and efficiency of NTK, we therefore choose to apply NTK in this paper for our ZOPO. We would like to add these discussions to our revised paper.\n\n> [W2] Statement on Bayesian Optimization\n\nThank you for your valuable feedback. We acknowledge that our previous statement about Bayesian Optimization performing poorly in local-optima situations could be overly broad. We will revise this statement in our revised version. Below, we clarify that our ZOPO is different from Bayesian Optimization algorithms.\n\nWhile we acknowledge the existence of previous works on local Bayesian Optimization, our method, ZOPO, is fundamentally a gradient ascent-like algorithm, which is inherently more suited for local optimization tasks. Similar to [35], our ZOPO does not construct the acquisition function like Bayesian optimization. Instead, ZOPO will apply the derived GP mean to estimate gradient (line 187-188) and derived GP covariance for more queries to better estimate the gradient (Sec. 4.3), which emphasizes exploitation when updating the next queries rather than the exploration-exploitation trade-off in Bayesian Optimization. Importantly, our empirical results in Sec. 5 show that our local optimization algorithm ZOPO generally outperforms the global optimization (i.e., Bayesian optimization) algorithms, such as InstructZero and INSTINCT, in the context of prompt optimization, which therefore indicates the advantages of local optimization in this specific setting.\n\n> [Q1] Implementation of $h^{-1}$\n\nYes, your understanding is correct. To clarify, the inverse mapping is built on a **finite set**. Specifically, we pre-generate a finite set of **unique** prompt candidates (i.e., $\\mathcal{V}=\\{v\\}$), that is, each text prompt $v$ in this set will be unique. With these unique prompt candidates, the complex embedding model usually will produce the corresponding unique embedding vectors $\\mathcal{Z} = \\{z\\}$. Our mapping $h$ is then defined on these two finite sets $\\mathcal{V}$ and $\\mathcal{Z}$, i.e., $h:\\mathcal{V}\\rightarrow\\mathcal{Z}$, which therefore leads to the one-to-one mapping. In practice, we only perform the search in the finite set $\\mathcal{Z}$ (as shown in Equation 2), and all the gradient-updated points are projected back into $\\mathcal{Z}$, which then finds a unique $v \\in \\mathcal{V}$ in the natural language space (as shown in line 201-203).\n\n>[Q2] Eq. 6\n\nWe clarify that Eq. 6 is not the acquisition function in BO and using argmax will require a global modeling like traditional BO which may not be better than our local modeling. Besides, L220-L230 states that we need more queries to improve the gradient estimation.\n\n---\nThanks for your insightful suggestions. We will incorporate these discussions above into our revised version. We hope our clarification will address your concerns and improve your opinion of our work.", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nzLSRFJp05", "reviewer": "Reviewer_TQjw", "summary": "The paper titled \"Localized Zeroth-Order Prompt Optimization\" proposes a novel algorithm called ZOPO (Localized Zeroth-Order Prompt Optimization) aimed at enhancing the efficiency of prompt optimization in large language models (LLMs). The authors argue that local optima, as opposed to global optima, are more prevalent and can be more effectively targeted for prompt optimization. They introduce a combination of Neural Tangent Kernel (NTK) and Gaussian processes within a zeroth-order optimization framework to improve query efficiency and optimization performance.", "questions": "How do the proposed prompt-tuning approaches compare to the fully fine-tuning ZO approaches such as MeZO? It would be better to justify the settings that require prompt optimization.", "limitations": "NA", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The thorough empirical study conducted provides a detailed comparison between local and global optima, highlighting the potential advantages of targeting local optima.\n\n2. The ZOPO algorithm is well-designed, incorporating NTK-based Gaussian processes to enhance the optimization process, which shows promise in improving query efficiency.", "weaknesses": "The proposed ZOPO algorithm is complex and might be challenging to implement for practitioners who are not deeply versed in NTK and Gaussian processes. This limits the accessibility and practical utility of the proposed method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to Reviewer TQjw for the constructive feedback and for positively recognizing that our empirical study is **thorough** and our proposed algorithm is **well-designed**. We will incorporate the suggested discussion into our revised work. We respond below to their concerns and hope our responses can improve the reviewer's opinion of our work.\n\n---\n\n> The proposed ZOPO algorithm is complex and might be challenging to implement for practitioners who are not deeply versed in NTK and Gaussian processes. This limits the accessibility and practical utility of the proposed method.\n\nWe would like to clarify that our proposed ZOPO algorithm is in fact quite straightforward. Specifically, ZOPO has only two major components: GP-NTK in `learner_diag.py` (52 lines for its core ideas of computing empirical NTK and fitting GP with query history), and the zeroth-order optimization in `optimization.py` (about 3 lines for its core ideas of gradient estimation from derived GP) in the supplementary material we have provided. Moreover, since we have provided the codes for our ZOPO, it becomes less challenging for practitioners without deep expertise in NTK and Gaussian processes to utilize and integrate our method into their interested problems, which we believe will highly benefit the accessibility and practical utility of our ZOPO.\n\n> How do the proposed prompt-tuning approaches compare to the fully fine-tuning ZO approaches such as MeZO? It would be better to justify the settings that require prompt optimization.\n\nTo clarify, the fully fine-tuning ZO approaches (e.g., MeZO) and prompt optimization ZO approaches (i.e., ZOPO) are designed for different contexts/settings.\n- **MeZO**: it utilizes ZO approach to **reduce the memory footprint** when fine-tuning the model parameters of **white-box** LLMs (e.g., LLaMA) on downstream tasks, as backpropagation typically requires a prohibitively large amount of memory.\n- **ZOPO**: In contrast, this method is tailored for scenarios where the LLMs (e.g., ChatGPT) are treated as **black box** systems, where direct fine-tuning of model parameters is not feasible. Therefore, prompt optimization becomes a better choice for adapting black-box LLMs to downstream tasks by only tweaking the text inputs for these tasks. \n\nWe will add a detailed discussion comparing MeZO and ZOPO in our revised version.\n\n---\nWe appreciate the reviewer's valuable input and hope our answers can address your concerns and increase your opinions of our work. Thank you!", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "N5jjBOHJmX", "reviewer": "Reviewer_TMXX", "summary": "This paper focuses on the prompt optimization task. The authors first propose two insights: (1) Instead of pursuing the global optimum, this paper claims that local optima are usually prevalent and well-performing. (2) The input domain for prompt optimization affects the choice of local optima. Inspired by these two observations, this paper proposes a zeroth-order optimization method that incorporates a Neural Tangent Kernel-based derived Gaussian process to search for local optima. This method achieves competitive results on benchmarking datasets.", "questions": "I cannot see a consistent advantage of ZOPO in many figures and tables. Can you explain this part? Thanks.", "limitations": "They listed the limitation and claimed to solve it in future work.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. I like the analysis in Section 3. The two insights are well supported by the provided studies, and the motivation and reasoning for decision-making in this paper are explained in an informative way.\n\n2. Compared to methods that aim to find global optimization, incorporating NTK-based Gaussian processes in prompt optimization should theoretically be much faster.\n\n3. The input domain transformation process leads to a dense numerical feature space for prompts, making the optimization problem easier.", "weaknesses": "1. This paper does not discuss the following recent prompt optimization methods:\n\n[1] Zekun Li, Baolin Peng, Pengcheng He, Michel Galley, Jianfeng Gao, and Xifeng Yan. Guiding large language models via directional stimulus prompting. Advances in Neural Information Processing Systems, 36, 2024.\n\n[2] Hao Sun, Alihan Hüyük, and Mihaela van der Schaar. Query-dependent prompt evaluation and optimization with offline inverse rl. In The Twelfth International Conference on Learning Representations, 2023.\n\n[3] Xinyuan Wang, Chenxi Li, Zhen Wang, Fan Bai, Haotian Luo, Jiayou Zhang, Nebojsa Jojic, Eric Xing, and Zhiting Hu. Promptagent: Strategic planning with language models enables expert-level prompt optimization. In The Twelfth International Conference on Learning Representations, 2024. 3\n\n2. For those compared methods, ZOPO did not consistently show advantages in Table 1 and Table 3 in Appendix D2.\n\n3. This paper emphasized efficiency. However, in Figure 5, Figure 10, and Appendix D.2, I can observe an obvious advantage in efficiency when compared with other methods. In addition, we can observe some results that are contradictory to the paper’s claim. In many scenarios in Figure 10, ZOPO does not show obvious advantages when the query number is small, which is contradictory to the 'query-efficient prompt' claim.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer TMXX for taking the time to review our paper and appreciate the reviewer's feedback. We would like to provide the following response to address the concerns and hope it can improve your opinion of our work.\n\n---\n\n> [W1] This paper does not discuss the following recent prompt optimization methods...\n\nIn fact, we have already covered a wide range of representative and most recent related works [3, 5, 8, 10, 17, 22, 29, 43, 44] in our main paper for the field of prompt optimization. We thank you for pointing out these additional related works. We will discuss those works in our revised paper.\n\n> [W2] For those compared methods, ZOPO did not consistently show advantages in Table 1 and Table 3 in Appendix D2.\n> [Q1] I cannot see a consistent advantage of ZOPO in many figures and tables. Can you explain this part? Thanks.\n\nIf the consistent advantages you mentioned mean that the proposed method should achieve the best performance across **the majority of tasks**, then our ZOPO has indeed demonstrated this **consistent advantage**. Actually our ZOPO has achieved the best performance on the largest number of tasks compared with other baselines in Table 1, which has dominated 14 out of 20 tasks vs. 8 out of 20 resulting from the second-best method INSTINCT [17]. The commonly used performance profile matrix [7] (defined in Eq. 10 of Appendix C.1) shown in Figure 1 has also supported this consistent advantage achieved by our ZOPO.\n\nHowever, if you are referring to consistent advantages to achieving the best performance on **every task**, we believe it is nearly impossible for a single algorithm to achieve these \"consistent advantages\", inspired by the no free lunch theorem in various fields [R1, R2].\n\nOverall, while ZOPO may not dominate every individual task (no other baseline method does), its superior average performance and higher frequency of achieving top results in our experiments can already underscore its effectiveness in practice. We believe this is sufficient to evidence the clear advantage of ZOPO across a broad spectrum of tasks.\n\n**References**\n\n[R1] Wolpert, D. H., & Macready, W. G. (1997). No free lunch theorems for optimization. *IEEE transactions on evolutionary computation*, 1(1), 67-82.\n\n[R2] Wolpert, D. H. (1996). The lack of a priori distinctions between learning algorithms. *Neural computation*, 8(7), 1341-1390.\n\n> [W3] This paper emphasized efficiency. However, in Figure 5, Figure 10, and Appendix D.2, I can observe an obvious advantage in efficiency when compared with other methods. In addition, we can observe some results that are contradictory to the paper’s claim. In many scenarios in Figure 10, ZOPO does not show obvious advantages when the query number is small, which is contradictory to the 'query-efficient prompt' claim.\n\nWe acknowledge that our method does not achieve **the highest efficiency in every individual task**. However, it consistently ranks among the top three most efficient methods across a wide range of tasks while the efficiency of other methods varies a lot for different tasks as shown in Figure 5 and Figure 10. These results should be reasonably sound to evidence that our ZOPO has **generally better query-efficiency** as claimed in our main paper (refer to line 281). We would add this clarification in our revised manuscript.\n\n---\n\nWe hope our clarifications have addressed your concerns and increased your opinions of our work. We are happy to provide any further clarification in the discussion period.", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
## **Global Response**

We sincerely appreciate the insightful feedback provided by the reviewers, which has significantly contributed to enhancing the quality of our paper. We hope we have addressed all questions raised by the reviewers, providing our clarifications and additional results. In this global response, we have attached an **Author Rebuttal PDF** file with the table and figure as additional results to support our response. Below, we summarize the  **strengths** of our paper as highlighted by the reviewers:

---
The reviewers have positively accepted several aspects of our work:
- The experiments conducted are thorough, rigorous, and comprehensive, demonstrating the promising empirical performance of ZOPO. The ablation studies are relevant and insightful (Reviewer `bDUw`, `GMgT`, `TQjw`).
- Our designed algorithm is intuitive, novel, efficient, and well-designed (Reviewer  `bDUw`, `GMgT`, `TQjw`, `TMXX`).
- Our empirical analysis in Section 3 is thorough and well-supported (Reviewer `TQjw`, `TMXX`).
- The visualization method we proposed is insightful and could serve as a crucial tool for studying the black-box prompt optimization landscape (Reviewer `GMgT`).
- The proposed input domain transformation simplifies the optimization problem (Reviewer `TMXX`).
- The paper is well-written and straightforward, with clear explanations of the motivation and reasoning (Reviewer `GMgT`,  `TMXX`). 

---
We would like to express our gratitude once again to the reviewers for their constructive feedback. We hope that our responses and clarifications have further improved your opinion of our work.

Best regards,

The Authors

Meta-review: There were no major outstanding concerns following the author rebuttal.

Reviewers were unanimously impressed by the visualization techniques, since they may be broadly applicable across LLM-based string-optimization tasks. The result showing the coincidence of local optima in the original and projected space is quite satisfying. This insight about the structure of the optimization space, instead of simply treating it as an end-to-end black-box as is done in prior work, is a major contribution of this paper.

For example, its ability to characterize smoothness v. ruggedness of a prompt generation scheme, can help diagnose optimization pathologies, and should lead to more rapid development of effective implementations, such as the one introduced in the paper: ZOPO.

I generally agree with reviewer ideas that ZOPO itself may not necessarily become the most common optimizer in practice, since the method is (1) somewhat more mathematically complicated than simpler approaches that stay completely in text space (e.g. OPRO), and (2) text-only methods often do perfectly fine (and it may be easier for practitioners to intuitively interpret their natural language behavior). However, the experimental results convincingly show that if one were forced to select a method today, without knowing the task a priori, ZOPO would be a good choice, and likely the optimal one.

Overall, I expect the paper to have a meaningful impact in the space of automated prompt optimization.
Decision: Accept (spotlight)