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_cc_2024_Conference
Published: 2024-05-15 11:39:31

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.

Main paper: 
 introduction: 
 In-context learning (ICL) has become an effective paradigm to help LLMs understand and generate appropriate responses when a few input-output pairs are provided to describe a specific task (Brown et al., 2020) . However, the outputs of LLMs can be highly sensitive and biased to the given ICL exemplars (Min et al., 2022) , leading to sub-optimal performance. On the other hand, in-context prompting also appears as an effective paradigm to instruct LLMs to generate desired outputs, where crafted prompts are added to the LLM's input (Ouyang et al., 2022) . Particularly, prompting can further leverage LLMs' capability of understanding ICL exemplars and thus improve performances. Such an approach is of particular interest when users interact with state-of-the-art LLMs like ChatGPT (OpenAI, 2024a) and GPT-4 (OpenAI, 2023) , which can only be accessed through black-box APIs (i.e., the interface of black-box LLMs only accepts discrete texts as input for querying). Therefore, optimizing in-context prompts becomes a critical effort in pursuing the optimal performance of black-box LLMs on downstream tasks.Although human knowledge may subjectively guide prompt designs (Mishra et al., 2021; Reynolds & McDonell, 2021) , this process is commonly time-intensive and its results are not always desirable in practice. To mitigate such human efforts and achieve better performance in optimizing crafted prompts, random sampling (Zhou et al., 2023) , Bayesian optimization (Chen et al., 2023; Lin et al., 2023) , and evolutionary algorithms (Guo et al., 2024) 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 strategies typically implement their prompt optimization across various input domains (i.e., natural texts (Guo et al., 2024; Zhou et al., 2023) or hidden embeddings (Chen et al., 2023; Lin et al., 2023) ), 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. Figure 1 : The performance profile for different methods on 20 tasks. A higher ρ(τ ) is better. More details in Sec. 5.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-efficient prompt optimization (Insight I in Sec. 3.1). Secondly, we visualize the estimated accuracy distributions for a number of prompt candidates and the corresponding function surfaces using various embeddings as 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 high-performing prompts, especially those local optimal ones (Insight II in 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. 1 . Motivated by Insight II, we first propose a general domain transformation that utilizes LLMs for prompt generation and existing embedding models for transforming these generated prompts into their corresponding hidden representations, which thereby enjoys not only the remarkable generation ability from any type of LLMs (white/blackbox) but also the impressive representation ability from existing embedding models for our prompt optimization (Sec. 4.1). Inspired by Insight I, we then leverage a cuttingedge zeroth-order optimization (ZOO) method enhanced by a derived Gaussian process for efficient gradient estimation (Shu et al., 2023a) to underpin our localized prompt optimization, which goes one step further by incorporating the Neural Tangent Kernel (NTK) (Jacot et al., 2018) to handle the complex and high-dimensional prompt optimization tasks (Sec. 4.2). Lastly, we present an uncertainty-informed local exploration method designed to improve the gradient estimation in our derived NTK-GP, thereby augmenting the practical performance of the ZOPO algorithm (Sec. 4.3).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. 3).• 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). 
problem setup: 
 Given an NLP task that is characterized by a data distribution D and a black-box LLM f (•), e.g., ChatGPT (OpenAI, 2024a) , discrete prompt optimization aims to generate a 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 x such that the queried LLM output f ([v; x] ) 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 Ω (Chen et al., 2023; Lin et al., 2023) :EQUATIONwhere R (f ([v; x] ), y) is applied to measure the alignment between the LLM output f ([v; x]) and the groundtruth y, and D V is the validation set sampled from D. Note that the performance of the optimal instruction found on D V (i.e., arg max v F (v)) will be evaluated on a held-out test set D T . 
