SVS Vamana および Milvus を使用した検索

SVS（Scalable Vector Search）は、Vamanaグラフアルゴリズムを実装した、インテル社の高性能ベクトル検索ライブラリです。 Milvusでは、FAISSインデックスのパススルーを通じてSVS Vamanaを利用できます。index_type をFAISS に設定し、SVSVamana というインデックスファクトリ文字列を指定すると、MilvusはFaissのSVS統合機能を通じてインデックスを構築し、検索を行います。

VamanaはDISKANNでも使用されているグラフ構造ですが、SVS Vamanaはグラフ全体をメモリ内に保持します。また、LeanVecやLVQを用いてベクトルを圧縮することができ、これによりメモリ使用量を削減し、検索速度を向上させつつ、非常に高いリコール率を維持します。

前提条件

• SVSを有効にしてソースからビルドしたMilvus 3.0.0以降
• PyMilvus 3.0.0 以降
• LVQ* またはLeanVec* ストレージを使用する場合は、Intel CPUが必要です。FP32 、FP16 、およびSQ8 ストレージは、どのプラットフォームでも動作します。
• FAISSのインデックスファクトリ文字列に関する知識

LVQおよびLeanVec圧縮はIntel CPUでのみ実行可能であり、AVX-512を搭載したCPUではより高速に動作します。その他のCPUでは、LVQ* およびLeanVec* のファクトリ文字列を使用した場合、インデックス構築に失敗します。

SVS Vamanaの仕組み

Vamanaグラフ

SVS Vamanaは、単層の近傍グラフを構築します。各ベクトルがノードとなり、近傍である可能性が高いベクトル同士をエッジで結びます。グラフを構築するために、SVSは各ノードx に対して以下の処理を行います：

1. 貪欲探索：SVSは、これまでに構築されたグラフを探索し、サイズがconstruction_window_size の候補リストを維持します。

2. 近傍の剪定：訪問済みのノードは、x の近傍候補となります。SVS は、x からの距離が小さい順にそれらを検討します。 すでに保持されているより近い近傍n が、alpha * distance(n, c) <= distance(x, c) を満たす場合、候補c はスキップされる。これにより、長距離のエッジは保持され、冗長な短距離のエッジは削除されるため、検索はグラフを1つずつ最も近い近傍をたどって進むのではなく、グラフを飛び越えて進むことができる。グラフの次数に達すると、剪定は停止する。

3. 逆方向のエッジ：xの新しい隣接ノードごとに、SVSはxへの逆方向のエッジを追加し、その隣接ノードのエッジリストがグラフの次数を超えている場合は、そのエッジリストを剪定します。

剪定は2回のパスで実行されます。最初はalpha = 1 で、次に設定されたalpha で行われます。グラフの次数とconstruction_window_size を大きくすると、より密で高品質なグラフが得られますが、メモリを多く消費し、構築に時間がかかります。

検索時、SVSはグラフを貪欲探索し、search_window_size にこれまでに見つかった最も近い候補を保持します。次に探索するのは、常に最も近い未訪問の候補です。現在のノードのすべての隣接ノードが、ウィンドウ内の最悪の候補よりもクエリから遠い位置にあるようになった時点で、検索は終了します。search_window_size を大きく設定すると、グラフのより広い範囲が探索されるため、リコール率は向上しますが、レイテンシも増加します。

LeanVec圧縮

LeanVecは、ベクトルあたりの次元数と次元あたりのビット数を両方とも削減します。LeanVecインデックスは、各ベクトルについて2つの表現を保持します：

• プライマリ（次元削減済み）：ベクトルをより少ない次元数へと線形投影したものです。グラフ検索はこのプライマリデータセットに対して実行されるため、距離計算の大部分は低次元空間で行われます。これにより、演算負荷とメモリ帯域幅の両方の要件が軽減されます。デフォルトでは、削減後の次元数は元の次元数の半分になります（dim / 2 ）。

• セカンダリ（フル次元）：ベクトルの元の次元での表現。SVSは、次元削減によって失われた精度を回復するために、プライマリグラフ検索によって返された候補を、このセカンダリデータセットに対して再ランク付けします。

両方の表現は、LVQ（局所適応ベクトル量子化）によって量子化されます。エンコーディングの選択は、ファクトリ文字列の「storage」コンポーネントによって行われます。例えば、LeanVec4x8 では、プライマリデータセットに対して次元あたり 4 ビット、セカンダリデータセットに対して次元あたり 8 ビットが使用されます。再ランク付けのステップにおいても、フル精度のベクトルが読み込まれることは決してありません。

