Trust the Direction, Search the Step: Zero-and-First-Order Methods for LLM Fine-Tuning

1 Introduction

• ZFO treats zeroth-order evaluations as a way to choose step size, not to replace gradients; its fixed-budget local-model framing extends beyond a single step rule.The authors note that the framework can apply when an approximate gradient direction is available but its appropriate magnitude is uncertain.Source: §1 · pp. 2–3
• Learning-rate schedules and tuning set the step length, which can be sensitive: tiny steps may underuse batch information, while aggressive steps can destabilize training.The paper identifies this scalar choice as distinct from the optimizer’s direction decision.Source: §1 · p. 3
• ZFO leaves the optimizer’s direction unchanged and uses a small number of function evaluations to choose an improved step length along that direction.The framework develops four Taylor- and Padé-based instances; GeN is interpretable as one fixed-budget directional step-selection rule.Source: §1 · p. 3
• The analysis establishes high-probability concentration of shared-sample curvature estimates, near-optimal model steps within a bounded region, and convergence to a stationary neighborhood.The neighborhood size is controlled by accumulated step-selection error.Source: §1 · p. 4
• ZFO is robust to initial learning-rate choice and matches or outperforms standard first- and zeroth-order baselines on most benchmarks.The authors report that this lightweight adaptation can improve stability and reliability without full line search or extensive hyperparameter tuning.Source: §1 · p. 4

2 Methodology

• The current forward and backward passes provide the objective value and directional derivative; two symmetric fixed-batch probes provide curvature information.The same probes, together with the available first-order derivative, support estimates used by both Taylor and Padé models.Source: §2 · p. 4
• ZFO constructs second- or third-order Taylor models and rational Padé models from the directional information to approximate the objective locally.For the quadratic Taylor model, candidate maximizers are the interval endpoints and any feasible stationary point.Source: §2 · p. 4
• If a Padé model has a pole inside the search interval or ill-defined coefficients, ZFO rejects it and falls back to the quadratic Taylor step.The framework also computes the direction with the base optimizer and updates parameters using the selected step along that direction.Source: §2 · pp. 4–5
• Each variant selects a model from T2, T3, P2, and P3, then maximizes it over the shared feasible interval to obtain the scalar step.The variants use the same direction, surrogate, and interval; they differ in how the two probes determine step length.Source: §2 · pp. 4–5
• ZFO’s contribution is a fixed-query local-model framework with Taylor and Padé instances and unified analysis, rather than a new individual step-size formula.GeN fits the abstraction as a specific quadratic instance; ZFO’s two probes, with the available derivative, support second- and third-order directional information.Source: §2 · pp. 4–5

3.1 Local Convergence Analysis

• The concentration theorem is a fixed-direction result: CRN alone does not establish the independence needed when the algorithm also computes its direction from the reused batch.The local approximation guarantee is pathwise once the batch and direction are fixed.Source: §3.1 · pp. 5–6
• With shared-batch evaluations, finite-difference curvature estimates concentrate around population counterparts, with sampling error decreasing at the 1/√n rate.The bounds combine deterministic finite-difference bias, controlled by perturbation scale and higher-order derivative bounds, with a stochastic sampling term.Source: §3.1 · p. 6
• The second-order Taylor model selects a step whose empirical objective is near the best value in the search interval, with errors from Taylor approximation and curvature estimation.The guarantee is strongest for moderate search radius, small perturbation scale, and limited higher-order variation; the proof strategy also extends to third-order Taylor and Padé models.Source: §3.1 · p. 6

3.2 Global convergence Analysis

• Under smoothness, boundedness, alignment, and interval conditions, ZFO’s average gradient norm is bounded by an optimization term plus a term for imperfect step selection.The method converges to a neighborhood of stationarity; exact stationarity is not guaranteed unless average step-selection error vanishes.Source: §3.2 · p. 7

4.1 ZFO for LLM fine-tuning and classic optimization

