Home
Blog
MilvusにおけるNVIDIA CAGRAの最適化：GPUとCPUのハイブリッドアプローチによるインデックス作成の高速化とクエリの低コスト化

MilvusにおけるNVIDIA CAGRAの最適化：GPUとCPUのハイブリッドアプローチによるインデックス作成の高速化とクエリの低コスト化

Engineering

December 10, 2025

Marcelo Chen

AIシステムが実験から生産インフラに移行するにつれ、ベクトル・データベースはもはや数百万の埋め込みを扱うことはなくなった。今や数十億は日常茶飯事であり、数百億はますます一般的になっている。このような規模では、アルゴリズムの選択はパフォーマンスやリコールに影響するだけでなく、インフラコストにも直結します。

つまり、計算リソースの使用量を制御不能に陥らせることなく、許容可能なリコールとレイテンシを実現するために適切なインデックスをどのように選択するかということです。

NSW、HNSW、CAGRA、Vamanaなどのグラフベースのインデックスが最も広く採用されている。あらかじめ構築された近傍グラフをナビゲートすることで、これらのインデックスは、ブルートフォーススキャンやクエリに対するすべてのベクトルの比較を回避し、億単位での高速最近傍検索を可能にします。

しかし、このアプローチのコストプロファイルにはばらつきがある。グラフのクエリは比較的安価だが、グラフの構築はそうではない。高品質のグラフを構築するには、大規模な距離計算と、データセット全体にわたる反復的な改良が必要です。

NVIDIAのCAGRAは、GPUを使用して大規模な並列処理によりグラフ構築を高速化することで、このボトルネックに対処します。これにより構築時間は大幅に短縮されますが、インデックス構築とクエリ処理の両方をGPUに依存することは、本番環境においてより高いコストとスケーラビリティの制約をもたらします。

これらのトレードオフのバランスをとるため、Milvus 2.6.1では GPU_CAGRA インデックスに ハイブリッド設計を採用しています：GPUはグラフ構築のみに使用され、クエリ実行はCPUで実行されます。これにより、GPUで構築されたグラフの品質の優位性を維持しながら、クエリ処理のスケーラビリティとコスト効率を維持することができ、データの更新頻度が低く、クエリ量が多く、コストに厳しいワークロードに特に適しています。

CAGRAとは何か、どのように機能するのか？

グラフベースのベクトルインデックスは一般的に2つの主要なカテゴリに分類される：

CAGRAに代表される反復的グラフ構築（Milvusでは既にサポートされています）。
Vamanaに代表される挿入ベースのグラフ構築（現在Milvusで開発中）。

これら2つのアプローチは、設計目標と技術的基盤が大きく異なるため、それぞれ異なるデータスケールとワークロードパターンに適しています。

NVIDIA CAGRA (CUDA ANN Graph-based)は、近似最近傍(ANN)探索のためのGPUネイティブアルゴリズムであり、大規模な近接グラフを効率的に構築し、クエリするために設計されています。GPU並列性を活用することで、CAGRAはグラフ構築を大幅に高速化し、HNSWのようなCPUベースのアプローチと比較して高スループットのクエリ性能を実現します。

CAGRAはNN-Descent (Nearest Neighbor Descent)アルゴリズムに基づいて構築されており、反復的な精密化によってk-nearest-neighbor (kNN)グラフを構築する。各反復において、近傍候補は評価され、更新され、データセット全体にわたってより質の高い近傍関係へと徐々に収束していく。

各改良ラウンドの後、CAGRAは2ホップ迂回枝刈りなどのグラフ枝刈り技術を追加適用し、探索品質を維持しながら冗長な辺を削除する。この洗練と枝刈りの反復の組み合わせにより、クエリ時に効率的にトラバースできる、コンパクトでありながらつながりの深いグラフが得られる。

洗練と刈り込みを繰り返すことで、CAGRAは大規模で高い再現性と低レイテンシの最近傍探索をサポートするグラフ構造を生成し、静的なデータセットや更新頻度の低いデータセットに特に適している。

ステップ1：NN-Descentによる初期グラフの構築

NN-Descentは、ノードuが vの近傍であり、ノードwが uの近傍である場合、wも vの近傍である可能性が非常に高いという、シンプルだが強力な観察に基づいている。この推移的な性質により、このアルゴリズムはすべてのベクトルのペアを網羅的に比較することなく、効率的に真の最近傍を発見することができる。

CAGRAはグラフ構築アルゴリズムの中核としてNN-Descentを使用する。このプロセスは以下のように動作する：

1.ランダムな初期化：各ノードはランダムに選択された隣人の小さな集合から開始し、大まかな初期グラフを形成する。

2.隣人拡大：各反復において、ノードは現在の近傍とその近傍を集めて候補リストを形成する。アルゴリズムはノードとすべての候補の間の類似性を計算する。各ノードの候補リストは独立しているため、これらの計算を別々のGPUスレッドブロックに割り当て、大規模に並列実行することができます。

3.候補リストの更新：アルゴリズムがノードの現在の近傍よりも近い候補を見つけた場合、より遠い近傍を入れ替え、ノードのkNNリストを更新する。何度も繰り返すことで、このプロセスはより質の高い近似kNNグラフを生成する。

