Technical Summary: SAMARK - Self-Anchored Text Watermarking with Paragraph-Level Paraphrase Robustness

1. Problem Definition

The rapid advancement of Generative AI (GenAI) necessitates robust methods for identifying machine-generated text. While Large Language Model (LLM) watermarking has emerged as a solution, existing methods face a critical vulnerability: Paragraph-Level Paraphrasing Attacks (PPA).

Current watermarking schemes fall into two categories:

• Token-Level Watermarking (TWM): Modifies token sampling distributions (e.g., Green-Red lists). While efficient, these signals are easily diluted or removed by local edits, word substitutions, or deletions.
• Semantic-Level Watermarking (SWM): Treats sentences as the basic unit, embedding signals into semantic space. While more robust to local edits, existing SWM methods (e.g., SemStamp, PMark) rely on step-dependent random seeds. These seeds are typically derived from the preceding context (context-hashing) or fixed step indices.
  • Context-Dependent Vulnerability: If an attacker paraphrases the preceding sentences, the reconstructed seed changes, causing the detection signal to fail.
  • Step-Dependent Vulnerability: If an attacker reorders sentences within a paragraph, the step-indexed seed no longer matches the sentence's position, disrupting the detection score.

The core problem addressed is the lack of a semantic-level watermarking scheme that is inherently robust to PPA (reordering and global paraphrasing) while maintaining high text quality and detection accuracy.

2. Methodology: SAMARK Framework

The authors propose SAMARK (Self-Anchored Mark), a framework that eliminates dependency on sentence order and context by establishing a step-independent green region in semantic space.

2.1. Core Insight: Self-Anchored Condition (SAC)

The fundamental innovation is the Self-Anchored Condition, where the random seed for a sentence depends solely on the sentence's own intrinsic semantics, rather than its position or preceding context.

• Mechanism: For a sentence $u$, the random seed is $r_t = R(\phi(u); k)$, where $\phi(u)$ is the semantic representation and $k$ is a private key.
• Theoretical Guarantee: Theorem 1 proves that this condition establishes a globally static "feasible region" (green region) $\mathcal{G} \subseteq \Omega$. A sentence belongs to the green region if and only if its own semantics map to a valid partition under the key, regardless of when or where it appears in the text. This ensures robustness against reordering and context modification.

2.2. Generator: Multi-Channel Hyperbolic Sampling

To generate watermarked text, SAMARK employs a rejection sampling strategy enhanced by a multi-channel hyperbolic scoring mechanism:

1. Candidate Generation: Sample $N$ candidate sentences from the base LLM.
2. Channel Matching: Filter candidates to retain only those whose semantic embeddings align with a target flag pattern $R$ across $c$ pivot vectors (channels).
3. Hyperbolic Scoring: Instead of using raw cosine similarity, the method applies a hyperbolic tangent ($\tanh$) transform to the signed cosine similarities:
   $$S_{wm}(x) = \sum_{j=1}^{c} \tanh(\kappa \cdot r_j \cdot \cos(E(x), v_j))$$
   • Purpose: This amplifies candidates with strong alignment (pushing scores toward $\pm 1$) while suppressing near-zero noise. It prevents the concentration of scores near the decision boundary, which is a known failure point under paraphrasing attacks.
4. Diversity-Aware Filtering: To prevent the quality degradation often associated with strict watermark constraints (e.g., repetitive text), SAMARK integrates:
   • Hard Filtering: Removes candidates with high n-gram overlap or high semantic similarity to previously generated sentences.
   • Soft Regularization: Adds diversity bonuses ($\lambda_{div}$ for semantic diversity, $\lambda_{nov}$ for vocabulary novelty) to the final selection score.
5. Selection: A softmax distribution is applied to the filtered candidates to introduce controlled stochasticity.

2.3. Detector: Majority-Vote Blind Detection

The detector operates without prior knowledge of the specific target flags used during generation:

1. Segmentation & Embedding: Split text into sentences and compute embeddings.
2. Blind Flag Inference: Since the true flags $R$ are unknown, the detector infers them via majority voting over the directional responses of all sentences in the text.
3. Hyperbolic Alignment: Apply the same $\tanh$ transform used in generation to the inferred flags.
4. Z-Test: Compute a global z-statistic based on the transformed alignment matrix. If the statistic exceeds a threshold, the text is classified as watermarked.

3. Key Contributions

1. Self-Anchored Paradigm: The first framework to decouple watermark signals from sentence order and context, rendering them robust to PPA.
2. Multi-Channel Hyperbolic Scoring: A novel scoring mechanism that amplifies robust signals and suppresses noise, addressing the issue of score concentration near boundaries.
3. Diversity-Aware Filtering: A combined hard/soft filtering strategy that mitigates the robustness-quality trade-off, preventing semantic redundancy and repetitive generation.
4. Empirical Validation: Comprehensive evaluation demonstrating state-of-the-art performance in robustness and quality.

4. Experimental Results

Experiments were conducted on C4 and BOOKSUM datasets using Llama-3.1-8B and Mistral-Small-3.1-24B models.

• Robustness (RQ1): SAMARK significantly outperforms existing baselines (including KGW, SemStamp, and PMark) under PPA.
  • Under the challenging Doc-P II attack (aggressive paraphrasing), SAMARK achieves 90.2% TP@FP1% on Mistral+BOOKSUM, compared to 57.5% for the next-best baseline (PMark).
  • This represents an average improvement of over 30% over the strongest prior baselines.
  • SAMARK maintains high detection rates (>72%) across all attack scenarios, whereas baselines often drop below 30%.
• Text Quality (RQ2): SAMARK preserves generation quality competitive with unwatermarked text.
  • Pairwise LLM judgments show SAMARK achieves high win rates against unwatermarked baselines.
  • Metrics like Sentence Duplicate (SD) and Distinct-2 (D-2) indicate that the diversity-aware filtering effectively prevents the repetition issues common in other SWM methods.
• Efficiency (RQ3):
  • SAMARK reduces the computational overhead of semantic-level methods. It requires 47.44 sampled tokens per output token, significantly fewer than SemStamp (64.5) or PMark (49.73).
  • Detection latency is negligible (0.0014s per token), as it avoids the LLM-based re-generation required by some multi-bit methods.
• Ablation Studies (RQ4):
  • Removing the hyperbolic transform in generation causes a massive drop in robustness (e.g., Doc-P II TP@FP1% drops from 93.2% to 67.4%), confirming its critical role.
  • Disabling diversity filters leads to significant quality degradation (increased repetition and lower distinctness).

5. Significance and Claims

The paper claims that SAMARK represents a paradigm shift in semantic-level watermarking. By moving away from step-dependent seeds to a self-anchored approach, it solves the "intractable" problem of paragraph-level paraphrase robustness that has limited the field.

• Breaking the Trade-off: SAMARK successfully breaks the traditional trade-off between robustness and text quality, achieving high detection rates under severe attacks without sacrificing fluency or diversity.
• Practical Deployment: The method is presented as a viable solution for real-world LLM services where content is frequently edited, shortened, or paraphrased by users.
• Limitations: The authors modestly acknowledge that SAMARK still incurs higher latency than token-level methods due to the need for sentence-level candidate sampling (a limitation of current autoregressive LLMs) and that it currently supports zero-bit (yes/no) detection rather than multi-bit payload embedding.

In conclusion, SAMARK establishes a new state-of-the-art for semantic-level watermarking, offering a robust, high-quality, and efficient solution for identifying AI-generated text in adversarial environments.