はじめに

私たちはスピーダ事業のプロダクトチームで企業の検索システムを開発しているチームです。このシステムは単純な企業名などでのキーワード検索にとどまらず、企業の特色といった文章そのものを検索できることを目指しており、基盤には Elasticsearch を採用しています。

こうした「意味で探す」検索を支えているのがベクトル検索です。しかし、すべてのベクトルとの距離をまじめに計算する全探索は、実用的な規模になると現実的ではありません。そこで必要になるのが、賢く候補を絞って高速に近いものを探す ANN（近似最近傍探索） であり、代表的なアルゴリズムとして HNSW と IVF があります。

本記事では、各ベクトル検索手法を紹介したうえで、HNSW と IVF を実際に動かし、精度や速度、メモリ使用量などの観点から両者を比較した実験結果をご紹介します。

なぜベクトル検索なのか

従来のキーワード検索（BM25 などの全文検索）は単語の一致で文書を探します。そのため企業検索では、会社名や事業内容などに含まれる言葉を知っていないと目的の企業にたどり着けません。「こういう特徴を持つ企業を探したい」といった漠然とした探し方は苦手です。

そこで役立つのが、単語ではなく意味で探すベクトル検索です。私たちのシステムでは、各企業を簡潔に説明した文章などをベクトル化しておき、「どんな企業か」を文章で検索できるようにしています。キーワードが一致しなくても意味が近ければヒットするので、例えば「AI を活用して物流の効率化に取り組む企業」のような自然文でも、その特徴に合う企業が見つかります。

ベクトル検索の基礎

埋め込みと類似度

ベクトル検索の土台になるのが埋め込み（Embedding）です。これは、文章を意味を表す数値の並び（ベクトル）に変換する技術で、大量の文章で学習した埋め込みモデルを使います。例えば「太陽光発電のベンチャー」という文章を入れると、[0.12, -0.34, ...] のような数百〜数千個の数字の並びが返ってきます。

埋め込みモデルは、意味の近い文章どうしが似た向きのベクトルになるように学習されています。だからこそ、ベクトルの「向きの近さ」を測れば、文章どうしの「意味の近さ」がわかります。この近さは内積や コサイン類似度 といった指標で数値化します。

つまりベクトル検索とは、クエリをベクトルに変換し、それに近いベクトルを持つ文書を近い順に上位 k 件（top-k）取り出す処理だと考えられます。

一番素朴なやり方: 全探索（exact kNN）

最もシンプルな方法は、全文書とクエリの距離をすべてまじめに計算する全探索（exact kNN）です。必ず正確な top-k が得られますが、データ件数に比例して計算量が増えていきます。

数十万〜数百万社の企業に対して検索しようとすると、1 クエリごとに全件と距離を計算するのは計算コスト的に現実的ではありません。そこで少しの誤差は許す代わりに、圧倒的に速くするというアプローチが欲しくなります。

ANN（近似最近傍探索）という考え方

ANN（Approximate Nearest Neighbor）は、全部の距離を計算する代わりに、賢く候補を絞って近いものを探すアプローチです。完全一致（exact）を捨てる代わりに、実用的な速度を得られます。

ANN では 精度（recall）・速度・コスト といった要素がトレードオフの関係にあります。このバランスをどう取るかが、ANN を使ううえでの肝になります。

ANN のアプローチには、木構造系（Annoy など）やハッシュ系（LSH）、量子化系（PQ）などさまざまな系統があります。本記事ではその中でも代表的な次の 2 系統を取り上げ、比較します。

グラフ系: 近いベクトル同士をあらかじめ辺でつないでグラフを作っておき、その辺を辿って近いベクトルを探す（代表例: HNSW）
クラスタ系: 事前にベクトルをクラスタに分け、近いクラスタだけを探す（代表例: IVF）

HNSW と IVF の仕組み

HNSW: 多層グラフを辿って探す

