# A Strong Baseline for Query Efficient Attacks in a Black Box Setting

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 41 references that are in the map.
- First posted on arXiv 10 Sep 2021.

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

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [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 large annotated corpus for learning natural language inference](https://mlsanity.com/paper/1508.05326/) (2015)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Practical Black-Box Attacks against Machine Learning](https://mlsanity.com/paper/1602.02697/) (2016)
- [Universal Adversarial Triggers for Attacking and Analyzing NLP](https://mlsanity.com/paper/1908.07125/) (2019)
- [BERT-ATTACK: Adversarial Attack Against BERT Using BERT](https://mlsanity.com/paper/2004.09984/) (2020)
- [Universal Sentence Encoder](https://mlsanity.com/paper/1803.11175/) (2018)
- [Generating Natural Language Adversarial Examples](https://mlsanity.com/paper/1804.07998/) (2018)
- [TextBugger: Generating Adversarial Text Against Real-world Applications](https://mlsanity.com/paper/1812.05271/) (2018)
- [BAE: BERT-based Adversarial Examples for Text Classification](https://mlsanity.com/paper/2004.01970/) (2020)
- [A Decomposable Attention Model for Natural Language Inference](https://mlsanity.com/paper/1606.01933/) (2016)
- [Probing Neural Network Comprehension of Natural Language Arguments](https://mlsanity.com/paper/1907.07355/) (2019)
- [Counter-fitting Word Vectors to Linguistic Constraints](https://mlsanity.com/paper/1603.00892/) (2016)
- [Contextualized Perturbation for Textual Adversarial Attack](https://mlsanity.com/paper/2009.07502/) (2020)
- [Deep Text Classification Can be Fooled](https://mlsanity.com/paper/1704.08006/) (2017)
- [Generating Natural Language Attacks in a Hard Label Black Box Setting](https://mlsanity.com/paper/2012.14956/) (2020)
- [Word-level Textual Adversarial Attacking as Combinatorial Optimization](https://mlsanity.com/paper/1910.12196/) (2019)
- [Searching for a Search Method: Benchmarking Search Algorithms for Generating NLP Adversarial Examples](https://mlsanity.com/paper/2009.06368/) (2020)
- [A Context Aware Approach for Generating Natural Language Attacks](https://mlsanity.com/paper/2012.13339/) (2020)

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

- [Query-Efficient and Scalable Black-Box Adversarial Attacks on Discrete Sequential Data via Bayesian Optimization](https://mlsanity.com/paper/2206.08575/) (2022)
- [HQA-Attack: Toward High Quality Black-Box Hard-Label Adversarial Attack on Text](https://mlsanity.com/paper/2402.01806/) (2024)
- [Practice Makes a Solver Perfect: Data Augmentation for Math Word Problem Solvers](https://mlsanity.com/paper/2205.00177/) (2022)
- [Rethinking Textual Adversarial Defense for Pre-trained Language Models](https://mlsanity.com/paper/2208.10251/) (2022)
- [Masked Language Model Based Textual Adversarial Example Detection](https://mlsanity.com/paper/2304.08767/) (2023)
- [Are Synonym Substitution Attacks Really Synonym Substitution Attacks?](https://mlsanity.com/paper/2210.02844/) (2022)
- [A Black-Box Attack on Code Models via Representation Nearest Neighbor Search](https://mlsanity.com/paper/2305.05896/) (2023)
- [CAMOUFLAGE: Exploiting Misinformation Detection Systems Through LLM-driven Adversarial Claim Transformation](https://mlsanity.com/paper/2505.01900/) (2025)
- [Adversarial Defence without Adversarial Defence: Enhancing Language Model Robustness via Instance-level Principal Component Removal](https://mlsanity.com/paper/2507.21750/) (2025)
- [Exploiting Class Probabilities for Black-box Sentence-level Attacks](https://mlsanity.com/paper/2402.02695/) (2024)
- [Assessing biomedical knowledge robustness in large language models by query-efficient sampling attacks](https://mlsanity.com/paper/2402.10527/) (2024)
- [Multi-task Adversarial Attacks against Black-box Model with Few-shot Queries](https://mlsanity.com/paper/2508.10039/) (2025)
- [GenFighter: A Generative and Evolutive Textual Attack Removal](https://mlsanity.com/paper/2404.11538/) (2024)
- [Robustness of Misinformation Classification Systems to Adversarial Examples Through BeamAttack](https://mlsanity.com/paper/2506.23661/) (2025)
- [Agentic Adversarial Rewriting Exposes Architectural Vulnerabilities in Black-Box NLP Pipelines](https://mlsanity.com/paper/2604.23483/) (2026)
- [LBA: Textual Hard-Label Adversarial Attack under Low Query Budgets](https://mlsanity.com/paper/2607.14101/) (2026)

## Abstract (arXiv)

Existing black box search methods have achieved high success rate in generating adversarial attacks against NLP models. However, such search methods are inefficient as they do not consider the amount of queries required to generate adversarial attacks. Also, prior attacks do not maintain a consistent search space while comparing different search methods. In this paper, we propose a query efficient attack strategy to generate plausible adversarial examples on text classification and entailment tasks. Our attack jointly leverages attention mechanism and locality sensitive hashing (LSH) to reduce the query count. We demonstrate the efficacy of our approach by comparing our attack with four baselines across three different search spaces. Further, we benchmark our results across the same search space used in prior attacks. In comparison to attacks proposed, on an average, we are able to reduce the query count by 75% across all datasets and target models. We also demonstrate that our attack achieves a higher success rate when compared to prior attacks in a limited query setting.