Semantic-Preserving Adversarial Attacks on LLMs: An Adaptive Greedy Binary Search Approach

Chong Zhang, Xiang Li, Jia Wang, Shan Liang, Haochen Xue, Xiaobo Jin · 2025

Read Semantic-Preserving Adversarial Attacks on LLMs: An Adaptive Greedy Binary Search Approach by Chong Zhang, Xiang Li, Jia Wang, Shan Liang, Haochen Xue, Xiaobo Jin (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-18756.txt.

Introduction

Chong Zhang and co-authors show how an attacker can hijack the auto-rewrite step built into large language models, in a paper from two thousand twenty-five. Many chat tools first polish the user prompt and show the polished text before they reply. The attack makes tiny word swaps that keep the sense near the same but bend the final output away from user intent.

The search works in layers, masking key word units and testing swaps at set meaning checks. Across more than two thousand test cases it beat older attacks at the same level of meaning match. Tests covered both shop and open models. Readers who build chat tools get a clear warning about a hidden weak point.

Catalog record

CREATORChong Zhang, Xiang Li, Jia Wang, Shan Liang, Haochen Xue, Xiaobo Jin
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE50 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-18756

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Semantic-Preserving Adversarial Attacks on LLMs: An Adaptive Greedy Binary Search Approach Chong Zhang, Xiang Li, Jia Wang, Shan Liang, Haochen Xue, Xiaobo Jin Abstract Large Language Models (LLMs) increasingly rely on automatic prompt engineering in graphical user interfaces (GUIs) to refine user inputs and enhance response accuracy. However, the diversity of user requirements often leads to unintended misinterpretations, where automated optimizations distort original intentions and produce erroneous outputs. To address this challenge, we propose the Adaptive Greedy Binary Search (AGBS) method, which simulates common prompt optimization mechanisms while preserving semantic stability. Our approach dynamically evaluates the impact of such strategies on LLM performance, enabling robust adversarial sample generation. Through extensive experiments on open and closed-source LLMs, we demonstrate AGBS’s effectiveness in balancing semantic consistency and attack efficacy. Our findings offer actionable insights for designing more reliable prompt optimization systems. Code is available at: https://github.com/franz-chang/DOBS . 1 Introduction The rapid deployment of large language models across industries has led to a paradigm shift in human-computer interaction, with leading manufacturers increasingly integrating automatic suggestion optimization directly into the user interface. Systems such as Microsoft’s Bing Copilot Microsoft 2023 and the data-efficient plug-and-play suggestion enhancement system (PAS) Zheng et al. 2024 embody this trend, employing complex algorithms to reconstruct user queries to improve response accuracy. These systems typically operate through a multi-stage refinement process that may include vocabulary normalization, intent disambiguation, and context-aware expansion—processes that have shown significant effectiveness in standardized testing environments. However, these automatic suggestion engineering systems have exposed their fundamental limitations in real-world applications. As shown in Figure 1, static optimization strategies often lead to semantic drift—a phenomenon in which iterative suggestion modifications gradually deviate from the user’s original intent—in the face of the inherent diversity of user contexts, language patterns, and task requirements. This drift is particularly severe in edge cases, where automated systems may: (1) incorrectly resolve lexical ambiguities, (2) overfit common query patterns while ignoring specific requests, or (3) inadvertently amplify subtle biases present in the training data. More worryingly, these optimizations create attack surfaces for adversarial attacks, as demonstrated by recent research on just-in-time injection vulnerabilities Zou et al. 2023 ; Maloyan and Namiot 2025 . Figure 1: The core of adaptive greedy binary search. After identifying the keyword x_{i} for each clause and masking it, we use this method to determine the \omega_{j} that replaces x_{i} and semantically compare the new clause with the original to guide the selection of top-k positions. To address these challenges, we propose the Adaptive Greedy Binary Search (AGBS) framework, which outperforms the current state-of-the-art methods in three key dimensions: Dynamic Semantic Stability: Unlike traditional beam search methods that apply fixed constraints, AGBS implements an adaptive threshold mechanism that dynamically adjusts the semantic similarity bounds based on real-time analysis of the effects of instantaneous perturbations. This innovation enables precise control of the balance between attack strength and semantic preservation. Hierarchical Cue Decomposition: AGBS adopts a novel hierarchical decomposition strategy to first identify key semantic units (keywords, clauses, and contextual markers) in the cue, and then applies targeted perturbations while maintaining grammatical and pragmatic coherence. Through extensive experiments, we demonstrate that AGBS can successfully induce targeted misbehavior in 2400 test cases of commercial LLMs while maintaining an average BERTScore of approximately 0.80 compared to the original prompts. These findings not only validate the effectiveness of our approach but also reveal fundamental limitations of current prompt optimization methods. Our main contributions include: • Formalize the attack surface of just-in-time optimization with a novel adversarial attack strategy, achieving high success rates across LLMs and datasets. • Integrate AGBS into automatic prompt learning to improve the concealment and success rate of adversarial attacks against complex scenarios and diversified inputs. • Provide practical guidelines for developing more robust just-in-time optimization systems that balance practicality and security. 2 Related Work 2.1 Adversarial Attacks on Deep Neural Networks Adversarial attack research mainly changes the input to detect the vulnerability of the model: since deep neural networks are vulnerable to adversarial samples, small perturbations may lead to serious classification errors Szegedy 2013 . In response to this phenomenon, the fast gradient representation method (FGSM) Goodfellow et al. 2014 shows how to induce model errors by generating perturbations through gradients. In the field of natural language processing, the discrete nature of text data makes text adversarial attacks more challenging Li et al. 2018 , so researchers have proposed a variety of complex attack methods that can bypass defense techniques Carlini and Wagner 2017 . On the other hand, adversarial training can effectively improve the robustness of the model, which has been proven to be one of the effective methods to improve the robustness of the model Mądry et al. 2017 . These studies have not only promoted the development of adversarial attack techniques and defense strategies but also had an important impact on the application of artificial intelligence in security-sensitive fields. 2.2 Adversarial Attacks for Large Language Models Adversarial attacks based on both white-box and black-box pose a significant threat to LLMs. In the white-box scenario, gradient-based distribution attack (GBDA) Guo et al. 2021 leverages the Gumbel-Softmax technique for optimization with a differentiable adversarial loss, and uses BERTScore and perplexity to enhance the perceptibility and fluency of the attack. HotFlip Ebrahimi et al. 2018 manipulates adversarial text by mapping text operations to a vector space and computing derivatives, while AutoPrompt Shin et al. 2020 leverages a gradient-based strategy to optimize the prompt template. Wallace et al. Wallace et al. 2021 introduced methods for discovering universal adversarial triggers to change model outputs. However, these gradient-based attacks do not apply to closed-source large language models. Black-box adversarial attacks leverage various techniques to exploit vulnerabilities in NLP models. Ribeiro et al. Ribeiro et al. 2018 introduced SEAs, a token manipulation method to identify and mitigate excessive sensitivity in models. BERT-Attack Li et al. 2020 uses context-aware word replacements to subtly modify inputs. Hint injection attacks, such as target hijacking and hint leakage, embed harmful instructions to deceive LLMs, as explored by McKenzie McKenzie et al. 2023 and Perez & Ribeiro Perez and Ribeiro 2022 . Other black-box methods include query-free techniques like BadNets Gu et al. 2017 and model replacement strategies Papernot et al. 2017 . Goal-driven attacks maximize KL divergence, equivalent to increasing Mahalanobis distance between clean and adversarial text embeddings, effectively targeting LLMs Zhang et al. 2024b ; Zhang et al. 2024a . These approaches highlight diverse tactics for addressing model security challenges Wang et al. 2024 . 2.3 Adversarial Attacks with Beam Search The TABS Choi et al. 2022 method combines semantic beam search with contextual semantic filtering while maintaining the Top-k candidate adversarial sentences and effectively narrows the search space through semantic filtering to maintain semantic consistency. In the improved beam search algorithm Zhao et al. 2021 , each iteration selects the K nodes from the previous iteration, and the word selection range is expanded by backtracking the iteration to improve efficiency. In leveraging transferability and improved beam search Zhu et al. 2022 , multiple words are randomly selected for replacement, multiple candidate sentences are generated for semantic filtering, and finally, the beam width selects the sentence with the highest defense. In Beam Attack Zhu et al. 2023

Read the complete text