4.収束チェック：反復が進むにつれて、近傍の更新は少なくなる。更新された接続の数が設定されたしきい値を下回ると、アルゴリズムは停止し、グラフが効果的に安定したことを示す。

異なるノードの近傍展開と類似度計算は完全に独立しているため、CAGRAは各ノードのNN-Descentワークロードを専用のGPUスレッドブロックにマッピングします。この設計は大規模な並列処理を可能にし、従来のCPUベースの手法よりもグラフ構築を桁違いに高速化します。

ステップ2：2ホップ迂回によるグラフの刈り込み

NN-Descentが完了した後のグラフは正確だが、密度が高すぎる。NN-Descentは意図的に余分な近傍候補を保持し、ランダムな初期化段階では弱いエッジや無関係なエッジを多数導入する。その結果、各ノードの次数は目標の次数の2倍、あるいは数倍になることが多い。

コンパクトで効率的なグラフを作成するために、CAGRAは2ホップ迂回枝刈りを適用する。

この考え方は簡単で、ノードAが共有の隣人Cを介して間接的にノードBに到達でき（パスA → C → Bを形成する）、この間接パスの距離がA-B間の直接距離と同程度である場合、直接エッジA → Bは冗長とみなされ、削除することができる。

この枝刈り戦略の主な利点は、各辺の冗長性チェックが局所的な情報（2つの端点間の距離とその共有近傍）にのみ依存することである。各辺は独立して評価できるため、枝刈りステップは非常に並列化可能であり、GPUバッチ実行に自然に適合する。

その結果、CAGRAはGPU上で効率的にグラフを刈り込むことができ、検索精度を維持しながらストレージのオーバーヘッドを40-50%削減し、クエリ実行時のトラバーサル速度を向上させる。

MilvusにおけるGPU_CAGRA：何が違うのか？

GPUはグラフ構築に大きなパフォーマンス上の利点をもたらしますが、本番環境では現実的な課題に直面します：GPUリソースはCPUよりもはるかに高価であり、制限されています。インデックス構築とクエリ実行の両方がGPUのみに依存する場合、いくつかの運用上の問題がすぐに浮上します：

リソース利用率の低さ：クエリ・トラフィックは不規則かつバースト的であることが多いため、GPUは長時間アイドル状態となり、高価な計算能力を浪費する。
高い導入コスト：ほとんどのクエリがGPUの性能をフルに活用していないにもかかわらず、クエリを提供するすべてのインスタンスにGPUを割り当てると、ハードウェアコストが上昇します。
限られたスケーラビリティ：利用可能なGPUの数は、実行可能なサービス・レプリカの数に直接影響するため、需要に応じて拡張する能力が制限されます。
柔軟性の低下：インデックス構築とクエリの両方がGPUに依存する場合、システムはGPUの可用性に縛られることになり、ワークロードをCPUに簡単にシフトすることができません。

これらの制約に対処するため、Milvus 2.6.1では、adapt_for_cpu パラメータを通じてGPU_CAGRAインデックスの柔軟な導入モードを導入しています。このモードはハイブリッドワークフローを可能にします：CAGRAはGPUを使用して高品質のグラフインデックスを構築し、クエリ実行はCPUで実行される。

このセットアップでは、GPUは高速で高精度なインデックス構築という最も価値のある場所で使用され、CPUは大規模なクエリワークロードをはるかにコスト効率が高くスケーラブルな方法で処理する。

その結果、このハイブリッドアプローチは以下のような作業負荷に特に適している：

データの更新頻度が低く、インデックスの再構築が少ない。
クエリー量が多く、安価なレプリカを多数必要とする。
コスト感度が高く、GPUの使用量を厳しく管理する必要がある。

理解`adapt_for_cpu`

Milvusでは、adapt_for_cpu パラメータが、インデックス構築時にCAGRAインデックスがどのようにディスクにシリアライズされ、ロード時にどのようにメモリにデシリアライズされるかを制御します。構築時とロード時にこの設定を変更することで、MilvusはGPUベースのインデックス構築とCPUベースのクエリ実行を柔軟に切り替えることができます。

構築時とロード時のadapt_for_cpu の異なる組み合わせにより、4つの実行モードが生まれ、それぞれが特定の運用シナリオ向けに設計されています。

構築時間 (`adapt_for_cpu`)	ロード時間 (`adapt_for_cpu`)	実行ロジック	推奨シナリオ
真	真	GPU_CAGRAでビルド→HNSWとしてシリアライズ→HNSWとしてデシリアライズ→CPUクエリ	コスト重視のワークロード、大規模クエリ処理
真	偽	GPU_CAGRAでビルド → HNSWとしてシリアライズ → HNSWとしてデシリアライズ →CPUクエリ	パラメータの不一致が発生した場合、後続のクエリはCPUにフォールバックされる
false	真	GPU_CAGRAで構築 → CAGRAとしてシリアライズ → HNSWとしてデシリアライズ →CPUクエリ	一時的なCPU検索を可能にしながら、オリジナルのCAGRAインデックスを保存用に保持する
false	false	GPU_CAGRAで構築 → CAGRAとしてシリアライズ → CAGRAとしてデシリアライズ →GPUクエリ	コストが二の次となるパフォーマンスクリティカルなワークロード

