💬 NLP

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

The paper proposes LBA, a sampling-based method that iteratively integrates prior and posterior knowledge to construct an approximate distribution of high-quality adversarial examples, thereby significantly outperforming existing greedy approaches in generating semantically preserved hard-label adversarial texts under low query budgets.

Original authors: Shixin Guo, Ming Zhong, Xuhong Zhang, Dandan Zhao, Zhe Wang, Bo Zhang, Shouling Ji, Hao Peng

Published 2026-07-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Shixin Guo, Ming Zhong, Xuhong Zhang, Dandan Zhao, Zhe Wang, Bo Zhang, Shouling Ji, Hao Peng

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are playing a game of "Telephone" with a super-smart robot that has read almost every book ever written. You whisper a sentence to it, and it tells you exactly what that sentence means—whether it's a happy movie review or a sad news story. This robot is a type of Artificial Intelligence called a Deep Neural Network, and it's incredibly good at understanding language. But, like any smart creature, it has a secret weakness: it can be tricked. If you change just a few words in a sentence, the robot might suddenly think a happy movie is a tragedy. This is called an "adversarial attack."

The tricky part is that in the real world, you can't just ask the robot, "How sure are you?" You can only ask, "What do you think this is?" and get a simple "Yes" or "No" answer. This is known as a "hard-label" scenario. To trick the robot without asking too many questions (which might get you caught or cost too much money), you have to be very clever. Most people try to fix the sentence one word at a time, like a gardener pruning a bush branch by branch. But this often misses the perfect combination of changes needed to fool the robot, wasting a lot of time and questions.

This paper introduces a new method called LBA (Low-query Budget hard-label Attack) that solves this problem by changing the game entirely. Instead of pruning the bush one branch at a time, the authors treat the problem like a treasure hunt using a magical map.

The Old Way: The Blind Gardener

Imagine you are trying to find the perfect combination of ingredients to make a cake that tastes exactly like a specific flavor, but you can only taste the result once you bake it. The old methods act like a blind gardener who picks one flower, cuts it off, and sees if the garden looks better. If it does, they keep the cut; if not, they put it back and try the next flower. They never look at the whole garden at once. This "greedy" approach often gets stuck in a local patch of flowers, missing the perfect arrangement that requires changing several flowers at once. It wastes a lot of time (or "queries") trying to find the right spot.

The New Way: The Magical Map (LBA)

The authors of this paper realized that instead of guessing one flower at a time, they could build a map that shows where the "best" changes are likely to be found. They call this a "sampling-based method."

Here is how their map works:

The Prior Knowledge (The Initial Map): Before they even start, they draw a rough map based on rules they already know, like "don't change too many words" and "keep the sentence sounding natural."
The Posterior Knowledge (Updating the Map): As they test different sentences and ask the robot for answers, they learn from the results. If changing a specific word often tricks the robot, they mark that spot on their map as "high value." If a change makes the sentence sound weird, they mark it as "low value."
The Sampling (The Treasure Hunt): Instead of walking step-by-step, they use this map to "sample" or pick promising combinations of word changes. It's like throwing darts at a board where the bullseye is the most likely place to find a winning trick. As they throw more darts, the map gets sharper, guiding them to better spots even faster.

What They Found

The researchers tested this new method against six different types of language robots, ranging from small ones to massive ones like GPT-4o. They used four different sets of data, including movie reviews and news articles.

The results were impressive. In a world where you are only allowed to ask the robot a limited number of questions (a "low query budget"), LBA consistently found better tricks than the old methods.

Better Quality: The sentences LBA created sounded much more natural. They changed fewer words and kept the meaning of the original sentence intact better than the other methods.
Smarter Efficiency: On long texts (like long movie reviews), the old methods struggled to find the right combination of changes. LBA, however, excelled at finding the perfect mix of word swaps, even in these complex scenarios.
Human Approval: When the researchers asked humans to read the tricked sentences, the humans couldn't tell the difference between the original and the tricked version. They also asked a super-advanced AI (GPT-4o) to judge the sentences, and it agreed that LBA's tricks were the most clever and least obvious.

Why This Matters

The paper suggests that by using this "map-based" sampling approach, we can trick AI models much more efficiently. This doesn't mean the AI is broken; rather, it shows that the old way of trying to trick AI (one word at a time) is inefficient. By understanding that the best tricks often involve a specific combination of changes rather than a single change, LBA opens a new door for testing how robust our AI systems really are. It proves that with a smarter strategy, you can achieve high-quality results without needing to ask the robot a million questions.

Technical Summary: LBA (Low-query Budget hard-label Attack)

1. Problem Statement

The paper addresses the challenge of generating high-quality adversarial texts in a black-box hard-label scenario under low query budgets.

Context: Deep Neural Networks (DNNs) in Natural Language Processing (NLP) are vulnerable to adversarial attacks where malicious inputs cause incorrect predictions.
Constraint: In real-world applications, attackers often cannot access confidence scores (soft labels) and are restricted to the top-1 predicted label (hard labels). Furthermore, query budgets are limited due to monetary costs and the risk of detection from excessive similar inputs.
Limitation of Existing Methods: Current hard-label attacks predominantly rely on greedy search paradigms. These methods iteratively select a single word position for substitution and lock it in before moving to the next. This local search approach fails to explore the full combinatorial space of position substitutions, often leading to suboptimal solutions and excessive query costs to escape local optima. Exhaustive search is computationally infeasible due to combinatorial explosion.

