\def\vector#1{\boldsymbol{#1}}

ベクトル検索

2026年8月16日 #VectorSearch #ANN

1. 概要

ベクトル検索 (vector search) は文書とクエリーを機械学習モデルによって固定次元の実数ベクトルに変換し、ベクトル空間上での距離の近さによって関連性を評価する検索方式。情報検索における密検索 (dense retrieval) に相当し、クエリーと文書が共通のタームを持たなくても、意味の近さによって照合できる点で全文検索を補う。

ベクトル検索の処理は、文書とクエリーをベクトルに変換する埋め込み (embedding) と、得られたクエリーベクトルに近い文書ベクトルをデータベース内の大量のベクトル集合の中から見つけ出す最近傍検索 (nearest neighbor search) の 2 つに分けられる。前者は検索の品質に、後者は検索の速度と規模に寄与する。このページでは後者、特に大規模なベクトル集合に対して実用的な速度を得るための近似最近傍探索 (ANN; approximate nearest neighbor search) のデータ構造を扱う。

1. 概要
2. 最近傍検索
3. 近似最近傍探索
1. 3.1. 精度・速度・記憶容量のトレードオフ
2. 3.2. 手法の分類
4. 直積量子化
5. 転置ファイルインデックス
6. 局所鋭敏型ハッシュ
7. 階層的経路誘導スモールワールドネットワーク
8. 手法の比較
9. 参考文献

2. 最近傍検索

$d$ 次元のクエリーベクトル $\vector{q} \in \mathbb{R}^d$ とベクトル集合 $X = \{\vector{x}_1, \vector{x}_2, \ldots, \vector{x}_N\} \subset \mathbb{R}^d$ 、および 2 つのベクトル間の距離関数 $\delta$ が与えられたとき、 $\vector{q}$ にもっとも近いベクトルを求める問題を最近傍検索 (NN search) と呼ぶ。 $\begin{equation} {\rm NN}(\vector{q}) = \mathop{\rm arg~min}\limits_{\vector{x} \in X}\, \delta(\vector{q}, \vector{x}) \label{nn} \end{equation}$ 検索システムが必要とするのは最も近い 1 件ではなく関連で順序付けられた一覧の上位であるため、実際には式 ( $\ref{nn}$ ) を距離の小さい順に $K$ 件返すよう一般化した  $K$ -最近傍検索 ( $k$ -NN search) を扱う。ここで $N$ は文書数、 $d$ は埋め込みモデルが出力する次元数であり、実用的な埋め込みモデルでは $d$ は数百から数千の値を取る。

2.1. 距離と類似度

ベクトル検索で用いられる距離や類似度は、ユークリッド距離 ( $L_2$ 距離)、内積、コサイン類似度の 3 つのいずれかを用いることが多い。これらは無関係ではなく、ユークリッド距離の二乗は式 ( $\ref{l2}$ ) のように展開できる。 $\begin{equation} \| \vector{q} - \vector{x} \|^2 = \| \vector{q} \|^2 - 2 \, \vector{q} \cdot \vector{x} + \| \vector{x} \|^2 \label{l2} \end{equation}$ 第 1 項の $\|\vector{q}\|$ はクエリーのみに依存するため文書間の順序付けには影響しない。さらに、すべてのベクトルをあらかじめ $\| \vector{x} \| = 1$ となるように正規化していれば、ユークリッド距離による近傍の順序付けは $\vector{q}$ と $\vector{x}$ の内積による順序と (符号を除いて) 一致し、さらにこれはコサイン類似度とも一致する。埋め込みベクトルを正規化して保存する実装が多いのは、一つのインデックスで 3 つの尺度を同じように扱えるようになるためである。

2.2. 最大内積探索

正規化を前提とせずに内積の大きい順を求める問題は最大内積探索 (MIPS; maximum inner product search) と呼ばれ、最近傍検索とは異なる性質を持つ。内積は式 ( $\ref{ip}$ ) のように分解できる。 $\begin{equation} \vector{q} \cdot \vector{x} = \| \vector{q} \| \, \| \vector{x} \| \cos \theta \label{ip} \end{equation}$ ここで $\theta$ は 2 つのベクトルのなす角である。 $\|\vector{q}\|$ はすべての文書に共通であるため順位には影響せず、順序を決めるのは方向の一致 $\cos\theta$ とベクトルの長さ $\|\vector{x}\|$ の積である。つまりベクトルの長さは、どのようなクエリーに対しても一律にスコアを押し上げる係数として働き、したがって、方向がやや異なっていても長いベクトルの方が上位に来る。

この性質により、ベクトルの向きに意味内容を、長さにクエリーに依存しない優先度を持たせる設計を行うことができる。もっとも典型的な例は行列分解による推薦システムで、ユーザとアイテムをベクトルで表してその内積を嗜好の一致の予測値とするとき、アイテムのベクトルの長さは「誰に対しても選ばれやすい」という人気度に相当する。同様に、クエリーと文書をそれぞれ別のモデルで埋め込みを算出する二塔モデルで、その内積をロジットとしてロジスティック損失で学習するケースでは、文書側のベクトルの長さ (ノルム) がその文書の出現頻度や人気度といった事前確率 (バイアス) を吸収する。文書の品質スコアやバイアス項 $b$ を $\vector{x}' = (\vector{x}, b)$ 、 $\vector{q}' = (\vector{q}, 1)$ のように追加次元として畳み込み、一度の内積計算で意味的な関連度と静的なスコアの両方を評価する手法も同じ考えに基づく。

逆に言えば、ベクトルの長さを 1 に正規化することはこの優先度を捨てる操作である。内積を前提に学習したモデルの出力を正規化してコサイン類似度で検索すると、人気度や品質の情報が失われて順位が変わる。埋め込みモデルがどの尺度で学習されたかによって、正規化してよいかどうかが決まる。

一方で、内積は (特に三角不等式で) 距離の公理を満たさないため、ユークリッド距離などを前提とした最近傍検索のデータ構造をそのまま適用することができない。例えばベクトル自身の内積ついて考えると、内積空間ではノルムが大きい別のベクトルとの内積の方が大きくなる場合があるため、ベクトル自身との内積が最大になるとは限らない。これにより「距離が近いものを辿ってゆけば目的 (クエリー) にたどり着く」という HNSW などの近傍グラフが持つ大前提が適用できなくなる。さらに、クエリーに対する内積の最大値はベクトル集合の凸包 (Convex Hull) の頂点で必ず達成されるため、凸包の内側に存在するベクトルは、いかなるクエリーに対しても最大内積の解になり得ないという性質もある。

この問題を回避するため、実装上は最大内積探索をユークリッド空間における最近傍探索へ帰着させる変換がよく用いられる。まず、検索対象となるすべてのベクトルを $\|\vector{x}\| \le 1$ となるようにスケールした上で、次元をひとつ追加して式 ( $\ref{alsh}$ ) のように変換する [6]。 $\begin{equation} \vector{x}' = \left( \vector{x}, \sqrt{1 - \|\vector{x}\|^2} \right), \qquad \vector{q}' = ( \vector{q}, 0 ) \label{alsh} \end{equation}$ この変換を行うことで変換後のデータ点 $\vector{x}'$ のノルムはすべて $\|\vector{x}'\|=1$ となる。また追加された次元のクエリー側が $0$ であるため、内積 $\vector{q}'\cdot \vector{x}' = \vector{q} \cdot \vector{x}$ がそのまま保たれる。ここで返還後のクエリーとデータ点の間のユークリッド距離 ( $\ref{l2}$ ) の平方を展開すると式 ( $\ref{l22}$ ) のようになる。 $\begin{equation} \| \vector{q}' - \vector{x}' \|^2 = \| \vector{q} \|^2 + \| \vector{x}' \|^2 - 2(\vector{q}' \cdot \vector{x}') \label{l22} \end{equation}$ 前述の通り $\|\vector{x}'\|=1$ であり、 $\|\vector{q}'\|^2$ はクエリーに依存する定数となる。したがって、このユークリッド距離 $\|\vector{q}'-\vector{x}'\|^2$ を最小化することは、元のベクトル間の内積 $\vector{q}\cdot\vector{x}$ を最大化することと意味的に同じである。これにより、既存の L2 距離に基づく最近傍探索アルゴリズムをそのまま最大内積探索に適用できるようになる。このようにクエリーとデータ点に異なる変換を適用することを非対称変換と呼ぶ。

