Collaborative Discrete-Continuous Black-Box Prompt Learning for Language Models

Authors: Hualin Zhang, Haozhen Zhang, Zhekai Liu, Bin Gu, Yi Chang
Primary area: optimization
Keywords: Black-box prompt learning, discrete optimization

Abstract:
Large Scale Pre-Trained Language Models (PTMs) have demonstrated unprecedented capabilities across diverse natural language processing tasks. 
Adapting such models to downstream tasks is computationally intensive  and time-consuming, particularly in black-box scenarios common in Language-Model-as-a-Service (LMaaS) environments, where model parameters and gradients are inaccessible. Recently, black-box prompt learning using zeroth-order gradients has emerged as a promising approach to address these challenges by optimizing learnable continuous prompts in embedding spaces, starting with \textit{randomly initialized discrete text prompts}.  However, its reliance on randomly initialized discrete prompts limits adaptability to diverse downstream tasks or models. To address this limitation,
this paper introduces ZO-PoG, a novel framework that optimizes prompts through a collaborative approach, combining Policy Gradient optimization for initial discrete text prompts and Zeroth-Order optimization for continuous prompts in embedding space. By optimizing collaboratively between discrete and continuous prompts, ZO-PoG maximizes adaptability to downstream tasks, achieving superior results without direct access to the model’s internal structures.
Importantly, we establish the sub-linear convergence of ZO-PoG under mild assumptions.
The experiments on different datasets demonstrate significant improvements in various tasks compared to the baselines.

Decision: accept (poster)
Reviewer scores: 6, 5, 8, 5

Reviews and discussion:
<thread>
creation date:
1730537945137

thread_type:
official_review

<thread_object>
creator: reviewer_hhwu

<content>
summary:
This paper studies the problem of soft prompt optimization for pre-trained language models. In some previous works, random initialization is applied to a soft prompt which will be added to a low-dimensional vector's random projection. The authors proposed to optimize this random initialization as they believe this may lead to suboptimal performance. Technically, an alternating optimization method is proposed where the random initialization is optimized via a policy gradient method over token distributions, and the low-dimensional vector $z$ is optimized through zeroth-order optimization. Detailed convergence analysis is provided and empirical results are shown to justify the effectiveness of the proposed method.

strengths:
- This work improves previous literature with special consideration on optimizing the initialization of soft prompts. The mixing of discrete prompt and soft prompt optimization is also innovative.
- Theoretical analysis of convergence is given to justify the design and principle of the proposed alternating optimization method.

weaknesses:
- The authors stated their focus is on PTMs that can be interacted solely via APIs. However, most commercial models nowadays do not open embedding access,  which makes the soft prompt tuning method not practical and thus less significant. Especially in the experimental section, only a few white-box models are included and no black-box models are not considered.
- The recent literature on prompt optimization is not included. For example, InstructZero [1], ZOPO [2], and TRIPLE [3] were proposed to use a derivative-free method (Bayesian optimization or zeroth-order method) to optimize soft or discrete prompts. ZOPO and TRIPLE also project the discrete prompts into an embedding space to conduct optimization. Those methods need to be at least discussed and possibly compared.

[1] Chen, L., Chen, J., Goldstein, T., Huang, H., & Zhou, T. (2023). Instructzero: Efficient instruction optimization for black-box large language models.

[2] Hu, W., Shu, Y., Yu, Z., Wu, Z., Lin, X., Dai, Z., ... & Low, B. K. H. (2024). Localized zeroth-order prompt optimization. 

[3] Shi, C., Yang, K., Yang, J., & Shen, C. (2024). Best arm identification for prompt learning under a limited budget. 


- A strong motivation for this work is to improve the random initialization which is claimed to lead to a suboptimal performance. However, no empirical or theoretical justification is given. I suggest the authors conduct some ablation studies to demonstrate the sensitivity of prompt optimization performances given random initialization (number of random initialization or different random seeds). 
- Why alternating optimization is necessary? Could the author demonstrate the difference between <just using one round of soft-prompt optimization + one round of zeroth-order optimization> and <the alternating optimization strategy>? I also feel a joint optimization is feasible here, where the low-dimensional $z$ and the encoded probability of the initialization prompt can be jointly optimized by zeroth-order optimization. These points should be helpful for justifying why the alternating optimization is designed.
- Assumption 1 normally does not hold in practice, especially when the loss function only produces discrete values for some NLP tasks, e.g., accuracy. I understand this assumption has to be made for the theory to work, but at least some level of justification should be given.
- Limited empirical results.
    - More representative baselines proposed in recent years should be considered.
    - Only one benchmark (i.e., GLUE) is considered. I expect to see comparisons on other more practical benchmarks, such as mathematical reasoning task GSM8K and some text generation tasks.

questions:
See the questions above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730657615495

thread_type:
official_review

<thread_object>
creator: reviewer_phzg

<content>
summary:
In the paper "Collaborative Discrete-Continous Black-Box Prompting Learning For Language Model," the authors propose a new method for learning prompts, considering LLMs as a black box model. Under this assumption, the algorithms only have access to token and output (thus possible computation of a loss); therefore, it is impossible to access gradient and modify embeddings contrary to classical prefix tuning.



Similar to the CMA-ES approach, the authors propose to learn prompt embeddings in a low dimension and then project it to the input dimension of the model. The input embeddings correspond to the addition of the continuous prompt and representation of tokens of the vocabulary  $Az + p_0$($p_0$ sampled from the vocabulary). Contrary to previous approaches, authors propose to learn $z$ using the zeroth-order approximation.
In addition, the authors propose to learn the distribution of discrete prompt tokens over the vocabulary (sampling p_0). The distribution is approximated using the gamble softmax distribution, where parameters are estimated using a policy gradient with a baseline (REINFORCE).

The authors propose to analyze the convergence of the algorithm proposed in section 4. The approach is then evaluated on different GLUE tasks, and performances are compared with the manual prompt approach (designing the tokens of the prompts manually) and other black box prompting approaches. Three LLMs are compared: RoBERTa large, GPT2-XL, and Llama3. 
An ablation study is set up, removing the Gumbel softmax (using a policy gradient approach from [1] instead), removing the discrete prompts optimization and the continuous prompt optimization.   

For all experiments, the settings were tested at 20 and 50 prompt lengths.

The contributions are the following : 
 * A new algorithm for black box prompting.
 * A new approach to select (sample) $p_0$ for discrete prompts  using  Gumbel softmax (contrary to the previous approach, choosing random token vocabulary)
* State-of-the-art results in black box prompting.
* Convergence analysis of the proposed method

strengths:
* The approach and related works are well-described and motivated
* New algorithm  for black box prompting combining previous ideas with new one proposed
* Proposal of optimizing discrete prompt using gumbel softmax
* State-of-the-art result for approach in a black box setting
* Relevant Ablation study removing some part of the algorithm to judge the effect of the different component
 * Justification of the algorithm

weaknesses:
* Limited dataset and configuration (20 and 50-length prompt) evaluation
* The related works section could have been extended

questions:
* In the 5.1 section, the authors observed a significant difference depending on the model when compared to the manual prompt (first result line of the tables). Particularly, GPT2-XL and mostly Llama3 have, for most datasets, lower improvement using black box rather than manual prompt, particularly on the CoLA dataset. The authors state that it is due to the nature of the CoLA corpus. Does the fact that Roberta is an encoder only and the others are decoders (different pretraining tasks) have a role in this difference? The latter are thus more likely to get better performances on grammatically correct prompts.
* What is the prompt size for manual prompts? How did you select manual prompts?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730783424619

thread_type:
official_review

<thread_object>
creator: reviewer_yhre

<content>
summary:
This paper proposes a new approach to black-box prompt learning by jointly optimizing both discrete text prompts and continuous embeddings, with a convergence analysis. Experiments on five commonly used datasets demonstrate its superiority.

strengths:
- The paper is clearly written and easy to follow
- The proposed method is technically sound 
- The experimental results show the proposed method has a significant performance improvement.

weaknesses:
- My main concern lies in that why the authors did not employ the true black-box models, such as GPT-4 and Claude-3.5, as their backbone models. Since the proposed method aims at black-box prompt learning, it would be more convincing to show how it works with these leading black-box API.  Is it still necessary to optimize the prompts for such powerful models in terms of cost versus benefit? It would be much better to include these results. 
- Why choosing a random matrix $\textbf{A}$? Is it good enough? If not, why not optimizing it or how to choose a better one?
- How does the performance change as the prompt length increases? Better show more results on different lengths.
- Does this method works only on natural language tasks? How does it behave on math or code tasks?

questions:
See the weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730950702258

thread_type:
official_review

<thread_object>
creator: reviewer_sg5f

<content>
summary:
This paper introduces a framework for prompt optimization in LLMs that combines discrete and continuous prompt tuning. This framework alternates between optimizing discrete prompts through policy gradient methods and continuous prompts via zeroth-order gradient optimization. The authors establish the sub-linear convergence of ZO-PoG under assumptions of Smoothness, Bounded Variance, Bounded Loss, and Lower-Bounded Parameters. This framework was evaluated on five datasets (CoLA, MNLI, QNLI, SNLI, WNLI) from the GLUE benchmark using RoBERTa-large, GPT2-XL, and Llama3 as backbone models. The code has been provided.

strengths:
1. ZO-PoG combines discrete and continuous prompt optimization. Discrete prompts are refined through policy gradient in the parameter space, and continuous prompts are adjusted using zeroth-order gradients. This dual optimization approach enhances the adaptability and efficiency of prompt learning.
2. The authors provide a theoretical analysis showing ZO-PoG’s sub-linear convergence, validating its efficiency. Sub-linear convergence means that ZO-PoG requires fewer iterations to achieve satisfactory performance, making it a computationally efficient solution for black-box prompt learning.
3. The framework is tested on five datasets and demonstrates improvements over other black-box prompt learning methods. Results from the ablation study confirm that each component positively contributes to ZO-PoG’s overall performance, further validating its design choices.

weaknesses:
1. Assumption 3 requires the loss function to be bounded. Does this assumption hold for the loss function in LLM fine-tuning? If not, could this assumption be relaxed in the theoretical analysis presented in this paper?
2. This paper evaluates ZO-PoG on five datasets from the GLUE benchmark, while methods like BBT and SSPT report results on additional datasets. It would be valuable if the authors could provide performance comparisons of ZO-PoG on a broader range of datasets to offer a more comprehensive evaluation.
3. I recommend that the authors discuss the query complexity of zeroth-order optimization following the theorem, as this would provide a clearer understanding of the computational efficiency of the proposed approach.

questions:
Given that the loss function of LLMs is unbounded, I'm wondering if Assumption 3 can be relaxed in theoretical analysis to better reflect practical scenarios?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732705859019

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summarization of Paper Revisions

comment:
Dear Reviewers,

We appreciate your thorough evaluations and constructive feedback on our submission. We have carefully addressed all your comments and made the following revisions to improve the paper:

1. **Extended related work:** Reviewer PhZG suggested that the related work section could be extended. In the revised version, we have revised this part and included more recent work on black-box prompt learning.

2. **Discussions on query complexity:** As suggested by Reviewer sg5f, we added the discussion about the query complexity (here we refer to the times of forward passes of the pre-trained language models) of the proposed ZO-PoG method for converging to an $\epsilon$-approximate stationary point. 

3. **Discussions on experimental results:** We sincerely appreciate Reviewer PhZG's suggestion to consider the potential influence of architectural differences between encoder-only models (e.g., RoBERTa) and decoder-only models (e.g., GPT2-XL and Llama3) as the factor of performance gap on CoLA dataset when compared with the manual prompt. We have added the corresponding discussions in the revised section 5.2.

4. **Additional ablation studies** According to reviewers' suggestions and concerns, we have conducted additional ablation studies in Appendix Section C, including the effect of optimizing initial prompt (Reviewer hHWU), the effect of prompt length (Reviewer yHre, Reviewe PhZG) and the effect of optimization strategy (Reviwer hHWU).

5. **Additional experiments:** Reviewers yHre and hHWU had the concerns of our method on real black-box language models, which only accept prompt tokens as input. In response, we have extended our method to this more challenging setting in Appendix Section D. The core idea is to incorporate an open-sourced embedding model to project continuous embedding back to the discrete token space. To verify the effectiveness of ZO-PoG on more complex tasks with black-box language models. We have conducted experiments on the mathematical reasoning task GSM8K.

We appreciate the time and effort you have invested in reviewing our work. Your comments have significantly strengthened our submission, and we hope that the revisions address your concerns comprehensively.

Thank you again for your thoughtful feedback and consideration.

Best regards,

The Authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper introduces a new framework for prompt optimization in black-box LLMs that combines discrete and continuous prompt tuning using policy gradient and zeroth-order gradient optimization methods. The authors prove sub-linear convergence under certain conditions and demonstrate the effectiveness of their approach on five GLUE benchmark datasets. 

The reviewers generally appreciated that the paper is well-written and technically sound. The proposed ZO-PoG method enhances prompt learning adaptability and efficiency. The theoretical analysis provided further supports the method’s effectiveness. Although several questions and concerns were raised during the initial round of reviews, including: 1) whether the assumption of a bounded loss function holds for LLM fine-tuning, 2) the absence of real black-box LLMs in the study, 3) the limited number of evaluation datasets and the recommendation to compare with other methods, and 4) concerns about the choice of a random matrix, the need for alternating optimization, and the impact of prompt length, the authors have addressed most of these points in the rebuttal. The remaining major concern comes from reviewer hHWU, who questions the novelty of the approach, noting that the idea of steering a white-box model’s embedding and constructing an embedding lookup table is similar to existing works such as InstructZero and ZOPO. However, the authors argue that the primary novelty of this work lies in its solution to the performance gap induced by the random initialization of $p_0$, as well as its collaborative optimization framework using policy gradient and zeroth-order techniques, which is also recognized as innovative by hHWU. After careful reading of the paper and discussion, I agree with the authors on this point. Given that all other major concerns have been addressed, I recommend acceptance. However, I strongly suggest that the authors include the additional discussions and experiments in the final version.