ZIP: An Efficient Zeroth-order Prompt Tuning for Black-box Vision-Language Models
Authors: Seonghwan Park
Jaehyeon Jeong
Yongjun Kim
Jaeho Lee
Namhoon Lee
Venue: ICLR 2025 Poster (2025)
Keywords: vision-language models
prompt-tuning
black-box optimization
zeroth-order optimization
Primary area: applications to computer vision, audio, language, and other modalities
TL;DR: We propose Zeroth-order Intrinsic-dimensional Prompt-tuning (ZIP), a method that reduces query demands in black-box prompt-tuning by optimizing in a lower-dimensional space with a robust clipping mechanism.

Abstract: Recent studies have introduced various approaches for prompt-tuning black-box vision-language models, referred to as black-box prompt-tuning (BBPT). While BBPT has demonstrated considerable potential, it is often found that many existing methods require an excessive number of queries (i.e., function evaluations), which poses a significant challenge in real-world scenarios where the number of allowed queries is limited. To tackle this issue, we propose Zeroth-order Intrinsic-dimensional Prompt-tuning (ZIP), a novel approach that enables efficient and robust prompt optimization in a purely black-box setting. The key idea of ZIP is to reduce the problem dimensionality and the variance of zeroth-order gradient estimates, such that the training is done fast with far less queries. We achieve this by re-parameterizing prompts in low-rank representations and designing intrinsic-dimensional clipping of estimated gradients. We evaluate ZIP on 13+ vision-language tasks in standard benchmarks and show that it achieves an average improvement of approximately 6% in few-shot accuracy and 48% in query efficiency compared to the best-performing alternative BBPT methods, establishing a new state of the art. Our ablation analysis further shows that the proposed clipping mechanism is robust and nearly optimal, without the need to manually select the clipping threshold, matching the result of expensive hyperparameter search.

