Optimal Watermark Localization in Mixed-Source Large Language Model Texts

技術要約：混合ソースの大型言語モデル（LLM）テキストにおける最適なウォーターマーク局所化

問題定式化
ウォーターマーク（電子透かし）は、テキストの真正性を保証するための原理的な手法であるが、現実世界のアプリケーションでは、人間の編集（書き換え、挿入、削除、パラフレーズ）によって元のウォーターマーク信号が乱される「混合ソース」のテキストが含まれることが多い。先行研究は、テキスト内に（集計として）ウォーターマークの証拠が「存在するかどうか」を判定する「グローバルな検出（global detection）」に焦点を当ててきた。しかし、ウォーターマークの局所化（どのトークン位置がウォーターマーク信号を保持しているかを正確に特定すること）の統計的限界については、依然として不明である。

著者らは、ウォーターマークの局所化をトークンレベルの多重検定問題として定式化している。長さ $n$ のテキストに対し、検証者は一連のピボタル統計量 $Y_{1:n}$ を観測する。各位置 $t$ において、潜在的なインジケーター $\theta_t \in \{0, 1\}$ が状態を決定する：

• $\theta_t = 1$：ウォーターマークへの依存性が編集後も生存している。このとき $Y_t$ は、局所的な次トークン予測（NTP）分布 $P_t$ によって決定される代替分布 $\mu_{1, P_t}$ に従う。
• $\theta_t = 0$：依存性が消失している。このとき $Y_t$ は、$P_t$ に依存せず、既知の帰無分布 $\mu_0$ に従う。

目標は、潜在的なシーケンス $\theta_{1:n}$ を推論することであり、以下の3つの、段階的に難易度が上がる推論タスクを区別する：

1. グローバル検出 (Global Detection): 少なくとも一つの $\theta_t = 1$ が存在するかどうかを判定する。
2. 発見 (Discovery): 周辺的な偽発見率（mFDR）が消失することを保証しつつ、$\theta_t = 1$ である位置の非自明な集合を特定する。
3. 分類 (Classification): すべての帰無位置と、すべてのウォーターマーク保持位置を漸近的に分離する（mFDRおよび見逃された発見率（Missed Discovery Rate）の両方を消失させる）。

手法：SPOT
本論文では、問題の漸近パラメータ（スパース性、信号強度、語彙の成長）や時変的なNTP分布に関する事前知識を必要とせずに、発見を実現するように設計された適応型局所化手法である SPOT (Scanning Pivots Over Thresholds) を提案する。

• メカニズム: SPOTは、ピボタル統計量に適用される裾（tail）の閾値をグリッド状にスキャンする。各候補閾値に対して、生存しているウォーターマーク信号の割合（$\hat{\varepsilon}_n$）を推定し、経験的な裾の質量に基づく代理の偽発見レベルを計算する。
• 適応性: 本手法は、真の割合を入力として要求するのではなく、データ駆動型の生存割合の推定値（例：Li et al. [26] によるもの）を用いて、推定された偽発見レベルが目標値 $\lambda_n$ を下回るような最大の発見集合を選択する。
• 主な利点: 異質な代替分布の密度推定（未知で時変的なNTPのため実行不可能）を必要とする手法とは異なり、SPOTはピボタル統計量の裾のカウントを用いることで偽発見を制御する。

理論的貢献と結果
著者らは、3つの指数によって索引付けされた漸近レジームの下で、3つの推論目標に関する鋭い相転移を確立した：

• $p$: 生存信号のスパース性 ($\varepsilon_n \asymp n^{-p}$)。
• $q$: NTP分布の集中度 ($1 - \max P_{t,w} \asymp n^{-q}$)。
• $\alpha$: 有効な低確率語彙の裾の成長率 ($|W_n| \asymp n^\alpha$)。

1. 検出境界 (Detection Boundary): グローバル検出が可能となるのは、$\max\{p + q, 2p + q - \alpha\} < 1$ の場合、かつその時に限る。これは、成長する語彙の裾（$\alpha > 0$）が集計的な証拠を提供することで、グローバル検出を助けることを示しており、固定語彙による従来の結果を一般化している。
2. 発見境界 (Discovery Boundary): 発見が可能となるのは、$p < \alpha$ かつ $p + q < 1$ の場合、かつその時に限る。
   • 条件 $p < \alpha$ は局所化に特有のものである。これは、個々のウォーターマーク保持トークンを帰無位置から区別するためには、語彙の裾が信号のスパース性に対して十分に速く成長する必要があることを意味する。
   • 厳格な困難性: 発見はグローバル検出よりも厳格に困難である。グローバルに検出可能であっても、単一のウォーターマーク保持位置すら信頼性を持って発見できないルールが存在するレジーム（具体的には $\alpha = 0$ の場合）が存在する。
3. 分類の不可能性 (Impossibility of Classification): 著者らは、座標ごとのピボットベースのルールのクラスにおいて、一貫した分類は全パラメータレジームを通じて不可能であることを証明した。
   • 理由: 弱い信号をすべて回収しようとする（見逃された発見を最小化する）ルールは、必然的に多くの帰無位置を選択してしまい（mFDR制御に失敗する）、逆に保守的なルールはmFDRを制御するが、相当数の信号を見逃す。この不整合が、帰無位置と信号位置の漸近的な分離を妨げている。
4. SPOTの最適性:
   • 境界の最適性: SPOTは、パラメータ $p, q, \alpha$ を知ることなく、理論的に発見可能な領域全体（$p < \alpha, p + q < 1$）において発見を達成する。
   • 近最適な検出力: 均質なピボットベースのルールの中で、SPOTは、低次項を除いて、最大可能な真の発見数の一定の割合を回収する。

実証的検証

• シミュレーション: ピボタル統計量を用いた合成実験により、理論的な相転移が確認された。パラメータが理論的境界（$p = \alpha$ および $p + q = 1$）を越えると、経験的な発見エラーが急激に増加する。
• LLM実験: コントロールされた編集（ランダムな置換/挿入/削除、敵対的編集、往復翻訳）を施したC4データセットのテキストに対し、OPT-1.3Bを用いて実験を行った：
  • SPOT（オラクル版およびプラグイン版の両方）は、ランダムおよび敵対的編集の下で、Intersection-over-Union (IoU) および真陽性率 (TPR) において、ベースラインであるAdaptive Online Locator (AOL) [61] を一貫して上回った。これは特に高い生成温度（$T=1$）において顕著であった。
  • 低温においては、すべての手法で性能が低下するが、SPOTのオラクル版とプラグイン版の差が広がる。この分析により、これは局所化ルール自体の失敗ではなく、NTPが高度に集中する低温環境における生存割合の推定値の不正確さに起因することが明らかになった。
  • SPOTの計算オーバーヘッドは、ベースラインと比較して無視できる程度である。

意義と主張
本論文は、混合ソースのLLMテキストにおけるウォーターマーク局所化の根本的な限界を特徴付ける、初の統計理論を提供したと主張している。その主な貢献は以下の通りである：

1. 理論的限界: 局所化は検出よりも厳格に困難であり、完全な分類は標準的な座標ごとのルールの下では不可能であることを確立し、局所化が可能となる正確な「相転移」を定義した。
2. 適応的最適性: 下層の生成パラメータや編集パラメータを知ることなく、理論的限界を達成できる適応的でデータ駆動型の手法（SPOT）を実証した。
3. 実用的有用性: 完全な分類という理論的な不可能性があるにもかかわらず、生存している信号の堅牢な局所化は達成可能であり、一般的な人間による編集メカニズムの下で実用的に有効であることを示した。

著者らは、本研究がピボタル統計量を用いたトークンレベルの局所化に焦点を当てており、新しいウォーターマーク・スキームを提案するものではないことを注記している。今後の方向性として、オンライン/ストリーミングでの局所化、ブロック構造を持つ編集への対応、およびセマンティック（意味論的）またはセンテンスレベルのウォーターマークへの理論の拡張を挙げている。