• At least one ZFO variant improves on AdamW first-order fine-tuning for every model–dataset pair in Table 1; Padé3 improves over FO in 14 of 16 settings summarized in Table 9.The preferred local model varies across tasks, and Padé3 is presented as a strong representative default.Source: §4.1 · p. 8
• At least one ZFO method outperforms the fine-tuning baseline on each of four Qwen-2.5-Math-1.5B reasoning benchmarks, with gains of ↑8.81 on ARC-Challenge and ↑4.92 on CODAH.The authors also report seed variance for FO fine-tuning under these settings, even with the best learning-rate configurations.Source: §4.1 · p. 8, Table 2 · p. 8
• On each classic optimization problem displayed, at least one ZFO variant achieves a substantially lower median objective than its FO baseline after 100 updates.Taylor3–AdamW is strongest on nonlinear least squares and Beale, while Padé3–AdamW performs best on Rosenbrock; the best approximant varies with the objective.Source: §4.1 · pp. 8–9, Figure 2 · p. 9
• The ablations show that changing the FO learning rate generally does not recover ZFO’s gains; increasing β can help at smaller α but may become unstable at larger α.The two parameters are complementary rather than interchangeable, and the four ZFO instances differ in how often they select interior versus endpoint steps.Source: §4.1 · p. 9

4.2 Computational Cost

• For Qwen-2.5-MATH-1.5B, ZFO adds approximately 5.2% relative wall-clock overhead in the reported configuration.Across five benchmarks, trajectory rollout dominates iteration time, while the additional ZFO computation contributes only a small fraction of FO-only update time.Source: §4.2 · p. 9, Figure 3 · p. 9
• Peak GPU-memory overhead ranges from 11.0% for Qwen/GSM8K to 19.1% for Phi-2/OpenBookQA across three model–dataset pairs.The authors report that ZFO widens the existing memory peak rather than introducing a new one.Source: Figure 4 · p. 9, §4.2 · p. 10

Discussion

• The analysis states that wider search intervals permit larger updates but increase approximation error, and that safeguards do not guarantee every step improves the surrogate.Under stated assumptions, ZFO retains a stationarity guarantee despite approximate steps.Source: §5 · p. 10
• Padé2 often selects the search-region endpoint unless a pole triggers fallback to Taylor2, making it a reference for separating search-range effects from model-based selection.The paper reports richer surrogates outperforming Padé2 on Qwen MATH, ARC-Challenge, and CODAH; when Padé2 improves over FO, the expanded range contributes beyond simply scaling α.Source: §5 · p. 10
• Taylor2, Taylor3, Padé2, and Padé3 are presented as initial ZFO instances whose lightweight probes yield measurable gains in evaluation performance and training stability across several benchmarks.The authors identify low-cost curvature extraction along the first-order direction as the framework’s broader opportunity.Source: §5 · p. 10

Conclusion

• Two additional function evaluations along a first-order direction support local models that select a step without estimating a gradient from zeroth-order queries.The authors position ZFO as a general fixed-query framework, rather than a particular Taylor or Padé formula.Source: §5 · p. 10
• The authors frame ZFO as an abstraction that extends GeN’s single-step rule to multiple local models, with analysis separating estimation, approximation, and optimization errors.Practitioners are encouraged to add other functional approximators to the framework.Source: §5 · p. 10

Discussion

• ZFO often improves step selection over a fixed first-order update, but step quality depends on the local model, search radius, and first-order direction alignment.The paper cautions that its reported instances are initial realizations, not necessarily the strongest possible ZFO methods.Source: §5 · p. 10

Policy Optimization Stability & Update Regulation

• Policy-optimization methods regulate updates through KL constraints, clipping, or acceptance wrappers, whereas this work models the objective along the update path.The cited examples include TRPO, PPO [46], GRPO [47], and wrapper-based stabilization.Source: A Related work · pp. 15–16

Zeroth-Order Optimization

• MeZO and CARS use random-direction finite differences for gradient or curvature estimates, while ZFO uses zeroth-order evaluations along a first-order direction.The related-work discussion also places ZFO alongside curvature, sparsity, query-efficiency, federated, and benchmarking extensions of zeroth-order fine-tuning.Source: A Related work · p. 16

Line-Search & Adaptive Step Size

• Classical and stochastic line-search methods often evaluate multiple candidate points, whereas ZFO uses two symmetric probes to construct a local objective model.The cited methods include Polyak step size, Barzilai-Borwein, Probabilistic line-search, and Stochastic Armijo line-search.Source: A Related work · p. 16

Generalized Newton Step Selection

• GeN already uses function evaluations along a first-order direction for step selection; ZFO generalizes this into a fixed-query framework supporting multiple local models.The analysis separates finite-difference estimation error, local-model approximation error, and global optimization error.Source: A Related work · p. 16

