FAISSベクトル検索

🔥 Vibe プロンプト

「1万件の128次元ベクトルでベクトル検索を構築。ブルートフォースvs IVFの速度と精度を比較。」

FAISSとは？

FAISS (Facebook AI Similarity Search) はMeta AIが開発した大規模類似検索ライブラリです。数十億のベクトルからミリ秒で最近傍を検索できます。

| 機能 | 性能 | |------|------| | 規模 | 最大数十億ベクトル | | 速度 | ブルートフォース比10-100倍 | | インデックスタイプ | Flat(正確), IVF(近似), HNSW(グラフ), PQ(圧縮) | | GPU対応 | マルチGPU自動シャーディング |

インデックスタイプ

1. Flat Index（正確検索）

IndexFlatL2 / IndexFlatIP: 全ベクトルを保存し、すべてをスキャン。100%再現率だが大規模では低速。

2. IVF（Inverted File）

ベクトルを (N_{list}) 個のクラスタに分割。検索時は (N_{probe}) 個の近傍クラスタのみ探索。計算量: O(N) → O(N_{list} + N/N_{list} × N_{probe})

3. HNSW（階層的ナビゲーション小世界グラフ）

マルチレイヤーグラフを構築。100万ベクトルで >99%再現率、0.5ms検索。

4. PQ（プロダクト量子化）

ベクトルを1/4〜1/32に圧縮。10億ベクトルをメモリ内で検索可能。

実装

import numpy as np
import faiss
import time

np.random.seed(42)
d = 128       # ベクトル次元
n = 10000     # ベクトル数
n_queries = 5
k = 5         # 最近傍数

xb = np.random.random((n, d)).astype('float32')
xq = np.random.random((n_queries, d)).astype('float32')

# 1. ブルートフォース（正確）— IndexFlatL2
index_flat = faiss.IndexFlatL2(d)
index_flat.add(xb)

start = time.time()
D_flat, I_flat = index_flat.search(xq, k)
t_flat = time.time() - start

print(f"=== ブルートフォース (IndexFlatL2) ===")
print(f"検索時間: {t_flat*1000:.2f} ms")

# 2. IVF（近似）— IndexIVFFlat
nlist = 100
quantizer = faiss.IndexFlatL2(d)
index_ivf = faiss.IndexIVFFlat(quantizer, d, nlist, faiss.METRIC_L2)
index_ivf.train(xb)
index_ivf.add(xb)
index_ivf.nprobe = 10

start = time.time()
D_ivf, I_ivf = index_ivf.search(xq, k)
t_ivf = time.time() - start

print(f"\n=== IVF (IndexIVFFlat) ===")
print(f"検索時間: {t_ivf*1000:.2f} ms")
print(f"高速化: {t_flat/t_ivf:.1f}x")

# 精度チェック
correct = sum(1 for i in range(n_queries) if set(I_flat[i]) == set(I_ivf[i]))
print(f"完全一致(top-{k}): {correct}/{n_queries}")

# 3. HNSW（最速近似）— IndexHNSWFlat
index_hnsw = faiss.IndexHNSWFlat(d, 32)
index_hnsw.hnsw.efConstruction = 40
index_hnsw.add(xb)
index_hnsw.hnsw.efSearch = 64

start = time.time()
D_hnsw, I_hnsw = index_hnsw.search(xq, k)
t_hnsw = time.time() - start

print(f"\n=== HNSW (IndexHNSWFlat) ===")
print(f"検索時間: {t_hnsw*1000:.2f} ms")
print(f"高速化: {t_flat/t_hnsw:.1f}x")

correct_hnsw = sum(1 for i in range(n_queries) if set(I_flat[i]) == set(I_hnsw[i]))
print(f"完全一致: {correct_hnsw}/{n_queries}")

インデックス比較

| インデックス | 検索タイプ | 100万ベクトル(128d) | 再現率@10 | |-----------|-----------|-------------------|----------| | Flat | 正確（全探索） | ~500ms | 100% | | IVF (nlist=4096, nprobe=64) | 近似 | ~5ms | ~95% | | HNSW | 近似 | ~0.5ms | ~99% | | IVF + PQ (M=64) | 圧縮近似 | ~4ms | ~90% |

実世界の応用

1. RAG（検索拡張生成）

LLMチャットボットが知識ベースから関連文書を検索し、コンテキストとしてLLMに渡す。100万文書から100ms未満で検索。

2. レコメンデーションエンジン

「これを気に入った人はこれも気に入っています」— Pinterest、Spotify、Instagramがユーザー埋め込みとアイテム埋め込みのベクトル検索でリアルタイム推薦。

3. セマンティック検索

キーワードではなく意味で検索。テキストを埋め込みに変換しFAISSで検索。類義語や文脈を理解。

クエリ: 「安いノートPC」→「格安ラップトップ」もマッチ

4. 画像類似検索

Google画像検索の「類似画像」機能。FAISSはPinterestで数10億の画像から類似検索を駆動。

5. 異常検知

最近傍距離が閾値を超えるものを異常値として検出。不正検知や品質管理に有効。

時間複雑度

| インデックスタイプ | 構築時間 | 検索時間(100万) | メモリ(128d, 100万) | |----------------|---------|----------------|-------------------| | Flat | O(nd) | O(nd) = ~500ms | 512 MB | | IVF | O(nd + nlist×train) | O(nlist×d×nprobe) = ~5ms | 512 MB + オーバーヘッド | | HNSW | O(nd log n) | O(log n×d) = ~0.5ms | 512 MB + グラフ(nd×8) | | PQ | O(nd) + 訓練 | O(nlist×M×4) = ~2ms | 512/32 = 16 MB |

まとめ

FAISS はベクトル類似検索の業界標準
Flat（正確）— 100%再現率、大規模では低速
IVF — 速度と精度の良いバランス、最も一般的
HNSW — 最速の近似検索、QPSが重要なアプリに最適
PQ（プロダクト量子化）— ベクトルを4-32x圧縮
使用例: ChatGPT (RAG)、Pinterest (推薦)、Spotify
規模: 1万（CPU）から10億以上（マルチGPU）