HNSW（Hierarchical Navigable Small World）は、近いベクトル同士をあらかじめ辺でつないでおき、その辺を辿って目的地に近づくグラフ系の手法です。全ベクトルと距離を測る代わりに「より近づけそうな隣」へ移動を繰り返すことで、距離計算の回数を大きく減らします。

特徴は、グラフを多層構造にしている点です。上層ほど疎、下層ほど密になっており、上層の長い辺でおおまかに目的地へ近づき、下層へ降りながら精密に詰めていきます。地図を「広域→市街地→番地」とズームインするイメージです。

HNSW は高い精度を高速に出しやすい反面、グラフをメモリに常駐させるためメモリを多く使い、投入時にグラフを構築するためデータ投入が重くなります。

IVF: クラスタで候補を絞る

IVF（Inverted File）は、ベクトル空間をあらかじめ複数のクラスタ（中心点＝セントロイドを持つ、似たベクトルの集まり）に分割しておき、検索時はクエリに近い一部のクラスタだけを探すクラスタ系の手法です。空間をエリアごとに小分けにしておくイメージです。

検索ではまずクエリと各クラスタの中心点を比べて近いクラスタをいくつか選び、そのクラスタに属するベクトルだけ距離を計算します。「クエリが入っていそうなエリアだけ」に絞ることで、計算対象を一気に減らせます。

IVF はグラフを常駐させないぶんメモリは比較的軽い一方、クラスタの中心を決める事前のモデル学習が必要で、その学習時間が構築コストに乗ってきます。また、データが増えると中心の取り直しが必要になり追加・更新が苦手です。

実験環境

データ: MIRACL の日本語サブセット（ja）。50 万件の文章を 1024 次元にベクトル化して投入
環境: OpenSearch の k-NN プラグイン（エンジンは Faiss）上に HNSW / IVF のベクトルインデックスを構築。類似度の比較は内積で統一
正解: クエリと全文章の内積を総当たりで計算し、本当に近い順に並べた top-k（exact top-k）

ANN は近似なので、この exact top-k をどれだけ拾えたかで精度を測ります。

なお、私たちの本番システムは Elasticsearch ですが、今回の実験は OpenSearch 上で行いました。Elasticsearch のベクトル検索は基本的に HNSW 系で、IVF（クラスタ系）を使うには Enterprise ライセンスが必要なためです。OpenSearch なら Faiss エンジン経由で HNSW / IVF の両方を同じ土俵で比較できるので、こちらを採用しました。

どちらの手法も「どれだけ広く探すか」を決めるパラメータ（HNSW は ef_search、IVF は nprobes）を持ちます。今回はこのパラメータを少しずつ変えながら、精度と速度がどう変わるかを検証します。

測定する指標は次のとおりです。

精度: recall@20（exact top-20 をどれだけ拾えたか）
速度: サーバ側レイテンシ took（p50/p95/p99）、並列負荷時のスループット QPS
メモリ / ディスク: グラフの常駐メモリ、インデックスの保存サイズ
構築コスト: 投入 docs/sec、学習込みの総構築時間、グラフ再構築の所要時間

具体的な計測手順は少し細かいので下記にまとめました。

計測方法の詳細（クリックで展開）

クエリとリクエスト回数 MIRACL ja dev の 301 クエリを使います。レイテンシは 1 クエリずつ逐次（並列度 1）で計測し、各クエリで 3 回のウォームアップを捨てたあと 20 回ずつ本計測します（301 × 20 ≒ 6,000 リクエスト）。並列にするとクライアント側のキュー待ちがレイテンシに混ざるため、レイテンシ計測はあえて逐次にしています。値はサーバが返す took（純粋な検索時間）を指標とします。

