LLM as a Complementary Optimizer to Gradient Descent: A Case Study in Prompt Tuning

## Abstract

Abstract Learning a skill generally relies on both practical experience by doer and insightful high-level guidance by instructor. Will this strategy also work well for solving complex non-convex optimization problems? Here, a common gradient-based optimizer acts like a disciplined doer, making locally optimal update at each step. Recent methods utilize large language models (LLMs) to optimize solutions for concrete problems by inferring from natural language instructions, akin to a high-level instructor.
In this paper, we show that these two optimizers are complementary to each other, suggesting a collaborative optimization approach.
The gradient-based optimizer and LLM-based optimizer are combined in an interleaved manner.
We instruct LLMs using task descriptions and timely optimization trajectories recorded during gradient-based optimization. Inferred results from LLMs are used as restarting points for the next stage of gradient optimization.
By leveraging both the locally rigorous gradient-based optimizer and the high-level deductive LLM-based optimizer, our combined optimization method consistently yields improvements over competitive baseline prompt tuning methods.
Our results demonstrate the synergistic effect of conventional gradient-based optimization and the inference ability of LLMs. The code is released at https://github.com/guozix/LLM-catalyst .

## 1 Introduction

Recent developments of Large Language Models (LLMs) have demonstrated an unprecedented ability to comprehend and generate human-like text, leading to significant breakthroughs in natural language processing Touvron et al. (); Chowdhery et al. ().
This has led to their adoption in various advanced open-ended applications, where they are being instructed to participate in dialogue (OpenAI et al., ), formulate and execute plans (Gupta and Kembhavi, ; Gao et al., ), solve mathematical problems (Yang et al., ), etc., rather than just performing rigid natural language understanding tasks (Wang et al., ) like previous language models (Radford et al., ; Devlin et al., ).
The robust capability of LLMs in natural language comprehension and the generation of more nuanced and contextually relevant text provides a foundation for solving complex optimization problems using LLMs.

Humans acquire skills through practical experience and external guidance from instructors. Similarly, solving optimization problems relies on well-designed algorithms incorporating prior knowledge, as well as meticulous procedural implementation.
We regard common gradient-based optimizer as disciplined doer. These optimizers are effective in navigating the parameter space through precise, incremental adjustments based on gradient information. However, their local perspective often limits their ability to escape local optima and discover more optimal solutions.
LLMs can be used as an high-level instructor, being capable of providing useful guidance for optimization, based on the abundant internal knowledge acquired through massive pre-training,
Recent studies have proposed to utilize LLMs as strategy planner or optimizer on concrete optimization tasks. For example, Eureka (Ma et al., ) trains agents by reinforcement reward function designed by GPT-4, which can learn various complex skills such as dexterous pen spinning. It shows that LLM can guide the trend of optimized policy on a delicate level.

Employing LLMs for optimization offers
unique advantages. The optimization is conducted with natural language interactions, which contributes to two charming properties. First, the implementation of the optimization is code-free. All the steps in the process use dialog-like interactions with LLMs. Secondly, LLMs generate instruction-related outputs by assembling task-related semantic tokens which is hardly constrained by the local optima issue, which is probably encountered by gradient-based optimization.
On the other hand, LLM returned solutions, generated by simply query and response interactions, may not be as precise as the results optimized by rigorous step-by-step gradient descent, especially under limited API calling budgets.
The local carefulness of gradient-based optimizer and diverse semantic exploration of LLM-based optimizer are complementary to each other, suggesting a collaborative optimization approach.

With this motivation, we propose a combined optimization method that adopts LLMs as an optimizer (MaaO) as a catalyst for the conventional gradient-based optimization. Our proposed optimization approach leverages both the locally rigorous gradient-based optimizer in parameter space and high-level deductive LLM-based optimizer in unconstrained vocabulary space for better performance.
To achieve a collaborative training based on the two optimizers, we interleave the conventional training process of gradient-based optimization with interactions with LLM. We first optimize the parameters for only dozens of iterations by gradient optimizer. Then the optimized parameters in the intermediate step, along with their loss and accuracy on the training set, are provided as history trajectory clues for LLM to infer new candidates that are potentially more effective, and, after grabbing the response from LLM, we use the generated results as restarting points of the parameters for subsequent gradient-based optimization iterations.
The two optimizers are operated alternately to optimize the parameter collaboratively. The final optimized results are obtained by the gradient optimizer with a stable convergence. Our proposed optimizing strategy only injects several API calls to LLM to the conventional gradient-based training workflow. We instantiate the target problem as prompt optimization and validate that our proposed combined optimizing method leads to consistent improvements.

In summary, our contributions include:

- •
We analyze the limitations of gradient-based optimization, especially the entrapment in local optima, and attribute the issues to the limitation of gradient-based optimizer in the short-sighted local perspective of the parameter space.
- •
We propose a novel optimization approach that combines the deductive LLM-based optimizer in unconstrained vocabulary space with the disciplined gradient-based optimizer in the parameter space for better optimization performance.
- •
We test the effectiveness of the proposed combined optimization method on prompt tuning tasks, and it achieves consistent improvements over existing prompt tuning methods, validating the complementary effect of LLM-based and gradient-based optimizers.

## 2 Related Work

### 2.1 LLMs and Optimization Problems

LLM’s superior capabilities in grasping intricate linguistic structures and accurate language generation enable it to handle complex optimization problems. Existing works have validated the effectiveness of LLM for solving small-scale mathematical optimization problems (Yang et al., ), optimizing prompts (Zhou et al., ; Pryzant et al., ; Guo et al., ; Liu et al., ; Fernando et al., ; Diao et al., ), searching for network architectures (Chen et al., ; Zheng et al., ), hyperparameter optimization (Chen et al., ) and discovering physical equations (Du et al., ).

