Deep Dive Note

Inverted File Index

RAGの検索フェーズにおけるベクトル検索高速化手法 Phase 02 — IVF
インデキシング
検索・計算量
数理的視点
クエリ embedding → ANN 検索 → Top-k 取得
区画に分ける

IVF

クラスタベース

ネットワークを辿る

HNSW

グラフベース

圧縮する

PQ

ベクトル量子化

I
Mechanism
「全部見ずに、近い区画だけ探す」 — IVFの基本的な仕組み
核心

基本発想

東京でラーメン屋を探すのに日本全国を回らない。まず「東京」に絞って、その中を探す。IVFはこれをベクトル空間でやっている。

近似最近傍探索 ANN
nprobe=1 → 「新宿だけ」探す
nprobe=10 → 「新宿・渋谷・池袋…10区」探す
パラメータ — 固定

nlist

グループの数。事前に決める設定で「空間をいくつに区切るか」を指定する。一度決めたら変えられない（グループ分けをやり直す必要がある）。

事前設定 k-means
目安: √N（データ件数の平方根）
10万件 → nlist ≈ 316
パラメータ — 可変

nprobe

検索時に見るグループの数。「いくつの区画を探すか」を指定する。検索のたびに自由に変えられる。

検索時設定 Recall制御
小さい → 速いが精度低下
大きい → 遅いが精度向上
Indexing（事前準備）
1
グループ数を決める nlist = 100
↓
2
中心点の初期値を決める
↓
3
k-meansで中心点を最適化 faiss: .train()
↓
4
各ベクトルを最寄りのグループに振り分け faiss: .add()
Search（クエリが来たとき）
5
クエリと全中心点を全件比較 O(nlist)
↓
6
距離が近い順にTop nprobe個の中心点を選ぶ
↓
7
選ばれたグループ内で全件比較 O(nprobe × N/nlist) → Top-k
II
Speed vs Accuracy
「完璧を少しだけ諦めることで、桁違いに速くなる」
核心トレードオフ

nprobeの影響

nprobeが小さいと速いがTop-kの一致率が下がり、nprobeが大きいと一致率は上がるが遅くなる。

速度 精度 Recall
精度測定: 全件比較のTop-5と
IVFのTop-5の共通要素を数える
5/5 = 完全一致、3/5 = 2件取りこぼし
設計判断

nlistの影響

nlistも精度と速度に直接影響する。少なすぎると速くならず、多すぎるとk-meansの学習が重くなり境界の見落としが増える。

nlist=5 nlist=10000 √N
nlist=5 → 1グループ2万件、速くならない
nlist=10000 → 1グループ10件、爆速だが見落とし増
目安: √N（10万件 → ≈ 316）
空間分割

ボロノイ図

「一番近い中心点のグループに入る」。これだけ。各ベクトルについて全中心点との距離を計算し、最も距離が小さい中心点のグループに割り当てる。

Voronoi 最近傍割当
2次元で考えると空間がボロノイ図の形で分割される
nprobe=1
速度 ◎
精度 △
超速い。Top-5が不一致の可能性
nprobe=10
速度 ○
精度 ○
少し遅くなるが、正解とほぼ一致
nprobe=50
速度 △
精度 ◎
全件比較に近い精度。まだ速い
nprobe=k
= 全件比較
全件比較と同じ
III
Computational Complexity
なぜ速くなるのか — 2段階全件比較のコスト構造を分解する
出発点

全件比較の問題

参照資料が N 件あれば N 回の距離計算が必要。N = 100万なら100万回。データが倍なら時間も倍。線形に増え続ける。

Brute-force O(N)
100万件 × 384次元 の内積計算
→ 実用的な応答速度が出ない
核心の式

IVFの計算量

IVFの検索は「2段階の全件比較」。第1段階で中心点だけを見て候補を絞り、第2段階で絞った範囲内を全件比較する。

O(nlist + nprobe × N/nlist)
第1段階: O(nlist) — 中心点との比較
第2段階: O(nprobe × N/nlist) — グループ内比較
nprobe個のグループ × 各 N/nlist 件
なぜ2段階か

コスト構造の直感

空間をnlist個に区切ると、各グループには平均 N/nlist 件が入る。nprobe個のグループだけ見るので、見る件数は nprobe × N/nlist。中心点の比較コスト nlist を足したものが総コスト。