スループット（QPS） レイテンシとは別に、16 並列のワーカーが 301 クエリを順ぐりに投げ続ける負荷フェーズを設けています。5 秒ウォームアップしたあと、20 秒間で捌けたリクエスト数 ÷ 経過秒を QPS とし、同時に負荷時のレイテンシ（p95）も記録します。逐次のレイテンシだけでは分からない「同時アクセス下でどれだけ捌けるか」を見るためです。

メモリ 2 系統で測ります。1 つは OpenSearch の統計 API（/_plugins/_knn/stats）から取れる k-NN グラフの常駐メモリ。ただし後述の BBQ のようにグラフをディスク側に置く方式はここに載らず 0 と出てしまいます。そこでもう 1 つ、インデックスのシャードが載っている Pod の実メモリ（cgroup の memory.current ＝ RSS + ページキャッシュ）を直接読み、両方式を同じ土俵で比べます。実メモリは cold → warm → peak の 3 点で測り、公平を期すため cold はインデックスを閉じて Pod を再起動しキャッシュを空にした状態、warm はウォームアップ後、peak は負荷をかけたあとの値としています。

ディスク・正解・その他 ディスクはインデックスの store size を使います。recall の正解（exact top-k）は、コーパス全件との内積を総当たりで計算してオフラインに用意しておきます（OpenSearch 上での厳密検索は 1 クエリ 200 秒近くかかり非現実的なため）。類似度は全手法内積（innerproduct）で統一し、top-k は 20 件、各パラメータ点（ef_search / nprobes）はインデックスを作り直さずクエリ単位で切り替えて測っています。インデックス構築時のパラメータは HNSW が m=16 / ef_construction=200、IVF が nlist=4096 です。

なお、各インデックスは計測前に force-merge で 1 セグメントに揃え、バックグラウンドのマージが動いていない定常状態で測っています（セグメント数が揃っていないと、ディスクサイズやレイテンシが手法間・試行間でぶれて公平に比べられないためです）。セグメント数そのものが速度に与える影響は、後述の「セグメント数と速度」で別途検証します。

実験結果: HNSW vs IVF

精度と速度のトレードオフ

ef_search（HNSW）/ nprobes（IVF）を振って、recall@20 とスループットを測りました。

ここからわかるのは、ざっくり次の 2 点です。

1 セグメントに揃えた今回は、両手法の速度差は小さい。 パラメータを上げれば両手法とも recall は伸び、その分の速度低下もそこまで大きな差はありませんでした。
ただし同じ recall なら HNSW の方がやや速く・高スループットという結果になりました。

サーバ側レイテンシ took の動きも見ておきます。パラメータを上げても p95 はおおむね 9〜10ms 前後で横ばいで、レイテンシが跳ねるのは高負荷側の一部だけでした。

実測値（recall@20 / レイテンシ / QPS）

手法	パラメータ	recall@20	took p50 / p95 (ms)	QPS（16 並列）
HNSW	ef_search=16	0.942	8 / 10	約 325
HNSW	ef_search=32	0.976	7 / 9	約 322
HNSW	ef_search=64	0.984	7 / 9	約 319
HNSW	ef_search=128	0.994	7 / 9	約 329
HNSW	ef_search=256	0.996	7 / 9	約 299
HNSW	ef_search=512	0.999	8 / 10	約 298
IVF	nprobes=1	0.734	8 / 12	約 288
IVF	nprobes=4	0.921	8 / 10	約 303
IVF	nprobes=8	0.955	8 / 10	約 296
IVF	nprobes=16	0.971	8 / 10	約 291
IVF	nprobes=32	0.983	9 / 10	約 272
IVF	nprobes=64	0.991	10 / 12	約 255
IVF	nprobes=128	0.996	11 / 13	約 212

メモリとディスク

メモリもディスクも、HNSW と IVF でほとんど差は出ませんでした。どちらも圧縮なしでは元のベクトルをそのまま丸ごと保持し、これが容量の大半を占めます。その上に HNSW はノード間をつなぐグラフを、IVF はどのクラスタに属するかの割り当てを持つだけなので、上乗せ分はごくわずかです。実測ではメモリ・ディスクとも HNSW がわずかに大きくなっていますが、これはグラフ構造のぶんだけ余分に持っているためと考えられます。

