HNSW Explorer：階層的ナビゲーション可能なスモールワールドの可視化
検索が階層化されたグラフを、疎な最上層（高速道路）から密な最下層（地方道路）へと移動していく様子をご覧ください。レイヤー0上のクエリポイントをドラッグし、M を調整して / ef を調整して、グラフがどのように変化するかを確認してください。
検索統計
レイヤーの分布
『HNSW 』の仕組み
- 階層化グラフ：各ノードには、指数分布を用いてランダムに最大階層が割り当てられる。ほとんどのノードは階層0にのみ存在し、最上層に到達するノードはごくわずかである。
- 各レイヤー内では、すべてのノードが
Mの最近傍に接続されている。上位のレイヤーは疎（ノード数が少なく、辺が長い＝「高速道路」）である。レイヤー0は密（すべてのノードが含まれ、辺が短い＝「地方道路」）である。 - 検索は最上部から開始される：固定された開始点から、クエリに最も近い隣接点へと貪欲に探索を進め、改善が見られなくなるまで繰り返す。
- レイヤーを1つ下げて繰り返し：前のレイヤーの位置が、次のレイヤーの探索の開始点となる。ドロップするたびに、よりきめ細かいエッジを用いて結果が精緻化される。
-
efを用いたレイヤー0：最下層において、HNSW は最初の局所最小値で停止するのではなく、ef最良の候補のプールを維持し、それらの近傍を拡張します。規模が大きいほどef→ 精度は高くなるが、処理速度は低下する。
高速な理由：最上位のレイヤーは、インデックス上のインデックスのように機能します。わずか数ホップで広範囲をカバーし、その後ズームインします。N個の点に対して、検索はN ではなく、およそO(log N) のノードを訪問します。
HNSW とは何ですか？
HNSW (Hierarchical Navigable Small World)は、グラフに基づく近似最近傍アルゴリズムである。これは、ベクトルをナビゲーション可能なスモールワールドグラフのスタックとして構成する。上層は疎で長距離のエッジを持ち、大まかなルーティングを行い、下層は密で短距離のエッジを持ち、最終的なきめ細かな探索を行う。 検索は各層でクエリに向かって貪欲にホップし、その後下層へ移動します。これにより、すべての N 個のノードをスキャンする代わりに、おおよそO(log N) 個のノードを訪問することになります。
HNSW は、最も広く使用されているインメモリベクトルインデックスであり、Milvus のデフォルトのグラフインデックスである。Milvus では、 HNSW_SQ および HNSW_PQ といったバリエーションも提供しており、これらは格納されたベクトルを量子化することで、リコールの精度をわずかに犠牲にする代わりにメモリ使用量を削減します。
HNSW パラメータはMilvus
M(構築時間)：ノードあたりの最大エッジ数。上記のスライダーと同じ調整項目です。一般的な値は8～64です。Mの値を大きくすると、リコール率とグラフの連結性が向上しますが、メモリ使用量は線形に増加し、構築速度が低下します。efConstruction(構築時間)：ノードを挿入する際に使用される候補プールのサイズ。値が大きいほど、インデックス構築に時間がかかる代わりに、より高品質なグラフ（より高いリコール率）が構築される。一般的な値は100～500である。ef/ef_search(クエリ時間)：Layer-0ウォーク中に保持される候補プール。検索時のリコール率とレイテンシを調整する主要なパラメータである。この値は、top-K の値以上でなければならない。リコール率が頭打ちになるまでこの値を増やしていく。レイテンシはこれにほぼ線形に比例して増加する。
HNSW vsIVF vsDiskANN
HNSW 通常、インメモリ検索において高いリコール率で最良のクエリレイテンシを実現します。そのため、データセット（およびグラフのオーバーヘッド）がRAM に収まる場合、これがデフォルトの選択肢となります。そのコストはメモリと構築時間です。グラフはベクトルごとに顕著なオーバーヘッドを追加し、挿入処理はIVF のk-means割り当てよりも遅くなります。 高速なインデックス構築や積極的な量子化が必要な場合はIVF を、データセットがRAM には大きすぎるものの高いリコール率が必要な場合はDiskANN を選択してください。
よくある質問
HNSW のMパラメータは何を制御しますか？
Mは、各ノードがレイヤーごとに保持するエッジの最大数を表します。Mが大きいほどグラフの接続性が向上し（リコール率が高くなり、ルーティングの堅牢性が増します）、しかしメモリ使用量はMに比例して増加し、インデックスの構築速度は低下します。8から64の範囲の値でほとんどのワークロードをカバーでき、16～32が一般的な最適値です。
ef とefConstruction の違いは何ですか？
これらはどちらも候補プールのサイズであり、異なるタイミングで適用される。「efConstruction 」はインデックスの構築時に使用される。これは、挿入された各ノードが近傍をどの程度徹底的に検索するかを決定し、グラフの品質を制御する。「ef 」（ef_search ）はクエリ実行時に使用される。これはLayer-0検索の範囲を制御し、各クエリにおいてレイテンシとリコール率のトレードオフを行う。
HNSW インデックスにはどのくらいのメモリが必要ですか？
おおよそ、生のベクトルとグラフの合計：float32データの場合、ベクトル1つあたり約d × 4バイトに加え、ノード1つあたりM × 2 × 8バイト程度のエッジデータが必要です。メモリに制約のある環境では、Milvus が提供するHNSW_SQ およびHNSW_PQ （保存されたベクトルを量子化する）や、DiskANN （完全なベクトルをSSD に移動する）を利用できます。
IVF の代わりにHNSW をいつ使用すべきですか？
高いリコール率でのクエリ遅延を優先し、かつインデックスがメモリに収まる場合は、HNSW を使用してください。通常、この方法が最速です。インデックスを頻繁に再構築する場合（構築がはるかに高速）、または限られたメモリ予算に収めるためにSQ8/PQ の量子化と組み合わせる場合は、IVF を優先してください。
さらに詳しく知りたい場合は、HNSW のドキュメントで正確なインデックスパラメータを確認するか、「Index Explained」を参照して完全な決定ガイドをご覧ください。