Unlocking Black-Box Prompt Tuning Efficiency via Zeroth-Order Optimization (2024)

Abstract: Prompt optimization emerges as an important technique for adapting Large Language Models (LLMs) to specific tasks. Unfortunately, LLM proprietors often limit access to models’ internal weights, confining users to inference API services. This restriction poses a significant challenge for prompt optimization, as conventional optimization-based algorithms rely heavily on gradient information, which is unavailable via inference APIs. Addressing this challenge, this paper presents the Zeroth-Order Tuning (ZOT) approach, which enables efficient prompt tuning solely via inference APIs. ZOT adopts the zeroth-order optimization framework, utilizing finite differences to approximate gradient information. We further incorporate ZOT with gradient clipping and momentum techniques to enhance the tuning effectiveness. Experimental results show that ZOT outperforms existing black-box prompt tuning methods in terms of both task-specific performance and convergence speed. Furthermore, we provide a theoretical explanation for the unexpectedly strong performance of zeroth-order methods on LLM prompt tuning. By introducing the concept of effective dimension, we establish a strong connection between the inherently low effective dimension of prompt spaces and the superior convergence speed of zeroth-order methods. Our code is available at https://github.com/ZhanHeshen/ZOT.

## introduction prompts serve as essential tools for adapting large language models (llms) to specific downstream tasks and aligning them with human objectives @xcite @xcite @xcite . research has demonstrated that carefully crafted prompts can significantly boost llm performance across various applications, such as facilitating creative writing @xcite , streamlining question-answering processes @xcite , and improving fairness by minimizing bias in content generation @xcite . a notable example is the "let's think step by step" prompt @xcite , which enabled instructiongpt @xcite to achieve an impressive accuracy increase of over 30% on the gsm8k task @xcite . despite these advances, creating effective prompts manually may involve extensive trial and error and demand specialized knowledge. these challenges has steered recent studies towards the development of prompt tuning algorithms, aiming at automating the discovery of effective prompts @xcite . driven by commercial and security concerns, llm owners often restrict access to the models' underlying weights, offering services solely through inference apis @xcite . in such scenarios, llms are perceived as "black boxes" by users. this poses a crucial challenge to prompt tuning because gradient information, which is a cornerstone for standard optimization algorithms, is no longer accessible. black-box tuning (bbt) method @xcite is among the first to perform automatic prompt tuning by only accessing the llm inference api. specifically, bbt adopts a blackbox optimization algorithm termed cma-es (covariance matrix adaptation evolution strategy) @xcite to refine the continuous embedding of prompts, known as "soft prompts". as a population-based algorithm, cma-es samples a considerable group of candidate solutions in each iteration. this process can lead to a significant increase in api calls, thereby incurring substantial time and financial costs. furthermore, despite cma-es's empirical efficacy across diverse applications, its theoretical convergence properties have yet to be justified. these limitations underscore the potential for future research on more efficient and theoretically grounded black-box tuning methods. this paper harnesses the potential of zerothorder optimization methods to enhance black-box prompt tuning. zeroth-order methods stand as the gradient-free analogs to first-order methods like gradient descent and stochastic gradient descent. by approximating gradients through finite differences, these methods necessitate only function value evaluations, circumventing the need for direct gradient access. in this work, we introduce zeroth-order tuning(zot). zot extends the zeroth-order stochastic gradient descent (zo-sgd) framework by integrating gradient clipping @xcite and momentum techniques @xcite to improve the algorithm performance. to counteract potential diminishment in momentum at the initial stage, we apply a bias correction mechanism. in the experiments, zot achieves over 2x speed-up compared to bbt with comparable or even better performance across various prompt tuning tasks. the success of zeroth-order methods in prompt tuning presents a notable surprise, offering a compelling deviation from established optimization theory. although nesterov's seminal work @xcite theoretically proved that zeroth-order gradient descent can converge, it also highlighted a significant caveat: their theoretical convergence speed is expected to be d times worse than that of standard gradient descent, where d is the dimensionality of the optimization problem. this slowdown effect, characterized by the number of samples evaluated, suggests a seemingly prohibitive inefficiency of zeroth-order methods in high-dimensional problems, including the llm prompt tuning problem. upon revisiting and refining the proof in nesterov and spokoiny (2017), we uncover that the anticipated slowdown of zeroth-order methods can be significantly mitigated if the sum of the eigenvalue of the hessian matrix remains small. this observation leads us to introduce the concept of effective dimension d e , defined by our contributions are summarized as follows: ## problem formulation in this section, we provide the necessary background on prompt tuning and zeroth-order optimization, followed by the introduction of our proposed algorithm, zot. ## discussion in this section, we aim to explain why the zerothorder method is effective in prompt tuning. in particular, we focus on how it can mitigate the curse of dimensionality. ## related work prompt tuning is an effective method for adapting large language models (llms) to downstream tasks and aligning them with human intentions. prompts can be manually designed @xcite @xcite , automatically generated @xcite , or tuned by gradients @xcite @xcite . a popular approach involves tuning a set of embeddings as soft prompts @xcite @xcite @xcite @xcite , leveraging their advantageous optimization properties. recently, a new line of methods has emerged, which discovers soft prompts without accessing model weights. to address the challenges posed by high-dimensional space in black-box optimization, bbt @xcite projects the soft prompt into a lower-dimensional space and optimizes it using a black-box solver like cma-es. however, the convergence speed of bbt is relatively slow. an advanced version, bbtv2 @xcite , optimizes multiple vectors in the middle layers of llms and uses a cma-es solver for each layer, thereby speeding up convergence. nonetheless, bbtv2 requires interaction with the middle layers of the model. there are also some works (diao black-box optimization methods have a longstanding history. most of these methods, however, struggle with the challenges brought by high dimensionality. for instance, it has been shown in various studies that zeroth-order gradient methods have a dimensional-dependent convergence rate @xcite @xcite @xcite . some works like @xcite suggest that without a more specific structure of the problem, the rate is at least proportional to the dimensionality d. @xcite applied zeroth-order methods to fine-tune llms with low memory requirements and demonstrated that the convergence rate of zo-sgd depends on the "local r-effective rank". our work introduces a metric called "effective dimension" and demonstrates that soft-prompt tuning tends to have a small effective dimension. this implies that zeroth-order optimization for soft-prompt tuning can also achieve rapid convergence. ## conclusion in this study, we have introduced zeroth-order tuning (zot), a black-box optimization method for efficiently tuning the llm prompts. zot is designed to operate without direct gradient access, facilitating prompt tuning through model inference apis alone. our experimental analyses across diverse models and datasets have demonstrated that zot not only improves accuracy by an average of 3.23% but also doubles the convergence speed compared to existing black-box tuning methods. such performance is unexpected given the conventional theories which suggest that the efficiency of zeroth-order methods may be significantly hampered by the curse of dimensionality. through a refinement of classical proofs, we have identified that the presence of a low effective dimension can substantially alleviate the anticipated slow convergence rates of zeroth-order methods. further empirical investigation validates the connection between the low effective dimension of prompt spaces and the unexpectedly fast convergence of zeroth-order methods in prompt tuning.