AliMark: Enhancing Robustness of Sentence-Level Watermarking Against Text Paraphrasing

Image generated by AI

TLDR

• What: AliMark is a sentence-level LLM watermarking framework that reformulates watermarking as a bit sequence encoding and global alignment problem, utilizing a proactive sentence "Re-Structurer" and adaptive alignment to survive structural paraphrasing attacks.
• Who's at risk: LLM deployment platforms, plagiarism detection tools, and content provenance systems (e.g., enterprise RAG pipelines, code assistants, or academic integrity checkers) relying on prefix-based watermarks.
• Key number: Under aggressive GPT-3.5 text rewriting, AliMark maintains a detection rate of 66.6% TPR@5% on the Booksum dataset, whereas the state-of-the-art SemStamp baseline collapses to 22.0%.

As generative models like GPT-4o, Claude 3.5 Sonnet, and Google's Gemini become deeply integrated into writing workflows, identifying AI-generated content has transformed into a critical security and intellectual property challenge. Traditional token-level watermarking techniques are easily broken by minor token substitutions, prompting a shift toward sentence-level semantic watermarks. However, existing sentence-level approaches are highly fragile under structural changes like sentence splitting and merging, which are trivially executed by advanced paraphrasing models.

To address this vulnerability, researchers from the National University of Singapore have proposed AliMark, a robust sentence-level watermarking framework. AliMark shifts the paradigm from prefix-conditioned hashing to global bit-sequence alignment. By restructuring candidate texts at detection time and aligning semantic bit blocks, AliMark secures watermark persistence even when an attacker aggressively rewrites, splits, or merges sentences to evade detection.

Threat Model

Background & Problem Setup

Existing sentence-level watermarking schemes, such as SemStamp (Hou et al., NAACL 2024a), typically employ a prefix-conditioned design. The watermark signal of sentence $x_n$ is pseudo-randomly conditioned on the semantic representation of its preceding context $x_{n-1}$.

While this prevents attackers from discovering the exact watermark pattern, it creates a cascading vulnerability. If an attacker splits or merges a single sentence, the context $x_{n-1}$ changes to $x'_{n-1}$. This destroys the pseudo-random relationship for all subsequent sentences, causing the entire downstream watermark signal to collapse.

Unlike token-level alignment schemes such as those proposed by Kuditipudi et al. (TMLR 2024) which handle token insertions/deletions, sentence-level structural attacks require reasoning over semantic boundaries.

Comparison of LLM Watermarking Paradigms

Methodology

AliMark mitigates structural cascading errors by removing inter-sentence prefix dependencies entirely. Instead, it relies on a global secret bit sequence $s \in \{0, 1\}^\infty$ and reformulates detection as a block-level sequence alignment problem.

       [ WATERMARKED TEXT GENERATION ]
                  Global Secret Bit Sequence s
                 +----+----+----+----+----+----+
                 | b1 | b2 | b3 | b4 | b5 | b6 | ...
                 +----+----+----+----+----+----+
                               |
               Candidate Sentences (Q = 64)
                 +----------------------------+
                 | x_1: Today is very sunny.  | ---> [Embedding] -> φ(e, V) -> Matches block?
                 | x_2: The weather is fine.  |
                 +----------------------------+
                               |
                        Selected Sentence

1. Watermarked Text Generation

During generation, given a context $X_{n-1}$, the LLM generates a candidate set of next sentences $x^*_n$ containing $Q$ variations (with $Q=64$ as default). AliMark's goal is to select a candidate $x^q_n \in x^*_n$ whose semantic bit representation matches the $n$-th block of the secret bit sequence $s(n)$.

1. Semantic Embedding: The sentence embedding $e^q_n$ is extracted using a lightweight sentence encoder (such as all-mpnet-base-v2).
2. Bit Extraction: The embedding is projected against $M$ pre-defined orthonormal secret vectors $V = \{v_1, v_2, \dots, v_M\}$ (with $M=8$). The $m$-th bit of the candidate sentence is calculated as: $$$$

b^q_{(n-1)M+m} \leftarrow \varphi(e^q_n, v_m) = \begin{cases} 0, & \text{if } \langle e^q_n, v_m \rangle < 0 \ 1, & \text{otherwise} \end{cases}

Z(X) = \max_{s^_Y \in S^_Y, Y \in \mathcal{Y}} \left( \frac{\bar{\mu}(M, N') - r}{\bar{\sigma}(M, N')} \right)