Attributing short LLM-generated texts to a specific source remains challenging for existing multi-bit watermarking methods, which often require long generations or costly decoding to recover payloads reliably. We propose a codebook-based watermarking scheme that maps an n-bit payload to a longer u-bit codeword and embeds it during generation through token-level logit biasing. During extraction, the received bit sequence is matched to the nearest codeword in a precomputed secret codebook using Hamming or Levenshtein distance. Experiments show that our method achieves near-perfect recovery for 16-24 bit payloads on 200-token generations and strong performance on 127-token generations for base models. Results are weaker on some instruction-tuned models with very short texts, where low-entropy output distributions reduce embedding reliability. We also study a BCH-based variant that avoids codebook storage but generally reduces robustness. The Levenshtein variant improves resilience to deletions and light paraphrasing, while insertions and stronger rewrites remain challenging. We analyze collision probability, codeword separation, extraction time, tokenization consistency, and text quality, highlighting both the practicality and limitations of codebook-based watermarking for short-form attribution.
Figures & tables
Method
Match Rate
Limitation
Fernandez et al. [ 7 ]
99.6%
very long or infeasible extraction time
Wang et al. [ 2 ]
98.8%
very long or infeasible extraction time
Yoo et al. [ 5 ]
30.4%
much below 98–100% match rate
Lin et al. [ 8 ]
90.0%
below 98–100% match rate
Qu et al. [ 6 ]
96.0%
below 98-100% match rate
Table I: Comparison of multi-bit watermarking methods on accuracy (match rate). The match rate is the percentage of watermarked texts from which the full hidden message is correctly extracted. Texts were generated with Llama 2 7B and embedded message was 24 bits long.
Fig. 1: Our watermarking scheme. A codebook is pre-generated offline and later used by the embedding and extraction algorithms. The embedding phase embeds a long codeword (e.g., 127 bits) into the generated text. During the extraction, a noisy version of codeword is first obtained and then the closest codeword is searched in the codebook. Once the closest codeword is identified, the corresponding watermark is extracted. The detection decision (watermarked vs. non-watermarked) is based on the distance threshold. A distance is measured by the Hamming or Levenshtein distance.
Watermark size
16
20
24
32
Fernandez et al. [ 7 ]
99.6
99.2
98.0
NA
Wang et al. [ 2 ]
98.8
98.4
97.2
NA
Yoo et al. [ 5 ]
73.6
49.2
30.4
8.4
Cohen et al. [ 11 ]
88.8
78.4
65.6
27.2
Qu et al. [ 6 ]
98.0
97.6
96.0
94.0
Ours (BCH † )
99.1
98.6
97.6
91.1
Table II: Comparison of methods on match rate (%) for different watermark lengths (in bits) on 200 tokens. Evaluated on the OpenGen dataset [ 10 ] . † BCH uses 127 tokens (native BCH codeword length) for 16–24-bit watermarks to maximize the error correction rate; the 32-bit watermark uses 200 tokens with code shortening (see Appendix D ). NA denotes that a method was too computationally expensive for the whole dataset.
Model
Hamming
Levenshtein
BCH
127 tokens
Llama 2 7B
99.3
97.5
98.3
Llama 3.1 8B
100
100
99.7
Llama 3.2 3B
100
100
99.6
Llama 3.2 3B Inst.
90.2
61.6
56.5
Mistral 7B
99.7
99.4
99.4
Table III: Match rate (%) at FPR ≤1% for a 24-bit watermark. Evaluated on Essays-With-Instructions dataset [ 12 ] and HC3 dataset [ 13 ] .
Variant
u=127
u=200
Levenshtein (GPU, Triton)
5.8 ms
75.5 ms
Hamming (CPU, Faiss)
4.1 ms
13.3 ms
BCH (CPU, algebraic)
2.3 ms
3.5 ms
Table IV: Average extraction time per query for n=24 ( ≈16.8 M codebook entries). Hamming and Levenshtein benchmarked on an AMD Epyc 7302 (16C/32T, 3.0 GHz) with a single Nvidia RTX 5090 (32 GB).
Fig. 2: Match rate under attacks, evaluated on generations from Llama 2 7B with the OpenGen dataset [ 10 ] . The attacker’s budget is 10% of a total number of tokens for a given text. Baseline values are estimated from Figure 6 of Qu et al. [ 6 ] .
Appendix figures & tables8 assets
Supplementary material from the paper’s appendix.
Appendix
Fig. 3: ROC curve with reported AUROC. Marked points have 1% False Positive Rate.
u=127
u=200
Native length n0
127
255
Field degree m
7
8
Message capacity k
29
79
Shortening
0
55 bits
Correction capability t
21
27
Correction rate t/u
16.5%
13.5%
Appendix
Table V: BCH parameters for a 24-bit watermark ( n=24 ) at two codeword lengths. At u=127 the code operates at its native length with no shortening, yielding a higher relative error correction rate.
Fig. 4: Nearest-neighbour distance statistics for Linear and RNG codebook construction with codeword length u=127 . Lines show the mean; shaded regions show the min–max range. The Linear method has no visible band under Hamming distance because min = mean = max at every n .
Fig. 5: Same as Figure 4 but for codeword length u=200 .
Fig. 6: Lexical diversity distributions for 200-token Llama 2 7B generations on the OpenGen dataset [ 10 ] .
Fig. 7: Lexical diversity distributions for 200-token Mistral 7B Instruct generations on the SAR Prompts dataset [ 15 ] .
Length
Not WM
Watermarked
Tie
u=127
39.7%
49.0%
11.3%
u=200
43.4%
53.7%
2.9%
Appendix
Table VI: LLM-as-a-Judge pairwise comparison on social authenticity. Generation: Mistral 7B Instruct ; judge: Gemma 4 31B IT . Position randomised per pair.
Fig. 8: Perplexity distribution for 200-token Llama 2 7B generations on the OpenGen dataset. Evaluator: Gemma 4 31B .
With LLM watermarking already being deployed commercially, practical applications increasingly require multibit watermarks that encode more complex payloads, such as user IDs or timestamps, into the generated text. In this work, we propose a fundamentally new approach for multibit watermarking: introducing binomial encoding to directly encode every bit of the payload at every token position. We complement our approach with a stateful encoder that during generation dynamically redirects encoding pressure toward underencoded bits. Our evaluation against 8 baselines on up to 64-bit payloads shows that our scheme achieves superior message accuracy and robustness, with the gap to baseline methods widening in more relevant settings (i.e., large payloads and low-distortion regimes). At the same time, we challenge prior works' evaluation metrics, highlighting their lack of practical insights, and introduce per-bit confidence scoring as a practically relevant metric for evaluating multibit LLM watermarks.
Multi-bit watermarking has emerged as a promising solution for embedding imperceptible binary messages into Large Language Model (LLM)-generated text, enabling reliable attribution and tracing of malicious usage of LLMs. Despite recent progress, existing methods still face key limitations: some become computationally infeasible for large messages, while others suffer from a poor trade-off between text quality and decoding accuracy. Moreover, the decoding accuracy of existing methods drops significantly when the number of tokens in the generated text is limited, a condition that frequently arises in practical usage. To address these challenges, we propose XMark, a novel method for encoding and decoding binary messages in LLM-generated texts. The unique design of XMark's encoder produces a less distorted logit distribution for watermarked token generation, preserving text quality, and also enables its tailored decoder to reliably recover the encoded message with limited tokens. Extensive experiments across diverse downstream tasks show that XMark significantly improves decoding accuracy while preserving the quality of watermarked text, outperforming prior methods. The code is at https://github.com/JiiahaoXU/XMark.
Jiahao Xu, Rui Hu, Olivera Kotevska +1
University of Nevada, Reno · Oak Ridge National Laboratory
The growing deployment of Large Language Models (LLMs) has raised concerns about their misuse in generating harmful or deceptive content. To address this issue, watermarking methods have been proposed to embed identifiable multi-bit messages into generated text for misuse tracing. However, existing methods often suffer from a fundamental trade-off between text quality and decoding accuracy. In particular, they have to restrict the size of the preferred token set (i.e., green list) during encoding to maintain a detectable watermark signal for decoding, which inevitably degrades generation quality. To improve this trade-off, we propose a novel message encoding paradigm called majority bit-aware encoding, which relaxes the watermark signal strength from the green list size. This strategy allows for a strong watermark signal to be preserved in generated texts even when using a large green list. We introduce two instantiations of this paradigm: MajorMark and MajorMark+, where the latter is specifically optimized for long messages. Extensive experiments on state-of-the-art LLMs demonstrate that our methods achieve higher decoding accuracy and superior text quality compared to prior baselines. The code is at https://github.com/JiiahaoXU/MajorMark.
Jiahao Xu, Rui Hu, Zikai Zhang +1
University of Nevada, Reno · Oak Ridge National Laboratory