REVIEW 4 major objections 6 minor 17 references
BinarySelect to Improve Accessibility of Black-Box Attack Research
T0 review · 4 major / 6 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read BinarySelect finds the first attack token in log2(n)*2 queries instead of n, cutting total attack queries by up to 60% with a smaller effectiveness drop.
desk verdict A practical, honestly written query-efficiency trick with a correct log query bound, but the empirical 'viable tradeoff' is softer than claimed and the selection heuristic is unvalidated. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the divide-and-conquer probability-drop comparison: given text $X$ split into $X_1$ and $X_2$, BinarySelect computes $\Delta_i = f(X) - f(X_i)$ for $i \in \{1,2\}$ and follows the half with the larger $\Delta$. A companion binary tree caches the segment scores so that later selections only need to expand branches not yet explored, which is what turns the $\log_2(n)$ per-token cost into a sublinear total. This mechanism converts the standard $n$-query exhaustive scan into a logarithmic search under the assumption that probability drop is a sufficiently reliable proxy for token influence.
What would settle it
Run BinarySelect and exhaustive GreedySelect on a fixed sample and record how often BinarySelect's first-chosen token is the token with the largest leave-one-out probability drop. The paper's own Table 2 shows the GreedySelect top token is absent from BinarySelect's top 10 in 583 of 1000 IMDB examples, so a direct argmax-agreement measurement would determine whether the convergence premise holds; if agreement is far below 50%, the query savings come at the cost of systematically choosing the wrong token.
Extended reading notes
Core claim
BinarySelect searches for the most influential token by repeatedly partitioning the text into two halves, querying the classifier on each half (with the other half removed), and recursing into the half whose removal causes the larger drop in target-class probability. Each split costs two queries and halves the candidate set, so the first token is found in $\log_2(n) \cdot 2$ queries, versus $n$ for GreedySelect, and a binary tree of previously computed segment scores lets subsequent token selections reuse cached queries. In attack experiments with a simple WordNet synonym-replacement step, BinarySelect reduced average query counts by up to 60% (e.g., from 318 to 172 on IMDB with the Albert classifier) while the attack-accuracy drop was comparatively smaller, and in the successful-attack subset the query savings were even larger. The authors thus claim BinarySelect offers a practical efficiency-effectiveness tradeoff, not a free lunch, and is best suited to attacks that modify relatively few words.
Load-bearing premise
The load-bearing premise is that the text half whose removal causes the larger classifier probability drop always contains the most influential token, so recursing into that half converges to the right word—an unproven heuristic that the paper's own agreement results (583 of 1000 IMDB examples miss the top GreedySelect word) show often fails.
Editorial extensions
If this is right
- On the Yelp dataset with BERT, queries drop 32% (72 fewer) while attack effectiveness drops only 5 points, showing the claimed tradeoff in a concrete setting.
- On IMDB successful attacks, query savings reach around 60% (e.g., 61% for Albert) compared to GreedySelect, so the efficiency gain is largest precisely when the attack succeeds.
- On short texts like AG News, BinarySelect saves few queries and matches GreedySelect's effectiveness, meaning the benefit grows with text length.
- Limiting the attack to a small number of word replacements ($k$) improves the query-versus-effectiveness tradeoff as measured by the paper's EDR metric, giving researchers a tunable knob.
- The method transfers to character-level attacks, where it reduces queries strongly for low $k$ against a CANINE character model, suggesting broader applicability beyond word-level selection.
Reading between the lines
- The cache of segment scores suggests an unexplored benefit: repeated attacks on the same text (e.g., for defense evaluation) should be even cheaper than the reported single-run figures, since no segment score would be recomputed.
- The paper's agreement results imply BinarySelect is better understood as finding a high-impact token rather than the highest-impact one; for attacks that only need any salient word, the effectiveness gap should shrink, which is testable with a replacement step that emphasizes meaning preservation.
- A natural extension is an adaptive variant that stops splitting when the probability drop falls below a threshold, treating whole segments as non-influential; the paper's oracle experiments suggest an automatic early-stopping rule could recover most of GreedySelect's effectiveness at BinarySelect's query cost.
- Because the query count follows $\log_2(n)$, for very long documents the savings become larger, but the convergence heuristic also becomes riskier, so the method's practical ceiling is probably on medium-length texts like reviews rather than on full-length articles.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes BinarySelect, a token-selection method for black-box text attacks that uses a binary-search-like splitting of the input text and classifier probability feedback to find an influential token in roughly 2*log2(n) queries, compared to n queries for the standard GreedySelect. The authors derive this query bound, validate it empirically on AG News and IMDB with an ALBERT classifier, and evaluate BinarySelect inside a WordNet-based attack against five classifiers across three datasets. They report substantial query savings with a smaller drop in attack effectiveness, an exploration of the attack budget k, a character-level verification, and an oracle analysis that combines BinarySelect with GreedySelect. The paper also includes a limitations section acknowledging that the extent to which BinarySelect retrieves the true top influential word is not known.
Significance. If the central heuristic is reliable, BinarySelect is a practically relevant primitive that lowers the query cost of black-box text attacks and improves accessibility for resource-constrained researchers. A strength of the paper is that the query-complexity claim is derived from the algorithm's control flow rather than fitted to data, and the empirical query counts in Table 1 and Figure 3 are consistent with that bound. The main risk is that BinarySelect often selects a different token than GreedySelect: the agreement experiments in Table 2 show that on IMDB the GreedySelect top-1 word is absent from the BinarySelect top-10 in 583 of 1000 cases, and Section 12 explicitly states that the retrieval quality is unknown. This gap is load-bearing because the tradeoff between query savings and attack effectiveness is only meaningful if the selected tokens are genuinely influential. The paper is honest about its limitations and provides reproducible code, but the selection-quality question needs a direct answer.
major comments (4)
- [§4.2, Table 2] The agreement experiments show that BinarySelect frequently does not find the same top token as GreedySelect. For IMDB, the GreedySelect top-1 word is not present in the BinarySelect top-10 in 583 of 1000 examples, and the average rank of that word in the BinarySelect list is 2.9; for AG News the corresponding numbers are 255 of 1000 examples and an average rank of 2.3. This is not merely a minor discrepancy: Section 3 and the Abstract claim that BinarySelect needs only log2(n)*2 queries 'to find the first token,' which is only comparable to GreedySelect's n-query scan if the token found is the same or nearly as influential. The paper's own limitation statement in Section 12 admits that 'it is not known to what extent the top or (top X) word is retrieved.' I therefore ask the authors to provide a direct validation of selection quality, for example by comparing BinarySelect's top-k selections against an exhaustive leave-one-out ranking on a subsample, or against gradient- or attention-based attributions, and to report precision/recall at various k. Without such evidence, the attack-effectiveness gap in Table 3 (e.g., IMDB Albert: 66.9 attack accuracy for BinarySelect versus 51.8 for GreedySelect) is plausibly a direct consequence of selecting different, less influential tokens, and the 'viable tradeoff' claim is not fully supported.
- [§3, Appendix A, Algorithm 1] The theoretical query count 'log2(n)*2' omits the initial baseline query Score Orig <- Classifier(text) in Algorithm 1 (line 1). With that query included, the total to find the first token is 1 + 2*log2(n). GreedySelect also needs the baseline f(X) in Equation (1), so the comparison can be made fair by stating the convention explicitly. Additionally, the 'average case' estimate in Section 3 borrows perturbation percentages from BERT-Attack (4.4 for IMDB, 15.4 for AG News) as external inputs; this should be labeled as an estimate based on prior work, not a derived property of BinarySelect. Please clarify these points in the revised manuscript.
- [§4.1, Figure 3 and §5.1] The empirical validation in Figure 3 shows that BinarySelect's query count follows a log trend, but this is expected from the algorithm's control flow and does not by itself demonstrate that the selected words are the most influential. The attack experiments compare BinarySelect only against GreedySelect, not against a random token-selection baseline. A random baseline (e.g., replacing k randomly chosen positions with the same WordNet replacement step) would isolate the contribution of selection quality and would strengthen the claim that the observed tradeoff is due to BinarySelect's heuristic rather than to the attack framework. Please add such a baseline to the attack evaluation.
- [Appendix C, Algorithm 2] The binary-tree extension for retrieving subsequent tokens is underspecified. When a leaf node is reached, Algorithm 2 says 'for each word w in cur_node.data do Scorew <- Classifier(text/w)', but according to Section 2.4 a leaf node corresponds to a single word. This contradiction makes it unclear how the top-10 lists in Table 1 are generated and how the query counts for subsequent tokens are computed. Please provide a consistent, precise algorithm and clarify whether the leaf handling differs from the first-token search described in Section 2.4.
minor comments (6)
- [§1] The Introduction describes BinarySelect as 'removing the first half of the text,' but the technical description in §2.4 is about excluding (masking/deleting) a segment from the original text while scoring the remaining segment. Please rephrase for consistency.
- [§3] The worst-case formula 'n + Plog2(n) i=1 n/(2i)' uses 'P' where a summation symbol is intended; please typeset it properly.
- [§7 and Appendix F] The text in §7 mentions 'XLNet' when describing query reductions, but Table 3 lists a 'Roberta' column and the appendix tables do not consistently include XLNet; please align the column names and narrative.
- [§10.1] The confidence-based oracle uses average confidence values computed from the same data that is then sorted into bins; this is not a fully independent oracle. Please state that limitation explicitly and, if possible, evaluate the confidence model on a held-out split.
- [§12] The sentence 'Part of this issues lies with the goal of the selection methods' contains a grammatical error; please revise.
- [Global] Please add a reproducibility statement with exact model versions, random seeds, and the number of runs per attack combination, since the appendix reports only that runs were performed on Colab/Kaggle GPUs.
Circularity Check
No circularity: the query count is a property of the algorithm's control flow, average-case estimates use external BERT-Attack inputs, and the BS/GS agreement gap is a validity concern, not a derivation-from-input.
full rationale
BinarySelect's headline query count, log2(n)*2 for the first selected word, is a direct consequence of the algorithm's control flow in Algorithm 1: each iteration issues exactly two classifier calls (ScoreLeft and ScoreRight), and the loop runs until start == end, with the search interval halved each iteration. This is not fitted to data and does not presuppose the identity of the returned word; the query count is a property of the search procedure itself. The average-case estimates in Section 3 combine this procedural count with BERT-Attack's externally reported perturbation percentages (4.4% for IMDB, 15.4% for AG News), which are inputs from prior work rather than values fitted inside this paper. The agreement experiments (Section 4.2, Table 2) show that BinarySelect often returns different words than GreedySelect's top-1; that is a threat to the claim that BS performs the same selection task, and a validity/effectiveness concern, but it is not circularity because the paper does not define BS's effectiveness as agreement with GS, and the downstream attack results are measured end-to-end. The only fitted elements are the exploratory confidence thresholds in Section 10.1, which are explicitly preliminary, flagged as still partly oracle, and not used to support the central tradeoff claim. Rusert et al. (2022), the sole self-citation, appears only as one example in a list of GreedySelect-based attacks; no load-bearing argument rests on it. No equation is defined in terms of the quantity it is said to predict, and no fitted parameter is renamed as a prediction. Verdict: no significant circularity.
Assumptions & free parameters
free parameters (2)
- k (attack word budget) =
5, 15, 30, 50, ALL
- Average confidence bin thresholds for oracle emulation =
93.77, 96.27, 97.12, 97.46, 97.67
assumptions (3)
- ad hoc to paper The segment whose removal causes the larger probability drop contains the most influential token (or a token of interest).
- domain assumption Classifier probability is an adequate salience signal for token importance.
- domain assumption Query counts are the bottleneck; wall-clock time scales with queries.
Cite this review
Pith. "Pith review of BinarySelect to Improve Accessibility of Black-Box Attack Research." pith.science (2026). https://pith.science/paper/LHAZIIDR
@misc{pith2026241210617,
author = {Pith},
title = {Pith review of: BinarySelect to Improve Accessibility of Black-Box Attack Research},
year = {2026},
howpublished = {\url{https://pith.science/paper/LHAZIIDR}},
note = {Machine review of arXiv:2412.10617}
}
abstract
Adversarial text attack research is useful for testing the robustness of NLP models, however, the rise of transformers has greatly increased the time required to test attacks. Especially when researchers do not have access to adequate resources (e.g. GPUs). This can hinder attack research, as modifying one example for an attack can require hundreds of queries to a model, especially for black-box attacks. Often these attacks remove one token at a time to find the ideal one to change, requiring $n$ queries (the length of the text) right away. We propose a more efficient selection method called BinarySelect which combines binary search and attack selection methods to greatly reduce the number of queries needed to find a token. We find that BinarySelect only needs $\text{log}_2(n) * 2$ queries to find the first token compared to $n$ queries. We also test BinarySelect in an attack setting against 5 classifiers across 3 datasets and find a viable tradeoff between number of queries saved and attack effectiveness. For example, on the Yelp dataset, the number of queries is reduced by 32% (72 less) with a drop in attack effectiveness of only 5 points. We believe that BinarySelect can help future researchers study adversarial attacks and black-box problems more efficiently and opens the door for researchers with access to less resources.
Figures
Figures from the paper (2 more)
Reference graph
Works this paper leans on
-
[1]
Character, 2. Word, 3. Phrase, 4. Sentence, 5. Multi-level. Character-level attacks change individual charac- ters in words to cause tokens to become unknown to the target NLP models. These attacks include addition/removal of whitespace (Gröndahl et al., 2018), replacement of visually similar characters (Eger et al., 2019), and shuffling of characters (Li...
work page 2018
-
[2]
Labels are positive or negative
IMDB - binary sentiment classification, con- taining text reviews for movies. Labels are positive or negative. The average text lengths are 215 to- kens
-
[3]
arXiv preprint arXiv:1909.11942
Albert: A lite bert for self-supervised learn- ing of language representations. arXiv preprint arXiv:1909.11942. Thai Le, Jooyoung Lee, Kevin Yen, Yifan Hu, and Dong- won Lee. 2022. Perturbations in the wild: Leveraging human-written text perturbations for realistic adver- sarial attack and defense. In Findings of the Asso- ciation for Computational Lingu...
arXiv 1909
-
[4]
RoBERTa outperforms BERT in classification tasks, due to different choices in pretraining
RoBERTa (Liu et al., 2019) - a fine-tuned ver- sion of RoBERTa. RoBERTa outperforms BERT in classification tasks, due to different choices in pretraining
work page 2019
-
[5]
Generating natural language adversarial exam- ples through probability weighted word saliency. In Proceedings of the 57th Annual Meeting of the Asso- ciation for Computational Linguistics, pages 1085– 1097, Florence, Italy. Association for Computational Linguistics. Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. 2018. Semantically equivalent adve...
work page 2018
-
[6]
On the robustness of offensive language classi- fiers. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Vol- ume 1: Long Papers) , pages 7424–7438, Dublin, Ireland. Association for Computational Linguistics. Sahar Sadrizadeh, Ljiljana Dolamic, and Pascal Frossard. 2022. Block-sparse adversarial attack to fool tra...
work page 2022
-
[9]
The labels are positive or negative
Yelp Polarity - binary sentiment classification, containing texts from Yelp reviews. The labels are positive or negative. The average text lengths are 157 tokens
-
[11]
The average text lengths are 43 tokens
AG News - A multi-class (Sports, World, Business, Sci/Tech) dataset containing news texts. The average text lengths are 43 tokens. D.2 Classifiers: We test against 5 classifiers for each dataset, by leveraging pretrained TextAttack (Morris et al.,
Show all 17 references
-
[12]
and other Huggingface models6:
-
[13]
Albert (Lan et al., 2019) - a fine-tuned version of Albert, which shares weights across layers in order to obtain a smaller-memory footprint than BERT
2019
-
[14]
Distilbert was pretrained using BERT as a teacher for self-supervision and thus is a lighter, faster model than BERT
Distilbert (Sanh et al., 2020) - a fine-tuned Distilbert model. Distilbert was pretrained using BERT as a teacher for self-supervision and thus is a lighter, faster model than BERT
2020
-
[15]
BERT pre-trains on next sentence prediction and masked language modelling tasks to gain an inherent understanding of text
BERT (Devlin et al., 2019) - a fine-tuned version of BERT-base-uncased. BERT pre-trains on next sentence prediction and masked language modelling tasks to gain an inherent understanding of text
2019
-
[17]
Original Acc
LSTM - LSTM trained on the respective datasets. The trained models are available from TextAttack7. E List of Huggingface Models Table 7 contains the locations of the different mod- els tested for our attack. F k Results We generate similar tables to Table 3 for k = {5, 15, 30,...
-
[2018]
DongHyun Choi, Myeong Cheol Shin, EungGyun Kim, and Dong Ryeol Shin
Generating natural language adversarial exam- ples. DongHyun Choi, Myeong Cheol Shin, EungGyun Kim, and Dong Ryeol Shin. 2021. OutFlip: Generating examples for unknown intent detection with natu- ral language attack. In Findings of the Association for Computational Linguistics...
2021 arXiv
-
[2019]
Text processing like humans do: Visually attacking and shielding NLP systems. In Proceed- ings of the 2019 Conference of the North American Chapter of the Association for Computational Lin- guistics: Human Language Technologies, Volume 1 (Long and Short Papers) , pages 1634–16...
2019
-
[2020]
Phrase-level attacks replace multiple consecutive words at once (Deng et al., 2022; Lei et al., 2022)
to find relevant synonyms for replacement. Phrase-level attacks replace multiple consecutive words at once (Deng et al., 2022; Lei et al., 2022). Sentence-level attacks leverage generation methods to rewrite text in a format that the target NLP model is unfamiliar with (Ribeir...
2022
-
[2022]
Neurocom- puting, 492:278–307
Adversarial attack and defense technologies in natural language processing: A survey. Neurocom- puting, 492:278–307. Shuhuai Ren, Yihe Deng, Kun He, and Wanxiang Che
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.