RMCW：基于 Reed-Muller 码的抗删除 LLM 水印方法

删除会打乱 token 与水印位置的对齐，使按位置绑定的编码水印难以做全局译码。

• 出现场景：作者称 LLM 水印在生成时注入隐藏信号，供检测器判断文本是否由特定带水印模型产生；实用水印还应能从有限文本检出、少损生成质量，并耐受常见后处理。作者称失步常见于文本被缩短、裁剪或只被部分再分发。
• 现有不足：作者称纠错码可在符号损坏后保留可检信号，但信号若绑在生成位置上，删除会移走 token 并平移其后符号，造成同步丢失；全局码字恢复所依赖的位置对齐因此不再成立。
• 核心观察：作者认为零比特检测不必恢复原码字，只需判断文本是否来自带水印分布。Reed–Muller 码在任意仿射线上的限制是次数至多 d 的 Reed–Solomon 码字，所以可以局部检验。
• 本文做法：提出 RMCW：生成时用密钥词表分箱注入 RM 结构，检测时用 Berlekamp–Welch 检验局部低次 RS 一致性，并做假设检验。
• 威胁模型：
  • 对手：可在文本到达检测器前，对带水印 LLM 的输出做文本编辑。论文未写对手是否掌握密钥。
  • 检测目标：判定水印是否存在；论文举例为模型提供方。
  • 看不到的信息：原文、原始位置，以及存活 token 与 RM 坐标的对应。
  • 检测要用的秘密：分箱键 Kbin。Algorithm 2 的输入不含 payload seed。

按引言与 Related Work 的分组转述。

统计水印

• KGW（Kirchenbauer et al., 2023）：每步用上下文与密钥把词表分成 green/red，解码偏向 green，再用 green token 比例检测。
• 后续改动：固定词表划分（Zhao et al., 2024）；改善低熵区域检测（Lu et al., 2024; Lee et al., 2024）；使信号在语义保持编辑下更稳（Liu et al., 2024a）。论文此处只描述做法。
• 目标文献：Liu et al.（2024b）与 Liang et al.（2026）被引为在保持文本质量的同时识别机器生成文本。

分布保持水印

• Christ et al.（2024）、Kuditipudi et al.（2023）：带水印采样器被设计成更好保持原模型分布，同时仍支持密钥检测。

编码水印

• PRC（Christ and Gunn, 2024）：用伪随机纠错码，使无密钥时带水印文本难与普通文本区分；有密钥的检测器在文本编辑后仍可识别。
• Qu et al.（2025）：可证明鲁棒的多比特文本水印。作者称本文沿这一编码方向，但关注删除攻击下的鲁棒性。

代数码

• Reed–Solomon（Reed and Solomon, 1960）：在有限域上对低次一元多项式求值。Berlekamp–Welch（Welch and Berlekamp, 1986）做有界纠错；Guruswami–Sudan（1998）做列表译码。
• Reed–Muller（Reed, 1954）：把低次多项式推广到多元。作者称其供检测使用的性质是：码字限制到任意仿射线后成为 RS 码字。

基线与数据

• 基线：KGW、EXP（Aaronson and Kirchner, 2022）、PRC。作者称 KGW 是 token 级 green-list 水印，EXP 是基于采样的水印，PRC 是最接近的 ECC 基线。
• 数据：开放式续写用 C4 的 RealNews 子集（Raffel et al., 2020）；长问答用 ELI5（Fan et al., 2019）；代码生成用 MBPP（Austin et al., 2021）。

作者把与位置对齐编码水印的区别写成：不恢复整段码字，改为寻找删除后仍幸存的局部代数结构。

RMCW 在自回归解码时把 Reed–Muller 结构写进密钥分箱序列；检测不恢复码字，只搜索仍满足低次 Reed–Solomon 一致性的局部窗口（Figure 1，Algorithm 1–2）。

问题设定

• 任务：零比特水印。检测器判断可疑文本是否来自带水印分布，不恢复嵌入消息。
• 代数对象：Fq 为素数阶有限域，运算可看成模 q。次数界 d 与窗口长 m 满足 0≤d<m≤q。二元、总次数至多 d 的多项式在全体域元素上取值，得到 q×q 的 RM 网格。
• 仿射限制：从点 a 沿非零方向 b，随 t 走出一条仿射线；限制后的一元多项式次数仍至多 d，沿该线读出的符号因此是 RS 码字。
• 为何改检测：删除后观测序列不完整且相对原水印位置错位。作者把困难从“符号缺失”扩到“剩余符号不再同步”。

生成

