🤖 AI

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

AliMark is a robust sentence-level watermarking framework that reformulates detection as a bit sequence alignment problem and employs a two-stage strategy with adaptive restructured text variants to effectively withstand structural perturbations like sentence splitting and merging.

Original authors: Yuexin Li, Wenjie Qu, Linyu Wu, Yulin Chen, Yufei He, Tri Cao, Bryan Hooi, Jiaheng Zhang

Published 2026-05-29

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Yuexin Li, Wenjie Qu, Linyu Wu, Yulin Chen, Yufei He, Tri Cao, Bryan Hooi, Jiaheng Zhang

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

The Problem: The "Secret Handshake" That Breaks

Imagine you are trying to prove that a story was written by a specific AI. To do this, you give the AI a secret handshake (a watermark) that it must perform while writing.

Old Method (Token Level): The AI changes the color of individual words (like making "the" blue and "cat" red). If a human or another AI rewrites the story and swaps "cat" for "feline," the blue and red pattern breaks, and the secret handshake is lost.
Better Method (Sentence Level): Instead of coloring words, the AI makes the meaning of each sentence follow a secret pattern. For example, Sentence 1 must be "happy," Sentence 2 must be "sad," and Sentence 3 must be "angry." This is harder to break because you can change the words ("feline" instead of "cat") but the meaning (the emotion) stays the same.

The New Problem:
The paper argues that even this "sentence-level" method has a fatal flaw. It relies on a chain reaction.

The Flaw: The "secret handshake" for Sentence 2 depends on Sentence 1. The handshake for Sentence 3 depends on Sentence 2.
The Attack: Advanced AI paraphrasers (like DIPPER or GPT-3.5) are like clumsy editors. They don't just swap words; they merge two sentences into one or split one sentence into two.
The Result: If Sentence 1 and 2 get merged into a single "Super-Sentence," the chain breaks. The "Super-Sentence" doesn't know how to shake hands with Sentence 3 anymore. One small edit causes the entire secret code to collapse, making the watermark undetectable.

The Solution: AliMark (The "Puzzle Piece" Approach)

The authors propose AliMark, a new way to hide the secret code that doesn't rely on a fragile chain.

1. The Secret is a Long String of Beads (Bit Sequence)
Instead of Sentence 2 needing to know about Sentence 1, AliMark gives the AI a long, secret string of beads (a sequence of 0s and 1s).

Sentence 1 must match the first few beads.
Sentence 2 must match the next few beads.
Sentence 3 must match the next few.
Crucial Difference: Sentence 2 doesn't care what Sentence 1 did. It only cares about matching its own specific spot in the long string.

2. The Detective's Toolkit: The "Re-Structurer"
When a detective tries to find the watermark in a rewritten text, they know the "clumsy editor" might have merged or split sentences. So, AliMark uses a Re-Structurer.

The Analogy: Imagine you have a puzzle that someone messed up by gluing two pieces together or tearing one piece in half.
The Action: The Re-Structurer tries every reasonable way to fix the puzzle. It tries gluing sentences back together and splitting them apart again, creating many different "versions" of the text.

3. The "Adaptive Matcher"
Once the detective has these different versions, they try to line up the secret bead string against each version.

They use a special ruler called Block Edit Rate. This ruler is smart enough to say, "Oh, this sentence was split in two, so I'll count it as two beads," or "These two sentences were glued together, so I'll count them as one block."
The system looks for the version where the beads line up the best. If even one version of the text matches the secret string well, the watermark is found.

Why It Works (The Results)

The paper tested this against the "clumsy editors" (strong paraphrasers like GPT-3.5 and DIPPER).

Old Methods: When the text was merged or split, the detection rate dropped to almost zero (like trying to find a needle in a haystack that was set on fire).
AliMark: Even when the text was heavily rewritten, merged, or split, AliMark could still find the secret beads in the "re-structured" versions. It maintained high detection rates because it didn't rely on a fragile chain; it just looked for the right pattern in the right place, regardless of how the sentences were arranged.

Summary

