摘要

水印技术为通过在数据中嵌入隐蔽信息来保障数据安全提供了一种很有前景的方法。该领域的一个首要挑战在于，在水印嵌入过程中保持原始数据的分布。我们的研究拓展并优化了现有的水印框架，着重强调了保持分布（DiP）水印的重要性。与当前的策略不同，我们提出的 DiPMark 在水印嵌入时能保留原始标记（token）的分布（具备隐蔽性），无需访问语言模型的应用程序接口（API）或权重即可被检测（具备高效性），并且对标记的适度变化具有鲁棒性（具备抗干扰性）。DiPMark 的工作机制是，在生成一个词之前，先从一系列 “绿色” 标记中随机选取，然后采用一种保持分布的重加权函数来提高这些绿色标记的利用率。我们方法的实证基准突显了它的隐蔽性、高效性和抗干扰性，使其成为那些对质量保存有极高要求的水印任务的可靠解决方案。

第一章引言

在人工智能已然突破类人文本生成壁垒的时代，这类内容的有效性与来源受到了极大的审视。大型语言模型（LLMs）的崛起，以及它们模拟人类文笔的惊人能力，是一把双刃剑。一方面，其潜在应用十分广泛，从简化复杂任务到增强人类能力，不一而足。反之，也存在着被滥用的潜在威胁，比如在学术场景中，学生寻求不正当优势；又或者像在 Reddit、Twitter 和 StackOverflow 等数字平台上，存在错误信息的传播现象。

随着机器生成内容与人类撰写内容之间的界限愈发模糊，用于区分二者的传统启发式方法也不再奏效。即便是最先进的检测器近来也遭遇失败，这充分表明我们迫切需要一种更可靠的解决方案。在这种情况下，水印技术作为一种精妙的解决方案应运而生：它通过在生成的内容中刻意嵌入独特信号，来表明内容的出处。通过在源头对内容进行标记，这项技术提供了一种追踪任何传播信息来源的机制。除了人们普遍认为水印应能通过密钥识别这一观念外，语言模型中高效水印还需要具备几个基本特征：

（隐蔽性）水印应能无缝融入生成的内容，保留原始文本的分布和质量，使得带水印和不带水印的文本难以区分。
（高效性）借助密钥，检测内容（或其片段）中的水印应快速且直接，无需访问语言模型和提示词。
（鲁棒性）如果内容经历适度的更改或修改，水印应保持完整且可识别。

据我们所知，当前的水印技术并不符合上述三个关键特性。这些方法要么影响模型的采样分布，进而导致模型性能下降（Kirchenbauer 等人，2023）；要么缺乏对文本编辑或裁剪等修改的鲁棒性（Christ 等人，2023）；要么在检测过程中需要数千次推理步骤（Kuditipudi 等人，2023）；要么在检测时需要语言模型 API 的标记对数概率（Hu 等人，2023），从而产生巨大的计算成本。传统的隐写方法，即在语言模型生成的文本中插入细微嵌入，往往在可检测性和鲁棒性方面存在不足（Ziegler 等人，2019；Kaptchuk 等人，2021）。我们的目标是创建一种开创性的水印技术，用于将文本归属于某一语言模型，且该技术涵盖所有这三个关键特性（整体对比见表 1）。

我们的水印框架与现有模式（Kirchenbauer 等人，2023）一致，主要由两个部分组成：生成函数，它将提示词和专有的水印密钥转换为来自语言模型的样本；检测函数，它将潜在的带水印文本与密钥进行匹配。在文本生成过程中，语言模型提供者会使用保密密钥对当前标记的输出概率进行重新加权。这种重加权函数保持了隐蔽性，确保每次文本生成都与原始语言模型的分布一致。在检测阶段，仅使用密钥和带水印文本（可能辅以 Python 中的标准哈希函数），就能高效检测到水印的存在。我们还通过在主要语言模型（包括 BART-large 模型（Liu 等人，2020）和 LLaMA-2（Touvron 等人，2023））上进行实验评估，验证了我们水印的上述三个基本特性。

