最近のAIエージェント開発や業務システムの現場において、しばしば耳にするフレーズがあります。「ベクトル検索？ とりあえずHNSWでインデックスを貼っておけば問題ない」。
Hierarchical Navigable Small World（HNSW）は非常に優れたアルゴリズムです。グラフベースのアプローチは、多くの場合において高い再現率（Recall）と高速なレスポンスを実現します。現在のベクトルデータベース市場において、PineconeやMilvusなどがコア技術として採用し、デファクトスタンダードに近い地位を築いているのも事実です。実際、Milvusではエンタープライズ向けのストレージ最適化が統合されるなど進化を続けており、Apache Luceneやpgvectorといった実装でも、メモリ低減や高速化に向けた最適化が継続的に行われています。
しかし、構築しようとしているシステムが、ペタバイト級のデータを扱い、ミリ秒単位のレイテンシを要求され、かつ頻繁にデータが更新されるような過酷な環境だとしたらどうでしょうか。あるいは、エッジデバイスのような限られたメモリリソースの中で動作しなければならないとしたら。
そのような制約下での「とりあえずHNSW」という思考停止は、プロジェクトの致命的なボトルネックになり得ます。グラフ構造の維持コスト、膨大なメモリ消費量、そしてコールドスタートの問題が顕在化するリスクがあるためです。大規模なEコマースシステムなどでは一般的に、トラフィック急増時にHNSWのメモリオーバーヘッドが原因で検索ノードのパフォーマンスが著しく低下するケースが指摘されています。また、運用コストの観点からPineconeのServerless環境からより軽量な代替手段へ移行して大幅なコスト削減を図る事例や、パラメータ（ef_constructionやMなど）のチューニングの複雑さが課題となるケースも珍しくありません。「最強のアルゴリズム」であっても、特定の条件下ではその強みが弱点に反転する構造を持っています。
ここで提案したいのは、LSH（Locality Sensitive Hashing：局所性鋭敏型ハッシュ）への回帰、そして再評価です。
LSHは決して「古い技術」ではありません。むしろ、確率論に基づいたアプローチであり、計算コストと精度のトレードオフをエンジニアが直接制御できる数少ないアルゴリズムの一つです。しかし、その制御性を手にするためには、アルゴリズムをブラックボックスとして扱うのではなく、背後にある数学的直感を深く理解する必要があります。
本稿では、LSHを単なるライブラリの機能としてではなく、確率を操るための「武器」として再定義します。なぜ似ているデータが衝突するのか、その確率曲線をどう設計すればビジネス要件を満たせるのか。数式とコードの狭間にある、真のエンジニアリングの核心に迫ります。確率という猛獣をいかにして手なずけ、システムに組み込むか。そのための実践的な技術論を展開します。皆さんも、日々の開発で直面する課題と照らし合わせながら読み進めてみてください。
「次元の呪い」と全探索の限界点
まず、「次元の呪い（Curse of Dimensionality）」について説明します。この言葉は1961年にリチャード・ベルマンによって提唱されましたが、AI時代においてその影響は極めて大きくなっています。
線形探索が通用しなくなる境界線
小規模なデータセットであれば、単純な線形探索（Linear Scan / Brute-force）が最も確実です。全てのデータとクエリベクトルの距離を計算し、近い順にソートします。計算量は $O(N \cdot D)$ です（$N$はデータ数、$D$は次元数）。
しかし、現代のAIシステム、特にLLM（大規模言語モデル）を活用したRAGシステムでは、この次元数 $D$ が計算コストを爆発させる要因となります。例えば、従来のBERTベースモデルや多くのオープンソースモデルでは768次元、OpenAIの埋め込みモデルでは1536次元、あるいは高精度なモデルでは3072次元にも達します。さらにデータ数 $N$ は数千万から数十億のオーダーになることも珍しくありません。
仮に $N=1,000,000$（100万）、$D=1536$ と想定してみてください。この場合、たった1回のクエリで約15億回の浮動小数点演算が必要になります。これを1秒間に数千リクエスト処理しようとすれば、巨大なGPUクラスターが必要になることは明白です。毎回全探索を行っていては、ユーザーが検索を実行してから結果が表示されるまでに許容できない遅延が発生してしまいます。
さらに、高次元空間の性質として、次元が増えると空間の体積は指数関数的に増大し、データはスカスカになります。そして、あらゆるデータペア間の距離が均一化し始めます。「全てのデータが、他の全てのデータと等しく遠い」という状況に近づくのです。これが次元の呪いであり、従来の空間インデックス（k-d木やR木など）が高次元データに対して無力化する理由です。一般的に、k-d木などは次元数が20を超えたあたりから、全探索と変わらないパフォーマンスまで低下することが知られています。
なぜ従来のハッシュ関数ではベクトル検索ができないのか
ここで、「ハッシュを使えば $O(1)$ で検索できるのでは？」と考えるエンジニアの方もいるかもしれません。ハッシュマップ（Dict型）は確かに高速です。
しかし、サーバーサイド開発で広く使われている暗号学的ハッシュ関数（MD5, SHA-256など）や、通常のデータ構造用ハッシュは、「衝突回避（Collision Resistant）」を目的に設計されています。入力データが1ビットでも違えば、出力されるハッシュ値は全く異なるものになります。これを「雪崩効果（Avalanche Effect）」と呼びます。
ベクトル検索において求められるのは「類似検索」です。「完全に一致するデータ」ではなく、「意味的に似ているデータ」を見つけたいのです。MD5のようなハッシュ関数では、「Apple」という単語のベクトルと、わずかにノイズが乗った「Apple」のベクトルは、全く別のバケットに分類されてしまい、検索不能になります。
必要なのは、従来のハッシュ関数の常識を覆す、「衝突促進型」のハッシュ関数です。
- 似ているデータ（距離が近い）ほど、高い確率で同じハッシュ値になる。
- 似ていないデータ（距離が遠い）ほど、高い確率で異なるハッシュ値になる。
この要件を満たすのが、LSH（局所性鋭敏型ハッシュ）です。LSHは、全探索という「確実だが遅い」手法と、従来のインデックスという「速いが次元の呪いに弱い」手法の間にあるギャップを、「確率的な近似」というアプローチで埋める技術です。エンジニアには、「絶対に正しい答え」へのこだわりを一度捨て、「確率的に十分正しい答え」を高速に導き出すシステム思考が求められます。
LSHの核心：似ているデータほど「衝突」させる数学的直感
では、具体的にどのようにして「似ているものを衝突させる」のか。そのメカニズムを、数式よりも先に視覚的なイメージで捉えてください。
ランダム射影による次元削減の仕組み
最も代表的なLSHの手法である「SimHash（Random Projection LSH）」を例にとります。これはコサイン類似度（角度の近さ）に基づいた検索に使われます。OpenAIのEmbeddingなどが正規化されたベクトルであることを考えると、実務で利用する機会が多い手法です。
高次元空間にデータ点（ベクトル）が星のように散らばっている様子を想像してください。そこに、原点を通る「超平面（Hyperplane）」をランダムに引きます。3次元空間なら、スイカを包丁で切るような「面」で空間を2つに分割するイメージです。
この超平面の法線ベクトルを $\mathbf{r}$ とします。あるデータベクトル $\mathbf{v}$ が、この超平面の「上側」にあるか「下側」にあるかは、内積 $\mathbf{r} \cdot \mathbf{v}$ の符号（プラスかマイナスか）で判定できます。
- $\mathbf{r} \cdot \mathbf{v} \ge 0$ ならばビット
1 - $\mathbf{r} \cdot \mathbf{v} < 0$ ならばビット
0
この操作で、高次元ベクトルを1ビットの情報に圧縮できます。これを $K$ 回、異なるランダムな超平面で繰り返せば、$K$ ビットのハッシュ値（フィンガープリント）が得られます。例えば $K=64$ なら、64ビットの整数（uint64）として表現できます。
コサイン類似度とハミング距離の相関関係
ここで重要なのは、「2つのベクトルが似ている（角度が小さい）ほど、ランダムに引いた超平面によって分断される確率は低い」という事実です。
再びスイカ割りを想像してみてください。2つの種が非常に近くにある（角度が小さい）場合、目隠しをして包丁を入れても、その2つの種が「右と左」に分かれる確率は低いでしょう。逆に、種が正反対の位置にあるなら、高い確率で分断されます。
数学的には、2つのベクトル $\mathbf{v}_1, \mathbf{v}_2$ のなす角を $\theta$ とすると、1回のランダム射影でハッシュ値（ビット）が一致する確率 $P(h(\mathbf{v}_1) = h(\mathbf{v}_2))$ は次のように表されます。
$ P(\text{match}) = 1 - \frac{\theta}{\pi} $
角度 $\theta$ が0（完全に一致）なら確率は1（100%）。$\theta$ が $\pi$（180度、正反対）なら確率は0になります。
この性質により、生成されたハッシュ値同士のハミング距離（ビットごとの不一致数）を計算することで、元のベクトル空間でのコサイン類似度を推定できます。ハミング空間での距離計算は、XORとPopcount（ビットカウント）というCPUが得意とする演算で行えるため高速です。Pythonであれば数行で書けます。
確率的保証：p1（近い）とp2（遠い）のギャップ
LSHがアルゴリズムとして成立するための条件は、以下の2つの確率 $p_1, p_2$ の間にギャップがあることです。
- $p_1$: 距離が $R$ 以内の「近い」ペアが衝突する確率（高いほど良い）
- $p_2$: 距離が $cR$ ($c>1$) 以上の「遠い」ペアが衝突する確率（低いほど良い）
もし $p_1$ と $p_2$ が近すぎると、LSHは機能しません。近いものも遠いものも同じようにバケットに入ってしまい、検索精度が低下するからです。この $p_1$ と $p_2$ の差を広げ、検索精度をコントロールするのが、次章で解説するパラメーター設計です。
精度 vs 速度：トレードオフを支配するパラメーター設計
LSHを導入して失敗する原因の多くは、パラメーターチューニングの誤りです。ライブラリのデフォルト値を使って「精度が出ない」と判断するのは、適切に調整されていないF1マシンに乗るようなものです。
LSHには主に2つの制御レバーがあります。
- $K$: ハッシュ関数の数（ハッシュコードの長さ、AND構成）
- $L$: ハッシュテーブルの数（OR構成）
これらを組み合わせて、確率曲線をS字型（Sigmoid状）に変形させます。これを「確率の増幅（Probability Amplification）」と呼びます。
AND構成とOR構成による確率の増幅
1. AND構成（$K$を増やす）
1つのハッシュテーブル内で、バケットへの振り分けに $K$ 個のハッシュ関数を全て使います。つまり、$K$ ビット全てが一致しないと「衝突」とみなしません。
- 効果: 衝突確率が下がります ($s^K$)。
- 意味: 精度（Precision）が向上します。本当に似ているものだけが残りますが、似ているのにたまたま1ビット違っただけで除外されることが増えます（再現率の低下）。
2. OR構成（$L$を増やす）
上記のようなテーブルを $L$ 個用意します。どれか1つのテーブルでも衝突すれば、候補として採用します。
- 効果: 衝突確率が上がります ($1 - (1 - P)^L$)。
- 意味: 再現率（Recall）が向上します。除外されるものを減らせますが、ノイズ（似ていないデータ）も混入しやすくなり、検索候補数が増えて速度が低下します。
ハッシュ関数数(K)とテーブル数(L)のバランス
これらを組み合わせた最終的な衝突確率 $P(s)$ は、元の類似度（衝突確率）を $s$ とすると、以下の式で表されます。
$ P(\text{collision}) = 1 - (1 - s^K)^L $
この関数をグラフに描くと、Sカーブが現れます。
- $s$ が小さい（似ていない）領域では、確率はほぼ0に抑えられます。
- $s$ がある閾値を超えると、確率は急激に立ち上がり1に近づきます。
技術の本質を見抜き、ビジネスへの最短距離を描くためには、このSカーブの「立ち上がり位置」と「急峻さ」を、ビジネス要件に合わせて調整することが不可欠です。
例えば、$K$ を大きくすればカーブは右にシフトし（より厳しい一致を求める）、$L$ を大きくすれば左にシフトします（より緩い一致を許容する）。$K$ と $L$ を両方増やせば、カーブはより急峻になり、理想的な「ステップ関数（ある閾値以上は全部1、以下は全部0）」に近づきます。
再現率（Recall）95%を目指すためのチューニング
「再現率95%以上」という要件がある場合、逆算して設計します。
- ターゲットとなる類似度 $s_{target}$ を決める: 例えば、「コサイン類似度0.8以上のデータは見つけたい」とします。SimHashの場合、$s_{target} \approx 1 - \arccos(0.8)/\pi$ となります。
- $L$ を計算する: $s_{target}$ における衝突確率が0.95以上になるように $K$ と $L$ を調整します。
一般的に、$K$ を増やすと計算コストとメモリ効率が向上しますが再現率が低下します。それを補うために $L$ を増やすと、インデックスサイズが $L$ 倍になり、検索時の計算量も増えます。
以下のようなアプローチが考えられます。
- メモリ制約が厳しい場合: $L$ を小さく抑え（例えば10〜20）、$K$ を調整してカーブを緩やかにします。そして、多めに候補を取得（Candidate Generation）した後、実データで距離計算（Re-ranking）を行ってノイズを除去します。
- レイテンシ制約が厳しい場合: $K$ を大きめにして候補数を絞り込みます。ただし、再現率を維持するために $L$ もある程度増やす必要があります。
他のANNアルゴリズムとの比較とLSHの特性
市場にはHNSWやIVF（Inverted File Index）、ScaNN、DiskANNなど、ANN（Approximate Nearest Neighbor）アルゴリズムが存在します。その中で、LSHを選ぶべきなのはどのようなシナリオでしょうか？
HNSW（グラフベース）に対するメリット・デメリット
HNSWの強み: 検索速度と高い再現率。静的なデータセットに対しては有力な選択肢です。グラフ上の近傍探索は効率が良いです。
HNSWの弱点:
- メモリ消費: グラフのエッジ情報を保持するため、メモリを多く消費します。10億規模のベクトルになると、数百GBからTB級のRAMが必要になることがあります。
- 構築コスト: インデックス構築に時間がかかります。データ挿入時にグラフの再接続計算が発生します。
- 更新コスト: データの追加・削除に伴うグラフの再構成コストが高いです。リアルタイムでデータが更新されるストリーム処理には不向きです。
LSHの特性:
- 更新が高速: LSHはデータごとに独立してハッシュ値を計算し、バケットに入れるだけです。他のデータとの関係性（グラフ）を考慮する必要がないため、追加・削除は高速に行えます。
- 分散処理との親和性: データ間の依存関係がないため、MapReduceやSparkでの分散処理が容易です。数百億規模のデータを扱う場合、HNSWのグラフを分割するのは難しいですが、LSHならバケットをサーバー間でシャーディングできます。
IVF（量子化ベース）との特性比較
IVF（Faissなどで採用されている転置インデックス）は、空間をVoronoi領域に分割します。これはLSHに近い発想ですが、分割のためにK-meansクラスタリングなどの学習が必要になります。
LSHの特性:
- 学習不要（Data Independent）: LSH（特にSimHashやRandom Projection）はデータの分布を知らなくても、ランダムな超平面でインデックスを作成できます。データの分布が未知、あるいは時間とともに変化する場合、IVFは再学習（Re-training）が必要になりますが、LSHはそのままで機能します。コールドスタート問題（データが十分にない状態）にも対応できます。
LSHが適しているシナリオ
以下のようなケースではHNSWやIVFよりもLSHが適しています。
- データ量がメモリに乗り切らない大規模システム: ディスクベースでの検索が必要な場合、ハッシュテーブルの構造はI/O効率が良いです。
- 高頻度なリアルタイム更新: ニュースフィードのように、コンテンツが生成され、検索対象になる場合。
- 分散アーキテクチャ: 共有状態を持たず、ノードをスケールさせたい場合。
実践的導入に向けたステップと評価指標
具体的な導入ステップを示します。まずは動くプロトタイプを作り、仮説を即座に形にして検証するアプローチをおすすめします。
Ground Truthを用いた再現率の計測
LSHの導入で重要なのは、「正解」との乖離を測定することです。
- テストデータセットの準備: 本番データの一部（例えば10万件）と、クエリ（100〜1000件）を用意します。
- Ground Truth（真の正解）の作成: 全探索（Brute-force）を行い、各クエリに対する「真の近傍トップK」を確定させます。Faissの
IndexFlatL2やIndexFlatIPを使うことができます。 - Recall@N の計測: LSHで検索を行い、上位N件の中に、Ground Truthが含まれている割合を計算します。
$ \text{Recall} = \frac{|\text{LSH結果} \cap \text{Ground Truth}|}{|\text{Ground Truth}|} $
レイテンシとメモリフットプリントの監視
再現率だけでなく、以下のメトリクスも計測します。
- Candidates per Query: ハッシュバケットから取り出された候補データの数。これが多すぎると、後の距離計算フェーズ（Re-ranking）でCPUに負荷がかかります。$K$ を増やして絞り込む必要があります。
- Empty Bucket Rate: クエリのハッシュ値に対応するバケットが空だった割合。これが高いと、何もヒットしないことになります。$L$ を増やすか、Multi-probe LSH（隣接バケットも探す手法）を検討します。
段階的なパラメーター最適化
まずは小さなデータセットで $K$ と $L$ の感度分析を行います。ReplitやGitHub Copilot等のツールを駆使すれば、こうした検証コードも即座に実装できるはずです。
- $L$ を固定し、$K$ を変化させて、Recallと候補数のグラフを描きます。
- 最適な $K$ を見つけたら、次は $L$ を変化させて、Recallとレイテンシのグラフを描きます。
- 目標とするRecall（例: 95%）を達成できる最小のコスト（$L$）を見つけます。
まとめ
LSHは、確率という現象を制御し、エンジニアの意図通りに機能させるための仕組みです。
多くのエンジニアがライブラリの import 文を書いている間に、$K$ と $L$ というパラメータの意味を理解し、システムの精度と速度を操ることができるようになります。「次元の呪い」に直面した時、ハードウェアリソースで解決しようとせず、アルゴリズムの選定とパラメーターの設計に立ち返ってください。
AI駆動開発の世界は、新しいアルゴリズムとライブラリで溢れています。しかし、その根底にある数学的な原理原則は変わりません。原理を理解して使いこなすエンジニアこそが、価値あるシステムを構築し、ビジネスの成功へと導くことができるのです。皆さんのプロジェクトでも、ぜひこのアプローチを試してみてください。どのような結果が得られたか、議論できることを楽しみにしています。
コメント