RAG（Retrieval Augmented Generation）開発者の方は、Googleの情報検索分野の新しい論文をぜひご覧ください。この論文では、MUVERAという先進的な検索アルゴリズムが紹介されています。このアルゴリズムは、複雑な多ベクトル検索の問題を、単一ベクトルの最大内積検索に巧みに簡素化することで、高い精度を維持しつつ、単一ベクトル検索に匹敵する速度を実現します。
背景：単一ベクトルから多ベクトルへ
ニューラル埋め込みモデルは、現代の情報検索（IR）の基盤です。検索エンジンであれ推薦システムであれ、その中核となるタスクは、ユーザーのクエリ（例：「エベレストの高さは？」）に基づいて、膨大なデータの中から最も関連性の高い情報を見つけることです。埋め込みモデルは、各データポイント（文書、画像など）を数値ベクトル、すなわち「埋め込み」に変換し、意味的に類似したデータポイントが数学的にも互いに近いことを保証します。
従来の手法では、各データポイントに対して単一のベクトル埋め込みを生成していました。ベクトル間の内積類似度を計算することで、システムは効率的な最大内積検索（MIPS）アルゴリズムを利用して、一致する結果を迅速に見つけることができます。しかし、近年、ColBERTに代表される多ベクトルモデルは、より優れた性能を示しています。これらのモデルは、各データポイントに対して単一のベクトルではなく、一連のベクトルを生成し、より複雑な類似度関数（Chamfer類似度など）を採用して、より豊かで繊細な意味的関係を捉えます。多ベクトル手法は精度を向上させる一方で、膨大な計算コストを伴い、検索プロセスが非常に高価になるという課題がありました。
多ベクトル検索の課題
多ベクトル表現は、解釈性と汎化能力において優れていますが、その検索プロセスは深刻な課題に直面しています。
1. 埋め込み数の急増：各トークン（token）ごとに埋め込みを生成するため、処理する必要のあるベクトルの数が急激に増加します。
2. 類似度計算の複雑さ：Chamferマッチングのような類似度計算は非線形操作であり、行列乗算を必要とするため、単一ベクトルのドット積よりもはるかに計算コストが高くなります。
3. 効率的な検索方法の不足：単一ベクトル検索は、空間分割などの高度に最適化された準線形検索アルゴリズムの恩恵を受け、総当たり的な比較を回避できます。しかし、多ベクトル類似度の複雑さにより、これらの高速な幾何学的技術を直接適用することは困難です。
したがって、ある文書が特定のトークンによってクエリと高度に関連していると認識されることはあっても、全体としては最適な一致ではない可能性があります。これにより、より複雑で計算集約的な検索方法が必要となります。
MUVERAの解決策：固定次元エンコーディング（FDE）
上記の課題を解決するため、論文「MUVERA: Multi-Vector Retrieval via Fixed Dimensional Encodings」では、革新的な多ベクトル検索アルゴリズムを提案しています。その核となる考え方は、巧妙な数学的変換を通じて、多ベクトルの集合を固定次元の単一ベクトル、すなわち固定次元エンコーディング（Fixed Dimensional Encoding, FDE）に圧縮することです。
この変換の鍵は、圧縮後、2つのFDEベクトル間の内積が、元の多ベクトル集合間のChamfer類似度を高度に近似できる点にあります。これにより、複雑な多ベクトル検索の問題が、単一ベクトルの最大内積検索（MIPS）問題へと効果的に簡素化されます。
MUVERAのワークフローは以下の3つのステップに分解できます。
1. FDE生成：特定の写像関数を通じて、クエリと文書の多ベクトル集合を固定長のFDEベクトルに変換します。
2. MIPSに基づく検索：標準的なMIPSインデックスとアルゴリズムを使用して、文書のFDEベクトルに対して効率的な検索を行い、最も類似する候補文書のバッチを迅速に呼び出します。
3. 再ランキング：呼び出された候補集合に対し、元のより正確なChamfer類似度を用いて再ランキングを行い、最終結果の精度を保証します。
MUVERAの顕著な利点の一つは、そのFDE変換プロセスが特定のデータセットに依存しないことです。これにより、データ分布の変化に対して非常に堅牢であり、ストリーミングデータ処理のアプリケーションシナリオにも非常に適しています。さらに重要なのは、FDEが特定の誤差範囲内で真のChamfer類似度を近似できることを保証することです。したがって、再ランキング後、MUVERAは最も一致する多ベクトル表現を見つけることを保証できます。
理論的基礎
この方法の理論的インスピレーションは、幾何学的アルゴリズム理論における強力なツールである確率的ツリー埋め込みに由来し、内積とChamfer類似度に適合するように調整されています。
FDE生成の核心は、埋め込み空間のランダムな分割にあります。クエリと文書内の類似ベクトルがたまたま同じ分割領域に落ちた場合、それらの類似度を効率的に近似計算できます。ランダム化された分割スキームにより、全体的な近似効果が確率的に保証されます。論文では、FDEのChamfer類似度近似能力を実証する厳密な理論的証明が提供されており、多ベクトル検索のために単一ベクトルプロキシを使用するための確固たる理論的基礎を提供します。
実験結果
BEIRベンチマークの複数の情報検索データセットにおいて、MUVERAは非常に優れた性能を示しました。実験により、以前の最先端手法（PLAIDなど）と比較して、MUVERAは遅延を大幅に削減しつつ、より高い検索再現率を獲得することが示されました。
主な発見は以下の通りです。
1. より高い再現率：一般的な多ベクトル検索方法（単一ベクトルヒューリスティック）と比較して、MUVERAははるかに少ない候補文書（5〜20倍）を検索する場合でも、同等かそれ以上の再現率を達成できます。
2. 極めて低い遅延：高度に最適化された多ベクトル検索システムPLAIDと比較して、BEIRベンチマークにおけるMUVERAの平均再現率は10%高く、遅延は驚異的に90%削減されました。
さらに、MUVERAのFDEは積量子化技術を用いて効率的に圧縮できることも実験で明らかになり、検索品質への影響を最小限に抑えつつ、メモリ使用量を32分の1に削減できます。
結論
MUVERAは、その近似品質と実用的な性能が理論と実験の両方で検証された、新規かつ効率的な多ベクトル検索アルゴリズムです。多ベクトル検索を単一ベクトルMIPSに簡素化することで、既存の最適化された検索技術を最大限に活用し、非常に高い効率で最先端の性能を実現します。
この研究は、効率的な多ベクトル検索の新しい道を開き、検索エンジン、推薦システム、RAGなどのアプリケーションにとって極めて重要です。
関連リソース
MUVERAという新しい方法は、RAGの検索フェーズの効率を効果的に向上させることができます。現在ではPythonライブラリも利用可能なので、興味のある方は試してみてください。
論文アドレス: http://research.google/blog/muvera-making-multi-vector-retrieval-as-fast-as-single-vector-search/
Chamfer類似度: http://sciencedirect.com/topics/engineering/chamfer-matching
Pythonライブラリ: http://github.com/sigridjineth/muvera-py