近似最近傍探索とは？HNSW・IVF・PQの選び分けとRecall調整を実装目線で解説【2026年版】

100万件のベクトルから上位10件を厳密に取り出すなら、1クエリごとに100万回の距離計算が発生します。次元数が768なら、乗算だけで7.68億回。この計算量を捨てて「おそらく上位10件」を数ミリ秒で返す方式が、近似最近傍探索（ANN、Approximate Nearest Neighbor）です。この記事では、HNSW・IVF・PQという3系統の構造がそれぞれ何を犠牲にしているのか、pgvectorやMilvusのどのパラメータがその犠牲を制御しているのか、そしてRecallの目標値からパラメータを逆算する手順までを扱います。採用を見送ってよい条件も、件数とQPSの数字で言い切ります。

まとめ：近似最近傍探索を採る条件と、厳密探索で足りる境界線

近似最近傍探索とは、クエリベクトルに最も近いものを厳密に求める代わりに、一定割合の取りこぼしを許して探索範囲を削り、応答時間を桁で縮める方式です。厳密解との一致度を示す指標がRecallで、上位10件を返す検索ならRecall@10が品質の物差しになります。速度と精度は独立に決められません。交換関係の上でどこに点を置くかを決める作業。それがANNの実装です。

構造は3系統。グラフをたどるHNSW、空間をクラスタに割って一部だけ見るIVF、ベクトルを圧縮してメモリに載せるPQで、実務ではIVFとPQのように組み合わせます。最初の1本を選ぶなら、件数が数万から数千万でメモリに余裕があるうちはHNSWが既定解です。pgvectorならmを16、ef_constructionを64のまま作り、検索側のhnsw.ef_searchだけを動かして目標Recallに合わせる順序が最短になります。

逆に、採らないほうがよい場面もはっきりしています。データが10万件程度でQPSが1桁なら、全件走査のほうが実装も運用も軽く済みます。構築時間、メモリ、調整工数、Recallの監視。これらを払う価値が出るのは、応答時間の要件を全件走査で満たせなくなってからです。

厳密な最近傍探索が破綻する計算量と、近似が交換している速度と再現率

近似を入れる前に、何が壊れるから近似するのかを数字で押さえます。

全件走査がO(N×d)で伸びる構造と、100万件規模で応答が詰まる境界

厳密な最近傍探索は、全ベクトルとの距離を計算して並べ替えるだけの処理で、計算量は件数Nと次元数dの積に比例します。10万件×768次元なら約7,680万回の積和演算。単一コアでも数十ミリ秒の領域に収まるため、この規模なら近似は不要です。

問題は1桁増えたときに起きます。100万件で秒間100クエリを捌く要件が乗ると、必要な演算量は毎秒768億回の規模です。SIMD命令で定数倍は改善できても、Nに比例する構造そのものは変わりません。この一次関数を折るために、探索前にデータ側へ構造を作っておくのがインデックスの役割になります。

製品側からの整理はベクトル化とインデックス構造から理解するベクトルデータベースの仕組みにあるため、本記事はアルゴリズムと調整の側だけを扱います。

Recall@kとQPSの交換関係を1本の曲線として読む評価の型

ANNの性能は単一の数値では表せません。横軸にRecall、縦軸にQPS（毎秒クエリ数）を取った曲線として扱うのが標準で、ANN-Benchmarksをはじめとする公開比較もこの形式です。同じインデックスでも探索パラメータを動かせば曲線上を移動するため、「HNSWは速い」という言い方には意味がありません。Recall 0.95のときに何QPS出るのか。比較はこの条件を揃えて初めて成立します。

Recall@10は、厳密探索で得た上位10件のうち何件を近似探索が拾えたかの割合です。10件中9件なら0.9。上位数件を生成モデルへ渡すRAG用途では0.90から0.98の帯に目標を置くことが多く、0.99を超えたあたりから探索コストが急に立ち上がります。曲線の右端は費用対効果が悪い領域だと理解しておくと、パラメータの上げすぎを避けられます。

次元が増えるほど距離差が縮む現象と、埋め込み次元を削る判断の基準

