はじめに: 「最も似たもの」を探す問題
LLM 時代の必須技術
2022 年の ChatGPT 以降、RAG (Retrieval-Augmented Generation) は LLM の中核手法となった。構造は単純:
- 文書を Embedding (ベクトル化)。
- ユーザー質問も Embedding。
- 最も類似する文書 を検索。
- LLM に検索結果をコンテキストとして与える。
この 3 番目が Similarity Search である。数百万〜数十億のベクトルから Top-K の最近接 を探す。
素朴な方法の罠
def naive_knn(query, vectors, k):
distances = [cosine_distance(query, v) for v in vectors]
return sorted(enumerate(distances), key=lambda x: x[1])[:k]
- 10 万ベクトル: 0.1 秒。
- 100 万: 1 秒 (遅い)。
- 1 億: 数十秒 (不可)。
- 1,000 次元 x 1 億: 数分 (破滅)。
実サービスは 数十ミリ秒 を求める。根本的に別のアプローチが必要。
精度を譲る
核心の洞察:
「正確な k 個」ではなく「十分に近い k 個」で足りる。
10% の誤差を許せば 1000 倍速い検索 が可能。これが ANN (Approximate Nearest Neighbor) の本質。
本記事の内容
- ベクトル類似度の基礎。
- LSH、IVF、Product Quantization、HNSW、DiskANN、ScaNN。
- 実戦での選択とパラメータチューニング。
1. ベクトル類似度の基礎
距離関数
L2 (Euclidean) 距離:
d(x, y) = sqrt(sum((x_i - y_i)^2))
Cosine 距離:
cos(x, y) = (x . y) / (|x| * |y|)
distance = 1 - cos(x, y)
内積 (Inner Product):
d(x, y) = -x . y (大きいほど類似)
正規化されたベクトル
単位長に正規化すると:
x . y = cos(x, y)(内積 = Cosine)|x - y|^2 = 2 - 2 * cos(x, y)(L2 と Cosine が等価)
OpenAI や Sentence-BERT が正規化済みベクトルを返すのはこのため。
次元の呪い
高次元では:
- すべての点がほぼ等距離。
- 平均と分散の比率が小さくなる。
- 2D/3D の直感が効かない。
実データは 低次元 manifold 上に分布するので ANN が機能する。
Recall の定義
ANN の品質指標: Recall@k。
「真の top-k のうち何個を見つけたか」
recall@10 = 見つけた真の top-10 の個数 / 10。- 1.0 は完全、0.9 は大半の用途で満足、0.5 は不合格。
目標は Recall 0.95 以上 を保ちつつ速度とメモリを最適化。
2. LSH: Locality-Sensitive Hashing
アイデア
LSH は 1998 年に提案された最古級の ANN:
「類似ベクトルを同じハッシュバケットに入れ、クエリ時はそのバケットだけを探す。」
通常のハッシュと逆で、類似入力は同じハッシュ になりやすい。
Random Projection LSH (Cosine 用)
import numpy as np
class CosineLSH:
def __init__(self, dim, num_hashes=32):
self.dim = dim
self.num_hashes = num_hashes
self.projections = np.random.randn(num_hashes, dim)
def hash(self, vector):
signs = np.sign(self.projections @ vector)
return tuple((signs > 0).astype(int))
衝突確率:
P(hash(x) == hash(y)) = 1 - theta(x,y)/pi
LSH テーブルの構築
from collections import defaultdict
class LSHIndex:
def __init__(self, dim, num_tables=10, num_hashes_per_table=16):
self.tables = []
for _ in range(num_tables):
lsh = CosineLSH(dim, num_hashes_per_table)
self.tables.append((lsh, defaultdict(list)))
def add(self, vector, id):
for lsh, buckets in self.tables:
h = lsh.hash(vector)
buckets[h].append((id, vector))
def query(self, vector, k):
candidates = set()
for lsh, buckets in self.tables:
h = lsh.hash(vector)
for id, v in buckets.get(h, []):
candidates.add((id, tuple(v)))
scored = [(id, cosine_distance(vector, v)) for id, v in candidates]
return sorted(scored, key=lambda x: x[1])[:k]
長所: 実装が単純、高速 insert、分散に向く、ストリーミング追加が容易。 短所: Recall が低い (0.7〜0.85)、多数のテーブルが必要、チューニングが難しい。
現代では HNSW/IVF が主流だが、超大規模分散やストリーミング追加では依然有用。
3. IVF: Inverted File Index
アイデア
IVF は FAISS でも定番。
- k-means でベクトル空間を Cluster に分割。
- 各ベクトルは最も近い Centroid に割り当てられる。
- クエリ時は 最も近い Cluster を nprobe 個 だけ検索。
クエリ手順
- クエリ q と全 Centroid の距離計算。
- 最近 nprobe 個の Cluster 選択。
- それらの中のベクトルと正確に距離計算。
- Top-k を返す。
class IVFIndex:
def __init__(self, dim, nlist=100):
self.nlist = nlist
self.centroids = None
self.lists = [[] for _ in range(nlist)]
def train(self, vectors):
from sklearn.cluster import KMeans
kmeans = KMeans(n_clusters=self.nlist)
kmeans.fit(vectors)
self.centroids = kmeans.cluster_centers_
assignments = kmeans.predict(vectors)
for i, c in enumerate(assignments):
self.lists[c].append((i, vectors[i]))
def query(self, q, k=10, nprobe=10):
centroid_dists = np.linalg.norm(self.centroids - q, axis=1)
top_clusters = np.argsort(centroid_dists)[:nprobe]
candidates = []
for c in top_clusters:
for id, v in self.lists[c]:
candidates.append((id, np.linalg.norm(q - v)))
return sorted(candidates, key=lambda x: x[1])[:k]
パラメータ
- nlist: Cluster 数、典型的には
sqrt(N)。 - nprobe: クエリで探す Cluster 数。増やすほど正確だが遅い。
長所: 線形探索より数十倍高速、単純、FAISS で最適化済み。 短所: Training が必要、追加で再均衡が必要、境界付近のベクトル取りこぼし。
4. Product Quantization: メモリ節約の王
問題
1 億 x 1024 次元 float32 = 400 GB。メモリに載らず、ディスクだと遅い。
PQ のアイデア (Jegou et al., 2011)
- 各ベクトルを M 個の subvector に分割 (例: 1024 -> 8 x 128)。
- 各 subspace ごとに独立に k-means (例: 256 Centroids)。
- 各 subvector を 最近の Centroid インデックス (1 byte) に置き換え。
- 1 ベクトル = M バイト。
元: 1024 * 4 = 4096 byte
PQ: 8 byte
圧縮率: 512 倍
エンコード
class ProductQuantizer:
def __init__(self, dim, M=8, nbits=8):
self.dim = dim
self.M = M
self.nbits = nbits
self.dsub = dim // M
self.K = 2 ** nbits
self.codebooks = None
def train(self, vectors):
from sklearn.cluster import KMeans
self.codebooks = np.zeros((self.M, self.K, self.dsub))
for m in range(self.M):
sub = vectors[:, m*self.dsub:(m+1)*self.dsub]
kmeans = KMeans(n_clusters=self.K)
kmeans.fit(sub)
self.codebooks[m] = kmeans.cluster_centers_
def encode(self, vectors):
codes = np.zeros((len(vectors), self.M), dtype=np.uint8)
for m in range(self.M):
sub = vectors[:, m*self.dsub:(m+1)*self.dsub]
dists = np.linalg.norm(
sub[:, None, :] - self.codebooks[m][None, :, :],
axis=2
)
codes[:, m] = np.argmin(dists, axis=1)
return codes
Asymmetric Distance Computation (ADC)
- クエリは 非圧縮 で保持。
- クエリと各 subspace の全 Centroid の距離を事前計算 -> Lookup Table
LUT[M, K]。 - 圧縮ベクトルの距離 = M 回の table 参照の和。
def query_adc(self, q, codes):
lut = np.zeros((self.M, self.K))
for m in range(self.M):
q_sub = q[m*self.dsub:(m+1)*self.dsub]
for k in range(self.K):
lut[m, k] = np.sum((q_sub - self.codebooks[m, k])**2)
distances = np.zeros(len(codes))
for i, code in enumerate(codes):
for m in range(self.M):
distances[i] += lut[m, code[m]]
return distances
距離計算が M 回の参照と加算で済む。原次元 dim の乗算の代わりに M (通常 1/64〜1/128) の操作。
IVF-PQ
FAISS の有名な組合せ:
- IVF で Cluster に絞る。
- 各 Cluster 内を PQ で圧縮保持。
- クエリ時は nprobe Cluster を ADC で高速スキャン。
結果: 100 億ベクトルを数 GB に収め、ミリ秒で検索。Meta 規模の画像検索はこの方式。
import faiss
d = 128; nlist = 1024; m = 8; bits = 8
quantizer = faiss.IndexFlatL2(d)
index = faiss.IndexIVFPQ(quantizer, d, nlist, m, bits)
index.train(training_vectors)
index.add(vectors)
index.nprobe = 32
distances, indices = index.search(queries, k=10)
5. HNSW: グラフベースの革命
アイデア
HNSW (Hierarchical Navigable Small World) は 2016 年発表 (Malkov と Yashunin)。現在の 最高性能 ANN とされ、Pinecone、Weaviate、Qdrant、Milvus、pgvector の既定エンジン。
- ベクトルを Graph で接続。
- 各ノードは近傍 M 個と Edge。
- クエリ時に Graph を辿って最近接を探す。
Greedy Search と Local Minimum
単純な Greedy 探索は Local Minimum に落ちる。近傍は皆遠いが、全体にはもっと近いノードがある場合。
HNSW の多層構造
Layer 2 (sparse): [A --- E --- I]
| | |
Layer 1: [A B D E G I J]
| | | | | | |
Layer 0 (dense): [A B C D E F G H I J K L]
- Layer 0: 全ベクトル、密な接続。
- 上位: ランダム部分集合、疎な接続。「高速道路」。
検索手順
- 最上位 Layer から開始。
- Greedy でその層の最近接を探す。
- 1 層下へ。
- Layer 0 まで繰り返し、最終 top-k を返す。
Skip list に似た構造。上位 = 大域移動、下位 = 詳細探索。
挿入
- ランダム Layer 選択:
L = floor(-log(uniform(0,1)) * mL)。 - 最上位から Greedy 探索で位置特定。
- 各 Layer で最近接 M 個と接続。
- 近傍数が
M_maxを超えたら heuristic pruning。
主要パラメータ
- M parameter: 各ノードの最大近傍数 (既定 16)。
- ef_construction: 挿入時探索幅 (既定 200)。
- ef_search: クエリ時探索幅。
擬似コード
class HNSW:
def __init__(self, M=16, ef_construction=200):
self.M = M
self.M_max0 = M * 2
self.ef_construction = ef_construction
self.mL = 1.0 / np.log(M)
self.nodes = {}
self.layers = defaultdict(dict)
self.entry_point = None
self.max_layer = -1
def search_layer(self, q, entry, ef, layer):
visited = {entry}
candidates = [(distance(q, self.nodes[entry]), entry)]
results = [(-distance(q, self.nodes[entry]), entry)]
while candidates:
dist, curr = heapq.heappop(candidates)
if -results[0][0] < dist:
break
for neighbor in self.layers[layer].get(curr, []):
if neighbor in visited:
continue
visited.add(neighbor)
d = distance(q, self.nodes[neighbor])
if d < -results[0][0] or len(results) < ef:
heapq.heappush(candidates, (d, neighbor))
heapq.heappush(results, (-d, neighbor))
if len(results) > ef:
heapq.heappop(results)
return sorted([(-d, n) for d, n in results])
性能
- Recall 0.95 で線形探索の 100〜1000 倍高速。
- メモリは元データの 1.5〜2 倍。
- 挿入は検索より遅い。
- 削除は難しい (tombstone + 再構築)。
短所
- メモリ前提 (ディスクは不得手)。
- 修正に弱い。
- パラメータに敏感。
6. DiskANN: ディスクベースの ANN
動機
10 億 x 768 次元 = 3TB。RAM に載らない。
Microsoft Research の DiskANN (2019) は SSD で動作 し、1 台のサーバで 数十億ベクトル を処理。
核心アイデア
- Vamana グラフ: 単一層で多様な Edge (
alpha > 1)。 - SSD アクセスを最小化 (数十回の random read)。
- 次ノードの Prefetching。
構成
- ベクトルは SSD。
- 圧縮グラフはメモリ (ノード ID のみ)。
- クエリ時はメモリでグラフを辿り、SSD からバッチでベクトル取得。
性能
- 1 億ベクトル: 8GB RAM + SSD、Recall 0.95 @ 10ms。
- 10 億: 64GB RAM + SSD。
メモリは元の 1/50 程度。Microsoft Bing 検索、Milvus の DiskANN 統合などで利用。
7. ScaNN: Google の回答
Google の ScaNN (2020) は PQ を改良。Anisotropic Quantization で量子化誤差を内積ベースで最適化。Asymmetric Hashing と組み合わせ、Recall と速度で最高水準。Google 検索、YouTube 推薦、Google Photos で使用。TensorFlow で OSS 公開。
8. Vector DB 比較
| DB | エンジン | 特徴 | 向く用途 |
|---|---|---|---|
| Pinecone | HNSW + 独自最適化 | Managed、Serverless | プロダクション |
| Weaviate | HNSW | Schema、GraphQL | 意味検索 |
| Qdrant | HNSW | Rust、filter 強力 | filter + ベクトル |
| Milvus | IVF/HNSW/DiskANN | GPU 対応 | 大規模 |
| pgvector | IVF-Flat、HNSW | PostgreSQL 拡張 | SQL 統合 |
| Elasticsearch | HNSW | 全文 + ベクトル | hybrid 検索 |
| FAISS | 全アルゴリズム | ライブラリ | 研究、カスタム |
| Chroma | HNSW | 開発者向け | プロトタイプ、RAG |
| Redis Stack | HNSW、Flat | Redis + ベクトル | 低遅延 |
pgvector
CREATE EXTENSION vector;
CREATE TABLE items (
id bigserial PRIMARY KEY,
content text,
embedding vector(1536)
);
CREATE INDEX ON items USING hnsw (embedding vector_cosine_ops)
WITH (m = 16, ef_construction = 64);
SELECT id, content, embedding <=> '[0.1,0.2,...]' AS distance
FROM items
ORDER BY embedding <=> '[0.1,0.2,...]'
LIMIT 10;
数百万規模までは十分。数億規模で専用 DB に差をつけられる。
Qdrant
from qdrant_client import QdrantClient
from qdrant_client.models import Filter, FieldCondition, MatchValue
client.search(
collection_name="my_collection",
query_vector=embedding,
query_filter=Filter(
must=[FieldCondition(key="category", match=MatchValue(value="tech"))]
),
limit=10,
)
9. パラメータチューニング
HNSW
M parameter:
- 低 (8〜16): メモリ節約、低次元 (128 以下) 向き。
- 中 (16〜32): 一般。
- 高 (32〜64): 高次元、高 Recall。
ef_construction:
- 100〜200: 高速ビルド。
- 400〜800: 高 Recall。
- 1000+: 最高品質、遅いビルド。
ef_search:
- 50〜100: 高速、Recall 低め。
- 100〜200: 均衡。
- 500〜1000: 最高 Recall、遅い。
レシピ
高 Recall (0.99 以上):
m = 32
ef_construction = 400
ef_search = 200
均衡 (Recall 0.95):
m = 16
ef_construction = 200
ef_search = 100
大規模、メモリ制約:
m = 8
ef_construction = 100
ef_search = 50
# + Product Quantization
次元削減
1536 次元 (OpenAI ada-002) は重い。PCA で 784 次元へ、Matryoshka Embeddings、より小さいモデル (384 次元 Sentence-BERT) など。
10. 実戦シナリオと落とし穴
RAG パイプライン
- 100 万文書、100ms 以内、高 Recall。
- 推奨: Qdrant または Pinecone、HNSW、M=32、ef_search=100、メタデータ filter 併用。
画像類似検索
- 1 億画像、top-100 を Re-ranking、メモリ制約。
- 推奨: Milvus + IVF-PQ、GPU、Recall 0.9 + 精密 Re-ranking。
リアルタイム推薦
- ユーザー + アイテム Embedding、10ms 以内、頻繁更新。
- 推奨: Redis Stack + HNSW、または FAISS in-memory。
落とし穴 1: Cold Start
HNSW はビルドが遅い。100 万ベクトルで数十分。バッチ挿入、バックグラウンドビルド + Swap。
落とし穴 2: 削除・更新
Tombstone + 定期再構築。削除が多ければ Annoy や Swap 方式を検討。
落とし穴 3: Filter の複雑さ
- Post-filter: 結果が少なすぎる。
- Pre-filter: HNSW グラフが部分集合で探索不能。
- Integrated (Qdrant 方式): 最も効率的だが実装が複雑。
落とし穴 4: 次元の呪い
2000 次元超は ANN の効果が落ちる。256〜768 次元推奨。
落とし穴 5: Recall 測定ミス
自分のデータ・クエリで測ること:
def measure_recall(index, queries, exact_answers, k=10):
correct = 0
total = 0
for q, exact in zip(queries, exact_answers):
approx = index.search(q, k)
correct += len(set(approx) & set(exact))
total += k
return correct / total
クイズ
Q1. なぜ「正確な K-NN」でなく「近似 K-NN」なのか？
A. 速度と精度のトレードオフが極端だから。正確な K-NN は O(N*d) で、1 億 x 1024 次元では 1 クエリに数分。ANN は数% の Recall を譲って 1000 倍速を得る。類似度の「正解」は主観的で、Recall 0.95 ならユーザーは違いを感じない。加えて top-100 を ANN で取り、そこに Cross-encoder などで Re-ranking をかければ精度も戻る。「十分に良く、速い」が ANN の哲学。
Q2. Product Quantization はなぜ 500 倍のメモリ節約ができるか？
A. 空間を M 個の subspace に分割して独立に量子化する。1024 次元 float32 (4096 byte) を 8 subvector + 256 Centroids で各 1 byte、計 8 byte に圧縮 (512 倍)。Recall が保たれる理由は 256^8 = 2^64 通りのコード組合せがデータ分布を十分被覆するため。ADC により、クエリは非圧縮のまま M 回の Lookup Table 参照で距離が計算できる。IVF-PQ は Cluster 絞込みと組合せ、大規模検索の事実上の標準。
Q3. HNSW が多層構造を使う理由と各層の役割は？
A. Greedy 探索の Local Minimum を避けるため。ノードは指数分布で Layer が決まり、大半が Layer 0、極少数が上位に入る。検索は最上位から始めて (大域的に正しい近傍へ高速移動)、層を降りながら粒度を細かくし、最後に Layer 0 で top-k を確定する。Skip list に近い構造で、O(log N) 相当の計算量と現行最高水準の Recall-Latency を実現する。
Q4. IVF の nprobe はどうトレードオフを決めるか？
A. nprobe はクエリ時に実際に探す Cluster 数。nprobe=1 は最速だが境界を取りこぼす (Recall 0.6)、nprobe=10 で 0.85、nprobe=32 で 0.95、nprobe=nlist は全探索。チューニングは自分のデータで Recall を測り、目標値 (例 0.95) に達する最小の nprobe を選ぶ。nlist=1000 なら nprobe=32 付近が一般的なスイートスポット。
Q5. HNSW を選ばないほうが良い場面は？
A. (1) メモリが極端に制約 -> IVF-PQ。(2) ディスクベース必須 -> DiskANN。(3) 挿入削除が頻繁 -> Annoy や定期再構築。(4) GPU 環境 -> FAISS IVF-PQ。(5) 10 万以下の小規模 -> 単純な Brute Force。(6) 大量ストリーミング挿入 -> LSH。(7) Filter 主導 -> Qdrant の pre-filter。(8) 既存 SQL スタック活用 -> pgvector。HNSW は強力な既定だが、限界を知ってこそ拡張時に正しい選択ができる。
おわりに
まとめ
- Exact -> Approximate: 速度のための必然の選択。
- LSH: ハッシュベース、ストリーミング向き。
- IVF: Cluster ベース、nprobe でチューニング。
- Product Quantization: メモリ 500 倍節約。
- IVF-PQ: 大規模の標準。
- HNSW: Graph ベース、現行最高の Recall-Latency。
- DiskANN: ディスクベース超大規模。
- ScaNN: Google の Anisotropic Quantization。
選択の要約
| 規模 | メモリ | 推奨 |
|---|---|---|
| 10 万未満 | 余裕 | Brute force |
| 10 万〜1000 万 | 余裕 | HNSW |
| 1000 万〜1 億 | 余裕 | HNSW or IVF-PQ |
| 1 億〜100 億 | 制約 | IVF-PQ or DiskANN |
| 100 億超 | 制約 | DiskANN、ScaNN 分散 |
RAG 時代における重要性
ChatGPT 以降、ほぼ全ての LLM アプリが RAG を使い、その性能とコストはベクトル検索に大きく依存する。遅い検索は UX を損ない、低い Recall は幻覚を招き、巨大なメモリはインフラコストを爆発させる。ANN を理解することで、適切な Vector DB を選び、パラメータを調整し、障害を推定し、将来の最適化機会を見通せる。
参考資料
현재 단락 (1/363)
2022 年の ChatGPT 以降、**RAG (Retrieval-Augmented Generation)** は LLM の中核手法となった。構造は単純: