PASA: A P rincipled Embedding-Space Watermarking A pproach for LLM-Generated Text under S emantic-Invariant A ttacks

Zhenxin Ai, Haiyun He · 2026

Read PASA: A P rincipled Embedding-Space Watermarking A pproach for LLM-Generated Text under S emantic-Invariant A ttacks by Zhenxin Ai, Haiyun He (2026) 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-2605-10977.txt.

Introduction

Zhenxin Ai and Haiyun He present PASA, a watermarking method for language-model text that survives paraphrasing attacks. Existing watermarks often break when meaning-preserving rewrites change the wording, since they hide marks in word choices rather than meaning.

PASA works on meaning groups in a hidden embedding space, tying token and helper sequences through shared randomness synced by a secret key and meaning history. Theory maps the jointly optimal embedding-detection pair, balancing detection accuracy, robustness, and distortion. Tests across models and strong paraphrase attacks show the mark holding while text quality stays high. Deployers get a principled, distortion-free watermark for responsible release.

Catalog record

CREATORZhenxin Ai, Haiyun He
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE76083
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.10977

Browse the full library · About the Tower of Babel

Full text

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

PASA: A P rincipled Embedding-Space Watermarking A pproach for LLM-Generated Text under S emantic-Invariant A ttacks Zhenxin Ai, Haiyun He Abstract Watermarking for large language models (LLMs) is a promising approach for detecting LLM-generated text and enabling responsible deployment. However, existing watermarking methods are often vulnerable to semantic-invariant attacks, such as paraphrasing. We propose PASA, a principled, robust, and distortion-free watermarking algorithm that embeds and detects a watermark at the semantic level. PASA operates on semantic clusters in a latent embedding space and constructs a distributional dependency between token and auxiliary sequences via shared randomness synchronized by a secret key and semantic history. This design is grounded in our theoretical framework that characterizes a jointly optimal embedding-detection pair, achieving the fundamental trade-offs among detection accuracy, robustness, and distortion. Evaluations across multiple LLMs and semantic-invariant attacks demonstrate that PASA remains robust even under strong paraphrasing attacks while preserving high text quality, outperforming standard vocabulary-space baselines. Ablation studies further validate the effectiveness of our hyperparameter choices. Webpage: PASA . Figure 1 : Left: Illustration of PASA , a principled watermarking approach operating in the latent embedding space on semantic clusters. By anchoring shared randomness to semantic clusters via a secret key, PASA remains robust against semantic-invariant attacks (e.g., paraphrasing) while ensuring distortion-free generation. Right: Quantitative results demonstrating that PASA outperforms standard vocabulary-space watermarking baselines across varying paraphrase strengths in both AUC-ROC and TPR@1%FPR. 1 Introduction Transformer-based large language models (LLMs) have demonstrated remarkable fluency and coherence in open-ended generation ( Achiam et al. 2024 ; Touvron et al. 2023 ; Yang et al. 2025a ) . As LLMs become increasingly powerful, the distinction between machine-generated and human-authored text has become blurred. This raises significant concerns around misuse, including large-scale disinformation ( Vykopal et al. 2024 ; Zhu et al. 2025b ) , automated spear phishing and targeted deception ( Hazell 2023 ) , amplified threats to organizational security ( Mirsky et al. 2023 ) , and challenges to academic evaluation systems ( Balalle & Pannilage 2025 ) . These concerns motivate the need for verifiable provenance and accountable attribution. Recent work has focused on active provenance via LLM watermarking ( Kirchenbauer et al. 2023 ; Liu et al. 2024c ; Yang et al. 2025b ; Dathathri et al. 2024 ) , which operates directly in the generation process. Unlike post-hoc detectors that are often unreliable, black-box watermarking leverages secret-key–conditioned randomized sampling to insert imperceptible yet statistically detectable patterns into generated text. This mechanism enables reliable third-party detection using only the text, without requiring access to model parameters or APIs. However, most existing watermarking schemes operate directly on the token vocabulary and construct detection statistics over surface-level token identities. Consequently, such approaches are inherently vulnerable to semantic-invariant attacks : meaning-preserving transformations, such as synonym substitution or paraphrasing, can arbitrarily alter the token realization while leaving the underlying semantics intact. As a result, semantic-invariant rewriting may easily remove the token-level watermarks and distort the associated detection statistics, undermining the effectiveness of naive watermarking schemes. While some alternatives improve robustness via heuristic semantic-aware logit biases ( Fu et al. 2024b ; Guo et al. 2024 ; He et al. 2024 ) , they inevitably shift the token distribution in expectation and sacrifice text quality for detectability. This observation highlights a fundamental scientific challenge: can we design a watermarking method that balances the following three facets? (i) Robustness under semantic-preserving transformations, (ii) Distortion-free generation, in the sense of preserving the original generation distribution, and (iii) Principled control over detection errors , particularly at low false-positive (false-alarm) rates, under adversarial semantic perturbations. Inspired by the well-known green/red list watermarking paradigm ( Kirchenbauer et al. 2023 ) , early attempts seek to improve robustness by aligning watermark behavior with contextual embeddings, i.e., token representations that depend on surrounding context, via soft mappings ( Liu et al. 2024a ; Zhang et al. 2024b ) . Along this line, subsequent studies further refine token-level logit biases (watermarking rules) to better trade off robustness and text quality ( Giboulot & Furon 2024 ; Shen et al. 2025 ; Kirchenbauer et al. 2024 ) . For instance, Liu & Bu 2024 employs an adaptive embedding strategy guided by token entropy, together with semantic-based seeding to mitigate quality degradation while enhancing robustness. These methods aim to better reflect semantic similarity than raw token identities, but still operate largely at the token level. More recently, partition-and-constrain strategies have been explored to design watermarking schemes related to semantic representations. SemStamp ( Hou et al. 2024a ) and k-SemStamp ( Hou et al. 2024b ) partition the sentence-embedding space using locality-sensitive hashing (LSH) or clustering to define watermark regions, while CoheMark ( Zhang et al. 2025a ) leverages fuzzy clustering to encourage discourse-level consistency. These results suggest that the geometric structure of the latent semantic space can provide a more stable anchor for watermarking than raw tokens. However, these approaches are largely heuristic and do not offer principled guarantees on the trade-offs among robustness, distortion, and detection accuracy. In parallel, some theoretical efforts have explored the fundamental trade-off between distortion and detection accuracy from both optimization and statistical viewpoints ( Takezawa et al. 2023 ; Wouters 2024 ; Cai et al. 2024 ; Huang et al. 2023 ; Li et al. 2025 ) . For example, DAWA ( He et al. 2025 ) proves the optimality of a distribution-adaptive approach at the token level, paired with a model-agnostic detector, achieving high true-positive rates (TPRs) at ultra-low false-positive rates (FPRs). Nonetheless, these works fail to incorporate robustness into their frameworks, nor do they guide the principled design of robust watermarking schemes. For a more comprehensive literature review, please refer to Appendix B . Taken together, existing approaches reveal a clear gap between practice and theory in LLM watermarking. On the one hand, semantic-aware designs suggest that operating in latent embedding spaces can substantially improve robustness to semantic-invariant attacks. On the other hand, existing theoretical frameworks primarily focus on token-level watermarking and do not account for robustness under meaning-preserving transformations, leaving the fundamental trade-offs among robustness, distortion, and detection accuracy poorly understood. This gap motivates a principled watermarking framework that operates at the semantic level while offering explicit theoretical guarantees. In this work, we introduce PASA , a P rincipled watermarking A pproach under S emantic-invariant A ttacks, which bridges this gap by elevating watermarking from the token level to the semantic level within a formal theoretical framework (cf. Figure 1 ). PASA operates in a latent semantic embedding space, embedding and detecting watermarks through a carefully designed distributional dependency between token sequences and auxiliary random sequences. Semantic-level shared randomness is synchronized by a secret key and the semantic history of a context window. Concretely, PASA models semantic-invariant rewriting through a semantic mapping function that assigns tokens to semantic clusters in the latent space, and introduces a novel two-stage sampling mechanism that enables stringent control of false alarms while maintaining distortion-free generation. This design is grounded in an information-theoretic framework extended from ( He et al. 2025 ) that characterizes the jointly optimal embedding–detection pair at the sequence level, achieving strong detection accuracy and semantic robustness while strictly preserving the original distribution. Our contributions can be summarized as

Read the complete text