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

arXiv: https://arxiv.org/abs/2610.02817 · HTML: https://mlsanity.com/paper/2610.02817/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Watermarking generated content and models, one of 12 directions in LLM safety and security.
- Builds on 13 of its 26 references that are in the map.
- First posted on arXiv 2 Oct 2026.

## Placed in

- LLM safety and security / [Watermarking generated content and models](https://mlsanity.com/safety/watermarking-generated-content-and-models/)

## Builds on (most cited first, 13 of 13)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [ELI5: Long Form Question Answering](https://mlsanity.com/paper/1907.09190/) (2019)
- [Paraphrasing evades detectors of AI-generated text, but retrieval is an effective defense](https://mlsanity.com/paper/2303.13408/) (2023)
- [Robust Distortion-free Watermarks for Language Models](https://mlsanity.com/paper/2307.15593/) (2023)
- [Provable Robust Watermarking for AI-Generated Text](https://mlsanity.com/paper/2306.17439/) (2023)
- [Who Wrote this Code? Watermarking for Code Generation](https://mlsanity.com/paper/2305.15060/) (2023)
- [An Entropy-based Text Watermarking Detection Method](https://mlsanity.com/paper/2403.13485/) (2024)
- [Provably Robust Multi-bit Watermarking for AI-generated Text](https://mlsanity.com/paper/2401.16820/) (2024)
- [CREBench: Evaluating Large Language Models in Cryptographic Binary Reverse Engineering](https://mlsanity.com/paper/2604.03750/) (2026)
- [SSG: Logit-Balanced Vocabulary Partitioning for LLM Watermarking](https://mlsanity.com/paper/2604.22438/) (2026)

## Abstract (arXiv)

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.