Zero-order fine-tuning stops sampling uniformly: query budget follows sample importance, up to 6x fewer queries to the same loss

When zero-order optimization fine-tunes a large language model, examples are no longer treated alike; each one gets a share of the query budget set by its own importance. Existing zero-order methods typically sample training examples uniformly, overlooking that their importance evolves and leaving avoidable estimation variance. Experiments across four model families show improved average downstream performance and, counted in queries, up to 6x faster convergence to the same training loss.

Sample importance is read out of the directional differences the method already computes, so no true gradients and no extra model evaluations are needed. It extracts gradient-norm information from those directional differences to estimate importance, and keeps a per-example exponential moving average that aggregates observations across updates to track importance from sparse minibatch feedback. Against MeZO the method adds only $O(N)$ scalar state; its convergence asymptotically matches the leading term of the minimum-variance sampling oracle and is strictly faster than standard methods.

The report covers the setting of zero-order optimization for fine-tuning large language models, for researchers and engineers working on memory-constrained fine-tuning. The material states experiments across four model families and a convergence proof; model scales, task types and deployment conditions beyond that are not developed.

The material states that the method asymptotically matches the leading convergence term of the minimum-variance sampling oracle and is strictly faster than standard methods, which is a theoretical statement; the experimental part reports improved average downstream performance across four model families and up to 6x fewer queries, without per-model differences.