local optima vs. global optimum: 
 In prompt optimization, methods like (Chen et al., 2023; Lin et al., 2023) are generally more effective than the others (Zhou et al., 2023; Guo et al., 2024) , 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 (Moriconi et al., 2020) . However, these methods sometimes perform poorly in certain prompt optimization tasks, e.g., cause and effect and informal to formal, indicating that they will fail to find the global optimum in these tasks given a limited query budget. This is likely because substantial portions of the budget are applied in these methods to explore the entire search space for the global optimum, which hence leads to the critical question about the necessity of finding 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 (Lin et al., 2023) ) are reduced by t-distributed stochastic neighbor embedding (t-SNE) (see more details in our Appx. D.1.1). 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 of prompt optimization tasks, making it extremely challenging to 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 animal of Fig. 2 ). Importantly, these local optima commonly enjoy relatively good performances, suggesting that local optima shall be more worthwhile to obtain in prompt optimization, especially for the scenarios of limited query budgets, as summarized below.Contrasting with the rarity of global optimum, local optima are usually prevalent and well-performed, which is more worthwhile for query-efficient prompt optimization.Besides, existing works (Chen et al., 2023; Guo et al., 2024; Lin et al., 2023) typically implement their prompt optimization across various input domains, leading to a wide range of performances in practice. These results thus inspire us to ask: How essential is the input domain for finding wellperforming prompts, particularly the local optimal ones? Thoroughly exploring this question is fundamental for the design of a well-performing prompt optimization algorithm.To answer this, we first visualize the accuracy distributions of 300 prompt candidates that are randomly generated by Vicuna-13B and ChatGPT for various tasks to study the essence of prompt generation in Fig. 3 (more details in Appx. D.1.2). Fig. 3 reveals that the prompt candidates produced by ChatGPT (a black-box model) generally exhibit better performance than those produced by Vicuna-13B (a whitebox model), which has been widely applied in (Chen et al., 2023; Lin et al., 2023) 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 animal of Fig. 3 ). These results indicate that the ability to generate 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. 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. Interestingly, Fig. 4 unveils that different embeddings will convey a varying number of well-performing local optima in practice. Particularly, the last token embedding is usually able to produce a larger number of well-performing local optima than the SBERT (i.e., a popular sentence embedding transformer (Reimers & Gurevych, 2019) ) embedding, making it easier to enjoy a good prompt optimization performance on this domain, as validated in Tab. 8. This therefore implies that the choice of the prompt embedding model is also essential for the finding of well-performing optima. In all, we conclude our aforementioned insights as below.The choice of the input domain, covering both the generation and the representation of prompt candidates, affects the identification of well-performing local optima.Algorithm 1 The ZOPO Algorithm1: Input: prompt generation model g(•), NLP embedding model h(•), size of prompt candidates m, iteration num- ber T , set V = ∅, set Z = ∅ 2: repeat 3: v ← g([D demo ]) 4: z ← h(v) 5: if v / ∈ V then V ← V {v}, Z ← Z {z} 6: until |V| = m 7: for t = 1 to T do 8: if 1 At (z t ) = 1 then do local exploration in Sec. 4.3 9: z t+1 = P Z (z t + η t µ t (z t )) 10: Query z t+1 to yield F (z t+1 ) 11: end for 12: z * ← arg max z 1:T F (z) 13: Return h -1 (z * ) 