• 分箱：b(v)=HMAC(Kbin, v) mod q，把词表分成 q 箱。HMAC 只当作带密钥伪随机函数。分箱依赖 token 与密钥，不依赖已生成上下文。
• 目标序列：payload seed 伪随机展开系数，定义 fpay 及其网格，再按行展成长度 q² 的 Apay。第 t 步目标箱为 Apay 的 t mod q² 项；生成长度 T 短于或长于 q² 时截断或重复。
• 注入：只改解码分布，不改基座权重。目标箱内 token 的 logit 加 δ（δ≥0），再按 Algorithm 1 从 softmax 采样。实验取 q=17、d=3、δ=5.0。

检测

• 映回：用同一 Kbin 把 token 映成箱序列。若长度 n<m，判未检出且 pdet=1。
• 窗口检验：起点 s、步长 τ、长度 m，每隔 τ 取一个符号，且下标必须有效。Cons_e(W)=1 当且仅当存在次数至多 d 的一元多项式 g，使窗口与 g 的不匹配坐标数不超过 e。e=0 为精确一致；e>0 容忍少量替换或分箱不匹配。实现是 Berlekamp–Welch 后再核对距离。实验取 m=12、e=2。
• 步长搜索：候选步长从 1 到 floor((n−1)/(m−1))。先做 Npilot 次试点，保留至多 k 个最高分合法步长。作者称这是启发式搜索，不预设某种编辑结构。实验为 500 次试点、至多 8 个步长。论文未给出正式阶段的 Ntrials。
• 判定：每个入选步长统计 Ntrials 个随机窗口的成功次数，对照该步长的零假设成功率 π0,τ 计算二项尾。pdet 取 min{1, |R| 乘以入选步长中最小的尾概率}，作者称用 Bonferroni 校正。pdet≤α 判为带水印。记号表把这些分数写成近似检测分数；π0,τ 离线估计。

理论条件

• 删除：作者称检测只需一条在至多 e 个错误内仍与低次 RS 码字一致的局部子序列；删除主要减少可观测坐标。突发删掉一整段后，其他窗口仍可能留下 RS 结构。
• 唯一重构：Proposition 1 称，接收值与某个次数至多 d 的多项式至多差 e 个坐标，且 2e<m−d 时，Berlekamp–Welch 可在多项式时间内唯一重构该多项式。按实验取值，2e=4，m−d=9。
• 替换界：Theorem 1 设每个坐标独立以概率 ρ 被替换。带水印侧是噪声 RS 码字中替换数不超过 e 的概率；零假设侧是均匀随机向量落在某 RS 码字 Hamming 距离 e 以内的概率。若前者的 0.99 倍大于后者，作者称两分布可用常数优势区分。推导在附录 B.2。

实验设置

• 模型：OPT-1.3B 与 Llama-3.1-8B-Instruct。与基线的全表只用后者；前者只在 Table 3 报告 RMCW。
• 数据与长度：C4 RealNews 做开放式续写，附录 C.1 写用验证集 5,000 条；ELI5 做长问答，附录写 1,000 条且只评 RMCW；MBPP 有 974 题。两种文本设定的最大生成长度为 500；Table 2 标题写 500-token generations。论文未写重复次数。
• 基线：KGW（γ=0.5，δ=2.0，prefix_length=1）、EXP（prefix_length=4）、PRC（固定词表置换，LDPC 式线性码，零假设匹配概率 1/2）。同条件共用提示、模型、分词器、长度与攻击。
• 指标：正类是带水印生成，可再经攻击；负类是数据集中的人类续写，并跨方法、攻击固定。报告 TPR@1%FPR、TPR@5%FPR、AUROC，均写成百分数。TPR@γFPR 取经验 FPR 不超过 γ 时的最高 TPR。低 FPR 点来自各方法自己的分数：RMCW 用 pdet，KGW 用 z，EXP 的 ROC 用 −log10(p)。不是另请 LLM 评审。
• RMCW 配置：q=17，d=3，m=12，e=2，δ=5.0；试点 500 次，至多 8 个步长。δ 按相对人类与基线的困惑度选取；所附文本没有给出困惑度数值。论文未给出 Ntrials。
• 攻击：附录 C.5 的主设定为随机删除 r=0.2、突发删除 r=0.5、截断 r=0.5、同义词替换 r=0.5、emoji r=1.0、DIPPER 释义。作者把 emoji 与删除放在一起，因为二者都改变序列长度并平移后续 token。

主结果

下表是 Table 2 的 TPR@1%FPR。模型为 Llama-3.1-8B-Instruct，数据为 C4，生成为 500 token。截断与 emoji 未列入。

表格较宽，可左右滑动

