跳转至

Towards Better Statistical Understanding of Watermarking LLMs

作者: Zhongze Cai, Shang Liu, Hanzhao Wang, Huaiyang Zhong, Xiaocheng Li
来源: Journal of the American Statistical Association
主题: 数理统计 / 假设检验
相关性: 4/10
机构绿灯: Imperial College London（US News 前 50，免分进入精读）
链接: https://doi.org/10.1080/01621459.2026.2618290

一、领域脉络与小综述

这个方向是什么： LLM 水印旨在在模型生成的文本中嵌入隐蔽的统计信号，使得后续检测者能通过假设检验判断文本是否由特定模型生成，同时要求嵌入过程不显著改变文本的分布（即不产生失真）。这个子方向的根本统计问题是：在维持生成分布尽可能接近原分布的约束下，如何最大化检测假设检验的统计功率。当前该方向处于从"启发式算法+经验验证"向"严格统计建模与优化界"过渡的阶段，成熟度中等——已有明确的假设检验框架，但失真度量的选取与功率-失真的理论边界仍处于争论中。

发展脉络： - 奠基工作：Aaronson (2022) 提出基于随机种子与词表划分的 watermark 机制，将检测问题转化为基于 token 序列的假设检验，但未严格处理失真约束。作者引用其作为"red-green list 框架的起点"，指出其留下了"失真与功率 tradeoff 未被形式化"的口子。 - 主要进展：Kirchenbauer et al. (2023) 引入了"distortion-free"概念，声称在特定硬度度量下水印不改变分布。作者在文中明确反驳此点，指出其"distortion-free"定义仅保证 token 级别的边际分布不变，而未约束联合分布或 KL 散度，留下了"失真度量选择不当"的口子。 - 当前 frontier：近期工作（如 Zhao et al. 2023 的 dip-mark）试图通过修改 logits 的软水印降低失真，但缺乏对检测功率的理论保证。作者引用这些工作作为"经验上有效但理论上无界"的代表。 - 本文的位置：将水印的嵌入与检测统一到一个约束优化问题（KL 散度约束失真，最大化检测功率）中，并证明其提出的在线对偶梯度上升算法在该约束下达到渐近 Pareto 最优，填补了"理论界"的口子。

子线索聚类： 1. 硬水印与假设检验框架（Aaronson 2022, Kirchenbauer 2023）：基于词表的硬划分（red-green list），检测通过统计 green token 的比例进行假设检验。这一簇在定义检测的统计检验问题，但失真度量模糊。 2. 软水印与经验失真控制（Zhao et al. 2023, Kuditipudi et al. 2023）：通过 logits 的连续调整嵌入水印，声称在 perplexity 或边际分布上"distortion-free"。这一簇在尝试降低经验失真，但缺乏功率的理论下界。 3. 统计优化与界理论（本文）：将功率-失真 tradeoff 形式化为约束优化，用 KL 散度约束失真，用对偶上升求解，给出渐近 Pareto 最优界。这一簇在追求严格的统计效率界。

这个方向在追问的核心问题： 1. 失真度量应如何定义？边际分布不变、perplexity 不变、还是 KL 散度不变？哪种度量能真实反映文本质量与检测功率的 tradeoff？ 2. 在给定失真约束下，检测功率的理论上界是什么？是否存在类似 minimax 或效率界的 Pareto 前沿？ 3. 能否设计算法同时达到理论界与实际可行性？在线嵌入（逐 token 生成）下，如何保证渐近最优性？

⚠️ 作者的 framing： 作者将缺口 frame 为：既有工作要么缺乏失真约束的理论建模（如 Aaronson），要么失真度量选择不当（如 Kirchenbauer 的"distortion-free"与 perplexity），导致无法严格讨论功率-失真 tradeoff。本文通过 KL 散度约束与约束优化，声称自己是"第一个严格给出渐近 Pareto 最优界"的工作。 - 被淡化的竞争路线：基于密码学或纠错码的水印（如 Christ et al. 2023 的 watermark 通过不可逆函数嵌入），作者未在 intro 中讨论这类路线的功率-失真 tradeoff，可能因为其难以纳入 KL 散度约束的优化框架。 - 明显该被引却未出现的：信息论中的 rate-distortion theory（如 Shannon 1959 或 Cover 1991 的经典工作）——本文的核心问题（KL 约束下最大化互信息或检测功率）与 rate-distortion 问题形式上高度同构，但 intro 未引用任何 rate-distortion 文献，这可能意味着作者未意识到此联系，或刻意回避了与信息论界的比较。值得研究者去查：rate-distortion 理论是否已给出本文 Pareto 界的更紧形式？

张力： 未见明显对立引用。Kirchenbauer 的"distortion-free"与本文的"KL 散度约束"是度量选择上的分歧，但非数学结论的矛盾。唯一潜在张力：作者声称 KL 散度是"正确"度量，而 Zhao et al. 2023 的 dip-mark 在经验上用 perplexity 控制失真且效果不错——这构成度量选择的实践与理论张力，但非严格对立。

二、最核心、最简单的例子 / 数学问题

第一步：符号、模型、可观测数据交代清楚

  • \(V\)：词表，大小为 \(|V|\)，包含所有可能生成的 token。
  • \(x_t\)：第 \(t\) 步生成的 token，随机变量，取值于 \(V\)。
  • \(p_t(v)\)：原 LLM 在第 \(t\) 步生成 token \(v\) 的概率分布，即 \(p_t(v) = P(x_t = v \mid \text{context up to } t-1)\)。这是未加水印的基准分布。
  • \(q_t(v)\)：加水印后第 \(t\) 步生成 token \(v\) 的概率分布，即 \(q_t(v) = P(\tilde{x}_t = v \mid \text{context up to } t-1, \text{watermark key})\)。这是实际生成分布，也是算法要设计的对象。
  • \(\tilde{x}_t\)：加水印后第 \(t\) 步实际生成的 token，随机变量。
  • \(S_t\)：第 \(t\) 步的 green list，是 \(V\) 的一个子集，大小为 \(|S_t| = \gamma |V|\)（\(\gamma \in (0,1)\) 是 green list 比例）。\(S_t\) 由随机种子（如前一步 token 的哈希）决定，在生成前确定。
  • \(\gamma\)：green list 比例，参数，通常取 \(0.5\)。
  • \(\delta\)：水印强度参数，控制 green list token 的 logits 提升。
  • \(T\)：生成序列的总长度（时间步数），样本量指标。
  • \(G_T\)：序列中 green list token 的总数，即 \(G_T = \sum_{t=1}^T \mathbf{1}(\tilde{x}_t \in S_t)\)，这是检测检验的核心统计量。
  • \(\epsilon\)：KL 散度约束的容忍度，即 \(\text{KL}(q_t \mid p_t) \leq \epsilon\)，这是失真约束的参数。
  • 可观测数据：检测者能观测到生成序列 \(\{\tilde{x}_t\}_{t=1}^T\) 与 green list 划分 \(\{S_t\}_{t=1}^T\)（因种子规则公开），从而能计算 \(G_T\)。原分布 \(p_t\) 与水印分布 \(q_t\) 对检测者是未知的（除非有模型访问），检测只能通过 \(G_T\) 的统计检验进行。水印嵌入者能观测 \(p_t\)（通过模型 logits）并设计 \(q_t\)。

第二步：最小内核——单步二值假设检验与 KL 约束优化

剥掉多步序列与在线算法的复杂性，最小内核是单步 token 生成的 KL 约束优化问题：

  • 原分布：\(p_t\) 在 \(V\) 上的分布，已知。
  • Green list：\(S_t \subset V\)，已知，比例 \(\gamma\)。
  • 目标：设计 \(q_t\)，使得：
  • 失真约束：\(\text{KL}(q_t \mid p_t) \leq \epsilon\)。
  • 最大化检测功率：最大化 \(q_t(S_t) = \sum_{v \in S_t} q_t(v)\)，即 green list token 的总概率。

  • 为什么这个内核支撑整篇论文：多步序列的检测功率依赖于每步 \(q_t(S_t)\) 的提升，而在线算法的渐近 Pareto 最优性本质上是单步优化在 \(T \to \infty\) 时的累积效应。论文的核心解析性质与对偶上升算法都源于这个单步优化问题的解结构。

  • 最小内核的解与直觉： 单步 KL 约束优化 \(\max_{q_t} q_t(S_t)\) s.t. \(\text{KL}(q_t \mid p_t) \leq \epsilon\) 的解具有解析性质：最优 \(q_t\) 是 \(p_t\) 的指数倾斜，即 \(q_t(v) \propto p_t(v) \exp(\lambda \mathbf{1}(v \in S_t))\)，其中 \(\lambda \geq 0\) 是对偶变量（与 \(\epsilon\) 的约束对应）。这直接给出：

  • Green list 概率提升：\(q_t(S_t) = \frac{\sum_{v \in S_t} p_t(v) e^\lambda}{\sum_{v \in S_t} p_t(v) e^\lambda + \sum_{v \notin S_t} p_t(v)}\)，当 \(\lambda > 0\) 时严格大于 \(p_t(S_t)\)。
  • 检测检验：在 \(H_0\)（无水印）下 \(G_T\) 的期望为 \(\gamma T\)；在 \(H_1\)（有水印）下期望为 \(\sum_{t=1}^T q_t(S_t) T\)，因 \(q_t(S_t) > \gamma\) 而功率提升。
  • Pareto 最优性：任何满足 \(\text{KL}(q_t \mid p_t) \leq \epsilon\) 的 \(q_t\)，其 \(q_t(S_t)\) 不可能超过上述指数倾斜解的值——这就是单步的 Pareto 前沿。

三、这篇论文做了什么

三句话： 1. 研究了 LLM red-green list 水印中模型失真与检测功率的 tradeoff，将其形式化为以 KL 散度约束失真、最大化 green list 概率的约束优化问题。 2. 核心工具是约束优化的对偶理论与在线梯度上升，利用最优解的指数倾斜解析性质设计算法。 3. 主要结论是提出的在线对偶梯度上升水印算法在 KL 散度约束下达到渐近 Pareto 最优，显式保证平均 green list 概率提升，并论证了 KL 散度优于"distortion-free"与 perplexity 作为失真度量。

关键设定与假设： 在第二节最小记号基础上补全： - Red-green list 机制：每步 \(t\)，根据随机种子（如前一步 token 的哈希）将词表 \(V\) 划分为 green list \(S_t\) 与 red list \(V \setminus S_t\)，比例 \(\gamma\) 固定。 - 水印嵌入规则：原 LLM logits \(\ell_t(v) = \log p_t(v)\)，加水印后 logits 变为 \(\tilde{\ell}_t(v) = \ell_t(v) + \delta \mathbf{1}(v \in S_t)\)，其中 \(\delta > 0\) 是水印强度。这对应 \(q_t(v) \propto p_t(v) \exp(\delta \mathbf{1}(v \in S_t))\)，即指数倾斜。 - 假设 1（独立种子）：\(S_t\) 的划分种子仅依赖前一步 token，使得 \(S_t\) 在给定 \(\tilde{x}_{t-1}\) 时确定，跨步条件独立。这是检测检验计算 \(G_T\) 分布的基础。 - 假设 2（KL 散度约束）：每步 \(\text{KL}(q_t \mid p_t) \leq \epsilon\)，或序列平均 \(\frac{1}{T} \sum_{t=1}^T \text{KL}(q_t \mid p_t) \leq \epsilon\)。统计含义：约束生成分布偏离原分布的信息论距离，保证文本质量。 - 假设 3（渐近设定）：\(T \to \infty\)，序列长度足够长使得 \(G_T\) 的分布可由中心极限定理近似。这是渐近 Pareto 最优性与检测检验功率计算的基础。 - 与已有文献的对比：Kirchenbauer et al. (2023) 用硬划分加固定 \(\delta\)，无失真约束；Zhao et al. (2023) 用软 logits 调整但无理论界。本文的 KL 约束与对偶优化是新的，放宽了"distortion-free"的强要求（边际分布不变），代之以更弱的 KL 约束。

主要结果： 1. 定理：最优解的解析性质（指数倾斜）： - 陈述：单步优化 \(\max_{q_t} q_t(S_t)\) s.t. \(\text{KL}(q_t \mid p_t) \leq \epsilon\) 的最优解为 \(q_t(v) \propto p_t(v) \exp(\lambda \mathbf{1}(v \in S_t))\)，其中 \(\lambda\) 是满足 KL 约束的对偶变量。 - 直觉：这是 KL 约束下最大化线性目标的标准结果，指数倾斜是信息论中 rate-distortion 与假设检验（如 Neyman-Pearson lemma）的常见解结构。 - 必要条件：\(p_t\) 已知（水印嵌入者有模型 logits），\(S_t\) 确定。 - 技术难点：无特殊难点，这是凸优化的标准结论，但本文首次将其应用于水印设计。

  1. 定理：在线对偶梯度上升的渐近 Pareto 最优性：
  2. 陈述：在线算法每步根据当前 \(p_t\) 与 \(S_t\)，用对偶梯度上升更新 \(\lambda_t\)（步长 \(\eta_t\)），生成 \(\tilde{x}_t \sim q_t \propto p_t \exp(\lambda_t \mathbf{1}(v \in S_t))\)。当 \(T \to \infty\) 时，算法达到 Pareto 最优：不存在其他满足 \(\frac{1}{T} \sum_{t=1}^T \text{KL}(q_t \mid p_t) \leq \epsilon\) 的算法，其 \(\frac{1}{T} \sum_{t=1}^T q_t(S_t)\) 超过本算法的渐近值。
  3. 直觉：在线对偶上升是约束优化的标准在线学习算法，渐近 Pareto 最优性意味着算法在平均意义上达到了离线优化的前沿。
  4. 必要条件：步长 \(\eta_t\) 满足 \(\sum \eta_t = \infty, \sum \eta_t^2 < \infty\)（标准随机逼近条件），\(p_t\) 与 \(S_t\) 的分布满足遍历性或平稳性。

  5. 技术难点：在线设定下 \(p_t\) 与 \(S_t\) 随步变化，无法离线计算全局最优 \(\lambda\)；需证明在线更新的 \(\lambda_t\) 渐近收敛到最优对偶变量，且平均 KL 约束与平均 green list 概率达到 Pareto 前沿。

  6. 论证：KL 散度优于"distortion-free"与 perplexity：

  7. 陈述："distortion-free"（Kirchenbauer et al. 2023）仅保证边际分布 \(q_t(v) = p_t(v)\) 对所有 \(v\)，但无法约束联合分布的偏离，且在 red-green list 硬划分下不可能同时保证边际不变与 green list 概率提升。Perplexity \(\exp(-\frac{1}{T} \sum \log q_t(\tilde{x}_t))\) 是生成概率的几何平均，对分布尾部敏感但无法捕捉局部结构变化（如 green list 区域的概率集中）。KL 散度 \(\text{KL}(q_t \mid p_t)\) 是信息论标准度量，约束整体分布偏离且与检测功率的假设检验界直接关联（Neyman-Pearson lemma 中 KL 散度决定两类错误的指数衰减率）。
  8. 直觉：KL 散度是假设检验与信息论的统一度量，选择它使得失真约束与检测功率在同一框架下优化。
  9. 必要条件：无特殊条件，这是度量选择的论证，非严格定理。

证明路线与技术技巧： - 整体路线（渐近 Pareto 最优性证明）： 1. 单步优化解结构：证明单步 KL 约束优化的最优解为指数倾斜，建立 Pareto 前沿的解析表达式（\(q_t(S_t)\) 作为 \(\epsilon\) 的函数）。 2. 在线对偶上升收敛性：证明在线更新 \(\lambda_{t+1} = \lambda_t + \eta_t (\mathbf{1}(\tilde{x}_t \in S_t) - q_t(S_t) - \epsilon \text{或相关梯度项})\) 使得 \(\lambda_t\) 渐近收敛到最优对偶变量 \(\lambda^*\)（满足平均 KL 约束的拉格朗日乘子）。 3. 平均约束满足：证明 \(\frac{1}{T} \sum_{t=1}^T \text{KL}(q_t \mid p_t) \leq \epsilon\) 渐近成立（利用对偶上升的 regret 界或鞅收敛）。 4. 平均目标达到前沿：证明 \(\frac{1}{T} \sum_{t=1}^T q_t(S_t)\) 渐近达到离线 Pareto 前沿的值（利用收敛的 \(\lambda_t\) 与指数倾斜的连续性）。 5. Pareto 最优性声明：结合 3 与 4，任何满足平均 KL 约束的算法其平均 green list 概率不超过本算法的渐近值，故算法渐近 Pareto 最优。

  • 关键跳跃点：
  • 在线对偶上升的收敛与 regret 界：在线设定下 \(p_t\) 与 \(S_t\) 随步变化，标准离线对偶理论不直接适用。需用在线凸优化的 regret 界（如 Zinkevich 2003 的在线梯度下降）证明对偶变量的平均 regret 趋于 0，从而渐近满足约束且达到前沿。这是证明最吃功夫的引理。

  • 指数倾斜与检测功率的显式关联：需将 \(q_t(S_t)\) 的提升转化为检测检验（基于 \(G_T\) 的假设检验）的功率提升，利用中心极限定理计算 \(G_T\) 在 \(H_0\) 与 \(H_1\) 下的分布差异，证明功率随 \(T\) 增加而趋于 1（只要 \(q_t(S_t) > \gamma\)）。

  • 技术技巧点名：

  • 凸对偶：用于建立单步优化的指数倾斜解与 Pareto 前沿，是整个框架的基石。
  • 在线梯度上升 / Zinkevich regret 界：用于证明在线对偶变量的收敛与平均约束满足，是渐近 Pareto 最优性的核心工具。
  • 中心极限定理 / 渐近假设检验：用于将 green list 概率提升转化为检测功率的显式保证，连接优化与统计检验。
  • Neyman-Pearson lemma / KL 散度与检验功率的关联：用于论证 KL 散度作为失真度量的合理性，指出 KL 散度直接决定假设检验的两类错误率。

真实例子与应用： - 数据 / 场景：在多个标准文本生成数据集上实验，包括 OpenWebText（续写任务）、CNN/DailyMail（摘要任务）、C4（随机片段生成）。模型使用 OPT-1.3B 与 LLaMA-7B。 - 如何用上去：对每个生成任务，用本文的在线对偶梯度上升水印算法（设定 KL 约束 \(\epsilon\) 与 green list 比例 \(\gamma\)）生成文本，然后用基于 \(G_T\) 的假设检验检测水印。对比 baseline 为 Kirchenbauer et al. (2023) 的硬水印与 Zhao et al. (2023) 的软水印。 - 结果：在相同检测功率（如 TPR@FPR=0.01）下，本文算法的文本质量（用 KL 散度、perplexity、语义保持度衡量）优于硬水印，与软水印持平但在理论保证上更优。在相同失真水平下，本文算法的检测功率高于软水印。 - 想说明什么：验证理论结论——在线对偶上升在 KL 约束下达到 Pareto 最优，且 KL 散度约束比 perplexity 或"distortion-free"更合理。同时展示算法的实际可行性（在线生成不显著增加延迟）。

🔎 结论是否比证明窄： - 渐近 Pareto 最优性在平均 KL 约束与遍历性/平稳性假设下严格证明，但论文泛泛 claim 为"算法在失真与检测间达到 Pareto 最优"，未强调"渐近"与"平均"的限制。有限样本下是否达到或接近 Pareto 前沿，仅有经验验证，无理论界——这是一个窄结论被宽泛 claim 的点。 - KL 散度优于 perplexity 的论证是逻辑推理而非定理，论文将其陈述为"系统性讨论"，但未严格证明"perplexity 约束下无法达到类似 Pareto 前沿"——这是另一个宽泛 claim。

四、开放问题（点到为止，扎根具体语句）

  1. 有限样本的 Pareto 前沿界：渐近 Pareto 最优性在 \(T \to \infty\) 下证明（定理陈述），有限 \(T\) 下算法与前沿的偏离有多大？能否给出有限样本的 excess risk 界？扎根在定理的渐近条件与"有限样本仅有经验验证"的缺口。
  2. Rate-distortion 理论的同构与更紧界：本文的 KL 约束优化与 Shannon rate-distortion 问题形式同构，但未引用 rate-distortion 文献。rate-distortion 理论是否已给出更紧的 Pareto 前沿界（如用互信息而非 green list 概率作为目标）？扎根在 intro 缺失的 rate-distortion 引用与本文目标函数的选择。
  3. 非平稳 \(p_t\) 下的在线对偶收敛：证明依赖 \(p_t\) 的遍历性或平稳性（假设 3），若 \(p_t\) 随步剧烈变化（如长文本生成中主题切换），对偶上升是否仍收敛？扎根在假设 3 的遍历性条件与实际 LLM 生成分布的非平稳性。
  4. 对抗攻击下的鲁棒性：本文的检测检验基于 \(G_T\) 的统计量，未讨论对抗性文本修改（如替换部分 green token）对检测功率的影响。能否在约束优化中加入鲁棒性约束？扎根在实验部分仅讨论无攻击场景与 intro 未提及对抗鲁棒性。

提醒：要确认某条是不是真 gap，去读同子领域近期约 5 篇的 intro——若都指向有限样本界或对抗鲁棒性，则为共识真 gap；若互相打架（如有人声称软水印已解决鲁棒性），则为机会。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论