the zopo algorithm: 
 Given the insights established in our Sec. 3, we then propose our Localized Zeroth-Order Prompt Optimization (ZOPO) algorithm (Algo. 1) for a better-performing as well as more query-efficient prompt optimization. Specifically, following our Insight II, we first develop a more general transformation for the input domain of prompt optimization (Sec. 4.1), which can enjoy both the remarkable generation ability from any type of LLMs (white/black-box) 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 a derived NTK Gaussian process inspired from (Shu et al., 2023a) to find well-performing local optima (Sec. 4.2). Lastly, we introduce an uncertainty-informed local exploration technique to refine the gradient estimation in our derived NTK Gaussian process, aiming to enhance the performance of our ZOPO algorithm in practice (Sec. 4.3).As introduced in our Sec. 3.2, the choice of 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 white/blackbox 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 ∈ Ω generated from a LLM g(•) and subsequently transform it into a continuous hidden representation z ∈ Z ⊂ R d by other sentence embedding model h(•) for the optimization, i.e., v = h -1 (z), where (1) can then be re-framed asmax z∈Z F (z) = E (x,y)∈D R f ([h -1 (z); x]), y . (2)Of note, our input domain transformation and (2) enjoy a number of major advantages compared with previous works: (a) Different from the direct optimization over the discrete and complex language space v ∈ Ω in (Guo et al., 2024) where optimization algorithms in the numerical domain can hardly be applied, our transformed input domain leads to a dense numerical space of lower dimension and therefore allows the usage of query-efficient optimization algorithms for (2) (e.g., our Algo. 1). (b) Different from the potential many-to-one mapping in the previous works (Chen et al., 2023; Lin et al., 2023) , i.e., the same discrete prompt v may be generated by various continuous soft prompts s, we develop a one-to-one mapping where one prompt generally has a unique hidden representation z, which thus can help eliminate the redundant queries during optimization and ultimately lead to 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-box) and the impressive representation ability from many NLP models whereas previous works are highly restricted to the LLMs, thus leading to a wider application.Practical Implementations. Before the start of the optimization on (2), we usually generate numerous prompt candidates V = {v} and their corresponding representations Z = {z} (line 2-6 of Algo. 1), where Z can be produced by an embedding model h(•). We store (z, v) in key-value pairs for constructing the one-to-one inverse mapping h -1 (•). Two practical methods are considered here for prompt generation: (a) Feeding randomly sampled soft prompts s ∈ R d and a few demonstrations D demo into a white-box LLM g(•). (b) Sampling the output distribution of a black-box LLM g(•) given a generation template filled with D demo . Specifically, if we consider the generation method in (a), z can be chosen as the last token embedding from g(•) (Lin et al., 2023) or the soft prompt s (Chen et al., 2023) when generating v. Here h(•) then represents a mapping function from v to z.As local optima are more prevalent than global optimum and can exhibit compelling performance for prompt optimization tasks (Sec. 3.1), we propose to apply zeroth-order optimization (ZOO), particularly 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 as many additional queries are required for gradient estimation in every gradient descent update (Flaxman et al., 2005; Nesterov & Spokoiny, 2017) . In light of this, we resort to the most recent ZoRD algorithm (Shu et al., 2023a) where a localized surrogate model will be applied for query-efficient gradient estimations.According to (Shu et al., 2023a) , given a well-specified kernel function k(•, •) such that the function F is sampled from a Gaussian process F ∼ GP(0, k(•, •)) or alternatively min G∼GP(0,k(•,•)) max z∈Z | F (z) -G(z)| = 0 and the observed value r of function F follows the Gaussian noise N (0, σ 2 ), then conditioned on the history of function queriesEQUATIONin which the mean function µ t (•) and the covariance function Σ 2 t (•, •) are defined asµ t (z) ≜ k t (z) ⊤ K t + σ 2 I -1 r t , Σ 2 t (z, z ′ ) ≜ k ′′ (z, z ′ ) -k t (z) ⊤ K t + σ 2 I -1 k t (z ′ ) . (4) Here, k t (z) ⊤ ≜ [∂ z k(z, z τ )] t τ =1 is a d × t-dimensional matrix, K t ≜ [k(z τ , k(z τ ′ )] t τ,τ ′ =1 is a t × t-dimensional matrix, r ⊤ t ≜ [r τ ] t τ =1 is a t-dimensional column vector, and k ′′ (z, z ′ ) ≜ ∂ z ∂ z ′ k(z, z ′ ) is a d×d-dimensional matrix.As a result, µ t (z) can be applied to estimate the gradient of the black-box function F at input z.Of note, the underlying black-box function F here is highly related to deep neural networks (DNN), more specifically transformers. It naturally inspires us to apply the Neural Tangent Kernel (NTK) (Jacot et al., 2018) theory for a better approach to the aforementioned assumption of a wellspecified kernel function k(•, •). This is because it has been widely proven that NTK is capable of well characterizing the predictions of neural networks (Arora et al., 2019; Lee et al., 2019; Shu et al., 2022a; b) and therefore should be a better-specified kernel in the setting of prompt optimization than the simple kernel (i.e., Matérn kernel) applied in ZoRD (Shu et al., 2023a) . Specifically, given a neural network ϕ(θ, z) parameterized by θ ∈ R p , we employ the following empirical NTK as the kernel in (3) and (4):k(z, z ′ ) = ∇ θ ϕ(θ, z) ⊤ ∇ θ ϕ(θ, z) θ=θ0 (5)where θ 0 is the initialized parameter of neural network ϕ. By incorporating (5) into (4), we realize the derived NTK-GP for the gradient estimation in our prompt optimization.Based on this derived NTK-GP, we finally apply standard first-order optimization (e.g., stochastic gradient descent) with projected gradients for our local prompt optimization. Specifically, in every iteration t of our Algo. 1, the next promising prompt candidate will be selected via:EQUATIONwhere P Z (z) ≜ arg min z ′ ∈Z ∥z -z ′ ∥ is the projection function that projects the updated z ∈ R d into domain Z and η t is learning rate.Practical Implementations. Following the localized modeling principle, only the neighbors of z in the query history D t are used to calculate the gradient µ t (z). As we 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 (Kratsios & Papon, 2022; Shen et al., 2022) . Our experiments in Sec. 5.4 will further validate the effectiveness of this implementation.Though the derived NTK-GP allows us to estimate the gradient at any z ∈ Z according to (Shu et al., 2023a) , we introduce the following Prop. 4.1 to demonstrate that the error in gradient estimation at a specific input z ∈ 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 ∈ Z. This insight, in turn, motivates the creation of our uncertaintyinformed local exploration approach, as opposed to the adoption of the virtual update mechanism described in (Shu et al., 2023a) for our prompt optimization strategy.Proposition 4.1. Assume k(z, z ′ ) ≤ α and ∥k ′′ (z, z)∥ ≤ κ for any z, z ′ ∈ Z. Let δ ∈ (0, 1) and N z,β ≜ {z ′ ∈ {z τ } t τ =1 | ∥∂ z k(z ′ , z)∥ 2 ≥ β} for given input z ∈ Z, thefollowing holds with a probability of at least 1 -δ,∥µ t (z) -∇F (z)∥ 2 ≤ ω Σ 2 t (z) ≤ ωκ - ωβ/d α + σ 2 /|N z,β | where ω = d + 2( √ d + 1) ln(1/δ) and Σ 2 t (z) ≜ Σ 2 t (z, z).The proof is given in Appx. A. Here, N z,β denotes a set of historical input queries that are effectively relevant for the gradient estimation at z where β can be regarded as a measure of effective relevance. Prop. 4.1 shows that the gradient estimation error of (3) at a specific input z ∈ Z is bounded by the norm of covariance matrix Σ 2 t (z), which is related to the query set N z,β of effective relevance. Specifically, the gradient estimation error at different z varies if the effective relevance β and the number of relevant queries |N z,β | varies with z. When β or |N z,β | 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 R d . That is, both the effective relevance β and the number of relevant queries |N z,β | can be small due to this sparsity. As a consequence, additional input queries should be conducted to increase both β and |N z,β | for better optimization.To this end, we propose an uncertainty-informed 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. 4.1. Specifically, we propose the local exploration condition informed by the local trajectory:1 At (z t ) = 1 z t ∈ A t 0 z t / ∈ A t where A t = {z t |σ(z t-i ) ≥ λ, ∀i ∈ [0, ξ]} is the condition that incorporates uncertainties and λ, ξ are the thresholds. If this condition is met (i.e., 1 At (z t ) = 1), we will query the neighbors of z t in the local region to update our derived NTK-GP, thus improving its gradient estimation.Practical Implementations. If we define the set of the n nearest neighbors of z t asN t ⊆ Z s.t. |N t | = n and ∀a ∈ Z \N t , ∥a-z t ∥ ≥ max b∈Nt ∥b-z t ∥, we propose to query each z ∈ N t in the local region, whenever 1 At (z t ) = 1. 
experiments: 
 In this section, we perform prompt optimization for Chat-GPT (i.e., f (•)) and evaluate the performance of ZOPO against several strong baselines, including APE (Zhou et al., 2023) , InstructZero (Chen et al., 2023) , INSTINCT (Lin et al., 2023) , EvoPrompt (Guo et al., 2024) , PromptBreeder (PB) (Fernando et al., 2023) , and OPRO (Yang et al., 2024) , on 30 instruction induction tasks (Honovich et al., 2023) , 3 arithmetic reasoning tasks (Cobbe et al., 2021; Ling et al., 2017; Patel et al., 2021) , and the GLUE benchmark (Wang et al., 2019) . The task-specific prompt is optimized for each task independently. We use the performance profile (Dolan & Moré, 2002) , defined in Appx. C.1, as the overall evaluation metric that measures the frequency (i.e., ρ(τ )) of a method within some distance (i.e., τ ) from the highest accuracy achieved by any method. We defer more experimental details to Appx. C.Instruction induction tasks are commonly used to investigate the prompt optimization performance by assessing LLM's zero-shot ICL ability in previous works (Chen et al., 2023; Lin et al., 2023; Zhou et al., 2023) . 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-13B as the prompt embedding (same as INSTINCT).Here Vicuna-13B is used to generate task-specific prompts by feeding random soft prompts. More experimental details are deferred to Appx. C.3.Superior performance of ZOPO. For better distinguishability, we follow the experimental setting from Lin et al. (2023) to display the results on 20 challenging tasks reported in Tab. 1, 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. 1 ) 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.ZOPO has better query efficiency. To justify that our local optimization method is more query-efficient, we compare ZOPO against baselines at different query budget scales. The results shown in Fig. 5 and Fig. 10 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 (Zhou et al., 2023) to generate task-specific prompts (i.e., V) from ChatGPT, and use a popular embedding model SBERT to provide the corresponding sentence embeddings (i.e., Z) for V. Then we apply ZOPO to perform optimization over the given V and Z, which we name ZOPO GPT . The result of ZOPO GPT compared against other baselines is shown in Tab. 1, with the corresponding performance profile shown in Fig. 9 in App. D.2. Fig. 9 demonstrates that ZOPO GPT significantly outperforms other baselines, achieving the best performance in 10 out of the 20 tasks as shown in Tab. 1. Specifically, ZOPO GPT achieves significantly higher accuracy on some challenging tasks such as second word letter and sentence similarity, which we attribute to the highquality 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 a direct comparison between ZOPO and ZOPO GPT , as the Vicuna last token embedding is specifically associated with the prompt generation process in ZOPO and cannot be applied to ZOPO GPT . However, using either ZOPO or ZOPO GPT 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 GPT .The hand-crafted prompt "Let's think step by step" (Kojima et al., 2022) (denoted as hand-craft) has been shown effective in improving LLMs' zero-shot multi-step reasoning performance. We show that ZOPO can find a better chain-of-thought prompt across different arithmetic reasoning tasks, as evidenced in Tab. 2 in Appx. C.4. Particularly, ZOPO produces a better prompt "Let's find the solution by using the given information." on GSM8K (Cobbe et al., 2021) compared to other baselines, improving the performance from 71.8 (hand-craft) to 75.4. Refer to Appx. C.4 for more experimental details.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 in Table . 7 in Appx. D.6, with the performance profile in Fig. 11 suggesting that applying ZOPO on ChatGPT-generated prompts is better. We ascribe its better performance to ChatGPT's remarkable prompt generation ability. This confirms the importance of the input domain on prompt generation in our Insight II.Besides, different embeddings (i.e., Z) 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-13B, the Ope-nAI embedding provided through an API (OpenAI, 2024b), the SBERT embedding, and a randomly projected embedding baseline. We observe from Tab. 8 in Appx. D.6 that, although last token embedding is generally better, there are certain tasks that OpenAI and SBERT embeddings perform equally well or better. Besides, random embedding shows a distinct lesser performance. This again highlights the im-portance of using more structured embeddings for prompt optimization and indicates the optimal choice of embedding can be task-dependent. We discuss how we might find better embeddings and further show the generality of ZOPO by experimenting with more embedding models in Appx. D.6. 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 in Table . 7 in Appx. D.6, with the performance profile in Fig. 11 suggesting that applying ZOPO on ChatGPT-generated prompts is better. We ascribe its better performance to ChatGPT's remarkable prompt generation ability. This confirms the importance of the input domain on prompt generation in our Insight II.Besides, different embeddings (i.e., Z) 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-13B, the OpenAI embedding (OpenAI, 2024b), the SBERT embedding, and a randomly projected embedding baseline. We observe from Tab. 8 in Appx. D.6 that, although last token embedding is generally better, there are certain tasks that OpenAI and SBERT embeddings perform equally well or better. Besides, random embedding shows a distinct lesser performance. This again highlights the importance of using more structured embeddings for prompt optimization and indicates the optimal choice of embedding can be task-dependent. We discuss how we might find the best embedding model and further show the generality of ZOPO by experimenting with more embedding models in Appx. D.6.  
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 instruction induction tasks, reasoning tasks, and GLUE benchmark demonstrate the efficacy of ZOPO, and ablation studies also validate the design and 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. 
 
 Appendix: A.1. Proof of Prop. 4.1We follow the ideas in (Shu et al., 2023a; b) to prove our Prop. 4.1. To begin with, we first introduce the following lemmas adapted from (Shu et al., 2023a ):Lemma A.1 (Thm. 1 in (Shu et al., 2023a) ). Let δ ∈ (0, 1) and ω ≜ d + 2( √ d + 1) ln(1/δ). For any z ∈ Z and any t ≥ 1, the following holds with probability of at least 1 -δ,∇ F (z) -µ t (z) 2 ≤ ω Σ 2 t (z) .Lemma A.2 (Lemma B.4 in (Shu et al., 2023a) ). For any z ∈ Z and any t ≥ 1, the following holdsΣ 2 t (z) ≤ Σ 2 t-1 (x) .Proof of Prop. 4.1. Recall that the covariance function (refer to (4)) of our derived NTK-GP conditioned on the history of function queries D t ≜ {(z τ , r τ )} t τ =1 of size t will beEQUATIONFor any c ∈ R and z ∈ Z, defineN z,β ≜ {z ′ ∈ {z τ } t τ =1 | ∥∂ z k(z, z ′ )∥ 2 ≥ β} with |N z,β | = N, the following then holds on the set N z,β :EQUATIONwhere (a) comes from the fact the maximum eigenvalue of a matrix is always larger or equal to its averaged eigenvalues, (b) is based on tr(AB) = tr(BA), (c) is from the definition of k N (z), and (d) results from the definition of N z,β .Meanwhile,Σ 2 t (z) (a) ≼ k ′′ (z, z) -k N (z) ⊤ K N + σ 2 I -1 k N (z) (b) ≼ κI -λ max (K N ) + σ 2 -1 k N (z) ⊤ k N (z) (c) ≼ κI - k N (z) ⊤ k N (z) N α + σ 2 (d) ≼ κ - N β/d N α + σ 2 I (9)where (a) comes from Lemma A.2, (b) is based on the assumption of ∥k ′′ (z, z)∥ ≤ κ and the definition of maximum eigenvalue. In addition, (c) comes from λ max (K N ) ≤ N max z,z ′ ∈N z,β k(z, z ′ ) (i.e., the Gershgorin theorem) and the assumption that k(z, z ′ ) ≤ α for any z, z ′ ∈ Z, and (d) is based on the results in (8).Finally, by introducing the results above into Lemma A.1, we conclude the proof.Localized Zeroth-Order Prompt OptimizationAs 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-box 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 to negative societal impacts. Therefore, we urge the black-box LLM API providers to impose a security check for the prompt that prevents users from querying for malicious purposes.Following previous works (Zhou et al., 2023; Lin et al., 2023) , we use the F1 score for tasks including common concept and informal to formal; we use the exact set matching for orthography starts with and taxonomy 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, we use the performance profile (Dolan & Moré, 2002) as the evaluation metric that measures the frequency (i.e., ρ(τ )) of a method within some distance (i.e., τ ) from the optimality achieved by any method, defined belowEQUATION)where Π is the set of all tasks, r π,m is the accuracy of method m on task π, and r * π = max{r π,m : ∀m ∈ M} is the best performance achieved by any method in M on task π. Specifically, ρ(0) represents the number of tasks where a method achieves the best performance. Accordingly, we use both ρ(0) and ρ(5) as the evaluation indicators in our tables to report the results.For all experiments using ZOPO in this work, we set the learning rate to 0.01, the uncertainty thresholds λ, ξ to 0.1 and 5 respectively, and the number n of nearest neighbors to query in local exploration (Section 4.3) to 10. A neural network with 2 fully connected layers of size 32 and ReLU activation functions is used in NTK-GP as the kernel. We use 20 nearest neighbors to fit the NTK-GP.In this subsection, we describe the experimental details of the instruction induction tasks.The same data partition and evaluation process as in previous works (Zhou et al., 2023; Chen et al., 2023; Lin et al., 2023 ) 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 D T . Specifically, 5 examples are sampled from the training set as the demonstrations (i.e., D demo ) for instruction induction, and another sampled 20 examples from the training set are used as the validation set D V to evaluate the objective function value as in Equation (1). The total query budget for each instruction induction task is fixed at 165 for all methods.To comprehensively compare with the baseline methods, we use GPT-3.5-turbo-0301 (supported by OpenAI API) as the black-box model for prompt evaluation and Vicuna-13B-v1.1 as the white-box LLM (i.e., g(•)) to generate the task-specific prompts by feeding g(•) with randomly sampled soft prompts and D demo , which is the same as InstructZero and INSTINCT.In the experiments, we only generate 500 prompt candidates for ZOPO (i.e., |V| = 500). Similarly, we also use 40 out of the 165 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 in Vicuna-13B) in optimization, InstructZero and INSTINCT use 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 et al. (2023) . 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 a 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 task-specific prompt from Vicuna-13B. The prompt generation template and the prompt evaluation template are shown below in the bounding boxes. We directly use the reported results of APE, IntructZero, and INSTINCT from Lin et al. (2023) for comparison, and we 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 to 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, as compared with using the relatively smaller model Vicuna-13B.To facilitate a more comprehensive comparison of different prompt optimization methods at different query budget scales, we set the maximum query budget to 200, and report the test accuracy of the best prompt found on the validation set with each incremental query budget, as shown in Fig. 5 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 5, without using the validation set to perform a grid search over the intrinsic dimension and the number of soft tokens. For our experiment on ZOPO GPT in the main text, we apply ZOPO on ChatGPT (i.e., GPT-3.5 turbo) generated prompts. We follow the generation template from APE (Zhou et al., 2023) , 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., D demo ) from the training set, and, for each D demo , 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. To harness the representation power of existing embedding models, we adopt the sentence transformer model (Reimers & Gurevych, 2019 ) "all-mpnet-base-v2" from HuggingFace to generate the high-dimensional sentence embedding for each generated prompt from ChatGPT.To improve the zero-shot chain-of-thought prompt performance on arithmetic reasoning tasks, we 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.e., GSM8K (Cobbe et al., 2021) , AQUARAT (Ling et al., 2017) , SVAMP (Patel et al., 2021) ). Similar as APE (Zhou et al., 2023) , we use all data from the test set for GSM8K and AQUARAT, and we sample 400 data points from AQUARAT's test set to evaluate the corresponding test accuracy. For all these three datasets, we sample 200 data points from their training dataset respectively as their individual validation dataset.We follow the experimental setting of Lin et al. (2023) : 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.Localized Zeroth-Order Prompt OptimizationIn 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 instruction induction datasets, including taxonomy animal, cause 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., it incurs monetary costs when we 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 a 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 to interpret the local optima visually, and we conclude that many local optima can already exhibit compelling performance. Prompt Generation To study the prompt quality of different prompt generation methods, we compare the prompts generated from Vicuna-13B and those generated from ChatGPT (i.e., GPT 3.5 turbo). For Vicuna-13B, we use the randomly sampled soft prompts with a fixed intrinsic dimension of 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 . It demonstrates that ChatGPT has a larger probability of generating prompts with higher accuracy, also with a larger mean. The result shows that ChatGPT-generated prompts are generally better, further validating our finding of the importance of the input domain. 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-13B here) to 2 by using t-SNE. The loss landscape is visualized in the surface plot shown in Fig. 8 . We observe that different optimization methods achieve similar performances on tasks like sentiment and singular to plural, 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. 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.1. 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 in Fig. 10 . We here follow the same experimental setting as our previous experiments on 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. Our algorithm ZOPO is in fact able to handle the few-shot settings as evidenced by the results in Tab. 5 below. Interestingly, the performance of our ZOPO is even better in a 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 to a better performance than the zero-shot setting. In this few-shot experiment, we provide exemplars for prompt evaluation and also report the test accuracy of the best prompt with exemplars provided. We use further experiments to show that our method can generalize to different prompt generation models and different black-box API LLMs for prompt evaluation (as f (•)). Specifically, we here consider two open-sourced models: Vicuna-13B and WizardLM-13B (Xu et al., 2024) 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 in our main text), PaLM2 (Anil et al., 2023) , and GPT-4. In total, we have six combinations. Tab. 6 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 on most tasks), which further verifies the generality of our method when a different black-box LLM f (•) is considered in the objective function in Eq. 1. 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. Instructor-Large) for GPT-4 generated prompts can even further improve its performance.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 e of the eigenvalues of the covariance matrix of the embeddings (i.e., Z). 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 in such representative space with equal spacing, it could help function modeling.Therefore, if such variance V e is small, the optimization performance using such an embedding model is more likely to be better. Based on the test accuracies from Tab. 9 and Tab. 10, we show that there exists a sufficiently high negative Spearsman's correlation (i.e., the average correlation is -0.47) between V e and the performance of ZOPO using different embedding models on each task. Therefore, we can check every embedding prior to the experiment, and it 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 a potential future direction. To validate the effectiveness of 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 (as in the recent ZOO 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 11 illustrates these two settings are both significantly worse than the original ZOPO, which validates the effectiveness of NTK-GP and uncertainty-informed local exploration. The prompt was to convert the given sentence into passive voice. antonymsThe prompt was to rewrite the given words into their opposite meaning. So, "humorless" becomes "humorous", "depressing" becomes "cheerful", "unwrap" becomes "wrap", "consumptive" becomes "generative", "uncoil" becomes "coil". auto categorizationThe prompt was to 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 debuggingThe prompt was to write a program that would take the given input and output the expected output. For example, the first input was a simple calculation, and the expected output was "2550". The second input was a class definition with a method, and the expected output was "5". cause and effectThe 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 conceptThe 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. diffThe prompt was to 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. first word letterThe prompt was to create a program that takes a single input (a word representing a legal concept or term) and outputs a corresponding letter of the alphabet that represents that concept or term. For example, if the input is "year", the program should output "y". informal to formal* The prompt was to rephrase each input sentence using a more formal or polite language. larger animalThe 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 listThe prompt was to create a program that takes a single word input (e.g. "year") and outputs a concatenated string of letters and spaces that approximates the pronunciation of that word (e.g. "y e a r"). negationThe 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 verbalThe 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 countingThe prompts were to provide the output of a given input, where the input is a list of 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. odd one out*The prompt was to identify the word that is most different from the others in the group. 


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

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: * The clarity of the algorithm could be improved (see the question part)

* The validity of the derived insights is not sufficiently high (see the question part)
questions: 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.
 
It 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.

L165. “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.

L197. “theta_0 is the initialized parameters …“ Is it trained? If so, how and when? 

Table 1. I couldn’t find the explanation of ZOPO_{GPT}. What is the difference between ZOPO and ZOPO_{GPT}?

The 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: limitations: A limitation has been addressed in the conclusion.
paper_summary: paper_summary: The paper proposes multiple contributions:

1. 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:
  * There is a correlation between the smoothness of the landscape and the strength of the prompt generator.
  * Much of the landscape is filled with local minima.

2. Proposes a new Bayesian Optimization-like algorithm, with the following setup:
* The regressor + uncertainty estimator is a NTK-GP using an MLP
* The acquisition maximization is a gradient descent in the embedding space, with a projection back into the original prompt space.
strength_weakness: strength_weakness: * 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?
  * 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).