Theoretical foundations

• The theoretical analysis first targets concentration guarantees for finite-difference curvature estimates, then connects local step quality to global stationarity.The stated goal is to distinguish stochastic estimation, local approximation, and step-selection errors.Source: B Addendum to Theoretical Analysis · p. 16

CRN curvature concentration

• The concentration question concerns whether second- and third-order directional derivatives estimated from a shared batch approximate their population counterparts.The proof uses bounded-variable and sub-Gaussian concentration arguments and concludes that both inequalities hold simultaneously with probability at least 1 − δ.Source: B Addendum to Theoretical Analysis · pp. 16–17
• Theorem 1 is presented as a CRN curvature concentration result under Assumptions 1–4.The supplied theorem statement includes a probability bound, while the accompanying proof treats second- and third-derivative estimates.Source: B Addendum to Theoretical Analysis · p. 17

B.1 ZFO Maximum Error

• Theorem 2 bounds the second-order Taylor-selected step’s objective gap from the best interval step by a term of order R^3.The result assumes the stated smoothness and approximation conditions.Source: §B.1 · p. 18
• The Padé3 construction is not unique: the paper’s 2/1 form and an alternative 1/2 form both match through third order under their respective nondegeneracy conditions but can yield different performance curves.The alternative 1/2 form is also used in the LLM experiments.Source: §B.1 · p. 18
• The Padé2 and Padé3 guarantees require a denominator bounded away from zero and bounded higher-order derivatives of the Padé residual.The stated assumptions also include smoothness and finite-difference conditions.Source: §B.1 · pp. 18–19
• The third-order Taylor bound replaces Taylor2’s O(R^3) term with O(R^4), while Padé2 and Padé3 bounds also include residual-controlled error terms.The analysis concludes that ZFO maximizers are close to the best local-trust-region step when the search region is moderate and perturbation scale is small.Source: §B.1 · pp. 19–21

ZFO Dominance

• A supplementary Taylor2 guarantee compares its selected step with the usual first-order step under curvature-error, strong-concavity, and interior-maximizer conditions.The theorem further assumes the first-order step lies within the search interval.Source: §B.1 · p. 21

B.2 ZFO Global Stationarity

• The analysis uses the sampled surrogate Ft for parameter updates and assumes its expectation has the same gradient as the true objective J at θt.Nearby perturbations reuse the minibatch St fixed at the current iterate.Source: §B.2 · p. 23
• With probability at least 1−δ, the objective gap between the best step in It and the selected step is at most ∆t, under Assumptions 1–5.Source: §B.2 · p. 23
• Under Assumptions 5–6 and qt/LJ ∈ It, Theorem 3 states a stationarity result holding with probability at least 1−δ for every T > 0.The supplied passage does not include the theorem’s bound.Source: §B.2 · p. 24

B.3 Finite Difference Lemmas

• The appendix gives proofs for two finite-difference approximations used by ZFO, including an asymmetric finite difference alongside a natural second-order central difference.Source: §B.3 · pp. 24–25

• The addendum tests step selection in two low-dimensional toy RLVR environments, examines local approximations on analytic functions, and reports cross-setting win ratios against the FO baseline.Source: C Addendum to Experimental Results · p. 26

C.1 Configuration

• The experimental configuration specifies GRPO as the fine-tuning surrogate and summarizes fixed settings, configuration types, and hyperparameters for the main study and Qwen sub-study.Source: §C.1 · p. 26, §C.1.1 · p. 26, Table 4 · p. 26

C.1.1 Surrogate Objective Formulation

• The GRPO surrogate uses prompt batches and sampled examples, with a group-relative advantage and a token-level KL penalty averaged across the batch.The KL coefficient is κ, and the correctness indicator ρ marks examples accepted by the verifier.Source: §C.1.1 · p. 27
• In implementation, ZFO searches the AdamW displacement dt along parameters θt + a dt for a ∈ [0, β], so the effective radius is β∥dt∥.Although α and β jointly set nominal search scale, α first affects the optimizer displacement and matched αβ pairs need not behave identically.Source: §C.1.1 · pp. 27–28
• The RLVR implementation approximates the theory’s same-surrogate probes by holding sampled responses and rewards fixed while probing a separate reward-minus-KL score.The GRPO optimizer supplies the direction and first-order coefficient; symmetric probes and the GRPO slope define the local model.Source: §C.1.1 · p. 28

