LBA: Textual Hard-Label Adversarial Attack Under Low Query Budgets

1 Introduction

Deep neural networks (DNNs) have achieved remarkable success and are widely applied to natural language processing (NLP) tasks[Brown et al., 2020; Hu et al., 2022; Zhang et al., 2023]. However, as DNNs become increasingly popular and widely applied, potential security problems have also raised significant concerns. It has been observed that DNNs are easily deceived into producing wrong predictions by well-designed malicious examples, known as adversarial attacks[Goodfellow et al., 2015; Szegedy et al., 2014]. To reveal the vulnerabilities and improve the robustness of neural language models, researchers have focused on generating plausible adversarial examples. In recent years, there has been a surge in textual adversarial attacks[Alzantot et al., 2018; Linyang et al., 2020; Zang et al., 2020], further intensifying the pursuit of crafting high-quality adversarial texts.

∗Corresponding author.

Based on the outputs the adversary obtained from victim models, existing works on black-box textual adversarial attacks can be categorized into soft-label attacks and hard-label attacks. Soft-label attacks[Li et al., 2020; Jin et al., 2020; Zang et al., 2020] typically calculate the importance of words using the confidence scores output by target models, and then modify words based on the importance ranking until the predicted label is reversed. Since most real-world APIs do not provide confidence scores, hard-label attacks that only require the top-1 label are more practical and challenging. The prevalent hard-label attacks usually adopt one of the following algorithms: (1) heuristic algorithms[Maheshwary et al., 2021a], (2) gradient estimation algorithms[Ye et al., 2022; Ye et al., 2023], or (3) direction estimation algorithms[Liu et al., 2024a] to optimize an initialized adversarial example. In real-world applications, query budgets tend to be limited by monetary costs, and a massive number of similar inputs also increases the risk of exposing the adversary. Therefore, generating high-quality adversarial texts under low query budgets has become a critical concern for hard-label attacks. Although existing methods strive to improve query efficiency, they still struggle with the trade-off between query efficiency and quality. To address this issue, we reveal the limitations of existing hard-label attacks and propose a novel approach.

Existing methods essentially follow a greedy search paradigm, leading to query inefficiency. Their exploration strategy iteratively refines adversarial examples, where each iteration improves upon the result of the previous one to improve quality. To accomplish this, greedy search selects a word position for substitution and locks in the change, then proceeds to the next candidate position without revisiting previous decisions. However, generating high-quality adversarial examples depends on selecting critical positions and appropriate word substitutions for these positions, which involves exploring substitutions for all combinations of perturbable positions. During greedy search, the search space of perturbable position combinations gradually shrinks, blocking the discovery of certain feasible solutions. Ideally, an optimal adversarial sample would consider all possible position combinations in the text. However, this would introduce a greater challenge of combinatorial explosion.

To address this challenge, we propose a novel method named LBA, which performs sampling from an approximate distribution of high-quality adversarial examples. Sampling from a distribution that statistically abstracts the population and theoretically covers all the combinations offers an effective solution for mitigating the explosion of the search space, compared to directly selecting from the population itself. However, it is not trivial to accurately characterize the distribution of high-quality adversarial examples. To overcome this challenge, we draw inspiration from MetropolisHastings (MH) sampling[Chib and Greenberg, 1995] to construct an approximating distribution (i.e., the target function) and sample from it, aiming to obtain samples conforming to the desired distribution. For effective approximation, we leverage both prior and posterior knowledge to shape the target function. The prior is derived from predefined quality constraints (e.g., perturbation rate and semantic similarity). During each attack, the posterior is learned from samples accumulated over previous sampling iterations and is used to iteratively update LBA's understanding of aggressiveness, uncovering which positional changes most strongly induce label inversion. Specifically, we quantify aggressiveness by the importance of each position, measured as its empirical label-flip frequency from adversarial examples discovered in previous iterations. By leveraging this target function, LBA progressively refines its approximation of the desired distribution through iterative sampling, and is self-correcting even when initial priors are too coarse to accurately characterize the distribution of high-quality adversarial examples.

The sampling process is an iterative cycle of generating a candidate sample and evaluating it for acceptance or rejection. At each iteration, we first generate a candidate by replacing a randomly chosen word in the sample from the previous iteration with a synonym, following the principle of with-replacement sampling. Subsequently, we incorporate the target function and a transition proposal to probabilistically determine whether to accept and then query the candidate. As iterations progress, query-derived posterior knowledge refines the estimated importance of positions in the target function, leading to more efficient sampling. In turn, improved sampling yields more informative observations, creating a positive feedback loop. To sum up, our contributions are as follows:

• We reveal the limitations of existing hard-label textual adversarial attacks. Furthermore, to the best of our knowledge, we are the first to formulate query-efficient adversarial text generation as a distribution-based sampling problem.
• We propose LBA 1 (Low-query Budget hard-label Attack), a novel method for generating high-quality adversarial texts in the hard-label scenario.
• We conduct experiments on six language models, ranging from small-scale to large-scale architectures, includ-

1 The code and supplementary material are available at https:// github.com/SpeisBound/LBA

ing BERT, LLaMA 2, and GPT-4o, across four datasets. The results demonstrate that LBA significantly outperforms existing hard-label baselines.

2 RelatedWork

2.1 Soft-Label Adversarial Attack

Soft-label adversarial attacks rely on the confidence scores of target models to craft adversarial examples. Typically, these methods [Li et al., 2020; Jin et al., 2020; Li et al., 2021; Maheshwary et al., 2021b; Garg and Ramakrishnan, 2020; Gao et al., 2024] calculate the importance of words based on confidence scores and then perturb those words according to their importance ranking until adversarial examples are generated. For instance, Textfooler[Jin et al., 2020] uses importance ranking to sequentially perform synonym substitutions. Additionally, Optimization-based methods[Alzantot et al., 2018; Zang et al., 2020] utilize combinatorial optimization techniques to craft adversarial texts. For instance, PSO[Zang et al., 2020] treats adversarial text generation as a combinatorial optimization problem and adopts a particle swarm optimization algorithm to address the challenge.

2.2 Hard-Label Adversarial Attack

Existing hard-label attacks typically adopt heuristic algorithms [Maheshwary et al., 2021a; Peng et al., 2023], gradient estimation-based search [Ye et al., 2022; Ye et al., 2023; Liu et al., 2024b], or direction estimation-guided search [Liu et al., 2024a] to approach the decision boundary of the target model. HLA[Maheshwary et al., 2021a] explores hard-label adversarial attacks in NLP by employing the genetic algorithm to optimize adversarial texts. However, it is easy to fall into the local optimum and requires numerous queries to maintain its population. TextHoaxer [Ye et al., 2022] first formulates the hard-label adversarial attack as a gradientbased optimization problem in the word embedding space. It introduces a perturbation matrix to estimate the gradient at each position, thereby determining the fixed substitute word for each position. To mitigate inaccurate gradient estimation, LeapAttack [Ye et al., 2023] implements an interchange between discrete substitutions and continuous vectors, thereby enhancing the effectiveness of gradient utilization in discrete text. To alleviate the issue of gradient estimation consuming numerous queries, HQA-Attack [Liu et al., 2024a] evaluates position importance and sequentially predicts the perturbation direction for each position, representing each direction with a transition synonym to avoid querying the entire synonym set. However, the reliance on the greedy search paradigm limits the potential of existing methods to further enhance query efficiency. In contrast to the aforementioned textual hard-label methods, LBA adopts samplingbased strategy as its search paradigm to efficiently explore the search space.

3 Proposed Attack

3.1 ProblemFormulation

In this paper, we focus on adversarial text generation under the black-box hard-label setting, where the adversary can only access the top-1 predicted label from the target language model. The target model, denoted by a function f , accepts an input text x = [w1,w2, ...,wn] with n words and outputs a predicted label f(x) = y, which matches the corresponding ground-truth label. The goal of the attack is to craft a highquality adversarial text x′ by synonym substitution in x under a query budget of η. Specifically, x′ is designed to mislead the victim model f into outputting an incorrect prediction result, i.e., f(x) ̸= f(x′ ). The term "high-quality" denotes adversarial texts characterized by high similarity and fluency, which correspond to low perturbation rates, high semantic similarity, and fluent sentences. These attributes are crucial to aligning with the definition of adversarial texts, which requires them to be imperceptible to humans. Formally, we define the optimization problem as:

where Q(x′ , x) denotes the quality of x′ , which is positively correlated with the fluency F(x′ ) and similarity S(x′ , x) of the adversarial example. Qrs(x′ ) represents the number of queries required to craft x′ , and η is the given query budget.

3.2 Framework of LBA

The proposed approach is summarized in Algorithm 1, which first utilizes random initialization to generate an initial adversarial example x′0 and then optimizes it using the samplingbased strategy.