現在ではこのような変換に頼らず、最大内積探索を直接扱うことを前提に設計された手法も開発されている。例えば Google の ScaNN はベクトル量子化を行う際に内積への悪影響が大きい「元のベクトルと平行な方向の量子化誤差」をより重いペナルティとして評価する異方性量子化 (anisotropic vector quantization) を取り入れており、最大内積探索において高い精度を達成している。

2.3. 全探索と次元の呪い

最近傍検索を厳密に解く単純な方法は、クエリーとすべてのベクトルとの距離を計算して上位 $K$ 件を抽出する全探索であり、その計算量は $O(Nd)$ となる。これは事前計算による償却を行わない逐次検索にあたる。

ただし、全探索は計算量の大きさに反して実際には比較的有利な実装上の性質を持つ。この処理は積和演算の繰り返しのみで構成され、条件分岐を含まず、メモリを連続的に読み出すことから、SIMD 命令や GPU による並列化を適用することができる。また、複数のクエリーをまとめれば行列積として扱えるため、最適化された行列演算ライブラリの恩恵も受けられる。文書数が数百万程度の規模であれば、全探索でも実用的な応答時間に収めることは可能である [1]。加えて、インデックスの構築が不要で、厳密解が得られ、文書の追加・削除が即座に反映されるといった利点もある。後述の近似手法の再現率を測るための正解データもこの全探索によって作られる。

一方、 $N = 10^8$ 、 $d = 768$ 程度の規模になると 1 回の検索で数千億回の積和演算が必要となり、これをクエリーごとに繰り返すことは現実的ではない。

低次元であれば k-d 木や R 木を使って探索範囲を枝刈りできる。しかし次元が上がるにつれてベクトル空間が指数的に大きくなり、データは空間の境界付近に薄く広く分散するようになる。その結果、どのベクトルとの距離も「似たような遠い値」となってしまい、「この領域は現在の最良解より遠いので探索不要」という枝刈りの判断がほとんど機能しなくなる。そして最終的にこれらのデータ構造をたどるコストが全探索と同等かそれ以上になる。この現象は次元の呪い (curse of dimensionality) と呼ばれる。

このように、高次元では厳密な全探索の計算コストを本質的に削減することが難しいことから、実用的なベクトル検索ではその厳密性の要件をあきらめ、近似的な手法を採用する。

3. 近似最近傍探索

近似最近傍探索 (ANN; approximate nearest neighbor search) は、真の最近傍を算出する代わりに、検索時間と記憶容量を大きく削減して概ね近い近傍ベクトルを検索する手法の総称である。検索システムでは、最終的な順位を決めるのがこの後の再ランキングであることや、埋め込みベクトル自体が情報要求の近似表現に過ぎないことを考慮すれば、第一段階の検索で厳密性を妥協しても最終的な検索精度やユーザー体験に与える影響は軽微であるという認識が一般的である。

3.1. 精度・速度・記憶容量のトレードオフ

近似の精度評価は一般に再現率 (recall) を用いる。厳密な $K$ -最近傍探索で得られた集合を $R$ とし、近似最近傍探索で得られた $K$ 件の結果を $\hat{R}$ とすると、再現率 recall@ $K$ は式 ( $\ref{recall}$ ) のように表すことができる。 $\begin{equation} {\rm recall}@K = \frac{|R \cap \hat{R}|}{K} \label{recall} \end{equation}$ 近似最近傍探索アルゴリズムはいずれもパラメータで再現率と計算効率を調整することができる。このため ANN-Benchmarks のような一般的なベンチマークでは、再現率を横軸、秒間クエリー処理数 (QPS; queries per second) を縦軸にした曲線で比較する。

現実的な選定ではこれに記憶容量が加わる。単精度浮動小数点で表現した $d$ 次元の埋め込みベクトルは $4d$ バイトの大きさを持つ。 $d = 768$ , $N = 10^8$ の設定では約 300 GB となるため、実際にインデックスをメモリ上に配置できるかは大きな判断材料となる。

3.2. 手法の分類

近似最近傍探索の代表的な手法は、その基本的な発想によって次のように分類できる。

量子化: ベクトルを少ないビット数の符号で近似して記憶容量と距離計算のコストを下げる (直積量子化)。
空間分割: ベクトル集合をクラスタに分け、クエリーに近いクラスタだけを走査する (転置ファイルインデックス)。
ハッシュ: 近いベクトルほど同じ値になりやすいハッシュ関数で候補を絞り込む (局所鋭敏型ハッシュ)。
近傍グラフ: 近いベクトル同士を辺で結んだグラフ上を貪欲に辿る (HNSW)。

これらは排他的ではなく直交する。量子化は候補を絞り込まず、空間分割・ハッシュ・グラフは記憶容量を削減しない。このため実用的な実装では「クラスタで候補を絞り、その中のベクトルは量子化して保持する」のように組み合わせて用いられる。いずれの手法も、ベクトル集合に対して一度だけコードブックやクラスタ、グラフを構築し、その後の検索がそれを繰り返し参照する事前計算による償却の形を取る。

4. 直積量子化

直積量子化 (PQ; product quantization) はベクトルを少数のバイト列に圧縮し、圧縮したままの状態で距離を近似的に計算できるようにする手法である [2]。

4.1. ベクトル量子化

ベクトル量子化 (VQ; vector quantization) は、あらかじめ用意した $K$ 個の代表ベクトル $C = \{\vector{c}_1, \ldots, \vector{c}_K\}$ の中でもっとも近いものの番号でベクトルを表現する。この代表ベクトルの集合をコードブック (codebook)、番号をコード (code) と呼び、コードブックは $k$ -means などで学習する。1 件あたりの記憶容量は $\lceil \log_2 K \rceil$ ビットにまで縮む。

しかし $d$ 次元の空間を直接量子化しようとすると、必要な代表ベクトルの数は次元に対して指数的に増える。 $d = 128$ の空間を各次元あたり 8 分割する程度の粗さで覆うだけでも $8^{128}$ 個の代表ベクトルが必要になり、学習も保持も不可能である。

4.2. 部分空間への分割

直積量子化は、 $d$ 次元のベクトルを $M$ 個の部分ベクトルに分割し、それぞれを独立に量子化することでこの問題を回避する。 $\begin{equation} \vector{x} = ( \underbrace{x_1, \ldots, x_{d/M}}_{\vector{u}_1(\vector{x})}, \ \ldots, \ \underbrace{x_{d - d/M + 1}, \ldots, x_d}_{\vector{u}_M(\vector{x})} ) \label{pqsplit} \end{equation}$ 各部分空間 $m$ について $K$ 個の代表ベクトルからなるコードブック $C_m$ を個別に学習し、ベクトル $\vector{x}$ を $M$ 個のコードの組 $( i_1(\vector{x}), \ldots, i_M(\vector{x}) )$ で表現する。全体として表現できる代表ベクトルは各部分空間のコードブックの直積 $C_1 \times \cdots \times C_M$ であり、その総数は $K^M$ となる。実際に保持しているのは $MK$ 個の部分ベクトルだけであるにもかかわらず、指数的に多い代表点を表現できる点がこの手法の要である。

