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

weakness 4: "why alternating optimization?"

Thank you for your valuable feedback. Alternating optimization was designed to leverage the complementary strengths of soft-prompt and continuous prompt optimization while mitigating their individual limitations. Soft-prompt optimization aligns the initialization with task-specific distributions, while continuous optimization fine-tunes embeddings for finer-grained task adjustments. By alternating, each stage benefits from the improvements made by the other, avoiding suboptimal convergence seen in single-round optimization.

Thank you for pointing out the potential of jointly optimizing the Gumbel-Softmax parameters and soft prompts using zeroth-order optimization. In our current approach, we use a policy gradient-based method, as it is specifically designed to handle discrete probability distributions. While zeroth-order optimization for Gumbel-Softmax parameters is theoretically feasible, it may introduce challenges such as higher gradient variance.

To further justify our design, we have included an experimental comparison of single-round optimization, joint optimization and alternating optimization in the revised manuscript.

Table: Comparison of average accuracy between one round ZO + one round Policy Gradient and ZO-PoG on Llama3 in 16-shot (per class)

The best results are underlined. Len represents the prompt length.

Table: Comparison of average accuracy between joint optimization with zeroth-order optimization and ZO-PoG on RoBERTa-Large in 16-shot setting

The best results are underlined. Len represents the prompt length.

weakness 5:

Thank you for your observation regarding Assumption 1 and its limitations in scenarios where the loss function is discrete, such as accuracy. In this paper, we focus on cross-entropy loss, which is a continuous and differentiable function commonly used as a surrogate for discrete metrics in NLP tasks. The smoothness assumption is valid for cross-entropy loss due to its Lipschitz continuous gradients and is essential for the theoretical convergence guarantees we provide. In the literature of zeroth-order fine-tuning of LLMs, such assumption was also utilized for the theoretical analysis [1]. Moreover, the purpose of this part is not solely to establish rigorous theoretical results but also to gain insights into the behavior of our method. We believe that selectively incorporating these assumptions can yield valuable guidance for developing more principled and effective approaches to black-box optimization, which could also helpful to optimize non-differentiable objectives like accuracy and F1 score.

[1] Fine-Tuning Language Models with Just Forward Passes. NeurIPS 2023.

weakness 6: Thanks for your suggestion. We have added the GSM8K dataset to show our algorithm performance on the math problems. In this experiment, we used GPT-4 to adapt our algorithm to a true black-box model.

Table: Averaged scores of baselines and Zo-PoG on the GSM8K dataset using GPT-4

We sincerely appreciate the reviewer’s insightful feedback. If there are any additional concerns or questions, please feel free to let us know.

We appreciate the time and effort put into reviewing our manuscript. Please find our responses to your concerns below:

weakness 1: Thank you for pointing this problem out. In the revised manuscript, we have adapted our method to the real black-box large language models. To tackle the problem having no access to the embedding space of black-box LLMs, we introduce to use an open-sourced embedding model to construct the mapping between the whole vocabulary and their embedding. To be specific, let $V_{s}$ denote the full vocabulary of the surrogate embedding model. Before the training of the algorithm, we will first need to compute the embedding ${ e(v) | v \in V_s }$ for all tokens in $V_{s}$. Then we could construct a lookup table $\{(v, e(v)) \mid v \in V_s\}$ for efficient access during training. During training, we define a projection function $e^{-1}(\cdot): R^D \to V_s^n$ that map a learned embedding $p \in R^D$ back to the nearest or the most similar token in $V_s$. In this work, we choose the cosine similarity as the projection function, i.e.,

which is a token-wise projection operation. By projecting the soft prompt back to the token space, we reformulated our approach to operate purely within the constraints of API-based interactions. To demonstrate the practicality and effectiveness of the updated method, we conducted additional experiments using GPT-4. The results, included in Appendix D.2 of the revised manuscript, show that our method achieves competitive performance on the mathematical reasoning task GSM8K while requiring no access to embeddings or model internals. This extension strengthens the significance of our work by aligning it with the limitations of modern commercial LLM APIs.

weakness 2: Thank you for pointing out the recent advancements in black-box prompt optimization, including InstructZero, ZOPO, and TRIPLE. We agree that these works are highly relevant and should be discussed to provide a more comprehensive context for our approach. We have revised the manuscript to include these methods in the related work section. For comparison, we conducted experiments on mathematical reasoning task GSM8K and compared our method with two black-box instruction optimization baselines: TRIPLE and InstructZero. The new results in Appendix D.2 demonstrate superior performance over these two instruction optimization methods. Note that, since our method are not dedicatedly designed for instruction optimization, the optimized discrete prompt may not be semantically meaningful. This is because our method are optimized directly for the downstream performance and didn't consider the semantic constraint, which may be a limitation of our method. We will consider this as a future work. However, considering the efficiency and scalability of our black-box prompt optimization method, it is still worthy of optimizing a task-specific prompt.

weakness 3: Thank you this question, to evaluate the impact of optimizing the initial discrete prompt, we conducted an ablation study where we compared the performance of ZO-PoG using optimized and randomly initialized initial prompts. Specifically, we investigated whether learning a task-specific distribution for selecting initial prompt tokens, instead of random selection, contributes to performance improvements across downstream tasks. To achieve this, we replaced sampling from Gumbel-Softmax with randomly selected tokens from the PTM vocabulary. Both setups employed the same continuous prompt optimization pipeline to isolate the impact of initial prompt optimization. The comparative results are reported in the following table. The comparative results indicate that models initialized with optimized discrete prompts consistently outperformed those using random initialization across all datasets.

Table: Comparison of the average accuracy (%) between randomly sampled $p_0$ and optimized $p_0$ (Zo-PoG) on Llama3 in 16-shot (per class)

Dear reviewer, thank you again for your time and effort put into reviewering our manuscript. Please let us know if our responses have addressed your concerns. If you have remaining concerns, please don't hestitate to let us know and we are happy to address them. Thank you!

Dear Reviewer hHWU

Thank you again for your time and effort dedicated to reviewing our paper. Please let us know if our responses have addressed your concerns. If you have remaining concerns, please don't hestitate to let us know and we are happy to address them.

With best wishes,

Authors

Dear Reviewer hHWU,

Thank you again for your time and effort dedicated to reviewing our paper. As the discussion phase is nearing its end, please let us know if our responses have addressed your concerns. If you have remaining concerns or questions, please don't hestitate to let us know and we are happy to discuss with you.

Best regards,

The Authors

In order to further verify the sensitivity of prompt initialization, we also tried the following different sampling strategies for $p_0$: 1) we sample the same token for each position of the fixed length prompt. 2) we uniformly randomly sample from the vocabulary (the same way as that sampled with random seeds). 3) We sample the continuous tokens of fixed length from the PTM vocabulary (this is the same way as implemented in BBT). We have also tried to directly sample $p_0$ in the embedding space as initialization through 3) Gaussian distribution (with the same mean and variance value for the sampling of random matrix $A$) and 4) uniform distribution within a fixed region (mean $\pm$ standard deviation of the sampling of random matrix $A$). For these ablations, we report the accuracy with three different random seeds. 6) Orthogonal initialization: each token embedding in $p_0$ are orthogonal with each other.

Table: Accuracy (%) on RoBERTa-Large in 16-shot (per class) setting with different initialization strategy

For all the above ablation studies, $p_0$ will be fixed during the optimization process and only the low dimensional soft prompt will be optimized. The above results state that performance of black-box prompt learning is sensitive to the random initialization, which motivates us to optimize the initial prompt distribution.

For Weakness 4, we need to clarify that our ZO-PoG alternatively conduct discrete optimization and continuous optimization iteration by iteration. Whereas "one round + one round" optimization strategy means that we first optimize soft prompt $z$ while keep $p_0$ fixed (this is the first round), and then we optimize $p_0$ while keep soft prompt fixed (this is the second round). Both optimization strategies are under the same budget limit for fair comparison. In the final version of the manuscript, we will include the corresponding discussions of the interpretation of different optimization strategies.

Dear reviewer,

Thank you so much for acknowledging our additional results and your remaining questions.

First, we want to emphasize that the main focus and novelty of this work is to solve the problem of performance gap of black-box prompt learning induced by the random initialization of $p_0$. In order to tackle this problem, we propose to collaboratively optimize the discrete prompt in the token space and the continuous soft prompt in the embedding space. In order to adapt our method to the setting of the black-box large language models, it should be a necessity and also a natural idea to project the optimized soft prompt back to the token space by using the white-box large language models. Moreover, our projection method is a bit different from the one used in ZOPO, which compares the Euclidean distance of the optimized soft prompt and the candidate prompt embedding. As a comparison, we implement the projection by computing the token-wise cosine similarity of token embedding and the whole vocabulary embedding.

For Weakness 3, thank you for your clarification. In our original response to this question, we conduct an ablation study on the randomness of the prompt initialization by sampling with three random seeds and report the average accuracy. For better demonstration on the sensitivity of prompt optimization performances given random initialization, we report the accuracy result with three random seeds respectively as in the following table:

Table: Accuracy (%) of randomly sampled $p_0$ with random seeds on Llama3 in 16-shot (per class) setting

Moreover, we conducted additional experiments on RoBERTa-Large under the same setup.

Table: Accuracy (%) of randomly sampled $p_0$ with random seeds on RoBERTa-Large in 16-shot (per class) setting

Dear Reviewer hHWU,

We sincerely appreciate your willingness to engage in discussions with us and for your suggestion of our paper.

We understand your concern about the extension to the black-box large language models. However, we don't think this will hurt the novelty of this work. Our framework, ZO-PoG, uniquely integrates discrete and continuous prompt optimization in a collaborative manner. By alternating between discrete prompts optimized via policy gradients and continuous prompts refined through zeroth-order gradients, we bridge gaps in adaptability and efficiency that are not addressed in prior methods. The novelty of our method lies in the collaborative optimization of discrete and continuous prompts using policy gradient and zeroth-order techniques. This fundamental contribution remains unchanged, irrespective of the model type. Instead, extending the application of our framework to the black-box large language model setting could enhance the work’s robustness and scalability.

Thanks again for your suggestion. Providing the results obtained from using different seeds and various sampling methods indeed enhances the motivation of our paper. Since modifications to the current manuscript are not permitted, we commit to including additional discussions and graphical presentations of these results in future revised versions.

We apologize for the manner in which the results were presented in the Llama3 table in our previous response, as this presentation may have caused misunderstandings. In the previous Llama3 table, to illustrate the sensitivity of prompt performance to random seeds, we separately reported the results of runs for each seed using the method of initializing $p_0$ with random sampling, as well as the average performance over multiple runs using our method. This biased comparison created the false impression that initializing with random sampling yields the highest performance. To clarify this misunderstanding, we provide the results of our method across various runs and offer a fair comparison based on the maximum and average values, as shown in the table below. It is evident that our method outperforms random sampling initialization in both average and maximum values, thereby demonstrating its effectiveness. Regarding your mention of optimizing random seeds, we don't think this is a fair comparison to our method, as it equates to comparing the maximum performance achieved through random initialization with the average performance of our method.

Table: Accuracy (%) on Llama3 in 16-shot (per class) setting

Best regards,

The Authors

We appreciate the time and effort put into reviewing our manuscript. Please find our responses to your concerns below:

weakness 1: "Limited dataset and configuration (20 and 50-length prompt) evaluation":

Thank you for this question. We have conducted an ablation study on the effect of th prompt length. The results in the following table show that the relationship between prompt length and model performance is non-linear. Short prompts may demonstrate limited representational capacity, leading to suboptimal performance and longer prompts do not necessarily produce better result. The observed trends suggest that a moderately long prompt provides a good trade-off between capacity and learnability.

Table: Ablation study of prompt lengths on Llama3 in 16-shot (per class) setting with the QNLI dataset

weakness 2: Thank you for your suggestions. In the revised version, we have added some more recent work.

question 1: We thank the reviewer for the insightful observation regarding the differences in performance between models when comparing black-box prompts to manual prompts, particularly on the CoLA dataset. We also appreciate the 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). In the revised manuscript, we have expanded our discussion about this point as follows: When using GPT2-XL and Llama3 as backbone models on the CoLA dataset, all prompt learning methods perform worse than manual prompts. This can be attributed to the CoLA task’s focus on grammatical acceptability, which aligns better with the pretraining objectives of encoder-only models like RoBERTa. Decoder-only models like GPT2-XL and Llama3, pretrained for generative tasks, are less sensitive to grammatical correctness unless explicitly encoded in the prompt. Additionally, learned prompts, such as those from BDPL, may include grammatically incorrect tokens, further impairing the performance of decoder-only models. In contrast, manual prompts, designed with grammatical correctness, provide clearer guidance for these models, explaining their superior performance on CoLA.

question 2: The details of manual prompts template are included in Appendix B.1 with no additional learnable prompts, which are chosen by following previous baselines.

We sincerely appreciate the reviewer’s insightful feedback. If there are any additional concerns or questions, please feel free to let us know.

Dear Reviewer PhZG,

Thank you again for your time and effort dedicated to reviewing our paper. As the discussion phase is nearing its end, please let us know if our responses have addressed your concerns. If you have remaining concerns or questions, please don't hestitate to let us know and we are happy to discuss with you.

Best regards,

The Authors

We appreciate the time and effort put into reviewing our manuscript. Please find our responses to your concerns below:

weakness 1: We appreciate your insightful suggestion regarding the evaluation of our proposed method on truly black-box models such as GPT-4. In the revised manuscript, we have adapted our method to the real black-box large language models. To tackle the problem having no access to the embedding space of black-box LLMs, we introduce to use an open-sourced embedding model to construct the mapping between the whole vocabulary and their embedding. To be specific, let $V_{s}$ denote the full vocabulary of the surrogate embedding model. Before the training of the algorithm, we will first need to compute the embedding ${ e(v) | v \in V_s }$ for all tokens in $V_{s}$. Then we could construct a lookup table $\{(v, e(v)) \mid v \in V_s\}$ for efficient access during training. During training, we define a projection function $e^{-1}(\cdot): R^D \to V_s^n$ that map a learned embedding $p \in R^D$ back to the nearest or the most similar token in $V_s$. In this work, we choose the cosine similarity as the projection function, i.e.,

which is a token-wise projection operation. By projecting the soft prompt back to the token space, we reformulated our approach to operate purely within the constraints of API-based interactions. To demonstrate the practicality and effectiveness of the updated method, we conducted additional experiments using GPT-4. The results, included in Appendix D.2 of the revised manuscript, show that our method achieves competitive performance on the mathematical reasoning task GSM8K while requiring no access to embeddings or model internals. This extension strengthens the significance of our work by aligning it with the limitations of modern commercial LLM APIs.

Table: Averaged scores of baselines and Zo-PoG on the GSM8K dataset using GPT-4

weakness 2: Thank you for pointing this problem out.

``why choosing a random matrix?": In our framework, we choose a random projection matrix $A$ to efficiently explore the intrinsic subspace of the embedding space. This choice is motivated by its simplicity and computational efficiency, which make it well-suited for the black-box optimization setting.

"Is it good enough?": Random projections have been shown to work well in many scenarios, as observed in our experiments.

"why not optimizing it?": The original embedding space of pre-trained language models is often extremely high-dimensional, which makes direct black-box optimization computationally prohibitive. Optimizing $A$, which is of dimension $R^{D\times d}$, introduces additional computational overhead and may complicate the optimization process.

"How to choose a better one?": Actually, the baseline method SSPT we compared in the experiment explored choosing a better one by employing subspace learning to identify the optimal ultra-low-dimensional subspace. Considering the optimization complexity for $A$, we instead utilize a random, which already yields good performance in practice.

weakness 3: We appreciate the reviewer’s insightful suggestion regarding the impact of prompt length on performance. In the revised version, we have conducted an ablation study exploring the effect of prompt length on model performance. The results indicate that a moderate length prompt is optimal and longer prompts do not necessarily produce better results. The results, along with more detailed analysis, are included in the revised manuscript in Appendix section C.

Table: Ablation study of prompt lengths on Llama3 in 16-shot (per class) setting with the QNLI dataset

weakness 4: Thanks for this question. In the revised version, we have conducted experiments on the GSM8K dataset to show our algorithm performance on the math problems. In this experiment, we used GPT-4 to adapt our algorithm to a true black-box model.

We sincerely appreciate the reviewer’s insightful feedback. If there are any additional concerns or questions, please feel free to let us know.

Dear Reviewer yHre,

Thank you again for your time and effort dedicated to reviewing our paper. Please let us know if our responses have addressed your concerns. If you have remaining concerns, please don't hestitate to let us know and we are happy to address them.

With best wishes,

Authors

Dear Reviewer yHre,

Thank you again for your time and effort dedicated to reviewing our paper. As the discussion phase is nearing its end, please let us know if our responses have addressed your concerns. If you have remaining concerns or questions, please don't hestitate to let us know and we are happy to discuss with you.

Best regards,

The Authors

We appreciate the time and effort put into reviewing our manuscript. Please find our responses to your concerns below:

weakness 1: Thank you for pointing out this important consideration regarding the boundedness of the loss function. While the cross-entropy loss used in our work is theoretically unbounded, in practice, it behaves as effectively bounded during large language model (LLM) fine-tuning. This is due to numerical stability in softmax calculations, and the finite precision of modern computing hardware, which prevent predicted probabilities from reaching exactly zero. Furthermore, empirical observations across LLM fine-tuning tasks consistently show that the loss remains within a stable and reasonable range, which aligns with the boundedness assumption.

weakness 2: Thanks for your suggestion. In the revised version, we have included more experimental results to verify the effectiveness of ZO-PoG. Specifically, we have adapted our method to the real black-box large language models. To tackle the problem having no access to the embedding space of black-box LLMs, we introduce to use an open-sourced embedding model to construct the mapping between the whole vocabulary and their embedding. To be specific, let $V_{s}$ denote the full vocabulary of the surrogate embedding model. Before the training of the algorithm, we will first need to compute the embedding ${ e(v) | v \in V_s }$ for all tokens in $V_{s}$. Then we could construct a lookup table $\{(v, e(v)) \mid v \in V_s\}$ for efficient access during training. During training, we define a projection function $e^{-1}(\cdot): R^D \to V_s^n$ that map a learned embedding $p \in R^D$ back to the nearest or the most similar token in $V_s$. In this work, we choose the cosine similarity as the projection function, i.e.,

which is a token-wise projection operation. By projecting the soft prompt back to the token space, we reformulated our approach to operate purely within the constraints of API-based interactions. To demonstrate the practicality and effectiveness of the updated method, we conducted additional experiments using GPT-4. The results, included in Appendix D.2 of the revised manuscript, show that our method achieves competitive performance on the mathematical reasoning task GSM8K while requiring no access to embeddings or model internals. This extension strengthens the significance of our work by aligning it with the limitations of modern commercial LLM APIs.

Table: Averaged scores of baselines and Zo-PoG on the GSM8K dataset using GPT-4

weakness 3: Thank you for your suggestion, in the revised version, we have added the corresponding discussions about the query complexity. To be specific, the theorem establishes that ZO-PoG achieves an $\epsilon$-stationary point in expectation with total query complexity ( times of forward passes of the PTMs) $T\cdot I = \mathcal{O} \left( \frac{\sqrt{n\kappa}}{\epsilon^3} \right)$.

questions: As discussed above in response to weakness 1, we think the bounded loss assumption is a general assumption and is reasonable in practical scenarios.

We sincerely appreciate the reviewer’s insightful feedback. If there are any additional concerns or questions, please feel free to let us know.

Dear Reviewer sg5f

Thank you again for your time and effort dedicated to reviewing our paper. As the discussion phase is nearing its end, please let us know if our responses have addressed your concerns. If you have remaining concerns or questions, please don't hestitate to let us know and we are happy to discuss with you.

Best regards,

The Authors