高次元空間では2点間の距離が平均値のまわりに集中し、最も近い点と平均的な点の差が相対的に縮みます。次元の呪いと呼ばれる現象です。差が小さいほど探索の打ち切り判断が難しくなり、同じRecallを保つのに見るべき候補数が増えます。次元数はメモリ消費だけでなく探索コストにも二重に効きます。

対処は2つ。1つはMatryoshka表現学習に対応した埋め込みモデルを選び、1536次元を768次元や256次元に切り詰める方法です。もう1つはhalfvecのように精度を落とした型で保持する方法。前者は検索品質に直接影響するため、切り詰めた次元でのRecall@10を実測してから採否を決めます。モデル側の選定基準は埋め込みモデルとは？仕組みと日本語モデルの選び方・RAG実装での判断基準【2026年版】で扱っています。

HNSW・IVF・PQという3系統のインデックス構造と、それぞれが崩れる条件

3系統は「何を省くか」が違い、その違いが得意なデータ規模と苦手な運用条件に直結します。

グラフ型HNSWのMとef_constructionが構築時間とメモリに効く関係

HNSW（Hierarchical Navigable Small World）は、Malkov と Yashunin が2016年に提出した arXiv:1603.09320 が原典です。各ベクトルをノードとして近いもの同士を辺でつなぎ、そのグラフを階層化します。上の層は疎で長距離の移動に使い、下の層ほど密になる。検索は最上層の入口から貪欲に近い隣へ移動し、層を降りながら目的地へ近づきます。

調整点は2つです。mは各ノードが持つ辺の本数で、増やせばRecallが上がる代わりにメモリ消費と構築時間が膨らみます。ef_constructionは構築時に保持する候補リストの長さで、大きいほど質の高い辺が選ばれますが構築が遅くなる。どちらも作り直さないと変えられません。対して探索時の候補リスト長は作り直さずに変更できます。ここが調整順序を決める理由です。

HNSWが崩れるのはメモリが先に尽きる場合です。グラフの辺はベクトル本体とは別に保持されるため、1億件規模では辺だけで数十GBに達します。ここからはディスク常駐型のVamana系（Subramanya ら NeurIPS 2019）や量子化との併用へ切り替える判断が要ります。階層グラフの内部構造と、pgvectorやMilvusで既定値が食い違う理由はHNSWとは？階層グラフの仕組みとM・ef_constructionの決め方を実装目線で解説【2026年版】にまとめました。

クラスタ分割型IVFのnlistとnprobeで探索範囲を絞る仕組みと限界

IVF（Inverted File）は、k-means系のアルゴリズムでベクトル空間をクラスタに分割し、各ベクトルを最寄りのクラスタに登録しておく方式です。検索時はクエリに近いクラスタだけを開いて走査します。全体の1%だけ開けば計算量も約1%。単純ですが効きます。

クラスタ数がnlist、検索時に開く数がnprobeです。pgvectorではlistsとivfflat.probesという名前になり、READMEは100万行までなら行数を1000で割った値、それ以上なら行数の平方根を出発点として示しています。ivfflat.probesの既定値は1。そのままでは1クラスタしか見ないためRecallが低く出ます。

IVFの弱点は境界です。クエリの真の最近傍が、開かなかった隣のクラスタに落ちていれば取りこぼします。nprobeを増やせば緩和できますが、その分だけ走査量が戻る。もう1つの弱点は重心が学習データに依存する点で、分布が変われば再学習しない限り偏りが蓄積します。

積量子化PQでメモリを圧縮する原理と、再ランキングで精度を戻す手順

PQ（Product Quantization）は Jegou らが2011年に IEEE TPAMI で示した圧縮手法です。ベクトルをm個の部分に分割し、部分ごとのコードブックで最も近い代表点の番号だけを保持します。768次元の float32 は3,072バイトですが、96個の部分に分けて各8ビットで表せば96バイト。32分の1になります。