注： adapt_for_cpu メカニズムは一方向の変換のみをサポートします。CAGRAグラフ構造はHNSWが必要とする全ての近傍関係を保持しているので、CAGRAインデックスはHNSWに変換できる。しかし、HNSWインデックスはGPUベースのクエリに必要な追加構造情報がないため、CAGRAに戻すことはできない。その結果、ビルド時の設定は、長期的な展開とクエリ要件を考慮して慎重に選択する必要があります。

GPU_CAGRAをテストする

ハイブリッド実行モデル（インデックス構築にGPUを使用し、クエリ実行にCPUを使用する）の有効性を評価するために、標準化された環境で一連の制御された実験を行いました。この評価では、インデックス構築性能、クエリ性能、リコール精度の3つの側面に焦点を当てている。

実験セットアップ

実験は、結果の信頼性を維持し、広く適用できるように、広く採用されている業界標準のハードウェアで実施した。

CPU：MD EPYC 7R13プロセッサー(16CPU)
GPUNVIDIA L4

1.インデックス構築性能

GPUで構築したCAGRAとCPUで構築したHNSWを、同じターゲットグラフ次数64で比較した。

主な結果

GPU CAGRAはCPU HNSWより12-15倍高速にインデックスを構築する。Cohere1MとGist1Mの両方において、GPUベースのCAGRAはCPUベースのHNSWを大幅に上回り、グラフ構築時のGPU並列処理の効率性を強調。
ビルド時間はNN-Descentの反復によって直線的に増加する。これは、NN-Descentの反復洗練の性質を反映し、構築コストとグラフ品質の間の予測可能なトレードオフを提供する。

2.クエリー性能

この実験では、CAGRA グラフを GPU 上で一度構築し、その後、2つの異なる実行経路を使用してクエリを実行する：

CPUクエリ：インデックスをHNSW形式にデシリアライズし、CPU上で検索する。
GPUクエリ：GPUベースのトラバーサルを用いてCAGRAグラフ上で直接検索を実行する。

主な結果

GPU検索のスループットはCPU検索より5-6倍高い。Cohere1MとGist1Mの両方で、GPUベースのトラバーサルは大幅に高いQPSを実現し、GPU上での並列グラフナビゲーションの効率性を強調している。
リコールはNN-Descentの反復によって増加し、その後停滞する。ビルドの反復回数が増えるにつれて、CPUとGPUの両方のクエリでリコールが向上する。しかし、ある点を超えると、さらなる反復は、グラフ品質がほぼ収束したことを示すように、利得を減少させる。

3.リコール精度

この実験では、CAGRAとHNSWの両方をCPUでクエリし、同一のクエリ条件下での再現率を比較する。

主な結果

CAGRAは両方のデータセットでHNSWより高い回収率を達成し、CAGRAインデックスがGPU上で構築され、CPU検索のためにデシリアライズされた場合でも、グラフの品質は十分に保たれていることを示している。

次へVamanaによるインデックス構築の拡張

MilvusのGPUとCPUのハイブリッドアプローチは、今日の大規模ベクトル検索ワークロードに実用的でコスト効率の高いソリューションを提供します。GPUで高品質のCAGRAグラフを構築し、CPUでクエリを処理することで、高速なインデックス構築とスケーラブルで手頃な価格のクエリ実行を組み合わせています。

数百億から数千億のベクトルというさらに大きなスケールでは、インデックス構築そのものがボトルネックになります。完全なデータセットがGPUメモリに収まらなくなると、業界では通常、Vamanaのような挿入ベースのグラフ構築手法に移行します。Vamanaはグラフを一度に構築するのではなく、データをバッチ処理し、グローバルな接続性を維持しながら新しいベクトルをインクリメンタルに挿入します。

その構築パイプラインは、3つの重要な段階を踏む：

1.1.幾何学的バッチ成長- スケルトン・グラフを形成するために小さなバッチから始め、並列性を最大化するためにバッチ・サイズを大きくし、最後に大きなバッチを使って詳細を洗練する。

2.貪欲な挿入- 各新規ノードは、中央のエントリーポイントからナビゲートして挿入され、その隣接セットを反復的に洗練していく。

3.後方エッジの更新- 対称性を保持し、効率的なグラフナビゲーションを保証するために、逆方向の接続を追加する。

プルーニングはα-RNG基準を用いて構築プロセスに直接組み込まれる：もし近傍候補vが既存の近傍p′によってすでにカバーされている場合（すなわち、d(p′, v) < α × d(p, v)）、vはプルーニングされる。パラメータαは、スパース性と精度の精密な制御を可能にする。GPUによる高速化は、バッチ内並列処理と幾何学的バッチスケーリングによって達成され、インデックスの品質とスループットのバランスをとる。

これらの技術を組み合わせることで、チームはGPUメモリの制限に陥ることなく、急激なデータ増加や大規模なインデックス更新を処理することができる。