【実装】ベクトルDBを自作する — 線形走査からHNSWへ

ベクトル検索の中身を、20行の線形走査から段階的に組み立てる。次元の呪い、IVFによる空間分割、HNSWのグラフ探索、量子化までを「再現率と速度の取引」という一本の軸で解説する。

Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs

全部見るか、賢く諦めるか

100万冊の蔵書がある図書館で、「いま手に持っているこの本と似た本を5冊」と頼まれたとします。確実な方法は1つだけです。全部の棚を回り、1冊ずつ手に取って似ているかを判定する。答えは必ず正しいのですが、1回の質問に何時間もかかります。

現実の図書館は違います。まずジャンルの棚へ行き、書架を絞り、そこから数冊を見る。速い代わりに、ジャンルの境目に置かれた「本当は一番似ている本」を見逃す可能性があります。

ベクトルデータベースがやっているのは、この後者です。「必ず正しい答え」を諦める代わりに、桁違いの速さを買う。この取引の名前が近似最近傍探索（Approximate Nearest Neighbor, ANN）です。

この記事では中身をブラックボックスのまま使うのをやめます。20行の線形走査から始め、なぜそれが壊れるのかを確かめ、IVFとHNSWという2つの逃げ道を組み立てます。全体像はRAGの基礎と設計パターンにありますが、ここでは「検索」の一点だけを掘ります。

何を「近い」とするか

前提を1つだけ。テキストや画像は埋め込みモデルによって数百〜数千次元の数値の並び（ベクトル）に変換され、意味が近いものは近い向きを指すよう学習されています（埋め込み(Embedding)を1から理解する）。

では「近い」をどう測るか。実務で使うのは主に3つです。

式(1)は左から順に、「対応する成分を掛けて足しただけの値（内積）」「それを長さで割って向きだけを見た値（コサイン）」「2点間の直線距離（L2）」です。内積とコサインは大きいほど近く、L2は小さいほど近い、という向きの違いに注意してください。

つまり3つは、同じ「近さ」を別の物差しで測っているだけです。$q$ は検索したいクエリのベクトル、$x$ は比べる相手の文書ベクトル、$q_i$ と $x_i$ はその $i$ 番目の成分、$\|\cdot\|$ はベクトルの長さ（原点からの距離）を表します。内積は「向きの合い具合」と「ベクトルの長さ」をまとめて1つの点数にしたもの、コサインは長さを捨てて向きだけを見たもの、L2は2点のあいだに定規を当てて測った長さ、ということです。

ここに実装上とても重要な性質があります。すべてのベクトルを長さ1に正規化しておくと、3つは同じ順位を返します。長さが1なら分母が1になってコサインは内積そのものになり、さらに

式(2)は「正規化済みなら、L2距離の2乗は内積を裏返しただけの値」と言っています。内積が大きいほどL2は小さい。だから順位は一致します。

つまり、長さを1に揃えてしまえば「距離が近い」と「内積が大きい」は同じ事実の別の言い方でしかありません。式の右辺に残った $2$ はどのベクトルでも変わらない定数なので順位には一切効かず、順位を動かしているのは $q \cdot x$ ただ1つ、ということです。

この一手間を最初に入れておけば、後でインデックスの距離設定を変えても結果がひっくり返りません。逆に正規化を忘れて内積で検索すると、単に長いベクトルが上位に居座ります。意味が近いのではなく、ただ大きいだけの文書が勝つわけです。

まず線形走査を書く

いきなりHNSWを書く必要はありません。ベクトルDBの出発点は、numpyで20行です。

import numpy as np

class FlatIndex:
    def __init__(self, dim):
        self.vecs = np.empty((0, dim), dtype=np.float32)
        self.ids  = []

    def add(self, vecs, ids):
        v = np.asarray(vecs, dtype=np.float32)
        v /= np.linalg.norm(v, axis=1, keepdims=True)   # 長さ1に正規化
        self.vecs = np.vstack([self.vecs, v])
        self.ids += list(ids)

    def search(self, q, k=5):
        q = np.asarray(q, dtype=np.float32)
        q /= np.linalg.norm(q)
        scores = self.vecs @ q                          # 全件との内積を一発で
        top = np.argpartition(-scores, k)[:k]           # 上位k件を部分選択
        top = top[np.argsort(-scores[top])]             # そのk件だけ並べ替え
        return [(self.ids[i], float(scores[i])) for i in top]

argpartition がささやかな工夫です。全件を並べ替えると $O(N \log N)$ かかりますが、「上位k個とそれ以外」に分けるだけなら $O(N)$ で済みます。

そして重要なのは、このFlatIndexが返す答えは常に正しいことです。近似ではありません。これから作るANNの良し悪しは、すべてこの結果を正解として測ります。

線形走査は、いつ破綻するか

素朴に見積もります。100万件の文書を768次元で埋め込むと、1クエリあたり $10^6 \times 768 \approx 7.7$ 億回の積和。float32のメモリは $10^6 \times 768 \times 4$ バイト ≈ 約3GB。1クエリなら数百ミリ秒に収まりますが、毎秒100クエリを捌こうとした瞬間に破綻します。1000万件ならメモリは30GBで、1台に載りません。

厄介なのは、この増え方が直線だという点です。指数関数ほど劇的ではないので「まだいける」と思いながらデータを足していき、ある日いきなり応答時間の基準を割ります。

近似という取引 — 再現率という物差し

そこで「必ず正しい」を諦めます。ただし、どれだけ諦めたのかを測れなければ、ただの壊れた検索です。物差しが再現率（recall@k）です。

式(3)の $G_k$ は線形走査が返した正解の上位k件、$R_k$ は近似手法が返したk件、$|\cdot|$ は集合の要素数です。「正解の上位k件のうち何割を取りこぼさずに拾えたか」。recall@10 が 0.9 なら、本来の上位10件のうち9件は取れています。

つまりこの式は答え合わせの採点表です。$R_k \cap G_k$ は「近似が返したk件と、正解のk件の、両方に入っていたもの」、その個数が得点で、満点は $k$。10問のテストで9問合っていたら0.9、という素朴な採点とまったく同じ形をしている、ということです。

ここが初学者のつまずきどころですが、ANNの性能は1つの数字では表せません。つまみを1つ回せば、遅くなる代わりに再現率が上がる。速くする代わりに取りこぼす。だから正しい比べ方は「recall@10 が 0.95 のとき何クエリ/秒 出るか」という曲線上の1点です。「速い」だけの主張は、片側の軸を隠しているだけだと思ってください。