betaFeedback

WorksComputer Science

ENGINE: Endogenous Variational MultiScale Optimization for Zeroth-Order LLM Fine-Tuning

Abstract

Zeroth-order (ZO) optimization enables memory-efficient large language model (LLM) fine-tuning, and recent methods incorporate curvature-aware strategies. However, in the high-dimensional parameter space of LLMs, these methods inherently suffer from exploding gradient variance and prohibitive costs. Conversely, confining updates to a low-dimensional subspace reduces variance but discards critical high-dimensional information, degrading performance. This creates a fundamental dilemma: full-space optimization is informative but has high variance, while subspace optimization has low variance but loses information. To break this trade-off, we propose ENGINE (Endogenous Variational MultiScale). Inspired by computational mechanics, we adapt static Variational MultiScale (VMS) theory to dynamic optimization, treating low- and high-dimensional spaces as resolved coarse and unresolved fine scales. Through a multigrid-style V-cycle, ENGINE alternates between spaces, dynamically probing fine-grained information in the high-dimensional space and injecting it to correct the efficient low-dimensional sampling process. Under appropriate assumptions, statistical analysis characterizes variance reduction and correction of curvature-induced bias, and convergence analysis establishes a stationarity bound for the corrected coarse updates. Evaluations on standard LLM benchmarks show that ENGINE achieves higher accuracy and faster convergence than existing ZO methods, achieving up to a 2.61×2.61\times speed-up in forward passes with zero additional peak memory overhead. Code is available at https://github.com/AI4Science-WestlakeU/ENGINE.

Introduction

Large language model fine-tuning relies on first-order (FO) optimizers [12]. However, FO training requires storing activations, gradients, and optimizer states, making it memory-intensive. Zeroth-order (ZO) optimization [13] is therefore an appealing alternative: it uses only forward passes and reduces memory to near inference level. Still, in the full LLM parameter space, ZO methods suffer from high variance and high query cost [15].

LoRA [6] offers a lower-dimensional alternative by restricting updates to a low-rank subspace, improving efficiency and usually reducing variance. But this also discards fine-grained curvature information from the full space, which can slow convergence and degrade performance.

This leads to a central dilemma in zeroth-order optimization (Table 1): full-space optimization is informative but high-variance, while subspace optimization is low-variance but blind. Recent curvature-aware ZO methods, such as LOREN [17], reduce estimator variance through anisotropic perturbations [10]. Even so, existing methods usually stay in one space only: either the full parameter space or a low-rank subspace such as LoRA. They therefore gain only one side of the trade-off. Full-space methods retain richer information but are statistically costly, while subspace methods are more efficient but inevitably lose part of the curvature structure that is present in the full space. This motivates a simple question: can we keep the efficiency of low-dimensional sampling while still using curvature information from the full space? We approach this question through Variational MultiScale (VMS) theory [7, 8] from computational mechanics. VMS separates a problem into a resolved coarse scale and an unresolved fine scale, then uses a correction term [9] to account for the effect of the unresolved part. This viewpoint suggests a natural way to think about low-dimensional and high-dimensional spaces in zeroth-order optimization.

SpaceEffic.Var.Perf.Curv.
Full space××✓✓
Subspace✓✓××
ENGINE (Ours)✓✓✓✓

Table 1. Trade-offs between full-space and subspace ZO optimization. ✓ denotes a relative strength, and × a weakness.

Based on this idea, we propose ENGINE (Endogenous Variational MultiScale). We treat the low-dimensional LoRA parameterization as the resolved coarse scale and incorporate unresolved full-space curvature through a fine-scale correction. Unlike classical VMS, the optimization operator evolves with the optimization state, so the interaction between the two spaces must be updated dynamically. ENGINE addresses this with an endogenous V-cycle that alternates between the two spaces during training. Through a closed-form subgrid correction, it uses fine-scale information from the high-dimensional space to correct the efficient low-dimensional update.

Experiments on standard LLM optimization benchmarks show that ENGINE consistently improves over state-of-the-art zeroth-order baselines, including LOREN. It achieves better downstream accuracy, faster convergence, and up to a 2.61× speed-up in forward passes (Figure 1), while keeping peak memory usage unchanged.

Figure 1. Left: Forward-pass and wall-clock speed-up of ENGINE over LOREN to reach LOREN’s best accuracy, across four representative (model, task) settings. Right: Validation accuracy convergence on LLaMA-3-8B (CB).

