高次元ベクトル索引：HNSW と IVF-PQ の内部

なぜ高次元では「全件距離計算」が破綻するのか

埋め込み（embedding）は、文章や画像を 768 次元や 1536 次元といった実数ベクトルへ写したものです。「意味が近い」を「ベクトルが近い」に対応させるので、検索とは「クエリベクトルに最も近い上位 k 件を返す」操作、すなわち 最近傍探索（nearest neighbor search） になります。

素朴にやるなら全 N 件と距離を計算して上位 k を取ります。これが 厳密最近傍（exact kNN） で、計算量は次元 d・件数 N に対して O(N * d)。N が数百万、d が四桁になると 1 クエリで数十億回の積和になり、実時間では返せません。

ではツリーで枝刈りすればよいかというと、ここで 次元の呪い（curse of dimensionality） が立ちはだかります。高次元では任意の2点間の距離が互いに似通い、空間分割（k-d 木など）の枝刈りがほとんど効きません。結局ほぼ全葉を見ることになり、線形走査と大差なくなります。

そこで実務では 近似最近傍探索（ANN: Approximate Nearest Neighbor） を使います。「ごく稀に真の最近傍を取りこぼす」ことを許す代わりに、桁違いの高速化を得る方針です。品質は次の三つの綱引きで測ります。

ANN の二大方式が、グラフを辿る HNSW と、クラスタ＋圧縮の IVF-PQ です。前者は速度と recall、後者はメモリを軸に設計されています。

HNSW：階層型近傍グラフを貪欲に降りる

HNSW（Hierarchical Navigable Small World） は、ベクトルをノードとし「近いもの同士」を辺で結んだ 近傍グラフ を探索する方式です。鍵は、その近傍グラフを 多層 に積むことにあります。

• 最下層（layer 0）は全ベクトルを含む密なグラフ。
• 上の層ほど確率的に間引かれ、ノードが疎になる。各ノードが属する最上層は指数分布で決まる。
• 上層の辺は遠くまで一気に飛べる「高速道路」、下層の辺は近場を細かく結ぶ「一般道」に相当する。

探索はスキップリストのアイデアを多次元へ拡張したものです。最上層の入口から始め、各層で 貪欲法（greedy） によりクエリに最も近づく隣へ移動し、それ以上近づけなくなったら一つ下の層へ降ります。最下層では、訪問候補を保持する優先度付きキューの幅 efSearch を使ったビーム探索で上位 k を絞り込みます。

HNSW 探索（概念）
  entry ← 最上層の入口ノード
  for layer = Lmax down to 1:
      entry ← layer 上で entry から貪欲に「クエリへ最も近いノード」へ移動
  layer 0 で efSearch 幅のビーム探索 → 上位 k を返す

上層で大きく近づき、下層で精密化するため、訪問ノード数は概ね O(log N) に収まります。内訳は、上層の貪欲降下が層数ぶんで概ね O(log N) ノード、最下層のビーム探索が概ね O(efSearch) ノードで、両者は足し算（積ではない）になります。1ノードを評価するたびに d 次元の距離を計算するので、1クエリの計算量はおおよそ (log N + efSearch) * d 相当。efSearch を上げるとビームが広がり recall は上がりますが、距離計算が増えて遅くなります。これが HNSW における recall と QPS のつまみです。

IVF：粗い量子化で探索範囲を切り出す

メモリと探索範囲を抑える別系統が、転置（IVF: Inverted File） です。発想は 全文検索 の転置インデックスや、データを区画へ割り当てる パーティショニング と同じく「全部見ない」ことにあります。

まず学習段階で全ベクトルを k-means で nlist 個のクラスタ（セルと呼ぶ）に分け、各セルの重心（セントロイド）を求めます。各ベクトルは最も近い重心のリスト（転置リスト）に登録されます。これが 粗い量子化（coarse quantization） です。

検索時はクエリと nlist 個の重心だけ距離を取り、近いほうから nprobe 個のセルを選んで、そのセル内のベクトルとだけ距離を計算します。走査対象が N * (nprobe / nlist) に縮むのが効きどころです。

• nprobe を増やす → 多くのセルを見るので recall ↑、ただし走査件数が増えて遅い。
• セル境界をまたぐ近傍を取りこぼすのが IVF の典型的な誤りで、nprobe はその救済つまみ。

ただし IVF 単体ではセル内を厳密距離で走査するため、元ベクトルをメモリに持つ必要が残ります。メモリを本気で削るには、次の直積量子化と組み合わせます。

PQ：直積量子化でベクトルを数バイトに圧縮する

直積量子化（PQ: Product Quantization） は、ベクトルを少数のバイトへ非可逆圧縮しつつ距離を近似計算できるようにする手法です。手順はこうです。

1. d 次元ベクトルを m 個の サブベクトル（各 d/m 次元）に分割する。
2. 各サブ空間ごとに、学習データから k-means で 2^nbits 個（通常 nbits=8 なので 256 個）の代表点からなる コードブック を作る。
3. 各サブベクトルを最も近い代表点の番号（1 バイト）に置き換える。ベクトル全体は m バイトのコードになる。

1536 次元 float32 は約 6144 バイトですが、m=64・nbits=8 なら 64 バイト に圧縮されます。約 96 倍の削減です。これがメモリを1〜2桁減らせる理由です。

距離は 非対称距離計算（ADC: Asymmetric Distance Computation） で近似します。クエリは圧縮せず、クエリの各サブベクトルと各コードブック代表点との距離をあらかじめ表（ルックアップテーブル）に焼いておき、各データ点についてはコード番号で表を引いて m 個を足すだけにします。

ADC（クエリ q と PQ コード c の距離近似）
  前処理: 各サブ空間 j について
          tbl[j][i] = dist( q_j , codebook[j][i] )  ← 256 通りを先に計算
  各データ点 c=(c_1,...,c_m) について
          dist ≈ Σ_j tbl[j][c_j]    ← 表引き m 回の足し算のみ

1点の距離評価が「d 回の積和」から「m 回の表引き加算」に変わり、m は d よりずっと小さい（例 64 対 1536）ので、距離計算そのものも軽くなります。代償は、コードブックの代表点で量子化したぶん 距離が近似値になり recall の上限が下がる ことです。m や nbits を増やせば精度は戻りますが、コードが太りメモリと計算が増えます。なお重心からの残差を量子化する IVFADC（IVF と PQ の標準的な組み合わせ）にすると、同じ m バイトでも精度が上がります。

二方式の使い分け

判断の軸は単純です。RAM に元ベクトルを載せきれて、とにかく速く高 recall が欲しいなら HNSW。件数が RAM を圧迫し、多少の精度低下を許してでもメモリを削りたいなら IVF-PQ。中間として、HNSW のグラフ上のベクトルを PQ で圧縮する HNSWPQ もあり、グラフの隣接リストは残しつつベクトル本体だけ縮めます。

まとめ