Can we Watermark Low-Entropy LLM Outputs?

论文技术总结：低熵大语言模型输出的不可检测水印

1. 研究背景与问题定义

随着大语言模型（LLM）生成内容的日益逼真，区分 AI 生成内容与人类生成内容变得至关重要。水印技术通过在生成内容中嵌入隐藏代码来实现这一目标。然而，现有的水印方案存在显著局限性：

• 不可检测性（Undetectability）： 水印不应改变 LLM 的输出分布，使得水marked 输出在计算上无法与原始输出区分。
• 鲁棒性（Robustness）： 水印应能抵抗攻击者的编辑（替换、插入、删除）。
• 核心痛点（熵要求）： 现有的不可检测水印方案（如 Christ et al. [CG24], Golowich et al. [GM24]）通常要求 LLM 输出具有高熵率。具体来说，它们要求输出中相当一部分 Token 的熵至少为 $O(\log |T|)$（其中 $|T|$ 是 Token 表大小），或者依赖于特定的分布假设。
• 现实挑战： 在实际应用中，LLM 经常生成低熵内容（例如重复短语、确定性回答、或熵仅为 1 bit 的 Token）。当 Token 熵很低时，现有方案无法可靠地嵌入水印，或者需要引入强分布假设（如 Huffman 编码假设），这在通用场景下不切实际。

本文核心问题： 能否在不依赖大 Token 表大小且**仅要求极低熵（如常数熵，甚至 1 bit）**的情况下，构建既不可检测又具有鲁棒性的 LLM 水印方案？

---

2. 方法论与核心技术

作者提出了一种基于**伪随机纠错码（Pseudorandom Error-Correcting Codes, PRC）**的新框架，专门针对大 Token 表但低熵输出的场景。

核心思想：哈希映射与分块复用
传统的二进制 PRC 方案（如 [CG24]）直接嵌入二进制位，或者将大 Token 表转换为二进制（导致熵需求随 Token 长度线性增加）。本文提出了一种“中间路线”：

1. 哈希映射（Hashing）： 不直接嵌入 Token，而是将 LLM 生成的每个 Token $t$ 通过一个随机哈希函数 $h: T \to \{0, 1\}$ 映射为 1 位比特。
2. 嵌入策略： 利用 PRC 生成的伪随机码字 $c$（二进制串），在生成 Token 时，尝试让 Token 的哈希值 $h(t)$ 与码字位 $c_i$ 匹配。
   • 如果 LLM 分布允许（即存在两个采样 $t_0, t_1$ 使得 $h(t_0) \neq h(t_1)$），则选择哈希值匹配 $c_i$ 的那个 Token。
   • 如果无法匹配（即 $h(t_0) = h(t_1)$），则随机选择一个，这会导致 50% 的概率产生“嵌入错误”。
3. 分块复用哈希函数（Block-wise Hash Reuse）：
   • 为了抵抗**删除（Deletion）**攻击，不能为每个 Token 使用独立的哈希函数（否则删除后无法对齐哈希函数）。
   • 作者将输出划分为多个块（Block），每个块对应一个 PRC 码字。在同一个块内，复用同一个哈希函数 $h$。
   • 这种设计允许在检测到删除后，通过尝试不同的哈希函数或块对齐来恢复水印，同时保持了块与块之间的独立性。

关键分析洞察：

• 低熵下的成功概率： 即使 Token 的熵仅为 1 bit（即 $D(t) \le 1/2$），只要存在常数比例的 Token 满足此条件，哈希函数 $h$ 以至少 $1/4$ 的概率将这两个 Token 映射到不同的比特（$h(t_0) \neq h(t_1)$）。
• 随机替换的鲁棒性： 即使攻击者进行随机替换，只要替换后的 Token 分布与 PRC 码字位独立，其哈希值错误的概率仍为 $1/2$。因此，只要原始嵌入的错误率低于 $1/2$，经过随机替换后的总错误率仍低于 PRC 的纠错阈值。
• 处理删除： 通过分块和哈希复用，即使部分 Token 被删除，只要剩余块中仍有足够的高熵 Token，PRC 解码器仍能恢复码字。

---

3. 主要贡献与结果

本文构建了多种水印方案，分别针对不同的攻击模型和假设条件：

1. 针对随机替换攻击的鲁棒性（无额外假设）