距離計算も速くなります。クエリ側は各部分と代表点との距離をあらかじめ表にしておき、検索時は番号を引いて足すだけ。乗算が消えます。ただし保持しているのは代表点であって元のベクトルではないため、距離は近似値になり、近い候補同士の順位が入れ替わります。

この誤差を戻す定番の手順が再ランキングです。PQで粗く上位100件から500件程度を取り、その候補だけを元の精度のベクトルで計算し直して上位10件を確定します。MilvusのSCANNが持つreorder_kやwith_raw_dataはこの工程のためのオプション。候補数を増やすほど精度は戻り、その分だけ読み出しが増えます。

構築時間・メモリ・更新耐性で見る3系統の比較と、初手で選ぶ既定値

迷ったらHNSWから入って構いません。理由は更新耐性です。IVF系は重心の学習を前提とするため初期データが少ないと後から偏る一方、HNSWは1件ずつ挿入してもグラフが伸びます。メモリが読めない段階で圧縮系に手を出すと、パラメータが2組に増えて切り分けが難しくなる点も避けたい理由です。

pgvector 0.8系とMilvusで見るパラメータ名の対応と、最初に触る値

製品ごとに名前が違うだけで、指しているものは共通です。対応表を1枚持っておけば、製品を移っても調整の勘所が使い回せます。

pgvectorのmとef_construction、ef_searchが効く場所

pgvectorは PostgreSQL の拡張として動き、2026年8月時点の最新リリースは v0.8.6 です。HNSWの作成時パラメータはm（既定16）とef_construction（既定64）、検索時はhnsw.ef_search（既定40）をセッション単位で設定します。格納型の上限はvectorが2,000次元、halfvecが4,000次元、sparsevecが非ゼロ1,000要素です。

次元の大きいモデルを使う場合はhalfvecへの切り替えか次元の切り詰めが前提になります。距離指標そのものの選び方はコサイン類似度とは？計算式・仕組みと類似検索での実装を実装目線で解説を参照してください。

フィルタ併用で件数が足りなくなる問題とiterative_scanでの回収

実務でいちばん踏むのが、WHERE句との併用でヒット件数が足りなくなる現象です。インデックスは指定件数ぶんの候補を返しますが、そこへ後段のフィルタが掛かると残りが目減りします。テナントIDや日付で絞る設計だと、10件欲しいのに3件しか返らない状態に。

pgvector 0.8系は回収手段として反復スキャンを持ちます。hnsw.iterative_scanにはstrict_orderとrelaxed_orderがあり、ivfflat.iterative_scanはrelaxed_orderのみ。既定は無効なので、明示的に有効化しないと従来どおりの挙動です。距離順を保つstrict_orderは遅く、緩和を許すrelaxed_orderは速い。アプリ側で再ソートするなら後者で足ります。絞り込み後に全体の0.1%しか残らない選択率では反復スキャンでも走査量が膨らむため、テナント単位でテーブルを分けます。

MilvusのIVF_PQやHNSW_SQなど種別名とpgvector側の対応関係

Milvusはメモリ型だけでもIVF_FLAT、IVF_SQ8、IVF_PQ、HNSW、HNSW_SQ、SCANNなどを持ち、ディスク型は別枠です。命名は「基本構造＋量子化方式」の組み合わせで、HNSW_SQはグラフ型にスカラー量子化、IVF_PQはクラスタ型に積量子化。この読み方が分かれば初見の種別名でも中身の見当がつきます。製品ごとの制限値はMilvusとは？v3.0の外部コレクション・インデックス選定・デプロイ形態【2026年版】に整理してあります。

Recall目標から逆算するパラメータ調整の手順と、測り方でつまずく箇所

調整は勘ではなく手順です。正解セットを先に作り、探索パラメータだけを動かして曲線を引く。

全件走査で正解セットを作りRecall@10を測るまでの5工程の組み方

1. 本番データから代表的なクエリを200件から1,000件サンプリングする
2. インデックスを使わない全件走査で上位10件を求め、正解セットとして保存する
3. インデックスを作成し、同じクエリを探索パラメータの既定値で流す
4. 正解セットとの一致件数を数え、クエリ平均のRecall@10を算出する
5. 探索パラメータを段階的に上げ、Recallと所要時間の組を記録する