中心点比較 グループ内比較

全件比較（Brute-force）

O(N)
データが倍 → 時間も倍
N = 100,000 → 100,000回

IVF（2段階の全件比較）

O(nlist + nprobe × N / nlist)
第1段階 O(nlist):
  クエリ vs 全中心点
第2段階 O(nprobe × N/nlist):
  nprobe個のグループ × 各 N/nlist 件

なぜこの式になるか — ステップごとの分解

Step 5: クエリと nlist 個の中心点を全件比較 → nlist 回の距離計算
Step 6: Top nprobe個を選ぶ → ソートのコストは nlist に比べ小さいので無視
Step 7: 各グループには平均 N / nlist 件のベクトル。nprobe個のグループを全件比較するので nprobe × N / nlist 回

合計: nlist + nprobe × N / nlist
nlist が大きいと前半が重く、小さいと後半が重い — ここに最適点がある。
IV
Optimal Parameters
nlist と nprobe の最適値を計算量から導く
最適化問題

nlist = √N の導出

コスト f(nlist) = nlist + nprobe × N / nlist の2つの項はトレードオフの関係にある。nlistを増やすと前半が増え後半が減る。相加相乗平均（AM-GM）の不等式から、両項が等しいとき総コストが最小。

AM-GM √N 最小化
a + b ≥ 2√(ab)、等号は a = b のとき
nlist = nprobe × N / nlist を解いて
nlist² = nprobe × N → nlist = √(nprobe × N)
U字カーブ

コスト曲線の直感

nlistが小さすぎると1グループが巨大で後半のコストが爆発。nlistが大きすぎると中心点の比較コストが爆発。底がU字型のカーブになり、その底が √N 付近。

前半コスト 後半コスト バランス点
実用ガイド

nprobeの選び方

nprobeは「Recallをどこまで許容するか」で決める。まず nprobe=1 で速度を測定し、nprobe を 5, 10, 20 と増やしながら Recall が目標（例: 95%）に達する点を探す。

Recall目標 二分探索的
nprobe=1 → Recall測定 → 不足なら倍に
典型的には nlist の 5〜10% あたりで
Recall 95%+ が得られることが多い
TOTAL COST
nlist →
√N 最小
総コスト
nlist + nprobe × N/nlist
U字型になる
前半 O(nlist)
中心点との比較
nlistに比例して増加
後半 O(N/nlist)
グループ内の比較
nlistに反比例して減少
最小点 = √N
AM-GM不等式より
前半 = 後半のとき最小
N nlist nprobe 件/グループ 中心比較 グループ内 合計 vs 全件
100,000 100 1 1,000 100 1,000 1,100 1/91
100,000 100 10 1,000 100 10,000 10,100 1/10
100,000 316 (√N) 1 316 316 316 632 1/158
100,000 316 (√N) 10 316 316 3,160 3,476 1/29
1,000,000 1,000 (√N) 1 1,000 1,000 1,000 2,000 1/500
1,000,000 1,000 (√N) 10 1,000 1,000 10,000 11,000 1/91
10,000,000 3,162 (√N) 10 3,162 3,162 31,620 34,782 1/287
nlist = √N かつ nprobe = 1 のとき、前半と後半のコストが完全に釣り合う。
nprobe を増やしても全件比較より桁違いに少ない計算量で高い Recall が得られる。
Appendix A — AM-GM Derivation

nlist = √(nprobe × N) の導出

コスト関数を f(nlist) = nlist + nprobe × N / nlist とおく。

方法1: AM-GM不等式
任意の正の実数 a, b について a + b ≥ 2√(ab)（等号は a = b のとき）。
a = nlist, b = nprobe × N / nlist とすると:
nlist + nprobe × N / nlist ≥ 2 × √(nprobe × N)
等号条件 a = b、すなわち nlist = nprobe × N / nlist を解くと nlist = √(nprobe × N)。

方法2: 微分
f'(nlist) = 1 − nprobe × N / nlist² = 0 を解いても同じ結果を得る。

実用的な簡略化: nprobe が小さい（1〜数十）とき、√(nprobe × N) ≈ √N。
よって「nlist ≈ √N」が目安として使える。nprobe = 1 なら厳密に √N。
V
FAISS Implementation
Meta（旧Facebook AI）のオープンソースベクトル検索ライブラリ
ライブラリ

