DIPMARK：一種隱蔽、高效且具備魯棒性的大語言模型水印技術

摘要

水印技術為通過在數據中嵌入隱蔽信息來保障數據安全提供了一種很有前景的方法。該領域的一個首要挑戰在于，在水印嵌入過程中保持原始數據的分布。我們的研究拓展并優化了現有的水印框架，著重強調了保持分布（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\)（即判斷得分是否超過閾值，以確定是否存在水印）。