Localized Zeroth-Order Prompt Optimization

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.

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. 2. Compared to methods that aim to find global optimization, incorporating NTK-based Gaussian processes in prompt optimization should theoretically be much faster. 3. 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: [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

I cannot see a consistent advantage of ZOPO in many figures and tables. Can you explain this part? Thanks.

Rating

3

Confidence

4

Soundness

2

Presentation

3

Contribution

2

Limitations

They listed the limitation and claimed to solve it in future work.

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.

Strengths

1. The thorough empirical study conducted provides a detailed comparison between local and global optima, highlighting the potential advantages of targeting local optima. 2. 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.

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.

Rating

5

Confidence

3

Soundness

2

Presentation

2

Contribution

2

Limitations

NA

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.

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. * The Bayesian optimization-like algorithm makes intuitive sense (bar the weaknesses, see below). This paper is well-written and is straightforward to read. * 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? * 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

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?

Rating

8

Confidence

4

Soundness

3

Presentation

4

Contribution

3

Limitations

Section 7 discusses some limitations, but it may be worth considering the raised weaknesses above.

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.

Strengths

* a novel and efficient prompt optimization algorithm targeted for a black-box API LLM * promising performance over baseline approaches * analysis and visualization of the objective function landscape using t-SNE

Weaknesses

* 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

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.

Rating

6

Confidence

3

Soundness

2

Presentation

2

Contribution

2

Limitations

A limitation has been addressed in the conclusion.

Thanks for clarification

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.

Thanks for the response

The things are now clearer and the response is satisfactory. Thanks.

We would like to know if you have any further questions that require additional clarification

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

We would like to know if you have any further questions that require additional clarification

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