For prompt optimization,
APE (Zhou et al., ) proposes a general framework that searches for prompts in the vocabulary space by instructing large language models with task information to obtain better solutions iteratively from the responses of LLMs by analyzing previously found candidates. Based on this framework, APO (Pryzant et al., ) proposes that editing prompts by LLM is analogous to conducting gradient descent in the natural language domain. They imitate the gradient-based learning by providing the failure cases to LLM for a semantic "gradient" and updating the prompt in an opposite semantic direction. EVOPROMPT (Guo et al., ) also connects LLM-based optimization to traditional algorithms for better explainability. They integrate LLM into the workflow of evolutionary algorithms by instructing LLM to act like evolutionary operators to generate new candidate prompts. The insight that LLM naturally enables an intelligent variation operator is also revealed in LMC (Meyerson et al., ) and ELM (Lehman et al., ) on image and code generation tasks.
BBO(Liu et al., ) searches prompts for vision-language model by merely conversing with LLM following designed strategies and achieves comparable results to white-box gradient-based prompt tuning. However, the performance superiority only holds in one-shot setting. LLM can not effectively optimize to gain more improvements based on more training data.

The results achieved in these approaches demonstrate that LLMs have the potential to be applied as a general-purpose optimizer to more tasks. Some of the works explored the connection between LLM-based inference and existing optimization algorithms (Pryzant et al., ; Guo et al., ). However, the proposed optimization workflow is still largely based on the inherent ability of LLM. It is still hard for LLM to make decisions as precise as deterministic optimization algorithms, e.g., gradient-based optimizer. And the API calling budget bounded by the high cost of operating super large-scale models also limits the performance of LLM-based optimization.

### 2.2 Prompt Tuning for Pre-trained Models

Prompt tuning has emerged as a standard approach for the parameter-efficient adaptation of pre-trained models, aimed at improving their performance in various natural language processing Lester et al. (); Li and Liang () and vision-language Zhou et al. (, ); Yao et al. () tasks.
Prompt-based tuning of pre-trained models appends learnable embeddings to the original sequence of the data for the input layer or intermediate layer. Fine-tuning the lightweight parameters in the prompt yields comparable performance even to full parameter fine-tuning and transferability (Vu et al., ; Su et al., ) on various tasks (Lester et al., ; Li and Liang, ; Liu et al., ).
Despite its widespread adoption, the conventional prompt tuning technique encounters challenges related to slow convergence and suboptimal optimization Ding et al. (), which undermines the effectiveness of prompt tuning in a wider and larger scale of pre-trained models and downstream tasks. We attribute these issues to the complexity of the input embedding space of the pre-trained model, making it challenging to optimize the prompt effectively based on back-propagated gradients in this space.

## 3 Method

Figure: Figure 1: Overview of our proposed method. The bold arrows with different color show the two collaborative optimizers of in our method. The thin arrows show the workflow of MaaO which infer for promising candidate prompt in vocabulary space for gradient-based optimizer.
Refer to caption: x1.png

In this section, we introduce our proposed combined optimization approach that leverages both the local carefulness of gradient-based optimizer and the flexible semantics exploration of LLM-based optimizer. The overview of our method is shown in Figure 1.
To elaborate on our proposed method, we instantiate the problem in a prompt tuning scenario. We will describe the general formulation of prompt tuning/optimization and the way of gradient-based prompt tuning in Section 3.1.
Next, we analyze the issues that occur in the conventional gradient-based prompt tuning process in Section 3.2, and attribute the problem to the characteristics of gradient-based optimizer that is limited to the local view of the parameter space.
Finally we introduce our proposed optimization method that adopts LLM as a catalyst for gradient-based prompt tuning in Section 3.3.

### 3.1 General Formulation of Prompt Tuning

In this part, we instantiate the task by prompt tuning for discriminative tasks, i.e., classification.
In a general situation, we consider a pre-trained multi-modal model $\mathcal{E}$. Recognizing the classes of input images $I$ or texts $T$ can be achieved by classifying the representations $\mathcal{E}\left(I,T\right)$, encoded by the pre-trained model. We denote the task-specific classifier as $\mathcal{F}\left(\cdot\right)$. The prediction can be obtained by $p\left(\hat{y}|I,T\right)=\mathcal{F}\left(\mathcal{E}\left(I,T\right)\right)$.

To better adapt pre-trained models to various downstream tasks, prompt tuning introduces learnable prompt tokens and formulates a task-specific input for the pre-trained model. The learnable prompt tokens can be either continuous vectors (Zhou et al., ; Lester et al., ) in the textual embedding space of the pre-trained model or discrete tokens (Diao et al., ; Deng et al., ) sampled from the vocabulary. The prompt $P$ parameterized by $\bm{\theta}$ is concatenated with the original input making up a task-specific input. The adapted output can be formulated as $p\left(\hat{y}|I,T;\bm{\theta}\right)=\mathcal{F}\left(\mathcal{E}\left(P_{\bm
{\theta}},I,T\right)\right)$. In common practice, the prompt tokens are learned through labeled few-shot samples from target task datasets. The parameters of the prompt are optimized by minimizing the loss function:

$$ $\begin{split}\bm{\theta}^{*}=\mathop{\arg\min}_{\bm{\theta}}\mathcal{L}(y,I,T, \bm{\theta})=\mathop{\arg\min}_{\bm{\theta}}-\log p(\hat{y}=y|I,T;\bm{\theta}) .\end{split}$ (1) $$

According to this formulation, it is straightforward to use a standard gradient-based optimizer to learn the parameters as is done in conventional prompt tuning methods:

$$ $\bm{\theta}_{t+1}=\bm{\theta}_{t}-\eta_{t}\nabla_{\bm{\theta}}\mathcal{L}(y,I, T,\bm{\theta}).$ (2) $$

### 3.2 Analysis on Issues of Gradient-Based Prompt Tuning

Figure: Figure 2: The result of gradient-based prompt optimization with different prompt initialization. The shadow denotes the standard deviation of the accuracy over three random seeds.
Refer to caption: extracted/5647675/figures/figure2.png