実装では $K = 256$ としてコードを 1 バイトに収める構成が標準的である。 $d = 128$ , $M = 8$ , $K = 256$ とすると、単精度浮動小数点で 512 バイトだったベクトルが 8 バイトになり、記憶容量は 1/64 に削減される。

4.3. 非対称距離計算

圧縮の効果は記憶容量だけではない。クエリー $\vector{q}$ と圧縮されたベクトルとの距離は、クエリーを復元せずに表引きで求められる。検索の開始時に、各部分空間についてクエリーの部分ベクトルとコードブック内の全代表ベクトルとの距離を計算した表を作る。 $\begin{equation} T[m][j] = \| \vector{u}_m(\vector{q}) - \vector{c}_{m,j} \|^2 \qquad (1 \le m \le M, \ 1 \le j \le K) \label{lut} \end{equation}$ この表の作成に必要な距離計算は $MK$ 回であり、クエリーごとに一度だけ行えばよい。個々のベクトルとの距離は式 ( $\ref{adc}$ ) のように表を $M$ 回引いて加算するだけで得られる。 $\begin{equation} \| \vector{q} - \vector{x} \|^2 \approx \sum_{m=1}^{M} T[m][i_m(\vector{x})] \label{adc} \end{equation}$ $d$ 回の積和演算が $M$ 回の加算に置き換わるため、 $d = 128$ , $M = 8$ であれば距離計算の負荷は 1 桁以上小さくなる。クエリー側を量子化せずに扱うこの方法を非対称距離計算 (ADC; asymmetric distance computation) と呼ぶ。クエリーも量子化して代表ベクトル間の距離表を引く対称距離計算 (SDC) も可能だが、クエリー側の量子化誤差が上乗せされるため精度で劣る。

ただし直積量子化が削減するのは 1 件あたりのコストであって、走査する件数ではない。すべてのベクトルについて表引きを行う限り計算量は $O(NM)$ のままであり、候補を絞り込む仕組みと組み合わせる必要がある。

なお、部分空間を先頭から機械的に区切ると、相関の強い次元が同じ部分空間に偏って量子化誤差が大きくなることがある。ベクトル全体に回転行列を適用してから分割することで各部分空間の情報量を均す最適化直積量子化 (OPQ; optimized product quantization) のような改良が知られている。

5. 転置ファイルインデックス

転置ファイルインデックス (IVF; inverted file index) はベクトル集合をあらかじめクラスタに分割しておき、クエリーに近いクラスタだけを走査することで候補を絞り込む手法である。全文検索の転置インデックスがタームからポスティングリストを引くのと同様に、クラスタからそこに属するベクトルのリストを引くことからこの名前で呼ばれる。

インデックスの構築では、まず $k$ -means によってベクトル集合を $n_{\rm list}$ 個のクラスタに分割し、各クラスタの重心 (セントロイド) $\vector{c}_1, \ldots, \vector{c}_{n_{\rm list}}$ と、それぞれのセントロイドを最近傍とするベクトルのリストを保持する。 $n_{\rm list}$ は $\sqrt{N}$ 程度の値が目安とされる。

検索では、まずクエリーと $n_{\rm list}$ 個のセントロイドとの距離を計算し、近い順に $n_{\rm probe}$ 個のクラスタを選ぶ。続いてそれらのクラスタに属するベクトルだけを走査して上位 $k$ 件を求める。走査するベクトル数は平均して $N \cdot n_{\rm probe} / n_{\rm list}$ 件に減り、 $n_{\rm probe}$ が精度と速度を調整するパラメータとなる。

この手法が真の最近傍を取りこぼすのは、クエリーがクラスタの境界付近にあり、真の最近傍が選ばれなかった隣のクラスタに属している場合である。 $n_{\rm probe} = 1$ では境界付近のクエリーで再現率が大きく落ちるため、実用上は複数のクラスタを走査する。

