RMCW: A Deletion-Robust Watermark Based on Reed--Muller Codes for Language Models
Authors: Yi Wang, Baicheng Chen, Yu Wang, Jian Zhao, Yilei Chen, Tianxing He
Organizations: Institute for Interdisciplinary Information Sciences, Tsinghua University · University of Wisconsin–Madison · Shanghai Qi Zhi Institute, 3Xiongan AI Institute · The Chinese University of Hong Kong, Shenzhen · Institute of Information Engineering, Chinese Academy of Sciences
Large Language Model (LLM) watermarking provides a lightweight mechanism for identifying text generated by a specific model, but its robustness remains fragile under post-processing attacks. Deletion attacks are particularly challenging because they shift token positions and break the alignment between observed tokens and their original watermark positions. We propose Reed--Muller Code Watermarking (RMCW), an LLM watermarking method based on Reed--Muller codes. In contrast to global codeword recovery, RMCW searches for surviving local algebraic structure, leveraging the Reed--Solomon consistency induced by affine-line restrictions of Reed--Muller codewords. During generation, RMCW injects a Reed--Muller structure into the sequence via a secret-keyed vocabulary partition. During detection, it maps the given text to keyed vocabulary bins and tests local subsequences for low-degree Reed--Solomon consistency using Berlekamp--Welch tests. Experiments on C4 and ELI5 datasets with OPT-1.3B and Llama-3.1-8B-Instruct show that RMCW preserves strong clean-text detectability and outperforms or matches the baseline methods under several deletion and rewriting attacks. Our code is available at https://github.com/BaichengDanny/RMCW.
Figures & tables
Figure 1: Overview of Reed–Muller Code Watermarking (RMCW). Generation (top): First, a secret-keyed vocabulary partition assigns each vocabulary token to one of q bins, while a bivariate Reed–Muller codeword is sampled as a q×q grid (explained in § 3.3 ). Then, the sampled grid is serialized into a structured sequence of target bin indices. At each decoding step, the language model increases the logits of tokens assigned to the target bin. Detection (bottom): Given candidate text that may have undergone deletion or rewriting, the detector maps each token to its secret-keyed bin label and samples local windows at candidate strides (explained in § 3.4 ). It tests each window for low-degree Reed–Solomon consistency, aggregates evidence across the tested windows, and outputs the watermark detection decision.
Notation
Meaning
q,d,m,e
Field size, degree bound, symbols per window, and tolerated mismatches.
Kbin,bKbin
Secret binning key and token-to-symbol map.
spayload,fpay,Apay
Payload seed, RM polynomial, and flattened target sequence.
A,W(s,τ)
Observed symbols and a window with start s and stride τ .
Xτ,π0,τ,pτ,pdet
Success count, null rate, and approximate detection scores.
Table 1: Core notations.
Method
Metric
Attack Scenarios
Clean
Rand. Del.
Burst Del.
Trunc.
Syn. Sub.
Para.
Emoji
Avg.
KGW
TPR@1%FPR
99.7
98.2
96.4
97.2
69.5
12.2
0.0
67.6
TPR@5%FPR
99.8
99.3
98.9
99.1
85.3
15.3
0.0
71.1
AUROC
99.9
99.8
99.8
99.8
97.3
41.2
28.6
80.9
EXP
TPR@1%FPR
98.9
79.1
93.8
94.6
21.1
10.1
1.9
57.1
TPR@5%FPR
99.5
87.3
97.3
96.8
33.3
15.6
5.6
62.2
Table 2: Main results on C4 with Llama-3.1-8B-Instruct for 500-token generations. We report TPR at 1% and 5% false-positive rates (FPRs) and AUROC, all expressed as percentages, on unmodified text ( Clean ) and under six post-processing attacks. Rand. Del. , Burst Del. , Trunc. , Syn. Sub. , Para. , and Emoji denote random deletion, burst deletion, truncation, synonym substitution, paraphrasing, and emoji attack, respectively. Avg. is the arithmetic mean across the clean setting and all six attack scenarios. Higher values indicate stronger watermark detectability. The best result for each metric under each scenario, including the average, is shown in bold.
Figure 2: Effect of generation length on clean-text watermark detection on C4 with Llama-3.1-8B-Instruct. AUROC (top) and TPR@1%FPR (bottom) are reported for RMCW, KGW, EXP, and PRC as the maximum number of generated tokens increases from 100 to 500.
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
Detector variant
Clean
Rand. Del. (0.2)
Syn. Sub. (0.5)
Burst Del. (0.5)
Emoji (1.0)
Full RMCW
99.8
90.0
86.6
98.1
95.5
Fixed contiguous ( τ=1 )
99.0
92.6
84.3
98.1
86.1
Exact RS consistency ( e=0 )
94.1
29.7
25.8
74.3
26.2
Appendix
Table 4: Ablation of the RMCW detector on C4 with Llama-3.1-8B-Instruct. We report TPR@1%FPR, expressed as percentages. The full detector uses adaptive pilot selection, multiple candidate strides, and Berlekamp–Welch consistency testing with e=2 . The fixed-contiguous variant uses only stride τ=1 , while the exact-RS variant requires zero symbol mismatches. The value in parentheses denotes the attack rate.
Method
WM Pass@1
AUROC
TPR@1%FPR
TPR@5%FPR
KGW
35.7
85.8
12.8
48.6
EXP
36.6
90.7
37.0
63.4
PRC
13.3
79.7
30.1
48.3
RMCW (Ours)
34.5
87.2
37.2
74.6
Appendix
Table 5: Results on the MBPP benchmark with Llama-3.1-8B-Instruct. The non-watermarked model obtains a Pass@1 of 46.7% . All remaining values are percentages, and higher values are better.
Attack
10%
20%
30%
40%
50%
Rand. Del.
98.8
90.0
79.5
64.9
39.1
Burst Del.
99.8
99.6
98.8
99.1
98.1
Trunc.
99.8
99.8
99.8
99.5
98.9
Emoji
98.9
98.2
97.4
97.9
96.7
Syn. Sub.
99.0
98.2
95.1
90.9
86.6
Appendix
Table 6: Detection performance of RMCW under varying attack rates. We report TPR@1%FPR, expressed as percentages, on C4 with Llama-3.1-8B-Instruct. For random deletion, burst deletion, and truncation, the attack rate denotes the fraction of removed content. For emoji attack and synonym substitution, it denotes the emoji insertion probability and maximum word-replacement fraction, respectively. The best result at each attack rate is shown in bold.
Method
Gen. speed (tokens/s) ↑
Detect. time (s/text) ↓
Avg. gen. time (s/sample) ↓
KGW
59.8
0.95
8.2
EXP
15.0
0.26
33.3
PRC
11.1
0.01
42.4
RMCW (Ours)
16.4
0.57
30.5
Appendix
Table 7: Wall-clock efficiency of the evaluated watermarking methods under a maximum generation length of 500 tokens. Generation speed is measured in generated tokens per second, detection time is the average latency per input text, and generation time is the average latency per sample. All methods are measured under the same hardware and runtime configuration. Higher generation speed and lower latency are better.