* (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.
questions: questions: Please address the main questions in the weaknesses above. 

These are more for clarification:
1. 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$? 

2.  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: limitations: Section 7 discusses some limitations, but it may be worth considering the raised weaknesses above.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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: limitations: NA
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. This paper does not discuss the following recent prompt optimization methods:

[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.

[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.

[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

2. For those compared methods, ZOPO did not consistently show advantages in Table 1 and Table 3 in Appendix D2.

3. 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.
questions: questions: I cannot see a consistent advantage of ZOPO in many figures and tables. Can you explain this part? Thanks.
limitations: limitations: They listed the limitation and claimed to solve it in future work.

Comments: title: We would like to know if you have any further questions that require additional clarification
We would like to know if you have any further questions that require additional clarification
Thank you and we hope our clarification can improve your opinion of our work!
Thanks for the response
Thank you for your reply and the positive recognition!
Thanks for clarification
comment: Dear Reviewer TMXX,

Thank you for taking the time to review our paper and for your valuable feedback. We have provided clarifications above to address your concerns. We sincerely hope our clarifications could increase your opinion of our work.

If you have any more questions or need more details, we are happy to answer them promptly within the discussion period.


Best,

Authors
Dear Reviewer TQjw,

Thank you for taking the time to review our paper and for your valuable questions. We have provided clarifications above to respond to your questions and we hope we have increased your opinion of our work.

If you have any more questions or need more details, we are happy to answer them promptly within the discussion period.

Best,

Authors
Thank you very much for the prompt reply! We are happy to hear that our response is satisfactory.

Do let us if you have any further questions. We would be glad to address them and sincerely hope that our clarifications can improve your opinion of our work.
The things are now clearer and the response is satisfactory. Thanks.
Thank you so much for your positive feedback and thoughtful suggestions. We sincerely appreciate your recognition and support.

---
We are glad to hear that our clarification on the NTK procedure was helpful. We will simplify the writing to make this aspect clearer in the revision.

---
Regarding the smooth landscape visualizations, we are pleased that you found them compelling. Below is a detailed explanation of the process with the code snippet used for generating these plots:
1. We initialized the space (based on 300 randomly sampled prompt candidates) for each task and extracted embeddings and their corresponding values.
2. We then performed a t-SNE transformation to reduce the dimensions of the embeddings to two dimensions (X and Y)
3. We used griddata from SciPy to **linearly interpolate** the Z values on a grid. This allowed us to create a smoother surface from these scatter points before rendering.

Here is the code snippet for generating the landscape visualizations:

```python
import numpy as np
from sklearn.manifold import TSNE
import matplotlib.pyplot as plt
from scipy.interpolate import griddata

fig = plt.figure(figsize=(6,2), dpi=500)
tasks = ['taxonomy_animal', 'cause_and_effect', 'informal_to_formal']
for i, task in enumerate(tasks):
    emb_space = load_init_space(task)

    ax = fig.add_subplot(1,len(tasks), i+1, projection='3d')
    data = np.array([emb_space[emb]['data'].tolist() for emb in emb_space])
    Z = np.array([np.asarray(emb_space[emb]['function_value']).item() for emb in emb_space])

    # We first perform t-SNE on the embedding representation
    tsne = TSNE(n_components=2)
    transformed_data = tsne.fit_transform(data)
    # Store the 2D t-SNE feature as x and y.
    X, Y = transformed_data[:, 0], transformed_data[:, 1]

    xi = np.linspace(X.min(), X.max(), 60)
    yi = np.linspace(Y.min(), Y.max(), 60)
    xi, yi = np.meshgrid(xi, yi)

    # Linearly interpolate Z values on the grid
    zi = griddata((X, Y), Z, (xi, yi), method='linear')

    my_cmap = plt.get_cmap('YlOrRd')
    surf = ax.plot_surface(xi, yi, zi, cmap = my_cmap,
                       edgecolor ='none',antialiased=True,
                       linewidth=0,rstride =1,cstride =1,
                       vmin=0,vmax=1)
    ax.view_init(azim=20)
    plt.setp(ax.get_xticklabels(), visible=False)
    plt.setp(ax.get_yticklabels(), visible=False)
    plt.setp(ax.get_zticklabels(), visible=False)
    ax.set_axis_off()

plt.show()
```
Thanks for clarifying on the NTK procedure. I now understand that the NTK-GP is used for gradient estimation to perform local gradient updates instead. I recommend simplifying the writing to make this clear.

Is it possible to further explain in more detail on how you produced the landscape images or provide code? I actually tried this method on my own data, but was unable to get such smooth landscapes. Did you apply some form of local smoothing before rendering the plot?

As for other reviewer scores: It seems that other reviewers gave lower scores, primarily due to raising the issue of more comparisons. I am not bullish on requiring so many comparisons myself (there are probably 10+ different prompt tuning algorithms out there at this point anyways) as long as the method itself makes sense and is clean, so I will keep my current score.