Although prompt tuning has become one of the most widely adopted parameter-efficient fine-tuning methods for the adaptation of pre-trained models. The optimization of the prompt still encounters challenges.
The prompts converges much slower than other parameters efficient fine-tuning methods, e.g., adapter tuning or even full parameter fine-tuning (Ding et al., ), based on the estimated gradients back-propagated through the entire pre-trained model.
Another main issue of prompt tuning is that the effectiveness of the learned prompt is sensitive to its initialization values, suggesting that the optimization of the prompt may easily entrapped in local optima due to the complexity of the embedding space of the pre-trained model. Unfortunately, it is challenging to carefully craft initial prompts for every downstream task. To address this issue, Gu et al. () propose to seek a satisfying initialization point for the prompt. However, their method needs to inject soft prompts into the pre-training stage, which limits its application to scenarios where pre-training resource is limited.

To demonstrate the issues more specifically, we analyze some empirical results of gradient-based prompt optimization performed on the one-shot training set of EuroSAT (Helber et al., ). We fix the training set for all experiments to eliminate the variance caused by data sampling. We run CoOp (Zhou et al., ) under three random initializations and show the results as indicated by "Random Initialization" in Figure 2. It can be seen that even if we fix the training samples, different random initialization value of the prompt can still bring considerable standard deviation in the results of final learned prompts, indicating a large performance gap (up to 9 percent of accuracy) between different seeds.
If we manually initialize the prompt as a prompt template "a photo of a", which is used in Radford et al. (), the final variance gets smaller but the absolute performance shows a slight decline.
Prior knowledge contained in manual prompts brings merits, providing better results at the starting phase of the training, but lacks proper flexibility for enhancement of final learned prompts.
Our method adds marginal steps of optimization based on the collaboration of gradient-based optimizer and MaaO at the start of the training workflow, which results in both lower standard deviation and better absolute performance.

The high sensitivity of prompt tuning results according to different initialization values indicate the complexity of the input embedding space, where gradient-based optimizer only leads to suboptimal converged parameters based on gradient information in a short-sighted local perspective,
hardly taking the semantics of the prompt and the overall task information into account. To mitigate the limitations of gradient-based optimizer, we leverage LLM as an unconstrained vocabulary space prompt optimizer based on textual semantic information of the task and previously found prompts.

Figure: Figure 3: The instruction used to query GPT-3.5 and GPT-4.0 in an iteration of optimizing the prompt using LLM.

Figure: Algorithm 1 Combined Optimization Algorithm

### 3.3 Catalyzing Prompt Tuning by Using LLM as a Prompt Optimizer

We propose to harness LLM as an optimizer (MaaO) to mitigate the issues of gradient-based prompt tuning.
We leverage the unconstrained inductive ability of LLM in vocabulary space based on high-level semantic information of the prompt to complement the gradient-based optimizer.

Our method optimizes the prompt by using the gradient optimizer and MaaO in an alternating pattern. Specifically, we first update the parameter of the prompt for minor steps of gradient-descent optimization and record the intermediate learned prompts and corresponding fitness scores, which are evaluated on the few-shot training samples. Then, we construct instruction for LLM with the intermediate learned prompts as optimizing trajectory information. Taking the instruction as input, LLM generates more promising candidate prompts for the target model. Next, we reinitialize the parameter of the prompts with LLM-generated prompts and restart the gradient-based training process for the next round. After operating the above two optimizers alternately for few rounds, we finally train the prompt to convergence using the gradient-based optimizer.
In the following, we will describe the components of MaaO and show the combination of it with the gradient-based optimizer for a collaborative prompt optimization.

Instruction construction.
The gradient optimizer calculates updates based on the current parameters and objective function. Information of the current state of optimization should also be properly provided for LLM to infer from. We collect the intermediate optimized prompt in the training trajectory of the gradient-based optimizer and evaluate the performance corresponding to each intermediate prompt as a fitness score, indicating how good or bad the prompt performs. Considering that the accuracy may be not precise enough on few samples, we employ loss as the indicator value. LLM is instructed to generate prompts that potentially achieve better performance based on observed patterns in top-performing candidates.

We also briefly define the role of LLM and explain the goal of optimization in natural language, encouraging LLM to assemble task-related tokens when constructing the prompt. Additional instructions to constrain the length and number of the generated prompts are included for programmed processing.
Figure 3 shows the instruction used in each optimization iteration of prompt using GPT-3.5 and GPT-4.

Token space projection.
Gradient-based prompt tuning typically optimizes soft prompt tokens in the embedding space of the pre-trained model. However, it is not feasible to directly provide the soft embedding vectors as input to the LLM, which is proficient in responding to natural language with semantics. To convert the soft prompt embedding to discrete words, we employ a reverse process of word2vec (Mikolov et al., ) to project the embedding to the matched vocabulary.

Given a pre-trained target model with token embedding layer $\mathcal{V\left(\cdot\right)}$, textual inputs $\{t_{i}\}_{i=1}^{l}$ to the model are first converted to vector sequence as $\{\bm{t}_{i}\}_{i=1}^{l}=\{\mathcal{V}(t_{i})|i\in[1,l]\}$, before input into the model. Gradient-based prompt tuning optimizes in the continuous vector space for best prompt embeddings. We project the continuous prompt vector $\bm{\hat{t}}_{i}$ to nearest discrete tokens by $\hat{t_{i}}=\mathcal{V}^{-1}(\bm{\hat{t}}_{i})$, where $\mathcal{V}^{-1}$ is defined as:

$$ $\mathcal{V}^{-1}(\bm{\hat{t}}):=\mathop{\arg\min}_{\hat{t}\in\mathcal{S}}\ \ \|\mathcal{V}(\hat{t})-\bm{\hat{t}}\|_{2}.$ (3) $$

$\mathcal{S}$ denotes the dictionary of the pre-trained model.
The projected prompt is used to construct the instruction for LLM to infer for better prompt candidates in the unconstrained semantic vocabulary space.

Integration with gradient-based optimizer.
Gradient-based optimizer conduct rigorous local-optimal update on the parameter based by back-propagated gradient. MaaO infers for promising candidate prompts by analyzing and generating semantic-related prompts based on currently found solutions. We propose a cooperation workflow of the gradient-based optimizer and MaaO in Algorithm 1.

