RMCW: A Deletion-Robust Watermark Based on Reed--Muller Codes for Language Models

• Deletion-induced synchronization loss occurs when removed tokens shift later observed symbols away from their original watermark positions.This can arise when generated text is shortened, cropped, or only partially reproduced.Source: §1 · p. 1
• RMCW replaces global codeword recovery with local structure testing, using Reed–Solomon consistency on affine-line restrictions of Reed–Muller codewords.A secret-keyed vocabulary partition maps tokens to bins, and detection searches candidate text for low-degree local consistency.Source: §1 · pp. 1–2
• 99.8% TPR@1%FPR on unmodified text, 98.1% under burst deletion, and 86.6% under synonym substitution; RMCW improves upon or matches baselines across several attacks.Source: §1 · p. 2
• The paper analyzes local consistency tests theoretically and evaluates RMCW across multiple models, datasets, and post-processing attacks.Source: §1 · p. 2

• KGW partitions vocabulary into green and red token sets, biases generation toward green tokens, and detects the watermark by testing their fraction (Kirchenbauer et al., 2023).Source: §2 · p. 2
• Follow-up statistical-watermark methods study fixed vocabulary partitions (Zhao et al., 2024), low-entropy detection (Lu et al., 2024; Lee et al., 2024), and stability under semantic-preserving edits (Liu et al., 2024a).Another line designs distribution-preserving or distortion-free keyed watermarking (Christ et al., 2024; Kuditipudi et al., 2023).Source: §2 · pp. 2–3
• Coding-based watermarking includes PRC, which uses pseudorandom error-correcting codes for keyed detection after text edits (Christ and Gunn, 2024; Qu et al., 2025).RMCW follows this direction while focusing on deletion robustness.Source: §2 · p. 3
• Reed–Muller codes generalize low-degree polynomial codes to multiple variables, and restricting an RM codeword to an affine line yields a Reed–Solomon codeword.This line structure supports local low-degree consistency testing.Source: §2 · p. 3

3.1 Preliminaries

• Affine-line restrictions of Reed–Muller codewords yield low-degree Reed–Solomon sequences, the local structure RMCW tests; the setup assumes an autoregressive model and 0 ≤ d < m ≤ q.The method defines the RM codeword as evaluations of a degree-bounded bivariate polynomial over a q × q grid.Source: §3.1 · p. 3

3.2 From Global Decoding to Local Detection

• Because deletion shifts surviving symbols out of alignment, zero-bit detection tests for local structure instead of recovering the original codeword.The detector needs evidence that text is watermarked, not reconstruction of the embedded codeword.Source: §3.2 · p. 4

3.3 Watermark Generation

• A keyed vocabulary partition maps tokens to field symbols, while a payload-derived RM grid supplies target symbols whose matching token logits are biased during generation.The keyed bins preserve lexical flexibility while allowing generation to favor a target symbol.Source: §3.3 · pp. 4–5

3.4 Watermark Detection

• The detector adaptively pilots candidate strides, tests shortlisted windows for low-degree RS consistency, and applies a calibrated hypothesis test to decide whether text is watermarked.Berlekamp–Welch decoding with distance verification permits up to e mismatches; detection requires the secret binning key.Source: §3.4 · p. 5

3.5 Theoretical Analysis

• Deleting symbols reduces observable coordinates rather than necessarily removing the watermark structure, since other windows may retain RS consistency even after burst deletions.Berlekamp–Welch uniquely reconstructs the low-degree polynomial in polynomial time when 2e < m − d.Source: §3.5 · pp. 5–6

This is the probability that a uniformly random

• The substitution-robustness theorem gives a direct parameter condition under which the noisy watermarked and null distributions are distinguishable with constant advantage.The supplied condition is 0.99P_wm_acc > P_null.Source: This is the probability that a… · p. 6

4.1 Experimental Setup

• Experiments use OPT-1.3B and Llama-3.1-8B-Instruct on C4 open-ended generation and ELI5 question answering, comparing RMCW with KGW, EXP, and PRC.The attack evaluation includes random deletion, burst deletion, truncation, emoji attack, synonym substitution, and DIPPER paraphrasing.Source: §4.1 · pp. 6–7

4.2 Main Results

• RMCW leads all three averaged metrics across clean text and six attacks: 82.5% TPR@1%FPR, 84.3% TPR@5%FPR, and 91.9% AUROC.These averages exceed the strongest baseline averages by 14.9, 13.2, and 11.0 percentage points, respectively.Source: §4.2 · p. 7
• Under structured deletion, RMCW reaches 98.1% TPR@1%FPR for burst deletion and 98.9% for truncation, versus PRC’s 45.9% and 39.7%.For random deletion, RMCW records 90.0% TPR@1%FPR, below KGW; for emoji attack, it reaches 95.5%, versus at most 1.9% for baselines.Source: §4.2 · p. 7
• Under synonym substitution, RMCW reaches 86.6% TPR@1%FPR versus the strongest baseline’s 69.5%, but strong paraphrasing remains challenging.For paraphrasing, RMCW has the highest AUROC at 53.7%, but its TPR@1%FPR is 8.3%.Source: §4.2 · p. 7

4.3.1 Cross Model and Dataset Generalization

• Across C4 and ELI5, Llama-3.1-8B-Instruct retains 98.1% and 95.5% TPR@1%FPR under burst deletion, and 86.6% and 90.8% under synonym substitution.On OPT-1.3B, the corresponding burst-deletion and synonym-substitution results are 83.6% and 81.4% on C4, and 87.6% and 85.7% on ELI5.Source: §4.3.1 · pp. 7–8, Table 3 · p. 8

4.3.2 Effect of Generation Length

• As the generation cap rises from 100 to 500 tokens, RMCW’s AUROC increases from 77.5% to nearly 98.0%, while TPR@1%FPR rises from 55.5% to nearly 99.8%.Longer outputs provide more induced symbols and candidate windows for accumulating local Reed–Solomon evidence.Source: Figure 2 · p. 8, §4.3.2 · p. 8

5 Conclusion

• RMCW embeds Reed–Muller-structured symbols and detects surviving Reed–Solomon consistency, targeting local evidence when attacks disrupt global token positions.The conclusion presents local algebraic consistency as a promising design for robust LLM watermarking.Source: §5 · p. 8
• Experiments across models and datasets show strong clean-text detectability and robustness under deletion and rewriting attacks.Source: §5 · p. 8

Limitations

• RMCW is designed for deletion-oriented processing, not universal robustness; strong document-level paraphrasing can leave little directly surviving watermark evidence.Independently distributed random deletion is more challenging than burst deletion or truncation because it changes synchronization throughout the sequence.Source: Limitations · pp. 8–9
• Short generations or heavily shortened fragments may lack enough symbols for reliable detection at low false-positive rates.The authors identify more sample-efficient local tests or aggregation across passages as directions for improving short-text detection.Source: Limitations · p. 9
• The approximate detection score relies on offline null-rate estimates; changes in model, tokenizer, vocabulary, domain, length, or parameters may require recalibration.Practical deployment would require validation on the target data distribution.Source: Limitations · p. 9

A LLM Usage Statement

• The authors used LLMs as writing and coding assistants, while stating that they developed and verified the core ideas, methods, experiments, implementation, and analysis.Source: A LLM Usage Statement · p. 11

B.1 Soundness of Berlekamp–Welch verification

• The soundness argument treats acceptance as lying within Hamming distance e of an RS codeword; distinct codewords have disjoint error balls.Source: §B.1 · p. 11

B.2 Proof of Theorem 1

• Under the noisy watermark distribution, Berlekamp–Welch decoding succeeds when substitutions do not exceed e; the proof compares this with null-distribution acceptance.The two distributions are distinguishable when watermark acceptance exceeds null acceptance by a constant factor.Source: §B.2 · p. 12

C.1 Datasets

• C4 RealNews tests open-ended news-style continuation, while ELI5 tests long-form answers to information-seeking questions.The evaluation uses 5,000 C4 validation samples and 1,000 ELI5 samples, with human continuations as negative examples.Source: §C.1 · p. 12

C.2 Models

• OPT-1.3B and Llama-3.1-8B-Instruct differ in scale, architecture family, and tokenizer design, providing distinct model distributions for transfer evaluation.Within each condition, methods share the base model, tokenizer, prompts, generation length, and attack configurations.Source: §C.2 · p. 12

C.3 Metrics

• Detection evaluation reports TPR at 1% and 5% FPR and AUROC, with higher values indicating better performance.The positive set consists of watermarked generations, optionally attacked; the negative set consists of corresponding human continuations.Source: §C.3 · p. 13

C.4.1 Baseline Methods

• Comparisons include KGW, EXP, and PRC; within each condition, methods share the prompt split, model, tokenizer, generation length, attack configuration, and metric computation.Low-FPR operating points use the same procedure for every method.Source: §C.4.1 · p. 13
• KGW biases sampling toward a secret-keyed green list and detects watermark evidence by scoring how many observed tokens fall in their reconstructed green lists.The configuration uses γ = 0.5, δ = 2.0, and prefix_length=1; the fixed decision threshold is z = 4.0.Source: §C.4.1 · p. 13
• EXP uses a keyed pseudorandom vector and model probabilities for exponential sampling, then scores observed tokens using a statistic tested against a Gamma null distribution.The configuration uses prefix_length=4 and a fixed threshold p = 10−4.Source: §C.4.1 · p. 13
• PRC encodes keyed pseudorandom bits with a small linear error-correcting code to perturb next-token probabilities, then tests token-window bits against expected encoded bits.The implementation uses an LDPC-style code; detection applies a one-sided binomial test with null match probability 1/2.Source: §C.4.1 · pp. 13–14

C.4.2 RMCW Implementation

• RMCW generation uses a bivariate Reed–Muller construction over F17 with q = 17, degree bound d = 3, window length m = 12, and logit bias δ = 5.0.Source: §C.4.2 · p. 14
• Detection maps tokenized text to keyed bin symbols and tests sampled local windows for degree-at-most-d polynomial consistency, allowing up to two symbol errors per length-12 window.The Berlekamp–Welch-style test uses rs_errors=2.Source: §C.4.2 · p. 14
• Adaptive detection runs 500 pilot trials, retains at most 8 candidate strides, and adjusts the best stride-specific binomial-tail score for the number of tested strides.Offline-calibrated stride-specific null rates make pdet an approximate detection score rather than an exact calibrated p-value.Source: §C.4.2 · p. 14

C.4.3 Computational Resources

• Experiments ran on Ubuntu 20.04.6 LTS with two AMD EPYC 7H12 processors, 503 GiB of memory, and one NVIDIA A40 GPU with 46 GB memory.Source: §C.4.3 · p. 14

C.5 Attacks

• Random deletion independently removes whitespace-separated words at r = 0.2, while burst deletion removes paragraph- or sentence-level units at r = 0.5.Source: §C.5 · p. 14
• Truncation retains a randomly selected contiguous span at r = 0.5, whereas the clean setting applies the detector directly to the original continuation.Source: §C.5 · p. 14
• The emoji attack inserts an emoji after every word at r = 1.0, changing tokenization while preserving visible lexical content; it is grouped with deletion attacks because it shifts later token positions.Source: §C.5 · p. 14
• Synonym substitution replaces up to half the words with WordNet synonym lemmas, while paraphrasing uses the MarkLLM document-level editor with its DIPPER-based paraphraser.Source: §C.5 · pp. 14–15
• Table 4 reports TPR@1%FPR for RMCW detector ablations on C4 with Llama-3.1-8B-Instruct; Table 5 reports MBPP results for Llama-3.1-8B-Instruct.Table 4’s parenthetical values denote attack rates; Table 5 reports percentages and states that higher values are better.Source: Table 4 · p. 15, Table 5 · p. 15

D.1 Ablation Study

