高速なベクトル検索を支える技術- HNSWの仕組み

はじめに

昨今のRAGシステムの流行を始めとして、検索のためにベクトルデータベースを導入しているシステムが増えている状況かと思います。

私も業務でベクトルデータベースを利用する機会があったため、これを機にベクトルデータベースの内部で利用されることが多い、近似最近傍探索手法の1つであるHNSW（Hierarchical Navigable Small World）について勉強しました。本稿ではその内容について記述します。

近似最近傍探索とは

ベクトル検索では、クエリに対して類似したアイテムを探索する計算を行います。

単純にクエリとアイテムの全件を比較すれば、最も近い値を探し出すこと（最近傍探索）はできます。
しかし、大量のデータに対して最近傍探索を行う場合、膨大な計算量（ O(n) ）を要します。

そのため、ベクトルデータベースでは完璧な回答を出力できない可能性があるけれども、効率的な演算で高速に近似した回答を探索する手法が用いられることが多いようです。これを近似最近傍探索と言います。

Elastic社のブログでは近似最近傍探索について以下の通り説明されています。

https://www.elastic.co/jp/blog/understanding-ann

近似最近傍探索（ANN）とは、指定のクエリポイントに非常に近いものの、必ずしも一番近いとは限らないポイントをデータセットから見つけるアルゴリズムです。NNアルゴリズムは完全に一致するポイントを見つけるために全データを徹底的に検索しますが、ANNアルゴリズムでは十分に近い一致で良しとしています。

これはソリューションとしては悪手のように聞こえますが、実際に高速類似検索を成功させる鍵となっています。

近似最近傍探索には下記のようなものがありますが、今回はその中からHNSWに焦点を当てます。

• Hierarchical Navigable Small World (HNSW)
• Locally Sensitive Hashing（LSH）
• Product Quantization（PQ）
• k-d木 など

各種ベクトルデータベースにおけるHNSWの利用

WikipediaのHNSWのページを見ると、以下のベクトルデータベースでHNSWが利用されている（サポートされている）という記述があります。

https://en.wikipedia.org/wiki/Hierarchical_navigable_small_world

Databases that use HNSW as search index include:

Apache Lucene Vector Search
Chroma
Qdrant
Vespa
Vearch Gamma
Weaviate
pgvector
MariaDB
MongoDB Atlas
ClickHouse
Milvus
DuckDB
Kuzu

Pineconeについては以下のブログ記事から、HNSWをデメリットを克服し、独自の実装によって近似最近傍探索を実現していることが推測されます。
https://www.pinecone.io/blog/hnsw-not-enough/

Hierarchical Navigable Small World (HNSW)

ここからは、本題のHNSWの内容についてです。

用語の整理

はじめに、以下の3つの用語について整理をします。

用語	説明
ノード	各ベクトルを表す点のこと
エッジ	ノード間を接続する線のこと
クエリ	与えられた探索対象のこと

概要

Hierarchical Navigable Small World (HNSW)は、日本語訳すると「階層型ナビゲーション可能なスモールワールドアルゴリズム」となります。

HNSWを一言で説明すると、与えられたクエリに対して、事前に構成された階層構造を持つネットワークを用いて、最上層の開始点からネットワークを辿りながら効率的に近似最近傍のノードを見つける手法と言えます。

簡単なイメージとしては、どこか遠くへ旅行に行くときに、飛行機で目的地付近まで一気に飛んで、最終目的地までは在来線を乗り継いで地道に向かうことと、原理的には同じと言うことができます。

例えば、一般的な旅程で東京から太宰府天満宮へ行く場合、羽田空港から福岡空港まで一気に移動した後は、西鉄（在来線）を乗り継ぎながら目的地の太宰府天満宮まで細かく移動していきます。

羽田から太宰府天満宮まで在来線を乗り継いで行くこともができますが、これでは大変な時間がかかってしまうため、一般的な旅程の方が効率的な移動手段と言えます

■羽田空港     
｜ 　航空便   
｜ 　
｜ 　
◇福岡空港
｜ 　福岡地下鉄空港線
｜ 　
｜ 　
◇天神/西鉄福岡［天神］
｜ 　西鉄天神大牟田線急行
｜ 　
｜ 　
◇西鉄二日市
｜ 　西鉄太宰府線(太宰府行)
｜ 　
｜
◇太宰府
｜ 　徒歩
｜
｜
■太宰府天満宮

下図は実際のHNSWにおける階層型のネットワークのイメージとなります。

この図における黒丸はノード（ベクトル）を表現しています。黒丸を結ぶ灰色の線がノード間を繋ぐエッジであり、探索の際に利用する経路です。検索時にはエッジを伝って、クエリのノード（ベクトル）に対して最も近いと想定されるノードを探します。

上記の図では、青線の流れに沿ってクエリに対する最近傍点を探索しています。上位層で一気に目的地付近に近づき、下層に進むに連れてより細かく移動しながら、最終的に最近傍点まで移動しています。

ノードと層の関係について補足します。