We connect the two optimizers in two ways. First, the gradient optimizer provides the LLM with the intermediate results in the prompt optimization process, from which LLMs infer for more promising candidate prompts. The generated prompts by LLMs assemble task-related semantic contents and provide opportunities to break free from local optimal that may encountered in gradient-based optimization.
Second, we restart the gradient-based optimization by using the prompts generated by the LLM optimizer as new initial values of the gradient optimizer to obtain refined prompts based on the LLM-generated ones.
By optimizing the prompt based on the two optimizers alternately, it guides the LLM to progressively exploit better prompts in a more promising area of the search space near the previously found good solutions. The gradient optimizer provides stable convergence for the final learned prompts.
Note that the overhead brought by our optimization algorithm compared to the original gradient-based prompt tuning is only about dozens (at most 30) of iterations using combined optimizer.

Figure: Figure 4: Interpretation of prompts optimized by LLM on EuroSAT dataset.
Refer to caption: x2.png

**Table 1: Few-shot prompt optimization results on downstream datasets.**
| Datasets | Settings | ResNet50 | ViT-B/16 |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| CoOp | BBO | Ours(GPT-3.5) | Ours(GPT-4) | Ours(Llama7B) | TCP | Ours(GPT-3.5) |  |  |
| Eurosat | 1-shot | 50.58 | 49.0 | 56.27 | 56.74 | 55.38 | 65.04 | 63.06 |
| 4-shot | 69.65 | - | 71.17 | 72.55 | 73.39 | 72.42 | 77.35 |  |
| 8-shot | 72.74 | - | 74.33 | 75.99 | 76.79 | 77.71 | 79.49 |  |
| 16-shot | 83.57 | 51.4 | 83.77 | 85.07 | 83.95 | 84.43 | 86.18 |  |
| Avg. | 69.14 |  | 71.39 | 72.59 | 72.38 | 74.90 | 76.52 |  |
| DTD | 1-shot | 43.13 | 44.8 | 47.24 | 44.78 | 42.47 | 55.06 | 55.14 |
| 4-shot | 53.45 | - | 54.87 | 55.04 | 54.14 | 61.88 | 63.36 |  |
| 8-shot | 59.38 | - | 60.30 | 60.18 | 60.48 | 68.62 | 68.56 |  |
| 16-shot | 63.87 | 44.9 | 64.40 | 64.30 | 64.48 | 73.48 | 73.66 |  |
| Avg. | 54.96 | - | 56.70 | 56.08 | 55.39 | 64.76 | 65.18 |  |
| Caltech101 | 1-shot | 87.76 | 89.1 | 87.02 | 86.87 | 87.86 | 94.08 | 94.00 |
| 4-shot | 89.05 | - | 88.72 | 88.68 | 89.03 | 95.18 | 95.38 |  |
| 8-shot | 90.58 | - | 90.26 | 90.66 | 90.25 | 95.39 | 95.33 |  |
| 16-shot | 91.66 | 89.5 | 92.28 | 91.83 | 92.33 | 95.89 | 95.71 |  |
| Avg. | 89.76 | - | 89.57 | 89.51 | 89.87 | 95.14 | 95.11 |  |
| Oxford_Flowers | 1-shot | 69.09 | 67.2 | 71.62 | 71.28 | 72.31 | 85.80 | 87.05 |
| 4-shot | 87.00 | - | 89.38 | 88.51 | 88.93 | 94.72 | 95.09 |  |
| 8-shot | 90.19 | - | 91.15 | 90.77 | 90.41 | 96.14 | 96.31 |  |
| 16-shot | 93.88 | 67.4 | 94.42 | 94.02 | 94.49 | 97.47 | 97.54 |  |
| Avg. | 85.04 | - | 86.64 | 86.15 | 86.54 | 93.53 | 94.00 |  |
| Fgvc_Aircraft | 1-shot | 18.38 | 18.1 | 18.69 | 18.82 | 18.50 | 28.90 | 28.33 |
| 4-shot | 21.90 | - | 22.73 | 22.77 | 23.19 | 35.61 | 35.61 |  |
| 8-shot | 25.15 | - | 26.53 | 26.42 | 27.35 | 39.76 | 40.69 |  |
| 16-shot | 28.86 | 18.1 | 31.27 | 31.24 | 31.44 | 43.29 | 43.79 |  |
| Avg. | 23.57 | - | 24.81 | 24.81 | 25.12 | 36.89 | 37.11 |  |
| Food101 | 1-shot | 72.60 | 78.3 | 73.86 | 73.98 | 72.47 | 85.74 | 85.40 |
| 4-shot | 70.93 | - | 70.44 | 70.25 | 69.76 | 86.43 | 86.01 |  |
| 8-shot | 73.97 | - | 73.12 | 73.97 | 72.51 | 86.83 | 86.67 |  |
| 16-shot | 75.72 | 78.3 | 75.20 | 74.94 | 73.85 | 87.25 | 87.26 |  |
| Avg. | 73.31 | - | 73.16 | 73.29 | 72.15 | 86.56 | 86.34 |  |
| Stanford_Cars | 1-shot | 55.70 | 56.2 | 54.74 | 54.89 | 54.78 | 68.87 | 68.05 |
| 4-shot | 61.22 | - | 61.93 | 61.76 | 62.01 | 75.25 | 76.17 |  |
| 8-shot | 65.14 | - | 65.89 | 66.82 | 67.37 | 79.27 | 79.29 |  |
| 16-shot | 67.97 | 56.8 | 68.84 | 69.34 | 73.30 | 83.79 | 83.98 |  |
| Avg. | 62.51 | - | 62.85 | 63.20 | 64.37 | 76.80 | 76.87 |  |
| Oxford_Pets | 1-shot | 85.14 | 88.1 | 85.70 | 84.38 | 84.78 | 91.26 | 90.75 |
| 4-shot | 85.37 | - | 85.03 | 85.33 | 84.47 | 92.67 | 92.65 |  |
| 8-shot | 85.70 | - | 84.65 | 84.82 | 84.58 | 92.91 | 92.55 |  |
| 16-shot | 86.84 | 88.3 | 86.37 | 86.00 | 85.02 | 93.34 | 93.19 |  |
| Avg. | 85.76 | - | 85.44 | 85.13 | 84.71 | 92.55 | 92.29 |  |
| UCF101 | 1-shot | 62.60 | 60.2 | 61.85 | 61.07 | 62.34 | 73.44 | 72.69 |
| 4-shot | 68.75 | - | 68.25 | 69.18 | 68.27 | 80.93 | 80.77 |  |
| 8-shot | 72.26 | - | 72.69 | 72.26 | 72.58 | 83.18 | 83.40 |  |
| 16-shot | 74.91 | 60.5 | 74.82 | 75.96 | 74.95 | 85.25 | 85.13 |  |
| Avg. | 69.63 | - | 69.40 | 69.62 | 69.54 | 80.70 | 80.50 |  |
| SUN397 | 1-shot | 58.33 | 61.0 | 58.13 | 57.25 | 57.47 | 69.20 | 69.13 |
| 4-shot | 64.48 | - | 65.21 | 64.06 | 64.40 | 73.78 | 73.94 |  |
| 8-shot | 66.79 | - | 67.20 | 66.90 | 66.79 | 75.78 | 75.99 |  |
| 16-shot | 68.79 | 60.8 | 68.39 | 68.42 | 68.42 | 76.81 | 76.69 |  |
| Avg. | 64.60 | - | 64.73 | 64.16 | 64.27 | 73.89 | 73.94 |  |

