Overcoming Black-box Attack Inefficiency with Hybrid and Dynamic Select Algorithms (2025)

Abstract: Adversarial text attack research plays a crucial role in evaluating the robustness of NLP models. However, the increasing complexity of transformer-based architectures has dramatically raised the computational cost of attack testing, especially for researchers with limited resources (e.g., GPUs). Existing popular black-box attack methods often require a large number of queries, which can make them inefficient and impractical for researchers. To address these challenges, we propose two new attack selection strategies called Hybrid and Dynamic Select, which better combine the strengths of previous selection algorithms. Hybrid Select merges generalized BinarySelect techniques with GreedySelect by introducing a size threshold to decide which selection algorithm to use. Dynamic Select provides an alternative approach of combining the generalized Binary and GreedySelect by learning which lengths of texts each selection method should be applied to. This greatly reduces the number of queries needed while maintaining attack effectiveness (a limitation of BinarySelect). Across 4 datasets and 6 target models, our best method(sentence-level Hybrid Select) is able to reduce the number of required queries per attack up 25.82% on average against both encoder models and LLMs, without losing the effectiveness of the attack.

## introduction adversarial attacks have been useful for studying the robustness of nlp models. black-box worldlevel attacks often follow a two-step approach, first selecting a word or token to modify and then modifying that word to cause the target nlp model to fail (with further constraints). selection algorithms can play a pivotal role in the computational overhead of adversarial attacks. greedyselect @xcite , a widely adopted method, iteratively evaluates each word in the text to determine its contribution to the classifier's de-cision. by removing/masking the word with the highest probability drop, greedyselect achieves high precision. however, its word-by-word approach often results in high query counts, limiting its efficiency. as nlp models continue to grow in size, high query counts can translate to attacks taking a large of amount of time per text. this inefficiency further affects researchers or users who do not have access to high-end gpu's to carry out attacks. furthermore, an increased time in attack execution, reduces the ability for researchers to adequately test their models. to address these challenges, binaryselect (ghosh and rusert, 2025) adopted a divide-andconquer strategy inspired by binary search. by partitioning the input into two segments and evaluating the probability change caused by excluding each segment, binaryselect aimed to narrow down the search space when selecting an influential word. while binaryselect helped reduced the number of queries compared to greedyselect in some instances, it caused a drop in attack effectiveness. building on these foundations, this paper proposes hybrid approaches that integrate queryefficient methods like binaryselect with greedyselect's effectiveness. these strategies aim to balance attack efficacy and computational efficiency, addressing critical gaps identified in prior literature and offering a solution to improve adversarial attack performance. our research makes the following contributions: the strategy automatically. we also evaluate their combination (hybrid + dynamic), highlighting where it helps and where it fails. across 4 datasets and 6 models, one variant of sentence-level hybrid reduces query counts by up 25.82% (e.g., 484 → 362 queries ( ## proposed approaches our proposed approaches focus on the domain of black-box attacks (sometimes noted as greybox). that is, following previous research @xcite @xcite , we assume information about the model, such as weights and architecture, are not known. the attack can pass a query to the model, which returns a prediction with a probability. the goal of the attacker is to modify an input text, such that it causes a target model to fail, but retains its original meaning to humans @xcite . in this research, we focus on the domain of text classification. often black-box word-level text attacks consist of 2 stages: selection and modification. in selection, the attacker finds the word or token that the classifier is relying on the most for its decision. in modification, the token found in the selection step is modified in such a way to keep the noted goals. this can be character level modification or word level by replacing the token with less known synonyms. if the attack does not succeed after the modification, the selection method finds the next influential word and the process continues. in this research, our objective is to improve the efficiency of attacks via the selection step by balancing the efficiency of binaryselect and the attack effectiveness of greedyselect. we first define greedyselect and binaryselect and then our own approaches. ## experimental setup to evaluate hybrid select and dynamic select in the adversarial attack setting, we test all noted selection methods as parts of attacks foot_0 against two encoder-based models distilbert @xcite and @xcite and 4 llm models gpt2 @xcite , gptneo @xcite , t5 @xcite , and llama3 (ai@meta, 2024). these models are tested in various amounts across 4 standard attack datasets @xcite : three binary sentiment datasets (imdb, yelp polarity, rotten tomatoes) and one multi-class news dataset ag news. imdb and yelp contain longer texts on average (215 and 157 words respectively) than ag news (43 words) and rotten tomatoes (20 words). we expect our methods to naturally perform better on longer texts due to the larger disadvantage greedyselect has (it must perform len(text) queries always at the beginning of an attack). following previous attack research, we randomly sample 1000 examples from each dataset to attack and keep these 1000 consistent across combinations. metrics: we use the following metrics to evaluate our approaches in the attack: ## results and discussions tables 1, 2, 3, and 4 present the evaluation of our attack strategies on imdb, yelp, ag news, and rotten tomatoes, respectively. for each dataset, we evaluate six target models-distilbert, de-berta, gpt-2, gpt-neo, t5, and llama3-and report four core metrics: attack success rate (asr), average number of queries for successful attacks (avgq), semantic similarity to the original input (sim.), and the percentage of tokens modified (pert.). alongside the baseline methods (binary and greedy), we evaluate fixed n-nary splitting (@xmath0, 3, 6}) and our four novel algorithms: hybrid, sentence-level hybrid, dynamic-n, and dynamic-n + hybrid. all hybrid-based strategies apply a fixed pruning threshold of @xmath1, which our preliminary experiments indicated provides a strong trade-off between efficiency and effectiveness. we explore these parameter choices more thoroughly in sections c.1 and c.4. our overarching objective remains to minimize queries and edits while reducing model confidence, and to demonstrate that our strategies scale reliably across model architectures, dataset lengths, and attack goals. ## ablation studies we perform further experiments to better understand our proposed methods. each experiment expands on specific hyper-parameters or choices in the overall algorithm. due to space, the full results of the studies can be found in appendix c. we provide a short summary of the findings. effect of n in n-nary algorithm: we explore multiple increasing n values of 12 and 24 on the imdb dataset against distilbert (seen in ## conclusion our study introduces a family of selection strategies-hybrid, sentence-level hybrid, dynamic-n, and dynamic-n + hybrid-that strike an effective balance between efficiency and semantic fidelity in black-box text attacks. across all four datasets and six model types, our methods consistently reduce query counts, sometimes by more than 20%, without compromising attack success or text quality. in particular, we find that word-level hybrid with @xmath4, especially for long-form datasets like imdb, while sentencelevel variants perform better on lengthy inputs such as yelp. even on compact datasets like ag news and rotten tomatoes, hybrid strategies retain their advantage, trimming redundant edits while preserving meaning. overall, these results validate that a simple, fixed pruning heuristic-anchored in flexible, recursive search-can deliver scalable and transferable improvements across diverse models and datasets. our methods offer a principled yet practical approach for adversarial attacks where query efficiency and semantic clarity are both essential.