デフォルトでは、LeanVecはインデックス化されたベクトル用とクエリ用で別々の射影を学習します。これにより、インデックス化されたベクトルとは異なる分布（アウト・オブ・ディストリビューション、OOD）から来るクエリにも対応できます。 これは、テキストから画像への検索などのクロスモーダルワークロードで特に効果的であり、クエリがインデックス化されたベクトルと同じ分布に属する場合にも有効です。Milvusでは、投影計算用のクエリを渡す方法はまだサポートされていないため、現在はベースベクトルのみが使用されます。OODトレーニングを行うと、ビルド時間が長くなります。 クエリ性能を多少犠牲にしてビルドを高速化するには、ood_training をFalse に設定してください。

LVQ圧縮

次元数が約512未満のデータセットの場合、次元削減を省略し、LVQ量子化のみで圧縮した方が良好な結果が得られることがあります。 LeanVecと同様に、LVQインデックスは高速検索用のプライマリ表現と、再ランク付け用の残差表現を保持します。例えば、LVQ4x4 では、プライマリ表現に4ビット、残差表現に4ビットを使用します。LVQ4x0 およびLVQ8x0 は再ランク付けを省略するため、ワークロードに対してリコール率が十分に高ければ、クエリ処理が高速化されます。

ファクトリ文字列の選択

SVS Vamanaのファクトリ文字列は、SVSVamana<degree>[,<storage>] という形式をとります。ここで、<degree> はグラフ内のノードあたりの最大エッジ数です。

SVSVamana64,LeanVec4x8 は良い出発点となります。そこから：

• メモリコストを多少犠牲にしてもリコール率を高めたい場合は、_<dim> というサフィックスを使用してLeanVecの次元数を増やします。

• リコール率を多少犠牲にしてメモリ使用量を削減したい場合は、LeanVecの次元数を下げます。

• 低次元のベクトルの場合は、LVQ8 を試してみてください。

• Intel製以外のCPUでは、FP16 またはSQ8 を使用してください。

インデックスの構築

次の例では、グラフの次数 64 および LeanVec 圧縮を使用した SVS Vamana インデックスを構築します。インデックスを構築する前に、セットアップ ブロックを展開して実行してください。

import random

from pymilvus import DataType, MilvusClient

client = MilvusClient(uri="http://localhost:19530")
collection_name = "svs_vamana_example"

if client.has_collection(collection_name):
    client.drop_collection(collection_name)

rng = random.Random(42)
vectors = [[rng.random() for _ in range(256)] for _ in range(3000)]

schema = client.create_schema(auto_id=False, enable_dynamic_field=False)
schema.add_field("id", DataType.INT64, is_primary=True)
schema.add_field("vector", DataType.FLOAT_VECTOR, dim=256)

client.create_collection(collection_name=collection_name, schema=schema)

client.insert(
    collection_name=collection_name,
    data=[{"id": i, "vector": vector} for i, vector in enumerate(vectors)],
)
client.flush(collection_name=collection_name)

index_type をFAISS に設定し、faiss_index_name を使用して SVS Vamana レシピを選択します。

index_params = client.prepare_index_params()
index_params.add_index(
    field_name="vector",
    index_name="svs_vamana_index",
    index_type="FAISS",
    metric_type="L2",
    params={
        # SVSVamana64 -> Vamana graph degree 64
        # LeanVec4x8  -> 4-bit primary, 8-bit secondary
        # _128        -> LeanVec dim 128 (omit the suffix for dim / 2)
        "faiss_index_name": "SVSVamana64,LeanVec4x8_128",
        "construction_window_size": 200,  # build-time search width
        "ood_training": True,             # OOD on (default)
    },
)

client.create_index(collection_name=collection_name, index_params=index_params)
client.load_collection(collection_name=collection_name)

インデックスの検索

search_window_size は、HNSWにおけるef と同様に、リコールとレイテンシのトレードオフを制御します。search_buffer_capacity を少なくとも同等の値に設定してください。両方のデフォルト値は10であり、SVSはsearch_window_size がsearch_buffer_capacity を超える検索を拒否します。

search_params = {
    "params": {
        "search_window_size": 100,      # wider = higher recall, lower QPS
        "search_buffer_capacity": 100,  # must be >= search_window_size
    }
}

res = client.search(
    collection_name=collection_name,
    data=[vectors[0]],
    anns_field="vector",
    limit=10,
    search_params=search_params,
)

limit がsearch_window_size より大きい場合、SVSはその検索に対してウィンドウをlimit まで拡大します。

SVS Vamana パラメータ

以下のビルドパラメータは、add_index() 内のparams に、faiss_index_name の隣に指定します。インデックスの構築後は、これらを変更することはできません。

以下の検索パラメータは `search_params.params` に指定します。これらをビルドパラメータとして設定することも可能で、その場合、これらのパラメータが設定されていない検索に対してインデックスが使用するデフォルト値が変更されます。

詳細

• 一般的なファクトリ・ストリングの契約、制限、およびエラー処理については、FAISSインデックスパススルーのリファレンスを参照してください。
• DISKANNに含まれるディスク上のVamana実装と比較してください。
• ビルドの詳細、パフォーマンスのチューニング、および基盤となる C++ API については、SVS リポジトリを参照してください。