BBTv2: Pure Black-Box Optimization Can Be Comparable to Gradient Descent for Few-Shot Learning

Black-Box Tuning (BBT) is a derivative-free approach to optimize continuous prompt tokens prepended to the input of language models. Although BBT has achieved comparable performance to full model tuning on simple classification tasks under few-shot settings, it requires pre-trained prompt embedding to match model tuning on hard tasks (e.g., entailment tasks), and therefore does not completely get rid of the dependence on gradients. In this paper we present BBTv2, a pure black-box optimization approach that can drive language models to achieve comparable results to gradient-based optimization. In particular, we prepend continuous prompt tokens to every layer of the language model and propose a divide-and-conquer algorithm to alternately optimize the prompt tokens at different layers. For the optimization at each layer, we perform derivative-free optimization in a low-dimensional subspace, which is then randomly projected to the original prompt parameter space. Experimental results show that BBTv2 not only outperforms BBT by a large margin, but also achieves comparable or even better performance than full model tuning and state-of-the-art parameter-efficient methods (e.g., Adapter, LoRA, BitFit, etc.) under few-shot learning settings, while maintaining much fewer tunable parameters.


Introduction
Pre-Trained Models (PTMs) (Devlin et al., 2019;Liu et al., 2019;Lewis et al., 2020;Raffel et al., 2020;Qiu et al., 2020) have pushed the state-of-the-art of many NLP tasks. Especially, supersized PTMs such as GPT-3 (Brown et al., 2020) can easily adapt to downstream tasks even with a few labeled samples. However, it is expensive for most users to locally run such supersized models. In addition, parameters of some 1 Work in progress. Code is publicly available at https: //github.com/txsun1997/Black-Box-Tuning. large-scale PTMs are inaccessible due to commercial reasons. Hence, supersized PTMs are often released as public services, allowing users to access the models through black-box APIs.
In such a scenario, namely Language-Model-asa-Service (LMaaS) (Sun et al., 2022b), considerable performance has been observed in many use cases (Brown et al., 2020). For instance, one can hand-craft textual prompts and include some labeled samples in the prompts (a.k.a. in-context learning (Brown et al., 2020)) that are then concatenated with input texts to query PTMs. Nevertheless, in-context learning heavily relies on humandesigned prompts and suffers from high variances. Recently, Sun et al. (2022b) propose the black-box tuning (BBT), which optimizes continuous taskspecific prompts using derivative-free optimization (DFO) algorithms. Although it has been demonstrated that, BBT with RoBERTa (Liu et al., 2019) achieves comparable or better performance than full model tuning on simple text classification tasks (e.g., sentiment analysis), it lacks versatility across tasks and language models. BBT struggles on more complicated tasks: on hard tasks (e.g., natural language inference), BBT still under-performs model tuning if not using pre-trained prompt embedding; the convergence of BBT can be slow when the number of classes becomes large (e.g., fine-grained topic classification tasks). Besides, our pilot experiments ( §2.2) show that, when switching to other PTMs, BBT has no promise in generalizing to unseen data, though it fits well on training data.
In this paper, we present BBTv2 to improve BBT across tasks and language models. We draw inspiration from two lines of work: (1) deep prompt tuning and (2) divide-and-conquer (DC) methods for high-dimensional DFO. On the one hand, deep prompt tuning, which is to prepend and optimize continuous prompt tokens at each layer of the PTM, has been demonstrated to significantly improve performance on various language understanding and generation tasks (Li and Liang, 2021;Qin and Eisner, 2021;Liu et al., 2021b). Hence, a straightforward extension of BBT is to optimize the deep prompts instead of the prompts merely in the input layer. However, the deep prompts contain an order of magnitude more parameters, posing a challenge for high-dimensional DFO. On the other hand, fortunately, we find that the forward computation of modern PTMs can be decomposed into an additive form w.r.t. the hidden states of each layer thanks to the residual connections. Therefore, the high-dimensional optimization problem can be decomposed into multiple low-dimensional subproblems, each corresponding to the prompts at one layer. Based on this insight, we propose a divideand-conquer algorithm to alternately optimize the prompt tokens at each layer. For the optimization at each layer, we maintain a random projection that maps the prompt parameters into a lowerdimensional subspace and perform derivative-free optimization in the generated subspace.
Experimental results show that BBTv2 significantly improves BBT on average performance across 7 language understanding tasks. As shown in Figure 1, BBTv2 also achieves comparable or even better performance than full model tuning and state-of-the-art parameter-efficient tuning methods including Adapter (Houlsby et al., 2019), BitFit (Zaken et al., 2022), LoRA (Hu et al., 2021), and P-Tuning v2 (Liu et al., 2021b), while with much fewer tunable parameters.

