XMark: Reliable Multi-Bit Watermarking for LLM-Generated Texts

1. Problem Statement

Large Language Models (LLMs) are increasingly used to generate text, raising concerns about malicious usage (e.g., fake news, phishing). While zero-bit watermarking (detecting if text is AI-generated) exists, it lacks the capacity to convey specific metadata (e.g., user IDs, timestamps). Multi-bit watermarking addresses this by embedding binary messages into text.

However, existing multi-bit methods face three critical limitations:

1. Computational Infeasibility: Some methods require brute-force enumeration of all possible messages for decoding, which becomes impossible for long messages.
2. Quality vs. Accuracy Trade-off: Methods that ensure high decoding accuracy often severely distort the text (high perplexity), while methods preserving text quality suffer from poor decoding accuracy.
3. Limited Token Sensitivity: Existing methods rely on a large number of generated tokens to reliably decode the message. In practical scenarios where text length is short, decoding accuracy drops significantly.

2. Methodology: XMARK

The authors propose XMARK, a novel framework that improves both text quality and decoding accuracy, particularly under limited-token conditions. It introduces three core innovations:

A. Leave-one-Shard-out (LOSO) Encoding

Traditional methods (like MPAC) select a single "green list" shard corresponding to the message block and boost its logits. This results in a small green list ratio ($\gamma = 2^{-d}$), causing high distortion.

• XMARK's Approach: Instead of boosting the shard corresponding to the message, XMARK boosts all shards except the one corresponding to the message.
• Mechanism: For a message block value $p$, the green list is $G = V' \setminus S_p$.
• Benefit: This increases the green list ratio to $\gamma = 1 - 2^{-d}$ (e.g., 0.75 for $d=2$), significantly reducing distortion and preserving text quality (lower Perplexity).
• Decoding Logic: The decoder identifies the message by finding the shard with the fewest token counts (the unboosted one), rather than the most.

B. Evergreen List via Multiple Permutations

To counter the reduced signal strength caused by the larger green list (which makes the "unboosted" shard harder to distinguish), XMARK utilizes multiple hash keys.

• Mechanism: The encoder uses $k$ distinct hash keys to generate $k$ different vocabulary permutations. For each permutation, a green list is created using the LOSO strategy.
• Evergreen List ($E$): The final set of boosted tokens is the intersection of all $k$ green lists ($E = \bigcap G_j$).
• Theorem: The expected size of the evergreen list is $E[|E|] \approx (1 - 2^{-d})^k |V|$.
• Benefit: While increasing $k$ slightly reduces the green list ratio (and thus text quality), it significantly strengthens the watermark signal, improving decoding reliability.

C. Constrained Token-Shard Mapping Matrix (cTMM)

Existing decoders use a standard Token-Shard Mapping Matrix (TMM) which can lead to over-counting errors when multiple permutations are involved.

• Problem: In standard TMM, a single token might be counted multiple times toward the same unboosted shard if it appears in the "non-green" regions of multiple permutations, obscuring the distinction between boosted and unboosted shards.
• XMARK's Solution: The cTMM imposes a constraint where each token contributes at most once to the count of any specific shard within a message block row.
• Benefit: This prevents the "unboosted" shard (the true message) from being artificially inflated by noise, allowing for accurate decoding even with a limited number of tokens ($T$).

3. Key Contributions

1. LOSO Paradigm: A novel encoding strategy that reverses the standard green-list selection to maximize text quality while maintaining a detectable signal.
2. Evergreen List: A robust intersection-based boosting mechanism that leverages multiple hash keys to amplify the watermark signal without requiring brute-force decoding.
3. cTMM Decoder: A constrained counting mechanism that resolves ambiguity in token-shard mapping, enabling high accuracy with short text sequences.
4. Computational Efficiency: Unlike methods requiring candidate enumeration, XMARK supports linear-time decoding regardless of message length.

4. Experimental Results

The authors evaluated XMARK on diverse tasks (Text Completion, Story Generation, Text Summarization, Machine Translation) using LLaMA-2 models.

• Decoding Accuracy (Bit Accuracy - BA):
  • XMARK consistently outperforms state-of-the-art baselines (MPAC, CycleShift, DepthW, StealthInk).
  • On Text Completion ($T=150$), XMARK achieved 98.75% BA, compared to 95.25% for CycleShift and 94.00% for MPAC.
  • It maintains high accuracy even with longer messages ($b=32$) and shorter text lengths where other methods fail.
• Text Quality (Perplexity - PPL):
  • XMARK preserves text quality significantly better than MPAC.
  • On Text Completion, XMARK achieved a PPL of 4.61, comparable to StealthInk (4.13) but with much higher accuracy (StealthInk: 85.00% BA).
• Robustness:
  • XMARK demonstrated superior robustness against Copy-Paste and Paraphrase attacks compared to other methods.
• Efficiency:
  • Decoding time is negligible (~0.08s), comparable to the fastest baseline (MPAC), and significantly faster than methods requiring enumeration (DepthW: 16.16s).

5. Significance

XMARK represents a significant advancement in LLM watermarking by solving the "trilemma" of decoding accuracy, text quality, and robustness to short text.

• Practical Applicability: By enabling reliable decoding with limited tokens, it makes watermarking viable for real-world applications where users may only generate short responses.
• Scalability: It supports longer messages without computational explosion, facilitating the embedding of complex metadata (e.g., full user profiles).
• Security: It provides a reliable mechanism for tracing malicious AI usage and attributing content to specific accounts, addressing critical ethical and security concerns in the era of generative AI.

The code is open-sourced at: https://github.com/JiiahaoXU/XMark.