実測値（メモリ / ディスク）

手法	グラフ常駐メモリ	store size（ディスク）	実メモリ増分（検索時の定常値）
HNSW	約 1.98 GB（33%）	約 4.16 GB	+約 3.98 GB
IVF	約 1.93 GB（32%）	約 4.11 GB	+約 3.89 GB

構築コスト

投入スループット（docs/s）は HNSW と IVF で大きな差はありませんでした。ただし IVF はクラスタ中心を決めるモデル学習が事前に必要で、その分の構築コストが上乗せされます。加えて今回は、書き込みが落ち着いたあとに 1 セグメントへ統合する force-merge（グラフの作り直し） のコストも測りました。ここでは全精度のグラフをまるごと組み直す HNSW が最も重く、IVF を上回りました。

実測値（投入スループット / 構築コスト）

手法	投入スループット	構築コスト（投入＋学習）	1 セグメント統合（force-merge・参考）
HNSW	約 450 docs/s	約 1110s（投入時にグラフ構築）	約 740s
IVF	約 450 docs/s	約 1120s ＋事前のモデル学習（約 1020s）	約 420s

セグメント数と速度

実際の Elasticsearch / OpenSearch では、書き込みが続くとインデックスは複数のセグメントに分かれ、検索はセグメントごとに走って結果をマージします。そのためセグメント数は検索速度に直結します。同じ動作点（recall ≈ 0.99：HNSW ef_search=128 / IVF nprobes=64）のまま、セグメント数だけを変えて測りました（recall はどのセグメント数でも ≈0.99 で保たれ、変わったのは速度だけです）。

IVF はセグメントが増えるほど大きく遅くなるのに対し、HNSW の落ち込みはゆるやかでした。IVF は「近いクラスタを探してからその中を探す」下調べがセグメントごとに毎回発生するためで、force-merge なしの素の状態では、IVF は 26 セグメントの時点で 40 セグメントの HNSW より遅くなっています（took p50 で約 1.5 倍、QPS で約 1.6 倍の差）。本番のように複数セグメントになるほど HNSW が有利です。

実測値（セグメント数別の took p50 / QPS）

セグメント数	HNSW（ef_search=128）	IVF（nprobes=64）
1（force-merge）	7 ms / 約 320 QPS	10 ms / 約 241 QPS
4	8 ms / 約 272 QPS	11 ms / 約 194 QPS
8	10 ms / 約 233 QPS	15 ms / 約 143 QPS
16	13 ms / 約 193 QPS	23 ms / 約 94 QPS
force-merge なし	16 ms / 約 154 QPS（40 セグメント）	24 ms / 約 96 QPS（26 セグメント）

※ took は p50、QPS は 16 並列時。force-merge なしのセグメント数は投入時にできた素の状態で、HNSW は 40、IVF は 26 と手法によって異なります。

ここまでの実験のまとめ

精度と速度: 1 セグメントに揃えると両手法の速度差は小さい。ただし同じ recall なら HNSW の方がやや速く・高スループットだった。
メモリとディスク: 圧縮なしでは HNSW・IVF でほとんど差がない。どちらも元ベクトルをそのまま丸ごと保持し、これが容量の大半を占めるため。グラフを持つぶん HNSW がわずかに大きいだけ。
構築コスト: 投入スループットは同等。ただし IVF はクラスタ中心のモデル学習が上乗せされる。一方で 1 セグメントへの force-merge は全精度グラフを組み直す HNSW の方が重い。
セグメント数: セグメントが増えるほど IVF が大きく遅くなり、HNSW の落ち込みはゆるやか。本番のように複数セグメントになるほど HNSW が有利。

メモリを減らす「量子化」

