Bilevel ZOFO: Efficient LLM Fine-Tuning and Meta-Training
Authors: Reza Shirkavand
Peiran Yu
Qi He
Heng Huang
Venue: NeurIPS 2025 poster ()
Keywords: arge language model
Multi-Task Learning
Zeroth-order Fine-tuning
Parameter Efficient Fine-tuning
Primary area: deep_learning

Abstract: Fine-tuning pre-trained Large Language Models (LLMs) for downstream tasks using First-Order (FO) optimizers presents significant computational challenges. Parameter-Efficient Fine-Tuning~(PEFT) methods have been proposed to address these challenges by freezing most model parameters and training only a small subset. While PEFT is efficient, it may not outperform full fine-tuning when high task-specific performance is required.
Zeroth-Order (ZO) methods offer an alternative for fine-tuning the entire pre-trained model by approximating gradients using only the forward pass, thus eliminating the computational burden of back-propagation,
% in first-order methods, 
but they converge painfully slowly and are very sensitive to the choice of task prompts.
We bridge these worlds with Bilevel‑ZOFO, a penalty‑based bilevel formulation that treats adapter parameters as a lower‑level learner coupled to an upper‑level ZO optimizer of the full backbone. This double-loop optimization strategy only requires the gradient of the PEFT model and the forward pass of the base model. We provide theoretical convergence guarantees for Bilevel ZOFO. Empirically, we demonstrate that Bilevel-ZOFO significantly outperforms existing ZO methods, achieves 2–4$\times$ faster training, and reduces sensitivity to prompts. Bilevel-ZOFO also outperforms FO PEFT methods while maintaining similar memory efficiency. Additionally, we show its strong potential for meta learning.