最下層には全てのノードが配置されています。上位層に行くに従ってノードの数は減少しています。
また、上位層に存在するノードは下位層にも必ず存在しているという関係になっています。上位層に存在するノードは、全体のノードから間引かれて残ったものが点在しているような状態です。

先程の交通の例で言うと、最上層には空港の点だけが存在していて、最下層には空港だけでなく駅やバス停など全ての乗降施設の点が含まれるとイメージしていただくと分かりやすいかもしれません。

検索時には、最上層の特定の開始点から走査をスタートし、クエリに対して最近傍であると想定されるノードを各階層で探索していきます。各階層の中で最近傍と想定されるノードが見つかった時点で、下の階層に進みさらに探索を繰り返し、最終的に最下層にて全体のノードの中での最近傍と想定される点を見つける流れです。

検索の流れについては、以下のXのpostの動画が大変分かりやすかったので、参考として添付しておきます。

https://x.com/i/status/1729835741130162272

このように、HNSWを利用して探索を行う場合には、検索対象となるアイテムのノード間をエッジで結んだ階層型のネットワークが事前に構築されていることが前提となります。HNSWを利用したベクトルデータベースのインデックス更新においては、このネットワーク構築が行われています。

簡単にまとめるとHNSWによる検索を行うためには、以下2つのステップが必要となるということです。

1. 事前に階層型ネットワークを構築する
2. クエリに対して、階層型ネットワークを走査しながら最近傍を探す

ネットワークの作り方

上述の通り、HNSWを用いて検索を行うためには、事前に階層型ネットワークが構築されている必要があります。ここではネットワークがどのように構築されるかについて概要を説明します。

1. ノードの挿入（階層の決定）

先ずは、ベクトルレコードであるノードを階層に対して配置していきます。
ノードが配置される際、ランダムにどの階層から該当のノードが現れるかが決定されます。

ランダムと言っても、上述した図のように、上位層は非常に少ないノード数で構成され、下位層に進むに連れてノード数が増えていくような状態とする必要があります。論文^[1]では負の自然対数を用いて、ノードの分布を決定する手法が提案されています。

ノードを配置する階層決定のための式

ここでは自然対数をlog(x)で表現しています。

$$l = \left\lfloor -\log(\text{unif}(0,1)) \cdot m_L \right\rfloor$$

式（部分）	説明
unif(0, 1)	0 ~ 1の値をランダムに取る関数。
-log()	負の自然対数。
mL	階層間のノード分布の密度を制御する係数。
⌊⌋	floor関数。少数点以下の値を切り捨てる。（例:2.3 → 2）

順を追って、上記の式をグラフで可視化してみます。

まずは、負の自然対数の部分 l = -log(x)*mL だけをグラフで可視化してみます。（mL=1とする）

y = -log(x) * 1

続いて、上記で可視化した -log(x)*mL に対して、小数点以下を切り捨てるfloor関数 ⌊⌋ を適用すると以下のようになります。

y = ⌊-log(x) * 1⌋

x は0~1の間でランダムな値を取るため、ほとんどの場合においては l = 0 になることが見て取れます。つまり、ほとんどのノードは layer: 0 である最下層のみに現れる状態となります。
x の値が仮に0.1ぐらいであれば、layer: 2 からノードが挿入されて、layer: 1 と layer: 0（最下層） まで存在するノードとなります。

mL の値を大きくすると上層のノード密度が高くなります。例えば mL を3にすると以下のようになります。

y = ⌊-log(x) * 3⌋, mL = 3の場合

単純な選択としては 1/ln(M) を mL の値とすると良いようです。（M値については後述します。）

2. ノード間を結ぶエッジの作成

ノード間を結ぶエッジの作成についても、概ね検索と同じような流れで行われます。新しく挿入されたノードに対して、既存のネットワークを最上層から走査しながら近傍点を見つけて、新しいノードが現れる各階層で近傍点とエッジを結んでいく流れとなります。

少し複雑ですが、具体的には以下の通りの処理が行われます。

最上層の開始点からエッジで結ばれている近所のノードに対して、一つずつクエリ（ここでは新しく挿入されたノードの意）との距離を評価しながら、以下の表に記載した集合を更新しつつ近傍を探していく流れで処理が行われます。特定のノードに接している全ての近所ノードを評価し終わったら、更新された C の中からクエリに対する現時点の最近傍点 c を抽出して、その最近傍点と接している近所ノードを再び一つずつ評価していく流れです。

集合	説明	集合の更新条件
v	既に訪問したノードの集合	訪問したノードが追加される。
C	近傍探索の候補集合	現在評価中の近所ノード e について、以下の条件を満たす場合 C に追加される ・初めて訪問している（v に存在しない） ・distance(e, q) < distance(f, q) の場合（ q : クエリ, f : W の内で最もクエリに遠いノード） C から取り出された候補 c はこの集合から削除される。
W	見つかった近傍の動的リスト	基本的には C と同様な条件で候補が追加されるが、 W は ef（後述）個しか候補を保持できず、収まらないものは最もクエリに遠いノードから削除される。

C が空になった場合、もしくは distance(c, q) > distance(f, q) になった時点で、現在の層での探索は終了します。（q : クエリ, f : W の内で最もクエリに遠いノード）

その後、lc（lc=新しく挿入されたノードが初めて現れる階層とする）以降の層であれば、W に残った候補の内、クエリと近い方から M 個（後述）のノードとクエリの間にエッジを結びます。

ef値について

W に候補を格納できるリストの制限数が ef 値です。以下の通り ef 値は層によって異なります。

レイヤー	ef値
最上層 ~ lc+1	ef = 1 で実行される。
lc ~ 最下層	ef = efConstruction で実行される。 efConstruction は事前に定義した定数。

一般的には efConstruction を大きくすることで、局所最適に陥ることを防ぎやすいようですが計算量は多くなります。

検索においてもこのef値を別途設定することが可能で efSearch というパラメータが用意されているDBもあります。

M値について

各ノードが所有することのできるエッジの数です。

最下層レイヤーだけは M を大きくした方が精度が出やすいようです。HNSWを実装できるpythonのライブラリ faiss では最下層のみノード数が M * 2 に設定されているようです。

近傍の選択方法（どの点にエッジを結ぶか？）

ノードからクエリに対してエッジを結ぶ近傍点の選択方法について、論文の中では2つの手法が紹介されています。

SELECT-NEIGHBORS-SIMPLE

W に含まれる候補ノードから、単純にクエリにより近いものを優先的にM個選ぶシンプルな方法です。

SELECT-NEIGHBORS-HEURISTIC（候補選択ヒューリスティック）

上述のSELECT-NEIGHBORS-SIMPLEでは、単純に最近傍のM個を選ぶため、同じクラスタ内の点ばかりがエッジを結ぶ相手として選ばれてしまい、距離のあるクラスタ間を通す接続が行われない可能性があります。

これを解決するのが、SELECT-NEIGHBORS-HEURISTICのようです。

この手法について、私は論文からだけでは十分に説明できるほどの理解はできませんでした。
代わりに、以下のページに分かりやすい説明があったため、参考までにご紹介します。

https://bakingai.com/blog/hnsw-semantic-search-faiss-integration/

引用作成: https://bakingai.com/blog/hnsw-semantic-search-faiss-integration/

上記のようにXが新しいノードとして投入されたケースを考えます。この場合、Xを橋渡しとしてAが所属するクラスタとBが所属するクラスタが接続されてクラスタ間に経路が出来ることが望ましい状態と考えられます。

これは以下のプロセスを経て決定されると記載されています。（日本語に翻訳した内容を引用として記述します。）

最初に X に最も近い近傍として B を選択し、エッジ BX を作成します。続いて C を次に近い近傍として選択すると、BC < CX であることが明らかになります。これは、ノード B と C が近接しており、エッジ BX がすでに存在しているため、エッジ CX をグラフに追加することは最適ではないことを示しています。この評価は、ノード D と E にも同様に拡張されます。次に、アルゴリズムはノード A を評価します。ノード A は条件 BA > AX を満たしているため、新しいエッジ AX が形成され、両方の初期領域間の接続が確立されます。

HNSWの難点

HNSWの難点としては、メモリ利用量が大きくなる点にあります。

https://aws.amazon.com/jp/blogs/news/choose-the-k-nn-algorithm-for-your-billion-scale-use-case-with-opensearch/

上記、AWSのブログには以下の記述があります。

HNSW は非常に優れた近似最近傍検索を低レイテンシーで実現できますが、大きなメモリを消費し得ます。HNSW の各グラフはおよそ 1.1 * (4 * dimension + 8 * m) * num_vectors バイトのメモリを消費します。

メモリ利用量の式

$$1.1 \cdot (4bytes \cdot \text{dimension} + 8bytes \cdot m) \cdot \text{num\_vectors}$$

式	説明
1.1	恐らく10%のオーバーヘッドを表す係数。追加のメタデータや内部構造のために確保される余分なメモリのことか？
4bytes * dimensions	1つのノードであるベクトルデータの容量（32ビット浮動小数点）
8bytes * m	1つのノードが持つエッジデータの容量（8bytesはポインタの容量）
num_vectors	ベクトルレコードの総数（ノードの総数）

例えば、以下のケースで計算してみます。

• num_vectors: 10万件
• dimension: 1,536（embeddingモデルの出力次元数では1,536が利用されていることが多い）
• m: 100（次元数が多い場合は100ぐらいあった方が良いとのこと）

1.1 * (4bytes * 1536 + 8bytes * 100) * 100000 = 728MB

上記の通りとなり、10万件程度でも728MBのメモリが必要になる計算になります。

終わりに

ここまでHNSWの概要について記載しました。ベクトルデータベースの中で高速な検索がどのように実現されているかイメージが伝われば幸いです。

脚注

1. Yu. A. Malkov, D. A. Yashunin “Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs”