Localized Zeroth-Order Prompt Optimization

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.

---

[W1] This paper does not discuss the following recent prompt optimization methods...

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

[W2] For those compared methods, ZOPO did not consistently show advantages in Table 1 and Table 3 in Appendix D2. [Q1] I cannot see a consistent advantage of ZOPO in many figures and tables. Can you explain this part? Thanks.

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

However, 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].

Overall, 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.

References

[R1] Wolpert, D. H., & Macready, W. G. (1997). No free lunch theorems for optimization. IEEE transactions on evolutionary computation, 1(1), 67-82.

[R2] Wolpert, D. H. (1996). The lack of a priori distinctions between learning algorithms. Neural computation, 8(7), 1341-1390.

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

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

---

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

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.

---

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.

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

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.

To clarify, the fully fine-tuning ZO approaches (e.g., MeZO) and prompt optimization ZO approaches (i.e., ZOPO) are designed for different contexts/settings.

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

We will add a detailed discussion comparing MeZO and ZOPO in our revised version.

---

We appreciate the reviewer's valuable input and hope our answers can address your concerns and increase your opinions of our work. Thank you!

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.

---

Firstly, 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.

[W1] Section 4.2 is not well-motivated

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

[W2] Statement on Bayesian Optimization

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

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

[Q1] Implementation of $h^{-1}$

Yes, 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).

[Q2] Eq. 6

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

---

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

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()

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.

---

[Q1] Validity of our insight

Thank you for your insightful comment. We address your concern below:

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

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

   • 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$.
   • 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.

   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.

We will include this clarification and the updated visualization to enhance our manuscript.

[R1] Van der Maaten, L., & Hinton, G. (2008). Visualizing data using t-SNE. Journal of machine learning research, 9(11).

---

[Q2] Section 4.1 and its novelty

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

[Q3] One-to-one mapping

To 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).

We will include a detailed clarification of this point in our revised manuscript.

---

[Q4] theta_0

No, 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.

[Q5] ZOPO_{GPT} in Table 1

The 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:

• 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].
• $\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.

We hope this clarifies the distinctions between the two variants and highlights the strengths of $\text{ZOPO}_{\text{GPT}}$.

[Q6] More queries

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

---

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