Our contributions are summarised as follows.

  • A cross-disciplinary perspective. We introduce the idea of Variational MultiScale (VMS) from computational mechanics into zeroth-order LLM fine-tuning. This perspective clarifies why unresolved fine-scale curvature matters and provides a systematic way to describe the interaction between low-dimensional and high-dimensional optimization spaces.

  • The framework of ENGINE. We propose ENGINE, an endogenous Variational MultiScale framework for zeroth-order optimization that combines low-rank sampling with a closed-form subgrid correction, thereby reintroducing unresolved full-space curvature into the coarse update. Under appropriate assumptions, we rigorously analyze the bias and variance of the corrected estimator. We also establish a stationarity bound for coarse updates.

  • Consistent improvements. Extensive experiments across diverse LLM fine-tuning settings demonstrate that ENGINE improves both downstream performance and convergence speed over state-of-the-art zeroth-order baselines (Figure 2). These gains come with up to a 2.61× speed-up in forward passes and no additional peak memory overhead.

Figure 2. Test accuracy on all 16 (model, task) combinations. Top row: GPT-2-XL (GLUE, FP32) and OPT-2.7B (GLUE, FP32). Bottom row: LLaMA-3-8B (SuperGLUE, BF16) and OPT-13B (SuperGLUE, BF16). ENGINE is shown in blue hatched. Full numerical values are in Appendix E.1.

Preliminaries & Problem Setup

To address the single-scale limitation of ZO methods discussed in § 1, ENGINE couples a low-dimensional LoRA scale with the high-dimensional full parameter space via Variational MultiScale (VMS). § 2.1 first introduces the curvature-aware ZO framework adopted from LOREN, after which § 2.2 recalls the Variational MultiScale (VMS) viewpoint underlying our method.

Zeroth-Order Setting & Notation Setup

Notation. We denote vectors by lowercase bold and matrices by uppercase bold, where ⊗\otimes is the Kronecker product and ∥⋅∥\lVert\cdot\rVert the Euclidean norm. For a weight matrix X∈Rm×n\mathbf{X} \in\mathbb{R}^{m \times n}, let x:=vec⁡(X)∈Rd\mathbf{x} := \operatorname{vec}(\mathbf{X}) \in\mathbb{R}^{d} with d=mnd = mn (multi-layer models are handled block-wise). We minimize f(x):=Eξ∼Pdata[ℓ(x,ξ)]f(\mathbf{x}) := \mathbb{E}_{\xi\sim P_{\mathrm{data}}}[\ell(\mathbf{x}, \xi)] using only function-value queries, where PdataP_{\mathrm{data}} is the data distribution.

Rank-1 Kronecker curvature. Full Hessian storage costs O(m2n2)O(m^{2}n^{2}) memory. K-FAC [14] and Shampoo [5] exploit matrix structure to reduce preconditioning costs. Following LOREN, we use the compact vector parameterization:

H~=Im⊗(ρIn+vvT),v∈Rn, ρ>0,(1)\widetilde{\mathbf{H}} = \mathbf{I}_{m} \otimes\left(\rho\mathbf{I}_{n} + \mathbf{v}\mathbf{v}^{\mathsf{T}}\right), \qquad\mathbf{v} \in\mathbb{R}^{n},\ \rho> 0, \tag*{(1)}

where vvT\mathbf{v}\mathbf{v}^{\mathsf{T}} captures anisotropy shared across blocks, and damping ensures positive definiteness. Storing v\mathbf{v} costs O(n)O(n). The inverse and inverse square root admit closed forms with O(mn)O(mn) application cost, avoiding dense matrices. § 3 extends this approximation to multiple scales.

Curvature as covariance. For u∼N(0,Id)\mathbf{u} \sim\mathcal{N}(\mathbf{0}, \mathbf{I}_{d}) and smoothing radius ϵ>0\epsilon> 0, the symmetric finite-difference estimator [18] is g^ϵ(x,u)=f(x+ϵu)−f(x−ϵu)2ϵu\widehat{\mathbf{g}}_{\epsilon}(\mathbf{x}, \mathbf{u}) = \frac{f(\mathbf{x}+\epsilon\mathbf{u})-f(\mathbf{x}-\epsilon\mathbf{u})}{2\epsilon}\mathbf{u}. Its expectation is the gradient of the Gaussian-smoothed loss. Generalized Gaussian smoothing extends this to anisotropic perturbations u∼N(0,Σ)\mathbf{u} \sim\mathcal{N}(\mathbf{0}, \mathbf{\Sigma}), and setting Σ=H~−1\mathbf{\Sigma} = \widetilde{\mathbf{H}}^{-1} yields the NES identity [21]