Published as a conference paper at ICLR 2025
ZIP: AN EFFICIENT ZEROTH-ORDER PROMPT TUNING FOR BLACK-BOX VISION-LANGUAGE MODELS
Seonghwan Park', Jaehyeon Jeong', Yongjun Kim Jaeho Lee Nammhon Lee !POSTECH, Yonsei University (seonghwan, park, chungsml, kus0505, jaeho. lee, naithooneee@ppostect...c
ABSTRACT
Recent studies have introduced various approaches for prompt-tuning black-box Aasion-anguuag models, referred as black-box prompt-tuning (BBPT). While BBPT has demonstrated considerable potential, it is often found that many exist- ing methods require an excessive number of queries (i.e., function evaluations), which poses significant challenge in real-world scenarios where the number allowed queries limited. To tackle this issue, we propose Zeroth-order murinsic-dimensional Prompt-tuning (ZIP), novel approach that enables effi- cient and robust prompt optimization in a purely black-box setting. The key idea of ZIP is to reduce the problem dimensionality and the variance of zeroth-order gradient estimates, such that the training is done fast with far less queries. We achieve this by re- re-parameterizing prompts in low-rank representations and design- ing intrinsie-dimensionn clipping of estimated gradients. We evaluate ZIP on 13+ Assionllaguagg tasks in standard benchmarks and show that it achieves an average improvement of approximately 6% in few-shot accuracy and 48% in query effi- ciency compared to the pest-performing alternative BBPT methods, establishing a new state of the art. Our ablation analysis further shows that the proposed clipping mechanism is robust and nearly optimal, without the need manually select the clipping threshold, matching the result of expensive hyperparameter search.
INTRODUCTION
Foundation models pre-trained on vast amount data are creating tremendous success across a wide range of applications in various domains (Ramesh al., 2021; Radford et al., 2021; Jia et al., 2021; Singh et al., 2022; Liu et al., 2023a; Copet et al., 2024). A notable example is CLIP (Radford al., 2021) which learns visual concepts from natural language supervision and works zero-shot at inference.
In fact, these models are fine-tuned for specific downstream tasks at deployment create yet more performance refinement in practice (Liu et al., 2022). is noteworthy, however, that fine-tuning these models is not only computationally expensive, but also requires full access model specifications. The complication here is that many high-performing foundation models are provided only as software-ass aawaaar--------vvie-ee (OpenAI, 2023; Google, 2023) without model details due commercial interests and security concerns.
To overcome this challenge, recent works have suggested fine-tune such black-box models via so-called black-box prompt-tuning (BBPT) (Sun et al., 2022b; Diao et al., 2023; Oh et al., 2023; Yu al., 2023); i.e.. by parameterizing input prompts and only optimizing them via classic derivative-Fii optimization methods such as evolutionary strategies (Hansen & Ostermeier, 2001; Hansen et al., 2003) and zeroth-order optimization (Spall, 1992; 1997; Ghadimi Lan, 2013), it enables fine-tuning without direct access to the model details pack-propagation.
Nevertheless, it still remains a major challenge to secure query-efficiency in existing BBPT methods. Specifically, we find that many existing approaches require excessive model evaluations (i.e., queries), often spanning several tens of thousands times (Tsai et al., 2020; Oh et al., 2023), and moreover, they result in significant performance drop when they given limited query budget. This is quite critical in many practical scenarios where large models are provided in the form prediction APIs, and users only make use of with limited budget.

---

Published as a conference paper at ICLR 2025
1829
Train Accuracy (3g
BBPT Baselines
2197
Rediuction:
CLEAK
BAR
BAR
Dlecetp
BlackVip
518
OPTSUH
36
BPTVLM
23P
2P (ours)
500 1000
Number Queries
1500
2000
1K
2K
Queries
3K
4K
5K
2401
(a) Query efficiency
(b) Training progress
(c) Generalization performance
Figure 1: ZiP performance summary: (a) number of queries required reach given target accuracy, (b) training accuracy vs. number of queries, and (c) test set accuracies, measured on 13 standard vision-language tasks; the first two arithmetic mean. ZIP shows its outstanding performance compared to other black-box prompt-tuning methods (e.g.. BAR (Tsai et al., 2020), BLACK VIP (Oh al., 2023), BPTVLM (Yu al., 2023); the details are provided in Appendix C.5) in terms of both training and generalization performances.
In this work, we propose a new method called ZIP: Zeroth-order Intrinsic-dimensionn Prompt-tuning to tackle this challenge. The key idea is to reduce the dimensionality of the problem (hence the term "intrinsic") and the variance of zeroth-order gradients, such that the training is done fast with far less queries, and subsequently, improves generalization. In essence, achieve this by re-parameterizing prompts in low-rank representations in effective forms and designing intrissi-diimenionne clipping of zeroth-order gradients (Section 4).
Fundamentally, we are inspired by a line of previous works that hint at the dimension dependency of zeorth-order methods (Spall, 1992; Ghadimi & Lan, 2013; Duchi et al., 2015) and noise in stochastic methods (Bottou et al., 2018) causing optimization difficulty when it comes to large models. Indeed, we find this pertinent BBPT in our empirical analysis, which we show that naive zeroth-order method suffers from increased dimensionality unlike the first-order counterpart (Section 3).
Our extensive experimental results show that ZIP is extremely efficient and robust, setting new state of the art. To be specific, we evaluate ZIP on 13+ datasets for various vision-languae tasks in standard benchmarks including few-shot learning. basc-to-new generalization, cross-dataset transfer, and out-of- d-istribbtiion generalization tasks, and across all, we find that ZIP consistently outperforms existing BBPT methods by substantial margins in terms of prediction accuracy, while demanding far less number of queries (Section 5). We provide summary of how ZIP performs in Figure 1.
2 BACKGROUND
Prompt-tuning is an emerging paradigm to update large pre-trained models before utilizing them for various downstream tasks (Lester et al., 2021; Liu al., 2023b). works by prepending learnable context tokens to the input prompts embedding and training them on some data for target task. Specifically, we can formulate it as an optimization problem as follows:
min (D
where E Ie refers to the learnable parameters where d = p denotes the problem dimensionality with and m being the word embedding dimensions and number of context tokens, respectively, and refers to the pre-trained model; also, f refers to the loss function, which is the cross-entropy for Vinion-language tasks in our case, and D a given dataset.
However, prompt-tuning is not directly applicable to black-box models since back-propagation is not allowed, and thus, the optimization must done derivative-fret free. To this end, many approaches have been developed to address this issue for namely derivative-free optimization (Larson et al., 2019). In particular, a series of evolution strategies such as covariance matrix adaptation (Hansen, 2016) has been used for black-box prompt tuning BBPT (Sun et al., 2022b;a; Yu et al., 2023).
2

---

Published as a conference paper at ICLR 2025
85
85
Train Accuracy
Train Accuracy
60
60
35
35-
10
10-
40
120 160 Epochs
80
200
40
120 Epochs
80
160 200
(a) Zeroth-order results
(b) First-order results
Figure 2: Zeroth-order first-order methods for prompt tuning under varying number of prompt parameters. The training progresses are plotted measured on the Flowers 102 dataset; we provide results 10 other datasets in Figure 9 of Appendix B.1 where observe the same trend that the zeroth-order method suffers from increasing prompt dimensionality.
An alternative approach to prompt-tuning in a black-box situation by zeroth-order optimization which leverages approximate gradients estimated from only function evaluations. In particular, one of the foundational techniques is the simultaneous perturbation stochastic approximation (SPSA) (Spall, 1992; 1997), by which the gradient estimate is computed as follows:
N
f( + ez;; B) - f( cz;; B) (z,)-1,
(): = N Σ
(2)
2c
where 2; refers to the perturbation vector randomly drawn from a probability distribution with mean and finite inverse moment, (-) denotes element-wis reciprocal, and N indicates the number of perturbation vector samples used for one gradient estimate; also, and B refer small positive scalar controlling the perturbation magnitude and the mini-batch of data points, respectively; i.e. SPSA estimates gradients by simultancously perturbing all dimensions in 9. Then, the optimization is done iteratively using the zeroth-order stochastic gradient descent (ZO-SGD) (Ghadimi & Lan, 2013) with (2) as follows:
0++1 = 7) f(;;
(3)
where T/2 denotes the step size at iteration f.
This approach has been demonstrated to effective for BBPT tuning Aasoon-anguuage models (Oh et al., 2023; Tsai et al., 2020), and yet, in theory, zeroth-order methods can suffer from high variance and slow convergence, especially for high-dimensional problems (Spall, 1992; Ghadimi & Lan, 2013; Duchi et al., 2015). This means that needs query the model high number of times, which find critical to secure the feasibility of BBPT in practice. As we show throughout this work, our key idea to fix this issue is to reduce the dimensionality of 0 and the variance of V.
3 MOTIVATION
In this section, we motivate our work by disclosing that naively applying a zeroth-order method can lead failure of BBPT. Precisely, we show that its performance deteriorates the number of context tokens (i.e., dimension of trainable parameters) increases. This rather unexpected because increasing their dimensions, in fact, is found improve performance when optimized with first-order method for prompt tuning.
To be specific, optimize vision-language model using both the basic zeroth-order or ZO (3) and first-order or FO (i.e., SGD) methods, with varying the number of context tokens (1, 8, 64), and measure their training progress. We used CLIP (Radford et al., 2021), representative pre- trained vision- language model widely used in the literature. The results are plotted in Figure 2. We summarize two key observations follows:
General prompt tuning can benefit from increased parameters, achieving higher expressive power and performance, especially with moderate number of context tokens (e.g., 8 tokens).
contrast, prompt tuning with zeroth-order optimization suffers in both training speed and performance the number of context tokens increases.
3

---

Published as a conference paper at ICLR 2025
Dipped
Random Projection
Black Box VLMS
Law Rank Approximation
v8-
Flowers 102
OxfordPets
Feature Sharing
Caltech
0
<8
[|9rool
Black-Box VLM
Prompt Reparameterization
Clipped
Downstreamn
ZO Optimization
Tasks
Figure 3: Overview of ZIP framework.
These findings reveal fundamental limitation of directly employing a zeroth-order method in BBPT: they are potentially applicable to BBPT, but not to the degree to which their performance is compatible with those of first-order methods they can benefit from an increased number of context tokens.
Additionally, we further provide a convergence analysis of ZO-SGD (3) in Theorem I of Appendix A.2 clearly show dependency on the problem dimensionality d and highlight the limitation of the zeroth-order approach.
We aim alleviate this discrepancy in this work. This approach represents significant departure from previous studies on BBPT, which have primarily focused on applying derivative-free optimization to specific domains, such as LLMs (Sun et al., 2022b) or vision-language models (Yu al., 2023; Oh al., 2023). We directly tackle this limitation of employing zeroth-orde order method for BBPT by enhancing both its efficiency and effectiveness, even suggesting potential to bridge the gap between black-box and general prompt tunings.
ZIP: ZEROTH-ORDER INTRINSIC-DIMENSIION
PROMPT-TUNING
In this section, explain ZIP in detail, which is designed to address the fundamental issue of applying a zeroth-order method to BBPT. To this end, we first suggest reducing the number of learnable parameters in representing the context tokens via series of reparameterization techniques. Then, we introduce a gradient clipping technique tailored for zeroth-order optimization intrinsic dimensions to enhance the efficiency and effectiveness of ZIP. An overview of the ZIP framework is provided in Figure 3.
4.1 PROMPT TUNING IN LOWER DIMENSIONAL SPACES
As discussed in previous sections, the convergence, and hence the performance, of zeroth-order methods depends highly on the problem dimensionality (Ghadimi & Lan, 2013; Duchi et al., 2015). thus first propose reducing the optimization dimensionality to secure applicability of zeorth-order methods to BBPT. In fact, Aghajanyan et al., 2021) which refers to an effective dimensionality of given problem and suggests that optimizing in that dimension can be effective in the full parameter space.
also inspired by the concept of intrinsic dimension (Li et al., 2018;
Specifically, we first project the learnable parameters each context token 0, E RR' onto a lower- dimensional space v; R using Fastfood transform matrix M, RPx0 in Le et al. (2013); Li et al. (2018); Aghajanyan et al. (2021). The total number of trainable parameters are then reduced from d = p x m, to d' q m with d' d. Each vector indexed by corresponds the i-th trainable context token where m indicates the total number of context tokens. The random projection can then be expressed follows:
0, = 0 + M,
where 0, initial parameters. With this reparameterization, we can project learnable parameter to much lower dimension, from to d'.
Further, we apply another reparameterization in a low-rank approximation fashion as below, to get trainable parameter matrix W:
W-
|0/1v// [mmml Udiag(s)VV
4

---

Published as a conference paper at ICLR 2025
We initialize U to zeros. V with standard normal distribution, and to ones, ensuring W starts at zero. With this reparameterization, the optimization variables become E RR V R Rrxm and e R". Unlike the other conventional low-rank approximation methods (Hu al., 2022), interpose a diagonal matrix, which can effectively adjust the importance of specific dimensions by letting diagonal parameters directly scaling each dimension independently. We verify the effectiveness of our approach in experiments section 6.3 and also compare with other decomposition methods in Appendix B.5. This reparameterization allows to reduce the number of trainable parameters while preserving the effectiveness as in optimizing the original parameters.
4.2 ENHANCING EXPRESSIVENESS WITH FEATURE SHARING
While reducing parameters can accelerate training with zeroth-order methods, it could also reduce the model expressivity. To address this issue, we introduce feature sharing technique, which incorporates vector u E R within W and can serve as a common base across the partitioned vectors. This vector is integrated into original vectors ey. by using outer product with vector R"", forming the final trainable parameter matrix
= W
+ a Udiag(s VT L
[o' 2/10 + u
10
u
[w] [22| |mml
where each wy E 189 a mixed vector that blends the original components v, with the feature sharing by u. The updated parameters for context tokens are then computed as:
0: Go M,
(7)
We argue that the model can better learn complex features, leading to improved performance. This technique only requires a negligible amount of learnable parameters. We empirically validate the importance of the feature sharing in Section 6.2.
4.3 REDUCING VARIANCE WITH INTRINSIC- DIMSSIICCDDENSTNNAAL CLIPPING
Through a series of reparameterizzatio schemes, we obtained the final trainable parameters matrix E, in which there are 8 r(q m + parameters in total. Now, the problem (1) reduces
min w(E,w;:)
(8)
One can consider employing ZO-SGD (3) to solve this problem, and yet, as demonstrated in Section 3, it can still cause slow convergence in practice due its large variance.
To address this issue, we propose a simple yet robust zeroth-order method based on what we call mntrisiieddimnssoon gradient clipping mechanism defined follows
E E, m.ar ff
(9)
where o₁ is a scaling factor defined as follows
V8
O22 min
(10)
5 Eim &E, w; B)
where d refers to the problem dimensionality mentioned above; i.e., it clips the zeroth-order stochastic gradient estimates f if its norm exceeds vō as a threshold, while iteratively updating E, There are several interesting aspects of this method described below.
First, the immediate advantage this approach is that there no need to manually select the clipping threshold (which is prone to be suboptimal) or perform expensive hyperparameter search. Considering that gradient clipping can accelerate the optimization process in general (Zhang et al., 2020b), and yet, that appropriate choice of the threshold value is required, this advantage is certainly nontrivial. We validate this adaptivity by showing that the threshold chosen based on (10) is, quite surprisingly, nearly optimal across diverse training workloads in Section 6.1.
5

---

Published as a conference paper at ICLR 2025
Also, the threshold being expressed in terms of the problem dimensionality 6, in particular, vō, should be reasonably inspiring, considering research results in the literature. Specifically, we can interpret that previous work suggests setting the clipping threshold (for general first-order methods) to be the standard deviation of estimated gradients (Zhang et al., 2020a; Pascanu et al., 2012; Zhang et al., 2020b;e). While this is again not quite practical to compute, we notice that it can be done relatively straightforwardly for zeroth-order optimization, since the variance of zeroth-order gradients is inherently bounded in terms of the problem dimensionality 6, thus the standard deviation being v8. We explicitly show this in Lemma 2 of Appendix A.1.
EVALUATIONS
5.1 EXPERIMENTAL SETUP
Datasets and tasks. To assess the query efficiency and performance of ZIP, we conduct evaluations on standard generalization tasks following the protocols of Zhou et al. (2022a;b); Oh al. (2023). These tasks include few-shot learning, base-to-new generalization, cross-dataset transfer, and out- of-distribution (OOD) generalization. For few-shot learning, base-to-new generalization, and cross- dataset transfer, we evaluate ZIP across 13 diverse image classification tasks: ImageNet (Deng et al., 2009), Caltech101 (Fei-Fei et al., 2004), OxfordPets (Parkhi et al., 2012 2), Flowers 02 (Nilsback Zisserman, 2008), Food101 (Bossard et al., 2014), FGVCAircraft (Maji et al., 2013), SUN397 (Xiao et al., 2010), Resise45 (Cheng et al., 2017), DTD (Cimpoi et al., 2014), SVHN (Netzer et al., 2011), 1), EuroSAT (Helber et al., 2019), CLEVR (Johnson et al., 2017), and UCF101 (Soomro et al., 2012). For evaluating OOD generalization, we employ four established OOD datasets to measure the robustness of ZIP under distribution shifts: ImageNetV2 (Recht et al., 2019), ImageNet-Skeet (Wang et al., 2019), ImageNet-A (Hendrycks et al., 2021b), and ImageNet-R (Hendrycks et al., 2021a).
Baselines. To thoroughly evaluate the performance of ZIP, compare it against variety of baselines: (1) manual prompt, where manually composed prompts to conduct the evaluation (human- detailed in Table 15); (2) state-of-the-art BBPT approaches for VLMs including BAR (Tsai et al., 2020), BLACKVIP (Oh et al., 2023) and BPTVLM (Yu et al., 2023). For all baselines, we follow the standardized few-shot evaluation protocol across datasets, consistent with Zhou et al. (2022b); Oh et al. (2023), which includes specific few-shot splits to ensure a fair comparison.
written prompts
Implementation details. We mainly experiment using the CLIP (Radford et al., 2021) model with vision transformer (Dosovitskiy et al., 1, keeping the CLIP model frozen. We consistently set the number of context tokens as 8 for ZTP and use 5,000 queries across all tasks for all BBPT baselines. The number of the intrinsic dimensionality d' set to 500, and the rank of low-rank matrices r = 5, resulting in a total of 417 learnable parameters ó with the formula r(ld' /m] + m + 1) + dd/m]. Following the previous works for transfer learning (Zhou et al., 2022a;b; Oh et al., 2023), we initialize soft prompts from prompts derived from source tasks. We use the official code reproduce BBPT baselines, and the results are averaged over three different random seeds. The implementation is available at https: httgt/tttuuttt www.moo----..... wwwpech/st...ppoo
5.2 GENERALIZATION PERFORMANCE
We present empirical evidence showcasing the effectiveness and robustness of our proposed method, ZIP, across 13+ vision-language tasks. Our results, summarized Table 2, and 3, cover evaluations on few-shot accuracy, base-to- -ow generalization, and cross-dataset transfer with out-of off-iittibbution generalization. The experiments reveal two main insights: (i) ZIP consistently outperforms other BBPT baselines across various tasks; (ii) ZIP achieves better robustness to unseen data distribution compared to existing BBPT methods; Detailed analyses of these findings are provided below.
Few-shot performance. As represented in Table 1, our experimental result indicates that ZIP con- sistently outperforms state-of-the-an BBPT approaches, including BAR, BLACKVIP, and BPTVLM, across 11 out of 13 datasets. On average, ZIP achieves accuracy gains of +7.7%, +6.8%, and +7.8% over BAR, BLACKVIP. and BPTVLM, respectively, demonstrating notable effectiveness in few- shot learning. In particular, ZIP excels on datasets requiring coarse semantic understanding. with

---

Published as a conference paper at ICLR 2025
Table 1: Few-shot performance on 13 vision-language tasks. All the results are based on 16-shots per class. The bold numbers denote the highest accuracy of all baselines on each dataset, and the underlined values indicate the second. ZIP clearly outperforms other BBPT baselines.
FOVCAleraft
Caltech
OxfordPets
Flowers102
Food101
SUN397
1T1I
SVHN
EuroAAT
Rosise45
CLEVR
UCF100
ImageNNal
Average
Method
#Params
Manual Pronut
Ok
93.2
89.1
70,8
85.9
24.8
62.6
44.1
19.2
48.4
$7.2
15.2
67.5
66.7
$7.3
BAR
37.6k
92.5
85.6
65.0
83.0
21.6
62.4
42,9
19.8
51.6
53,9
18.1
63.5
64.0
55.7
BLACK VIP
9.9k
92.6
86.9
63.5
83.5
21.5
62.3
43.1
27.5
44.4
55.5
25,9
64.0
65.5
56.6
BPTVLM
4.0k
88.6
89.4
66.9
84.2
24.0
53.2
40.6
29.8
$3.0
56.2
16.4
64.8
55.5
55.6
ZIP
0.4k
94.0
92.3
86.4
26.8
63.3
47.8
47.8
64.6
66.1
28.4
69.8
66.2
Table 2: Base-to-new generalization performance. H represents the harmonic mean, providing
balanced measure of accuracy across seen and unseen classes (Xian et al., 2017). ZIP consistently
outperforms BAR, BLACKVIP, and BPTVLM across base, new, and harmonic mean evaluations.
RGVCAireraft
Caltech101
OxfordPess
Flowers102
Food101
SUN397
EumSAT
Resine45
CLEVR
UCF101
ImageNes
Average
SVHN
DTD
Method
Set
BAR
96.5
87.3
67.5
87.5
25.6
69.2
51.2
23.5
60.2
66.1
27.5
66.4
69.6
61.4
BLACKVIP
96.6
87.7
67.9
87.6
25.8
69.0
51.8
26.4
66.4
69.9
38.9
67.0
70.3
63.5
BPTVLM
Base
93.2
90.6
66.9
88.7
29.1
65.3
53,2
45.4
70.3
72.0
41.5
68.3
66.3
65.4
Zip
97.0
94,9
72.1
89.9
29.7
70.3
61.7
52.9
84.0
81.6
50.1
75.1
72.1
71.6
BAR
94.5
94.9
73.2
88.9
29.2
74.6
55.8
27.3
72.1
62.3
27.1
73.3
64.9
64.5
BLACKVIP BPTVLM
93.2
90.9
74.5
30.9
73.9
55.4
21.8
48.8
61.2
28.0
72.6
66.8
62.1
New
92.7
95.8
72.7
85.4 4
32.3
64.8
45,3
40.1
47.0
61.3
28,4
65.0
55,2
60.5
ZIP
94.3
97.0
73.4
90.0
32.9
71.5
51.0
45.8
64.4
65.2
26.8
69.5
65.6
65.2
BAR
95.5
90.9
70,2
88.2
27.3
71.8
53.4
25.3
65.6
64.1
27.3
67.7
67.2
62.9
BI BLACKVIP
Harmonic
94.9
89.3
71.0
88.5
28.1
71.4
53.5
23.9
56.3
65.3
32,6
69.7
68.5
62.8
BPTVLM
92.9
93.1
69.7
87.0
30.6
65.0
48.9
42.6
56.3
66.2
33.7
66.6
60.2
62.9
ZIP
95.6
95.9
72.7
89.9
31.2
70.9
55.8
49.1
72.9
72.5
34,9
72.2
68.7
Table 3: Cross-dataset transfer and out-of-distribttion generalization performance. After training on ImageNet (i.e.. source) with 16-shot data per class, ZIP is evaluated on 12 target datasets for CDT and 4 ImageNet variants for OOD. ZIP demonstrates better transferability and generalizability. outperforming BAR, BLACKVIP, and BPTVLM.
Source
CDT Targel
0OD Targel
ImageNer- Sherthh
TCVCAirenai
Imagshet
Calteet01
OrfordPets
Flowars02
10od101
SUNS9T
DTD
SVIN
FunSAT
Resisok5
CLEVR
LICH11
AverAMe
InageNet-A
ImageNerVV2
LowgsNet-Rt
Averuse
Method
BAR
64.0
92.3
84.3
64.3
83.1
20.8
61.0
42.2
20.0
49.6
90.6
14.5
63.0
53.8
40.2
57.5
72.0
43.8
53.4
BLACKVIP
65.5
92.5
86.2
61.9
83.6
22.3
62.0
43.3
18.7
40.5
55.7
15.
64.1
51.1
42.5
59
73.1
41.6
51.9
BPTVLM
55.5
77.7
77.6
16.3
43.8
30.8
15.5
34.6
37.7
12.4
34.8
44.4
32.7
46.7
33.5
43.7
41.5
26.4
46.7
547
613
548
improvements of +11.66 1..6 on EuroSAT, and +8.9% on Resise45 compared to the second-best method. Additionally, ZIP shows remarkable performance in digit recognition, surpassing the next best method by +18.0% on the SVHN dataset, further highlighting its capability in few-shot learning.
Basc-to-new generalization. Table 2 presents the base-to-new generalization results, where models are trained on base classes and evaluated on both base and new classes across 13 datasets. ZIP consistently outperforms all BBPT baselines, achieving the highest base, new, and harmonic mean scores. By leveraging its lower parameter count and the robustness of zeroth-order optimization, ZIP effectively mitigates overfitting, as its reduced model capacity and rough gradient estimates help avoid fitting to noisy outliers, resulting in better generalization.
Cross-dataset transfer & Out-of-distribution generalization. To assess robustness in challenging scenarios, evaluate ZIP for cross dataset transfer (CDT) and ofitt--diitributiin (OOD) gener- alization. As shown in Table 3, ZIP, trained on ImageNet (i.e., source), demonstrates competitive generalization capabilities in the CDT setting, achieving slight improvements of 1.0% over BAR and
7

---

Published as a conference paper at ICLR 2025
Ca
OxfordPets
Flowers102
Food1D1
80
64
80-
Accurecy (N0)
73
Tran Perorang
56
68
50
40
50
23 1ount
(ouns
2K
Number Quarles
Number Quorles
Number Quorlas
Querles
Figure 4: Training performance measured on 101, OxfordPets, Flowers and Food101. We provide more results on other datasets in Figure 10.
Catedh15t
Oxfordiets
Flowers 22
Fredf D0
2300
2000
$12
1000
Numbrrof Ouele
Mamber Quartes
Kumber ououees
BAR
BidVP
IITVIM
Figure 5: Number of queries to reach a target accuracy. For the datasets Caltech101, OxfordPets, Flowers Food101, and FGVCAireraft, ZIP requires fewer API calls to reach target accuracy thresholds in most cases. This demonstrates considerable query efficiency when compared to other BBPT methods. We provide more results on other datasets in Figure 11.
0.7% over BLACKVIP, with a more notable gain of 10.4% over BPTVLM across 12 diverse target datasets. More significantly, in the OOD evaluations on four ImageNet variants, ZIP consistently outperforms all baselines, achieving substantial gains of 3.5% over BAR, 2.0% over BLACK VIP, and remarkable 13.2% improvement over BPTVLM. These results highlight the exceptional robustness and adaptability of 7IP handling domain shifts, making it particularly effective for real-world applications where OOD generalization is critical.
5.3 QUERY EFFICIENCY
This section provides empirical evidence highlighting the query efficiency of ZIP We start by tracking the training progress of different BBPT methods, ensuring all operate within the same computational budget. For fair comparison, ZIP and other baselines are allocated budget of 5,000 queries. This query budget was chosen to reflect more practical scenario, as
Oxford Pets
81
Train Accuracy (3%)
75
many existing methods often require thousands of epochs (Oh
69
et al., 2023), which is unrealistic for real-world applications with strict API query limitations. By setting a more feasible budget, we aim to evaluate efficiency of each methods under conditions that closely resemble practical deployment settings.
63
1K 2K
4K
5K
Number of Queries
Figure 6: Training curves of first- order (FO), zeroth-order (ZO) and ZIP. ZIP effectively bridges the gap between FO and 70 with notably faster training and high accuracy.
Figure 4 shows that ZIP consistently achieves faster training speed and higher accuracy than other BBPT methods under identical query budget constraints. This efficiency is attributed to the effective combination of low-rank approximation with diagonal matrix and our specialized threshold for zeroth-order optimization, which accelerates training, while the feature sharing and compactness of the low-rank representation enhance overall performance. These design elements work synergistically. allowing ZIP to achieve rapid training progress and improved accuracy. Detailed analysis of the module combination is provided in Appendix B.7. To further analyze query efficiency, we evaluate the number of queries required to reach target accuracy, which is determined as the minimum of the maximum accuracy achieved by all methods. As shown Figure 5, ZIP demonstrates strong query efficiency, achieving the best performance in datasets like Caltech101 and Food101, and maintaining competitive efficiency in OxfordPets and Flowers 102, even when not the absolute best. The overall results, summarized in Figure la, show that ZIP achieves over 48% improvement in query efficiency compared to the second-best BBPT method. This indicates that ZIP utilizes its query budget effectively, making it particularly suited in resource-constrained scenarios.
8

---

Published as a conference paper at ICLR 2025
OxfardPets
Caltech101
DxfordPets
80
Jae Meuuaay (S0
Acconaty
1.3
accurayy
14
Crpary
Citpping
friin
70
Lo
1.
30
0.6
Number of Queries
Number Queries
Exponent K
Exporent
(a) Effects our clipping threshold (in Scction 6.1)
(b) clipping method varying threshold 5
Figure 7: Effects of intrinsic-dimensiona clipping.
(a) Training progress comparison with and without intrinsieddimnnsional clipping. (b) Test accuracy with varying thresholds 8*, The red point indicates the chosen threshold of ZIP, which consistently achieves near-optimal accuracy.
Table 4: Benefits of feature sharing over unshared. Integrating shared features consistently boosts
model expressive power and accuracy across diverse tasks, demonstrating improved performance.
FGVCAireraft
Caltech101
OxfordPets
Flowers
Food101
SUN397
SVHN
EuroSAT
Resise45
CLEVR
UCE101
ImageNet
Average
DID
Method
Unshared
93.1
90.8
67.1
86.0
25.2
59.0
44.4
40.9
60.6
63.3
20.2
67.4
65.2
60.2
Shared
93.5
91.8
70.6
86.2
26.3
62.2
46.5
43.8
66.2
65.6
24.4
69.0
65.5
62.4
We also compare the query efficiency of ZIP with first-order and naive zeroth-order optimization, using tokens and 5,000 queries across all methods. As shown in Figure 6, ZiP bridges the gap between first-order and zeroth-order optimization, achieving training speeds similar to first-order on the OxfordPets dataset. While zeroth-order methods typically exhibit dependence on for training speed, the efficient design of ZIP allows it to match first-order optimization behavior: This demonstrates the enhanced query efficiency of ZIP, making highly suitable for practical applications where efficient resouree utilization is critical. Further details query efficiency across additional datasets can be found in Figure 10, 11 and 12.
ABLATIONS
6.1 INTRINSC-DDMENSSIONE CLIPPING
In this section, we evaluate the effectiveness of our clipping method, with setting threshold as vō. We begin by tracking the training progress ZiP with catrinsie-immensional clipping and the one without. As shown in Figure 7a, ZIP with our clipping threshold consistently achieves faster training speeds and higher accuracy, indicating its efficiency in enhancing zeroth-order optimization. This improvement is largely due the aariance-reducing nature of clipping, which results in more stable gradient estimates and consequently accelerates the training process.
To further validate the effectiveness of gradient clipping with our threshold, we compared vō thresh- old against various alternative values to ensure its optimality. As shown in Figure 7b, the v8 threshold consistently achieved near-optimal performance
Caltech 101 and OxfordPets, outperforming other clipping settings ranging from 1 (= 80/10) to 8 (= 810/10). The gray dashed line, representing clipping, further underscores the advantage of v5 threshold. These results highlight the effectiveness of the V threshold, demonstrating its capability optimization without requiring extensive hyperparameter tuning. Additional validation results on other datasets available in Figure 16 and 17.
efficient clipping strategy for zeroth-ord orderr
6.2 FEATURE SHARING
To evaluate the expressive power of feature sharing, compared the performance of models with and without feature sharing. As shown Table 4, models utilizing feature sharing consistently achieved higher accuracy, increasing the overall average score from 60.2% to 62.4%. These consistent gains

---

Published as a conference paper at ICLR 2025
Table Benefits of low-rank approximation with diagonal matrix. Comparing our method against standard dimensionality reduction, demonstrating notable test accuracy improvements.
FGVCAirerat
Caltech101
OxfordPets
Flowers102
Fond1001
SUN397
EuroSAT
Resise45
CLEVR
UCFIOI
ImageNet
Average
SVHN
DTD
Method
Standard
90.9
88.1
67.5
84.6
23.8
57.9
43.2
31.5
56.5
58.3
18.3
65.3
62.3
57.6
Ours
93.1
90.8
67.1
86.0
25.2
59.0
44.4
40.9
60.6
63.3
20.2
67.4
64.8
60.2
across diverse datasets highlight the effectiveness of features sharing in retaining model expressiveness and improving performance, even when parameters reduced.
Furthermore, feature sharing shows consistent benefits across diverse datasets, underscoring its robustness technique for maintaining accuracy while optimizing parameter efficiency. To evaluate whether feature sharing improves generalization to unseen datasets, we analyze its impact on base-to-new generalization, cross-dataset transfer, and out-of-distribution scenarios, as detailed in Appendix B.4. These findings validate the role of feature sharing in enhancing generalization and its potential utility in broader domain adaptation tasks.
6.3 Low RANK APPROXIMATION WITH DIAGONAL MATRIX
The low-rank approximation with a diagonal matrix piv- otal in enhancing both the efficiency and performance of our method. Unlike naive lower-dimensional projections, this ap- proach effectively preserves the most crucial components of the parameter space, allowing for accelerated training without compromising the expressive power of the model.
OxfordPets
1.9
None SVD
Train
As shown in Figure and Table this approach not only accel- erates the training process but also improves model accuracy. For instance, the average accuracy across datasets increased from 57.6% 60.2% with the application low-rank approx- imation using a diagonal matrix. These gains highlight the effectiveness of the technique in enhancing training efficiency and overall model performance, making it particularly advan- tageous for optimizing zeroth-order based prompt tuning com- pared to more straightforward projection methods. Additional results on other datasets further validating this improvement can be found in Figure 14.
0.7
1K 2K Number Queries
3K
5K
Figure 8: Effects of low-rank ap- proximation with diagonal matrix. Our method improves training effi- ciency compared to standard dimen- sionality reduction.
CONCLUSION
In this paper, we propose ZIP, a new method for prompt-tuning black-box vision- languaeee models. Extensive experiments show that ZIP outperforms of-te-of-the-rr art BBPT methods in generalization performance while offering faster training with far less number of queries. We believe that our work unlocks numerous opportunities for future work including, instance, extending broader range of foundation models and addressing diverse prompting schemes in different black-box optimization scenarios. We intend to explore these ideas in future work.
REPRODUCIBILITY STATEMENT
To ensure reproducibility, we provide detailed information experimental setup in Appendix C.4, including training and evaluation procedures. All datasets used in this work are publicly available. We conduct experiments NVIDIA 3090, A6000, A A100 and Intel Gaudi-y2 GPUs.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENT
This work was partly supported by the Institute of Information & communications Technology Planning & Evaluation (ITPP) grant funded by the Korean government (MSIT) (RS-2019-1199196 Artificial Intelligence Graduate School Program (POSTECH), RS-2024-00338 40, Development of learning and utilization technology to reflect sustainability of generative language models and up-to- dateness over time, and RS-2022-DB5 2022-11220959, (part2) Few-Shot learning of Causal Inference in Vision and Language for Decision Making), the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) RRS-2023-0021 10466, RS-2003-00265444), Samsung Research 00220558--9925-000 and the NAVER-Intel Co-Lab. The work was conducted by POSTECH and reviewed by both NAVER and Intel.
REFERENCES
Armen Aghajanyan, Sonal Gupta, and Luke Zettlemoyer. Intrinsic dimensionality explains the effectiveness of language model fine-tuning. In IJCNLP, 2021.
Lukas Bossard, Matthieu Guillaumin, and Luc Van Gool. Food- 101- mining discriminative compo- nents with random forests. In ECCV, 2014.
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM review, 2018.
Gong Cheng, Junwei Han, and Xiaoqiang Lu. Remote sensing image scene classification: Benchmark and state of the art. Proceedings of the IEEE, 2017.
Mircea Cimpoi. Subhransu Maji. lasonas Kokkinos, Sammy Mohamed, and Andrea Vedaldi. De- scribing textures in the wild. In CVPR, 2014.
Jade Copet, Felix Kreuk, Itai Gat, Tal Remez, David Kant, Gabriel Synnaeve, Yossi Adi, and Alexandre Défosse7. Simple and controllable music generation. NeurlPS, 2024.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In CVPR, 2009.
Shizhe Diao, Zhichao Huang, Ruijia Xu, Xuechun Li, Yong Lin, Xiao Zhou, and Tong Zhang. Black-box prompt learning for pre-trained language models. TMLR, 2023.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In ICLR, 2021.
John C Duchi, Michael Jordan, Martin J Wainwright, and Andre Wibisono. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, 2015.
Li Fei-Fei, R. Fergus, and Perona. Learning generative visual models from few training examples: An incremental bayesian approach tested on 101 object categories. In CVPR Workshop, 2004.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 2013.
Google. Gemini: a family of highly capable multimodal models. arXiv preprint arXiv:2312.11805. 2023.
Nikolaus Hansen. The ema evolution strategy: tutorial. arXiv preprint 1604. 000772, 2016.
Nikolaus Hansen and Andreas Ostermeier. Completely derandomized self-adaptation in evolution strategies. Evolutionary Computation, 2001.
Nikolaus Hansen, Sibylle D. Müller, and Petros Koumoutsakos. Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (cma-es). Evolutionary Computation, 2003.
11

---

Published as a conference paper at ICLR 2025
Patrick Helber, Benjamin Bischke, Andreas Dengel, and Damian Borth. Eurosat: A novel dataset and deep learning benchmark for land use and land cover classification. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 2019.
Dan Hendrycks, Steven Basart, Norman Mu, Saurav Kadavath, Frank Wang, Evan Dorundo, Rahul Desai, Tyler Zhu, Samyak Parajuli, Mike Guo, et al. The many faces of robustness: A critical analysis of out-of-distribution generalization. In ICCV, 2021a.
Dan Hendrycks, Kevin Zhao, Steven Basart, Jacob Steinhardt, and Dawn Song. Natural adversarial examples. In CVPR, 2021b.
Edward J Hu, yelong shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. LoRA: Low-rank adaptation of large language models. In ICLR, 2022.
Chao Jia, Yinfei Yang. Ye Xia, Yi-Ting Chen, Zarana Parekh, Hieu Pham, Quoe Le, Yun-Hsuan Sung. Zhen Li, and Tom Duerig, Scaling up visual and lisoonlanguagg representation learning with noisy text supervision. In ICMI., 2021.
Justin Johnson, Bharath Hariharan, Laurens Van Der Maaten, Li Fei-Fei, C Lawrence Zitnick, and Ross Girshick. Clevr: A diagnostic dataset for compositional language and elementary visual reasoning. CVPR, 2017.
Jeffrey Larson, Matt Menickelly, and Stefan Wild. Derivative-free optimization methods. Acta Numerica, 2019.
Quoe Le, Tamás Sarlós, Alex Smola, et al. Fastfood-appro-ne -aprxxot-a kernel expansions in loglinear time. In ICML, 2013.
Brian Lester, Rami Al-Rfou, and Noah Constant. The power of scale for parameter-efficien prompt tuning. In EMNLP, 2021.
Chunyuan Li, Heerad Farkhoor, Rosanne Liu, and Jason Yosinski. Measuring the intrinsic dimension of objective landscapes. In ICLR, 2018.
Haokun Liu, Derek Tam, Mohammed Mugeeth, Jay Mohta, Tenghao Huang, Mohit Bansal, and Colin A Raffel. Few-shot parameter-efficient fine-tuning is better and cheaper than in-context learning. NeurIPS, 2022.
Haotian Liu, Chunyuan Li, Qingyang Wu, and Yong Jae Lee. Visual instruction tuning. NeurlPS, 2023a.
Pengfei Liu, Weizhe Yuan, Jinlan Fu, Zhengbao Jiang, Hiroaki Hayashi, and Graham Neubig. Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing. ACM Computing Surveys, 2023b.
Subhransu Maji, Esa Rahtu, Juho Kannala, Matthew B. Blaschko, and Andrea Vedaldi. Fine-grained visual classification of aircraft. CoRR, 2013.
Yurii Evgen' evech Nesterov. A method of solving convex programming problem with convergence rate ( Doklady Akademii Nauk, 1983.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. In NeurIPS Workshop, 2011.
Maria-Elena Nilsback and Andrew Zisserman. Automated flower classification over a large number of classes. In ICVGIP, 2008
Changdae Oh, Hyeji Hwang, Hee-young Lee, Yong Lim, Geunyoung Jung, Jiyoung Jung, Hosik Choi, and Kyungwoo Song. Blackvip: Black-box visual prompting for robust transfer learning. In CVPR, 2023.
OpenAL. ChatGPT. https: https:///ppeaa...omm/l.gg/
2023.
Yassine Ouali, Adrian Bulat, Brais Matinez, and Georgios Tzimiropoulos. Black box few-shot adaptation for vision-language models. In ICCV, 2023.
12

---

Published as a conference paper at ICLR 2025
Omkar M Parkhi, Andrea Vedaldi, Andrew Zisserman, and C. V. Jawahar. Cats and dogs. In CVPR, 2012.
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. Understanding the exploding gradient problem. arXiv preprint arXiv:1211.5063 2012.
Alec Radford, Jong Wook Kim, Chris Hallacy. Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In ICML, 2021.
Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever. Zero-shot text-to-image generation. ICML, 2021.
Benjamin Recht, Rehecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do imagenet classifiers generalize to imagenet? In ICML, 2019.
Amanpreet Singh, Ronghang Hu, Vedanuj Goswami, Guillaume Couairon, Wojeiech Galuba, Marcus Rohrbach, and Douwe Kiela. Flava: A foundational language and vision alignment model. In CVPR, 2022.
Khurram Soomro, Amir Roshan Zamir, and Mubarak Shah. UCF101: A dataset of 101 human actions classes from videos in the wild. CoRR, 2012.
James C Spall. Multivariate stochastic approximation using a simultancous perturbation gradient approximation. IEEE transactions automatic control, 1992.
James C. Spall. A meeeureasueeent form of simultaneous perturbation stochastic approximation. Automatica, 1997.
Tianxiang Sun, Zhengfu He, Hong Qian, Yunhua Zhou, Xuan-Jing Huang, and Xipeng Qiu. Bbtv2: towards a gradient-free future with large language models. EMNLP, 2022a.
Tianxiang Sun, Yunfan Shao, Hong Qian, Xuanjing Huang, and Xipeng Qiu. Black-box tuning for language-model-at as as-assevice. In ICML, 2022b.
Yun- Tsai, Pin-Yu Chen, and Tsung- Yi Ho. Transfer learning without knowing: Reprogramming
black-box machine learning models with scarce data and limited resources. In ICML, 2020.
Haohan Wang, Songwei Ge, Zachary Lipton, and Eric Xing. Learning robust global representations by penalizing local predictive power. NeurlPS, 2019.
Zhengbo Wang, Jian Liang, Ran He, Zilei Wang, and Tieniu Tan. Connecting the dots: Collaborative fine-tuning for black-box vision-language models. In ICML, 2024.
Yongqin Xian, Bernt Schiele, and Zeynep Akata. Zero-shot learning- good, the bad and the ugly. In CVPR, 2017.
Jianxiong Xiao, James Hays, Krista A. Ehinger, Aude Oliva, and Antonio Torralba. Sun database: Large-scale scene recognition from abbey zoo. CVPR, 2010.
Lang Yu, Qin Chen, Jiaju Lin, and Liang He. Black-box prompt tuning for vision-language model as service. In IJCAI, 2023.
Xiaohua Zhai, Basil Mustafa, Alexander Kolesnikov, and Lucas Beyer. Sigmoid loss for language image pre- trainiiingg. In ICCV, 2023.
Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of clipping algorithms for non-convex optimization. NewrIPS, 2020a.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie, Why gradient clipping accelcrates training: theoretical justification for adaptivity. ICLR, 2020b.
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why adaptive methods good for attention models? NeurIPS, 2020c.
13

---

Published as a conference paper at ICLR 2025
Kaiyang Zhou, Jingkang Yang, Chen Change Loy, and Ziwei Liu. Conditional prompt learning for vision-lanuuage models. In CVPR, 2022a.
Kaiyang Zhou, Jingkang Yang, Chen Change Loy, and Ziwei Liu. Learning to prompt for vision- language models. IJCV, 2022b.
14

---

Published as a conference paper at ICLR 2025
A THEORETICAL ANALYSIS
A.I ASSUMPTION LEMMA
Assumption 1. On the function f()), there exists some L O such that for all y, have [V)(z) - ff(il S L|| yll
Lemma 1. (Unbiasdness of ZO-SGD) In the et - O limit, ZO-SGD is unbiased estiamtor of FO-SGD terms of random perturbation vector, which follows a Bernoulli distribution of two different values with equal absolute value and probability. That is,
IN (V (0c; B.)) (00;;
(11)
Proof of Lemma 1. Note that as Cz. limit, have
1
Σ Vz)BBBB
N
let A Iadxd be matrix of (zx) (Zx) then we get
if
A
Z6i
otherwise
Rki
Note that znd is i-th element the vector Zn. By taking expectation terms of 2n over matrix A, get
[1 ifi=j
{= JN (4
0 otherwise
since 2 have zero inverse moment and zero mean as we assumed. Therefore,
E 1 IN (vI(O. B.)
as desired.
Lemma 2. (Second moment of ZO-SGD) In the et - 0 limil, second moment of ZO-SGD in terms of random perturbation vector, which follows Bernoulli distribution of two different values with equal absolute value and probability, That is,
d E Je (1 [(0,; N [V](0:B.)11
(12)
Proof of Lemma 2. Starting from Lemma 1, zeroth-order gradient can be represented as below.
N
(0,;B
(Ov](((;
N
n=1
Therefore, the second moment of zeroth-order gradient
1 W. (1 [(, (.)] = 1=, IN
( AOVS(O0;B.)
N
let _ Raxd be result of (A*) we can get
ifi=j
B
Ed Ei=l
( EngEnn
otherwise
Taking expectation over matrix 8", we can get
= d if=
E 11
(B
0 otherwise
By plugging above results, the second moment of zeroth-order gradient is
E (..,) Yy (0;
[V,(0,
N
as desired.
15

---

Published as a conference paper at ICLR 2025
Lemma 3. With assumption for any unbiased gradient estimate 2f B.).
B(f(O++1)laz) - f(0:) - - 2
n" f0(; BB)
A.2 CONVERGENCE ANALYSIS OF ZEROTH-ORDER OPTIMIZATION
The high variance of zeroth-order gradient estimates stems from the estimation process involving random perturbations, introducing additional problem dimension (d) related terms convergence compared with corresponding first-order (FO) methods. Although the convergence rate was originally proven by Ghadimi & Lan (2013), we have also confirmed similar convergence behavior using Spall (1992) approach. Note that we assumed has zero inverse moment, as it is sampled from Bernoulli distribution of two different values with equal absolute value and probability in practice. The convergence rate of ZO-SGD using (2) is as follows:
Theorem 1 (Convergence rate of ZO-SGD). Under Assumption 1, in the + O limit, when T.dd V where F := f(xo) - f(x.) and sampling the 2n from a Bernoulli distribution of two different values with equal absolute value and probability convergence rate of ZO-SGD is
2NF
d (V
( (0, B.) O
(13)
T
Proof of Theorem 1. With Lemma 1, start from Lemma 3. By assuming that FO-SGD has
finite variance bound as E, | [
S G and reformulate Lemma then we get
1 Er, [f(x)) f(x++1)] + S "
Ld 2N n,.
Summing over from t = =
Ld GT..
Σ
ff [f(xo) Ef(xr)]+
2N
Remind that f is lower bounded with fa and divide with T
V (xx)) < ((xo) - So Ld
T/T +
2N n.
T
Let 17 = O (V
then,
T-1
[f = (V2 d
T t=
16

---

Published as a conference paper at ICLR 2025
B FURTHER ANALYSIS
We conducted additional supplementary experiments to further validate and gain deeper insights into our proposed method, ZIP. To ensure comprehensive analysis, we extended our evaluation to include all remaining standard classification tasks mentioned in Section 5 and 6. This extended evaluation provides a more detailed understanding of the performance of ZIP across a diverse range of datasets.
B.1
IMPACT OF OPTIMIZATION METHODS VARYING CONTEXT TOKEN COUNTS
Caltech101
Caltech101
FO OxfordPets
Z0 OxfordPets
80
Train Accuracy
90.
Train Accuracy (%)
40
Train Accuracy
Tran Accuracy
75
75
4.5
15
40
100
200
20
120
I60
200
40
80 120
100 200
120 660 Epochs
Epachs
Epochs
Epachs
FO Food101
ZO Food101
FO FGVCAircraft
Zo FGVCAircraft
Train Rccurooy (88)
Train Accurary
Train Accuracy
Train Accuracy
75
8
%
60
25
20
120
180 200
120 100
Epochs
Epochs
Epochs
Epechs
FO SUN397
20 SUN397
FO
ZO DTD
Accuracy
85
Train Accuracy
85
Tain Tain Accuracy
1.55
Tain Accuracy
40
35
40
BO
120
100
200
40
120
2000
40
80 120 160 200
260 200
Epachs
Epoche
Epochs
Epochs
FO EuroSAT
ZO EuroSAT
FO UCF101
ZO UCF101
Accuracy
85
Train Accuracy
Itain Accuracy
85
Tain Accuracy
60-
2
60
55 60
25
35
10
40
40
100 zbo
200
Epachs
Epochs
Epochs
FO SVHN
ZO SVHN
FO RESISC45
ZO RESISC45
8
Train Accuracy
Tain Accuracy
Train Accurary
Accurayy
60
60
35
10
200
80 120 40
80
2010
40
80 120 607000
Epachs
Fpochs
Epachs
Epochs
ZO
Train Accuracy
In Accuracy
60-
20 BO 120 IEU
20
90 120 T0O
206
Epochs
Epochs
Figure 9: Effect of optimization methods in prompt tuning across various vision-language tasks.
We conduct series of experiments to examine how varying the number of context tokens affects both first-order and seroth-orde optimization methods across multiple datasets, as illustrated Figure and 9.
17

---

Published as a conference paper at ICLR 2025
Our findings reveal that zeroth-ordes optimization generally performs better with fewer context tokens (e.g.. token). However, certain datasets such as UCF101, SVHN, and CLEVR deviate from this trend. In contrast, first-order optimization typically aligns with the trends shown in Section 3, displaying improved accuracy with a moderate number of context tokens across most datasets, except for SVHN and CLEVR, which demonstrate variations in optimal token counts.
These results suggest that while the optimal number of context tokens depends on the dataset, first-order optimization generally benefits from larger context token count, whereas zeroth-order optimization tends to be more effective with fewer tokens.
B.2 QUERY EFFICIENCY
FGVCAirrraR
EurSSAT
Tain Accuraoy (S)
Tan Recurayy
10
40-
Number Queries
Number Qucries
Number Queries
Number Queries
2 So (h)
Accuruy (80)
1.5
Nimber
ImageNet
Vain
JK
Figure 10: Training curves with 5,000 query budgets across various vision-language tasks.
Figure 4 and 10 display the training accuracy curves of ZIP under a 5,000 query budget across various tasks. Throughout the training process, ZIP consistently demonstrates faster training speeds and achieves higher accuracy compared to other BBPT methods across most datasets, highlighting its capability utilize the available query budget more efficiently.
In Figure 5 and 11, we further analyze the number of API calls required to reach specific accuracy targets across various datasets. The target accuracy is determined as the minimum of the maximum accuracy achieved by all methods. The results indicate that ZIP consistently reaches these accuracy milestones with fewer queries than other methods, underscoring its query-efficient design and adaptability across a diverse range of tasks.
Additionally, in Figure and 12, compare the performance of first-order, zeroth-order optimization, and ZIP across multiple datasets. These results further validate our claim in Section 5.3 that ZIP effectively bridges the gap between first-order and zeroth-order optimization. ZIP not only consistently outperforms standard zeroth-order methods in test accuracy across all evaluated datasets but also frequently surpasses first-order optimization, demonstrating its outstanding training efficiency.
Moreover, we include results for context token m = as reference (See Figure 13), demonstrating that naive zeroth-order optimization with one token often struggles to match the performance ZIP with 8 tokens, particularly in maintaining stable training accuracy. ZIP significantly outperforms the naive method on OxfordPets, FGVCAireraft, EuroSAT, and CLEVR. While the naive method shows comparable results some other datasets, it is worth noting that the first-order method with 8 tokens does not yield substantial improvements over the first-order method with token on 101 OxfordPets, and Food101 (See Figure 9). Additionally, using token performs better
18

---

Published as a conference paper at ICLR 2025
FEVCAIrcratt
SUN397
DTD
2018
4695
2480
2720
843
1197
620
IM7
Number Queries
Number Querles
Number
EuroSAT
UCF101
SVHN
167
2097
4000
833
3647
1127
163
1305
06
200
627
40
Number of Queries
Number Querles
Number of Querles
BackVPP
8PTA/M
tours)
ImageNet
1024
3123
2587
253
1287
529
1690
260
Jk
4t
5k
1k
2X
5%
4k
IK
5K.
Number Queries
Number Quedes
Number Querles
SAR
SlacviP
SPTNUM
2IP teurs)
Figure 11: Queries to reach target accuracy across various vision- languan tasks.
Caktehh011
Flowers102
Food101
FGVCAirrrrft
Tran Accuracy 180.
Then Famuneyy
4X
Number Querries
Namber Dustms
Number Queries
Number Quenss
80
TIN Jec.mac (56)
Toll Accurozy 186
TOi Accurazy
50c
Number RESISC45
Number
Number Querris
SVHNN
CLEVR
Imageflet
Tahn Accurry 156)
Tal Accurcyy 18))
101
20
10
38
Figure 12: Training curves of first-order, zeroth-order and ZIP across various vision-language tasks.
CLEVR and SVHN, highlighting that the optimal number of prompt tokens remains an important factor for performance.
We also conduct an extended evaluation of the performance of ZIP by increasing the API query budget to 20,000, as detailed in Table 6. Several notable insights emerged from this analysis. With 5,000-query budget, ZIP achieves an ImageNet accuracy of 66.2%, performing on par with strong baselines such as Manual Prompt (66.7%) and BLACK (65.5%). When the query budget is increased to 20,000, ZIP further improves its accuracy to 67.2%. surpassing Manual Prompt and BLACK VIP by margins of 0.5% and 0.9%, respectively. These results highlight the ability of ZIP
19

---

Published as a conference paper at ICLR 2025
Ca
OxfordPetts
Flo 202
Food101
Tals fecurerry (N)
Pat Acc.rccoooo
74
Oucrics
QMOrics
FGVCAircraR
SUNS97
EuroSAT
1ain Accuracy
Tain accurcyy
30
15 2k
Number Quericcs UCF101
Number Qucrics
Number Querles
Numbor of Querics
Bain Accurugy (S)
Tain Aenragy
2.54
Number Quercs
Number Queries
Number Que
Numb Queries
ImageNet
tain Acuuug
Figure 13: Training curves of zeroth-order (m 1), zeroth-order (m 8) and ZIP (m 8) across various lision-language tasks.
Table 6: Few-shot performance on 13 vision-language tasks with 20,000 API query budget. All the results based 16-shots per class. The bold numbers denote the highest accuracy of all baselines on each dataset, and the underlined values indicate the second. ZIP consistently outperforms other BBPT baselines, achieving outstanding accuracy across diverse tasks and showcasing its scalability and efficiency under an expanded query budget.
FGVCAirenft
Caltech101
OxfordPPts
Flowers102
Food101
SUN397
SWHN
EuroSAT
Resiso45
CLEVR
UCFI01
ImageNet
Average
DTID
Method
#Params
Manual Prompt
89.1
62.6
44.1
18.8
58.1
14.5
67.5
BAR
37.6k
92.5
88.1
67.7
83.2
23.0
63.8
47.1
32.3
$4.0
64.1
25.4
65.7
65.5
59.4
BLACKVIP
9.9k
93.0
88.0
64.8
85.0
22.5
62.3
44.4
42.3
57.2
57.1
28.8
66.1
BPTVLM
4.0k
91.6
90.3
69.9
85.1
26.3
57.2
50.1
34.4
65.8
63.6
27.8
67.4
61.6
60.9
ZIP
0.4k
94.1
92.4
71.8
86,9
27.3
64.4
52.9
49.9
66.6
68.4
28.6
70.0
67.2
64.7
to leverage additional query budgets effectively, scaling performance significantly with increased resources. Notably, compared to previous work, such as BLACKVIP which achieved 67.1% on ImageNet using substantially higher query budgets (625,000 API queries), ZIP delivers competitive and often outstanding performance using only 20,000 API queries. This demonstrates exceptional efficiency and adaptability of ZIP, particularly in computationally constrained environments.
These supplementary findings reinforce assertions in Section 5.3, confirming that ZIP not only accelerates training but also makes highly efficient use of query budgets, making it exceptionally suited for resource-constrained scenarios.
20

---

Published as a conference paper at ICLR 2025
Table 7: Few-shot performance 13 vision-language tasks with SigLIP (Zhai et al., 2023). All results are based on 16-shot data class. Bold numbers represent the highest accuracy among all baselines for each dataset, while underlined values indicate the second-best, On average, ZiP outperforms other BBPT baselines, demonstrating its strong generalization and adaptability across diverse datasets, even when applied to a vision-language model distinct from CLIP.
PGVCAinena
OxfordPets
Flowers 102
Caltech
Food101
SUN397
EuroSAT
Resise45
CLEVR
LCC1101
InageNer
Average
SVHN
DTD
Method
#Params
85.8
82.2
68.0
58.3
15.2
23.6
42.9
BLACKVIP
9.9k
81.6
78.9
56.6
47.8
9.6
46.3
41.1
30.7
22.5
37.0
26.3
37.0
49.4
43.4
BPTVLM
4.0k
63.9
71.7
47.7
37.2
9.9
35.5
45.6
14.7
44.8
37.0
24.8
35.5
39.5
39.1
82.0
59.3
40.9
48.7
Table 8: Base-to-new generalization performance. H represents the harmonic mean, providing balanced measure of accuracy across seen and unseen classes (Xian et al., 2017). Feature sharing consistently surpasses unshared models in base, new, and harmonic mean evaluations, demonstrating its effectiveness in improving generalization to novel classes.
PGVCAiremai
Caltech101
OxfordPets
Flowers102
Food101
SUN397
SWHN
EuroSAT
Resise45
CLEVR
UCF101
ImageNet
Average
DTD
Method
Set
Unshured
96.3
94.5
68.6
89.9
29.4
67.9
56.6
51.9
81.2
77.4
43,2
72.5
71.0
69.3
Base
Shared
96.6
94,9
72.1
89.9
29.8
70.3
61.7
52,9
84.0
81.6
50.1
75.1
72.1
71.6
Unshared
93.9
71.5
89.5
31.3
47.1
46.1
66.1
25.0
67.4
64.5
63.6
New
Shared
73.4
90.0
32,0
71.5
51.0
45.8
64.4
26.8
69.5
65.0
Unshured Shared
Harmonic
95.1
94.1
70.0
89.7
30.3
69.2
.4
48.8
72.9
67.7
31.7
69.9
67.6
66.0
94.9
95.9
72.8
89.9
30.9
70.9
55.8
49.1
72.9
72.5
34,9
72.2
68.7
68.2
Table 9: Cross-datasct transfer and outtof-distribution generalization performance. After training on ImageNet (i.e.. source) with 16-shot data per class, ZIP is evaluated on 12 target datasets for CDT and 4 ImageNet variants for OOD, Feature sharing consistently enhances transfcrability and robustness, outperforming the unshared models across both CDT and OOD tasks, highlighting its value in adapting to diverse and unseen distributions.
Source
CDT Target
OOD Target
ImsugeNe Skenth
PGVCAircaatt
InsgeNNt
OxfordPets
Flowers102
102
Food101
SUN397
EOOSAAT
Rosset
CLEVE
InsugeNetA
InaggeNet
InsggNer-RR
Awerae
SVHN
10010
DTD
Method
Unshared
65.2
91.3
85.4
64.2
84.2
19.6
58.3
38.1
27.9
46.3
$3.3
17.6
61.3
54.0
45.0
56.6
27.0
B.3 PERFORMANCE ON ALTERNATIVE MODEL FAMILIES.
We extend our evaluation to SigLIP (Zhai et al., 2023), laaguaelanguage model distinct from CLIP. to assess the versatility of ZIP across different model families. The results, presented in Table 7, indicate that while ZIP does not achieve the best performance on all datasets, records significantly higher accuracy several tasks, including DTD, SVHN, EuroSAT, Resisc45, CLEVR, and UCF101. Notably, ZIP achieves the highest average accuracy across datasets, underscoring its robustness and adaptability.
These findings highlight the generality of our method, demonstrating that ZIP consistently delivers strong performance across diverse datasets and model architectures, outperforming existing BBPT methods key scenarios. This reinforces the potential of ZIP as a reliable approach for black-bor box prompt tuning in varied vision-language models.
21

---

Published as a conference paper at ICLR 2025
B.4 IMPACT OF FEATURE SHARING ON GENERALIZATION PERFORMANCE
To further assess the impact of feature sharing on generalization performance, particularly in unseen domains, we conducted experiments with and without feature sharing. The results are presented in Table 8 and Table 9.
From these results, we observe that feature sharing significantly enhances generalization across various tasks. For base-to-new generalization, feature sharing yields substantial performance improve- ments, with average gains of +2.3%, +1.4%, and +2.2% across different datasets. In cross-dataset transfer and out-of-distribution generalization tasks, the improvements are more moderate, averaging +0.2% and +0.3%, respectively.
These findings highlight the effectiveness of feature sharing in improving generalization to unseen datasets, especially in tasks requiring robust representations across varying distributions. While the gains in OOD settings are smaller, they still indicate the potential benefits this approach. Future work will focus an in-depth analysis of the relationship between feature sharing and generalization, aiming to uncover the mechanisms driving these improvements. This could offer valuable insights for broader domain generalization research and practical applications.
B.5 LOW-RANK APPROXIMATION WITH DIAGONAL MATRIX
Ca Caltech101
Flowers102
Food101
FGVCAircraft
Standiard Durs
2,5
4.6
14
2.2
1.4
4.0
1.9
3.4
Quarics
Numbar Queries
Number Quaries EuroSAT
Numbur
SUN397
DTD
UC 103
3.0
2.7
2.0
2.2
2.5
2.5
1.a
Lone
2:0
2.2
Nimber Quiries SVHNN
Number Querles
Number of Querles
Number of
CLEVE
Imagefiet
2.30
2.2
2.15
2.0
1,25
2.0
2.5
2.15
16
2.00
1:
1x. Number Querles
Number of Quefes
Number of Quefles
Mumber Querles
Figure 14: Effects of low-rank approximation with diagonal matrix across various vision- vision-language tasks.
To further validate the effectiveness of our low-rank approximation with a diagonal matrix, introduced in Section 1, we conducted a comprehensive ablation study. This study compares the standard dimensionality reduction technique with our proposed low-rank approximation, evaluated in two settings.
First, we fixed the intrinsic dimensionality at 500 for both the standard method and our approach. However, our method applics an additional low-rank approximation with a diagonal matrix, reducing the parameter size to 417. As shown in Figure 14, this results in improved training speed.
Next, to isolate the effects of the low-rank approximation, we set the parameter size to 417 for both methods, demonstrating that hyper-pau paremeerreeeer size alone is not the key factor driving the efficiency gains. As illustrated in Figure 15, our low-rank approximation method retains core information while reducing parameters, significantly enhancing both training speed and performance.
22

---

Published as a conference paper at ICLR 2025
OdfordPets
Flowers O0
Food100
3.9
Duns
1.4
1.5
2.2
1.44
1.34
1:3
1.3
Number Quaries FGVGAircraft
Number Queries
Number Quercss
SUN397
DTD
EuroSAT
4.5
3.0
2.7
2.0
4.0
2.6
2.5
B 1.6
2.4
1.0
X
Number Quaris
Number Queries
Number of Quariss
Number of Queria
SVHN
RESISC45
CLEVS
2.2
2.25
2.0
2.15
2.0
2.00
Number of Querles
Nummer Queries
Number Quefes
Mumber Queries
Imagetict
2:3
Nurbee of Ovelee
Figure 15: Effects of low-rank approximation with diagonal matrix at fixed parameter size (i.e., 417) across various vision-language tasks.
Table 10: Benefits of low-rank approximation with diagonal matrix. Our method outperforms both
standard dimensionality reduction and LoRA, showing significant improvements in test accuracy.
PGVCAireaaft
Ca
OxfordPets
Flowers112
Food101
SUN397
EuroSAT
Resisc45
CLEVR
UCFI0N
ImageNet
Average
DID
SVIN
Method
Standard
90.9
88.1
67.5
84.6
23.8
57.9
43,2
31.5
56.5
58.3
18.3
65.3
62.3
$7.6
LoRA
90.7
89.3
68.1
85.0
23.7
57.4
43.9
36.0
59.2
57.0
21.2
65.2
62.6
58.4
LoRA Diagonal
90.8
86.0
25.2
59.0
44.4
40.9
60.6
63.3
20.2
67.4
64.8
60.2
Additionally, we compared our technique to the LoRA-style approximation (Hu er al., 2022). Our method, which introduces only parameters in the diagonal matrix, effectively captures essential information from the parameter space, boosting the expressive power of the model without significant parameter overhead. Table 10 presents the test accuracy comparison between our approach. the standard dimensionality reduction method, and LoRA. Our method consistently outperforms both alternatives, demonstrating the clear advantage of integrating a diagonal matrix with low-rank approximation. These findings highlight the effectiveness of our approach in preserving model expressiveness while optimizing parameter efficiency, making a compelling solution for efficient model training.
B.6
CLIPPING
In Figure 16 and 17, we further investigate the impact intrinsio-dimensionall clipping and the effect of varying the optimal clipping threshold across multiple datasets. The results indicate that applying cntrinsic-dimnssionn clipping consistently enhances training accuracy and reduces loss across most datasets, demonstrating its effectiveness in stabilizing the training process.
23

---

Published as a conference paper at ICLR 2025
Caltech10]
OxfordPets
Flowers100
Food 00
88
66
Exponent
Experinn:
Expoment
Exporenc EumSAT
#CVCAircraft
SUN397
DTD
Aucurriy (Sc
Tard Prrunayy (14)
Tos Jocuratyy (36)
20
92
Expoment K
Exponenc
Exporenex
Exponentc
70
Tist Socura Mhi
12
33
13
12 30
ImageNet
Teat Accurcc
Exponont
Figure Effects of optimal threshold across various vision-language tasks.
61
3.
3.6
25
62
Twln Accumcy
50
3.0 Clasing
Acomnry
1.3
Ewe Acronry
4.5
Spal Lona
Bair Acunayy (60
Eo
Numbar
DTD
EuroSAT
UCF101
SVHN
Train MainnAcca Racuracc 194
Thin Aecuracy
Iaiir Losa
20
Than
Thin
2
2.0
22
12
1x
dk
3K
4k
Number Querles
Number of Queres
Number Querles
Number Querees
ImageNet
Tran Acuursy (9)
(96)
20
Paintsg
Fran
Tatn
Train
Quarries
Number
Figure 17: Efffett of intrinsic-dimensionall clipping across various vision-language tasks.
24

---

Published as a conference paper at ICLR 2025
Table 11:
Few-shot performance on vision-language tasks with varying combinations of the proposed modules (e-g., diagonal matrix, feature sharing (FS), and mutrnsic-dimmnnionne clipping). All the results are based on 16-shots per class. The bold numbers denote the highest aceuracy of all baselines each dataset, and the underlined values indicate the second.
PGVCAireaa
Caltecht01
OxfordPets
Flower100
Food
SUN397
SVHN
FurnS
Resio445
CLEVR
UCF100
ImageNes
Average
DED
Number
Diagonal
F$
Clipping
91.2
82.3
56.9
83.4
13.2
56.8
41.0
38.9
58.8
58.5
23.1
64.4
61.5
56.2
90.1
89.3
65.3
84.6
22.7
60.6
42.4
38.4
59.3
59.8
18.9
66.7
63.4
58.6
90.7
89.3
68.1
85.0
23.7
57.4
43.9
36.0
59.2
57.1
21.2
65.1
62.6
58.4
58.9
44.9
61.2
59.2
64.8
x
89.8
89.5
66.4
85.3
25.
58.5
44.7
38.3
61.0
58.9
18.9
65.9
63.4
58.9
86.0
40.9
67.4
V
93.4
91.7
70.0
86.3
26.6
62.2
47.8
44.2
64.2
65.2
25.1
69.8
66.0
62.5
When evaluating test accuracy with varying gradient clipping thresholds, ZIP achieves near-optimal performance across the majority of datasets, consistently outperforming cases where no gradient clipping is applied. Although there some exceptions, such SVHN, DTD, and CLEVR. where gradient clipping does not yield significant improvements in test accuracy. the results remain comparable to ZIP without clipping, indicating that the technique does not hinder performance in these cases.
These findings substantiate that our intrinsic-dimensionn clipping approach significantly improves the overall performance of zeroth-order optimization, and the selected vō threshold effectively serves as reliable and practical choice for enhancing training efficiency.
B.7 ANALYSIS OF MODULE COMBINATIONS
We evaluate all combinations of the proposed modules, including diagonal matrix, feature sharing (FS), and citiisic-dimensionall clipping. The results are presented in Table 11. First, we observe that using all the proposed modules together results in significantly better performance compared using individual modules or pairs of modules. This demonstrates that each component works harmoniously to contribute to the generation of effective results. Additionally, from the transitions 6, 4 and 5 - 7, we find that combining the low-rank approximation with diagonal matrix with intrinsic dimensional clipping yields more pronounced performance improvements (+4%, +4.5%, +3.6%) compared to other combinations. These findings suggest that while each component is effective on its own, their combination creates a complementary synergy that maximizes overall performance. In future work, plan to conduct behind this synergy. This will provide deeper insights into its practical utility, paving the way for its application broader range of tasks.
in-depth analysis to uncover the underlying mechanisms
B.8 SIGNIFICANCE TEST OF ZIP
To ensure the robustness of our results, we conduct statistical significance analysis comparing ZIP and competing methods. While the average CDT accuracies of ZiP and the second-best method, BLACKVIP, appear close (Table 3), we extend the evaluation using 10 random seeds (1-10) to provide more reliable conclusions. A t-test was then perform compute p-values for statistical significance. The results reveal that ZIP demonstrates statistically significant improvements in OOD tasks, while its performance CDT tasks comparable to BLACKVIP Detailed results are presented in Table 12 and Table 13.
In CDT tasks, ZIP achieves statistically significant improvements on specific datasets such as Flowers (p 0.009). Food101 (p 0.008). SVHN (p 0.018), and EuroSAT (p 0.003). Conversely, BLACK VIP shows significantly higher performance on Aircraft (p = 6.45e - 08), DTD 0.023), and UCF101 (p 0.016). These findings underscore that
(p 3.87e 04), CLEVR while ZIP delivers strong and consistent performance, dataset-specific characteristics can influence the effectiveness of each method.
In OOD tasks, ZIP consistently outperforms BLACKVIP average performance (ZIP: 56.82%, BLACK VIP: 54.47%). Statistically significant improvements observed on ImageNet-A (p
25

---

Published as a conference paper at ICLR 2025
Table 12: Cross-datasee transfer performance comparison between ZIP and BLACKVIP including significance test results. The p-values from t-tests highlight statistically significant differences on specific datasets. ZIP demonstrates notable improvements in query efficiency and aceuracy on datasets like Flowers and EuroSAT, while BLACKVIP excels in others such as Aircraft and DTD.
Target
LongeNer
Caltech101
OxfordPes
Plowers122
Food
SUN397
EboSAT
Resio45
CLEVR
LCF
Average
DTD
Method
BLACKVIP
65.19
92.69
86,28
64.72
83.36
22.31
62.04
42.88
17.68
39.71
55.98
15.70
64,07
$4.82
91.69
39.39
54.65
t-stats
1,745
-1,879
-0.690
2.942
2,974
-8.771
-2.755
-4.349
2,615
3.409
-1,588
-2.479
-2,650
potauee 0.998
0.076
0.498
0.009
0.008
6.45e-08
0.013
3.87c-04
0.018
0.003
0.130
0.023
0.016
Table 13: Out-of-distributiio (OOD) generalization performance comparison between ZIP and
BLACKVIP including significance test results. The p-values from t-tests reveal statistically signif- icant improvements by ZiP on datasets such as ImageNet-A, ImageNet-R, and ImageNet- mnaeehet-Sketch demonstrating its robustness under domain shifts. While ZiP achieves higher average performance, the results on ImageNetV2 show comparable performance with no statistical significance.
Source
OOD Target
ImageNet Sketch
ImageNct-A
ImageNerva
ImageNer-RR
ImugeNet
Average
Method
BLACKVIP
65.19
41,90
58.85
72.81
44.32
54.47
ZIP
65.91
47.94
59.48
74.64
45.25
56.82
1.745
10.299
1.549
4.359
2.619
p-valuu
0.098
5.66c-09
0.139
3.78e-4
0.017
5.66e 09), ImageNet-R (p 3.78e - 4), and ImageNet-Sketch (p 0.017). For ImageNetV2, the performance difference (p 0.139) is not statistically significant, suggesting similar performance on this dataset.
The strong generalization performance of BLACKVIP stems from its image- dengeede prompting strategy, drawing from prior works like CoCoOp (Zhou al.. 2022a). This design is tailored to improve generalization capabilities. In contrast, ZIP focuses on query efficiency, making it particularly effective in scenarios with limited API budgets. Despite differing objectives, ZIP demonstrates superior performance in OOD and base-to-new generalization tasks, while maintaining competitive performance in CDT tasks. These results highlight the balanced capabilities and adaptability ZiP across various generalization settings.
B.9 VALIDATION ACCURACY
To evaluate the generalization capability of ZIP and verify that it does not overfit, we report validation accuracies corresponding the training results presented in Figure 4, 6, and 17. These are illustrated in Figure 18, 19, 20, and Figure 21.
Across all datasets and experimental settings, the validation accuracy trends closely mirror the training accuracy, demonstrating consistent performance and negligible signs of overfitting. Notably, for zeroth-order optimization (Figure 20), the validation results confirm the stability and efficiency the query- query-efficient design of ZIP. Similarly, the validation outcomes for intrinsic-dimensions clipping (Figure 21) highlight the effectiveness of the Vo threshold in enhancing both training and validation accuracy without introducing instability.
These findings provide strong evidence of robustness of ZIP, showing that it maintains reliable performance across both training and validation datasets. This underscores its generalization ability and query efficiency, further validating its applicability across diverse vision-lane language tasks, even under resource constraints.
26

---

Published as a conference paper at ICLR 2025
FO Caltech101
70 Caltech101
OxfordPets
20 OxfordPets
Waterten Aetuwry
75
75
15-
60
60-
60
80-
10
T20
120
200
160
160 Epochs
80 120
200
Epochs
Epachs
Flowers102
20 Flowers102
Food101
Zo Food101
83
900-
Suucon Accunay
14 Aemuary
60
25-
60
60-
25
20
10
20
so 120 160 zóo
40
120
180
260
40
120
200
FGVCAircraft
FGVCAircraR
FO
SUN397
885-
Ueicaton Arouneyy (kg
60-
60
25
100
10.
10
40
50 120 100 200
20
120
200
40 120 Epochs
160 200
40
120
Epochs
Epochs
FO DTD
ZO DTD
FO EuroSAT
20 EuroSAT
95
Widtton Acturary (S4)
53
40
80-
33
13
35+
1.
20-
40
120
160 200
40 120
zúo
40
80
120
160 200
120 160 200 Epochs
Epechs
Epochs
Epochs
FO UCF101
ZO UCF101
FO SVHN
ZO SVHN
196)
Wiltern Aecurnty 190)
Acouray
60
600
60-
33
35-
10
20 120 160 200
40 60 120
700
40 1ua Epachs
16a 200
40 80 120 160 700
Epechs
Epochs
Epochs
FO RESISC45
ZO RESISC45
FO CLEVR
ZO CLEVR
1oo0x-00 on Acoraar (9)
rokion Aecuunyy (h))
60
80
60
on
1
20
20
80 20 160 Epochs
200
60
00
120
100
260
120 200
00 120 40
360 200 Epochs
Epochs
Epochs
Figure 18: Validation curves illustrating the performance of different optimization methods across various vision-language tasks. The black dotted line represents trainable parameters (m 0, i.e., only the [CLASS] token), serving as a baseline for comparison.
27

---

Published as a conference paper at ICLR 2025
OxfordPets
Flowers] 07
Saston Acouracy (N0
877
30
60
52
Number
Queries
RGVCAireaaft
SUN399
DTD
EurOSAT
Saldetteon Auruveey 110
laldii Acc: Accurroc thg
21
30
1.0
20
33
28
46
1%
26 3
4K
3K
16
46
16.
46
50
UCF101
SVH-N
Resiso45
CLEVR
doten Accuracy (8)
Val cottin Acc upoc (8))
Mattee svery
23
46
15
3K
46
15.
15.
4%
Qusees
Number
Quanii
ImageNet
Numberr of QQuer
Figure 19: Validation curves under 5,000 query budget across various vision-language tasks, show- casing ZiP's efficient utilization of limited queries achieve competitive performance, The results demonstrate consistent validation trends, reflecting ZIP's robustness and generalization capabilities.
28

---

Published as a conference paper at ICLR 2025
Caltech111
OxfordPets
Flower1022
Food101
Mat en Accursoy PN6
on
1x
1x 2X dk
Number of Queries
Number Dusris
Number Querles
Number Quenas
770
sne on Arr Aeruraryy (51)
luz Accursor 18)
15
dx
Number of Querees
Number Queries SyliN
Number Queries
Number of Queries
UCF103
RESISC85
CLEVR
444
V6 Moran Accursoy B9
23
05
15
68
Number
Imagehett
Vi soicin Accuree
40
55
2x
18
Figure 20: Validation curves comparing first-order, zeroth-order, and ZIP optimization methods across various vision- tasks. ZIP bridges the gap between first-order and zeroth-order optimization, maintaining stable validation accuracy while achieving better generalization compared to standard zeroth-order methods.
29

---

Published as a conference paper at ICLR 2025
Calted1011
OxfortPets
Flowers102 00
Food10)
We dedert Parurayy (M)
100 Laldda Accursoy (8))
91-
60
Cippree Oliping
3K 4%
2x 31
4%
1K:
1k. 2x ik de Number Queries
Number Querress
Number Ducries
Number Querles
FGVCAArrraf
SUNB97
DTD
EumSAT
Gaaan Accurco
33
Jk Number of Queress
Number Querics
Number Queries
Number Queries
dettoo Arnuracy (N)
10 da Accursoy (8)
60
Goc
12
Number
Number
ImagaNet
Va dation Acuurco
10
11 25
JK
Figure 21: Validation curves illustrating the impact of zeroth-order gradient clipping on various vision- language tasks. The results emphasize the effectiveness of the vo threshold stabilizing training and improving validation accuracy, confirming its utility in zeroth-order optimization scenarios.
30

---

Published as a conference paper at ICLR 2025
C EXPERIMENT DETAILS
C.I ALGORITHM
Algorithm 1: The training process of ZIP.
Input:
The training data D { }s), pre-trained CLIP model g. projection matrix
{ [M, Jim fimm learnable parameters of each context token 6, gradient clipping threshold 8, context token counts m, number of gradient estimates N for N-SPSA. smoothing parameter c, batch size B, and API call budget T.
Function f (E,; X)
Calculate the original token parameters O₁
for to m do
| 0,, = fo. + M,W;
end
Forward propagate through CLIP model with reconstructed tokens g( X) return g
Function N-SPSA (E,, N, X):
for n to N do
Sample Uniform(0, 1). with ensuring a is not
Sample 2, Bernoulli(a 0.5, -a 0.5)
Calculate the first loss ʃ(=; + cZn; X)
Calculate the second loss f(E, - CZn; X)
Calculate the nith gradient estimation
V (E,; X) f(E,+o,, X] - (1) cz (zn) 1m
2c
end
Calculate N-SPSA gradient estimation VS(E;)) = N E (E,)))))
return /E{;;
Initialize Eg. Uu, So. Vo
for / to T/2N do
for each training mini-batch X, Y do
Calculate the weight matrix E, = [ur, / ... |w,,,] U,diag {;) V + u @
Calculate the gradient estimation fE X) using N-SPSA (E, c, N, X)
Calculate the clipping coefficient ag min( VE-= 4
v6
Gradient descent using clipping Et41 E. - a) f(E,)
end
end
During the training process, our method, ZIP, initiates by calculating the low-rank approximation and integrating shared feature representations. These approximations are subsequently utilized to reconstruct the original parameter space through random projection, allowing ZIP to generate the prompt representations necessary for loss computation efficiently. To ensure clarity and provide a comprehensive understanding of the training procedure, the summarized training algorithm can be found in Algorithm 1, which outlines each stage of the process for easy reference.
C.2 COMPARISON OF BLACK- BOX SETTINGS IN VLMS
Our work builds upon the Language-moded as----ice (LMaaSS) framework (Sun et al., 2022b), which envisions large language models as services accessible via APIs. This paradigm has attracted significant attention in previous studies as a practical and flexible setting for black-box prompt tuning (Sun et al., 2022b; Yu et al., 2023). In the LMaaS framework, models are treated as opaque systems, and users fine-tune them through external signals-an such as logits or losses without requiring direct access the internal parameters. Moreover, the LMaaS framework accepts soft prompt inputs, further enhancing its adaptability. Although current models like ChatGPT (OpenAI, 2023) and Gemini (Google, 2023) do not yet support this specific configuration, the LMaaS approach
31

---

Published as a conference paper at ICLR 2025
Black-box Assumption
Method
Access Permission
Prompt Type
BAR (Tsai et al., 2020)
Loss
Hard
BLACKVIP (Oh et al., 2023)
Loss
Hard
BPTVLM (Yu et al., 2023)
Loss
Soft
LFA (Ouali et al., 2023)
Logits
Hard
CraFT (Wang et al., 2024)
Logits
Soft
ZIP (ours)
Loss
Soft
Table 14: Comparison of black-box assumptions. We compare our setting with prior methods in terms of access permission and prompt type.
establishes a foundation for future methods that emphasize flexible, efficient, and secure fine-tuning of black-box models.
As detailed in Table 14, our approach adheres to black-box setting where only loss values are accessible while soft prompts are utilized. This design is particularly advantageous as avoids the need for accessing logits, i.e., type of sensitive information that should ideally remain concealed for security and privacy reasons. In contrast, methods such as LFA (Ouali et al., 2023) and CraFT (Wang al., 2024) rely on logits, which raises concerns model confidentiality and may not be feasible in many real-world API scenarios. By leveraging closely practical constraints and fosters the development of robust optimization strategies capable of deriving meaningful insights from limited information.
feedback, our method conforms more
C.3 DATASET DETAILS
Classification Tasks
Dataset
#Train
#Valid
#Test
Classification Type
Manual Prompt
ImageNet
1,28M
N/A
50,000
Generic object
"a photo of [CLASS]]"
Caltech101
4.128
1,649
2,465
Generic object
"a photo of a [CLASS]."
OxfordPets
2,944
736
3,669
Fine-grained objects
"a photo a [CLASSS] a type of pet."
Flowers102
4,093
1,633
2,463
Fine-grained objects
"a photo of [CLASS]. type flower."
Food101
50,500
20,200
30,300
Fine-grained objects
"a photo of [CL (CLASS), type of food."
FGVCAirerat
3,334
3,333
3,333
Fine-gruined objects
"a photo of a [CLASS]. a type of aireruft."
SUN397
15,880
3,970
19,850
Scene
"a photo [CLASSS].
DTD
2,820
1.128
1.692
Text
"[CLASS] texture."
SVHN
73,257
26,032
26,032
Digit
"This is photo of a (CLASS)."
EuroSAT
13,500
5,400
8,100
Satellite
"a centered satellite photo of a (CLASS)."
Resisc45
6,300
2,520
7,560
Scene
"This photo of [CLASS]." "This is photo of [CLAASS] objects."
CLEVR
70,000
15,000
15,000
Diagnosis
UCF101
7,639
1 1,898
3,783
Action
"a photo of a person doing (CLASS)]"
ImageNetV2
N/A
N/A
10,000
Generic object
"a photo of [CLAASS].
ImageNet-Sketeh
N/A
N/A
50,889
Sketch image
"a photo
[CLASS]."
ImugeNet-A
N/A
N/A
7,500
Adversurially filtered image
"u photo of [CLASS]."
ImageNet-R R
N/A
N/A
30,000
Cartoon, Sculptures, Paintings
"a photo of a [CLASS]]"
Table 15: The datasets used in this study, along with the corresponding manual prompts. Samples are drawn exclusively from the original training set to ensure consistency with baseline data.
In this study, we leverage a total of 13 general classification datasets and 4 out-of-distribution (OOD) datasets, widely used in prior research. These 13 classification tasks are employed to comprehensively evaluate the performance of ZIP in general few-shot learning, base-to-new generalization, and cross- dataset transfer scenarios. Additionally, the 4 OOD datasets are used to rigorously assess the ability of ZIP to handle -ot-ttiiittiiitoi generalization. A detailed overview of each dataset, including task descriptions and evaluation metrics, is provided in Table 15.
C.4 HYPER-PAR SATER-PARAMTTERR
To achieve stable and accurate gradient approximations, zeroth-order optimization algorithms typi- cally perform multiple gradient estimations, with the results being averaged obtain a more reliable
32

---

Published as a conference paper at ICLR 2025
Hyper-parameter
Assignment
Method
initial LR
{40.0, 20.0, 10.0, 5.0, 1.0)
BAR
initial LR (a1)
{1.0, 0.1, 0.01, 0.005)
BLACKVIP, ZIP
min LR
{0.1. 0.01, 0.0013
BAR
decaying step
{0.9, 0.5, 0.1}
BAR
LR decaying factor
{0.6, 0.5, 0.4, 0.3)
BLACKVIP, ZIP
initial PM (ci)
{0.01. 0.005, 0.001)
BLACKVIP, ZIP
PM decaying factor
(0.2, 0.1)
BLACKVIP, ZIP
std. of perturbation
[1.0, 0.5}
BAR
smoothing
{0.1, 0.01, 0.0013
BAR
gradient smoothing
{0.9, 0.7, 0.5, 0.3}
BLACKVIP
population size
(5, 10, 15, 20}
BPTVLM
intrinsic dimensionality
(500, 1000, 2000}
BPTVLM, ZIP
rank
31.3.5)
ZIP
visual tokens
{5. 10)
BPTVLM
text tokens
{5, 10)
BPTVLM
Table 16: Hyper- papee-prrreeter search range for BBPT approaches.
gradient estimate. Following the methodology outlined in Oh al. (2023), repeat this gradient estimation process five times for all zeroth-order-based baselines to ensure consistency and robustness. For SPSA methods, tune key hyper syper-parameters, including the perturbation magnitude and decay factor. For evolutionary strategies, we adjust the population size, intrinsic dimensionality, and the number of visual and text tokens. The search ranges for these hyper-parametters are based the recommendations provided by the authors BAR (Tsai et al., 2020), BLAACK (Oh et al., 2023), and BPTVLM (Yu et al., 2023), and are summarized in Table 16. Regarding the learning objectives, cross-entropy loss is employed for BLACKVIP and BPTVLM, while focal loss is used for BAR. All BBPT experiments utilize batch size of 128 across all datasets, ensuring consistent and comparable evaluation.
C.5 BASELINE DETAILS
C.5.1 ZERO-SHOT CLIP
CLIP (Radford et al., 2021) is a prominent vision-language foundation model widely employed across various tasks, such as classification, segmentation, and other vision- lision-language applications. Trained on large-scale image-text datasets, CLIP has demonstrated exceptional effectiveness in numerous downstream tasks, thanks its ability to leverage visual concepts learned from natural language supervision. It performs zero-shot classification using manually crafted prompt templates (e.g.. "a photo of a (CLASS].). Due to its versatility and strong performance, CLIP serves as the backbone for many black-box prompt tuning models, including our proposed method, ZIP.
C.5.2 BAR
Originally developed for transferring knowledge from an ImageNet pre-trained model to the medical domain, BAR (Tsai et al., 2020) reprograms pre-trained models using a frame-shaped, learnable program that embeds the target task image within this frame and optimizes it via zeroth-order algorithms. The size of this learnable program adjusted based on the input image resolution. For example, in the original study, when the resolution of the downstream image was larger than that of the pre-trained model, an embedded target image size of 64 x 64 was used within a 299 x 299 learnable program. In contrast, BLACK VIP (Oh al., 2023) modified this approach by designing image resolution of 194 x 194 to avoid performance degradation caused by the heavy- seaviinadding of thin images within the prompt. In this paper, adopt the settings established by BLACKVIP (Oh et al.,
embedded
33

---

Published as a conference paper at ICLR 2025
2023) when optimizing BAR, ensuring consistency and addressing the limitations of the original design.
C.5.3 BLACKVIP
BLACKVIP (Oh al., 2023) generates input-conditional visual prompts for each image via projec- tion network, allowing prompts to adapt dynamically to the specific features of each input. For the optimization process, BLACK VIP employs Simultaneous Perturbation Stochastic Approximation with Gradient Correction (SPSA-GC), which integrates Nesterov Accelerated Gradients (NAG) (Nesterov, 1983), enhancing the efficiency zeroth-order training. Unlike other methods such as CoCoOp (Zhou al., 2022a), which optimize additional input-attached parameters, BLACK VIP focuses exclusively on the projection network, effectively creating adaptive, input-conditioned visual prompts for BBPT tasks. While this design choice makes BLACK IIP highly adaptable and well-suited for black-box settings, the large number of parameters introduced by the projection networks can negatively impact training efficiency, posing challenge in cesuurce-onstrrained environments.
C.5.4 BPTVLM
BPTVLM (Yu et al., 2023) utilizes evolutionary strategies for BBPT, distinguishing itself from previous approaches. In this method, BPTVLM introduces learnable parameters into both text and image prompts, enabling more comprehensive adaptation various tasks. To enhance efficiency, BPTVLM incorporates the concept of intrinsic dimensionality, reducing the overall number of learnable parameters by applying a random projection matrix both text and image prompts. This approach effectively balances adaptability and parameter efficiency, making BPTVLM a more versatile option for BBPT scenarios.
34


Reviews:
[{"review_id": "T5cH8zHfJM", "reviewer": "Reviewer_BGp2", "summary": "The paper introduces ZIP for efficient zeroth-order prompt-tuning of black-box vision-language models. ZIP addresses the challenge of excessive query requirements in existing black-box prompt-tuning methods by reducing problem dimensionality and gradient estimate variance through feature sharing and intrinsic-dimensional gradient clipping. ZIP demonstrates significant improvements in few-shot accuracy and query efficiency over other existing methods. Various experiments on image classification show the effectiveness of ZIP.", "questions": "See weaknesses.", "limitations": "", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- ZIP is well-motivated.\n- The paper is well-organized.\n- Empirical analyses of the proposed method are sufficient.", "weaknesses": "I'm not familiar with this research field, i.e. black box prompt tuning. Therefore, it's hard for me to accurately judge the novelty of the proposed method compared with existing works. \n\nFrom my perspective, one major weakness is that I find the competitors in the experiments are slightly old, e.g. BLACKVIP is published at CVPR'23 and BPTVLM is published at IJCAI'23. There are some more recent works like [a][b] in this field. I think the authors should better discuss the differences between ZIP and more recent works like [a][b], and provide fair experimental comparisons as well. \n\n[a] Language Models as Black-Box Optimizers for Vision-Language Models, CVPR 2024, https://openaccess.thecvf.com/content/CVPR2024/html/Liu_Language_Models_as_Black-Box_Optimizers_for_Vision-Language_Models_CVPR_2024_paper.html\n[b] Connecting the Dots: Collaborative Fine-tuning for\nBlack-Box Vision-Language Models, ICML 2024, https://arxiv.org/abs/2402.04050", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pXpJqo6Mik", "reviewer": "Reviewer_Tcth", "summary": "The paper proposes a method to optimize black-box models without the need for computing gradients (zeroth-order). The key observation is that increasing the number of learnable parameters in soft prompts hurts the performance and training speed of zeroth-order optimization, while this trend is reversed for SGD-based prompt tuning (first-order). To overcome this, authors propose to reparameterize soft prompts in order to reduce the effective number of learnable parameters while maintaining the extrinsic embedding dimensionality. The proposed reparameterization involves projecting parameters into a diagonal matrix, feature sharing and gradient clipping. In addition, reducing the number of learnable parameters results in increased query efficiency (reduced number of forward passes through the model). The proposed method is applied to black-box prompt-tuning of a CLIP model, and evaluated on a suite of standard vision-language benchmarks, achieving improvements of 6% in few-shot accuracy and 48% in query efficiency compared to the best performing existing methods.", "questions": "* It is not until the background section that I understood what zeroth-order intrinsic-dimensional prompt-tuning means. I suggest to improve the introduction to make it clearer from early on.\n* In figure 2, it would be good to add a baseline of accuracy when no soft prompts are optimized (i.e. m=0).\n* Where are the learned soft prompts injected? Are they concatenated to text embeddings and fed to CLIP's text encoder?\n* In table 3, the average accuracies for CDT between ZIP and the second-best method seem very close. Did authors run a significance test?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "* Good motivation to reduce the number of learnable parameters in ZO optimization (section 3) and clever idea to reduce the intrinsic dimensionality while maintaining the number of tokens (and the extrinsic dimensionality, which is a requirement from the model being optimized).\n* Several techniques (diagonal matrix, parameter sharing) are applied to preserve performance while reducing the number of learnable parameters.\n* The proposed method not only improves few-shot performance wrt existing ZO methods but also reduces considerably the number of function evaluations required to reach a certain level of performance (section 5.3).\n* All the design choices for the soft prompt reparameterization are thoroughly ablated in section 6.\n* The paper is clearly written and easy to follow.", "weaknesses": "* Authors motivate fine-tuning black-box models with the use case of improving proprietary LLMs (e.g. GPT-4, Gemini) which are only accessible through API. However, this interface only accepts text and images as input, not soft prompts or embeddings, so the proposed method would not be directly applicable to API-based models.\n* To verify the method's robustness and generality, it should be evaluated on other model families such as multimodal LLMs.\n* Figures 2, 4, 6 and 7a should report validation accuracy since there could be overfitting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YgzhtrdLwf", "reviewer": "Reviewer_Fqbz", "summary": "The paper introduces ZIP, a zeroth-order prompt tuning method designed for efficient prompt optimization in black-box vision-language models, particularly under limited query budgets. ZIP achieves high efficiency by using low-rank representations and intrinsic-dimensional gradient clipping, which reduces query usage while maintaining robust performance. Evaluations on multiple benchmarks show that ZIP not only outperforms state-of-the-art methods in accuracy but also greatly enhances query efficiency.", "questions": "(1) In Section 4.2, the paper introduces feature sharing to enhance expressiveness. Could the authors clarify whether this feature sharing technique affects the generalization ability on unseen datasets, and if so, how?\n\n(2) ZIP has demonstrated strong results across vision-language tasks, but could the authors provide more insights into its potential for domain generalization? Specifically, how well does ZIP adapt to unseen domains or datasets outside the evaluated benchmarks, and would any adjustments be necessary to improve its robustness in such scenarios? Such as CoOp and CoCoOp.  \n\n(3)  Could the authors elaborate on the sensitivity of ZIP to the choice of intrinsic dimensionality and low-rank approximation parameters? How do these choices impact both performance and query efficiency?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "(1) The paper is well-organized and accessible, with clear visuals and structured explanations that effectively communicate the method's strengths.\n\n(2) ZIP innovatively enhances zeroth-order prompt tuning through intrinsic-dimensional gradient clipping and low-rank parameterization, making it highly efficient.\n\n(3) Comprehensive evaluations demonstrate ZIP's superior accuracy and query efficiency across 13+ tasks, proving its practical value under query constraints.", "weaknesses": "(1) While ZIP outperforms existing BBPT methods, comparisons with additional baseline methods in zeroth-order optimization could strengthen claims of superiority.\n\n(2) While ZIP shows strong performance on various tasks, its results on ImageNet in Table 1 are comparatively modest, suggesting limitations in scalability to complex datasets. An in-depth analysis of ZIP's performance on larger, diverse datasets would clarify its robustness and potential for broader application.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "X44QHK1RSH", "reviewer": "Reviewer_NLRG", "summary": "This paper introduces ZIP, a zeroth-order intrinsic-dimensional prompt-tuning method designed to efficiently optimize black-box vision-language models. By leveraging low-rank approximation, feature sharing, and intrinsic-dimensional gradient clipping, ZIP achieves faster training speeds and superior generalization performance while significantly reducing query requirements. Extensive experiments on diverse tasks demonstrate ZIP's robustness and query efficiency, outperforming existing BBPT methods and establishing it as a practical approach for resource-constrained scenarios.", "questions": "Suggestions: \n\nThe caption for Figure 1 should include citations for the baseline methods (BAR, BlackVIP, BPT-VLM) to provide appropriate references and context for these comparisons. This would enhance clarity for readers unfamiliar with these specific methods.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.The paper presents a novel black-box prompt-tuning method, effectively addressing the issue in zeroth-order methods where an increase in trainable parameters adversely impacts accuracy. By reducing the number of parameters and query requirements, the proposed approach is well-suited for practical applications with limited query budgets.\n\n2.The paper demonstrates strong performance across three extensive and diverse experimental settings, which effectively validate the method’s efficacy. The ablation studies further support the approach, particularly highlighting that the feature-sharing technique helps preserve the model’s expressive capacity.           \n\n3.The intrinsic-dimensional clipping mechanism in ZIP requires no manual hyperparameter tuning, making it highly practical and user-friendly.    \n\n4.The paper is well-written, with clear explanations and logical organization that make the proposed method and its contributions easy to understand.", "weaknesses": "1.Although the paper performs ablation studies on individual modules such as  low-rank approximation with a diagonal matrix and feature sharing, it lacks ablation experiments on different combinations of these modules.   Without evaluating different combinations, it is challenging to fully understand the synergistic effects and the relative contributions of each module to the overall performance.      \n\n\n\n2.The paper lacks an ablation study to isolate the effect of low-rank approximation alone, making it unclear if improvements are mainly due to the diagonal matrix. This analysis would clarify the diagonal matrix's contribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)