ベクトルデータベースの仕組み — FAISS・HNSWの理論とPython実装

RAG（Retrieval-Augmented Generation）をはじめとする多くのAIアプリケーションでは、「数百万〜数十億のベクトルの中から、クエリベクトルに最も近いベクトルを高速に見つける」処理が必要です。これが近似最近傍探索（ANN: Approximate Nearest Neighbor search）であり、ベクトルデータベースの中核技術です。

素朴に全てのベクトルとの距離を計算する方法（全探索）は $O(Nd)$ の計算量がかかり、$N = 10^8$（1億）のベクトルでは到底実用になりません。しかし、100%の正確さを少し諦めれば（例えば99%の再現率）、計算量を $O(\log N)$ 程度に削減できるアルゴリズムが存在します。

ベクトルデータベースの仕組みを理解することは、以下のような場面で直接役立ちます。

• RAGパイプラインの構築: チャンクの埋め込みベクトルを効率的に検索するインデックスの選択に不可欠です
• セマンティック検索: ドキュメント検索、画像検索、推薦システムなどの基盤技術です
• インデックス設計の最適化: データ量やクエリ要件に応じて、適切なインデックスタイプとパラメータを選択できるようになります

本記事の内容

• 全探索の限界と近似最近傍探索の必要性
• IVF（Inverted File Index）: クラスタリングベースの探索
• HNSW（Hierarchical Navigable Small World）: グラフベースの探索
• PQ（Product Quantization）: ベクトル圧縮による省メモリ化
• FAISSによるインデックス構築と性能比較
• 各手法の理論的な計算量分析

前提知識

この記事を読む前に、以下の記事を読んでおくと理解が深まります。

全探索の限界

ブルートフォース（Flat Index）

最も単純な最近傍探索は、クエリベクトル $\bm{q} \in \mathbb{R}^d$ と全ての格納ベクトル $\bm{x}_1, \ldots, \bm{x}_N \in \mathbb{R}^d$ との距離を計算し、最も近い $k$ 個を返すものです。

$$ \text{kNN}(\bm{q}) = \underset{S \subset \{1,\ldots,N\}, |S|=k}{\arg\min} \sum_{i \in S} \|\bm{q} – \bm{x}_i\|^2 $$

計算量は $O(Nd)$、メモリは $O(Nd)$。$N = 10^6$、$d = 768$（BERT埋め込み）の場合：

$$ \text{計算量} = 10^6 \times 768 \approx 7.7 \times 10^8 \text{ FLOPs} $$

1クエリあたり数十ミリ秒で済むかもしれませんが、$N = 10^9$ になると数十秒かかり、リアルタイム検索は不可能です。

さらに、メモリ使用量は：

$$ 10^6 \times 768 \times 4 \text{ bytes (FP32)} \approx 2.9 \text{ GB} $$

$N = 10^9$ では約3TBとなり、メモリにも載りません。

全探索は100%正確ですが、大規模データには使えません。そこで、精度を少し犠牲にして検索を高速化する近似最近傍探索（ANN）が必要になります。

ANN手法は大きく分けて空間分割系（IVF）とグラフ系（HNSW）の2つがあります。まずIVFから見ていきましょう。

IVF（Inverted File Index）

基本アイデア: クラスタリングによる空間分割

IVFの基本アイデアは、事前にデータベースのベクトルをk-meansでクラスタリングし、検索時にはクエリに近いクラスタだけを探索することです。図書館の本を分類棚に整理し、検索時に関連する棚だけを見るのに似ています。

インデックス構築

1. k-meansで $C$ 個のセントロイド $\bm{c}_1, \ldots, \bm{c}_C$ を学習する
2. 各ベクトル $\bm{x}_i$ を最寄りのセントロイドに割り当てる
3. 各セントロイドに割り当てられたベクトルのリスト（inverted list）を構築する

$$ \text{IVL}(j) = \{i \mid j = \arg\min_{c} \|\bm{x}_i – \bm{c}_c\|^2\} $$

検索

クエリ $\bm{q}$ に対して：

1. $\bm{q}$ と全セントロイド $\bm{c}_1, \ldots, \bm{c}_C$ の距離を計算し、最も近い $\texttt{nprobe}$ 個のセントロイドを選択する
2. 選択されたセントロイドのinverted list内のベクトルとのみ距離を計算する
3. 最も近い $k$ 個を返す

検索の計算量は：

$$ O\left(Cd + \frac{N \cdot \texttt{nprobe}}{C} \cdot d\right) $$

第1項はセントロイドとの距離計算、第2項は選択されたリスト内の全探索です。$C = 1000$、$\texttt{nprobe} = 10$ の場合、探索範囲は全体の約1%に削減されます。

精度と速度のトレードオフ

nprobe を大きくすると精度は上がりますが速度が低下します。このトレードオフはrecall@kで評価します：

$$ \text{recall@}k = \frac{|\text{ANNの結果} \cap \text{真のkNN}|}{k} $$

一般的に nprobe = C の 1〜10% で recall@10 > 0.9 が達成できます。

IVFは実装がシンプルで理解しやすいですが、高次元空間ではクラスタリングの品質が低下し、精度が落ちるという問題があります。次に、グラフベースのアプローチであるHNSWを見てみましょう。

HNSW（Hierarchical Navigable Small World）

Navigable Small Worldグラフ

HNSWは、Small Worldネットワークの性質を利用した探索アルゴリズムです。Small Worldネットワークとは、「ほとんどのノード間が少数のホップで到達可能」なグラフ構造です。社会学の「6次の隔たり」（6 degrees of separation）がその代表例です。

NSW（Navigable Small World）グラフでは、各ノード（ベクトル）は近傍のベクトルへの辺（short-range links）と、遠くのベクトルへの辺（long-range links）の両方を持ちます。探索時は、遠くの辺で大まかな位置に素早く移動し、近くの辺で正確な最近傍に到達します。

階層構造

HNSWは、NSWグラフを複数の解像度レベルに階層化します。

• レベル0: 全てのベクトルが存在する（最も密なグラフ）
• レベル1: ベクトルの一部が存在する
• レベル $l$: 確率 $p = e^{-l / m_L}$ でベクトルが含まれる

ここで $m_L = 1/\ln(M)$ はパラメータで、$M$ は各ノードの最大エッジ数です。

この階層構造は、スキップリスト（Skip List）と類似しています。上位レベルでは少数のノードをジャンプして大まかな位置に移動し、下位レベルで精密な探索を行います。

挿入アルゴリズム

新しいベクトル $\bm{x}$ を挿入する際：

1. ベクトルのレベル $l$ を $\lfloor -\ln(\text{uniform}(0,1)) \times m_L \rfloor$ で決定する
2. 最上位レベルからレベル $l+1$ まで、greedy searchで最近傍を見つける（エントリーポイントの更新）
3. レベル $l$ からレベル0まで、各レベルで最近傍を見つけ、$\bm{x}$ とその近傍の間にエッジを追加する

探索アルゴリズム

クエリ $\bm{q}$ に対する探索：

1. 最上位レベルのエントリーポイントから開始する
2. 各レベルで、現在のノードの近傍を調べ、$\bm{q}$ に最も近いノードに移動する（greedy search）
3. 改善がなくなったら、次の（低い）レベルに降りる
4. レベル0で $\texttt{ef\_search}$ 個の候補を探索し、最も近い $k$ 個を返す

計算量の分析

HNSWの探索計算量は：

$$ O(d \cdot M \cdot \log N) $$

$M$ は各ノードのエッジ数（通常16〜64）、$\log N$ は階層の数です。$N = 10^9$ でも $\log N \approx 30$ なので、探索は非常に高速です。

一方、インデックスの構築は各ベクトルの挿入に $O(d \cdot M \cdot \log N)$ かかるため、全体で $O(N \cdot d \cdot M \cdot \log N)$ です。IVFのk-means学習 $O(N \cdot C \cdot d \cdot \text{iterations})$ と比較すると、HNSWの構築は遅い傾向があります。

IVFとHNSWの比較

IVFとHNSWを組み合わせたIVF+HNSW（粗い探索にHNSWを使い、各クラスタ内で精密探索）も実用的です。

両手法ともメモリ使用量がベクトルの次元に比例するため、大規模データでは依然としてメモリがボトルネックになります。次に、ベクトルを圧縮してメモリ使用量を削減するProduct Quantizationを見ましょう。

PQ（Product Quantization）

ベクトル圧縮の必要性

$N = 10^8$（1億）のベクトル、$d = 768$ の場合、FP32で必要なメモリは：

$$ 10^8 \times 768 \times 4 \approx 286 \text{ GB} $$

これは1台のサーバーのRAMに収まりません。Product Quantizationは、各ベクトルを数十バイトに圧縮して、このメモリ問題を解決します。

基本アイデア: 部分空間の独立量子化

PQは、$d$ 次元のベクトルを $m$ 個の部分ベクトルに分割し、各部分ベクトルを独立に量子化します。

ベクトル $\bm{x} \in \mathbb{R}^d$ を $m$ 個のサブベクトルに分割：

$$ \bm{x} = [\bm{x}^{(1)}, \bm{x}^{(2)}, \ldots, \bm{x}^{(m)}], \quad \bm{x}^{(j)} \in \mathbb{R}^{d/m} $$

各部分空間 $j$ で、$k^*$ 個のセントロイド $\bm{c}^{(j)}_1, \ldots, \bm{c}^{(j)}_{k^*}$ をk-meansで学習します。通常 $k^* = 256$ として、各部分ベクトルは8ビット（1バイト）のコードブック番号で表現します。

圧縮後のベクトル表現：

$$ \bm{x} \approx [\bm{c}^{(1)}_{q_1(\bm{x})}, \bm{c}^{(2)}_{q_2(\bm{x})}, \ldots, \bm{c}^{(m)}_{q_m(\bm{x})}] $$

ストレージは $m$ バイト/ベクトルです。$d = 768$、$m = 96$ の場合：

$$ \text{圧縮率} = \frac{768 \times 4}{96} = 32\text{倍} $$

距離計算の高速化

PQでは、クエリと各ベクトルの距離をルックアップテーブルで高速に計算できます。

クエリ $\bm{q}$ に対して、事前に各部分空間の距離テーブルを計算：

$$ D^{(j)}[c] = \|\bm{q}^{(j)} – \bm{c}^{(j)}_c\|^2, \quad j = 1, \ldots, m, \quad c = 1, \ldots, k^* $$

テーブルサイズは $m \times k^* = 96 \times 256 \approx 24$KBで、L1キャッシュに収まります。

ベクトル $\bm{x}_i$ との近似距離は：

$$ \|\bm{q} – \bm{x}_i\|^2 \approx \sum_{j=1}^{m} D^{(j)}[q_j(\bm{x}_i)] $$

$m$ 回のテーブルルックアップと加算だけで距離が計算でき、$d$ 次元の内積計算（$d$ 回の乗算+加算）より大幅に高速です。

理論を理解したところで、Pythonで各手法を実装して性能を比較しましょう。

Pythonによる実装と性能比較

IVFインデックスのスクラッチ実装

import numpy as np
import matplotlib.pyplot as plt
from time import time

np.random.seed(42)

class SimpleIVF:
    """シンプルなIVFインデックスの実装。"""

    def __init__(self, n_clusters=100):
        self.n_clusters = n_clusters
        self.centroids = None
        self.inverted_lists = {}

    def build(self, data, n_iter=20):
        """k-meansでインデックスを構築する。"""
        N, d = data.shape

        # k-means初期化（ランダム）
        indices = np.random.choice(N, self.n_clusters, replace=False)
        self.centroids = data[indices].copy()

        for _ in range(n_iter):
            # 割り当て
            dists = np.sum((data[:, None, :] - self.centroids[None, :, :])**2, axis=2)
            assignments = np.argmin(dists, axis=1)

            # 更新
            for c in range(self.n_clusters):
                mask = assignments == c
                if np.sum(mask) > 0:
                    self.centroids[c] = np.mean(data[mask], axis=0)

        # 転置インデックスの構築
        dists = np.sum((data[:, None, :] - self.centroids[None, :, :])**2, axis=2)
        assignments = np.argmin(dists, axis=1)
        for c in range(self.n_clusters):
            self.inverted_lists[c] = np.where(assignments == c)[0]

        self.data = data

    def search(self, query, k=10, nprobe=10):
        """検索を実行する。"""
        # セントロイドとの距離
        dists_to_centroids = np.sum((self.centroids - query)**2, axis=1)
        nearest_clusters = np.argsort(dists_to_centroids)[:nprobe]

        # 選択されたクラスタ内のベクトルとの距離
        candidate_ids = []
        for c in nearest_clusters:
            candidate_ids.extend(self.inverted_lists[c])

        if len(candidate_ids) == 0:
            return np.array([]), np.array([])

        candidate_ids = np.array(candidate_ids)
        candidates = self.data[candidate_ids]
        dists = np.sum((candidates - query)**2, axis=1)

        # 上位k個を返す
        top_k = np.argsort(dists)[:k]
        return candidate_ids[top_k], dists[top_k]


# データ生成
N = 50000  # データベースサイズ
d = 128    # ベクトル次元
n_queries = 100

data = np.random.randn(N, d).astype(np.float32)
queries = np.random.randn(n_queries, d).astype(np.float32)

# ブルートフォースで真の最近傍を求める
def brute_force_knn(data, query, k=10):
    dists = np.sum((data - query)**2, axis=1)
    top_k = np.argsort(dists)[:k]
    return top_k, dists[top_k]

# IVFインデックスの構築
ivf = SimpleIVF(n_clusters=100)
t0 = time()
ivf.build(data, n_iter=20)
build_time = time() - t0
print(f"IVF構築時間: {build_time:.2f}s")

# nprobeを変えてrecallと速度を計測
nprobe_list = [1, 2, 5, 10, 20, 50, 100]
recalls = []
search_times = []

for nprobe in nprobe_list:
    recall_sum = 0
    t0 = time()
    for q in queries:
        ivf_result, _ = ivf.search(q, k=10, nprobe=nprobe)
        bf_result, _ = brute_force_knn(data, q, k=10)
        recall_sum += len(set(ivf_result) & set(bf_result)) / 10
    elapsed = time() - t0
    recalls.append(recall_sum / n_queries)
    search_times.append(elapsed / n_queries * 1000)  # ms per query

# ブルートフォースの速度
t0 = time()
for q in queries[:10]:
    brute_force_knn(data, q, k=10)
bf_time = (time() - t0) / 10 * 1000

# 可視化
fig, axes = plt.subplots(1, 2, figsize=(14, 5))

# 左: nprobe vs recall
axes[0].plot(nprobe_list, recalls, 'o-', color='#00d4ff', markersize=8)
axes[0].axhline(y=1.0, color='gray', linestyle='--', alpha=0.5, label='Exact (brute force)')
axes[0].set_xlabel('nprobe')
axes[0].set_ylabel('Recall@10')
axes[0].set_title('IVF: Search Accuracy vs nprobe')
axes[0].legend()
axes[0].grid(True, alpha=0.3)
axes[0].set_ylim(0, 1.05)

# 右: recall vs search time
axes[1].plot(recalls, search_times, 'o-', color='#ffa726', markersize=8, label='IVF')
axes[1].axhline(y=bf_time, color='#ef5350', linestyle='--', alpha=0.7,
                label=f'Brute force ({bf_time:.1f} ms)')
axes[1].set_xlabel('Recall@10')
axes[1].set_ylabel('Search Time (ms/query)')
axes[1].set_title('Accuracy-Speed Tradeoff')
axes[1].legend()
axes[1].grid(True, alpha=0.3)

for i, np_val in enumerate(nprobe_list):
    axes[1].annotate(f'np={np_val}', (recalls[i], search_times[i]),
                     textcoords="offset points", xytext=(5, 5), fontsize=8)

plt.tight_layout()
plt.savefig('vector_db_ivf.png', dpi=150, bbox_inches='tight')
plt.show()

左のグラフから、nprobeを増やすとrecallが単調に増加し、nprobe=20程度で0.9以上のrecallが達成できることがわかります。全クラスタを探索（nprobe=100）すれば完全一致ですが、nprobe=10でも十分実用的な精度です。

右のグラフでは、精度と速度のトレードオフが明確に見えます。ブルートフォース（赤い破線）と比較して、recall@10=0.9の条件でIVFは数倍〜数十倍高速です。このトレードオフの制御が、実用上の最も重要な設計判断になります。

FAISSの実用例

FAISSは実際のプロダクションで使われるライブラリです。複合インデックスを簡潔に構築できます。

try:
    import faiss

    # データ
    data_f32 = data.astype(np.float32)
    queries_f32 = queries.astype(np.float32)

    # 1. Flat (brute force)
    index_flat = faiss.IndexFlatL2(d)
    index_flat.add(data_f32)
    t0 = time()
    D_flat, I_flat = index_flat.search(queries_f32, 10)
    flat_time = (time() - t0) / n_queries * 1000

    # 2. IVF
    quantizer = faiss.IndexFlatL2(d)
    index_ivf = faiss.IndexIVFFlat(quantizer, d, 100)
    index_ivf.train(data_f32)
    index_ivf.add(data_f32)
    index_ivf.nprobe = 10
    t0 = time()
    D_ivf, I_ivf = index_ivf.search(queries_f32, 10)
    ivf_time = (time() - t0) / n_queries * 1000

    # 3. HNSW
    index_hnsw = faiss.IndexHNSWFlat(d, 32)
    index_hnsw.hnsw.efSearch = 64
    index_hnsw.add(data_f32)
    t0 = time()
    D_hnsw, I_hnsw = index_hnsw.search(queries_f32, 10)
    hnsw_time = (time() - t0) / n_queries * 1000

    # Recall計算
    def compute_recall(result, ground_truth, k=10):
        recall = 0
        for i in range(len(result)):
            recall += len(set(result[i, :k]) & set(ground_truth[i, :k])) / k
        return recall / len(result)

    recall_ivf = compute_recall(I_ivf, I_flat)
    recall_hnsw = compute_recall(I_hnsw, I_flat)

    print(f"{'Method':<15} {'Time (ms)':<15} {'Recall@10':<10}")
    print("-" * 40)
    print(f"{'Flat':<15} {flat_time:<15.3f} {'1.000':<10}")
    print(f"{'IVF':<15} {ivf_time:<15.3f} {recall_ivf:<10.3f}")
    print(f"{'HNSW':<15} {hnsw_time:<15.3f} {recall_hnsw:<10.3f}")

except ImportError:
    print("FAISSがインストールされていません。pip install faiss-cpu でインストールしてください。")
    print("上記のスクラッチ実装の結果を参照してください。")

FAISSのインデックスタイプの選択は、データ規模とメモリ制約で決まります。一般的な推奨は以下の通りです。

まとめ

本記事では、ベクトルデータベースの仕組みをIVF、HNSW、PQの3つの手法を中心に解説しました。

• 全探索は$O(Nd)$の計算量で大規模データに不向き。近似最近傍探索（ANN）で精度と速度のトレードオフを制御する
• IVFはk-meansクラスタリングで空間を分割し、nprobeパラメータで探索範囲を制御する。実装がシンプルでスケーラブル
• HNSWは階層的なSmall Worldグラフで$O(d \cdot M \cdot \log N)$の探索を実現。高精度だがメモリ消費が大きい
• PQはベクトルを部分空間ごとに量子化して圧縮率32倍以上を達成し、ルックアップテーブルで距離計算を高速化する
• 実用上はFAISSがデファクト。データ規模に応じてFlat → IVFFlat → HNSW → IVFPQ を選択する

次のステップとして、以下の記事も参考にしてください。