H~−1∇f(x)=Eu~∼N(0,H~−1)[⟨∇f(x),u~⟩u~],\widetilde{H}^{-1}\nabla f(x)=\mathbb{E}_{\widetilde{u}\sim\mathcal{N}(0,\widetilde{H}^{-1})}\left[\langle\nabla f(x),\widetilde{u}\rangle\widetilde{u}\right],

so preconditioning by H~−1\widetilde{H}^{-1} corresponds to larger ZO perturbations along directions of lower estimated curvature.

Variational MultiScale Method

The Variational MultiScale (VMS) method decomposes problems into resolved (coarse) and unresolved (fine) scales. Let Ω⊂Rd\Omega\subset\mathbb{R}^d be a bounded domain, VV a function space over Ω\Omega with dual V∗V^*, and L:V→V∗\mathcal{L}:V\to V^* a linear operator, where the symmetric bilinear form a(w,u):=(w,Lu)a(w,u):=(w,\mathcal{L}u) uses the L2(Ω)L^2(\Omega) inner product (w,u):=∫Ωw(x)u(x) dx(w,u):=\int_{\Omega}w(x)u(x)\,dx. The weak problem seeks u∈Vu\in V such that a(w,u)=(w,f)a(w,u)=(w,f) for all test functions w∈Vw\in V. VMS decomposes V=V‾⊕V′V=\overline{V}\oplus V' into coarse V‾\overline{V} and fine V′V' subspaces, so that u=u‾+u′u=\overline{u}+u' and w=w‾+w′w=\overline{w}+w' with u‾,w‾∈V‾\overline{u},\overline{w}\in\overline{V} and u′,w′∈V′u',w'\in V'. The fine scale is driven by the coarse residual Lu′=−(Lu‾−f)\mathcal{L}u'=-(\mathcal{L}\overline{u}-f). Following the sign convention of Hughes [1995], the fine-scale solution operator M:V∗→V′M:V^*\to V' includes the negative sign, so u′=M(Lu‾−f)u'=M(\mathcal{L}\overline{u}-f). Substitution yields the closed coarse equation:

a(w‾,u‾)+(L∗w‾,M(Lu‾−f))=(w‾,f),(2)a(\overline{w},\overline{u})+(\mathcal{L}^*\overline{w},M(\mathcal{L}\overline{u}-f))=(\overline{w},f), \tag*{(2)}

where L∗:V→V∗\mathcal{L}^*:V\to V^* is the adjoint of L\mathcal{L}, and the second term in (2) is the subgrid correction encoding unresolved-scale feedback. In our setting, u‾\overline{u}, u′u', and L\mathcal{L} correspond to the LoRA-space update, unresolved full-space curvature, and endogenous Hessian operator H~\widetilde{H}, respectively. The subgrid correction corresponds to the VMS-EO fine-scale curvature injection developed in § 3.

Method

Building on the rank-1 curvature primitive (H~,v)(\widetilde{H},v) from Eq. (1) and the VMS formulation coupling coarse and fine scales from Eq. (2), this section develops and analyzes ENGINE (Figure 3). §3.1 contrasts the rigid linear operator L\mathcal{L} of classical VMS with the dynamic Hessian H(θ)H(\theta) of optimization, motivating why classical VMS cannot be ported verbatim. §3.2 derives the central correction τsgs\tau_{\mathrm{sgs}} and its rank-1 LoRA-branch surrogate. §3.3 embeds VMS-EO into a V-cycle so that the endogenous state vfv_f is refreshed across phases. §3.4 then quantifies how coarse sampling and exact subgrid correction affect variance and bias relative to a common target.

Figure 3. ENGINE overview. Left: the gap between the restricted fine direction R(ΣfVf)\mathcal{R}(\Sigma_f V_f) and the coarse direction ΣcR(Vf)\Sigma_c\mathcal{R}(V_f) defines the subgrid correction τsgs\tau_{\mathrm{sgs}}. Middle: V-cycle alternates Coarse (ϕ\phi) and Fine (WW) phases, with every SS steps a fine probe refreshing vf←vf−νg(vf)v_f \leftarrow v_f-\nu g(v_f) and λ\lambda (Hessian refresh), while VMS-EO (τsgs\tau_{\mathrm{sgs}}) injects the subgrid correction into each coarse step. Right: classical VMS uses a fixed operator L\mathcal{L}, while ENGINE uses the dynamic Hessian H(θ)H(\theta).

