Survival of the Most Influential Prompts: Efficient Black-Box Prompt Search via Clustering and Pruning
Authors: Han Zhou
Xingchen Wan
Ivan Vulić
Anna Korhonen
Venue: EMNLP 2023 Findings (2023)
Keywords: large language models
black-box
discrete prompt learning

Abstract: Prompt-based learning has been an effective paradigm for large pretrained language models (LLM), enabling few-shot or even zero-shot learning. Black-box prompt search has received growing interest recently for its distinctive properties of gradient-free optimization, proven particularly useful and powerful for model-as-a-service usage. However, the discrete nature and the complexity of combinatorial optimization hinder the efficiency of modern black-box approaches. Despite extensive research on search algorithms, the crucial aspect of search space design and optimization has been largely overlooked. In this paper, we first conduct a sensitivity analysis by prompting LLM, revealing that only a small number of tokens exert a disproportionate amount of influence on LLM predictions. Leveraging this insight, we propose the Clustering and Pruning for Efficient Black-box Prompt Search (ClaPS), a simple black-box search method that first clusters and prunes the search space to focus exclusively on influential prompt tokens. By employing even simple search methods within the pruned search space, ClaPS achieves state-of-the-art performance across various tasks and LLMs, surpassing the performance of complex approaches while significantly reducing search costs. Our findings underscore the critical role of search space design and optimization in enhancing both the usefulness and the efficiency of black-box prompt-based learning.

Survival of the Most Influential Prompts:
Efficient Black-Box Prompt Search via Clustering and Pruning
Han Zhou
Xingchen Wan Ivan Vulić" Anna Korhonen'
'Language Technology Lab, University of Cambridge Machine Learning Rescarch Group, University of Oxford {hz416, iv250, alk23)@cam ac. uk xwan@robots ox. ac. uk
Abstract
90
RLPrompt
BDPL
Prompt-based learning has been an effective paradigm for large pretrained language mod- els (LL.M), enabling few-shot or even zero-shot learning. Black-box prompt search has received growing interest recently for its distinctive prop- erties of gradient-free optimization, proven par- ticularly useful and powerful for model-as-a- service usage. However. the discrete nature and the complexity of combinatorial optimization hinder the efficiency of modern black-box -ox ap- proaches. Despite extensive research on search algorithms. the crucial aspect of search space design and optimization has been largely over- looked. In this paper, first conduct sensitiv- ity analysis by prompting LLM, revealing that only a small number of tokens exert dispro- portionate amount of influence on LLM predic- tions. Leveraging this insight, we propose the Clustering and Pruning for Efficient Black-box Prompt Search (CLAPS), simple black-box search method that first clusters and prunes the influen- search space focus exclusively
88
Search
Prune Search
86
ClaPS (ganstics)
Accuracy
ClaPS (greedy)
82
80
10
101
102
10a
Wall-Clock Time (s)
Figure 1: Our proposed method achieves the best any- time performance: Anytime test accuracy against wall- clock time CLAPS (our proposed method) compared to other baselines in a few-shot learning setup on SST-2 with Flan-T5 Lines and shades denote the mean and standard deviation over 5 random seeds, respectively (single seed CLAPS (greedy)).
trained with simple, self-supervised text comple- tion on a large corpus. This is typically followed by fine-tuning and/or, more recently, prompting- based methods on specific tasks (Lyu et al., 2022; Kojima et al., 2022; Chen et al., 2023).
tial prompt tokens. By employing even sim- ple search methods within the pruned search space, CLAPS achieves state-of ofth-ooft perfor- mance across various tasks and LLMs, surpass- ing the performance of complex approaches while significantly reducing search costs. Our findings underscore the critical role of search space design and optimization in enhancing both the usefulness and the efficiency of black- box prompt-base learning.
Prompt-based learning is particularly appealing for modern LLMs due to its sample efficiency and flexibility compared to conventional fine-tuning. This enables few-shot even zero-shot learning (Brown et al., 2020; Liu al., 2023). It can be categorized into two types: soft and hard prompt tuning. Soft prompt tuning directly optimizes the embedding space of the model with other model parameters frozen (Li and Liang, 2021; Lester et al., 2021, inter alia). Although these methods do not require full gradient updates like fine-tuning, they still require parameter access, back-propagatie through massive models, and typically model- and/or task-specific.
1 Introduction
Many of the recent astounding breakthroughs in ar- tificial intelligence have revolved around pretrained large language models (LLMss) Though capabili- ties of L.MMs have advanced at breakneck speed, modern LLMs are remarkably consistent in that they are almost invariably powered by Transformer- based architectures (Vaswani et al., 2017) pre-
Hard prompt tuning (HPT), on the other hand, is an emerging paradigm that directly searches for discrete tokens to be added to text input. Hard prompts are more portable and more amenable
"Fqual contribution, Code is available at https:// gi thub.. htt.c///aaanbnneee//////o.

---

human interpretation, as they are actual tokens rather than abstract arrays the embedding space (Shin et al., 2020). More importantly, unlike soft prompting, which invariably requires parameter access of LLMs due to the need to modify the em- beddings, HPT is feasible even if the task LLM is only available outputs, but not information like parameters and gradients, are available. Indeed, methods leverag- ing reinforcement learning (RL) (Deng et al., 2022; Zhang et al., 2023) and gradient estimation (Diao et al., 2023) have been recently proposed to exploit this powerful property, particularly since many ad- vanced LLMs (e.g.. GPT-4 (OpenAI, 2023) and Bard) are increasingly made available in a model- as-a-service (MaaS) manner, on which parameter gradient access is expensive impossible thus, in this paper, we also focus on this practical but challenging black-box setup.
Inspired by these findings, we then propose Clustering and Pruning for Efficient Black-box Prompt Search (CLAPS), a simple black-box search method that first clusters and prunes the search space to focus on this subset of inftuential tokens, followed by the discrete prompt search on few-shot objective. We find that after pruning. even the simplest search strategy (e.g.. random evolutionary search)
'black box', i.e., only the model
outperform state-of-the- art methods with much more complicated search strategies, often a fraction of the search costs over these competing methods (c.g., CLAPS out- performs RLPrompt with only 2.8% of its cost mea- sured in terms of wall-clock time). In summary, in this paper, we offer the following contributions: 1) We analyze the influence different tokens in the vocabulary exert on LLM predictions, and find that only a small fraction of tokens positively influence LLMs when used as discrete prompts.
2) We propose CLAPS, a black-box discrete prompt search method compatible with a few-shot learning setup, via a cluster-prune-thee seeee-tthen--ecehlee rou- tine that focuses on a small set of influential tokens as discrete prompt candidates.
Despite the promising progress, one challenge plaguing the aforementioned black-box HPT ap- proaches is the difficulty of the discrete and combi- natorial optimization inherent this problem when no gradient guidance is available - common that existing methods require a large number of model queries, frequently in the order of O(10²) or more, before convergence. While previous works have attempted to alleviate this problem by improv- ing the search strategy, search space design has been largely overlooked. For example, previous works take the natural decision of using the entire tokenizer vocabulary as the search space (Deng et al., 2022), by convenient extension from the soft prompt tuning. However, as we will show with an analysis of the search spaces of discrete prompts, such a practice is actually suboptimal and has made the optimization unnecessarily difficult. Similar to the phenomenon observed in related dis- crete optimization problems such as neural archi- tecture search (Wan al., 2022; Ru al., 2020; Zhou et al., 2023b), we find the influence exerted by different tokens on the LLM when prepended to the text queries as discrete prompts to be highly non-uniform, with a small number of tokens (e.g., - 1% of all tokens) exerting a disproportionate amount of influence. Meanwhile, the models are insensitive or even harmed by the vast majority of the other, 'non-influential" tokens, which never- theless act as nuisance variables during the search to substantially increase the optimization difficulty and resources required.
3) We then show that while conceptually simple. CLAPS attains state-of-the-arr performance, of- achieved at very small fraction of the cost of competing methods in more than 8 tasks with enstruction-finttung Flan-T5 models.
Preliminaries
Hard prompt tuning (HPT). As mentioned in 11, HPT aims to find discrete tokens to be concate- nated directly to the test queries with the goal of maximizing task performance. Formally, HPT may be represented as an optimization problem:
pd = arg max E DEP
(p)(C((p.))) (1)
where {2,,y1 denotes a query-target pair, p [P1,.., are the additional tokens to be con- catenated with the text query x this is often re- ferred to as the discrete prompts, whose optimiza- tion is the focus of HPT and use P to denote the prompt search space, the set of all possible discrete prompts. C(,, 2;) refers to the concatenation of p and a formatted query zy:
C(p, xx) Concat(p, template(z:)), (2)
where template(-) denotes any human-designed pre-processing procedure that formats 2;;

---

((C(p, 2:)) E RR the output probability distribution of the model given iy over all possible classes y (defined by the verbalizers) with E z4) - 1; it is worth stressing again that under a black-box setup considered in this paper, the output probabilities are the only observation available to us and we assume no access to other information, including but not limited to the model architectures, parameters gradients. Finally, I((,.) refers to a reward function given the model predictions and the ground-truth labels (an example is the negative cross-entropy loss). The goal of HPT is thus to find the optimal p that maximizes this reward on expectation over some data generraing distribution D. Since the true data-generating distribution is always assumed to be latent, in practice we solve Eq. (1) via empirical risk minimization with standard train-validation-tess split.
1200-
Bottom 90%
1000
Top 10%
800
Top 5%
Count
Top 1%
600
400
200
Bottom 90%
5.%
1.96
-0.06
-0.04
-0.02
0.00
0.02
0.04
Reward
Figure 2: Only a small fraction of tokens improve perfor- mance. Distribution of the incremental reward A A(v)) (Eq. 3) evaluated on 16-shot RTE samples with Flan- These- The top- (op-(1,5,10) % tokens in terms their in- cremental reward are highlighted in colors.
study of the search space design is crucial. As dis- cussed, existing search spaces are often expensive and heuristically designed. However, a large search space is not necessarily well well-designed: crucially, it is unknown whether all parts of P positively con- tribute to downstream task performance, or it could simply be highly redundant, i.e., a large fraction of P might in fact be unimportant or even harmful, which simply increase complexity but nevertheless act as confounding factors that make the optimiza- tion in Eq. (1) unnecessarily hard.
Search strategy and search space. Solving Eq. (1) is, in general, challenging, as it involves difficult combinatorial discrete optimization, and the gradi- ents essential for standard first-order optimization are not available. A natural recourse, that most previous works have focused on, is developing bet- ter zeroth order search strategies, via, for example, reinforcement learning and Monte Carlo gradient estimation. Search space (i.c., P), on the other hand, is much less well-studied despite the fact that its design has been previously shown to be one of the most important influencing factors in related discrete optimization problems. In HPT, the overall search space P can be decomposed as a Cartesian product over the search space individ- ual tokens: P = I Pk. which in turn often designed heuristically, and popular choices include the entire tokenizer vocabulary Pa= = = (and thus [P] = [ for a K-token discrete prompt) (Deng et al., 2022) (Diao et al., 2023) given the exponential scaling w.r.t. the value of K, [P] is typically huge even for modest [P&| and/or K.
To answer this question, we analyze the building blocks of the most general search space where the individual tokens of the discrete prompts may be any token in the vocabulary V. To quantify the incremental influence for a token v E V, we define: AR(V) EN R(f(C(v, m.)) m.) R(f(C(x.))..) N
(3)
where treat token v as a single-token discrete prompt to be concatenated to text queries x; and its influence AR(v) is the change in reward compared to the case where a formatted input without any prompt token C(z;;;; N denotes the number of la- beled samples randomly sampled from the training set of the target task - we use N = 16 throughout this paper, and we define R(,,-) as the negative cross-entropy:
subset of frequent n-grams from it
DI R))( () log اام (C(p. o.)). (4)
3 Analyzing Prompt Search Spaces
General search spaces are highly redundant. We argue that, like any other optimization problem, the search space, in our case, may also have pro- found effect on both the search strategy and the downstream performance. As the research com- munity of HPT grows, we argue that a systematic
We visualize the results of the above analysis on representative task in Fig. 2 where we compute A AR(e) for all tokens in the vocabulary and we
'Noee that the enumeration here is over Pt, which is typ- ically tractable, as opposed to P. The computation may he further accelerated via clustering - see $4.

---

Algorithm 1 CLAPS.
80
RLPrompt
I: Input: Original token search space Ps (typically the en- tire vocabulary V); search space size to retain after clus- tering [V.] (can be set to V if no clustering is required); search space fraction to retain after pruming a; discrete prompt length (in terms of tokens) K.
75
Accuracy (%)
70
65
60
2: Output: Optimized discrete prompts p
3: if [Vyl < [V] then
55
4: [Clustering]: Obtain a reduced set of representative tokens V. with clustering (84) as the new token search space Pk +- V.
50
Vocab
Random Search Space
BDPL Pruning (ours)
5: end if
6: for E PE do
Figure 3: Praning improves prompt search. Distribu- tion of accuracy on RTE with Flan-T5hase by random sampling 100 5-token prompts from different vocabu- lary spaces. Random refers to random vocabulary set, and BDPL prunes a context-relevant vocabulary set based on task-dependent 7-gram scores. Pruning indicates our reward pruning on the vocabulary space. RLPrompt denotes the final test accuracy achieved by RLPrompt (Deng al., 2022) on this task.
7: Compute the incremental influence AR(e) of each token v according to Eq. 3.
8: end for
9: [Pruning]: Rank and prune the tokens in Ps and only retain the top-a fraction of tokens in terms of AR())) as the new token search space.
10: [Search]: Run black-box prompt search in the prompt search space P = II Pa to solve Eq. 1 to obtain an optimized discrete prompt p"
randomly selected (Random), and 3) a Ps consists of frequent n-grams selected via pointwise mutual information as in Diao et al. (2023) (BDPL). We visualize the test accuracy distribution in the RTE task in Fig. 3, and we find pruning to massively improve search space quality and reduce search difficulty compared to both random pruning and the pruning strategy proposed in BDPL., the latter of which does outperform Random and Vocab but is nevertheless outperformed by our pruning strat- egy. Crucially, the fact that the median of the 100 randomly sampled discrete prompts already per- forms similarly to RLPrompi (Deng et al., 2022), a state-of-the-art method that features much more complicated and expensive RL search strategy and tailored reward function, highlights the extreme importance of search space design.
find the distribution of influence over the vocabu- lary of tokens is, in fact, heavily non-uniform, with a small fraction (roughly 1,, marked in green) of all tokens exerting a disproportionate amount of influence on the prediction of LLMs whereas the vast majority of tokens either actively harm LLM predictions or exert negligible influence.
Search space pruning. The finding above means that it would be highly challenging for any search method to navigate in the original search space, especially in a black-box setup: the method has to learn to both identify the small fraction of func- tioning tokens and to avoid the vast majority of unimportant or harmful ones. Instead of doing so, we propose to prune Px by focusing on the small fraction of the most influential tokens identified above only given the Cartesian structure of this results in an exponential reduction of the overall search space P: with a representative K- = 5 and if we retain the top-1% 1% tokens in terms of AR(v) given by Eq. 3, there is (1010)) reduction in [P]. To validate the effectiveness of the pruning pro- cedure and that the search space reduction does not lead to sacrifices in performance, we randomly sample 100 5-token discrete prompts from the re- duced search space after the aforementioned prun- ing procedure and use their performances an approximation of the overall search space qual- ity, and we compare the results against the sam- ples drawn from 1) the original, unmodified search space (Vocab), 2) a reduced search space with Pk reduced to 10% of the original, but the tokens are
Efficient Black-Box Prompt Search via Clustering and Pruning
Inspired by the analyses presented in $3, we now present Efficient Black-Box Prompt Search via Clustering and Pruning, or CLAPS in short, with the overall procedure illustrated in Fig. 4 and Al- gorithm 1. At a high level, CLAPS utilizes a multi- step approach, combining the search space pruning proposed in $3 with an optional clustering step to reduce further the computational cost and a simple black-box prompt search routine. We describe the procedure in detail below.
Clustering. By default, CLAPS enumerates the tokens in V and obtains the influence score (Eq. 3)