水印中保持文本分布的重要性

我们强调在水印技术中保持文本分布的关键意义，主要基于以下充分的理由：
a) 隐蔽水印：如果一种水印破坏了语言模型的原始分布，那么它就缺乏隐蔽性这一属性。这种分布上的改变，会让人们通过多次采样，相对容易地区分带有水印和不带有水印的大语言模型（LLMs）。
b) 行业级大语言模型应用：当考虑将水印应用于像 ChatGPT 和 Bard 这类行业标准的大语言模型时，首要考虑的是确保水印不会损害这些基础大语言模型的性能。任何干扰原始文本分布的水印，都不可避免地会影响生成文本的质量，而这一结果是行业相关方无法接受的。

注记：

“采样”（sampling）在大语言模型的语境里，指的是模型生成文本的过程。

大语言模型生成文本时，并非直接 “吐出” 完整内容，而是基于自身的训练数据和内部的概率分布，一步一步挑选（也就是 “采样”）下一个要生成的词（token）。比如，当模型要生成 “今天天气____” 时，它会从众多可能的词汇（像 “很好”“晴朗”“糟糕” 等）里，按照一定的概率来选择下一个词，这个选择的过程就是一次 “采样”。多次这样的采样，就组成了完整的文本生成。

我们的贡献

我们的工作致力于解决为大型语言模型设计水印且不影响其天然性能的问题，并在多个方面推动了该领域的前沿发展。

我们提出了一种新颖的水印框架 DiPmark，它为语言模型引入了一种经证明能保持分布的水印方案。与现有方法不同，DiPmark 同时具备隐蔽性、高效性和鲁棒性。
我们为 DiPmark 开发了一种有效的水印检测机制。通过利用假设检验和一套定义完善的统计方法，我们能够可靠地检测到水印的存在，同时保持较低的假阳性率。我们还证明，我们的检测算法经证明对文本修改具有鲁棒性。
在实验方面，我们通过在机器翻译和文本摘要任务上评估生成文本的质量，验证了 DiPmark 保持分布的特性。值得注意的是，对于由 LLaMA-2 生成的 1000 个带水印的序列，检测时间仅为 90 秒，且不需要进行 API 访问。此外，即使面临 30% 的随机文本修改（包括插入、删除和替换操作），DiPmark 也表现出了鲁棒性。

表1

表1分析：

该表格对比了本文提出的 DiPmark 水印与之前相关工作（Kirchenbauer 等人 2023、Christ 等人 2023、Kuditipudi 等人 2023、Hu 等人 2023）在 ** 隐蔽性（Stealthy）、高效性（Efficient）、鲁棒性（Resilient）** 这三个关键特性上的表现。

隐蔽性：DiPmark、Christ 等人 2023 的方案符合要求（打勾）；Kirchenbauer 等人 2023、Kuditipudi 等人 2023、Hu 等人 2023 的方案不符合（打叉）。这说明 DiPmark 在不破坏文本自然分布、让水印难以被察觉方面，和 Christ 等人的工作效果一致，优于另外三者。
高效性：只有 DiPmark 和 Kuditipudi 等人 2023 的方案符合（打勾）；Kirchenbauer 等人 2023、Christ 等人 2023、Hu 等人 2023 的方案不符合（打叉）。意味着 DiPmark 在检测水印时，无需复杂操作（如频繁访问模型 API 等）、能快速完成检测的能力，与 Kuditipudi 等人的工作相当，比其他三者更高效。
鲁棒性：DiPmark、Kirchenbauer 等人 2023、Kuditipudi 等人 2023、Hu 等人 2023 的方案符合（打勾）；Christ 等人 2023 的方案不符合（打叉）。表明 DiPmark 在文本经历适度修改（如插入、删除、替换等）后，仍能保留并被识别出水印的能力，和除 Christ 等人外的其他工作一样可靠，强于 Christ 等人的方案。

整体来看，DiPmark 是唯一在 “隐蔽性、高效性、鲁棒性” 三个特性上都满足要求的水印方案，综合性能优于之前的相关研究。

第二章相关工作

在近期一项具有开创性的研究中，Kirchenbauer 等人（2023）提出了一种为大型语言模型（LLMs）量身定制的开创性水印方案。然而，这种方法不可避免地会导致生成文本的分布发生重大变化，可能会损害生成内容的质量。为了在带水印的内容中保持未受干扰的输出分布，研究人员探索了其他策略。Christ 等人（2023）和 Kuditipudi 等人（2023）采用了逆采样方法来生成带水印的标记分布。值得注意的是，Christ 等人（2023）的方法在面对修改或变更时存在鲁棒性问题，并且缺乏对可检测性的实证验证。同时，Kuditipudi 等人（2023）的方法在检测过程中需要密钥分布，这可能会损害数据安全性和水印的隐蔽性。此外，它们的检测过程涉及从密钥分布中进行数千次重采样步骤，这对于长文本来说是低效的。Hu 等人（2023）使用了基于逆采样和排列的重加权方法进行水印嵌入，但检测器需要语言模型 API 的标记对数概率，这降低了其操作效率。关于大型语言模型水印的详细讨论见附录 C。

我们的研究与 Kirchenbauer 等人（2023）的工作密切相关。在他们的方法中，他们通过将标记集分为 “红色” 和 “绿色” 列表，对来自语言模型的文本进行水印处理。在这一基础上，我们的研究保留了红 - 绿列表的配置，但引入了一系列改进的重加权策略。这种方法确保了：1）提高了绿色标记的利用率；2）带水印的语言模型生成的样本与原始语言模型生成的样本在分布上是等价的。

第三章预备知识

符号说明：为给后续讨论奠定基础，我们首先明确一些基本符号。用 V 表示词汇（或标记）集合，其大小记为 \(N = |V|\)。进一步引入集合 \(\mathcal{V}\)，它是所有可能字符串序列的集合，即便长度为零的序列也包含在内。在语言模型的场景中，模型会基于预先确定的上下文生成标记序列。对于这一过程中的单个步骤，在考虑当前上下文（从 \(x_1\) 到 \(x_n\)）的情况下，生成下一个标记 \(x_{n+1} \in V\) 的概率表示为 \(P_M(x_{n+1} \mid x_1, x_2, \dots, x_n)\)。大型语言模型（LLM）在设计上本身采用自回归的运行模式，这意味着生成多个标记（具体来说是从 \(x_{n+1}\) 到 \(x_{n+m}\)）的联合概率形式为： \(P_M(x_{n+1}, \dots, x_{n+m} \mid x_1, x_2, \dots, x_n) = \prod_{i=1}^{m} P_M(x_{n+i} \mid x_1, x_2, \dots, x_n, x_{n+1}, \dots, x_{n+i-1})\)

为简洁清晰起见，我们采用简化符号：\(P_M(\boldsymbol{x}_{n+1:n+m} \mid \boldsymbol{x}_{1:n})\)，其中 \(\boldsymbol{x}_{n+1:n+m} = (x_{n+1}, \dots, x_{n+m})\)。需要注意的是，在这种表示中，提示词被特意省略了。

在水印的场景下，服务提供商将使用密码空间 \(\Theta\) 上的一组独立同分布（i.i.d.）水印密码 \(\{\theta_i \in \Theta, i \in \mathbb{N}\}\) 来生成文本。密码 \(\theta_i\) 通常由密钥 k 和之前上下文的一个片段（称为纹理密钥 \(s_i\)）生成。每个 \(\theta_i\) 相互独立且服从相同分布 \(P_\Theta\)。大型语言模型带水印的输出服从分布 \(P_W(x_{n+1} \mid \boldsymbol{x}_{1:n}, \theta_n)\)，该分布同时以密码 \(\theta_n\) 和上下文 \(\boldsymbol{x}_{1:n}\) 为条件。我们将 \(P_W\) 称为水印的重加权策略。

