💻 computer science

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

The paper introduces PASA, a principled watermarking algorithm that embeds and detects watermarks at the semantic level within a latent embedding space, achieving robustness against semantic-invariant attacks like paraphrasing while maintaining high text quality and optimal trade-offs between detection accuracy, robustness, and distortion.

Original authors: Zhenxin Ai, Haiyun He

Published 2026-05-13

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Zhenxin Ai, Haiyun He

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 have a very talented robot writer (a Large Language Model, or LLM) that can write stories, emails, and articles that sound almost exactly like they were written by a human. The problem is, how do you know if a piece of text came from this robot or a real person? And what if someone tries to trick the system by taking the robot's text and rewriting it to look different?

This paper introduces a new method called PASA to solve this problem. Think of it as a high-tech, invisible watermarking system that is incredibly hard to wash away.

Here is how it works, using some simple analogies:

1. The Problem: The "Paraphrase" Thief

Most current watermarking systems are like stamping a secret code directly onto individual words.

The Old Way: Imagine the robot writes, "The cat sat on the mat." The watermark is hidden in the specific words "cat," "sat," and "mat."
The Attack: A bad actor (or a clever editing tool) comes along and rewrites the sentence to: "The feline rested on the rug."
The Failure: Because the specific words changed, the old watermark detectors get confused. They can't find the "cat" or "sat" anymore, so they think the text is human-written. The watermark was washed away by the change in vocabulary.

2. The Solution: PASA (The "Theme" Tracker)

PASA changes the game. Instead of hiding the secret in the words, it hides the secret in the meaning (the "theme" or "vibe" of the sentence).

The Semantic Map: Imagine the robot's brain has a giant map where all words are grouped by what they mean, not how they look.
- Group A: "Cat," "Feline," "Kitty," "Puss."
- Group B: "Sit," "Rest," "Lounge," "Perch."
- Group C: "Mat," "Rug," "Carpet," "Floor."
The Secret Key: The robot and the detector share a secret key (like a password). This key tells them which "Group" to pick for the next word.
The Process:
1. The robot looks at the secret key and decides, "Okay, for this next word, I must pick something from Group A."
2. It picks "Feline" (which is in Group A).
3. The detector, using the same secret key, knows, "Ah, the next word should be from Group A."
4. The detector sees "Feline," checks the map, and says, "Yes! That matches our secret plan!"

3. Why It's Robust (The "Shape-Shifter" Defense)

Now, let's go back to the thief who changes "The cat sat on the mat" to "The feline rested on the rug."

Old System: "Cat" is gone. "Sit" is gone. "Mat" is gone. The watermark is broken.
PASA System:
- "Feline" is still in Group A.
- "Rest" is still in Group B.
- "Rug" is still in Group C.
- Even though the words changed, the groups (the semantic clusters) stayed exactly the same. The secret plan was followed perfectly. The detector still sees the pattern and knows, "This was written by the robot."

4. The "Distortion-Free" Promise

Usually, when you try to force a robot to follow a secret rule, it starts writing weird, unnatural sentences (like a robot trying to speak like a pirate). This is called "distortion."

PASA is special because it is distortion-free.

The Analogy: Imagine a chef who is told to only use ingredients from a specific basket. A bad system might force the chef to use a weird ingredient just to fit the basket, ruining the taste.
PASA's Trick: It uses a clever two-step sampling method. It picks the right basket (semantic group) based on the secret key, but then it picks the ingredient (the specific word) exactly how the chef usually would.
The Result: The text sounds 100% natural and high-quality, just like the robot's normal writing, but the secret pattern is still there.

5. The Results

The paper tested this against various "attacks" where text was rewritten, synonyms were swapped, and sentence structures were shuffled.

The Outcome: PASA remained strong. Even when the text was heavily rewritten (like changing "The movie has an interesting plot" to "The film features a fascinating tale"), PASA could still detect it.
Comparison: Older methods failed miserably under these rewrites, but PASA kept its cool, proving that hiding the watermark in the meaning is much safer than hiding it in the spelling.

In a nutshell: PASA is a way to watermark AI text by tagging the ideas instead of the words. This means even if someone tries to rewrite the text to hide the source, the secret "idea tags" remain visible to the detector, all without making the text sound robotic or unnatural.

Technical Summary: PASA – A Principled Embedding-Space Watermarking Approach

Problem Statement

The rapid advancement of Large Language Models (LLMs) has blurred the distinction between machine-generated and human-authored text, raising significant concerns regarding misinformation, automated deception, and academic integrity. While watermarking offers a promising solution for detecting AI-generated content, existing methods face a critical vulnerability: semantic-invariant attacks.

Most current watermarking schemes operate directly on the token vocabulary, constructing detection statistics based on surface-level token identities. Consequently, they are highly susceptible to meaning-preserving transformations such as synonym substitution, paraphrasing, or token replacement. These attacks can arbitrarily alter the specific tokens realized by the model while preserving the underlying semantics, effectively stripping away token-level watermarks and distorting detection statistics. Furthermore, existing approaches often struggle to balance three competing objectives: (i) robustness against semantic-preserving transformations, (ii) distortion-free generation (preserving the original text quality), and (iii) principled control over detection errors, particularly at low false-positive rates.

Methodology: PASA

