# Query-Efficient and Scalable Black-Box Adversarial Attacks on Discrete Sequential Data via Bayesian Optimization

arXiv: https://arxiv.org/abs/2206.08575 · HTML: https://mlsanity.com/paper/2206.08575/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 54 references that are in the map.
- First posted on arXiv 17 Jun 2022.

## Builds on (most cited first, 26 of 26)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding](https://mlsanity.com/paper/1804.07461/) (2018)
- [SQuAD: 100,000+ Questions for Machine Comprehension of Text](https://mlsanity.com/paper/1606.05250/) (2016)
- [XLNet: Generalized Autoregressive Pretraining for Language Understanding](https://mlsanity.com/paper/1906.08237/) (2019)
- [A Broad-Coverage Challenge Corpus for Sentence Understanding through Inference](https://mlsanity.com/paper/1704.05426/) (2017)
- [Character-level Convolutional Networks for Text Classification](https://mlsanity.com/paper/1509.01626/) (2015)
- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [Square Attack: a query-efficient black-box adversarial attack via random search](https://mlsanity.com/paper/1912.00049/) (2019)
- [Is BERT Really Robust? A Strong Baseline for Natural Language Attack on Text Classification and Entailment](https://mlsanity.com/paper/1907.11932/) (2019)
- [Black-box Adversarial Attacks with Limited Queries and Information](https://mlsanity.com/paper/1804.08598/) (2018)
- [BERT-ATTACK: Adversarial Attack Against BERT Using BERT](https://mlsanity.com/paper/2004.09984/) (2020)
- [Generating Natural Language Adversarial Examples](https://mlsanity.com/paper/1804.07998/) (2018)
- [BAE: BERT-based Adversarial Examples for Text Classification](https://mlsanity.com/paper/2004.01970/) (2020)
- [Regularizing and Optimizing LSTM Language Models](https://mlsanity.com/paper/1708.02182/) (2017)
- [High-Dimensional Bayesian Optimization with Sparse Axis-Aligned Subspaces](https://mlsanity.com/paper/2103.00349/) (2021)
- [Counter-fitting Word Vectors to Linguistic Constraints](https://mlsanity.com/paper/1603.00892/) (2016)
- [High Dimensional Bayesian Optimisation and Bandits via Additive Models](https://mlsanity.com/paper/1503.01673/) (2015)
- [Batched Large-scale Bayesian Optimization in High-dimensional Spaces](https://mlsanity.com/paper/1706.01445/) (2017)
- [Crafting Adversarial Input Sequences for Recurrent Neural Networks](https://mlsanity.com/paper/1604.08275/) (2016)
- [Combinatorial Bayesian Optimization using the Graph Cartesian Product](https://mlsanity.com/paper/1902.00448/) (2019)
- [Bayesian Optimization of Combinatorial Structures](https://mlsanity.com/paper/1806.08838/) (2018)
- [Batched High-dimensional Bayesian Optimization via Structural Kernel Learning](https://mlsanity.com/paper/1703.01973/) (2017)
- [Searching for a Search Method: Benchmarking Search Algorithms for Generating NLP Adversarial Examples](https://mlsanity.com/paper/2009.06368/) (2020)
- [A Strong Baseline for Query Efficient Attacks in a Black Box Setting](https://mlsanity.com/paper/2109.04775/) (2021)
- [Black-box Adversarial Attacks with Bayesian Optimization](https://mlsanity.com/paper/1909.13857/) (2019)

## Built on by (most cited first, 22 of 22)

- [Text-CRS: A Generalized Certified Robustness Framework against Textual Adversarial Attacks](https://mlsanity.com/paper/2307.16630/) (2023)
- [Query-Efficient Black-Box Red Teaming via Bayesian Optimization](https://mlsanity.com/paper/2305.17444/) (2023)
- [Evaluating the Robustness of Text-to-image Diffusion Models against Real-world Attacks](https://mlsanity.com/paper/2306.13103/) (2023)
- [TextGrad: Advancing Robustness Evaluation in NLP by Gradient-Driven Optimization](https://mlsanity.com/paper/2212.09254/) (2022)
- [HQA-Attack: Toward High Quality Black-Box Hard-Label Adversarial Attack on Text](https://mlsanity.com/paper/2402.01806/) (2024)
- [Advancing the Robustness of Large Language Models through Self-Denoised Smoothing](https://mlsanity.com/paper/2404.12274/) (2024)
- [Efficient Black-box Adversarial Attacks via Bayesian Optimization Guided by a Function Prior](https://mlsanity.com/paper/2405.19098/) (2024)
- [LEAP: Efficient and Automated Test Method for NLP Software](https://mlsanity.com/paper/2308.11284/) (2023)
- [In and Out-of-Domain Text Adversarial Robustness via Label Smoothing](https://mlsanity.com/paper/2212.10258/) (2022)
- [SSCAE -- Semantic, Syntactic, and Context-aware natural language Adversarial Examples generator](https://mlsanity.com/paper/2403.11833/) (2024)
- [Revisiting Character-level Adversarial Attacks for Language Models](https://mlsanity.com/paper/2405.04346/) (2024)
- [COVER: A Heuristic Greedy Adversarial Attack on Prompt-based Learning in Language Models](https://mlsanity.com/paper/2306.05659/) (2023)
- [Query-Based and Unnoticeable Graph Injection Attack from Neighborhood Perspective](https://mlsanity.com/paper/2502.01936/) (2025)
- [EaTVul: ChatGPT-based Evasion Attack Against Software Vulnerability Detection](https://mlsanity.com/paper/2407.19216/) (2024)
- [Tougher Text, Smarter Models: Raising the Bar for Adversarial Defence Benchmarks](https://mlsanity.com/paper/2501.02654/) (2025)
- [Robustness in Both Domains: CLIP Needs a Robust Text Encoder](https://mlsanity.com/paper/2506.03355/) (2025)
- [Text Adversarial Attacks with Dynamic Outputs](https://mlsanity.com/paper/2509.22393/) (2025)
- [Exploiting Class Probabilities for Black-box Sentence-level Attacks](https://mlsanity.com/paper/2402.02695/) (2024)
- [Multi-task Adversarial Attacks against Black-box Model with Few-shot Queries](https://mlsanity.com/paper/2508.10039/) (2025)
- [Interactionless Inverse Reinforcement Learning: A Data-Centric Framework for Durable Alignment](https://mlsanity.com/paper/2602.14844/) (2026)
- [Unveiling Vulnerability of Self-Attention](https://mlsanity.com/paper/2402.16470/) (2024)
- [PivotAttack: Rethinking the Search Trajectory in Hard-Label Text Attacks via Pivot Words](https://mlsanity.com/paper/2603.10842/) (2026)

## Abstract (arXiv)

We focus on the problem of adversarial attacks against models on discrete sequential data in the black-box setting where the attacker aims to craft adversarial examples with limited query access to the victim model. Existing black-box attacks, mostly based on greedy algorithms, find adversarial examples using pre-computed key positions to perturb, which severely limits the search space and might result in suboptimal solutions. To this end, we propose a query-efficient black-box attack using Bayesian optimization, which dynamically computes important positions using an automatic relevance determination (ARD) categorical kernel. We introduce block decomposition and history subsampling techniques to improve the scalability of Bayesian optimization when an input sequence becomes long. Moreover, we develop a post-optimization algorithm that finds adversarial examples with smaller perturbation size. Experiments on natural language and protein classification tasks demonstrate that our method consistently achieves higher attack success rate with significant reduction in query count and modification rate compared to the previous state-of-the-art methods.