ここまでは HNSW と IVF をそのまま使う前提で見てきました。ですが両手法とも、ベクトルの 1 つ 1 つの数値をそのままのかたちで保持するため、文書が増えるほど必要なメモリ・ディスクがふくらんでいきます。

そこで登場するのが量子化（Quantization）です。ざっくり言うと、「精度はできるだけ保ちつつ、データをもっと軽くする」ための工夫です。

2 つの量子化: BBQ と PQ

量子化とは、ベクトルの数値をより少ないビット数で近似的に表し、データを軽くする工夫です。今回は 同じ HNSW インデックスに BBQ と PQ をそれぞれ適用して比較します。

バイナリ量子化（BBQ） は、各数値を 1bit まで圧縮し（32x）、精度を 2 段構成で補う方式です。まず圧縮ベクトルで候補をざっくり集め、次に元のベクトルで並べ直します（rescore）。圧縮ベクトルだけメモリに置き元のベクトルはディスクに残すため、メモリを大きく削りつつ精度の低下を抑えられます。投入時に自動で量子化され事前学習は不要。rescore の深さ（oversample_factor）で精度と速度を調整します。

プロダクト量子化（PQ） は、ベクトルを分割し、それぞれを「近い代表点の番号」に置き換えて、元より小さいコードだけを持つ方式です。元のベクトルを残さず済むぶんメモリを大きく削れますが、BBQ のような並べ直しをしないため精度は落ちやすく、事前に代表点を学習しておく必要があります。検索の深さ（ef_search）で精度と速度を調整します。

量子化なしの HNSW と同じ環境で、精度・速度・メモリ・ディスクがどう変わるかを見ていきます。

実験結果: 量子化ありなしの比較

精度と速度への影響

まず HNSW-BBQ です。oversample_factor が小さめでも recall はすでに無圧縮 HNSW とほぼ並び、そこから上げてもわずかに伸びるだけで、到達できる上限も無圧縮 HNSW とほぼ同等でした。単発のレイテンシも、低めの設定では無圧縮とほとんど変わりません。一方で、oversample_factor を上げるほど並列スループットは徐々に低下します。

一方 HNSW-PQ は、BBQ のような並べ直しをせず、圧縮したコードだけで距離を計算します。そのため ef_search を上げても recall は 0.92 前後で頭打ちになり、無圧縮 HNSW（best 約 0.9985）を大きく下回りました。同じ HNSW に載せているのに上限がここまで違うのは、BBQ が元ベクトルで並べ直して精度を取り戻すのに対し、PQ は圧縮したコードだけで距離を決めるという、量子化方式そのものの差によるものです。

HNSW-BBQ の実測値（oversample_factor 別）

oversample_factor	recall@20	took p50 / p95 (ms)	QPS（16 並列）
5	0.991	8 / 11	約 313
10	0.996	8 / 10	約 321
20	0.997	8 / 10	約 291
50	0.998	10 / 12	約 254
100	0.999	12 / 15	約 209

HNSW-PQ の実測値（ef_search 別）

ef_search	recall@20	took p50 / p95 (ms)	QPS（16 並列）
16	0.897	10 / 13	約 268
32	0.907	9 / 11	約 280
64	0.912	9 / 11	約 281
128	0.916	9 / 12	約 273
256	0.916	10 / 12	約 259
512	0.918	10 / 13	約 178

メモリとディスクへの影響

HNSW-BBQ は元のベクトルをディスクに残し、1bit に圧縮したベクトルだけをメモリに置くことで実メモリを約半分（約 −50%）に、HNSW-PQ は元のベクトルを持たず小さな PQ コードだけを置くことで、実メモリを最小クラス（+約 0.4 GB、約 −90%）まで削れました。メモリ削減という一点では、並べ直し用に元ベクトルの一部をメモリに残す BBQ より、コードだけを持つ PQ の方が大きく効きます。