正解セットは一度作れば使い回せます。目視評価で済ませると、パラメータを変えた効果が測れません。クエリは実際の検索ログから取り、無ければ想定質問を人手で書いて代用します。件数は200件で傾向が見え、1,000件で安定します。

ef_searchとnprobeを動かして曲線を引く順序と、打ち切りの目安

最初に動かすのは探索時パラメータだけです。HNSWならhnsw.ef_searchを40から80、160、320と倍にしていき、各点でRecallと平均応答時間を記録します。IVFならivfflat.probesを1から2、4、8、16と倍にする。作り直しが不要なので、1回のインデックス構築で曲線全体が引けます。

目標Recallに届かない、あるいは届いたが応答時間が要件を超える。どちらかに当たった時点で、初めて構築時パラメータへ手を付けます。mを16から32へ、ef_constructionを64から200へ。作り直しが発生するので構築時間とディスク消費も記録します。

打ち切りの目安は、探索パラメータを倍にしてもRecallの改善が0.005未満になった点。0.99を狙うより0.95で止め、浮いた時間をリランキングや検索前処理に回したほうが最終的な検索品質は上がります。

平均レイテンシだけで判断して本番で詰まる測定の落とし穴と対処法

測定でよく壊れるのは、平均値だけを見ているときです。グラフの入口から遠いクエリやクラスタ境界に落ちたクエリでは探索が長引き、p95やp99が平均の3倍を超えます。体感するのは尾のほう。記録はp50・p95・p99の3点で残します。

もう1つは同時実行の扱いです。1クエリずつ順番に投げた測定は本番の並列負荷を再現していません。HNSWの探索はメモリ帯域を強く使うため、並列度を上げるとスループットが頭打ちになる点が出てきます。想定QPSの2倍まで負荷を掛け、曲線が寝る位置を確認しておくとインスタンス選定を外しません。ウォームアップ後に毎回異なるクエリを流す手順も併せて守ります。

近似最近傍探索を採用しないと判断してよい条件と、代わりに置く設計

ここは言い切ります。ANNは万能の高速化手段ではなく、払うコストが見合う条件のときだけ採るものです。

10万件・低QPSなら全件走査で足りると言い切れる根拠と試算の手順

10万件×768次元の全件走査は積和演算にして約7,680万回です。現行世代のCPUがSIMD命令で毎秒数百億回の積和を回せることを踏まえれば、単一クエリの距離計算は数ミリ秒に収まります。秒間10クエリ程度なら、pgvectorでインデックスを張らず距離順に並べる素朴な実装で要件を満たせます。

この構成の利点はRecallが常に1.0である点です。取りこぼしがないため、精度の問題が起きたときにベクトル検索そのものを疑わずに済みます。切り分けの速さは応答時間の数ミリ秒より価値が大きい。

試算は3つの数字で足ります。件数N、次元数d、想定QPS。N×d×QPSが毎秒10億回を下回るうちは全件走査を第一候補にし、超えてから初めてインデックスを検討します。

更新が多いデータでIVFを選ぶと再構築で詰まる失敗パターンと回避

IVF系を初期データ1万件で構築し、そのまま100万件まで追加していく。これが典型的な失敗パターンです。重心は構築時のデータで決まるため、後から追加されたベクトルが特定のクラスタへ偏ります。開いたクラスタに大量のベクトルが入って走査が終わらない、狙いのベクトルが別クラスタに散ってRecallが落ちる、という状態に陥ります。

症状は「日が経つほど遅くなる」「特定カテゴリの検索だけ精度が悪い」という形で出ます。原因が重心のずれなのでnprobeを上げても根本は直りません。回避策は、データが揃ってから構築する、定期的に再構築する、最初からHNSWを選ぶ。日次で文書が増え続けるRAGの索引なら3番目が素直です。再構築を選ぶなら、別名で新インデックスを作って参照先を切り替える二重化まで設計しておきます。

RAGの精度不足がANNではなく埋め込みと分割にある場合の切り分け