红 - 绿列表水印

基于 Kirchenbauer 等人（2023）提出的软 / 硬红 - 绿列表，词汇集合被系统地分成红列表和绿列表。这一过程在采样时巧妙地突出了绿标记的使用。具体而言，为生成第 n 个标记 \(x_n\)，红列表和绿列表是通过对词汇集合 V 进行随机排列得到的。然后，在排列后的列表中插入一个预先定义的分隔符，使得排列后列表中前 \(\gamma \%\) 的标记构成红列表，其余 \(1 - \gamma \%\) 的标记构成绿列表。通过这种方式，密码空间 \(\Theta\) 涵盖了 V 的所有可能排列，其中 \(\theta_n\) 表示 V 的一种独特排列。在标记生成过程中，绿列表标记的概率会被提高，从而对生成的文本进行水印处理。为了检测水印，用户借助密钥，能够推断出红 - 绿列表，并通过红、绿标记数量的差异来确定水印是否存在。

重加权策略

重加权策略是水印算法的核心，从根本上决定了带水印文本的分布。如 Kirchenbauer 等人（2023）所述，作者提出了一种软重加权技术。给定初始标记概率 \(p(t)\)，标记的带水印概率记为 \(p'(t)\)，其公式为： \(p'(t) = \begin{cases} \frac{p(t)}{\sum_{t \in \text{red}} p(t) + \sum_{t \in \text{green}} e^\delta p(t)}, & t \in \text{红列表}; \\ \frac{e^\delta p(t)}{\sum_{t \in \text{red}} p(t) + \sum_{t \in \text{green}} e^\delta p(t)}, & t \in \text{绿列表}, \end{cases} \tag{1}\) 其中 \(\delta > 0\) 是预先确定的常数。对该策略的粗略分析表明，带水印的分布存在内在偏差。例如，考虑 \(\gamma = 0.5\)，即 V 的一半构成红列表。假设 \(V = \{a, b\}\)，且给定概率 \(p(a) = 0.99\)，\(p(b) = 0.01\)，那么 V 有两种等价的排列方式，出现的可能性相同。对任何 \(\delta > 0\) 进行分析，可得 \(p'(a) = 0.5 \left( \frac{e^\delta p(a)}{e^\delta p(a) + p(b)} + \frac{p(a)}{e^\delta p(b) + p(a)} \right) < p(a)\)。这就凸显出红 - 绿列表水印无法保留原始文本的概率。

保持分布性

若重加权策略 \(P_W\) 在单个生成步骤中是保持分布的，即对于所有 \(\boldsymbol{x}_{1:n} \in \mathcal{V}\) 和任何 \(i \leq n\)，都有 \(P_M(x_i \mid \boldsymbol{x}_{1:i-1}) = \mathbb{E}_{\theta_i \sim P_\Theta} [P_W(x_i \mid \boldsymbol{x}_{1:i-1}, \theta_i)]\)。进一步地，如果对于水印框架，在所有生成步骤中都保留了固有的文本分布，即对于所有序列 \(\boldsymbol{x}_{1:n} \in \mathcal{V}\) 和任何正整数 n，有 \(P_M(\boldsymbol{x}_{1:n}) = \mathbb{E}_{\theta_1, \dots, \theta_n} [P_W(\boldsymbol{x}_{1:n} \mid k, \theta_1, \dots, \theta_n)]\)，那么该水印就被认为是保持分布的。需要认识到，保持分布的重加权策略自然能带来保持分布的水印，如下所示： \(\begin{align*} \mathbb{E}_{\theta_1, \dots, \theta_n} [P_W(\boldsymbol{x}_{1:n} \mid k, \theta_1, \dots, \theta_n)] &= \mathbb{E}_{\theta_1, \dots, \theta_n} \left[ \prod_{i=1}^{n} P_W(x_i \mid \boldsymbol{x}_{1:i-1}, k, \theta_i) \right] \\ &= \prod_{i=1}^{n} \mathbb{E}_{\theta_i} [P_W(x_i \mid \boldsymbol{x}_{1:i-1}, k, \theta_i)] = P_M(\boldsymbol{x}_{1:n}). \end{align*} \tag{2}\) 上述等式源于集合 \(\{\theta_i\}\) 的独立性质。因此，要建立保持分布的水印，必须同时包含：a) 保持分布的重加权策略；b) 一组独立同分布（i.i.d.）的密码 \(\{\theta_i\}\)。