IVF は候補を絞り込むが記憶容量は削減しないため、直積量子化と組み合わせた IVFPQ (IVFADC) が大規模なベクトル検索の標準的な構成となっている。このとき量子化の対象はベクトルそのものではなく、所属するクラスタのセントロイドからの残差 (residual) $\vector{x} - \vector{c}_i$ とする。残差はベクトルそのものより分散が小さく原点付近に集まるため、同じコードブックの大きさでも量子化誤差を小さくできる。

なお IVF のクラスタは構築時のベクトル集合の分布に基づいて決まる。追加や削除そのものは対応するリストの更新で済むが、扱う文書の分布が当初と変わればクラスタの偏りが大きくなり、再学習が必要になる。

6. 局所鋭敏型ハッシュ

局所鋭敏型ハッシュ (LSH; locality-sensitive hashing) は、近いベクトルほど同じハッシュ値になりやすいハッシュ関数の族を用いて候補を絞り込む手法である [4]。ハッシュテーブルで用いられる通常のハッシュ関数が、入力のわずかな違いを無関係な値に散らすことを目的とするのに対して、局所鋭敏型ハッシュは入力の近さをハッシュ値に残すことを目的とする。

ハッシュ関数族 $\mathcal{H}$ が $(r_1, r_2, p_1, p_2)$ -鋭敏であるとは、 $\mathcal{H}$ からランダムに選んだ $h$ について式 ( $\ref{lsh}$ ) が成り立つことをいう。 $\begin{eqnarray} \delta(\vector{x},\vector{y}) \le r_1 & \Rightarrow & \Pr[h(\vector{x}) = h(\vector{y})] \ge p_1 \label{lsh} \\ \delta(\vector{x},\vector{y}) \ge r_2 & \Rightarrow & \Pr[h(\vector{x}) = h(\vector{y})] \le p_2 \nonumber \end{eqnarray}$ ここで $r_1 \lt r_2$ 、 $p_1 \gt p_2$ である。すなわち近いベクトルの組は高い確率で、遠いベクトルの組は低い確率で衝突する。

コサイン類似度に対する代表的な構成がランダム射影 (random projection; SimHash) である。標準正規分布からランダムに生成した $\vector{a} \in \mathbb{R}^d$ を用いて、ベクトルを超平面のどちら側にあるかの 1 ビットに写す。 $\begin{equation} h_{\vector{a}}(\vector{x}) = \left\{ \begin{array}{ll} 1 & (\vector{a} \cdot \vector{x} \ge 0) \\ 0 & (\vector{a} \cdot \vector{x} \lt 0) \end{array} \right. \label{simhash} \end{equation}$ 2 つのベクトルのなす角を $\theta$ とすると、ランダムな超平面が両者を分離する確率は $\theta / \pi$ であるから、衝突確率は $1 - \theta/\pi$ となり、角度が小さいほど、すなわちコサイン類似度が高いほど衝突しやすいという性質が得られる。

1 ビットでは遠いベクトルもおよそ半数が衝突してしまうため、実際には増幅を行う。 $k$ 個のハッシュ関数を連結して 1 つのキーとすれば衝突確率は $p^k$ となり、遠いベクトルが候補に混入する確率を下げられる (AND による増幅)。一方でこれは近いベクトルの取りこぼしも増やすため、独立に構成した $L$ 個のハッシュテーブルを用意し、いずれかで衝突したものを候補とする (OR による増幅)。近いベクトルが候補に含まれる確率は $1 - (1 - p_1^k)^L$ となり、 $k$ と $L$ の組み合わせで精度と計算量を調整する。

局所鋭敏型ハッシュは、必要な計算量と得られる再現率の関係を理論的に保証できる点が他の手法にない特徴である。実データに対する recall と QPS の関係ではグラフに基づく手法に劣ることが多いが、インデックスがハッシュテーブルの集合に過ぎないため構築が軽く、追加・削除が容易で、ハッシュ値によってデータを分散配置できるという実装上の利点がある。

7. 階層的経路誘導スモールワールドネットワーク

HNSW (hierarchical navigable small world) はベクトルをノード、近いベクトル同士の関係を辺とする近傍グラフ (proximity graph) の上を貪欲に辿ることで最近傍を探す手法である [3]。近年のベクトル検索ライブラリやデータベースで広く採用されている。

7.1. 近傍グラフ上の貪欲探索

近傍グラフでは、各ノードから近傍のノードへ辺が張られている。適当なノードを起点として、隣接ノードのうちクエリーにもっとも近いものへ移動する操作を繰り返し、どの隣接ノードも現在のノードよりクエリーに近くなくなった時点で停止すれば、その位置が最近傍の候補となる。

この単純な貪欲法は局所最適解に陥りやすいため、実際には現在の最良解だけでなく有望なノードを優先度付きキューに保持しながら探索範囲を広げるビームサーチとして実装される。

1.	${\bf function} \ {\rm Search}(q, ep, ef)$
2.	$\hspace{12pt}C := \{ep\}$	// 探索候補
3.	$\hspace{12pt}W := \{ep\}$	// 発見済みの上位 ef 件
4.	$\hspace{12pt}V := \{ep\}$	// 訪問済み
5.	$\hspace{12pt}{\bf while} \ C \neq \emptyset \ {\bf do}$
6.	$\hspace{24pt}c := {\rm nearest}(C, q); \ C := C \setminus \{c\}$
7.	$\hspace{24pt}{\bf if} \ \delta(q,c) \gt \delta(q, {\rm furthest}(W, q)) \ {\bf then \ break}$	// これ以上近づかない
8.	$\hspace{24pt}{\bf for \ each} \ e \in {\rm neighbors}(c) \setminus V \ {\bf do}$
9.	$\hspace{36pt}V := V \cup \{e\}$
10.	$\hspace{36pt}{\bf if} \ \delta(q,e) \lt \delta(q, {\rm furthest}(W,q)) \ {\bf or} \ \|W\| \lt ef \ {\bf then}$
11.	$\hspace{48pt}C := C \cup \{e\}; \ W := W \cup \{e\}$
12.	$\hspace{48pt}{\bf if} \ \|W\| \gt ef \ {\bf then} \ W := W \setminus \{{\rm furthest}(W, q)\}$
13.	$\hspace{12pt}{\bf return} \ W$

パラメータ ${\it ef}$ は保持する候補数であり、大きくするほど探索範囲が広がって再現率が上がる一方、距離計算の回数が増える。検索時に ${\it ef}$ を変えるだけで精度と速度を調整できるため、インデックスを再構築せずに動作点を選べる。

この探索が少ない手数で目的地に到達するためには、グラフがスモールワールド性、すなわち任意の 2 ノード間が少ないホップ数で結ばれている性質を持つ必要がある。近いもの同士だけを結んだグラフでは、遠い出発点からは近傍を一歩ずつしか進めず膨大なホップ数を要する。逆に長距離の辺だけでは目的地の周辺を細かく探索できない。長距離の辺で大まかに近づき、短距離の辺で精密に絞り込むという役割分担が必要になる。

7.2. 階層構造

HNSW はこの役割分担を階層構造として明示的に構成する。各ノードに対して確率的に最大層 $l$ を割り当て、層 $0$ にはすべてのノードが、上の層にいくほど少数のノードだけが所属するようにする。 $l$ は式 ( $\ref{hnswlevel}$ ) のように指数分布に従って決める。 $\begin{equation} l = \lfloor - \ln (u) \cdot m_L \rfloor, \quad u \sim U(0,1), \quad m_L = \frac{1}{\ln M} \label{hnswlevel} \end{equation}$ ここで $M$ は各ノードが持つ辺の数の上限である。上の層ほどノードが疎になるため、そこで結ばれる辺は必然的に長距離の辺となり、下の層ほど短距離の辺で構成される。これは順序付き連結リストに疎な上位層を重ねるスキップリストと同じ考え方である。

検索は最上位層の入口ノードから始め、各層で貪欲探索を行い、その層で到達した最良のノードを次の層の出発点として一つ下の層へ降りる。最下層に到達したところで ${\it ef}$ 件の候補を保持したビームサーチを行い、上位 $k$ 件を返す。上位層で大域的な位置がすでに絞り込まれているため、探索に必要なホップ数は $N$ に対して対数的になる。

インデックスの構築はノードを 1 件ずつ挿入することで行う。挿入するノードの層 $l$ を決めた上で、最上位層から $l$ 層まで降りてその位置を見つけ、 $l$ 層以下の各層で近傍を ${\it efConstruction}$ 件探索し、その中から接続先を選んで双方向の辺を張る。接続先を単純に近い順の $M$ 件とすると、辺が特定の方向のノード群に偏り、その先へ到達できない領域が生じる。このため HNSW では、すでに選んだ接続先のいずれかに対してよりも自分に対して近いノードを優先する枝刈りを行い、辺の方向が多様になるよう選択する。

7.3. 特性

HNSW は同じ再現率に対する検索速度が他の手法より優れていることが多く、ベクトル検索の既定の選択肢とされることが多い。一方で、各ノードが最大 $M$ 本の辺を持つグラフを保持するため、ベクトル本体とは別に相応の記憶容量を必要とする。この点は直積量子化と組み合わせてベクトル本体を圧縮する構成や、グラフを SSD 上に配置する構成で緩和される。

また、ノードの削除はグラフの連結性を壊すため苦手である。実装では削除フラグを立てて検索結果から除外し、一定量に達した時点でインデックスを再構築する方式が採られることが多い。

8. 手法の比較

Table 1. 近似最近傍探索の代表的な手法の特性。
手法	基本的な発想	調整パラメータ	記憶容量	更新
PQ	部分空間ごとの量子化	$M$ , $K$	大幅に削減	容易 (コードブックは要再学習)
IVF	クラスタによる候補の絞り込み	$n_{\rm probe}$	削減しない	容易 (分布の変化に弱い)
LSH	近さを保つハッシュ	$k$ , $L$	ハッシュテーブル分が増加	容易
HNSW	近傍グラフ上の貪欲探索	${\it ef}$ , $M$	グラフ分が大きく増加	削除が苦手

実際の検索システムでは、これらのいずれかを単独で用いるのではなく、Faiss や hnswlib のようなライブラリ、あるいはそれらを内蔵したベクトルデータベースが提供する構成 (IVFPQ、HNSW、HNSW+PQ など) から、扱う件数とメモリ量に応じて選択することになる。Apache Lucene も HNSW による $k$ -最近傍検索を備えており、同一のインデックスでキーワード検索とベクトル検索の両方を扱える。

なお、ここまでに述べたのはいずれも与えられたベクトル集合に対する検索の効率化であって、検索の品質を決めるのは埋め込みモデルである。ANN によって失われる精度は再現率として定量化できるが、埋め込みが情報要求を捉えていなければ、どれだけ厳密に最近傍を求めても適合する文書は得られない。また、キーワード検索が得意とする固有名詞や型番の完全一致はベクトル検索が不得手とするため、実用的な検索システムではハイブリッド検索として両者を併用する。

9. 参考文献

佐藤竜馬. 検索システム ― なぜ検索システムは欲しい情報を見つけられるのか、あるいはなぜ見つけられないのか ―. 講談社 (2026)
Herve Jegou, Matthijs Douze, Cordelia Schmid. Product Quantization for Nearest Neighbor Search. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 33, No. 1, pp. 117-128 (2011)
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, Vol. 42, No. 4, pp. 824-836 (2020)
Piotr Indyk, Rajeev Motwani. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC), pp. 604-613 (1998)
Moses S. Charikar. Similarity Estimation Techniques from Rounding Algorithms. Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), pp. 380-388 (2002)
Anshumali Shrivastava, Ping Li. Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS). Advances in Neural Information Processing Systems 27 (NIPS), pp. 2321-2329 (2014)