「RAGの検索結果が的外れなので、ANNのパラメータを調整したい」という相談は、切り分けから始めます。全件走査で厳密な上位10件を取り、それでも欲しい文書が入らないなら原因はANNではありません。埋め込みモデルが日本語の意味を捉えていないか、チャンク分割が文脈を切っているか、対象文書に答えが書かれていないかのどれか。

Recallが0.95なら厳密上位10件のうち9.5件は拾えている計算で、的外れな結果の原因としては小さすぎます。キーワード一致が効くべき問い合わせを落としているなら、ハイブリッド検索とは？RAGでBM25とベクトル検索を統合する仕組み・RRF・実装コードの系統で語彙一致を補うほうが効果的です。検索工程全体の組み立てはリトリーバルとは？RAGの検索工程の仕組みと実装・精度改善の判断基準【2026年版】で扱っています。

この切り分けから索引構成の設計までを外部に任せたい場合は、RAG構築支援で対応しています。既存データの性質から索引方式とパラメータの初期値を決め、Recallの実測まで含めて設計する進め方です。

よくある質問

近似最近傍探索の実装で問い合わせの多い論点を5つ挙げます。

近似最近傍探索と厳密最近傍探索は結果がどれくらい違いますか？

Recall@10が0.95なら、厳密探索の上位10件のうち平均9.5件を拾えている状態で、残りは順位の近い別候補に置き換わります。RAGのように上位数件を生成モデルへ渡す用途では体感差がほとんど出ません。1件の取りこぼしが結果を変える重複検出や網羅性の要る全件抽出では、Recall 1.0を保証する厳密探索を選びます。

HNSWとIVFはどちらを先に試すべきですか？

データが増え続ける運用ならHNSWからです。IVFは重心を学習で決めるため構築時点の分布に依存し、初期データが少ないと後から偏ります。HNSWは1件ずつの挿入でグラフが伸びるので、育つデータに追随できる構造。件数が固定でメモリを節約したい場合だけ、IVF系に量子化を組み合わせます。

pgvectorでインデックスを張ったのに速くならないのはなぜですか？

まずクエリプランでインデックスが使われているかを見ます。ORDER BY句の距離演算子が作成時の演算子と一致していないと使われません。次にivfflat.probesやhnsw.ef_searchの設定値。IVFFlatの既定は1クラスタしか見ないためRecallが低く出ます。WHERE句との併用時は反復スキャンの設定も併せて見直してください。

ベクトルの次元数はRecallと速度にどう影響しますか？

次元数はメモリ消費と距離計算コストの両方に線形で効き、高次元ほど距離差が縮むため同じRecallに必要な候補数も増えます。1536次元から768次元への切り詰めに対応した埋め込みモデルなら、メモリと計算量を半減できる計算。ただし品質低下の度合いはデータ依存なので、実データのRecall@10と生成結果の質を測ってから決めます。

インデックスの再構築はどのタイミングで必要になりますか？

HNSWは追加に強い一方で削除による断片化が進むため、削除率が全体の2割を超えたあたりが目安。IVF系は分布が変わったときで、件数が構築時の10倍に達した、新しいカテゴリの文書が大量に入った、といった変化が引き金になります。判定は勘に頼らず、保存した正解セットでRecall@10を定期的に測り、目標値を割ったら再構築する運用に落とします。

関連記事

• ベクトル化とインデックス構造から理解するベクトルデータベースの仕組み：製品側から見た索引構造と選定基準
• コサイン類似度とは？計算式・仕組みと類似検索での実装を実装目線で解説：距離指標の計算式と使い分け
• リトリーバルとは？RAGの検索工程の仕組みと実装・精度改善の判断基準【2026年版】：検索工程全体の組み立て方
• 埋め込みモデルとは？仕組みと日本語モデルの選び方・RAG実装での判断基準【2026年版】：次元数と日本語品質の選定基準
• Pineconeとは？サーバーレス型ベクトルDBの料金・制限値・実装と選び分け【2026年版】：索引運用をマネージドに寄せる判断材料