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.
Text watermarking has emerged as a crucial technique for identifying AI-generated content. However, current watermarking schemes entail a trade-off between text quality and watermark detectability, which is further intensified by the inherent low-entropy nature of code. To mitigate this dilemma, we propose Grammar-Driven Watermark (GDW), a training-free watermarking approach tailored to LLM-based code generation. GDW employs a three-level masking mechanism consisting of a green-list mask, a syntactic validity mask, and a structural role mask to regulate watermark injection. These masks are integrated through hierarchical modulation, which limits the scope of watermark injection to syntactically admissible green-list tokens and adjusts watermark strength based on structural roles through a role function. Accordingly, we design a role-aware weighted detection statistic. For comprehensive evaluation, we introduce the Area Under the Trade-off Curve (AUTC), a metric that quantifies the quality-detectability trade-off. Extensive experiments demonstrate that GDW outperforms existing baselines and achieves state-of-the-art (SOTA) trade-off performance, while maintaining superior performance under seven semantics-preserving attacks.
As watermarking of LLM-generated text enters deployment, users increasingly need to check text whose source is unknown. Existing detectors read the watermark through a specific tokenizer or embedding pipeline, and even if all providers adopted the same watermarking method, differences in these representations would leave their watermarks incompatible, and the text alone does not reveal which representation produced it. We propose ByteMark, a unified watermarking scheme that defines its signal on the UTF-8 bytes of published text. Models with different tokenizers embed this signal under one public specification and key, and a single detector verifies the text from the text and key alone. When the tokenizer or embedding model of a baseline detector is replaced, its detection degrades sharply, whereas ByteMark, which uses neither, retains its detection rate; ByteMark also remains detectable when participating models continue or rewrite the text.
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, Olivera Kotevska +1
University of Nevada, Reno · Oak Ridge National Laboratory