The multiscale state is carried by three rank-1 curvature vectors: the full-space vf∈Rnv_f\in\mathbb{R}^n and the two LoRA-branch curvatures vB∈Rrv_B\in\mathbb{R}^r, vA∈Rnv_A\in\mathbb{R}^n. We instantiate the resolved coarse scale by a rank-rr LoRA factorization ΔW=BA\Delta W=BA with B∈Rm×rB\in\mathbb{R}^{m\times r}, A∈Rr×nA\in\mathbb{R}^{r\times n}, and r≪min⁡(m,n)r\ll\min(m,n), so the coarse parameter ϕ=(B,A)\phi=(B,A) has dimension dc=r(m+n)d_c=r(m+n), much smaller than df=mnd_f=mn. Fine-scale information is obtained from the full parameter space and used to correct curvature effects not captured by the coarse model.

Endogenous Operator: Why Classical VMS Fails?

Classical VMS starts from a linear problem Lu=f\mathcal{L}u=f with operator L\mathcal{L} fixed by the underlying physics, which is what allows the unresolved component u′u' to be eliminated analytically in closed form (Figure 3 Right, top). In optimization the analogous linear equation is the Newton step H(θ)Δθ=−∇f(θ)\mathbf{H}(\theta)\Delta\theta=-\nabla f(\theta), giving the correspondence (L,u,f)↔(H,Δθ,−∇f)(\mathcal{L},u,f)\leftrightarrow(\mathbf{H},\Delta\theta,-\nabla f). Unlike L\mathcal{L}, however, H(θ)\mathbf{H}(\theta) co-evolves with the iterate (Figure 3 Right, bottom), so the closure cannot be derived once and for all but must be refreshed periodically by the V-cycle of § 3.3. We call this state-dependent operator an endogenous operator and the resulting subgrid correction VMS-EO.

Coarse increments are represented by changes in the LoRA factors. The prolongation operator P:(ΔB,ΔA)↦BΔA+ΔBA∈Rm×n\mathcal{P}:(\Delta\mathbf{B},\Delta\mathbf{A})\mapsto\mathbf{B}\Delta\mathbf{A}+\Delta\mathbf{B}\mathbf{A}\in\mathbb{R}^{m\times n} lifts a coarse update to the full space (the differential of the LoRA product), and the restriction operator R=(RB,RA)\mathcal{R}=(\mathcal{R}_{\mathbf{B}},\mathcal{R}_{\mathbf{A}}) with RB(X)=XAT∈Rm×r\mathcal{R}_{\mathbf{B}}(\mathbf{X})=\mathbf{X}\mathbf{A}^{\mathsf{T}}\in\mathbb{R}^{m\times r} and RA(X)=BTX∈Rr×n\mathcal{R}_{\mathbf{A}}(\mathbf{X})=\mathbf{B}^{\mathsf{T}}\mathbf{X}\in\mathbb{R}^{r\times n} maps a full-space matrix X\mathbf{X} to the two LoRA gradient blocks. The two operators are formal adjoints under the Frobenius inner product, R=P∗\mathcal{R}=\mathcal{P}^{*}, i.e., ⟨P(ΔB,ΔA),X⟩F=⟨(ΔB,ΔA),R(X)⟩F\langle\mathcal{P}(\Delta\mathbf{B},\Delta\mathbf{A}),\mathbf{X}\rangle_{F}=\langle(\Delta\mathbf{B},\Delta\mathbf{A}),\mathcal{R}(\mathbf{X})\rangle_{F} for all X∈Rm×n\mathbf{X}\in\mathbb{R}^{m\times n}.

At LLM scale, H∈Rdf×df\mathbf{H}\in\mathbb{R}^{d_f\times d_f} cannot be formed, so ENGINE inherits LOREN’s rank-1 Kronecker H~=Im⊗(ρIn+vvT)\widetilde{\mathbf{H}}=\mathbf{I}_{m}\otimes(\rho\mathbf{I}_{n}+\mathbf{v}\mathbf{v}^{\mathsf{T}}) as the practical operator with preconditioner Σ=H~−1\boldsymbol{\Sigma}=\widetilde{\mathbf{H}}^{-1}. Given parameter x\mathbf{x} and curvature v\mathbf{v}, LOREN draws KK anisotropic perturbations zk=x+εΣ1/2uk\mathbf{z}_{k}=\mathbf{x}+\varepsilon\boldsymbol{\Sigma}^{1/2}\mathbf{u}_{k} where uk∼N(0,I)\mathbf{u}_{k}\sim\mathcal{N}(\mathbf{0},\mathbf{I}) to simultaneously form RLOO estimators for both parameter and curvature gradients:

References

  1. [1]Yiming Chen, Yuan Zhang, Liyuan Cao, Kun Yuan, and Zaiwen Wen. Enhancing zeroth-order fine-tuning for language models with low-rank structures. arXiv preprint arXiv:2410.07698, 2024.arxiv.org/abs/2410.07698
  2. [2]Nikita Doikov, Martin Jaggi, et al. Second-order optimization with lazy hessians. In International Conference on Machine Learning, pages 8138–8161. PMLR, 2023.arxiv.org/abs/2212.00781
  3. [3]Tanmay Gautam, Youngsuk Park, Hao Zhou, Parameswaran Raman, and Wooseok Ha. Variance-reduced zeroth-order methods for fine-tuning language models. arXiv preprint arXiv:2404.08080, 2024.arxiv.org/abs/2404.08080
  4. [4]Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, et al. The llama 3 herd of models. arXiv preprint arXiv:2407.21783, 2024.arxiv.org/abs/2407.21783
  5. [5]Vineet Gupta, Tomer Koren, and Yoram Singer. Shampoo: Preconditioned stochastic tensor optimization. In International Conference on Machine Learning, pages 1842–1850. PMLR, 2018.arxiv.org/abs/1802.09568
  6. [6]Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. Lora: Low-rank adaptation of large language models. arXiv preprint arXiv:2106.09685, 2021.arxiv.org/abs/2106.09685
  7. [7]Thomas JR Hughes. Multiscale phenomena: Green’s functions, the dirichlet-to-neumann formulation, subgrid scale models, bubbles and the origins of stabilized methods. Computer methods in applied mechanics and engineering, 127(1-4):387–401, 1995.DOI
  8. [8]Thomas JR Hughes, Gonzalo R Feijóo, Luca Mazzei, and Jean-Baptiste Quincy. The variational multiscale method—a paradigm for computational mechanics. Computer methods in applied mechanics and engineering, 166(1-2):3–24, 1998.DOI
  9. [9]Thomas JR Hughes, Luca Mazzei, and Kenneth E Jansen. Large eddy simulation and the variational multiscale method. Computing and visualization in science, 3(1):47–59, 2000.DOI
  10. [10]Wouter Kool, Herke van Hoof, and Max Welling. Buy 4 reinforce samples, get a baseline for free! 2019.
  11. [11]Vladislav Lialin, Sherin Muckatira, Namrata Shivagunde, and Anna Rumshisky. ReloRA: High-rank training through low-rank updates. In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id=DLJZnSp6X3.arxiv.org/abs/2307.05695
  12. [12]Ilya Loshchilov, Frank Hutter, et al. Fixing weight decay regularization in adam. arXiv preprint arXiv:1711.05101, 5(5):5, 2017.
  13. [13]Sadhika Malladi, Tianyu Gao, Eshaan Nichani, Alex Damian, Jason D Lee, Danqi Chen, and Sanjeev Arora. Fine-tuning language models with just forward passes. Advances in Neural Information Processing Systems, 36:53038–53075, 2023.arxiv.org/abs/2305.17333
  14. [14]James Martens and Roger Grosse. Optimizing neural networks with kronecker-factored approximate curvature. In International conference on machine learning, pages 2408–2417. PMLR, 2015.arxiv.org/abs/1503.05671
  15. [15]Yuri Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2):527–566, 2017.
  16. [16]Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAI blog, 1(8):9, 2019.
  17. [17]Hyunseok Seung, Jaewoo Lee, and Hyunsuk Ko. Low-rank curvature for zeroth-order optimization in llm fine-tuning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 40, pages 25235–25242, 2026.
  18. [18]James C Spall. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation. IEEE transactions on automatic control, 37(3):332–341, 1992.DOI
  19. [19]Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. Glue: A multi-task benchmark and analysis platform for natural language understanding. In Proceedings of the 2018 EMNLP workshop BlackboxNLP: Analyzing and interpreting neural networks for NLP, pages 353–355, 2018.
  20. [20]Alex Wang, Yada Pruksachatkun, Nikita Nangia, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. Superglue: A stickier benchmark for general-purpose language understanding systems. Advances in neural information processing systems, 32, 2019.
  21. [21]Daan Wierstra, Tom Schaul, Tobias Glasmachers, Yi Sun, Jan Peters, and Jürgen Schmidhuber. Natural evolution strategies. The Journal of Machine Learning Research, 15(1):949–980, 2014.
  22. [22]Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona 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, 2022. URL https://arxiv.org/abs/2205.01068.
  23. [23]Yanjun Zhao, Sizhe Dang, Haishan Ye, Guang Dai, Yi Qian, and Ivor Tsang. Second-order fine-tuning without pain for llms: A hessian informed zeroth-order optimizer. In International Conference on Learning Representations, volume 2025, pages 43496–43520, 2025.arxiv.org/abs/2402.15173

Paper details

vlnc:W_pcx58pyh
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 11

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents