Fast segmentation of watermarked texts from large language models through an epidemic change-point framework

技術要約：エピデミック・チェンジポイント・フレームワークによる大規模言語モデルからのウォーターマーク付きテキストの高速セグメンテーション

問題提起
大規模言語モデル（LLM）の普及に伴い、真正性、著作権、および学術的誠実性に関する懸念に対処するため、機械生成コンテンツを検出するための堅牢なメカニズムが必要となっている。ウォーターマーキング手法（秘密鍵を用いてトークン生成に統計的信号を埋め込む手法）は、LLM生成テキストの「存在」を検出するために開発されてきたが、混合ソースのテキスト（人間と機械の両方によって生成されたコンテンツを含むもの）内において、特定のウォーターマーク付きセグメントを「局在化」するという、より微細なタスクについては未だ十分に研究されていない。既存のセグメンテーション・アルゴリズムは、長いテキストに対しては計算複雑性が高すぎて不適切であったり、パラフレーズや後編集に対して堅牢な理論的保証を欠いていたりすることが多い。さらに、現在の手法は、単一の文書内に存在する複数の離れたウォーターマーク区間を効率的に特定することに苦慮している。

手法：エピデミック・チェンジポイントの視点
著者らは、ウォーターマークのセグメンテーション問題をエピデミック・チェンジポイント（流行型変化点）検出問題として再定義するアルゴリズム、WISER（Watermark Identification via Segmenting Epidemic Regions）を提案する。

1. ピボット統計量と上昇した代替仮説: この手法は、生成されたトークンと擬似乱数キーの関数である「ピボット統計量」（$Y_t$）に依存している。帰無仮説（人間が生成した／ウォーターマークが付与されていないトークン）の下では、これらの統計量は既知の定常分布に従い、平均 $\mu_0$ を持つ。代替仮説（ウォーターマークが付与されたトークン）の下では、統計量は「上昇した代替仮説」の特性を示し、LLMの特定の次トークン分布（NTP）に関わらず、期待値が $\mu_0$ よりも厳密に大きな値 $d$ だけ上昇する。
2. エピデミック・モデリング: 変化が永続的に続く標準的なチェンジポイント問題とは異なり、ウォーターマーキングは「エピデミック（流行）」的な区間を作り出す。すなわち、ピボット統計量の平均が特定の連続するセグメント（ウォーターマーク）の間で上昇し、そのセグメントの外側ではベースラインに戻る。
3. アルゴリズム設計:
   • 単一セグメント推定器: 単一のウォーターマーク・パッチに対して、候補となる区間の外部にある偏った余剰を最小化する推定器を適応させる。候補区間の外側にある統計量の和からバッファ項（$\rho \tilde{d}$）を差し引くことで、非ウォーターマーク・トークンを含めることをペナルティとし、上昇したウォーターマーク・トークンを除外することを報酬とする。
   • マルチセグメント戦略 (WISER): セグメントの数（$K$）に関する事前知識なしに複数のセグメントを扱うため、WISERは4段階のパイプラインを採用している。
     • ブロッキング (Blocking): テキストをブロックに分割する。合計値が閾値 $Q$ を超えるブロックを保持する。
     • 破棄 (Discarding): 保持されたブロックの連結成分を形成する。短い成分（偽陽性の可能性が高いもの）は、長さの閾値（$c\sqrt{\log n}$）に基づいて破棄される。
     • 拡張 (Enlargement): 残った連結領域を $\sqrt{n}$ の係数で拡張し、真のウォーターマーク・セグメントを完全にカバーすることを確実にする。
     • 精緻な局所探索 (Refined Local Search): これらの拡張された領域内で、単一セグメント推定器を適用して開始点と終了点を正確に特定する。
   • 計算効率: スクリーニング段階から導出された拡張領域に探索空間を制限することで、WISERは$O(n)$の計算複雑性を達成しており、これは理論的に保証された最初の線形時間計算量のセグメンテーション・アルゴリズムである。

主な貢献

• 斬新な視点: 本論文は、ウォーターマークの局在化とエピデミック・チェンジポイント検出との間の形式的な関連性を確立しており、このフレームワークはこれまでこの領域では活用されていなかった。
• 理論的保証: 著者らは、有限サンプルにおける誤差境界を提供し、WISERが複数のウォーターマーク・セグメントを検出することの整合性を証明している。定理3.1は、推定された区間と真の区間の対称差が $O((\rho \tilde{d})^{-1})$ の速度でゼロに収束することを確立している。定理4.1はこれをマルチセグメントのケースに拡張し、WISERが $n \to \infty$ において高い確率でセグメントの数とその位置を正しく特定することを証明している。
• アルゴリズムの革新性: WISERは、一般的なマルチセグメントのウォーターマーク局在化に対して、理論的な妥当性を証明しつつ、$O(n)$ の計算効率を維持する初めてのアルゴリズムである。
• 堅牢性: 本手法は、特定のLLMアーキテクチャやNTPに依存せず、ピボット統計量と上昇した代替仮説の特性のみに依存するように設計されている。

実験結果
様々なLLM（OPT、Gemma、Llama-3、Mistralなど）および多様なウォーターマーキング・スキーム（Gumbel、Inverse Transform、Red-Green、Permute-and-Flip）を用い、ベンチマーク・データセット（C4 News）に対して広範な数値実験が行われた。

• 精度: WISERは、Intersection-over-Union (IoU)、適合率（Precision）、再現率（Recall）、F1スコアを含むすべての指標において、最先端のベースライン（Aligator、SeedBS-NOT、Waterseeker）を一貫して上回った。多くのシナリオにおいて、WISERは「オラクル（Oracle）」推定器（真のセグメント数 $K$ を既知と仮定するもの）に近い性能を達成した。
• 速度: 実験的な実行時間分析により、理論的な $O(n)$ の複雑性が確認された。WISERは、超線形または二次的なスケーリングを示す競合手法よりも大幅に高速であった。
• 堅牢性: アルゴリズムは、トークン生成における様々なレベルの時間的依存関係の下でも高い性能を維持し、混合ソースのテキストにおける人間の編集（置換、挿入、削除）に対する耐性を示した。

意義と主張
本論文は、WISERをAIモデレーションおよびコンテンツ検証のための重要なツールとして位置づけている。著者らは、古典的な統計理論（エピデミック・チェンジポイント）と現代の生成AIの課題を橋渡しすることで、理論的に妥当であり、かつ計算効率が高いソリューションを生み出したと主張している。

その意義は、既存の手法が長い文書に対する実用的な展開には遅すぎたり、厳密な統計的保証を欠いていたりしたという、文献上のギャップに対処している点にある。著者らは、自身のアプローチが特定のLLMアーキテクチャの知識を必要としないことを強調しており、これにより、混合された人間とAIのテキストを含む現実世界のシナリオにおいて、ウォーターマーク付きコンテンツを検出および局在化するための汎用的なソリューションを提供している。また、本研究は、標準的なチェンジポイント検出の文献とは異なる特徴である、ウォーターマーク付きトークン配列の非定常性を扱うためのピボット統計量の有用性を浮き彫りにしている。