P$^2$RAG: Efficient Privacy-Preserving RAG Service Supporting Arbitrary Top-$k$ Retrieval

P2RAG の技術的概要：任意の Top-k 検索をサポートする効率的なプライバシー保護型 RAG サービス

問題定義
検索拡張生成（RAG）は、大規模言語モデル（LLM）が外部知識を利用することを可能にしますが、RAG サービスの外部委託は、データ所有者（その専有データベースが露出する）とユーザー（そのプロンプトが可視化される）の両方にとって重大なプライバシーリスクをもたらします。既存のプライバシー保護型 RAG（PP-RAG）システムは、通常、この問題を安全な Top-k 検索タスクとして捉え、安全なソートまたは安全な k-近似最近傍（k-ANN）技術に依存しています。しかし、これらのシステムには以下の決定的な限界があります：

1. 柔軟性の欠如：検索パラメータ $k$ に対する任意または動的な調整をサポートできないことが多い。
2. 効率性の低下：$k$ が増加するにつれてパフォーマンスが著しく低下する。これは、現代の金融、法務、医療分野のアプリケーションや長文脈 LLM が、最適な精度を達成するためにしばしば大きな $k$ 値（例：100〜150 以上）を必要とするため、重大なボトルネックとなる。
3. セキュリティの隙間：一部の既存のアプローチは新たなセキュリティ問題を引き起こすか、悪意のあるユーザーに対する情報漏洩の厳密な制限に失敗している。

手法
著者は、任意の Top-k 検索を効率的にサポートするように設計されたプライバシー保護型 RAG サービス「P2RAG」を提案する。このシステムは、半正直（正直だが好奇的）で非共謀である 2 つのサーバーを想定した 2 サーバーモデル上で動作する。

• システムアーキテクチャ：

  • データ所有者：暗号化されたデータベースを 2 つのサーバーに外部委託する。データベースは $N$ 個のドキュメント埋め込みから構成され、これらは素数体におけるシャミアの秘密共有を用いて 2 つのサーバー間で秘密共有される。
  • ユーザー：プロンプト埋め込みを提出し、これも 2 つのサーバー間で秘密共有される。
  • 脅威モデル：サーバーはプロトコルに従うが、データを推測しようとする可能性がある。ユーザーは悪意のあるものとしてモデル化され、情報を抽出するためにプロトコルから逸脱する可能性がある。データ所有者は正直であると仮定される。

• 中核的な革新：対話的二分探索対ソート
  既存のシステムがすべての候補ドキュメントをソートする（安全なプロトコルにおいて計算コストの高い操作）のに対し、P2RAG はソートを完全に回避する。代わりに、Top-k 集合を定義する距離閾値（$d_k$）を決定するために対話的二分探索法を採用する。

  1. 距離計算：サーバーは、ビーバーのトリプルを用いて、ユーザーのプロンプトとすべてのドキュメント埋め込み間の秘密共有されたコサイン距離（ドット積で近似）を計算する。
  2. 二分探索の反復：ユーザーとサーバーは対話して距離閾値を絞り込む。各反復において、ユーザーは閾値 $d_k$ を指定する。サーバーは**分散比較関数（DCFs）**を用いて、距離が $d_k$ 未満のドキュメントの数をカウントする。
  3. 閾値の選択：ユーザーは返されたカウントに基づいて $d_k$ を更新し、閾値内のドキュメント数が目標の $k$ に近づくまでこれを繰り返す。
  4. 結果の取得：閾値が決定されると、サーバーは閾値内のドキュメントを示す秘密共有されたバイナリベクトルを生成する。ユーザーは単一サーバー型プライベート情報検索（PIR）を用いて、これらのドキュメントのインデックスを取得する。

• セキュリティメカニズム：

  • プライバシー：秘密共有により、どちらのサーバーもデータベースやプロンプトを学習しないことを保証する。
  • 悪意のあるユーザーへの防御：ユーザーが過剰な情報を抽出するのを防ぐため、P2RAG は厳格な制限を課す：
    • 二分探索の反復回数を上限設定し、漏洩する総カウントを $O(\log^2 N)$ に制限する。
    • 最終結果セットのサイズを制限する。
    • 検証メカニズムにより、ユーザーは合意されたバイナリベクトルに対応するインデックスのみを取得でき、検索プロセスの操作を防ぐ。

主な貢献

1. 任意の Top-k サポート：P2RAG は、ソートベースのアプローチで見られる効率性の低下なく、任意の $k$ 値を効率的にサポートする最初のシステムであり、現代の長文脈モデルが必要とする大規模な $k$ シナリオに適している。
2. 効率的なプロトコル設計：安全なソートを DCF を用いた対話的二分探索法に置き換えることで、P2RAG は安全なプロトコルにおける主要なボトルネックである比較回数を大幅に削減する。
3. 堅牢なセキュリティ：このシステムは、半正直なサーバーに対するデータ所有者のデータベースとユーザーのプロンプトの両方を保護する。また、悪意のあるユーザーに対する情報漏洩を厳密に制限するために、特定の制限と検証手順を導入する。
4. 実装と評価：著者は P2RAG を実装し、Apache License 2.0 の下でコードを公開した。

実験結果
著者は、BEIR データセット（約 17 万ドキュメントの trec-covid など）と合成データセットを用いて P2RAG を評価した。

• 精度：P2RAG は高い計算精度を達成する。$k'$ が 16 から 1024 の範囲でリコールは 1.0 のまま維持され、関連性スコアは取得されたドキュメントが一般的にプロンプトに関連していることを示している。
• パフォーマンス：P2RAG は、最先端のシステムである PRAG に対して大幅な高速化を示す。
  • $k = 16$ の場合、P2RAG は3.78 倍高速である。
  • より大きな $k$（例：$k=1024$）の場合、高速化は322 倍に増加する。
  • このシステムはドキュメント数（$N$）に対して線形にスケーリングするが、$k$ が増加するにつれて相対的に高速になる。これに対し、PRAG は効率性の低下に苦しむ。
• 通信：サーバー間通信は数百メガバイトに達する可能性があるが、これは高帯域幅のデータセンターリンクを介して管理可能である。ユーザー - サーバー間の通信は低く（数枚の標準的な画像と同程度）、維持される。

意義と主張
この論文は、P2RAG がプライバシー保護型 RAG における重要なギャップ、すなわち大規模な $k$ 値を効率的に処理できないという課題に対処していると主張している。著者は、標準的な非セキュリティ型 RAG はより単純で高速であるが、データプライバシーが厳格な要件である医療、金融、法務サービスなどの高リスク分野では P2RAG が不可欠であると強調している。このシステムは、これらの分野が、専有データベースやユーザークエリの機密性を損なうことなく、LLM の精度を向上させる大規模な検索セットを活用することを可能にする。著者は控えめに、このシステムは半正直な非共謀サーバーの仮定に依存しており、プライバシーが重要でない場合は標準的な非セキュリティ型 RAG が選択され続けると注記している。