方法	Clean	Rand. Del.	Burst Del.	Syn. Sub.	Para.
KGW	99.7%	98.2%	96.4%	69.5%	12.2%
EXP	98.9%	79.1%	93.8%	21.1%	10.1%
PRC	95.0%	55.2%	45.9%	29.9%	8.4%
RMCW	99.8%	90.0%	98.1%	86.6%	8.3%

• 作者称按干净文本加六种攻击做算术平均后，RMCW 三项都最高：TPR@1%FPR 82.5%、TPR@5%FPR 84.3%、AUROC 91.9%，相对最强基线平均分别高 14.9、13.2、11.0 个百分点。
• 表外的 Table 2 数字：截断下 RMCW 的 TPR@1%FPR 为 98.9%，PRC 为 39.7%；emoji 下 RMCW 为 95.5%，基线的该项至多 1.9%。随机删除上 RMCW 低于 KGW，作者称其为第二高。
• 作者称强释义对所有方法都难。RMCW 的释义 AUROC 为 53.7%，是该列最高，但 TPR@1%FPR 低于 KGW。作者把释义写成 RMCW 的主要限制。

跨模型与数据集

• Table 3 只报告 RMCW。Llama-3.1-8B-Instruct、ELI5 的 TPR@1%FPR / TPR@5%FPR / AUROC：干净 99.5% / 99.5% / 99.8%，突发删除 95.5% / 95.7% / 97.7%，同义词替换 90.8% / 92.7% / 94.9%。这里的 95.5% 不是 Table 2 的 emoji。
• OPT-1.3B、C4：干净 87.1% / 87.6% / 93.5%，突发删除 83.6% / 86.8% / 90.6%，同义词 81.4% / 83.7% / 87.3%。OPT-1.3B、ELI5：89.6% / 90.4% / 94.7%，87.6% / 87.8% / 92.9%，85.7% / 88.3% / 89.6%。
• 作者称绝对强度随基座模型变化，四种组合仍保持同一模式。Llama、C4 一行与 Table 2 的 RMCW 相同。Table 3 没有基线。

生成长度

• Figure 2 在 C4、Llama-3.1-8B-Instruct 的干净文本上，把最大新 token 从 100 增到 500，比较 RMCW、KGW、EXP、PRC 的 AUROC 与 TPR@1%FPR。正文只给出 RMCW 的读数。
• 正文称 RMCW 的 AUROC 在 100 token 为 77.5%，200 token 时高于 93.3%，300 token 起接近 98.0%。TPR@1%FPR 从 55.5% 到 200 token 的 87.6%、300 token 的 96.0%，500 token 时接近 99.8%。
• 作者称更长文本提供更多诱导符号和候选窗口，局部证据更容易累积。正文没有给出另三种方法在该图上的端点数字。

检测器消融

• Table 4 仍是 C4、Llama-3.1-8B-Instruct 的 TPR@1%FPR。全检测器：干净 99.8%，随机删除 90.0%，同义词 86.6%，突发删除 98.1%，emoji 95.5%。只测步长 τ=1：99.0%、92.6%、84.3%、98.1%、86.1%。
• 作者称全检测器在五档里四档最高或并列；相对 τ=1，同义词高 2.3 个百分点、emoji 高 9.4 个百分点。随机删除上 τ=1 反而高 2.6 个百分点。作者称自适应步长并非对每种删除都更好。
• e=0 的精确 RS：94.1%、29.7%、25.8%、74.3%、26.2%。作者称相对全检测器，降幅为随机删除 60.3、同义词 60.8、突发删除 23.8、emoji 69.3 个百分点，并称 logit 偏置只鼓励、不强制 token 落入目标箱。

其他消融与分析

• Table 6，同一模型与 C4，TPR@1%FPR：随机删除 10% 到 50% 为 98.8%、90.0%、79.5%、64.9%、39.1%；突发删除为 99.8%、99.6%、98.8%、99.1%、98.1%；截断为 99.8%、99.8%、99.8%、99.5%、98.9%。
• 同表 emoji 插入率 10%–50% 为 98.9%、98.2%、97.4%、97.9%、96.7%；同义词为 99.0%、98.2%、95.1%、90.9%、86.6%。主实验 emoji 的 r=1.0 不在此表。
• Table 5，MBPP、Llama-3.1-8B-Instruct：无水印 Pass@1 为 46.7%。RMCW 为 34.5%，AUROC 87.2%，TPR@1%FPR 37.2%，TPR@5%FPR 74.6%。EXP 的 Pass@1 为 36.6%、AUROC 90.7%、TPR@1%FPR 37.0%。
• 同表 KGW：Pass@1 35.7%，AUROC 85.8%，TPR@1%FPR 12.8%，TPR@5%FPR 48.6%。PRC：13.3%、79.7%、30.1%、48.3%。作者称水印会影响程序是否通过测试，并称这促使后续研究更少破坏正确性的注入。
• Table 7，最长 500 token、同一硬件：RMCW 生成 16.4 token/s、检测 0.57 秒/文本、生成 30.5 秒/样本。KGW 为 59.8、0.95、8.2；EXP 为 15.0、0.26、33.3；PRC 为 11.1、0.01、42.4。作者称 RMCW 的检测不到其平均生成延迟的 2%。

