HNSW：数百万のベクトルの中から最も近い隣人を探す方法

クエリベクトルを100万個の他のベクトルと網羅的に比較すると、1回の検索ごとに100万回の演算が必要になります。実規模では実用できません。HNSWは絶対的な精度を犠牲にして速度を優先していますが、そのトレードオフの比率は非常に有利です。

多層グラフ

このアイデアは、ハノイからサイゴンへ向かう際の移動方法に着想を得たものです。まず長距離を飛行機で移動し、目的地に着いてからタクシーに乗り、最後は徒歩で移動するというものです。HNSWは、多層的なグラフを作成しました：

• 最上層は非常に疎で、各辺がベクトル空間内で大きく飛躍している
• 下の層は次第に密になり、辺は短くなっていく
• 最下層にはすべての点が含まれており、辺は実際に互いに近い点同士を結んでいる

探索は上層から開始し、クエリに最も近いポイントに向かって貪欲に進行し、行き止まりになったら下層へ移動してこれを繰り返す。ステップ数は、ポイントの数に比例して線形に増加するのではなく、対数関数に従って増加する。

調整が必要な2つのパラメータ

• M — 各ノードで保持するエッジの数。この値が大きいほど検索精度は高くなりますが、RAMの消費量も増えます
• efSearch — 検索時にキューに保持する候補の数。これは速度と精度のバランスを調整するパラメータであり、インデックスを再構築することなく実行中に調整可能です

選ぶ前に知っておくべきこと

HNSWはほぼ常にインデックス全体をRAMに保持しています。これが大規模なシステムにおける最大のコスト要因となっています。要素の削除も困難です。実際、多くの実装では削除済みとしてマークするにとどまり、定期的に再構築する必要があります。

結果は「ほぼ正確」です。意味検索では、8番目の結果が見落とされていますが、誰も気づかないでしょう。正確な照合を行う場合は、使用しないでください。