在我们的研究中，我们引入了一种具有 “保持分布” 特性的水印技术。这一特性确保，即使在水印过程中我们提高了绿列表标记的利用率，文本分布也能保持不变。

第四章 DiPMARK

动机：Kirchenbauer 等人（2023）提出的重加权策略在采样时优先使用绿标记，会破坏文本的固有分布。这种破坏会导致采样出现偏差，对生成文本的质量产生显著影响。我们的目标是构思一种新的重加权策略，确保在水印过程中标记分布保持不变。与 Kirchenbauer 等人（2023）中推广使用绿列表所有标记的方法不同，我们强调增加绿列表标记的概率总和。通过这种方式，当带水印的文本结合密钥时，仍会对绿列表标记表现出偏向性。基于这一思路，我们设计了一种特殊的重加权函数，它能在水印过程中保持文本分布。

水印的密码空间：我们所选的水印密码空间包含词汇集合的排列，记为 \(\Theta = \{V_1^p, \dots, V_{N!}^p\}\)，其中 \(V_i^p\) 代表 V 的一种排列。对于密码分布 \(P_\Theta\)，我们在 \(\Theta\) 上采用均匀分布，这意味着每种排列被选中的概率是相等的。

α- 重加权：设 \(\theta \in \Theta\) 为一个密码，它构成了 V 的一种排列。单个标记的概率可根据其在 \(\theta\) 中的各自位置，在区间 \([0, 1]\) 内进行排序。给定区间 \([0, 1]\) 内的一个固定常数 \(\alpha\)，区间 \([0, \alpha]\) 内的标记概率被调整为 0，而区间 \([\alpha, 1]\) 内的标记概率则按 \(\frac{1}{1 - \alpha}\) 的因子进行缩放。通过这一过程，对于任意排列分隔符 \(\gamma\)，我们提高了绿列表标记的概率总和，因为绿列表标记始终出现在有序集合 \(\theta\) 的末尾。如果我们将 \(\theta\) 表示为 \(\{t_1, \dots, t_N\}\)，并将 \(P_M(\cdot | \boldsymbol{x})\) 记为原始标记分布，令 \(F(i | \theta) = \frac{1}{1 - \alpha} \max\left\{ \sum_{j=1}^{i} P_M(t_j | \boldsymbol{x}) - \alpha, 0 \right\}\)。最终的 α- 重加权概率分布可表示为 \(P_W(t_i | \boldsymbol{x}, \theta) = F(i | \theta) - F(i - 1 | \theta)\)。

我们希望强调概率分位数 \(\alpha\) 与红 - 绿列表分隔符 \(\gamma\) 之间的区别。根据 Kirchenbauer 等人（2023）的定义，\(\gamma\) 作为排列后标记列表的划分依据。相比之下，\(\alpha\) 分隔的是排列后标记列表的概率区间 \([0, 1]\)。因此，α- 重加权和 DiP - 重加权（如下文定义）都与 \(\gamma\) 无关，但仍能有效促进绿列表标记的使用。

注记：分步描述 α- 重加权的过程，辅助理解：

步骤 1：确定原始标记及概率

假设词汇表 \(V = \{t_1, t_2, t_3, t_4\}\)，原始语言模型生成各标记的概率为

\(P_M(t_1) = 0.1\)
\(P_M(t_2) = 0.2\)
\(P_M(t_3) = 0.3\)
\(P_M(t_4) = 0.4\)

步骤 2：密码\(\theta\)对标记排序