Bilevel ZOFO: Efficient LLM Fine-Tuning and Meta-Training
Reza Shirkavand
Peiran Yu
Department of Computer Science University of Maryland- College Park rezashkvocs. umd edu
Department of Computer Science and Engineering University of Texas Arlington peiran. yu@uta. edu
Qi He Department of Computer Science University of Maryland College Park qhe1230cs. umd. edu
Heng Huang"
Department Computer Science University of Maryland College Park heng@cs umd. edu
Abstract
Fine-tuning pre-trained Large Language Models (LLMs) for downstream tasks using First-Order (FO) optimizers presents significant computational challenges. Parameter-Effiiiee Fine- Tuning (PEFT) methods address these by freezing most model parameters and training only small subset. However, PEFT often un- derperforms compared to full fine-tuning when high task-specific accuracy is required. Feroth-Order (ZO) methods fine-tune the entire pre-trained model with- out back-propagation, estimating gradients through forward passes only. While memory-efficient, 70 methods suffer from slow convergence and high sensitivity prompt selection. We bridge these two worlds with Bilevel-ZOFO, bilevel optimization method that couples fast, local FO-PEFT adaptation at the inner level with stable, memory-efficiiee ZO updates of the full backbone at the outer level. The FO-PEFT inner loop performs fast, low-memory local adaptation that reduces the variance of ZO estimates and stabilizes the search, guiding the outer ZO up- dates of the full backbone and reducing prompt sensitivity. In the mean time, the outer ZO provides better generalization ability for PEFT. We provide theoretical convergence guarantees and empirically demonstrate that Bilevel-ZOFO signif- icantly outperforms existing 70 and FO-PEFT methods, achieving 2-4x faster training while maintaining similar memory efficiency. Additionally, we show by updating the backbone with ZO and adapting only tiny FO-PEFT block per task, Bilevel-ZOFO combines full-model capacity with few-shot efficiency, making it very efficient meta- lecanlea algorithm that quickly adapts to new tasks.
Introduction
Fine-tuning pretrained Large Language Models (LLMs) has become standard approach for down- stream tasks. Traditional First-Order (FO) optimizers like Adam (20. commonly used for this process, rely on backpropagation. However, as highlighted Malladi et 35 computing gradients for LLMs can require up to 12 times the memory needed for inference. This scaling challenge becomes even more pronounced as models grow larger, imposing significant memory demands and complicating the fine-tuning process, especially in resource-constranned environments.
"This work was partially supported by NSF ISS 2347592, 2348169, DBI 2405416, CCF 2348306, CNS 2347617, RISE 2536663.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

TEOOnD
DOUAD
0572
Cot
6:0
200 Trinkin Dunnitn J.cwer Ditber
Traniin Duntion 3.ower Betten
1000
Traniing Durriin Lower barber
Tharinn Dumtton J.cke Barber
20772
0.00
C.90
Peaciderrdy ampice Lonne Batte"
Pasl bitrnry sumplio
Peaccdericyy Commuritoor (sonee bubbes
6''
Figure 1: LLaMA-7B: (top) Accuracy vs. training duration and (bottom) Accuracy vs. memory across four tasks. Almost all bilevel-zofo points lie on the Pareto frontier and higher than the baselines. (top) Our method (blue) achieves significantly higher accuracy than MeZO (orange) while being ~2-4x faster in training offering a better trade-offs in accuracy and runtime. (bottom) Bilevel- zofo maintains the same memory footprint and significantly outperforms each corresponding PEFT variant (compare blue vs. green circles, squares, and triangles). Bilevel-zofo effectively combines the efficiency and expressivity of full ZO fine-tuning with the speed and robustness of first-order methods. It incorporates elements from both baselines but takes a definitive step beyond them.
To address these computational challenges, Parameter-Efficien Fine-Tuning (PEFT) methods have been developed. These techniques freeze most of the model's parameters and train only small subset, significantly reducing both memory and computational overhead. Popular PEFT approaches include prompt tuning, LoRA fine-tuning, and prefix tuning. Prompt tuning 22 40 58 48) optimizes continuous prompt vectors that concatenated with the input embeddings, while prefix tuning 224 introduces learnable prefix tokens that serve as conditioning variables at each transformer layer. LoRA (Low-Rank Adaptation) [16 [5] modifies the model's 's attention and feedforward layers by injecting low-rank trainable matrices, further reducing the resources required for fine-tuning.
While Parameter-Efficien Fine- Fine-Tuning (PEFT) methods reduce training costs and memory usage, they may not always achieve the same level of task-specific performance as full model fine-tuning. Research has shown that for tasks requiring high accuracy, complex adaptations, or knowledge, full fine-tuning often outperforms PEFT approaches due to its ability to adjust all model parameters for better adaptation [6 24 59). To make full model fine-tuning more computationally feasible, Zeroth-Order (ZO) methods offer an alternative by reducing the high computational cost. Rather than computing gradients via backpropagation, zeroth-order methods estimate the gradient using only the forward pass. Initially explored in the 1990s [50, 38 11 6 (30,, these methods have recently gained traction for fine-tuning LLMs 35
4
25 and have been shown to be able to
outperform FO PEFT methods given enough training time 63
A major limitation of 70 methods is their slow convergence due to the need for gradient estimation. For instance, McZO (35) required 10 times more iterations than PEFT baselines to match or exceed their performance. Additionally, ZO methods suffer from extreme sensitivity to prompt selection. In tasks like sentiment analysis with the SST-2 dataset, templated prompts (c.g.. "< CLS text data. It was [terrible great]. < <SEP>> ") are crucial for success (63]. These prompts effectively align the text data with task-specific objectives. As result, prompt selection becomes an important hyperparameter that significantly affect performance. In particular, ZO methods have been shown to be highly sensitive to prompt selections [3]. Without proper prompts, the performance of MeZO drastically drop (Table
In this paper, we ask: Can zeroth-order (70) and PEFT methods be smoothly integrated to mutually enhance each acher-nc greater robustness prompt variations, faster convergence, and better

---

performance than either method while maintaining memory efficiency comparable to each individually? We target settings where full FO fine-tuning is impractical due to memory/trouughptt (ii) pure PEFT lacks full-model capacity on harder adaptations, and (iii) pure 70 is slow and highly prompt--ensittve.
We propose Bilevel-ZOFO, novel bilevel optimization framework explicitly designed to leverage the complementary strengths of these two approaches:
At the inner level, FO-PEFT rapidly performs targeted, local adaptation using first-order gradients, stabilizing training and mitigating sensitivity to task-specific prompts that ZO methods need.
At the outer level, ZO method updates the full backbone model parameters efficiently, guided by the stable and informative inner-level adaptation. This full model finetuning enhances the model's generalization ability, enables a more sophisticated understanding. and improves transfer to new tasks.
This clear separation enables efficient bilevel optimization, addressing the major drawbacks of pure ZO methods (slow convergence, prompt sensitivity) and pure PEFT methods (limited full- model adaptation). Extensive ablation studies empirically verify this synergy, demonstrating faster convergence and more robust performance.
1.1 Contributions
We summarize main contributions follows:
We propose Bilevel-ZOFO, a theoretically grounded and practical bilevel optimization method that enhances zeroth-order (ZO) optimization by selecting the best prompt and thereby improves 70 fine-tuning with first-order PEFT (FO-PEFT). At the same time, strengthens PEFT by leveraging full fine-tuning through 7O updates.
2. Bilevel-ZOFO reduces ZO sensitivity to prompt choices and significantly accelerates con- vergence, achieving state-of-the-art performance with minimal memory overhead.
3. Extensive experiments confirm that Bilevel-ZOFO consistently outperforms existing FO- PEFT and ZO basclines across diverse tasks.
4. By updating the backbone with 70 and adapting only tiny FO-PEFT block per task, our method couples full-capacity transfer with few-shot efficiency. We show that this design has strong potential for efficient meta-learning, demonstrating improved multi-task adaptation with minimal computational resources.
Related work
2.1 Zeroth-Order Methods in Fine-Tuning LLMs
MeZO (35 pioneered zeroth-order (ZO) fine-tuning for LLMs, demonstrating compatibility with both full-model and PEFT approaches while improving computational efficiency. Subsequent work provided a benchmark for ZO optimization methods [63]. and expanded ZO applications to vari-
ance reduction [TO], federated fine-tuning 41 25 softmax layers [3] sparse tuning [4 3T and
privacy [51]. In contrast, we propose bilevel training framework that unifies the strengths of ZO full-model and FO PEFT fine-tuning, outperforming both individually, while using as much resources.
2.2 First-Order Methods for Bilevel Optimization
Bilevel optimization is computationally demanding, especially for LLMs, due to the cost of computing
hypergradients. Classical approaches rely on second-order methods {8] 9 23 43
322 while
29 21 [8 334 bypass the need for second-order information by reformulating bilevel problem as a constrained optimization problem. We build on this by incorporating ZO approximations into the upper-level optimization to bypass full gradient computation for L.Mss. These methods significantly reduce computational costs by eliminating the need for second-order information. Nevertheless, when fine tuning LLMs, back propagation for calculating the gradient
recent work [33 46

---

of an LLM is still too expensive. Liu et al. [29] and Lu and Mei [3] explore the convergence of their proposed methods the original bilevel problem, while other approaches only demonstrate convergence to the penalized problem. In this paper, we adapt the method from Lu and Mei [33 to approximate part of the upper-level parameters using 70 approximation in order to address the challenge posed by the large number of training parameters in large language models. We also provide convergence guarantees for this adapted zeroth-order-first forst-rrrrr method.
Bilevel Model with Zeroth-Order-First-
Method
In this section, we introduce our bilevel model and the zeroth-ordeerfiist-rree method for solving it.
3.1 Preliminaries and Notation
Let p E R represent the parameters of the PEFT model, and 0 E R represent the parameters of the pretrained base model. We denote the loss function given dataset D as F(θ, p: D) := ExED F(0, p)).. Given single downstream task, such as classification, aim to solve the following optimization problem:
min P:)). BER
(1)
Where corresponds to the embeddings of the hard prompt (as shown in Table 13 in the appendix of 35).. the model above reduces classical fine-tuning on single downstream task. In model ( the parameters of the PEFT model, p, are fixed.
To enhance generalization ability, we split the dataset D into two parts: one for tuning the PEFT model (denoted by p) and another for fine-tuning the LLM (denoted by f) To maximize performance on downstream tasks, need the optimal PEFT model parameters that best suited for the current LLM base model. To achieve this, we require p to satisfy the following condition:
E arg min F(O,,; Pp)
*ER"
Here 8 is just the dummy optimization variable for the inner problem-i.e. a candidate PEFT- parameter vector over which we minimize to obtain the optimal p for the current 0 on Dp. 0 This condition reveals that as the parameters 0 of the L.L change, the parameters p in the PEFT model should also be updated accordingly to be the best match for 0. Therefore, instead of solving true objective becomes:
min OER
F(O, p: Dy) s. t. arg min F(0,;; Pp).
SERa'
In this way, find the optimal pair of parameters for both the PEFT model and the LLM base model to achieve the best performance on downstream tasks.
3.2 Bilevel Model
Eq. (2) is an instance of bilevel optimization problem. To solve it, classical bilevel methods (as discussed related work) view Eq. (2) as a single-level problem ming F(O, p). Since p is the minimizer of another optimization problem, these methods typically require computing the Hessian- vector product (matrix multiplication of Fep p) and some vector v) multiple times to estimate the gradient of F(O,p p) with respect to 0. However, for large language models (LLMs), this approach computationally prohibitive because the number of parameters in 0 is too large.
To reduce the computational cost, following 33 we consider using penalty method for the bilevel problem 22). Specifically, (2) is equivalent to the following constrained optimization problem:
min BER Rd F(A.p:2)) s.t. F(0. p: 2p) inf F(e, s; pp) <
By penalizing the constraint with a constant À > 0, we obtain the following penalized problem: inf SER
min ((),p(0):))) + X(F(O. dER
F(0,s:2p)).
PER
2s does introduce parameters. only denotes the search variable of the inner minimization.

---

Algorithm Bilevel first-order method
1: Symbols: 0 E R2 (backbone params), RE (PEFT params), s R (aux inner variable), Gx(O,p. p. (penalized objective), K (number of outer steps), T (number of inner steps between two outer steps), 7 > 0 (inner LR), (outer LR), {Aa} C R (penalty at step k).
2: Input: step sizes 7) Q > 0; initial states 0 ,','" K, T E N4; penalty schedule {>x {>=]==0
K--1
3: for k O..... K 1 do
4:
for = ,
do
5:
1/-11 8/
1) v G22, (0k p",
6:
end for
7:
s f- it.
8:
@h+1 H
Va Gs. (0 p² sht1)
9: p pd
Vp Gba ( - s
10: end for
As À increases, the solution to the penalized problem approaches the solution to (3), and thus the solution to (2) (see Lemma 3.44for explicit relationship between the stationary points of (4) and those of the original problem (2)
Note that the penalized problem (4) is equivalent to the following
minimax problem:
min max (2(O.p.s) = F(0. p())2)) + X(F(0.P:2p)
F(0, Pp)). (5)
6ER PER"" SER="
In this way, we can solve the bilevel problem as a minimax problem. The basic minimax algorithm works as follows: iteration k, we first solve the maximization problem max, Gx ph, s) with (0% p)) fixed. For example, we can update s using inner loop with stochastic gradient descent (SGD). Let s be the result of this inner loop. Then, in the outer loop, update (0*, p²) by solving mine.p Gx (0, p.s**1 ***1) with ++1 fixed. Again, SGD can be used to update 0³ and p The conceptual algorithm is presented in Algorithm [ We assume do total of K outer iterations and T inner iterations between each two consecutive outer steps.
However, note that
VoGx, (0* (0'. s*) = VOF "oF(O".p":2) - \u(V : + VOF(O", 2+))) (6)
requires calculating the gradient with respect to 0, i.e, VoF Dy) Given the large scale of in LLMs, this is computationally expensive. To avoid this, we use zeroth-order (ZO) information to approximate the gradient VgG. Following [35 63 [4], employ the Simultancous Perturbation Stochastic Approximation (SPSA) as a classical zeroth-order gradient estimator. Specifically, at each iteration k. we sample z² (0, Ia), recalling that is the dimension of 0. We then approximate the gradient o F as follows:
FoF 2²;x)= F(O + ez pp;;x) F(O ez (a",p";:)
2c
As opposed to the number of LLM parameters 0, the number of PEFT parameters is very small, So it is feasible compute the exact gradient with respect to p. Thus, we calculate Vp F(, p: B) exactly.
Additionally, in each iteration A we sample mini- batchs B3 and By and use F( p²: ph;B3 B) to sub- stitude Vo ((O ; and V (( : Dp)in in (6) We also mini-batcha when calculating the gradients with respect to the PEFT parameters s and p.
This approach leads to the final algorithm (Algorithm and Figure 5) for fine-tuning LLMs using the bilevel model ( We refer to this method as the Bilevel Zeroth-Order- First-Orddrr (Bilevel
ZOFO) method. In Appendix B we show that Bilevel ZOFO converges at rate of O(c under widely accepted assumptions
The complexity of Bilevel ZOFO matches that in previous ZO
In our theorem, we assume strong convexity on the lower level objective function, as is common other theoretical work on bilevel optimization. While strong convexity facilitates theoretical analysis. our experiments demonstrate that the method remains robust when this condition not strictly satisfied.
5

---

Algorithm 2 Bilevel Serteeeleeettt-ooo------------- Method (Bilevel ZOFO)
1: Symbols: 0 E R (backbone params), p E Rd' (PEFT params), s E Rd (aux inner variable), p; (avg. loss over data D). Ve F' (20 grad. estimator; see (7). 2p (inner dataset), D (outer dataset), B (mini-batch size), K (number of outer steps), 7' (number of inner steps between two outer steps), > O (inner LR), Ç >> 0 (outer LR), {AR] S R_ (penalty schedule).
2: Input: step sizes 17:5 0; batch size B; datasets pp: D initial states 0 ,,,," K,T
N4:
penalty {
3: for k=0,... K do
4: for t00==....,TT
5: Sample batch B from Pp.
6: Let Let
- F si: Bxpp)
7: Output s s++1 = ST.
8:
end for
9:
Sample a batch {B}} from D and {Bp) from Pp.
For E B. U By, calculate F(F x) following
11: Let
p k+1 p* <(V p. B7) + da F(t pp; B))) 0++1 0 C(VoP(O( By; + du (V .p Bp: voF ,++1,
(8)
end for 12:
minimax algorithm in 15 but solves bilevel optimization problem (2) and does not depend the dimensionality d thanks to the efficient rank assumption B.5 providing efficiency guarantee for our algorithm.
Experiments
We conduct extensive experiments on various LLMs of different scales to demonstrate the effec- tiveness of bilevel-ZOFO in improving current zeroth order methods and PEFT. We also conduct experiments in testing potential in meta training. Noticing that our proposed structure is able to incorporate any variation of veroth-order methods in the upper-level step and any PEFT method in the lower level, to maintain focus on testing the effectiveness of the proposed bilevel structure and its unique multitask learning capabilities, we used the classic MeZO 335
4.1 Single Task Experiments
4.1.1 Experimental Setting
Following MeZO [35), we evaluate our approach on a range of classification and multiple-choice tasks. In this setting, training and testing are conducted on the same task. We employ prompt-tuning [22], prefix- tuning (24. and LoRA [[6]- well-known PEFT baselines-for lower-level training validate bilevel- ZOFO under different conditions and resource con- straints. During each lower-level update, we update only the PEFT parameters, and during the upper- level optimization step, we tune the full model using zeroth-order gradient approximation. We perform 10 lower-level updates between each pair of upper-level updates. For each task, we randomly sample 1000 examples for training, 500 examples for validation, and 1000 examples for testing. We use the Adam optimizer 20 and report test accuracy or Fl-score.
Sata
tack
Figure 2: Training loss for the lower-level objective of the bilevel framework with Lora as the PEFT model.
We compare our method against several baselines, including Me70 for Full Model Fine-tuning, MeZO for PEFT, and First-order PEFT. We fix the total memory budget each step across bilevel- ZOFO and the baselines. We train zeroth-order methods for 10,000 steps, and first-order methods

---

Trainer
Mode
BoolQ
CB
Copa
ReCoRD
RTE
SST2
WIC
WinoGrande
WSC
Average
0.6927
0.7767
0,7000
0.6980
0.6587
0.8214
0.5543
0.5480
0.5054
0.6617
0.6860
0.7607
0.7200
0.7083
0.6755
0.8501
0.5549
0.5607
0.5570
0.6748
McZO
prefix
0,6573
0.7945
0.7033
0.7047
0.6972
0.8218
0.5622
0,5370
0,5105
0.6654
prompi
0.6260
0,5821
0.7067
0,7070
0,5415
0,7463
0,5574
0,5556
0.4654
0.6098
average
0.6655
0.7285
0.7075
0.7045
0.6432
0.8099
0,5572
0.5503
0.5096
0.6529
lora 0.7456
0,8512
0,7500
0.7206
0.7292
0.9258
0,6463
0.5806
0.6474
0.7330
prefix 0.7300
0.8571
0.7167
0.7093
0.7136
0.8133
0.5387
0.5787
0.5705
0.6920
FO
prompi
0,7150
0.7142
0.7466
0.7163
0.6936
0.8016
0,5386
0,5980
0,5062
0,6700
average
0.7302
0.8075
0.7378
0.7154
0.7121
0.8470
0,5745
0.5857
0.5747
0.6977
lora
0.7433
0.9167
0,7400
0.7183
0.7401
0.9331
0.6447
0,5903
0,6428
0,7410
prefix
0.7340
0.8690
0.7267
0.7140
0.7304
0.8550
0.6317
0.5710
0,5810
0.7125
Ours
prompt 0.7367
0.7679
0.7633
0.7257
0.6867
0.8335
0.6267
0.5900
0.5133
0.6938
average 0.7380
0,8512
0.7433
0.7193
0.7191
0.8739
0.6344
0,5838
0,5790
0.7158
Table 2:
Single- Task Experiments on OPT-1.3B with 1000 samples. Values correspond to mean
across three random seeds. FO: First-Order. FT: full-model fine-tuning. See Table in in the Appendix for standard deviation values.
for 5000 steps. For all experimental details, refer the Appendix D.1 We also provide the training loss for the lower-level objective of the bilevel framework in Figure 2 to show that consistent with
the guarantees provided by our theoretical analysis in Section B Bilevel-ZOFO converges. See Appendix D.2 for more details.
4.1.2 Results
Bilevel-ZOFO mitigates MeZO's sensitivity to task prompts: We present experimental results demonstrating that Bilevel-ZOFO significantly reduces the prompt sensitivity observed in MeZO.
Following the setup of Table in the MeZO
paper (35), we evaluate both McZO and Bilevel- where simple task prompt is prepended to each input versus 2- where no such prompt is used. Table [ re- ports results for tuning OPT- on SST-2 and COPA using LoRA as the PEFT method. Our findings show that Bilevel-ZOFO is markedly less sensitive to prompt variations than MeZÓ; the performance gap between prompted and un- prompted settings substantially smaller for Bilevel-ZOFO.
Method
Task
prompt
w/o prompt (%)
Dift.
ZOFO in two scenarios:
McZO
SST-2
89.6
51.9
-38.6
COPA
70.0
54.8
-15.2
SST-2
93.3
92.9
-0.4
Ours
COPA
76.7
73.6
-3.1
Table I: Prompt sensitivity comparison for MeZO and Bilevel-ZOFO. Bilevel-ZOFO effectively mit- igates the extreme sensitivity of McZO to adding task prompts to inputs.
Table presents the test metrics when applying bilevel-ZOFO and baselines fine-tune OPT- 1.3B 662 on a downstream task. Table ddmoonstrateee the results for Llama2-7b 52 We can make the following observations:
Bilevel-ZOFO offers a better training speed - accuracy tradeoff than MeZO Bilevel-ZOFO outperforms MeZO, even when trained for half the number of iterations across almost all tasks, thus offering a better training duration-performance trade-off than MeZO (Also see Figure I
Bilevel-ZOFO outperforms FO PEFT most tasks and on average: From Table 2 and Table 3
we see that Milevcl-ZOFF outperforms the corresponding FO-PEFT methods across most instances and on average, comparing each FO PEFT setting with the corresponding bilevel-ZOFO setting. This is while using the same level of memory as FO PEFT.
BiOe scales effectively to larger LLMs: Figure 1 and Table 3 shows that hilevel-ZOFO's advantages are not confined to smaller models like O.T-1.3b, ,bb but also extend to larger LLMs.
4.1.3 Memory Profiling and Wall Clock Time Analysis
Figure 3 demonstrates the memory profiling of -iOe MeZO and First-order prefix tuning on four different tasks. Memory consumption of MeZO and first-order PEFT meth-
Trainer
Mode
BoolQ
RcCoRD
SQuAD
SST2
Average
ft. 0.7915
0.7890
0.7737
0.8646
0.8047
lora
0,8020
0.7970
0.7412
0.8529
0.7983
McZO
prefix
0,7830
0.7905
0.7093
0.8364
0.7798
prompt
0.7787
0.7935
0.7014
0.8246
0.7746
average 0.7888
0.7925
0.7489
0.8397
0.7825
lora 0,8420
0.7920
0.8197
0.9557
0.8524
rо
prefix 0.7783
0,8013
0.7946
0.9243
0,8246
prompt 0.8083
0.8023
0.7805
0.9284
0.8299
average
0.8095
0.7985
0.7983
0.9361
0.8356

---

Task
MeZO
FO
Bilevel-ZOFO
notsdel
diicel 20r0undrt
Copa
0.299
0.127
0.135
MultiRC
0.622
0.474
0.502
WSC
0.278
0.120
0.164
Taxa
Figure 3: Memory consumption of baselines and Bilevel-ZOFO for OPT1.3B (batch size 8, A6000ada 48GB). Bilevel-ZOFO demonstrates memory usage comparable to both baselines.
Table 4: Wallclock time per step of baselines and Bilevel-ZOFO when fine-tuning OPT1.3B. Values are averaged over runs using batch size of 8 on single A6000ada 48GB GPU.
ods varies across tasks, with one occa- sionally surpassing the other. Each lower-level update in our method matches that of the corresponding PEFT method. Similarly, each upper- level update requires the greater mem- ory usage between MeZ0 and PEFT under comparable settings. As re- sult, the total memory requirement of our method corresponds to the maxi- mum memory usage of the PEFT and MeZO experiments. Nonetheless, as demonstrated in Table Banle@annd ure I1 our method outperforms both PEFT and MeZO on most cases and on average.
Fig-
We also present a wall-clock time analysis of bilevel-ZOFO compared to the baseline. As shown in Table similar MeZO [35], we observe that zeroth-order steps exhibit higher latency compared to first-order steps. The results indicate that our bilevel-ZOFO achieves comparable delays to the FO-PEFT method while significantly reducing step duration compared to MeZO. Moreover, as highlighted in Table bilevel-ZOFO outperforms both methods average.
Ablations
4.2.1 Effect of Hyper-parameters
We perform an ablation study by varying the regularization parameter (as defined in Equation (5) and the number of lower-level training steps between each pair of upper-level updates. Figure shows the results. From Figure 4a. the effect À appears to be non-linear, indicating the need to find an optimal balance. Nontheless, a moderate value like 10 or 100 seems to work reasonably well on tasks. As anticipated, Figure 4bb demonstrates that performance generally degrades when the total number of upper-level updates is reduced, suggesting there is trade-off between latency and performance. While more upper-level updates improve results, they also extend the overall training time. We also analyze different data splits for lower and upper level training. The 1:2 split generally performs well, though effectiveness varies by task. Using a separate upper-level dataset, rather than sharing data across both levels, allows our method to adapt more quickly new tasks in meta-learning.
Dffect of Dutaset Spil Palis Performance
2125
22 Ct
Solt rutu 20to/2 burng Youd deat
(a)
(b) lower-level training steps
(c) Lower-Upper Data Ratio
Figure 4: Ablation over in 5). the number of lower-level training steps before each upper-level update, and the ratio of lower/upper data.

---

4.2.2 Effect of Design Choice
Full-model tuning is only practical via zeroth-order (ZO) optimization due to the high cost of first- order (FO) methods in large models, a core assumption this work. To address MeZO's 's sensitivity and slow convergence while leveraging the strengths of FO PEFT, we propose a hybrid bilevel approach that applies FO to PEFT parameters and ZO to the base model. This section evaluates the benefits of using exact gradients for PEFT. Table S compares Bilevel-ZOFO with Bilevel-ZOZO, MeZO, and FO PEFT across four benchmarks, demonstrating the gains from both FO usage and the bilevel structure.
To ensure that performance gains are not sim- ply due to tuning more parameters, we compare against a Two-Stage Pipeline baseline that is identical to Bilevel-ZOFO in parameter count, memory, and runtime. applies FO prompt tuning for the same number of steps as Bilevel- ZOFO's lower level, followed by ZO tuning for the same number of upper-level steps. As shown in Table 5 only the bilevel formulation yields significant improvements, reinforcing the im- portance of the optimization structure. See Ap- pendix 1 for detailed discussion.
Method
BoolQ
CB
COPA
SST2
McZ0
0.6927
0.7767
0.7000
0.8214
FO PEFT
0.7150
0.7142
0.7466
0.8016
Bilevel-ZOZ0
0.6280
0.6092
0.7146
0.7633
Two-Stage Pipeline
0,7060
0.6786
0.7433
0.8016
Jointly Optimized
0.7209
0.7500
0.7466
0.8148
Bilevel-ZOPO
0.7367
0.7679
0.7633
0.8335
Table 5: Ablation studies of the effect of different design choices of bilevel-ZOFO as well as gains from the bilevel structure itself.
We also compare with a baseline which jointly
optimizes the base model parameters and PEFT parameters together with the same objective function Eq. [ (Jointly Optimized row in Table 5). While this baseline could slightly outperform MeZO and FO PEFT, it still falls short of our bilevel method, reinforcing our approach's 's benefits, although it more resource consuming and has strictly longer steps due to 70 gradient estimation at every iteration.
4.3 Adopting Bilevel ZOFO to Meta-learning
Following Min et al. 36 we evaluate the performance of bilevel-ZOFO as a fast and efficient meta-learning algorithm. We perform experiments using four of the distinct meta- meta-learning settings: toticaatiiontt--classiccttooooto For instance, in subtasks and test on a number of distinct classification subtasks. Fach of these meta-learning tasks includes a set of training sub-tasks and a different set of test sub-tasks. The sub-tasks are sourced from CROSSFIT [57] and UNIFIEDQA [9]] comprising a total of 142 unique sub-tasks. These sub-tasks cover variety of problems, including text classification and question answering all in English. We use GPT2-Large 42 as the base model for these experiments.
QA-to-QA, and non-QA-to-- setting, we train a number of non-classification
We compare our method against several baseline approaches:
MetalCL [36]: A method for meta-learnin with in-context learning. MetalCL tunes all the parameters of the base model using the first-order method. In both training and testing, the model is given & demonstration examples, b), -. (ax, bx), where b; represents either classification labels or possible answers in question-answering tasks, along with one test example (a, b). The input is formed by concatenating the demonstration examples a1 bi.b,..... Og by, a. The model then computes the conditional probability of each label, and the label with the highest probability is selected as the prediction.
Zero-shot: This method uses the pretrained language model (LM) without any tuning, performing zero-shot inference without any demonstration examples.
In-context Learning (ICL): This method uses the pretrained I.M with in-context learning by conditioning on concatenation of l demonstration examples and actual test sample similar to MetalCI.
We sample 768 examples from each training sub-task. We train MetalCL in their original setting for 30,000 steps. To train our method, we split the training dataset of each sub-task to two subsets, 256 samples as the development dataset for upper-level updates and 512 samples for lower-level training. For each outer iteration of our method, we randomly sample subset of 5 training tasks. We perform 10 level updates between each pair of upper-level updates. To keep bilevel-ZOFO as lightweight possible, unlike MetalCL, we DO NOT include demonstration examples in the

---

Methed
Training Perk Mem(be-1) 1)
non non_class
qa
non_qa
FLOPS
Step Duration
Tokens / Sample
-> class
class
+>
34.2
Few-shot
~v 5X
34.9 (1.4)
(1.4)
40.5 (0.3)
40.5 (0.4)
MetalCL
1.1351 10th
32GB
0.48s
(1.1)
31.7
45.5 (0:3)
40.2
Ours (Zero-shot)
1.2486
10
12GB
0.18
X
34,5
34,3
41.8
40.4
Ours(Tuned)
1.2493 10"*
12GB
(1.3)
Table 6: Multi-task Meta learning results using GPT2-Large as the base model. Values correspond to the mean and standard deviation over 5 test seeds which include different demonstration samples for each test task. class: Classification, qa: Question Answering
inputs. Since bilevel-ZOFO uses significantly less memory and has much faster updates compared to MetalCI., theoretically we are able to train it for many more iterations within the same total training duration as MetalCI.. However, due to resource constraints, we only train bilevel-ZOFO for 50,000 iterations. Similar to [5 we did not observe plateau in performance for bilevel-ZOFO, indicating that further training can yield additional improvements.
For both ICL and MetaICL, during the testing phase the model is given k 4 demonstration examples for each test data point. We don't I use demonstration examples in test samples for bilevel-ZOFO evaluation. We evaluate the zero-shot capabilities of our method well the performance of the final model LoRA-tuned for 10 additional iterations on 4 demonstration samples from each class of each test sub-task. Similar [6).. we report Macro-averaged F1 as the evaluation metric. See Appendix D.3 for all training details.
Table 6 presents the meta-leariing results. We observe that in zero-shot setting, bilevel- ZOFO (ours(zeroshot) outperforms zero-shot on all tasks. Note that although ICL and MetalCL perform better than ours (zero-shot) 1)MetaICL fine-tunes the entire base model using first-order methods, which incurs a significantly higher computational cost. 2)both ICL and MetaICL with k 4 demonstration examples take 4 times more time do inference than our method with no demonstration examples. Nonetheless, after lightweight 10-iteration LoRA fine-tuning phase, surpasses ICL and MetalCL on nearly every hyper-task, highlighting its strong potential as meta-learning algorithm.
(onvellZOOOouurs(ttuuue
5 Conclusions
In this work, introduced novel bilevel optimization framework designed to mitigate the downsides of PEFT and zeroth-order full model fine-tuning. We propose a new method that is more efficient than existing bilevel methods and thus more suitable for tuning full pre-trained large language models. Bilevel-ZOFO preserves PEFT and Z0-like peak memory, reaches target accuracy in fewer iterations than ZO (yielding 2-4x faster time-to-target despite multi-forward ZO steps), and matches or surpasses FO-PEFT at similar per-step cost-offering a practical accuracy-effictt efficiency trade-off for resource-constrained fine-tuning. Theoretically, we provide convergence guarantees for this new method. Empirically, we show that this method outperforms both zeroth-order and FO PEFT methods in single task settings. Additionally, show this method is effective and efficient when adapted to do multi-task learning. With competitive and even better performance compared to existing meta-training methods, our method offers significantly cheaper training process.
Acknowledgments
This work was made possible by NSF IIS 2347592, 2348169, DBI 2405416, CCF 2348306, CNS 2347617.
References
[1] Nader Asadi, Mahdi Beitollahi, Yasser H. Khalil, Yinchuan Li, Guojun Zhang, and Xi Chen. Does combining sarameter-efffcient modules improve few-shot transfer accuracy? CoRR, abs/2402, 154144 2024. doi: 10.45550AARXI12222215544 h/L/httss:///oo.oo org/10. 18550/arXiiv 2402. 15414
10

---

[2] Ziyi Chen, Bhavya Kailkhura, and Yi Zhou. A fast and convergent proximal algorithu for regularized nonconvex and nonsmooth bi-level optimization. arXiv preprini urXiv:2203.16615 2022.
[3] Christopher Clark, Kenton Lee, Ming-
Bing-Wei Wei Chang, Tom Kwiatkowski, Michael Collins, and Kristina Toutanova. Boolq: Exploring the surprising difficulty of natural yes/no questions. arXiv preprint arXiv:1905.10044 2019.
[4] Yichuan Deng, Zhihang Li, Sridhar Mahadevan, and Zhao Song. Zero-th order algorithm for softmax attention optimization. CoRR, ahs/2307.08... .83352, 2023, doi: 10.48550/ARXIV2230.003333 URL.ttps https
01t.1//..555555/11111 2307 08352
[5] Yichuan Deng, Zhihang Li, Sridhar Mahadevan, and Zhao Song. Zero-th order algorithm for softmax attention optimization. CoRR, abs/2307 .08352, 2023, doi: 10448550/ARXII.2307.00668 URLhttps
https
//doi.org/// 10 48550/85555533 arriv 2207 08352
[6] John C. Duchi, Michael I. Jordan, Martin J. Wainwright, and Andre Wibisono. Optimal rates for zero-order convex optimization: The power of two function evaluations. JEEE Trans. Inf. Theory, 61(5))2788 2806, 2015. doi: 10.1 1119/TTT2011.2249925555
1109/TIT. 2015 2409256
[7] Chelsea Finn, Picter Abbcel, and Sergey Levine. Modcl-agnostic meta- veta-lcarning for fast adaptation of deep networks. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August, 2017.
[8] Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient- based hyperparameter optimization. In Proceedings of the 34th International Conference on Machine Learning, ICML. 2017, Sydney, NSW, Australia, 6-11 August, 2017.
[9] Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi. and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning In Proceedings of the 35th International Conference on Machine Learning, JCML 2018, Stockholmsmässan, Stockholm. Sweden, July 10-15, 2018.
[10] Tanmay Gautam, Youngsuk Park, Hao Zhou, Parameswaran Raman, and Wooseok Ha. Variance-reduced zeroth-order methods for fine-tuning language models. In Forty-first International Conference Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024. URL https://
openreviev wwdd:
wieerrummmii--ooooo VHO4nEE774
[11] Saeed Ghadimi and Guanghui Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic programming. SIAM J. Optim., 23(4):2341-235 -2364,,,1,,22--1 2013, doi: 10888871. URL httpss/:///do
org/ 10/ 1117112171218811111
[12] Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv:1802.022. 88..02224........ 2018
[13] Ruohao Guo, Wei Xu, and Alan Ritter. Meta-tuning Ilms to leverage lexical knowledge for generalizable language style understanding. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar, editors, Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume I: Long Pupers), ACL 2024, Bangkok, Thailand. August 11-16. 2024, pages 13708-13733 Association for Computational Linguistics, 2024. SoLLitttss//aalaathoolo
org/ 2024. acl-long.........mm 740
[14] Wentao Guo, Jikai Long, Yimeng Zeng, Zirui Liu, Xinyu Yang, Vide Ran, Jacob R. Gardner, Osbert Bastani, Christopher De Sa, Xiaodong Yu, Beidi Chen, and Zhaozhuo Xu. Zeroth-order fine-tuning of Imss with extreme sparsity. CoRR. abs/2406.022 029113 2024. doi: 10. (0-4850//AXXXI2240600090 URL https: org/ waerg//...855///00 48550/arXi 2406.02913
[15] Neil Houlsby, Andrei Giurgiu, Stanislaw Jastrzebski, Bruna Morrone, Quentin de Laroussilhe, Andrea Gesmundo, Mona Attariyan. and Sylvain Gelly. Parameter-efficient transfer learning for NLP. In Kamalika Chaudhuri and Ruslan Salakhutdinov. editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 Proceedings of Machine Learning Research, pages 2790-2799. PMLR, 2019. URL http:://proceedinneee/ mlr html
ftess//99/houlsbyyy
[16] Edward Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen- Zhu, Yuanzhi Li, Shean Wang. Lu Wang. and Weizhu Chen. Lora: Lowkrank adaptation of large language models. In The Tenth International Conference on Learning Representations, ICLR 2022, Viriual Event, April 25-29, 2022. OpenReview.net, 2022, URL https://openreeview. nwt/forummmiiiee wiw.orrmmmmddn22eeeeee......
[17] Chengsong Huang. Qian Liu, Bill Yuchen Lin, Tianyu Pang, Chao Du and Min Lin. Lorahub: Efficient cross-task generalization via dynamic Iora composition. CoRR, abs/2307.1322 2023. doi: 10.48550/ 12919. URL https: //doi org/10 10. 48550/arXiv 2307. 13269

---

[18] Kaiyi Ji. Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In Marina Meila and Tong Zhang. editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 4882-4892. PMLR, 18-24 Jul 2021.
[19] Daniel Khashabi, Sewon Min. Tushar Khot, Ashish Sabharwal, Oyvind Tafjord, Peter Clark, and Hannaneh Hajishirzi. Unifiedqa: Crossing format boundaries with single QA system. In Trevor Cohn, Yulan He, and Yang Liu, editors, Findings of the Association for Computational Linguistics: EMNLP 2020, Online Event, 16-20 November 2020, volume EMNLP 2020 of Findings of ACL, pages 1896-1907. Association for Computational Linguistics, 2020, doi: 10. 10.18653/V (0066/////0220F/2/60 12022.FINDINGS EMNLP.11I URL
https://dol: org/ 10. 11w53//1//2022 wwt.220.....nnnnng wwwdingndnn--ii emnlp. p.17
[20] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA. USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL http://arxiv, org/ /a/abb//1111 1412
6980
[21] Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert D. Nowak. A fully first-order method for stochastic bilevel optimization. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honoludu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 18083 18113. PMLR, 2023. ptttt:://////cceeeeeee
mlr. Natsss//222//uue www.//woon...cncccc .html
[22] Brian Lester, Rami Al-Rfou, and Noah Constant. The power of scale for parameter-efficient prompt tuning. In Marie-Francine Moens, Xuanjing Huang. Lucia Specia, and Scott Wen-tau Yih, editors, Proceedings of the 2021 Conference Empirical Methods in Natural Language Processing, EMNLP 2021, Virtual Event / Punta Cana, Dominican Republic, 7-11 November, 2021, pages 3045 3059. Association for Computational Linguistics, 2021. doi: 10. 11865//1/202111 EMNLP WWW.L-MAIN.24- 243.. URL htttp:://do..oooro 186533.18633
v1/2021. emn main. 243
[23] Junyi Li, Bin Gu, and Heng Huang. A fully single loop algorithm for bilevel optimization without hessian inverse. In Thirty Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty- Foorth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22- March 1, 2022.
[24] Xiang Lisa Li and Percy Liang. Prefix-tuning: Optimizing continuous prompts for generation. In Chengqing Zong, Fei Xia, Wenjie Li, and Roberto Navigli, editors, Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing, ACL/JCNLP 2021, (Volume I: Long Papers), Virtual Event, August 1-6, 2021. pages 4582 4597. Association for Computational Linguistics, 2021. URL/https:///oo: org/10 18653/v1/2021 acl-221..clloongg .353
[25] Zhenqing L Ling, Daoyuan Chen, Liuyi Yao, Yaliang Li, and Ying Shen. On the convergence of zeroth-order federated tuning for large language models. In Ricardo Baeza-Yates and Francesco Bonchi, editors, Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2024, Barcelona, Spain, August 25-29, 2024, pages 1827-1838, ACM. 2024. doi: 10.1145/36375288367755 UtRl/httss///aae www.loi.ooggiii org/10. 1145 3687728777788228 3671865
[26] Bo Liu, Mao Ye, Stephen Wright, Peter Stone, and Qiang Liu. Bome! bilevel optimization made easy: A simple first-order approach. In Sanmi Koyejo. S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho. and A. Oh, editors. Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022, 2022.
[27] Chenxi Liu, Junjie Liang. Yugi Jia, Bochuan Cao. Yang Bai, Heng Huang, and Xun Chen. Explore data left behind reinforcement learning for reasoning language models. arXiv preprint arXiv:2511.04800 2025.
[28] Chenxi Liu, Tianyi Xiong, Yanshuo Chen, Ruibo Chen, Yihan Wu, Junfeng Guo, Tianyi Zhou, and Heng Huang.
preference optimization of large multimodal models by adversarial negative mining. arXiv preprint arXiv:2506.08022, 2025.
[29] Risheng Liu, Zhu Liu, Wei Yao, Shangzhi Zeng, and Jin Zhang. Moreau envelope for nonconvex bi- level optimization: A loogle-loop and free solution strategy. CoRR, abs/2405 009907.999.72.. 2024. doi: 10. 10.48855//ARXI122455.00
TRRl.https::// //do:p:://do.... org/10. 48550/ arxiv. 2405.09927
[30] Sijia Liu, Pin- Chen, Bhavya Kailkhura, Gaoyuan Zhang, Alfred Hero III, and Pramod K. Varshney. primer on seroth-order optimization in signal processing and machine learning: Principals, recent advances, and applications. IEEE Signal Process. Mag.. 37(5):43-55) 54, 2020. doi:
URL
//dos: org/ 1109/MSP 2020. 3003837
12

---

[31] Yong Liu, Zirui Zhu, Chaoyu Gong, Minhao Cheng, Cho-Jui Hsieh, and Yang You. Sparse mezo: Less parameters for better performance in zeroth-order LLM fine-tuning. CoRR, abs/2402.1575/1 2024. doi: 10.48550/ARXII22402.57777
URL httpps:: wtt//....///////.....
48550/ arxiv. www....ww...........m...... .
[32] Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. In The 23rd International Conference on Artificial Intelligence and Statisticx, AISTATS 2020, 26-28 August, Online [Palermo, Sicily, Italy], 2020.
[33] Zhaosong Lu and Sanyou Mei. First-order penalty methods for bilevel optimization. SIAM Journal on Optimization, 34(2):1977-1699, 2024, doi: 10.1 137/23M11666555. httphttt/////o..rrr 1137/
28M1566753
[34] Matthew Mackay, Paul Vicol, Jonathan Lorraine, David Duvenaud, and Roger Grosse. Self-tuning networks: Bilevel optimization of hyperparameters using structured best-response functions. In International Confer- ence on Learning Representations, 2019. URL
[35] Sadhika Malladi, Tianyu Gao, Eshaan Nichani, Alex Damian, Jason D. Lee, Danqi Chen, and Sanjeev Arora. Fine-tuning language models with just forward passes. In Alice Oh. Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
[36] Sewon Min. Mike Lewis. Luke Zettlemoyer. and Hannaneh Hajishirzi. Metaicl: Learning to learn in context. In Marine Carpuat, Marie- Cathhrinee de Marneffe, and Iván Vladimir Meza Ruíz, editors, Proceedings of the 2022 Conference of the North American Chapter of the Association for Compulational Linguistics; Human Language Technologies, NAACL 2022, Seattle, WA, United States, July 10-15, 2022, pages Association for Computational Linguistics, 2022. doi: 10. 1865/N1/2222NNAACL MAIN.,.0. URL
https://doi. 10. 10. 18613/166vvvv 2022/22///22222//// maacl-main.200 201
[37] Yurii Nesterov. Introductory lectures on convex optimization: A basic course. volume 87. Springer Science & Business Media, 2013.
[38] Yurii F.. Nesterov and Vladimir G. Spokoiny. Random gradient-free minimization of convex functions. Found. Comput. Math., 172):527-566, 2017. doi: 10.1007/511208--05-99909 URL httpps//doi
org/10 10. 100000000000---- 015 9296-2
[39] Mohammad Taher Pilehvar and Jose Camacho-Collados. Wie: the word-in-context dataset for evaluating context-sensitive meaning representations. arXiv preprint (808.0000 2018.
[40] Guanghui Qin and Jason Eisner. Learning how to ask: Querying Ims with mixtures of soft prompts. In Kristina Toutanova, Anna Rumshisky, Luke Zettlemoyer. Dilek Hakkani- -ür, Iz Beltagy, Steven Bethard, Ryan Cotterell, Tanmoy Chakraborty, and Yichao Zhou, editors. Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 1021, Online, June 6-11, 2021, pages 5203-5212. Association for Computational I Linguistics. orgoii..rg/// 10. v8253/v1/2021
2021. doi: 10. 118633/V1/2222 1 NAAAL-AAALAAAAAT URL
naacl mainn.ainn...mmm.. 410
[41] Zhen Qin, Daoyuan Chen, Bingchen Qian, Bolin Ding, Yaliang Li, and Shuiguang Deng. Federated full Gull-parameter tuning of billion-sized language models with communication cost under 18 kilobytes. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024. Uttthtps::////nt httpp///wwevii.eeeeeererrraaiiaa
[42] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8)9, 2019.
[43] Aravind Rajeswaran, Chelsea Finn, Sham M. Kakade, and Sergey Levine. Meta-leamingg with implicit gradients. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, Vancouver. BC, Canada, 2019.
[44] Melissa Roemmele, Cosmin Adrian Bejan, and Andrew S Gordon. Choice of plausible alternatives: An evaluation of commonsense causal reasoning. In 201 AAAI spring symposium series, 2011.
[45] Keisuke Sakaguchi. Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. Winogrande: An adversarial winograd schema challenge at scale. Communications of the ACM, 64(9):99 106, 2021.
[46] Han Shen and Tianyi Chen. On baselty-based bilevel gradient descent method. In Andreas Krause, Emma Brunskill, Kyunghyun Cho. Barbara Engelhardt, Sivan Sabato, and Jonathan Searlett, editors. International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 30992- 11992-11015 31015. PMLR, 2023. URL https::/ httpss//proceedings mlr, ppess/v2022 shen23c...3c html
13

---

[47] Zhengxiang Shi and Aldo Lipani. DePT: Decomposed prompt tuning for parameker-efficienl fine-tuning. In The Twelfth International Conference on Learning Represeniations, 2024. URL https://ppeenrerierr
pet//forum?idekeegfPPn
[48] Taylor Shin, Yasaman Razeghi, Robert L. Logan IV, Fric Wallace, and Sameer Singh. AutoPrompt: Eliciting Knowledge from Language Models with Automatically Generated Prompts. In Bonnie Wehber, Trevor Cohn, Yulan He, and Yang Liu, editors, Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), Online, November 2020. Association for Computational Linguistics.
[49] Reza Shirkavand, Peiran Yu, Shangqian Gao, Gowthami Somepalli, Tom Goldstein, and Heng Huang. Fifi- cient fine-tuning and concept suppression for pruned diffusion models. arXiv preprint a1Xiv:24/2.15311, 15341, 2024.
[50] J.C. Spall. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation. IEEE Transactions on Automatic Control, 37(3):332 -31333111111111 1992. doi: 10.1 119632.
[51] Xinyu Tang, Ashwinee Panda, Milad Nasr, Saeed Mahloujifar, and Prateek Mittal, Private fine-tuning of large language models with zeroth-order optimization. CoRR, http//2001.044445 2024. doi: 10.48550/
ARXIV.2401.0434 URL htttps://dii. hww.iddooo.grgg/// 10. 48550/arXiv 2401. 04343
[52] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaci, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosalc, Dan Bikel, Lukas Blecher, Cristian Canton- Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian. Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kamhadur, Sharan Narang, Aurélien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. Llama 2: Open foundation and fine- tuned chat models. CoRR, abs/2307 092888. 2023. doi: 10.48550/ARXIV.2337.000 //doi /'oiiorr//i org/10 10. 48850/88550.i.. 2307 092288
URL. https
[53] Alex Wang. Glue: A multi-task benchmark and analysis platform for natural language understanding. arXiv preprint arXiv:1804.07440 074666 2018.
[54] Alex Wang, Yada Pruksachatkun, Nikita Nangia, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. Superglue: A stickier benchmark for eeneral-purpose language understanding systems, Advances in neural information processing systems, 32, 2019.
[55] Zhongruo Wang, Krishnakumar Balasubramanian, Shiqian Ma, and Meisam Razaviyayn. Zeroth-order minimax problems with improved complexities. Journal of
algorithms for woonccoovee-stroogyyycooom Global Optimization, 87(2):709-740, 2023.
[56] Enneng Yang. Li Shen, Guibing Guo, Xingwei Wang, Xiaochun Cao, Jie Zhang, and Dacheng Tao, Model merging in lls,, milms, and beyond: Methods, theories, applications and opportunities, 2024. URL https://arxiv. org/ abs/2408 07666
[57] Qinyuan Ye, Bill Yuchen Lin, and Xiang Ren. Crossfit: A few-shot learning challenge for cross-task generalization in NLP. In Marie- Francine Moens, Xuanjing Huang. Lucia Specia, and Scott Wen-tau Yih. editors, Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, EMNLP 2021, Virtual Event / Punta Cana, Dominican Republic, 7-11 November, 2021, pages 7163-7189. Association for Computational I Linguistics, 2021. doi: 10. 118633V1/20222 120.://1112211MMLMMMMMMM W.W.L- https: //ops://doi.... www.orrg//11 10. 18653/v1 vv. 2021 smnnp-main...
URL.
[58] Lang Yu, Qin Chen, Jiaju Lin, and Liang He. Black-box prompt tuning for vision-language model as a service. In Proceedings of the Thirty Second International Joint Conference on Artificial Intelligence, IJCAI 2023, 19th-25th August 2023, Macao, SAR, China, pages 1686 1694. ijcai.org, 2023. doi: 10.24963/ UCA312023/187. URL htttps://oos org/10. httg///.2996////// ljcai. 2023/187
[59] Elad Ben Zaken, Yoav Goldberg, and Shauli Ravfogel. Bitfit: Simple parameter-efficient fine-tuning for transformer-based masked language-moxlels. In Smaranda Muresan, Preslav Nakov, and Aline Villavicencio, editors, Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), ACL 2022, Dublin, Ireland, May 22-27, 2022, pages 1-9. Association for Computational Linguistics, 2022. doi: (0.18653/V1/2022 ACLL122222222-222222222222 BOL-022ACL--OOORRE SHORT.I. URL https: //dps://doi..o org/r//// 18663/v1/20222 acl- short.1
14

---

[60] Liang Zhang, Bingcong Li. Kiran Koshy Thekumparampil. Sewoong Oh, and Niao He. Dpzero: Private fine-tuning of language models without backpropagation. In Forty-first International Conference on Machine Learning, 2024.
[61] Sheng Zhang, Xiaodong Liu, Jingjing Liu, Jianfeng Gao, Kevin Duh, and Benjamin Van Durme. Record: Bridging the gap between human and machine commonsense reading comprehension. arXiv preprint 1iXiv:8810112855 2018.
[62] Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona T. Diab, Xian Li, Xi Victoria Lin, Todor Mihaylov, Myle Ott, Sam Shleifer, Kurt Shuster, Daniel Simig, Punit Singh Koura, Anjali Sridhar, Tianlu Wang. and Luke Zettlemoyer. OPT: open pre- trained transformer language models. CoRR, abs//205.au 01068, 2022. doi: 1044550/ARXXV.2205000666 org/10 10. ar550/ariiv.... 2205. 22...02063 01068
[63] Yihua Zhang, Pingzhi Li, Junyuan Hong. Jiaxiang Li, Yimeng Zhang, Wenqing Zheng, Pin-Yo Yu Chen, Jason Lec, Wotao Yin, Mingyi Hong, Zhangyang Wang, Sijia Liu, and Tianlong Chen. Revisiting zeroth-order reroth-orderropimmizttie optimization for memory Conference on Machine Learning, JCML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024.
LLM fine-tuning: benchmark. Forty-first International
URL
net/forum's ?id-THP J
[64] Ziyu Zhao, Leilei Gan, Guoyin Wang, Wangchunshu Zhou, Hongxia Yang, Kun Kuang, and Fei Wu. Loraretriever: Input-aware lora retrieval and composition for mixed tasks in the wild. In Lun- Wei Ku, Andre Martins, and Vivek Srikumar, editors, Findings of the Association for Computational Linguistics, ACL 2024, Bangkok, Thailand and virtual meeting, August 11-16, 2024, pages 4447-446) Association for org/ 2024 findings-----ii ac1.263
Computational Linguistics, 2024. URL httttpps:/aclaanoolllg/eo/ooo/eo
[65] Ruiqi Zhong, Kristy Lee, Zheng Zhang, Dan Klein. Adapting language models for zero-shot learning by meta-tuning on dataset and prompt collections. In Marie-Francine Moens, Xuanjing Huang, Lucia Specia, and Scott Wen-tau Yih, editors, Findings of the Association for Computational Linguistics: EMNLP 2021, Virtual Event / Punta Cana, Dominican Republic, 16-20 November. 2021, pages 2856-2878. Association for Computational Linguistics, 2021. doi: 10.18653/V 120/3//V//2221./// FINDDIGSS EMNLP.244 URL https://doi. org 10. 10. 1853/111115///2 Sindings-emnlp.. 244
15

---

Limitations and Broader Impact
This paper introduces an optimization framework that enhances the efficiency of fine-tuning large language models. By reducing computational costs and memory requirements, the approach promotes environmental sustainability and broadens access to advanced AI tools, promoting accessibility in Al development. While our framework is designed for scalability, we have not tested very large LLMs due to resource constraints. However, experiments sufficiently validate the research idea. Future work includes exploring masked ZO tuning for efficiency and applying our approach to style mixing in image generation models.
A Related Work
A.1 Zeroth order in fine tuning LLMs
McZO 35 is the first work to use Zeroth-Order (ZO) methods to finetune LLMs for downstream tasks. They demonstrate that their method is compatible with both full-parameter tuning and parameter- efficient tuning techniques, such LoRA and prefix tuning, while being significantly more computa- tionally efficient. Zhang et al. 63 provide a benchmark for ZO optimization in the context LLM fine-tuning, comparing different ZO optimizers and applying the method to various models. Gautam et al. [[0] introduce variance reduction techniques into ZO methods for fine-tuning, improving both stability and convergence. In addition, ZO methods are applied in federated fine-tuning by Qin et al. [1 and Ling et al. (25 Deng et al. S implement 70 optimization for softmax units in L.Mss. Guo et al. [14 and Liu al.
31 explore fine-tuning minimal subset of LLM parameters using 7O methods by sparsifying gradient approximation or the perturbations used in gradient estimation. Tang
al. 51 investigate the privacy of ZO optimization methods.
In contrast to previous approaches. we propose a bilevel training algorithm that effectively combines the strengths of both First-Order (FO) Parameter-Efficiee Fine-Tuning (PEFT) and ZO full-model fine-tuning. Our experiments demonstrate that the bilevel structure, when paired with the most suitable PEFT technique, outperforms both ZO full-model fine-tuning and FO PEFT methods individually.
A.2 Fine-tuning LLMss for Multitask and Few-Shot Learning
Multi-task learning (MTL) enables a model to handle multiple tasks simultaneously, fostering knowledge transfer between tasks and improving overall efficiency [36, [6). Typical meta-tuning approaches employ First-Order methods to train autoregressive LLMS on multitask dataset for
28 27 Zhong et al. [65] apply meta-training to tasks such hate speech detection, question categorization, topic classification, and sentiment classification. Guo et al. [13] adopt the method from Min al. (36] for generating stylistic text. While Min et al. 36 focus on enhancing the in-context learning ability of the meta-trained model for multitask learning, Zhong et al. [65] focus improving zero-shot performance. This approach is particularly valuable low-resource settings, where collecting large labeled datasets can be costly, as is often the case with medical data. In such environments, few-shot learnin-
various tasks 665] 36
13
model is fine-tuned on a high-resource dataset to quickly adapt to new tasks with minimal daca-becomes essential [57] To address the challenges of multi-task and few-shot learning in natural language processing, several meta fine-tuning methods have been proposed [17] 64, 57, 1 However, traditional meta fine-tuning approaches, such as MetalCL (36), still require full-model first-order gradient calculations, which become computationally expensive with large language models (LLMs) containing billions of parameters. During training, Min et al. [66] sample a task from the dataset for each iteration to perform in-context learning. In contrast to Zhong et al. 65 and Min et al. (36), our approach uses a bilevel structure: the full LLM is fine-tuned (PEFT) models are tuned at the lower level. At test time, we freeze the meta-tuned base model and fine-tune only the PEFT model using few-shot setup, which both more cost-effective and efficient. Crucially, Min et al. 36 fine tune the full model with first order methods, while we employ ZO method in meta-tuning the base model at the upper level. Our approach allows us to bypass the need for backpropagation in the meta-model, significantly reducing computational costs.
the upper level, while parameter-efficienn fine-tuning
16

---

A.3 First-order Methods for Bilevel Optimization
Solving a bilevel optimization problem is challenging because the function value in the upper-level objective depends on the optimizer of the lower-level problem. This makes it difficult to compute the gradient of the upper-level objective, also known as the hypergradient. Classical methods require calculating Hessian- veettor multiplications to approximate the hypergradient [8 However, when fine-tuning large language models, this process becomes extremely expensive due to the high computational and memory demands.
23
43 12 32]
Recently, new frameworks for bilevel optimization have been introduced 33 46 29
21
26
18 34
These methods bypass the need for second-order information by reformulating the bilevel problem a constrained optimization problem. The constraint penalized, allowing the problem to be tackled as minimax problem using only first-order information. These methods significantly reduce computational costs by eliminating the need for second-order information. Nevertheless, when fine tuning LLMs, back propagation for calculating the gradient of an LLM is still too expensive.
Liu et al. 29 and Lu and Mei 33 explore the convergence of their proposed methods to the original bilevel problem, while other approaches only demonstrate convergence to the penalized problem. In this paper, we adapt the method from Lu and Mei 33 approximate part of the upper-level parameters using a ZO approximation in order to address the challenge posed by the large number of training parameters in large language models. We also provide convergence guarantees for this adapted zeroth-order-firstoone method.
B Theoretical guarantees of Bilevel ZOFO
In this section we give convergence guarantee for Bilevel ZOFO. Suppose (0.p) p) E Rd+d' and E ngd The following assumptions are made throughout this section.
Assumption B.1. We make the following assumptions:
G(O, p. can be potentially nonconvex and G(.,,s) is T- strongly concave; F(O, p) is twice continuously differentiable O.P.
G is f-Lipschitz smooth in RR42d' i.e. v(O1, Pı, 81), (0,, P2, 82) Rd+2d"
P2,
(I,(O,,Pi,s)) - (G,00,,p2882) S
(1((0),)I,s:) (02, 82)
We define == l/T the problem condition number.
p.s) E R2+22 sample estimates satisfy
E[G p. { = G(O,
E p. [] VG p.s),
σ²
p. E [V - p.s(.
B
for sample & with size [ = B and constant σ > 0.
max, G(O, p, s) is lower bounded.
We first discuss the relationship between the optimality condition and 2p. We start with defining the e-stationary points of 4 and (2) for general bilevel and minimax problems. In the following definitions, the expectation is taken over the randomness in the algorithm that (x,y) is generated. Definition B.2. Given a bilevel optimization problem
min f(x, y" (x)). y" (x) E arg min g z)
and any 6 > 0, a point (x,, ) is called an e-stationary point
E | fx,, y (x.)) < O(e), f(x. min f(xe, z) S
Definition B.3. Given a minimax problem
min max y(x
17

---

and any e > 0, point Ye) is called an e-stationary point if
|| V v y.) - e, Eill yf y ))ll e.
Lemma B.4. If assumption B.1 holds and X 1/e, assume that FO,)) is Lipschitz continuous and s. is an e-stationary point of 4 then (0, s) is e-stationary point of (2)
The following is the low effective rank assumption from 33 This assumption avoids dimension in the total complexity. Following [35], assume here that z" in (7) is sampled from shpere in R with radius vd for ease of illustration.
Assumption B.5. For any (0, p,s) E IRd+2d" there exists matrix H(0, p,s) such that (' p. 3 ((O.p.s) = é- La and (0. sr- s)ll
Theorem B.6. If Asssmpttioss B. and B.5 hold, by setting
1
26r A
- O
28
(En (d d') ( (ogg((e 1)),
K = O(rre" -2)
there exists an iteration Algorithm that returns an e-stationary point (0, p. s) for 5 and satisfies
(0I & O(e,, F(0,s; s;) - min F(0,p;
p: S.
Remark B.7. The total number of ZO gradient calculations is
TKB: + KB2 = 0 xre re log(ec))))
This result matches the complexity in previous ZO minimax algorithm in (55) but solves our bilevel optimization problem (2) and does not depend on the dimensionality d thanks to the efficient rank assumption B.5 providing efficiency guarantee for our algorithm.
C
Method
C.1
Proofs
In the proofs we use the simplified notations x = (0.p), := f(x,)) == (() arg maxy (xxy) and g(x) f(x, y" (x)).
C.1.1 proof of lemma B.4
First we introduce some lemmas from previous literature.
Lemma C.1. (Lemma 1.2.3, Theorem 2.1.8 and Theorem 2.1.10 (37)
Suppose function h is Li Un-gradienn-Lipshiie and has a unique maximizer x*. Then, for any x, we have:
La
[[Vh(x)]12 M(x*) M(x)
|| 11
(15)
2T
2
Suppose a function h is Th -t-soongyly concave and has a unique maximizer x*. Then, for any x, we have:
1
x - -
< - h((x) -
(16)
2
2Th
From lemma C.I.and and the definition of e-stationary point (in definition B.3) we can get the following lemma.
B.1 holds and (XexYe) is an e-stationary point of Lemma C.2. Suppose assumption
ming maxy y), let (0,, P.) x, we have
F(0.,s.) min F(O.,s) 00 2
18

---

Upper Level
Zeroth Order
Classification Loss (eg: SST2)
Base Model
Penalty from the Lower Level Loss
First Order
PEFT Model (P)
PEFT Model (P)
Lower Level
*
Base Model
+1
First Order
Classification Loss (eg: SS12)
PEFT Model (S)
Figure 5: Bilevel ZOFO optimizes LLM fine-tuning by solving bilevel problem using penalty- based minimax approach, combining zeroth-order gradient estimation for LLM updates and first-order methods for PEFT parameters.
Proof.
F(O.,S.) min F(,,,)) IV s.) (V
1 X²r
1
1Vy s 2o 5 x
here the first inequality is from Lemma C.I applied to - and the second inequality from definition
The following a rephrase of theorem 2 in 33
Proof. (proof of lemma B.4) By Lemma C.2 and the value of À we have
F(Q., s.) min F(O.. s) O(e*).
Therefore, by Theorem 2 33 have (I) S O()) and Lemma B.4 proven.
C.1.2 proof theorem B.6
Based on Lemma B 4 it suffices to prove that the algorithm 2 outputs an e-stationary point of ming maxy f(x, y. In this section we will prove this conclusion.
First we introduce the smoothed function of f. which will be useful the proof.
Lemma C.3. (Lemma C.2 in (60)) Let be uniformly sampled from the Euclidean sphere v Vdsd-1 and v be uniformly sampled from the Euclidean ball Vdld = {x E Te ||x|| S Vdy. For any function f(x): gdd + R and a > O, we define its zeroth-order gradient estimator as:
f(x + au) f(x au)
V (x)
2a
19

---

and the smoothed function as:
fa(x) = ExIf(x + av)].
The following properties hold:
(i) fa(x) is differentiable and Eu V [x (x).
(ii) If [(x) is 8-smooth, then we have that:
- Vff(xl) & 3 _ad
If we use fxx y; denote forward evaluation with random samples & and let batch size B |< then f f(x. E) is function from I& to R and Ł-smooth. The above lemma can be used f f(x.
and f(x, E). We can define its smoothed function fa(x; {) and has the properties above.
Lemma C.4. If dfassumption B.1 holds, for fa defined in Lemma C.3 Vxfa(x, y) is E-continuous on i.e.
Vxfa(x,y1) Vx)a(x, S flyy y2ll.
for any x E Rd. Y2, E Rdd..
Proof.
[ Exff(x+ ov, y2)ll (x - f(x + y2)
<(lly; y2ll-
Here the first inequality is from the convexity of norm and the second inequality is from the f- smoothness of] f-
2 Using the simplified notations we can write the update step in the inner loop y y + 1) V y (x*, : Et). We use Bi, B2 to denote the batch size for the inner loop and outer loop, respectively. But finally we will prove that they are in fact of the same order.
We first give the iteration complexity of the inner loop of Algorithm
Lemma C.5. In Algorithm
by setting 1/28, T = =O(x (ok(()) and B = ( we have Ellly - y-"(x") (x**)11 s²
in outer loop k.
Proof.
Ilył+1 yd (xx)))1
= =Ily + Vxx"' - (x2))1
=Ily? (1+) f .f: - + (x:: E.)1.
Now taking expectations on both sides we have
Ellly y" 11*
<E]ly?? yx(x*) || ( fx" yf) - y (x+))) + 7 (EIIV xf) a² /
1?02
<Eilly² - (x*))) Ef y" (x*)) - f(x": . + 2 Blf(x" y (x*)
f(x . B1
=Eilly y" [xx
22 Elf (x** y (x*)) - fxt st)1 +
4
0²
<E y" (x+) - FBll y" (x* (x
482
20

---

The first inequality is from Assumption B.1. second and last inequalities from Lemma C.1 and the equation is from the value of 17. In order for Fllly y" (x** < 2 we need = O( log())) and B1 = O(c
The following lemma is from Theorem 1 in 35
Lemma C.6. If Assumption B.5 holds, there exists constant 7 =r(r such that
x :) H(x", ++1 V y + :01 < (x V /
:01)).
Finally, we give the proof for Theorem B.6 In this part we assume both and updates with zeroth order gradient for the convenience of analysis and this does not change the order of the total complexity.
Proof. (proof of Theorem B.6
From Assumption B.5
taking expectation conditioning on x² and y we have
Elg(x k 5x(xx) - <(V (x [ ()1
2² + Z 1x -) 4 , ;k+
2
5g(xt) <(Vxg(>>>>>>>>>>>>><<<<') ) (a y 22 &11l V (x y
Let us bound the inner product term:
- -((Vxs(x*), V
S - <(Vx((X"" (x*)) Vxfa(x y (x*)) - Vxfa(x' y y (x*))
Vela(x", Vzfa(x* (xla(xt,yttl)
Vx
VVJa (x" y 21112
4
(267
+
(x*)) (x* 212
|V
fx* y1
4
<(Vafa y ,+1), (x* )
R2d +
1 Mby By (x*) 112 + (²07
<(VoJa(x* y ) (x y x+1))
Here the last inequality is from Lemma C and Lemma C.4
Now back to the original inequality, taking expectations over all the randomness in the algorithm we have
5(1 cey
V fa fx"
y 11
2
22 E V .
2²ed
<Eig(x*) |(x
Ellly (xe*) - +1
47
22
<2ky02
2ddd
<Eig(x") -(xx++1)]
Ellly (xx*) 1
Elll V f(("
111
2B
47
where the last inequality is from Assumption B.I
21

---

On the other hand, from Lemma
C.3 by letting < = 28y
1_
we have
++1) |
a (d d')
<21|||| V afa
11
2
16
- (X
9(x -(xx*11) }] E (x*) -y y 119
k+1
3
3
+ 2
BIIV f (xx
|
+ 20
+
11
(2 + ddys
3
3B2
6
=BIIV=J[(x
|1 1667 - (())+))] + Elly" (x*) - +y1+
20 11
+ + a² e (d d'ys
B2 2
Taking summation of k from 1 to K we have
K+1
[ [(x )(
K k=1
1667
16
20²
11 a (d (d+
Elg(x)) 0(x*+11
Bllly* (x -
"2a
K
K
B2
1667
16
20
$
Elg(x+) - min 9(x)]
+
Ellly* (x*)
1 +
+ a² (d (d
K
K
B2
2
A
Thus, by setting parameters as in Theorem On the other hand, since
B.6 we have ming B(] Vx/ y ) 112] S 2
V fx* .y *+ | Bil v (xx,yxx)))))) yhtl) Vyf(x".''
y (xx)) EBlly h+1 1---t+1-00 - y" (xx )1
similar to Lemma C.5 we have B|ll V vxf(x*, y S e² by setting T = 0(k (()l))()) and
B1 = =
D Experimental Setup
D.1 Single-Task experiments
Following MeZO 35
we evaluate our approach on a range of classification and multiple-choice
tasks: BoolQ
3
CB
[54]
CB [54], COPA 44) ReCoRD: [TT) [53], SST2 [53], WiC (39].
WinoGrande
45 In this setting, training and testing are conducted on the same task.
Hyperparameter Search Given resource limitations, we focus on sweeping only the learning rate as the key hyperparameter. For McZO and first-order PEFT experiments, we explore learning rates from the set {le - 2, 1e 3, 1e 4, 1e 5, 1e 63. For Bilevel-ZOFO, we sweep both the upper-level and lower-level learning rates: lrupper E {le 4, 1e-5, 5, 1e 1e-6) and Injowrr E {le-2, 1e-3, 3, 1e 4, 1e- 5). We perform all experiments in tables 7 and 8 using three random seeds and report the average and standard deviation. We also set c = le 3, Following MeZ0 35
D.1.1 Training
All experiments used batch size of 8 and were conducted in b precision single A6000 Ada 48GB GPU. MeZO was run for 10,000 steps, while FO and Bilevel-ZOFO methods were run for 5,000 steps. Our implementation builds upon MeZO's ' codebase, and memory profiling as well as latency calculations are based on their framework.
For each task, 1000 examples are randomly sampled for training, 500 for validation, and 1000 for testing. For bilevel-ZOFO, the training set split into upper-level and lower-level subsets with a 1:2 ratio. During each lower-level update, only the PEFT parameters are optimized, while in the
22

---

upper-level step, the entire model is fine-tuned using zeroth-order gradient approximation. We set 10000 and perform 10 lower-level updates between each upper-level update for all bilevel-ZOFO experiments.
All experiments use the Adam optimizer 20 including baselines and both lower-level and upper-level optimizers. No weight decay was applied, and the models were trained with a constant learning rate schedule. Batch size is set to 16 for all experiments. We load all models in blloat16. We find the best performing model based on validation loss and report test results from that checkpoint. We report the test accuracy or Fi-score based on the test dataset being imbalanced or not.
We fix the memory budget of each step across bilevel-ZOFO and the baselines. We train zeroth- order methods for 10,000 steps, and Ailevel-ZOFO and first-order methods for 5000 steps. We use A6000ada 48GPUs in our experiments. We load all models in bfloat16.
D.2 More Results for single task fine tuning
Table 7 presents the detailed test metrics when applying bilevel-ZOFO and baselines to fine-tune
OPT- 1-T-1.31 .3B [62 on a downstream task.
Traser
Mak
Beck)
CH
Copa
AcCokD
KIE
5512
WIC
WaxChaak
WSC
Averas
16827 8100690
182567
0.3392
(05530
(1659)
(11651
016677
0.554)
3.5453
3.617 01053
kmp
2010012
= $1400
porrpt
01539)
0.0655
(8591
9.0079
037057
6 0.0055
0.7570
6.0651
05415
0.0063
0.763--00 0.055
03551
- 0.046
05556
- 01606
0-454
- 01616
5.804-1
(1:083
(L3333
112292200.00
0.1232
0.5039
0.483
01077
01166
0.674
51010
DO
preept
W2
18577
6-188035
4-9
1663
116666
6 6-80775
1087
10466
3.041
-00143
6.124
EJ00/
01556
011164
02121
05540
0.5:41
3.082 00150
Doo
porepp
032300 8-0 1995
0533
01
2-0
B 2234
--0
0-0 L0B
13 8590
- 1010
62-7
- 1053
0150
00056
3
3.7355
0117
6,700
EJ012
67885
67706
0.7280 2 01026
Table 7: Single- Task Experiments on OPT-1.3B with 1000 samples. Values correspond to mean across three random seeds. FO: First-Order. FT: full-model fine-tuning.
Table S demonstrates the results for fine-tuning Llama2-7b [52 on various classification and open- ended generation tasks.
D.2.1 Compare with the two-stage pipeline
To also validate that the improved results are not because of tuning more parameters, we conducted an experiment on COPA using OPT1.3B and compared Bilevel-ZOFO to two-stage pipeline that tunes the same number of parameters. First, we performed first-order prompt tuning for fixed number of steps (same the number of lower-level updates in bilevel-ZOFO), followed by additional tuning using ZO for the same number of iterations as the upper level updates in Bilevel-ZOFO (A two-stage pipeline). As shown in Table 9 even with extensive hyperparameter tuning, the second stage does not improve the results achieved after the first stage and is highly likely to decrease performance. Our method, however, improves performance when using the same number of steps in the upper and lower levels, respectively. The bilevel structure makes the trained prompts dynamically optimal for the full ZO fine-tuning and reaches an accuracy of 76.33.
Trainer
Mode
BoolQ
ReCoRD
SQUAD
SST2
Average
ft
0.7915 0,0516
0.7890 0.0001
0.7737 0.1634
0.8646 0.0216
0.8047
lora
0.8020 + 0.0014
0.7970 + 0.0001
0.7412 + 0.0013
0.8529 + 0.0117
0.7983
McZO
prefix
0,7830 + 0.0131
0,7905 = 0.0007
0.7093 + 0.0207
0,8364 + 0.0010
0.7798
prompt
0.7787 = 0.0049
0.7935 = 0.0007
0.7014 # 0.0451
0.8246 + 0.0216
0.7746
lora
0.8420 + 0.0104
0.7920 + 0.0053
0.8197 + 0.0043
0,9557 + 0.0007
0.8524
FO
pretix
0.7783 = 0.0021
0.8013 = 0.0012
0.7946 + 0.0419
0.9243 # 0.0053
0.8246
prompt
0.8083 = 0.0142
0.8023 = 0.0074
0.7805 + 0.0633
0.9284 = 0.0072
0.8299
lora 0.8473 = 0.0025
0.8290 = 0.0044
0.8160 + 0.0041
0.9629 + 0.0053
0.8638
Ours
pretix
0.0122
0.8067 = 0.0065
0.8090 + 0.0302
0.9382 = 0.0064
0.8433
prompt
0.8145
0.8108 0.0065
0.7960 0.0028
0.9222 0.0039
0.8359
Table 8: Single-Task Experiments on Llama2-7B with 1000 samples. Values correspond to mean and
std across three random seeds. FO: First-Order. FT: full-model fine-tuning
23

---

trainyless
10 Mymlullm
(a) First-Stage PEFT
(b) Second-Ste Stagd---teeeeaa MeZO
(c) Bilevel
Figure 6: The training loss curves for both stages of two-stage approach (a and b) and our bilevel framework (c).
The observed performance drop after the second stage is indeed counter-intuitive at first glance. However, is limitation of MeZO it approx- imates gradients. While further fine-tuning intu- itively should improve performance. the inher- ent noise in gradient approximation can lead to suboptimal updates. This observation is consis- tent with the fact that MeZO typically requires significant number of iterations converge. This is key contribution of our work: Our ap- proach addresses MeZO's challenges, such sensitivity hard prompts and long convergence times, while outperforming both MeZO and PEFT and maintaining similar memory efficiency. The intuition behind why our method is effective in enhancing both MeZO's s full-model tuning and PEFT is in the nested bilevel structure. This structure encodes more information (as reflected in the training method) from the prompt tuning stage than only treating guidance for MeZO. In contrast, our bilevel method effectively addresses the issues of Me70 and demonstrates improved performance over both MeZO and the PEFT baseline, even with the same number of ZO iterations. This phenomenon that silevel-method is better than a two-staged pipeline also observed in the later work on diffusion models 49
Method
Experiment (COPA)
Ace
After Stage
74.33
After Stage (Ir 0.001)
$1.66
Two-Stage
After Stage (Ir 0.0001)
70.33
After Stage (Ir 0.00001)
72.66
After Stage (Ir 0.000001)
74.33
Bilevel-ZOPO
76.33
Table 9: Comparison of Bilevel-ZOFO with two- staged pipeline.
first stage. thereby providing better
The training loss curves for both stages of a two-stage approach and our bilevel framework are provided in Figure When running MeZO in the second stage, the training loss exhibits oscillations and does not show improvement within 500-1000 iterations. This behavior is consistent with findings in the original MeZO (35) paper, which notes that McZO typically requires much longer to converge- on the order of 100k iterations. The oscillatory behavior observed within the shorter training duration is not surprising due to gradient approximation errors.
D.3 Multi-task experiments
In this section explain the experimental details of mutil-task experiments.

---

D.3.1 Meta-Tase Tasks
Following the methodology of Min et al. [3], we evaluate the performance of bilevel-ZOFO as a fast and efficient meta-learning algorithm. We perform experiments using four of the distinct meta-learning settings outlined in MetalCL [3) classification, QA-to-QA, and non-QA-to-QA Each of these meta-leaming lasks includes a set of training sub-tasks and different set of test sub-tasks. The sub-tasks are sourced from CROSSFIT [57] and UNIFIEDQA [99), comprising a total of 142 unique sub-tasks. These sub-tasks cover a variety of problems, including text classification, question answering, and natural language understanding, all in English. Table I0] shows the number tasks in each training and testing meta-lcarning setting and the total number of examples in each training task.
non-classificationtt
Meta-train Setting
tasks
# examples
Target Setting
# tasks
Classification
43
384,022
Classification
20
Cln-Classifiiation
37
368,768
QA
37
486,143
QA
22
Non-QA
33
521,342
Table 10: Details of four different meta-learning settings, Each row indicates metaatrainnnngttrre tasks for each setting. There is no overlap between the training and test tasks.
See Tables 14 and 15 of MetalCL 36 for a list of all sub-tasks.
D.3.2 Baselines
We use GPre-Large as the base model for these experiments. We compare our method against several baseline approaches:
42
MetalCL [36]: A method for meta-learning with in-context learning. MetalCL tunes all the parameters of the base model using the first-order method. In both training and testing, the model is given k demonstration examples, (a1, b1). ................................ (ax. by), where b; represents either classification labels or possible answers in question-answerrreee answering tasks, along with one test example (a, b). The input is formed by concatenating the demonstration examples 01, bi.....00 0g: be, a. The model then computes the conditional probability of each label, and the label with the highest probability is selected as the prediction.
Zero-shot: This method uses the pretrained language model (LM) without any tuning, performing zero inference without any demonstration examples.
In-context Learning (ICL): This method uses the pretrained LM with in-context learning by conditioning on a concatenation of l demonstration examples and actual test sample similar to MetaICL.
We sample 768 examples from each training sub-task. We use these samples to train MetaICL in their original setting for 30,000 steps. This includes learning rate of 1e 1--5, batch size of on 8 GPUs, 8-bit Adam optimizer and fp16 half precision. See MetalCL[[36 for full details. To train our method, we split the training dataset of each sub-task to two subsets, 256 samples as the development dataset for upper-level updates and 512 samples for lower-level training. For each outer iteration of our method, we randomly sample a subset of training tasks. We perform lower-level updates between each pair of lpper-level updates. To keep bilevel-ZOFO not include demonstration examples in the inputs. Since bilevel-ZOFO uses significantly less memory and has much faster updates compared to MetalCL, theoretically are able to train it for many more iterations within the same total training duration as MetaICL. However, due to resource constraints, we only train bilevel-ZOFO for 50,000 iterations. Similar to [35, we did not observe a plateau in performance for DoOFO indicating that further training can yield additional improvements. We use Adam optimizer and learning rate of 1e 6 for both upper and lower-level training. We employ a batch size of 4 and train on single rtx6000ada GPU.
lightweight as possible, unlike MetalCI, we do
For both ICL and MetalCL, during the testing phase the model is given k = 4 demonstration examples for each test data point. We don't use demonstration examples in test samples for bilevel-ZOFO evaluation. We evaluate the shro capabilities of our method as well as the performance of the
25

---

final model LoRA-tuned for 10 additional iterations on 4 demonstration samples from each class of each sub-task. Similar [36]. we report Macro-averaged F1 the evaluation metric.
D.4
Additional Experiments and Clarifications
D.4.1 Full First-Order Fine- Line-Tuning (FO-FT) Baselines
Our problem setting targets memory/throughput-oo contoogtpputt-ontttiineededd fine-tuning where full first-order (FO) updates on all backbone parameters are often impractical. Accordingly, the main paper emphasizes comparisons against PEFT and ZO methods that are actually deployable under such constraints. Here we include FO full finetuning results on identical data splits and evaluation protocols as our single-task experiments to contextualize the gap in Table 11 and Table 12
Table 11: FO-FT OPT-1.3B (accuracy).
Method
BoolQ
CB
COPA
ReCoRD
RTE
SST-2
WiC
WinoGrande
WSC
PO-FT
0.660
0.821
0.730
0.719
0.690
0.937
0.586
0.526
0.635
Table 12: FO-FT on Llama-2-7B (aceuracy).
Method
BoolQ
ReCoRD
SQuAD
SST-2
FO-FT
0.863
0.814
0.801
0.952
D.5 On Task Choice (Math/Code vs. Other Benchmarks)
We acknowledge the community's current emphasis mathematical reasoning and code generation, but real-world fine-tuning spans QA, classification, retrivval-augment workflows, and recommen- dation. These practical settings still require task-specific instructions and remain sensitive prompt formats. To demonstrate that our observations about MeZO's prompt sensitivity also hold on popular reasoning tasks, include GSM8K study in Table 13
Table 13:
Prompt sensitivity on GSM8K (accuracy).
Method
With prompt (nabssiroo
Raw format
McZO
0.329
0.122
Bilevel-ZOFO
0.762
0.744
D.6 Code & Math Experiments
We conduct code/math experiments to demonstrate transfer beyond small classification suites. Train- ing details: Qwen2-7B is trained on GSM8K (train), HumanEval (train), and Math500 (4:1 train/test). is evaluated on the standard test splits. LoRA and Bilevel-ZOFO are trained for 2000 steps. McZO trained for 10000 steps. Metrics are accuracy (GSM8K, Math500) and pass @ (HumanEval), Across GSM8K, Math500, and HumanEval, Bilevel-ZOFO consistently improves over LoRA and strongly over MeZO.
D.7 Other PEFT Variants
Bilevel-ZOFO is a framework: the lower level can adopt any FO-PEFT method and the upper level any ZO estimator. To illustrate compatibility beyond LoRA-style adapters, we add results with DePT [47]. prompt-tuning method in Table [5] We see gains persist when swapping a stronger PEFT variant.
D.8 More Realistic Applications
We showed the applicability of bilevel-zofo in Meta Learning. Future work can explore bilevel-zofo in Multi-Tas Task Reinforcement Learning to tune LLM multiple domains. Also another application
26

---

Table 14: Qwen2-7B on math/code tasks.
Method
GSM8K (acc)
Math500 (acc)
HumanFval (pass 1)
Before tuning
0,420
0.18
0,476
LoRA
0.727
0.28
0,518
MeZ0
0.329
0.05
0.110
Bilevel-ZOFO (ours)
0.762
0.31
0.543
Table 15: Llama-2-7B with DePT (accuracy).
Method
BoolQ
SST-2
DePT
0.813
0.932
MeZO
0.792
0.865
Bilevel-ZOFO + DePT
0.852
0.946
of bilevel-zofo is in Federated or privacy-sensitive scenarios where clients can run small FO-PEFT steps locally and aggregate ZO signals centrally, which we leave future work.
27

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
We provide theoretical analysis in Section B and empirical results in Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Provided in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
28

---

Justification:
We provide a theoretical analysis with proof' and assumptions in Section B
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: All experimental details are provided in Section and D
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
29

---

Answer: [Yes]
Justification: All datasets used are open source. We will provide the code for our experiments after paper decision is available.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm ec/
public/guides, htwps///oooeeuubsssssoooooooo
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https http://ooooSuuiisssodsee
//nips. //nips.cc/pil wwwppbblccgguiicuceccccccoeooopp
htt.SSbbbiiiiooooiiiiiooooi for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All experimental details are provided in Section and D
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
We provide mean and standard deviation of values in Section D.2
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
30

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: All experimental details are provided in Section and information.
D
They include this
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
There are not ethical concerns that we know of.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: discussion of broader impact provided in Section 6 Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
31

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All original owners of assets have been properly cited.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
32

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
33

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
34


Reviews:
[{"review_id": "9ZyFy0zi2X", "reviewer": "Reviewer_CENo", "summary": "The paper introduces Bilevel ZOFO, a bi-level fine-tuning algorithm for memory efficient training of LLMs. The method proposed uses improvements from both first-order (FO) PEFT and zeroth-order (ZO) tuning methods to improve overall model quality. The authors identify that ZO take long training durations to converge and have affinity to certain prompt formats. On the other hand, PEFT methods like lora are not able to fully achieve the same model quality as full-finetuning. The authors propose a bilevel optimization framework, where both FO-PEFT + ZO are combined. The base model is updated only using ZO, while the PEFT weights are updated in a low-level pass at some update frequency. By combining these two methods, the authors show better performance over either method on some downstream tasks. They further extend their method to meta-learning and show improvements over conventional methods such as Meta-ICL, while being more compute (memory + throughtput) efficient.", "questions": "1. the paper looks at very simple classification tasks for experimental evaluation. Have the authors tried it on more difficult tasks such as code / math tuning and have been able to see any success from the method ? \n2. For methods like lora, there have been many more advancements in the literature, that enable high quality PEFT training. Did the authors look at those and see if any of them are more useful in the setting of ZOFO?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n1. The method has good convergence guarantees and all proposed lemmas have proofs that can be followed. \n2. The method improves over standard PEFT and Zero-Order (ZO) methods, including some limitations of ZO methods such as affinity to prompt structure and longer training intervals.\n3. The paper has ablations for different design choices related to the final algorithm, showcasing the strengths of the designed method. \n4. The method is easily adaptable to meta-learning settings, where it outperforms methods such as Meta-ICL on several tasks, while being more compute efficient and taking lower time per training iteration. \n\n**Weaknesses**\n\n1. For most of the main experimental results, we see comparisons against lora and other peft methods, but there is no full fine-tuning with first order methods to compare as a baseline, so as to understand the gap that ZO or PEFT methods have and how much of that is ZOFO able to cover.\n2. There are some parts of the paper which are tricky to follow. For example, in Section 3, when the original method is being introduced, a lot of variables such as $D_f$ and $s$ are explained after their use in equations. Also, usage of dimensions such as d vs d' etc. are not explained beforehand. It took some time and multiple re-reads of the section to fully understand this part. Would recommend rewording and introducing necessary notations for clarity.", "was_revised": true, "final_justification": "The authors addressed my concerns. I did not raise the score beyond the original rating, since the paper is not a groundbreaking work - there are some technical challenges in scaling this work to larger datasets and model sizes.", "rebuttal": "We thank the reviewer for the positive assessment and the thoughtful feedback. Below we address the main points and list concrete updates made to the paper.\n\n---\n\n## 1. Full First-Order Fine-Tuning Baselines\n\n Our problem setting targets memory/throughput-constrained fine-tuning where full first-order (FO) updates on all backbone parameters are often impractical. This is stated in the motivation (Introduction and Problem Setup). We therefore emphasized comparisons against PEFT and ZO methods that are actually deployable under such constraints.\n\nPer the request, we now include FO-FT results to contextualize the gap. These runs use the same data splits and evaluation protocol as our single-task experiments (see Experimental Setup). We will add a short resource note beside the table so readers can see the cost profile of FO-FT versus PEFT/ZOFO. The resource usage comparison of FO FT and FO PEFT and MeZO can also be found in the MeZO paper.\n\n**OPT-1.3B (FO-FT)**\n\n| boolq | cb    | copa  | record | rte   | sst2  | wic   | winogrande | wsc   |\n|-------|-------|-------|--------|-------|-------|-------|------------|-------|\n| 0.660 | 0.821 | 0.730 | 0.719  | 0.690 | 0.937 | 0.586 | 0.526      | 0.635 |\n\n**Llama-2-7B (FO-FT)**\n\n| boolq | record | squad | sst2  |\n|-------|--------|-------|-------|\n| 0.863 | 0.814  | 0.801 | 0.952 |\n\nThe new results do not change our conclusions: **Bilevel-ZOFO outperforms FO-PEFT and MeZO at comparable memory and narrows the gap to FO-FT while remaining much more efficient. It also acts as a strong efficient meta learning algorithm.**\n\n---\n\n## 2. Clarity of Section 3 and Notation\n\nWe revised  section 3 for readability:\n\n- Introduced parameters and dimensions before use.\n- Reordered equations so definitions come before usage.\n- Added a compact Notation section.\n- Added forward references from main-text claims to the specific lemmas in the appendix.\n\n---\n\n## 3. Beyond “Simple” Tasks: Code and Math\n\nWe followed MeZO’s protocol for comparability, and these kinds of tasks remain widely used in practice. We agree that adding more challenging tasks Weill improve the paper so we have added harder settings to test generality.\n\n**Setup (Qwen2-7B):**  \nGSM8K (train/test), HumanEval (train/test), Math500 (4:1 train/test split).  \nLoRA and Bilevel-ZOFO trained for 2,000 steps; MeZO for 10,000 steps.  \nMetrics: accuracy for GSM8K/Math500; pass@1 for HumanEval.\n\n\n| Method             | GSM8K | Math500 | HumanEval (pass@1) |\n|--------------------|-------|---------|--------------------|\n| Before tuning      | 0.420 | 0.18    | 0.476              |\n| LoRA               | 0.727 | 0.28    | 0.518              |\n| MeZO               | 0.329 | 0.05    | 0.110              |\n| Bilevel-ZOFO (ours)| 0.762 | 0.31    | 0.543              |\n\nAcross all three tasks, Bilevel-ZOFO improves over LoRA and strongly over MeZO.\n\n---\n\n## 4. Other PEFT Variants\n\nAs we mention in the paper Bilevel-ZOFO is a framework: the lower level can use any FO-PEFT and the upper level any ZO estimator. Another reviewer has mentioned DePT [1] (not a lora variant but a prompt tuning variant) and to demonstrate compatibility with other PEFT methods we added support for that:\n\n**Llama-2-7B with DePT**\n\n| Method           | BoolQ | SST-2 |\n|------------------|-------|-------|\n| DePT             | 0.813 | 0.932 |\n| MeZO             | 0.792 | 0.865 |\n| Bilevel-ZOFO+DePT| 0.852 | 0.946 |\n\nWe can see that gains persist when swapping in a stronger PEFT variant. If there is a specific LoRA variant that the reviewer is interested in, we would be happy to compare with it.\n\n---\n## 5. References\n[1] DePT: Decomposed Prompt Tuning for Parameter-Efficient Fine-tuning. In ICLR 2024.\n\n---\n\nOnce again we thank the reviewer for their valuable feedback."}, {"review_id": "4tvKOgTdaW", "reviewer": "Reviewer_WksX", "summary": "This paper proposes Bilevel ZOFO, a fine-tuning method that combines parameter-efficient fine-tuning with gradient-free (zeroth-order) optimization for full-parameter fine-tuning. Experimental results show that the proposed method has certain advantages over either approach individually.", "questions": "1. In the description of Algorithm 1, it is recommended to add explanations for different symbols.\n2. The equations after line 113 do not have equation numbers.\n3. The definitions of symbols $s$, $K$, and $T$ should be explicitly stated.", "limitations": "yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n1. This paper presents a bilevel fine-tuning method, where introducing a certain degree of gradient computation increases the stability and convergence speed of zeroth-order optimization algorithms.\n2. The proposed method does not significantly increase memory usage.\n\nWeaknesses\n1. The writing of the paper is not good. The abstract’s explanation of the motivation appears to be more like a direct combination of MeZO-type work and PEFT-type work, which leads to an unclear statement of the core issue in the introduction and affects readers’ understanding of the main contributions. In addition, the presentation in the methods section is not clear, and some symbols lack explicit definitions.\n2. The novelty is limited. The paper simply combines MeZO and gradient-based PEFT without clear improvement or contribution, and this combination lacks reasonable practical significance. The core advantage of MeZO is that it does not require backpropagation, which is applicable to many deployment hardware devices. The core advantage of PEFT is to obtain good model adaptation with limited training resources. I cannot imagine a realistic application scenario for the method proposed in this paper.\n3. The experiments are limited. Since the proposed method allows gradient backpropagation, it is recommended to use larger-scale SFT datasets for tasks such as mathematical reasoning and code generation for validation, rather than only using subsets of classification datasets as in purely gradient-free methods like MeZO.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed review. Below we address each concern and list concrete edits we made (with pointers to the paper).\n\n---\n\n## 1. Writing, motivation, and method presentation\n\nWe revised the abstract and introduction to state our motivation clearly and consistently. Our goal is to combine the strengths of MeZO-style ZO and FO-PEFT:\n- ZO on the backbone enables tuning all model weights while keeping memory low.\n- A small FO-PEFT inner update allows quick adaptation from few examples, stabilizes ZO search, and reduces prompt/format sensitivity.\n\nThese design choices are intentional, as they enable efficient meta-learning: full-model capacity supports adaptation across tasks, while the PEFT steps provide fast, low-memory updates from limited data. This “best of both worlds” approach is our core goal. While there are many ways to combine MeZO and PEFT, our method is specifically designed to address MeZO’s sensitivity to task prompts by mitigating prompt sensitivity. We will ensure this motivation is stated clearly and consistently in both the abstract and introduction.\n\nIn method section, we have:\n- Introduced parameters and dimensions before use.\n- Reordered equations so definitions come before usage.\n- Added a compact Notation section.\n- Added forward references from main-text claims to the specific lemmas in the appendix.\n\nWe will do another full proofread to keep the narrative tight and the notation consistent.\n\n---\n\n## 2. Practical significance and novelty\n\nWe appreciate the clear separation you drew between MeZO and PEFT. As we said in the previous section that separation is exactly why the bilevel design is useful in practice:\n\n- **Efficient Meta Learning** We have added a section on meta-learning as a direct application of our method. For this reason, we are unsure about the reviewer’s comment regarding a lack of realistic or practical scenarios.\n- **Other realistic applications (we added a short paragraph in Discussion):**\n    - Multi-Task RL. We are actively exploring this.\n    - Federated or privacy-sensitive scenarios where clients can run small FO-PEFT steps locally and aggregate ZO signals centrally.\n\nWe also contribute:\n- A penalized bilevel formulation that yields a practical algorithm (Algorithm 1) with ZO outer updates and FO inner PEFT steps.\n- Convergence under standard assumptions.\n- Empirical benefits beyond either component alone: faster convergence and reduced prompt sensitivity vs. MeZO; higher accuracy than FO-PEFT at similar memory.\n- Ablating every design choice and showing its optimality.\n- Compatibility with multiple PEFT methods: replacing LoRA with DePT improves the baseline and our bilevel method continues to add gains (table below).\n\n---\n\n## 3. Experiments, including code and math\n\nWe understand the field’s current focus on code and math. Still, practitioners fine-tune LLMs on many other tasks every day (classification, extraction, domain QA, retrieval-augmented workflows). Our main suite reflects those common uses, and as per the request we have added code/math to show that the method transfers.\n\n**New code/math experiments (Qwen2-7B).** Train on GSM8K (train split), HumanEval (train split), and Math500 (4:1 train/test). Evaluate on the standard test splits. LoRA and Bilevel-ZOFO trained for 2,000 steps; MeZO for 10,000 steps. Metrics: accuracy (GSM8K/Math500), pass@1 (HumanEval).\n\n| Method             | GSM8K | Math500 | HumanEval (pass@1) |\n|--------------------|-------|---------|--------------------|\n| Before tuning      | 0.420 | 0.18    | 0.476              |\n| LoRA               | 0.727 | 0.28    | 0.518              |\n| MeZO               | 0.329 | 0.05    | 0.110              |\n| Bilevel-ZOFO (ours)| 0.762 | 0.31    | 0.543              |\n\nAcross all three tasks, Bilevel-ZOFO improves over LoRA and strongly over MeZO. We believe these additions demonstrate that the method is practical beyond small classification suites.\n\n---\n\n## 4. Questions and Notes\n\nWe have fixed all the noted issues. Thank you for  the careful read.\n\n---\n\nWe believe the motivation is strong: the bilevel design preserves the deployment benefits of ZO while recovering the stability and few-shot adaptability of FO-PEFT, which leads directly to efficient meta-learning and other realistic applications. The new experiments and clarifications address the concerns about novelty, clarity, and scope.\n We appreciate the feedback and will ensure the updated paper reflects these improvements and suggestions."}, {"review_id": "NPbsqhZDuT", "reviewer": "Reviewer_sRKn", "summary": "This paper points out that Zeroth-Order methods suffer from slow convergence, due to the requirement for full-parameter gradient estimation and the necessity of careful prompt selections. Thus, to address these issues, this paper proposes Bilevel ZOFO, which optimizes the full backbone model in the upper level and optimizes the PEFT in the lower level. Experiments show that Bilevel ZOFO outperforms other FO PEFT methods with faster convergence.", "questions": "I think Algorithm 2 (BiLevel ZOFO) is actually a three-level optimization process, and the hyperparameter tuning could be very complex. This increases my concerns about the feasibility of scaling the algorithm to more complex tasks.", "limitations": "There is no experimental evidence showing that the proposed bilevel ZOFO can scale to complex reasoning tasks such as math, code, and instruction following.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**_Strengths_**:\n1. The paper finds that the FO methods suffer from slow convergence and careful prompt selections, and proposes Bilevel ZOFO to address these issues.\n2. The paper provides theoretical guarantees for the convergence of the proposed Bilevel ZOFO.\n3. The experiments show that the proposed Bilevel ZOFO outperforms other FO methods.\n\n**_Weaknesses_**:\n1. The motivation is weak: In the introduction, the authors use the SST-2 dataset as an example to argue that first-order (FO) methods require careful prompt engineering. However, to my understanding, SST-2 was originally designed for masked language models like BERT. When adapting it for decoder-only models such as GPT, which rely on next-token prediction, prompt engineering becomes necessary. In contrast, for tasks like GSM8K or HumanEval, such manual prompt design is typically not required. Therefore, the paper's motivation seems to be based primarily on datasets tailored for masked language models, rather than those naturally suited for decoder-only architectures. When evaluated on datasets such as GSM8K or HumanEval, the core motivation of this paper — the necessity for careful prompt engineering — no longer hold. \n2. I do not fully understand the authors' reasoning for shifting from the observation that hard prompts significantly affect the performance of first-order (FO) methods to proposing a hybrid approach that combines PEFT-based first-order optimization with full-parameter zeroth-order optimization. In effect, simple soft prompt tuning can achieve significantly better performance on GLUE and SuperGLUE benchmarks compared to BiLevel ZOFO, which makes the proposed BiLevel ZOFO a bit meaningless [1].\n3. The experiments in this paper are quite limited. Most of them are conducted on datasets with only 1,000 samples, and the datasets used are all from before 2020. For models with 1.3B or 7B parameters, these datasets (e.g., GLUE or SuperGLUE) are too simple. In my opinion, such datasets are insufficient to evaluate and compare the performance of different algorithms on models of this scale. I think the paper would be stronger if the method was tested on reasoning-heavy datasets like GSM8K, Math, MBPP, HumanEval, and MTBench. It would also help to study how sensitive these tasks are to changes in hyperparameters\n4.  The majority of experiments in this paper are conducted on datasets with only 1,000 samples. I cannot understand why the authors chose this experimental setup. \n\n[1] DePT: Decomposed Prompt Tuning for Parameter-Efficient Fine-tuning. In ICLR 2024.", "was_revised": true, "final_justification": "My concerns have been addressed.", "rebuttal": "We appreciate the reviewer’s detailed comments. However, we believe there has been a major misunderstanding about our paper’s core motivation and contributions, which we clarify below. We also address the concerns on experimental scope and complexity explicitly.\n\n---\n\n## 1. Clarification of Major Misunderstanding (Weaknesses 1 and 2)\nThe reviewer states in weaknesses #1 and #2 that we argue first-order (FO) PEFT methods are sensitive to prompt selection and hyperparameters. This is not what we say in our paper at all. We clearly state that our method addresses the weaknesses of MeZO (zeroth-order) methods, not FO-PEFT methods.\n\nSpecifically:\n- Our motivation and experiments (e.g., Introduction lines 44-52) show that MeZO, which is a zeroth-order (ZO) method, is highly sensitive to prompt structure and hyperparameters.\n- We explicitly state (Lines71-74) that we introduce an FO-PEFT inner loop to stabilize and accelerate MeZO’s ZO backbone updates, NOT because FO-PEFT itself is unstable or sensitive. The reviewer’s assertion about FO-PEFT sensitivity is a misunderstanding of our clearly-stated motivation.\n- The reviewer’s statement mentioning “simple soft prompt tuning” (DePT) outperforming our method further suggests confusion that we are addressing a problem of FO PEFT: our proposed bilevel framework is entirely compatible with soft prompt methods like DePT. In fact, we explicitly say (Lines 159-164) that Bilevel ZOFO can directly incorporate advanced PEFT methods (including DePT), and we demonstrate empirically that combining DePT with our approach achieves even better performance:\n\n| Method           | BoolQ | SST-2 |\n|------------------|-------|-------|\n| DePT             | 0.813 | 0.932 |\n| MeZO             | 0.792 | 0.865 |\n| Bilevel-ZOFO+DePT| 0.852 | 0.946 |\n\n\n---\n\n## 2. On the Relevance of the Chosen Tasks (Math and Code vs. Other Benchmarks)\n\nWe fully acknowledge that mathematical reasoning and code generation tasks are currently popular benchmarks. However LLM fine-tuning applications extend far beyond these two domains:\n- Practitioners routinely fine-tune models on QA, classification, retrieval-augmented QA, and user-history-driven recommendation tasks. Such practical tasks still require task-specific instructions, and sensitivity to prompt formats remains practically relevant.\n- As a concrete example, one author is currently fine-tuning pretrained GPT models for multi-task recommendation, demonstrating real-world, high-impact applications for tasks outside the “hot” math/code trend.\n\nNonetheless, to show clearly that our observations regarding MeZO’s sensitivity to prompts also hold for these popular reasoning tasks, we performed additional explicit experiments on GSM8K:\n\n| Method                                   | Accuracy |\n|-------------------------------------------|----------|\n| MeZO (with simple prompt: Question: {Q}\\nAnswer: {A})      | 0.329    |\n| MeZO (without this prompt, raw format)    | 0.122    |\n| Bilevel-ZOFO (with prompt)                | 0.762    |\n| Bilevel-ZOFO (without prompt, raw format) | 0.744    |\n\n\nThese experiments decisively confirm our claims: MeZO is highly sensitive to prompt structure even for challenging datasets like GSM8K. Our method substantially alleviates this sensitivity and consistently achieves better results.\n\n\n## 3. Experimental Setup and Data Size\n\nWe understand the reviewer’s perspective on using larger reasoning datasets, but our chosen tasks and dataset sizes reflect intentional methodological choices:\n- Our setup deliberately follows standard PEFT evaluation practices, which commonly assume limited data points (few-shot adaptation scenarios). This aligns with our practical scenarios where labeled data is expensive and scarce.\n- Although the reviewer emphasizes math and code, it is once again critical to recognize that many real-world applications indeed rely on QA and classification benchmarks (GLUE, SuperGLUE), and such tasks remain very relevant in practical industry deployments. Our choice is not arbitrary.\n- Nonetheless, to further demonstrate generality and scale, we added challenging math/code experiments.\n\n**New code/math experiments (Qwen2-7B).** Train on GSM8K (train split), HumanEval (train split), and Math500 (4:1 train/test). Evaluate on the standard test splits. LoRA and Bilevel-ZOFO trained for 2,000 steps; MeZO for 10,000 steps. Metrics: accuracy (GSM8K/Math500), pass@1 (HumanEval).\n\n| Method             | GSM8K | Math500 | HumanEval (pass@1) |\n|--------------------|-------|---------|--------------------|\n| Before tuning      | 0.420 | 0.18    | 0.476              |\n| LoRA               | 0.727 | 0.28    | 0.518              |\n| MeZO               | 0.329 | 0.05    | 0.110              |\n| Bilevel-ZOFO (ours)| 0.762 | 0.31    | 0.543              |\n\nThese results clearly show our method’s effectiveness beyond simple datasets and support our original claim.\n\n##  4. Regarding Algorithm 2 (“Three-Level” Optimization Misunderstanding)\nIn bilevel optimization, there’s an outer optimization that updates one set of variables using the solution of an inner problem. In this algorithm, the outer level updates the backbone weights $\\theta$ with a zeroth-order step. Before each outer update, the method freezes $\\theta$ and runs a few first-order adaptation steps on the inner variables (the PEFT parameters $p$ and the auxiliary state $s$) to produce an inner solution $(p^{k+1}, s^{k+1})$. The zeroth-order update of $\\theta$ is then computed using that inner solution, so the outer move explicitly depends on the result of the inner adaptation. This is exactly the bilevel pattern.\n\nIt is not three-level: $p$ and $s$ are both inner-level variables updated while $\\theta$ is fixed; they serve the same purpose (fast, low-memory adaptation/penalty tracking) and are obtained with a short inner procedure. Multiple inner steps (over t) don’t create a new “level”, they’re just the algorithmic solver for the inner problem. Hyperparameters like the numbers of inner steps or ZO queries control how well the inner problem is solved, not an additional optimization level.\n\n\n## 5. Regarding Scalability and Complexity (Question from Reviewer)\n\nRegarding the reviewer’s scalability concern due to hyperparameter tuning:\n\n- In practice, tuning the hyperparameters we introduce is simple, and we provide ablation studies to show our method is not overly sensitive to this parameter (see paper section 4.2.1).\n- Crucially, we empirically demonstrate scalability to more challenging tasks (GSM8K, HumanEval, Math500). These datasets confirm the method is both stable and performant without complex hyperparameter tuning.\n\n--- \n**We thank the reviewer for reading our work and providing feedback. However, we believe the reviewer’s criticism primarily arose from a fundamental misunderstanding of our motivation (FO-PEFT vs. MeZO sensitivity). We sincerely ask the reviewer to reconsider their evaluation in light of our clarifications and the provided additional experiments, which confirm our original motivation and contributions.**"}, {"review_id": "WY0ndAu1MW", "reviewer": "Reviewer_BdLv", "summary": "This paper proposes to improve parameter-efficient fine-tuning (PEFT) algorithms by incorporating a zero-th order optimization technique (MeZO) to update the full model parameters with little memory overhead, maintaining the **memory efficiency** of PEFT algorithms and improving the downstream task accuracy at the expense of **slightly longer training time**. The proposed bi-level minimax algorithm outperforms the performance of first-order PEFT and parameter-efficient MeZO by achieving the pareto-front optimal tradeoff over the baselines in terms of training duration and peak memory consumption, as illustrated in Figure 1.", "questions": "**Wall Clock Time Analysis in Table 4**\n- It is not clear to me why ZO methods consumes more time per step than FO methods. Intuitively, FO methods require computing the forward and backward pass and therefore should be more time-consuming than ZO methods which only requires 2 forward passes. I hope the authors can provide explanation to this phenomenon, and include it in the main text to give readers a better understanding on the practical complexity of the baseline algorithms.", "limitations": "See **Strengths And Weaknesses**.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Writing**\n- In line 70, \"converge guarantees\" should be \"convergence guarantees\".\n- In Eq. (6), the second term on the right hand side has $\\theta$ as its first argument, which should be $\\theta^k$.\n- Missing full stop in line 157.\n- I suggest the authors to give a concluding summary in Section 5, re-emphasizing the comparison with the FO/ZO PEFT baselines in terms of **memory efficiency** and **runtime/iteration complexity**. This will expand on the sentence \"We propose a new method that is more **efficient** ...\" in line 329 and let the readers know what kind of **efficiency** is achieved by Bilevel-ZOFO.\n\n-------\n\n**Convergence Analysis in Appendix B**\n\n**Pros**\n- The proposed convergence analysis removed the dimension dependence of zeroth order method using a bounded hessian assumption (Assumption B.5).\n\n**Cons**\n- The convergence theorem depends on the assumption that the lower level objective is strongly convex. I suggest the authors to emphasize this limitation in line 154, because such limitation is not mentioned nor discussed in the main text.\n\n------ \n**Significance**\n- The proposed algorithm achieves state-of-the-art training time and memory consumption tradeoff. This is important for practical training especially in large language model fine-tuning.\n\n\n**Originality**\n- While the techniques of the proposed algorithm are not novel, the combination of first-order PEFT and zeroth-order full parameter tuning is novel to the best of my knowledge.", "was_revised": true, "final_justification": "My concerns are well-addressed and I keep my rating as 5 Accept.", "rebuttal": "We appreciate the thoughtful review and positive feedback on our method’s efficiency and novelty. Below, we address the specific comments and questions raised by the reviewer.\n\n---\n\n## 1. Writing and clarity\nWe thank the reviewer for the careful reading and suggested improvements. We have made the following edits:\n- Line 70: Corrected the typo.\n- Eq. (6): Fixed the argument typo.\n- Line 157: Added the missing full stop.\n- Section 5 (Conclusion): Following the reviewer’s suggestion, we added a concluding paragraph clearly summarizing our method’s advantage over FO/ZO PEFT methods in terms of runtime efficiency, iteration complexity, and memory efficiency. Thank you.\n\nThese revisions will enhance clarity and explicitly summarize the main contributions in terms of practical efficiency.\n\n---\n\n## 2. Convergence analysis (Assumptions):\n\nThe reviewer correctly notes our convergence theorem depends on the assumption of strong convexity of the lower-level objective. This is a standard assumption in related work. We agree this assumption should be clearly emphasized in the main text. We now explicitly mention and discuss this limitation in line 154, clarifying that while strong convexity simplifies theoretical analysis, in practice, our experiments demonstrate robustness even when strict convexity might not fully hold\n\n--- \n\n## 3. Wall-clock time analysis (Question about Table 4):\nWhile FO methods involve a forward and backward pass, modern GPU hardware and optimized frameworks efficiently perform gradient computations, often rendering FO steps surprisingly fast. ZO methods require multiple forward passes (typically at least two) per gradient estimation and additional overhead from explicit finite-difference computations, increasing wall-clock time substantially. Unlike the FO method’s single backward call, multiple forward evaluations in ZO don’t benefit from optimized gradient routines. So average over multiple steps, MeZO seems slower in our analysis. We added a concise version of this explanation to the main text, clearly explaining the practical complexity differences. Thank you.\n\n---\nWe thank the reviewer again for the valuable suggestions and encouraging feedback."}]

Author rebuttal:

Meta-review: This paper introduces Bilevel-ZOFO, a fine-tuning framework that integrates zeroth-order (ZO) optimization on the full backbone with first-order (FO) parameter-efficient fine-tuning (PEFT) in a bilevel structure. The FO inner loop stabilizes and accelerates the ZO outer loop, mitigating prompt sensitivity and slow convergence issues observed in pure ZO approaches. The authors provide convergence analysis, ablation studies, and experiments across classification, meta-learning, and reasoning benchmarks (including math and code). Results show that Bilevel-ZOFO improves over LoRA, MeZO, and related baselines, with competitive memory efficiency.

Overall, the majority of reviewers find the paper technically solid and novel enough for NeurIPS. The bilevel formulation is well-motivated, convergence guarantees are provided, and empirical evidences, especially with new results on GSM8K, Math500, and HumanEval, demonstrates the usefulness of the approach beyond small classification tasks.
Decision: Accept (poster)