acceptodds
Under review as a conference paper at ICLR 2027

Continuous Search Allocation: Jointly Shaping Probes and Updates for Query-Efficient Black-Box Video Attacks

Abstract

Zeroth-order video attacks reduce query cost by structuring where the search is performed: they restrict the search space, select key frames or regions, or reuse a transformed perturbation across frames. We study another degree of freedom: how strongly each coordinate is explored. Continuous search allocation (CSA) derives a graded coordinate-wise allocation from the input before any victim query and applies it to both the zeroth-order probes and the update. A controlled factorial shows that probe weighting alone increases query cost, whereas joint probe–update weighting reduces it, with interactions of and queries on two victims. We instantiate CSA with codec motion vectors obtained without victim queries or additional model inference; the advantage persists when the motion-warped base probe is replaced by i.i.d. noise. Across five victims and two zeroth-order optimizers, CSA lowers CANQ, which charges failures the full query budget, in all ten comparisons against a control matched on probe amplitude and per-iteration update , by on Kinetics-400 and on UCF101. At the default budget, larger savings are associated with more concentrated allocations. Under a tight bound, controlled sweeps reverse this ordering as high-weight coordinates increasingly saturate under projection.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
black-box adversarial attacks, zeroth-order optimization, query efficiency, video recognition, continuous search allocation, motion vectors

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_HdTeOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposes Continuous Search Allocation (CSA) for black-box video attacks. It derives a continuous coordinate-wise allocation from the input before any victim query and applies it jointly to zeroth-order probing and perturbation updates. CSA uses codec motion-vector magnitudes through the Change Magnitude Feature (CMF), and evaluate it with NES and SPSA across multiple video recognition models. It has lower query cost than matched uniform controls and competitive performance against prior video attacks.

Critical strengths
  1. CMF derives its allocation directly from codec motion vectors before the first victim query, without requiring additional model inference or surrogate access.

  2. The experimental section is thorough: the authors use matched controls, paired statistics, two ZO optimizers, multiple victim architectures, a probe/update factorial, i.i.d.probe interventions, and perturbation-budget sweeps to isolate the source and limits of the observed query reduction. Across the main matched comparisons, CSA consistently lowers CANQ, and the additional ablations make the empirical effect substantially more convincing.

Critical weaknesses
  1. The paper is written in an overly defensive and fragmented way: factorial results, matched controls, permutation studies, and other caveats appear before the central motivation and contribution are made sufficiently clear, which makes the paper unnecessarily difficult to follow. After separating the framing from the actual method, the main novelty seems to be the specific combination of "input-derived, pre-query, continuous coordinate-wise allocation with shared probe/update weighting", instantiated using codec motion information; I find this contribution relatively small, and its scope is not clearly delineated.

  2. The paper explains in detail how CMF is used, but not convincingly why CMF should produce the right allocation "W", or why this particular signal is necessary. Motion magnitude captures where pixels move, not necessarily where the victim model is sensitive or where perturbations are most valuable. For example, for a person sitting on a moving train, the face may be task-relevant but nearly static, while the rapidly changing background may receive much larger CMF weights. This concern is reinforced by the paper’s own spatial-permutation result, where rearranging CMF weights within each frame preserves almost the same query saving, suggesting that the gain may come from generic heterogeneity/concentration of "W" rather than from motion-specific relevance; stronger comparisons against other query-free or synthetic allocations with matched concentration are therefore needed.

Questions for authors
  1. How broadly does CSA generalize beyond NES and SPSA? Both are classical finite-difference estimators, so results on a structurally different black-box attack would materially affect the contribution.

  2. How should the query-efficiency claim be interpreted under different distortion criteria? The advantage under L2L_2 norm are not conclusive.

Reviewer_m2zBOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies query-efficient black-box adversarial attacks on video models, where the attacker only observes prediction scores and must mislead a video classifier with as few queries as possible. To address the problem that prior methods only decide where to search while treating all retained coordinates equally, the authors propose CSA, which derives a per-pixel weight map from codec motion vectors before the attack and uses it to scale both the zeroth-order probes and the updates. Experiments show that, under matched probe amplitude and update budget, the method consistently reduces the number of queries needed.

Critical strengths
  1. The idea of weighting both probes and updates with a motion-derived map is easy to follow, and it requires no extra queries or model inference.
  2. The controls are carefully matched and the source of the gain is analyzed with factorial and shuffling experiments.
Critical weaknesses
  1. The experiments only target video action recognition, and it is not shown whether the method transfers to more popular tasks such as video question answering. The victim models are mostly convolutional; commonly used Transformer video models such as VideoMAE are not evaluated.

  2. Diffusion-based purification such as DiffPure, which is among the strongest input-purification defenses, is missing.

  3. The main experiments use an L∞ bound of 25.5/255, larger than the commonly used 8/255 or 16/255. A comparison of all methods under a common bound such as 16/255 is needed.

Questions for authors
  1. Can the method be applied to tasks beyond action recognition, such as video question answering, and to Transformer video models such as VideoMAE?
Reviewer_zyamOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies query-efficient score-based black-box attacks on video classifiers. It proposes Continuous Search Allocation (CSA), which derives a fixed coordinate-wise allocation from the clean input before querying the victim and applies it to both finite-difference probes and perturbation updates. The video instantiation constructs this allocation from codec motion magnitudes. Controlled factorial experiments and interventions support the benefit of joint probe–update weighting under the evaluated settings. Comparisons with a uniform control show lower CANQ when probe amplitude and per-iteration update (L_1) are matched. The manuscript also explicitly documents important limitations, including inconclusive results under (L_2)-family distortion matching and reversed rankings under tight (L_\infty) constraints.

Critical strengths

+. The paper addresses a meaningful problem with a lightweight design. Query efficiency is important for black-box attacks on high-dimensional video inputs. Computing an allocation once from the input, without victim queries or additional model inference, is a reasonable approach. The distinction between structuring probe correlations and allocating coordinate-wise magnitudes is clearly explained.

+. The controlled experiments provide useful evidence about probe–update coupling. The factorial experiments on I3D and X3D report negative interactions of approximately −950 and −806 queries, respectively, and joint weighting outperforms the matched unweighted arm on both victims. The advantage also persists when motion-correlated probes are replaced with independent noise. These interventions help distinguish the allocation effect from the particular probe structure used in the default implementation.

+. The evaluation is careful about failure accounting and uncertainty. CANQ charges failed attacks the full query budget, addressing an important limitation of reporting queries only over successful attacks. The paired analyses, confidence intervals, multiple-comparison correction, and clip-clustered overall test strengthen the empirical evidence.

+. The analysis reports informative boundary conditions. The manuscript investigates allocation concentration, spatial and temporal rearrangements, distortion criteria, and projection effects. It acknowledges negative and inconclusive findings rather than presenting the method as uniformly superior. The local first-order analysis also provides a conditional explanation of the factorial ordering without claiming an attack-level query-complexity guarantee.

Critical weaknesses

-. The methodological contribution appears incremental, and the additional value of the input-derived allocation remains incompletely isolated. The manuscript appropriately acknowledges the relationship to separable evolution strategies, diagonal preconditioning, and adaptive zeroth-order methods in Section 2 and Appendix E. Nevertheless, the basic operation remains a fixed coordinate-wise scaling applied to sampling and updating. The distinction of obtaining this scale from the input is clear, but its empirical importance relative to a generic heterogeneous allocation is less established. In particular, the random-layout controls in Table 17 retain the target clip’s complete CMF value multiset. They therefore test the arrangement of those values, rather than whether a target-specific motion-derived value profile is needed. A generic graded allocation, calibrated under the same budget convention, would provide a more direct assessment of this contribution.

-. The query-efficiency advantage has a restricted distortion and perturbation regime. Appendix C.1.2 supports an advantage at matched MAP in three victim–optimizer settings, but MAP remains an (L_1)-family criterion. Under RMS and PSNR matching, Table 12 does not establish a significant advantage on I3D/NES. Moreover, Table 20 shows that the uniform control significantly outperforms CSA at (8/255) on both tested victims. These limitations are explicitly acknowledged and do not invalidate the reported MAP-based results. However, they narrow the practical benefit of the method, particularly when stricter per-coordinate constraints or alternative distortion measures are relevant. Evidence under (L_2)-family matching is currently limited to one victim–optimizer setting.

-. The comparisons with existing video attacks do not establish superiority under a common threat constraint. Table 3 uses (L_\infty) bounds of 0.1 for CSA, 0.05 for AstFocus, and 0.03 for ME-Sampler. The authors correctly describe these as comparisons at method-specific operating points. However, because the paper itself demonstrates that the ranking against a uniform control changes with the perturbation bound, a representative comparison with prior attacks under a shared bound is particularly relevant. The controlled uniform comparisons establish an allocation effect, but leave its competitive value against existing attacks under the same constraint unresolved.

-. External validity remains limited. The main experiments use (24\times128\times128) inputs and predominantly convolutional victims. The MViTv2-S experiment is useful but statistically inconclusive, and the reduced input setting substantially lowers the clean accuracy of several checkpoints. These factors limit extrapolation to native-resolution video models. The preprocessing timing excludes re-encoding, and the user study uses only one clip per backbone without the matched uniform control. I regard these as secondary limitations of applicability and perceptual evidence, rather than failures of the main controlled experiments.

Questions for authors

Q1. Can the authors compare CMF with a generic fixed or randomly generated graded allocation under the same budget-calibration convention, rather than only rearranging CMF’s values? This would help determine the additional benefit of the target-specific motion-derived value profile.

Q2. Can a representative comparison with ME-Sampler and AstFocus be provided under a shared (L_\infty) bound, using the same score access, query budget, and query accounting? A focused comparison on one or two victims would be informative.

Q3. Does the absence of a statistically established advantage under (L_2)-family distortion matching persist on another victim–optimizer setting? A focused replication would clarify how broadly the observed dependence on distortion geometry applies.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.