Reproduce “Searching for a Search Method: Benchmarking Search Algorithms for Generating NLP Adversarial Examples” on OpenResearch

About this paper

Jin Yong Yoo, John X. Morris, Eli Lifland, Yanjun Qi

The authors benchmark black-box word-substitution attacks by holding each search space fixed while comparing algorithms across query budgets. They find beam search and particle swarm optimization perform best without query limits, while WIR uses fewer queries under constrained budgets. On BERT-base Yelp data, PSO reaches 96.6% success versus beam search’s 95.6%, but requires 62,346 versus 19,810 queries, in these tested settings.

Key insights

• Search-space control is essential: differences between attack methods can otherwise reflect synonym resources or constraints rather than the optimizer itself.
• Beam search width eight usually gives the strongest overall trade-off and produces more localized, semantically similar perturbations, whereas PSO's extra search yields limited gains at high query cost.
• Word-importance ranking scales approximately linearly with document length and is effective under tight budgets, although its advantage depends on the dataset, model, and available queries.

Summary by alphaXiv.