Initialization

To establish a starting point for sampling, we use random initialization, an approach commonly used in existing hard-label adversarial attacks[Maheshwary et al., 2021a; Ye et al., 2023; Ye et al., 2022; Liu et al., 2024a], to create an initial adversarial example. This process begins by randomly selecting a word wj from the input text x and substituting it with a randomly chosen synonym from its synonym set Syn(wj). This substitution is repeated for other words in x until an example x′0 = [w′1 ,w′2 , ...,w′n ] is generated, such that f(x) ̸= f(x′0 ). Before substituting a word, synonyms with mismatched partof-speech (POS) tags are filtered out to improve grammatical consistency. To further improve the semantic similarity of the initial adversarial text, we follow previous attacks to substitute some original words back into x′0 . Under limited query budgets, fast random initialization is a practical choice. Moreover, compared to greedy methods that progressively shrink perturbable positions during iteration, ourmethod is not more sensitive to initialization.

Sampling-Based Strategy

As shown in Figure 1, we employ a sampling-based strategy inspired by MH sampling to explore the search space from the initial adversarial example. MH sampling enables drawing samples from an intractable distribution by constructing a tractable approximation. It provides theoretical convergence guarantees under ergodicity, a condition our adaptive target function naturally satisfies as statistics accumulate. The sampling is an iterative process consisting of the following steps:

• Propose a candidate sample by substituting the word at a randomly selected perturbable position in the current sample (initially set to x′0 ) with a synonym.
• Calculate the acceptance rate of the candidate sample based on the target function and transition proposal.
• Accept or reject the candidate: if rejected, retain the current sample; if accepted, query the victim model to validate aggressiveness and update the current sample accordingly.

In the following, we provide a detailed introduction to the three steps of sampling:

(1) Proposing a Candidate Sample. This step aims to generate a candidate sample from the search space composed of all perturbable positions. In existing methods, the search space of positions gradually shrinks, which can block the discovery of certain feasible solutions. To avoid this, we generate candidate samples using with-replacement modification over the perturbable positions. Let lp denote the set of perturbable positions, i.e., the indices where the words differ between the initial adversarial example and its original counterpart. We generate the candidate sample x′i by substituting the j-th word wj in the current example x⋆ with a synonym skj that is randomly picked from Syn(wj) = {s1j , s2j , ..., srj }. The index j is randomly picked from the set lp. There are two reasons for selecting indices from lp. As shown in previous work, if the perturbable positions are expanded to include all words, the search space becomes excessively large, making

Algorithm 1: LBA

Input : Original text x = [w1,w2, ...,wn], ground-truth label y, target model f. Output: Adversarial example x′ . 1 Generate an initial adversarial example x′0 = [w′1 , w′2 , ..., w′n ] by randomly substitution 2 Current example x⋆ ← x′0 , optimal adversarial example x′ ← x′0 , sampling counter i ← 0 3 while Query budget is not exhausted do 4 i ← i + 1, select an index j form perturbable position indices lp 5 Propose a candidate sample x′i by substituting the j-th word of x⋆ with a synonym skj 6 α(x′i , x⋆ ) ←Calculate the acceptance rate of x′i via Eq. (2) 7 if Uniform(0, β) < α(x′i , x⋆ ) then 8 yi ← obtain the prediction result of x′i 9 if yi ̸= y then 10 Further improve the quality of x⋆ 11 Updating current example x⋆ and optimal adversarial example x′ 12 Return x′

it difficult to achieve effective coverage. Furthermore, these positions, compared to unchanged words, have already been validated for effectiveness during the initialization process.

(2) Calculating the Acceptance Rate. To select samples that better align with the desired distribution and control the stochasticity of sampling transitions, we use the acceptance rate to determine whether a proposed sample should be accepted. The acceptance rate is calculated by comparing the relative probabilities of the candidate and the current sample with respect to the target function and transition proposal. Specifically, the target function is designed to approximate the distribution of high-quality adversarial examples. The accuracy of the distribution approximation directly influences the effectiveness of the obtained samples and plays a guiding role in the overall sampling process. The transition proposal is asymmetric, measured by the change in semantic similarity between samples, guiding the search toward semantically coherent adversarial examples. The acceptance rate of a proposed candidate x′i , is defined as:

where π(x′i ) denotes the target function, and g(x⋆ | x′i ) represents the transition proposal. A detailed explanation of these components is provided below.

The target function π(x′i ) is designed for approximating the distribution of high-quality adversarial examples. Methodologically, a task-driven approach that maximizes the use of knowledge yields a more accurate approximation. Accordingly, the target function incorporates two key attributes, namely aggressiveness and quality, to capture the essential characteristics of high-quality adversarial examples. Aggressiveness reflects the attack capability of inducing label inversion, informed by posterior knowledge learned from samples accumulated over previous sampling iteration. Quality measures the similarity between candidate examples and original inputs, as well as fluency, derived from predefined quality constraints. Specifically, π(x′i ) is defined as:

where A(x′i ) and Q(x′i , x) quantify the aggressiveness and quality, respectively.

To achieve the estimation of aggressiveness, we transform the statistics from query feedback during the sampling history into position importance scores. Previous studies[Jin et al., 2020] have shown that only some key words act as influential signals for the final prediction. Without confidence scores, posterior knowledge from previous queries can identify positions more strongly correlated with aggressiveness. Therefore, we employ the empirical label-flip frequency to measure the importance of word position. Specifically, the importance of a position is determined by the frequency at which its perturbation induces label inversion, with this frequency calculated based on all discovered adversarial examples. These frequencies are normalized into final importance scores. The aggressiveness component is defined as follows:

where f(j) represents the number of times that position j, the index selected for substitution in the previous step, has appeared among the indices that induce label inversion.

The other component of the target function is the quality Q(x′ , x). According to the definition in Equation 1, "highquality" denotes adversarial texts characterized by high similarity and fluency. We evaluate similarity using semantic similarity and perturbation rate, and assess fluency using the increase in grammatical errors and perplexity. Since the priorities among these features differ, we integrate these four metrics via weighted summation, and it is defined as:

where λ1, λ2, λ3 and λ4 are weight parameters. S(x′i , x) measures the semantic similarity between x′i and x as follows:

where Enc(·) is the universal sentence encoder[Cer et al., 2018], a machine learning model that converts sentences into high-dimensional vectors. The term C(x′i , x′0 ) quantifies the reduction in perturbation rate, with larger values indicating a smaller perturbation rate in x′i compared to the initial adversarial example x′0 . G(x′i ) evaluates grammatical error changes, calculated with the help of LanguageTool, where G(x′i ) is set to 0 if x′i contains more grammatical errors than x⋆ , and 1 otherwise. The perplexity term P(x′i , x) calculates the perplexity of x′i and is defined as:

where ppl(x) is calculated with the help of GPT-2.

The transition proposal g(x⋆ | x′i ), representing the transition probability between the current sample and the candidate sample, is defined as:

The reason for choosing semantic similarity as the primary element of the transition proposal is that it plays a crucial role in guiding the search toward the decision boundary while avoiding abrupt jumps. To some extent, previous works[Maheshwary et al., 2021a; Liu et al., 2024a] view the search process as iteratively optimizing the semantic similarity between the original example and the adversarial example.

(3) Updating the Adversarial Example. This step determines whether to accept a candidate sample. Given the acceptance rate α(x′i , x⋆ ) for xi,A value is sampled from a uniform distribution over (0, β). If α(x′i , x⋆ ) exceeds this sampled value, the candidate sample is accepted. This randomness allows LBA to occasionally accept lower-probability candidates, enabling proper exploration of the target distribution. Upon acceptance, x⋆ is updated to x′i , and the target model is queried to obtain label yi. If yi differs from the ground truth label, xi is identified as an adversarial example. Finally, original words are substituted back where possible while preserving the adversarial condition.

4 Experiments

4.1 Datasets and Query Budgets

We randomly select 500 samples from the test sets of four commonly used datasets, including two short-text datasets and two long-text datasets: (1) MR[Pang and Lee, 2005], a movie review dataset; (2) AG[Zhang et al., 2015], a 4-class news classification dataset; (3) YELP[Zhang et al., 2015], a binary sentiment classification dataset; and (4) IMDB[Maas et al., 2011], another binary classification dataset. We allocate three query budgets, for each dataset based on the average number of queries required by a strong soft-label attack, Textfooler[Jin et al., 2020]. In all experiments, all queries, including queries used to initialize adversarial examples in hard-label attacks, are counted in the given budgets.

4.2 VictimModels