Pilot Experiments
First we conduct pilot experiments to demonstrate the limitations of BBT across tasks and models.

Limitations Across Tasks
Unsatisfactory Performance on Entailment Tasks. As demonstrated by Sun et al. (2022b), BBT can outperform model tuning on entailment tasks when using pre-trained prompt embedding for initialization. However, pre-trained prompt embedding is not always available for many languages and models. Without pre-trained prompt embedding, BBT is still lagging behind model tuning on entailment tasks. In other words, BBT does not completely get rid of the dependence on gradients to exceed model tuning. In contrast, as depicted in Figure  Slow Convergence on Classification Tasks with Many Classes. BBT suffers from slow convergence rate when the number of classes becomes large. As reported by Sun et al. (2022b), BBT cannot converge within a budget of 8,000 API calls, which is sufficient for common tasks to converge, on DBPedia , a topic classification task with 14 classes. Figure 3 shows the cross entropy loss and the accuracy on the training set during training. Compared with BBT, the proposed BBTv2 significantly accelerate the convergence on DBPedia.

Limitations Across Models
Overfitting on Training Data. When switching the backbone model from RoBERTa (Liu et al., 2019) to other PTMs, we find that BBT tends to overfit training data. As shown in Figure 4, the original BBT with BERT LARGE (Devlin et al., 2019) and BART LARGE (Lewis et al., 2020) can achieve 100% accuracy on the SST-2 training set, but achieves little improvement on the development set. We conjecture that the random projection adopted by the original BBT hinders its generalization. By generating random projections with normal distributions ( §3.3), our modified BBT and BBTv2 exhibit stronger generalization ability.

Methods
We first introduce the original BBT in § 3.1, and then describe the proposed BBTv2 in § 3.2. In §3.3, we revisit the random projection with normal distribution.

Black-Box Tuning
Black-Box Tuning (BBT) (Sun et al., 2022b) is a derivative-free framework to drive PTMs for fewshot learning. In particular, for a batched training data (X, Y ), we first convert the texts X with some pre-defined templates (e.g., "It was [MASK]") intõ X, and the labels Y with a pre-defined map into label wordsỸ (e.g., "great" and "terrible"). By this, we can formulate various downstream tasks into a general-purpose (masked) language modeling task and utilize the pre-trained (masked) language modeling head to solve them. Assume the PTM inference API f takes a continuous prompt p and a batch of textsX as input, and outputs the logits of the tokens of interest (e.g., the [MASK] token). BBT seeks to find the optimal prompt p = arg min p∈P L(f (p;X),Ỹ ), where P is the prompt space and L is some loss function such as cross entropy. The closed form and the gradients of f are not accessible to BBT. Since the prompt p ∈ R D usually has tens of thousands of dimensions, making it infeasible to be optimized with derivative-free optimization (DFO) algorithms. Hence, BBT adopts a random projection A ∈ R D×d to generate a low-dimensional subspace Z ∈ R d and performs optimization in the generated subspace, i.e., where p 0 is the initial prompt embedding. If not using pre-trained prompt embedding, p 0 is the word embeddings randomly sampled from the PTM vocabulary.

Algorithm 1: Black-Box Tuning v2
Require: L-layer PTM Inference API f ; Budget of API calls B; Derivative-free optimizers {M j } L j=1 1: Initialize random projections A 1 , . . . , A L and parameters to be optimized z end for 8: end for 9: return Optimized deep prompts p = p 1 , . . . , p L BBT adopts the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) (Hansen and Ostermeier, 2001;Hansen et al., 2003) to optimize Eq.(1) and obtain the desired prompt p = Az . The random projection A is frozen during optimization.

BBTv2: Deep Black-Box Tuning
Though BBT achieved comparable performance to model tuning on simple classification tasks, our pilot experiments ( §2) show that it lacks versatility across tasks and language models. As an improved variant of BBT, BBTv2 seeks to generalize BBT across tasks and models through deep prompts.
Inspired by the success of deep prompt tuning (Li and Liang, 2021; Qin and Eisner, 2021;Liu et al., 2021b), we manage to inject continuous prompt tokens to every layer of the PTM and optimize them with DFO methods. Compared to BBT that optimizes the prompts merely in the input layer, BBTv2 has an order of magnitude more parameters. For a PTM with L layers, BBTv2 seeks to optimize p = p 1 , . . . , p L , where p i ∈ R D . Hence, the number of parameters to be optimized becomes LD. Say we are using RoBERTa LARGE with 24 layers and insert 50 prompt tokens at each layer, the total number of parameters to be optimized is 1.2M. Instead of simply extending the dimension of the random projection matrix A to LD × d, we propose a divide-and-conquer (DC) algorithm to handle the increased parameters.
In fact, DC is another effective technique to cope with high-dimensional DFO problems by decomposing the original high-dimensional problem into multiple low-dimensional subproblems, and solving them separately (Kandasamy et al., 2015;Mei et al., 2016). The key assumption of applying DC is that, the objective f can be decomposed into some additive form. Fortunately, modern PTMs can be expanded into an additive form due to the residual connections (He et al., 2016). For instance, a three-layered PTM can be decomposed as where f i is the transformation function of the i-th layer, x i is the input of the i-th layer, and x 1 is the input embedding. Thus, optimizing the continuous prompts {p i } L i=1 attached to the hidden states at every layer {x i } L i=1 can be regarded as independent subproblems. 2 Since the assumption is satisfied, we propose a DC-based algorithm, which is described in Algorithm 1, to implement BBTv2.
The prompts at different layers are optimized alternately from bottom to up. For the optimization at each layer, we maintain a specific random projection A j and a CMA-ES optimizer M j . When alternating to layer j (Line 5-6 in Algorithm 1), a single CMA-ES iteration is performed in the same fashion as BBT, i.e., a new z j is generated by M j and is then projected to p j using A j .
During PTM inference, p j = A j z j is first added with an initial prompt embedding p j 0 and then concatenated with the hidden states x j . Thus, according to Eq.(4), the computation of a L-layered PTM can be viewed as where [·; ·] means concatenation. Tunable parameters are highlighted in color. Following Sun et al. (2022b), we set p 1 0 as the word embeddings randomly drawn from the PTM vocabulary. p j 0 (1 < j < L) is the hidden states of the prompt tokens at the j-th layer.

Revisiting Random Projections
In the original BBT, each entry in the random projection A is sampled from a uniform distribution (He et al., 2015). In their experiments, using normal distribution N (0, 1/d) to generate the random projection results in slow convergence and inferior performance. However, we show in pilot experiments that the uniform distribution exhibits poor generalization when using other PTMs than RoBERTa. In this section, we shed some light on the effect of the random projection, and propose to use normal distributions with model-related means and standard deviations to generate random projections. In fact, most prior works in high-dimensional DFO (Wang et al., 2016;Qian et al., 2016;Letham et al., 2020) also adopt normal distributions to generate random projections. However, they usually simply use N (0, 1) or N (0, 1/d).
To take a closer look into the effect of the random projection, we draw distribution of the initial prompts p that are projected from z by the projection matrix A. Here, z is sampled from the normal distribution maintained by the CMA-ES, which is initially set to N (0, 0.5) in BBT. By generating A from different distributions, we obtain the distribution of the projected prompts and compare with the distribution of RoBERTa LARGE word embeddings. 3 As revealed by Figure 5, when A is sampled from the normal distribution used in the original BBT, the projected prompts p cannot cover the range of word embeddings, and therefore suffers from slow convergence. In contrast, using uniform distribution can cover the range of embeddings, which explains why it performs well on RoBERTa LARGE .
Thus, to generalize BBT (and BBTv2) across different language models, we have to take into account the distribution of word embeddings (and hidden states for BBTv2) of the PTM for generating random projections. In particular, we use the normal distribution with mean and standard devia- 3 We hypothesis that high-quality prompt embeddings p should lie within the distribution of word embeddings. Uniform Normal (Ori. BBT) Normal (Ours) Embedding Figure 5: Distributions of the RoBERTa LARGE word embeddings, and initially generated prompts p = Az where A is sampled from different distributions. When using our designed normal distribution to generate the random projection, the distribution of the projected prompts well matches the shape of word embeddings, and therefore leads to faster convergence and stronger generalization. tion as follows, whereμ andσ are observed mean and standard deviation of word embeddings (and hidden states for BBTv2). The main idea behind the above calculations is to match the distribution between projected prompts and word embeddings (and hidden states for BBTv2). Detailed derivation of Eq.(6) and Eq. (7) can be found in Appendix A. As simulated in Figure 5, when using our designed normal distribution to generate the random projection, the distribution of the projected prompts matches the distribution of RoBERTa word embeddings.

Datasets and Tasks
For comparison, we mainly evaluate on the same datasets as BBT, i.e., SST-2 (Socher et al., 2013), Yelp polarity , AG's News , DBPedia ,  ChnSent 4 and LCQMC (Liu et al., 2018), for evaluation on CPM-2 (Zhang et al., 2021b), a Chinese PTM with ∼11B parameters. ChnSent is a sentiment analysis task while LCQMC is a question matching task. We follow the same procedure as Zhang et al. (2021a); Gu et al. (2021); Sun et al. (2022b) to construct the true few-shot learning settings (Perez et al., 2021). In particular, we randomly draw k samples for each class to construct a k-shot training set D train , and construct a development set D dev by randomly selecting another k samples from the original training set such that |D train | = |D dev |. We use the original development sets as the test sets. For datasets without development sets, we use the original test sets. Therefore, in our experiments we have |D test | |D train | = |D dev |.

Baselines
We consider two types of methods as our baselines: gradient-based methods and gradient-free methods.

Implementation Details
Backbones. To compare with BBT, we mainly use RoBERTa LARGE (Liu et al., 2019) as our backbone model. To verify the versatility of BBTv2, we also evaluate on another discriminative PTM, BERT LARGE (Devlin et al., 2019), and a generative PTM, BART LARGE (Lewis et al., 2020). In addition, we also evaluate BBTv2 on a supersized Chinese generative PTM, CPM-2 (Zhang et al., 2021b), which has ∼11B parameters.
Hyperparameters. Most of the hyperparameters remain the same as BBT: we insert 50 continuous prompt tokens at each layer; the subspace dimen-  sionality is set to 500; the CMA-ES with the population size of 20 and the budget of 8,000 API calls is applied to all the tasks; the cross entropy is adopted as the loss function. The only exception is that we generate the random projections from normal distributions with means and standard deviations calculated by Eq.(6) and Eq. (7), respectively, instead of uniform distributions.

Results
Overall Comparison. As shown in Table 1, BBTv2 outperforms BBT and other gradient-free methods on 6/7 tasks. In contrast to BBT, the improvement of BBTv2 mainly comes from DBPedia, which has 14 classes, and hard entailment tasks, namely MRPC, SNLI, and RTE. On simple tasks such as SST-2 and Yelp, BBT can perform on par with BBTv2. When compared with gradient-based methods, BBTv2 still achieves the best results on average across the 7 tasks while maintaining much fewer tunable parameters. It is worth noting that BBTv2, without any gradient-based components (e.g., the pre-trained prompt embedding used in BBT on entailment tasks (Sun et al., 2022b) or the white-box prompt optimization required by Diao et al. (2022)), is the first purely black-box method that matches the performance of gradient-based optimization on various understanding tasks.
Detailed Comparison. In Table 2, we compare BBTv2 with BBT in other dimensions than accuracy. In addition to the improvement in accuracy, BBTv2 also confers faster convergence than BBT in most cases. For fair comparison of training time, we perform early stopping for both BBT and   BBTv2, i.e., we stop optimization if the development accuracy does not increase after 1,000 steps. We report training times under two implementations, PyTorch (Paszke et al., 2019) and ONNX Runtime 7 , on a single NVIDIA GTX 3090 GPU.
In terms of memory footprint and network load, BBTv2 slightly increases the memory on the user side and the amount of data to be uploaded.
BBTv2 Across Models. To verify the universality of BBTv2 across language models, we also evaluate on BERT LARGE and BART LARGE . As shown in Table 3, BBTv2 can achieve considerable performance across different types of PTMs, i.e., discriminative and generative PTMs. In addition, we also verify the effectiveness of BBTv2 on a supersized Chinese PTM, CPM-2, which has ∼11B parameters. As shown in Table 4, when using CPM-2 as the backbone, BBTv2 outperforms model tuning on the two Chinese tasks. The results of Vanilla PT, Hybrid PT, and LM Adaption, which are three variants of prompt tuning, are taken from Gu et al. (2021). We run CPM-2 on 4 NVIDIA A100 GPUs.

Ablations
Effect of Subspace Dimensionality. The ddimensional subspace is the space where the optimization actually performs. We explore the subspace dimensionality from 10 to 1000 using both BBT and BBTv2. The population size is set to λ = 4 + 3 log ( Figure 6: Ablation results on subspace dimensionality and prompt length. We show mean and standard deviation of performance over 5 runs with different random seeds.  Figure 7: Ablation results on the random projection with different distributions. When using our designed normal distribution to generate random projections, both BBT and BBTv2 achieve fast and stable convergence. dimensionality, we perform 5 runs with different random seeds and record the mean and standard deviation. Experimental results on SST-2 and SNLI are demonstrated in Figure 6, from which we find that: (1) Increasing subspace dimensionality d generally confers improved performance for both BBT and BBTv2, but marginal effect is also observed when d > 100; (2) BBTv2 almost always performs better than BBT with the same subspace dimensionality.
Effect of Prompt Length. As reported in prior work (Lester et al., 2021;Sun et al., 2022b), prompt length can be a sensitive hyperparameter to affect the model performance. In our context, prompt length determines the dimensionality of the original prompt parameter space. Hence, we explore the prompt length from 5 to 100 using BBT and BBTv2. Also, we perform 5 runs for each prompt length and report the mean and standard deviation. As shown in Figure 6: (1) The optimal prompt length lies in the range from 5 to 100 and varies across tasks; (2) The effect of prompt length is somehow consistent between BBT and BBTv2.
On Convergence of Normal Distributions. Previously in Figure 4, we show that using our designed normal distribution leads to better generalization from training data to development data. Nevertheless, as reported by Sun et al. (2022b), using normal distributions can suffer from slow convergence. Therefore, we compare the convergence rates using random projections generated from different distributions. As demonstrated in Figure 7: (1) For BBT, the convergence rate of using our designed normal distribution is significantly faster than the normal distribution used in the original BBT, and is comparable to uniform distribution; (2) For BBTv2, using our normal distribution converges more stably on both SST-2 and AG's News. Especially, we observe that using our normal distribution converges faster than uniform distribution on AG's News.

Related Work
Parameter-Efficient Tuning. In order to reduce the computation and storage cost of large PTMs, much effort has been devoted to parameter-efficient tuning (PET), which is to optimize only a small portion of parameters while keeping the main body of the model unchanged. Thanks to the low intrinsic dimensionality of PTMs (Aghajanyan et al., 2021), PET can achieve comparable performance to full model tuning when training data is sufficient (He et al., 2021). Though the number of tunable parameters is reduced, back-propagation through the entire model is still required to calculate the gradients to update the small portion of parameters. Hence, BBT (Sun et al., 2022b) is proposed to optimize the continuous prompt tokens prepended to the input layer with derivative-free optimization (DFO). This work improves BBT with deep prompts that are injected to every layer of the PTM.
Prompt-Based Learning. Another line of work that is related to this work is prompt-based learning, which is to formulate downstream tasks as a (masked) language modeling task, and therefore reduces the gap between PTM pre-training and finetuning (Liu et al., 2021a;Sun et al., 2022a). The prompt can be manually designed (Brown et al., 2020;Schick et al., 2020;Schick and Schütze, 2021), mined from corpora (Jiang et al., 2020), generated by paraphrasing (Jiang et al., 2020) or generative PTMs (Gao et al., 2021), or be constructed using gradient-guided search (Shin et al., 2020). In this work, we also insert manually crafted textual prompts into input samples but only optimize the continuous prompt tokens prepended to the hidden states of each layer.

Conclusion
In this work, we present BBTv2, an improved variant of BBT (Sun et al., 2022b) with deep prompts that are attached to every layer of the PTM. To optimize the high-dimensional prompt parameters, we propose a divide-and-conquer (DC) algorithm combined with random projections to alternately optimize the continuous prompt tokens at each layer. Besides, by simulating the distribution of the generated prompts, we shed some light on the effect of random projections, and propose to use normal distributions with model-related means and standard deviations to generate random projections. Experimental results demonstrate that the proposed BBTv2, without any gradient-based component, can achieve comparable or even better performance than state-of-the-art parameter-efficient tuning methods and full model tuning while maintaining much fewer tunable parameters.