## 4 Experiments

### 4.1 Experimental Setup

Implementation details and baselines.
To comprehensively evaluate the effectiveness of our method, we use GPT-3.5, GPT-4 (OpenAI et al., ), and white-box LLM Llama2 (Touvron et al., ) as the LLM-based optimizer.
We integrate MaaO into existing prompt tuning methods for language pre-trained models, P-tuning (Liu et al., ),  Lester et al. (), and two methods for vision-language model, CoOp (Zhou et al., ), TCP (Yao et al., ). CoOp pioneered prompt tuning for vision-language models, and TCP is one of the recent state-of-the-art prompt tuning approaches. Both of the methods are typical textual prompting methods for vision-language models.
For a fair comparison, we fix the original hyperparameter of previous methods, such as pre-trained backbone and prompt module design, and only apply our method as new optimization strategy. For the configuration of Algorithm 1, the number of rounds $N$ is set as 3 and the iteration for the gradient optimizer $m$ is set as 10. All experimental results are averaged over 3 random seeds. The experiments are conducted on a V100 GPU. Detailed hyperparameter setting is provided in the Appendix.

Datasets.
For lauguage model, we conduct experiments over commonly-used pre-trained model RoBERTa (Liu et al., ) on NLU tasks from SuperGLUE (Wang et al., ) to test our methods.
We apply our prompt optimization algorithm to vision-language pretrained CLIP (Radford et al., ) for adaptation of image classification tasks.
We adopt commonly used 10 datasets to comprehensively evaluate our method, including Caltech101 (Li et al., ), OxfordPets (Parkhi et al., ), StanfordCars (Krause et al., ), Flowers102 (Nilsback and Zisserman, ), Food101 (Bossard et al., ), FGVCAircraft (Maji et al., ), SUN397 (Xiao et al., ), UCF101 (Soomro et al., ), DTD (Cimpoi et al., ), and EuroSAT (Helber et al., ).
For each dataset, labeled few-shot samples from each class are used as training data.

### 4.2 Main Results

Experiments on vision-language pre-trained models.
We compare the results of employing our proposed optimization method for existing prompting methods (Zhou et al., ; Yao et al., ). From Table 1, the results on "RN50" backbone show that our integrated optimization outperforms existing gradient-based prompt tuning methods at seven out of ten benchmark datasets and the other tasks remain close to the baseline performance. Both black-box GPT and open-sourced Llama2 achieve consistent improvements, demonstrating the effectiveness of our combined optimization framework. TCP (Yao et al., ) is one of the state-of-the-art prompt tuning approaches with a stronger backbone. Although the absolute improvement inevitably decreases, our method still brings stable improvements on six out of ten datasets.

We also compare with methods that optimize by LLM only, e.g., BBO (Liu et al., ). We list the results reported in BBO paper since the code has not been released yet and our reproduced results can not match the results published in the paper.
Although BBO achieves a completely program-free prompt learning method for CLIP, their performances in 16-shot setting are poor. Their method largely relies on the inherent deductive ability of LLM, which can not make good use of information in more training samples. Our method instruct LLMs with intermediate results of gradient optimizer, enabling LLMs to exploit in a more promising sub-region of the semantic space. The prompts generated by LLM are further refined by the disciplined gradient-based optimizer to achieve stable improvements.

Experiments on language models. We also test our method on pre-trained language models and NLU tasks. From Table 3, our method with GPT-4 as optimizer surpasses P-tuning (Liu et al., ) and  Lester et al. () on four out of five tasks from SuperGLUE, showing the superiority of our optimization method over vanilla gradient-based prompt tuning.

In summary, the results indicate that our proposed combined optimization approach, which leverages both the local precision of a gradient-based optimizer and the flexible semantics exploration of an LLM-based optimizer, is better than both single methods and outperforms each method individually.

**Table 2: Results on SuperGLUE dev-set. (PT: P-tuning & Lester et al. (); Model: RoBERTa-Large).**
| Methods | COPA | BoolQ | RTE | WiC | WSC |
| --- | --- | --- | --- | --- | --- |
| PT | 61.67 | 62.29 | 55.72 | 53.81 | 64.10 |
| Ours | 68.67 | 63.09 | 58.00 | 55.85 | 63.46 |

