{"id":"e4c7228f-9f4d-4481-a7b4-7d096ece73c9","arxiv_id":"2412.10617","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"BinarySelect locates influential tokens with about log2(n)*2 queries instead of n, trading a modest drop in attack effectiveness for large query savings in black-box text attacks.","lead":"BinarySelect is a new way to choose which words to change in black-box text attacks, using binary search to cut the number of queries a researcher must send to a classifier. The paper reports roughly 30 to 60 percent fewer queries for a small loss in attack success, which could make adversarial attack research more feasible without large GPU budgets.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The binary-search heuristic is unvalidated: on IMDB, the GS top-1 word is absent from BS's top-10 in 58% of cases, so the query-efficiency claim may not find the same 'first token' as GreedySelect.","rationale":"After reading the paper in good faith, I agree with the reader's identification of the weakest assumption. The central claim has two parts: query efficiency and attack-effectiveness tradeoff. The query count of log2(n)*2 for finding a token is arithmetically sound as an upper bound on classifier calls for the described recursive procedure, but the phrase 'to find the first token' is only meaningful if the token found is the same one GreedySelect would return. Table 2 shows this is frequently not the case: the top-1 GS word is missing from BS's top-10 in 58% of IMDB examples. Section 12 candidly admits the uncertainty. This is not a fatal flaw, because the attack results still show a favorable tradeoff on long texts, and the paper frames the method as a query-saving alternative rather than an exact replacement. But the lack of a validation of the core search heuristic means the effectiveness drop is not explained or controlled for. A direct per-split accuracy measurement would settle whether the heuristic has empirical support. I do not see an internal contradiction that falsifies the tradeoff claim, so the verdict remains CONDITIONAL as the reader set.","tokens_in":17596,"tokens_out":9517,"duration_ms":85449,"concrete_test":"Instrument the released code to record, for the 1000 IMDB examples, whether the true GreedySelect top-1 word lies in the half chosen at the first split (and at each subsequent split). Report the per-split hit rate with a bootstrap confidence interval. If the first-split hit rate is not significantly above 50%, the binary-search premise is unsupported and the query savings come at the cost of effectively arbitrary token selection; if it is high (e.g., >80%), the heuristic is validated and the effectiveness gap has another cause.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing premise is the binary-search heuristic of Section 2.4: the half whose removal yields the larger probability drop contains the most influential token, so recursing into that half converges to the right word. The paper's own agreement experiments (Section 4.2, Table 2) show this premise fails often: for IMDB, the GreedySelect top-1 word is absent from the BinarySelect top-10 in 583 of 1000 cases, and the average rank of the top-1 GS word is 2.9. Section 12 explicitly says 'it is not known to what extent the top or (top X) word is retrieved.' Because the central claim compares queries to find 'the first relevant word,' a method that frequently returns a different word is not doing the same task as GreedySelect's n-query scan. The measured attack-effectiveness gap (e.g., IMDB Albert attack accuracy 66.9 vs 51.8 for GS at k=15, Table 3) is plausibly the direct consequence of this selection error. Without evidence that the selected word is close to the true most-influential token, the 'viable tradeoff' claim rests on an unvalidated heuristic.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":17836,"tokens_out":6288,"duration_ms":57491,"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":[{"comment":"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.","section":"§4.2, Table 2"},{"comment":"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.","section":"§3, Appendix A, Algorithm 1"},{"comment":"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.","section":"§4.1, Figure 3 and §5.1"},{"comment":"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.","section":"Appendix C, Algorithm 2"}],"minor_comments":[{"comment":"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.","section":"§1"},{"comment":"The worst-case formula 'n + Plog2(n) i=1 n/(2i)' uses 'P' where a summation symbol is intended; please typeset it properly.","section":"§3"},{"comment":"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.","section":"§7 and Appendix F"},{"comment":"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.","section":"§10.1"},{"comment":"The sentence 'Part of this issues lies with the goal of the selection methods' contains a grammatical error; please revise.","section":"§12"},{"comment":"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.","section":"Global"}],"recommendation":"major_revision","confidential_remarks":"The paper fits the scope of a security/robustness venue and the query-complexity bound is clear and internally consistent. The main concern is the unvalidated selection heuristic, which the authors themselves acknowledge in Section 12. I believe this is addressable with additional experiments (e.g., exhaustive leave-one-out on a subsample, or comparison against attribution methods), so I recommend major revision rather than rejection. Please also ensure the authors correct the baseline-query omission in the theoretical count and clarify the binary-tree pseudocode, as these affect the precision of the claims."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a sensible, clearly written paper about a simple but useful query-efficiency trick for black-box text attacks, and the headline query bound is correct. The main issue is that the empirical 'viable tradeoff' is less clean than the abstract suggests, and the paper's own agreement numbers show the selection heuristic often misses the top greedy token. Still, it deserves a serious referee.\n\nWhat's new: applying binary search to token selection, with a tree cache so computed segment probabilities are reused across iterations. The bound of about 2 log2(n) queries to find a first candidate versus n for greedy deletion is correct as an operation count, and the paper is careful to point out the extreme worst case where BS is worse. The attack experiments cover a lot of ground: five classifiers, three datasets, multiple k values, a character-level variant, and an oracle combination. Code and model links are provided. The limitations section is honest: it explicitly says it is not known to what extent the top word is retrieved.\n\nSoft spots: the selection heuristic is unvalidated. Section 4.2 shows the GS top-1 word does not appear in the BS top-10 in 583/1000 IMDB texts (and 255 AG News). The authors acknowledge this, but the intro still says BS finds 'the most relevant words', which is an overclaim. Second, the reported effectiveness drops don't recompute. For IMDB Albert, the paper says a 23% drop in attack effectiveness; from Table 3, the relative ASR drop is about 33%. That matters for judging the tradeoff. Third, no error bars or significance tests; on AG News BS is not better and sometimes uses more queries. Fourth, minor inconsistencies: the classifier list changes (XLNet appears in Table 10 but not Table 3), and the query count omits the initial scoring query. None of these are individually fatal, but together they make the central 'viable tradeoff' claim weaker than the presentation.\n\nWho it's for: people building or benchmarking black-box attacks who want a cheap selection primitive. It is a practical contribution, not a deep theoretical one.\n\nRecommendation: send it to review. A referee should ask for a clearer statement of what BS guarantees (it guarantees finding a local optimum of the segment-splitting procedure, not the global most influential token), corrected numbers, and uncertainty estimates. The code and breadth of experiments justify one round of revisions.","headline":"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.","tokens_in":18365,"tokens_out":5525,"would_cite":false,"duration_ms":50098,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["BinarySelect","black-box attack","query efficiency","word saliency","binary search","adversarial text attack","token selection","text classification"],"falsifier":"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.","tokens_in":17357,"feed_emoji":"🔍","tokens_out":7276,"duration_ms":57052,"temperature":0.7,"pith_summary":"The paper proposes BinarySelect, a word-selection method for black-box adversarial text attacks that replaces the standard one-token-at-a-time scan (GreedySelect) with a binary search guided by classifier probability drops. The central claim is that BinarySelect finds the first candidate token in $\\log_2(n) \\cdot 2$ queries instead of $n$, and that in full attacks this cuts total queries by up to 60% while costing only a smaller drop in attack effectiveness. The paper validates this across five classifiers and three datasets, and also on a character-level model, arguing that the tradeoff makes adversarial attack research feasible for researchers with limited computing resources. A sympathetic reader would care because query cost is the main barrier to black-box attack experiments, and any reliable reduction in queries lowers the resource floor for robustness testing.","feed_headline":"Binary search cuts black-box attack queries by up to 60%","feed_subtitle":"New selector finds each attack word in log(n)*2 queries, not n, making robustness tests affordable on limited hardware.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the probability-weighted word saliency replacement step the attack framework is built on, and is a GreedySelect-style baseline that BinarySelect replaces.","marker":"Ren et al., 2019"},{"why":"Provides the BERT-Attack statistics on percentage of perturbed tokens used to estimate average-case query counts for both methods.","marker":"Li et al., 2020"},{"why":"Represents the token-removal attacks whose one-token-at-a-time scan defines the n-query GreedySelect baseline.","marker":"Jin et al., 2020"},{"why":"Supplies the pretrained classifiers used as targets in the attack experiments.","marker":"Morris et al., 2020"},{"why":"Defines the ALBERT/BERT model family used both for the validation classifier and as an attacked model.","marker":"Devlin et al., 2019"},{"why":"Provides the CANINE character-level model used to verify BinarySelect at character granularity.","marker":"Clark et al., 2021"},{"why":"Supplies the ECES unicode replacement used in the character-level attack verification.","marker":"Eger et al., 2019"}],"fun_headline_variants":["BinarySelect slashes black-box attack queries by up to 60%","Find attack tokens in log(n)*2 queries, not n","Cut black-box attack queries by 60% with BinarySelect","BinarySelect: half the queries, same attack impact","Binary search for token selection: 60% fewer queries"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["BinarySelect slashes black-box attack queries by up to 60%","Find attack tokens in log(n)*2 queries, not n","Cut black-box attack queries by 60% with BinarySelect","BinarySelect: half the queries, same attack impact","Binary search for token selection: 60% fewer queries"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000705,"raw_usage":{"total_tokens":3197,"prompt_tokens":984,"completion_tokens":2213,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":600,"completion_tokens_details":{"reasoning_tokens":2128}},"tokens_in":600,"tokens_out":2213,"duration_ms":14876,"temperature":1.0,"reasoning_tokens":2128,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T15:46:18.761346+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"BERT pre-trains on next sentence prediction and masked language modelling tasks to gain an inherent understanding of text","cited_arxiv_id":null,"evidence_quote":"Defines the ALBERT/BERT model family used both for the validation classifier and as an attacked model."}],"review_version":1}