PASA: A Principled Embedding-Space Watermarking Approach for LLM-Generated Text under Semantic-Invariant Attacks

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: https://ai-kunkun.github.io/PASA_page/.

Large language models can now produce fluent text that is difficult to distinguish from human writing, which creates challenges for misinformation control, academic integrity, and intellectual property protection. A common way to address this problem is watermarking: adding hidden signals to AI-generated text so that it can later be detected. However, many existing watermarking methods are fragile because simple rewriting or paraphrasing can remove the signal while keeping the meaning almost unchanged. We propose PASA, a watermarking method that works at the level of meaning rather than individual words. Instead of relying on exact word choices, PASA groups tokens according to their semantic roles and embeds the watermark through these semantic patterns. This makes the watermark more robust when the text is paraphrased, while still preserving the quality and fluency of the generated text. Our theoretical analysis explains the trade-off between detectability, robustness, and text distortion and guides the design of the method. Experiments across multiple language models and rewriting attacks show that PASA detects AI-generated text more reliably than standard word-level watermarking methods. This work provides a step toward more trustworthy and accountable use of generative AI.