ローカルベクトルデータベースのHNSW検索は、メモリと再現率をどのようにトレードオフするのか？

エヴァ・ウォン

IceWhale author

エヴァ・ウォン は テクニカルライター であり ZimaSpaceの常駐ティンカーでもあります。 生涯のオタクであり、 ホームラボとオープンソースソフトウェアに情熱を持っています。彼女は複雑な技術的概念をわかりやすく、 実践的なガイドに翻訳することを専門としています。エヴァはセルフホスティングは楽しくあるべきで、怖がるものではないと信じています。彼女のチュートリアルを通じて、コミュニティが ハードウェアのセットアップを解明する手助けをしています。初めてのNAS構築からDockerコンテナの習得まで。

How Does HNSW Search Trade Memory for Recall in a Local Vector Database? - Zima Store Online

HNSWは、探索可能な近傍グラフを保存することでメモリと再現率をトレードオフします。接続性と検索範囲によって、クエリが近傍ベクトルをどれだけ徹底的に探索できるかが決まります。

ローカルベクトルデータベースには、家庭内の文書、OCRテキスト、写真のメタデータ、マニュアル、文字起こし、アプリケーションの記録などの埋め込みを保存できます。総当たり検索ではクエリとすべてのベクトルを比較しますが、HNSWは階層化されたグラフをたどることで、同じように有用な近傍へ到達しようとします。この近道が高速なのは、データベースがあらかじめ追加のグラフ構造を保存しているためです。また、その精度はグラフがどれだけ密に接続されているか、そしてクエリが探索できる候補数によって決まります。

HNSWは保存されたベクトルの周囲に階層化された近接グラフを追加する

各ベクトルは、選択された近傍と接続されたノードになります。さらに、一部のノードは上位レイヤーにも現れ、ベクトル同士が近い可能性の高い領域へ検索を素早く移動するための長距離経路を作ります。

多層近接グラフにより、HNSWは上位レイヤーで大まかな経路を提供し、階層の下部に近づくにつれて、より細かな近傍ナビゲーションを行います。

保存されるエッジが、最初のメモリ上のトレードオフになります。ベクトルのフラットな配列とは異なり、インデックスは探索中に利用できる状態を維持しなければならないトポロジー情報を保持します。

この階層構造により、通常のクエリが訪問するコレクションの範囲を減らせますが、これは近似手法です。グラフや検索の予算によって適切な経路が見つからない場合、真の近傍を見落とす可能性があります。

Mパラメーターは、より多くの経路を作るためにグラフメモリを消費する

HNSWの実装には、一般に`m`または`M`と呼ばれる接続性パラメーターがあります。値を大きくすると、ノードがより多くの近傍リンクを保持できるようになり、ベクトル空間の密な領域や不規則な領域を通る代替経路が増えます。

HNSWのm値を大きくすると、ノードごとにより多くの近傍接続が保存されます。通常はナビゲーションの選択肢と再現率が向上しますが、その分グラフのメモリ使用量と構築作業が増えます。

メモリの増加は、元の埋め込み値を大きくすることではなく、グラフのエッジと関連するインデックス構造によって生じます。数百万のベクトルがある場合、ノードごとの追加リンクがコレクション全体で積み重なります。`m`を小さくすると、メモリに制約のあるホームサーバーでも扱いやすくなりますが、グラフが疎になりすぎると、検索が局所的な行き止まりを回避する方法が減り、再現率が低下する可能性があります。

Ef Constructionは、構築作業を増やしてグラフ自体を改善する

グラフの品質は、ベクトルの挿入中にも決まります。`ef_construct`は、新しいノードのリンクを選ぶ前に、構築処理が調べる候補近傍の範囲を制御します。

構築品質を左右するパラメーターとしてefConstructionを使うと、エッジを選択する前により広い候補近傍を調べられるため、構築時の作業量は増えますが、グラフの品質を向上できます。

このコストは、すべてのクエリで発生するのではなく、構築または再構築の段階で支払われます。変化の少ないプライベートなコーパスであれば、ベクトルの精度を恒久的に高めなくても検索品質を改善できるため、構築時間を増やすことが許容される場合があります。

ただし、構築時の作業量を増やしても、極端に小さなグラフを無期限に補うことはできません。`m`、構築時の探索範囲、データ分布、挿入履歴は相互に影響します。

Featured

ZimaCube 2 パーソナルクラウドホームNAS

ZimaCube2

Ef Searchは、永続的なグラフメモリではなくクエリ処理を消費する

クエリ実行時、HNSWは候補のフロンティアを維持し、有望なグラフノードを探索します。一般に`ef`、`ef_search`、または`hnsw_ef`と呼ばれるパラメーターは、その探索中に検討対象として残す候補数を制御します。

クエリの探索範囲を広げると、最も近い結果を確定する前に、より多くのグラフ候補を調べられます。通常は再現率が向上しますが、クエリのレイテンシーも増加します。

`m`とは異なり、クエリの`ef`を大きくしても、保存されているすべてのノードに永続的なエッジを追加する必要はありません。主なコストは、そのリクエストで追加される距離計算、メモリアクセス、レイテンシーとして現れます。この違いにより、ホームサーバーでは2種類の調整が可能になります。グラフの接続性は永続的なインデックスのメモリ使用量を決める一方、クエリの探索範囲は、追加の処理に見合う難しい検索にだけ引き上げられます。

ベクトル圧縮ではHNSWグラフのコストはなくならない

埋め込みを量子化すると、保存する各ベクトルを大幅に小さくできます。しかし、HNSWには近傍関係が依然として必要です。そのため、インデックス全体には少なくとも、ベクトルデータとグラフのトポロジーという2つの主要なメモリ構成要素が含まれます。

ベクトル値を圧縮しても、量子化によってグラフリンクが小さくなるわけではありません。HNSWには、ベクトルを取り囲むトポロジー、ID、関連構造が依然として必要です。

そのため、ベクトルの圧縮率が4倍以上になっても、HNSW全体のメモリ使用量が同じ割合で削減されるとは限りません。グラフエッジ、オブジェクトID、メタデータ、アロケーターのオーバーヘッド、キャッシュは残ります。

小規模なホームサーバーでは、ベクトルの次元数だけからRAMを見積もるのではなく、コレクション全体の常駐メモリ使用量を測定してください。

再現率は設定値から推測せず、正確な近傍と比較して測定する

通常、`m`と`ef`を大きくすると再現率は向上します。しかし、どのようなパラメーター値でも、すべての埋め込みモデル、コーパスサイズ、文書分布に対して一定の精度が保証されるわけではありません。

複数のRAGコレクションでHNSWグラフのメモリが必要になると、ローカルモデル、メタデータインデックス、キャッシュ、その他のホームサーバーサービスと並行して複数のプライベートコレクションをアクティブにした際に、そのコストが積み重なります。

代表的なクエリセットを作成し、扱いやすいサンプルに対する正確なスキャンと近似検索の結果を比較してください。再現率、レイテンシー、インデックスのRAM使用量、構築時間、同時リクエストの影響を追跡します。したがって、HNSWの実用的なトレードオフは「RAMを増やせば常に検索が良くなる」というものではありません。測定した再現率を満たしながら、ホームAIスタックの他の部分を圧迫しない範囲で、十分なグラフ接続性とクエリ探索を選ぶことが重要です。