• 结果： 构建了在**最小经验熵（Minimal Empirical Entropy）**条件下（即仅需常数比例的 Token 具有 1 bit 熵）的鲁棒水印方案。
• 假设： 基于子指数硬度的 LPN（Learning Parity with Noise）假设（同 [CG24]）。
• 能力： 可抵抗高达 $(1/2 - \epsilon)$ 比例的随机 Token 替换。
• 意义： 这是首个无需大 Token 表或强分布假设，仅凭低熵即可抵抗随机替换的不可检测水印方案。

2. 针对随机替换与随机删除的鲁棒性

• 方案 A（启发式假设）： 假设 LLM 输出是“自然”的（Natural Prompt），即嵌入错误和随机替换错误共同构成的信道符合**二进制对称信道（BSC）**模型。
  • 在此假设下，方案可抵抗 $(1/2 - \epsilon)$ 的随机替换和 $(1 - \epsilon)$ 的随机删除。
  • 注：此假设排除了如"Emoji 攻击”等构造性攻击，但在自然语言生成中通常成立。
• 方案 B（无启发式假设）： 如果存在一种能抵抗对抗性替换和随机删除的二进制 PRC，则可直接构建无启发式假设的水印方案。
  • 目前已知构造（如 [CGG+25]）基于“置换码（Permuted Codes）”假设，能抵抗少量对抗性编辑，但参数较小。

3. 针对任意编辑（插入/删除/替换）的鲁棒性

• 结果： 利用 [CGG+25] 的 PRC 构造，构建了能抵抗常数比例任意编辑（Adversarial Edits）的水印方案。
• 代价： 需要整个输出中更大比例（常数比例）的 Token 具有低熵，而不仅仅是局部子串。
• 参数： 可抵抗 $\tilde{O}(\delta^4)$ 比例的编辑攻击（$\delta$ 为低熵 Token 的比例）。

---

4. 与现有工作的对比

特性	[CG24] (Christ & Gunn)	[GM24] (Golowich & Moitra)	本文 (Mazor et al.)
Token 表大小	二进制 (Binary)	大表 (Polynomial size)	大表 (Large Alphabet)
熵要求	$O(\log |T|)$ (高熵)	$O(\log |T|)$ (高熵)	$O(1)$ (低熵，仅需 1 bit)
攻击模型	随机替换/删除 (需假设)	任意编辑 (Adversarial Edits)	随机替换/删除/任意编辑
结构保持	需将 Token 转为二进制，破坏结构	保持 Token 结构	保持 Token 结构 (直接操作 Token)
核心假设	LPN (子指数)	局部弱 PRF	LPN 或 置换码假设

• 优势： 本文方案直接在大 Token 表上操作，保留了 LLM 输出的语义结构（如 paraphrasing 攻击在 Token 级别而非 Bit 级别），且显著降低了对 Token 熵的要求，使其适用于更广泛的实际 LLM 输出场景。

---

5. 意义与局限性

意义：

1. 理论突破： 证明了在极低熵（常数熵）条件下，依然可以实现不可检测且鲁棒的 LLM 水印，打破了此前必须依赖高熵或大 Token 表的限制。
2. 实用性提升： 方案直接处理 Token 级别的攻击（如同义词替换、删除），比基于二进制编码的方案更符合自然语言处理的实际攻击场景。
3. 灵活性： 提供了多种权衡方案，从基于启发式假设的高鲁棒性方案到基于更强密码学假设的无假设方案。

局限性与未来方向：

• 参数限制： 针对任意编辑（Adversarial Edits）的鲁棒性参数目前较小（$\tilde{O}(\delta^4)$），依赖于 [CGG+25] 的 PRC 构造参数。
• 启发式假设： 在抵抗随机删除时，部分方案仍依赖“自然提示（Natural Prompt）”假设，即假设错误分布符合 BSC。虽然这在自然语言中合理，但理论上存在被构造性攻击（如 Emoji 攻击）绕过风险。
• PRC 构造依赖： 最终的最强鲁棒性方案依赖于尚未完全标准化的“置换码”假设。

总结：
该论文为大语言模型水印领域开辟了新方向，证明了即使在不理想的低熵输出环境下，通过巧妙的哈希分块策略和 PRC 编码，依然可以构建安全、不可检测且具备一定鲁棒性的水印系统。这为未来在实际 AI 内容生成中部署水印技术奠定了重要的理论基础。