Fine-Tuning Language Models with Just Forward Passes

ArXiv: 2305.17333

🎯 Pitch

You can fine-tune a 30-billion-parameter language model on a single GPU using only forward passes, matching backpropagation’s accuracy while using 12× less memory. The MeZO optimizer estimates gradients from two forward passes with random perturbations, turning catastrophic memory costs into something that fits in the same footprint as inference.

---

1. Executive Summary

This paper introduces MeZO (memory-efficient zeroth-order optimizer), a method that adapts the classical ZO-SGD algorithm to fine-tune large language models using only forward passes, requiring the same memory footprint as inference. Tested on masked (RoBERTa-large) and autoregressive (OPT, up to 66B) models across classification, multiple-choice, and generation tasks, MeZO estimates gradients via the SPSA estimator—perturbing parameters with random noise and using two forward-pass loss differences to construct a gradient estimate (e.g., ℓ⁺ − ℓ⁻ divided by 2ε, projected onto the perturbation vector z)—while an in-place implementation that resamples z from a stored random seed avoids storing the full perturbation vector. The method achieves up to 12× memory reduction over standard Adam fine-tuning (enabling 30B-parameter model training on a single 80GB A100 GPU vs. only 2.7B with backpropagation), produces accuracy within 1% of full fine-tuning on 7 of 11 OPT-13B tasks, and requires roughly half the GPU-hours of Adam for a 30B model, establishing that zeroth-order optimization can effectively fine-tune billion-parameter LMs when adequate pre-training and task prompts ensure the loss landscape has low local effective rank rather than depending on raw parameter count.

2. Context and Motivation

The Core Problem: Backpropagation Memory Costs Are Prohibitive for Large Language Model Fine-Tuning

The fundamental tension this paper addresses is a practical one that confronts almost every practitioner working with large pretrained language models: fine-tuning requires dramatically more memory than inference, and as models scale, this gap becomes the dominant bottleneck. The paper opens with a concrete, actionable measurement that crystallizes the problem: while you can comfortably run inference with a 30-billion parameter OPT model on a single Nvidia A100 GPU with 80GB of memory, attempting to fine-tune that same model with backpropagation and the Adam optimizer is only feasible for a model roughly 11× smaller—a 2.7B parameter LM. This is not a minor inconvenience; it is a hard wall that determines which models researchers and practitioners can adapt to their specific tasks.

Why does backpropagation consume so much more memory? The paper breaks this down into three components (Section 1, Section 3.4):

• Activation caching during the forward pass. To compute gradients during the backward pass, the framework must retain the intermediate outputs of each layer. For deep transformer models processing long sequences, these activations can easily dominate the memory budget.
• Gradient storage during the backward pass. The gradient with respect to every parameter must be computed and stored, which requires memory proportional to the model size itself—another full copy of the parameters.
• Optimizer state for adaptive methods like Adam. Adam maintains two additional moving-average buffers (first and second moment estimates) per parameter, essentially tripling the per-parameter memory requirement beyond the raw gradient.

Even parameter-efficient fine-tuning (PEFT) methods like LoRA (Hu et al., 2022) and prefix-tuning (Li and Liang, 2021), which update only a small fraction of the model's parameters, do not escape this bottleneck. The paper reports that fine-tuning OPT-13B with full parameter tuning requires approximately 12× the inference memory, while PEFT methods still require roughly 6× the inference memory (Section 1). Why? Because the tuned parameters, though few, are scattered throughout the model layers, meaning that activations must still be cached for all layers to propagate gradients back to those sparse update sites. PEFT reduces checkpoint storage costs but does not meaningfully reduce training-time memory consumption.

Why This Problem Matters: Democratizing Access to Large Language Model Adaptation

The practical implications of this memory bottleneck extend across multiple dimensions that the paper addresses directly:

On-device and resource-constrained deployment. Not every practitioner has access to a cluster of A100 GPUs. A researcher at a small university or a startup engineer may have access to a single high-memory GPU, or even just a consumer-grade card. If fine-tuning a 6.7B model requires 2–4 GPUs with 80GB each (as shown in Figure 4 and Table 22), then a substantial portion of the community is locked out of adapting state-of-the-art models. MeZO's ability to fine-tune a 30B model on a single A100 fundamentally changes who can participate in building specialized language applications.

The rise of non-differentiable objectives in language model training. The paper highlights a second, equally important motivation: backpropagation fundamentally requires that the training objective be differentiable. Yet the most impactful recent advances in language model alignment—specifically, reinforcement learning from human feedback (RLHF; Christiano et al., 2017; Ouyang et al., 2022)—center on optimizing non-differentiable criteria such as human preference scores, safety ratings, or task-specific metrics like F1 and accuracy. Currently, adapting models to these criteria requires a complex pipeline: training a reward model on human preferences, then using reinforcement learning (typically PPO) that still requires backpropagation through the policy network. If a method could optimize non-differentiable objectives directly—say, by treating the model as a black box that returns a score for any set of parameters—this pipeline could be dramatically simplified. The paper explicitly positions MeZO as enabling this capability (Section 3.3), opening up applications in direct preference optimization and safety alignment that were previously cumbersome or prohibitively expensive.

Storage costs of fine-tuned model checkpoints. Beyond training-time memory, the paper identifies an often-overlooked cost: storing fine-tuned models for multiple downstream tasks. In production systems that serve dozens or hundreds of specialized tasks, storing a full copy of a 66B-parameter model per task (approximately 132GB in half-precision, per checkpoint) is infeasible. Parameter-efficient fine-tuning methods partially address this by reducing the number of tuned parameters—a LoRA adapter for a 66B model may require only 38MB—but MeZO pushes this logic even further. Because MeZO's trajectory can be entirely reconstructed from a single random seed plus a sequence of scalar projected gradients (Section 2.1), the entire fine-tuning provenance for a 66B model can be stored in less than 0.1MB, a roughly 380× reduction compared even to LoRA and a ~1200× reduction compared to storing a full model checkpoint. This has profound implications for model versioning, reproducibility, and multi-task serving infrastructure.

The pretraining-inference compute tradeoff. At a higher level, this paper engages with a question that the field is increasingly confronting: as pretraining costs balloon into the hundreds of millions of dollars, should we invest more compute in training larger models, or in running smarter inference with smaller ones? In-context learning (Brown et al., 2020) was an early answer—don't fine-tune at all, just provide examples in the prompt—but it comes with its own limitations. MeZO offers a third path: fine-tune with dramatically reduced memory cost, enabling adaptation of models that would otherwise be too large to touch. This is not just about saving money; it's about changing the calculus of where value is extracted in the model lifecycle.

Where Existing Approaches Fall Short

The paper builds its case by systematically identifying the limitations of prior methods along several axes:

In-Context Learning: Powerful but Brittle and Slow

In-context learning (ICL)—providing a handful of labeled examples in the prompt and letting the model infer the task pattern—has been celebrated as a breakthrough capability of large language models. The paper acknowledges its strengths (no training required, works across arbitrary tasks, requires only a single forward pass) but identifies key weaknesses that motivate the search for better alternatives (Section 1):

• Performance ceiling. ICL often underperforms fine-tuning of even medium-sized models, especially on tasks requiring substantial domain-specific adaptation. The paper's own experiments bear this out: on OPT-13B across 11 tasks, MeZO outperforms ICL on the majority of benchmarks (Table 1), sometimes by substantial margins (e.g., 84.7 vs. 75.9 on SQuAD).
• Context length constraints. The number of demonstrations is limited by the model's maximum context window, which, despite rapid advances, remains a hard constraint. Many tasks benefit from more than a handful of examples, and ICL simply cannot leverage larger training sets.
• Sensitivity to demonstration selection and formatting. Extensive prior work (Liu et al., 2022; Lu et al., 2022) has shown that ICL performance varies substantially based on which examples are chosen, how they are ordered, and how the prompt is formatted. This makes ICL unpredictable and difficult to productionize reliably.
• Inference cost scales linearly with demonstrations. Each additional demonstration adds tokens to the prompt, increasing both latency and per-query cost. At 32 demonstrations (the paper's ICL setting), the prompt alone can consume significant computation, especially for long-context tasks.

Linear Probing: Memory-Efficient but Capacity-Limited

Linear probing—training a linear classifier on top of frozen pretrained representations—requires no backpropagation through the base model and thus shares inference-level memory. But it fundamentally cannot adapt the model's internal representations to the downstream task, limiting its capacity to handle complex reasoning or tasks where the pretraining distribution differs substantially from the target domain. The paper's results (Table 1) show linear probing trailing MeZO by large margins on most tasks, and failing entirely on generation tasks and multiple-choice tasks where the output space is the full vocabulary rather than a small set of classification labels.

Parameter-Efficient Fine-Tuning: Still Needs Backpropagation

LoRA (Hu et al., 2022) and prefix-tuning (Li and Liang, 2021) reduce the number of trainable parameters and the checkpoint storage cost, which the paper acknowledges as valuable. But as noted earlier, they do little to reduce training-time memory because the tuned parameters are distributed across layers, requiring full activation caching. The paper's measurements (Figure 4) show that prefix-tuning OPT-13B still requires 6× the memory of inference—better than full fine-tuning's 12×, but far from the 1× that MeZO achieves. From a memory perspective, PEFT is a half-measure; from a performance perspective, it often matches or slightly trails full fine-tuning, so it does not expand the frontier of what can be trained on a given hardware budget.

Classical Zeroth-Order Optimization: Theoretically Doomed for Large Models

The paper situates its work in a long history of zeroth-order (ZO) optimization, which estimates gradients from function value differences rather than through automatic differentiation. The SPSA estimator (Spall, 1992) that MeZO uses has been known for decades: perturb the parameters with random noise $\mathbf{z}$, evaluate the loss at $\boldsymbol{\theta} + \epsilon \mathbf{z}$ and $\boldsymbol{\theta} - \epsilon \mathbf{z}$, and construct the gradient estimate as:

$\hat{\nabla} \mathcal{L}(\boldsymbol{\theta}; \mathcal{B}) = \frac{\mathcal{L}(\boldsymbol{\theta} + \epsilon \mathbf{z}; \mathcal{B}) - \mathcal{L}(\boldsymbol{\theta} - \epsilon \mathbf{z}; \mathcal{B})}{2\epsilon} \mathbf{z}$

This estimator is an unbiased estimate of the true gradient in the limit $\epsilon \to 0$, because $\mathbb{E}[\mathbf{z} \mathbf{z}^\top \nabla \mathcal{L}] = \nabla \mathcal{L}$ for Gaussian $\mathbf{z}$. So why has ZO optimization not been widely used for deep learning?

The classical lower bounds are damning. The paper reviews a series of results (Nemirovskij and Yudin, 1983; Duchi et al., 2015; Jamieson et al., 2012; Raginsky and Rakhlin, 2011) showing that for general convex and strongly convex optimization problems, the convergence rate of ZO methods scales linearly with the number of parameters $d$. For a model with billions of parameters, this predicts that ZO optimization would be catastrophically slow—requiring billions of times more steps than gradient-based methods to reach the same accuracy. This theoretical prediction has been so intimidating that ZO methods in deep learning have largely been confined to low-dimensional settings: generating adversarial examples (Chen et al., 2017; Liu et al., 2019a), tuning input embeddings (Sun et al., 2022b), or optimizing in low-dimensional subspaces (Sun et al., 2022a, b; BBT, BBTv2). No prior work had attempted to directly optimize all parameters of a billion-scale model using ZO methods.

The variance problem is real. Lemma 2 in the paper quantifies why: the expected squared norm of the SPSA gradient estimate scales as:

$\mathbb{E}[\|\hat{\nabla} \mathcal{L}(\boldsymbol{\theta}; \mathcal{B})\|^2] = \frac{d + n - 1}{n} \cdot \mathbb{E}[\|\nabla \mathcal{L}(\boldsymbol{\theta}; \mathcal{B})\|^2]$

where $n$ is the number of perturbation vectors averaged (typically $n = 1$ in MeZO) and $d$ is the parameter count. With $n = 1$ and $d$ in the billions, the gradient estimate has roughly $d$ times the variance of the true stochastic gradient. The descent lemma (Lemma 1) shows that this forces the learning rate to be reduced by a factor of approximately $d$ to guarantee loss decrease, which in turn slows convergence by the same factor. On paper, ZO-SGD for a 13B-parameter model should be 13 billion times slower than SGD—clearly unusable.

The Crucial Missing Piece: Why Pre-Training Changes Everything

The paper's central theoretical insight is that the classical lower bounds do not apply to fine-tuning pretrained models. The classical results assume a worst-case loss landscape with no structure—essentially, that the Hessian can have full rank $d$ and the gradient can point in an arbitrary direction. But fine-tuning a pretrained LM is fundamentally different: the model has already been trained for many steps on a closely related objective (the pretraining task), and the inclusion of a simple prompt ensures that the fine-tuning objective is "close" to the pretraining objective in the parameter space.

The paper builds on prior work (Saunshi et al., 2021; Malladi et al., 2022) that demonstrated how prompts make the fine-tuning objective behave like the pretraining objective, and extends this by connecting it to a well-documented empirical phenomenon: the Hessian of deep neural network losses exhibits remarkably low effective rank (Papyan, 2018, 2020; Ghorbani et al., 2019; Yao et al., 2020). The bulk of the Hessian spectrum is concentrated near zero, with only a small number of outlier eigenvalues that dominate the optimization dynamics. The number of these outliers—the effective rank $r$—can be as small as a few hundred, even for models with billions of parameters. Prior work (Aghajanyan et al., 2021; Li et al., 2018) further showed that LM fine-tuning can occur in an intrinsically low-dimensional subspace, sometimes with fewer than 200 effective parameters.

If the Hessian has effective rank $r \ll d$, then the variance of the SPSA gradient estimate does not scale with $d$. Instead, the paper's Theorem 1 shows that under a local $r$-effective rank assumption, the slowdown factor scales as $\gamma = \Theta(r / n)$, where $r$ is the effective rank and $n$ is the number of perturbation vectors averaged. For $r$ in the hundreds and $n = 1$, the slowdown is only a factor of a few hundred—large enough to be noticeable, but not the 13-billion-fold slowdown that the classical bounds would predict. This is the key theoretical innovation that transforms ZO optimization from "impossible in principle" to "merely somewhat slower in practice."

How This Paper Positions Itself

The paper positions MeZO not as a replacement for backpropagation in all contexts—backpropagation will remain faster when memory is abundant—but as a capability expansion: it enables fine-tuning of models that would otherwise be untunable on a given hardware budget. It also enables optimization of objectives that backpropagation literally cannot handle (non-differentiable metrics). The paper frames its contributions along four parallel tracks:

1. Algorithmic: An in-place implementation of classical ZO-SGD that reduces memory to inference-level by resampling the perturbation vector $\mathbf{z}$ from a stored random seed rather than materializing it in memory (Algorithm 1, Section 2.1).

2. Empirical: Comprehensive experiments across model types (masked and autoregressive), scales (350M to 66B parameters), and task types (classification, multiple-choice, generation) showing that MeZO significantly outperforms memory-equivalent baselines (zero-shot, ICL, linear probing) and approaches or matches backpropagation-based fine-tuning on the majority of tasks (Section 3, Tables 1–2, Table 18).

3. Theoretical: An analysis showing that pre-training and prompting cause the loss landscape to exhibit low local effective rank, which makes the convergence rate of ZO-SGD depend on this effective rank $r$ rather than the parameter count $d$, explaining why MeZO works despite classical impossibility results (Section 4, Theorem 1, Lemma 3).

4. Practical: Demonstrations of MeZO's compatibility with full-parameter tuning and PEFT (LoRA, prefix-tuning), its ability to optimize non-differentiable objectives (accuracy, F1), and its wall-clock time advantages in certain regimes (Section 3.3, Section 3.4, Section F.6).

The paper explicitly does not claim that MeZO is faster than backpropagation in all scenarios—it takes substantially more steps to converge (e.g., 100K steps vs. 1K for RoBERTa-large, 20K vs. 625 steps for OPT). Rather, the claim is that the per-step speedup (7.74× for a 30B model, due to avoiding backpropagation and reducing inter-GPU communication) combined with the memory reduction can lead to a net win in total GPU-hours (approximately half for a 30B model) while enabling training of models that would otherwise require substantially more hardware. This is a careful, measured positioning that acknowledges the tradeoffs rather than overselling the method.

A crucial, easily overlooked detail: the paper's experiments reveal that MeZO only works when using prompts (Appendix A.1, Table 5). Without a prompt, MeZO on SST-2 drops from 89.6% to 51.9% accuracy, and on TREC from 66.7% to 19.5%. Prompts are not merely a convenience—they are essential for making the fine-tuning landscape compatible with zeroth-order optimization. This finding connects directly to the theoretical framework: prompts ensure that the fine-tuning objective is "close" to pretraining in a way that preserves the low effective rank structure of the Hessian. Without prompts, the landscape reverts to the worst-case behavior that classical lower bounds describe. This is a non-obvious empirical finding that the theory retroactively explains and justifies.

3. Technical Approach

3.1 Reader orientation

This paper presents MeZO, a memory-efficient implementation of classical zeroth-order stochastic gradient descent that fine-tunes large language models using only forward passes, consuming exactly the same GPU memory as inference. The system solves the problem that backpropagation requires 12× more memory than inference for large models (due to activation caching, gradient storage, and optimizer state), by instead estimating gradients through repeated forward passes with perturbed parameters and reconstructing the perturbation vector on-the-fly from a stored random seed rather than materializing it in memory.

3.2 Big-picture architecture (diagram in words)

The MeZO system has four major components that operate in a tight loop per training step:

1. The base language model (e.g., RoBERTa-large, OPT-13B through 66B) — the pretrained model whose parameters $\boldsymbol{\theta} \in \mathbb{R}^d$ are to be fine-tuned. It serves as a black-box function that maps parameters and input tokens to a scalar loss value $\mathcal{L}(\boldsymbol{\theta}; \mathcal{B})$ on a minibatch $\mathcal{B}$.

2. The perturbation mechanism (PerturbParameters subroutine in Algorithm 1) — adds scaled Gaussian noise $\epsilon \mathbf{z}$ to every parameter in-place, where $\mathbf{z} \sim \mathcal{N}(0, \mathbf{I}_d)$ and $\epsilon$ is the perturbation scale. Crucially, $\mathbf{z}$ is never stored; a random seed $s$ is used to deterministically regenerate each coordinate of $\mathbf{z}$ exactly when needed.

3. The SPSA gradient estimator (Definition 1) — computes a scalar projected_grad as $(\ell_+ - \ell_-) / (2\epsilon)$ from two forward-pass loss evaluations: one at $\boldsymbol{\theta} + \epsilon \mathbf{z}$ and one at $\boldsymbol{\theta} - \epsilon \mathbf{z}$. This scalar, multiplied elementwise with $\mathbf{z}$, forms the approximate gradient.

4. The parameter update step — applies SGD (or a memory-efficient variant of Adam or momentum) by stepping each parameter $\theta_i$ by $-\eta \cdot \text{projected\_grad} \cdot z_i$, where $\eta$ is the learning rate and $z_i$ is regenerated from the stored seed.

Information flows as follows at each training step: (a) sample a minibatch $\mathcal{B}$ and random seed $s$; (b) use $s$ to generate $\mathbf{z}$ coordinate-by-coordinate and perturb parameters to $\boldsymbol{\theta} + \epsilon \mathbf{z}$; (c) evaluate loss $\ell_+$; (d) regenerate the same $\mathbf{z}$ from $s$ and perturb parameters to $\boldsymbol{\theta} - \epsilon \mathbf{z}$ (which requires adding $-2\epsilon \mathbf{z}$ to the current $\boldsymbol{\theta} + \epsilon \mathbf{z}$); (e) evaluate loss $\ell_-$; (f) reset parameters to their original values by adding $\epsilon \mathbf{z}$; (g) compute projected_grad; (h) regenerate $\mathbf{z}$ from $s$ a third time and apply the per-coordinate SGD update. The only persistent storage beyond model parameters is the scalar seed $s$ and the scalar projected_grad.

3.3 Roadmap for the deep dive

The technical deep dive proceeds in the following order, which mirrors how the algorithm is built from classical foundations to practical implementation:

• First, the SPSA gradient estimator (Definition 1) — the mathematical core of how forward-pass loss differences approximate gradients — because every subsequent component depends on understanding what quantity is being estimated and why its variance matters.
• Second, the classical ZO-SGD algorithm (Definition 2) and its variance properties (Lemma 2) — because the variance analysis explains the classical lower bounds that predict catastrophic slowness and sets up the theoretical innovation that resolves this paradox.
• Third, the MeZO in-place implementation (Algorithm 1) — the key algorithmic contribution that reduces memory from 2× inference to 1× inference by resampling $\mathbf{z}$ from a seed — because this is what makes the method practical for large models.
• Fourth, the MeZO extensions to momentum and Adam — because these require recomputing gradient history from stored past seeds and scalars, which is a non-obvious memory-saving technique.
• Fifth, the perturbation granularity tradeoff — perturbing individual scalars versus entire weight matrices — because this affects both runtime and the memory-accuracy boundary.
• Sixth, the theoretical analysis connecting pre-training, prompts, and Hessian effective rank to ZO convergence (Assumption 1, Theorem 1, Lemma 3) — because this explains why MeZO works at all on billion-parameter models despite the classical lower bounds.

3.4 Detailed, sentence-based technical breakdown

This is an algorithm-and-theory paper whose core idea is that classical ZO optimization can be made memory-efficient enough to fine-tune billion-parameter models, and that pre-training ensures the optimization landscape has low effective rank, making convergence depend on this rank rather than the raw parameter count.

---

The SPSA Gradient Estimator

The fundamental building block of MeZO is the Simultaneous Perturbation Stochastic Approximation (SPSA) gradient estimator, introduced by Spall (1992). SPSA estimates the gradient of a loss function $\mathcal{L}$ with respect to model parameters $\boldsymbol{\theta} \in \mathbb{R}^d$ using only two evaluations of the loss function, rather than the $d$ evaluations that a naive finite-difference approach would require (one per parameter).

Definition 1 (SPSA). Given parameters $\boldsymbol{\theta} \in \mathbb{R}^d$, a loss function $\mathcal{L}$, and a minibatch $\mathcal{B}$, the SPSA gradient estimate is:

$\hat{\nabla} \mathcal{L}(\boldsymbol{\theta}; \mathcal{B}) = \frac{\mathcal{L}(\boldsymbol{\theta} + \epsilon \mathbf{z}; \mathcal{B}) - \mathcal{L}(\boldsymbol{\theta} - \epsilon \mathbf{z}; \mathcal{B})}{2\epsilon} \cdot \mathbf{z}$

where $\mathbf{z} \in \mathbb{R}^d$ is a random perturbation vector with $\mathbf{z} \sim \mathcal{N}(0, \mathbf{I}_d)$ and $\epsilon$ is the perturbation scale (a small positive scalar controlling the magnitude of parameter perturbation).

What it computes: The numerator computes a finite-difference approximation of the directional derivative of $\mathcal{L}$ along the random direction $\mathbf{z}$ — it measures how much the loss changes when we step from $\boldsymbol{\theta} - \epsilon \mathbf{z}$ to $\boldsymbol{\theta} + \epsilon \mathbf{z}$ (a step of size $2\epsilon$ along $\mathbf{z}$). Dividing by $2\epsilon$ gives an approximation of the scalar projection $\mathbf{z}^\top \nabla \mathcal{L}(\boldsymbol{\theta}; \mathcal{B})$, which is the directional derivative along $\mathbf{z}$. Multiplying this scalar by the vector $\mathbf{z}$ produces a rank-1 matrix applied to the true gradient: $\mathbf{z} \mathbf{z}^\top \nabla \mathcal{L}(\boldsymbol{\theta}; \mathcal{B})$. The output is a vector in $\mathbb{R}^d$ that serves as a noisy estimate of the true gradient.

Why this form: The SPSA estimator is specifically designed to be an unbiased estimator of the true gradient in the limit $\epsilon \to 0$. This unbiasedness holds because for any fixed vector $\mathbf{v}$, the expectation of $\mathbf{z} \mathbf{z}^\top \mathbf{v}$ over Gaussian $\mathbf{z}$ equals $\mathbf{v}$ (since $\mathbb{E}[z_i z_j] = \delta_{ij}$ for independent standard normals, giving $\mathbb{E}[\mathbf{z} \mathbf{z}^\top] = \mathbf{I}_d$). The two-point symmetric difference (using both $+\epsilon \mathbf{z}$ and $-\epsilon \mathbf{z}$) is crucial: a one-point estimator using only $\mathcal{L}(\boldsymbol{\theta} + \epsilon \mathbf{z})$ would be biased by the $\mathcal{O}(\epsilon)$ term in the Taylor expansion, whereas the symmetric difference cancels the $\mathcal{O}(\epsilon)$ term and has bias only $\mathcal{O}(\epsilon^2)$. The paper empirically validates in Appendix B.5 (Table 11) that one-point estimators are substantially less efficient than SPSA when fixing the number of forward passes — for example, on SNLI, the one-point estimator achieves only 70.1% accuracy vs. 82.9% for SPSA at equivalent forward-pass budgets.

The $n$-SPSA variant (Definition 1 extension). The paper also defines $n$-SPSA, which averages the SPSA estimate over $n$ independently sampled perturbation vectors $\mathbf{z}_1, \ldots, \mathbf{z}_n$:

$\hat{\nabla} \mathcal{L}(\boldsymbol{\theta}; \mathcal{B}) = \frac{1}{n} \sum_{i=1}^n \frac{\mathcal{L}(\boldsymbol{\theta} + \epsilon \mathbf{z}_i; \mathcal{B}) - \mathcal{L}(\boldsymbol{\theta} - \epsilon \mathbf{z}_i; \mathcal{B})}{2\epsilon} \cdot \mathbf{z}_i$

where each $\mathbf{z}_i \sim \mathcal{N}(0, \mathbf{I}_d)$ independently. This requires $2n$ forward passes per step but reduces gradient variance by a factor of approximately $n$. However, the paper's ablation experiments (Appendix A.2, Table 6) show that increasing $n$ while fixing the total forward-pass budget (by reducing the number of steps proportionally) yields marginal at best improvement — for example, on SST-2, $n=1$ gives 89.6% while $n=16$ gives 90.4%, a gain of only 0.8 percentage points at 16× the per-step forward-pass cost. The paper therefore uses $n=1$ as the default throughout.

The perturbation scale $\epsilon$. The hyperparameter $\epsilon$ controls the magnitude of parameter perturbation. In the limit $\epsilon \to 0$, the SPSA estimate becomes exactly $\mathbf{z} \mathbf{z}^\top \nabla \mathcal{L}(\boldsymbol{\theta}; \mathcal{B})$ (the rank-1 reconstruction of the gradient). However, using a non-zero $\epsilon$ may provide a beneficial implicit regularization effect by including higher-order terms from the Taylor expansion that promote flat minima (a form of sharpness-aware minimization). The paper uses $\epsilon = 10^{-3}$ for full-parameter MeZO, $\epsilon = 10^{-1}$ for MeZO with prefix-tuning, and $\epsilon = 10^{-2}$ for MeZO with LoRA on OPT models (Table 16). The choice of $\epsilon$ was found to not significantly impact performance in the ablation study (Appendix A, Table 4 grid included $\epsilon \in \{10^{-3}, 10^{-5}\}$ with similar results).

---

Classical ZO-SGD and Its Variance Properties

The SPSA estimate can be plugged into any gradient-based optimizer. The simplest such optimizer is ZO-SGD (Definition 2):

$\boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_t - \eta \cdot \hat{\nabla} \mathcal{L}(\boldsymbol{\theta}_t; \mathcal{B}_t)$

where $\eta$ is the learning rate and $\mathcal{B}_t$ is the minibatch at step $t$. This directly replaces the backpropagation-computed gradient with the SPSA estimate.

The variance problem (Lemma 2). The paper derives the expected squared norm of the SPSA gradient estimate for the $n$-SPSA case:

$\mathbb{E}[\|\hat{\nabla} \mathcal{L}(\boldsymbol{\theta}; \mathcal{B})\|^2] = \frac{d + n - 1}{n} \cdot \mathbb{E}[\|\nabla \mathcal{L}(\boldsymbol{\theta}; \mathcal{B})\|^2]$

where $d$ is the number of model parameters and $n$ is the number of $\mathbf{z}$ vectors averaged.

What this equation says: The expected squared norm of the ZO gradient estimate is larger than that of the true stochastic gradient by a factor of $(d + n - 1)/n$. For $n = 1$ (the default MeZO setting) and a model with $d = 13 \times 10^9$ parameters (OPT-13B), this means the gradient estimate has roughly 13 billion times the squared norm of the true gradient. This is not a small variance inflation — it means the gradient estimate is dominated by noise, and the signal (the true gradient direction) is buried under an enormous amount of random fluctuation.

Why this matters for optimization (the descent lemma, Lemma 1). The classical descent lemma bounds the expected decrease in loss at each optimization step for an $\ell$-smooth function:

$\mathbb{E}[\mathcal{L}(\boldsymbol{\theta}_{t+1}) \mid \boldsymbol{\theta}_t] - \mathcal{L}(\boldsymbol{\theta}_t) \leq -\eta \|\nabla \mathcal{L}(\boldsymbol{\theta}_t)\|^2 + \frac{1}{2} \eta^2 \ell \cdot \mathbb{E}[\|\hat{\nabla} \mathcal{L}(\boldsymbol{\theta}_t; \mathcal{B}_t)\|^2]$

What this inequality says: The expected loss decrease depends on two competing terms. The first term $-\eta \|\nabla \mathcal{L}\|^2$ is the beneficial descent from following the true gradient direction — larger learning rate means more progress. The second term $\frac{1}{2} \eta^2 \ell \cdot \mathbb{E}[\|\hat{\nabla}\|^2]$ is the harmful effect of gradient variance — stochasticity in the gradient estimate injects noise that can increase the loss, and this term grows quadratically with the learning rate. For the loss to decrease (making the right-hand side negative), the learning rate must satisfy:

$\eta \leq \frac{2\|\nabla \mathcal{L}(\boldsymbol{\theta}_t)\|^2}{\ell \cdot \mathbb{E}[\|\hat{\nabla}\|^2]}$

Plugging in the variance inflation from Lemma 2 gives the maximum permissible learning rate for ZO-SGD:

$\eta_{\text{ZO}} = \frac{n}{d + n - 1} \cdot \eta_{\text{SGD}}$

where $\eta_{\text{SGD}}$ is the maximum permissible learning rate for standard SGD.

The classical impossibility argument: For $n=1$ and large $d$, this says $\eta_{\text{ZO}} \approx \eta_{\text{SGD}} / d$. The learning rate must be reduced by a factor of $d$ (billions) compared to SGD, which means ZO-SGD would need billions of times more steps to achieve the same loss reduction. This is the theoretical basis for the widely-held belief that ZO methods are "catastrophically slow for optimizing large models" (as the paper states in its abstract). And indeed, for a randomly initialized model, this analysis would be accurate — the Hessian would have full effective rank, and ZO-SGD would be hopeless.

The paper's key theoretical observation: This classical analysis assumes the worst case — that $\mathbb{E}[\|\hat{\nabla}\|^2]$ truly scales with $d$. But this scaling arises from the trace of the gradient covariance, which depends on the structure of the Hessian. If the Hessian has low effective rank $r \ll d$ (meaning most eigenvalues are near zero), then the variance inflation factor can be much smaller than $d$. The paper formalizes this in Assumption 1 and Theorem 1, which we'll examine after understanding the algorithm itself.

---

The MeZO In-Place Implementation (Algorithm 1)

The naive implementation of ZO-SGD requires storing the perturbation vector $\mathbf{z} \in \mathbb{R}^d$ in GPU memory, because it is used in three separate operations: (1) perturbing parameters to $\boldsymbol{\theta} + \epsilon \mathbf{z}$, (2) perturbing parameters to $\boldsymbol{\theta} - \epsilon \mathbf{z}$, and (3) computing the per-coordinate update $-\eta \cdot \text{projected\_grad} \cdot z_i$. For a 66B-parameter model in half-precision (FP16), $\mathbf{z}$ would require $66 \times 10^9 \times 2 \text{ bytes} \approx 132 \text{ GB}$ — more than the memory capacity of two A100 GPUs combined, and comparable to the model itself. This would double the memory footprint relative to inference, negating the memory advantage that ZO methods promise.

The core algorithmic innovation: deterministic resampling from a seed. MeZO eliminates this storage entirely through an in-place implementation that treats the random number generator (RNG) as a deterministic function: given the same seed $s$, it will produce the exact same sequence of pseudo-random numbers. The algorithm stores only the scalar integer seed $s$ (8 bytes) rather than the entire vector $\mathbf{z}$. At each of the four points where $\mathbf{z}$ is needed, the RNG is reset with seed $s$ and the relevant coordinate of $\mathbf{z}$ is regenerated on-the-fly.

Step-by-step walkthrough of Algorithm 1 (one training step):

1. Sample a minibatch and seed. The step begins by sampling a minibatch $\mathcal{B} \subset \mathcal{D}$ of size $B$ and a random integer seed $s$. The seed is the only persistent random state stored for this step — just one scalar.

2. First perturbation (positive direction): Call PerturbParameters(\boldsymbol{\theta}, \epsilon, s). This subroutine resets the RNG with seed $s$, then iterates over every parameter $\theta_i$ in the model, sampling $z \sim \mathcal{N}(0, 1)$ and updating $\theta_i \leftarrow \theta_i + \epsilon \cdot z$ in-place. After this, the parameters are $\boldsymbol{\theta} + \epsilon \mathbf{z}$.

3. First loss evaluation: Compute $\ell_+ \leftarrow \mathcal{L}(\boldsymbol{\theta}; \mathcal{B})$ on the positively perturbed parameters. This is a standard forward pass.

4. Second perturbation (negative direction): Call PerturbParameters(\boldsymbol{\theta}, -2\epsilon, s). The same seed $s$ is reused, so the RNG produces the identical sequence of $z$ values. Each parameter is updated as $\theta_i \leftarrow \theta_i - 2\epsilon \cdot z$. Since the parameters were at $\theta_i + \epsilon z$ after step 2, subtracting $2\epsilon z$ yields $\theta_i - \epsilon z$. After this, the parameters are $\boldsymbol{\theta} - \epsilon \mathbf{z}$.

5. Second loss evaluation: Compute $\ell_- \leftarrow \mathcal{L}(\boldsymbol{\theta}; \mathcal{B})$ on the negatively perturbed parameters.

6. Reset parameters to original: Call PerturbParameters(\boldsymbol{\theta}, \epsilon, s). Adding $\epsilon z$ to each $\theta_i - \epsilon z$ restores the original $\theta_i$. After this, parameters are back to $\boldsymbol{\theta}$.

7. Compute projected gradient: projected_grad $\leftarrow (\ell_+ - \ell_-) / (2\epsilon)$. This scalar, a single floating-point number, encodes the directional derivative estimate.

8. Apply the SGD update: Reset the RNG with seed $s$ a fourth time. For each parameter $\theta_i$, sample $z \sim \mathcal{N}(0, 1)$ and update $\theta_i \leftarrow \theta_i - \eta_t \cdot \text{projected\_grad} \cdot z$. The learning rate $\eta_t$ at step $t$ multiplies the scalar projected_grad and the coordinate $z$ to produce the per-parameter step.

Why this works: The key insight is that a pseudo-random number generator is a deterministic state machine — seed → state → output. By storing only the seed (the initial state), the entire sequence of random numbers can be perfectly reconstructed. Since the same seed produces the same $\mathbf{z}$ at each call to PerturbParameters, the three perturbations (positive, negative, reset) are guaranteed to use identical $\mathbf{z}$ vectors. The fourth regeneration during the update step also uses the same $\mathbf{z}$, ensuring that the gradient estimate $\hat{\nabla}$ is properly formed as projected_grad $\cdot \mathbf{z}$.

Memory cost analysis. The only additional memory required beyond the model parameters and the standard inference activations (for computing $\mathcal{L}$ on a minibatch) is:

• One integer for the seed $s$ (8 bytes)
• One float for projected_grad (4 bytes)
• One float for the temporary $z$ value during coordinate iteration (4 bytes, reused per coordinate)
• Two floats for $\ell_+$ and $\ell_-$ (8 bytes)

This totals approximately 24 bytes of additional memory, independent of model size. The memory footprint is therefore identical to inference, because the forward pass activations for a single minibatch dominate by many orders of magnitude. For example, on OPT-13B processing 400-token sequences, the activation memory during a forward pass is roughly 26GB (as shown in Table 22), while the MeZO overhead is 24 bytes — a factor of roughly $10^9$ smaller.

Perturbation granularity (the caveat in Section 2.1). The paper notes that Algorithm 1 describes perturbing "each parameter separately," iterating over every scalar weight in the model. For a 66B-parameter model, this would require 66 billion calls to the RNG and 66 billion in-place additions per perturbation phase, which would be prohibitively slow. In practice, the implementation perturbs entire weight matrices rather than individual scalars — generating a matrix $\mathbf{Z}$ of the same shape as each weight matrix $\mathbf{W}$ from the RNG and performing $\mathbf{W} \leftarrow \mathbf{W} + \epsilon \mathbf{Z}$. This requires storing the perturbation matrix $\mathbf{Z}$ temporarily, incurring additional memory equal to the size of the largest weight matrix in the model, which is typically the word embedding matrix (for OPT-66B, the authors note this is 0.86GB). This is still a small fraction of total inference memory, but it means the memory footprint is technically slightly above pure inference — inference_memory + max_matrix_size, not strictly inference_memory.

---

Memory-Efficient Extensions: MeZO-Adam and MeZO-Momentum

The SPSA gradient estimate can be used in place of the true gradient in any gradient-based optimizer, including those that maintain historical gradient statistics like SGD with momentum or Adam (Kingma and Ba, 2015). However, these optimizers typically require storing additional buffers per parameter — momentum requires one buffer (the exponential moving average of gradients), and Adam requires two (first and second moment estimates). For a 66B-parameter model, Adam's optimizer state alone would require $2 \times 66 \times 10^9 \times 4$ bytes ≈ 528 GB in FP32, completely defeating the memory efficiency of MeZO.

The recomputation trick (Section 2.2, Appendix B.2). The paper observes that the entire gradient history can be recomputed from stored past scalars rather than stored explicitly. Recall that the SPSA gradient estimate at step $t$ is $\hat{\nabla}_t = \text{projected\_grad}_t \cdot \mathbf{z}_t$, where $\mathbf{z}_t$ is determined by the step's seed $s_t$. If we store only the scalars $\{s_1, \ldots, s_t\}$ and $\{\text{projected\_grad}_1, \ldots, \text{projected\_grad}_t\}$, then the full gradient vector at any past step can be reconstructed by regenerating $\mathbf{z}_\tau$ from seed $s_\tau$ and multiplying by projected_grad_\tau$. The momentum or Adam moving averages can then be recomputed on-the-fly by iterating over the history.

Storage cost for optimizer state. To recompute the optimizer state, we need to store:

• One integer seed per step: $T \times 4$ bytes (for a 32-bit integer)
• One float projected_grad per step: $T \times 4$ bytes (for FP32)

For $T = 20,000$ steps (the OPT experiment budget), this requires $20,000 \times 8$ bytes = 160 KB total — negligible compared to the model size. For comparison, storing Adam's full optimizer state for a 66B model would require over 500 GB. The recomputation itself adds computational overhead (re-running RNG and accumulating moving averages over all past steps) but requires no additional forward passes through the model.

Experimental results (Appendix F.1, Table 18). The paper reports that MeZO-Adam sometimes outperforms MeZO (ZO-SGD), though not consistently across tasks. On RoBERTa-large with $k=512$, MeZO-Adam achieves 85.3% on SNLI vs. 83.0% for MeZO, and 79.2% on RTE vs. 78.6% for MeZO — modest but consistent improvements. On SST-2, both achieve 93.3%. The paper does not conduct exhaustive MeZO-Adam experiments on OPT models, leaving the question of when adaptive optimizers help in the ZO setting largely open.

---

The Theoretical Resolution: Low Effective Rank of the Fine-Tuning Hessian

The classical analysis (Lemma 2) predicts that MeZO would be catastrophically slow because the gradient variance scales with $d$, the parameter count. Yet the experiments clearly show that MeZO works — it fine-tunes 66B-parameter models to accuracies within a few percent of backpropagation-based fine-tuning. The paper's theory section resolves this apparent paradox by showing that under a realistic assumption about the fine-tuning loss landscape, the convergence rate does not depend on $d$.

Assumption 1 (Local $r$-effective rank). The paper formalizes the key structural property needed for efficient ZO optimization. Let $\boldsymbol{\theta}_t$ be the current parameter iterate, and let $G(\boldsymbol{\theta}_t) = \max_{(\mathbf{x}, \mathbf{y}) \in \mathcal{D}} \|\nabla \mathcal{L}(\boldsymbol{\theta}_t; \{(\mathbf{x}, \mathbf{y})\})\|$ be the maximum per-example gradient norm. The assumption states:

1. Hessian upper bound near the current iterate: There exists a matrix $\mathbf{H}(\boldsymbol{\theta}_t) \preceq \ell \cdot \mathbf{I}_d$ (meaning $\mathbf{H}$ is positive semidefinite with maximum eigenvalue at most $\ell$, the smoothness constant) such that for all $\boldsymbol{\theta}$ satisfying $\|\boldsymbol{\theta} - \boldsymbol{\theta}_t\| \leq \eta d G(\boldsymbol{\theta}_t)$, we have $\nabla^2 \mathcal{L}(\boldsymbol{\theta}) \preceq \mathbf{H}(\boldsymbol{\theta}_t)$. In plain language: within a ball of radius $\eta d G(\boldsymbol{\theta}_t)$ around the current parameters, the true Hessian is bounded above by a fixed matrix $\mathbf{H}(\boldsymbol{\theta}_t)$.

2. Low effective rank: The effective rank of $\mathbf{H}(\boldsymbol{\theta}_t)$, defined as $\text{tr}(\mathbf{H}(\boldsymbol{\theta}_t)) / \|\mathbf{H}(\boldsymbol{\theta}_t)\|_{op}$, is at most $r$. The numerator $\text{tr}(\mathbf{H})$ is the sum of eigenvalues; the denominator $\|\mathbf{H}\|_{op}$ is the largest eigenvalue. The effective rank measures how many eigenvalues are "meaningfully large" — if most eigenvalues are near zero, the effective rank is small even if the matrix is $d \times d$.

Why this assumption is realistic for fine-tuning. The paper marshals substantial empirical evidence from prior work:

• Hessian spectra of deep networks have low effective rank. Papyan (2018, 2020), Ghorbani et al. (2019), Yao et al. (2020), Wu et al. (2020), and Sagun et al. (2017) all demonstrate that the Hessian of the loss for trained deep neural networks has a bulk of eigenvalues concentrated near zero, with only a small number of outliers. The number of outliers — which upper-bounds the effective rank — can be as small as a few dozen to a few hundred, even for networks with millions of parameters.

• LM fine-tuning occurs in a low-dimensional subspace. Aghajanyan et al. (2021) and Li et al. (2018) showed that fine-tuning large LMs can be effectively performed in a subspace of fewer than 200 parameters without substantial performance degradation, suggesting the intrinsic dimensionality of the fine-tuning objective is tiny relative to the parameter count.

• Prompts are crucial for this structure. The paper's own ablation (Appendix A.1, Table 5) shows that without prompts, MeZO collapses to near-random performance — evidencing that prompts are what make the fine-tuning landscape "close" to pretraining and thus low-effective-rank.

Theorem 1 (Dimension-Free Per-Step Rate). Under Assumption 1, for a single step of ZO-SGD with learning rate $\eta_{\text{ZO}}$ using the $n$-SPSA estimate on a minibatch of size $B$, there exists a $\gamma = \Theta(r / n)$ such that:

$\mathbb{E}[\mathcal{L}(\boldsymbol{\theta}_{t+1}) \mid \boldsymbol{\theta}_t] - \mathcal{L}(\boldsymbol{\theta}_t) \leq -\eta_{\text{ZO}} \|\nabla \mathcal{L}(\boldsymbol{\theta}_t)\|^2 + \frac{1}{2} \eta_{\text{ZO}}^2 \ell \cdot \gamma \cdot \mathbb{E}[\|\nabla \mathcal{L}(\boldsymbol{\theta}; \mathcal{B})\|^2]$

What this inequality says: The form is identical to the classical descent lemma (Lemma 1), but with the variance term multiplied by $\gamma = \Theta(r/n)$ instead of $(d + n - 1)/n$. The per-step loss decrease now depends on the effective rank $r$, not the parameter count $d$. If $r$ is in the hundreds and $d$ is in the billions, the slowdown factor is reduced by a factor of roughly $d/r \approx 10^7$.

Corollary 1 (Learning rate comparison). Choosing $\eta_{\text{ZO}} = \gamma^{-1} \cdot \eta_{\text{SGD}}$ yields a loss decrease of:

$\mathbb{E}[\mathcal{L}(\boldsymbol{\theta}_{t+1}) \mid \boldsymbol{\theta}_t] - \mathcal{L}(\boldsymbol{\theta}_t) \leq \frac{1}{\gamma} \cdot \left[-\eta_{\text{SGD}} \|\nabla \mathcal{L}(\boldsymbol{\theta}_t)\|^2 + \frac{1}{2} \eta_{\text{SGD}}^2 \ell \cdot \mathbb{E}[\|\nabla \mathcal{L}(\boldsymbol{\theta}; \mathcal{B})\|^2]\right]$

What this says operationally: ZO-SGD is a factor of $\gamma$ slower than SGD in terms of per-step progress, where $\gamma \approx r/n$. For $n=1$ and $r \approx 100$–$500$, this means MeZO is roughly 100–500 times slower than SGD — a large factor, but not the billions-fold slowdown that the classical analysis would predict. The paper's experiments confirm this qualitatively: MeZO requires roughly 100× more steps than backpropagation-based fine-tuning (100K vs. 1K steps for RoBERTa-large, 20K vs. 625 steps for OPT-13B), but each step is substantially faster (7.74× per-step speedup for a 30B model), and the memory savings enable training models that would otherwise be impossible on the same hardware.

Lemma 3 (Global Convergence). Under stronger assumptions — specifically, that the loss satisfies the Polyak-Łojasiewicz (PL) inequality (Definition 4) and the trace of the gradient covariance is bounded by $\alpha$ times the suboptimality (Definition 5) — ZO-SGD converges to within $\epsilon$ of the optimum after:

$t = \mathcal{O}\left(\left(\frac{r}{n} + 1\right) \cdot \underbrace{\left(\frac{\ell}{\mu} + \frac{\ell \alpha}{\mu^2 B}\right) \log \frac{\mathcal{L}(\boldsymbol{\theta}_0) - \mathcal{L}^*}{\epsilon}}_{\text{SGD rate (Lemma 4)}}\right)$

iterations, where $\mu$ is the PL constant, $\ell$ is the smoothness constant, $\alpha$ bounds the gradient covariance, and $B$ is the batch size.

What this equation says: The total number of iterations for ZO-SGD is the SGD iteration count multiplied by a factor of $(r/n + 1)$. The $+1$ accounts for the base cost that would exist even with exact gradients. The $r/n$ term is the overhead from ZO gradient variance. The key claim is that this overhead does not scale with $d$ — it scales with the effective rank $r$, which the paper argues is small for pretrained models fine-tuned with prompts.

Why the PL inequality (Definition 4) matters: The PL inequality states that $\frac{1}{2}\|\nabla \mathcal{L}(\boldsymbol{\theta})\|^2 \geq \mu (\mathcal{L}(\boldsymbol{\theta}) - \mathcal{L}^*)$. This means that when the loss is far from optimal, the gradient is large — there are no flat plateaus where the gradient vanishes while the loss is still high. This is a weaker condition than strong convexity, but it ensures that gradient-based methods will make steady progress. Many overparameterized neural networks have been shown to satisfy PL-like conditions near their training trajectory.

Verification of the gradient covariance assumption (Appendix G.1.1). The paper verifies that the condition $\text{tr}(\mathbf{\Sigma}(\boldsymbol{\theta})) \leq \alpha (\mathcal{L}(\boldsymbol{\theta}) - \mathcal{L}^*)$ holds for common loss functions in the kernel regime (where the model behaves like a linear function of a fixed feature map):

• For square loss with Lipschitz features: $\alpha = 2 N L^2$, where $N$ is the dataset size and $L$ is the Lipschitz constant.
• For cross-entropy loss in the kernel regime: $\alpha = N \ell r$, which is independent of $d$ and scales only with the effective rank.

These verifications demonstrate that the assumption is not vacuous — it holds for realistic settings that capture the behavior of fine-tuned LMs.

The theoretical narrative in summary: Classical ZO lower bounds predict catastrophic slowness because they assume worst-case Hessian structure (full rank $d$). Pre-training and prompting ensure that the fine-tuning Hessian has low effective rank $r \ll d$, which drops the variance inflation factor from $d$ to $r$. This makes ZO optimization merely "somewhat slower" (factor of $r$) rather than "impossibly slow" (factor of $d$). The paper's experiments confirm this narrative: MeZO works, the number of tuned parameters does not substantially affect convergence speed (Section F.3, Figure 5 — full-parameter MeZO, MeZO with LoRA, and MeZO with prefix-tuning converge at similar rates despite tuning vastly different numbers of parameters), and the prompt is essential for this to hold (Appendix A.1).

4. Key Insights and Innovations

Innovation 1: The Effective Rank Hypothesis — Why Classical ZO Lower Bounds Don't Apply to Fine-Tuning

The paper's deepest conceptual contribution is not the algorithm itself, but the diagnostic reframing of why zeroth-order optimization can work at all on billion-parameter models. Classical ZO lower bounds (Nemirovskij and Yudin, 1983; Duchi et al., 2015; Jamieson et al., 2012) — which have occupied a near-axiomatic status in the optimization community for decades — predict that the convergence rate of any gradient-free method must scale linearly with the number of parameters $d$. For a 13B-parameter model, this would mean MeZO needs roughly 13 billion times more steps than SGD. The empirical results (Tables 1, 2, 18) flatly contradict this prediction: MeZO converges in roughly 100× more steps, not $10^{10} \times$ more.

What makes this more than an "empirical surprise" is that the paper provides a falsifiable structural explanation for why the classical bounds don't apply: the Hessian of the fine-tuning loss has low local effective rank $r \ll d$ (Assumption 1). The classical bounds assume the loss landscape can be adversarial — that the Hessian can have full rank $d$ and the gradient can point in any direction, forcing any gradient-free method to "search in the dark" across all $d$ dimensions. But pre-training and prompting fundamentally change the geometry: the model has already been optimized on a closely related objective, and the prompt ensures the fine-tuning task is "near" the pretraining manifold. This collapses the effective dimensionality of the optimization problem from $d$ to $r$, where $r$ may be as small as a few hundred (as suggested by prior work on intrinsic dimensionality; Aghajanyan et al., 2021; Li et al., 2018).

Why this is a conceptual advance rather than just an observation. Prior work had documented low effective rank of Hessians in trained networks (Papyan, 2018, 2020; Ghorbani et al., 2019) and low intrinsic dimensionality of fine-tuning (Aghajanyan et al., 2021), but no one had connected these empirical phenomena to the algorithmic viability of ZO optimization at scale. The paper's Theorem 1 makes this connection explicit: the slowdown factor $\gamma$ scales with $r/n$, not $d/n$. This transforms the question from "can ZO methods work for large models?" (answer per classical theory: absolutely not) to "under what conditions on the pretraining and task does the effective rank stay small?" (answer: when prompts are used and the task is close to pretraining). The ablation in Appendix A.1 (Table 5) is crucial confirmatory evidence: without prompts, MeZO collapses to near-random performance (SST-2 drops from 89.6% to 51.9%), validating that prompts are what maintain the low-effective-rank structure.

Comparison to prior theoretical ZO work. Prior ZO convergence analyses that avoided the $d$-dependence either assumed explicit low-dimensional structure known a priori (Wang et al., 2018; Balasubramanian and Ghadimi, 2018; Cai et al., 2022) — requiring the user to specify which subspace to search in — or used variance reduction techniques that still required $\Omega(sd \log d)$ memory (Ji et al., 2019; Liu et al., 2018). MeZO's insight is that pre-training automatically provides this low-dimensional structure without any explicit subspace identification, and the in-place implementation eliminates the memory cost entirely. This is a fundamental reframing of ZO optimization for deep learning: the question is no longer "how do we design ZO methods that overcome the $d$ curse?" but rather "how do we ensure our pretraining and task design maintain low effective rank so that simple ZO methods suffice?"

Significance beyond this paper. This insight opens a research program that the paper itself doesn't fully explore. If effective rank is the key quantity governing ZO efficiency, then measuring and predicting effective rank for different model architectures, pretraining objectives, and downstream tasks becomes a central diagnostic. The paper's finding that PEFT does not substantially accelerate MeZO convergence (Section F.3, Figure 5) — despite tuning far fewer parameters — makes sense under this lens: the effective rank $r$ is a property of the landscape geometry, not the number of tuned parameters. Reducing the parameter count from 13B to 19M (as with LoRA) doesn't change $r$ if the Hessian's outlier structure remains similar. This is a counterintuitive prediction that the paper's theory explains but that classical "variance scales with $d$" thinking would get exactly wrong.

---

Innovation 2: In-Place Gradient Estimation as a Memory Primitive

The algorithmic contribution — resampling the perturbation vector $\mathbf{z}$ from a stored seed rather than materializing it — may appear at first glance to be an implementation detail. It is not. It is a fundamental shift in the memory-compute tradeoff for gradient estimation that changes what is possible on a given hardware budget.

What the field did before. Prior work on memory-efficient backpropagation — gradient checkpointing (Chen et al., 2016), reversible layers, activation recomputation — trades compute for memory by discarding and recomputing intermediate activations during the backward pass. These methods can reduce memory by factors of 2–4× but still fundamentally require a backward pass: they must compute exact gradients through the computational graph. Parameter-efficient fine-tuning (LoRA, prefix-tuning) reduces the number of trainable parameters and checkpoint storage but, as the paper documents (Section 3.4, Figure 4), still requires 6× the inference memory because the sparse parameter updates require activation caching through all layers. These are quantitative improvements within the backpropagation paradigm — they make backpropagation cheaper but don't escape its core memory requirement of caching activations proportional to network depth.

What MeZO does differently. MeZO's in-place SPSA implementation is qualitatively different: it eliminates the backward pass entirely, reducing the memory-to-compute relationship from "memory proportional to model depth" to "memory proportional to the largest single weight matrix." This is not a quantitative improvement on backpropagation — it is a different point on the memory-compute Pareto frontier that backpropagation cannot reach, because backpropagation fundamentally requires storing or recomputing the computational graph. Proposition 2 (Appendix C) formalizes this: backpropagation can achieve $O(N^{1/c})$ memory at $O(cN)$ compute cost for a network of $N$ bits, but MeZO achieves $O(1)$ memory (plus the largest weight matrix) at $2N$ compute — a regime that backpropagation cannot match.

The seed-as-surrogate pattern. The specific technique — storing a seed and regenerating a pseudo-random vector on-demand — is not novel per se (it appears in various forms in reproducible research and distributed computing). What is novel is recognizing that this pattern can serve as a general memory primitive for zeroth-order optimization: any ZO gradient estimator that uses random perturbation vectors can be made memory-efficient by storing seeds rather than vectors. The paper demonstrates this for momentum and Adam (Section 2.2, Appendix B.2), where the full optimizer state can be recomputed from stored per-step seeds and scalar projected gradients. This requires only $2T$ scalars for $T$ steps — 160KB for 20,000 steps — compared to the hundreds of gigabytes that Adam's full moment buffers would require. The pattern generalizes beyond the specific optimizers tested: any optimizer that maintains per-parameter statistics derived from past gradients can, in principle, be implemented memory-efficiently by storing the random seeds and loss differences rather than the statistics themselves.

Evidence and limitations. The paper's memory profiling (Figure 4, Table 22) shows the practical impact: MeZO enables fine-tuning a 30B model on a single A100, while full fine-tuning requires 8 A100s. The storage efficiency argument (Section 2.1) — entire fine-tuning trajectory reconstructible from <0.1MB — is a striking demonstration of the seed-as-surrogate principle's power, reducing checkpoint storage by ~1200× compared to full model saving and ~380× compared to LoRA. However, this innovation comes with a significant caveat: the per-step compute cost is not negligible. Perturbing entire weight matrices (rather than individual scalars) is necessary for practical runtime but adds memory equal to the largest weight matrix (0.86GB for OPT-66B). The recomputation of optimizer state for momentum/Adam adds computational overhead per step. These are engineering tradeoffs, but they mean the memory savings are most dramatic at extreme scales where the largest weight matrix is still small relative to total inference memory.

---

Innovation 3: Non-Differentiable Objectives as a First-Class Target for Language Model Optimization

Backpropagation is fundamentally a tool for minimizing differentiable loss functions. Yet many of the most important objectives in modern LM development — human preference scores, safety ratings, task-specific metrics like F1 and BLEU, factual accuracy, and fairness criteria — are non-differentiable. The current dominant approach to optimizing these objectives is RLHF (Christiano et al., 2017; Ouyang et al., 2022): train a differentiable reward model to approximate the non-differentiable objective, then use reinforcement learning (typically PPO) to optimize the LM against this proxy. This pipeline is complex (requiring reward model training, RL infrastructure, and careful tuning to prevent reward hacking), computationally expensive, and introduces approximation error between the proxy reward and the true objective.

What MeZO enables that backpropagation cannot. Because MeZO estimates gradients from function value differences, the "function" being evaluated need not be differentiable — it need only return a scalar value given a set of parameters and a batch of data. The paper demonstrates (Section 3.3, Table 3) that MeZO can directly optimize accuracy (for RoBERTa-large classification) and F1 score (for OPT-13B on SQuAD), treating the model as a black box that returns the metric value given perturbed parameters. The results are preliminary — cross-entropy still outperforms direct accuracy/F1 optimization (e.g., 94.3% vs. 68.6% on TREC) — but they establish the feasibility of the approach and open a path toward simplifying complex optimization pipelines.

Why this is a conceptual reframing, not just a feature. Prior work on gradient-free LM adaptation — BBT and BBTv2 (Sun et al., 2022b, a), black-box prompt tuning (Diao et al., 2022; Chai et al., 2022) — also used forward-pass-only optimization, but these methods were limited to tuning low-dimensional continuous prompts or discrete prompt tokens, not the full model parameters. They treated the model as frozen and optimized the input representation. MeZO flips this: the model parameters themselves are optimized against any black-box objective, while the input format (prompts) remains fixed. This distinction matters because adapting model parameters can capture deeper task-specific knowledge than prompt optimization alone, as evidenced by MeZO's substantial outperformance of BBTv2 (Table 21: +11.2% on SNLI, +7.3% on RTE).

Limitations and open questions. The paper's non-differentiable optimization results are not yet competitive with cross-entropy training, and the authors do not investigate why — is it a variance issue (gradients estimated from accuracy differences are noisier than those from loss differences), a landscape issue (accuracy surfaces are flatter or have more local optima), or a sample efficiency issue (accuracy only changes when predictions cross decision boundaries)? Understanding these failure modes is essential before MeZO can be used for RLHF-style preference optimization at scale. The paper also doesn't explore the interaction between non-differentiable objectives and the low-effective-rank theory — if the effective rank assumption relies on the objective being "close" to pretraining, a non-differentiable objective like human preference may violate this assumption and degrade ZO efficiency.

---

Innovation 4: Storage as a Novel Design Axis — Checkpoint Efficiency Through Trajectory Reconstruction

The storage cost of fine-tuned model checkpoints is typically treated as an afterthought — a deployment concern, not a training concern. The paper elevates storage to a first-class design consideration by showing that MeZO's seed-based perturbation mechanism enables an entirely new mode of checkpoint management: rather than storing the fine-tuned parameters, store the trajectory (seeds and projected gradients) and replay it to reconstruct the final model.

What this enables that no prior method achieves. The numbers are striking (Section 2.1): a 66B-parameter model fine-tuned with MeZO requires saving one initial seed plus 20,000 steps × 2 bytes ≈ 0.04MB. LoRA for the same model requires 38MB (for 19M tuned parameters at FP16). Full model storage requires ~132GB (at FP16). This is not a 2× or even 10× improvement — it is a factor of ~1200× over LoRA and ~3,300,000× over full model storage. More importantly, this storage efficiency comes with a qualitatively new capability: the ability to exactly reproduce any checkpoint from the training trajectory without storing intermediate parameter snapshots. This has implications for:

• Multi-task serving: A system serving 100 specialized fine-tuned variants of a 66B model would need ~13.2TB to store full checkpoints, ~3.8GB for LoRA adapters, or ~4MB for MeZO trajectories. The MeZO number is small enough to store in a configuration file.
• Reproducibility and debugging: The full training trajectory can be archived with negligible cost, enabling exact reproduction of any training run for debugging or auditing.
• Continual learning and model versioning: Since the trajectory is additive (new steps append new seeds and scalars), incremental updates can be stored as diffs without duplicating the base model.

Why this hasn't been done before. Prior work on storage-efficient fine-tuning focused on reducing the number of trained parameters (PEFT methods) or quantizing the trained weights (Dettmers et al., 2022a, b). These methods reduce storage proportionally to the compression ratio — 8-bit quantization gives 2× reduction, LoRA with rank 8 gives $\sim 100\times$ reduction on a 13B model. But they all fundamentally store parameter deltas. MeZO's approach is categorically different: it stores the random seed and scalar measurements that generated the deltas, exploiting the fact that pseudo-random number generators are deterministic functions. This is an insight from the systems/randomness community that hadn't been applied to model storage because no prior fine-tuning method had a training procedure where the parameter updates were fully determined by a seed and a scalar.

The catch. Trajectory reconstruction requires replaying all forward passes to apply the stored updates — reconstructing the final checkpoint from a MeZO trajectory costs one full training run of compute (though without the data loading and loss computation overhead of actual training). For a 66B model trained for 20,000 steps, this could take hours. The paper presents this as a capability — you can store at this compression ratio — rather than claiming it's always the right tradeoff. For applications where storage is the bottleneck (e.g., serving hundreds of task-specific models from limited disk), paying the reconstruction cost once at deployment time may be well worthwhile.

5. Experimental Analysis

Evaluation Methodology

• Dataset. The paper uses two families of benchmarks. For RoBERTa-large experiments (masked LM), six classification datasets are used: SST-2 (sentiment, Socher et al., 2013), SST-5 (5-way sentiment), TREC (6-way topic classification, Voorhees and Tice, 2000), MNLI and SNLI (natural language inference, Williams et al., 2018; Bowman et al., 2015), and RTE (textual entailment, Dagan et al., 2005; Bar Haim et al., 2006; Giampiccolo et al., 2007; Bentivogli et al., 2009). Test sets are limited to 1,000 examples for fast iteration, and two data regimes are studied: few-shot (k = 16 examples per class) and many-shot (k = 512 examples per class), with the same k used for both training and validation. For OPT autoregressive model experiments, the paper uses classification datasets (SST-2, BoolQ, CB, RTE, WSC, WiC), multiple-choice datasets (COPA, MultiRC, ReCoRD), and two generation/question-answering datasets (SQuAD, Rajpurkar et al., 2016; DROP, Dua et al., 2019), with 1,000 training, 500 validation, and 1,000 test examples randomly sampled per dataset.

• Base model(s). Experiments span two model families: RoBERTa-large (350M parameters; Liu et al., 2019b), a masked language model, for the medium-scale experiments; and the OPT family (Zhang et al., 2022a) at scales of 13B, 30B, and 66B parameters, autoregressive decoder-only transformers. The choice of RoBERTa-large enables direct comparison with prior fine-tuning and ZO baselines (BBTv2, Malladi et al., 2022), while OPT models test scaling to the regime where backpropagation becomes memory-prohibitive (the 13B model already requires 4× A100s for full fine-tuning and 2× for prefix-tuning; the 30B model requires 8× A100s for full fine-tuning, while MeZO fits on a single A100).

• Metrics. For classification tasks, accuracy (%) is reported, computed as the fraction of test examples where the model's predicted label (the one with highest average log-likelihood among candidate label words) matches the ground truth. For multiple-choice tasks, the same accuracy metric applies. For generation tasks (SQuAD, DROP), exact match is used, comparing the greedily decoded output string against the reference answer. All RoBERTa-large results are averaged over 5 random seeds with standard deviations reported; OPT results are single-run best-validation-checkpoint evaluations.

• Baselines. Four categories of baselines are compared, spanning the memory-accuracy tradeoff space:

  • Zero-shot: the pretrained model evaluated with the same prompt template but no training examples.
  • In-context learning (ICL) (Brown et al., 2020): 32 labeled examples provided in the prompt, with no parameter updates. The paper notes that using more than 32 examples did not improve performance and sometimes caused instability.
  • Linear probing (LP): a linear classifier trained on top of frozen pretrained representations. For classification tasks, this uses scipy's solver on the output feature; for multiple-choice and generation, where the output space is the full vocabulary, head-tuning (training only the LM projection head for 5 epochs with batch size 8 and learning rates in {1e-4, 5e-4}) is used instead. This baseline has the same memory footprint as inference but limited capacity.
  • Fine-tuning with Adam (FT): full backpropagation-based fine-tuning with the Adam optimizer (Kingma and Ba, 2015). For RoBERTa-large, this uses 1,000 steps with linear learning rate decay and batch sizes in {2, 4, 8} for k = 16 and {8, 16, 32} for k = 512, with learning rates {1e-5, 3e-5, 5e-5}. For OPT, this uses 5 epochs (625 steps for 1,000 training examples) with batch size 8 and learning rates in {1e-5, 5e-5, 8e-5}. Also included are FT (LoRA) and FT (prefix) variants, corresponding to parameter-efficient fine-tuning via backpropagation.
  • BBTv2 (Sun et al., 2022a): a prior gradient-free method that uses evolutionary algorithms to optimize a low-dimensional projection of prefix tokens, included for RoBERTa-large comparisons on mutually assessed tasks (SST-2, SNLI, RTE; Table 21).

• Generation budget / compute accounting. The paper measures compute in number of forward passes, which is the standard unit in the zeroth-order optimization literature. For MeZO, each step requires 2 forward passes (one for ℓ+, one for ℓ-), so T training steps consume 2T forward passes. For backpropagation-based fine-tuning, one step consumes one forward and one backward pass, which the paper treats as approximately comparable to two forward passes in terms of computation (though exact FLOP counting would show backpropagation is more expensive; the paper's wall-clock measurements in Section 3.4 capture the practical difference). The paper standardizes total forward passes for ablation comparisons (Appendix A uses 10,000 forward passes as a fixed budget to compare ZO algorithmic variants). For the main experiments, the step counts are fixed rather than the forward-pass count: RoBERTa-large MeZO runs for 100K steps (200K forward passes) vs. FT's 1K steps; OPT MeZO runs for 20K steps (40K forward passes) vs. FT's 5 epochs (~625 steps, each costing one forward + backward). This means MeZO uses substantially more forward passes — roughly 200× more for RoBERTa-large and 64× more for OPT — but the per-step wall-clock time is much lower due to avoiding backpropagation and enabling single-GPU execution.

• Cross-validation / statistical protocol. For RoBERTa-large experiments, each setting is run with 5 different random seeds, and the mean and standard deviation of test accuracy are reported (Table 18). For OPT experiments, a single training run is performed per configuration, with the best model selected based on validation set performance evaluated every 1/5 of total training steps. The 30B and 66B OPT models skip intermediate validation checkpointing due to storage costs and use the final checkpoint directly. The paper uses a fixed hyperparameter grid for each method (Tables 15 and 16) and selects the configuration achieving the best validation accuracy. The standard deviation for OPT results is not reported.

---

Main Quantitative Results

The experimental results are organized by model family and scale, with separate analyses for medium-sized masked LMs (RoBERTa-large, Section 3.1) and large autoregressive LMs (OPT, Section 3.2). Within each, the paper compares MeZO against baselines of increasing memory cost (zero-shot, ICL, LP, FT) and evaluates across task types (classification, multiple-choice, generation).

Medium-Sized Masked Language Models: RoBERTa-Large (Table 18, Figure 2)

Headline result: MeZO substantially outperforms memory-equivalent baselines and closes most of the gap to backpropagation-based fine-tuning while using 1× inference memory vs. 12× for FT.

In the few-shot setting (k = 16), MeZO achieves strong results across all six tasks. On SST-2, MeZO reaches 90.5% accuracy — compared to 79.0% for zero-shot, 76.0% for linear probing, and 91.9% for full FT. The gap to FT is only 1.4 percentage points. On SST-5, MeZO's 45.5% trails FT's 47.5% by 2.0 points. On the harder NLI tasks, the gaps widen: SNLI shows MeZO at 68.5% vs. FT at 77.5% (9.0 point gap), and MNLI shows 58.7% vs. 70.0% (11.3 point gap). RTE shows 64.0% vs. 66.4% (2.4 points), and TREC shows 76.9% vs. 85.0% (8.1 points). Across all six tasks, MeZO improves over zero-shot by an average of 25.2 percentage points and over linear probing by 14.5 points.

In the many-shot setting (k = 512), the gaps to FT narrow substantially. On SST-2, MeZO reaches 93.3% vs. FT's 93.9% (0.6 point gap). On SST-5: 53.2% vs. 55.9% (2.7 points). SNLI: 83.0% vs. 88.7% (5.7 points). MNLI: 78.3% vs. 84.4% (6.1 points). RTE: 78.6% vs. 82.7% (4.1 points). TREC: 94.3% vs. 97.3% (3.0 points). All within the paper's stated "within 5% gap" claim when considering the absolute percentage difference on SST-2, SST-5, RTE, and TREC, with SNLI and MNLI slightly exceeding 5 percentage points.

Comparison of MeZO variants (Table 18). MeZO with full-parameter tuning, MeZO (LoRA), and MeZO (prefix) achieve broadly comparable performance. In the k = 512 setting, the best MeZO variant on each task is: SST-2: MeZO (LoRA) at 93.4%; SST-5: MeZO-Adam at 53.9%; SNLI: MeZO-Adam at 85.3%; MNLI: MeZO (prefix) at 79.8%; RTE: MeZO-Adam at 79.2%; TREC: MeZO-Adam at 95.1%. The differences between the best and worst MeZO variant within each task are typically 1–2 percentage points, confirming that the choice of parameter subset (full vs. PEFT) and optimizer variant (SGD vs. Adam) has limited impact on final performance in this regime.

MeZO vs. BBTv2 (Table 21). On the three mutually assessed tasks, MeZO substantially outperforms BBTv2. On SST-2: MeZO 90.5% vs. BBTv2 90.3% (similar). On SNLI: MeZO 68.5% vs. BBTv2 57.3% (11.2 point advantage). On RTE: MeZO 64.0% vs. BBTv2 56.7% (7.3 point advantage). The paper attributes this to BBTv2's limitation to optimizing only a low-dimensional projection of prefixes, whereas MeZO can optimize all model parameters directly.

---

Large Autoregressive Language Models: OPT-13B (Table 1, Figures 1 and 4)

Headline result: MeZO outperforms or matches FT on 7 of 11 tasks while using 12× less memory, and outperforms zero-shot, ICL, and LP across the board.

Classification tasks (SST-2, RTE, CB, BoolQ, WSC, WiC). MeZO achieves results that are close to or better than FT on most classification benchmarks:

• SST-2: MeZO 91.4% vs. FT 92.0% (0.6 point gap). ICL achieves 87.0%, and LP reaches 93.4% — the one case where LP slightly exceeds MeZO.
• RTE: MeZO 66.1%, MeZO (prefix) 70.8%, FT 70.8%. The prefix variant ties FT exactly.
• CB: MeZO 67.9%, MeZO (prefix) 69.6%, FT 83.9%. This is the largest classification gap (16.0 points for the best MeZO variant vs. FT), suggesting CB is one of the harder tasks for ZO optimization.
• BoolQ: MeZO 67.6%, MeZO (LoRA) 73.8%, FT 77.1%. The gap narrows to 3.3 points with LoRA.
• WSC: MeZO 63.5%, FT 63.5%. Exact match.
• WiC: MeZO 61.1%, FT 70.1%. A 9-point gap, the second largest classification shortfall.

Multiple-choice tasks (MultiRC, COPA, ReCoRD). Performance patterns vary by task:

• MultiRC: MeZO (prefix) achieves 63.7% vs. FT at 71.1% (7.4 point gap), but substantially above LP (63.5%), ICL (53.1%), and zero-shot (46.9%).
• COPA: MeZO 88.0%, surpassing FT at 79.0% by a full 9 points. This is one of the 7 tasks where MeZO outperforms FT. The paper does not analyze why MeZO would exceed FT — possibly due to FT overfitting on the small (1,000-example) training set while MeZO's implicit regularization from noise injection prevents overfitting.
• ReCoRD: MeZO 81.7% vs. FT 74.1%. Another case where MeZO exceeds FT by a substantial margin (7.6 points).

Generation tasks (SQuAD, DROP). MeZO demonstrates effective training on generative tasks, which the paper notes are "regarded as more intricate than classification":

• SQuAD: MeZO 84.7% vs. FT 84.9%. Essentially identical (0.2 point difference), and substantially above ICL (75.9%), LP (3.7% — head-tuning fails badly on generation), and zero-shot (46.2%).
• DROP: MeZO (LoRA) 31.4% vs. FT 31.3%. Again nearly identical, with both methods far above zero-shot (14.6%) and ICL (29.6%).

Across-task summary. MeZO achieves comparable (within 1% absolute) or better performance than FT on SST-2, RTE, WSC, COPA, ReCoRD, SQuAD, and DROP — exactly 7 of 11 tasks as claimed. The remaining tasks (CB, BoolQ, WiC, MultiRC) show gaps of 3–16 points, with CB being the most challenging. MeZO consistently outperforms ICL (10 of 11 tasks, with RTE being the sole exception where ICL at 62.1% edges MeZO's 66.1%) and LP (9 of 11 tasks, with LP winning only on SST-2 and losing catastrophically on generation tasks).

---

Scaling to 66B Parameters: OPT-30B and OPT-66B (Table 2, Table 20)

Headline result: MeZO continues to effectively optimize models up to 66B parameters, outperforming zero-shot and ICL, though direct FT comparison is infeasible at these scales due to hardware constraints.

On OPT-30B: MeZO (best of full-parameter and prefix) achieves: SST-2 90.6% vs. ICL 81.9% vs. zero-shot 56.7%; RTE 72.6% vs. ICL 66.8%; BoolQ 73.5% vs. ICL 66.2%; WSC 63.5% vs. ICL 56.7%; WiC 59.1% vs. ICL 51.3%; SQuAD 85.2% vs. ICL 78.0%. On every task, MeZO substantially exceeds ICL and zero-shot performance. No FT baseline is provided at this scale — the paper's Figure 4 shows that full FT of a 30B model requires 8 A100s, making systematic comparison across 6+ tasks prohibitively expensive.

On OPT-66B: MeZO (best variant) achieves: SST-2 93.6% vs. ICL 89.3% vs. zero-shot 57.5%; RTE 66.4% vs. ICL 65.3%; BoolQ 73.7% vs. ICL 62.8%; WSC 63.5% vs. ICL 52.9%; WiC 58.9% vs. ICL 54.9%; SQuAD 85.0% vs. ICL 81.3%. Performance is broadly similar to or slightly better than OPT-30B, with SST-2 showing the clearest improvement (93.6% vs. 90.6% at 30B). The paper notes that MeZO with full-parameter tuning on the 66B model required "further tuning to successfully optimize" for SQuAD (indicated by * in Table 20), suggesting that the learning rate and perturbation scale choices may need model-size-dependent adjustment at extreme scales.

---

Memory Profiling Results (Figures 3 and 4, Table 22, Section 3.4)

Headline result: MeZO consumes the same GPU memory as inference across all model scales, representing 12× reduction vs. full FT and 6× vs. prefix FT on OPT-13B.

The memory profiling (Table 22, Figure 3) on the MultiRC dataset (average 400 tokens per example) reveals:

• OPT-1.3B: MeZO/zero-shot 4GB, FT 27GB (6.8× reduction).
• OPT-2.7B: MeZO 7GB, FT 55GB (7.9× reduction).
• OPT-6.7B: MeZO 14GB, FT requires 2×A100s with 156GB total. MeZO fits on a single A100.
• OPT-13B: MeZO 26GB, FT requires 4×A100s with 316GB total, prefix FT requires 2×A100s with 158GB. MeZO uses 12× less than FT and 6× less than prefix FT (since 26GB × 6 ≈ 158GB).
• OPT-30B: MeZO 58GB, FT requires 8×A100s (633GB). A single 80GB A100 can run MeZO but not even inference for larger models.
• OPT-66B: MeZO requires 2×A100s (128GB), FT would require 16×A100s (estimated, not tested).

Figure 4 tabulates the largest tunable model on common hardware configurations: with a single A100, FT can tune only OPT-2.7B while MeZO can tune OPT-30B — an 11× increase in model scale.

Wall-clock time analysis (Section F.6, Table 23). The per-step timing on MultiRC shows: MeZO (batch size 16) on OPT-30B takes 5.896 seconds per step on 1 GPU; FT (batch size 8) takes 45.608 seconds per step on 8 GPUs — a 7.74× per-step speedup for MeZO. However, MeZO requires 32× more steps (20K vs. 625), so the net GPU-hour comparison is: MeZO uses 20,000 × 5.896 / 3600 ≈ 32.8 GPU-hours on 1 GPU; FT uses 625 × 45.608 / 3600 ≈ 7.9 GPU-hours on 8 GPUs = 63.3 GPU-hours total. MeZO therefore requires roughly half the total GPU-hours of FT (32.8 vs. 63.3) while fitting on 8× fewer GPUs. The paper emphasizes that this advantage is "not inherent to the algorithm and is highly dependent on the implementation" — the primary claim is memory efficiency, with wall-clock time being a secondary benefit in certain regimes.

---

Non-Differentiable Objective Optimization (Table 3, Section 3.3)

Headline result: MeZO can optimize non-differentiable objectives (accuracy, F1) directly, achieving performance between zero-shot and cross-entropy-trained models, while backpropagation cannot optimize these objectives at all.

On RoBERTa-large with k = 512 classification tasks:

• SST-2: Zero-shot 79.0%, MeZO with cross-entropy 93.3%, MeZO with accuracy 92.7% (0.6 point gap from cross-entropy).
• SST-5: Zero-shot 35.5%, cross-entropy 53.2%, accuracy 48.9% (4.3 point gap).
• SNLI: Zero-shot 50.2%, cross-entropy 83.0%, accuracy 82.7% (0.3 point gap).
• TREC: Zero-shot 32.0%, cross-entropy 94.3%, accuracy 68.6% (25.7 point gap — a large degradation).

On OPT-13B with SQuAD (1,000 examples), MeZO (prefix) with F1 as the objective:

• Zero-shot 46.2%, cross-entropy (MeZO prefix) 84.7%, F1 (MeZO prefix) 78.5% (6.2 point gap from cross-entropy, but 32.3 points above zero-shot).

The pattern is task-dependent: accuracy/F1 optimization works well on some tasks (SST-2, SNLI) but degrades substantially on others (TREC, SST-5). The paper acknowledges that "minimizing cross entropy results in stronger performance" and frames these as "preliminary findings" demonstrating feasibility rather than state-of-the-art.

---

Ablation Studies and Robustness Checks

The ablation experiments are primarily conducted on RoBERTa-large in a standardized setting with k = 16 examples per class, a fixed budget of 10,000 forward passes, and 5 random seeds, evaluated on SST-2, SNLI, and TREC (Appendix A). This protocol allows fair comparison of algorithmic variants by controlling total forward-pass compute.

• Prompt vs. no prompt (Appendix A.1, Table 5). The presence of a prompt is critical. On SST-2, MeZO with prompt achieves 89.6% vs. 51.9% without prompt — essentially random-chance performance for binary classification. On SNLI: 65.1% with prompt vs. 34.8% without. On TREC: 66.7% with prompt vs. 19.5% without. The paper interprets this as evidence that prompts ensure the fine-tuning objective is "close" to pretraining, preserving the low-effective-rank Hessian structure that enables efficient ZO optimization. Without prompts, the landscape reverts to the "worst-case" behavior that classical ZO lower bounds describe. This is the pivotal empirical finding that motivated the paper's theoretical framework.

• Number of perturbation vectors n in n-SPSA (Appendix A.2, Table 6). When fixing total forward-pass budget at 10,000, increasing n (and proportionally decreasing the number of steps) yields marginal improvements at best. For n = 1 (constant schedule): SST-2 89.6%, SNLI 65.1%, TREC 66.7%. For n = 4 (constant): 89.5%, 68.6%, 62.3%. For n = 16 (constant): 90.4%, 67.0%, 62.8%. The largest gain is 0.8 points on SST-2 for a 16× increase in per-step forward-pass cost. The paper also tests linearly increasing n (starting small and growing), which does not consistently help. This justifies n = 1 as the default — the variance reduction from averaging multiple z vectors does not compensate for the reduced number of optimization steps at a fixed total budget.

• MeZO-Adam vs. MeZO (SGD) (Appendix B.2, Table 18). Using the memory-efficient Adam implementation (recomputing moment estimates from stored seeds and scalars; Section 2.2) sometimes but not consistently improves performance. On RoBERTa-large k = 16: SST-2 90.4% (Adam) vs. 90.5% (SGD); SNLI 74.1% vs. 68.5% (5.6 point improvement for Adam), RTE 59.2% vs. 64.0% (Adam underperforms). On k = 512: SST-2 93.3% (tie); SNLI 85.3% vs. 83.0% (2.3 point improvement); RTE 79.2% vs. 78.6% (0.6 point); TREC 95.1% vs. 94.3% (0.8 point). Adam provides modest gains on some tasks but is not universally superior, and the paper uses SGD as the default MeZO optimizer to keep the method simple and the memory analysis clean.

• One-point vs. two-point gradient estimator (Appendix B.5, Table 11). The one-point estimator (Zhang et al., 2022b), which uses ℒ(θ_t + εz_t; ℬ_t) and ℒ(θ_{t-1} + εz_{t-1}; ℬ_{t-1}) to estimate the gradient with only one forward pass per step, is much less efficient than the two-point SPSA estimator when fixing total forward passes. On RoBERTa-large k = 16 at 20K steps, SPSA achieves SST-2 92.8%, SNLI 82.9%, RTE 76.7%, TREC 92.7%. The one-point estimator at 20K steps (half the forward passes of SPSA): 90.0%, 70.1%, 64.1%, 57.3% — substantially worse. Even at 40K steps (equal forward passes to SPSA's 20K): 91.8%, 74.4%, 68.7%, 73.0% — improving but still trailing SPSA on all tasks except TREC. This validates the two-point symmetric difference as the preferred estimator despite requiring twice the forward passes per step.

• Variance-modified SPSA using gradient norms or parameter norms (Appendix B.3, Tables 8 and 9). Scaling the perturbation in each parameter group by the estimated gradient norm (Definition 6) does not improve performance. With the gradient norm estimated via Proposition 1 (the ZO estimate requiring 2L forward passes for L layers), results are mixed and generally worse than baseline MeZO. On SST-2: 89.6% (baseline) vs. 87.0% with ZO-estimated gradient norms. On SNLI: 65.1% vs. 49.6% — a 15.5 point degradation. On TREC: 66.7% vs. 32.6%. If gradient norms are "cheated" via one backpropagation, the results improve (89.7%, 65.2%, 64.3%) but still do not beat the baseline. Using parameter norms instead (Table 9) is also not beneficial: 89.2%, 65.4%, 64.8% at best. The paper interprets this negative result as supporting the effective-rank theory — the straightforward variance analysis (which would predict improvement from per-layer variance scaling) does not capture the optimization dynamics, and the low-effective-rank structure makes such variance reduction unnecessary.

• Expectation-modified SPSA for normalized gradient (Appendix B.4, Table 10). Using Definition 7 to estimate a coordinate-wise normalized gradient (analogous to what Adam or signSGD would compute) performs worse than the standard SPSA gradient estimate. On SST-2: 88.0% vs. 89.6% baseline; SNLI: 60.0% vs. 65.1%; TREC: 44.0% vs. 66.7%. The degradation is most severe on TREC, where accuracy nearly halves.

• Linear probing before MeZO (LP-MeZO) (Appendix F.1, Table 19). Following the suggestion of Kumar et al. (2022) that linear probing before fine-tuning can improve out-of-distribution robustness, the paper tests LP → MeZO on RoBERTa-large k = 16. Results are mixed and sometimes harmful: SST-2 improves from 90.5% (MeZO only) to 91.4% (LP-MeZO); SST-5 degrades from 45.5% to 41.9%; SNLI slightly improves from 68.5% to 70.7%; TREC severely degrades from 76.9% to 54.0%. The paper does not recommend LP-MeZO as a general strategy.

• Convergence speed vs. number of tuned parameters (Section F.3, Figure 5). MeZO with full-parameter tuning, MeZO (LoRA) tuning ~19M parameters, and MeZO (prefix) tuning ~6M parameters converge at similar rates on SST-2 and SNLI during the first 5,000 steps. This is a critical validation of the effective-rank theory: if convergence depended on the number of tuned parameters d_tuned, MeZO (prefix) should converge ~2,000× faster than full-parameter MeZO (since d_tuned is ~10^4× smaller). The observation that convergence speed is similar regardless of how many parameters are tuned supports the claim that the relevant quantity is the effective rank r of the Hessian, not the raw parameter count.

• Prefix initialization for MeZO (prefix) and FT (prefix) (Appendix B, Table 17). Initializing prefix tokens by passing real vocabulary tokens through the model (rather than random initialization) is "crucial to make prefix tuning stable with MeZO" and also boosts FT (prefix) performance. On SST-2: FT (prefix, random init) 90.7% vs. FT (prefix, real activation init) 91.9%. On SNLI: 70.7% vs. 77.2% (6.5 point improvement). On TREC: 83.4% vs. 85.7%. This suggests that the optimization landscape for prefixes is more benign when initialized near meaningful representations, consistent with the effective-rank theory.

---

Critical Assessment

Claim 1: "MeZO significantly outperforms in-context learning and linear probing"

This claim is well-supported. Across all model scales (350M to 66B), task types (classification, multiple-choice, generation), and data regimes (few-shot, many-shot), MeZO consistently outperforms ICL and LP. The margins are often large: on OPT-13B generation tasks, MeZO achieves 84.7% vs. ICL's 75.9% on SQuAD and 30.9% vs. 29.6% on DROP (Table 1); on RoBERTa-large k = 16, MeZO improves over LP by an average of 14.5 points across six tasks (Table 18). The sole exception is SST-2 on OPT-13B, where LP edges MeZO 93.4% vs. 91.4% — but LP fails catastrophically on generation tasks (3.7% on SQuAD), making it not a general-purpose alternative. The ICL baseline uses 32 demonstrations, which the paper notes is the maximum that consistently helped; more demonstrations sometimes caused instability, so ICL is tested at a reasonable strength.

However, the ICL comparison has a nuance: MeZO uses 1,000 training examples (for OPT) or k examples per class (for RoBERTa), processes them through many optimization steps, and incurs significant compute. ICL uses only 32 labeled examples with zero training compute. These are fundamentally different operating points: MeZO trades data and compute for accuracy, while ICL prioritizes zero training cost. The paper's framing that MeZO "outperforms" ICL is accurate as a performance statement but elides the computational cost difference. A fairer comparison might ask: at equivalent total inference FLOPs (including both the training forward passes and the final inference), does MeZO still beat ICL? The paper does not address this.

Claim 2: "MeZO achieves comparable performance to fine-tuning with backpropagation across multiple tasks"

This claim is supported with qualifications that the paper itself makes clear. On OPT-13B, MeZO is within 1% of FT on 7 of 11 tasks (SST-2, RTE, WSC, COPA, ReCoRD, SQuAD, DROP). On RoBERTa-large k = 512, MeZO is within 5 percentage points of FT on all six tasks, with the gaps ranging from 0.6 points (SST-2) to 6.1 points (MNLI). These are genuine achievements given the 12× memory reduction.

The qualifications that matter:

• MeZO uses substantially more training steps than FT (100K vs. 1K for RoBERTa, 20K vs. 625 for OPT). The paper's wall-clock analysis (Section F.6) shows that the per-step speedup partially compensates, but the total compute (forward passes) is much higher for MeZO. On RoBERTa-large k = 512, FT uses ~1,000 × 2 × 32 = 64,000 forward-pass-equivalents (counting backward as ~2× forward), while MeZO uses 100,000 × 2 = 200,000 forward passes — roughly 3× more. On OPT, FT uses ~625 × 2 × 8 = 10,000 forward-pass-equivalents, while MeZO uses 20,000 × 2 = 40,000 — 4× more. The "comparable performance" comes at a higher computational cost in terms of total FLOPs, which is traded against dramatically lower memory. This is a legitimate tradeoff, but it means the claim is specifically about accuracy at fixed memory, not accuracy at fixed FLOPs.
• On 4 of 11 OPT tasks (CB, BoolQ, WiC, MultiRC), MeZO trails FT by 3–16 points. These are not "comparable." The paper does not analyze what makes these tasks harder for ZO optimization — perhaps their loss landscapes have higher effective rank, or they require more precise gradient information, or they are simply harder tasks where FT's advantage from exact gradients compounds over more steps. A task-level diagnostic would strengthen the paper's narrative about when MeZO works and when it doesn't.
• The FT baseline uses Adam, which adapts learning rates per parameter and often substantially outperforms SGD. MeZO's default is ZO-SGD (no momentum or adaptivity), though MeZO-Adam variants are tested. A reader might ask: if FT used SGD instead of Adam, would the gap narrow? The paper includes FT with SGD in the hyperparameter grid (Table 15) but does not report those results, making the FT baseline a moving target — it's the best of several optimizer choices, while MeZO is the best of ZO variants. In fairness, FT with SGD typically underperforms FT with Adam for transformer fine-tuning, so this choice likely makes FT stronger, not weaker.

Claim 3: "MeZO is compatible with both full-parameter and parameter-efficient tuning techniques"

This claim is well-supported. Tables 1 and 18 show MeZO (full), MeZO (LoRA), and MeZO (prefix) results across all tasks. The three variants achieve broadly comparable performance, with neither PEFT approach consistently outperforming full-parameter MeZO. The convergence rate comparison (Figure 5) shows that PEFT does not accelerate training — the three variants follow similar loss curves despite tuning vastly different numbers of parameters. This is actually a positive finding for full-parameter MeZO: it means practitioners can choose full-parameter tuning for maximal expressivity without paying a convergence penalty.

A nuance: The paper reports that MeZO (prefix) "sometimes outperforms MeZO" (Section 3.1), which could be interpreted as evidence that PEFT is better. But the differences are small (1–3 points, not consistently in one direction), and the theoretical framework predicts that both should converge at similar rates because the effective rank r is similar regardless of the parameter subset. The experimental evidence supports this prediction.

Claim 4: "MeZO can effectively optimize non-differentiable objectives"

This claim is supported but weakly and preliminarily. Table 3 shows that MeZO can optimize accuracy and F1 directly, achieving results substantially above zero-shot. However:

• The cross-entropy-trained MeZO consistently outperforms the accuracy/F1-trained MeZO, often by large margins (25.7 points on TREC, 6.2 points on SQuAD F1). The paper does not investigate why — is it the noise properties of accuracy vs. cross-entropy as a loss function, or the landscape geometry, or something else?
• The experiments are limited to two model-task combinations (RoBERTa classification, OPT SQuAD) with a total of five data points. No systematic sweep of tasks, objectives, or hyperparameters is performed for the non-differentiable setting.
• The most exciting application — optimizing against human preference scores (RLHF-style) — is not tested in any form. The paper mentions this as motivation but does not run experiments, even with a synthetic preference signal.
• The accuracy/F1 experiments use the same hyperparameter grids and perturbation scales as the cross-entropy experiments. It's possible that these objectives require different ε or learning rate choices that were not explored.

Given the paper's positioning of non-differentiable optimization as a key capability (it's the fourth contribution bullet point in Section 1), the experimental support is thin. The results demonstrate feasibility but not competitiveness.

Claim 5: "Our theory suggests that adequate pre-training ensures the per-step optimization rate and global convergence rate depend on the local effective rank of the landscape instead of the number of parameters"

This theoretical claim is supported by a combination of mathematical derivation and indirect empirical evidence, but not by direct measurement of effective rank. The paper's Theorem 1 and Lemma 3 are mathematically sound given Assumption 1 (low local effective rank). The convergence rate is shown to scale with r/n rather than d. The empirical evidence supporting the assumption comes from:

• Prior work documenting low effective rank of Hessians in trained networks (Papyan, 2018, 2020; Ghorbani et al., 2019).
• The prompt ablation (Table 5), showing that removing the prompt causes MeZO to fail — consistent with the prompt being what maintains the low-effective-rank structure.
• The PEFT convergence experiment (Figure 5), showing that reducing the number of tuned parameters from 350M to ~6M does not accelerate convergence — consistent with the effective rank being the bottleneck, not d.
• The variance-reduction ablation (Tables 8, 9), showing that per-layer variance scaling does not help — consistent with the bottleneck being a global property (effective rank) rather than per-layer gradient magnitudes.

What is missing: The paper never directly measures the effective rank r for its specific models and tasks. The argument is a plausibility argument — "prior work found low effective rank in similar settings, and our empirical observations are consistent with this explanation" — rather than a demonstrated causal chain. Measuring the Hessian effective rank for a 13B-parameter model on a 1,000-example dataset is computationally demanding (requiring Hessian-vector products or Lanczos iterations), so the omission is understandable but leaves the theory as a compelling explanatory framework rather than a verified mechanism. A skeptical reader could posit alternative explanations for why MeZO works (e.g., the prompt constrains the optimization to a region where the loss is nearly convex, or the SPSA gradient noise acts as beneficial regularization that prevents overfitting on small datasets) that are not ruled out by the presented evidence.

Claim 6: "Up to 12× memory reduction and up to 2× GPU-hour reduction"

The 12× memory reduction claim is solidly supported by the memory profiling (Table 22, Figure 4). On OPT-13B with MultiRC at 400 tokens per example, MeZO uses 26GB vs. FT's 316GB across 4 GPUs — a 12.2× ratio. The profiling methodology is clearly described (Section E.7): PyTorch with HuggingFace transformers, no gradient checkpointing or FlashAttention, per-device batch size of 1, nvidia-smi monitoring, and a run considered successful if no OOM for 100 steps. This is a clean comparison at standard settings.

The 2× GPU-hour reduction claim is more conditional. Section F.6 reports that for OPT-30B, MeZO requires 32.8 GPU-hours on 1 GPU vs. FT's 63.3 GPU-hours on 8 GPUs — roughly half. However:

• This comparison depends on the specific implementation and hardware. The paper acknowledges this dependency: "The wall-clock benefit of MeZO is not inherent to the algorithm and is highly dependent on the implementation."
• FT's GPU hours are inflated by multi-GPU communication overhead (FSDP). A more optimized FT implementation (using model parallelism, better communication scheduling, or mixed precision) could reduce the FT wall-clock time.
• MeZO's per-step speed advantage (7.74×) shrinks as model size decreases (Table 23 shows 1.74× for OPT-1.3B, 1.68× for OPT-2.7B, and 5.05× for OPT-13B). For smaller models where FT fits on fewer GPUs with less communication overhead, the wall-clock advantage diminishes or reverses.
• The paper states the 2× figure for OPT-30B specifically, not as a universal claim. The abstract says "up to 2× GPU-hour reduction," which is technically accurate — it's an upper bound observed at the largest tested scale.

Missing Experiments and Baselines

Several experiments would have meaningfully strengthened the paper's claims:

• Direct effective rank measurement. Running a Hessian spectrum analysis (even on a smaller model like RoBERTa-base) to directly quantify r for prompted vs. unprompted fine-tuning would transform the theory from plausible to verified.

• Comparison with gradient checkpointing. Gradient checkpointing (Chen et al., 2016) trades compute for memory in backpropagation, achieving O(√n) memory at ~1.5× compute cost. How does MeZO compare against FT with aggressive gradient checkpointing? If checkpointing can fit OPT-13B FT on 2 A100s instead of 4, the memory advantage of MeZO narrows.

• Comparison with 8-bit optimizers and quantization. Dettmers et al. (2022a, b) showed that 8-bit Adam and 8-bit quantization can substantially reduce memory. How does MeZO's memory footprint compare to FT with 8-bit Adam? The paper mentions this as future work but does not test it.

• Task-level diagnostics for when MeZO fails. On CB (16-point gap to FT), BoolQ, WiC, and MultiRC, MeZO substantially underperforms FT. What characterizes these tasks? Are they harder (lower zero-shot performance)? Do they have higher effective rank? Larger gradient variance? A systematic analysis would provide practical guidance for when to use MeZO.

• Larger-scale non-differentiable optimization. The RLHF motivation is prominent in the introduction, but no experiment even approximates this setting (e.g., using a synthetic reward model or preference dataset). This is a significant gap between the paper's motivating narrative and the experimental evidence.

• Comparison against forward-mode auto-differentiation (Appendix D). The paper profiles forward auto-differentiation's memory and finds it to be 2.5× inference (Table 12), placing it between MeZO (1×) and backpropagation (74× for this measurement). However, no accuracy comparison is provided — does forward-mode AD achieve FT-level accuracy with 2.5× memory? If so, it might be a better operating point than MeZO's 1× memory with 100× more steps.

• Standard deviation for OPT results. The OPT experiments are single-run, making it impossible to assess whether the small gaps between MeZO and FT (e.g., 91.4% vs. 92.0% on SST-2) are statistically significant. Given the random seed sensitivity of fine-tuning, reporting variance would contextualize claims of "comparable" performance.

Overall Assessment

The experimental program is comprehensive along the breadth dimension (three model families, multiple scales up to 66B, 11+ tasks spanning three task types, multiple MeZO variants) but thinner along the depth dimension for specific analyses (single-run OPT results, preliminary non-differentiable experiments, no direct effective rank measurement). The core empirical claims — that MeZO achieves inference-level memory, substantially outperforms zero-shot/ICL/LP, and approaches FT on many tasks — are well-supported. The theoretical narrative is coherent and consistent with the empirical observations but relies on indirect evidence for its central mechanism (low effective rank). The most significant gaps are the missing baselines (gradient checkpointing, quantization, forward-mode AD), the lack of error bars on OPT results, and the thin coverage of non-differentiable optimization despite its prominence in the paper's motivation.

6. Limitations and Trade-offs

The Difficulty of In-Context Learning Demonstrations

The constraint. In-context learning (ICL) performance heavily depends on the selection, formatting, and ordering of demonstrations — a well-documented sensitivity acknowledged in prior work that this paper cites (Liu et al., 2022; Lu et al., 2022). The paper's own ICL baseline uses 32 demonstrations across all experiments, noting that "filling in as many examples as possible in the context... does not improve performance and sometimes leads to unstable results" (Appendix E.4). The choice of 32 demonstrations is practical but arbitrary, and the paper does not systematically evaluate whether MeZO's advantage over ICL holds when ICL demonstrations are carefully curated rather than randomly sampled.

The consequence. A practitioner comparing MeZO against ICL may reach different conclusions depending on how much effort they invest in prompt engineering for ICL. Recent work (not cited in this paper) has shown that retrieval-augmented ICL — selecting demonstrations that are semantically similar to the test example — can substantially outperform random demonstration selection. If retrieval-based ICL closes or reverses the performance gap on the tasks where MeZO currently leads, the practical motivation for MeZO's forward-pass training overhead weakens significantly. The paper's ICL comparison is therefore not against the strongest possible ICL baseline, but against a reasonable default configuration.

What evidence exists. Table 1 shows MeZO outperforming ICL on 10 of 11 OPT-13B tasks, often by substantial margins (SQuAD: 84.7% vs. 75.9%; COPA: 88.0% vs. 87.0%; BoolQ: 67.6%–73.8% vs. 66.9%). Table 18 shows MeZO k = 16 improving over zero-shot by ~25 points on average on RoBERTa-large. However, the paper never evaluates ICL with demonstration retrieval, demonstration ordering optimization, or instruction tuning — all techniques known to improve ICL performance. The sensitivity of ICL to these factors is acknowledged (Section 1) but not controlled for experimentally.

Mitigation status. The paper does not attempt to optimize the ICL baseline, treat demonstration selection as a hyperparameter, or report variance across different random demonstration sets. The authors frame MeZO as complementary to ICL ("MeZO consistently outperforms zero-shot, ICL, and linear probing," Section 3.2), not as a replacement. The limitation is in the strength of the evidence for the "MeZO > ICL" claim, not in the viability of MeZO itself.

---

No Combination of MeZO with Other Memory-Saving Techniques

The constraint. The paper evaluates MeZO in isolation against standard backpropagation with Adam, without combining it with other memory-efficient methods that could reduce backpropagation's memory footprint. Gradient checkpointing (Chen et al., 2016), FlashAttention (Dao et al., 2022), and quantization (Dettmers et al., 2022a, b) are all mentioned in Section 3.4 and Section 5 (Related Work) as complementary techniques, but none are tested alongside MeZO. The paper acknowledges: "We leave investigating how MeZO works with these methods to future work" (Section 3.4).

The consequence. The 12× memory reduction claim compares MeZO against naive backpropagation with Adam, not against a memory-optimized backpropagation pipeline. A practitioner using gradient checkpointing with 2 segments (which reduces activation memory by approximately half at ~20% compute overhead) plus FlashAttention (which reduces attention memory from O(n²) to O(n)) plus 8-bit Adam (which reduces optimizer state by 4×) could potentially fit substantially larger models with FT than the paper's Figure 4 suggests. The paper does not measure where MeZO sits on the Pareto frontier relative to such an optimized backpropagation pipeline. If aggressive memory optimization closes the gap — say, allowing FT of a 6.7B model on a single A100 instead of the 2.7B the paper reports — the practical memory advantage of MeZO narrows from "enables training 11× larger models" to something more modest.

What evidence exists. The memory profiling in Figure 3 and Table 22 explicitly states that no memory-saving options were used: "We did not turn on any advance memory-saving options, e.g., gradient checkpointing" (Appendix E.7). The per-device batch size is set to 1, and FSDP is used for multi-GPU backpropagation. The profiling is transparent about what it measures, but it measures a baseline that many practitioners would consider suboptimal.

Mitigation status. The paper is forthcoming about this exclusion and frames it as future work. The authors note that "the above analyses also do not consider recent advances" (Section 3.4). The limitation is in the generalizability of the 12× figure — it applies specifically to unoptimized backpropagation and may overstate MeZO's advantage relative to a well-engineered training pipeline.

---

The Hardest Problems Remain Unsolved — MeZO Cannot Compensate for Fundamental Capability Gaps

The constraint. MeZO estimates gradients from loss differences and can only optimize within the basin of the pretrained model's existing capabilities. If the base model cannot produce correct outputs for a task even at low probability, no amount of ZO optimization will help — the gradient signal from SPSA requires that perturbing parameters can change the loss in a way that correlates with correctness. This is the analog of the "difficulty bin 5" finding in the test-time compute paper, and it manifests in this work through tasks where MeZO trails FT by large margins or fails to improve over zero-shot.

The consequence. MeZO is fundamentally an amplifier of existing model capability, not a creator of new capability. For tasks that require knowledge or reasoning patterns absent from the pretraining distribution, MeZO will fail regardless of step count, just as backpropagation-based fine-tuning would fail — but backpropagation at least provides exact gradient information that might navigate the model toward distant minima, whereas MeZO's noisy gradient estimates are less able to escape poor initial regions. A practitioner evaluating MeZO needs to know whether their target task falls in the "MeZO works well" or "MeZO adds little" regime.

What evidence exists. The worst-case tasks in the OPT-13B experiments illustrate this boundary:

• CB (CommitmentBank): MeZO achieves 67.9%, MeZO (prefix) 69.6%, while FT reaches 83.9% — a 14–16 point gap (Table 1). The zero-shot baseline is 46.4%, so both MeZO and FT improve substantially, but FT does so far more effectively. The paper does not diagnose why CB is harder for MeZO — possibly higher effective rank, or the task requiring more precise gradient information.
• WiC (Word-in-Context): MeZO 61.1% vs. FT 70.1% (9-point gap). Zero-shot is 55.0%, so the absolute improvement from MeZO (6.1 points) is modest compared to FT's 15.1 points.
• MultiRC: MeZO (prefix) 63.7% vs. FT 71.1% (7.4-point gap). Zero-shot is 46.9%.
• On DROP, all methods struggle: zero-shot 14.6%, MeZO 30.9%, FT 31.3%. The base model's capability ceiling on this complex reasoning task is low, and MeZO does not break through it — but neither does FT.

The RoBERTa-large results (Table 18) show a related pattern: on the hardest tasks (MNLI, SNLI), the gap between MeZO and FT is larger (6–9 points in k = 16) than on easier tasks like SST-2 (1.4 points). This suggests a difficulty-dependent scaling where MeZO's efficiency degrades as task complexity increases.

Mitigation status. The paper does not explicitly characterize which tasks cause MeZO to underperform or propose diagnostic metrics for predicting MeZO's effectiveness on a new task (e.g., zero-shot accuracy, effective rank estimates, or gradient variance measurements). The theoretical framework (Section 4) implies that tasks with higher effective rank will be harder for MeZO, but no task-level effective rank measurements are provided. A practitioner currently has no principled way to decide ex ante whether MeZO will work for their task without running the experiment.

---

Prompts Are Essential but Not Systematically Studied

The constraint. The paper's most striking ablation (Appendix A.1, Table 5) shows that MeZO collapses without prompts: on SST-2, accuracy drops from 89.6% to 51.9%; on SNLI, from 65.1% to 34.8%; on TREC, from 66.7% to 19.5% (near random for a 6-way task). The theoretical framework (Section 4) connects this to the low-effective-rank assumption — prompts keep the fine-tuning objective "close" to pretraining, preserving the benign Hessian structure. Yet the paper conducts no systematic study of which prompt properties matter, how sensitive MeZO is to prompt quality, or whether some tasks resist prompting in ways that would make MeZO unusable.

The consequence. A practitioner adopting MeZO must use prompts, but the paper provides only the specific prompt templates used (Tables 13, 14) without guidance on prompt design for new tasks. If a task does not admit a natural prompt template, or if the best prompt for accuracy is not the best prompt for maintaining low effective rank (and thus ZO efficiency), the practitioner faces an uncharacterized risk. The paper's results may not transfer to tasks where prompt engineering is difficult — e.g., structured prediction, long-form generation, or tasks requiring complex output formats beyond simple classification or answer extraction.

What evidence exists. The prompt ablation (Table 5) is conducted on only three tasks (SST-2, SNLI, TREC) with a single prompt template per task. There is no comparison of multiple prompt templates per task, no measurement of how MeZO's convergence rate varies with prompt quality, and no test of whether "better" prompts (in terms of zero-shot accuracy) correlate with "better" prompts for MeZO optimization. The paper uses prompts from prior work (Gao et al., 2021 for RoBERTa; GPT-3 and PromptSource for OPT) without evaluating alternatives. The theoretical claim that prompts ensure low effective rank is supported only indirectly — the prompt-on vs. prompt-off performance gap is consistent with the theory but does not isolate effective rank as the mechanism.

Mitigation status. The paper acknowledges the importance of prompts in the theoretical narrative and the ablation, but does not treat prompt design as a tunable hyperparameter or characterize its sensitivity. The task-level prompt templates are documented (Appendix E.2) for reproducibility, but no design principles are extracted. A practitioner with a novel task is left to guess whether their prompt will enable MeZO to work, and at what level of performance.

---

Sequential Dependency Creates a Latency Bottleneck Not Captured by GPU-Hour Metrics

The constraint. Each MeZO training step requires sequential operations: (1) perturb positively → forward pass → compute ℓ+, (2) perturb negatively → forward pass → compute ℓ-, (3) reset parameters → update weights. These cannot be parallelized across GPUs in the way that data-parallel backpropagation scales, because SPSA computes a single scalar projected_grad from the loss difference, and that scalar is needed to update all parameters before the next perturbation. While MeZO can use multiple GPUs for the forward pass itself (via model parallelism for inference), the training loop is inherently sequential per step. The paper's wall-clock analysis (Section F.6) reports per-step speed but does not analyze latency scaling with additional hardware.

The consequence. The GPU-hour comparison in Section F.6 (MeZO: 32.8 GPU-hours on 1 GPU; FT: 63.3 GPU-hours on 8 GPUs) masks a critical latency difference: MeZO's 32.8 GPU-hours are serial — they take ~33 hours on 1 GPU — while FT's 63.3 GPU-hours are parallel across 8 GPUs and take only ~8 hours of wall-clock time. A practitioner with access to 8 GPUs, concerned about experiment turnaround time, would face a 4× wall-clock penalty with MeZO despite the 2× GPU-hour advantage. This matters for iterative model development, hyperparameter tuning, and any workflow where time-to-result is the bottleneck rather than total compute cost.

The sequential nature also means that MeZO cannot benefit from scaling to more GPUs to reduce training time — the per-step latency is bounded by the forward pass time on whatever hardware configuration is used. Backpropagation with data parallelism, by contrast, can process larger effective batch sizes by distributing across more GPUs, reducing the number of steps and thus the wall-clock time. MeZO's batch size is limited by what fits in a single forward pass on the available GPUs.

What evidence exists. Table 23 reports per-step times: MeZO on OPT-30B takes 5.896 seconds per step on 1 GPU; FT takes 45.608 seconds per step on 8 GPUs (5.7 seconds per GPU-step equivalent). The total step counts differ by 32× (20K MeZO steps vs. 625 FT steps). The wall-clock time is 20,000 × 5.896 ≈ 32.8 hours for MeZO vs. 625 × 45.608 / 3600 ≈ 7.9 hours for FT (since the 8 GPUs operate in parallel). The paper explicitly frames this as a GPU-hour comparison ("MeZO only requires half as many GPU-hours") but the wall-clock implications are not discussed.

Mitigation status. The paper acknowledges that MeZO "takes more steps to converge" as a limitation (Section 6) and that "the wall-clock benefit of MeZO is not inherent to the algorithm and is highly dependent on the implementation" (Section F.6). The latency tradeoff is implicit in these statements but never quantified as a wall-clock comparison. The paper frames MeZO primarily as a memory-efficiency innovation, and the GPU-hour metric aligns with that framing (memory-constrained users care about total compute, not just wall-clock time). However, for practitioners with access to multiple GPUs who are not memory-constrained, the latency penalty may dominate the decision.

---

The ε → 0 Theoretical Limit Differs from Practical ε, and Higher-Order Effects Are Unexplained

The constraint. The SPSA gradient estimator (Definition 1) is unbiased for the true gradient only in the limit ε → 0, where it becomes zzᵀ∇ℒ(θ) — a rank-1 reconstruction of the gradient. For non-zero ε, the estimator includes higher-order terms from the Taylor expansion of ℒ(θ ± εz):

$\hat{\nabla}\mathcal{L} = \mathbf{z}\mathbf{z}^\top \nabla\mathcal{L} + \frac{\epsilon^2}{6} \mathbf{z} (\mathbf{z}^\top \nabla^3\mathcal{L} \mathbf{z}) + \mathcal{O}(\epsilon^4)$

These higher-order terms are not merely noise — they can systematically bias the gradient estimate in directions that depend on the third and higher derivatives of the loss. The paper's theory (Section 4) treats the ε → 0 limit, deriving convergence rates based on the rank-1 reconstruction property. But the experiments use finite ε values: ε = 10⁻³ for full-parameter MeZO, ε = 10⁻¹ for MeZO (prefix), ε = 10⁻² for MeZO (LoRA) (Tables 15, 16). These are far from the ε → 0 limit, particularly for prefix-tuning where ε = 0.1 means parameter perturbations of 10% of a standard deviation.

The consequence. The paper cannot distinguish whether MeZO's empirical success comes from (a) the gradient estimation mechanism analyzed in the theory (the zzᵀ∇ℒ term), or (b) beneficial effects of the finite-ε perturbations, such as implicit regularization toward flatter minima (analogous to sharpness-aware minimization) or exploration of the loss landscape that helps escape poor local optima. If (b) is significant, then the theoretical analysis — which is the paper's primary intellectual contribution for explaining why MeZO works — may be incomplete or even misattributing the mechanism.

This matters practically because the optimal ε may depend on model scale, task, and training stage in ways the paper doesn't characterize. The hyperparameter grid (Appendix A) includes only ε ∈ {10⁻³, 10⁻⁵} for the ablation study, and the paper states that "the choice of ε seemed to not significantly impact performance" in that limited test. But 10⁻³ and 10⁻⁵ differ by only 100×, while 10⁻¹ (used for prefix-tuning) differs by 10,000× from 10⁻⁵. The paper does not conduct a systematic sweep of ε across tasks and models, nor does it report how performance varies with ε.

What evidence exists. The theory section (Section 4, Lemmas 2 and 5, Theorem 1) explicitly takes the ε → 0 limit. Lemma 2 states "in the ε → 0 limit, we have \hat{\nabla}\mathcal{L} = \frac{1}{Bn} \sum \mathbf{z}_i \mathbf{z}_i^\top \nabla\mathcal{L}$" (Appendix G proof). The forward auto-differentiation discussion (Appendix D) notes that using ε = 0 via Jacobian-vector products "removes potentially beneficial third-and-higher order Taylor expansion terms from the estimate" — implying the authors recognize finite-ε effects exist but neither quantify nor theoretically analyze them. The memory comparison for forward-mode AD (Table 12) shows that ε = 0 via JVP requires slightly more than 2× inference memory, which is why MeZO uses ε > 0 — but the optimization consequences of this choice are not studied.

Mitigation status. The paper does not attempt to separate the ε-dependent and ε-independent contributions to MeZO's performance. There is no ablation comparing different ε values across the full set of tasks, no experiment using forward-mode AD (which implements ε = 0 exactly) to see if performance degrades, and no theoretical analysis incorporating finite-ε effects. The statement that ε "seemed to not significantly impact performance" (Appendix A) is based on a grid of only two values on three tasks in a limited compute budget (10,000 forward passes) — far from conclusive. A practitioner tuning MeZO for a new task cannot determine whether their ε choice is near-optimal or whether the method's success depends on a particular range of ε that may not generalize.

7. Implications and Future Directions

How This Work Changes the Landscape

This paper does not propose a new pretraining objective, a novel architecture, or a different fine-tuning loss. It changes the field by reframing memory as a constraint that can be algorithmically decoupled from gradient quality, rather than an immutable hardware limitation. Before MeZO, the prevailing memory narrative was: "to fine-tune a model, you must cache activations proportional to network depth, store gradients proportional to parameter count, and maintain optimizer state proportional to parameter count — these are all consequences of backpropagation and cannot be avoided." Gradient checkpointing and PEFT softened this by trading compute or expressivity for memory, but they operated within the backpropagation paradigm — they reduced memory by factors of 2–4×, not 12×, and they never reached the inference-level memory floor that MeZO achieves.

The conceptual shift is this: the memory bottleneck in fine-tuning is not a fact about model size — it is a fact about the choice of gradient estimator. By replacing backpropagation's exact gradient computation with a zeroth-order estimate constructed from forward-pass loss differences and a resampled perturbation vector, MeZO demonstrates that you can exchange gradient precision for memory efficiency at a ratio that classical optimization theory would have declared impossible (12× memory reduction for only ~100× more steps, rather than the d-fold slowdown predicted by prior lower bounds). This decoupling creates a genuinely new point on the memory-accuracy-compute Pareto frontier — one that backpropagation cannot reach because it fundamentally requires storing or recomputing the computational graph.

The paper's theoretical framework converts this from an empirical curiosity into a diagnostic principle: the relevant quantity governing ZO optimization efficiency is not the parameter count d but the local effective rank r of the Hessian (Assumption 1, Theorem 1). This reframing has several cascading consequences for the field:

It reconciles contradictory prior findings about zeroth-order optimization. Classical ZO theory (Nemirovskij and Yudin, 1983; Duchi et al., 2015) predicted catastrophic slowness scaling with d. Prior empirical ZO work in deep learning consequently restricted itself to low-dimensional subspaces — BBT and BBTv2 (Sun et al., 2022b, a) optimized only projected prefixes, adversarial example generation (Chen et al., 2017) perturbed inputs rather than parameters, and black-box prompt tuning (Diao et al., 2022) tuned discrete tokens. These restrictions were rational responses to the classical lower bounds: if convergence scales with d, optimizing d = 10^9 parameters is hopeless. MeZO's empirical success and accompanying theory show that this pessimism was misplaced specifically for fine-tuning pretrained models with prompts — a setting where the loss landscape has low effective rank. The prior work was not wrong about general ZO optimization; it was answering a different question (worst-case optimization from scratch) than the one that matters for practical LM adaptation (fine-tuning from a strong initialization on a related task). This is analogous to how the test-time compute paper unified conflicting findings about self-correction and search by introducing difficulty as a conditioning variable — here, the conditioning variable is pretraining quality and prompt design, which control effective rank.

It redirects research effort in memory-efficient training. Before MeZO, the dominant approach to reducing fine-tuning memory was to make backpropagation itself cheaper: gradient checkpointing (Chen et al., 2016), reversible layers, activation recomputation, FlashAttention (Dao et al., 2022), quantization of activations and optimizer states (Dettmers et al., 2022a, b). These are all valuable, but they are incremental improvements on a fundamentally memory-intensive algorithm. MeZO suggests an alternative research direction: develop gradient estimators that are natively memory-efficient, trading precision for memory from the ground up rather than patching backpropagation. Forward-mode auto-differentiation (Appendix D) represents an intermediate point on this spectrum (2.5× inference memory, exact gradients), and future work on structured perturbation matrices, learned perturbation distributions, or hybrid estimators that use exact gradients for a subset of layers could populate the Pareto frontier between MeZO's extreme memory efficiency and backpropagation's exact gradients.

It elevates "prompt design" to a first-class optimization concern. The prompt ablation (Appendix A.1, Table 5) is the paper's most consequential single experiment: MeZO drops from 89.6% to 51.9% on SST-2 without prompts. This is not a minor sensitivity — it is evidence that prompts are what make the fine-tuning landscape low-effective-rank, and thus what make ZO optimization viable. This transforms prompts from a convenience for task specification into a necessary condition for the algorithm to work. The implication for practitioners is clear: if you cannot design a prompt that makes your task "look like" pretraining, MeZO will fail. The implication for researchers is that studying the relationship between prompt design and Hessian effective rank is now a directly impactful research question, not an abstract curiosity about loss landscapes.

It opens the door to optimizing objectives that backpropagation cannot touch. Section 3.3 demonstrates that MeZO can directly optimize accuracy and F1 — non-differentiable metrics — by treating the model as a black box and using the SPSA estimator on the metric value itself. This is not just a "nice to have" feature; it represents a fundamentally different capability than backpropagation-based training. The current pipeline for optimizing non-differentiable objectives (RLHF, safety constraints, factual accuracy) requires training a differentiable proxy (a reward model) and then using RL to optimize against it — a complex, multi-stage process with well-documented failure modes (reward hacking, distribution shift, reward model misspecification). MeZO's ability to optimize any scalar objective directly, using only forward passes, promises to collapse this pipeline into a single training loop. The preliminary results (Table 3) are not yet competitive with cross-entropy training, but they demonstrate feasibility and establish a new capability frontier: any objective that can be evaluated can be optimized, without the need for differentiable surrogates.

It changes the economics of model adaptation and serving. The storage efficiency argument (Section 2.1) — a 66B-parameter model's entire fine-tuning trajectory stored in <0.1MB — is not just an implementation detail. It implies that multi-task serving infrastructure, where dozens or hundreds of task-specific model variants must be stored and served, can be dramatically simplified. Instead of storing a full model checkpoint (~132GB at FP16) or even a LoRA adapter (~38MB) per task, a system could store a base model plus a seed file per task and reconstruct fine-tuned variants on demand. This shifts the cost structure of model adaptation from "storage proportional to number of tasks × model size" to "storage proportional to number of tasks × trajectory length × 2 bytes" — a reduction of roughly six orders of magnitude.

---

Follow-Up Research This Work Enables

Cheap and online difficulty estimation for effective rank. The paper's central theoretical claim — that MeZO works because the fine-tuning Hessian has low effective rank r — is supported by indirect evidence (prompt ablation, PEFT convergence similarity, prior Hessian spectrum measurements) but never directly validated. A high-priority follow-up would directly measure the effective rank r for the specific models and tasks used in this paper, and correlate r with MeZO's convergence speed and final performance. This is computationally demanding for 13B+ models (requiring Hessian-vector products or stochastic Lanczos quadrature), but feasible at RoBERTa-large scale. A strong experiment would: (a) compute the Hessian spectrum at initialization and at several points along the MeZO trajectory for prompted vs. unprompted SST-2, SNLI, and TREC; (b) extract the effective rank r = tr(H) / ||H||_op at each point; (c) test whether r predicts the per-step loss decrease (as Theorem 1 would predict), and whether r is substantially smaller with prompts than without. A negative result — finding that r is large even with prompts, or that r does not correlate with optimization speed — would falsify the paper's explanatory framework and redirect attention to alternative mechanisms (e.g., noise-induced regularization, implicit bias of SPSA toward flat minima).

Combining MeZO with selective exact gradient computation. MeZO treats all parameters identically — every weight receives the same SPSA-based update. But deep transformers exhibit heterogeneous gradient structure: attention layers and feedforward layers have different gradient scales, and certain parameters (e.g., the classification head, layer normalization parameters) may benefit more from exact gradient information than others. A natural extension would be a hybrid estimator that uses backpropagation to compute exact gradients for a small subset of parameters (e.g., the final classification head, which is small and has high gradient signal) while using MeZO for the bulk of the model. This would consume additional memory proportional to the exact-gradient parameter subset but could substantially improve convergence speed if the exact gradients provide a stronger signal in critical regions. A well-designed experiment would compare: (a) MeZO with all parameters ZO-updated, (b) MeZO with exact gradients for the classification head (adding ~2× the head's parameter count in memory), (c) MeZO with exact gradients for the last k transformer layers, and (d) full FT baseline — measuring both convergence speed (steps to reach a target accuracy) and final performance. The hypothesis is that a small exact-gradient subset could recover most of the gap to FT while staying well below FT's memory footprint.

MeZO for direct preference optimization and RLHF simplification. The paper motivates non-differentiable optimization as a key capability (Section 1, Section 3.3) but only tests it on accuracy and F1 — metrics with clear ties to the cross-entropy objective that the model was already optimizing. The next step is to apply MeZO to objectives with no relationship to pretraining, specifically human preference scores. A concrete experiment: take a pretrained OPT-13B model, collect pairwise human preference data on a subset of its generations (following the RLHF setup of Ouyang et al., 2022), and use MeZO to directly maximize the preference win rate — a non-differentiable, black-box objective that depends on an external reward model or human judge. Compare against: (a) standard RLHF (reward model training + PPO), (b) direct preference optimization (DPO; Rafailov et al., 2023), and (c) MeZO with cross-entropy on preferred completions. The key metrics are final preference win rate, KL divergence from the base model (to measure reward hacking), and total training compute. A positive result — MeZO matching RLHF/DPO performance while eliminating the reward model and the RL infrastructure — would be transformative for the alignment community. A negative result — MeZO failing because the preference landscape has high effective rank or because SPSA's noise prevents effective credit assignment — would clarify the boundaries of ZO applicability and motivate hybrid approaches.

Prompt design for effective rank minimization. The paper shows that prompts are essential for MeZO but does not study what properties of a prompt matter. Is it semantic similarity to the pretraining distribution? Syntactic simplicity? Length? The number of demonstrations? A systematic study would take a single task (e.g., SST-2) and a family of prompts varying along each of these dimensions, measure both zero-shot accuracy and MeZO's convergence rate (loss decrease per 1,000 steps) for each prompt, and test whether these metrics correlate. More ambitiously, one could train a lightweight "prompt scorer" that predicts, from the prompt text alone, the effective rank of the resulting fine-tuning loss — enabling prompt selection without running MeZO. The paper's theoretical framework implies that the best prompt for zero-shot accuracy may not be the best prompt for low effective rank (and thus ZO efficiency), so the optimal prompt for MeZO-based fine-tuning could differ from the optimal prompt for ICL or zero-shot evaluation. This is a testable hypothesis: compare MeZO performance using the prompt that maximizes zero-shot accuracy vs. the prompt discovered by a grid search over the prompt space for MeZO convergence speed.

MeZO across architectures, modalities, and scales beyond language. The paper tests MeZO on transformer-based masked and autoregressive LMs. The effective-rank argument is not specific to transformers — it should apply to any architecture where pretraining induces low-dimensional structure in the loss landscape. A natural extension is to test MeZO on: (a) vision transformers (ViT) fine-tuned on downstream classification tasks, (b) encoder-decoder models (T5) fine-tuned on sequence-to-sequence tasks, (c) diffusion models fine-tuned on domain-specific image generation, and (d) speech or multimodal models. For each, the key question is whether the pretraining → prompt → fine-tuning pathway preserves low effective rank in the same way. A particularly informative stress test would be MeZO on randomly initialized models — the theory predicts catastrophic failure because the Hessian should have full effective rank at initialization, and confirming this would strengthen the theoretical narrative by showing that the failure mode is exactly what the theory predicts, not an artifact of the specific models or tasks tested.

The ε tradeoff: gradient estimation vs. implicit regularization. The paper uses ε = 10⁻³ for full-parameter MeZO and ε = 10⁻¹ for MeZO (prefix), with the note that "the choice of ε seemed to not significantly impact performance" — but this is based on a grid of only two values on three tasks with limited forward-pass budget. A systematic study of ε's role is needed to distinguish whether MeZO's performance comes primarily from the ε → 0 gradient estimation mechanism (analyzed in the theory) or from finite-ε effects like implicit sharpness regularization. A clean experiment: for a fixed task and model, run MeZO with ε spanning {0, 10⁻⁵, 10⁻⁴, 10⁻³, 10⁻², 10⁻¹} for the same number of steps, and evaluate both final accuracy and the sharpness of the resulting minima (via the largest Hessian eigenvalue). To implement ε = 0, use forward-mode auto-differentiation (Appendix D) to compute the exact zzᵀ∇ℒ gradient estimate without perturbation. If performance is flat across a wide ε range, the ε → 0 theory is sufficient; if performance peaks at intermediate ε and drops at both extremes, finite-ε effects are important and the theoretical framework needs extension. If ε = 0 fails entirely, the entire theoretical basis (which assumes small ε) is called into question, and a new theory incorporating finite-ε terms is required.

---

Practical Applications and Downstream Use Cases

Single-GPU fine-tuning of large models for research labs and startups. The paper's most immediate practical impact is democratizing access to large model adaptation. A researcher with a single 80GB A100 can fine-tune OPT-30B with MeZO (Table 22) — a model that would require 8 A100s for full backpropagation-based fine-tuning. At the time of writing, a single A100 80GB costs approximately $1–2/hour on cloud platforms, while 8 A100s cost$8–16/hour. For a lab that needs to fine-tune models for 10 downstream tasks, the hardware cost difference is roughly 10 × (8 GPUs × 8 hours × $1.50) ≈ $960 for FT vs. `10 × (1 GPU × 33 hours ×$1.50)` ≈ $495 for MeZO — roughly half the cost, but more importantly, feasible on hardware that the lab can actually access (a single GPU is much easier to provision than an 8-GPU cluster). The storage savings compound this: storing 10 fine-tuned 30B checkpoints requires ~600GB for FT, ~380MB for LoRA, or ~0.4MB for MeZO trajectories — negligible enough to version-control alongside code.

Direct metric optimization for production ML systems. Many production ML systems have objectives that are not well-captured by cross-entropy loss: recommendation systems optimize click-through rate or revenue, content moderation systems optimize precision at a fixed recall, question-answering systems optimize F1 or BLEU. Currently, these systems either use a surrogate loss (e.g., cross-entropy, which is misaligned with the true metric) or a complex RL-based optimization pipeline. MeZO's demonstrated ability to directly optimize accuracy and F1 (Table 3) — with results approaching cross-entropy-trained models on some tasks — offers a simpler path: define the metric as the training objective and run MeZO. The preliminary results show gaps (68.6% vs. 94.3% on TREC for accuracy vs. cross-entropy), so this is not yet a drop-in replacement, but the trajectory from feasibility to competitiveness is clear: better variance reduction, adaptive ε schedules, or hybrid objectives that combine cross-entropy with the target metric could close these gaps. A concrete deployment scenario: a customer support chatbot that needs to optimize a composite metric of answer correctness, politeness, and resolution rate. MeZO could directly maximize this composite score (evaluated by a classifier or human-in-the-loop) without requiring differentiable proxies for each component.

Multi-task model serving with on-demand fine-tuning reconstruction. For serving systems that support many downstream tasks — e.g., an API that provides specialized models for legal document analysis, medical coding, and financial sentiment — storing full checkpoints or even LoRA adapters per task imposes significant storage costs. MeZO's trajectory storage (<0.1MB per task for a 66B model) enables a deployment architecture where a single base model checkpoint is stored alongside a small configuration file per task containing the MeZO seed and projected gradients. When a task-specific model is requested, the serving infrastructure replays the MeZO trajectory to reconstruct the fine-tuned parameters on-the-fly. The reconstruction cost (one full fine-tuning run of forward passes) is amortized over the serving lifetime of the model and can be performed during low-traffic periods or on spot instances. The storage reduction is approximately 132GB / 0.1KB ≈ 10^6× per task — enough to store fine-tuning trajectories for millions of tasks on a single disk, enabling personalization at a scale that would be infeasible with any other approach.

Fine-tuning on edge devices with tight memory constraints. A 13B-parameter model quantized to 8 bits requires ~13GB of memory for inference — just barely fitting on a high-end consumer GPU (e.g., RTX 4090 with 24GB). Standard fine-tuning of this model would require an additional ~150GB for activations, gradients, and optimizer state, far exceeding any consumer hardware. MeZO with the same memory as inference means that a quantized 13B model can be fine-tuned on a consumer GPU in the user's home. This has implications for privacy-preserving personalization: a user's on-device model could be fine-tuned on their personal data (emails, documents, messages) without that data ever leaving the device, using MeZO to adapt the model with only forward passes and negligible additional memory. The 33-hour training time for a 30B model (Section F.6) is impractical for interactive use but reasonable for overnight or background fine-tuning. Combined with PEFT for further memory reduction (MeZO + LoRA reduces the parameter count for trajectory storage but not for training memory), this could enable practical on-device adaptation within the next hardware generation.

---

When to Prefer This Method

The paper positions MeZO against three alternatives — full fine-tuning with backpropagation (FT), parameter-efficient fine-tuning (PEFT), and in-context learning (ICL) — and the experimental results support a clear decision framework based on which resource constraint is active:

Prefer MeZO over full FT when: (1) GPU memory is the binding constraint — you have a single GPU with limited memory and cannot provision a multi-GPU cluster (the 12× memory reduction enables training a 30B model where FT can only fit 2.7B on the same hardware; Figure 4); (2) you need to fine-tune for many tasks and checkpoint storage cost dominates — MeZO's <0.1MB per trajectory vs. ~132GB per FT checkpoint translates to a ~10^6× storage reduction; (3) your objective is non-differentiable (e.g., accuracy, F1, human preference scores) and you want to optimize it directly without training a differentiable proxy or setting up an RL pipeline; (4) wall-clock time is not the primary constraint and you can tolerate ~100× more training steps (33 hours on 1 GPU for a 30B model vs. ~8 hours on 8 GPUs for FT).

Prefer full FT or PEFT with backpropagation over MeZO when: (1) you have access to sufficient GPU memory (e.g., 4–8 A100s for a 13B model) and the primary constraint is developer iteration speed — FT converges in ~1/100 the number of steps, meaning faster experiment cycles; (2) the task does not admit a natural prompt that makes the objective "look like" pretraining — MeZO collapses without prompts (Table 5), and tasks requiring complex output formats or lacking clear prompt templates may not be amenable; (3) you need maximal final accuracy and a 1–5 percentage point gap to FT is unacceptable — on tasks like CB, MeZO trails FT by 14–16 points (Table 1), and on MNLI/SNLI the gap is 5–9 points (Table 18); (4) you are fine-tuning a small model (<1B parameters) where FT already fits in memory — the memory advantage is irrelevant, and the per-step speed advantage of MeZO shrinks as model size decreases (Table 23 shows only 1.7× per-step speedup for OPT-1.3B).

Prefer MeZO over ICL when: (1) you have more than a few dozen labeled examples and want to extract signal from them — ICL is limited by context length and performs worse than fine-tuning as training data increases (Table 1: MeZO 84.7% vs. ICL 75.9% on SQuAD with 1,000 examples); (2) performance consistency matters — ICL is sensitive to demonstration selection and ordering, while MeZO provides deterministic improvement from training data; (3) you need to adapt the model's internal representations, not just its input-output mapping — ICL conditions on demonstrations at the input level and cannot change the model's weights to acquire new capabilities, while MeZO updates all parameters.

Prefer ICL over MeZO when: (1) you have zero or very few training examples and cannot afford any training compute — ICL provides immediate adaptation with a single forward pass; (2) you need to adapt to a novel task with no training data at all — MeZO's effective rank argument relies on the task being "close" to pretraining via a prompt, and a genuinely out-of-distribution task may not satisfy this; (3) training latency is unacceptable — ICL produces results in milliseconds, while MeZO requires hours of training.