Vector indexes: IVF, PQ, HNSW と実用ベクトル検索の基礎¶
Verified license
- License: mixed — Faiss library paper is CC BY 4.0; Johnson et al. 2017, Malkov & Yashunin 2016, and additional ANN papers listed below are arXiv non-exclusive unless otherwise noted
- 検証日: 2026-05-24
- 検証方法:
pwsh -NoProfile -File scripts/check-arxiv-license.ps1 - このページの掲載モード: summary-only
このページで扱う「インデックス」¶
ここでのインデックスは、単に「ベクトル DB が内部に持つデータ構造」ではなく、近傍探索の計算量・メモリ・再現率・更新コストを決める IVF, PQ, HNSW などの ANN / vector similarity search index を指す。
実験用・小規模なら、FAISS の IndexFlatIP / IndexFlatL2 のような全件走査でもよい。特にコサイン類似度はベクトルを L2 正規化して内積検索に落とせるので、件数が少ないうちは総当たりが最も単純で、実装ミスも少ない。
しかし実用規模では、以下の制約が支配的になる。
- N: ベクトル件数
- d: 次元数
- k: 返す近傍数
- latency budget: ユーザー操作面で許容される待ち時間
- recall target: 近似探索で落としてよい正解率
- memory budget: RAM / VRAM / SSD の上限
- update pattern: 追加・削除・再学習・再構築の頻度
- filtering: metadata filter とベクトル探索の組み合わせ
DB 選定は「どの DB が人気か」ではなく、この制約に対してどのインデックスが合うかで決まる。
読むべき中心文献¶
| 技術 | 代表文献 / 実装 | 位置づけ | ライセンス確認 |
|---|---|---|---|
| FAISS 全般 | Douze et al., "The Faiss library" | IVF, PQ, HNSW, GPU 検索などを実装する代表的ライブラリの設計説明 | CC BY 4.0 |
| GPU brute-force / PQ | Johnson, Douze, Jégou, "Billion-scale similarity search with GPUs" | brute-force, k-selection, PQ 系検索を GPU で高速化する設計 | arXiv non-exclusive |
| HNSW | Malkov & Yashunin, "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs" | グラフベース ANN の代表的手法 | arXiv non-exclusive |
| PQ | Jégou, Douze, Schmid, "Product Quantization for Nearest Neighbor Search" (IEEE TPAMI 2011) | 圧縮表現でメモリと距離計算を削る古典的基礎 | IEEE TPAMI 掲載 (HAL にプレプリント inria-00514462)。ここでは本文転載せずリンクのみ |
| ScaNN / AVQ | Guo et al., "Accelerating Large-Scale Inference with Anisotropic Vector Quantization" | anisotropic vector quantization による MIPS / retrieval 高速化 | arXiv non-exclusive |
| DiskANN / streaming graph | DiskANN / FreshDiskANN 系 | SSD / streaming update を意識した graph ANN | FreshDiskANN は arXiv non-exclusive。NeurIPS DiskANN 本体は外部 proceedings 参照 |
| GPU graph | CAGRA / BANG 系 | GPU 並列性を意識した graph ANN / billion-scale ANN | arXiv non-exclusive |
| filtered ANN | Window filters / Filtered-DiskANN 系 | metadata filter と ANN の衝突を扱う | arXiv non-exclusive / ACM 等、個別確認 |
Flat / brute-force¶
Flat index は全ベクトルとクエリの距離を計算する。計算量は素直に O(Nd)。
使える場面¶
- N が小さい
- d が小さい
- QPS が低い
- GPU に載る
- recall 100% を基準値として測りたい
- ANN チューニング前の ground truth を作りたい
実用上の意味¶
Flat は「遅いからダメ」ではなく、評価基準として重要。IVF / PQ / HNSW の recall を測るには、まず exact search の結果が必要になる。
IVF: Inverted File Index¶
IVF はベクトル空間を coarse centroid に分割し、クエリに近いクラスタだけを探索する考え方。
- build 時: k-means などで
nlist個の coarse centroid を作る - insert 時: 各ベクトルを近い centroid の posting list に入れる
- search 時: クエリに近い
nprobe個の list だけを走査する
主要パラメータ¶
| パラメータ | 意味 | 効き方 |
|---|---|---|
nlist |
coarse cluster 数 | 大きいほど list が細かくなるが、学習・管理が難しくなる |
nprobe |
search 時に見る list 数 | 大きいほど recall が上がり、latency も上がる |
| training data | centroid 学習に使うサンプル | 分布ズレがあると recall が落ちる |
判断ポイント¶
IVF は「候補集合を減らす」技術。データ分布が比較的安定していて、再学習・再構築を許容できる場合に扱いやすい。一方で、動的更新が多い、分布が時間で変わる、filter 条件で list が極端に偏る場合は注意が必要。
PQ: Product Quantization¶
PQ は d 次元ベクトルを複数の sub-vector に分け、それぞれを小さな codebook の ID で表す。目的は主に メモリ削減 と 距離計算の高速化。
直感¶
float32 の生ベクトルを大量に RAM に置くと、件数が増えた瞬間にメモリが支配的になる。PQ はベクトルを短いコードに圧縮し、クエリとの距離を lookup table で近似計算する。
トレードオフ¶
- メモリは大きく減る
- キャッシュ効率が上がる
- ただし距離は近似になる
- 圧縮誤差が recall / ranking 品質に効く
- 再ランキング用に raw vector を別保持する設計もある
IVF + PQ¶
実用では IVF と PQ を組み合わせることが多い。
- IVF で見る list を減らす
- PQ で list 内のベクトルを圧縮表現のまま距離計算する
- 必要に応じて候補を raw vector で rerank する
これは「候補数を減らす」と「候補 1 件あたりのメモリ・計算を減らす」を同時に行う設計。
HNSW: Hierarchical Navigable Small World graph¶
HNSW は近傍グラフを作り、クエリから近いノードへ greedy に辿るグラフベース ANN。階層構造により、上位層で大まかに近づき、下位層で細かく探索する。
主要パラメータ¶
| パラメータ | 意味 | 効き方 |
|---|---|---|
M |
各ノードが持つリンク数の目安 | 大きいほど recall が上がりやすいがメモリ増 |
efConstruction |
構築時探索幅 | 大きいほど高品質なグラフ、構築は遅い |
efSearch |
検索時探索幅 | 大きいほど recall が上がり、latency も上がる |
判断ポイント¶
HNSW は高 recall / 低 latency を出しやすく、多くのベクトル DB が採用する。ただし、グラフのエッジを保持するためメモリ消費が大きい。削除・大量更新・厳しい filter 条件との相性は実装依存で、DB 選定時に確認が必要。
ScaNN / AVQ: partitioning + quantization の別系統¶
ScaNN は、Google 系の ANN 実装としてよく参照される。論文上の中心は anisotropic vector quantization (AVQ) で、内積検索で重要な方向の誤差をより強く見る量子化として読める。
実用上の意味は、単に「ベクトルを圧縮する」ではなく、検索スコアに効く誤差をどう最小化するかという設計にある。PQ 系を使う場合でも、圧縮率だけでなく、ランキング品質に効く distortion を意識する必要がある。
DiskANN / FreshDiskANN: SSD と更新を含む graph ANN¶
DiskANN 系は、全データを RAM に置く前提を崩し、SSD を使って billion-scale の ANN を扱う方向。グラフ探索をベースにしつつ、ノード近傍やベクトルをどの階層のストレージに置くかが設計の中心になる。
FreshDiskANN は streaming update を意識した系統で、実運用で避けにくい追加・削除・鮮度の問題に近い。DB 選定では、静的 benchmark の recall/latency だけでなく、更新時の index maintenance を見る必要がある。
CAGRA / BANG: GPU graph ANN¶
GPU 検索は brute-force や PQ だけでなく、graph ANN でも重要になっている。CAGRA や BANG のような系統は、graph construction / graph traversal を GPU 並列性に合わせて設計する。
GPU を使う場合、理論上の計算量だけでなく、memory coalescing、warp divergence、k-selection、host-device transfer などが latency に効く。
Filtered ANN¶
実アプリでは「ベクトルで近いもの」だけでなく、「tenant_id が同じ」「公開範囲が一致」「時刻範囲内」などの filter が必ず入る。
filtered ANN は難しい。post-filter だと候補が消えて recall が落ち、pre-filter だと index の探索性が壊れることがある。DB 選定では、HNSW / IVF の名前だけでなく、filter 実装が pre-filter か post-filter か、filter selectivity が低い時にどうなるかを見る。
その他: ScaNN / DiskANN / CAGRA など¶
IVF, PQ, HNSW は基本語彙だが、実運用ではさらに以下のような方向がある。
- ScaNN / AVQ: partitioning + quantization + score-aware quantization で高速化する Google 系手法 / 実装
- DiskANN / FreshDiskANN: SSD、ストレージ階層、streaming update を意識した graph ANN
- CAGRA / BANG / GPU graph index: GPU 並列性を意識した graph ANN
- filtered ANN: metadata filter と ANN を両立させる方向
- hybrid sparse+dense: BM25 / SPLADE と dense retrieval を併用する方向
このページではまず DB 選定に効く基礎語彙として IVF / PQ / HNSW を押さえ、その周辺にある量子化・GPU・SSD・filter の問題へ広げる。
DB 選定に効く質問¶
| 質問 | 見るべき技術要素 |
|---|---|
| 100% recall が必要か、近似でよいか | Flat vs ANN |
| メモリに全 raw vector を置けるか | PQ / scalar quantization / disk index |
| 低 latency が最優先か | HNSW, GPU flat, IVF tuning |
| 大量 update があるか | HNSW update 実装、IVF 再学習、segment merge |
| metadata filter が多いか | pre-filter / post-filter / filtered ANN |
| クラウド費用を抑えたいか | 圧縮、disk index、sharding |
| 日本語・専門語の exact match が重要か | sparse retrieval / hybrid search |
| RAG の再ランキングを入れるか | candidate recall 重視、cross-encoder / LLM rerank |
小規模実験から実用へ移る目安¶
まずは FAISS Flat でよい。
- L2 正規化 + inner product で cosine を再現
- exact search を ground truth とする
- 件数・次元・QPS を測る
- top-k の評価セットを作る
次に ANN を入れる。
- HNSW: まず高 recall / 低 latency を狙う
- IVF: 件数が多く、クラスタリングで候補削減したい場合
- PQ: メモリが支配的になった場合
- IVF+PQ: billion-scale / GPU / 圧縮検索を考える場合
このプロジェクトへのメモ¶
「セマンティック検索」はユーザー操作面に近いので、インデックス設計が体感速度に直結する。ここを「RAG の一部」と雑に呼ぶと、LLM 推論層の待ち時間と混ざって議論が壊れる。
このページの要点は、インデックスは DB の付属機能ではなく、検索システムの計算機科学そのものということ。
Attribution¶
- Original paper: The Faiss library
- Authors: Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre-Emmanuel Mazaré, Maria Lomeli, Lucas Hosseini, Hervé Jégou
- Source: https://arxiv.org/abs/2401.08281
- License: CC BY 4.0
- Changes: Japanese study commentary, selection of related index concepts, summary framing, and formatting were added by the maintainer of this notebook.
- Disclaimer: This is an unofficial study note. No endorsement by the original authors is implied.
Additional sources used in summary-only mode:
- Original paper: Billion-scale similarity search with GPUs
- Authors: Jeff Johnson, Matthijs Douze, Hervé Jégou
- Source (read here): https://arxiv.org/abs/1702.08734 · https://ar5iv.labs.arxiv.org/html/1702.08734 · https://arxiv.org/pdf/1702.08734
- License: arXiv non-exclusive (第三者再配布の許諾なし)
- Original paper: Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
- Authors: Yu. A. Malkov, D. A. Yashunin
- Source (read here): https://arxiv.org/abs/1603.09320 · https://ar5iv.labs.arxiv.org/html/1603.09320 · https://arxiv.org/pdf/1603.09320
- License: arXiv non-exclusive (第三者再配布の許諾なし)
- Original paper: Accelerating Large-Scale Inference with Anisotropic Vector Quantization
- Authors: Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, Sanjiv Kumar
- Source (read here): https://arxiv.org/abs/1908.10396 · https://ar5iv.labs.arxiv.org/html/1908.10396 · https://arxiv.org/pdf/1908.10396
- License: arXiv non-exclusive (第三者再配布の許諾なし)
- Original paper: CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs
- Authors: Hiroyuki Ootomo, Akira Naruse, Corey Nolet, Ray Wang, Tamas Feher, Yong Wang
- Source (read here): https://arxiv.org/abs/2308.15136 · https://ar5iv.labs.arxiv.org/html/2308.15136 · https://arxiv.org/pdf/2308.15136
- License: arXiv non-exclusive (第三者再配布の許諾なし)
- Original paper: FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search
- Authors: Aditi Singh, Suhas Jayaram Subramanya, Ravishankar Krishnaswamy, Harsha Vardhan Simhadri
- Source (read here): https://arxiv.org/abs/2105.09613 · https://ar5iv.labs.arxiv.org/html/2105.09613 · https://arxiv.org/pdf/2105.09613
- License: arXiv non-exclusive (第三者再配布の許諾なし)
- Original paper: Approximate Nearest Neighbor Search with Window Filters
- Authors: Joshua Engels, Benjamin Landrum, Shangdi Yu, Laxman Dhulipala, Julian Shun
- Source (read here): https://arxiv.org/abs/2402.00943 · https://ar5iv.labs.arxiv.org/html/2402.00943 · https://arxiv.org/pdf/2402.00943
- License: arXiv non-exclusive (第三者再配布の許諾なし)
- このページに含まれるもの: 自分の要約・解説、技術選定メモ、短い技術用語の説明のみ。
- このページに含まれないもの: 原文全文、原文の段落単位コピー、全文翻訳、図表転載。
- Disclaimer: This is an unofficial study note. No endorsement by the original authors is implied.