---

(a) Original search space
(b) K-Means clustering
(c) Rank prume
(d) Black-box hard prompt search
Hilesann mind
thinc
pescnpttio
Figure 4: Illustration of the CLAPS pipeline. Starting from (a) the original search space (in this case, the entire vocabulary V with [V| O11*)). visualized via t-SNE plots of vector embeddings for illustration only). (b) we first perform the optional, unsupervised step of K-Means clustering to retain a fraction of representative tokens V. with V4.1 ~ O(10)). We then (c) prune the tokens using the procedure described in $3 to retain small fraction of inffuential (~~ (11))) tokens the search space. We finally perform (d) Mack-box prompt search over the reduced search space to identify the final K-token discrete prompts.
of each token by evaluating on 16-shot training set. While this procedure, which requires O11*)) model evaluations can be already tractable, here we propose an additional optional step to acceler- ate further our method: instead of enumerating all tokens, we may use an unsupervised algorithm on the token embedding space to obtain a subset of di- verse tokens V. that well-represent V (illustrated in Fig. 4(b)) while alternative methods that explic- itly optimize for diversity set selection exist, we opt for the simple greedy K-means++ (Arthur and Vas- silvitskii, 2007) to generate Ve (we set Vall= = 2000 unless otherwise stated). Formally, for each cen- troid ee identified by K-means++,, we collect the closest token in terms of its embedding & distance:
Ranking and pruning. As illustrated in Fig. 4(c), we prune V. (with clustering) or V (without cluster- ing) using the procedure described in $3 obtain the set of influential tokens for prompt search Vi-- The size of 1/s is another hyperparameter, which in this case encodes the greediness with a small Vill suggesting a more greedy algorithm that only considers tokens that minimize the validation loss. However, as we empirically show in $6, combining the most influential tokens does not necessarily lead to the optimal prompt, and balancing greediness with prompt search in the next stage leads to the optimal outcome - in this paper, we set |iil = 200 for all experiments without further model- or task- specific hyperparameter tuning.
V. = (id D'd where tee = arg min| e, eell2-
Black-box prompt search. The final step of CLAPS, as illustrated in Fig. 4(d), is search. To demonstrate that CLAPS is search method- agnostic, we consider three different search strate- gies in our experiments. To differentiate from pre- vious work focusing on search strategies, we first consider lightweight search strategy with basic evolutionary search algorithm with the following ingredients:
vEV
(5) The size of the retained vocabulary [Val is a hyper- parameter of the search algorithm (to be discussed in detail at the end of this section) and determines the number of model queries in the next stage, with smaller [vrl leading more aggressive reduc- tion and improved query efficiency but may lead to some performance loss as some influential tokens may be removed from the search space at this stage. In our experiments, we set [Vll = 2000 for all model and task combinations without further hy- perparameter tuming, and after the above procedure, the number of LLM queries at the pruning stage reduces from (114)) to (103). Empirically, as shown in $6, we find this additional procedure to reduce the cost by roughly 3/4 relative enumera- tion (i.e., no pruning) in terms of wall-clock time at only a small performance impact. A sensitivity study of hyperparameters is also performed in $6.
Initialization: we initialize with population of M uniformly sampled K-token discrete prompts from the pruned search space, and we evaluate the accuracy of each discrete prompt on a held- out, 16-shot validation set.
Evolution: after evaluating all prompts in the population, at each search epoch, we retain the top 10% of the population in terms of the vali- dation loss as seed prompts. We then generate M
the next population of 2 prompts via crossover, where two randomly selected seed prompts ex-

---

change tokens to create new offispiing, and M new prompts via mutation, where we swap a to- ken in a seed prompt with another token in the (pruned) vocabulary with a fixed probability. Termination: at the end of the final search epoch, we simply return the prompt that leads to the best validation loss seen as the final p".
Other methods, such as the parameter-effcient fine- tuning (PEFT) techniques (He al., 2022), which only tune small fraction of the model parameters (Houlsby et al., 2019; Hu et al., 2022), may also be regarded as soft prompt learning. While promising, drawback of the soft prompting methods is that since the model-specific input embedding layers often need to be modified, these methods inevitably require internal model access. Furthermore, with few exceptions like BBT (discussed in the next paragraph), many soft prompting methods still re- quire prop-propng of gradients through mas- sive models, which can still be computationally ex- pensive. In contrast to soft prompting, hard prompt learning learns discrete tokens: AutoPrompt (Shin et al., 2020) uses model gradients to select appro- priate tokens automatically, but is nevertheless stricted 'white-box' setup.
To demonstrate the versatility of CLAPS, also consider two additional search strategies, namely greedy search and particle swarm optimiza- tion (Kennedy and Eberhart, 1995; Bonyadi and Michalewicz, 2017). The greedy algorithm is a commonly used baseline in combinatorial optimiza- tion: Starting with an empty string P == 0, at the k + 1-th iteration, space Vit (with [i+l 200 following the previous paragraph) and simply select the token that leads to the highest reward, conditioned on partial prompt p with & tokens already selected so far. More formally, the (I: + 1)-th token of p" is recursively selected by:
iterate through the search
Black-box box prompt optimization. In contrast to the white-box methods discussed above, several methods are proposed to tune discrete prompts in black-box manner (i.e., not using internal knowl- edge about the pretrained LLM). Black-box tun- ing (BBT) and BBTv2 (Sun et al., 2022b,a) use gradient-free optimization to learn soft prompts that are projected back to the embeddiin/weeight space and concatenated to the query embedding and/or weights. While not using model gradi- ents, these methods nevertheless require access to input embedding of the task model itself, and hence not black-box in the strictest sense. In the strictly black-box setup, methods using rein- forcement learning (Deng et al., 2022; Zhang et al., 2023), discrete optimization (Prasad al., 2023), and gradient estimation (Diao et al., 2023) have been proposed; we empirically compare against them in $6. Furthermore, as discussed in $4, CLAPS is fully orthogonal to the previous work since these techniques focus improving search strategy. Several other works have focused on opti- mizing specific components of the prompt design, e.g., Rubin et al. (2022); Liu et al. (2022a); Wan et al. (2023a,b) focus on selecting in-context exam- ples and Zhou et al. (2023a) mitigate the in-context bias by calibration. We argue that these methods are again orthogonal to our contributions and thus may offer combining benefits.
N MCE(C(Concat(pgge..). ax)), vt),
pi+1
arg max VE
(6) and the algorithm terminates when all K tokens are selected. For the particle swarm optimizer, we use an adapted version of the algorithm described by Zang et al. (2020) work in the discrete search space, and we refer the reader to Appendix A for further implementation details.
is worth noting that we only consider a small representative. and definitely non-exhaustive set of search algorithms. CLAPS, which focuses on search space design, can be deemed as a meta- method that is compatible with any search strategy, including but not limited to the ones proposed in previous work, in plug-and-play manner. It is therefore possible that combining CLAPS with more advanced search method would lead to even stronger performance - we defer a thorough inves- tigation to future work.
5 Related Work
Prompt learning. Prompt learning is a class of powerful methods for LLM adaptation and has be- come efficient alternative to full model finetun- ing (Liu et al., 2023). Earlier methods (Li and Liang, 2021: Lester al., 2021; Liu al., 2022b) typically feature soft prompt tuning, where con- tinuous prompts which modify the input embed- ding of an otherwise frozen LLM are optimized.
Experiments and Results
Evaluation data. We include various tasks from single-sentence to multi-sentence classification

---

Model
Flan-T5uur
Flan-T Flan-T5upg
CLAPS
CLAPS
Method
FT
Manual
BDPL
RLP.
Search
FT
Manual
BDPL.
RLP.
Search
Genetics
Greedy
Genetics
Greedy
SST-2
76.19
85.32
84.89
86.01
85.85
87.78
90.37
83,72
92.32
92.43
92.35
92.73
93.03
94.27
RTE
51.55
73.65
72.27
78.52
77.47
81.23
79.42
49.10
84.12
84.12
84.55
85.05
86.12
86.28
SNLI
60.98
48.97
51.65
63.06
59.30
65.92
63.47
74.62
76.50
78.05
85,57
84.27
84.08
84.75
QNLI
67.94
62.40
61.53
74.85
65.83
70.52
80.07
77.32
82.67
80.45
83,80
82.78
85,81
86.47
45.99
43.15
42.52
57.60
47.30
50.45
57.02
51.91
70.68
75.32
79.26
81.81
77.82
MRPC
68.73
69.12
71.49
58.82
72.74
68.43
65.93
70.83
76.72
83.96
80.15
74.85
77.11
75.49
QQP
66,31
79.07
68.44
80.09
80.57
80.87
81,40
77.23
81.29
77.25
72.23
82.01
81.31
78, 10
News
83.62
71.15
70.71
76.91
77.20
76.06
77.13
83.72
81.22
80.77
82,62
82.96
84,24
83.08
Average
65.16
66.60
65,44
71,98
70.78
72.66
74.35
71.06
80.69
81.54
82.39
82.99
84.19
83,28
Table I: Accuracy on Flan-T5 buse (Left) and Flane (Right). We reproduce all baselines and report the mean for random seeds for mhase- For cemputationexpenssie experiments, we report single-seed results for Flan Flan-T5 The best and second-best results are marked in bold fonts and ranked by color.
Model
Flan Trese
Flan- Plan-TSupe TSurge
CLAPS
CLAPS
Method
FT
Manual
BDPL
RLP.
Search
FT
Manual
BDPL
RL..
Search
Genetics
Greedy
Geneties
Greedy
BG
34.85
33.97
33.36
37.16
35.67
36.16
34.57
33,95
43.87
44,91
44.61
44.78
45.13
44.63
DE
37.35
35.47
35.07
38.16
36.91
39.56
41.64
40.56
55.17
55.63
62.67
60.80
62.29
57.74
EN
47.69
41.20
40.08
54.23
46.17
54.14
54.77
69.04
69.84
76.77
81.18
79.04
81.15
77.11
ES
35.51
34.53
33.82
34.27
36.62
38,00
40,50
52.40
53.03
51.92
58.58
58.55
60.52
55.59
FR
40,23
35.15
33.92
37.27
35.67
38.16
41.98
48,30
54.69
55.07
63.81
60.35
63.76
57.62
HI 33.50
33.33
33.33
33.13
33.51
33,99
34.61
32,95
33.81
34.41
35.45
34.97
35,03
34.61
RU
34.99
33.85
33.42
33.51
36.91
37.46
37.01
37.13
48.96
49.34
49.74
49.68
50.62
47.84
SW
34.01
33.37
33.33
34.19
33.72
33.71
35.95
36.33
36.87
37.29
38.94
36.67
37.56
36.81
TR 34.14
33.81
33.5 33.54
36.53
33.8 86
36.
36.67
35,35
43.91
44.57
45.69
45.85
45.31
42.91
Avg.
36.92
34.96
34.43
37.61
36.56
38,59
39.74
42.89
48.91
50.00
53,41
52.30
53,49
50.54
Table 2: Accuracy in 9 languages on XNLI with Shase (Left) and Flane (Right). Methods other languages show similar performance to Hindi and Swahili with marginal improvements over random prediction and are omitted from the table. We report single-seed RLPrompt results due to its computation costs for XNLI tasks, Refer to Table for additional explanations.
tasks, from mono-lingual to multi multi-lingual NLI datasets for widely validating the performance of CLAPS at different levels of task difficulty. We conduct experiments
in comparison are included in Appendix A.
Finetuning: we finetune the seq2seq language model following the standard setup (Karimi Ma- habadi et al., 2021; Zeng et al., 2023).
the standard GLUE dataset (Wang et al., 2018) including: SST-2, RTE,
BDPL (Diao et al., 2023): BDPL first mod- els the prompt generation as samples drawn from multi-dimensional categorical distribution, and uses Monte Carlo-estimated gradients to optimize the distribution parameters. The search space is over a subset of V that appear as frequent n-grams in the task training corpus.
QNLI, MNLI, MRPC, QQP. Furthermore, we in- clude AG's News (Zhang et al., 2015) and SNLI (Bowman et al., 2015) following the previous hard prompt tuning papers (Deng et al., 2022: Zhang et al., 2023). In addition, we include XNLI (Con- neau et al., 2018). a multilingual NLI task, as the most challenging unseen dataset for revealing the potential of our method in different languages. For all tasks, we follow the standard shw- setting (Perez et al., 2021), where 16 shots represent 16 examples per class for both training and valida- tion sets. Since the test labels for GLUE tasks are unavailable, following standard practice we take validation shots from the training sets and treat the validation set as the test set.
RLPrompt (Deng et al., 2022): trains a pol- icy network that generates discrete prompts (an MLP layer on top of a frozen, pretrained GPT-2 model) with bespoke piece-wise reward. The search space is over the whole vocabulary.
Search and Prune & Search: we include these baselines both as ablation experiments and di- rectly gauge the impact of search space design on the downstream task performance. Search baseline utilizes the genetics search algorithm described in $4 directly in the full, non non-prdmed vocabulary
Baselines. In the few-shot learning setup, we mainly compare CLAPS with gradicnt- free black- box baselines. Training details of all the methods

---

search space without clustering and pruning. Prune & Search refers CLAPS without the clustering step where we prune on the whole vocabulary fol- lowed by the genetics search.
Methods
# Param.
VRAM
Time
Querry
SST-2 (%)
FT
250M
6.53BB
0.42 min
76.15
R.Prompe BDPL.
3M
3,60BB
65.1 min
12000
86.01
2.54GB
0:20 min
Search
0
2,54GB
1.26 min
4000
85.82
Prune Search
2,54GB
7.65 min
24000
87.84
CLAPS (Genetios)
2,54GD
1.30 min
6000
87.78
Models. We explore the potential of CLAPS with instruction-finetuned models, and we test wide range of challenging tasks with hhase and Flane models, one of the most powerful open- sourced models of their size (Chung et al., 2022). We refer readers for detailed hyperparameters and training setups to Appendix A.
CLAPS (Greedyy
2,54GD
0.86 min
3000
90.37
Table 3: Comparing the efficiency of CLAPS with base- lines in the few-shot learning setup with Flan-T5 report the number of trainable parameters, the peak VRAM load, and the wall-clock time for the training phase of all methods. The pruming- -paase time span is included in CLAPS, Note that RL RtProppt and BDPL are under their default settings, respectively.
Discussion of main results. We present the re- sults all tasks except XNLI Table 1, whereas the XNLI results are provided in Table 2. For CLAPS results, we present CLAPS with genetics and greedy search algorithms in the main text and show the results with particle swarm optimization in Appendix B. Across both sets of tasks, we find CLAPS (i) to consistently improve on standard, no-prompt Manual bascline and (ii) to outperform the other prompting baselines across the models and tasks. More specifically, CLAPS (genetics) outperforms RI.rommt 0.6% and 1.8% on average for Flan-T3pase and Flan-TSjaree- respectively. In addition, we find that when used with CLAPS, the greedy search algorithm, although straightforward, can be surprisingly strong across many experiments except for XNLI with FlaneT this concretely shows that CLAPS may orthogonally benefit dif- ferent suitable search algorithms. Furthermore, in contrast to other prompting baselines like BDPL and RLPrompt, which occasionally lead to perfor- mance detcrioration from Manual, CLAPS consis- tently improves over the latter. We hypothesize that it is exactly due to the stability of our approach enabled by searching only on pruned search space fcaturing positively influential tokens, whereas the competing methods may suffer from unstable and noisy gradient estimations and/or RL policies over a search space with more harmful sub-components.
Dataset
RLPrompttfound Prompt
SST-2 RTE
Revi BeCCuusttomeBBBnBannkk....
Databaseanswer aeapeeeeeseeernnseeeeeeeeeeeee
QQP
XNLJEN
NodeAr MaleArgsArgsArgaeee Sassrrgraaaeettngggggggoo
Dataset
CLAPS-found Prompt
SST-2 RTE
cruise perfect properly review cruise answer respectively minimum tell answer suggest outside cause exists statement think ask relevant description mind
QQP XNLIEN
Table 4: Examples of CLAPS-discoven prompts com-
pared to RLPrompt for collection of tasks using Flan- T5pae- The CLAPS prompts are prepended to the for- matted text queries, whose templates are listed Ap- pendix A.
tative task in Table 3, which highlights the much- enhanced practicality of CLAPS compared to the baselines: CLAPS is extremely storage-efficient it requires no additional parameters to be stored in the GPU, and the only memory requirement is to maintain the task model under an inference- only (i.e., no gradient storage) mode. CLAPS also achieves the best trade-off' between time efficiency and performance as faster methods (FT and BDPL. perform much worse, whereas methods like RL- Prompt perform better, but are orders-of-mageee -aaggniude slower. It is worth noting for fairness of compar- ison, we also perform additional experiments by running BDPL longer than the default, but we find that doing so only brings marginal improvement over the Manual baseline, as illustrated in Fig.
Finally, we emphasize that CLAPS achieves state-of-the-art performance with rather naïve search strategies, which stands in stark contrast to the competing methods that are both much more complicated methodologically and often orders-of- magnitude more expensive we argue that this highlights that methods focusing on search space design warrant further investigation in future work.
Examples of discovered discrete prompts. Ta- ble 4 presents examples of CLAPS-discoverre prompts, and interestingly, we often observe some interpretability even though CLAPS has not been explicitly tuned towards fluency. For example, in SST-2, a movie review sentiment-classffcatinn task, CLAPS picks 'review' as a part of the best
Efficiency analysis. We analyze the performance- cost trade-off of various methods on represen-

---

SST-2
RTE
additional ablation experiments test the robust- ness of CLAPS w.r.t. other hyperparamelers, such as the number of clusters during clustering and the prompt length; the readers are referred to Ap- pendix for details.
100
Accuracy (%)
90
80
70
7 Conclusion
ClaPS Prune&Search
ClaPS SSarc&
100
We first analyzed the search spaces in the gen- eral paradigm of hard prompt search. Inspired by the findings that only small fraction of to- kens exert positive influence prediction, we proposed CLAPS, an efficient black-box prompt search method via clustering and pruning. The CLAPS method is methodologically simple, easy to implement, and cost-effcotive, and we showed that it achieves state-of-the-art performance in both monno-lnngual and multi--ingual tasks with Flan-T5 models. CLAPP is a meta-method orthogonal to the search strategy, and expect more efficient and effective prompt search algorithms can be cre- ated on top of it. We hope that future work will invest more time into the important problem of search space design.
Accuracy (%)
0.0
90.0
95.0
99.
99.5
5
99. 9
0.0
90
0
95.0 0
99
99.5
99.9
pruned
pruned
Figure 5: Ablation studies. Top row: Flan-T3rase accu- racy SST-2/RTE with (ClaPS-genetics) and with- out (Prune&Search) clustering. Bottom row: perfor- mance sensitivity to pruning strength from 0% (no prun- ing, i... the Search baseline in Tables 1 & to 99.9%. Mean + standard deviation (error bar or shade) shown.
prompt. On the other hand, RTE and XNLIEN are both textual entailment tasks and CLAPS again spontameously discovers prompts provide instruction-like signal to 'ask' the model to "answer' the question. While the other prompts are less immediately interpretable, we hypothesize that they nevertheless act to tune the model embed- ding towards the optimal direction for the target task for performance improvement. CLAPS does share some words with the competitive baseline, RLPrompt, and these words (c.g.. 'review' and "answer") are usually 'influential prompts' identi- fied by our pruning strategy and have significant impacts on the model's prediction. With similar or even better quality of prompts, CLAPS stands out by first establishing an efficient search space while saving substantial computation costs.
Limitations
We argue that CLAPS only serves as a first step towards the promising direction of better search space design and automation, and thus, the room for improvement is ample. First, we have only con- sidered a suite of natural language understanding (NLU) tasks that may be cast as classification in the present study, whereas prompting techniques for generative tasks are, in general, less developed.
Second, we have only explored a token-based search space for hard prompts as it is the most general, but alternative search spaces built on the overall instruction templates and exemplifiers exist (such as the ones used in Zhang et al. (2023) and Prasad et al. (2023). We hypothesize that since these search spaces are also often heuristically de- signed, the search space issues and the pruning procedure may also apply to these scarch spaces, which are often claimed to be more interpretable, and thus, it would be interesting to extend our anal- ysis, and methodology to these alternative spaces. Third, discussed in $4, while the present paper primarily focuses on search space, it is possi- ble combine CLAPS with more advanced search methods for further potential gains: some promis- ing strategics include reinforcement learning, as used in Deng et al. (2022) and Zhang et al. (2023),
Ablation and sensitivity studies. In Fig. 5, we first study the performance impact the use of cluster- ing by comparing CLAPS against Trane&Search we find that in the tasks considered, clustering mini- mally affects the performance, but leads to a 75% speed-up in terms of wall-clock time. We also in- vestigate the effect of different pruning strengths, and find that 1) pruning generally improves per- formance, 2) performance is rather insensitive to (reasonable) pruning strength, and 3) the threshold 1% (corresponding to 99% in Fig. 5) is a gener- alizable choice across tasks. Finally, we conduct

---

and sample-efficient zeroth-order algorithms that may operate directly over the token search spaces, such as the recent advancements Bayesian opti- mization over discrete and/or combinatorial vari- ables (Baptista and Poloczek, 2018; Wan et al., 2021: Daulton et al., 2022). We defer thorough investigations to future work.
Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay. William Fedus, Eric Li, Xuezhi Wang. Mostafa Dehghani, Siddhartha Brahma, Albert Web- son, Shixiang Shane Gu, Zhuyun Dai, Mirac Suz- gun, Xinyun Chen, Aakanksha Chowdhery: Sharan Narang, Gaurav Mishra, Adams Yu, Vincent Y. Zhao, Yanping Huang, Andrew M. Dai, Hongkun Yu, Slav Petrov, Ed H. Chi, Jeff Dean, Jacob Devlin, Adam Roberts, Denny Zhou, Quoe V. Le, and Jason Wei. 2022. Scaling instruction finctumed language models, CoRR, abs/2210. 10210.11441 11416.
iestruction-finetunedd
Acknowledgements
Han Zhou is supported by the UK Research and Innovation (UKRI) Frontier Research Grant EP/Y031350/1 (the UK government's funding guarantee for ERC Advanced Grants) awarded to Anna Korhonen at the University of Cambridge. Xingehen Wan is supported by the Clarendon Scholarship University of Oxford. The work has been supported in part by a Royal Society Uni- versity Research Fellowship (no 221137: 137; 2022-) awarded to Ivan Vulić, and by the UK EPSRC grant FP/TO2250X/1.
Alexis Conneau, Ruty Rinott, Guillaume Lample, Adina Williams, Samuel Bowman, Holger Schwenk, and Veselin Stoyanov. 2018. XNLI: Evaluating cross- lingual sentence representations. the 2018 Conference on Empirical Methods in Nat- ural Language Processing, pages 2475-2485, Brus- sels, Belgium. Association for Computational Lin- guistics.
Proceedings of
Sam Daulton, Xingchen Wan, David Eriksson, Maximil- ian Balandat, Michael A Oshome, and Eytan Bakshy, 2022. Bayesian optimization over discrete and mixed spaces via probabilistic reparameterization. In Ad- vances in Neural Information Processing Systems.
Mingkai Deng, Jianyu Wang, Cheng-Ping Hsieh, Yi- han Wang, Han Guo, Tianmin Shu, Meng Song, Eric Xing, and Zhiting Hu. 2022. RLPrompt: Optimizing discrete text prompts with reinforcement learning. In Proceedings of the 2022 Conference on Empiri- cal Methods in Natural Language Processing, pages 3369-3391, Abu Dhabi, United Arab Emirates. As- sociation for Computational Linguistics.
References
David Arthur and Sergei Vassilvitskii. 2007. k-
means++; the advantages of careful sceding. In Pro- ceedings of the Eighteenth Annual ACM-SIAM Sym- posium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, pages 1027-1035. SIAM.
Shizhe Diao, Zhichao Huang, Ruijia Xu, Xuechun Li, LIN Yong, Xiao Zhou, and Tong Zhang. 2023. Black- box prompt learning for pre-trained language models. Trunsactions on Machine Learning Research.
Ricardo Baptista and Matthias Poloczek. 2018. Bayesian optimization of combinatorial structures. In International Conference on Machine Learning, pages 462-471. PMLR.
Junxian He, Chunting Zhou, Xuezhe Ma, Taylor Berg- Kirkpatrick, and Graham Neubig. 2022. Towards a unified view of parameter-efficieet transfer learning. In The Tenth International Conference on Learning Reprexentations, ICLR 2022, Virtual Event, April 25- 29, 2022. OpenReview.net.
Mohammad Reza Bonyadi and Zhigniew Michalewiez. 2017. Particle swarm optimization for single objec- tive continuous space problems: a review. Evolaton- ary computation, 2-(1):
Samuel R. Bowman, Gabor Angeli, Christopher Potts, and Christopher D. Manning. 2015, A large anno- tated corpus for learning natural language inference. In Proceedings of the 2015 Conference on Empiri- cal Methods in Natural Language Processing, pages 632-642, Lisbon, Portugal. Association for Compu- tational Linguistics.
Neil Houlsby, Andrei Giurgiu, Stanislaw Jastrzebski. Bruna Morrone, Quentin de Laroussilhe, Andrea Ges- mundo, Mona Attariyan, and Sylvain Gelly. 2019. crrameter-efficienn transfer learning for NLP. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pages 2790-2799.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020. Language models are few-shot learners. Advances in neural information processing systems, 13:7777-1
Edward J. Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang. Lu Wang, and Weizhu Chen. 2022. Lora: Low-rank adaptation of large language models. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net.
Wei-Linn Chen, Cheng-Kuang Wu, and Hsin-Hsi Chen. 2023. Self-iel: Zero-shot in-context learning with self-generated demonstrations, arXiv preprint urXiv:2305.15033.
Rabech Karimi Mahabadi, Sebastian Ruder, Mostafa Dehghani, and James Henderson. 2021. Parameter- efficient multi-task fine-tuning for transformers via

---

shared hypernetworks. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 1 1tth International Joint Confer- ence on Natural Language Processing (Volume I: Long Pupers), pages 565-576, Online. Association for Computational Linguistics.
Ethan Perez, Douwe Kiela, and Kyunghyun Cho. 2021. True sho-shot learning with language models. In Ad- vances in Neural Information Processing Systems 34: Anmual Conference on Neural Information Process- ing Systems 2021, NeurlPS 2021, December 6-14, 2021, viriual, pages 11054-11070.
James Kennedy and Russell Eberhart. 1995. Particle swarm optimization. In Proceedings of ICNN'95- international conference on neural networks, vol- ume 4, pages 1942-1948, IEEE.
Archiki Prasad, Peter Hase, Xiang Zhou, and Mohit Bansal. 2023. GrIPS: Gradient-free edit-based in- struction search for prompting large language models. In Proceedings of the 17th Conference of the Euro- pean Chapter of the Association for Computational Linguistics, pages 3827-3846, Dubrovnik, Croatia. Association for Computational Linguisties.
Takeshi Kojima, Shixiang Shane Gu. Machel Reid, Yu- taka Matsuo, and Yusuke Iwasawa. 2022. Large lan- guage models are zero-shot reasoners. In NeurlPS.
Robin Ru, Pedro Esperanca, and Fabio Maria Carlucci. 2020. Neural architecture generator optimization. Advances in Neural Information Processing Systems, 33:12057-12069.
Brian Lester, Rami AI-Rfou, and Noah Constant. 2021. prompt
The power of scale for parameter-efficte tuning. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 3045-3059, Online and Punta Cana, Domini- can Republic. Association for Computational Lin- guistics.
Ohad Rubin, Jonathan Herzig, and Jonathan Berant. 2022. Learning to retrieve prompts for in-context learning. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Numan Language Tech- nologies, pages (671-2677,, Seattle, United States. Association for Computational Linguistics.
Xiang Lisa Li and Percy Liang. 2021. Prefix-tuning: Optimizing continuous prompts for generation. In Proceedings of the 59th Annual Meeting of the Asso- ciation for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 4582- 4597, Online. Association for Computational Lin- guistics.
Taylor Shin, Yasaman Razeghi, Robert L. Logan IV, Eric Wallace, and Sameer Singh. 2020. AutoPrompt: Elic- iting Knowledge from Language Models with Auto- matically Generated Prompts. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), P), pages 4222-4235, Online. Association for Computational Linguistics.
Jiachang Liu, Dinghan Shen, Yizhe Zhang, Bill Dolan, Lawrence Carin, and Weizhu Chen. 2022a. What makes good in-context examples for GPT-3? In Proceedings of Deep Learning Inside Out (DeeLiO 2022): The 3rd Workshop on Knowledge Extrac- tion and Integration for Deep Learning Architectures, pages 100-114, 14, Dublin, Ireland and Online. Associa- tion for Computational Linguistics.
Tianxiang Sun, Zhengfu He, Hong Qian, Yunhua Zhou, Xuanjing Huang, and Xipeng Qiu. 2022a. BBTv2: Towards a fradient-free future with large language models. In Proceedings of the 2022 Conference Empirical Methods in Natural Language Processing, pages 3916-3930, Abu Dhabi, United Arab Emirates. Association for Computational Linguisties.
Pengfei Liu, Weizhe Yuan, Jinlan Fu, Zhengbao Jiang, Hiroaki Hayashi, and Graham Neubig. 2023. Pre- train, prompt, and predict: A systematic survey of prompting methods in natural language processing. ACM Computing Surveys, 1-35)
Tianxiang Sun. Yunfan Shao, Hong Qian, Xuanjing Huang, and Xipeng Qiu. 2022b. Black-box tuning for sattugg--odellas-a--ee
In International Con- ference on Machine Learning, pages 20841-2003 PMLR.
Xiao Liu, Kaixuan Ji, Yicheng Fu, Weng Tam, Zhengx- iao Du, Zhilin Yang, and Jie Tang. 2022b. P-tuning: Prompt tuning can be comparable to fine-tuning across scales and tasks. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 61-68. Dublin, Ireland. Association for Computational Lin- guistics.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. Advances in nearal information processing systems, 30.
Xingchen Wan, Vu Nguyen, Huong Ha, Bin Xin Ru, Cong Lu, and Michael A. Osborne. 2021. Think global and act local: Bayesian optimisation over high- dimensional categorical and mixed search spaces. In International Conference on Machine Learning, pages 10663-10674.
Xinxi Lyu, Sewon Min, Iz Beltagy, Luke Zeulemoyer, and Hannanch Hajishirzi. 2022. Z-icl: Zero-shot in- context learning with neuud-demonstratioon. arXiv preprint 1rX.v:2212..98865
Xingchen Wan, Binxin Ru, Pedro Esperança, and Zhenguo Li. 2022. On redundancy and diversity
OpenAI. 2023. Gpt-4 technical report.

---

in cell-based neural architecture search. In Interna- tional Conference on Learning Representations.
A Implementation Details
A.1 Additional Experimental Details
Xingchen Wan, Ruoxi Sun, Hanjun Dai, Sercan Arik, and Tomas Pfister. 2023a. Better zero-shot reasoning with self-adaptive prompting. In Findings of the As- sociation for Computational Linguistics: ACL 2023, pages 3493-3514, Toronto, Canada. Association for Computational Linguistics.
For all experiments that record wall-clock time, we run on a single RTX 4090 24GB GPU. The main experimental results in Table & 2, we run on the RTX 4090 24GB GPU and the A100 80GB GPU.
Xingchen Wan, Ruoxi Sun, Hootan Nakhost, Han- jun Dai, Julian Martin Eisenschlos, Sercan O Arik, and Tomas Pfister. 2023b. Universal self-adaptive prompting. arXiv preprint arXiv:2305.149990
CLAPS, During the phase of search space pruning, we exclusively focus on tokens with a space in front of it, which removes the majority of tokens that are not single word and various symbols across different languages. In clustering, we collect 2000 centroids with the closest word in the embedding space. Then, we filter the clustered set by removing repetitive words, which then gives 1867 tokens the initial search space before pruning.
Alex Wang. Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman, 2018. GLUE; A multi-task, benchmark and analysis platform for nat- ural language understanding. In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 553-355, Brussels, Belgium. Association for Com- putational Linguistics.
In implementing the evolutionary search algo- rithm, we conduct 30-epoch search with a popu- lation size of 128, and both mutation and crossover size of 64. At each epoch, we retain 10% fraction of top candidates to the next epoch. We searched only for the 5-token length for all our experiments.
Yuan Zang, Fanchao Qi, Chenghao Yang, Zhiyuan Liu, Meng Zhang. Qun Liu, and Maosong Sun. 2020. Word-level textual adversarial attacking as combi- natorial optimization. In Proceedings of the 58th An- nual Meeting of the Association for Computational Linguistics, pages 6066-6080, Online. Association for Computational Linguistics.
For the particle swarm optimization, we use the open-source implementation (https:// gi github.ce catuu..com/huunnn httm://ttnnlp/Semmmes-tttttt ZZang et al. (2020) that is compatible with dis- crete search spaces over word tokens. The key changes that we made were to reflect the fact that the prompting setup is less restrictive than the ad- versarial attack that Zang et al. (2020) considered, which would also require the changes in text to be as imperceptible as possible. As such, we removed constraints such as only substitution is allowed, and, unlike adversarial attacks where the algorithm is terminated whenever successful perturbation is found, we always run full 40 epochs.
from
Guangtao Zeng, Peiyuan Zhang, and Wei Lu. 2023, One network, many masks: Towards more parameter- efficient transfer learning. CoRR, abs/2305. 17682.
Tianjun Zhang, Xuezhi Wang, Denny Zhou, Dale Schu- urmans. and Joseph E. Gonzalez. 2023. TEMPERA: Test-time prompt editing via reinforcement learning. In The Eleventh International Conference on Learn- ing Representations.
Xiang Zhang, Junbo Jake Zhao, and Yann LeCun, 2015. Character-level convolutional networks for text clas- sification. In Advances in Neural Information Pro- cessing Systems 28: Annual Conference Neural In- formation Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 449-657.
Fine-tuning. We follow the same implementation of standard T5 fine-tuning (Karimi Mahabadi et al., 2021: Zeng et al., 2023). Due the simplicity of the seq2seq pipeline, we keep the default training templates for all fine-tuning experiments.
Han Zhou, Xingchen Wan, Lev Proleev, Diana Mincu, Jilin Chen, Katherine Heller, and Subhrajit Roy. 2023a. Batch calibration: Rethinking calibration for in-context learning and prompt engineering. arXiv preprint 2309. 17249.
BDPL. We use the same prompt templates for both CLAPS and BDPL. We use the default hyperparam- eter setup for all its experiments with sample size of 20 and 30 epochs. For the experiments in Fig. 1, we run BDPL for roughly the same wall-clock time as CLAPS, which lasts 360 epochs.
Han Zhou, Xingchen Wan, Tvan Vulić, and Anna Ko- rhonen. 2023b. Autopeft: Automatic configuration search for parameter-efficiens fine-tuning. arXiv preprint arXiv:2301.122 12132.
RLPrompt. We implement the same prompt tem- plates for both CLAPS and RLPrompt for a fair comparison. We report the default hyperparam-

---

CLAPS
Method
FT
Manual
BDPL
RLP.
Search
Genetics
Partiele Swarm
Greedy
SST-2
76.190.93
85.32
84.892.29
86.01
85.85
87.78
87.551.81
90.37
RTE
51.552.46
73.65
72.272.77
78.52a.60
77.471.13
81.23u.56
79.93
79.42
SNLI
60.984.18
48.97
51.65
63.06p.42
59.302.27
65.923.14
66.123.35
63.47
QNLI
67.944.19
62.40
1..5
74.853.40
65.832.20
70.522.04
69.45
80.07
MNLI
45.994.81
43.15
42.524.29
57.60
47.30
50.453.09
53.71 1.78
57.02
MRPC
68.730.71
69.12
7..49
58.82
72.741.11
68.433.03
70.832,14
65.93
QQP
66.31281
79.07
68.4 68.442.64
80.099.59
80.571.76
80.870.75
81,51
81,40
AG's News
83.620.77
71.15
70.7
1..9
77.20
76.06n.86
77.031.1a
77.13
Average
65.16
66.60
65.44
71.98
70.78
72.66
73.27
74.35
Table 5: Accuracy on Flam-T5hms. with three different search algorithms on CLAPS. We reproduce all baselines and report the mean and standard deviation random seeds Flan-T5bae- The best and second-best results are marked in bold fonts and ranked by color.
#Cluster 20000
6000
2000
1000
proved task performance, and this is thus largely task-dependent. In relative terms, CLAPS im- proves almost all of the tasks with significantly enhanced efficiency, validating its orthogonality to the selected search algorithm.
SST-2
87.842.11
87.662.07
87.78
18.52
RTE
91.950.44
80,431,57
81.23pb56
77.91 1.43
Table 6:
Performance CLAPS (Genetics) with respect the number of clusters in the phase of clustering.
We provide ablation study that conducts the CLAPS pipeline with different numbers of clusters in the phase of clustering in Table 6. It reveals that having the number of clusters at 2000 stands as a good empirical trade-off point for saving the cost while showing strong performance across tasks.
#Token
5
10
SST-2 RTE
87.0 87.041.18
87.781.77
87.41
80.07..87 1.87
81.230.56
79.49
We then provide an ablation study with various token lengths in Table 7. First, increasing the token length from 2 to 5 leads to an improvement in per- formance the two tasks. It shows that longer sentence can provide more expressive control and description for prompting the language model. By further increasing the token length from to 10. we observe decrease in performance and consider this to be due to the dimensionality problem in derivative- optimization.
Table 7: Performance of CLAPS (Genetics) over the number of discrete tokens in the stage of black-box prompt search.
eter setup for all experiments. For computation- ally expensive experiments with XNLI or using Flan-T5jarg as the backbone, we set the training steps as 6000 instead of 12000. In addition, since RLPrompt requires an order-of order-of-magnune magnitude training cost than CLAPS, set strict wall-clock limit all RLPrompt experiments that go beyond 12 training hours via A100. We then take the same number of evaluation prompts as CLAPS fixed time intervals. Following RLPrompt's open-source script, we test the prompt with the highest valida- tion reward score.
C Prompt Template
We present the prompt template of the tasks con- sidered in Table 8.
B Additional Experimental Results
We attach the main experimental results from Ta- ble I with standard deviation and additional CLAPS results by particle swarm optimization in Table Based on three different CLAPP search strategies, we find that, in absolute terms, it does matter what search strategy used to yield im-

---

Dataset
Prompt template
SST2
Template: [prompt), Sentence: (sentence)); Sentiment:
Verbalizer: negative, positive
CLAPS: cruise perfect properly review cruise
RTE
Template:
(prompt). Sentence 1: (sentence:), Sentence 2: (sentence>), Textual Entai Iment:
Verbalizer: yes,
CLAPS: answer respectively minimum tell answer Template I: {prompt) (sentence:) (sentence;) Entailment:
SNLI
Template 2: (prompt). In this task, the goal is to predict textual entailment with "yes' 'maybe' 'no', sentence implies sentence B entailment: yes; sentence A neutral to sentence entailment: maybe; sentence contradicts sentence B entailment: no. Sentence A: (sentence:) Sentence [sentencez], Entailment:
Verhalizer: yes, maybe,
CLAPS: möchten kannst procent dass that Template: (prompt). Question: (sentencer), Sentence: (sentence>), Entailment: Verbalizer: yes,
QNLI
CLAPS: leider respectively read respectively
MNLI
Template I: [prompt) [sentence:) (sentence,) Entailment:
Template 2: (prompt). In this task, the goal is to predict textual entailment with "yes' 'maybe' 'no" sentence implies sentence B entailment: yes; sentence A neutral to sentence entailment: maybe; sentence contradicts sentence B entailment: no. Sentence A: (sentence:) ) Sentence {sentencez), Entailment: Verhalizer: yes, maybe,
CLAPS: tell relevant statement suggest suggest
MRPC
Template: (prompt), Sentence (sentencer), Sentence 2: (sentence:), Semantically Equivalent: Verbalizer: yes
CLAPS: courses beschrieben serial vertical Über
QQP
Template: [prompt). Sentence 1: (sentence:), Sentence 2: (sentence:), Semantically Equivalent:
Verbalizer: no, yes
CLAPSS: suggest outside cause exists statement
AG's
Template: (prorpt). Classify the news articles into the categories World, Sports, Business, Technology. (sentence:):
News
Verhalizer: World, Sports, Business, Technology
CLAPS: prize computing panel Congress certified
XILI
Template I: (prompt) [sentence: (sentencez) Entailment:
Template (prompt). In this task, the goal is to predict textual entailment with 'yes' 'maybe' 'no'. sentence impliies sentence B entailment: yes; sentence A is neutral to sentence B entailment: maybe; sentence contradicts sentence 8 entailment: no. Sentence A: {sentence:); Sentence B: (sentence;), Entailment: Verbalizer: yes, maybe, no CLAPS: think ask relevant description mind
Table 8: Prompt templates for prompt search experiments, where we also implement the same template for both BDPL and RLPrompt experiments. We use Template for Flan-T5 experiments. Due to the level of difficulty SNLIMNLI/XNLJ, evaluate Template with task instruction for Flan-T5 experiments, which demonstrate better in-context learning capability than small language models. All templates are manually created and fixed without iterations.


Reviews:
[{"review_id": "rFTZrWwyGq", "reviewer": "Reviewer_a6rh", "summary": "", "questions": "See above.", "limitations": "", "rating": 3, "confidence": 3, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed and insightful review! Please see our response below, which we believe has addressed all the concerns. We hope that in light of the response, the reviewer could consider improving their score.\n***\n> The proposed Clustering and Pruning for Efficient Black-box Prompt Search (ClaPS) method involves several stages, which may lead to reduced elegance and lack of principled reasoning. This complexity could make it challenging to understand and reproduce the method in a straightforward manner.\n\nWe emphasize that while ClaPS involves several stages, the design of each and every stage is strongly justified with technical rationales and motivated in the paper rather than artificially constructed for unnecessary complexity. We thus do not see as a weakness the fact that our method involves multiple stages. In a nutshell, 1) we perform clustering to reduce the computational cost (note that the method does work even without the clustering step, 2) pruning to curate a high-performing search space, and 3) search to identify a final set of token prompts. The reviewer is also welcome to run our attached code, which, in our opinion, alleviates any potential challenges the reviewer mentioned regarding reproducibility.\n***\n> The paper lacks comprehensive implementing details of the ClaPS method.\n\nWe report the overall step-by-step walkthrough in Alg. 1, and all our implementation details are in Section 3 and Appendix A.1. We also kindly refer the reviewer to our codebase in the submitted supplementary materials to examine all the implementation and reproducibility details. We will also open-source our codebase, as stated in the paper. \n***\n> The paper does not report standard deviations or conduct statistical tests when comparing the proposed method with the baselines, which makes it difficult to assess the significance and reliability of the observed performance improvements.\n\nWe thank the reviewer for pointing this out. In the main results, Tables 1 and 2, we have reported the mean for 5 random seeds for the Flan-T5 base model, and the standard deviation was omitted for conciseness. We recall that our Figure 1 and Figure 3 are also reported with 5 random seeds, which ensured the reliability of our observed performance improvements. We now attach Table 1 with standard deviations, and we will include this new table in the appendix section to remove any concerns.\n\n\n| Method | FT                | Manual  | BDPL       | RLP.            | Search      | ClaPS        | \n|--------------|----------------|----------|-----------------|----------------|----------------|----------------|\n| SST-2      |76.19+-0.93|85.32   |84.89+-2.29|86.01+-1.32|85.82+-1.79|87.78+-1.77|  \n| RTE         |51.55+-2.46|73.65   |72.27+-2.37|78.52+-0.60|77.47+-1.13|81.23+-0.56|  \n| SNLI        |60.98+-4.18|48.97   |51.65+-3.95|63.06+-0.42|59.30+-2.27|65.92+-3.14|  \n| QNLI       |67.94+-4.19|62.40   |61.53+-1.81|74.85+-3.40|65.83+-2.20|70.52+-2.04|  \n| MNLI       |45.99+-4.81|43.15   |42.52+-4.29|57.60+-0.88|47.30+-3.85|50.45+-3.09|  \n| MRPC     |68.73+-0.71|69.12   |71.49+-7.93|58.82+-1.83|72.74+-1.11|68.43+-3.03|  \n| QQP        |66.31+-2.81|79.07   |68.44+-2.64|80.09+-0.59|80.57+-1.76|80.87+-0.75|", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "\n- The paper presents an interesting and important research problem, addressing the efficiency of black-box prompt search for large pretrained language models (LLMs). \n\n- It showcases strong performance compared to recent baselines, demonstrating the effectiveness of the proposed Clustering and Pruning for Efficient Black-box Prompt Search (ClaPS) method across various tasks and LLMs.\n\n- Figure 4 provides a clear and easy-to-understand visualization of the sensitivity analysis and influential prompt tokens, contributing to the paper's overall clarity and readability.", "reasons_to_reject": "1. The proposed Clustering and Pruning for Efficient Black-box Prompt Search (ClaPS) method involves several stages, which may lead to reduced elegance and lack of principled reasoning. This complexity could make it challenging to understand and reproduce the method in a straightforward manner.\n\n2. The paper lacks comprehensive implementing details of the ClaPS method.\n\n3. The paper does not report standard deviations or conduct statistical tests when comparing the proposed method with the baselines which makes it difficult to assess the significance and reliability of the observed performance improvements.", "questions_to_authors": "See above.", "paper_topic_and_main_contributions": "The paper introduces ClaPS, a Clustering and Pruning method for Efficient Black-box Prompt Search, to enhance prompt-based learning for large pretrained language models (LLMs). By identifying and focusing on influential prompt tokens, ClaPS achieves state-of-the-art performance across tasks and LLMs while reducing search costs, highlighting the significance of search space design and optimization for efficient black-box prompt-based learning.\n\n\n", "excitement": 3, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "lURBYmo94t", "reviewer": "Reviewer_4AgN", "summary": "", "questions": "A. I have some concerns about the design choices of the methods\n\n(i) How did you set the values of the hyper-parameters including the number of clusters, pruning ratio, and number of evolution iterations?\n\n(ii) How the performace correlates with each of hyper-parameters?\n\n(iii) How sensitive is the performance to the hyper-parameters?\n\n(iv) Why is the proposed method only evaluated in the settings of fixed 5-token prompts? I think that the proposed method have more scalability and flexibility to the prompt length than RL-based methods. So, would you provide some results with more diverse lengths (e.g., 2-token prompts, 10-token prompts, or dynamic-length prompts)?\n\n(v) As the k-means clustering and evolutionary search have randomness, the reported results might not be replicated in other runs with different random seeds. Would you report the mean and variance of the benchmark performance?\n\nB. Previous work [1] on prompt search has shown that the searched prompts might include some unreadable words, but those by the proposed method seems mostly readable and semantically related to given tasks. What component of the proposed method does make the differences?\n\n[1] Deng et al., RLPrompt: Optimizing Discrete Text Prompts with Reinforcement Learning, EMNLP 2022.\n\n---\n\nI have read the response. The authors have mostly addressed my concerns. Thus, I adjust the scores in favor of acceptance.", "limitations": "", "rating": 3, "confidence": 3, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed and constructive feedback! Please see below for our response. We hope that the reviewer will consider increasing their scores if they think we have sufficiently addressed their concerns.\n***\n> A. The lack of analysis on the design choices raises the question about the optimality and robustness of the proposed method.\n\nBefore responding to the reviewer’s questions on optimality and robustness of hyperparameters, we would like to stress that we **deliberately did not perform extensive hyperparameter tuning** for our method, nor did we seek to use a different, optimal set of hyperparameters for each task/model that many previous works did – while it is indeed possible to achieve so and to perform hyperparameter optimization per-task for even higher performance with our proposed method, we opted not to do so as this is typically expensive or otherwise unrealistic for real-life tasks. Instead, we achieved impressive results, as the reviewer acknowledged, with a single set of hyperparameters, without tuning, for all experiments. For the baselines, we did lean on the hyper-parameters suggested by previous research (which puts the baselines in a slight prior advantage compared to our method). We believe this is extremely strong evidence demonstrating the robustness and practicality of our method and is one of the key strengths of the proposed CLaPS method.\n\nWith this key point in mind, we now respond to the rest of the questions in detail.\n***\n> (i) How did you set the values of the hyper-parameters including the number of clusters, pruning ratio, and number of evolution iterations?\n\nAs discussed, the hyperparameters are simply set to reasonable values without further tuning. As described in Fig 4 of our manuscript, the high-level rationale is to reduce the number of “surviving” vocabulary by an order of magnitude in each stage. Starting with $\\mathcal{O}(10^4)$ tokens, we use clustering to reduce the vocabulary to $\\mathcal{O}(10^3)$, pruning to $\\mathcal{O}(10^2)$ and search to identify the final tokens to be used as discrete prompts. \n\nSpecifically, the number of clusters is selected to be as large as computationally tractable to ensure diversity; evolution iteration is set at an empirically observed value until the accuracy stops increasing for several epochs. We already analyzed the effect of the pruning ratio in Fig 5, and we found the method to be quite robust – we can see that any non-zero pruning value leads to improvements over the performance at 0.0 (i.e., no pruning).\n***\n>(ii) How the performace correlates with each of hyper-parameters? (iii) How sensitive is the performance to the hyper-parameters?\n\n**Number of evolution epochs**: The performance with respect to evolution epochs can be interpreted from Figure 1, where ClaPS starts from the first epoch and ends at the 30th epoch. The curve is observed to plateau around or before this point and is thus set as a common stop point for all our experiments.\n\n**Number of clusters**: Recalling that the purpose of clustering is to obtain a diverse set of candidate tokens and thus to save computation in the pruning stage, we now attach an ablation study that conducts the ClaPS pipeline with different numbers of clusters, and we will include this study in the appendix section. From the following table, having our number of clusters at 2000 stands as a good trade-off point for saving the cost while showing strong task performance.\n\n| #Cluster  | 20000 | 6000  | 2000   | 1000  |\n|--------------|----------|---------|----------|-----------|\n| SST-2      |87.84+-2.11|87.66+-2.07|87.78+-1.77|88.19+-0.52|\n| RTE         |81.95+-0.94|80.43+-1.57|81.23+-0.56|77.91+-1.43|   \n\n**Pruning ratio**: The most sensitive hyperparameter is the pruning ratio that controls the size of the search space, and we have included relevant discussions in Figure 5 and Line 559-570. \n***\n> (iv) Why is the proposed method only evaluated in the settings of fixed 5-token prompts? I think that the proposed method have more scalability and flexibility to the prompt length than RL-based methods. So, would you provide some results with more diverse lengths (e.g., 2-token prompts, 10-token prompts, or dynamic-length prompts)?\n\nThe reviewer is correct that our method is more flexible, and we used fixed 5-token prompts as we would like a direct comparison with the strongest baseline of RLPrompt, which achieved the best performance in the 5-token setup. We now provide an ablation study with various token lengths, and we will include this result in the appendix section. First, increasing the token length from 2 to 5 leads to an improvement in performance over the two tasks. This is expected as a longer sentence can provide more expressive control and description for prompting the language model. By further increasing the token length from 5 to 10, we observe a decrease in performance and consider this to be due to the dimensionality problem in derivative-free optimization. \n\n| #Token     | 2               | 5                   | 10            | \n|--------------|----------------|------------------|--------------|\n| SST-2      |87.04+-1.18|87.78+-1.77  |87.41+-0.88|\n| RTE         | 80.07+-1.87|81.23+-0.56 |79.49+-1.59|\n***\n> (v) As the k-means clustering and evolutionary search have randomness, the reported results might not be replicated in other runs with different random seeds. Would you report the mean and variance of the benchmark performance?\n\nIn the main results, Tables 1 and 2, we have reported the mean for 5 random seeds for the Flan-T5 base model, and the standard deviation was omitted for conciseness. We recall that our Figure 1 and Figure 3 are also reported with 5 random seeds, which ensured the reliability of our observed performance improvements. We now attach Table 1 with standard deviations, and we will include this new table in the appendix section. The reviewer is also referred to our codebase in the submitted supplementary materials for any reproducibility concerns. We will also open-source our codebase. \n\n| Method | FT                | Manual  | BDPL       | RLP.            | Search      | ClaPS        | \n|--------------|----------------|----------|-----------------|----------------|----------------|----------------|\n| SST-2      |76.19+-0.93|85.32   |84.89+-2.29|86.01+-1.32|85.85+-1.79|87.78+-1.77|  \n| RTE         |51.55+-2.46|73.65   |72.27+-2.37|78.52+-0.60|77.47+-1.13|81.23+-0.56|  \n| SNLI        |60.98+-4.18|48.97   |51.65+-3.95|63.06+-0.42|59.30+-2.27|65.92+-3.14|  \n| QNLI       |67.94+-4.19|62.40   |61.53+-1.81|74.85+-3.40|65.83+-2.20|70.52+-2.04|  \n| MNLI       |45.99+-4.81|43.15   |42.52+-4.29|57.60+-0.88|47.30+-3.85|50.45+-3.09|  \n| MRPC     |68.73+-0.71|69.12   |71.49+-7.93|58.82+-1.83|72.74+-1.11|68.43+-3.03|  \n| QQP        |66.31+-2.81|79.07   |68.44+-2.64|80.09+-0.59|80.57+-1.76|80.87+-0.75|  \n\n***\n> B. The proposed method is only evaluated on text classification tasks. It is unclear that the proposed method universally works well including reasoning and generation tasks. Although the authors partially mentioned this point in the limitation section in the paper, but it needs to be clarified whether the efficiency comes at a limited capability of models.\n\nWe mainly follow the evaluation datasets from competitive baselines like BDPL and RLPrompt. In addition, we also carry out more challenging experiments on multilingual XNLI datasets to reveal the potential of different prompt search methods in multilingual learning. We will endeavor to include results on more models and datasets as part of future work.\n***\n> C. The paper lacks discussion about the differences of the prompts searched by the proposed method compared with those of existing methods.\n\nIn Lines 543-558, we provide a short discussion of the ClaPS-discovered prompts. Since the ClaPS is not explicitly tuned towards fluency, we list ClaPS-discovered prompts as an interesting reference for readers. We now attach a table below that contains the prompts from the strongest baseline. We will include the corresponding discussion in the appendix section in the camera-ready version. \n\nIt is noticeable that ClaPS shares some words with competitive baselines, and these words (e.g., 'review' and 'answer') are usually 'influential prompts' identified by our pruning strategy and have significant impacts on the model’s prediction.  With a similar or even better quality of prompts, ClaPS stands out by first establishing an efficient search space while saving significant computation costs. For a more detailed discussion on the readability of our prompts, please find our response to the next question.\n\n|Method     |SST-2  | RTE    | \n|--------------|----------|----------|\n| RLP.      |ReviewCustomerBankBankBank  | DatabaseansweranswerYesĠyes|\n| ClaPS   |cruise perfect properly review cruise |answer respectively minimum tell answer|\n\n***\n> B. Previous work [1] on prompt search has shown that the searched prompts might include some unreadable words, but those by the proposed method seems mostly readable and semantically related to given tasks. What component of the proposed method does make the differences?\n\nAs described in Appendix A.1 Lines 821-825, we ensure the pruning phase works on a single word while filtering all special tokens, which eventually improves the readability of the whole sentence with multiple words. In addition, during the pruning phase, we discover that the most influential prompts are usually contextual words or in-domain words, e.g., 'review' and 'answer' for SST-2 and RTE, respectively. This contextual feature also helps the interpretability of our results. RLPrompt has no implementation of search space reduction, which occasionally results in unreadable and gibberish prompts. This finding further coincides with the main claim of this paper, and it emphasizes the importance of the search space for prompts.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "A. The paper is easy-to-follow. The emprical observations in the paper clearly illustrate the problem.\n\nB. The proposed method is simple, intuitive, and apparently sound.\n\nC. The proposed method shows impressive results in terms of accuracy and efficiency.", "reasons_to_reject": "A. The lack of analysis on the design choices raises the question about the optimality and robustness of the proposed method.\n\nB. The proposed method is only evaluated on text classification tasks. It is unclear that the proposed method universally works well including reasoning and generation tasks. Although the authors partially mentioned this point in the limitation section in the paper, but it needs to be clarified whether the efficiency comes at a limited capability of models.\n\nC. The paper lacks discussion about the differences of the prompts searched by the proposed method compared with those of existing methods.", "questions_to_authors": "A. I have some concerns about the design choices of the methods\n\n(i) How did you set the values of the hyper-parameters including the number of clusters, pruning ratio, and number of evolution iterations?\n\n(ii) How the performace correlates with each of hyper-parameters?\n\n(iii) How sensitive is the performance to the hyper-parameters?\n\n(iv) Why is the proposed method only evaluated in the settings of fixed 5-token prompts? I think that the proposed method have more scalability and flexibility to the prompt length than RL-based methods. So, would you provide some results with more diverse lengths (e.g., 2-token prompts, 10-token prompts, or dynamic-length prompts)?\n\n(v) As the k-means clustering and evolutionary search have randomness, the reported results might not be replicated in other runs with different random seeds. Would you report the mean and variance of the benchmark performance?\n\nB. Previous work [1] on prompt search has shown that the searched prompts might include some unreadable words, but those by the proposed method seems mostly readable and semantically related to given tasks. What component of the proposed method does make the differences?\n\n[1] Deng et al., RLPrompt: Optimizing Discrete Text Prompts with Reinforcement Learning, EMNLP 2022.\n\n---\n\nI have read the response. The authors have mostly addressed my concerns. Thus, I adjust the scores in favor of acceptance.", "paper_topic_and_main_contributions": "This paper addresses the problem of a large search space in prompt search. To reduce the cost in searching over a large size of vocabulary, the authors propose an evolutionary algorithm combined with a vocabulary pruning method. The experimental results in the paper show that the proposed method outperforms state-of-the-art prompt search methods on 5-token prompt search with various NLP benchmarks.", "excitement": 3, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "7AOvTvAlU1", "reviewer": "Reviewer_3YDq", "summary": "", "questions": "- Discrete prompt optimization problem is a combinatorial optimization problem. In ClaPS, the authors propose search algorithm based on evolutionary method. However, the effectiveness of the proposed search method was not exploited enough. I list some possible candidates of method.\n1. Greedy : Similar to ClaPS, [1] reduce the token cadidate set using gradient signal and search optimal prompt using greedy algorithm. I think search algorithm can be directly applied into the setting of ClaPS.\n2. Bayesian Optimization : Adversarial attack research on NLP models also solves similar combinatorial optimization problem with discrete prompt optimization. [2] uses Bayesian optimization (BO) as the solver. \n3. Particle swarm optimization : [3] uses particle swarm optimization (PSO) as the solver.\n4. RLPrompt : I think you may directly plug in RLPrompt method as the search method for the reduced search space.\nIf possible, can you show the superiority of your proposed search algorithm compared to some possible candidates of search algorithm? Also, I want to see the curve of validation accuracy and test accuracy for each optimization method.\n- Since ClaPS is a black-box prompt optimization method, you may apply the proposed method into black-box API such as GPT-4 or ChatGPT. Can you provide comparison between manual prompt and discrete prompt optimized by ClaPS?\n- In the black-box setting, the number of queries to the target model is one of the most important factor that measures computational resource. Can you provide test accuracy vs number of queries plot of ClaPS and other black-box prompt optimization method? It will help visualize query-efficiency of your method.\n- If I understood correctly, ClaPS require some queries on target model during clustering and pruning procedure (for ranking candidates). Does the resource (time and vram) in table 3 contain the resource used in clustering and pruning step?\n\nI promise that I'll raise my score if the responses are satisfactory.\n\n[1] AutoPrompt: Eliciting Knowledge from Language Models with Automatically Generated Prompts, Shin et al., EMNLP 2020\n\n[2] Query-Efficient and Scalable Black-Box Adversarial Attacks on Discrete Sequential Data via Bayesian Optimization, Lee et al., ICML 2022\n\n[3] Word-level Textual Adversarial Attacking as Combinatorial Optimization, Zang et al., ACL 2020\n\n[4] RLPrompt: Optimizing Discrete Text Prompts with Reinforcement Learning, Deng et al., EMNLP 2022", "limitations": "", "rating": 2, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful comments, especially the suggestions on additional search methods, which are particularly useful in further strengthening our manuscript. We refer the reviewer for a detailed response below and would be grateful if the reviewer could consider increasing their rating if they found our response convincing.\n***\n> I'm curious whether the proposed search algorithm is suitable algorithm to search in the reduced search space. I think ablation on search algorithm is necessary to make sure that the algorithm is one of the contribution or not.\n\nWe would like to emphasize we did *not* claim the search method described as a key contribution. As we discussed in the Introduction, our focus is primarily on search space and its importance (“Line 090: While previous works have attempted to alleviate this problem by improving the search strategy, search space design has been largely overlooked.”), which is supported by our findings in Sec 3 that after search space pruning, even “randomly sampled discrete prompts can be competitive with the state of the art” (Line 283). As we stated in Line 355, we deliberately opted to use a very basic algorithm to contrast with previous methods with advanced search algorithms but made little to no attempt to improve the search space. \n\nIt is indeed possible (and in some tasks indeed the case — see our response later) that, as the reviewer suggested, another search algorithm is superior to the one adopted in the paper. However, if that is the case, the fact that the suboptimal search algorithm used in this paper with intelligent search space pruning outperforms complicated, state-of-the-art search algorithm without search space pruning exactly proves the point of this paper, that search space is equally, if not more important, which is a key aspect the community has so far (largely) ignored. We will show later, per the reviewer’s suggestions, that it is indeed true that CLaPS benefits from search method improvements, leading to an even larger gain.\n***\n> The experiments are only conducted on Flan-T5 models.\n\nWe acknowledge the reviewer’s concerns. The chief reason we focused on Flan-T5 models is that of the model scale that we have computational resources to perform extensive experiments for, instruction-finetuned Flan-T5 achieves the best performance. We will endeavor to include results on more models in the future.\n***\n> The number of queries to the target model should be considered as the evaluation metric for resource usage.\n> Test accuracy vs number of queries plot of ClaPS and other black-box prompt optimization method? \n\nWe thank the reviewer for suggesting also considering the number of queries as a metric for resource usage. We now update our Table 3 by also including the number of queries. By comparing with the strongest baseline, RLPrompt, the proposed ClaPS method is more query efficient than RLPrompt by leveraging half the number of queries with better task performance.  Though we would like to provide the visualization of the plot of test accuracy vs. the number of queries, we are not allowed to attach any links. However, Figure 1 can still be interpreted with the number of queries as each method requires a fixed time span per query. Therefore, with the support of updated Table 3 and Figure 1, ClaPS also shows as the most query-efficient method, and other baselines (e.g. the blue line, RLPrompt) will not surpass ClaPS given even larger query budgets. We will include this number of query plot as the reviewer suggested in the camera-ready version. \n \n| Method             |#Params|VRAM| Time| #Query  | SST-2(%)  |\n |---------------------|----------|----------|----------|----------|----------|\n| FT                    | 250M  |6.53GB|0.42min|     -       |76.15|  \n| RLPrompt        |  3M     |3.60GB|65.1min| 12000  |86.01| \n| BDPL               | 1K      |2.54GB|0.20min|   600   |84.89|  \n| Search             |   0       |2.54GB|1.26min|  4000  |85.82| \n| Prune&Search |   0       |2.54GB|7.65min| 24000 |87.84|  \n| ClaPS              |   0       |2.54GB|1.80min|  6000  |87.78|  \n\n***\n> Discrete prompt optimization problem is a combinatorial optimization problem. In ClaPS, the authors propose search algorithm based on evolutionary method. However, the effectiveness of the proposed search method was not exploited enough. \n\nWe thank the reviewer for the insightful suggestions; we tested some of the suggestions (but not all of them due to time and resource constraints during rebuttal), and we indeed found some of the suggested algorithms perform well – we will include full sets of such results for the camera-ready version. \n\nRe-emphasizing the point made above, though, we’d still like to stress the fact that the primary focus of this paper is on search space, not search methods and that the key contributions of the paper stand regardless of whether an alternative search algorithm outperforms, although we do thank the reviewer for suggesting alternative, potentially more suitable search algorithms that have made the performance of CLaPS even stronger.\n\nSpecifically, in the table below, we added a greedy search algorithm and a particle swarm optimizer as suggested. The greedy algorithm starts with an empty string, iterates through the pruned search space (200 tokens in our case), and picks the token that leads to the highest reward (or lowest loss). Conditional on this token, we then pick the second token that, when combined with the first chosen token, led to the highest reward. This process continues until all 5 tokens are selected – this process requires $k|\\mathcal{V}|$ total model queries, and thus shrinking $|\\mathcal{V}|$ leads to an $\\mathcal{O}(n)$ speedup.\n\nThe particle swarm optimizer is adapted from the [open-source implementation](https://github.com/thunlp/SememePSO-Attack) of the paper [3] that the reviewer mentioned. The main changes made are to reflect the fact that the prompting setup is less restrictive than the adversarial attack, which would also require the changes in text to be as imperceptible as possible. As such, we removed constraints such as only substitution is allowed, and, unlike adversarial attacks where the algorithm is terminated whenever a successful perturbation is found, we always run full 40 epochs. \n\nWe will also add the rest algorithms as the reviewer suggested in camera-ready. We hope the reviewer would sympathize with us that these algorithms are significantly more complicated given the short rebuttal timeframe.\n\n| Method    | RLP.  | Genetics (Ours) | Greedy (Ours) |Particle Swarm (Ours) | \n|--------------|---------|------------------------|--------------------|------------------------------|\n| SST-2      |86.01+-1.32   |87.78+-1.77 |**90.37**            |87.55+-1.81|\n| RTE        |78.52+-0.60   |**81.23+-0.56**  |79.42            |79.93+-1.85|  \n| SNLI       |63.06+-0.42   |65.92+-3.14  |63.47            |**66.12+-3.35**|  \n| QNLI       |74.85+-3.40   |70.52+-2.04 |**80.07**             |69.45+-1.73|  \n| MNLI       |**57.60+-0.88**  |50.45+-3.09  |57.02             |53.71+-1.78|  \n| MRPC     |58.82+-1.83  |68.43+-3.03  |65.93             |**70.83+-2.14**|  \n| QQP       |80.09+-0.59   |80.87+-0.75 |81.40             |**81.51+-0.25**| \n| ag_news |**77.20+-0.76**   |76.06+-0.85 |77.13             |77.03+-1.13| \n| Average    |71.98           |72.66            |**74.35**             |73.27          | \n\n\n***\n> Since ClaPS is a black-box prompt optimization method, you may apply the proposed method into black-box API such as GPT-4 or ChatGPT. Can you provide comparison between manual prompt and discrete prompt optimized by ClaPS?\n\nWe use the popular definition of “black box” following published works like RLPrompt [1], BDPL [2], and earlier works like BBT [3] that while no model architecture, parameter, or gradient is required, the output probabilities over the verbalizer classes are still expected. However, to our knowledge, the public GPT-4 or ChatGPT APIs do not provide the logits. However, as we responded previously, we appreciate the reviewer’s feedback and will endeavor to include experiments on other models of similar scale to the GPT models to show the point further.\n\n[1] Deng, M., Wang, J., Hsieh, C. P., Wang, Y., Guo, H., Shu, T., ... & Hu, Z.. Rlprompt: Optimizing discrete text prompts with reinforcement learning. EMNLP 2022.\n\n[2] Diao, S., Huang, Z., Xu, R., Li, X., Lin, Y., Zhou, X., & Zhang, T. Black-box prompt learning for pre-trained language models. TMLR 2022.\n\n[3] Sun, T., Shao, Y., Qian, H., Huang, X., & Qiu, X. Black-box tuning for language-model-as-a-service. ICML 2022\n***\n> Does the resource (time and vram) in table 3 contain the resource used in clustering and pruning step?\n\nThe table does not include the clustering step, which is a preprocessing step with negligible computation cost on the CPU and is done *once for all tasks per model*.\n\nThe table does contain the cost for both the pruning phase and search phase, and the time difference between Search and ClaPS is the time required for pruning. We will clarify this point when we revise the manuscript.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "- The existing discrete black-box prompt optimization methods suffer from computational cost caused by their huge search space. The proposed method solve this issue based on clustering and pruning the token candidates to search.\n- Sequentially, ClaPS solves the problem of high computational cost in existing methods such as RLPrompt.", "reasons_to_reject": "- However, I'm curious whether the proposed search algorithm is suitable algorithm to search in the reduced search space. I think ablation on search algorithm is necessary to make sure that the algorithm is one of the contribution or not.\n- Also, the experiments are only conducted on Flan-T5 models. \n- The number of queries to the target model should be considered as the evaluation metric for resource usage.\n\nPlease refer to questions.", "questions_to_authors": "- Discrete prompt optimization problem is a combinatorial optimization problem. In ClaPS, the authors propose search algorithm based on evolutionary method. However, the effectiveness of the proposed search method was not exploited enough. I list some possible candidates of method.\n1. Greedy : Similar to ClaPS, [1] reduce the token cadidate set using gradient signal and search optimal prompt using greedy algorithm. I think search algorithm can be directly applied into the setting of ClaPS.\n2. Bayesian Optimization : Adversarial attack research on NLP models also solves similar combinatorial optimization problem with discrete prompt optimization. [2] uses Bayesian optimization (BO) as the solver. \n3. Particle swarm optimization : [3] uses particle swarm optimization (PSO) as the solver.\n4. RLPrompt : I think you may directly plug in RLPrompt method as the search method for the reduced search space.\nIf possible, can you show the superiority of your proposed search algorithm compared to some possible candidates of search algorithm? Also, I want to see the curve of validation accuracy and test accuracy for each optimization method.\n- Since ClaPS is a black-box prompt optimization method, you may apply the proposed method into black-box API such as GPT-4 or ChatGPT. Can you provide comparison between manual prompt and discrete prompt optimized by ClaPS?\n- In the black-box setting, the number of queries to the target model is one of the most important factor that measures computational resource. Can you provide test accuracy vs number of queries plot of ClaPS and other black-box prompt optimization method? It will help visualize query-efficiency of your method.\n- If I understood correctly, ClaPS require some queries on target model during clustering and pruning procedure (for ranking candidates). Does the resource (time and vram) in table 3 contain the resource used in clustering and pruning step?\n\nI promise that I'll raise my score if the responses are satisfactory.\n\n[1] AutoPrompt: Eliciting Knowledge from Language Models with Automatically Generated Prompts, Shin et al., EMNLP 2020\n\n[2] Query-Efficient and Scalable Black-Box Adversarial Attacks on Discrete Sequential Data via Bayesian Optimization, Lee et al., ICML 2022\n\n[3] Word-level Textual Adversarial Attacking as Combinatorial Optimization, Zang et al., ACL 2020\n\n[4] RLPrompt: Optimizing Discrete Text Prompts with Reinforcement Learning, Deng et al., EMNLP 2022", "paper_topic_and_main_contributions": "- This paper deal with the problem of black-box discrete prompt optimization. \n- Existing black-box discrete prompt optimization papers consider catesian product of whole token sets as the search space. \n- On the other hand, the authors propose ClaPS that search prompt on the reduced search space. In detail, they cluster tokens on the embedding space and prune redundant tokens to construct reduced candidates of tokens.\n- The empirical results show that ClaPS achieve state-of-the-art peformance with faster runtime compared to baseline methods.", "excitement": 2, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a clustering and pruning method for black-box prompt search called CLaPS. The methodology integrates evolutionary algorithms with vocabulary pruning techniques to address the extensive search space associated with prompt search. The approach appears to outperform existing black box optimization methods in wall clock time while achieving similar or better prompts.

Some reviewers felt that the multi-stage nature of ClaPS potentially makes the approach a bit convoluted, hindering straightforward understanding and reproduction. Figure 4 does a reasonable job of visually demonstrating the different stages in the algorithm. Similarly, some reviewers found that the method lacked enough details/justifications for each step. During the rebuttal, the authors argue that their main contribution is the use of pruning to reduce the search space, and that a better search algorithm may further improve performance.

More qualitative comparison on how the prompts derived using ClaPS differ from those of existing methods. During the rebuttal, the authors provide additional comparison and commentary on the differences between the CLaPS output and RLPrompt output. However, this seems like a clear place where the work could be further improved.
Decision: Accept-Findings