• Large-model results average three seeds, use shared fixed settings, and apply early stopping after evaluation accuracy is unchanged for three consecutive epochs.Source: §C.1.2 · p. 28
• The main study sweeps FO learning rates over {1e-6, 5e-6, 1e-5} and ZFO bounds over {3, 5, 10}; the Qwen sub-study uses narrower sweeps and fixes configuration c.MeZO’s ZO learning rate is tuned independently; reported performance is mean verifiable reward on the evaluation set.Source: §C.1.2 · p. 28
• Toy validation uses β = 1, making the ZFO search interval collapse to the FO typical step.The toy models use a six-dimensional context and two-layer policy network.Source: §C.1.2 · p. 28
• Large-model experiments used models ranging from 1.23B to 2.7B parameters across mathematical reasoning, commonsense reasoning, and knowledge-based benchmarks, with datasets also reported for the Qwen sub-study.Source: §C.1.2 · p. 28
• For classical optimization problems, initial positions receive independent Gaussian perturbations with standard deviation 0.2, shared across methods for each task–seed pair.Source: Table 8 · p. 29
• The MeZO baseline uses two-sided finite differences along an unnormalized Gaussian direction, holding sampled responses, reward advantages, and reference-policy log probabilities fixed across probes.It avoids backpropagation and regenerates the perturbation from the same random seed for the probes and update.Source: §C.1.2 · p. 29

C.2 Additional Insights

• Taylor3–AdamW has the lowest final median objectives on nonlinear least squares and Beale, while Padé3–AdamW leads on Rosenbrock.Several ZFO and GeN variants accelerate matrix factorization versus SGD; logistic regression converges to essentially the same objective across methods, while some nonconvex combinations stall or underperform.Source: §C.2 · p. 29, Figure 5 · p. 30
• The analytic-function panels show that the four interpolants generally agree, while toy RLVR tests show ZFO improving over FO and ZO baselines at β = 1.On super-polynomial functions the approximants show some variance; in both toy environments, Taylor3 performs best, with Taylor2 and Padé3 close behind.Source: §C.2 · pp. 29, 31, Figure 6 · p. 30, Figure 7 · p. 31
• ZFO trajectories outperform fixed-rate FO runs in the reported learning-rate comparisons, while larger β helps at smaller α but can destabilize performance at larger α.The α = 10^-6 and α = 5 × 10^-6 settings improve as β increases from 1 to 100 across all four methods; at α = 10^-5, the best results shift toward small β, and the largest bound drives reward near zero for almost all methods.Source: Figure 8 · p. 31, §C.2 · pp. 31–32, Figure 9 · p. 32
• Taylor2, Taylor3, Padé2, and Padé3 beat their corresponding FO baselines in 14/16, 7/16, 13/16, and 14/16 reported settings, respectively.The counts span 12 main-result settings and four Qwen sub-study settings.Source: §C.2 · p. 32, Table 9 · p. 32
• The strongest ZFO variant outperforms cosine-decay AdamW and Prodigy on all eight Qwen datasets, but the worst ZFO variant loses to cosine-decay AdamW on several.The comparison indicates that ZFO's advantage is not uniform across local models.Source: Table 10 · p. 33, §C.2 · p. 33
• ZFO-Seq is strongest on CODAH and stays within approximately two points of the best method on ARC-Challenge and SVAMP.Across the three evaluated settings, it is competitive with classical line-search and adaptive step-size methods.Source: §C.2 · pp. 33–34, Table 11 · p. 34
• With β = 1, ZFO improves on the shared-rate FO result in some settings, but a separately tuned FO rate performs better on ARC-Challenge and FO remains narrowly best on ASDiv.On StrategyQA, Taylor3 reaches 74.87; on ARC-Challenge, FO at 5 × 10^-6 reaches 55.12, exceeding the shared-rate FO result. These results bound the β = 1 gains to some settings.Source: Table 12 · p. 34, §C.2 · p. 34
• Taylor3 selects interior steps most often, reaching an 80.77% exact interior frequency at β = 3; Padé2 never selects an interior step in either cohort.At β = 3, Taylor3's 1%-trimmed interior frequency is 70.28%; Taylor2 more often selects the full step, while Padé3 remains endpoint-driven and its fallback frequency rises to 54.95%.Source: §C.2 · pp. 34–35, Table 13 · p. 35