ZoAQ: 基于查询重用耦合的自适应零阶查询

# ZoAQ: Adaptive Zeroth-Order Querying via Query-Reuse Coupling
Source: [https://arxiv.org/html/2609.22115](https://arxiv.org/html/2609.22115)
Yao ShuAffiliation:The Hong Kong University of Science and Technology \(Guangzhou\)Email:[yfeng044@connect\.hkust\-gz\.edu\.cn](mailto:)yaoshu@hkust\-gz\.edu\.cn

###### Abstract

Zeroth\-order optimization \(ZOO\) estimates updates from function evaluations, making perturbation queries a primary cost\. Fixed budgets spend the same number of queries at every step, while adaptive controllers may offset their savings by using additional oracle calls to test estimator reliability\. We introduce ZoAQ111An implementation is available at[https://anonymous\.4open\.science/r/ZoAQ\-312A](https://anonymous.4open.science/r/ZoAQ-312A)\., an adaptive ZOO method built around query reuse\. Rather than discarding past evaluations after each step, ZoAQ makes them useful for both the next update and the decision to query further\. This enables adaptive query allocation without extra validation queries\. Our analysis characterizes when this agreement identifies an update that supports descent and guides the controller to a sufficient query budget\. On synthetic objectives, ZoAQ reduces queries by 43–48% relative to fixed baselines using 1\.2M queries\. In black\-box attacks, it reaches 100% success with 320 and 625 average queries on MNIST and CIFAR\-10, respectively\. Across four OPT fine\-tuning settings, ZoAQ saves 43–46% forward evaluations relative to fixedK=4K=4, with accuracy changes within tasks ranging from−0\.018\-0\.018to\+0\.010\+0\.010\.

## 1Introduction

Figure 1:Two hidden query costs in adaptive ZOO\.Zeroth\-order optimization \(ZOO\) enables learning when gradients are unavailable or too costly to materialize, including black\-box adversarial attacks and fine\-tuning of large language models \(LLMs\) using forward passes only\([Chen et al\. 2017](https://arxiv.org/html/2609.22115#bib.bib4);[Chen et al\. 2019](https://arxiv.org/html/2609.22115#bib.bib5);[Malladi et al\. 2023](https://arxiv.org/html/2609.22115#bib.bib17)\)\. Each update is estimated from function evaluations along random perturbations, so the local direction count determines both the reliability of the estimate and its cost\([Spall 1992](https://arxiv.org/html/2609.22115#bib.bib22);[Nesterov & Spokoiny 2017](https://arxiv.org/html/2609.22115#bib.bib18)\)\. A small budget may produce a noisy direction, whereas a large fixed budget wastes evaluations at iterates where fewer directions suffice\. Choosing one budget for the entire trajectory therefore leaves the variation in local requirements unused\.

Figure[1](https://arxiv.org/html/2609.22115#S1.F1)summarizes the two difficulties in allocating queries that motivate ZoAQ\. Adaptive sampling can exploit this variation by adding directions only when the current estimate is unreliable\. Existing rules often test estimator variance, norm, or accuracy\([Byrd et al\. 2012](https://arxiv.org/html/2609.22115#bib.bib3);[Bollapragada & Wild 2023](https://arxiv.org/html/2609.22115#bib.bib1);[Bollapragada et al\. 2024](https://arxiv.org/html/2609.22115#bib.bib2)\)\. To run such a test, a controller may query a separate pilot or validation batch\. Those evaluations consume the same oracle budget as the perturbations used to construct an update, but their responses do not improve the candidate estimate if they are used only for validation\([Ghadimi & Lan 2013](https://arxiv.org/html/2609.22115#bib.bib10)\)\. When the candidate itself contains only a few directions, even a small validation batch can offset the savings from adaptation\([Lin et al\. 2025](https://arxiv.org/html/2609.22115#bib.bib15)\)\. ZOO estimators based on variance reduction or query reuse can improve estimate quality under a prescribed sampling plan\([Liu et al\. 2018](https://arxiv.org/html/2609.22115#bib.bib16);[Qiu et al\. 2025](https://arxiv.org/html/2609.22115#bib.bib19)\), but do not by themselves determine when the current iterate has received enough directions\. A useful adaptive rule should instead make its decision from evidence that also enters the candidate update\.

Momentum consistency is a natural candidate because it compares the current estimate with an exponential moving average \(EMA\) of past estimates\. Momentum\-based ZOO backbones already maintain this EMA\([Chen et al\. 2019](https://arxiv.org/html/2609.22115#bib.bib5);[Shu et al\. 2025](https://arxiv.org/html/2609.22115#bib.bib21)\), so computing the cosine requires no additional function evaluations\. When each step samples perturbation directions independently, however, this cosine is difficult to interpret\. A low score may reflect either a change in the underlying gradient or simply a mismatch between the two direction samples\.

ZoAQ makes this comparison useful by retaining past query information across consecutive steps\. Each record stores its observed scalar response together with a reproducible perturbation seed, so the corresponding direction can be reconstructed without another oracle call\. Retained records and newly acquired records form the same candidate estimate, whose agreement with the EMA determines whether ZoAQ accepts the update or adds more queries\. After acceptance, the next step returns to the minimum budget\. A difficult iterate can therefore spend more queries without making the larger budget the default at the next one\. Because retained responses and every new evaluation contribute directly to the candidate update, the controller adapts the local query budget without a separate validation batch\.

Our analysis explains when reuse is useful: additional historical records reduce estimation noise, but stale responses also introduce bias\. We further show that the EMA error remains controllable even when consecutive estimates share records, so the consistency test can identify updates that support descent and stop expansion by a sufficient local budget\.

Our contributions are summarized as follows:

- •We propose ZoAQ, which reuses past query information to construct the candidate update and decide whether more queries are needed, enabling adaptive local budgets without a separate validation batch\.
- •We characterize the trade\-off between concentration and staleness induced by stored responses, derive pathwise EMA tracking under overlapping histories, and show that first passage yields a directionally safe update no later than a sufficient local budget\.
- •On synthetic objectives, ZoAQ reduces queries by 43–48% relative to fixed baselines using 1\.2M queries\. In black\-box attacks, it reaches 100% success with 320 and 625 average queries on MNIST and CIFAR\-10, respectively\. Across four OPT fine\-tuning settings, ZoAQ saves 43–46% forward evaluations relative to fixedK=4K=4, with accuracy changes within tasks ranging from−0\.018\-0\.018to\+0\.010\+0\.010\.

## 2Related Work and Positioning

#### Fixed\-budget zeroth\-order backbones\.

A first line of work establishes how to make useful updates when gradients are unavailable\. Classical zeroth\-order methods estimate gradients from randomized function evaluations\([Spall 1992](https://arxiv.org/html/2609.22115#bib.bib22);[Nesterov & Spokoiny 2017](https://arxiv.org/html/2609.22115#bib.bib18)\), and the broader derivative\-free optimization literature develops principled search and trust\-region machinery for function\-value oracles\([Conn et al\. 2000](https://arxiv.org/html/2609.22115#bib.bib6);[Conn et al\. 2009](https://arxiv.org/html/2609.22115#bib.bib7)\)\. Modern ZOO methods bring this viewpoint to black\-box learning and attacks through coordinate or random\-direction estimators and adaptive\-momentum updates\([Chen et al\. 2017](https://arxiv.org/html/2609.22115#bib.bib4);[Chen et al\. 2019](https://arxiv.org/html/2609.22115#bib.bib5)\), while R\-AdaZO stabilizes the high\-dimensional adaptive backbone used in our experiments\([Shu et al\. 2025](https://arxiv.org/html/2609.22115#bib.bib21)\)\. Forward\-only LLM fine\-tuning gives the same query\-accounting issue at model scale, with MeZO showing that language models can be tuned through forward passes and LoRA reducing the number of trainable parameters\([Malladi et al\. 2023](https://arxiv.org/html/2609.22115#bib.bib17);[Hu et al\. 2022](https://arxiv.org/html/2609.22115#bib.bib11)\)\. These methods solve the backbone problem: they specify how function evaluations become update directions\. Their local query budget, however, is usually chosen outside the online accept\-or\-expand decision\. ZoAQ keeps this backbone view and studies the missing allocation layer: when a step has enough query evidence to move\. Normalized momentum provides a first\-order precedent for separating directional progress from update magnitude\([Cutkosky & Mehta 2020](https://arxiv.org/html/2609.22115#bib.bib8);[Cutkosky & Mehta 2021](https://arxiv.org/html/2609.22115#bib.bib9)\); our normalized\-update protocol follows this analytical convention to isolate directional reliability from update magnitude\.

#### History reuse and variance reduction\.

A second line of work improves zeroth\-order estimates by reducing variance or reusing information\. ZO\-SVRG adapts variance\-reduction ideas to nonconvex ZOO\([Liu et al\. 2018](https://arxiv.org/html/2609.22115#bib.bib16)\), and ZoAR shows that query reuse can produce more stable zeroth\-order estimators\([Qiu et al\. 2025](https://arxiv.org/html/2609.22115#bib.bib19)\)\. These methods improve the estimator built from a collection of function evaluations, but they do not by themselves determine when sampling should stop at the current step\. ZoAQ uses retained acquisition records to enlarge the candidate estimate and compares that candidate with an EMA of previously accepted estimates\. Its distinct question is how the concentration gained from retained evidence can support local budget allocation without letting response staleness dominate\.

#### Adaptive sampling\.

A third line of work chooses sample sizes online rather than fixing one budget for the whole trajectory\. This idea is classical in first\-order stochastic optimization\([Byrd et al\. 2012](https://arxiv.org/html/2609.22115#bib.bib3)\), and derivative\-free or zeroth\-order variants control stochastic approximation accuracy through norm\-, variance\-, or accuracy\-based criteria\([Bollapragada & Wild 2023](https://arxiv.org/html/2609.22115#bib.bib1);[Bollapragada et al\. 2024](https://arxiv.org/html/2609.22115#bib.bib2)\)\. Such criteria are effective when their reliability statistics can be estimated affordably\. In low\-query ZOO, additional oracle calls used only to assess reliability may consume a material fraction of the local budget\. ZoAQ instead computes its momentum\-consistency score from the candidate update and an EMA already maintained by the optimizer\. Its novelty lies in combining stored\-response estimation with an accept\-or\-expand allocation rule and characterizing when the resulting score is directionally meaningful\.

## 3Problem Setup

### 3\.1Zeroth\-Order Estimation and Local Budgets

The zeroth\-order problem is to minimizeF⁡\(𝜽\)F\(\\bm\{\\theta\}\)over𝜽∈ℝd\\bm\{\\theta\}\\in\\mathbb\{R\}^\{d\}using only function\-value queries\. For a smoothing radiusμ\>0\\mu\>0, define the Gaussian\-smoothed objective

Fμ​\(𝜽\)≜𝔼𝒖∼𝒩⁡\(0,𝑰d\)​\[F⁡\(𝜽\+μ​𝒖\)\]\.F\_\{\\mu\}\(\\bm\{\\theta\}\)\\triangleq\\mathbb\{E\}\_\{\\bm\{u\}\\sim\\mathcal\{N\}\(0,\\bm\{I\}\_\{d\}\)\}\[F\(\\bm\{\\theta\}\+\\mu\\bm\{u\}\)\]\.\(1\)For an exogenous direction𝒖∼𝒩⁡\(0,𝑰d\)\\bm\{u\}\\sim\\mathcal\{N\}\(0,\\bm\{I\}\_\{d\}\), two function evaluations define the scalar response and its single\-direction vector estimate:

rμ​\(𝜽,𝒖\)≜F⁡\(𝜽\+μ​𝒖\)−F⁡\(𝜽−μ​𝒖\)2​μ,𝒈μ​\(𝜽,𝒖\)≜rμ​\(𝜽,𝒖\)​𝒖\.r\_\{\\mu\}\(\\bm\{\\theta\},\\bm\{u\}\)\\triangleq\\frac\{F\(\\bm\{\\theta\}\+\\mu\\bm\{u\}\)\-F\(\\bm\{\\theta\}\-\\mu\\bm\{u\}\)\}\{2\\mu\},\\qquad\\bm\{g\}\_\{\\mu\}\(\\bm\{\\theta\},\\bm\{u\}\)\\triangleq r\_\{\\mu\}\(\\bm\{\\theta\},\\bm\{u\}\)\\bm\{u\}\.\(2\)For fixed𝜽\\bm\{\\theta\}, the Gaussian smoothing identity gives𝔼𝒖​\[𝒈μ​\(𝜽,𝒖\)\]=∇Fμ​\(𝜽\)\\mathbb\{E\}\_\{\\bm\{u\}\}\[\\bm\{g\}\_\{\\mu\}\(\\bm\{\\theta\},\\bm\{u\}\)\]=\\nabla F\_\{\\mu\}\(\\bm\{\\theta\}\), so each direction yields an unbiased estimate of the smoothed gradient\.

At steptt, a fresh\-query budgetKKaveragesKKsuch estimates:

𝒈tfresh​\(K\)≜1K​∑k=1K𝒈μ​\(𝜽t,𝒖t,k\),\\bm\{g\}\_\{t\}^\{\\mathrm\{fresh\}\}\(K\)\\triangleq\\frac\{1\}\{K\}\\sum\_\{k=1\}^\{K\}\\bm\{g\}\_\{\\mu\}\(\\bm\{\\theta\}\_\{t\},\\bm\{u\}\_\{t,k\}\),\(3\)where each𝒖t,k\\bm\{u\}\_\{t,k\}has marginal distribution𝒩⁡\(0,𝑰d\)\\mathcal\{N\}\(0,\\bm\{I\}\_\{d\}\)\. The controller acceptsKtK\_\{t\}from𝒦=\{Kmin,Kmin\+Δ​K,…,Kmax\}\\mathcal\{K\}=\\\{K\_\{\\min\},K\_\{\\min\}\+\\Delta K,\\ldots,K\_\{\\max\}\\\}, while a fixed\-budget method uses the sameKKat every step\. ZoAQ combines theKKnewly acquired records with retained records to formℋt​\(K\)\\mathcal\{H\}\_\{t\}\(K\)and the candidate estimate𝒈t​\(K\)\\bm\{g\}\_\{t\}\(K\), withnt​\(K\)=\|ℋt​\(K\)\|n\_\{t\}\(K\)=\|\\mathcal\{H\}\_\{t\}\(K\)\|\. Thus,KKcounts fresh directions acquired at steptt, whilent​\(K\)n\_\{t\}\(K\)counts the records used by the candidate estimate\. Only theKKfresh directions incur new oracle calls at steptt\. Section[4](https://arxiv.org/html/2609.22115#S4)gives the exact construction\.

### 3\.2Directional Reliability

We assess a local budget by whether its estimated direction supports descent\. To isolate this directional requirement, the analysis uses the following normalized\-update protocol\.

###### Assumption 3\.1\(Normalized\-Update Analysis Protocol\)\.

For a nonzero candidate estimate, let𝒅t​\(K\)=𝒈t​\(K\)/‖𝒈t​\(K\)‖\\bm\{d\}\_\{t\}\(K\)=\\bm\{g\}\_\{t\}\(K\)/\\\|\\bm\{g\}\_\{t\}\(K\)\\\|\. The analyzed update is𝜽t\+1=𝜽t−αt​𝒅t​\(K\)\\bm\{\\theta\}\_\{t\+1\}=\\bm\{\\theta\}\_\{t\}\-\\alpha\_\{t\}\\bm\{d\}\_\{t\}\(K\)\.

Under this protocol, a candidate budget satisfies the directional reliability condition when

cos⁡\(𝒅t​\(K\),∇Fμ​\(𝜽t\)\)≥δ,δ\>0,\\cos\\\!\\left\(\\bm\{d\}\_\{t\}\(K\),\\nabla F\_\{\\mu\}\(\\bm\{\\theta\}\_\{t\}\)\\right\)\\geq\\delta,\\qquad\\delta\>0,\(4\)
###### Definition 3\.2\(Oracle Alignment Budget\)\.

Forδ\>0\\delta\>0, when the following set is nonempty, define the oracle alignment budget

Kt∘​\(δ\)≜min⁡\{K∈𝒦:cos⁡\(𝒅t​\(K\),∇Fμ​\(𝜽t\)\)≥δ\}\.K\_\{t\}^\{\\circ\}\(\\delta\)\\triangleq\\min\\\!\\left\\\{K\\in\\mathcal\{K\}:\\cos\\\!\\left\(\\bm\{d\}\_\{t\}\(K\),\\nabla F\_\{\\mu\}\(\\bm\{\\theta\}\_\{t\}\)\\right\)\\geq\\delta\\right\\\}\.\(5\)If no grid point satisfies the condition, we setKt∘​\(δ\)=KmaxK\_\{t\}^\{\\circ\}\(\\delta\)=K\_\{\\max\}to keep the budget on the finite grid\.

The oracle budget depends on∇Fμ​\(𝜽t\)\\nabla F\_\{\\mu\}\(\\bm\{\\theta\}\_\{t\}\)and cannot be evaluated directly\. ZoAQ instead choosesKKfrom a momentum\-consistency score computed from the candidate estimate and recent accepted estimates\. Every new record acquired during expansion enters the same candidate estimate\.

## 4ZoAQ: Query\-Reuse Adaptive Querying

Figure[2](https://arxiv.org/html/2609.22115#S4.F2)summarizes how ZoAQ builds one nested candidate, expands it when needed, and commits the accepted update and controller state\.

Figure 2:ZoAQ at one optimizer step\. Retained records andKKfresh directions form a nested candidate estimate\. The same estimate drives both the backbone update and momentum\-consistency gate; a failed test appends onlyΔ​K\\Delta Kfresh records, whereas acceptance commits the update, EMA, threshold, and FIFO history\.### 4\.1Query\-Response Reuse

ZoAQ decides whether to expand the current query budget by comparing the candidate estimate with an exponential moving average \(EMA\) of previously accepted estimates\. With fresh directions alone, a low consistency score can reflect either local gradient change or sampling noise\. ZoAQ reduces this ambiguity by allowing retained query\-response records to enter the candidate estimate\.

Recordiistores a reproducible seed for the direction𝒖i\\bm\{u\}\_\{i\}, its acquisition stepaia\_\{i\}, and the paired scalar responseri=rμ​\(𝜽ai,𝒖i\)r\_\{i\}=r\_\{\\mu\}\(\\bm\{\\theta\}\_\{a\_\{i\}\},\\bm\{u\}\_\{i\}\)defined in Section[3\.1](https://arxiv.org/html/2609.22115#S3.SS1)\. The seed reconstructs𝒖i\\bm\{u\}\_\{i\}without a new query, whilerir\_\{i\}remains the response observed at its acquisition iterate\. Letℛt−1\\mathcal\{R\}\_\{t\-1\}be the FIFO history and𝒬t​\(K\)\\mathcal\{Q\}\_\{t\}\(K\)theKKfresh records acquired at𝜽t\\bm\{\\theta\}\_\{t\}\. Their unionℋt​\(K\)=ℛt−1∪𝒬t​\(K\)\\mathcal\{H\}\_\{t\}\(K\)=\\mathcal\{R\}\_\{t\-1\}\\cup\\mathcal\{Q\}\_\{t\}\(K\)defines the candidate estimate

𝒈t​\(K\)=1nt​\(K\)​∑i=1nt​\(K\)ri​𝒖i,nt​\(K\)=\|ℋt​\(K\)\|\.\\bm\{g\}\_\{t\}\(K\)=\\frac\{1\}\{n\_\{t\}\(K\)\}\\sum\_\{i=1\}^\{n\_\{t\}\(K\)\}r\_\{i\}\\bm\{u\}\_\{i\},\\qquad n\_\{t\}\(K\)=\|\\mathcal\{H\}\_\{t\}\(K\)\|\.\(6\)The sets𝒬t​\(K\)\\mathcal\{Q\}\_\{t\}\(K\)are nested, so expanding fromKKtoK\+Δ​KK\+\\Delta Kqueries only the additionalΔ​K\\Delta Kdirections\. After acceptance, FIFO retention keeps the most recent records for subsequent steps\.

Query reuse and momentum average information at different stages\. The candidate in Eq\.[6](https://arxiv.org/html/2609.22115#S4.E6)pools acquisition records before a budget is accepted, changing both the evidence available to the gate and the estimate sent to the backbone\. The EMA instead pools previously accepted estimates after those decisions and supplies the reference at the next step\. The first operation trades concentration against response staleness, whereas the second trades update noise against trajectory lag\. They are complementary rather than duplicate smoothing operations; Appendix[I](https://arxiv.org/html/2609.22115#A9)gives the corresponding decomposition\.

### 4\.2Momentum\-Consistency Gate

For each candidate budget, ZoAQ computes

st​\(K\)≜cos⁡\(𝒈t​\(K\),𝒎t−1\),s\_\{t\}\(K\)\\triangleq\\cos\\\!\\left\(\\bm\{g\}\_\{t\}\(K\),\\bm\{m\}\_\{t\-1\}\\right\),\(7\)where𝒎t−1\\bm\{m\}\_\{t\-1\}is the EMA of previously accepted estimates\. Starting fromKminK\_\{\\min\}, the controller accepts the first budget whose score reaches the current threshold:

Kt=min⁡\(\{K∈𝒦:st​\(K\)≥τt−1\}∪\{Kmax\}\)\.K\_\{t\}=\\min\\\!\\left\(\\\{K\\in\\mathcal\{K\}:s\_\{t\}\(K\)\\geq\\tau\_\{t\-1\}\\\}\\cup\\\{K\_\{\\max\}\\\}\\right\)\.\(8\)If‖𝒎t−1‖≤εanc\\\|\\bm\{m\}\_\{t\-1\}\\\|\\leq\\varepsilon\_\{\\text\{anc\}\}, ZoAQ takes a warm\-start update atKminK\_\{\\min\}\. If no score passes, it accepts the candidate atKmaxK\_\{\\max\}\. Otherwise, every failed test adds fresh records to the same candidate estimate before the score is recomputed\. The added queries therefore improve the candidate that can be accepted at the same step\. After acceptance, ZoAQ passes𝒈t\\bm\{g\}\_\{t\}to the ZOO backbone, updates the estimate EMA and score threshold, and restarts the next step fromKminK\_\{\\min\}\.

This control flow separates evidence acquisition within a step from state adaptation across steps\. Within a step, rejection changes only the fresh budget: it neither advances𝜽t\\bm\{\\theta\}\_\{t\}nor updates the EMA, threshold, or FIFO buffer\. Because the candidate sets are nested, each retest preserves all records already collected at that step and pays only for the nextΔ​K\\Delta Kfresh directions\. Acceptance is the commit point at which the chosen candidate updates the backbone and persistent controller state\. Restarting fromKminK\_\{\\min\}then lets every new iterate test whether the cheapest budget is adequate, while the calibrated threshold carries information about the consistency of previously accepted estimates\. Accordingly,KtK\_\{t\}is a local stopping outcome rather than a persistent operating level: expansion at one iterate does not force the next iterate to inherit the larger budget\.

In Algorithm[1](https://arxiv.org/html/2609.22115#alg1),Scorereturnsτt−1\\tau\_\{t\-1\}during warm start, returns−∞\-\\inftywhen the candidate estimate is zero and the EMA is nonzero, and otherwise returns the cosine score above\.ExtendHistorycarries retained records forward and adds only the new records from the current step needed to reachKK\. For a finite accepted score,Calibrateappliesτt=βτ​τt−1\+\(1−βτ\)​st\\tau\_\{t\}=\\beta\_\{\\tau\}\\tau\_\{t\-1\}\+\(1\-\\beta\_\{\\tau\}\)s\_\{t\}; it leaves the threshold unchanged whenst=−∞s\_\{t\}=\-\\infty\.

Algorithm 1ZoAQ Accept\-or\-Expand with Query ReuseInput:oracle

FF, initial point

𝜽0\\bm\{\\theta\}\_\{0\}, horizon

TT
Parameters:grid

\(Kmin,Δ​K,Kmax\)\(K\_\{\\min\},\\Delta K,K\_\{\\max\}\),

NhistN\_\{\\text\{hist\}\}, and

\(τ0,β1,βτ,εanc\)\(\\tau\_\{0\},\\beta\_\{1\},\\beta\_\{\\tau\},\\varepsilon\_\{\\text\{anc\}\}\)
Initialize:retained buffer

ℋ0←∅\\mathcal\{H\}\_\{0\}\\leftarrow\\emptysetand EMA

𝒎0←𝟎\\bm\{m\}\_\{0\}\\leftarrow\\bm\{0\}
for

t=1,…,Tt=1,\\dots,Tdo

K←KminK\\leftarrow K\_\{\\min\}

whiletruedo

ℋt​\(K\)←ExtendHistory​\(F,𝜽t,ℋt−1,K\)\\mathcal\{H\}\_\{t\}\(K\)\\leftarrow\\textsc\{ExtendHistory\}\(F,\\bm\{\\theta\}\_\{t\},\\mathcal\{H\}\_\{t\-1\},K\)

𝒈t​\(K\)←PairedEstimate​\(ℋt​\(K\)\)\\bm\{g\}\_\{t\}\(K\)\\leftarrow\\textsc\{PairedEstimate\}\(\\mathcal\{H\}\_\{t\}\(K\)\)Eq\.[6](https://arxiv.org/html/2609.22115#S4.E6)

st​\(K\)←Score​\(𝒈t​\(K\),𝒎t−1,τt−1,εanc\)s\_\{t\}\(K\)\\leftarrow\\textsc\{Score\}\(\\bm\{g\}\_\{t\}\(K\),\\bm\{m\}\_\{t\-1\},\\tau\_\{t\-1\};\\varepsilon\_\{\\text\{anc\}\}\)

if

st​\(K\)≥τt−1s\_\{t\}\(K\)\\geq\\tau\_\{t\-1\}or

K=KmaxK=K\_\{\\max\}break; else

K←min⁡\{K\+Δ​K,Kmax\}K\\leftarrow\\min\\\{K\+\\Delta K,K\_\{\\max\}\\\}
endwhile

\(Kt,𝒈t,st,ℋt\)←\(K,𝒈t​\(K\),st​\(K\),ℋt​\(K\)\)\(K\_\{t\},\\bm\{g\}\_\{t\},s\_\{t\},\\mathcal\{H\}\_\{t\}\)\\leftarrow\(K,\\bm\{g\}\_\{t\}\(K\),s\_\{t\}\(K\),\\mathcal\{H\}\_\{t\}\(K\)\)

𝜽t\+1←BackboneStep​\(𝜽t,𝒈t\)\\bm\{\\theta\}\_\{t\+1\}\\leftarrow\\textsc\{BackboneStep\}\(\\bm\{\\theta\}\_\{t\},\\bm\{g\}\_\{t\}\)

𝒎t←β1​𝒎t−1\+\(1−β1\)​𝒈t\\bm\{m\}\_\{t\}\\leftarrow\\beta\_\{1\}\\bm\{m\}\_\{t\-1\}\+\(1\-\\beta\_\{1\}\)\\bm\{g\}\_\{t\}

τt←Calibrate​\(τt−1,st,βτ\)\\tau\_\{t\}\\leftarrow\\textsc\{Calibrate\}\(\\tau\_\{t\-1\},s\_\{t\};\\beta\_\{\\tau\}\)

ℋt←FIFO​\(ℋt,Nhist\)\\mathcal\{H\}\_\{t\}\\leftarrow\\textsc\{FIFO\}\(\\mathcal\{H\}\_\{t\},N\_\{\\text\{hist\}\}\)

endfor

return

𝜽T\\bm\{\\theta\}\_\{T\}and

\{Kt\}t=1T\\\{K\_\{t\}\\\}\_\{t=1\}^\{T\}

The same candidate records determine both the update and the accept\-or\-expand score, so the controller requires no separate validation queries\. Appendix[G\.1](https://arxiv.org/html/2609.22115#A7.SS1)gives the function evaluation accounting and update backbone for each protocol\. Section[5](https://arxiv.org/html/2609.22115#S5)analyzes the stored\-response controller and uses the normalized\-update protocol in Assumption[3\.1](https://arxiv.org/html/2609.22115#S3.Thmtheorem1)for its descent result\.

## 5Theory: Estimation, Consistency, and Local Budgets

ZoAQ reuses scalar responses at their acquisition iterates\. This increases the evidence available to a candidate without new function evaluations, but older records target earlier local gradients\. We analyze this stored\-response estimator and its accept\-or\-expand controller by quantifying the trade\-off between concentration and staleness, propagating the accuracy of accepted candidates through the EMA, and characterizing safe first passage\. The resulting estimation, tracking, and gate guarantees apply directly to the controller; the final descent statement uses the normalized\-update protocol in Assumption[3\.1](https://arxiv.org/html/2609.22115#S3.Thmtheorem1)\. Appendices[A](https://arxiv.org/html/2609.22115#A1)–[E](https://arxiv.org/html/2609.22115#A5)give the full assumptions and proofs\.

### 5\.1Stored Responses Trade Concentration for Staleness

For a candidate built fromnt​\(K\)n\_\{t\}\(K\)records, define its total acquisition staleness

At​\(K\)≜∑j∈𝒥t​\(K\)‖𝜽t−𝜽aj‖\.A\_\{t\}\(K\)\\triangleq\\sum\_\{j\\in\\mathcal\{J\}\_\{t\}\(K\)\}\\\|\\bm\{\\theta\}\_\{t\}\-\\bm\{\\theta\}\_\{a\_\{j\}\}\\\|\.\(9\)This quantity measures staleness by optimization movement, so an old record need not be harmful when the iterate has moved little\. The candidate differs from the current smoothed gradientht=∇Fμ​\(𝜽t\)h\_\{t\}=\\nabla F\_\{\\mu\}\(\\bm\{\\theta\}\_\{t\}\)through acquisition noise and gradient movement\.

###### Lemma 5\.1\(Selection\-Safe Stored\-Response Control\)\.

On the simultaneous candidate event established in Appendix[B](https://arxiv.org/html/2609.22115#A2), every candidate inspected by the controller satisfies

‖𝒈t​\(K\)−ht‖≤et​\(K\)≜q⁡\(nt​\(K\),δ\)\+L​At​\(K\)nt​\(K\)\.\\\|\\bm\{g\}\_\{t\}\(K\)\-h\_\{t\}\\\|\\leq e\_\{t\}\(K\)\\triangleq q\(n\_\{t\}\(K\),\\delta\)\+\\frac\{LA\_\{t\}\(K\)\}\{n\_\{t\}\(K\)\}\.\(10\)The statement remains valid for the random first\-passing candidate\.

Under a common local noise scale, the radiusqqdecreases as records accumulate, whereas the second term grows with the distance traveled since acquisition\. At a common fresh budgetKK, reuse improves the error certificate whenever

L​At​\(K\)nt​\(K\)≤q⁡\(K,δ\)−q⁡\(nt​\(K\),δ\)\.\\frac\{LA\_\{t\}\(K\)\}\{n\_\{t\}\(K\)\}\\leq q\(K,\\delta\)\-q\(n\_\{t\}\(K\),\\delta\)\.\(11\)Thus history is useful when its concentration gain exceeds its staleness cost\. Under a full FIFO buffer, the leading envelope has the format/C\+bt​Ca\_\{t\}/\\sqrt\{C\}\+b\_\{t\}C, yielding the interior capacity scale

Copt≍\(at​KminL​ℓ¯\)2/3\.C\_\{\\text\{opt\}\}\\asymp\\left\(\\frac\{a\_\{t\}K\_\{\\min\}\}\{L\\bar\{\\ell\}\}\\right\)^\{2/3\}\.\(12\)More history is therefore not uniformly better: noisier problems favor larger buffers, while faster movement favors smaller ones\.

### 5\.2Momentum Consistency as a Directional Certificate

Because cosine is invariant to positive scaling, the implemented score is unchanged if the raw EMA is replaced by its debiased form𝒎~t−1=𝒎t−1/\(1−β1t−1\)\\widetilde\{\\bm\{m\}\}\_\{t\-1\}=\\bm\{m\}\_\{t\-1\}/\(1\-\\beta\_\{1\}^\{t\-1\}\)\. If accepted estimates satisfy‖𝒈r−hr‖≤εr\\\|\\bm\{g\}\_\{r\}\-h\_\{r\}\\\|\\leq\\varepsilon\_\{r\}, Appendix[C\.1](https://arxiv.org/html/2609.22115#A3.SS1)proves the pathwise bound

‖𝒎~t−1−ht‖≤∑r<tw¯r,t​εr\+L​Dtema\.\\\|\\widetilde\{\\bm\{m\}\}\_\{t\-1\}\-h\_\{t\}\\\|\\leq\\sum\_\{r<t\}\\bar\{w\}\_\{r,t\}\\varepsilon\_\{r\}\+LD\_\{t\}^\{\\text\{ema\}\}\.\(13\)This avoids independence assumptions between overlapping accepted buffers\. Letκt\\kappa\_\{t\}denote the right\-hand side divided by‖ht‖\\\|h\_\{t\}\\\|\.

###### Theorem 5\.2\(Soundness and Completeness of Momentum Consistency\)\.

Supposeκt<1\\kappa\_\{t\}<1and a nonzero candidate passescos⁡\(𝐠t​\(K\),𝐦t−1\)≥τt−1\\cos\(\\bm\{g\}\_\{t\}\(K\),\\bm\{m\}\_\{t\-1\}\)\\geq\\tau\_\{t\-1\}\. Then

cos⁡\(𝒈t​\(K\),ht\)≥Δ⁡\(τt−1,κt\)≜τt−1​1−κt2−κt​1−τt−12\.\\cos\(\\bm\{g\}\_\{t\}\(K\),h\_\{t\}\)\\geq\\Delta\(\\tau\_\{t\-1\},\\kappa\_\{t\}\)\\triangleq\\tau\_\{t\-1\}\\sqrt\{1\-\\kappa\_\{t\}^\{2\}\}\-\\kappa\_\{t\}\\sqrt\{1\-\\tau\_\{t\-1\}^\{2\}\}\.\(14\)Conversely, a candidate is guaranteed to pass whenever

‖𝒈t​\(K\)−ht‖≤η⋆​\(τt−1,κt\)​‖ht‖,\\\|\\bm\{g\}\_\{t\}\(K\)\-h\_\{t\}\\\|\\leq\\eta\_\{\\star\}\(\\tau\_\{t\-1\},\\kappa\_\{t\}\)\\\|h\_\{t\}\\\|,\(15\)where

η⋆​\(τ,κ\)≜1−τ2​1−κ2−τ​κ\.\\eta\_\{\\star\}\(\\tau,\\kappa\)\\triangleq\\sqrt\{1\-\\tau^\{2\}\}\\sqrt\{1\-\\kappa^\{2\}\}\-\\tau\\kappa\.\(16\)

Both directions are geometrically sharp\. They coexist in the nonempty band

κt<τt−1<1−κt2,κt<12\.\\kappa\_\{t\}<\\tau\_\{t\-1\}<\\sqrt\{1\-\\kappa\_\{t\}^\{2\}\},\\qquad\\kappa\_\{t\}<\\frac\{1\}\{\\sqrt\{2\}\}\.\(17\)Within the band, every pass is descent\-relevant and sufficiently accurate candidates can pass\. Our experiments use Algorithm[1](https://arxiv.org/html/2609.22115#alg1)’s unprojected EMA, so these guarantees apply when its threshold lies in the band; Appendix[C\.3](https://arxiv.org/html/2609.22115#A3.SS3)gives the projected calibration\.

### 5\.3Safe First Passage and Query Control

Letκ¯<1/2\\bar\{\\kappa\}<1/\\sqrt\{2\}uniformly boundκt\\kappa\_\{t\}, and chooseκ¯<τ¯≤τt−1≤τ¯<1−κ¯2\\bar\{\\kappa\}<\\underline\{\\tau\}\\leq\\tau\_\{t\-1\}\\leq\\overline\{\\tau\}<\\sqrt\{1\-\\bar\{\\kappa\}^\{2\}\}\. Define

Δ¯≜Δ⁡\(τ¯,κ¯\),η¯≜η⋆​\(τ¯,κ¯\),\\underline\{\\Delta\}\\triangleq\\Delta\(\\underline\{\\tau\},\\bar\{\\kappa\}\),\\qquad\\underline\{\\eta\}\\triangleq\\eta\_\{\\star\}\(\\overline\{\\tau\},\\bar\{\\kappa\}\),\(18\)and the first sufficient grid point

Ktsuf≜min⁡\{K∈𝒦:et​\(K\)≤η¯​‖ht‖\}\.K\_\{t\}^\{\\text\{suf\}\}\\triangleq\\min\\left\\\{K\\in\\mathcal\{K\}:e\_\{t\}\(K\)\\leq\\underline\{\\eta\}\\\|h\_\{t\}\\\|\\right\\\}\.\(19\)
###### Theorem 5\.3\(Safe First\-Passing Local Allocation\)\.

IfKtsuf≤KmaxK\_\{t\}^\{\\text\{suf\}\}\\leq K\_\{\\max\}, the increasing\-grid search passes no later thanKtsufK\_\{t\}^\{\\text\{suf\}\}\. Its first passing candidate satisfies

Kt≤Ktsuf,cos⁡\(𝒈t​\(Kt\),ht\)≥Δ¯\>0\.K\_\{t\}\\leq K\_\{t\}^\{\\text\{suf\}\},\\qquad\\cos\(\\bm\{g\}\_\{t\}\(K\_\{t\}\),h\_\{t\}\)\\geq\\underline\{\\Delta\}\>0\.\(20\)Hence capped fallback does not occur on the simultaneous event\. Under the normalized\-update protocol in Assumption[3\.1](https://arxiv.org/html/2609.22115#S3.Thmtheorem1),

Fμ​\(𝜽t\+1\)−Fμ​\(𝜽t\)≤−αt​Δ¯​‖ht‖\+L​αt22\.F\_\{\\mu\}\(\\bm\{\\theta\}\_\{t\+1\}\)\-F\_\{\\mu\}\(\\bm\{\\theta\}\_\{t\}\)\\leq\-\\alpha\_\{t\}\\underline\{\\Delta\}\\\|h\_\{t\}\\\|\+\\frac\{L\\alpha\_\{t\}^\{2\}\}\{2\}\.\(21\)

Soundness and completeness play different roles in this stopping argument\. Soundness evaluates whichever candidate happens to pass, including one belowKtsufK\_\{t\}^\{\\text\{suf\}\}, and guarantees its alignment from the observed score rather than from its budget\. Completeness supplies the stopping envelope: once the candidate error reaches the sufficient level in Eq\.[19](https://arxiv.org/html/2609.22115#S5.E19), the score must pass\. Their combination therefore does not require the empirical score to increase withKK, nor does it require every earlier candidate to fail\. An irregular score sequence may pass early, but any such pass remains covered by the same soundness guarantee; otherwise, the search stops byKtsufK\_\{t\}^\{\\text\{suf\}\}\.

Reuse enters this conclusion through the candidate erroret​\(K\)e\_\{t\}\(K\)\. When Eq\.[11](https://arxiv.org/html/2609.22115#S5.E11)holds at the sufficient budget based on fresh directions alone, retained records meet the same accuracy requirement with no larger fresh budget\. The comparison therefore holds locally under the stated reuse condition\. Over a window before stationarity, the cost of fresh directions is bounded by∑tKtsuf\\sum\_\{t\}K\_\{t\}^\{\\text\{suf\}\}and hence byKmaxK\_\{\\max\}times the window length\. These guarantees cover steps satisfying the movement, tracking, threshold, and cap conditions, while the experiments measure realized allocation with the optimization backbone used in each task\.

## 6Experiments: Mechanism\-to\-Scale Evidence

The experiments measure the oracle cost incurred by ZoAQ together with the resulting task outcome\. Synthetic objectives expose how its scores and direction budgets evolve, black\-box attacks compare queries at a common success rate, and OPT fine\-tuning reports forward evaluations alongside task metrics\. Mechanism diagnostics help interpret these results but are not used to assign all end\-to\-end gains to the gate alone\. Appendix[G](https://arxiv.org/html/2609.22115#A7)and Table[6](https://arxiv.org/html/2609.22115#A7.T6)provide the full configurations, accounting conventions, baseline standardization, and evidence\-to\-claim map\.

### 6\.1Synthetic Mechanism Tests

The synthetic regime makes local allocation directly visible\. Figure[3](https://arxiv.org/html/2609.22115#S6.F3)shows the main effect under the protocol of 60k steps: the fixed baselines spend 1\.2M queries, whereas ZoAQ uses about 0\.62M–0\.68M on the displayed objectives, a 43–48% reduction\. The fixed budget sweep in Table[15](https://arxiv.org/html/2609.22115#A7.T15)controls for budget choice: changing the budget trades cost against final gap on individual tasks, but no single fixed value reproduces the adaptive balance between cost and quality across the suite\. ZoAQ instead revisitsKminK\_\{\\min\}after every accepted update and acquires more evidence only when the current candidate fails the gate\.

Figure 3:Synthetic convergence under the protocol of 60k steps, averaged over five runs\. On the query axis, ZoAQ reaches regions of low error with fewer queries than baselines based on fixed budgets or variance\.The auxiliary controls support the controller design\. ZoAQ\-Norm needs 28\.1% more queries to reach the same Rosenbrock target and shows a weaker descent rate than ZoAQ \(1\.3 vs\. 1\.9 loss drop per 1k queries\); Appendix[H\.4](https://arxiv.org/html/2609.22115#A8.SS4)and Figure[12](https://arxiv.org/html/2609.22115#A8.F12)provide the corresponding diagnostic\. Figure[13](https://arxiv.org/html/2609.22115#A9.F13)checks the gate statistic directly: the displayed baselines stay near zero or decay toward it, whereas ZoAQ remains more positive through most of the trajectory\. Appendix[H](https://arxiv.org/html/2609.22115#A8)reports the reset diagnostics, and Appendix[I](https://arxiv.org/html/2609.22115#A9)compares direction reuse with fresh independent sampling\.

### 6\.2Black\-Box Attacks under Query Constraints

Black\-box attacks test query allocation in a regime whered≫Ktd\\gg K\_\{t\}, local budgets are often one or two directions, and every additional oracle call changes the realized cost\. Under a common stabilized R\-AdaZO backbone, Table[1](https://arxiv.org/html/2609.22115#S6.T1)gives 100% success for all methods and separates them by required queries\. ZoAQ reduces average queries to 320 on MNIST and 625 on CIFAR\-10, corresponding to 4\.77×\\timesand 1\.61×\\timesspeedups over fixed budget; StatZO does not recover comparable savings in this regime\. Figure[14](https://arxiv.org/html/2609.22115#A9.F14)provides a complementary diagnostic: ZoAQ maintains a more stable momentum\-consistency score under the same attack regime\. At the same 100% success rate, history reuse alone does not recover the full gain: relative to ZoAR with fixedK=2K=2, ZoAQ uses 56\.9% fewer queries on MNIST and 17\.3% fewer on CIFAR\-10; Table[11](https://arxiv.org/html/2609.22115#A7.T11)reports the full comparison\.

Table 1:Black\-box attack query efficiency \(mean±\\pmstd over five runs\)\. Full protocol details are deferred to Appendix[G](https://arxiv.org/html/2609.22115#A7)\.Table[1](https://arxiv.org/html/2609.22115#S6.T1)keeps the common stabilized R\-AdaZO backbone explicit, with fixedK=2K=2for R\-AdaZO, best sweptKmax=2K\_\{\\max\}=2for StatZO, andKt∈\[1,2\]K\_\{t\}\\in\[1,2\]for ZoAQ\. Appendix[G\.10](https://arxiv.org/html/2609.22115#A7.SS10)justifiesNhist=8N\_\{\\text\{hist\}\}=8, and Appendix[F](https://arxiv.org/html/2609.22115#A6)reports both the original and stabilized StatZO behavior\.

### 6\.3LLM Fine\-Tuning with Forward Passes Only

LLM fine\-tuning tests the same accounting when each function evaluation is a forward pass through a large model\. We fine\-tune OPT\-1\.3B and OPT\-13B on SST\-2 and COPA for 5,000 steps with LoRA under a two\-sided ZOO protocol that uses forward passes only, with three seeds\. Table[2](https://arxiv.org/html/2609.22115#S6.T2)summarizes the resulting trade\-off between FE and quality\.

Table 2:Main LLM fine\-tuning summary over three seeds\. FE denotes forward evaluations; full metrics and theKt∈\[1,2\]K\_\{t\}\\in\[1,2\]endpoint are deferred to Table[13](https://arxiv.org/html/2609.22115#A7.T13)\.ZoAQ withKt∈\[1,4\]K\_\{t\}\\in\[1,4\]is the main operating point\. Across the four OPT/task pairs in Table[2](https://arxiv.org/html/2609.22115#S6.T2), it saves 43–46% FE relative to fixedK=4K=4\. The allocation is repeated at each of the 5,000 steps rather than chosen once as a smaller fixed direction count\. On OPT\-1\.3B SST\-2, it matches R\-AdaZO accuracy and slightly improves best evaluation loss; on COPA, it keeps accuracy close while accepting higher loss; on OPT\-13B SST\-2, it trails R\-AdaZO with a fixed budget in both metrics\. These results show FE savings relative to fixedK=4K=4, while the quality trade\-off varies by task\. Reporting both quantities makes the saved computation and resulting task quality directly comparable\. Appendix[G\.6](https://arxiv.org/html/2609.22115#A7.SS6)gives FE accounting, hyperparameters, full metrics, and the aggressiveKt∈\[1,2\]K\_\{t\}\\in\[1,2\]endpoint; Appendix[F](https://arxiv.org/html/2609.22115#A6), Sections[G\.9](https://arxiv.org/html/2609.22115#A7.SS9)–[G\.10](https://arxiv.org/html/2609.22115#A7.SS10), and Appendix[H](https://arxiv.org/html/2609.22115#A8)provide the related stability and sensitivity checks\.

#### Reuse and staleness across regimes\.

Sweeps over the history window expose the balance predicted by the analysis of stored responses\. On MNIST attacks, average queries decrease from 374\.4 atNhist=4N\_\{\\text\{hist\}\}=4to 319\.6 atNhist=8N\_\{\\text\{hist\}\}=8, then increase to 349\.2 atNhist=12N\_\{\\text\{hist\}\}=12\. On OPT\-1\.3B, enlarging the main window from 15 to 24 reduces FE by 3\.00% on SST\-2 and 3\.67% on COPA, with changes in loss and accuracy that vary by task\. The best intermediate window is consistent with the capacity trade\-off in Eq\.[12](https://arxiv.org/html/2609.22115#S5.E12)\. Together, these results show that the balance between reuse and staleness depends on the regime; Tables[18](https://arxiv.org/html/2609.22115#A7.T18)and[14](https://arxiv.org/html/2609.22115#A7.T14)report the full sweeps\.

The controlled objective switch probes the complementary case in which retained records suddenly become stale\. When the objective changes from Rosenbrock to Levy, the effective threshold drops with the consistency mismatch, failed tests add fresh evidence, and ZoAQ reaches a lower final loss than R\-AdaZO in this test\. The controller therefore refreshes its evidence instead of remaining locked to the previous history\. Together, the window and switch tests show that useful reuse depends on current movement rather than a fixed history length, consistent with the staleness quantity in Eq\.[9](https://arxiv.org/html/2609.22115#S5.E9)\. Appendix[H\.3](https://arxiv.org/html/2609.22115#A8.SS3)gives the protocol and trajectories\.

## 7Conclusion

ZoAQ uses acquired responses as evidence for both updates and allocation\. Retained records join fresh directions in each candidate, and failed EMA consistency tests trigger additional queries\. Our analysis identifies when the gain in concentration exceeds staleness and when the first passing candidate supports descent under a sufficient local budget\. ZoAQ reduces queries by 43–48% on synthetic objectives, delivers 4\.77×\\timesand 1\.61×\\timesattack speedups at 100% success, and saves 43–46% FE in OPT fine\-tuning with quality changes reported for each task\. The history window and controlled objective switch show how the controller exploits useful records and refreshes stale ones, supporting query reuse as a practical basis for adapting local ZOO budgets\.

## References

- Bollapragada & Wild \(2023\)Raghu Bollapragada and Stefan M\. Wild\.Adaptive sampling quasi\-Newton methods for zeroth\-order stochastic optimization\.*Mathematical Programming Computation*, 15\(2\):327–364, 2023\.doi:10\.1007/s12532\-023\-00233\-9\.URL[https://doi\.org/10\.1007/s12532\-023\-00233\-9](https://doi.org/10.1007/s12532-023-00233-9)\.
- Bollapragada et al\. \(2024\)Raghu Bollapragada, Cem Karamanli, and Stefan M\. Wild\.Derivative\-free optimization via adaptive sampling strategies, 2024\.URL[https://arxiv\.org/abs/2404\.11893](https://arxiv.org/abs/2404.11893)\.
- Byrd et al\. \(2012\)Richard H\. Byrd, Gillian M\. Chin, Jorge Nocedal, and Yuchen Wu\.Sample size selection in optimization methods for machine learning\.*Math\. Program\.*, 134\(1\):127–155, 2012\.doi:10\.1007/S10107\-012\-0572\-5\.URL[https://doi\.org/10\.1007/s10107\-012\-0572\-5](https://doi.org/10.1007/s10107-012-0572-5)\.
- Chen et al\. \(2017\)Pin\-Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho\-Jui Hsieh\.Zoo: Zeroth order optimization based black\-box attacks to deep neural networks without training substitute models\.In*Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security*, AISec ’17, pp\. 15–26, New York, NY, USA, 2017\. Association for Computing Machinery\.ISBN 9781450352024\.doi:10\.1145/3128572\.3140448\.URL[https://doi\.org/10\.1145/3128572\.3140448](https://doi.org/10.1145/3128572.3140448)\.
- Chen et al\. \(2019\)Xiangyi Chen, Sijia Liu, Kaidi Xu, Xingguo Li, Xue Lin, Mingyi Hong, and David Cox\.ZO\-AdaMM: zeroth\-order adaptive momentum method for black\-box optimization\.In*Proceedings of the 33rd International Conference on Neural Information Processing Systems*, Red Hook, NY, USA, 2019\. Curran Associates Inc\.
- Conn et al\. \(2000\)Andrew R\. Conn, Nicholas I\. M\. Gould, and Philippe L\. Toint\.*Trust Region Methods*\.Society for Industrial and Applied Mathematics, 2000\.doi:10\.1137/1\.9780898719857\.URL[https://epubs\.siam\.org/doi/abs/10\.1137/1\.9780898719857](https://epubs.siam.org/doi/abs/10.1137/1.9780898719857)\.
- Conn et al\. \(2009\)Andrew R\. Conn, Katya Scheinberg, and Luis N\. Vicente\.*Introduction to Derivative\-Free Optimization*\.Society for Industrial and Applied Mathematics, 2009\.doi:10\.1137/1\.9780898718768\.URL[https://epubs\.siam\.org/doi/abs/10\.1137/1\.9780898718768](https://epubs.siam.org/doi/abs/10.1137/1.9780898718768)\.
- Cutkosky & Mehta \(2020\)Ashok Cutkosky and Harsh Mehta\.Momentum improves normalized SGD\.In*Proceedings of the 37th International Conference on Machine Learning*, volume 119 of*Proceedings of Machine Learning Research*, pp\. 2260–2268\. PMLR, 2020\.
- Cutkosky & Mehta \(2021\)Ashok Cutkosky and Harsh Mehta\.High\-probability bounds for non\-convex stochastic optimization with heavy tails\.In*Advances in Neural Information Processing Systems*, volume 34, 2021\.
- Ghadimi & Lan \(2013\)Saeed Ghadimi and Guanghui Lan\.Stochastic first\- and zeroth\-order methods for nonconvex stochastic programming\.*SIAM Journal on Optimization*, 23\(4\):2341–2368, 2013\.doi:10\.1137/120880811\.URL[https://doi\.org/10\.1137/120880811](https://doi.org/10.1137/120880811)\.
- Hu et al\. \(2022\)Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen\-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen\.LoRA: Low\-rank adaptation of large language models\.In*International Conference on Learning Representations*, 2022\.URL[https://openreview\.net/forum?id=nZeVKeeFYf9](https://openreview.net/forum?id=nZeVKeeFYf9)\.
- Kingma & Ba \(2014\)Diederik P\. Kingma and Jimmy Ba\.Adam: A method for stochastic optimization\.*CoRR*, abs/1412\.6980, 2014\.URL[https://api\.semanticscholar\.org/CorpusID:6628106](https://api.semanticscholar.org/CorpusID:6628106)\.
- Krizhevsky & Hinton \(2009\)Alex Krizhevsky and Geoffrey Hinton\.Learning multiple layers of features from tiny images\.Technical report, University of Toronto, 2009\.URL[https://api\.semanticscholar\.org/CorpusID:18268744](https://api.semanticscholar.org/CorpusID:18268744)\.
- LeCun et al\. \(1998\)Y\. LeCun, L\. Bottou, Y\. Bengio, and P\. Haffner\.Gradient\-based learning applied to document recognition\.*Proceedings of the IEEE*, 86\(11\):2278–2324, 1998\.doi:10\.1109/5\.726791\.
- Lin et al\. \(2025\)Wei Lin, Qingyu Song, and Hong Xu\.The multi\-query paradox in zeroth\-order optimization, 2025\.URL[https://arxiv\.org/abs/2509\.15552](https://arxiv.org/abs/2509.15552)\.
- Liu et al\. \(2018\)Sijia Liu, Bhavya Kailkhura, Pin\-Yu Chen, Paishun Ting, Shiyu Chang, and Lisa Amini\.Zeroth\-order stochastic variance reduction for nonconvex optimization, 2018\.URL[https://arxiv\.org/abs/1805\.10367](https://arxiv.org/abs/1805.10367)\.
- Malladi et al\. \(2023\)Sadhika Malladi, Tianyu Gao, Eshaan Nichani, Alex Damian, Jason D\. Lee, Danqi Chen, and Sanjeev Arora\.Fine\-tuning language models with just forward passes\.In*Thirty\-seventh Conference on Neural Information Processing Systems*, 2023\.URL[https://openreview\.net/forum?id=Vota6rFhBQ](https://openreview.net/forum?id=Vota6rFhBQ)\.
- Nesterov & Spokoiny \(2017\)Yurii Nesterov and Vladimir Spokoiny\.Random gradient\-free minimization of convex functions\.*Found\. Comput\. Math\.*, 17\(2\):527–566, April 2017\.ISSN 1615\-3375\.doi:10\.1007/s10208\-015\-9296\-2\.URL[https://doi\.org/10\.1007/s10208\-015\-9296\-2](https://doi.org/10.1007/s10208-015-9296-2)\.
- Qiu et al\. \(2025\)Junbin Qiu, Zhengpeng Xie, Xiangda Yan, Yongjie Yang, and Yao Shu\.Zeroth\-order optimization is secretly single\-step policy optimization\.In*Tiny Titans: The next wave of On\-Device Learning for Foundational Models \(TTODLer\-FM\)*, 2025\.URL[https://openreview\.net/forum?id=HQwuvp7nc0](https://openreview.net/forum?id=HQwuvp7nc0)\.
- Roemmele et al\. \(2011\)Melissa Roemmele, Cosmin Adrian Bejan, and Andrew S\. Gordon\.Choice of plausible alternatives: An evaluation of commonsense causal reasoning\.In*AAAI Spring Symposium: Logical Formalizations of Commonsense Reasoning*, 2011\.URL[https://people\.ict\.usc\.edu/˜gordon/copa\.html](https://people.ict.usc.edu/~gordon/copa.html)\.
- Shu et al\. \(2025\)Yao Shu, Qixin Zhang, Kun He, and Zhongxiang Dai\.Refining adaptive zeroth\-order optimization at ease\.In*Forty\-second International Conference on Machine Learning*, 2025\.URL[https://openreview\.net/forum?id=NpIIbrg361](https://openreview.net/forum?id=NpIIbrg361)\.
- Spall \(1992\)J\.C\. Spall\.Multivariate stochastic approximation using a simultaneous perturbation gradient approximation\.*IEEE Transactions on Automatic Control*, 37\(3\):332–341, 1992\.doi:10\.1109/9\.119632\.
- Wang et al\. \(2018\)Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman\.GLUE: A multi\-task benchmark and analysis platform for natural language understanding\.In Tal Linzen, Grzegorz Chrupała, and Afra Alishahi \(eds\.\),*Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP*, pp\. 353–355, Brussels, Belgium, November 2018\. Association for Computational Linguistics\.doi:10\.18653/v1/W18\-5446\.URL[https://aclanthology\.org/W18\-5446/](https://aclanthology.org/W18-5446/)\.
- Zhang et al\. \(2022\)Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, Todor Mihaylov, Myle Ott, Sam Shleifer, Kurt Shuster, Daniel Simig, Punit Singh Koura, Anjali Sridhar, Tianlu Wang, and Luke Zettlemoyer\.OPT: Open pre\-trained transformer language models, 2022\.URL[https://arxiv\.org/abs/2205\.01068](https://arxiv.org/abs/2205.01068)\.

## Appendix AAssumptions and Preliminaries

This appendix fixes the notation and probability interfaces used throughout the proofs\. The analysis uses paired Gaussian two\-sided responses stored at their acquisition iterates\. Evaluation counts for each protocol are reported with the experiments rather than folded into the estimator definition\.

### A\.1Proof Notation

Objective and gradients\.F:ℝd→ℝF:\\mathbb\{R\}^\{d\}\\to\\mathbb\{R\}is the black\-box objective,𝜽t\\bm\{\\theta\}\_\{t\}is the iterate, and

Fμ​\(𝜽\)≜𝔼𝒖∼𝒩⁡\(0,𝑰d\)​\[F⁡\(𝜽\+μ​𝒖\)\]F\_\{\\mu\}\(\\bm\{\\theta\}\)\\triangleq\\mathbb\{E\}\_\{\\bm\{u\}\\sim\\mathcal\{N\}\(0,\\bm\{I\}\_\{d\}\)\}\[F\(\\bm\{\\theta\}\+\\mu\\bm\{u\}\)\]\(22\)is its Gaussian smoothing at radiusμ\>0\\mu\>0\. We writeht≜∇Fμ​\(𝜽t\)h\_\{t\}\\triangleq\\nabla F\_\{\\mu\}\(\\bm\{\\theta\}\_\{t\}\)\. The constantsLfL\_\{f\}andLLare gradient\-Lipschitz constants forFFandFμF\_\{\\mu\}, respectively\.

Acquisition records\.Directions are indexed in acquisition order\. Thejjth record is sampled at stepaja\_\{j\}after conditioning on the pre\-sampling informationℱj−1\\mathcal\{F\}\_\{j\-1\}\. It contains𝒖j\|ℱj−1∼𝒩⁡\(0,𝑰d\)\\bm\{u\}\_\{j\}\\mid\\mathcal\{F\}\_\{j\-1\}\\sim\\mathcal\{N\}\(0,\\bm\{I\}\_\{d\}\)and the paired responserj≜rμ​\(𝜽aj,𝒖j\)r\_\{j\}\\triangleq r\_\{\\mu\}\(\\bm\{\\theta\}\_\{a\_\{j\}\},\\bm\{u\}\_\{j\}\)\. Its vector contribution, conditional mean, and centered acquisition noise are

Xj≜rj​𝒖j,hj≜∇Fμ​\(𝜽aj\),ξj≜Xj−hj\.X\_\{j\}\\triangleq r\_\{j\}\\bm\{u\}\_\{j\},\\qquad h\_\{j\}\\triangleq\\nabla F\_\{\\mu\}\(\\bm\{\\theta\}\_\{a\_\{j\}\}\),\\qquad\\xi\_\{j\}\\triangleq X\_\{j\}\-h\_\{j\}\.\(23\)
Candidate estimates\.At steptt,KKis the cumulative number of fresh directions acquired so far,ℋt​\(K\)\\mathcal\{H\}\_\{t\}\(K\)is the candidate record set, and𝒥t​\(K\)\\mathcal\{J\}\_\{t\}\(K\)contains its acquisition indices\. Withnt​\(K\)=\|𝒥t​\(K\)\|n\_\{t\}\(K\)=\|\\mathcal\{J\}\_\{t\}\(K\)\|,

𝒈t​\(K\)≜1nt​\(K\)​∑j∈𝒥t​\(K\)Xj\.\\bm\{g\}\_\{t\}\(K\)\\triangleq\\frac\{1\}\{n\_\{t\}\(K\)\}\\sum\_\{j\\in\\mathcal\{J\}\_\{t\}\(K\)\}X\_\{j\}\.\(24\)The controller searches𝒦=\{Kmin,Kmin\+Δ​K,…,Kmax\}\\mathcal\{K\}=\\\{K\_\{\\min\},K\_\{\\min\}\+\\Delta K,\\ldots,K\_\{\\max\}\\\}and acceptsKtK\_\{t\}, after which𝒈t≜𝒈t​\(Kt\)\\bm\{g\}\_\{t\}\\triangleq\\bm\{g\}\_\{t\}\(K\_\{t\}\)\.

Momentum and path\.Accepted estimates form𝒎t=β1​𝒎t−1\+\(1−β1\)​𝒈t\\bm\{m\}\_\{t\}=\\beta\_\{1\}\\bm\{m\}\_\{t\-1\}\+\(1\-\\beta\_\{1\}\)\\bm\{g\}\_\{t\}\. Its debiased version is𝒎~t≜𝒎t/\(1−β1t\)\\widetilde\{\\bm\{m\}\}\_\{t\}\\triangleq\\bm\{m\}\_\{t\}/\(1\-\\beta\_\{1\}^\{t\}\)\. The score isst​\(K\)≜cos⁡\(𝒈t​\(K\),𝒎t−1\)s\_\{t\}\(K\)\\triangleq\\cos\(\\bm\{g\}\_\{t\}\(K\),\\bm\{m\}\_\{t\-1\}\), andτt−1\\tau\_\{t\-1\}is the threshold used at steptt\. The realized path increment isℓt≜‖𝜽t\+1−𝜽t‖\\ell\_\{t\}\\triangleq\\\|\\bm\{\\theta\}\_\{t\+1\}\-\\bm\{\\theta\}\_\{t\}\\\|\.

### A\.2Regularity and Smoothing

###### Assumption A\.1\(Smooth Objective and Surrogate\)\.

The original objectiveFFis differentiable withLfL\_\{f\}\-Lipschitz gradient, andFμF\_\{\\mu\}has anLL\-Lipschitz gradient on the region analyzed\. Hence

Fμ​\(𝜽′\)≤Fμ​\(𝜽\)\+⟨∇Fμ​\(𝜽\),𝜽′−𝜽⟩\+L2​‖𝜽′−𝜽‖2\.F\_\{\\mu\}\(\\bm\{\\theta\}^\{\\prime\}\)\\leq F\_\{\\mu\}\(\\bm\{\\theta\}\)\+\\langle\\nabla F\_\{\\mu\}\(\\bm\{\\theta\}\),\\bm\{\\theta\}^\{\\prime\}\-\\bm\{\\theta\}\\rangle\+\\frac\{L\}\{2\}\\\|\\bm\{\\theta\}^\{\\prime\}\-\\bm\{\\theta\}\\\|^\{2\}\.\(25\)

###### Lemma A\.2\(Smoothing Bias\)\.

Under Assumption[A\.1](https://arxiv.org/html/2609.22115#A1.Thmtheorem1),

‖∇Fμ​\(𝜽\)−∇F​\(𝜽\)‖≤μ​Lf​d\.\\\|\\nabla F\_\{\\mu\}\(\\bm\{\\theta\}\)\-\\nabla F\(\\bm\{\\theta\}\)\\\|\\leq\\mu L\_\{f\}\\sqrt\{d\}\.\(26\)Thus anϵ\\epsilon\-stationary point ofFμF\_\{\\mu\}is an\(ϵ\+μ​Lf​d\)\(\\epsilon\+\\mu L\_\{f\}\\sqrt\{d\}\)\-stationary point ofFF\.

###### Proof\.

Differentiation under the Gaussian expectation gives∇Fμ​\(𝜽\)=𝔼⁡\[∇F​\(𝜽\+μ​𝒖\)\]\\nabla F\_\{\\mu\}\(\\bm\{\\theta\}\)=\\mathbb\{E\}\[\\nabla F\(\\bm\{\\theta\}\+\\mu\\bm\{u\}\)\]\. Gradient Lipschitzness and𝔼​‖𝒖‖≤𝔼​‖𝒖‖2=d\\mathbb\{E\}\\\|\\bm\{u\}\\\|\\leq\\sqrt\{\\mathbb\{E\}\\\|\\bm\{u\}\\\|^\{2\}\}=\\sqrt\{d\}prove Eq\.[26](https://arxiv.org/html/2609.22115#A1.E26)\. ∎

### A\.3Paired Gaussian Contributions

For𝒖∼𝒩⁡\(0,𝑰d\)\\bm\{u\}\\sim\\mathcal\{N\}\(0,\\bm\{I\}\_\{d\}\), define

rμ​\(𝜽,𝒖\)≜F⁡\(𝜽\+μ​𝒖\)−F⁡\(𝜽−μ​𝒖\)2​μ,𝒈μ​\(𝜽,𝒖\)≜rμ​\(𝜽,𝒖\)​𝒖\.r\_\{\\mu\}\(\\bm\{\\theta\},\\bm\{u\}\)\\triangleq\\frac\{F\(\\bm\{\\theta\}\+\\mu\\bm\{u\}\)\-F\(\\bm\{\\theta\}\-\\mu\\bm\{u\}\)\}\{2\\mu\},\\qquad\\bm\{g\}\_\{\\mu\}\(\\bm\{\\theta\},\\bm\{u\}\)\\triangleq r\_\{\\mu\}\(\\bm\{\\theta\},\\bm\{u\}\)\\bm\{u\}\.\(27\)An acquired record stores a reproducible seed for𝒖\\bm\{u\}and its scalar response\. Reuse reconstructs the direction and reuses the scalar observed at acquisition without evaluatingFFagain\.

###### Lemma A\.3\(Mean Paired Contribution\)\.

Whenever Gaussian differentiation is valid,

𝔼𝒖​\[𝒈μ​\(𝜽,𝒖\)\]=∇Fμ​\(𝜽\)\.\\mathbb\{E\}\_\{\\bm\{u\}\}\[\\bm\{g\}\_\{\\mu\}\(\\bm\{\\theta\},\\bm\{u\}\)\]=\\nabla F\_\{\\mu\}\(\\bm\{\\theta\}\)\.\(28\)

###### Proof\.

Gaussian symmetry gives

𝔼𝒖​\[𝒈μ​\(𝜽,𝒖\)\]=1μ​𝔼𝒖​\[F⁡\(𝜽\+μ​𝒖\)​𝒖\]\.\\mathbb\{E\}\_\{\\bm\{u\}\}\[\\bm\{g\}\_\{\\mu\}\(\\bm\{\\theta\},\\bm\{u\}\)\]=\\frac\{1\}\{\\mu\}\\mathbb\{E\}\_\{\\bm\{u\}\}\[F\(\\bm\{\\theta\}\+\\mu\\bm\{u\}\)\\bm\{u\}\]\.\(29\)Stein’s identity identifies the right\-hand side with∇Fμ​\(𝜽\)\\nabla F\_\{\\mu\}\(\\bm\{\\theta\}\)\. ∎

###### Lemma A\.4\(Local Second\-Moment Scale\)\.

Under Assumption[A\.1](https://arxiv.org/html/2609.22115#A1.Thmtheorem1),

𝔼𝒖​‖𝒈μ​\(𝜽,𝒖\)‖2≤2​\(d\+2\)​‖∇F​\(𝜽\)‖2\+Lf2​μ22​d​\(d\+2\)​\(d\+4\)\.\\mathbb\{E\}\_\{\\bm\{u\}\}\\\|\\bm\{g\}\_\{\\mu\}\(\\bm\{\\theta\},\\bm\{u\}\)\\\|^\{2\}\\leq 2\(d\+2\)\\\|\\nabla F\(\\bm\{\\theta\}\)\\\|^\{2\}\+\\frac\{L\_\{f\}^\{2\}\\mu^\{2\}\}\{2\}d\(d\+2\)\(d\+4\)\.\(30\)Consequently, for a universal constantC\>0C\>0,

𝔼𝒖​‖𝒈μ​\(𝜽,𝒖\)−∇Fμ​\(𝜽\)‖2≤C⁡\(d​‖∇Fμ​\(𝜽\)‖2\+Lf2​μ2​d3\)\.\\mathbb\{E\}\_\{\\bm\{u\}\}\\\|\\bm\{g\}\_\{\\mu\}\(\\bm\{\\theta\},\\bm\{u\}\)\-\\nabla F\_\{\\mu\}\(\\bm\{\\theta\}\)\\\|^\{2\}\\leq C\\left\(d\\\|\\nabla F\_\{\\mu\}\(\\bm\{\\theta\}\)\\\|^\{2\}\+L\_\{f\}^\{2\}\\mu^\{2\}d^\{3\}\\right\)\.\(31\)

###### Proof\.

Letg⋆=∇F​\(𝜽\)g^\{\\star\}=\\nabla F\(\\bm\{\\theta\}\)\. The fundamental theorem of calculus gives

rμ​\(𝜽,𝒖\)=⟨g⋆,𝒖⟩\+ζ⁡\(𝜽,𝒖\),\|ζ⁡\(𝜽,𝒖\)\|≤Lf​μ2​‖𝒖‖2\.r\_\{\\mu\}\(\\bm\{\\theta\},\\bm\{u\}\)=\\langle g^\{\\star\},\\bm\{u\}\\rangle\+\\zeta\(\\bm\{\\theta\},\\bm\{u\}\),\\qquad\|\\zeta\(\\bm\{\\theta\},\\bm\{u\}\)\|\\leq\\frac\{L\_\{f\}\\mu\}\{2\}\\\|\\bm\{u\}\\\|^\{2\}\.\(32\)Therefore

‖𝒈μ​\(𝜽,𝒖\)‖2≤2​⟨g⋆,𝒖⟩2​‖𝒖‖2\+Lf2​μ22​‖𝒖‖6\.\\\|\\bm\{g\}\_\{\\mu\}\(\\bm\{\\theta\},\\bm\{u\}\)\\\|^\{2\}\\leq 2\\langle g^\{\\star\},\\bm\{u\}\\rangle^\{2\}\\\|\\bm\{u\}\\\|^\{2\}\+\\frac\{L\_\{f\}^\{2\}\\mu^\{2\}\}\{2\}\\\|\\bm\{u\}\\\|^\{6\}\.\(33\)For a standard Gaussian vector,

𝔼⁡\[⟨g⋆,𝒖⟩2​‖𝒖‖2\]=\(d\+2\)​‖g⋆‖2,𝔼​‖𝒖‖6=d⁡\(d\+2\)​\(d\+4\)\.\\mathbb\{E\}\[\\langle g^\{\\star\},\\bm\{u\}\\rangle^\{2\}\\\|\\bm\{u\}\\\|^\{2\}\]=\(d\+2\)\\\|g^\{\\star\}\\\|^\{2\},\\qquad\\mathbb\{E\}\\\|\\bm\{u\}\\\|^\{6\}=d\(d\+2\)\(d\+4\)\.\(34\)This proves Eq\.[30](https://arxiv.org/html/2609.22115#A1.E30)\. Lemma[A\.3](https://arxiv.org/html/2609.22115#A1.Thmtheorem3), Eq\.[26](https://arxiv.org/html/2609.22115#A1.E26), and\(a\+b\)2≤2​a2\+2​b2\(a\+b\)^\{2\}\\leq 2a^\{2\}\+2b^\{2\}then give Eq\.[31](https://arxiv.org/html/2609.22115#A1.E31)after collecting constants\. ∎

### A\.4Probability Interfaces

###### Assumption A\.5\(Second Moments at Acquisition\)\.

For every acquired record,

𝔼⁡\[ξj∣ℱj−1\]=0,𝔼⁡\[‖ξj‖2∣ℱj−1\]≤σj2,\\mathbb\{E\}\[\\xi\_\{j\}\\mid\\mathcal\{F\}\_\{j\-1\}\]=0,\\qquad\\mathbb\{E\}\[\\\|\\xi\_\{j\}\\\|^\{2\}\\mid\\mathcal\{F\}\_\{j\-1\}\]\\leq\\sigma\_\{j\}^\{2\},\(35\)whereσj\\sigma\_\{j\}isℱj−1\\mathcal\{F\}\_\{j\-1\}\-measurable\. Lemma[A\.4](https://arxiv.org/html/2609.22115#A1.Thmtheorem4)permits

σj2=C⁡\(d​‖hj‖2\+Lf2​μ2​d3\)\\sigma\_\{j\}^\{2\}=C\\left\(d\\\|h\_\{j\}\\\|^\{2\}\+L\_\{f\}^\{2\}\\mu^\{2\}d^\{3\}\\right\)\(36\)for the paired Gaussian model\.

###### Assumption A\.6\(Conditional Bernstein Tails\)\.

There areℱj−1\\mathcal\{F\}\_\{j\-1\}\-measurableνj,bj\>0\\nu\_\{j\},b\_\{j\}\>0such that, for every deterministic unit vector𝒗\\bm\{v\}and\|λ\|<1/bj\|\\lambda\|<1/b\_\{j\},

𝔼⁡\[exp⁡\(λ⁡⟨𝒗,ξj⟩\)\|ℱj−1\]≤exp⁡\(λ2​νj22​\(1−bj​\|λ\|\)\)\.\\mathbb\{E\}\\\!\\left\[\\exp\(\\lambda\\langle\\bm\{v\},\\xi\_\{j\}\\rangle\)\\middle\|\\mathcal\{F\}\_\{j\-1\}\\right\]\\leq\\exp\\\!\\left\(\\frac\{\\lambda^\{2\}\\nu\_\{j\}^\{2\}\}\{2\(1\-b\_\{j\}\|\\lambda\|\)\}\\right\)\.\(37\)

The second\-moment route is complete under Assumption[A\.5](https://arxiv.org/html/2609.22115#A1.Thmtheorem5)\. Assumption[A\.6](https://arxiv.org/html/2609.22115#A1.Thmtheorem6)is a separate stronger premise used only for concentration with logarithmic dependence on confidence; it is not inferred from a variance bound\.

## Appendix BStored\-Response Estimation

This section establishes the estimation guarantee that supports the rest of the theory\. A stored\-response candidate differs from the current smoothed gradient through two terms: acquisition noise, whose concentration can improve as records accumulate, and staleness, which increases as retained records move farther from the current iterate\.

The analysis uses the objects at acquisition defined in Appendix[A](https://arxiv.org/html/2609.22115#A1)and FIFO pruning by pairs after acceptance\. The main event is uniform over all candidates that the controller may inspect, so it remains valid after selection of the first passing candidate\. We give a complete second\-moment bound and a sharper version with logarithmic dependence on confidence under the additional conditional tail assumption\.

### B\.1A Uniform Error Bound for Stored\-Response Candidates

The controller inspects a nested sequence of candidates and accepts the first one that passes\. We therefore control every candidate that can be formed, rather than analyze a fixed budget and substitute the selected budget afterward\.

Under FIFO pruning by pairs after acceptance, each candidate index set𝒥t​\(K\)\\mathcal\{J\}\_\{t\}\(K\)is an interval in acquisition order\. Up to a horizonTT, letℑT\\mathfrak\{I\}\_\{T\}contain every interval of acquisition indices that can occur for anyt≤Tt\\leq TandK∈𝒦K\\in\\mathcal\{K\}, and writeMT≜\|ℑT\|M\_\{T\}\\triangleq\|\\mathfrak\{I\}\_\{T\}\|\. Since at mostT​KmaxTK\_\{\\max\}directions are acquired, one may use the deterministic bound

MT≤T​Kmax​\(T​Kmax\+1\)2\.M\_\{T\}\\leq\\frac\{TK\_\{\\max\}\(TK\_\{\\max\}\+1\)\}\{2\}\.\(38\)For a realized candidate, define its total staleness

At​\(K\)≜∑j∈𝒥t​\(K\)‖𝜽t−𝜽aj‖\.A\_\{t\}\(K\)\\triangleq\\sum\_\{j\\in\\mathcal\{J\}\_\{t\}\(K\)\}\\\|\\bm\{\\theta\}\_\{t\}\-\\bm\{\\theta\}\_\{a\_\{j\}\}\\\|\.\(39\)
###### Lemma B\.1\(Uniform Candidate Error\)\.

Suppose Assumptions[A\.1](https://arxiv.org/html/2609.22115#A1.Thmtheorem1)and[A\.5](https://arxiv.org/html/2609.22115#A1.Thmtheorem5)hold\. For each admissible candidate, letV¯t​\(K\)\\overline\{V\}\_\{t\}\(K\)be a deterministic upper bound on∑j∈𝒥t​\(K\)σj2\\sum\_\{j\\in\\mathcal\{J\}\_\{t\}\(K\)\}\\sigma\_\{j\}^\{2\}, and define

q2​\(t,K,δ\)≜1nt​\(K\)​MT​V¯t​\(K\)δ\.q\_\{2\}\(t,K,\\delta\)\\triangleq\\frac\{1\}\{n\_\{t\}\(K\)\}\\sqrt\{\\frac\{M\_\{T\}\\overline\{V\}\_\{t\}\(K\)\}\{\\delta\}\}\.\(40\)Then, with probability at least1−δ1\-\\delta, every candidate inspected up to stepTTsatisfies

‖𝒈t​\(K\)−ht‖≤q2​\(t,K,δ\)\+L​At​\(K\)nt​\(K\)\.\\\|\\bm\{g\}\_\{t\}\(K\)\-h\_\{t\}\\\|\\leq q\_\{2\}\(t,K,\\delta\)\+\\frac\{LA\_\{t\}\(K\)\}\{n\_\{t\}\(K\)\}\.\(41\)
If Assumption[A\.6](https://arxiv.org/html/2609.22115#A1.Thmtheorem6)also holds, letV¯tν​\(K\)\\overline\{V\}\_\{t\}^\{\\nu\}\(K\)andb¯t​\(K\)\\overline\{b\}\_\{t\}\(K\)be deterministic bounds on∑j∈𝒥t​\(K\)νj2\\sum\_\{j\\in\\mathcal\{J\}\_\{t\}\(K\)\}\\nu\_\{j\}^\{2\}andmaxj∈𝒥t​\(K\)⁡bj\\max\_\{j\\in\\mathcal\{J\}\_\{t\}\(K\)\}b\_\{j\}\. There is a universal constantc\>0c\>0such that Eq\.[41](https://arxiv.org/html/2609.22115#A2.E41)also holds withq2q\_\{2\}replaced by

qB​\(t,K,δ\)≜cnt​\(K\)​\[V¯tν​\(K\)​\(d\+log⁡MTδ\)\+b¯t​\(K\)​\(d\+log⁡MTδ\)\]\.q\_\{\\text\{B\}\}\(t,K,\\delta\)\\triangleq\\frac\{c\}\{n\_\{t\}\(K\)\}\\left\[\\sqrt\{\\overline\{V\}\_\{t\}^\{\\nu\}\(K\)\\left\(d\+\\log\\frac\{M\_\{T\}\}\{\\delta\}\\right\)\}\+\\overline\{b\}\_\{t\}\(K\)\\left\(d\+\\log\\frac\{M\_\{T\}\}\{\\delta\}\\right\)\\right\]\.\(42\)

###### Proof\.

For any candidate, the definitions in Appendix[A](https://arxiv.org/html/2609.22115#A1)give the exact decomposition

𝒈t​\(K\)−ht=1nt​\(K\)​∑j∈𝒥t​\(K\)ξj\+1nt​\(K\)​∑j∈𝒥t​\(K\)\(hj−ht\)\.\\bm\{g\}\_\{t\}\(K\)\-h\_\{t\}=\\frac\{1\}\{n\_\{t\}\(K\)\}\\sum\_\{j\\in\\mathcal\{J\}\_\{t\}\(K\)\}\\xi\_\{j\}\+\\frac\{1\}\{n\_\{t\}\(K\)\}\\sum\_\{j\\in\\mathcal\{J\}\_\{t\}\(K\)\}\(h\_\{j\}\-h\_\{t\}\)\.\(43\)The second term is controlled pathwise\. TheLL\-smoothness ofFμF\_\{\\mu\}yields

‖1nt​\(K\)​∑j∈𝒥t​\(K\)\(hj−ht\)‖≤L​At​\(K\)nt​\(K\)\.\\left\\\|\\frac\{1\}\{n\_\{t\}\(K\)\}\\sum\_\{j\\in\\mathcal\{J\}\_\{t\}\(K\)\}\(h\_\{j\}\-h\_\{t\}\)\\right\\\|\\leq\\frac\{LA\_\{t\}\(K\)\}\{n\_\{t\}\(K\)\}\.\(44\)
Fix an acquisition intervalI∈ℑTI\\in\\mathfrak\{I\}\_\{T\}\. The sequence\{ξj\}\\\{\\xi\_\{j\}\\\}is a martingale\-difference sequence with respect to the acquisition filtration, so its cross terms vanish and

𝔼​‖∑j∈Iξj‖2≤𝔼​∑j∈Iσj2≤V¯t​\(K\),\\mathbb\{E\}\\left\\\|\\sum\_\{j\\in I\}\\xi\_\{j\}\\right\\\|^\{2\}\\leq\\mathbb\{E\}\\sum\_\{j\\in I\}\\sigma\_\{j\}^\{2\}\\leq\\overline\{V\}\_\{t\}\(K\),\(45\)where\(t,K\)\(t,K\)denotes the candidate associated withII\. Markov’s inequality with failure probabilityδ/MT\\delta/M\_\{T\}, followed by a union bound overℑT\\mathfrak\{I\}\_\{T\}, gives Eq\.[40](https://arxiv.org/html/2609.22115#A2.E40)simultaneously for every admissible interval\.

Under Assumption[A\.6](https://arxiv.org/html/2609.22115#A1.Thmtheorem6), scalar martingale Bernstein applied to⟨𝒗,∑j∈Iξj⟩\\langle\\bm\{v\},\\sum\_\{j\\in I\}\\xi\_\{j\}\\ranglegives the usual variance\-plus\-range bound for each fixed unit vector𝒗\\bm\{v\}\. A1/21/2\-net of the unit sphere has at most5d5^\{d\}elements\. Taking a union bound over this net and overℑT\\mathfrak\{I\}\_\{T\}yields Eq\.[42](https://arxiv.org/html/2609.22115#A2.E42)\. Combining either noise radius with Eq\.[44](https://arxiv.org/html/2609.22115#A2.E44)proves the result\. Because the event holds for every admissible interval, it also holds for the adaptively selected first\-passing candidate\. ∎

### B\.2When Stored Responses Reduce the Required Fresh Budget

History is useful only when the reduction in sampling error exceeds the staleness it introduces\. The next result states this comparison at a common fresh budget\.

###### Proposition B\.2\(Reuse\-Benefit Condition\)\.

Fix a stepttand fresh budgetKK\. Suppose the same nonincreasing noise radiusq⁡\(n,δ\)q\(n,\\delta\)bounds an average ofnnadmissible records\. The candidate using only fresh directions containsKKrecords from the current step and has error certificateq⁡\(K,δ\)q\(K,\\delta\)\. The candidate with stored responses usesnt​\(K\)≥Kn\_\{t\}\(K\)\\geq Krecords and has the certificate from Lemma[B\.1](https://arxiv.org/html/2609.22115#A2.Thmtheorem1)\. If

L​At​\(K\)nt​\(K\)≤q⁡\(K,δ\)−q⁡\(nt​\(K\),δ\),\\frac\{LA\_\{t\}\(K\)\}\{n\_\{t\}\(K\)\}\\leq q\(K,\\delta\)\-q\(n\_\{t\}\(K\),\\delta\),\(46\)then the candidate with stored responses has an error certificate no larger than the candidate using only fresh directions at the same fresh query cost\.

###### Proof\.

The candidate using only fresh directions has no acquisition staleness, so its certificate isq⁡\(K,δ\)q\(K,\\delta\)\. Lemma[B\.1](https://arxiv.org/html/2609.22115#A2.Thmtheorem1)bounds the candidate with stored responses by

q⁡\(nt​\(K\),δ\)\+L​At​\(K\)nt​\(K\)\.q\(n\_\{t\}\(K\),\\delta\)\+\\frac\{LA\_\{t\}\(K\)\}\{n\_\{t\}\(K\)\}\.\(47\)Applying Eq\.[46](https://arxiv.org/html/2609.22115#A2.E46)proves the claim\. ∎

FIFO pruning turns the staleness term into an explicit capacity constraint\.

###### Lemma B\.3\(FIFO Staleness Envelope\)\.

Let the retained buffer contain at mostCCdirection records, with pruning applied after each accepted step\. Suppose every accepted step acquires at leastKminK\_\{\\min\}fresh directions andℓr≤ℓ¯\\ell\_\{r\}\\leq\\bar\{\\ell\}over the steps that can contribute to the current buffer\. Once the buffer is full, every retained record is at most

HC≜⌈CKmin⌉H\_\{C\}\\triangleq\\left\\lceil\\frac\{C\}\{K\_\{\\min\}\}\\right\\rceil\(48\)accepted steps old\. Before pruning after acceptance, a candidate with fresh budgetKKtherefore satisfies

nt​\(K\)=C\+K,At​\(K\)≤C​HC​ℓ¯\.n\_\{t\}\(K\)=C\+K,\\qquad A\_\{t\}\(K\)\\leq CH\_\{C\}\\bar\{\\ell\}\.\(49\)

###### Proof\.

During anyHCH\_\{C\}consecutive accepted steps, at leastHC​Kmin≥CH\_\{C\}K\_\{\\min\}\\geq Cnewer records arrive\. FIFO pruning by pairs must therefore remove every older record\. A retained record acquiredrraccepted steps earlier is at distance at most∑sℓs≤r​ℓ¯\\sum\_\{s\}\\ell\_\{s\}\\leq r\\bar\{\\ell\}from𝜽t\\bm\{\\theta\}\_\{t\}\. Summing this bound over at mostCCretained records gives Eq\.[49](https://arxiv.org/html/2609.22115#A2.E49); theKKfresh records contribute zero staleness\. ∎

###### Corollary B\.4\(Interior Capacity Scale\)\.

Suppose the leading sampling radius for a full buffer has the homogeneous format​\(δ\)/Ca\_\{t\}\(\\delta\)/\\sqrt\{C\}, and the average FIFO age iscage​C/Kminc\_\{\\text\{age\}\}C/K\_\{\\min\}for a constantcage\>0c\_\{\\text\{age\}\}\>0\. The leading certificate is then

et​\(C\)=at​\(δ\)C\+cage​L​ℓ¯Kmin​C\.e\_\{t\}\(C\)=\\frac\{a\_\{t\}\(\\delta\)\}\{\\sqrt\{C\}\}\+\\frac\{c\_\{\\text\{age\}\}L\\bar\{\\ell\}\}\{K\_\{\\min\}\}C\.\(50\)Its continuous minimizer is

Ct⋆=\(at​\(δ\)​Kmin2​cage​L​ℓ¯\)2/3\.C\_\{t\}^\{\\star\}=\\left\(\\frac\{a\_\{t\}\(\\delta\)K\_\{\\min\}\}\{2c\_\{\\text\{age\}\}L\\bar\{\\ell\}\}\\right\)^\{2/3\}\.\(51\)Thus the useful history size grows with local noise and refresh rate, but shrinks with smoothness\-weighted movement\. More retained records are not uniformly better\.

###### Proof\.

Differentiate Eq\.[50](https://arxiv.org/html/2609.22115#A2.E50)with respect toCCand set the derivative to zero:

−at​\(δ\)2​C3/2\+cage​L​ℓ¯Kmin=0\.\-\\frac\{a\_\{t\}\(\\delta\)\}\{2C^\{3/2\}\}\+\\frac\{c\_\{\\text\{age\}\}L\\bar\{\\ell\}\}\{K\_\{\\min\}\}=0\.\(52\)Solving forCCgives Eq\.[51](https://arxiv.org/html/2609.22115#A2.E51)\. The implementable capacity is the nearest admissible integer\. ∎

### B\.3Outputs of the Stored\-Response Analysis

The results above reduce the effect of query reuse to one candidate\-specific error certificate\. For either probability route, write

εt​\(K\)≜q⁡\(t,K,δ\)\+L​At​\(K\)nt​\(K\),\\varepsilon\_\{t\}\(K\)\\triangleq q\(t,K,\\delta\)\+\\frac\{LA\_\{t\}\(K\)\}\{n\_\{t\}\(K\)\},\(53\)whereqqis the applicable radius from Lemma[B\.1](https://arxiv.org/html/2609.22115#A2.Thmtheorem1)\. On the simultaneous event,‖𝒈t​\(K\)−ht‖≤εt​\(K\)\\\|\\bm\{g\}\_\{t\}\(K\)\-h\_\{t\}\\\|\\leq\\varepsilon\_\{t\}\(K\)for every inspected candidate, including the first one accepted by the controller\.

Two consequences feed the remaining proofs\. First, Eq\.[46](https://arxiv.org/html/2609.22115#A2.E46)identifies when retained responses improve the certificate at a fixed fresh budget\. Second, Eq\.[51](https://arxiv.org/html/2609.22115#A2.E51)shows how FIFO capacity balances sampling error against staleness induced by movement\. Appendix[C\.1](https://arxiv.org/html/2609.22115#A3.SS1)next propagates the certificates for accepted candidates through the EMA and derives its tracking accuracy\.

#### Movement enters through staleness\.

For every retained record,

‖𝜽t−𝜽aj‖≤∑r=ajt−1ℓr\.\\\|\\bm\{\\theta\}\_\{t\}\-\\bm\{\\theta\}\_\{a\_\{j\}\}\\\|\\leq\\sum\_\{r=a\_\{j\}\}^\{t\-1\}\\ell\_\{r\}\.\(54\)ThusAt​\(K\)A\_\{t\}\(K\)already carries the complete path dependence needed by the stored\-response estimator\. Once a candidate is accepted, Appendix[C\.1](https://arxiv.org/html/2609.22115#A3.SS1)uses its realized certificateεt​\(Kt\)\\varepsilon\_\{t\}\(K\_\{t\}\)together with the EMA\-weighted path length; no separate covariance\-transport margin is required\.

#### Probability interface\.

The analytical estimator directly averages the paired contributionsXj=rj​𝒖jX\_\{j\}=r\_\{j\}\\bm\{u\}\_\{j\}defined in Eq\.[23](https://arxiv.org/html/2609.22115#A1.E23)\. Its statistical input is therefore contained in Lemma[B\.1](https://arxiv.org/html/2609.22115#A2.Thmtheorem1): second moments at acquisition yield the radiusq2q\_\{2\}with polynomial dependence on confidence, while conditional Bernstein tails yield the radiusqBq\_\{\\text\{B\}\}with logarithmic dependence\. All subsequent results condition on the corresponding simultaneous candidate event\.

## Appendix CMomentum Tracking and Directional Control

This section converts the candidate certificates from Appendix[B](https://arxiv.org/html/2609.22115#A2)into a certificate for the momentum\-consistency gate\. The argument is pathwise after the simultaneous candidate event is fixed, so overlapping FIFO buffers and adaptive first\-passing selection introduce no additional independence requirement\.

### C\.1Debiased EMA Tracking

Assume𝒎0=0\\bm\{m\}\_\{0\}=0and𝒎r=β1​𝒎r−1\+\(1−β1\)​𝒈r\\bm\{m\}\_\{r\}=\\beta\_\{1\}\\bm\{m\}\_\{r\-1\}\+\(1\-\\beta\_\{1\}\)\\bm\{g\}\_\{r\}\. Fort≥2t\\geq 2, define

zt−1≜1−β1t−1,𝒎~t−1≜𝒎t−1zt−1,w¯r,t≜\(1−β1\)​β1t−1−rzt−1\.z\_\{t\-1\}\\triangleq 1\-\\beta\_\{1\}^\{t\-1\},\\qquad\\widetilde\{\\bm\{m\}\}\_\{t\-1\}\\triangleq\\frac\{\\bm\{m\}\_\{t\-1\}\}\{z\_\{t\-1\}\},\\qquad\\bar\{w\}\_\{r,t\}\\triangleq\\frac\{\(1\-\\beta\_\{1\}\)\\beta\_\{1\}^\{t\-1\-r\}\}\{z\_\{t\-1\}\}\.\(55\)The weights are nonnegative and sum to one\. Moreover,zt−1\>0z\_\{t\-1\}\>0, so replacing𝒎t−1\\bm\{m\}\_\{t\-1\}by𝒎~t−1\\widetilde\{\\bm\{m\}\}\_\{t\-1\}leaves every cosine score unchanged\.

###### Proposition C\.1\(Pathwise Debiased\-EMA Tracking\)\.

Suppose the final estimate accepted at steprrsatisfies

‖𝒈r−hr‖≤εr\.\\\|\\bm\{g\}\_\{r\}\-h\_\{r\}\\\|\\leq\\varepsilon\_\{r\}\.\(56\)Then

‖𝒎~t−1−ht‖≤∑r<tw¯r,t​εr​L​Dtema,Dtema≜∑r<tw¯r,t​∑s=rt−1ℓs\.\\\|\\widetilde\{\\bm\{m\}\}\_\{t\-1\}\-h\_\{t\}\\\|\\leq\\sum\_\{r<t\}\\bar\{w\}\_\{r,t\}\\varepsilon\_\{r\}LD\_\{t\}^\{\\text\{ema\}\},\\qquad D\_\{t\}^\{\\text\{ema\}\}\\triangleq\\sum\_\{r<t\}\\bar\{w\}\_\{r,t\}\\sum\_\{s=r\}^\{t\-1\}\\ell\_\{s\}\.\(57\)In particular, ifεr≤ε¯\\varepsilon\_\{r\}\\leq\\bar\{\\varepsilon\}andℓs≤ℓ¯\\ell\_\{s\}\\leq\\bar\{\\ell\}over the contributing steps, then

‖𝒎~t−1−ht‖≤ε¯\+L​ℓ¯​At,β1≤ε¯\+L​ℓ¯1−β1,\\\|\\widetilde\{\\bm\{m\}\}\_\{t\-1\}\-h\_\{t\}\\\|\\leq\\bar\{\\varepsilon\}\+L\\bar\{\\ell\}A\_\{t,\\beta\_\{1\}\}\\leq\\bar\{\\varepsilon\}\+\\frac\{L\\bar\{\\ell\}\}\{1\-\\beta\_\{1\}\},\(58\)where

At,β1=1−t​β1t−1\+\(t−1\)​β1t\(1−β1\)​\(1−β1t−1\)\.A\_\{t,\\beta\_\{1\}\}=\\frac\{1\-t\\beta\_\{1\}^\{t\-1\}\+\(t\-1\)\\beta\_\{1\}^\{t\}\}\{\(1\-\\beta\_\{1\}\)\(1\-\\beta\_\{1\}^\{t\-1\}\)\}\.\(59\)

###### Proof\.

Equation[55](https://arxiv.org/html/2609.22115#A3.E55)gives

𝒎~t−1−ht=∑r<tw¯r,t​\(𝒈r−hr\)\+∑r<tw¯r,t​\(hr−ht\)\.\\widetilde\{\\bm\{m\}\}\_\{t\-1\}\-h\_\{t\}=\\sum\_\{r<t\}\\bar\{w\}\_\{r,t\}\(\\bm\{g\}\_\{r\}\-h\_\{r\}\)\+\\sum\_\{r<t\}\\bar\{w\}\_\{r,t\}\(h\_\{r\}\-h\_\{t\}\)\.\(60\)The first sum is bounded by∑r<tw¯r,t​εr\\sum\_\{r<t\}\\bar\{w\}\_\{r,t\}\\varepsilon\_\{r\}\. Smoothness gives‖hr−ht‖≤L​∑s=rt−1ℓs\\\|h\_\{r\}\-h\_\{t\}\\\|\\leq L\\sum\_\{s=r\}^\{t\-1\}\\ell\_\{s\}, which yields Eq\.[57](https://arxiv.org/html/2609.22115#A3.E57)\. Under uniform bounds, the first weighted sum is at mostε¯\\bar\{\\varepsilon\}, while the second isL​ℓ¯​∑r<tw¯r,t​\(t−r\)L\\bar\{\\ell\}\\sum\_\{r<t\}\\bar\{w\}\_\{r,t\}\(t\-r\)\. Evaluating the finite geometric sum givesAt,β1A\_\{t,\\beta\_\{1\}\}, andAt,β1≤\(1−β1\)−1A\_\{t,\\beta\_\{1\}\}\\leq\(1\-\\beta\_\{1\}\)^\{\-1\}\. ∎

The proposition uses errors of the final estimates, not an independence assumption between them\. On the simultaneous event of Lemma[B\.1](https://arxiv.org/html/2609.22115#A2.Thmtheorem1), one may take

εr=q⁡\(nr​\(Kr\),δ\)\+L​Ar​\(Kr\)nr​\(Kr\)\.\\varepsilon\_\{r\}=q\(n\_\{r\}\(K\_\{r\}\),\\delta\)\+\\frac\{LA\_\{r\}\(K\_\{r\}\)\}\{n\_\{r\}\(K\_\{r\}\)\}\.\(61\)Thus acquisition noise and response staleness enter the EMA with their realized geometric weights\.

###### Corollary C\.2\(Relative Tracking Level\)\.

At any pre\-stationary step with‖ht‖\>0\\\|h\_\{t\}\\\|\>0, define

κt≜∑r<tw¯r,t​εr\+L​Dtema‖ht‖\.\\kappa\_\{t\}\\triangleq\\frac\{\\sum\_\{r<t\}\\bar\{w\}\_\{r,t\}\\varepsilon\_\{r\}\+LD\_\{t\}^\{\\text\{ema\}\}\}\{\\\|h\_\{t\}\\\|\}\.\(62\)Then‖𝐦~t−1−ht‖≤κt​‖ht‖\\\|\\widetilde\{\\bm\{m\}\}\_\{t\-1\}\-h\_\{t\}\\\|\\leq\\kappa\_\{t\}\\\|h\_\{t\}\\\|\. If‖ht‖≥ϵ\\\|h\_\{t\}\\\|\\geq\\epsilon,εr≤ε¯\\varepsilon\_\{r\}\\leq\\bar\{\\varepsilon\}, andℓs≤ℓ¯\\ell\_\{s\}\\leq\\bar\{\\ell\}, the explicit sufficient bound is

κt≤ε¯\+L​ℓ¯/\(1−β1\)ϵ\.\\kappa\_\{t\}\\leq\\frac\{\\bar\{\\varepsilon\}\+L\\bar\{\\ell\}/\(1\-\\beta\_\{1\}\)\}\{\\epsilon\}\.\(63\)

### C\.2Sharp Gate Geometry

The next result characterizes both directions of the consistency test\. Soundness states what a passing score guarantees; completeness states how accurate a candidate must be in order to pass\.

###### Theorem C\.3\(Soundness and Completeness of Momentum Consistency\)\.

Leth≠0h\\neq 0, let an anchorm≠0m\\neq 0satisfy‖m−h‖≤κ​‖h‖\\\|m\-h\\\|\\leq\\kappa\\\|h\\\|for0≤κ<10\\leq\\kappa<1, and letg≠0g\\neq 0\.

Ifcos⁡\(g,m\)≥τ\\cos\(g,m\)\\geq\\tau, then

cos⁡\(g,h\)≥Δ⁡\(τ,κ\)≜τ​1−κ2−κ​1−τ2\.\\cos\(g,h\)\\geq\\Delta\(\\tau,\\kappa\)\\triangleq\\tau\\sqrt\{1\-\\kappa^\{2\}\}\-\\kappa\\sqrt\{1\-\\tau^\{2\}\}\.\(64\)In particular, every passing candidate is positively aligned withhhwheneverτ\>κ\\tau\>\\kappa\.

Conversely, if‖g−h‖≤η​‖h‖\\\|g\-h\\\|\\leq\\eta\\\|h\\\|for0≤η<10\\leq\\eta<1, then

cos⁡\(g,m\)≥1−η2​1−κ2−η​κ\.\\cos\(g,m\)\\geq\\sqrt\{1\-\\eta^\{2\}\}\\sqrt\{1\-\\kappa^\{2\}\}\-\\eta\\kappa\.\(65\)Therefore the gate must pass whenever

η≤η⋆​\(τ,κ\)≜1−τ2​1−κ2−τ​κ\.\\eta\\leq\\eta\_\{\\star\}\(\\tau,\\kappa\)\\triangleq\\sqrt\{1\-\\tau^\{2\}\}\\sqrt\{1\-\\kappa^\{2\}\}\-\\tau\\kappa\.\(66\)

###### Proof\.

The relative anchor error implies∠⁡\(m,h\)≤arcsin⁡κ\\angle\(m,h\)\\leq\\arcsin\\kappa: among allmmin the radius\-κ​‖h‖\\kappa\\\|h\\\|ball centered athh, the largest angle is attained by a tangent ray\. A passing score gives∠⁡\(g,m\)≤arccos⁡τ\\angle\(g,m\)\\leq\\arccos\\tau\. The spherical triangle inequality therefore yields

∠⁡\(g,h\)≤arccos⁡τ\+arcsin⁡κ\.\\angle\(g,h\)\\leq\\arccos\\tau\+\\arcsin\\kappa\.\(67\)Taking the cosine proves Eq\.[64](https://arxiv.org/html/2609.22115#A3.E64)\.

Similarly,‖g−h‖≤η​‖h‖\\\|g\-h\\\|\\leq\\eta\\\|h\\\|implies∠⁡\(g,h\)≤arcsin⁡η\\angle\(g,h\)\\leq\\arcsin\\eta\. Hence

∠⁡\(g,m\)≤arcsin⁡η\+arcsin⁡κ,\\angle\(g,m\)\\leq\\arcsin\\eta\+\\arcsin\\kappa,\(68\)whose cosine gives Eq\.[65](https://arxiv.org/html/2609.22115#A3.E65)\. Solving the resulting inequality forη\\etayields Eq\.[66](https://arxiv.org/html/2609.22115#A3.E66)\. ∎

Soundness and nontrivial completeness coexist exactly in the band

κ<τ<1−κ2,\\kappa<\\tau<\\sqrt\{1\-\\kappa^\{2\}\},\(69\)which is nonempty if and only ifκ<1/2\\kappa<1/\\sqrt\{2\}\. Both constants are sharp: coplanar vectors placed at the tangent angles used in the proof attain equality\.

### C\.3Threshold Interface

The geometry requires the threshold to remain inside a feasible band; it does not require a particular calibration statistic\. A fixed threshold suffices\. An adaptive rule can preserve the same guarantee through projection,

τt=Π\[τ¯,τ¯\]​\(βτ​τt−1\+\(1−βτ\)​stref\),\\tau\_\{t\}=\\Pi\_\{\[\\underline\{\\tau\},\\overline\{\\tau\}\]\}\\left\(\\beta\_\{\\tau\}\\tau\_\{t\-1\}\+\(1\-\\beta\_\{\\tau\}\)s\_\{t\}^\{\\text\{ref\}\}\\right\),\(70\)where, for a uniform tracking levelκ¯<1/2\\bar\{\\kappa\}<1/\\sqrt\{2\},

κ¯<τ¯≤τ¯<1−κ¯2\.\\bar\{\\kappa\}<\\underline\{\\tau\}\\leq\\overline\{\\tau\}<\\sqrt\{1\-\\bar\{\\kappa\}^\{2\}\}\.\(71\)Projection separates the guarantee from the selection bias of the score written after first passage\. Without a fixed upper bound, updating the threshold only from passing scores makes it nondecreasing and can eventually destroy completeness\.

## Appendix DFirst\-Passing Budget Control

The controller inspects a finite increasing grid𝒦\\mathcal\{K\}and stops at the first candidate whose momentum\-consistency score reaches the current threshold\. The proof below controls this stopping rule directly through the candidate error envelope and the gate geometry\. It does not introduce an expected score curve or require earlier candidates to be separated from an oracle threshold\.

### D\.1Sufficient Local Budget

Fix a stepttand work on the simultaneous candidate event from Lemma[B\.1](https://arxiv.org/html/2609.22115#A2.Thmtheorem1)\. Write

et​\(K\)≜q⁡\(nt​\(K\),δ\)\+L​At​\(K\)nt​\(K\),K∈𝒦,e\_\{t\}\(K\)\\triangleq q\(n\_\{t\}\(K\),\\delta\)\+\\frac\{LA\_\{t\}\(K\)\}\{n\_\{t\}\(K\)\},\\qquad K\\in\\mathcal\{K\},\(72\)so that‖𝒈t​\(K\)−ht‖≤et​\(K\)\\\|\\bm\{g\}\_\{t\}\(K\)\-h\_\{t\}\\\|\\leq e\_\{t\}\(K\)for every inspected candidate\. The first\-passing result below uses the first grid point that meets a sufficient error level; it does not require the empirical score or a candidate\-specific concentration radius to be monotone inKK\.

Suppose the debiased anchor satisfies the uniform relative tracking bound

‖𝒎~t−1−ht‖≤κ¯​‖ht‖,0≤κ¯<12,\\\|\\widetilde\{\\bm\{m\}\}\_\{t\-1\}\-h\_\{t\}\\\|\\leq\\bar\{\\kappa\}\\\|h\_\{t\}\\\|,\\qquad 0\\leq\\bar\{\\kappa\}<\\frac\{1\}\{\\sqrt\{2\}\},\(73\)and the threshold lies in

κ¯<τ¯≤τt−1≤τ¯<1−κ¯2\.\\bar\{\\kappa\}<\\underline\{\\tau\}\\leq\\tau\_\{t\-1\}\\leq\\overline\{\\tau\}<\\sqrt\{1\-\\bar\{\\kappa\}^\{2\}\}\.\(74\)Define the uniform geometry margins

Δ¯≜Δ⁡\(τ¯,κ¯\)\>0,η¯≜η⋆​\(τ¯,κ¯\)\>0\.\\underline\{\\Delta\}\\triangleq\\Delta\(\\underline\{\\tau\},\\bar\{\\kappa\}\)\>0,\\qquad\\underline\{\\eta\}\\triangleq\\eta\_\{\\star\}\(\\overline\{\\tau\},\\bar\{\\kappa\}\)\>0\.\(75\)
###### Definition D\.1\(Sufficient Grid Budget\)\.

For‖ht‖\>0\\\|h\_\{t\}\\\|\>0, let

Ktsuf≜min⁡\{K∈𝒦:et​\(K\)≤η¯​‖ht‖\},K\_\{t\}^\{\\text\{suf\}\}\\triangleq\\min\\left\\\{K\\in\\mathcal\{K\}:e\_\{t\}\(K\)\\leq\\underline\{\\eta\}\\\|h\_\{t\}\\\|\\right\\\},\(76\)whenever the set is nonempty\.

###### Lemma D\.2\(A Sufficient Budget Exists Below the Cap\)\.

If

et​\(Kmax\)≤η¯​‖ht‖,e\_\{t\}\(K\_\{\\max\}\)\\leq\\underline\{\\eta\}\\\|h\_\{t\}\\\|,\(77\)thenKtsufK\_\{t\}^\{\\text\{suf\}\}exists andKtsuf≤KmaxK\_\{t\}^\{\\text\{suf\}\}\\leq K\_\{\\max\}\. On a pre\-stationary region‖ht‖≥ϵ\\\|h\_\{t\}\\\|\\geq\\epsilon, it is sufficient to replace the right\-hand side of Eq\.[77](https://arxiv.org/html/2609.22115#A4.E77)byη¯​ϵ\\underline\{\\eta\}\\epsilon\.

###### Proof\.

Equation[77](https://arxiv.org/html/2609.22115#A4.E77)placesKmaxK\_\{\\max\}in the defining set of Eq\.[76](https://arxiv.org/html/2609.22115#A4.E76); the minimum therefore exists on the finite grid\. The pre\-stationary statement follows from‖ht‖≥ϵ\\\|h\_\{t\}\\\|\\geq\\epsilon\. ∎

### D\.2Safe First Passage

###### Proposition D\.3\(First\-Passing Control\)\.

Assume Eqs\.[73](https://arxiv.org/html/2609.22115#A4.E73)–[74](https://arxiv.org/html/2609.22115#A4.E74), and supposeKtsufK\_\{t\}^\{\\text\{suf\}\}exists\. LetKtK\_\{t\}be the first grid point accepted by the consistency test\. Then

Kt≤Ktsuf,cos⁡\(𝒈t​\(Kt\),ht\)≥Δ¯\>0\.K\_\{t\}\\leq K\_\{t\}^\{\\text\{suf\}\},\\qquad\\cos\(\\bm\{g\}\_\{t\}\(K\_\{t\}\),h\_\{t\}\)\\geq\\underline\{\\Delta\}\>0\.\(78\)Consequently, if Eq\.[77](https://arxiv.org/html/2609.22115#A4.E77)holds, the search passes before capped fallback\. If a continuous sufficient level is rounded upward to the next grid point, the corresponding implementation bound incurs at most one incrementΔ​K\\Delta K\.

###### Proof\.

AtKtsufK\_\{t\}^\{\\text\{suf\}\}, the simultaneous candidate event and Definition[D\.1](https://arxiv.org/html/2609.22115#A4.Thmtheorem1)give

‖𝒈t​\(Ktsuf\)−ht‖≤η¯​‖ht‖\.\\\|\\bm\{g\}\_\{t\}\(K\_\{t\}^\{\\text\{suf\}\}\)\-h\_\{t\}\\\|\\leq\\underline\{\\eta\}\\\|h\_\{t\}\\\|\.\(79\)Becauseτt−1≤τ¯\\tau\_\{t\-1\}\\leq\\overline\{\\tau\}and the actual tracking level is no larger thanκ¯\\bar\{\\kappa\}, the completeness part of Theorem[C\.3](https://arxiv.org/html/2609.22115#A3.Thmtheorem3)forces this candidate to pass\. The increasing search therefore stops no later, soKt≤KtsufK\_\{t\}\\leq K\_\{t\}^\{\\text\{suf\}\}\.

For the selected candidate, passage givescos⁡\(𝒈t​\(Kt\),𝒎~t−1\)≥τt−1≥τ¯\\cos\(\\bm\{g\}\_\{t\}\(K\_\{t\}\),\\widetilde\{\\bm\{m\}\}\_\{t\-1\}\)\\geq\\tau\_\{t\-1\}\\geq\\underline\{\\tau\}\. The soundness part of Theorem[C\.3](https://arxiv.org/html/2609.22115#A3.Thmtheorem3)then yields

cos⁡\(𝒈t​\(Kt\),ht\)≥Δ⁡\(τt−1,κt\)≥Δ⁡\(τ¯,κ¯\)=Δ¯\.\\cos\(\\bm\{g\}\_\{t\}\(K\_\{t\}\),h\_\{t\}\)\\geq\\Delta\(\\tau\_\{t\-1\},\\kappa\_\{t\}\)\\geq\\Delta\(\\underline\{\\tau\},\\bar\{\\kappa\}\)=\\underline\{\\Delta\}\.\(80\)Thus an earlier accidental pass can reduce the budget but cannot invalidate the directional guarantee\. ∎

The proposition deliberately provides an upper bound rather than exact recovery of an oracle budget\. Exact equality would require a lower separation condition for every earlier score, which is unnecessary for either safety or query savings\.

### D\.3Full Buffer and Query Accounting

Suppose the FIFO buffer after acceptance is full with capacityCC, each accepted step adds at leastKminK\_\{\\min\}fresh records, and the relevant path increments satisfyℓs≤ℓ¯\\ell\_\{s\}\\leq\\bar\{\\ell\}\. When a common nonincreasing radiusq⁡\(n,δ\)q\(n,\\delta\)controls averages ofnnadmissible records, let

HC≜⌈CKmin⌉\.H\_\{C\}\\triangleq\\left\\lceil\\frac\{C\}\{K\_\{\\min\}\}\\right\\rceil\.\(81\)Before pruning after acceptance, a candidate withKKfresh records hasnt​\(K\)=C\+Kn\_\{t\}\(K\)=C\+KandAt​\(K\)≤C​HC​ℓ¯A\_\{t\}\(K\)\\leq CH\_\{C\}\\bar\{\\ell\}\. Hence

eC​\(K\)≜q⁡\(C\+K,δ\)\+L​C​HC​ℓ¯C\+Ke\_\{C\}\(K\)\\triangleq q\(C\+K,\\delta\)\+\\frac\{LCH\_\{C\}\\bar\{\\ell\}\}\{C\+K\}\(82\)is a deterministic sufficient envelope\. The cap conditioneC​\(Kmax\)≤η¯​ϵe\_\{C\}\(K\_\{\\max\}\)\\leq\\underline\{\\eta\}\\epsilonmakes the no\-fallback statement operational using buffer, movement, confidence, and cap parameters alone\.

###### Corollary D\.4\(Controller Query Cost\)\.

Let𝒢\\mathcal\{G\}contain the steps on which the simultaneous candidate event, the tracking bound, the threshold band, and cap sufficiency all hold\. Then

∑t=1TKt≤∑t∈𝒢Ktsuf\+Kmax​\(T−\|𝒢\|\)\.\\sum\_\{t=1\}^\{T\}K\_\{t\}\\leq\\sum\_\{t\\in\\mathcal\{G\}\}K\_\{t\}^\{\\text\{suf\}\}\+K\_\{\\max\}\(T\-\|\\mathcal\{G\}\|\)\.\(83\)If the joint conditions hold throughout a window, the second term vanishes\. Moreover, whenever the reuse condition in Eq\.[46](https://arxiv.org/html/2609.22115#A2.E46)holds at the sufficient budget for fresh directions alone, the sufficient budget with reuse is no larger\.

###### Proof\.

Proposition[D\.3](https://arxiv.org/html/2609.22115#A4.Thmtheorem3)givesKt≤KtsufK\_\{t\}\\leq K\_\{t\}^\{\\text\{suf\}\}on𝒢\\mathcal\{G\}\. Every other step is bounded by the deterministic capKmaxK\_\{\\max\}\. Summing these two cases proves Eq\.[83](https://arxiv.org/html/2609.22115#A4.E83)\. The final comparison follows by evaluating the reuse envelope at the sufficient budget for fresh directions alone and applying Eq\.[46](https://arxiv.org/html/2609.22115#A2.E46)\. ∎

## Appendix EDescent and Query Accounting

This section closes the theorem chain for the normalized\-update model\. The result is local to a pre\-stationary window on which the estimation, movement, threshold, and cap conditions established above hold\. It does not identify coordinatewise adaptive preconditioning with global Euclidean normalization\.

### E\.1Normalized Descent

###### Assumption E\.1\(Normalized\-Update Analysis Protocol\)\.

For the descent analysis, the selected nonzero candidate defines

𝒅t≜𝒈t‖𝒈t‖,𝜽t\+1=𝜽t−αt​𝒅t,‖𝒅t‖=1\.\\bm\{d\}\_\{t\}\\triangleq\\frac\{\\bm\{g\}\_\{t\}\}\{\\\|\\bm\{g\}\_\{t\}\\\|\},\\qquad\\bm\{\\theta\}\_\{t\+1\}=\\bm\{\\theta\}\_\{t\}\-\\alpha\_\{t\}\\bm\{d\}\_\{t\},\\qquad\\\|\\bm\{d\}\_\{t\}\\\|=1\.\(84\)This is the formal optimizer scope of the descent theorem\. The experiments use the stated R\-AdaZO backbone; a coordinatewise second\-moment preconditioner need not preserve Euclidean angles and is not covered without an additional spectral condition\.

###### Lemma E\.2\(Normalized Descent\)\.

Under Assumption[A\.1](https://arxiv.org/html/2609.22115#A1.Thmtheorem1), ifcos⁡\(𝐝t,ht\)≥δt\>0\\cos\(\\bm\{d\}\_\{t\},h\_\{t\}\)\\geq\\delta\_\{t\}\>0, then

Fμ​\(𝜽t\+1\)−Fμ​\(𝜽t\)≤−αt​δt​‖ht‖\+L​αt22\.F\_\{\\mu\}\(\\bm\{\\theta\}\_\{t\+1\}\)\-F\_\{\\mu\}\(\\bm\{\\theta\}\_\{t\}\)\\leq\-\\alpha\_\{t\}\\delta\_\{t\}\\\|h\_\{t\}\\\|\+\\frac\{L\\alpha\_\{t\}^\{2\}\}\{2\}\.\(85\)

###### Proof\.

The smoothness inequality and Eq\.[84](https://arxiv.org/html/2609.22115#A5.E84)give

Fμ​\(𝜽t\+1\)−Fμ​\(𝜽t\)\\displaystyle F\_\{\\mu\}\(\\bm\{\\theta\}\_\{t\+1\}\)\-F\_\{\\mu\}\(\\bm\{\\theta\}\_\{t\}\)≤−αt​⟨ht,𝒅t⟩\+L​αt22​‖𝒅t‖2\\displaystyle\\leq\-\\alpha\_\{t\}\\langle h\_\{t\},\\bm\{d\}\_\{t\}\\rangle\+\\frac\{L\\alpha\_\{t\}^\{2\}\}\{2\}\\\|\\bm\{d\}\_\{t\}\\\|^\{2\}\(86\)≤−αt​δt​‖ht‖\+L​αt22\.\\displaystyle\\leq\-\\alpha\_\{t\}\\delta\_\{t\}\\\|h\_\{t\}\\\|\+\\frac\{L\\alpha\_\{t\}^\{2\}\}\{2\}\.\(87\)∎

### E\.2Operational Pre\-Stationary Window

The next theorem gathers the preceding interfaces into one statement\. Its probability is exactly that of the simultaneous candidate event used to instantiate the error radii; after conditioning on that event, every step of the argument is deterministic\.

###### Theorem E\.3\(Certified Descent and Local Query Control\)\.

Consider a finite window beginning after warm\-up in which‖ht‖≥ϵ\\\|h\_\{t\}\\\|\\geq\\epsilonand the candidate event of Lemma[B\.1](https://arxiv.org/html/2609.22115#A2.Thmtheorem1)holds simultaneously\. Suppose:

1. 1\.the final estimates entering the debiased EMA satisfy Eq\.[61](https://arxiv.org/html/2609.22115#A3.E61);
2. 2\.the resulting tracking levels obeyκt≤κ¯<1/2\\kappa\_\{t\}\\leq\\bar\{\\kappa\}<1/\\sqrt\{2\};
3. 3\.the threshold is fixed or projected into the band in Eq\.[74](https://arxiv.org/html/2609.22115#A4.E74);
4. 4\.the cap satisfieset​\(Kmax\)≤η¯​ϵe\_\{t\}\(K\_\{\\max\}\)\\leq\\underline\{\\eta\}\\epsilon; and
5. 5\.the update follows Eq\.[84](https://arxiv.org/html/2609.22115#A5.E84)with0<αt≤Δ¯​ϵ/L0<\\alpha\_\{t\}\\leq\\underline\{\\Delta\}\\epsilon/L\.

Then every search in the window passes byKtsuf≤KmaxK\_\{t\}^\{\\text\{suf\}\}\\leq K\_\{\\max\}, and its selected direction satisfies

cos⁡\(𝒅t,ht\)≥Δ¯\.\\cos\(\\bm\{d\}\_\{t\},h\_\{t\}\)\\geq\\underline\{\\Delta\}\.\(88\)Consequently,

Fμ​\(𝜽t\+1\)−Fμ​\(𝜽t\)≤−αt​Δ¯​ϵ2\.F\_\{\\mu\}\(\\bm\{\\theta\}\_\{t\+1\}\)\-F\_\{\\mu\}\(\\bm\{\\theta\}\_\{t\}\)\\leq\-\\frac\{\\alpha\_\{t\}\\underline\{\\Delta\}\\epsilon\}\{2\}\.\(89\)

###### Proof\.

Proposition[C\.1](https://arxiv.org/html/2609.22115#A3.Thmtheorem1)and the certificates for accepted candidates give the stated relative tracking level\. The threshold band and cap condition then satisfy the premises of Proposition[D\.3](https://arxiv.org/html/2609.22115#A4.Thmtheorem3), which rules out capped fallback, givesKt≤KtsufK\_\{t\}\\leq K\_\{t\}^\{\\text\{suf\}\}, and proves Eq\.[88](https://arxiv.org/html/2609.22115#A5.E88)\. Lemma[E\.2](https://arxiv.org/html/2609.22115#A5.Thmtheorem2)yields

Fμ​\(𝜽t\+1\)−Fμ​\(𝜽t\)≤−αt​Δ¯​ϵ\+L​αt22\.F\_\{\\mu\}\(\\bm\{\\theta\}\_\{t\+1\}\)\-F\_\{\\mu\}\(\\bm\{\\theta\}\_\{t\}\)\\leq\-\\alpha\_\{t\}\\underline\{\\Delta\}\\epsilon\+\\frac\{L\\alpha\_\{t\}^\{2\}\}\{2\}\.\(90\)The step\-size condition bounds the curvature term byαt​Δ¯​ϵ/2\\alpha\_\{t\}\\underline\{\\Delta\}\\epsilon/2, proving Eq\.[89](https://arxiv.org/html/2609.22115#A5.E89)\. ∎

### E\.3Finite\-Horizon Accounting

###### Corollary E\.4\(Pre\-Stationary Steps and Fresh Directions\)\.

Suppose the conditions of Theorem[E\.3](https://arxiv.org/html/2609.22115#A5.Thmtheorem3)hold until the first stepTϵT\_\{\\epsilon\}with‖hTϵ‖<ϵ\\\|h\_\{T\_\{\\epsilon\}\}\\\|<\\epsilon, and supposeFμF\_\{\\mu\}is bounded below byF⋆F\_\{\\star\}\. Ifαt=α=c​ϵ\\alpha\_\{t\}=\\alpha=c\\epsilonwith0<c≤Δ¯/L0<c\\leq\\underline\{\\Delta\}/L, then

Tϵ−t1≤2​\(Fμ​\(𝜽t1\)−F⋆\)c​Δ¯​ϵ2\.T\_\{\\epsilon\}\-t\_\{1\}\\leq\\frac\{2\\bigl\(F\_\{\\mu\}\(\\bm\{\\theta\}\_\{t\_\{1\}\}\)\-F\_\{\\star\}\\bigr\)\}\{c\\underline\{\\Delta\}\\epsilon^\{2\}\}\.\(91\)The cumulative number of fresh directions satisfies

∑t=t1Tϵ−1Kt≤∑t=t1Tϵ−1Ktsuf≤\(Tϵ−t1\)​Kmax\.\\sum\_\{t=t\_\{1\}\}^\{T\_\{\\epsilon\}\-1\}K\_\{t\}\\leq\\sum\_\{t=t\_\{1\}\}^\{T\_\{\\epsilon\}\-1\}K\_\{t\}^\{\\text\{suf\}\}\\leq\(T\_\{\\epsilon\}\-t\_\{1\}\)K\_\{\\max\}\.\(92\)

###### Proof\.

Summing Eq\.[89](https://arxiv.org/html/2609.22115#A5.E89)fromt1t\_\{1\}toTϵ−1T\_\{\\epsilon\}\-1and using the lower boundF⋆F\_\{\\star\}gives Eq\.[91](https://arxiv.org/html/2609.22115#A5.E91)\. Proposition[D\.3](https://arxiv.org/html/2609.22115#A4.Thmtheorem3)givesKt≤Ktsuf≤KmaxK\_\{t\}\\leq K\_\{t\}^\{\\text\{suf\}\}\\leq K\_\{\\max\}at every step in the window, which proves Eq\.[92](https://arxiv.org/html/2609.22115#A5.E92)\. ∎

The sharper quantity in Eq\.[92](https://arxiv.org/html/2609.22115#A5.E92)is the sum of local sufficient budgets, not the cap product\. For the full\-buffer envelope in Eq\.[82](https://arxiv.org/html/2609.22115#A4.E82), eachKtsufK\_\{t\}^\{\\text\{suf\}\}is obtained by inverting

q⁡\(C\+K,δ\)\+L​C​HC​ℓ¯C\+K≤η¯​ϵ\.q\(C\+K,\\delta\)\+\\frac\{LCH\_\{C\}\\bar\{\\ell\}\}\{C\+K\}\\leq\\underline\{\\eta\}\\epsilon\.\(93\)This expression exposes the two ways in which queries help: they add acquisition evidence and dilute the staleness carried by the retained records\.

###### Corollary E\.5\(Reuse Versus Fresh\-Only Accounting\)\.

LetKt,freshsufK\_\{t,\\text\{fresh\}\}^\{\\text\{suf\}\}be the first grid point satisfyingq⁡\(K,δ\)≤η¯​‖ht‖q\(K,\\delta\)\\leq\\underline\{\\eta\}\\\|h\_\{t\}\\\|\. If the reuse\-benefit condition in Eq\.[46](https://arxiv.org/html/2609.22115#A2.E46)holds at this budget, then

Ktsuf≤Kt,freshsuf\.K\_\{t\}^\{\\text\{suf\}\}\\leq K\_\{t,\\text\{fresh\}\}^\{\\text\{suf\}\}\.\(94\)The inequality is strict whenever an earlier reuse candidate already satisfies the sufficient\-error condition\.

###### Proof\.

AtKt,freshsufK\_\{t,\\text\{fresh\}\}^\{\\text\{suf\}\}, Eq\.[46](https://arxiv.org/html/2609.22115#A2.E46)makes the reuse envelope no larger than the fresh\-only envelope, which is at mostη¯​‖ht‖\\underline\{\\eta\}\\\|h\_\{t\}\\\|\. This grid point is therefore feasible for Definition[D\.1](https://arxiv.org/html/2609.22115#A4.Thmtheorem1); taking the minimum proves the result\. ∎

The conclusion is a conditional local saving, not an unconditional dominance statement\. When response staleness exceeds the concentration gain, the comparison reverses, which is precisely why Appendix[B](https://arxiv.org/html/2609.22115#A2)predicts an interior useful history capacity\.

## Appendix FDiagnostics for Variance\-Based Adaptation

The main text compares strategies for query allocation under a common stabilized backbone\. This section explains why adaptation based on variance remains costly in the tested regimes after separating instability in the optimization backbone from the sampling rule itself\.

### F\.1StatZO in Ultra\-High\-Dimensional Fine\-Tuning

The original implementation of StatZO\([Bollapragada et al\. 2024](https://arxiv.org/html/2609.22115#bib.bib2)\)relies on standard zeroth\-order optimizers \(e\.g\., ZO\-SGD or ZO\-AdaMM\)\. While theoretically sound for lower\-dimensional problems, this configuration exhibits severe instability in ultra\-high\-dimensional non\-convex landscapes \(d≈105d\\approx 10^\{5\}\)\.

As illustrated in Figure[4](https://arxiv.org/html/2609.22115#A6.F4)\(referencing the ablation in Section[6\.3](https://arxiv.org/html/2609.22115#S6.SS3)\), the original StatZO configuration fails to descend effectively on SST\-2, stagnating at high loss values \(\>3\.5\>3\.5\)\. In this regime, estimating the population varianceσ2\\sigma^\{2\}from a mini\-batch in such high dimensions produces unstable SNR signals, which in turn destabilize the optimizer’s second\-moment estimates\.

Figure 4:Behavior of the original StatZO configuration on SST\-2\. Without the stabilized update rule used in our main experiments, the original StatZO configuration stagnates at a high loss, motivating the standardized optimizer backbone used in the main comparison\.
### F\.2Stabilized StatZO in Black\-Box Attacks

To evaluate the adaptive sampling strategy more cleanly, we examine StatZO in two stages: its original formulation and a stabilized version using the same backbone as the main comparisons\. This two\-step analysis helps separate backbone effects from sampling effects\.

First, we evaluate the original StatZO equipped with the standard ZO\-AdaMM backbone\. As shown in Table[3](https://arxiv.org/html/2609.22115#A6.T3), the configuration requiring the fewest queries among the tested caps isKmax=4K\_\{\\max\}=4, with 4,382 queries\. However, the overall efficiency is hampered by the instability of the standard update rule in high\-dimensional settings \(d=784d=784\)\.

Table 3:Original StatZO hyperparameter sweep\. All configurations useKmin=2K\_\{\\min\}=2and variance\-to\-norm threshold 0\.75\. Among the tested settings for this version,Kmax=4K\_\{\\max\}=4gives the lowest query cost, but the absolute cost remains high in the reported setting\.To ensure that the comparison targets the sampling strategy rather than optimizer defects, we also evaluate a stabilized StatZO variant with the R\-AdaZO backbone\. Table[4](https://arxiv.org/html/2609.22115#A6.T4)shows the effect of this standardization: the query cost drops from roughly 4,382 to 1,996\. The tested cap requiring the fewest queries isKmax=2K\_\{\\max\}=2, while increasing the adaptive budget \(Kmax≥4K\_\{\\max\}\\geq 4\) degrades performance\. Even this strongest tested stabilized configuration remains well above the reported ZoAQ cost of 320 queries, suggesting that the query overhead required to validate geometry can outweigh the benefit of variance reduction in this setting\.

Table 4:Stabilized StatZO hyperparameter sweep\. Equipping StatZO with the R\-AdaZO backbone improves performance relative to Table[3](https://arxiv.org/html/2609.22115#A6.T3)\. Among the tested caps, the lowest query count occurs atKmax=2K\_\{\\max\}=2, and the method remains less query\-efficient than ZoAQ in this setting\.#### Cross\-dataset pattern: CIFAR\-10\.

We replicate the StatZO sweep on CIFAR\-10 \(d=3072d=3072\) to examine whether the same pattern persists across dimensions\. As shown in Table[5](https://arxiv.org/html/2609.22115#A6.T5), the tested configuration requiring the fewest queries remainsKmax=2K\_\{\\max\}=2, consistent with MNIST\. Even with this tuned setting, StatZO achieves 964 queries, still 1\.54×\\timesslower than ZoAQ \(625 queries withNhist=8N\_\{\\text\{hist\}\}=8\)\.

This analysis across datasets suggests that the same overhead from validation persists across problem scales: StatZO’s variance estimation overhead prevents it from matching ZoAQ’s efficiency in the reported settings\.

Table 5:StatZO hyperparameter sweep on CIFAR\-10 \(d=3072d=3072\)\. Consistent with MNIST, the tested configuration requiring the fewest queries isKmax=2K\_\{\\max\}=2, yet StatZO still lags behind ZoAQ \(625 queries\) in the reported setting\.

### F\.3Validation Overhead

#### Remark: Why history reuse is not folded into StatZO\.

A natural question is whether history reuse could also be added to StatZO\. That modification is not theoretically neutral\. As formalized by[Bollapragada et al\. 2024](https://arxiv.org/html/2609.22115#bib.bib2), the adaptive sampling analysis behind the Norm Condition is built around fresh i\.i\.d\. samples for estimating local accuracy and variance quantities\.

Incorporating historical queries\{\(𝒖,y\)∈ℋt−1\}\\\{\(\\bm\{u\},y\)\\in\\mathcal\{H\}\_\{t\-1\}\\\}into the current estimate𝒈t\\bm\{g\}\_\{t\}introduces cross\-step correlations and transport bias because𝜽t≠𝜽t−τ\\bm\{\\theta\}\_\{t\}\\neq\\bm\{\\theta\}\_\{t\-\\tau\}\. It would therefore require a different variance\-estimation analysis rather than being a drop\-in improvement to StatZO’s sample\-variance estimator\. ZoAQ’s momentum\-consistency condition is instead built around this correlation structure\.

The empirical gap is therefore not only an implementation issue; it also reflects a structural bottleneck from validation overhead\.

To estimate the variance𝕍⁡\[𝒈\]\\mathbb\{V\}\[\\bm\{g\}\], StatZO requires a reliable estimate of the function valueF⁡\(𝜽t\)F\(\\bm\{\\theta\}\_\{t\}\)at the current center point\. This incurs a fixed cost of at least one extra query per iteration purely for statistical estimation\.

- •Overhead ratio: In a low\-budget one\-sided regime with two perturbed directional calls, an additional center\-value query changes the accounting from22directional calls to2​directions\+1​baseline=32\\text\{ directions\}\+1\\text\{ baseline\}=3oracle calls, a 50% overhead relative to the directional calls alone\.
- •ZoAQ: The momentum\-consistency test uses𝒎t−1\\bm\{m\}\_\{t\-1\}, a historical variable stored in memory, and requires no additional queries to validate the search direction\.

This analysis makes the practical implication explicit: when only a few queries are used, the cost of validating geometry can itself become a meaningful part of the total budget\.

### F\.4Reference Stability

Beyond query overhead, there is a second statistical reason for StatZO’s weaker performance in this regime: the instability of the reference signal itself\. Both methods rely on a reference vector to judge the quality of the current estimate𝒈t\\bm\{g\}\_\{t\}\.

- •StatZO uses the sample varianceVkV\_\{k\}\(or effectively, the batch mean𝒈¯k\\bar\{\\bm\{g\}\}\_\{k\}relative to variance\) estimated from a small batch of sizekk\.
- •ZoAQ uses the historical momentum𝒎t−1\\bm\{m\}\_\{t\-1\}as the reference anchor\.

The comparisons above are empirical diagnostics of the tested configurations\. The pathwise treatment of the EMA under overlapping accepted histories is given in Appendix[C](https://arxiv.org/html/2609.22115#A3)\.

## Appendix GExperimental Protocols

This appendix collects the implementation details, protocol standardization choices, and additional result tables referenced in the main text\. Its role is to make the experimental comparison reproducible without expanding the main paper’s evidence budget\.

Table 6:Experimental evidence map\. Each regime tests a distinct part of the mechanism chain, with claims stated at the level supported by the source ledger\.### G\.1Algorithm and Cost Accounting

Algorithm[1](https://arxiv.org/html/2609.22115#alg1)in the main paper is the authoritative pseudocode\. This appendix section records the implementation\-level accounting assumptions used by that algorithm in our experiments, together with the protocol choices needed for reproducibility\.

#### Query accounting\.

The momentum\-consistency test itself introduces no additional oracle queries beyond those already used to construct𝒈t\\bm\{g\}\_\{t\}\. In attacks, a one\-sided forward\-difference step withKtK\_\{t\}sampled directions requires one baseline evaluation plusKtK\_\{t\}perturbed evaluations\. In synthetic benchmarks and LLM fine\-tuning, the two\-sided protocol requires two evaluations per sampled direction\. The practical saving provided by ZoAQ is therefore a reduction in oracle calls rather than auxiliary computation: the extra cost is primarily memory, since the method retains recent direction\-response pairs in order to induce query\-reuse coupling\. In seed\-based implementations, this footprint can be reduced because directions need not be stored explicitly\.

These accounting rules vary by protocol\. Within each regime, all methods are compared under the same estimator protocol and the same cost definition; across regimes, the reported synthetic query savings, attack query counts, and LLM savings in forward evaluations measure efficiency for their respective tasks rather than one absolute cost scale\.

### G\.2Compute, Assets, and Scope

#### Compute resources\.

Synthetic and attack experiments were run on standard CPU\-accessible hardware or a single GPU\. The main LLM fine\-tuning runs were executed on a server with four NVIDIA RTX 4090 GPUs \(24GB each\), which was sufficient for the OPT\-1\.3B and OPT\-13B LoRA runs using forward passes only\. We report oracle calls or forward evaluations as the primary cost metric because the paper studies query allocation rather than systems throughput; elapsed time also depends on model loading, the data pipeline, and scheduling across runs\.

#### Existing assets and licenses\.

The experimental study uses standard public datasets and model checkpoints, including MNIST, CIFAR\-10, GLUE/SST\-2, COPA, and OPT checkpoints, under their respective public terms of use\. We rely on these assets only for benchmarking and do not redistribute modified versions in the paper artifact\.

Table 7:Existing assets used in the experiments\. When the original source or benchmark metadata does not state a single explicit license, we report that status rather than assigning a license name\.
#### Broader impact\.

The attack experiments are included to study query efficiency in a controlled black\-box setting, not to advocate misuse\. The same techniques are also relevant to robustness evaluation and to black\-box optimization problems where gradients are unavailable for benign reasons\. We therefore view the main broader\-impact consideration as responsible disclosure and evaluation practice rather than a new capability claim\.

### G\.3Baseline Standardization

#### Unified Optimizer Backbone\.

As noted in Section[6](https://arxiv.org/html/2609.22115#S6), standard zeroth\-order optimizers often suffer from diverging second\-moment estimates in high dimensions\. To reduce this confounding factor in the main attack and stabilized adaptive comparisons, we use the R\-AdaZO rectified update rule as the common backbone for R\-AdaZO, stabilized StatZO, ZoAR\-style reuse diagnostics, and ZoAQ\. Legacy ZO\-AdaMM and MeZO appear only in the protocol roles listed in Table[8](https://arxiv.org/html/2609.22115#A7.T8)\. This standardization makes the comparison focus on sampling strategy rather than claiming uniform dominance over every original adaptive ZOO implementation\.

#### Baselines Configuration\.

We compare ZoAQ against the following representative methods:

- •R\-AdaZO \(Fixed\-Budget SOTA\): Uses a static query budgetKKper iteration\. We setK=10K=10for synthetic benchmarks andK=2K=2or44for high\-dimensional tasks, following the optimal settings reported in\([Shu et al\. 2025](https://arxiv.org/html/2609.22115#bib.bib21)\)\.
- •Refined StatZO \(Norm\-Based SOTA\): A stabilized version of StatZO\([Bollapragada et al\. 2024](https://arxiv.org/html/2609.22115#bib.bib2)\)\. We integrate it with the R\-AdaZO backbone to prevent divergence\. It adaptsKt∈\[Kmin,Kmax\]K\_\{t\}\\in\[K\_\{\\min\},K\_\{\\max\}\]based on the norm condition‖𝒈t−𝒎t−1‖/‖𝒎t−1‖≤cnorm\\\|\\bm\{g\}\_\{t\}\-\\bm\{m\}\_\{t\-1\}\\\|/\\\|\\bm\{m\}\_\{t\-1\}\\\|\\leq c\_\{\\text\{norm\}\}, withcnorm=0\.5c\_\{\\text\{norm\}\}=0\.5as the default tolerance\.
- •ZoAQ \(Ours\): Utilizes the momentum\-consistency conditioncos⁡\(𝒈t,𝒎t−1\)≥τt−1\\cos\(\\bm\{g\}\_\{t\},\\bm\{m\}\_\{t\-1\}\)\\geq\\tau\_\{t\-1\}to trigger budget expansion\. The effective thresholdτt\\tau\_\{t\}is updated via EMA\.

Table[8](https://arxiv.org/html/2609.22115#A7.T8)lists every baseline family that appears in the figures or tables and records its protocol role\. When a baseline has a tunable cap, we report the sweep or selection rule rather than comparing against an unreported hand\-picked setting\.

Table 8:Baseline and protocol map\. The table separates method role, update backbone, query rule, and selection rule so that the experiments compare strategies for query allocation under the intended protocol rather than mixing incompatible baselines\.

### G\.4Hyperparameter Settings

Synthetic experiments were conducted overT=60,000T=60,000iterations in ad=100d=100dimensional space, with results averaged over 5 independent runs\. Random seeds are matched across methods within each synthetic run; figures plot mean trajectories without uncertainty bands for readability, while tables report means and standard deviations where the corresponding columns are shown\. Attack and LLM configurations are specified in their dedicated subsections below\.

#### Gradient Estimator Configuration\.

Consistent with the protocol defined in Sec\.[3](https://arxiv.org/html/2609.22115#S3):

- •Synthetic Benchmarks \(d=100d=100\): We use the two\-sided symmetric\-difference estimator to minimize gradient approximation error\. Thus, R\-AdaZO withK=10K=10directions corresponds to 20 queries/step \(Total≈\\approx1\.2M queries over 60k steps\)\.
- •High\-Dimensional Attacks \(d≥784d\\geq 784\): Following the R\-AdaZO protocol\([Shu et al\. 2025](https://arxiv.org/html/2609.22115#bib.bib21)\), we use the one\-sided forward\-difference estimator\. For example, R\-AdaZO withK=2K=2directions corresponds to 3 queries/step \(1​baseline\+2​perturbed evaluations1\\text\{ baseline\}\+2\\text\{ perturbed evaluations\}\)\.
- •LLM Fine\-Tuning: We use the two\-sided protocol with forward passes only and report forward evaluations \(FE\)\. A step withKtK\_\{t\}directions costs2​Kt2K\_\{t\}FE, as detailed in Appendix[G\.6](https://arxiv.org/html/2609.22115#A7.SS6)\.

#### Common Hyperparameters\.

A set of common hyperparameters was shared across most algorithms to ensure a fair comparison\. These are summarized in Table[9](https://arxiv.org/html/2609.22115#A7.T9)\.

Table 9:Common hyperparameters used across all algorithms\.
#### Algorithm\-Specific Configurations\.

The specific settings for each algorithm, including both non\-adaptive and adaptive methods, are detailed in Table[10](https://arxiv.org/html/2609.22115#A7.T10)\. The query budget per iteration is denoted byKtK\_\{t\}\. For non\-adaptive methods, this is a fixed value\. For adaptive methods, it varies within a specified range\.

Table 10:Algorithm\-specific hyperparameter settings\.AlgorithmParameterValueNon\-Adaptive BaselinesR\-AdaZOFixed queries per iteration,KtK\_\{t\}10Statistics\-Based Adaptive SOTAStatZOQuery range,Kt∈\[Kmin,Kmax\]K\_\{t\}\\in\[K\_\{\\min\},K\_\{\\max\}\]\[1, 10\]Variance\-to\-norm threshold0\.5Our ProposalZoAQQuery range,Kt∈\[Kmin,Kmax\]K\_\{t\}\\in\[K\_\{\\min\},K\_\{\\max\}\]\[1, 10\]Initial EMA threshold,τ0\\tau\_\{0\}1\.0EMA factor,βτ\\beta\_\{\\tau\}0\.9History Window Size,NhistN\_\{\\text\{hist\}\}8Budget reset policy’min’ \(Greedy Reset\)

### G\.5Attack Protocol

#### Experimental Protocol\.

For the black\-box adversarial attack experiments \(Section[6\.2](https://arxiv.org/html/2609.22115#S6.SS2)\), we follow the experimental protocol established in\([Shu et al\. 2025](https://arxiv.org/html/2609.22115#bib.bib21)\)\. We evaluate on two standard vision benchmarks:

- •MNIST \(d=784d=784\)\([LeCun et al\. 1998](https://arxiv.org/html/2609.22115#bib.bib14)\): A CNN with two convolutional layers \(32 and 64 filters, kernel size 3×\\times3\) followed by max\-pooling and two fully connected layers \(128 and 10 units\), achieving 98\.5% test accuracy\. Perturbation constraintϵ=0\.2\\epsilon=0\.2\.
- •CIFAR\-10 \(d=3072d=3072\)\([Krizhevsky & Hinton 2009](https://arxiv.org/html/2609.22115#bib.bib13)\): A deeper CNN achieving 85% test accuracy\. Perturbation constraintϵ=0\.03\\epsilon=0\.03\.

The attack objective is to find a minimal perturbation𝜹\\bm\{\\delta\}such that the model misclassifies𝒙\+𝜹\\bm\{x\}\+\\bm\{\\delta\}while satisfying theℓ∞\\ell\_\{\\infty\}constraint\.

#### MNIST Hyperparameter Settings\.

All methods use identical common hyperparameters: learning rateη=0\.01\\eta=0\.01, momentum coefficients\(β1,β2\)=\(0\.9,0\.99\)\(\\beta\_\{1\},\\beta\_\{2\}\)=\(0\.9,0\.99\), perturbation scaleμ=0\.5\\mu=0\.5, and Adam’s numerical stability constantεAdam=10−8\\varepsilon\_\{\\text\{Adam\}\}=10^\{\-8\}\([Kingma & Ba 2014](https://arxiv.org/html/2609.22115#bib.bib12)\)\. We evaluate over 5 independent runs with different random seeds \(101, 202, 303, 404, 505\), with a maximum of 20,000 iterations per attack\.

For specific algorithms:

- •Non\-adaptive methods \(R\-AdaZO, ZO\-AdaMM\) use a fixed query budget ofK=2K=2per iteration\.
- •Methods with history reuse \(ZoAQ and ZoAR\) use a history buffer sizeNhist=8N\_\{\\text\{hist\}\}=8\(the tested value requiring the fewest queries in Table[18](https://arxiv.org/html/2609.22115#A7.T18)\)\.
- •ZoAQ is configured withKmin=1K\_\{\\min\}=1,Kmax=2K\_\{\\max\}=2, initial thresholdτ0=1\.0\\tau\_\{0\}=1\.0, EMA factorβτ=0\.9\\beta\_\{\\tau\}=0\.9, and the ‘min’ \(greedy\) reset policy\.

#### CIFAR\-10 Hyperparameter Settings\.

For the CIFAR\-10 dataset \(d=3072d=3072\), we use the following configurations:

- •Learning rate:η=0\.0001\\eta=0\.0001\(lower than MNIST due to higher sensitivity\)
- •Perturbation scale:μ=0\.005\\mu=0\.005\(smaller due to higher sensitivity\)
- •History window:Nhist=8N\_\{\\text\{hist\}\}=8for ZoAQ \(unified with MNIST for simplicity\)
- •StatZO: tested settingKmax=2K\_\{\\max\}=2\(the cap requiring the fewest queries in Table[5](https://arxiv.org/html/2609.22115#A6.T5)\)
- •All other parameters remain identical to MNIST

The CIFAR\-10 table uses the same five\-run reporting protocol as MNIST, with matched random seeds across methods within each run\.

#### Fixed\-Budget History\-Reuse Control\.

History reuse improves query efficiency, but it does not recover the full benefit of adaptive allocation\. Table[11](https://arxiv.org/html/2609.22115#A7.T11)compares fixed\-budget ZoAR with R\-AdaZO and ZoAQ under the common stabilized backbone\. All methods achieve 100% success\. Relative to ZoAR atK=2K=2, ZoAQ uses 56\.9% fewer queries on MNIST and 17\.3% fewer on CIFAR\-10\.

Table 11:Fixed\-budget history\-reuse control for black\-box attacks\. Values are average queries±\\pmstandard deviation; all methods achieve 100% success\.

### G\.6LLM Fine\-Tuning Protocol

For the LLM fine\-tuning experiments described in Section[6\.3](https://arxiv.org/html/2609.22115#S6.SS3), we use the hyperparameter settings listed in Table[12](https://arxiv.org/html/2609.22115#A7.T12)\. The base models are OPT checkpoints\([Zhang et al\. 2022](https://arxiv.org/html/2609.22115#bib.bib24)\), and the downstream tasks include SST\-2 from GLUE\([Wang et al\. 2018](https://arxiv.org/html/2609.22115#bib.bib23)\)and COPA\.

The main ZoAQ configuration uses the moderate capKt∈\[1,4\]K\_\{t\}\\in\[1,4\], which shares the same maximum direction budget as the fixedK=4K=4baselines while allowing adaptive reductions\. We also reportKt∈\[1,2\]K\_\{t\}\\in\[1,2\]as an aggressive endpoint with a smaller budget to show the trade\-off between budget and quality\.

All LLM metrics are reported as mean±\\pmstd over three seeds\. Total FE is the cumulative number of forward evaluations per run of 5,000 steps, not the sum across seeds\. Best Eval Loss is the lowest held\-out evaluation loss over checkpoints, Last Eval Loss is the final checkpoint loss, Accuracy is the primary task accuracy summary for the selected run/checkpoint protocol, and Dev Acc is the development\-set accuracy reported by the training pipeline\. We report both loss and accuracy because lower FE can affect them differently, especially on COPA\.

Table 12:Hyperparameter configurations for LLM fine\-tuning tasks\. All LLM runs use the two\-sided zeroth\-order protocol with forward passes only and report forward evaluations \(FE\) as the cost metric\.CategoryParameterValueCommonModelsOPT\-1\.3B, OPT\-13BTasksSST\-2, COPASeeds3Training Steps5,000Evaluation Interval250 stepsBatch Size16Learning Rateη\\eta5×10−55\\times 10^\{\-5\}Perturbation Scale10−210^\{\-2\}Precisionfp16AdaptationLoRAMeZO / R\-AdaZOFixed Direction BudgetK=4K=4StatZODirection\-Budget RangeKt∈\[2,4\]K\_\{t\}\\in\[2,4\]ZoAQMain Direction\-Budget RangeKt∈\[1,4\]K\_\{t\}\\in\[1,4\]Low\-Budget VariantKt∈\[1,2\]K\_\{t\}\\in\[1,2\]Reset PolicyMin \(Greedy\)Initial EMA Thresholdτ0\\tau\_\{0\}1\.0EMA Factorβτ\\beta\_\{\\tau\}0\.9History Window Size,NhistN\_\{\\text\{hist\}\}15Table 13:Complete LLM fine\-tuning results over three seeds\. Total FE is the cumulative number of forward evaluations under the two\-sided protocol with forward passes only; FE savings are relative to fixedK=4K=4, which costs 40,000 FE over 5,000 steps\.#### Accounting for Forward Evaluations\.

We detail the exact FE accounting used to derive the total costs reported in the LLM experiments\. All LLM fine\-tuning tasks run for 5,000 training steps and use the two\-sided protocol with forward passes only\. A step with local direction budgetKtK\_\{t\}costs

𝖥𝖤t=2​Kt,\\mathsf\{FE\}\_\{t\}=2K\_\{t\},\(95\)where each direction uses two perturbed forward evaluations\. Thus fixedK=4K=4costs 8 FE per step and 40,000 FE over 5,000 steps\.

- •Fixed baselines: MeZO and R\-AdaZO useK=4K=4, so each complete run uses 40,000 FE\.
- •StatZO: The direction budget varies inKt∈\[2,4\]K\_\{t\}\\in\[2,4\]; total FE is the cumulative FE per 5,000\-step run, reported as mean±\\pmstd over three seeds\.
- •ZoAQ: The main setting usesKt∈\[1,4\]K\_\{t\}\\in\[1,4\], while the endpoint with a smaller budget usesKt∈\[1,2\]K\_\{t\}\\in\[1,2\]\. Total FE is the cumulative FE per run of 5,000 steps, reported as mean±\\pmstd over three seeds, and the reported averageKKis computed as𝖥𝖤tot/\(2⋅5000\)\\mathsf\{FE\}\_\{\\text\{tot\}\}/\(2\\cdot 5000\)\.

#### Sensitivity to the LLM History Window\.

The main OPT configuration usesNhist=15N\_\{\\text\{hist\}\}=15\. Table[14](https://arxiv.org/html/2609.22115#A7.T14)reports the changes obtained with windows of 8 and 24 on OPT\-1\.3B\. Increasing the window to 24 further reduces FE on both tasks, with changes in loss and accuracy that vary by task\. This comparison measures how the reported outcomes vary with the history window\.

Table 14:Sensitivity to the history window on OPT\-1\.3B relative to the main settingNhist=15N\_\{\\text\{hist\}\}=15\. NegativeΔ\\DeltaFE denotes fewer forward evaluations\.

### G\.7Budget Sweeps

This subsection collects supplementary sweeps that isolate the role of query budget choice and controller design\. They complement the evaluation in the main text without changing the main experimental protocol\.

Table 15:Sweep over fixed budgets on synthetic benchmarks\. The comparison shows how ZoAQ combines the efficiency of smaller budgets with the performance of larger budgets without manual tuning of the query count\.
### G\.8Controller Variants

This diagnostic checks whether the query savings come from the full accept/expand/reset controller rather than from disabling one side of its decision rule\. These are ablation\-only controllers, not additional branches used by the final ZoAQ algorithm\. All variants share the same history\-reuse estimator and update backbone; they differ only in how the momentum\-consistency test is acted upon\.

- •ZoAQ\-Adaptive: the reported controller, which accepts the first budget whose history\-reuse estimate passes the momentum\-consistency gate and otherwise expands the local budget up to the cap\.
- •ZoAQ\-AlwaysMomentum: a diagnostic that bypasses rejection by the gate and therefore keeps the behavior with few queries driven by history reuse even when the consistency score would have triggered expansion\.
- •ZoAQ\-AlwaysGradient: a diagnostic that suppresses the history\-reuse acceptance shortcut and relies on the expanded current\-budget estimate instead\.

Table[16](https://arxiv.org/html/2609.22115#A7.T16)shows the results under the neutral threshold settingτ0=0\.0\\tau\_\{0\}=0\.0used for this diagnostic\. The full controller achieves the best balance: the ablation using fewer queries can save queries but reaches worse final gaps, while the ablation using the expanded estimate spends more queries without matching the adaptive controller\. Figure[5](https://arxiv.org/html/2609.22115#A7.F5)shows the corresponding convergence dynamics\.

Table 16:Diagnostic of controller actions\. The full accept/expand/reset controller balances query efficiency and final accuracy across diverse landscapes\.\(a\)Quadratic\(b\)Rosenbrock
Figure 5:Convergence comparison across variants of the controller actions\. The full controller \(ZoAQ\-Adaptive\) provides the best balance between query efficiency and final accuracy\.
### G\.9Threshold Sensitivity

To assess the sensitivity of ZoAQ to the initial consistency thresholdτ0\\tau\_\{0\}, we evaluated the algorithm under different threshold settings\. We use a conservative initialization ofτ0=1\.0\\tau\_\{0\}=1\.0for the main benchmarks \(to enforce strict directional consistency at the start\), and include that default alongside a neutral\-range sweep ofτ0∈\{−0\.5,−0\.3,−0\.1,0\.0,0\.1,0\.3,0\.5\}\\tau\_\{0\}\\in\\\{\-0\.5,\-0\.3,\-0\.1,0\.0,0\.1,0\.3,0\.5\\\}\.

Table[17](https://arxiv.org/html/2609.22115#A7.T17)shows representative numerical results, and Figure[6](https://arxiv.org/html/2609.22115#A7.F6)visualizes the convergence dynamics across all four benchmark functions\. The main stable quantity in this sweep is query allocation: total queries vary little across the listed thresholds\. Final gaps remain in the same qualitative regime but are not threshold\-invariant, especially for stricter positive thresholds on Quadratic\. This is the intended conclusion of the diagnostic: the EMA mechanism reduces sensitivity to initialization, but it does not make the threshold irrelevant\.

Table 17:Numerical sensitivity analysis of the initial thresholdτ0\\tau\_\{0\}\. Query counts are stable across the tested values, while final gaps can vary; the diagnostic supports reduced sensitivity from EMA calibration rather than threshold invariance\.\(a\)Quadratic\(b\)Cubic\(c\)Levy\(d\)Rosenbrock
Figure 6:Sensitivity analysis of the initial thresholdτ0\\tau\_\{0\}across four benchmarks\. The trajectories are broadly stable in the tested range, while the table shows that stricter positive initial thresholds can still affect final gaps\.
### G\.10Sensitivity to the History Window

The history window controls the expected trade\-off between reuse and staleness\. Very small windows are noisy, while overly long windows introduce stale search directions\. On MNIST adversarial attacks, the empirical curve is convex and reaches its best point at the defaultNhist=8N\_\{\\text\{hist\}\}=8used in the main attack experiments\.

Table 18:Sensitivity analysis for history window sizeNhistN\_\{\\text\{hist\}\}on MNIST adversarial attacks\. The defaultNhist=8N\_\{\\text\{hist\}\}=8gives the lowest average query count among the tested settings\.
### G\.11Synthetic Convergence Curves

Figures[7](https://arxiv.org/html/2609.22115#A7.F7)and[8](https://arxiv.org/html/2609.22115#A7.F8)present the complete convergence dynamics for the Quadratic, Cubic, and Levy functions, complementing the Rosenbrock results shown in the main paper\. The plots support three qualitative patterns in the tested suite:

- •Efficiency: ZoAQ \(green\) often reaches a low\-error region with fewer queries than the fixed\-budget baselines in the ‘Gap vs\. Queries‘ plots\.
- •Overhead: StatZO \(blue\) shows an initial lag on the Quadratic and Cubic functions, consistent with the diagnosed overhead from validation\.
- •Cost: Methods with fixed budgets consume the query budget set by the protocol regardless of local difficulty\.

\(a\)Quadratic Function\(b\)Cubic Function
Figure 7:Full convergence dynamics on smooth landscapes \(Quadratic and Cubic\)\. The curves show ZoAQ \(green\) reaching low objective gaps with fewer queries in these tested settings\.\(a\)Levy Function\(b\)Rosenbrock Function
Figure 8:Full convergence dynamics on difficult landscapes \(Levy and Rosenbrock\)\. The plots test whether the same adaptive\-query behavior persists beyond smooth objectives\.

## Appendix HAdditional Mechanism Diagnostics

This section gathers the secondary mechanism diagnostics referenced from the main synthetic discussion\. The subsections below separate the effects of reset policy, threshold dynamics, stress tests under changing objectives, and the failure mode of the norm trigger so that each diagnostic supports a distinct question\.

### H\.1Reset Ablation

Table[19](https://arxiv.org/html/2609.22115#A8.T19)presents the numerical comparison of different budget reset strategies\. After an accepted step, ‘min’ resets the next search toKminK\_\{\\min\}, ‘half’ restarts from the midpoint betweenKminK\_\{\\min\}and the accepted budget, and ‘linear’ continues from the previous accepted budget and therefore reduces reset aggressiveness\. The ‘Min’ policy \(Greedy Reset\) is the most query\-efficient among the tested reset strategies across the benchmark functions\.

Table 19:Ablation study: performance across reset strategies \(summarized\)\. ‘Min‘ minimizes total queries across all functions; ‘Linear‘ often yields the smallest final gap but at ~1\.06M queries\.
### H\.2Threshold Dynamics

Figure[9](https://arxiv.org/html/2609.22115#A8.F9)illustrates the dynamic evolution ofτt\\tau\_\{t\}\. The EMA threshold records the recent scale of the momentum\-consistency score: lower values relax the gate after inconsistent evidence, while higher values require stronger agreement before accepting a low\-budget step\.

\(a\)Quadratic\(b\)Cubic\(c\)Levy\(d\)Rosenbrock
Figure 9:Dynamics of the effective thresholdτt\\tau\_\{t\}across functions\. The EMA adapts the gate to the observed momentum\-consistency scale, lowering it after inconsistent evidence and keeping it higher when recent accepted scores remain strong\.
### H\.3Controlled Objective Switch

A key concern with history reuse is whether stale gradients could trap the optimizer when the landscape changes abruptly\. We design a Sharp Turn stress test to directly evaluate ZoAQ’s drift\-detection capability\.

#### Protocol\.

We optimize the Rosenbrock function \(d=100d=100\) for 15,000 iterations, then instantly switch the objective to the Levy function \(samedd\) and continue for another 15,000 iterations\. This simulates an abrupt distribution shift where accumulated momentum points in a fundamentally wrong direction\.

#### Results\.

Figure[10](https://arxiv.org/html/2609.22115#A8.F10)shows the optimality gap\. The apparent drop at step 15,000 is expected because Rosenbrock has naturally larger objective values than Levy\. After the switch, ZoAQ reaches a lower final loss than R\-AdaZO in this test, indicating that the retained buffer does not trap the method in the old landscape under this protocol\.

Figure 10:Optimality Gap during the Sharp Turn test\. After the switch atT=15T=15k, ZoAQ adapts faster to the new Levy landscape, reaching a lower final objective than R\-AdaZO\.
#### Mechanism:τt\\tau\_\{t\}as a drift\-sensitive trigger\.

Figure[11](https://arxiv.org/html/2609.22115#A8.F11)shows that, at the switch point,τt\\tau\_\{t\}drops sharply toward zero, indicating a mismatch between the momentum accumulated on Rosenbrock and the new Levy geometry\. The failed\-consistency phase refreshes the buffer through added queries, while the lower EMA threshold records the new local score scale rather than treating the old high\-consistency regime as still valid\.

Figure 11:ZoAQ’s effective thresholdτt\\tau\_\{t\}during the Sharp Turn\. The drop atT=15T=15k shows that the momentum\-consistency trigger reacts to the abrupt landscape change\.
#### Takeaway\.

This experiment shows that ZoAQ refreshes its history after the objective changes\. The momentum\-consistency trigger detects the mismatch, adds fresh evidence during failed tests, and recalibrates the acceptance scale\.

### H\.4Trigger Metric Ablation

The main text compares the momentum\-consistency trigger with a relative norm trigger,

‖𝒈t−𝒎t−1‖‖𝒎t−1‖≤cnorm\.\\frac\{\\\|\\bm\{g\}\_\{t\}\-\\bm\{m\}\_\{t\-1\}\\\|\}\{\\\|\\bm\{m\}\_\{t\-1\}\\\|\}\\leq c\_\{\\text\{norm\}\}\.\(96\)This ablation asks whether matching vector magnitude is a useful allocation signal in the reported high\-dimensional setting\. It is not used as a theoretical lower bound on norm\-based adaptive sampling\.

Two effects can make Eq\.[96](https://arxiv.org/html/2609.22115#A8.E96)more demanding than a cosine trigger\. First, the paired Gaussian contribution has the local second\-moment scale in Eq\.[31](https://arxiv.org/html/2609.22115#A1.E31), so finite\-direction estimates can fluctuate substantially in magnitude even when their directions are useful\. Second, the denominator becomes sensitive when the momentum norm is small\. A relative norm trigger may therefore expand the budget in response to radial fluctuation as well as directional disagreement\.

The formal descent result in Appendix[E](https://arxiv.org/html/2609.22115#A5)isolates this distinction with a globally normalized proxy update: its one\-step bound depends on angular alignment and not on the candidate norm\. This statement should not be extended automatically to the experimental R\-AdaZO update\. Coordinatewise second\-moment preconditioning need not preserve Euclidean angles; the ablation below is empirical evidence about the tested controller and backbone, not a proof of scale invariance for Adam\-style updates\.

Figure[12](https://arxiv.org/html/2609.22115#A8.F12)reports the comparison\. On Rosenbrock withd=10,000d=10\{,\}000, the relative\-norm trigger uses 28\.1% more queries to reach the same target loss, while ZoAQ obtains a larger loss drop per 1k queries \(1\.9 versus 1\.3\)\. The result supports the use of directional consistency in this operating regime without implying that norm\-based criteria are universally inferior\.

Figure 12:Trigger\-metric ablation on Rosenbrock \(d=10,000d=10\{,\}000\)\. In this run, the relative\-norm trigger requires 28\.1% more queries to reach the same target, and its loss drop per 1k queries is 1\.3 versus 1\.9 for momentum consistency\.

## Appendix IQuery\-Reuse Diagnostics

This section connects the stored\-response estimator analyzed in Appendix[B](https://arxiv.org/html/2609.22115#A2)to the empirical momentum\-consistency traces\. Its purpose is diagnostic: the formal guarantees come from candidate accuracy and debiased\-EMA tracking, not from treating overlap\-induced agreement as a certificate by itself\.

### I\.1Fresh and Stored\-Response Estimation

A fresh spatial estimator uses only directions acquired at the current step,

𝒈tfresh=1Kt​∑k=1Kt𝒈μ​\(𝜽t,𝒖t,k\)\.\\bm\{g\}\_\{t\}^\{\\text\{fresh\}\}=\\frac\{1\}\{K\_\{t\}\}\\sum\_\{k=1\}^\{K\_\{t\}\}\\bm\{g\}\_\{\\mu\}\(\\bm\{\\theta\}\_\{t\},\\bm\{u\}\_\{t,k\}\)\.\(97\)ZoAQ instead averages the contributions observed at acquisition in its candidate record set,

𝒈thist​\(K\)=1nt​\(K\)​∑j∈𝒥t​\(K\)Xj,Xj=rμ​\(𝜽aj,𝒖j\)​𝒖j\.\\bm\{g\}\_\{t\}^\{\\text\{hist\}\}\(K\)=\\frac\{1\}\{n\_\{t\}\(K\)\}\\sum\_\{j\\in\\mathcal\{J\}\_\{t\}\(K\)\}X\_\{j\},\\qquad X\_\{j\}=r\_\{\\mu\}\(\\bm\{\\theta\}\_\{a\_\{j\}\},\\bm\{u\}\_\{j\}\)\\bm\{u\}\_\{j\}\.\(98\)Retained records therefore increase the effective sample count without new function evaluations, but they target gradients at their acquisition iterates\. The exact trade\-off is the error envelope

‖𝒈thist​\(K\)−ht‖≤q⁡\(nt​\(K\),δ\)\+L​At​\(K\)nt​\(K\)\.\\\|\\bm\{g\}\_\{t\}^\{\\text\{hist\}\}\(K\)\-h\_\{t\}\\\|\\leq q\(n\_\{t\}\(K\),\\delta\)\+\\frac\{LA\_\{t\}\(K\)\}\{n\_\{t\}\(K\)\}\.\(99\)The first term decreases with accumulated evidence; the second prices movement since acquisition\. Their balance is the mechanism used by the theory\.

###### Proposition I\.1\(When Momentum Consistency Is Interpretable\)\.

Suppose the simultaneous candidate event holds, and let accepted estimates satisfy‖𝐠r−hr‖≤εr\\\|\\bm\{g\}\_\{r\}\-h\_\{r\}\\\|\\leq\\varepsilon\_\{r\}\. Then Proposition[C\.1](https://arxiv.org/html/2609.22115#A3.Thmtheorem1)gives

‖𝒎~t−1−ht‖≤∑r<tw¯r,t​εr\+L​Dtema\.\\\|\\widetilde\{\\bm\{m\}\}\_\{t\-1\}\-h\_\{t\}\\\|\\leq\\sum\_\{r<t\}\\bar\{w\}\_\{r,t\}\\varepsilon\_\{r\}\+LD\_\{t\}^\{\\text\{ema\}\}\.\(100\)If the right\-hand side is at mostκt​‖ht‖\\kappa\_\{t\}\\\|h\_\{t\}\\\|, a passing score obeys the alignment bound in Eq\.[64](https://arxiv.org/html/2609.22115#A3.E64)\. Thus history reuse can stabilize the score through improved candidate accuracy, while FIFO staleness and EMA lag determine whether that score still represents current geometry\.

###### Proof\.

Equation[100](https://arxiv.org/html/2609.22115#A9.E100)is Eq\.[57](https://arxiv.org/html/2609.22115#A3.E57)with the certificates for accepted candidates substituted\. The final statement is the soundness part of Theorem[C\.3](https://arxiv.org/html/2609.22115#A3.Thmtheorem3)\. ∎

The proposition also explains why raw agreement alone is insufficient\. A large stale buffer may make consecutive estimates visually stable while tracking an outdated direction\. The path\-length terms in Eqs\.[99](https://arxiv.org/html/2609.22115#A9.E99)–[100](https://arxiv.org/html/2609.22115#A9.E100)exclude precisely this failure mode\.

### I\.2Cosine Stability

We record the cosine similarity between the candidate estimate and the previous momentum throughout optimization\. Figure[13](https://arxiv.org/html/2609.22115#A9.F13)reports the synthetic diagnostics\.

\(a\)Quadratic\(b\)Cubic\(c\)Levy\(d\)Rosenbrock
Figure 13:Synthetic cosine similarity between the candidate estimate and previous momentum under the 60k\-step protocol\. Curves are recorded every 100 iterations and averaged over five runs; faint lines show the recorded means and dark lines show smoothed trends\. ZoAQ remains more persistently positive than the displayed baselines in these runs\.The comparison is descriptive rather than a direct measurement of the theorem’s tracking ratio\. A positive trace is consistent with a stable reference, but the guarantee additionally requires the candidate and path\-length bounds above\.

Figure[14](https://arxiv.org/html/2609.22115#A9.F14)gives the corresponding black\-box attack diagnostic\. The same qualitative pattern appears in this setting: the history\-reuse variants maintain a more persistent positive similarity signal, whereas the spatial variants fluctuate more strongly\.

\(a\)R\-AdaZO \(Spatial\)\(b\)ZO\-AdaMM \(Spatial\)\(c\)ZoAR \(History Reuse\)\(d\)ZoAQ \(History Reuse\)
Figure 14:Momentum\-consistency traces during black\-box adversarial attacks on MNIST\. History\-reuse variants show a more persistently positive signal than the spatial variants in the reported runs\.
### I\.3Query\-Space and Update\-Space Averaging

History reuse and momentum average at different stages\. Equation[98](https://arxiv.org/html/2609.22115#A9.E98)pools acquisition records before a candidate is accepted\. Momentum then averages the sequence of accepted estimates:

𝒎t=\(1−β1\)​∑r=1tβ1t−r​𝒈r\.\\bm\{m\}\_\{t\}=\(1\-\\beta\_\{1\}\)\\sum\_\{r=1\}^\{t\}\\beta\_\{1\}^\{t\-r\}\\bm\{g\}\_\{r\}\.\(101\)The first operation trades sampling concentration against response staleness; the second trades estimate noise against trajectory lag\. Their effects are complementary but not interchangeable, and both costs appear explicitly in the proofs\.

This view suggests a practical design rule\. A longer history is useful in noisy, slowly moving regions, whereas faster movement favors a shorter history\. The capacity scale in Eq\.[51](https://arxiv.org/html/2609.22115#A2.E51)makes this dependence explicit\. Similarly, the momentum parameter should be interpreted through the lag factor\(1−β1\)−1\(1\-\\beta\_\{1\}\)^\{\-1\}in Eq\.[58](https://arxiv.org/html/2609.22115#A3.E58), rather than as cost\-free smoothing\.

### I\.4Diagnostic Scope

The figures support two empirical observations: candidates built from stored responses yield a more stable score in the reported regimes, and failed tests add fresh evidence before the candidate is accepted\. They do not show that overlap guarantees correctness\. Formal interpretability requires the same ingredients as the main theorem\. These are candidate concentration valid under selection, bounded acquisition staleness, debiased EMA tracking, and a feasible threshold band\.

## Appendix JLimitations and Future Directions

We currently retain a fixed numberNhistN\_\{\\text\{hist\}\}of recent records and initialize the EMA threshold with a warm start\. Our window sweep and controlled objective switch show when reused responses remain helpful and when they become stale\. Adapting or reweighting the retained history as the trajectory changes is therefore a natural next step\. The present analysis assumes explicit bounds on iterate movement, EMA tracking, thresholds, and local query budgets; extending it across initialization, resets, and record pruning would give a fuller account of transient behavior\. We evaluate forward\-pass fine\-tuning on OPT\-1\.3B and OPT\-13B with SST\-2 and COPA\. Broader model families, tasks, and training horizons remain to be studied\.