To address these challenges, the authors propose PASA (Principled Embedding-Space Watermarking Approach under Semantic-invariant Attacks). Unlike prior methods that operate at the token level, PASA embeds and detects watermarks within the latent semantic embedding space.

Core Mechanism

PASA operates by partitioning the latent token embedding space into disjoint semantic clusters. It establishes a distributional dependency between token sequences and auxiliary random sequences, synchronized by a secret key and the semantic history of the context.

Semantic Cluster Mapping: A surjective function $f$ maps token embeddings to $K$ distinct semantic clusters. This mapping is designed to be invariant to token-level perturbations; different tokens with similar meanings fall into the same cluster.
Two-Stage Sampling Strategy:
- Stage 1 (Auxiliary Distribution Construction): The model constructs an auxiliary distribution over the semantic clusters. To control the false-alarm (FA) error, this distribution is "truncated" at a threshold $\alpha$ . An "overflow state" ( $\tilde{\zeta}$ ) is introduced to absorb probability mass exceeding the threshold, ensuring the FA error remains bounded while minimizing miss-detection (MD) error.
- Stage 2 (In-Cluster Sampling): The next token is sampled based on the selected auxiliary variable. If a specific cluster is selected, the token is sampled from within that cluster according to a re-normalized distribution. If the overflow state is selected, tokens are sampled across clusters in a manner that preserves the original Next-Token-Prediction (NTP) distribution in expectation.
Detection: The detector, equipped with the secret key and a surrogate language model (SLM), reconstructs the auxiliary distribution and the expected semantic history. It accumulates a score based on the alignment between the observed token's semantic cluster and the re-sampled auxiliary variable.

Theoretical Framework

The design of PASA is grounded in a formal theoretical framework that characterizes the jointly optimal embedding-detection pair for a given attack model. The authors prove that their approach achieves the fundamental trade-offs among detection accuracy, robustness, and distortion. Specifically, they demonstrate that PASA is distortion-free (i.e., the expected distribution of the watermarked text is identical to the original unwatermarked distribution) while providing explicit guarantees on robustness against semantic-invariant attacks.

Key Contributions

Principled Semantic-Level Watermarking: PASA elevates watermarking from the token level to the semantic level within a formal theoretical framework. By anchoring shared randomness to semantic clusters rather than individual tokens, it achieves superior robustness against paraphrasing and token replacement while maintaining distortion-free generation.
Theoretical Guarantees: The paper provides a theoretical framework for robust watermark embedding and detection under semantic-invariant attacks. It characterizes the fundamental trade-offs among detection accuracy, robustness, and distortion, identifying the jointly optimal embedding-detection pair and providing formal guarantees for PASA's performance.
Empirical Superiority: Extensive evaluations across multiple LLMs (Llama-2-13B, Mistral-8×7B) and datasets (C4, ELI5) demonstrate that PASA consistently outperforms standard baselines (including KGW, Exp-edit, AWTI, and DAWA) under both token-replacement and strong paraphrasing attacks (e.g., DIPPER).

Experimental Results

Robustness: Under T5-based token replacement attacks, PASA maintains high detection accuracy (e.g., TPR@1%FPR of 0.9296 on Llama-2-13B), significantly outperforming token-level baselines which degrade substantially. Under strong DIPPER paraphrasing attacks (involving lexical substitution and word-order reordering), PASA retains robust detection capabilities, whereas token-level methods suffer sharp performance drops.
Text Quality: PASA preserves text quality effectively. The Perplexity (PPL) of watermarked text generated by PASA (11.44) remains close to the unwatermarked baseline (12.41) and human text (10.41), confirming its distortion-free property. This contrasts with methods like Exp-edit and AWTI, which exhibit significantly higher PPL values.
Efficiency: PASA incurs negligible computational overhead. Generation latency increases by less than 0.5 seconds compared to the baseline, and detection latency (0.27s) is competitive, outperforming more complex robust baselines like AWTI (10.52s).
Ablation Studies: The authors found that a moderate number of semantic clusters ( $K=4$ ) and a small synchronization window ( $w=3$ ) offer the best trade-off between robustness and detection accuracy. Finer clustering ( $K > 500$ ) degrades robustness, reverting the method toward token-level behavior.

Significance and Claims

The paper claims that PASA bridges the gap between practice and theory in LLM watermarking. While semantic-aware designs have suggested that latent spaces improve robustness, and theoretical works have analyzed distortion-accuracy trade-offs, no prior work has successfully integrated robustness against semantic-invariant attacks into a principled, distortion-free framework.

The authors assert that PASA provides a reliable tool for AI governance by enabling the detection of machine-generated text even after aggressive paraphrasing, without compromising the quality of the generated content. They emphasize that their approach offers explicit theoretical guarantees on the trade-offs between robustness, distortion, and detection accuracy, a feature lacking in previous heuristic approaches. The work suggests that anchoring shared randomness at the semantic level is a key mechanism for enhancing watermark survivability against meaning-preserving transformations.

Limitations Acknowledged:
The authors note that PASA may degrade under extremely strong rewriting attacks that alter both semantic content and distributional structure. Detection on very short texts remains challenging due to limited statistical evidence. Additionally, the method relies on tokenizer compatibility between the generation model and the detector-side surrogate model, though they suggest deploying multiple lightweight detectors to mitigate this.