2. Methodology: LBA

The authors propose LBA (Low-query Budget hard-label Attack), a novel method that reframes adversarial text generation as a distribution-based sampling problem. Instead of greedy local refinement, LBA samples from an approximate distribution of high-quality adversarial examples, leveraging both prior and posterior knowledge.

Core Framework

The method is inspired by Metropolis-Hastings (MH) sampling. It constructs a target function to approximate the distribution of high-quality adversarial examples and iteratively refines this distribution through sampling.

A. Initialization

LBA begins with a random initialization (similar to HLA) to generate an initial adversarial example $x'_0$ that misleads the victim model. This involves randomly substituting words with synonyms while filtering for Part-of-Speech (POS) consistency.

B. Sampling Strategy

The core loop involves three steps:

Candidate Proposal: A candidate sample $x'_i$ is generated by replacing a word at a randomly selected perturbable position (from the set of indices where the current example differs from the original) with a synonym. This uses with-replacement sampling to avoid the shrinking search space issue found in greedy methods.
Acceptance Rate Calculation: The candidate is evaluated using an acceptance rate $\alpha$ $α$ , defined by the ratio of the target function values and transition proposals:
$\alpha(x'_i, x^\star) = \min \left( 1, \frac{\pi(x'_i)g(x^\star | x'_i)}{\pi(x^\star)g(x'_i | x^\star)} \right)$
- Target Function $\pi(x'_i)$ : This approximates the desired distribution and is the product of Aggressiveness ( $A$ $A$ ) and Quality ( $Q$ $Q$ ):
  $\pi(x'_i) = A(x'_i) \cdot Q(x'_i, x)$
  - Aggressiveness ( $A$ ): Derived from posterior knowledge. It quantifies the "importance" of a position based on the empirical frequency that perturbations at that position have induced label inversions in previous iterations. This is calculated using a softmax over empirical label-flip frequencies.
  - Quality ( $Q$ ): Derived from prior knowledge (predefined constraints). It is a weighted sum of semantic similarity, perturbation rate reduction, grammatical error increase, and perplexity.
- Transition Proposal $g$ : An asymmetric probability based on the change in semantic similarity between the current and candidate samples, guiding the search toward semantically coherent examples.
Update: If the candidate is accepted (based on a uniform random threshold), the current example is updated, and the victim model is queried to validate the label inversion. The posterior knowledge (position importance) is updated based on the query result.

3. Key Contributions

Problem Formulation: The authors identify the limitations of greedy search in hard-label attacks and are the first to formulate query-efficient adversarial text generation as a distribution-based sampling problem.
Novel Algorithm (LBA): They propose LBA, which integrates prior constraints (quality) and posterior feedback (aggressiveness) into a target function for MH-style sampling. This allows the method to self-correct and explore the search space more effectively than greedy approaches.
Comprehensive Evaluation: Extensive experiments were conducted on six language models (ranging from small-scale NLMs like WordCNN to large-scale LLMs like GPT-4o) across four datasets (MR, AG, YELP, IMDB).

4. Experimental Results

The paper reports that LBA significantly outperforms state-of-the-art baselines (including HLA, TextHoaxer, LeapAttack, and HQA-Attack) across all evaluation metrics:

Query Efficiency: LBA achieves high attack success rates (ASR) under "Tiny," "Tight," and "Moderate" query budgets.
Quality Metrics: LBA generates adversarial texts with:
- Lower Perturbation Rates: Fewer words changed.
- Higher Semantic Similarity: Closer to the original meaning.
- Better Fluency: Lower perplexity (PPL) and fewer grammatical errors (Ige).
LLM Robustness: LBA demonstrates superior performance when attacking Large Language Models (LLMs) like LLaMA 2, Vicuna, and GPT-4o, where the performance gap with baselines is particularly pronounced on long-text datasets.
Human and LLM Evaluation:
- GPT-4o Assessment: LBA achieved the highest Consistency Rate (CR) (preserving original semantics) and Fully Understood Rate (FUR) (comprehensibility) among hard-label baselines.
- Human Evaluation: Human annotators correctly classified LBA-generated adversarial examples at higher rates than other methods, confirming that the attacks successfully fool the victim model while preserving the original sentiment/meaning.

5. Significance and Claims

The paper claims that LBA addresses the critical trade-off between query efficiency and adversarial quality in hard-label scenarios. By moving away from greedy local search to a sampling-based strategy that learns from accumulated query feedback, LBA mitigates the combinatorial explosion of the search space.

The authors emphasize that their method is not only more efficient but also generates more semantically preserved and comprehensible adversarial texts. This suggests that LBA is a more realistic threat model for real-world applications where attackers have limited resources and must avoid detection. The work highlights the need to enhance the adversarial robustness of both traditional NLP models and emerging Large Language Models.