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 .