# Don't Search for a Search Method -- Simple Heuristics Suffice for Adversarial Text Attacks

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

## Key facts

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

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

- [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)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Character-level Convolutional Networks for Text Classification](https://mlsanity.com/paper/1509.01626/) (2015)
- [Is BERT Really Robust? A Strong Baseline for Natural Language Attack on Text Classification and Entailment](https://mlsanity.com/paper/1907.11932/) (2019)
- [ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models](https://mlsanity.com/paper/1708.03999/) (2017)
- [Generating Natural Language Adversarial Examples](https://mlsanity.com/paper/1804.07998/) (2018)
- [Counter-fitting Word Vectors to Linguistic Constraints](https://mlsanity.com/paper/1603.00892/) (2016)
- [Interpretable Adversarial Perturbation in Input Embedding Space for Text](https://mlsanity.com/paper/1805.02917/) (2018)
- [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)

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

- [Step by Step Loss Goes Very Far: Multi-Step Quantization for Adversarial Text Attacks](https://mlsanity.com/paper/2302.05120/) (2023)
- [Assessing biomedical knowledge robustness in large language models by query-efficient sampling attacks](https://mlsanity.com/paper/2402.10527/) (2024)
- [The Dog the Cat Chased Stumped the Model: Measuring When Language Models Abandon Structure for Shortcuts](https://mlsanity.com/paper/2510.20543/) (2025)
- [Embedding-Space Data Augmentation to Prevent Membership Inference Attacks in Clinical Time Series Forecasting](https://mlsanity.com/paper/2511.05289/) (2025)
- [Generalization Is Stability, Not Accuracy: Multi-Axis Evaluation of LLMs](https://mlsanity.com/paper/2610.01428/) (2026)

## Abstract (arXiv)

Recently more attention has been given to adversarial attacks on neural networks for natural language processing (NLP). A central research topic has been the investigation of search algorithms and search constraints, accompanied by benchmark algorithms and tasks. We implement an algorithm inspired by zeroth order optimization-based attacks and compare with the benchmark results in the TextAttack framework. Surprisingly, we find that optimization-based methods do not yield any improvement in a constrained setup and slightly benefit from approximate gradient information only in unconstrained setups where search spaces are larger. In contrast, simple heuristics exploiting nearest neighbors without querying the target function yield substantial success rates in constrained setups, and nearly full success rate in unconstrained setups, at an order of magnitude fewer queries. We conclude from these results that current TextAttack benchmark tasks are too easy and constraints are too strict, preventing meaningful research on black-box adversarial text attacks.