Interpretation of prompts optimized by LLM. To further analyze the contribution of LLM-based optimizer in prompt optimization, we list the prompts contained in the instruction and generated by LLM in Figure 4.
In round 1, the gradient-based optimizer tend to navigate around senseless prompt tokens, e.g., "beh", "ila", etc. This phenomenon is alleviated after leveraging LLM to infer for more meaningful prompts. In round 3, prompts with both interpretability and low loss values are obtained by the collaboration of gradient-based optimizer and LLM.

### 4.3 Ablation Study

Our method’s sensitivity to the choice of LLMs, prompt tuning baseline methods and amount of training samples are already shown in Table 1. We provide ablation results of three factors of our method in this section. The ablation experiments are based on CoOp baseline, using GPT-3.5 as optimizer. More ablation studies can be found in the Appendix.

Design of instruction.
The instruction from which LLMs infer for new candidates is influential on the results. We empirically analyze the effect of each component in our instructions in Table 3. Task definition (TD) denotes raw instruction defining the task information. Manual prompt (MP) means LLMs are instructed with hand-crafted prompt template. Optimization trajectory (OT) denotes the intermediate results from the gradient optimizer is provided.
The results in first line of Table 3 correspond to no LLM-based optimization, serving as a stronger baseline than CoOp. Random noise is added to perturb the prompts after each round of gradient-based optimization for the opportunity to escape from local optima.
The ablation results show that hand-crafted template, providing prior knowledge of the prompt, and optimization trajectory, providing timely semantic landscape of current optimized prompts, are both important components for ideal performance.

**Table 4: Ablation on the rounds of alternating optimization.**
| $N$ | EuroSAT | DTD | Oxford_Flowers |
| --- | --- | --- | --- |
| 1 | 72.51 | 56.33 | 84.45 |
| 2 | 71.69 | 56.13 | 84.82 |
| 3 | 71.39 | 56.70 | 86.64 |
| 4 | 71.50 | 56.41 | 86.89 |

Rounds of alternating optimization.
We analyze the effect of the alternating rounds $N$ of the two optimizer on the result. Table 5 indicate that the optimal round for each task varies. But more rounds involve more interactions with LLM, providing more candidates prompts. The average performance improves with more rounds generally. We choose 3 rounds as a proper value.

Iterations of gradient optimizer.
We analyze the effect of the training iterations $m$ of gradient optimizer in every round. From Table 5, we can see that increasing training iterations leads to descending results. A longer training process by gradient-based optimizer may not necessarily benefit the final prompt tuning results. We find that more iterations of gradient-based optimization may results in candidate prompts with less semantic diversity, which is not good for proposing LLM to generate more promising candidate prompts. Thus, we use a small training iteration for better performance and efficiency of our optimization method.

## 5 Conclusion

In this paper, we proposed a combined optimization method that integrates LLM-based optimizer with conventional gradient-based optimization. Our method mitigates the inherent limitations of gradient-based optimization, such as entrapment in local optima, by leveraging the inductive reasoning capabilities of LLMs.
By interleaving gradient-based optimization process with natural language interactions with LLMs, we introduced a higher-level guidance for optimization that effectively utilizes task descriptions and real-time optimization trajectories.
We validated our combined optimization strategy through prompt tuning tasks, where the synergy between LLM-based optimizer and gradient-based optimizer has consistently demonstrated improved performance over competitive baselines. These results underscore the complementary effect of LLM-based optimizer and conventional gradient-based optimization.
Our contributions inspire further exploration of the advantages of LLM-based optimization over existing algorithms, paving the way for more effective integration of LLM-based inference into conventional optimization workflows.

Limitations. Our proposed method can not be effectively employed for adapter-based fine-tuning methods. Feasible solution of expressing optimization status of adapter module to LLMs needs further design. We leave the application of the proposed method to more wider range of optimization problems (e.g., adapters, LoRA) and algorithms (e.g., reinforce learning) as future work.

## Appendix A Appendix

### A.1 More Experimental Details

Instructions used to query LLMs. The instruction used to query GPT-3.5 and GPT-4 has been shown in Figure 3 of the main text. The instruction for Llama2-7B-chat is provided in Figure 5.

The design of instruction for Llama2-7B is different from GPT-3.5 and GPT-4, since we notice that the instruction following ability of Llama2-7B is weaker. It is more likely to produce unexpected output. Even though we emphasized desired way of responding to our query, the responses from Llama2-7B still need proper post-processing to obtain the clean returned prompts.

Figure: Figure 5: The instruction used to query Llama2-7B-chat in an iteration of optimizing the prompt using LLM.

Detailed hyperparameter settings.
The backbone models used by CoOp and TCP are ResNet50 and ViT-B/16 respectively. The prompt length is set as 4 for both CoOp and TCP. The training hyperparameters, such as epochs and learning rate, are remained the same as the original methods. The number of training iterations $M$ for Algorithm 1 is equal to the training iterations of the original methods. We set the number of rounds $N$ as 3 and the iteration for the gradient optimizer $m$ is set as 10 for CoOp, 30 for TCP. The prompt length for NLU tasks is set as 8.

### A.2 More Ablation Study

Distance function used for token space projection.
The token space projection operator in Eqn. 3 uses L2 distance to find the nearest discrete tokens for continuous prompt embeddings. We also tried to using cosine similarity as distance function. The results are provided in Table 6

**Table 6: Ablation on distance function used for token space projection.**
| Distance Function | EuroSAT | DTD | Oxford_Flowers |
| --- | --- | --- | --- |
| L2 | 71.39 | 56.70 | 86.64 |
| Cosine | 71.36 | 56.19 | 87.09 |

Length of the prompt. We use a default prompt length 4 for our experiments. We provide the result of our method with longer prompt in Table 7.

**Table 7: Ablation on the length of the prompt.**
| Prompt Length | EuroSAT | DTD | Oxford_Flowers |
| --- | --- | --- | --- |
| 4 | 71.39 | 56.70 | 86.64 |
| 8 | 70.52 | 56.38 | 86.90 |

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 5
presentation: 3
questions: 1.	One potential baseline could be using random initialization to restart the gradient based optimization method. Have the authors considered that?