作者指出的局限与后续方向

• 鲁棒边界（Limitations）：RMCW 针对删除类后处理之后仍幸存的局部代数结构，而不是对任意文本变换都保持可检；效果依赖观测文本里还留有局部、由 token 派生的结构。
• 释义（Limitations）：强的文档级释义可以换掉大部分原有词面和句式，直接幸存的水印证据就很少。
• 随机删除（Limitations）：独立分布的随机删除比突发删除或截断更难，因为同步变化分布在整个序列上。
• 文本长度（Limitations）：检测器从更长文本中受益很多；短生成或被缩得很短的片段，在低假阳率下可能证据不足。作者把更省样本的局部检验，或跨多段汇总证据，写成后续方向。
• 标定与部署（Limitations）：各步长的零假设成功率离线估计，pdet 是近似检测分数，不是精确校准的 p 值。基座模型、分词器、词表、领域、生成长度或检测参数一变，零分布就可能变，需要重标定；实际部署要在目标分布上验证。
• 代码效用（附录 D.2）：作者称 MBPP 上相对无水印 Pass@1 的下降，促使后续研究更能保持程序正确性的水印注入。

实验覆盖范围

• 生成模型为 OPT-1.3B 与 Llama-3.1-8B-Instruct（§4.1）。与 KGW、EXP、PRC 的对照主表是 C4、Llama-3.1-8B-Instruct、500 token 生成，含干净文本和附录 C.5 的六种后处理（Table 2）。
• Table 3 只含 RMCW，覆盖上述两模型、C4 与 ELI5，以及干净、突发删除、同义词替换。附录 C.1 写 C4 用验证集 5,000 条，ELI5 用 1,000 条评 RMCW。
• 另有干净文本上最大生成长度 100 到 500（Figure 2）、检测器消融（Table 4）、攻击率 10%–50%（Table 6）、MBPP 的 974 题（Table 5）、最长 500 token 的墙钟时间（Table 7）。
• 负类是数据集给出的人类续写，不是人工标注员。低 FPR 由各检测器的经验分数算出。
• 论文未报告主结果的重复次数，也未给出正式检测阶段的 Ntrials；pdet 使用离线估计的步长相关零假设率（附录 C.4.2）。

RMCW 是面向删除后同步丢失的 LLM 水印：生成时写入 Reed–Muller 结构，检测时只查局部 Reed–Solomon 一致性。

• 问题：水印符号若绑在生成位置上，删除、裁剪或只保留片段会使剩余 token 对不齐原坐标。作者认为零比特检测不必译出码字，只要找到无水印文本里不太可能出现的结构。
• 做法：Kbin 把每个 token 映到 q 个箱之一；payload seed 采样次数至多 d 的二元多项式，排成网格并按行重复使用。解码只给目标箱的 logit 加 δ。检测在至多 k 个步长上抽长度为 m 的窗口，允许至多 e 个不匹配，再用二项尾和 Bonferroni 校正得到近似分数 pdet。实验主取 q=17、d=3、m=12、e=2、δ=5。
• 主结果：Table 2 在 C4、Llama-3.1-8B-Instruct、500 token 上，RMCW 的 TPR@1%FPR 为干净 99.8%、突发删除 98.1%、截断 98.9%、同义词替换 86.6%、emoji 95.5%。随机删除为 90.0%，低于 KGW；DIPPER 释义为 8.3%。七种设置平均为 82.5%，作者称比最强基线平均高 14.9 个百分点。
• 其他结果：Table 3 里 OPT-1.3B 在 C4 干净文本上为 87.1%，突发删除 83.6%，同义词 81.4%，作者称模式仍在，但该表没有基线。Figure 2 中 RMCW 在 100 token 时 TPR@1%FPR 为 55.5%，500 token 时接近 99.8%。MBPP 上无水印 Pass@1 为 46.7%，RMCW 为 34.5%（Table 5）。
• 作者结论：作者称局部代数一致性是鲁棒 LLM 水印的一种有前景的设计；Limitations 同时写明，强释义、短文本，以及需要重标定的近似 pdet，会限制检测。