AliMark is like a detective who knows that a criminal might rearrange the furniture in a room to hide a clue. Instead of looking for the clue in one specific spot (which might be moved), the detective tries moving the furniture back to its original positions in their mind, then looks for the clue. Because the clue is a standalone pattern (not dependent on what's next to it), the detective can find it no matter how the room was messed up.

Technical Summary: AliMark

Problem Statement
Existing sentence-level watermarking methods for Large Language Models (LLMs), such as SemStamp, aim to enhance robustness against paraphrasing by anchoring watermarks in sentence semantics rather than token-level patterns. However, these methods typically rely on a prefix-based design, where the watermark signal of a sentence is conditioned on its preceding context (e.g., the immediately preceding sentence).

The paper identifies a critical vulnerability in this design: structural perturbations. Advanced paraphrasing models (e.g., DIPPER, GPT-3.5) frequently alter text structure by splitting or merging sentences. When a sentence is split or merged, the context for subsequent sentences changes. Because the watermark signal is pseudorandomly conditioned on this specific context, any alteration to the context breaks the pseudorandom relationship required for detection. Consequently, a single structural change can cascade, causing the loss of watermark signals across multiple subsequent sentences, rendering existing frameworks fragile under strong paraphrasing attacks.

Methodology: AliMark
To address this, the authors propose AliMark, a framework that reformulates sentence-level watermarking as a bit sequence encoding and alignment problem between a potentially watermarked text and a secret bit sequence, rather than relying on inter-sentence dependencies.

The framework operates in two main stages:

Watermarked Text Generation (Embedding):
- Instead of conditioning on prefix context, AliMark uses a global secret bit sequence $s$ as the watermark key.
- This sequence is partitioned into blocks of size $M$ , where each block corresponds to the bit signals embedded in a single sentence.
- During generation, the LLM produces $Q$ candidate sentences for the next position.
- A Bit Signals Extractor (using a sentence embedder and secret vectors) converts each candidate's semantic embedding into a discrete bit sequence.
- The system selects the candidate whose extracted bit sequence matches the corresponding block of the secret bit sequence. This ensures the entire text encodes a sequential bit pattern independent of sentence boundaries.
Watermarked Text Detection:
To handle structural perturbations (splits, merges, insertions, deletions) introduced by paraphrasing, AliMark employs a two-stage detection strategy:
- Re-Structurer (RS): This module operates at the text level to recover potential original structures. It generates multiple text variants by performing single-step re-merging (combining two consecutive sentences) and re-splitting (dividing a sentence into two) operations. This creates a candidate set of restructured texts.
- Adaptive Bit Sequence Alignment (ABSA): This module operates at the bit level. For each restructured candidate, it extracts the bit sequence and aligns it against a set of secret bit sequence candidates of varying lengths (to account for sentence count changes).
- Alignment Metric: The authors introduce the Block Edit Rate (BER), an adaptation of the Levenshtein Distance tailored for sentence-level scenarios. Unlike standard edit distance, BER treats the insertion/deletion of a sentence (a block of $M$ bits) as a single operation with a fixed cost, while substitution costs are based on Hamming distance between bit blocks.
- Scoring: The system calculates a $z$ -score for each alignment attempt. The final watermark score is the maximum $z$ -score obtained across all restructured variants and all secret sequence length candidates.

Key Contributions

Identification of Structural Vulnerability: The paper demonstrates that structural perturbations (sentence splitting and merging) are common in automated paraphrasing and catastrophically degrade the performance of prefix-based sentence-level watermarking methods.
Novel Formulation: AliMark proposes a new formulation of sentence-level watermarking as a global bit sequence encoding and alignment task, decoupling watermark signals from specific sentence contexts.
Robust Detection Mechanism: The integration of a Re-Structurer and Adaptive Bit Sequence Alignment allows the system to recover watermark signals even when the text structure has been significantly altered.
Empirical Validation: Extensive experiments show that AliMark substantially outperforms state-of-the-art baselines (including SemStamp, k-SemStamp, and token-level methods like KGW) under diverse paraphrasing attacks, particularly against strong models like DIPPER and GPT-3.5.

Experimental Results

Performance: On datasets like Booksum and C4, AliMark maintains high True Positive Rates (TPR) under strong paraphrasing attacks where baselines fail. For instance, using OPT-1.3B, AliMark achieves a TPR@5% of 61.6% under DIPPER and 66.6% under GPT-3.5, whereas the best baseline (SemStamp) drops to 26.7% and 22.0% respectively.
Adversarial Robustness: In probing experiments involving random sentence insertion, deletion, and reordering, AliMark consistently outperforms baselines, maintaining detectability even at perturbation rates of 0.4–0.5.
Text Quality: Perplexity analysis indicates that AliMark introduces negligible degradation to text quality compared to unwatermarked outputs, with only slight increases observed as the block size $M$ increases.
Efficiency: While the detection process involves generating multiple candidates, engineering optimizations (such as consolidating dynamic programming table computations) keep the runtime manageable, scaling linearly with the number of input sentences.

Significance and Claims
The paper claims that AliMark provides a necessary evolution in LLM watermarking by addressing the specific fragility of semantic-based methods to structural changes. By shifting from context-dependent prefix hashing to global sequence alignment, AliMark offers a robust defense against the sophisticated rewriting capabilities of modern LLMs. The authors position this work as a critical step toward ensuring content provenance and academic integrity in an era where automated writing and paraphrasing are prevalent. They acknowledge limitations, specifically that the current Re-Structurer uses a single-step approach and may not handle complex multi-step structural changes perfectly, suggesting future work could involve more sophisticated restructuring heuristics or custom-trained models.

The Problem: The "Secret Handshake" That Breaks

The Solution: AliMark (The "Puzzle Piece" Approach)

Why It Works (The Results)

Summary

Technical Summary: AliMark

More like this