2.	Why are some cells in Table 2 for Liu et al. (2023a) missing?


3.	What is "$M$" in the algorithm 1?
soundness: 3
strengths: 1.	The proposed method is a hybrid method that combines the strengths of local gradient-based optimization and global LLM-based guidance.

2.	The experiments conducted in the paper are comprehensive.
summary: This paper introduces a collaborative optimization framework that combines gradient descent with LLMs to further enhance prompt tuning. In this method, gradient-based optimizer performs local updates while the LLM provides a new restarting point to help escape local optima. Experiments are conducted on language tasks and vision-language tasks.
weaknesses: 1.	Based on the experiment results in both language and vision-language tasks, the improvement of the proposed method is mostly incremental, admittedly with a few cases where the improvement from the proposed method is significant. Additionally, as shown in Table 2, whether the proposed method is better than the baseline CoOp seems to depend on what LLM models are used too. 

2.	To better gauge the significance of the improvements, it would be beneficial for the authors to report standard deviations, especially given that some performance gains are as small as 0.07. This would provide a clearer picture of the method's reliability and consistency.

3.	Beyond accuracy metrics, I recommend that the authors also compare the running time and memory usage between the proposed method and baseline methods. This additional analysis would give valuable insights into the efficiency and practicality of the approach in real-world applications.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: 1. The paper lacks a clear trend in performance improvement with additional optimization rounds.

2. The paper tries to use LLM planner to provide diverse semantic exploration of prompts, how could the author measure the diversity of the prompts generated prompts by the LLM planner?

3. In lines 479-480, there are incomplete sentences that may affect clarity.
soundness: 3
strengths: 1. The paper introduces a novel combination of gradient-based methods and LLM-based planner. This approach is both creative and promising, as it leverages the complementary strengths of gradient-based optimization for local search and LLMs for strategic guidance.

2. The authors perform a comprehensive set of experiments to demonstrate the effectiveness and efficiency of their method. The breadth of experimentation, covering both text model and vision-language model prompt tuning, demonstrate the approach’s versatility and potential applicability across various domains.
summary: This paper presents an innovative approach to non-convex optimization by combining gradient-based methods with large language models (LLMs) to mimic a mentor-doer relationship. The gradient-based optimizer makes locally optimal search, while the LLM suggest possible improved starting points based on instructions that include the gradient-based optimizer's search history. The authors apply this approach to prompt tuning for both text models and vision-language models.
weaknesses: The main limitation of this approach is the unpredictable nature of the LLM-based planner. 
1. Based on results in Table 5, additional rounds of optimization do not always yield better outcomes, and N is too small to observe a clear performance trend in the optimization performance. 
2. Table 2  shows that smaller models like LLaMA-7B sometimes outperform larger models such as GPT-3.5 and even GPT-4. This suggests that the observed performance gains may not stem from any advanced reasoning ability inherent to the LLMs, but rather from task-specific nuances. 
3. Table 6 results show that increasing training iterations of the gradient optimizer leads to worse results, which suggests that the gradient-based optimizer and LLM planner may not be fully compatible, potentially causing interference rather than collaborative improvement.    

Overall, I personally believe the paper may overstate the readiness of LLMs as optimization planners, it may be premature to combine LLMs with gradient-based optimizer for complex optimization tasks.

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 3
questions: - In Table 2, the comparison is only made with the CoOp method on the ResNet50 model and with the TCP method on the ViT-B/16 model. Why was the SOTA method, TCP, not compared on the ResNet50 model?
- Looking at the flow in Figure 4, each time the LLM generates three candidate prompts. When using gradient descent for optimization, is one of these prompts selected, or do all three prompts need to be optimized?
- In Section 3.2, it is mentioned that "the combined method can achieve smaller standard deviations and better absolute performance." From Figure 2, I cannot clearly see the smaller standard deviation. Listing the numbers might be better.
- In Section 4.2, "From Table 1, the results on the 'RN50' backbone show that...," should it be Table 2?
- I don't quite understand the Single-start gradient optimization and Multi-start Gradient Optimization in Table 3. Could you provide a more detailed explanation? Also, in Section 4.3, the sentence "Multi-start Gradient Optimization (w/w.o. Perturbations)." seems incomplete.

I'm willing to improve my score if you address my concerns.
soundness: 3
strengths: The paper innovatively combines the gradient-based optimizers and the optimization capabilities of LLMs, achieving good results on many benchmarks and providing detailed experimental details.
summary: This paper proposes an optimization method that combines LLM and gradient descent to address the prompt tuning problem. The LLM generates potential prompts based on the historical path of gradient descent, and then these prompts are used as  restarting point for the next stage of gradient descent. This combined optimization approach ultimately achieves results that match or even surpass the current SOTA method, TCP, on several benchmark tasks.
weaknesses: The experiments are not very comprehensive. The paper only compares with two methods, CoOp and TCP (I am ignoring the results from Liu et al.), and it only compares with CoOp on Resnet50 and with TCP on ViT-B/16, lacking a comparison with the other method. Additionally, there is no comparison with other methods such as PromptSRC, MaPLe, and KgCoOp.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: - What happens if you do not discretise the gradient outputs (i.e. follow the original P-tuning protocol)
- How does this method compare to purely combinatorial solvers, like Promptbreeder, Guo et al (https://arxiv.org/pdf/2309.08532), and Zhou et al (https://arxiv.org/pdf/2211.01910)
- How stable is this method against changes in tuning-prompts?
- If I use 32 tokens, does this close the gap?
- How do you set the learning rate for the gradient based systems?

For more details, see the "weaknesses" section
soundness: 3
strengths: The paper is well written and presents the ideas in a clear manner. 

The idea itself is well motivated and should be easily replicatable.

One potentially really interesting part of this paper is the interpretability mentioned in line 464: This is indeed a unique advantage of the LLM based optimization above what can be provided by EA or Gradient based methods, and could potentially even be interesting to use as a standalone interpretation method (i.e. following the gradient, but keeping the result readable).
We encourage the authors to follow up on this.
summary: This paper proposes a method to optimize the answers provided by large language models by combining the properties of prompt tuning using an LLM and gradient based optimization. They compare their method against previous works that use either of these methods individually and showcase superior performance to the individual algorithms used in isolation.
weaknesses: In the abstract you ask the question:
> “ Will this strategy also work well for solving complex non-convex optimization problems?”

This is not sufficiently answered (or arguably answered at all): This paper is not principally about optimization, but rather about prompt tuning. The title is also misleading: This is not a general optimization scheme that happens to have been studied in prompt tuning, but instead a technique _only_ applicable to prompt tuning. I would recommend the authors to remove the references towards more general optimization. Reading the title and abstract of this paper I would expect something closer to https://arxiv.org/pdf/2309.03409 than prompt tuning.

The “Algorithm 1” definition is quite messy: the embedding and token space projection operators are not inverses of each other, so shouldn’t be treated as such. E.g. in line 15 $\tilde p$ is reinitialized despite never being initialized in the first place.


Regarding token-space projection: In line 311 you claim that
> However, it is not feasible to directly provide the soft embedding vectors as input to the LLM,

This might be true with API models, but is not necessarily true for Llama models: As long as the tuned model and the model tuner are of the same type, one could directly input the continuous embeddings. This is done in textual inversion (https://arxiv.org/pdf/2208.01618), and is also the way that the original P-tuning (https://arxiv.org/pdf/2103.10385) worked. Are you also discretizing the P-tuning outputs?
As long as the prompt tuner and the prompt tunee is the same model, I see no reason why the inputs to the tuner have to be discretised first.
For gradient based tuners I would like to see a comparison on the same model with/without discretization since I suspect that the discretization is the true culprit for the performance drops, not the local optimality (indeed recent work, such as https://arxiv.org/pdf/2305.12827 suggests quasi-linearity of models when finetuning around pretrained models).

In line 515ff. you say that:
>A longer training process by gradient-based optimizer may not necessarily benefit the final prompt tuning results. We find that more iterations of gradient-based optimization may result in candidate prompts with less semantic diversity, which is not good for proposing LLM to generate more promising candidate prompts.

Doesn’t this show that the LLM can*not* escape local optima? If the LLM was necessary to escape the local optima, I would expect the LLM to make more of a difference the closer you are to the optimum.

In general, there are not enough comparisons against the state-of-the-art: from the LLM point of view I would expect a comparison against Zhou et al (https://arxiv.org/pdf/2211.01910) which also provide code to reproduce their experiments.
Due to the problem of gradient based optimization in discrete spaces, people have also started moving towards black-box combinatorial solvers, such as Guo et al’s Evolutionary method (https://arxiv.org/pdf/2309.08532, code is also available). Alternatively, you can also look at Deepmind’s PROMPTBREEDER (https://arxiv.org/pdf/2309.16797) which follows a similar idea
The reason I would like an ablation against the e.g. evolutionary method is because as-is it is unclear whether the LLM component of your framework is necessary or whether the advantage simply comes from the optimizer not being gradient based: “Is it necessary to have an LLM, or is it necessary to _not_ use gradients?”.

As a general note: when using APIs such as GPT-3.5 or GPT-4, please also give information of the time the experiments were done. APIs change all the time, so without knowing the timeframe the experiments were conducted in, it becomes hard to evaluate the results 2-3 years later.

In appendix A1 you list the prompt used for Llama2, which is quite different from the GPT-3.5/4 models: you mention that this is due to the inherent differences in the Llama and GPT models, but that opens up another question: How stable are the models to changes in prompts?
The prompt is a quite complex hyperparameter that you do not need in e.g. Evolutionary or gradient based methods, so one should compare different prompts as to not accidentally overfit the used prompt to the explored datasets.

Appendix A2 shows that the performance gap generally reduces as you increase the prompt length: Is there any interpretation for why this might be happening?
If I use 32 tokens, does this close the gap?


How do you set the learning rate for the gradient based systems? I've seen people use the traditional line-search with Wolfe/armijo rules to "get rid" of the learning rate hyperparameter.

Meta-review: This paper studies LLM prompt tuning, by combining LLMs and gradient descent methods. Specifically, the authors propose using an LLM to generate the "restarting points" for the gradient descent procedure using the historical trajectory of gradient descent. 

Reviewers, while commending the idea being interesting and the presentation being clear, have concerns regarding (1) not enough baseline methods in comparison, and (2) branding of the approach as an "oversell". Author rebuttal addressed some, but not all of the concerns.

After a brief read, I also have doubts in whether the method in its current form can be generalised to solving general non-convex optimisation. This is not because the authors only demonstrated the prompt tuning example, but about how the method is justified empirically. 

In my opinion, the major question is about the difference between: 

(a) using an LLM to **generate** the "restarting points" using the historical trajectory of gradient descent;

(b) using an LLM to **evaluate** the historical trajectory of gradient descent, and then **select** the "restarting point" with the highest fitness.

The proposed approach conducts the first step of option (b) and then feeds in the fitness results to an LLM for "restarting point" generation. The advantage of option (a) is that the generated "restarting point" can be different from the gradient descent history, so might be helpful in terms of jumping out of local optima. 

However, first there's no theoretical guarantee that LLMs can do so. Second, even empirically, I think it is critical to continue the second step of option (b) to truly evaluate the effectiveness of an LLM for generating a better "restarting point" compared to the historical solution with best fitness evaluated by an LLM. Also if the non-convex optimisation task is not about prompt tuning, how can LLM help even in the fitness evaluation (i.e., the first step of option (b)) -- perhaps this part also requires some task-specific template design?

Overall I found the idea very interesting, in general I'm curious to see whether this method really works. I encourage the authors to revise their work by incorporating reviewer suggestions and, answering my questions above.

PS --  please provide the error bar results for your 3 seed averaged results to show that your experimental results are indeed statistically significant.

Decision: Reject