論文「Can we Watermark Low-Entropy LLM Outputs?」の技術的サマリー

この論文は、大規模言語モデル（LLM）の出力に対する**「検出不可能かつ頑健な透かし（Watermarking）」**を、**低エントロピー（Low-Entropy）**の出力に対しても実現可能にするための新しい枠組みを提案するものです。従来の研究は、LLM の出力トークンに高いエントロピー（多様性）があることを強く仮定していましたが、本論文はその制約を緩和し、実用的な自然言語生成（多くのトークンが低エントロピーである場合）でも機能する透かし方式を構築しました。

以下に、問題設定、手法、主要な貢献、結果、および意義について詳述します。

1. 問題設定と背景

背景:
LLM による生成コンテンツの増加に伴い、AI 生成物を人間が作成したものと区別する「透かし」技術が重要視されています。理想的な透かしは以下の特性を持つべきです。

1. 検出不可能性 (Undetectability): 透かしを埋め込んだことで、LLM の出力分布が変化せず、統計的に検出できないこと。
2. 頑健性 (Robustness): 敵対者が出力を編集（置換、挿入、削除）して透かしを除去しようとしても、検出可能であること。

既存研究の限界:
近年の透かし研究（Christ et al. [CGZ24], [CG24], Golowich et al. [GM24] など）は、以下のいずれかの強い仮定を必要としていました。

• 高エントロピーの仮定: 出力の一定割合のトークンが、辞書サイズ $|T|$ に対して対数的なエントロピー（$O(\log |T|)$）を持つこと。
• 辞書サイズの制約: 辞書サイズ $|T|$ がセキュリティパラメータよりも十分に大きいこと。
• ヘリスティックな仮定: 出力が「十分に可変的（sufficiently variable）」であること（エラー分布が対称チャネルのように振る舞うこと）。

しかし、実際の自然言語では、多くのトークンが文脈的に予測可能であり、エントロピーが非常に低い（例：1 ビット程度、あるいはそれ以下）ことが一般的です。従来の方式は、このような低エントロピーの出力に対しては頑健性を保証できず、あるいは辞書サイズを大きくすることでエントロピー要件を無理やり満たす必要があり、実用性に欠けていました。

本研究の問い:
「辞書サイズやセキュリティパラメータに依存せず、トークンあたりのエントロピーが定数（例：1 ビット）であっても、検出不可能かつ頑健な透かしは可能か？」

2. 手法と技術的アプローチ

本研究は、**疑似ランダムコード（Pseudorandom Code: PRC）**を基盤とした透かし方式を提案します。PRC は、暗号学的にランダムに見える（検出不可能）かつ、誤り訂正能力を持つ（頑健）符号です。

2.1 基本的なアイデア：ハッシュによる二値化

従来の [CG24] は二値アルファベット（0/1）の出力を想定し、PRC のビットを直接埋め込んでいました。これを大辞書（トークン集合 $T$）に拡張する際、単純にトークンを二値化するとエントロピー要件が跳ね上がります。

本研究の核心は、トークンを直接二値化せず、ランダムなハッシュ関数 $h: T \to \{0, 1\}$ を用いてトークンをビットに変換し、そのビットに PRC のコードワードを埋め込むというアプローチです。

• 埋め込みプロセス:
  1. LLM の次のトークン分布 $D$ から 2 つの独立したトークン $t_0, t_1$ をサンプリングします。
  2. ハッシュ値 $h(t_0)$ と $h(t_1)$ を比較します。
     • 成功 (Success): $h(t_0) \neq h(t_1)$ の場合、PRC の対応するビット $c_i$ に一致する方（$h(t_b) = c_i$）を出力します。この場合、分布を歪めることなく意図したビットを埋め込めます。
     • 失敗 (Failure): $h(t_0) = h(t_1)$ の場合、ランダムに一方を選びます。この場合、埋め込みビットと一致しない確率（誤り）が 1/2 発生します。
  3. このプロセスを、PRC の 1 つのコードワードに対応するトークンブロックごとに同じハッシュ関数 $h$ を使いながら繰り返します。

2.2 エントロピー要件の緩和

この手法の鍵は、**「エントロピーが 1 ビット以上あるトークン」**の存在です。

• トークン $t_i$ のエントロピーが 1 以上であれば、$D(t_i) \le 1/2$ です。
• このとき、$t_0 = t_1 = t_i$ となる確率は最大でも 1/2 です。
• 結果として、$h(t_0) \neq h(t_1)$ となる確率（成功確率）が一定以上（少なくとも 1/4）保たれ、誤り率が 1/2 を下回ることを示せます。
• これにより、**「出力の一定割合のトークンが 1 ビットのエントロピーを持つ」**という極めて緩い条件（定数エントロピー）だけで、PRC の復号が可能になることが証明されます。

2.3 削除・挿入への頑健性

• 置換のみ: 各トークンごとに独立したハッシュ関数を使えば解析は容易ですが、削除・挿入には脆弱です。
• 削除・挿入への対応: 本研究では、1 つの PRC コードワード（ブロック）に対して同じハッシュ関数 $h$ を再利用します。これにより、ブロック内のトークンが削除されても、残ったトークンに対して同じ $h$ を適用して復号を試みることができます。
• 課題と解決: 同じ $h$ を使うと、トークンの相関により誤りが相関するリスクがあります。これを回避するため、以下の 2 つのアプローチを提案しています。
  1. ヒューリスティック仮定（自然なプロンプト）: 出力のエラー分布が「対称二値チャネル」のように振る舞うと仮定する（[CG24] の拡張）。
  2. 強固な PRC の利用: 敵対的な置換とランダムな削除に耐性を持つ PRC（[CGG+25] の構成）を利用し、ヒューリスティック仮定なしで頑健性を証明する。

3. 主要な貢献と結果

本研究は、以下の定理と帰結（Corollary）を通じて、低エントロピー環境での透かし実現を証明しました。

3.1 主要な定理（Informal）

• 定理 1（置換耐性）: 二値 PRC が敵対的な置換に耐性を持つなら、大辞書 LLM に対して、**定数エントロピー（1 ビット）**の出力でも、ランダム置換（最大 1/2 未満）に頑健な透かしが構築可能。
• 定理 2（置換・削除耐性・ヒューリスティック）: 自然なプロンプト（エラー分布が対称チャネル的）を仮定すれば、ランダム置換とランダム削除の両方に頑健な透かしが構築可能。
• 定理 3（置換・削除耐性・非ヒューリスティック）: 敵対的な置換とランダムな削除に耐性を持つ二値 PRC が存在すれば、ヒューリスティック仮定なしで同様の頑健性が得られる。
• 定理 4（編集耐性）: 敵対的な置換と編集（挿入・削除）に耐性を持つ PRC（[CGG+25]）を利用することで、敵対的な編集にも耐性を持つ低エントロピー透かしを構築可能（ただし、必要な最小エントロピー部分文字列の長さは増加）。

3.2 既存研究との比較（図 1 要約）

• 重要な点: 本研究は、出力を二値化してビット単位で攻撃を定義するのではなく、**トークン単位での攻撃（言い換え、削除など）**を直接モデル化し、かつ低エントロピーを許容する点で画期的です。

4. 意義と結論

1. 実用性の向上:
   自然言語の多くは低エントロピーです。従来の方式が要求する「高いエントロピー」や「大きな辞書サイズ」の仮定は現実的ではありませんでした。本研究は、実世界の LLM 出力（定常的な文脈や反復的な表現を含む）に対しても、透かしを埋め込み、かつ編集に対して検出可能にすることを初めて示しました。

2. 攻撃モデルの現実化:
   従来の二値化アプローチでは、ビット単位のランダムな誤りが「トークン単位のランダムな誤り」に対応しないという問題がありました。本研究は、トークンレベルでの置換（類義語への置換など）や削除を直接扱えるモデルを構築し、より現実的な攻撃に対する頑健性を保証します。

3. 理論的限界の克服:
   「低エントロピー」と「高い頑健性」は両立しないと考えられていましたが、ハッシュ関数の再利用と PRC の特性を巧みに組み合わせることで、このジレンマを解決しました。

4. 今後の課題:

   • 敵対的な編集（挿入・削除）に対して完全な頑健性を得るためには、[CGG+25] のような特殊な PRC 構成が必要であり、そのパラメータ（許容される編集率）がまだ小さいという制限があります。
   • 「自然なプロンプト」の形式的な定義や、より一般的なエントロピー条件での完全な解決は、今後の研究課題です。

結論:
本論文は、LLM 透かし技術において、**「低エントロピー出力」**という長年のボトルネックを克服し、実用的な攻撃モデルに対して検出不可能かつ頑健な透かしを実現する最初の体系的な枠組みを提供しました。これは、AI 生成コンテンツの追跡と信頼性確保において、極めて重要な進展です。