💬 NLP

PMark: Towards Robust and Distortion-free Semantic-level Watermarking with Channel Constraints

This paper introduces PMark, a robust and distortion-free semantic-level watermarking method for large language models that utilizes a novel theoretical framework of proxy functions and multi-channel constraints to dynamically estimate sentence medians, thereby significantly improving resistance to paraphrasing attacks while maintaining text quality.

Original authors: Jiahao Huo, Shuliang Liu, Bin Wang, Junyan Zhang, Yibo Yan, Aiwei Liu, Xuming Hu, Mingxun Zhou

Published 2026-03-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jiahao Huo, Shuliang Liu, Bin Wang, Junyan Zhang, Yibo Yan, Aiwei Liu, Xuming Hu, Mingxun Zhou

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 an artist who paints beautiful landscapes. You want to protect your work from being stolen or claimed by someone else, so you decide to sign every painting.

The Problem with Current "Signatures"
Right now, most AI text "signatures" (watermarks) are like tiny, invisible dots of ink placed on individual brushstrokes (words).

The Flaw: If a thief takes your painting, scrapes off the brushstrokes, and repaints the scene using a different style but keeping the same picture, those tiny ink dots are gone. The thief can claim the new painting is theirs. This is what happens when someone uses an AI to "paraphrase" or rewrite AI-generated text; the old watermarks vanish.
The Distortion: To make these old watermarks work, some methods force the AI to pick specific words, like only using blue paint when it wanted to use red. This makes the final picture look a bit weird or unnatural (distorted).

The New Solution: PMARK
The paper introduces PMARK, a new way to watermark AI text. Instead of signing every word, PMARK signs the entire sentence as a single unit. Think of it not as signing the brushstrokes, but signing the whole landscape.

Here is how PMARK works, using a simple analogy:

1. The "Proxy Function" (The Magic Compass)

Imagine you have a magical compass (called a Proxy Function) that points in a specific, random direction.

When the AI generates a sentence, PMARK checks: "Does this sentence point in the 'Green' direction or the 'Red' direction according to our secret compass?"
If the sentence points "Green," it's a valid candidate. If "Red," it's not.

2. The "Median" Trick (No Distortion)

Old methods would throw away all the "Red" sentences and force the AI to pick a "Green" one. This is like telling a chef, "You can only cook with carrots, no matter what the recipe says." The food tastes bad (distortion).

PMARK's clever trick:
Instead of throwing away the "Red" sentences, PMARK looks at a group of candidate sentences and finds the middle point (the median).

It says, "Okay, half the sentences are 'above' the middle, and half are 'below'."
It randomly picks one side (Top or Bottom) to be the "Green" zone for this specific sentence.
Why this is genius: Because it picks the middle, it doesn't force the AI to pick weird, extreme sentences. It picks from the natural flow of the AI's thoughts. The text sounds perfectly natural, just like a human wrote it. No distortion.

3. The "Multi-Channel" Defense (The Fortress)

Here is the biggest problem with previous sentence-watermarks: They only use one compass. If a thief rewrites the sentence just enough to flip that one compass from "Green" to "Red," the watermark is gone. It's like having a lock with only one keyhole; a skilled thief can pick it.

PMARK's upgrade:
PMARK uses multiple compasses (called Channels) at the same time.

Imagine you have 4 different secret compasses, all pointing in different directions.
To be a valid "watermarked" sentence, it has to satisfy the rules of all these compasses simultaneously.
Even if a thief rewrites the sentence to fool Compass #1, it will likely still satisfy Compass #2, #3, and #4.
The Result: The watermark is incredibly hard to remove. It's like having a fortress with four different layers of security. To break in, the thief has to break all four locks at once, which is nearly impossible without destroying the sentence's meaning.

4. The "Offline" Mode (The Shortcut)

There are two versions of PMARK:

Online: The AI checks the "middle point" of the compasses every time it writes a sentence. This is very accurate but takes a bit more computing power (like checking a map every step of the way).
Offline: The researchers realized that in the vast world of language, the "middle point" is almost always zero (straight ahead). So, they just assume the middle is zero and skip the checking step. This makes it super fast and cheap to run, almost like driving with a GPS that knows the route so well it doesn't need to check the map anymore.

Why This Matters

For Creators: You can finally prove that a long, complex story or article was written by an AI, even if someone tries to rewrite it to hide the source.
For Readers: The text still sounds natural and high-quality. It doesn't sound robotic or forced.
For the Future: It sets a new standard for how we protect AI content, moving from fragile "word-level" signatures to robust "sentence-level" seals.

In a nutshell: PMARK is like putting a heavy, multi-layered, invisible seal on a whole paragraph of text. It's so strong that even if someone tries to melt the wax and reshape the letter, the seal remains intact, and the letter still looks perfect.

1. Problem Statement

The rapid advancement of Large Language Models (LLMs) has raised critical concerns regarding the traceability of AI-generated content and copyright protection. While token-level watermarking (e.g., Green-Red schemes) is effective, it is inherently vulnerable to paraphrasing attacks, where an attacker rephrases the text to preserve semantics while removing token-level statistical biases.

Semantic-Level Watermarking (SWM) attempts to solve this by treating the sentence as the fundamental unit. However, existing SWM methods (e.g., SemStamp, k-SemStamp) suffer from two major limitations:

Distribution Distortion: They typically rely on rejection sampling (split-and-reject), which biases the output distribution away from the original model, degrading text quality.
Lack of Theoretical Guarantees: There is no rigorous framework ensuring that the watermarked distribution remains identical to the unwatermarked one (distortion-free) or that the watermark is robust against adversarial attacks.
Sparse Evidence: Single-channel constraints often result in sparse watermark evidence, making the system vulnerable to attacks that slightly alter the sentence embedding.

2. Methodology: PMARK

The authors propose PMARK, a novel semantic-level watermarking framework that achieves distortion-free generation and high robustness through multi-channel constraints.

A. Theoretical Framework: Proxy Functions (PFs)

The paper introduces a unified theoretical framework based on Proxy Functions.

Definition: A Proxy Function $F: \Sigma^* \to \mathbb{R}$ maps a semantically complete sentence to a scalar value.
PMARK's PF: The function is defined as the cosine similarity between the sentence embedding and a pre-defined random pivot vector $v$ : $F_v(s) = \langle v, T(s) \rangle$ .
Distortion-Free Condition: The authors prove that if the sampling process selects sentences based on the median of the PF distribution, the marginal distribution of the output remains identical to the original model's distribution, provided the selection is symmetric (e.g., selecting the upper or lower half with equal probability).

B. Multi-Channel Constrained Generation

To address the sparsity of evidence and improve robustness, PMARK utilizes multiple orthogonal pivot vectors (channels).

Sampling: The model samples $N$ candidate sentences from the natural distribution.
Channel Constraints: For each of the $b$ orthogonal pivot vectors, the candidates are partitioned into two sets based on the median of their PF scores (upper vs. lower half).
Selection: A random seed determines which half (upper or lower) to keep for each channel. The final sentence is selected from the intersection of these valid sets.
Result: This process ensures that the final output satisfies multiple independent constraints simultaneously, significantly increasing the density of watermark evidence without distorting the text distribution.

C. Two Variants

Online PMARK: Dynamically estimates the median of the PF distribution for the current context using the sampled candidates. This guarantees strict theoretical distortion-freeness.
Offline PMARK: Leverages the empirical observation that in high-dimensional spaces, random vectors are nearly orthogonal, causing the median of the cosine similarity to concentrate around zero. It uses 0 as a fixed prior median, eliminating the need for dynamic estimation during generation. This reduces computational cost while maintaining low distortion.

D. Detection Mechanism: Soft-z-Test

To detect watermarks, PMARK employs a Soft-z-Test:

It reconstructs the expected median (either dynamically or via the fixed prior).
It calculates a "soft count" of watermark evidence for each sentence and channel. If a sentence's PF score aligns with the expected direction (based on the secret key), it contributes a score of 1; otherwise, it contributes a decaying exponential value based on the distance from the median.
A global z-statistic is computed to determine if the text is watermarked, offering robustness against noise and minor paraphrasing.

3. Key Contributions

Unified Theoretical Framework: Introduced the concept of Proxy Functions to analyze and unify existing SWM methods, providing a solid mathematical foundation for evaluating distortion and robustness.
Distortion-Free SWM: Proposed the first SWM method with provable distortion-free guarantees by utilizing median-based sampling, overcoming the quality degradation inherent in rejection sampling.
Multi-Channel Constraints: Identified that sparse evidence is the root cause of SWM vulnerability. Introduced multi-channel constraints to densify watermark evidence, significantly boosting robustness against paraphrasing and word-level attacks.
Efficient Implementation: Developed both an Online version (theoretically perfect) and an Offline version (computationally efficient with fixed priors), making the method practical for real-world deployment.

4. Experimental Results

The authors evaluated PMARK on OPT-1.3B and Mistral-7B models using C4 and BookSum datasets, comparing against token-level (KGW, UPV, SynthID) and semantic-level (SemStamp, k-SemStamp, SimMark) baselines.

Robustness:
- PMARK significantly outperforms all baselines under paraphrasing attacks (using Pegasus, Parrot, and GPT-3.5-turbo).
- Online PMARK achieved a True Positive Rate (TPR) of >93% across various paraphrasers, improving upon the best prior SWM (SemStamp) by up to 20.8% and token-level methods by up to 55.6%.
- It also demonstrated superior robustness against word-level attacks (deletion and synonym substitution), where previous SWMs failed due to sparse evidence.
Text Quality:
- PMARK maintains distortion-free properties, achieving Perplexity (PPL) scores comparable to or better than unwatermarked text.
- On the BookSum benchmark, Online PMARK achieved a PPL of 4.37–4.71, outperforming the best baseline (EXP) by nearly 0.7 points on Mistral-7B.
Efficiency:
- The Offline PMARK version requires only ~240 tokens per sentence for generation, a massive improvement over SemStamp which requires ~1,694 tokens.
- It achieves the best trade-off between token consumption and robustness among all SWM methods.

5. Significance

PMARK represents a paradigm shift in LLM watermarking:

Theoretical Rigor: It moves SWM from heuristic rejection sampling to a mathematically grounded, distortion-free framework.
Practical Viability: By solving the "sampling failure" and "high distortion" issues of previous methods, it makes semantic-level watermarking viable for real-world applications.
Security: The multi-channel approach effectively counters the most common adversarial strategy (paraphrasing), ensuring that machine-generated text can be reliably traced even after semantic modification.

In conclusion, PMARK offers a robust, high-quality, and theoretically sound solution for detecting AI-generated text, setting a new state-of-the-art for semantic-level watermarking.