HNSW アルゴリズムの仕組み

1なぜ調べたか

Faiss と Lucene のベクトル検索を比べた記事^[7]を書いたとき、どちらも中身は HNSW でした。M や ef といったパラメータを「上げると精度が上がるらしい」ではなく、仕組みから説明できるようにしたくて整理しました。

この記事で扱うのは、グラフの形・探し方・作り方・パラメータまでです。ベクトルを圧縮して軽くする量子化（PQ など）や、クラスタに分けてから探す IVF といった別の方式には触れません。

2近いベクトルを探すのは重い

文章や画像を埋め込みモデルに通すと、数百〜数千次元のベクトルになります。意味が近いものほどベクトルどうしの距離が近くなるように学習されているので、「似ているもの」を探すことは、このベクトル空間で一番近い点を探すことになります。

確実なのは全部の点と距離を測ること（総当たり）です。ただ、距離を 1 回測るだけで次元の数だけ掛け算が要ります。100 万個の 768 次元ベクトルなら、1 回の検索でおよそ 7.7 億回の掛け算です。検索のたびにこれを払うのは重すぎます。

2 次元や 3 次元なら、空間を箱に区切る木構造（k-d 木など）で速く探せます。しかし次元が高くなると、どの箱にも近い点がありうるので区切りが効かなくなり、結局ほとんど全部を見ることになります（次元の呪い）。

そこで「必ず正解する」ことを少しだけ諦めて、測る点を大きく減らすのが近似最近傍探索（ANN）です。どれだけ正解できたかは、本当の上位 k 件のうち何件を取れたかの割合（recall@k）で測ります。HNSW は、この ANN の中でも速さと recall のバランスが良い方式として広く使われています。

3グラフをたどって近づく

土台になるのは、近い点どうしを線でつないだグラフです（NSW と呼ばれる、HNSW の前身）^[2]。探すときは、どこかの点から始めて「つながっている点の中で、目的地に一番近い点へ移る」を繰り返します。どの隣に移っても近づかなくなったら終わりです。これを貪欲探索と呼びます。

うまくいくかどうかは、グラフの形しだいです。名前の「Small World」は、知り合いを数人たどれば世界の誰にでも届く、という「世間は狭い」性質のこと。近い点とのつながりに加えて、ところどころ遠くへのつながりがあれば、どこからでも少ない手数で目的地の近くまで行けます。NSW では、点が少ないうちに入れた初期の点どうしのつながりが、結果としてこの「遠くへのつながり」になります^[2]。

ただ、この方法には 2 つの弱点があります。1 つは、ほとんどのつながりが近い点どうしなので、遠い目的地まで小さな歩幅で何度も移動すること。もう 1 つは、途中でそれ以上近づけない場所（局所解）に止まることがあることです。Animation 2 でも、本当に一番近い点のすぐそばまで来ているのに、そこへつながる隣を持っていないせいで止まっています。NSW では、入口を変えて何度か探し直すことでこれを和らげていました^[2]。

4層を重ねて、遠くから一気に近づく

HNSW は、このグラフを何層も重ねます。一番下の層 0 には全部の点。上の層にはその一部だけが載っていて、点が少ないぶん、その中で「近い点」とつないでも 1 本のつながりが遠くまで届きます。地図でいえば、高速道路 → 一般道 → 路地、の順に乗り継ぐイメージです。

この発想は、整列したリストに「急行の段」を重ねて探索を速くするスキップリスト^[8] と同じです。HNSW はそれを、順番のない高次元の空間に持ち込んだものといえます^[1]。

探し方は単純です。一番上の層にある入口から始めて、その層で貪欲探索をします。止まった点は下の層にも必ず載っているので、そこを 1 つ下の層の入口にして、また貪欲探索をする。これを層 0 まで繰り返します^[1]。上の層では「一番近い 1 点」だけを持って進み、最後の層 0 では候補を efSearch 個まで持って広めに探します（7 で詳しく）。

上の層は大股で目的地の近くまで運ぶ役、下の層は近くを細かく探す役です。入口がはじめから目的地の近くになるので、細かい層を長く歩かずに済み、局所解にも落ちにくくなります。Animation 2 で行き詰まったのと同じ点を、今度は正しく見つけられています。

5どの層まで載るかは確率で決まる

どの点を上の層に載せるかは、データの中身では決めず、点を入れるときに乱数で決めます。式にすると floor(-ln(U) × mL)（U は 0〜1 の乱数、mL = 1 / ln(M)）。こうすると、1 つ上の層に載る確率がちょうど 1/M になります^[1]。M = 16 なら、層 1 に載るのは 16 点に 1 点、層 2 は 256 点に 1 点です。

層が上がるごとに点が 1/M に減るので、層の数はおよそ log_M N 段にしかなりません。M = 16 で 100 万点なら log_16(1,000,000) ≈ 5 なので、層は 6 段ほどです。各層で数歩ずつ進むとすると、全体の手数もおよそlog N に比例します。点が 10 倍になっても、手数は少し増えるだけです^[1]。

乱数で決めるのは手抜きではありません。上の層の点がデータ全体にまんべんなく散らばるので、どの方向の目的地にも大股で近づけます。データを順番に入れても、偏った順番で入れても、層の作りが崩れにくいという利点もあります。

6点の入れ方

グラフは、点を 1 つずつ入れながら育てます。入れ方は探し方とほぼ同じで、新しい点そのものを探しに行き、見つかった近い点とつなぐだけです。手順は 2 段に分かれます^[1]。

まず、新しい点が載る層を乱数で決めます。それより上の層では、探索と同じく貪欲に降りてくるだけで、つながりは作りません。自分が載る層まで来たら、そこから層 0 までの各層で、近い候補を efConstruction 個まで集め、その中から M 個を選んで両方向につなぎます。相手のつながりが上限（上の層は M 本、層 0 は 2M 本）を超えたら、相手の側で一番遠いつながりを切って上限に収めます。

つながりを両方向にするのは、あとから入った点からも、先に入っていた点からもたどれるようにするためです。片方向だと、新しい点は「誰からも来られない行き止まり」になりかねません。また、点をあとから足せる仕組みなので、データが少しずつ増える用途にもそのまま使えます。

73 つのパラメータ

ここまでで、HNSW のパラメータがそれぞれ何を決めているかが見えてきます^[1,4]。

M はグラフの「道の多さ」です。多いほど遠回りせずに済み、局所解にも落ちにくくなりますが、点ごとに持つつながりが増えてメモリと作る時間が増えます。hnswlib のドキュメントでは、ほとんどの用途は M = 12〜48 で足り、埋め込みのように次元が高く高い recall が要るデータでは 48〜64 くらいまで上げる、とされています^[4]。

efConstruction は、点を入れるときにどれだけ広く候補を探すかです。大きいほど「本当に近い点」とつながった質の良いグラフになりますが、作る時間が延びます。ある程度より上げても質は良くならないので、目安として、作ったあとに efSearch = efConstruction で M 件を探した recall が 0.9 を下回るなら、まだ上げる余地がある、という確かめ方が紹介されています^[4]。

この 2 つはグラフを作るときに決まり、あとから変えるには作り直しが要ります。一方、efSearch だけは検索のたびに変えられます。層 0 で持っておく候補の数で、返したい件数 k 以上にする必要があります^[4]。精度と速さの調整は、まずここで行います。

Animation 6 のとおり、efSearch は小さいところで少し上げるだけで recall が大きく上がり、100% に近づくほど同じ伸びに多くの計算が要るようになります。「どこまで精度を取りに行くか」を、検索の用途ごとに決めるのがチューニングの中心です。

8実際に使うとき

Faiss では、M を作るときに渡し、efConstruction と efSearch は属性で設定します^[3]。efConstruction はグラフを作る add の前に決めておく必要があり、efSearch は検索の前ならいつでも変えられます。

import faiss

d = 768                                  # ベクトルの次元
index = faiss.IndexHNSWFlat(d, 32)       # M = 32
index.hnsw.efConstruction = 200          # add の前に決める
index.add(xb)                            # xb: (n, d) の float32

index.hnsw.efSearch = 64                 # 探すときに変えられる
D, I = index.search(xq, 10)              # 近い 10 件の距離と番号

OpenSearch では、ベクトルのフィールドを定義するときにパラメータを書きます^[6]。距離の測り方（space_type）もここで決めます。efSearch にあたる値は、インデックスの設定や検索のリクエストで指定します。なお、OpenSearch や Elasticsearch の中で使われている Lucene では、M を maxConn、efConstruction を beamWidth と呼びます^[5]。

PUT my-index
{
  "settings": { "index.knn": true },
  "mappings": {
    "properties": {
      "embedding": {
        "type": "knn_vector",
        "dimension": 768,
        "method": {
          "name": "hnsw",
          "engine": "lucene",
          "space_type": "l2",
          "parameters": { "m": 16, "ef_construction": 100 }
        }
      }
    }
  }
}

どの実装でも、まずは既定値で作り、実際のクエリで recall と応答時間を測りながら efSearch を動かす、という順番が手堅いです。それでも recall が足りないときに、M や efConstruction を上げて作り直します。

9弱いところ

HNSW は速くて扱いやすい一方で、グラフを持つ方式ならではの弱点もあります。

10参考文献

1. [1]Yu. A. Malkov, D. A. Yashunin. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4), 2020（arXiv 2016） doi:10.1109/TPAMI.2018.2889473
2. [2]Y. Malkov, A. Ponomarenko, A. Logvinov, V. Krylov. Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems, 45, 2014
3. [3]Meta. Faiss indexes. Faiss Wiki（GitHub）
4. [4]nmslib. HNSW algorithm parameters. hnswlib（GitHub）
5. [5]Apache Lucene. Lucene99HnswVectorsFormat. Lucene 9.12 API ドキュメント
6. [6]OpenSearch. Methods and engines. OpenSearch Documentation
7. [7]水野航太. GIF で見る、Faiss と Lucene のベクトル検索. Zenn, 2026
8. [8]W. Pugh. Skip lists: a probabilistic alternative to balanced trees. Communications of the ACM, 33(6), 1990