A Comparative Study of Vector Indexing Strategies Using Facebook AI Similarity Search as a Case Study

あなたは、あらゆる本が書かれた図書館に立っていると想像してください。ただし、それらの本はタイトルや著者によって整理されているのではなく、お互いにどれほど「似ている」かによって分類されています。もしあなたが「勇敢な猫」についての物語を求めたら、司書は単に「勇敢」や「猫」という言葉が含まれる本を探すのではありません。司書は、たとえ言葉が違っていても、その「アイデア」が持つ「感じ（フィーリング）」が似ている物語を見つけ出します。これが現代の人工知能の魔法です。アイデアを数字のリスト（ベクトルと呼ばれます）に変換し、データの海の中から最も近い一致を見つけ出すのです。

しかし、ここに落とし穴があります。もしあなたの図書館に10億冊の本があったとしたら、最高の組み合わせを見つけるためにすべての本をチェックするのは、永遠に時間がかかってしまいます。それは、砂浜から一粒一粒手に取って、特定の砂粒を探すようなものです。これを解決するために、科学者たちは「インデックス（索引）」を発明しました。これは、コンピュータが退屈な部分をスキップして、面白い部分へ直接ジャンプするのを助ける特別なショートカットです。あるショートカットは、超整理された地図のようなもの（正確な検索）であり、別のものは、一瞬で99%の正解にたどり着く巧妙な推測ゲームのようなものです（近似検索）。大きな疑問は、「どのショートカットが最適か？」ということです。それは、あなたのライブラリの規模によって変わるのでしょうか？ あなたが小さなノートを持っているのか、それとも巨大な倉庫を持っているのかによって変わるのでしょうか？

これは、まさにアルメニア欧州大学の研究チームが解明しようとした問題です。彼らは、これらのベクトルのショートカットのためのスイス・アーミーナイフ（万能ナイフ）のような、FAISS（Facebook AI Similarity Search）という人気のツールキットを取り上げ、そのさまざまなツールをテストしました。彼らは、データが巨大になり、数値が複雑になり、メモリが不足したときに、それぞれのツールがどのように機能するかを調べたかったのです。これは、異なる種類の検索エンジンが、息切れすることなく、あるいはメモリを使い果たすことなく、いかに早く正しい答えを見つけられるかを競う、大規模なレースのようなものです。

研究者たちは、いくつかの異なる戦略をテストしました。それらは、「ブルートフォース（総当たり）」法（すべてをチェックする）から、クラスタリング（似たものをグループ化する）や圧縮（データを小さく押しつぶす）、グラフベースのナビゲーション（接続のネットワークを利用して答えへと飛び跳ねる）といった巧妙なトリックまで多岐にわたります。彼らは主に2つの要素を測定しました：再現率（Recall）（正しい答えを見つけられたか？）と、レイテンシ（Latency）（回答にどれくらいの時間がかかったか？）です。

実験の結果、彼らは以下のことを発見しました。

「ブルートフォース」のチャンピオン（IndexFlat）
容疑者の列にいる全員を一人ずつチェックすることを拒む探偵を想像してください。これが IndexFlat メソッドです。研究者たちは、このアプローチが完璧であることを発見しました（決して正解を逃しません、再現率100%）。しかし、これは信じられないほど低速です。データの数（ベクトル）が1,000から10,000へと増えるにつれ、答えを見つけるのにかかる時間は着実に増加しました。小さなデータセットであれば、これは素晴らしいものです。しかし、数百万のベクトルを持つ場合、このメソッドは現実世界では役に立たないほど遅くなってしまいます。それは、干し草の山の中から針を見つけるために顕微鏡を使うようなものです。うまくいきますが、あまりにも時間がかかりすぎます。

「グルーピング」戦略（IVFFlat）
次に、彼らはベクトルを「アドベンチャー」「ロマンス」「ミステリー」といったラベルが付いたビンに分類するように、ベクトルをクラスターにグループ化する方法を試しました。これが IndexIVFFlat です。クエリが来ると、システムは答えが含まれている可能性が最も高いビンだけをチェックします。研究によると、これは素晴らしい中間地点です。すべてをチェックするよりもはるかに速く、より多くのビンをチェックするように調整することで、精度を高めることができます。研究者たちは、より多くのクラスター（nprobeと呼ばれる設定）をチェックすれば結果は良くなりますが、それには少し時間がかかることも発見しました。これは、中規模から大規模のデータセットに対して、速度と精度のバランスをうまく取る柔軟なツールです。

「圧縮」のエキスパート（IVFPQ と IVFSQ）
もし、10億個のベクトルがあるけれど、それらすべてを保存するためのハードドライブの容量が足りないとしたらどうでしょう？ 研究者たちは、高画質の映画をより小さなファイルサイズに圧縮するように、データを圧縮する手法である IndexIVFPQ と IndexIVFSQ を調査しました。これらはデータを押しつぶして、使用メモリを節約します。

• IVFPQ（プロダクト量子化）は、ベクトルを小さな断片に分割して圧縮します。研究では、メモリが最大の課題となる大規模なデータセットにおいて、これがチャンピオンであることが分かりました。非常に高速で、使用スペースも極めて少ないですが、時々「完璧な」答えを逃すことがあります（再現率がわずかに低下します）。
• IVFSQ（スカラー量子化）は、よりシンプルな圧縮バージョンです。これは優れた「中間的な存在」です。スペースを節約し、圧縮されていないバージョンよりも高速ですが、IVFPQほど激しく圧縮することはありません。研究者たちは、未圧縮のバージョンと比較して精度がわずかに低下するものの、大規模システムにおいてはメモリ節約のメリットの方が大きいと指摘しています。

「接続のウェブ」 （HNSW）
最後に、IndexHNSW がありました。これは、エクスプレスライン（急行）とローカルストップ（各駅停車）を持つ地下鉄の路線図のように、データを多層的なウェブ状に整理します。まず、上層（エクスプレスライン）から始まり、大まかな方向を掴み、その後、正確な停留所を見つけるために一層ずつズームインしていきます。研究では、これがスピードと精度の面で全体的なスーパースターであることが判明しました。「非常に高速」であり、「非常に高い」再現率を持っています。しかし、ウェブを構築するためにより多くのメモリを必要とし、研究者は注意深くチューニングする必要があると指摘しています。接続を増やしすぎてウェブを過密にすると検索が遅くなり、逆に疎にしすぎると、最良の答えを見逃してしまう可能性があります。しかし、適切に調整されれば、スピードと精度の最高のバランスを提供します。

結論
論文は、あらゆる仕事に対して「唯一のベストなツール」というものは存在しないと結論づけています。それは、ハンマー、ドライバー、レンチのどれが一番良いかを尋ねるようなもので、何を作っているかによります。

• 小規模なデータセットがあり、完璧な精度が必要なら、Flat インデックスを使用してください。
• 中規模のデータセットがあり、バランスが必要なら、IVFFlat が堅実な選択肢です。
• 何十億ものベクトルを扱っており、コンピュータのメモリが不足しているなら、IVFPQ があなたの親友になります。
• 高い精度とともに可能な限り高速な検索が必要で、十分なメモリがあるなら、HNSW が勝者です。

研究者たちはまた、「類似性」を測定するさまざまな方法（空間内の2点がいかに近いかなど）についてもテストしました。彼らは、特定のタイプのAIモデル（言語に使用されるものなど）については、数学を正しく機能させるためにデータを正規化する必要があることを確認しましたが、一度正規化を行えば、異なるインデックス戦略は十分に機能することを明らかにしました。

要するに、この研究はAIシステムを構築しようとしているすべての人への実践的なガイドを提供しています。完璧なスピード、完璧な精度、そしてゼロのメモリ使用量を同時に手に入れることはできないとしても、私たちは特定のニーズに合わせて適切なトレードオフを選択できるのです。銀行の不正検知システムを構築しているのか、あるいは医療記録の検索エンジンを作っているのか、どのような場合であっても、このツールキットの中には、干し草の山の中から針を見つけ出し、迷子になることのない適切なインデックス戦略が存在します。