Survival of the Most Influential Prompts: Efficient Black-Box Prompt Search via Clustering and Pruning (2023)

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.

## introduction many of the recent astounding breakthroughs in artificial intelligence have revolved around pretrained large language models (llms). though capabilities of llms have advanced at a breakneck speed, modern llms are remarkably consistent in that they are almost invariably powered by transformerbased architectures @xcite trained with simple, self-supervised text completion on a large corpus. this is typically followed by fine-tuning and/or, more recently, prompting-based methods on specific tasks @xcite @xcite . 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 or even zero-shot learning @xcite . 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 @xcite . although these methods do not require full gradient updates like fine-tuning, they still require parameter access, back-propagation through massive models, and are typically modeland/or task-specific. 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 to human interpretation, as they are actual tokens rather than abstract arrays in the embedding space @xcite . more importantly, unlike soft prompting, which invariably requires parameter access of llms due to the need to modify the embeddings, hpt is feasible even if the task llm is only available as a 'black box', i.e., only the model outputs, but not information like parameters and gradients, are available. indeed, methods leveraging reinforcement learning (rl) @xcite and gradient estimation @xcite have been recently proposed to exploit this powerful property, particularly since many advanced llms (e.g., @xcite and bard) are increasingly made available in a modelas-a-service (maas) manner, on which parameter or gradient access is expensive or impossible -thus, in this paper, we also focus on this practical but challenging black-box setup. despite the promising progress, one challenge plaguing the aforementioned black-box hpt approaches is the difficulty of the discrete and combinatorial optimization inherent to this problem when no gradient guidance is available -it is common that existing methods require a large number of model queries, frequently in the order of o(10 3 ) or more, before convergence. while previous works have attempted to alleviate this problem by improving 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 @xcite , by a 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 discrete optimization problems such as neural architecture search @xcite @xcite , 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., 0.1 -1% of all tokens) exerting a disproportionate amount of influence. meanwhile, the models are insensitive to or even harmed by the vast majority of the other, 'non-influential' tokens, which nevertheless act as nuisance variables during the search to substantially increase the optimization difficulty and resources required. 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 influential tokens, followed by the discrete prompt search on a few-shot objective. we find that after pruning, even the simplest search strategy (e.g., random or evolutionary search) can outperform state-of-theart methods with much more complicated search strategies, often at a fraction of the search costs over these competing methods (e.g., claps outperforms rlprompt with only 2.8% of its cost measured 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. ## preliminaries hard prompt tuning (hpt). as mentioned in §1, hpt aims to find discrete tokens to be concatenated directly to the test queries with the goal of maximizing task performance. formally, hpt may be represented as an optimization problem: search strategy and search space. solving eq. ( 1 ) is, in general, challenging, as it involves difficult combinatorial discrete optimization, and the gradients essential for standard first-order optimization are not available. a natural recourse, that most previous works have focused on, is developing better zeroth order search strategies, via, for example, reinforcement learning and monte carlo gradient estimation. search space (i.e., 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 of individual tokens: @xmath0, which is in turn often designed heuristically, and popular choices include the entire tokenizer vocabulary p @xmath1.r.t. the value of k, |p| is typically huge even for modest |p k | and/or k. ## 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 a profound effect on both the search strategy and the downstream performance. as the research community of hpt grows, we argue that a systematic study of the search space design is crucial. as discussed, existing search spaces are often expensive and heuristically designed. however, a large search space is not necessarily well-designed: crucially, it is unknown whether all parts of p positively contribute 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 optimization in eq. ( 1 ) unnecessarily hard. 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 @xmath2, we define: we visualize the results of the above analysis on a representative task in fig. 2 where we compute ∆r(v) for all tokens in the vocabulary foot_0 , and we find the distribution of influence over the vocabulary 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. ## efficient black-box prompt search via 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 algorithm 1. at a high level, claps utilizes a multistep 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 & prune (d) black-box hard prompt search of each token by evaluating on a 16-shot training set. while this procedure, which requires o(10 4 ) model evaluations can be already tractable, here we propose an additional optional step to accelerate further our method: instead of enumerating all tokens, we may use an unsupervised algorithm on the token embedding space to obtain a subset of diverse tokens v c that well-represent v (illustrated in fig. 4(b) ) -while alternative methods that explicitly optimize for diversity set selection exist, we opt for the simple greedy k-means++ @xcite to generate v c (we set |v c | = 2000 unless otherwise stated). formally, for each centroid e c identified by k-means++, we collect the closest token in terms of its embedding ℓ 2 distance: in our experiments, we set |v c | = 2000 for all model and task combinations without further hyperparameter tuning, and after the above procedure, the number of llm queries at the pruning stage reduces from o(10 4 ) to o(10 3 ). empirically, as shown in §6, we find this additional procedure to reduce the cost by roughly 3/4 relative to enumeration (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. ranking and pruning. as illustrated in fig. 4(c ), we prune v c (with clustering) or v (without clustering) using the procedure described in §3 to obtain the set of influential tokens for prompt search v it . the size of v it is another hyperparameter, which in this case encodes the greediness with a small |v it | 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 |v it | = 200 for all experiments without further model-or taskspecific hyperparameter tuning. ## conclusion we first analyzed the search spaces in the general paradigm of hard prompt search. inspired by the findings that only a small fraction of tokens exert a positive influence on 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-effective, and we showed that it achieves state-of-the-art performance in both mono-lingual and multi-lingual tasks with flan-t5 models. claps is a meta-method orthogonal to the search strategy, and we expect more efficient and effective prompt search algorithms can be created on top of it. we hope that future work will invest more time into the important problem of search space design.