Statistical Watermarking

Statistical watermarking embeds detectable patterns into the token probability distribution during text generation by language models. The technique modifies how tokens are sampled without noticeably changing output quality, creating a statistical fingerprint that authorized verifiers can detect.

How It Works (Kirchenbauer et al., 2023)

• Vocabulary Partitioning: For each token position, use a hash of preceding tokens to partition the vocabulary into "green" (preferred) and "red" (avoided) lists.
• Biased Sampling: During generation, add a bias $\delta$ to green token logits, making them more likely to be sampled.
• Detection: Given a text, recompute the green/red partitions using the same hash function and count green tokens. A statistically significant excess of green tokens (measured by z-score) indicates watermarking.

Watermark Variants

• Hard Watermark: Only allow green token selection — strongest signal but may reduce text quality, especially when the best token is red.
• Soft Watermark: Add a bias $\delta$ to green token logits — softer impact on quality while maintaining detectability.
• Multi-Key Schemes: Rotate hash functions or use multiple keys to increase security and prevent reverse-engineering.
• Distortion-Free: Use shared randomness (e.g., random sampling reordering) to maintain the exact original distribution while enabling detection. No quality degradation at all.

Detection Mathematics

• Null Hypothesis: Text is not watermarked — green tokens appear at the expected rate (~50%).
• Test Statistic: $z = (|s|_G - T/2) / \sqrt{T/4}$ where $|s|_G$ is the count of green tokens and $T$ is total tokens.
• Decision: If $z$ exceeds a threshold (e.g., $z > 4$), reject the null hypothesis — text is watermarked.
• Minimum Length: Reliable detection requires sufficient text length — typically 200+ tokens for high confidence.

Key Trade-Offs

• Strength vs. Quality: Larger bias $\delta$ makes watermarks easier to detect but may reduce text naturalness.
• Robustness vs. Detectability: Stronger patterns survive more modifications but are easier for adversaries to detect and exploit.
• Context Window: Longer hash windows (more preceding tokens) create stronger watermarks but increase sensitivity to text modifications.

Robustness Challenges

• Paraphrasing Attacks: Rewriting text with different words can disrupt token-level patterns.
• Token Editing: Inserting, deleting, or substituting tokens breaks the hash chain.
• Cross-Model Transfer: Watermarked text copied and regenerated by another model loses the watermark.
• Short Texts: Detection reliability decreases for short passages due to insufficient statistical signal.

Statistical watermarking is the most studied text watermarking approach — it provides mathematical guarantees on detection confidence and has been adopted by major AI labs as a potential tool for responsible AI content generation.