Based on the classification in [Zhao et al., 2023], we select six representative language models from three categories as victim models: Neural Language Models (NLMs), Pretrained Language Models (PLMs), and Large Language Models (LLMs). For NLMs and PLMs, we follow the setup used in existing hard-label adversarial attacks and target three models: WordCNN[Kim, 2014], WordLSTM[Hochreiter and Schmidhuber, 1997], and BERT[Devlin et al., 2019]. All the NLMs and PLMs are provided by TextAttack [Morris et al., 2020]. For LLMs, we adopt the following three popular models as victims: LLaMA2-7b-chat (LLaMA2, [Touvron et al., 2023]), Vicuna-7b-v1.5 (Vicuna, [Du et al., 2022]), and GPT-4o-mini-tts-2025-03-20 (GPT-4o, [OpenAI, 2023]). For the generation parameters of the two opensource LLMs, i.e., LLaMA2 and Vicuna, we set the temperature to 0.1 and the maximum tokens to 15.

4.3 Baselines

We choose two strong soft-label attacks and four state-ofthe-art hard-label attacks as our baselines. These baselines include: (1) Textbugger[Li et al., 2020], a soft-label attack that leverags word importance ranking to guide perturbations; (2) Textfooler[Jin et al., 2020], a soft-label attack baseline; (3) HLA[Maheshwary et al., 2021a], a heuristicbased hard-label attack method; (4) Texthoaxer[Ye et al., 2022], a gradient-based hard-label attack method; (5) LeapAttack[Ye et al., 2023], another gradient-based hard-label attack method; and (6) HQA-Attack[Liu et al., 2024a], a semantic similarity-guided hard-label attack method. We grant the soft-label attacks access to the confidence scores output by the target models to successfully execute the attacks.

4.4 Implementation Setting

Following prior work[Ye et al., 2023; Ye et al., 2022; Liu et al., 2024a], all the hard-label attacks utilize the same initialization method originally proposed by HLA [Maheshwary et al., 2021a] for fair comparison. For the quality component weights in our target function, we set λ1 = 0.25, λ2 = 0.50, λ3 = 0.15, and λ4 = 0.10. These values were determined through a sensitivity analysis, where we first optimized the allocation between the similarity group (λ1 +λ2) and the fluency group (λ3 +λ4), then tuned the ratio within each group. Detailed results are provided in Appendix C.

4.5 EvaluationMetrics

We evaluate the quality of adversarial examples from two dimensions: similarity and fluency. Following previous studies[Ye et al., 2022; Ye et al., 2023; Liu et al., 2024a], we use two metrics perturbation rate (Pert.) and semantic similarity (Sim.), to quantify the similarity. The semantic similarity is measured by the cosine similarity between the original text and its adversary, calculated using the Universal Sentence Encoder[Cer et al., 2018]. To assess the fluency of adversarial texts, we employ two metrics: perplexity (PPL) and the increase in grammatical errors (Ige.). We utilize GPT-2[Radford et al., 2019] to calculate the perplexity of texts. The increase in grammatical errors refers to the percentage of increased grammar mistakes compared to the original text.

To more objectively evaluate the aggressiveness and quality of adversarial texts, we further utilize GPT-4o as an evaluator and propose two metrics: consistency rate (CR) and fully understood rate (FUR). The CR metric measures the percentage of adversarial examples classified by GPT-4o as matching their ground truth labels, distinguishing whether aggressiveness stems from altering the original semantics:

where Xadv is the set of adversarial texts, y is the ground truth label of the original text, Eval(x′ ) denotes GPT-4o's predicted label, and I(·) returns 1 if the condition holds. The FUR metric is used to assess whether GPT-4o can fully understand the content of adversarial text, highlighting the robustness of the attack. A "fully understood" response indicates that the text is coherent and fluent, suggesting that perturbations introduced by the attack are more difficult to detect. FUR is defined as follows:

where Eval(x′ ) denotes whether GPT-4o's response is classified as "fully understood" (represented by 1).

4.6 Experimental Results

Comparison of Similarity and Fluency

We performed experiments with the given query budgets against WordCNN, WordLSTM, and BERT. Due to limited space, we present results on BERT in Table 1, and others in Appendix A.1. As shown in Table 1, LBA significantly outperforms baselines under all query budgets, achieving the highest similarity (Pert., Sim.) and fluency (Ige., PPL.) across all victim models and datasets. For example, when attacking BERT under the tiny budget, our method reduces the average Pert., Ige., and PPL by 56.18%, 58.56%, and 47.76%, respectively, while improving the average Sim.

by 11.74%, compared to the second-best baseline. Moreover, it can be observed that on datasets with larger combinatorial spaces, namely the long-text datasets YELP and IMDB, the performance gap in the quality metrics between LBA and other baselines is more significant compared to the other two datasets. This trend further highlights the effectiveness of LBA's distribution-based sampling strategy in efficiently considering all possible position combinations. To further analyze the distribution of generated samples in terms of similarity, we also compare the cumulative distributions of perturbation rate and semantic similarity for adversarial examples in Appendix A.2. As the query budget increases from tiny to tight and moderate levels, the results show that LBA maintains its superiority over other hard-label baselines.

Comparison of Attack Under More Query Budgets

In real-world scenarios, both limited and ample query budgets may be encountered. Therefore, to more comprehensively evaluate the applicability of LBA, we further compare the Pert. and Sim. of hard-label attacks across various query budgets. Considering the effect of text length on the search space, we choose two datasets with varying lengths: the short-text MR dataset and the long-text YELP dataset.

The results shown in Figure 2 indicate that LBA's performance continues to improve as the query budget increases and always surpasses that of other methods. This suggests that LBA effectively adapts to both limited and ample query budgets, making it well-suited for real-world applications.

Comparison of Attacking LLMs

To further evaluate the practicality of LBA on LLMs, we conduct experiments on representative LLMs under the tiny query budget. In view of the observed performance on NLMs and PLMs, we exclude HLA and select TextHoaxer, LeapAttack, and HQA-Attack as the baselines. We use 500 texts from two representative datasets, MR (a short-text dataset) and YELP (a long-text dataset), as the target samples. As shown in Table 2, the results show that LBA generates the highest quality adversarial texts in all three LLMs. For example, in attacks on dataset YELP, compared with the second best results, LBA achieves a 12.39% lower perturbation rate, 1.28% lower increase in grammatical errors, and 185.67 lower perplexity, and an 11.74% higher semantic similarity compared to the second-best method. Overall, the results not only confirm the robust practicality of LBA but also highlight the need to enhance the adversarial robustness of LLMs.

4.7 Evaluation by LLMAssistant

To more accurately evaluate the utility of the generated adversarial text, we leverage GPT-4o to automatically assess the adversarial examples across two aspects: aggressiveness and quality. Aggressiveness is measured by CR, which helps distinguish whether the aggressiveness of adversarial examples stems from altering the original meaning, further evaluating the semantic preservation of the samples. Quality is measured by FUR, which reflects whether the fluency of the samples aligns with natural language, further evaluating the comprehensibility of the samples. We use the adversarial texts generated against BERT with the tiny query budget. As shown in Table 3, LBA achieves the highest CR and FUR among the hard-label baselines, indicating that these adversarial texts remain the most semantically preserved and comprehensible. Human evaluation results are shown in Appendix A.3.

4.8 Ablation Study and Case Study

We study LBA's performance with and without the aggressiveness and quality components on MR against BERT under a tight query budget. To further validate the effectiveness of the aggressiveness component, we introduce the label inversion hit rate (LIHR), which measures the proportion of accepted samples that successfully induce label flipping. Results in Table 4 show that the aggressiveness component improves LIHR, while the quality component enhances sample quality. Overall, this demonstrates that both the aggressiveness and quality components play crucial roles in approximating the distribution of high-quality adversarial examples. We also list some adversarial texts crafted by LBA, which are shown in Appendix B. These adversarial texts further demonstrate that LBA can generate high-quality adversarial texts with low-query budgets.

5 Conclusion

In this paper, we present LBA, a novel sampling-based hardlabel attack that generates high-quality adversarial texts with low query budgets. Our approach overcomes the limitations of existing methods by designing a sampling-based strategy to mitigate the explosion of the search space, thereby improving the query efficiency. Through extensive experiments on six language models and four datasets, we demonstrate that LBA significantly outperforms existing hard-label attacks across all evaluation metrics. Furthermore, our results show that the adversarial texts generated by LBA are not only effective but also comprehensible, as evaluated by GPT-4o.

Acknowledgments

This work was supported by the Key Project of the National Natural Science Foundation of China under grant no. 62536007, the National Natural Science Foundation of China under grant no. 62502454, the Zhejiang Province Science Foundation under grant no. LD24F020002, LQ24F020025, LZYQ25F020003, the Zhejiang Province's 2025 "Leading Goose + X" Science and Technology Plan under grant no. 2025C02034, and the Jinhua Science and Technology Plan under Grant 2023-1-091.