一方ディスク（store size）は HNSW-BBQ・HNSW-PQ とも同程度（無圧縮比約 −40〜44%）。インデックスの full-precision ベクトルが量子化表現（1bit / PQ コード）に置き換わったぶん減りますが、並べ直しや文書取得用に元のベクトルを含む _source がディスクに残るため、この共通の下限に両手法とも張り付き、差はつきません。

実測値（各手法のメモリ / ディスク）

手法	実メモリ増分（検索時の定常値）	store size（ディスク）
HNSW（無圧縮）	+約 3.98 GB	約 4.16 GB
HNSW-BBQ	+約 1.96 GB（約 −50%）	約 2.32 GB（約 −44%）
HNSW-PQ	+約 0.42 GB（約 −90%）	約 2.48 GB（約 −40%）

セグメント数への影響

同じ HNSW をベースにしていても、BBQ と PQ ではセグメント数が増えたときの挙動が変わります。同じ動作点（HNSW-BBQ oversample_factor=10／HNSW-PQ ef_search=128。recall はそれぞれ約 0.996／約 0.92）のまま、セグメント数だけを変えて測りました。

HNSW-BBQ はセグメントが増えても took p50 が 7→9ms とほぼ横ばいで、スループットも約 322→221 QPS とゆるやかにしか落ちません。一方 HNSW-PQ は took p50 が 9→20ms、スループットは約 276→122 QPS と、より大きく落ち込みます。セグメントが増えるほど各セグメントで PQ のコード距離計算をやり直すコストが効いてくるためで、書き込みが続いてセグメントが増える本番環境では、この点でも BBQ が有利になります。

実測値（セグメント数別の took p50 / QPS）

セグメント数	HNSW-BBQ（oversample=10）	HNSW-PQ（ef_search=128）
1（force-merge）	7 ms / 約 322 QPS	9 ms / 約 276 QPS
4	8 ms / 約 281 QPS	10 ms / 約 232 QPS
8	8 ms / 約 261 QPS	12 ms / 約 196 QPS
16	8 ms / 約 235 QPS	16 ms / 約 141 QPS
force-merge なし	9 ms / 約 221 QPS（38 セグメント）	20 ms / 約 122 QPS（38 セグメント）

構築コストへの影響

HNSW-BBQ は投入時に自動で量子化され事前学習が不要なため、構築コストは無圧縮 HNSW とほぼ同じ（投入約 1130s）。しかも 1 セグメントへの force-merge（グラフ再構築）は、圧縮でデータが小さいぶん無圧縮版より軽く済みます（約 360s）。一方 HNSW-PQ は、代表点（コードブック）を学習する必要があり（約 1310s）、さらに HNSW グラフの再構築（force-merge 約 1290s）も重く、構築コストは 3 者の中でもっとも高くつきました。

実測値（各手法の構築コスト）

手法	投入スループット	構築コスト（投入＋学習）	1 セグメント統合（force-merge・参考）
HNSW（無圧縮）	約 450 docs/s	約 1110s（学習不要）	約 740s
HNSW-BBQ	約 440 docs/s	約 1130s（学習不要）	約 360s
HNSW-PQ	約 437 docs/s	約 1145s ＋学習約 1310s	約 1290s

まとめ

今回の 50 万件・1024 次元・OpenSearch という条件で見えたことは、大きく 2 つです。

速度・スループットは HNSW 系が有利。1 セグメントに揃えれば IVF もほぼ並ぶが、書き込みが続いてセグメントが増えるほど HNSW の優位が広がる。
メモリ・ディスクは量子化で大きく減らせる。無圧縮では容量の大半を元ベクトルが占め、HNSW と IVF でほとんど差はなかった。HNSW に量子化を入れて初めて実メモリ・ディスクとも大きく減り、その削減幅は方式しだい（BBQ で実メモリ約 −50%・ディスク約 −44%、PQ で実メモリ約 −90%・ディスク約 −40%）。