密码 \(\theta\) 是 V 的一种随机排列，这里假设 \(\theta = [t_2, t_1, t_4, t_3]\)（即按 \(t_2\)、\(t_1\)、\(t_4\)、\(t_3\) 的顺序排列标记）。

按照 \(\theta\) 的顺序，将原始概率依次排列并计算累积概率区间（从 0 开始累加，直到和为 1）：

\(t_2\)：概率 0.2，对应累积区间 \([0, 0.2]\)
\(t_1\)：概率 0.1，对应累积区间 \([0.2, 0.3]\)
\(t_4\)：概率 0.4，对应累积区间 \([0.3, 0.7]\)
\(t_3\)：概率 0.3，对应累积区间 \([0.7, 1.0]\)

步骤 3：设置 α 并切割、调整概率

设定 \(\alpha = 0.3\)（即累积概率的 30% 位置为切割点），执行以下操作：

（1）屏蔽前\(\alpha\)区间的标记

累积概率区间 \([0, 0.3]\) 内的标记是 \(t_2\)（区间 \([0, 0.2]\)）和 \(t_1\)（区间 \([0.2, 0.3]\)），这部分标记的概率被强制设为 0。

（2）缩放后\(1-\alpha\)区间的标记

累积概率区间 \([0.3, 1.0]\) 内的标记是 \(t_4\)（区间 \([0.3, 0.7]\)）和 \(t_3\)（区间 \([0.7, 1.0]\)）。这部分标记的概率总和原本是 \(0.4 + 0.3 = 0.7\)，现在要让它们的概率总和重新为 1，所以需要按 \(\frac{1}{1 - \alpha} = \frac{1}{0.7} \approx 1.428\) 倍缩放：

\(t_4\)：原概率 0.4 → 缩放后 \(0.4 \div 0.7 \approx 0.571\)
\(t_3\)：原概率 0.3 → 缩放后 \(0.3 \div 0.7 \approx 0.429\)

最终结果

经过 α- 重加权后，各标记的概率变为：

\(t_1\)：0
\(t_2\)：0
\(t_4\)：\(\approx 0.571\)
\(t_3\)：\(\approx 0.429\)

可以看到，排列在 \(\theta\) 后半段的标记（\(t_4\)、\(t_3\)，即绿列表标记）概率被提升，而前半段标记（\(t_2\)、\(t_1\)，即红列表标记）概率被屏蔽。但由于 \(\theta\) 是随机均匀排列的，对所有可能的 \(\theta\) 取平均后，每个标记被 “提升” 或 “屏蔽” 的概率均等，整体分布会和原始模型一致，保证了水印的隐蔽性；只有知道具体 \(\theta\)（通过密钥），才能检测到绿列表标记的概率偏向，验证水印。

你可能会有疑问：如果t1=0.5,t2=0.4,t3=0.05,t4=0.05，这样生成的水印不是会影响文本的质量吗？

1. 单次 α- 重加权可能 “扭曲” 局部选择，但这是可控的

假设密码 \(\theta\) 的排列是 \([t_1, t_2, t_3, t_4]\)，设定 \(\alpha=0.3\)：

累积区间 \([0, 0.3]\) 对应 \(t_1\) 的部分概率（0.5 中的前 0.3），这部分会被屏蔽；
剩余区间 \([0.3, 1.0]\) 包含：\(t_1\) 的剩余概率（0.2）、\(t_2\)（0.4）、\(t_3\)（0.05）、\(t_4\)（0.05），总和为 0.7；
缩放后，这部分概率会被放大到 1，即 \(t_1\) 剩余概率变为 \(0.2/0.7≈0.286\)，\(t_2\) 变为 \(0.4/0.7≈0.571\)，\(t_3\) 和 \(t_4\) 各变为 \(0.05/0.7≈0.071\)。

此时，单次生成中 \(t_2\) 的概率反而高于原始的 \(t_1\)，看起来确实 “扭曲” 了分布。但这只是单次基于特定密码 \(\theta\) 的结果。

2. 多次密码平均后，分布回归原始，不影响文本质量

DiPmark 的密码 \(\theta\) 是所有可能排列的均匀分布（即每种排列被选中的概率相等）。对于你举的例子，当考虑所有可能的 \(\theta\) 排列时：

每个标记在 \(\theta\) 中 “靠前被屏蔽” 和 “靠后被放大” 的概率是均等的；
对所有排列的重加权结果取平均后，每个标记的概率会精确回归原始分布（数学上可证明）。

比如 \(t_1\) 原始概率 0.5，在所有排列中，它有时被屏蔽、有时被放大，但平均后仍为 0.5；同理，\(t_2\) 平均后仍为 0.4，以此类推。

本质：“局部波动” 不影响 “整体均衡”

就像抛硬币时，单次可能出现正面或反面（局部波动），但大量抛掷后正反概率仍趋近 50%（整体均衡）。DiPmark 正是通过这种机制，让单次生成可能偏向绿列表标记（实现水印），但整体文本分布与原始模型一致（保证质量）。

因此，即使原始概率分布不均衡，DiPmark 也能在嵌入水印的同时，不影响文本的自然性和质量。

算法 1：DiPmark 生成器

输入：水印密钥 \(k \in K\)、重加权参数 \(\alpha\)、提示词 \(\boldsymbol{x}_{-m:0}\)、生成长度 \(n \in \mathbb{N}\)、纹理密钥历史 hist 以及排列生成函数 h。
循环：对于 \(i = 1, \dots, n\)：
- 计算语言模型（LM）生成第 i 个标记的分布 \(P_M(\cdot \mid \boldsymbol{x}_{-m:i-1})\)。
- 基于 \(\boldsymbol{x}_{1:i-1}\) 生成纹理密钥 \(s_i\)。
- 条件判断：如果 \(s_i \in hist\)，则使用原始语言模型分布 \(P_M(\cdot \mid \boldsymbol{x}_{-m:i-1})\) 采样下一个标记 \(x_i\)。
- 否则：
  - 生成标记集的排列 \(\theta_i = h(k, s_i)\)。
  - 结合 \(\alpha\) 和定义 4.1，计算 DiP - 重加权 \(P_W(\cdot \mid \boldsymbol{x}_{-m:i-1}, \theta_i)\)。
  - 使用分布 \(P_W(\cdot \mid \boldsymbol{x}_{-m:i-1}, h(k, s_i))\) 采样下一个标记 \(x_i\)。
输出：返回生成的序列 \(\boldsymbol{x}_{1:n}\)。

利用排列的固有对称性，我们可以证明，\(\alpha\)- 重加权和 \((1 - \alpha)\)- 重加权的加权组合能产生一种保持分布的重加权策略。关键要认识到，\(\alpha\)- 重加权和 \((1 - \alpha)\)- 重加权都会放大绿列表标记的概率总和。因此，这些重加权函数的组合效果仍然会对绿列表标记表现出偏好。我们的保持分布重加权策略的形式化表述随后呈现。

定义 4.1（DiP - 重加权）：给定原始标记分布 \(P_M(t \mid \boldsymbol{x})\)，对所有 \(t \in V\)，其中 \(\boldsymbol{x} \in \Sigma\) 是之前的标记序列。记 \(\theta = \{t_1, \dots, t_N\}\) 为密码（即 V 的一种排列）。令： \(F(i \mid \theta) := \max\left\{ \sum_{j=1}^{i} P_M(t_j \mid \boldsymbol{x}) - \alpha, 0 \right\} + \max\left\{ \sum_{j=1}^{i} P_M(t_j \mid \boldsymbol{x}) - (1 - \alpha), 0 \right\}, \quad i \in [1, N], \tag{3}\) 其中 \(0 < \alpha < 1\)。DiP - 重加权策略可表示为 \(P_W(t_i \mid \boldsymbol{x}, \theta) := F(i \mid \theta) - F(i - 1 \mid \theta)\)，且 \(F(0 \mid \theta) := 0\)。

容易证明 \(P_W(t_i \mid \boldsymbol{x}, \theta)\) 是 V 上的分布。首先，由于 \(F(i \mid \theta)\) 随 i 单调递增，故 \(P_W(t_i \mid \boldsymbol{x}, \theta) = F(i \mid \theta) - F(i - 1 \mid \theta) \geq 0\)。其次，所有标记的概率和为 \(\sum_{i=1}^{N} P_W(t_i \mid \boldsymbol{x}, \theta) = \sum_{i=1}^{N} (F(i \mid \theta) - F(i - 1 \mid \theta)) = F(N \mid \theta) = 1 - \alpha + \alpha = 1\)。

定理 4.2：DiP - 重加权是一种保持分布的重加权策略

我们将定理 4.2 的证明推迟到附录 D。借助 DiP - 重加权方法，独立同分布（i.i.d.）密码（记为\(\theta_i\)）的生成对于构建保持分布的水印至关重要。

令k表示从密钥空间K中依据分布\(P_K\)生成的随机密钥，令\(s \in \mathcal{V}\)为纹理密钥，它是先前生成上下文的子序列。考虑在时间步t之前生成的上下文（记为\(\boldsymbol{x}_{1:t-1}\)），纹理密钥的实例包括\(x_{t-1}\)、\(x_{t-3:t-1}\)和\(\boldsymbol{x}_{1:t-1}\)。我们引入一个哈希函数\(h(k, s): K \times \mathcal{V} \to \Theta\)，用于协调秘密密钥与纹理密钥的映射，从而得到标记集V的一个排列。所选的哈希函数h必须满足以下条件： a) 对于不同的纹理密钥，即\(s_1 \neq s_2\)，当\(k \sim P_K(k)\)时，\(h(k, s_1)\)应与\(h(k, s_2)\)统计独立； b) 在保持s不变的情况下，对于任意\(V_i^p \in \Sigma\)，在给定随机密钥时，都有均等的被选中概率，具体而言，\(\forall V_i^p \in \Sigma\)，\(\mathbb{E}_{k \sim P_K}[1_{h(k, s) = V_i^p}] = 1/N!\)。

存在满足上述条件的哈希函数，Kirchenbauer 等人（2023）所阐述的函数就是一个例子。在这种情况下，如果每个实例的纹理密钥\(s_i\)都是独特的，那么密码\(\theta_i\)可被视为独立同分布的。为确保这种唯一性，会使用一个寄存器来保留之前步骤中生成的纹理密钥。如果识别出重复的纹理密钥（在历史记录中存在），后续的标记生成将使用固有分布；否则，将应用 DiP - 重加权进行标记生成。详细的方法在算法 1 中进行了阐述。

推论 4.3：DiPmark（算法 1）是一种保持分布的水印

这一点可通过结合 DiP - 重加权的保持分布特性与密码\(\theta_i\)的独立性轻松验证。

算法 2：DiPmark 检测器

输入：文本\(\boldsymbol{x}_{1:n}\)、水印密钥k、标记集的大小N、排列生成函数h、绿列表分隔符\(\gamma\)、阈值z。
初始化绿标记计数器（基于\(\gamma\)）为0：\(L_G(\gamma) = 0\)。
循环：对于\(i = 2, \dots, n\)：
- 基于\(\boldsymbol{x}_{1:i-1}\)生成纹理密钥\(s_i\)。
- 生成标记集的排列\(\theta_i = h(k, s_i)\)。
- 通过\(G = \theta_i[\lfloor \gamma N \rfloor: N]\)计算绿标记列表。
- 条件判断：如果\(x_i \in G\)，则绿标记计数器加1：\(L_G(\gamma) = L_G(\gamma) + 1\)。
计算得分：\(\Phi(\gamma, \boldsymbol{x}_{1:n}) = \frac{L_G(\gamma) - (1 - \gamma)n}{\sqrt{n}}\)。
输出：返回\(\Phi(\gamma, \boldsymbol{x}_{1:n}) > z\)（即判断得分是否超过阈值，以确定是否存在水印）。