Robustness to Paraphrasing

Robustness to paraphrasing measures whether text watermarks survive content modifications that preserve meaning while changing surface-level wording. It is the most critical challenge for statistical text watermarking because paraphrasing directly attacks the token-level patterns that detection relies on.

Why Paraphrasing Threatens Watermarks

• Token-Level Patterns: Statistical watermarks (green/red list methods) create patterns in specific token sequences. Replacing tokens with synonyms destroys these patterns.
• Hash Chain Disruption: Detection relies on hashing previous tokens to determine green/red lists. Changed tokens produce different hashes, cascading through the entire sequence.
• Meaning Preservation: The attack preserves the content's value while stripping the watermark — the attacker loses nothing from paraphrasing.

Types of Paraphrasing Attacks

• Synonym Substitution: Replace individual words with equivalents — "happy" → "pleased," "utilize" → "use." Simple but partially effective.
• Sentence Restructuring: Change syntactic structure — active to passive voice, clause reordering, sentence splitting/merging.
• Back-Translation: Translate to French/Chinese/etc. and back to English — changes surface form while roughly preserving meaning.
• LLM-Based Rewriting: Use GPT-4, Claude, or similar models to rephrase text with explicit instructions to maintain meaning. Most effective attack — can reduce detection rates from 95% to below 50%.
• Homoglyph/Character Substitution: Replace characters with visually identical Unicode alternatives — doesn't change appearance but breaks text processing.

Research Findings

• Basic Watermarks: Green-list biasing methods lose 30–60% detection accuracy after aggressive LLM-based paraphrasing.
• Minimum Survival: Even heavy paraphrasing typically preserves 60–70% of tokens — some watermark signal often remains.
• Length Matters: Longer texts retain more watermark signal after paraphrasing — more tokens provide more statistical evidence.

Approaches to Improve Robustness

• Semantic Watermarking: Embed signals in meaning representations (sentence embeddings) rather than individual tokens. Meaning survives paraphrasing even when words change.
• Multi-Level Embedding: Watermark at lexical, syntactic, AND semantic levels simultaneously — paraphrasing may defeat one level but not all.
• Redundant Encoding: Embed the same watermark signal multiple times throughout the text — partial survival enables detection.
• Robust Detection: Train detectors on paraphrased examples — learn to identify residual watermark patterns even after modification.
• Edit Distance Metrics: Use approximate matching that tolerates some token changes rather than requiring exact hash matches.

The Fundamental Trade-Off

• Watermark Strength ↑ → More detectable but potentially lower text quality and more obvious to adversaries.
• Paraphrasing Robustness ↑ → Requires deeper semantic embedding which is harder to implement and verify.
• Perfect Robustness is Likely Impossible: If the meaning is preserved but every token is changed, a purely token-level method cannot survive.

Robustness to paraphrasing remains the hardest open problem in text watermarking — achieving watermarks that survive aggressive LLM-based rewriting without degrading text quality would be a breakthrough for AI content provenance.