A General Framework for Black-Box Attacks Under Cost Asymmetry
Authors: Mahdi Salmani
Alireza Abdollahpoorrostam
Seyed-Mohsen Moosavi-Dezfooli
Venue: ICLR 2026 Poster (2026)
Keywords: zeroth-order optimization
asymmetric cost
black-box adversarial attacks
Primary area: interpretability and explainable AI

Abstract: Traditional decision-based black-box adversarial attacks on image classifiers aim to generate adversarial examples by slightly modifying input images while keeping the number of queries low, where each query involves sending an input to the model and observing its output. Most existing methods assume that all queries have equal cost. However, in practice, queries may incur *asymmetric costs*; for example, in content moderation systems, certain output classes may trigger additional review, enforcement, or penalties, making them more costly than others. While prior work has considered such asymmetric cost settings, effective algorithms for this scenario remain underdeveloped. 
In this paper, we introduce asymmetric black-box attacks, a new family of decision-based attacks that generalize to the asymmetric query-cost setup. We develop new methods for boundary search and gradient estimation when crafting adversarial examples. Specifically, we propose *Asymmetric Search (AS)*, a more conservative alternative to binary search that reduces reliance on high-cost queries, and *Asymmetric Gradient Estimation (AGREST)*, which shifts the sampling distribution in Monte Carlo style gradient estimation to favor low-cost queries.
We design efficient algorithms that reduce total attack cost by balancing different query types, in contrast to earlier methods such as *stealthy attacks* that focus only on limiting expensive (high-cost) queries. We perform both theoretical analysis and empirical evaluation on standard image classification benchmarks. Across various cost regimes, our method consistently achieves lower total query cost and smaller perturbations than existing approaches, reducing the perturbation norm by up to 40\% in some settings.

Published as a conference paper at ICLR 2026
A GENERAL FRAMEWORK FOR BLACK-BOX ATTACKS UNDER COST ASYMMETRY
Mahdi Salmani
Alireza Abdollaahhhhhoorrrssttm EPFL al reza abdol htt.raaaabblllpppprrrrtaaae.....
University of Southern Califoria sa manissuus.. edu
Seyed-Mohsen Moosavi-Dezfooli Apple
snoosavi@apple.com
ABSTRACT
Traditional decision-based black-box adversarial attacks on image classifiers aim to generate adversarial examples by slightly modifying input images while keeping the number of queries low, where each query involves sending an input to the model and observing its output. Most existing methods assume that all queries have equal cost. However, in practice, queries may incur asymmetric costs; for example, in content moderation systems, certain output classes may trigger additional review, enforcement, or penalties, making them more costly than others. While prior work has considered such asymmetric cost settings, effective algorithms for this scenario remain underdeveloped. In this paper, we introduce asymmetric black-box attacks, new family of decision-basee attacks that generalize the asymmetric query-cost setup. We develop new methods for boundary search and gradient estimation when crafting adversarial examples. Specifically, we propose Asymmelric Search (AS), more conservative alternative to binary search that reduces reliance on high-cost queries, and Asymmetric Gradient Estimation (AGREST), which shifts the sampling distribution in Monte Carlo style gradient estimation to favor low-cost queries. We design efficient algorithms that reduce total attack cost by balancing different query types, in contrast to earlier methods such as stealthy attacks that focus only on limiting expensive (high-cost) queries. We perform both theoretical analysis and empirical evaluation standard image classification benchmarks. Across various cost regimes, our method consistently achieves lower total query cost and smaller perturbations than existing approaches, reducing the perturbation norm by up to 40% in some settings. The code for Asymmetric Attacks is available at github. gittii....o.mmmddiiiaaaaaaaammee
INTRODUCTION
Decision-baat basedd adversarial attacks, first introduced by Brendel al. (2017), generate adversarial examples in black-box settings by systematically querying a classifier and observing only its output decisions for perturbed inputs. The original Boundary Attack (Brendel al., 2017) initially required over 100,000 queries to reliably identify minimal adversarial perturbations for large-scale datasets such as ImageNet (Deng al., 2009). Subsequent works (Chen et al., 2020: Chen & Gu, 2020; Cheng et al., 2018: 8; 2019; Liu et al., 2019b; Rahmati et al., 2020) significantly enhanced the efficiency of decision-based attacks by reducing the number of queries needed, achieving improvements of one to three orders of magnitude. These advancements have led to more practical and efficient frameworks for adversarial testing in limited-query settings.
While prior work (discussed in detail in App. A) has primarily assumed that all queries have equal cost and focused on minimizing the total number of queries, in many practical scenarios, queries can incur asymmetric costs depending their nature. For instance, Not Safe for Work (NSFW) image detection models have become increasingly important, with major platforms such as Facebook (Facebook, 2024) and X (formerly
2024a) deploying automated mechanisms for identifying sensitive

---

Published as a conference paper at ICLR 2026
content, alongside commercial APIs developed by Google(Google, 2024). Amazon (Amazon, 2024), and Microsoft (Microsoft, 2024). In these settings, submitting explicit or borderline explicit queries could trigger more severe consequenees, such account suspension or content flagging, compared to benign queries. As a result, minimizing only the total number of queries is insufficient; effective attack strategies must account for the asymmetric costs associated with different types of queries.
Debenedetti et al. (2024) introduced stealthy attack techniques to better handle asymmetric query costs. They empirically demonstrated that the standard binary search procedure for boundary point detection, mostly for projecting an adversarial point onto the decision boundary or for OPT-style gradient estimation (Cheng et al., 2018). leads a large number of high-cost queries. In particular, it can be observed from Fig. I that at least 50% of the queries made during these attacks are high-cost. To address this, they replaced the binary search with a search strategy inspired by the classic egg dropping problem (Alves et al., 2024), which is similar to a line search algorithm. However, they did not provide a stealthy variant of the Monte Carlo gradient estimation used in HSJA (Chen et al., 2020), GeoDA (Rahmati et al., 2020), and qFool (Liu et al., 2019b). Instead, they substituted it with an OPT-style gradient estimation procedure (Cheng et al., 2018).
Although stealthy attacks move toward addressing asymmetric query costs, they are not designed to handle arbitrary cost ratios. They implicitly assume that benign queries have zero cost, which may not reflect realistic settings where even benign queries contribute to the overall cost. In addition, since stealthy attacks could not adapt the Monte Carlo gradient approximation used in HSJA (Chen al., 2020), they instead rely on a suboptimal and inefficient OPT-style gradient estimation (Cheng et al., 2018), which is already significantly outperformed by the HSJA gradient approximation under symmetric cost settings. These limitations motivate us answer the following question:
Q: How can we develop an efficient framework to adapt attacks for any arbitary cost ratio without discarding any of their core components, including gradient estimation and binary search?
In this work, we propose a general framework for decision-basee attacks that operates under ar- bitrary query cost asymmetries. Instead of only considering high-cost queries, we change the core components of black-box attacks, namely search along adversarial paths and gradient estimation, to explicitly reduce the total query cost. Our framework handles any cost ratio between high-cost and low-cost queries and completely outperforms stealthy attacks by op- timizing the attack structure without sacrificing efficiency. Unlike stealthy attacks (Debenedetti et al., 2024), which rely on inefficient gradient approximations, we retain the more efficient Monte Carlo gradient estimation technique used in HSJA (Chen et al., 2020), GeoDA (Rahmati et al., 2020), and qFoo (Liu et al., 2019b).
Query efficiency vanilla and steathyy stlacks on ImageNet
S Brodttyees Weee Woris)
Vanilla Astarks Stalthy Attacks
Total Quertes (Quaa)
10
10s
(630 TTNUMR
100
Corradta--GGiDAA (Cuuri
OPT (.711)
30
SIGN-OPT (1,238 9.RM)
(HO0 1,7000
10
Flagged Queries (Q (haged)
Figure 1: Each point represents the median number of queries required by an attack method to reach median Eg norm of 10. The x-axis shows the num- ber of flagged queries (Qunggedd) and the y-axis re- ports the total number of queries (Quna)) It demon- strates the superiority of our method in achieving a more favorable trade-off between flagged and total number of queries in stealthy attack settings.
First, for the boundary search, instead of dividing the interval into two equal parts at each iteration, as in the standard binary search, we take a more conservative strategy. Specifically, we split the interval according to the cost ratio between high-cost and low-cost queries. This approach minimizes the expected cost rather than merely minimizing the expected number of queries. We call this method Asymmetric Search (AS).
Second, unlike traditional gradient estimation where samples are drawn from a norm ball centered at a boundary point, which causes roughly half the queries to be high-cost and the other half low-cost as in standard HSJA, we shift the center to a point in the low-cost region and generate queries around it (Fig. 2). This adjustment naturally reduces the frequency of high-cost queries, with the degree of shifting providing direct control over this frequency. To further reduce variance in estimation, we weight high-cost and low-cost queries differently when computing the gradient. We refer to this method as Asymmetric GRadient ESTimation (AGREST). Our framework is broadly compatible with a wide range of state-of-the -fte----tthtrrr-r-e art decision-basse attacks, including HSJA (Chen et al., 2020), GeoDA (Rahmati et al., 2020), and CGBA (Reza et al., 2023). Through both theoretical analysis and extensive experimental evaluation, show that AGREST consistently outperforms existing attacks
2

---

Published as a conference paper at ICLR 2026
Clcan (llagge)
Advorsarial (hon-flagged)
c 2
4
1|x; - x'1l
by
bm
(xe)
2x
1x
by
b
b
28
Xt
(() +1
2
1x
by
bi
m
=
28
1x
Figure 2: Left. Illustration of Asymmetric Gradient Estimation (AGREST). which reduces the frequency of high-cost queries by shifting the sampling region from x, toward the adversarial region x and appropriately reweighting the outcomes. Right. Three steps of Asymmetric Search (AS) along the path from clean (flagged) source image adversarial (non-flagged) image. Flagged queries are shown in red, non-flagged queries in green, and the dashed line denotes the decision boundary.
under arbitrary cost ratios. Notably, even under extreme asymmetry where the cost of high-cost queries approaches infinity, our method achieves significantly lower total query costs reach given adversarial perturbation size compared to prior stealthy methods (Debenedetti et al., 2024) (see Fig. 1 (left)). This robustness underscores the effectiveness of our framework in balancing query efficiency and perturbation quality across diverse attack scenarios.
The contribution of our paper is as follows:
To the best of our knowledge, we are the first to propose a versatile framework capable of handling arbitrary query cost ratios, providing flexibility across a wide range of scenarios.
Our framework introduces AS and AGREST as two core operations that enhance existing algorithms. We conduct a comprehensive theoretical analysis to establish the foundations of the framework and demonstrate its robustness across diverse setups.
We validate the framework through extensive empirical testing on benchmark datasets and models, including ImageNet, well as advanced models such CLIP and Vision Transformers and ResNet. This validation highlights the framework's superior performance.
PROBLEM STATEMENT
An insight into unequal queries. Consider an attacker trying to deceive an NSFW detector using decision-based methods. It may seem sufficient to choose an existing attack algorithm and add a small perturbation to an NSFW image based on that algorithm. However, this approach may encounter some practical obstacles. Most social networks enforce policies against uploading adult content, suspending users for violating these terms multiple times (Twitter, 2024a). Using the terminology from Debenedetti et al. (2024), this means that the cost of queries identified by the detector as NSFW, i.c., flagged queries, is higher than that of other queries, i.c., non-flagged queries. For example, X. attacker can make up to 2,400 posts per day single account (Twitter, 2024b). However, after about 5 to 10 rule violations for uploading flagged posts, the attacker's account will be suspended, requiring them to create attacks, approximately half of the made queries are flagged (Debenedetti et al., 2024). Therefore. if we assume the violation limit is 10, an attacker will be banned on X after about 20 posts. This example demonstrates the potential asymmetry in the costs of queries in decision based black-box setup. Debenedetti al. (2024) addressed this asymmetry in costs by proposing stealthy attacks' designed to reduce the number of flagged queries. However, they overlooked the cost of non-flagged queries in their framework, leading to the generation of millions of non-flagged queries for every hundred flagged queries in stealthy attacks, which can also be costly.
one. On the other hand, in existing decision- based
For example, in the NSFW detector scenario, assume the attacker must create new account after reaching the daily post limit. In stealthy attacks like HSJA, the attack can generate around 106
Hereafter. we refer to prior stealthy attacks simply as stealthy attacks, and to our approaches as asymmetric attacks to emphasize their cost-aware design. Though inherently stealthy due to query cost awareness, we adopt the term asymmetric attacks distinguish our method from prior work (Dehenedetti et al., 2024).
3

---

Published as a conference paper at ICLR 2026
non-flagged queries for every 100 flagged queries (Fig. 1). While 100 flagged queries may lead to the creation of 10 new accounts, those 10th non-flagged queries result in approximately 400 new accounts. This shows that non-flagged queries, despite being lower-cost, have greater overall impact. Therefore, it is essential to develop generalized decision-based attacks that can effectively manage asymmetric query costs, making full use of low-cost queries without relying heavily on expensive ones.
General formulation. Assume that f : Rd R is a pre-trained classifier with L classes and parameters 0. For an input image x E [0. 11s. fx (x), the 14th component of f (x), represents the predicted probability of the 1tth class. Additionally, for each correctly classified image x and query image x', we define
Sx (x') = arg max fir (x) - F5(x) (x') and Φx (x')
= sign (Sx (x')).
(1)
kx)(()
Given correctly classified source image x", the attacker's goal is to find the closest perturbed image x' to the source image x' such that dx (x') =
minimize ||xx xx'l s.t. (x)) =.
(2)
Note that in a decision-basee based black-box setup, the attacker has access to Øx- (x') but not Sx- (x'). Previous methods sought to solve Eq. (2) while keeping the total number of queries as low as possible. However, as discussed, asymmetric query costs can make this approach ineffective. Instead, we must keep the total cost of queries in an asymmetric setup as low as possible (Debenedetti et al., 2024):
cost := Queal CD + Qiagged
Cilagged
where Qtaeged is the number of flagged queries (o (x) -1), and Quotal is the total number of queries. Our goal is to solve this for arbitrary values of and Cuageed. unlike stealthy attacks where Cp O. Since only the relative magnitude of Ciagged with respect to cy matters, we use the following reformulation to reduce the number of tunable parameters:
cost := enon-Blagee + Q Riagged c²,
where c* Cilaagee + Co Existing decision- based attacks assume c* = 1, while stealthy attacks
Co
assume c* = oc. Our goal in this paper is to propose framework that is effective for any arbitrary value of c², unlike both vanilla and stealthy attacks. Furthermore, we demonstrate that our approach outperforms stealthy attacks even when c* 20.
For brevity, we omit x* when mentioning S and o. We also refer to queries x' where @(x') -1 as high-cost queries and others as low-cost queries. These new terms reflect the concept of general asymmetric costs better than the previous terms used by Debenedetti et al. (2024), i.e., flagged and non-flagged queries, which more suitable when the discrepancy between query costs is too large.
3 PROPOSED METHOD
Decision-basee black-box attacks typically involve two core operations, often applied iteratively to find small adversarial perturbations: 1. choosing path, either straight, like GeoDA and HSJA (Rahmati et al., 2020; Chen et al., 2020), or curved, like SurFree and CGBA (Maho et al., 2021; Reza al., 2023), and then 2. Searching along this path to find a new adversarial example, X that is closer to x* than xx, the adversarial example from the previous iteration. These attacks either choose a path randomly, as in Boundary Attack (Brendel et al., 2017) and SurFree, or use queries to find a path that leads to closer adversarial example than random path, as in HSJA, GeoDA, and CGBA. To find this better-than thanddooaa- path, these attacks estimate the normalized gradient direction of S at x, by approximating VS (x.) as follows:
VS (xii
Σ Φ (x: + du;) u,
(5)
where 5 a small positive parameter and u1...., Uny are i.i.d. draws from either the uniform distri- bution over gd the (d --ddmennsiin unit sphere, the multivariate normal distribution. After finding a path, most attacks use variations of binary search to find X,+1. This is generally achieved by finding a boundary point x,41 along the selected path, where S (x++1) O, using binary search.
4

---

Published as a conference paper at ICLR 2026
As highlighted by Debenedetti et al. (2024), the issue with binary search and Eq. (5) is that, in an asymmetric setup, crafting adversarial examples using these operations becomes costly because approximately half of the generated queries high-cost. This raises the question of whether we can alter the distribution of generated queries to reduce the number of high-cost queries while maintaining the effectiveness of these two operations as observed in vanilla attacks. As solution, we propose AS and AGREST techniques in the following sections.
3.1 ASYMMETRIC SEARCH (AS)
We define T: [0, 1] + R as the function that parameterizes the search path. For example, when the path is a straight line between the source image x" and an adversarial image x Rahmati et al. (2020); Chen et al. (2020), the parameterization is given by T(0) = 0x* + (1 0) X. Similarly, when the search path follows a circular are Reza et al. (2023); Maho et al. (2021) between x* and &, lying and a unit vector v satisfying (u, v) = 0,
on a circle in the 2D subspace spanned by u = || x 2[,
x-x*
the parameterization is given by T(0) = x" + cos 0)
|| x
l2 (cos (5) u + sin (5)) v).
As mentioned, the objective is to find the along-the- path boundary point T (0*) for some 0* E [0.1]. 1].
Algorithm AS Algorithm
However, since the search space is discrete in practice, our goal is to find a point Xe+1 that is near the boundary, i.e., where (x++1) R 0. This implies that for a given error threshold т, we need to find [a, b] C. [0, 1] such that or E la, bj. Since S is continuous, one approach to achieve this is find 0 < k < [ for which o (T (KT)) = and o (T ((k 1)r))
Inputs: Parametrization function T, thresh- old T Outputs: Near-boundary adversarial exam- plc
b b-a S 5 and
bi t 0, by + [x]
2: while by b > do
bm s b + [+] b
(c +1)
-1. The smaller т is, the closer we get to the boundary, although this requires more queries.
4: if a (T (bmT))
= then
bi + bm
6: else
b + byn binary search is the optimal comparison-based 8: end if
is well-known that one-dimensional search,
algorithm in terms of minimizing the expected number of queries, assuming that the boundary point is uniformly distributed along the path (see Assumption A1). Nonetheless, in the asymmetric cost setting, the expected cost of binary search is θ (c* log (1/T)), because the expected number of queries is θ (log (1/T)), and about half of these queries are expected to incur the higher cost c*.
9: end while
10: return T(b
Assumption A1. Let 0%2 [0,1) be a random variable. 1f)());)) lies on the decision boundary, that is, () = 0, then we assume O,,, is drawn uniformly from [0, 1).
The core idea behind AS is similar to that of binary search, but with a more conservative strategy to account for asymmetric costs. Instead of splitting the interval into two equal parts, AS divides it with a 1 c* ratio at each step, favoring lower-cost queries. More specifically, suppose we know the desired
point lies within [bir, bwT] C: [0, 1]. Then, as shown in Alg. 1, if [T (DITT
+
By Tuy bz
e+11
T
= 1, AS
continues the search in (ur +
bu- c++1 T, buT otherwise, it proceeds within (bLT, byt +
bu-
This process is repeated until AS locates a point within 7 of the boundary.
Note that when e* = 1, AS reduces to standard binary search, and when e* = oc, it becomes a simple line search strategy, as used in stealthy attacks (Debenedetti et al., 2024), where the algorithm checks T, 2T, 3r,.. sequentially. The expected cost of AS is given in Thm. 1, showing that it improves over binary search by factor of θ (log (c* + +1).
Theorem 1. (Cost Analysis of AS) Suppose 0 < T < and c² 2 1. Under Assumption AI, the expected cost of the AS algorithm is O(e" log +1) (1/T)).
To illustrate the effect of AS in practice, we compare the cost of AS and binary search when c* = 103 and we observe that the cost of binary search is approximately 2.5 times higher than that of AS. The results are provided in App. C. An illustration of the AS algorithm can be found in App. I (Right) and Fig. 9.
5

---

Published as a conference paper at ICLR 2026
3.2 ASYMMETRIC GRADIENT ESTIMATION (AGREST)
As mentioned carlier, our goal is adjust the distribution of queries generated during the process. To achieve this, we first propose a family of estimations that provides flexibility in adjusting the distribution of queries used for estimation. Then, we introduce method select the estimator within this family that maximizes the similarity between the approximated gradient and the true gradient.
How can we control the query distribution? The main idea behind AGREST is to estimate point like X/, which is close to X This approach
VS (xx) by approximating the gradient allows us to alter the distribution of made queries while approximating effective directions for the attacks. In this method, we move X, away from x" by wy the overshooting value, to reach the new point x = X + We ||x, -x-1] II (Fig. (left)). Then, we use Eq. (5) at x almost similar to the vanilla estimation, except that AGREST assigns more weight to high-cost queries than to low-cost ones (using importance sampling). In other words, we estimate VS follows:
X,
V (x,, Wt: 5e)
n2
(x/ + ou,) u, te
Rt Φ1
1 no
Σ
X1 Wt
X1 X"
Su:; u;
(6)
n2
||x:
x² 12
= = - 1 = -1} is the sampling weight function, S 3r < 1 is the sampling weight parameter, u1....; un, are i..dd draws from UNIFORM($ and 1(- denotes the indicator function. The parameters We and Br allow us to control the likelihood of making high-cost queries and their associated weight in our estimation.
where (x) = (1-
How can we choose the best AGREST estimator? To ensure the selected estimation is as close as possible to the true gradient direction among all AGREST estimators, one potential solution is find the estimator that maximizes:
plxe, We, m1) = Eut.., cos (xx)) VS (x,, we. 8.)..
within the query budget, where cos represents the cosine similarity function. To calculate this function, we need to assume that S has certain characteristics. One common choice is assume that S is L-smooth However, this assumption introduces excessive complexity to our analysis and may add additional hyperparameters related to to the current set of hyperparameters in the existing attacks. Therefore, similar to Rahmati et al. (2020); Maho et al. (2021) and based on observations from Fawzi et al. (2016), we assume that is locally linear around x,, S(x/ + ōu) Ro ((xx) + (VS())) + du x²). Since x; is boundary point, S(x,) = 0. Thus, we have:
o(x; + 5u)= = sign (VV((x)) x + őu x,)) = sign(cos ag We + (g.,5u)).
(8)
where g: [VS(x>]] and is the angle between x, -x* and ge (Fig. 2). Additionally, based on this assumption, we can calculate the probability of low-cost queries, namely pe (wr) = P[o(x; +ōu) = 1].
(xx,)
using Lem. 1.
Lemma 1. (Hyperspherical Cap Chudnov (1986)) Under local linearity around x2 (Eq. (8)), we have (w(,:) = 1/2 (1 II+Ia-2 2 cos (I where [x(x) = -
Based on Lem. 1, we can infer that ((() is strictly increasing and therefore invertible. Nonetheless, even with the linearity assumption, calculating the expected value remains challenging due to the nonlinearity of cosine similarity and the complexity of handling multiple independent random vectors. Therefore, inspired by measure concentration Ledoux (2001), we approximate ((Xx,, Br, n.) as follows:
J(x,, We, 3r, n²) = (n) E [(x + òu)(g.
ui))
[o(x + ou)²1) 1/2
(9)
This new objective is easier to calculate since it removes the need to deal with multiple random vectors. Thm. 2 establishes a convergence bound for the approximation.
Theorem 2. (Expected Cosine Similarity Approximation) Under the local linearity assumption around X for any constants 0 < z <
& and S q, 3 < 1, as ny and approach infinity, we have
p(x, P. pxxx
(g),
< 0
(10)
J [xx, Pi 3.)

---

Published as a conference paper at ICLR 2026
Now, we formulate the optimization problem. The goal is to maximize J (x,,,w,, we: Se, me) within query budget. Specifically, we want to:
max Re
We, n4) s.t.
nz(c" - - ()))(w))) s cs
(1I)
where et is the maximum allowed cost of estimation at iteration t of the algorithm. The constraint in
Eq. (11) ensures that the expected estimation cost at iteration / is at most ct. To solve this optimization problem, we propose Thm. 3.
Theorem 3. (Optimal AGREST Parameters) Suppose the solution to Eg. (11) is represented by (wt, wf, ng). Given the local linearity around x,, the following statements hold:
1. nt =aaec ((c---(("))p((xt)) -1)p:(wt) and 3 pp(ww))
2. wt maximizes the following function over the interval [o, 6/ cos ore]:
J((w)) (1- ( d-1 ( (polwe) (1 - po(we)) (c" (ce--))((uz))
(12)
An immediate consequence of Lem. and Thm. is the existence of wt such that w = cos d1 w cos 0g . w .... As result, we aim to find wt One problem is that Ia has a complex closed form. Thus, finding a closed form for wn would be challenging. Instead, we use numerical methods to evaluate this integral and numerical optimization techniques find w In partieular, we use QUADPACK Piessens et al. (2012) for the integral calculation and the Nelder-Mead method Nelder & Mead (1965) for maximizing (ww) Another problem is that need to know ax, which is not possible in a black-box setup. Thus, we need to estimate a at each iteration t.
How can we estimate a,? We split this problem into two steps: 1. estimating a1, and 2. under- standing the behavior of a₁ with respect to f. For the first problem, initially, we expect X₁ - x" and gi be somehow independent, as most existing attacks select Xı using a random direction. The only reasonable assumption about these two vectors is that they likely have positive correlation, i.e., (x) x² xi) 2 Specifically, if we know that X1 is the closest boundary point to x* along the direction of x1 x", meaning there is no < < such that o(x* + r(xi - x*)) 1, this
Algorithm Overshooting Scheduler Step
Inputs: Iteration t, dimension d, desired probability p, scheduler rate
Outputs: Next cosine value a4-1 I: 01 INIT-ANGLE (d)
Thm. 4
u
(1 - COs a1) (1+1)-
3: 04+1 < arccos (át+1)
return a++1
assumption provably holds. Given this assumption, we can use Thm. 4 to attain 01.
Theorem 4. (Initial Cosine Value) Under local linearity around x1, there is no 0 < < 1 such that ø(x* + + - -x')) = 1, then we have E [c = - ( (2 (4+1)
The next step is to estimate at after the first iteration. Chen et al. Chen et al. (2020) showed that in HSJA, cos(x; x", x²) 1 cm for some constant and m < 1.2 This motivated us to heuristically estimate ag as arccos(1 - (1 - cos (t))tm)) where m is new hyperparameter introduced to the existing attacks (Alg. 2). As stated in Thm. 3, under the assumption of local linearity, the value of Bg an optimal AGREST estimation is the probability of making low-cost queries. However, similar to Chen et al. (2020), we use the empirical probability of making low-cost z4 ,. to reduce the variance of the estimation. Here, ny and nt represent the
queries, namely
number of high-cost and low-cost queries made in an AGREST estimator, respectively. Additionally,
we set a to the expected cost of the vanilla attack, namely +1(c+11) where ni is the number of made queries by the vanilla attack at iteration f. A detailed overview of AGREST is provided in Alg. 3. Note that in practice, most attacks are performed in given subspace rather than in the entire space to improve sample efficiency. In these cases, we use the effective dimension d' of the subspace instead of d, the dimension of the original space. For more details, see App. D.3. Finally, it is worth mentioning that the probability of making low-cost queries in AGREST closely follows theoretical analysis in practice. Further details and empirical results presented in App. C.
7

---

Published as a conference paper at ICLR 2026
Algorithm 3 AGREST Estimation
Inputs: Iteration t. source image x", boundary point xs, dimension d, high-cost query cost c*, sampling radius 6, sampling batch size b, cosine value or, vanilla gradient estimation query budget ni,, scheduler rate
Outputs: Normalized approximated direction St. next cosine value ac+1
1: nz +0, TH + O, vt + +0, V t- 0, č O, w + OVERSHOOTING (c*)
-Thm.
Ct t ni(c² + 11/2 2: wi t --w"cost
3: while ė < c2 do
4: for each u; UNIFORM(S0-1) 1), 1, ,,..., do xx-x" Xt wt xx1-xx + +du;
5: if Φ
then
6: v f vt + Uis n. t R1 1, ē e+1
7:
else
8:
vV- u, nH t nu +1, c+
9: end if
10: end for
11: end while
Pt + -LL/ (ny + nH)
13: Dt - (1 Dr) v + D.v_ ac+1 < SCHEDULER-STEP (t, (t.p..)
> Alg. 2
14: return 9t/ 9ell, a++1
EXPERIMENTS
Model, dataset, and metric. We employed ImageNet-trainee models: ResNet-50 (He et al., 2016), ViT-B/32, ViT-B/16 (Dosovitskiy al., 2021), and CLIP (Radford et al., 2021). Original images (x") were 500 correctly classified ImageNet validation samples similar to the Dehenedetti et al. (2024). Numerical tasks used SciPy (Virtanen al., 2020). Attack performance
measured by the median l2 distance between perturbations and originals over query costs, consistent with previous work.
Attacks and hyperparameters. We modify SurFree, HSJA, GeoDA, and CGBA by using AS for search and AGREST for gradient estimation where applicable. The other components of the attacks remain largely unchanged (see App. D). Moreover, to compare our framework with stealthy attacks, we use Stealthy HSJA, it outperforms other stealthy attacks when the & norm is the evaluation metric (Fig.
Debenedetti et al. (2024)). For the hyperparameters used in the vanilla attacks, we generally the same values. The only exception is the subspace method in SurFree. Specifically, instead of using the DCT method in SurFree, we set it to DCT This adjustment allows for a fair comparison of SurFree with other attacks, GeoDA and CGBA both the DCT technique. Furthermore, we set the newly introduced hyperparameter m. the overshooting scheduler rate, to 0.02, 0.06, and 0.06 for HSJA, GeoDA, and CGBA, respectively (for more details see App. D.2).
Ablation study. To evaluate the effectiveness of AS and AGREST in different attacks, we test various combinations of these two approaches with each attack when e* 2, 5, 103, or 10 (Tab. 1). As shown in Tab. 1, for SurFree, we compare the vanilla attack with A-SurFree, the new asymmetric attack that utilizes AS, As expected, replacing binary search with AS leads to smaller adversarial perturbations for all c*. Furthermore, we compare the performance of gradient-based attacks with their corresponding variations, namely: 1. Replacing binary search with AS 2. Replacing vanilla gradient estimation with AGREST 3. Combining the two previous approaches to obtain A-HSJA, A- A-GeoDA, A-CGBA, In general, using asymmetric attacks results in incremental improvements when e* 2 5. This is expected because anticipate binary search and vanilla gradient estimation perform well when the cost of high-cost queries is not significantly different from the cost of low-cost queries. However, for larger values of c*, namely 10 and 1 the improvements are substantial. Specifically, using AGREST alone reduces the &g norm by approximately 40% in all cases. Moreover, combining AGREST with AS further decreases the norm. One notable point that AGREST enhances attacks utilizing gradient estimation more than AS does. This occurs because attacks using gradient estimation spend most of their query budget on gradient approximation rather than on search. (Tab. III of Debenedetti et al. (2024)). We also compared several methods, including some baseline transfer attacks, using attack success rate (ASR) as the metric (see App. E).
Comparison to stealthy attacks. As mentioned, for larger values of c", we expect asymmetric attacks significantly improve over vanilla attacks. Nonetheless, in these cases, must compare
8

---

Published as a conference paper at ICLR 2026
Table Median E2 distance for various c* values and different types of attacks across neural network architectures. VA stands for Vanilla Attack. The bold numbers represent the best performance among different variants of each attack for each value and model (For a comprehensive analysis of attacks under varying total cost constraints, we refer readers to Tab. 9 and Tab. 10 in App. F, which present exhaustive experimental results across different total cost budgets and query cost c*))
ResNet-50 50
ViT-B/32
=
===5 5
c'
10
=
10
e
10
c²
10
Trnal Cost of Queries
Attack
Method
10K
15K
150K
250K
10K
15K
150K
250K
VA
4.09
5.19
5.21
17.49
2.9
5.13
16.12
SurFree
VA+AS (A-SurFrce)
3.45
3.52
3.80
7.59
2.4
2.1
3.68
6.35
VA
2.24
2.77
4.66
23.72
18.3
13.9
4.21
22.46
VA+AS
2.16
2.72
4.09
19.07
18.3
13.5
3.88
18.79
HSJA
VA+AGRSST
2.19
2.49
2.7
2.19
11.28
VA+ AGRESST (A-HSIA)
2.13
2.39
2.16
12.28
2.7
2.1
2.06
10.74
VA
2,80
3,21
4.02
10.80
2.7
2.4
3.97
9.83
GcoDA
VA+AS
2.66
3.12
3.32
9.24
2.7
2.3
3.12
VA+AGREST
2.89
2.95
2.19
6.28
1,9
1.7
2.10
5.12
VA+AS+AGREST (A-GeoDA)
2.93
2.8
2.11
5.78
1.9
1.8
2.03
4.35
VA
1.21
1,42
2.22
9.97
1.6
2.13
9.67
CGBA
VA+AGREST
VA+AS
1.12
1.17
1.36
2,06
1.63
5.73
1.7
1.5
1.3
197
1.56
5.46
VARAST (A-CGBA)
1.15
1.58
6.23
1.5
1.42
our framework stealthy attacks, since, unlike with lower to medium values of c*, stealthy attacks outperform vanilla attacks when e* is large (Fig. 7 of Debenedetti et al. (2024)). As a result, we eval- uate the performance A-SurFree, A-HSJA, A-GeoDA, and A-CGBA against Stealthy HSJA on the ResNet model when e* = 10 10a. co. As demonstrated in Fig. 3, when c* 104, all asymmetric attacks, including A A-HSJA which retains the gradient estimation method that Stealthy HSJA discards, outperform Stealthy HSJA. The same holds for e* 10 (Fig. 3). For the case where c cc, follow- ing Debenedetti et al. (2024), we determine the cost each attack by counting the number of high-cost (flagged) queries it generates. In this setup, assume e 10 during the execution of AGREST and AS. As shown in Fig. 3, all asymmetric attacks outperform Stealthy HSJA by a wide margin.
ARBJA
AHSJA
AHSJA
GedDA
GeibA
A-GGA
A-CAAA
Frre
A:SaFiee
disaance
Staalhy H5.A
disaance
Staaldy HBJ4
distance
Staakby HSJ4
Total high-cost queries)
Figure 3: Performance of various asymmetric attacks compared to Stealthy HSJA under high cost asymmetry with ResNet-50, The value of c* is 104, 10", and co from left to right.
Asymmetric attacks against CLIP. We evaluate CLIP (Radford al., 2021) as a representative uision-languas model (VLM) under both zero-shot and fine-tuned settings. Our asymmetric attack achieves significantly better performance than stealthy baselines; results are provided in App. H.
CONCLUSION AND OUTLOOK
We proposed framework that extends existing decision-based black-box attacks to handle asymmetric query costs, where querying the source class is more expensive than others. Our method introduces new gradient estimation and search techniques, achieving significant improvements over both standard and stealthy attack baselines. However, it introduces may require tuning for different settings. Additionally, we assume local linearity around decision boundaries; while this assumption is common in the adversarial examples literature, may not
hyperparameter, which

---

Published as a conference paper at ICLR 2026
hold in practice. There are also many interesting directions for future work, such generalizing the framework beyond the binary setting of source versus non-source classes. For instance, different target classes may each have their own associated query cost. Applying our framework to vision- language models such as Vision LLaMA (Chu et al., 2024) is another promising direction. AS could also enhance jailbreak attacks on large language models, potentially replacing random carch-based methods (Andriushchenko et al., 2024; Chao et al., 2024). though adapting our framework to LLMs presents challenges due the discrete nature of text prompts (Rocamora al., 2025). Exploring these avenues could expand the impact of asymmetric attacks across a wide range of applications.
REFERENCES
Alireza Abdolahpourrostam, Mahed Abroshan, and Seyed-Mohsen Moosavi-Dezfooli. Superdeepfool: new fast and accurate minimal adversarial attack. In The Thirty-eighth Anmual Conference on Neural Information Processing Systems, 2024. URL https: /ttp///ppeeeeeeeeeeeeeee net / forum?
id=pqD7ckR8AA.
Gabriel Alves, Geoff Pilling, James Innes, Refath Bari, Nguyen Quang, Josh Silverman, Ar- ron Kau, and Jimin Khim. Egg dropping. URL
ege-dropping/. 2024. Accessed 26-04-2024.
Amazon. Moderating content. URL https::////. //occs..//////////////////////// aws www.aa..aaao...o.......o wttp//oo..ccomeeegonniiioooo dettett/dg/mddrattioo html, 2024. Accessed 03-05-2024.
Maksym Andriushchenko, Francesco Croce, and Nicolas Flammarion. Jailbreaking leading safety- aligned Iims with simple adaptive attacks, arXiv preprint arXivv2404.02155, 2024.
Wieland Brendel, Jonas Rauber, and Matthias Bethge. Decision beasio adversarial attacks: Reliable attacks against black-box machine learning models. arXiv preprint arXiv: 171.002212 2017.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 ieee symposium security and privacy (sp), pp. 39-57. leee, 2017.
Patrick Chao, Edoardo Debenedetti, Alexander Robey, Maksym Andriushchenko, Francesco Croce, Vikash Sehwag. Edgar Dobriban, Nicolas Flammarion, George Pappas, Florian Tramer, et al. lailbreakbench: An open robustness benchmark for jailbreaking large language models. arXiv preprint arXivv2-40.001318 2024.
Jianbo Chen, Michael I Jordan, and Martin J Wainwright. Hopskipjumpattack: A query-efficient bociiion-bbsed attack. In 2020 ieee symposium on security and privacy (sp). pp. 1277-1294. IEEE, 2020.
Jinghui Chen and Quanquan Gu. Rays: A ray searching method for hard-label adversarial attack, 2020. URL https: //axivv..vvvv.//a org/ abs 20.2.0006222
Pin- Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsich. 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, pp. 15-26, 2017.
Minhao Cheng, Thong Le, Pin-Ye Yu Chen, Jinfeng Yi, Huan Zhang, and Cho-Jui Hsieh. Query-efficient hard-label black-box attack: An optimization-basse approach. arXiv preprint arXiv: 1007.048:00444 04457, 2018.
Minhao Cheng, Simranjit Singh, Patrick Chen, Pin- Yu Chen, Sijia Liu, and Cho-Jui Hsieh. Sign-opt: A query-effcient hard-label adversarial attack. arXiv preprint arXiv:1909 10773. 2019.
Herman Chernoff. A measure of asymptotic efficiency for tests of hypothesis based on the sum of observations. The Annals of Mathematical Statistics, pp. 493-507, 1952.
Xiangxiang Chu, Jianlin Su, Bo Zhang, and Chunhua Shen. Visionllama: A unified Ilama backbone for vision tasks, 2024. URL https:
art/ attaaab///3// /403. 00522.
Alexander Mikhailovich Chudnov. On minimax signal generation and reception algorithms. Problemy Peredachi Informatsii, 22(():49-55 55, 1986.
10

---

Published as a conference paper at ICLR 2026
Edoardo Debenedetti, Nicholas Carlini, and Florian Tramèr. Evading black-box classifiers without breaking eggs. In 2024 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML), pp. 408-424, IEEE, 2024.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference computer vision and pattern recognition, pp. 248-255 leee, 2009.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn. Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale, 2021. URL wwwph:ttts/.ooo... //arxiv////ii//////a org/orrgaas.. 201 0 1929.
Facebook. How does facebook use artificial intelligence to moderate content? URL https: //www. facebook. com/he / 584448858555 6247, 2024, Accessed 03-05-2024.
Alhussein Fawzi, Seyed Mohsen Gooosavi-Dezfooo and Pascal Frossard. Robustness of classifiers: from adversarial to random noise. Advances in neural information processing systems, 29, 2016.
Abraham Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex optimization in the bandit setting: gradient descent without gradient. arXiv preprint cs/0408007, 2004.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572. 2014.
Google. Detect explicit content (safe search). URL https::/ccoot c/clodd. google.com/viss... 2024. Accessed 03-05-2024.
docs / eeteecttttttteteeeeeceeeeeecce
Mor Harchol-Balter Introduction to probability for computing. Cambridge University Press, 2023.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition, In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Andrew llyas, Logan Engstrom, Anish Athalye. and Jessy Lin. Black-box adversarial attacks with limited queries and information. In International conference machine learning, pp. 2137-2146. PMLR, 2018
Michel Ledoux. The concentration of measure phenomenon. Number 89, American Mathematical Soc., 2001.
Huichen Li, Xiaojun Xu, Xiaolu Zhang, Shuang Yang, and Bo Li. Qeba: Query-efficient boundary- based blackbox attack. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 1221-1230, 2020.
Yujia Liu, Seyed Mohsen Moosavi-Dezfooli, and Pascal Frossard. A ceometry-inspiree decision- based attack. In Proceedings of the JEEF/CVF International Conference on Computer Vision, pp.
4890-4898, 2019a.
Yujia Liu, Seyed-Mohsen Moosavi-Dezfooli, and Pascal Frossard. A geometry-inspired decision- based attack, 2019b. URL https::///// http://////aaivooor///////////// 10826.
Thibault Maho, Teddy Furon, and Erwan Le Merrer. Surfree: a fast surrogate- free black-box attack. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10430-10439, 2021.
Microsoft. Detect
adult, racy, or gory content.
URL
https://
learn. wwwso http://sfff..oo/o/oooooooooooa hatom/azre/aaai aaivveiviiiiiiie ces/ http//ompteeeeeeee eennter-vii si-vviiinn sion/ concept-detectingg httprr/ddttttccciiaaaaattttot-ee
2024. Accessed 03-05-2024.
Vitali D Milman and Gideon Schechtman. Asymptotic theory of finite dinensional normed spaces:
Isoperimetric inequalities in riemannian manifolds, volume 1200. Springer Science & Business
Media, 1986.
11

---

Published as a conference paper at ICLR 2026
Seyed Mohsen Moosavi-Dezfoude Alhussein Fawzi, and Pascal Frossard. Deepfool: simple and accurate method to fool deep neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2574-2582 2016.
Nina Narodytska and Shiva Prasad Kasiviswanathan. Simple black-box adversarial perturbations for deep networks. arXiv preprint arXiv: 2016.
John A Nelder and Roger Mead. A simplex method for function minimization, The computer journal, 7(4):308-311 1965.
Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization convex functions. Foundations of Computational Mathematics, 17(2):277556, 2017.
Robert Piessens, Elise de Doncker-Kapengee Christoph W Überhuber, and David K Kahaner, Quad- pack: a subroutine package for automatic integration, volume 1. Springer Science & Business Media, 2012.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. Learning transferable visual models from natural language supervision, 2021. URL https:
Ali Rahmati,, Seyed Mohsen Moosavi-Dezae Pascal Frossard, and Huaiyu Dai. Geoda: geometric framework for black-box adversarial attacks. In Proceedingy of the IEEE/CVF conference on computer vision and pallern recognition, pp. 8446-8455, 2020.
Md Farhamdur Reza, Ali Rahmati, Tianfu Wu, and Huaiyu Dai. Cgba: Curvature-awand geometric black-bor -box attack. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 133,133, 2023.
Elias Abad Rocamora, Grigorios G. Chrysos, and Volkan Cevher. Certified robustness under bounded levenshtein distance, 2025. URL https: org/ abs 13676.
Twitter. X's sensitive media policy. URL https: /tops://help... twi twitter..... /tet::/tt/e.p...ttterrrr
com/en/
rules-and and-aandllin powpciies/mmddaappllloooooeeeeee policy, 2024a. Accessed 03-05-20224
Twitter. Understanding x limits. URL
rulles-and-oolicies//e
2024b. Accessed 04-05-2024.
Pauli Virtanen, Ralf Gommers, Travis Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, al. Scipy 1.0: fundamental algorithms for scientific computing in python. Nature methods, 17(3):261-22) 2020.
Xiaosen Wang, Zeliang Zhang, Kangheng Tong, Dihong Gong, Kun He, Zhifeng Li, and Wei Liu. Triangle attack: A query-efficient decision-based adversarial attack. In European conference computer vision, pp. 156-174, Springer, 2022.
12

---

Published as a conference paper at ICLR 2026
A RELATED WORK
Decision-based attacks. Adversarial examples can be crafted in three setups: white-box (Good- fellow et al., 2014; Moosavi-Dezfool al., 2016; Carlini & Wagner, 2017; Abdolahpourrostam et al., 2024), score-based black-box (Narodytska & Kasiviswanathan, 2016; Chen et al., 2017; Ilyas et al., 2018), and decision- based black-box box (Brendel et al., 2017). In the decision-based black- setup, the attacker relies solely on predictions without access to models or class scores. Moreover, decision-based attacks can be either targeted or non-targered. Non-targeted attacks craft adversarial examples without any constraints on the model's prediction for the adversarial example. Boundary Attack (Brendel et al., 2017) was the first effective decision-based attack based on random walking. OPT (Cheng et al., 2018) outperforms Boundary Attack by introducing gradient-based approach. Inspired by zeroth-order optimization methods (Flaxman et al., 2004; Nesterov Spokoiny, 2017), HSJA estimates the gradient of the classification margin without direct access the margin itself and minimizes perturbation size using optimization techniques (Chen et al., 2020). QEBA (Li et al., 2020) uses various techniques to approximate the gradient of the classification margin more effectively than HSJA, leveraging insights like local similarity and the importance of the low-frequency subspace. GeoDA and qooo (Rahmati al., 2020; Liu al., 2019a) use techniques similar to HSJA's gradient estimation to locally approximate the decision boundary as a hyperplane at cach iteration. They then search for optimal adversarial examples based on these estimated hyperplanes. While gradient-based methods outperform previous approaches, their reliance on generating numerous queries for efficient gradient estimation led (Maho al., 2021) focus on decision boundary geometry. They introduced SurFree, which iteratively selects a random 2D subspace and searches for adversarial examples along a circular path. In a similar way, TriA (Wang et al., 2022) generates effective adversarial examples while using minimal queries. CGBA (Reza al., 2023) combines the gradient approximation method from GcoDA with SurFree's s 2D subspace search technique to achieve state-of-the- oh-the-rrt results.
Asymmetric query costs. Existing decision-based attacks assume all queries have the same cost. However, (Debenedetti et al., 2024) showed this may not be the case in real-world scenarios. They found that queries belonging to the target class can be problematic in certain situations and noted that all decision- based attacks produce many of these bad queries. To mitigate this, they introduced stealthy attacks inspired by the egg dropping problem (Alves et al., 2024). However, stealthy attacks face two main challenges. First, they overlook the cost of queries that are not bad. For example, their most effective attack, Stealthy HSJA, generates about 10? queries for every 1,000 bad queries. Second, to reduce the number of bad queries during the gradient estimation phase, (Debenedetti et al., 2024) replaced the HSJA gradient approximation, known for its benefits in crafting adversarial examples, with OPT gradient estimation, believing that modifying the HSJA gradient estimation to perform well in this new setup would be difficult. In this paper, we address these challenges in non-targeted decision-based based attacks. In particular, we find way to efficiently distribute our total query budget between problematic and non-problematic queries while keeping the HSJA method of gradient approximation by slightly modifying the method.
13

---

Published as a conference paper at ICLR 2026
B PROOFS
B.1 PROOF OF THM.
We define the expected cost of the algorithm for m [ points as C(m). Using Alg. I and applying the law of total expectation, we obtain
((m) j (T (bm=T) (bmT))= = (o(c ((Tm)
c- (1 + ( (bmT))= = (c
c'm 1
c +11
(13)
We now claim that
(m)) < 2c" [loge. m
(14)
We prove this by induction.
For the base case, when m c + 1, Alg. reduces to simple line search. Assuming uniform
distribution for the boundary point, the expected cost of the line search is approximately c* + m/2, which clearly satisfies Eq. (14).
For the induction step, suppose the claim holds for all values smaller than m. Under the uniform distribution assumption for the boundary point, we have
1 PP [ (T (bmr)) =-1 c +1'
(bm =] c* +
Substituting into Eq. (13) and applying the induction hypothesis yields:
((m)
1
C
m
+
+ c* c++1 (c c-(c
cx
) +1)
c.m
c* +1
c*
+1
2c
loge c +1
m
+c")
+
c²
22"
e'm loger+1 c* +1
+1)
c
+
c
+1
Noting that
logo++1 c* +1
171
=
logger +1 (1m) 11 loge+41
c.m
=
log.r+1(11) + log.
(
c
and observing that loge++1 (m))).
< O but close to 0 for large c*, we can bound both ceilings by
Thus.
2ct C(m) <
c*
20*2
log +1 m] + c²
c* +1 (floge--1 mi 1) +
c* +
c +1
ct +1
6* +1
2c [loge- ml.
Thus, the expected complexity of the algorithm is
c" log (1/T) log(c* + +1)
O
completing the proof.
B.2 PROOF OF THM.
Before proving the theorem, we first introduce some useful lemmas.
Lemma 2. (Lévy's Lemma (Milman & Schechtman, 1986; Ledoux, 2001)) Let f :d3d1 R be an L-Lipschitz function on the unit hypersphere, and let x ~ UNIFORM (8d-1). Then, for some constant > 0, we have:
Cdd2
(x)
2exp
"
14

---

Published as a conference paper at ICLR 2026
Corollary 1. Suppose R& is unit vector, and x UNIFORM (S*-1). Then, for some constant C>20, O, we have:
P ((( x) 2) S 2xxp (-Cde²).
Lemma Suppose P f....... R.n, are i..dd Bernoulli random variables with support {8), (1-1:111)) (1-3))3)
where Be 3. 1f oi is i.i.d copy of Φ1 then the following inequality holds:
11
exp (- (2,3g 1)2
2n1
Σ 74
>6
Proof of Lem. 3: The result follows by applying the Chernoff bound for binomial distributions
(Chernoff, 1952; Harchol-Baile 2023) to the transformed random variables
Pi B,)²
3 - 3,)2
which are i...d Bernoulli random variables taking values in {0, 1}.
Lemma 4. Given the local linearity around xs, for any we E [0. cos or
we have:
1=1
( (1- (1-(cos (cos wr/8)²
E
oe (gt, ui)
2/- I(
Proof of Lem. 4: By the law of total expectation and linearity assumption, we have
E
Φ gi. u) = 3 (1 Pa (w)) (g. u\/ (gr. u) S - cos ag w2/d]
(15)
+ (1 - 8,) Pt (w) E [g u) (gr u) > a wr/8]
Now, by applying the divergence theorem the constant vector field F gr, have E | (gr, u (gr. u) s cos we/o] = (-g: gt,
up (u) du)
(g..u)5 cos w1/
(- gi,
udu)
- 1/ p (wi)) Aa (1)
(VI 1- (cos Cr wr/8)²
Va-1
(1 - Pt P.rw)) Ad-1 (1)
r(4) (1- (coos ar w//8)² 1
2/T [( [+11
P. (w,))
(16)
Where Va(r) and (r- are the volume of a d-dimensional ball and the area of d 1-dimensional sphere with radius r, respectively. Note that the last equality comes from Va(r)
x d/22
yd and
[ +
d/2 dd- Similarly, the following holds:
1
r (
r(g) (1 (cos ar we/6)²) 4
E
[(g u) Kg. u) 2 - cos a₁ wr/8]
(17)
2 r( dd1) Pt (wi)
By using Eq. (16) and Eq. (17) in Eq. (15), have
r( (1- (cos 0r wt/ wx) +
E
o (g. u/
(18)
2 [ d+1
2
15

---

Published as a conference paper at ICLR 2026
Lemma 5. Let E1 be given. a (xxe, why Be, nt):
Then the following upper and lower bounds hold for
1. (Upper bound)
n E
@e (gi, u1)
uix We, ne)
E2 - (n+ - -1)8881
/tlr Bc.
+ 1+
Knnd (21,
V |B(081 52 (1e: 1)18E1
2. (Lower bound)
v /n E
oc u)
nxx1, we, Bog nx) 2
E(0z] + 62
(nt - -1)8981
Vne St
Knnd (E1,
ElAl + 62 + (nz - 11)3781
Here, the error term (()) is defined as
2n
Kndd (51, nn(n + 1) exp (-Cde + exx
(2,3, 1)2
for some universal constant C 0.
Proof of Lem. 5: Let 61, E2 > 0 be arbitrary. We define the following sets:
S,(81) U [U.....: Un.)
Kge u,)
81},
St)(E)) = U = (u).... un.)
[u; ا,}س 2 $1h,
1
Sa(E2) = U = (u und)
E
2 82
The i=1
S(51,82) = (SSte) U
U Isi<jšm
SEI(EI)
USa(E2).
s=1
For notational convenience, we also define
M4 H., (ge, ou:).
A(U)
2
Applying Lem. 2 and Lem. 3, and using the union bound, we obtain
[+
e E S] < n. P(U e S,] +
PIU E S1.2l + +P E Sol & Kn 62),
(19)
Now, we derive the upper bound. By the law of total probability, we have
Xt, We, 36) (g
p(xe, We, Br, n4) =
Xxx wiz, 3c)
(g:, S Xt, We, Be))
E
U $ S
PiU S
S Xzy wi, 3r)
(g) V ( Wes Bz)
UES P s).
V V5(x), 3x)
16

---

Published as a conference paper at ICLR 2026
To calculate the desired expected value given the event {U & S}, expand the squared norm directly. By definition,
2
(xts Wes 3r)
-
Ui
T4t
8er Us
8 U
2
74
==1
P (u; U1)
74
8²
Σ
(u.
Li
7
Isijsme $#1
From the previous expansion, we have
8
VS((x, wr, 20)
Bloi
82 - (11 - 1)8781.
/nz
Thus, on the event {U & S}. can bound
gg (x wi, Bc)
1
t4e
gt:
ui
A(U).
VS(Xi, wt: 3.)
VS
V5
2
Therefore,
1r, V
A(U)
VS
8 8 E
(n: 1)5fE1
Taking expectations, we get
VS)
1
E
U Φ S
<
E[A(U)]
8 8 B E2 (n. 1)
Moreover, by independence and identical distribution of the samples, we have
E[A(U)] n,, E (g) u.
Therefore,
vn, E (gr, u1)
(gt
V
U U
<
VS
E - E2 - (n, - 1)87E1
For the event {U E S), we use the trivial bound
(gr, VS)
1
44
2
and hence
gg VS
UES
1
4
17

---

Published as a conference paper at ICLR 2026
Substituting back into the law of total probability, we have
Vne E
Te (B:, u)
,(x;,, We, 3r, ne)
PIU 8)) + P(U S)
V
B
62 (nt 1),8fe1
V E ES]
E
(ne 1)
Grouping terms, obtain
R
Φe (gt: 12)
1xx;, We, Pc. me) s
E2
E2
(n+ 1)18E1
/n Br
+
1+
PIU E S].
82 (n+ - 1)83
Applying the bound P PU E S K Kn,d 62) from Eq. (19), we finally get
/ng EE
De (gt; u1)
Wi, 5
(n, 1),3EE1
E2
Te 3t
1+
Kn,,(E1,,2).
E2
(nt - 1),878
Similarly, for the lower bound, we have
Vng EE
(gi+ u1)
p(x,, Wix We, n4)
82
(n+ -1),8e
Th 3e
+
E2 + (n: - 1)g8e1
This completes the proof of the lemma. We note that the argument does not rely on the linearity assumption.
Lemma 6. Assume local linearity holds around x Then, for any constant
[ 1). we have
Xx - x + +ōu (g., u/ - (
X, x*
④ Xx P.
[
Proof of Lem. 6: Based Lem. 4, analyze the asymptotic behavior of
r and
(1- (cos on w//
tends to infinity.
By Lem. 2, we have
PP [1 8:))
S 2exp (-Cde?).
18

---

Published as a conference paper at ICLR 2026
so in particular
P [ gr) <<E S exp (-Cds²).
We know that 1 1 [P ge) > cos wr/6]. based on the selection of the overshooting value
wy. Thus,
1 - S exp (-Cd (4 wt/
which implies
In(1 - 9) 5 -Cd(coosar wr/
and consequently
14 In(1 - 9)
Cd 3 1 (cos 0z - w²
Raising both sides to the (d - 1)/2 power yields
( 1n(1-9)) 9)
( (cos - w2/8)²) 2
Cd
Applying the classical limit lom (1 + (1)²)²
e", we obtain
In(1 9)
In(1 9)
lim d=000
1+
exp
Cd
2C
which implies that (1 - (cos or : wx//)²)
0 =01))
On the other hand, by Stirling's approximation
2n
2 )
[(n)
1+ O
we find that Now, we proceed to prove the theorem.
r (
Substituting these results into Eq. (18) concludes the proof.
Proof of Thm. 2: For any 0 < z < 3. let n, = d= E1 = d d== and E2 = d=. Also, let
We define
De (ge, u)
74
E =
0
52
(n4 1))3211
/ne 3
Ee
RR
(n+ -1),281
Eg := K K(,,d(E
Then using the upper bound derived in Lem. 5, we have
p(x,, P, (g), J [xt,, (q), B,
E,
1 1+E2
1+
Egg (20)
[xx, 14).8mm)
J(x,, B,,,
19

---

Published as a conference paper at ICLR 2026
Since 0 = (1)) +1- q is constant, we can estimate -9) 9)
F1 -
J [xx, (q),
c -1)8E
- 0 (02 + (n+ - -1)8Pe1)
(since for 0 S 2 2' vI- 2
1
2
Odd
(21)
2 0(11)) (11/2) ) Using Lem. 6, we also have [xx,, (,), 9,
Moreover, we have Ei
1/2 n4 (1/.)))). Thus,
+ E2
3)d
(22)
J(x,, Pi 3,
3, mz)
Substituting the values of n,, E1, and Eg into Eg yields
2d
Es θ (do2) exp (-Cdt-Ba) exp
(23)
(2. - 1)2
Since 1- 8z 0 and exponential functions dominate polynomial growth, combining Eq. (21),
Eq. (22), and Eq. (23) with Eq. (20) yields
(xx, P. 8g) - -1 O(d O. (x,, P: B,)))
Applying similar steps using the lower bound in Lem. 5, find
1 mxx,, (4), m)) J(x, P. (g), m.) I O(d
Thus, the proof is complete.
B.3 PROOF OF THM.
Since J [xx, we; Br, nz) is increasing with respect to n,, the optimal choice is to take at its maximum allowed value:
C
Th e* - (c- (w)) Substituting this into the definition of and applying Lem. we obtain
JX Wi, Br, m2) x (1- 1-(cos - w/ ()))
Vee- - (() B
Expanding B[pe) gives
B = 3, - P.(w:)) + (1 (1- (..)))
Thus,
(1 - (ocos//ww///)3330 (
J(x Be) x Vle - (ct 1)P, (1 (w()) + (1 (wx))
To maximize J. suffices to minimize
o P.(w))) -1-
3.)² P.
20

---

Published as a conference paper at ICLR 2026
Differentiating with respect to 3t and setting the derivative to zero yields
Br = Pr(w)).
Substituting this optimal 3r back, we find
E E = Pt(wr)(1 (((())))
and thus the final expression to maximize is
(1 (cos (112)8)2))
J((we) -((x)(1-P(w))(ee - (ct - P))((w)))
B.4 PROOF THM.
First, we show that cos on 2 0. Suppose for contradiction that cos on < < i.e.
(x1 - x", VS((x)) < O.
Using the definition of the directional derivative, we have
(x1 h(x; - xx')) - 5(x)) (x1 -x", VS((x)) < 0.
lim h
h
Since the directional derivative is strictly negative, there exists such that for all sufficiently small e > 0,
( c(x1 x²)) 5(x1).
Noting that
X1 c(x1 - x*) = x" + (1 - e)(x1 x*),
we can rewrite this inequality as
(xx (1 (x x")) S(x1).
Since ((xi) = 1 by assumption, and assuming remains in neighborhood where S does not decrease, we also have
o (x" + - - (1-e)(xi-x') 1.
Thus, for r = 1 - e, we find a point < < 1 such that 6(x" + r(xi - -x")) = 1, contradicting the
assumption that such exists. Therefore, our assumption that cos 0r < must be false, and conclude that
cos 01 0.
Now that we have established cos on 2 0, it follows that
Elcos ail = [cos a1 cos 01 2 0].
Expanding cos or terms of the vectors involved, we write
x*
01
||x|
x 1|2
g1
Thus,
(
X1 x*
X1 x*
E|cos 01l
E
||x] - x* 2|2
gi
[x]
x 2|
8g
2
Finally, applying the result from Eq. (17) with wi
0, we obtain
X1
X1
x*
r 1z
E
gi
g
20
x
- x 1|2"
|x|
x*
2//T
r
d+1
This completes the proof.
21

---

Published as a conference paper at ICLR 2026
C
EMPIRICAL STUDY OF AS AND AGREST
Here, we design two experiments to validate the effectiveness of our analysis for both AS and AGREST. (Fig. 4)
First, we sample 100 random correctly classified images from the ImageNet dataset and run the experiments using binary search and asymmetric search when e* 10a We observe that the average cumulative search cost across iterations for binary search is approximately 2.5 times higher than that of AS. This highlights the effectiveness of AS compared to vamilla search.
Second, to show that using the overshooting value obtained by AGREST leads to probability of making low-cost queries close the theoretical value in Thm. 3, we again sample 100 random images and run one iteration of AGREST using 500 queries for gradient estimation. We then compute the empirical probability of making low-cost queries, defined as the ratio low-cost to total (500) queries, and compare it to the optimal probability predicted by our theoretical analysis. As shown in Fig. 4, our analysis is close empirical results, especially for larger values of e*.
1e4
Asymmetric search
Cumulative search cost
2.5
Binary search
0.9
2.0
0.8
1.5
Py(w)]
1.0
0.6
Empirical
0.0
0.5
Theoretical
15 20
25
0
20
10
60
80
100
iteration t
Figure Empirical study of AS and AGREST. The left plot compares AS with vanilla search (binary search) in terms of cumulative search cost over iterations in GcoDA when e* = 100, while the right plot shows the optimal theoretical probability of making low-cost queries (assuming local linearity of
the decision boundary) versus the empirical ratio of low-cost total queries for different values of c²
22

---

Published as a conference paper at ICLR 2026
m/
0.02
m 0.04
in
0.06
m
0.08
m 0.10
2
2.45
2.91
2.87
2.54
3.16
5
3.52
3.59
3.75
3.37
3.62
100
3.02
4.36
3.43
4.20
4.95
1000
17.69
19.71
23.75
22.84
30.10
10000
12.91
17.30
23.72
24.728
24.004
Table Peformance of HSIA+AGREST to m across different values of c* (25 random images).
D IMPLEMENTATION
D.1 MODIFICATION TO GRODA
We modify the direction-basee adversarial example search phase in GeoDA. In its original implemen- tation, GeoDA estimates the gradient and then proceeds from the original image, taking fixed-size steps along that direction until finds an adversarial example. However, this process often leads to large number of flagged queries, since many of the intermediate steps cross the decision boundary.
To address this issue, we change the starting point of the search. Instead of beginning the original image, we start from
(S((,,
x" xx xel12
V (x)x1,)))l2
This new starting point lies further the direction the estimated gradient and is designed with the expectation that it is already adversarial-or at least closer to adversarial example than the original image. If x" is not adversarial, the algorithm continues the search in the estimated gradient direction. This modification significantly reduces the number of flagged queries encountered during the search.
D.2 SELECTION OF THE HYPERPARAMETE
We select values for the hyperparameter by evaluating the performance of the corresponding attacks under different settings of m. using 20 randomly selected correctly classified images. This evaluation is performed with e* 10 and a total query cost of 250K, as shown in Fig. 5.
Although the optimal value of can vary with c*, we choose to fix m independently of ct. This decision simplifies the attack process and avoids the additional computational overhead of tuning m for each value of c², while still enabling effective attack performance.
Sensitivity of the hyperparameter. We report in Tab, the results of running HSJA with AGREST on 25 randomly selected images for different values c* and m, indicating that performance is only weakly sensitive to the hyperparameter This suggests that be transferred from known model for a fixed e*.
D.3 AGREST WITH DIMENSION REDUCTION
As mentioned earlier, most practical attacks use a dimension reduction matrix R E Rdxdd to perform the sampling process in subspace of dimension d' & d, where d is the dimension of the original space, order to increase sample efficiency. To apply the same subspace the AGREST estimator, the only modifications needed compared to the original AGREST Alg. 3 are: first, projecting each sample into the subspace; and second, using the effective dimension to compute at An overview of this version of AGREST is provided in Alg. 4.
D.4 COMPUTATION RESOURCES
For our experiments on ResNet-50, we use NVIDIA P100 GPUs. All other experiments, including those involving ViT and CLIP models, are conducted on NVIDIA 1.00 GPUs accommodate the higher computational and memory demands of these models.
23

---

Published as a conference paper at ICLR 2026
HSJA GeoDA CGBA
35
8 distance
700
5
Scheduler rate
Figure 5: Median & distance of adversarial perturbations for varying values of m, with c* total query cost of 150K.
-00 and
Algorithm 4 AGREST Estimation
Inputs: Iteration source image x*, boundary point x,, dimension d, sampling subspace dimension d', sampling subspace matrix R. high-cost query cost c*, sampling radius 6, sampling batch size b, cosine value ae, vanilla gradient estimation query budget n/, scheduler rate m
Outputs: Normalized approximated direction Gt. next cosine value a++1
1: < 0, < 0, v+ +- 0, v x- 6, è < 0, w <- OVERSHOOTING (c*)
6'Thm.3 3
2: wi < -=t/cosaa, ar, Ct 4- n/(("* 1)/2
3: while é c₁ do
4: B RRu, Ru,l| where u, UNIFORM (S--1)} }
Dimension reduction
5: for each E B do
6:
x,-x" Xi W/ x + óō;) then
7:
-- + us un + nl + +1, ê č
8: else
9:
-V u, nH t nH 1, ô+ô+c
10: end if
end for
12: end while
13: Pt + n (nL + nH)
14: St + (1 De) + + p.v 0441 <- SCHEDULER-STER (t.p.,
Alg. 2
15: return gt/ /1 a1+1
E MORE RESULTS
E. ASR COMPARISONS
In this section, present detailed comparison of attack success rates (ASR) achieved by various methods under perturbation norms & and &2 = 10 on ResNer-50. The following results highlight that proposed enhancements consistently deliver substantial gains, reaching up 20% improvement in ASR.
E.2 QUALITATIVE
Fig. 6 presents qualitative results for different HSJA variants at c* 1000. As be seen, incorporating AS and AGREST improves the qualitative quality of the generated adversarial examples.
24

---

Published as a conference paper at ICLR 2026
Table ASR (%)
under &
for different (c", total cost) on ResNet-50.
Attack
Variant
(2,10000)
(5,15000)
(100,150000)
(1000,250000)
SURFREE
VA
55.4
48.7
37.2
16.7
SURFREE
VA+AS
63.9
63.9
HSJA
VA
74.2
69.8
52.8
18.5
HSJA
VA+AS
75.4
67.7
55.7
18.8
HSJA
VA+AGREST
77.7
73.0
73.4
22.6
HSJA
VA+AGREST+AS
76.8
73.6
GEODA
VA
66.3
61.6
56.0
29.9
GEODA
VA+AS
65.4
61.9
57.5
32.3
GEODA
VA+AGREST
61.6
65.7
73.3
43,4
GEODA
VA+AGREST+AS
60.4
66.0
69.3
46.1
CGBA
VA
92.7
88.0
78.0
CGBA
VA+AS
92.1
88.9
78.0
31.8
CGBA
AGREST
91.8
89.4
89.5
45,5
CGBA
VARASTTT
91.5
89.7
90.6
43,0
Table 4: ASR (%) under & = 10 for different (c*, total cost) on ResNet-50.
Attack
Variant
(2,10000)
(5,15000)
(100,150000)
(1000,250000)
SURFREE
VA
80.4
71.0
58.4
31.1
SURFREE
VA+AS
81.8
82.7
59.8
HSJA
VA
89.1
86.2
73.9
25.2
HSJA
VA+AS
90.9
85.9
76.5
29.6
HSJA
VA+AGREST
90.6
88.9
89.3
37.8
HSJA
VA+AGREST+AS
90.6
89.4
43.0
GEODA
VA
83.0
79.8
75.4
47.5
GEODA
VA+AS
81.2
77.7
75.4
53.1
GEODA
VA+AGREST
79.2
82.1
84.8
65.4
GEODA
VA+AGREST+AS
78.6
79.8
84.3
68.4
CGBA
VA
99.1
97.7
92.7
50.1
CGBA
VA+AS
99.1
97.7
93.0
52.1
CGBA
AGRESTT
99.1
98.5
99.0
70.4
CGBA
VA+AGREST+AS
98.2
98.5
99.3
65.0
25

---

Published as a conference paper at ICLR 2026
Figure 6: Qualitative results for HSJA variants at ct. From left to right: vanilla, AS, AGREST, and VA+AGT.
Table 5: Transfer ASR (%) for different source and target models using PGD-40 with & = 10.
Source Model
Target Model
Transfer ASR
VGG19
ResNet50 VIT-B/32
79.6
VGG19
9.4
VIT-B/16
ResNet50
41.0
VIT-B/16
VIT-B/32
28.4
E.3 TRANSFER ATTACKS
We evaluated the transferability of adversarial examples generated from different surrogate models under PGD-40 attack with & norm radius of 10. Tab. summarizes the ASR when transferring from VGG19 and ViT-B/16 to ResNet50 and ViT-B/32.
Transfer attacks usually have lower success are especially useful when the budget is limited. For example, transferring from VGG19 to ResNet50 achieves 79.6% attack success rate without using any queries.
than query-heavy decision-based methods, but they
These results show the complementary role of transfer-based strategies. They may not always be strong across every model pair, but they provide a powerful and cost-free option when query budgets are very limited.
E.4 ASYMMETRIC ATTACKS VS ADVERSARIAL DEFENSES
In this section, we evaluate VA and AGREST under several adversarial defenses. this end, we use the PGID-trained model with lg 3 (whose clean accuracy drops by roughly 20%) and observe that both VA and AGREST improve over the vanilla HSJA attack (Tab. 6).
Method
1000
VA
67.43
127.18
VA+AS
66.02
116.59
VA+AGE
61.88
108.75
AARASTT
60.39
85.85
Table 6: HSJA variant performance on the PGD-trained robust model (lg 3) across different values of c²
In addition to the white-box defense, we also evaluate quantization as a defense against black-box attacks, which results in much smaller reduction in clean accuracy compared to white-box defenses. We observe further improvements when using VA and AGREST (Tab. 7).
E.5 CIFAR-10 ON RESNET-20: RESULTS FOR HSJA
Our experiments CIFAR-10, 10, where the number of classes is significantly smaller than in ImageNet, indicate that the method continues to deliver substantial improvements. Even this setting, our method achieves up to 40% reduction in the perturbation norm (Tab. 8).
26

---

Published as a conference paper at ICLR 2026
Method
e* 1000
VA
9.13
37.60
VA+AS
8.82
36.93
VA+AGREST
6.70
34.79
VA+AST
7.08
31.48
Table HSJA variants under quantization defense.
Variant
(2, 10000)
(5, 15000)
(100, 150000)
(1000, 250000)
VA
0,130
0.148
0.186
0.584
VA + AS
0.129
0.147
0.184
0,506
VA AGREST
0.132
0.142
0.137
0.409
VA AGREST AS
0.133
0.139
0.130
0.309
Table 8: Performance of HSJA variants. Each pair is reported in the form (c*, total_cost).
F ADDITIONAL RESULTS FOR VISION TRANSFORMERS (VIT)
In this section, we present comprehensive empirical evaluations that extend our analysis across varying budget constraints and different query cost parameters c* Specifically, we conduct experiments utilizing Vision Transformer architectures (ViT-B/32 and ViT-B/16) on the ImageNet dataset.
Table 9: Median & distance for various c* values and different types of attacks for ViT-B/32 model on ImageNet dataset.
Medid
VEETUM
Tear
SURERSE
10
113
117
11:1
11.
1.13
12:17
53.
61.
36.7
18.3
130
01.5
483
23.8
664
672
67.5
02.6
53.1
18.3
1:5
(8.
06.1
12.3
-133
23:45
1506
1/1
43
27
23
11.3
74
31
891
71.1
75.7
27.8
13.6
48.3
125
68.
7913
68.3
2.15
11:25
1942
14
163
123
87
631
863
153
12:1
463
08:
012
02:2
300
GIODA
14
31
19
13
43
37
367
800
11.5
137
68.6
12.2
66.1
400
3.11
OGBA
120
11
951
56.5
151
132
15.5
181
13.1
121
1.00
-11
WAAASHREEEST (ACUSAA)
134
700
Table 10: Median & distance for various e* values and different types of attacks for VIT-B/16 model on ImageNet dataset.
ST
Maked
2005
3031
TIKEO
1530
1001
240
2005 TOAB
1200
3001
2001
2000
12031 T3KCG
1006
2001
3400
1200)
VA-AS (4-tatee)
377
2,3
8.3
2.6
86.
56.2
16.4
56.0
54,6
26.9
37.3
17.
111
71
11177
3117
111
17:3
2033
391
311
35.1
75.17
1151A
MA-ACIREST
145
80
4.0
1.3
1.3
28.4
14.5
3.8
2.7
96.1
56.9
59.
16.5
31.6
55.
88.3
18.2
$7.4
58
VANAS-AGMEST (A-BSJA)
39
2-3
223
14.
2.6
561
21.8
562
56.7
VA
(R0DM
VALAS
164
75
122
3J0
1.5
164
12.
33
15
012
016
306
23.1
12.6
580
173
300
18.3
17.
YA YA-ASH AWW.ASHAKKETTT (A-Ga()))
2.0
38
111
165
1.4
130
85
22
55.
36.5
153
912
51.
38.0
6.0
2.5
1-3
112
16
131
185
9.1
611
CUBA
MAAARREST
344
13
1,2
88
140
76
34
18
55.
56.7
15.0
18.5
143
963
554
163
876
115
27

---

Published as a conference paper at ICLR 2026
G ASYMMETRIC SEARCH (AS) ILLUSTRATION
Fig. 7 provides a visual example of the Asymmetric Search (AS) algorithm running with parameters 7 = 0.1 and c* 2. The illustration shows the iterative progression and query evaluations leading to successful convergence near the decision boundary.
Asymmetric Search (AS) Algorithm
Asymmetric
Parameters:
(Threshoid parametes)
Can
(Coet ratio parameter)
Iteration
201
(0T()a))) 607 (0.003))
Iteration 2:
bet
1-0.1
ha h 5 $ 8
600 (1) = (B-0)) 0.13) 6l' (0.06)))))
Iteration
br 0.1 0.003
0.006
d
Returned point: T(b.7) T()) 0.1) ((.001))
AS locates point within 0.1 of the boundary
Convergence to Near-Boundary Point
Tibr) T(0.033)
T(b.r) 7(0.00)
St U.1
Decision Boundary
Figure Asymmetric Search (AS) illustration.
28

---

Published as a conference paper at ICLR 2026
H ASYMMETRIC ATTACKS AGAINST CLIP
We evaluate the robustness of vision-language models (VLMs), such as CLIP (Radford et al., 2021). against stealthy adversarial attacks. Our experiments cover both the zero-shot and fine-tuned versions of CLIP. We apply our asymmetric attacks to these models and observe substantial improvements over stealthy baselines. As shown Fig. 8, after making 300 total queries, asymmetric methods achieve 80-60% lower lg distortion compared to Stealthy HSJA
Zero-Shot CLIP
Fine-Tuned CLIP
Comseriscn Mecheds Zur Model
Attack Methods Taned CLIP Modsl
10a
A-HSIA
10a
A-HIAA
A-GeohA
A-teobA
A-CGBA
A-EBBA
6 101
daann
dalance
104
3 10!
2 10!
0
100 Number hish
200
300
0
100
2001
300
Number
Figure 8: Performance of various asymmetric attacks compared to Stealthy HSJA on CLIP.
I CONCEPTUAL ILLUUSRRATION
In this section, show the conceptual illustration of the vanilla gradient estimation and our proposed gradient estimation AGREST.
Vanilla Gradient Estimation
Asymmetric GRadient EStimation (AGREST)
X;
X2 We
1x:
x'Il
Xt
8
(() +1
a
B
Xt
Φ() = +1
x()) -1
(() = -1
Figure 9: Comparison of vanilla gradient estimation and its asymmetric counterpart. Vanilla sampling results roughly half high-cost and half low-cost queries, whereas AGREST reduces the frequency of high-cost queries by shifting the sampling region and weighting outcomes accordingly.
J NOTE ON THE USE OF LARGE LANGUAGE MODELS
Large language models (LLMs) were utilized exclusively for the purpose of writing and refining the manuscript. LLMs were employed to enhance grammar, increase clarity, and rephrase sentences for improved readability. All research concepts, experiments, and analyses were carried out without the assistance LLMs.
29


Reviews:
[{"review_id": "ZONmVfSNF3", "reviewer": "Reviewer_LRJp", "summary": "This paper proposes a general framework for decision-based attacks in the setting where flagged queries have a different cost from non-flagged queries. The main difference from prior work is that their framework does not force the attacker to completely rewrite the attack, and instead leverages the same primitives as standard decision-only attacks.", "questions": "- Is this attack more effective against models that have been defended, either via adversarial training or via gradient masking-style defenses?\n- What do the distortions look like qualitatively? I couldn't find any examples in the paper.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "- The paper introduces general abstractions for black-box attacks that might be useful to apply in different ways, and provide a clean conceptual model for thinking about these attacks\n- The paper is easy to read, and the experiments are thorough\n- The theoretical analysis is convincing and not completely unrealistic, actually shedding some light on the design of the estimators.", "weaknesses": "- Given that the motivation is to increase the practicality of black-box attacks, it would be interesting to see a real-world study of an adversarial attack pulled off using this method.\n- In terms of the actual benefit over Debenedetti et al., it seems like the main thing is just the conceptual advantage of keeping the same primitives as normal black-box attacks, rather than an actual practical advantage\n- Conceptually, the AS algorithm seems to be just a weighted binary search, so I'm similarly unsure of the actual novelty there. \n\nOverall, the paper is a conceptually interesting contribution, but I'm not sure of the practical significance, especially without a real-world case study.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Y9qkDHyLHL", "reviewer": "Reviewer_mvch", "summary": "This paper addresses the practical limitation of decision-based black-box attacks that assume all queries have equal cost. The paper proposes a new general framework for asymmetric black-box attacks to minimize the total query cost when certain queries are more expensive. The framework introduces two core components: Asymmetric Search, a boundary search method that splits the search interval based on the query cost ratio to minimize the expected cost; and Asymmetric Gradient Estimation, which shifts the sampling distribution to favor low-cost queries and applies differential weighting for variance reduction. Empirically, the proposed asymmetric framework consistently achieves lower total query costs and smaller adversarial perturbations than existing methods, including prior stealthy attacks.", "questions": "Please see Weaknesses.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The paper tackles the highly practical and often overlooked problem of cost asymmetry in black-box attacks, making the research highly relevant to real-world deployment scenarios.\n- The proposed method can be integrated with existing decision-based attacks, offering flexibility. \n- The methods consistently and substantially outperform existing methods by achieving a significantly lower total query cost while maintaining the quality of the adversarial examples.", "weaknesses": "- The claim that the method is superior to existing black-box attacks is unconvincing to me. More specifically, asymmetric cost in Eqn. 3 is optimized in the proposed method and also used in the evaluation, while other methods are optimized with **different objectives** ($c^*=0$ or $\\infty$). Incorporating the new objective seems straightforward. I acknowledge the novelty in the problem setting and theoretical analysis, but the novelty in the method is quite trivial to me.\n- The main weakness of this paper is the limited evaluation. The experiments only contain three models (ResNet50 and two ViT variants), one dataset (ImageNet), and **no defense**. Especially, there are many adaptive defenses for black-box attacks, which should be considered to support the claim that the method is effective and reduces attack cost compared to other stealthy attacks. Furthermore, the paper should dedicate a section to discuss possible adaptive strategies to defend against AS and AGREST.\n- The experiments report the performance with different values of $c^* $, but the paper does not propose any method or heuristic to choose $c^*$, limiting the practicality.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "osW7eWzl1B", "reviewer": "Reviewer_JvF8", "summary": "This paper addresses the practical and important problem of asymmetric query costs in decision-based black-box adversarial attacks, where queries to a model may incur different costs depending on their output. The authors challenge the common assumption of uniform query costs and propose a general framework that can handle arbitrary cost ratios between \"low-cost\" (e.g., benign) and \"high-cost\" (e.g., flagged) queries. The core contributions are two novel techniques: Asymmetric Search (AS), a cost-aware alternative to binary search for finding the decision boundary, and Asymmetric Gradient Estimation (AGREST), a method that shifts the gradient sampling distribution towards the low-cost region and uses importance weighting to maintain estimation accuracy. Through extensive experiments on models like ResNet, ViT, and CLIP, the authors demonstrate that their framework significantly outperforms standard attacks and prior \"stealthy\" attacks, achieving lower perturbation norms for a given total cost budget.", "questions": "1. The paper focuses on enhancing state-of-the-art gradient-based attacks. Could you elaborate on why non-gradient-based methods, such as a modified Boundary Attack or an evolutionary strategy designed to favor low-cost regions, were not considered as baselines? Do you hypothesize that your gradient-based framework would still be superior, and if so, why?\n\n2. Regarding the hyperparameter m: How sensitive is the attack's performance to the choice of this value? Could you provide a brief sensitivity analysis? Furthermore, have you considered an adaptive schedule where m could be adjusted dynamically based on the cost ratio c* or the attack's progress?\n\n3. The framework is presented for non-targeted attacks. What do you foresee as the primary challenges in extending AS and AGREST to the targeted attack setting, where there may be multiple \"high-cost\" classes (the original class and non-target classes) and one \"low-cost\" class (the target class)?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The work tackles a highly significant problem with direct real-world implications. In many practical scenarios, such as content moderation systems or pay-per-query APIs, the cost of a query is not uniform. By generalizing the problem from the niche \"stealthy attack\" setting (where benign queries have zero cost) to one with arbitrary cost ratios, the authors dramatically increase the practical relevance and applicability of decision-based attacks.\n\n2. The proposed techniques, AS and AGREST, are both novel and technically sound. While AS is an intuitive and clever modification of a standard procedure, AGREST is a more profound contribution. The idea of shifting the sampling center away from the boundary into the low-cost region and compensating with importance sampling is an elegant solution to the core challenge of balancing cost reduction with gradient estimation quality. This is supported by solid theoretical analysis (Theorems 2 and 3), which adds a layer of rigor and confidence to the method.\n\n3. The experimental evaluation is comprehensive and convincing. The authors validate their framework across multiple modern and diverse architectures (CNNs, Transformers, VLMs), demonstrating its general applicability. The comparisons are thorough, including not only vanilla baselines but also a direct and fair comparison against the most relevant prior work, Stealthy HSJA. The ablation studies (Table 1) are particularly effective, clearly isolating the individual and combined benefits of AS and AGREST. The reported performance gains—reducing perturbation norms by up to 40% in some cases—are substantial, not marginal.\n\n4. The paper is exceptionally well-written. The motivation is clearly established using a tangible example (NSFW detection). The methodology is presented logically, aided by clear notation and insightful illustrations (Figure 2). The paper is easy to follow from problem formulation to experimental results, making the complex ideas accessible to the reader.", "weaknesses": "1. The paper's contributions and evaluations are focused exclusively on improving gradient-based decision attacks (HSJA, GeoDA, etc.). However, there exists another class of decision-based attacks that do not rely on explicit gradient estimation, such as evolutionary algorithms[1] or random walks[2]. These methods might be naturally resilient to query-intensive steps and could potentially be adapted to the asymmetric cost setting with simple modifications to their search strategy. The lack of discussion or comparison to this family of attacks makes the evaluation feel slightly incomplete. While gradient-based methods are the state-of-the-art in terms of query efficiency in the symmetric setting, acknowledging and contextualizing these alternative approaches would strengthen the paper's positioning.\n\n2. AGREST introduces a new hyperparameter, m (the overshooting scheduler rate). According to Appendix D.2, this parameter is tuned on a small set of images and then fixed for all experiments, irrespective of the cost ratio c*. This simplifies the method's application but raises concerns about its robustness. The performance might be sensitive to this choice, and an optimal m for c*=100 may not be optimal for c*=10,000.\n\n3. Reliance on the Local Linearity Assumption: The theoretical justification for AGREST relies on the assumption that the decision boundary is locally linear. While the authors acknowledge this is a common assumption in the literature, and the strong empirical results suggest the method is robust in practice, a deeper discussion of the limitations would be beneficial. For instance, on a highly curved boundary, the shifted sampling region of AGREST could lead to a biased gradient that is not fully corrected by the re-weighting, potentially impacting performance more than a standard estimator.\n\n[1] Efficient decision-based black-box adversarial attacks on face recognition. CVPR, 2019.\n\n[2] Aha! Adaptive History-Driven Attack for Decision-Based Black-Box Models. ICCV, 2021.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oDDDJrBGpV", "reviewer": "Reviewer_gn6L", "summary": "This paper introduces two techniques for creating adversarial examples against black-box image classifiers when queries have asymmetric cost. These techniques, AS and AGREST, can be plugged into existing attack frameworks (e.g. HSJA, GeoDA...) to substantially increase their performance under asymmetric query costs. AS is a variant of binary search where the interval is split in two parts of length proportional to the cost of the respective queries, and can also be seen as a better version of multi-stage line search. AGREST estimates the gradient around a boundary point by sampling from a hypersphere that is not exactly at the boundary, but shifted toward the low-cost class in order to make fewer high-cost queries, and adjustments are made to estimate the gradient at the original boundary point.", "questions": "1) In Table 1, are you able to report confidence intervals?\n\n2) Table 1: intuitively, your method must increasingly outperform other methods as c* grows. That's why I find the HSJA results on ViT-B/32 at c* = 2 surprising: 18.3, 18.3, 2.7 and 2.7. I would have expected 4 values instead of just 2, and results more similar to HSJA on ResNet-50 at c* = 2 or c* = 5. In most other cases, the ResNet-50 and ViT-B/32 results are roughly the same. Is the experiment underpowered? What is the sample size? As a sanity check, did you verify that the performance is the same when you set c* = 1?\n\n3) When you mention the median L2 distance, what is the sample size?\n\n4) Table 5: what do you mean by \"Higher queries\"? What is the value of c*?\n\n5) Figure 1: what is the cost ratio?\n\n6) 107: there's no Fig. 1 (left). I believe this should be Fig. 3 (right).\n\n7) Do your results hold with a binary classifier, consistent with the motivation of the paper (evading a content moderation classifier) and similar to Debenedetti et al. (e.g. ImageNet-Dogs)?\n\n8) Do you take query discretization into account, as recommended for future work by Debenedetti et al.?\n\n9) Does your method retain appropriate performance when the hyperparameter m is estimated on the same attack but a different classifier than the target one, as would be the case in practice?\n\nSuggestions:\n* You could consider converting Table 1 into a plot.\n\nTypos:\n * 377: duplicate Chen et al.\n  * 244: I believe that what you call a random variable is instead a sample / realization from a random variable.\n    Rating 6\n    Confidence", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* solid theoretical grounding\n* the techniques can be plugged into existing attack frameworks\n* introduction of asymmetric gradient estimation, which addresses a question left as an open problem in prior work\n* good experimental results\n* source code provided", "weaknesses": "* introduction of a new hyperparameter (m) which is set by evaluating the performance of the attacks under different values, and presumably would result in degraded performance when attacking an unknown classifier for which the value of m may not be optimal.\n* no tests on binary classifiers, only on multi-class classifiers", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)