近似最近傍探索の内部：HNSW・IVF・PQ

厳密探索がなぜ破綻するか

クエリベクトル q に最も近い上位 k 件を、N 件のデータから探すのが最近傍探索です。素朴な方法は全件と距離を計算する総当たりで、計算量は次元 D を含めて O(N D) になります。N が数百万を超えると、1クエリあたり数十〜数百ミリ秒かかり、スループットが頭打ちになります。

低次元なら kd木やボール木で対数時間に落とせますが、埋め込みベクトルは数百〜数千次元です。高次元では「次元の呪い」により、ほぼ全ての点がクエリから同程度の距離に分布し、木の枝刈りが効かなくなります。結局ほぼ全件を調べることになり、厳密索引の優位が消えます。

そこで実用系は**近似最近傍探索（ANN）を採る。厳密な正解を諦め、「正解上位 k 件のうち何件を取りこぼさず返せたか」を示す再現率（recall）**を品質指標に据えます。recall@10 が 0.95 なら、上位10件の95%を取れているという意味です。再現率を少し下げる代わりに、探索する候補数を劇的に減らすのが共通戦略です。

HNSW：多層グラフを貪欲に辿る

HNSW（Hierarchical Navigable Small World）はグラフ系ANNの代表格で、レイテンシ重視の用途で広く使われます。各ベクトルをノードとし、近いノード同士を辺で結んだ近傍グラフを作ります。検索は、現在地から「クエリにより近い隣接ノード」へ移動し続ける貪欲探索です。

単層グラフだと最適な隣を辿るうちに局所解で詰まったり、遠距離の移動に多くのホップを要したりします。HNSW はノードを確率的に複数の層へ昇格させ、上層ほど疎で長距離の辺を持つ構造にします。検索は最上層の入口から始めて貪欲に降下し、各層で局所最適へ到達したら下の層へ移ります。最上層が高速道路、最下層が一般道に当たり、平均探索量は約 O(log N) に収まります。

挙動を決める主なパラメータは次の通りです。

実運用では efSearch を動かして再現率と速度を連続的に調整します。値を上げるほど探索が広がり取りこぼしが減りますが、距離計算回数が増えて遅くなります。HNSW は全ベクトルをそのまま保持するためメモリ消費が大きく、辺リストの分も加わる点が弱点です。詳細な近傍検索の位置づけはベクトルデータベースも参照してください。

IVF：クラスタで候補空間を絞る

IVF（Inverted File）は転置インデックスの発想を高次元ベクトルへ持ち込んだ手法です。構築時に全ベクトルを k-means で nlist 個のクラスタに分け、各クラスタの重心（セントロイド）を求めます。各ベクトルは最も近い重心の転置リスト（posting list）へ登録されます。

検索ではまずクエリと全重心の距離を計算し、近い順に nprobe 個のクラスタだけを選びます。そして選んだクラスタの転置リスト内のベクトルとだけ距離を比較します。nlist が10000、nprobe が16なら、原理的に探索対象は全体の 16/10000 ほどに絞られます。

nprobe が再現率と速度のつまみです。クエリの真の最近傍が、選ばなかったクラスタの境界付近に潜んでいると取りこぼします。nprobe を増やすほど境界の取りこぼしが減り再現率が上がりますが、走査するベクトルが増えて遅くなります。IVF は重心計算と1段の絞り込みだけなので構築が軽く、グラフ系より省メモリで大規模化しやすい一方、クラスタ境界付近の精度はグラフ系に劣りがちです。

PQ：ベクトルを量子化して圧縮する

PQ（Product Quantization、積量子化）は索引構造ではなく、ベクトルそのものを圧縮し距離計算を高速化する直交した技術です。D 次元ベクトルを m 個の部分ベクトルに分割し、各部分空間ごとに独立した k-means で 2^b 個の代表点（コードブック）を学習します。各部分ベクトルを最も近い代表点の ID（b ビット）に置き換えると、元のベクトルは m 個の ID 列として保存されます。

例えば 768 次元の float32（3072 バイト）を m=96・b=8 で符号化すると 96 バイトになり、約32分の1に縮みます。圧縮効果が「積」になるのは、各部分空間が独立に量子化され、表現できる全体の組み合わせが各部分のコードブックサイズの積になるためで、これが手法名の由来です。

距離計算も速くなります。検索時、クエリの各部分ベクトルと各部分空間の全代表点との距離を事前計算し、小さな距離テーブルに持ちます。各データベクトルとの距離は、その m 個の ID でテーブルを引いて足すだけで近似できます（ADC, Asymmetric Distance Computation）。実距離の計算が m 回のテーブル参照と加算に化けます。代償は量子化誤差で、代表点に丸めた分だけ距離が近似値になり再現率が下がります。ビット幅を削る発想は量子化と蒸留：モデル圧縮の原理と同じ系譜です。

トレードオフの三角形を設計する

ANN設計は、メモリ・速度・再現率を頂点とするトレードオフの中で目的に合う点を選ぶ作業です。三つを同時に最大化することはできません。

判断の起点は規模とメモリ予算です。全ベクトルをメモリに置けてレイテンシ最優先なら HNSW、メモリに収まらない規模なら PQ で圧縮し IVF で絞る IVFPQ が定石です。いずれも efSearch や nprobe で再現率を後から調整できるので、まず代表クエリで recall を実測し、要件を満たす最小の探索幅に詰めるのが実務的な進め方になります。再現率は必ず厳密な正解（総当たりの結果）と突き合わせて測定し、推測で決めないことが肝心です。

埋め込みの性質そのものを理解しておくと索引選択の判断が速くなります。基礎は埋め込み（Embedding）とベクトル検索を参照してください。最終的に、ANN は「どの近似を許容できるか」を決める問題であり、データ規模・許容レイテンシ・必要再現率の三点を先に固定してから手法とパラメータを選ぶのが、最短で実用解へ到達する道筋です。