Backpropagation (BP) dominates deep learning but imposes a massive memory tax. For example, training OPT-30B with Adam requires ≈ 600GB of GPU memory (assuming batch size 8 and sequence length 2048). Alternatively, zero-order optimization (ZOO) trains in inference-mode (requiring only ≈ 60GB for the same model): no stored activations, no gradients, and no optimizer states. However, ZOO convergence has lagged behind BP. In this work, we evaluate two methods to close this gap. First, we show that reallocating training compute budget from many steps to large effective batch sizes with many perturbations (or probes) but fewer steps, allows 1SPSA (Spall, 1992) to outperform zero order methods like MeZO (Malladi et al., 2023) with less training compute. Next, we introduce 1.5-SPSA, adding a single "clean" forward-pass per step to 1SPSA to calculate a cheap diagonal preconditioner in probe-space, which improves convergence rate and convergence by down-weighting high curvature directions. Benchmarking on 6 post-training datasets on both Qwen3 and OPT model families, we show that 1.5-SPSA achieves State-of-the-Art results over previous ZOO solvers with much less optimization steps. For example, we train OPT-13B (for direct comparison to MeZO) and find 1.5-SPSA achieves +3.1% accuracy on SST-2 over both MeZO and BP in only 70 steps vs. MeZO's 100,000 steps. Finally, we combine an 8-bit-packing random generator, triton fused unpack/apply kernels, and distributed parallelism to achieve fast and stable training of models as large as OPT-30B in-place on commodity GPUs (e.g. A100).
Figures & tables
Figure 1: Overview of 1.5-SPSA. (A) Inference-mode training avoids optimizer state and stored activations, reducing memory relative to BP+Adam. (B) forward-passes are reallocated from many optimization steps to large (parallelizable) batch size × perturbations per step for 44× less training compute to achieve SOTA test accuracy via a ZOO method (on SST-2). (C) Directional curvature estimates c^i set weights wi=∣ci^∣α=0.1 : high-curvature directions cause instability so steps are down-weighted, while flat regions yield wi≈1 , which improves stability, convergence rate, and test accuracy with inference-mode memory use.
Figure 2: Comparison of 1SPSA (top) and 1.5-SPSA (bottom) for OPT-13B sweeping over npert and batch size per optimization step. Each cell reports: test accuracy on SST-2 (top), optimization steps to convergence (middle), forward-passes to convergence (bottom). Convergence is defined to be when validation loss has plateaued. All configurations are compared at equal total forward-pass budgets (500,000 forward-passes), although convergence may happen before the final optimization step. We find more batch size and perturbations per step seems to increase convergence rate, but only improves final convergence value up to a point of diminishing returns. We also find that 1.5-SPSA outperforms 1SPSA in both final convergence and convergence rate.
Method
SST-2
RTE
BoolQ
WSC
WiC
Zero-shot
58.8
59.6
59.0
38.5
55.0
ICL
87.0
62.1
66.9
39.4
50.5
LP
93.4
68.6
59.3
63.5
60.2
MeZO ( Malladi et al., 2023 )
91.4
66.1
67.6
63.5
61.1
MeZO (LoRA)
89.6
67.9
73.8
64.4
59.7
MeZO (prefix)
90.7
70.8
73.1
60.6
59.9
Table 1: OPT-13B post-training accuracy results on common GLUE/SuperGLUE tasks. Rows above the midrule are baselines. All 1SPSA and 1.5-SPSA were trained with less than 300 optimization steps. 1.5-SPSA has superior performance.
Method
SST-2
RTE
BoolQ
WSC
WiC
MeZO / Prefix
90.6
72.6
73.5
63.5
59.1
1SPSA
94.0
69.0
73.0
67.5
59.9
1.5-SPSA
94.5
77.0
74.0
67.5
59.3
Table 2: OPT-30B post-training accuracy results on common GLUE/SuperGLUE tasks. All 1SPSA and 1.5-SPSA were trained with less than 300 optimization steps. 1.5-SPSA proves superior performance.
Method
SST-2
RTE
BoolQ
WSC
WiC
1SPSA
94.5
88.5
85.7
75.0
64.6
1.5-SPSA
94.7
88.0
86.1
80.8
71.2
Table 3: Qwen3-8B post-training accuracy results on common GLUE/SuperGLUE tasks. All 1SPSA and 1.5-SPSA were trained with less than 300 optimization steps. 1.5-SPSA proves superior performance.
Method
lr=1e-3
lr=5e-4
lr=1e-4
lr=5e-5
lr=1e-5
lr=5e-6
BP+Adam
72.0 (70)
70.2 (80)
77.0 (285)
77.0 (284)
70.2 (279)
65.3 (275)
1SPSA
diverge
diverge
78.6 (38)
78.5 (38)
77.2 (44)
77.2 (45)
1.5-SPSA
77.0 (24)
79.0 (24)
78.0 (37)
77.6 (37)
77.1 (39)
77.0 (44)
Table 4: Qwen3-1.7B post-training accuracy results on Stable ToolBench to teach tool-use. Format: Test Acc (on top), optimization steps to converge (on bottom). All 1SPSA and 1.5-SPSA were trained with less than 300 optimization steps. We show 1.5-SPSA outperforms 1SPSA and BP with Adam on Qwen3. Additionally, we show that 1.5-SPSA permits larger learning rates which improves convergence rate.
Figure 3: Comparing convergence rates on a stiff paraboloid x⊤R⊤diag(k,1,…,1)Rx at varying condition numbers ( κ=k/1 ). 10 seeds per κ×solver . Random R and perturbations to compare 1SPSA vs. 1.5-SPSA convergence rates. As κ grows, 1.5-SPSA converges faster (up to 7 × on average).
Figure 4: DNC overfitting stress test: steps to reach a near-zero loss for 7 different model sizes up to 1B. 1.5-SPSA reduces steps over 1SPSA at the same perturbation count. More perturbation count improves convergence rate. Larger models converge faster. BPTT cannot run the 1.1B model in this setup due to GPU memory limits.
Appendix figures & tables11 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5: We perturb Qwen3-8B in random directions and plot the 1-D loss landscape at 40-points (SST-2, batch size = 256). The resulting “spaghetti plot” shows an indefinite and ill-conditioned Hessian : local curvature ranges from sharply negative to sharply positive (up to 108 ).
Figure 6: Histogram of 3-point curvature of Qwen3-8B loss landscape against SST-2. We see values ranging from −408 to 308 proving the post-training loss is ill-conditioned. We use batch size = 128, sequence length = 256, and ϵ=10−4 for eight thousand random perturbation directions.
Figure 7: Box plot showing the distribution of gradient estimates for different batch size. We measure the finite difference gradient estimate using a Qwen3-8B model on the SST-2 sentiment classification task. A single Rademacher perturbation vector z∈{−1,+1}d is sampled once (seed =0 ) and held fixed across all measurements. For each batch size B∈{2,4,8,16,32,64,128,256} , we sample n=200 independent batches Bj from the training set and compute g^(Bj) using ϵ=10−4 . The same perturbation z and perturbed models θ±ϵz are used for every batch; only the data batch varies.
Figure 8: Empirical variance follows the expected O(1/B) decay (red dashed line), consistent with the central limit theorem applied to mini-batch loss averaging. The green dashed line indicates the SNR =1 threshold where the gradient signal magnitude equals the noise standard deviation.
Figure 9: Variance reduction in finite difference gradient estimates as a function of the number of perturbations. We load Qwen3-8B and fix a single batch B of size 128 from SST-2. We generate 1000 independent Rademacher perturbations {zi}i=11000 and compute our gradient estimate with ϵ=10−4 . The same batch B is used for all 2000 loss evaluations, isolating perturbation variance from batch variance. For each npert∈{2,4,8,16,32,64,128,256,512} , we bootstrap 1000 times by sampling n perturbations without replacement. Variance decreases as O(1/npert) .
Figure 10: Empirical variance of the averaged finite difference estimator gˉn as a function of npert . Same experimental setup as Figure 9 . Blue circles show empirical variance from 1000 bootstrap samples at each npert . Red dashed line shows the theoretical O(1/npert) decay. Green dashed line marks Var(gˉnpert)=gˉ2≈252 , the SNR =1 threshold where standard deviation equals signal magnitude. The estimator crosses into the SNR >1 regime around npert≈256 . Deviation from 1/npert at large npert is due to finite population effects (sampling 512 of 1000 total perturbations without replacement).
Figure 11: Comparing convergence rates for our ”stiff” paraboloid with a κ=100 . 1.5-SPSA converges in just 6 steps while 1SPSA takes ∼ 2000 steps.
Figure 12: DNC overfitting stress test: compute (measured as forward-passes or equivalent) to reach a near-zero loss threshold vs model size. We convert steps to forward-passes as follows: 1SPSA uses 2npert forward-passes per step, 1.5-SPSA uses (2npert+1) forward-passes per step, and BPTT is approximated as 3 forward-pass equivalents per step (forward + backward). BPTT cannot run the 1.1B model in this setup due to GPU memory limits.
Table 6: Epsilon Ablation Results ( lr=10−4 for all runs). Best performance at ϵ=10−4 . The range 10−5>ϵ>10−3 converge well, outside this range they fail. Intuitively, this makes sense as we are measuring where we are stepping to vs. measuring farther or earlier than we are stepping to.
Method
Probe gen
96 perts
Step
Speedup
Speedup
(ms/pert)
(s)
(s)
(probe gen)
(step)
triton_bitpacked
102.1
9.8
21.7
4.9 ×
2.76 ×
pytorch_flat
246.6
23.7
35.6
2.0 ×
1.68 ×
pytorch
499.5
48.0
59.9
1.0 ×
1.00 ×
Appendix
Table 7: Perturbation generation comparison. “Speedup (probe gen)” is computed from ms/pert relative to naive pytorch implementation. “Speedup (total)” is computed from end-to-end total time relative to original, per parameter pytorch implementation. Analysis done in series on a single A100 to isolate the impact of just the triton kernel.
Zeroth-order optimization uses function values or comparisons, rather than gradients, to optimize objectives when differentiation is unavailable or costly.
Zeroth-order (ZO) optimization offers a memory-efficient alternative to backpropagation for fine-tuning large language models. However, existing ZO methods typically sample training examples uniformly, overlooking their evolving importance and leaving avoidable estimation variance. To address this limitation, we propose Sample-Adaptive Zeroth-Order Optimization (SAZO), which learns sample importance online and adaptively allocates queries to accelerate convergence. SAZO extracts gradient-norm information from existing directional differences to estimate sample importance without access to true gradients. Furthermore, to track evolving importance from sparse minibatch feedback, SAZO maintains per-example exponential moving averages that aggregate observations across updates. The method requires no additional model evaluations and only O(N) additional scalar state compared with MeZO. We prove that SAZO asymptotically matches the leading convergence term of the minimum-variance sampling oracle, and achieves a strictly faster convergence rate than standard methods. Extensive experiments across four model families demonstrate improved average downstream performance and up to 6× faster convergence to the same training loss in terms of query count.
Haiyuan Wan, Yanyi Li, Weicheng Lin +1
School of Physics, Peking University · School of Intelligence Science and Technology, Peking University
Zeroth-order (ZO) optimization with SGD in random subspaces enables memory-efficient fine-tuning of large language models without backpropagation. However, high gradient estimation noise fundamentally undermines adaptive optimizers like Adam. We propose SubZero+, which achieves practical adaptive ZO optimization through a carefully designed dual low-dimensionality strategy: (i) multi-query forward-difference gradient estimation in periodically refreshed random subspaces to mitigate noise amplification in moment buffers, and (ii) Adam updates with periodic restarts performed directly in low-dimensional space rather than full-parameter space. In experiments, this dual design retains memory overhead comparable to momentum-free ZO methods while achieving stronger optimization performance than the evaluated ZO baselines. Theoretically, in the exact-directional limit, K-query averaging preserves conditional unbiasedness, while the coefficient estimator's covariance and mean-squared error, as well as query-induced second-moment inflation, scale exactly as 1/K. Extensive experiments across SuperGLUE with models from 1.3B to 32B parameters under both full fine-tuning and LoRA schemes demonstrate consistent improvements over competing ZO methods. SubZero+ significantly narrows the performance gap with first-order optimization while preserving ZO's inference-time memory efficiency.
Ziming Yu, Shuyao Xiao, Xingyu Zhao +6
Beijing Normal University · Singapore Management University · Xiaomi Inc. +2
Zeroth-order (ZO) optimization has become increasingly popular and important in fine-tuning large language models (LLMs), especially on edge devices due to its ability to adjust the model to local data without the need for memory-intensive back-propagation. Recent works try to reduce ZO variance through low-dimensional subspace search, but subspace restriction alone leaves key optimization geometry under-exploited, motivating additional acceleration. In this work, we focus on the hidden layer training problem in which spectral optimizers like Muon outperform AdamW due to its ability to exploit weak spectral directions by orthogonalization. However, we have discovered that unlike in the first-order setting, full orthogonalization works poorly in the ZO setting since the gradient estimates are highly noisy and unreliable. To address this issue, we propose applying partial spectral orthogonalization to accelerate ZO optimization. To do so, we replace the iconic Newton-Schulz procedure in Muon with the faster, more concentrated power-iteration method so that it only amplifies dominant spectral directions. Furthermore, to improve the efficiency and generalization of the algorithm, we adopted a streaming variant of power-iteration that requires low variance in gradients, which was achieved through constraining our search inside a subspace obtained through the projection of momentum, echoing recent advances. Experiments on LLM fine-tuning show that our method can achieve from 1.5x to 4x the convergence speed of ZO-Muon, the current SOTA algorithm, across SuperGlue datasets in the OPT-13B model. Across different models, we also reach competitive final accuracies with less time in most cases compared with strong ZO baselines such as MeZO, LOZO and ZO-Muon. Code is available at https://github.com/MOFA-LAB/ZO-MOPI.git.
Jiahe Chen, Ziye Ma
Department of Computer Science City University of Hong Kong