「PoC（概念実証）の段階ではサクサク動いていたRAG（検索拡張生成）システムが、本番データを入れた途端に重くなった」
実務の現場では、このような課題に直面するケースが少なくありません。数千件程度のドキュメントなら問題なかった検索が、数百万、数千万件という規模になった瞬間、ユーザーを待たせるボトルネックになってしまうのです。
AI検索、つまりベクトル検索において、データ量と検索速度は常にトレードオフの関係にあります。しかし、ビジネスの現場では「精度も欲しいし、速度も欲しい」というのが本音ですよね。そこで登場するのが、今回解説するHNSW（Hierarchical Navigable Small World）というアルゴリズムです。
名前だけ聞くと難しそうに感じるかもしれませんが、その中身は非常に理にかなった「近道の探し方」に基づいています。今回は、数式を一切使わず、高速道路や地図アプリといった身近な例えを使って、このHNSWがなぜこれほど高速なのか、その仕組みを紐解いていきます。
プロジェクトチーム全体が、ライブラリのパラメータをただの「おまじない」として扱うのではなく、意味を理解してチューニングできるようになること。それがこの記事のゴールです。
なぜ「正確な検索」は遅くなるのか？：ベクトル検索の基本課題
HNSWの凄さを理解するには、まず「なぜ普通の検索じゃダメなのか」を知る必要があります。ここで言う「普通の検索」とは、手抜きなしの全件チェックのことです。
KNN（K近傍法）と計算コストの壁
ベクトル検索の最も基本的な形は、KNN（K-Nearest Neighbors / K近傍法）と呼ばれます。これは、クエリ（検索したい内容）のベクトルと、データベースにある全てのデータのベクトルとの距離を計算し、近い順にK個選ぶという手法です。
例えるなら、図書館で「特定の本」を探すときに、蔵書を端から一冊ずつ全部手に取って内容を確認するようなものです。蔵書が100冊なら一瞬ですが、100万冊あったらどうでしょう？ 想像するだけで日が暮れてしまいますよね。
計算機科学の用語で言えば、データ量 $N$ に対して計算時間が線形に増える $O(N)$ の処理です。データが倍になれば、待ち時間も倍になる。これでは、膨大なデータを扱う現代のAIシステムには到底追いつけません。
次元の呪いと全探索の限界
さらに厄介なのが「ベクトルの次元数」です。OpenAIの最新の埋め込みモデル（Embedding）などを利用すると、1つのデータが1536次元や3072次元といった巨大な数字の羅列として表現されます。
2次元（平面）や3次元（空間）なら「近くのもの」を探すのは直感的で計算も簡単ですが、数千次元という高次元空間では計算コストが劇的に跳ね上がります。これを専門用語で「次元の呪い」と呼びます。単にデータ数が多いだけでなく、1つ1つの距離計算自体が非常に重い処理になってしまうのです。
近似解（ANN）を受け入れるトレードオフ
そこで、システム開発の現場ではある実用的な決断がなされました。「厳密に一番近い正解じゃなくてもいいから、そこそこ近いやつを爆速で見つけたい」というアプローチです。
これがANN（Approximate Nearest Neighbor / 近似最近傍探索）です。「全探索」という完璧主義を諦め、確率的に「たぶんこれが一番近いだろう」という候補を効率よく見つける手法です。
HNSWは、このANNアルゴリズムの一種であり、現在最も性能バランスが良いとされている手法の一つです。精度（Recall）を95%〜99%程度維持しながら、検索速度を劇的に向上させることができます。「100%の正解を出すのに1秒かかる」のと、「99%の正解で0.01秒で終わる」のでは、リアルタイム性が求められるAIアプリケーションにおいて、どちらがユーザー体験として優れているかは明白ですよね。ROI（投資対効果）の観点からも、このトレードオフの受け入れは非常に合理的です。
HNSWの構成要素：グラフ理論の基礎用語
HNSW（Hierarchical Navigable Small World）という複雑なアルゴリズムを理解するために、まずはその核となる後半部分「NSW（Navigable Small World）」に焦点を当ててみましょう。ここには、最新のAIエージェントが膨大な知識ベースから瞬時に情報を引き出す際にも通じる、興味深い「グラフ理論」の性質が使われています。
スモールワールド現象（Small World Phenomenon）
皆さんは「6次の隔たり（Six Degrees of Separation）」という概念をご存知でしょうか？ 「友達の友達」を辿っていけば、世界中の誰とでもおおよそ6人を介して繋がれる、という社会ネットワークの仮説です。
これをデータ探索のネットワークに応用したのがスモールワールドネットワークです。このネットワーク構造には、効率的な探索を支える2つの重要な特徴があります。
- 局所的な繋がり: 近所（似ているデータ）とは密に繋がっている。
- 大域的なショートカット: 遠く離れた場所への「飛び石」のようなリンクが少数存在する。
この「遠くへのリンク（ロングレンジ・リンク）」が極めて重要です。これがあるおかげで、ネットワークの端から端まで移動するのに、何千回もホップする必要がなく、数回のジャンプで目的地付近まで到達できるのです。これは、最新のLLMが推論を行う際に、関連性の低い情報を飛び越えて核心に迫るプロセスにも似た効率性を生み出します。
ボロノイ図とドローネグラフ
少し専門的な視点になりますが、空間上の点をどう繋ぐかというルールとして、ボロノイ図やドローネグラフといった概念があります。これらは「自分に近い点同士を繋ぐ」ための数学的な定義です。
HNSWのベースとなる考え方は、データ（ベクトル）をノード（点）とし、意味的に似ているデータ同士をエッジ（線）で結んでグラフを作ることです。こうすれば、あるデータから出発して線を辿るだけで、類似したデータに効率よく辿り着けるようになります。
NSW（Navigable Small World）のナビゲーション原理
NSWは、このスモールワールドの性質をそのまま検索アルゴリズムに応用したものです。
基本的な検索の流れは以下の通りです。
- グラフの中の任意の点（エントリーポイント）からスタートする。
- 現在地から繋がっている隣の点（近傍）を見て、「目的地（クエリベクトル）」により近い点へ移動する。
- どの隣人も現在地より遠ければ、そこでストップ（そこが近似的な正解）。
これを「貪欲法（Greedy Search）」と呼びます。常に「今より良い場所」を選び続けるシンプルなルールです。
しかし、初期のNSWには明確な弱点がありました。それは「最初のスタート地点」への依存です。もしスタート地点がゴールから遠すぎると、いくらショートカットがあっても辿り着くのに時間がかかります。また、途中で「局所解（Local Minimum）」という袋小路に迷い込み、本当の正解（大域解）に辿り着けないリスクもありました。
AIモデルが進化し、扱うデータ規模が爆発的に増加している現在、この非効率性は無視できません。そこで、このNSWの課題を解決するために「階層構造」を取り入れ、改良されたのがHNSW（Hierarchical NSW）なのです。
HNSWアルゴリズムの核心：階層構造のメカニズム
HNSW（Hierarchical Navigable Small World）が大規模データ検索において圧倒的なパフォーマンスを発揮する理由、その核心はアルゴリズム名の通り「階層構造（Hierarchical）」にあります。
数百万、数億というベクトルデータの中から、どのようにして瞬時に「似ているデータ」を見つけ出しているのか。その仕組みを紐解いていきましょう。
Hierarchical（階層性）：高速道路と一般道の使い分け
この仕組みを直感的に理解するために、車での移動を想像してみてください。例えば、東京から大阪の特定の住所へ向かうとします。
もし、最初から全ての信号や交差点がある「下道（一般道）」だけで移動しようとすれば、途方もない時間がかかってしまいます。
効率的な移動とは、通常次のようなステップを踏むはずです。
- 高速道路を利用して、一気に大阪エリアまで移動する（長距離・大まかな移動）。
- インターチェンジで降り、幹線道路を使って目的の地域へ近づく（中距離・ある程度の絞り込み）。
- 最後に路地に入り、特定の番地を探し当てる（近距離・詳細な探索）。
HNSWは、高次元空間の中でこれと全く同じアプローチをとっています。
- 最上位レイヤー（Layer N）: ノード（データ点）の数は非常に少なく、互いに長い距離でリンクされています。これが「高速道路」の役割を果たし、空間を大きくジャンプします。
- 中間レイヤー: 下層に行くにつれてノード密度が高まり、リンクの距離も短くなります。
- 最下層レイヤー（Layer 0）: 全てのデータが存在し、近接するノード同士が密に繋がっています。これが詳細な探索を行う「一般道」です。
検索クエリが入力されると、アルゴリズムはまず最上位レイヤーで大まかな位置を特定し、そこから段階的に下のレイヤーへ降りていくことで、探索範囲を劇的に絞り込んでいます。これにより、無駄な距離計算を極限まで減らすことが可能になるのです。
レイヤー構造とエントリポイント
では、アルゴリズムが実際にどのように動いているのか、そのプロセスを整理します。
- エントリポイント: 検索は必ず最上位レイヤーに設定された特定の「入り口（エントリポイント）」から開始されます。
- ズームイン（Greedy Search）: 現在のレイヤーで、クエリベクトルに対して「より近い隣人」がいなくなるまで移動を続けます。これ以上近づけない地点（局所解）に達したら、その位置座標を保ったまま一つ下のレイヤーへ降下します。
- 詳細探索の継続: 下のレイヤーではノードの密度が上がっているため、先ほど到達した地点からさらに「より近い隣人」が見つかる可能性があります。探索を再開し、再び局所解を目指します。
- ゴールへの到達: このプロセスを最下層（Layer 0）まで繰り返し、最終的に到達したノードが「近似最近傍（ANN）」の解となります。
この挙動は、Web地図サービスで世界地図から日本、特定の都市、そして街区へとズームインしていく操作に似ています。最初から全データをスキャンするのではなく、上空から当たりをつけて効率的に降下していくアプローチです。
スキップリスト（Skip List）との類似性
専門的な視点から補足すると、この階層構造はデータ構造における「スキップリスト（Skip List）」の概念をグラフ探索に応用したものと言えます。
スキップリストは、連結リストに対して「飛ばし読み」用のポインタを追加することで検索効率を高める手法ですが、HNSWはこれを高次元ベクトルのグラフ構造（Small World Graph）に適用しました。この巧みな階層設計のおかげで、データ量が爆発的に増加しても、検索に必要なステップ数は対数的（$O(\log N)$）にしか増加しません。
最新のAIエージェントやRAG（検索拡張生成）システムが、膨大な知識ベースから瞬時に関連情報を引き出せるのは、裏側でこのような効率的なアルゴリズムが支えているからなのです。
パフォーマンス調整の重要パラメータ解説
HNSWは素晴らしいアルゴリズムですが、導入すれば自動的に最適化される魔法の杖ではありません。実務でAzure AI Search、Faiss、あるいはQdrantなどのベクトルデータベースを使用する際、プロジェクトマネージャーやエンジニアはいくつかのパラメータ設定に直面します。
特にQdrantのような最新のツールはデフォルトでも優れたパフォーマンスを発揮しますが、要件に応じた微調整（チューニング）が必要になる場面は珍しくありません。ここでは、HNSWの挙動を決定づける特に重要な3つのパラメータについて、その意味と調整の指針を解説します。
※ツールによってパラメータの名称が異なる場合があります（例：ef、ef_construct、hnsw_configなど）。最新の仕様や推奨値については、各ツールの公式ドキュメントをご参照ください。
M（各ノードの最大接続数）：メモリと速度のバランス
- 定義: グラフ上で1つのノードが持つエッジ（繋がり）の最大数です。
- 影響:
- 大きくすると: ネットワークが密になり、検索時に「より良い近道」を見つけやすくなるため、検索精度（Recall）が向上します。また、孤立したノードができにくくなり、グラフの堅牢性が増します。
- デメリット: ノードごとの接続情報が増えるため、メモリ消費量が増大します。また、エッジを計算するコストが増え、インデックス構築にかかる時間も長くなります。
- 実践アドバイス: 一般的には
16から64程度の間で設定されることが多いです。メモリリソースに余裕があり、かつ精度を最優先したい場合は大きめに設定しますが、数値を倍にすれば精度が倍になるわけではない点に注意が必要です。コスト対効果を見極める必要があります。
ef_construction / ef_search（探索深さ）：精度と速度のトレードオフ
ef は「探索時の候補リストサイズ（Search Queue Size）」と捉えると分かりやすいでしょう。多くの実装で、構築時と検索時で個別に設定できます。
ef_construction（構築時の探索深さ）
- 定義: インデックスを作る（グラフを構築する）際に、どれだけ広く近傍候補を探してエッジを結ぶか。
- 影響:
- この値を大きくすると、より質の高い（最適な接続を持つ）グラフが出来上がります。結果として、後の検索精度が向上します。
- ただし、計算量が増えるため、インデックス構築時間が大幅に伸びます。
- 実践アドバイス: インデックス構築はバックグラウンドやオフライン処理で行うことが多いため、検索時のレイテンシには影響しません。許容できる構築時間の範囲内で、比較的大きめに設定するのが定石です（例：100〜500など）。これにより、検索効率の良い「高品質な地図」を作ることができます。
ef_search（検索時の探索深さ）
- 定義: 実際にユーザーが検索する際に、どれだけの候補を探索キューに入れて比較検討するか。
- 影響:
- これが最も直接的に「検索速度（QPS）」と「検索精度（Recall）」のトレードオフを決定します。
- 値を小さくすれば処理は爆速になりますが、正解を見逃す（Recallが下がる）リスクが増えます。逆に大きくすれば精度は上がりますが、その分だけ計算時間が必要となり、レスポンスは遅くなります。
- 実践アドバイス: これは運用中に動的に変更できる場合が多いパラメータです。まずは小さめの値から始め、システムに求められる精度要件（例えばRecall@10で0.95以上など）を満たすポイントまで徐々に上げていくチューニングが一般的です。
再現率（Recall）とQPS（Queries Per Second）の関係
パラメータ調整の究極のゴールは、「目標とするQPS（秒間クエリ数）やレイテンシを維持しつつ、Recall（正解率）を最大化する」ポイントを見つけることです。
「とりあえずデフォルト値で」と放置してしまうケースも見受けられますが、サービスの性質によって最適解は全く異なります。
例えば、社内ドキュメント検索ボットのように「1〜2秒待っても正確な答えが欲しい」場合はef_searchを上げて精度重視に設定します。一方で、ECサイトのリアルタイムレコメンドのように「ミリ秒単位の速度が売上に直結する」場合は、多少の精度を犠牲にしてでもef_searchを調整し、速度重視にする判断が求められます。
こうしたトレードオフを理解し、ビジネス要件に合わせてパラメータを制御できるかどうかが、AI検索プロジェクトの成功を左右すると言っても過言ではありません。
他のインデックス手法との比較と使い分け
HNSWは非常に優れたアルゴリズムですが、万能ではありません。最大の課題は「メモリ消費量が大きい」という点にあります。グラフ構造（ノード間のつながり）をメモリ上に保持する必要があるため、データ量に比例してメモリコストが増大します。
HNSW vs 量子化・ディスクベース手法：メモリ効率の戦い
大規模データを扱う際は、HNSW単体ではなく、以下のような技術との比較や組み合わせが検討されます。
- HNSW: グラフ構造を全てメモリ上に保持します。高速ですが、データ量が増えるとメモリ容量の限界に直面します。
- IVF（Inverted File / 転置インデックス）: データをクラスタリングし、クエリに近いクラスターのみを探索する方法です。HNSWに比べてメモリ効率が良いですが、検索精度や速度のバランス調整が必要です。
- 量子化（Quantization）: ベクトルデータを圧縮する技術の総称です。
- PQ（Product Quantization / 直積量子化）: ベクトルを分割して圧縮します。
- SQ（Scalar Quantization / スカラー量子化）: 浮 ক্যামের小数点数をより小さなビット数（int8など）で表現します。
- BQ（Binary Quantization / バイナリ量子化）: ベクトルを0と1のビット列に変換し、極めて高い圧縮率と高速化を実現します（精度とのトレードオフあり）。
これらはHNSWと排他的なものではなく、「HNSW + 量子化」のように組み合わせて使用されることが一般的です。グラフ探索で候補を絞り込みつつ、データ自体は圧縮してメモリ消費を抑えるアプローチです。
Faiss, Milvus, Qdrant等での実装状況
主要なベクトルデータベースや検索ライブラリでは、HNSWの実装に加え、メモリ効率を高めるための工夫が凝らされています。
- Azure AI Search: HNSWアルゴリズムを標準採用しており、インデックス作成時のパラメータ（
mやefConstruction）調整が可能です。また、量子化技術を用いた圧縮機能も提供されています。 - Qdrant / Weaviate / Milvus / Elasticsearch: これらのデータベースもHNSWをコアインデックスとして採用していますが、スカラー量子化やバイナリ量子化のサポート、あるいはSSDを活用したディスクベースのインデックス（DiskANNの考え方に近い実装など）により、メモリに乗らない規模のデータを扱えるように進化しています。
※最新の対応状況や設定方法は、各製品の公式ドキュメントをご確認ください。
オンメモリ運用の限界と対策
「HNSWは速いが、メモリリソースを大量に消費する」。この制約はシステム設計時の重要な考慮事項です。クラウドのインフラコストを試算する際、純粋なHNSW構成ではメモリリッチな高価なインスタンスが必要になる場合があります。
コストと性能のバランスを取るために、以下の対策が有効です。
- 次元削減: PCA（主成分分析）などでベクトルの次元数を減らし、データサイズそのものを小さくする。
- 量子化の活用: HNSWと量子化（SQやPQ）を併用し、インデックスサイズを削減する。精度の低下が許容範囲内か検証が必要です。
- ハイブリッド/階層化: 頻繁にアクセスされる「ホットデータ」はオンメモリのHNSWで高速化し、アクセス頻度の低いデータはディスクベースのインデックスや安価なストレージに配置する構成を検討する。
まとめ：高速なAI検索を実現するために
今回は、ベクトル検索の高速化を支えるHNSWアルゴリズムについて、その「階層構造によるナビゲーション」の仕組みを中心に解説しました。
要点を振り返ります。
- 全探索からの脱却: データが増えるほど遅くなるKNN（全探索）に対し、実用的な速度を維持するには近似探索（ANN）が不可欠です。
- HNSWの階層構造: 上位レイヤーで大まかに移動し、下位レイヤーで詳細を探す仕組みが、対数的な高速検索を実現しています。
- トレードオフの調整:
M（接続数）やef（探索深さ）といったパラメータを調整することで、メモリ・速度・精度のバランスを最適化できます。 - リソース管理: 高速な反面、メモリ消費が激しいアルゴリズムです。データ規模に応じて、量子化技術の併用やインフラ選定を慎重に行う必要があります。
AI検索の実装は、単にライブラリを導入して終わりではありません。「データ量が10倍、100倍になったとき、このアーキテクチャで耐えられるか？」という視点を持ち、将来の拡張性を見据えた設計を行うことが、長期的なプロジェクトの成功につながります。AIはあくまでビジネス課題を解決するための手段です。ROIを最大化するためにも、技術の特性を正しく理解し、適切なアーキテクチャを選択していきましょう。
コメント