FAISS

「データベース」ではなく「アルゴリズムの道具箱」。IndexFlatL2（全件比較）からIndexIVFFlat、HNSWまで複数のインデックスを提供。

Meta OSS IndexIVFFlat IndexFlatL2
quantizer → 第1段階の全件比較用
"Flat" → ベクトルを圧縮せず保持
# IVFインデックスの作成 nlist = 100 quantizer = faiss.IndexFlatL2(dim) # 中心点の管理用 index_ivf = faiss.IndexIVFFlat(quantizer, dim, nlist) # 学習とデータ登録 index_ivf.train(data) # k-meansで中心点を決定 index_ivf.add(data) # 各ベクトルを最寄りのグループに割り当て # 検索 index_ivf.nprobe = 10 distances, indices = index_ivf.search(query, 5) # Top-5検索
VI
Mathematical Perspective
商空間・束・圏論 — IVFの構造を数学で整理する
中心概念

商空間としてのIVF

「同じクラスタに属するものは同じとみなす」ことで、元の世界をk個の代表点だけの世界に縮約する。全件比較（一本の矢印）を商を経由する二本の矢印に分解している。

quotient 同値関係 factorization
精度劣化の理由

商で失われる情報

精度が落ちるのは、同値関係の境界付近にいるベクトルが間違ったクラスタに分類されるから。「本当は近いのに違う同値類に入ってしまった」ペアの情報が消える。

境界問題 情報損失
nprobeの数理

nprobe = 商をほどく操作

nprobe=1は商を全面的に信用。nprobe=kは商を取らない（元の空間に戻る）。nprobeの調整は商空間上の位相を変えている（ε-近傍の膨張）。

ε-近傍 位相空間論
全探索（直接） query ─────────────────────────→ 結果 │ ↑ │ 代表点と比較 │ クラスタ内を探索 ↓ │ V/~（k個の代表点）───────────→ 候補クラスタ
元の世界

100万個のベクトルが一つ一つ区別されている。日本に住む1億2000万人、一人一人が区別される。

商の世界

k個の代表点だけの世界。同じクラスタの点は「同じ」とみなす。47都道府県。同じ県の人は「同じ」。

nprobe=1
「同じ県だけ探す」 — 商を全面的に信用
最速・最低精度
nprobe=5
「隣の県も探す」 — 商を少しほどく
ε-近傍の膨張
nprobe=k
「全県探す」= 商を取らない — 元の空間に戻る
= 全件比較
VII
Broader Perspectives
抽象的な3つの視点と圏論との関係
抽象視点 1

分割の束

全ての「分け方」は順序構造を持ち、束を成す。nlistを選ぶとはこの束の中の一点を選ぶこと。

partition lattice
束の底 (k=1): 全部1グループ → 検索不能
束の頂 (k=N): 全部バラバラ → 全探索と同じ
抽象視点 2

メトリックの劣化

元の距離 d と商の距離 d̃ のズレには上界がある。クラスタが小さいほど商の距離は元の距離に近い。nlistの選択は「メトリックの劣化をどこまで許容するか」の定量的な判断。

距離空間の商
|d(x,y) - d̃(C_i,C_j)| ≤ diam(C_i) + diam(C_j)
圏論との関係

余等化子

商を圏論で言い直すと余等化子（coequalizer）。Embed/検索の構造が随伴、IVFのクラスタリングが余極限（余等化子）に対応する。

coequalizer colimit adjunction
Method 速度 精度 メモリ 適用場面
HNSW ◎ ◎ △（重い） 100万件以下、リアルタイム応答 — デファクトスタンダード
IVF ○ ○ ○ メモリとのバランスが必要な場面
IVF-PQ ○ △ ◎（軽い） 数億件〜、メモリコストが問題になる規模
迷ったらHNSWから始めて、データが増えてメモリが厳しくなったらIVF-PQ。
※
IVF vs Chunking
名前が似ているが別の概念

IVFのグループ分け

ベクトル空間上の話。すでにベクトルになったものを「検索を速くするために」空間的に区画分けする。

vs

チャンク分け（chunking）

テキストの話。元の文書を「LLMに渡せるサイズの断片に切る」作業。

元の文書 → チャンク分け → 各チャンクをembedding → IVFのグループ分け → 検索