• The full detector is best or tied-best in four of five settings, improving TPR by 2.3 points under synonym substitution and 9.4 points under emoji insertion versus fixed-contiguous windows.The larger emoji gain is associated with searching multiple strides when post-processing disrupts local symbol spacing.Source: §D.1 · p. 15
• Both full and fixed-contiguous detectors reach 98.1% TPR under burst deletion, while fixed-contiguous windows perform 2.6 points better under random deletion.The passage relates burst-deletion performance to surviving unchanged spans that preserve stride-1 local structure.Source: §D.1 · p. 15
• Exact consistency reduces clean-text TPR from 99.8% to 94.1% and lowers TPR versus the full detector by 60.3 points under random deletion, 60.8 under synonym substitution, 23.8 under burst deletion, and 69.3 under emoji insertion.The passages attribute the clean-text decrease to logit bias encouraging, but not forcing, tokens into their target vocabulary bins.Source: §D.1 · p. 15
• Bounded-error Berlekamp–Welch testing addresses mismatches from generation and editing, whereas adaptive multi-stride search provides additional robustness that depends on the attack pattern.Source: §D.1 · pp. 15–16
• Table 6 reports RMCW TPR@1%FPR on C4 with Llama-3.1-8B-Instruct across attack rates, with the best result at each rate shown in bold.Rates indicate removed content for deletion and truncation, emoji insertion probability, or maximum word-replacement fraction for synonym substitution.Source: Table 6 · p. 16

Dataset and evaluation setup

• The evaluation uses 974 MBPP Python tasks, reporting Pass@1 alongside AUROC, TPR@1%FPR, and TPR@5%FPR.MBPP is used with Llama-3.1-8B-Instruct to assess transfer to code generation.Source: §D.2 · p. 16

Code-generation utility

• RMCW achieves 34.5% Pass@1, 12.2 points below the unwatermarked model and within 2.1 points of the strongest watermarked result, EXP at 36.6%.PRC achieves 13.3% Pass@1.Source: §D.2 · p. 16

Watermark detectability

• 37.2% TPR at 1% FPR gives RMCW the highest rate, slightly exceeding EXP at 37.0%; at 5% FPR, RMCW reaches 74.6% TPR.RMCW's overall AUROC is 87.2%, below EXP's 90.7%.Source: §D.2 · p. 16

D.3 Deletion Rate

• Burst deletion keeps TPR@1%FPR above 98% across evaluated rates; random deletion yields 90.0% at 20%, while 50% synonym replacement retains 86.6%.At 50% burst deletion, TPR is 98.1%; truncation declines from 99.8% to 98.9%, and emoji-attack TPR remains above 96%.Source: §D.3 · pp. 16–17

D.4 Watermarking Efficiency

• RMCW generates at 16.4 tokens per second, second-highest, and detects in 0.57 seconds per text, below one second but slower than EXP and PRC.Its generation throughput is 9.3% higher than EXP; detection latency is 40% lower than KGW's 0.95 seconds.Source: Table 7 · p. 17, §D.4 · p. 17

E Case Study

• Four case studies compare model continuations across three C4 prompts and examine six attacks applied to one clean RMCW continuation.The continuation comparisons use Llama-3.1-8B-Instruct with the same generation configuration.Source: E Case Study · p. 17

Case Analysis

• Across three prompts, RMCW preserves local voice, completes an unfinished contrast, and continues a reflective argument, while alternatives show repetition, generic framing, or grammatical problems.The examples cover a community complaint, an expository discussion, and a reflective essay.Source: Case Analysis · pp. 18–19

Clean RMCW Output

• Attack effects differ by operation: random deletion spreads positional shifts, emoji insertion disrupts tokenization, and synonym replacement changes keyed vocabulary-bin assignments.Emoji insertion can preserve visible words while substantially changing tokenization; synonym replacements may also introduce grammatical artifacts.Source: Clean RMCW Output · pp. 19–20

E.4 Case 4: Effects of Different Post-Processing Attacks

• The controlled attack case contrasts structured deletion, which preserves ordered spans, with DIPPER paraphrasing, which rewrites wording and may leave few local symbol sequences.The paraphrase remains fluent and broadly on topic but can introduce semantic drift and factual artifacts.Source: Clean RMCW Output · pp. 19–20, Case Analysis · p. 20