フィルタリングされたベクトル検索：ACORNが修正するもの、ACORNを修正するもの

Qdrantの内部に戻る フィルタリングされたベクトル検索：ACORNが修正するもの、ACORNを修正するもの Dylan Couzon & Meina Ghafouri · 2026年8月7日 メタデータフィルタリングが健全な最近傍探索グラフを散在する島に変えてしまうと、フィルタリングされたベクトル検索は破綻します。 HNSWのmパラメータは、各点がいくつリンクを持つかを制御します。 Qdrantのデフォルト値m=16では、以下でベンチマークされた100万点のコレクションは、レイヤー0でノードあたり約21個のリンクを持っていました。 点の96%をフィルタリングすると、ノードあたり平均で1つ未満のリンクしか残らなくなるため、真の最近傍に到達する前に探索が立ち往生する可能性があります。 Qdrantは、そのダメージを2つの場所で修復します。 Filterable HNSWはインデックス作成時に追加のリンクを挿入します。 ACORNは検索時に隣接ノードの隣接ノードをステップします。 どちらも同じコレクション上で実行されます。 追加のリンクが届かない場所でACORNはそのコストに見合う働きをします：リンクするには共通すぎる値、ANDフィルタで単一フィールドのリンクがカバーできないもの、ビルドがサイレントにスキップしたペイロードフィールド。 このベンチマークは、単一のQdrantインスタンスで実行され、4つのビルドにわたるQdrant自身の4つの検索戦略を比較します。 2つのACORN ACORN論文（Patel et al., SIGMOD 2024）は、2つのアルゴリズムを説明しています。 「固定リコール率で2〜1,000倍高いスループット」という見出しの主張はACORN-gammaのもので、これは論文自身の表で、通常のHNSWのビルド時間の8.8倍から33.1倍で、インデックス構築時に隣接リストを拡張します。 ACORN-1はより軽量です。 標準的なHNSWグラフを構築し、その後、直接の隣接ノードがフィルタに失敗した場合に、検索時に隣接ノードの隣接ノードをチェックします。 QdrantはACORN-1を、インデックス変更なしで、リクエストごとにオプトインするクエリパラメータとして実装しています。 Qdrantが構築するグラフ Filterable HNSWは、共同創設者のAndrey Vasnetsovが2019年に説明したもので、修復をインデックスに組み込みます。 ペイロードフィールド（各点に付随するメタデータ）がインデックス化されると、Qdrantはそのフィールドの値を持つ点を結ぶ追加のHNSWリンクを挿入するため、フィルタリングされたクエリは移動するための接続されたグラフを維持します。 Qdrantはこれらのリンクをインデックス作成時にペイロードフィールドごとに付与しますが、すべてのフィールドがそれに見合うわけではありません。 これらのリンクはビルド時間にコストがかかります。 私たちの100万点のコレクションでは、HNSWインデックスはそれなしで116秒、それありで507〜652秒で構築され、コストの4.4倍から5.6倍でした。 この範囲は、同一設定での2回のビルドをカバーしており、ビルドごとのばらつきです。 両方の数値はインデックスビルド時間であり、インジェストは除外されています。 Qdrantはこれらのリンクをペイロードフィールドごとに構築し、組み合わせごとではないため、ANDフィルタは単一フィールドのリンクがカバーしない交点に着地します。 ACORN-1はそのギャップをカバーし、ビルド時間ではなくクエリ時にコストを支払います。 Qdrantのクエリプランナーは、ACORN、フルスキャン、ペイロードインデックスからの直接取得、およびFilterable HNSWの間で自動的に選択します。 同じグラフが2つの方法で修復されています。 ACORNは検索時にフィルタリングされた隣接ノードをステップします。 Filterable HNSWはインデックス作成時に追加のリンクを挿入し、フィルタリングされたクエリは直接それをたどることができます。 ベンチマーク ベンチマークは、ANN-benchmarksスイートからの100万個のdeep-image-96ベクトル（96次元の画像埋め込み）で実行されます。 キーワードフィルタは、点の20%から0.012%に一致します。 Recall@10は、フィルタごとに500クエリに対する正確な総当たり検索でスコアリングされ、レイテンシはサーバーサイドの平均クエリ時間です。 私たちは4つの戦略をテストしました。 * プレーングラフ：追加リンクなしの標準HNSW。 * プレーングラフ + ACORN：ACORNを強制オンにした同じグラフ。 * Filterable HNSW：追加リンクを持つデフォルトビルド。 * プランナー + ACORN：Qdrantのデフォルトクエリプランナー。各クエリをACORN、フルスキャン、またはペイロードインデックスにルーティングできます。 すべてのフィルタは、ペイロードフィールドの1つのキーワード値に一致します。 コレクションは7つのそのようなフィールドを持ち、それぞれ10、50、または100の異なる値を含んでいます。 ほとんどのフィルタはベクトルとは独立しています。 Correlated (10%)行は簡単なケースで、フィルタを通過する点がベクトル空間で互いに近くに位置しています。 以下のすべての数値は、Qdrant v1.18.2で、ラップトップクラスのマシン1台で、シリアルにクエリして測定されました。 比率を読み取ってください、絶対ミリ秒ではありません。 再現キットはハードウェアと完全な方法論を文書化しています。 単一フィルタ：追加リンク hnsw_ef（以下efと略記）は、検索が評価する候補の数なので、これを増やすとリコールが向上し、クエリが遅くなります。 選択率は、フィルタを通過する点の割合です。 この表は最初の3つの戦略を比較しています。 full_scan_thresholdは、フィルタリングされた結果セットが直接スキャンするのに十分小さい場合にQdrantに通知します。 値はキロバイト単位のベクトルデータで測定され、一致するベクトルがそれを下回るとQdrantはHNSWグラフをスキップします。 これらの3つの戦略では、すべてのクエリがグラフ上に留まるように値を低く設定しました。 プランナー+ACORNはデフォルトのしきい値で実行されます。 各セルは、hnsw_ef=64でのRecall@10とサーバーサイドの平均レイテンシを示しています。 Filter (selectivity) Plain graph Plain graph + ACORN Filterable HNSW One keyword (20%) 62.9% @ 1.6ms 98.9% @ 4.4ms 94.8% @ 1.2ms One keyword (10%) 20.6% @ 1.7ms 98.1% @ 4.3ms 99.0% @ 1.1ms One keyword (1%) 0.1% @ 1.6ms 67.7% @ 4.7ms 99.8% @ 1.0ms Correlated (10%) 88.4% @ 1.7ms 98.6% @ 3.5ms 99.0% @ 1.2ms プレーングラフはフィルタが厳しくなるにつれて崩壊し、相関フィルタのみが持ちこたえます。 ACORNはリコールをプレーングラフのレイテンシの2.1倍から2.9倍で回復させ、その後1%フィルタで停止します。 これはRACORN-1フォローアップ論文がターゲットとする弱点です。 ACORNが勝つ20%のフィルタは、追加リンクが付与されなかったペイロードフィールドで実行され、次のセクションでその理由を説明します。 バーはRecall@10を示しています。 各バーのラベルはそのサーバーサイドの平均レイテンシです。 追加リンクは約1msでトップのリコールを維持します。 ACORNはその3〜5倍のコストを支払います。 Qdrantのプランナーはこれらすべての上に位置します。 フィルタが通過する点の数を推定し、クエリごとにパスを選択します。 グラフ、グラフ上のACORN、または推定値がfull_scan_thresholdを下回った場合のペイロードインデックスです。 4番目の戦略であるプランナー+ACORNは、すべての4つのフィルタで99.9%〜100%のリコールを維持し、グラフでは7.2ms〜10.9ms、1%フィルタでは1.5ms（すべての500クエリがペイロードインデックスから来ました）です。 一部のペイロードフィールドが追加リンクを取得しない理由 Qdrantは、各インデックス化されたペイロードフィールドの値をウォークすることで追加リンクを構築します。 各値について、それを持つ点を検索し、それらをリンクするため、その値にフィルタリングされたクエリは、移動するためのグラフを維持します。 点の数がサイズキャップを超える値は、追加リンクを取得しません。 なぜなら、メイングラフはすでにその数の点を接続しておくべきだからです。 Qdrantは、コレクションのスライスであるセグメントごとにそのキャップを導き出します。 そのセグメントは独自のインデックスを持っています。 式は、点の数 / ノードあたりの平均リンク数 * 4 です。 ここで、1つのセグメントが100万点すべてを保持していたため、100万 / 21リンク * 4 = 190,476点となり、コレクションの約19%に相当します。 より密なグラフは、より厳しいキャップを持ちます。 ノードあたり24リンクの場合、キャップは16.7%に低下します。 Qdrantはこれらの決定を報告しないため、再現キットはトレースレベルのビルドログとフィールドサイズからそれらを導き出します。 ベンチマークの7つのペイロードフィールドは次のように配置されました。 Field Distinct values Points per value Extra edges built 2 fields 5 ~200,000 No, all 5 values over the cap 2 fields 10 ~100,000 Yes, 10 of 10 values Correlated field 10 ~100,000 Yes, 10 of 10 values 2 fields 100 ~10,000 Yes, 100 of 100 values 5値フィールドはキャップを5%超えているため、すべての値がスキップされました。 このスキップが、ACORNが20%フィルタ、および次のセクションの4%交差でFilterable HNSWを上回る理由です。 それ以外の場所では、ギャップはビルドごとのばらつきの範囲内に留まります。 スキップは意図的です。 追加リンクはビルド時間とメモリを消費するため、キャップが存在します。 キャップを下回る値でも、full_scan_thresholdフロアを下回る場合や、点の接続性がどの程度良好かのサンプリングチェックに失敗した場合にスキップされる可能性があるため、値の数だけでは結果は決まりません。 二重フィルタ：交差ギャップ hnsw_ef=64での同じベンチマーク、今回は2つのキーワードフィールドに対するANDフィルタを使用。 Filter (selectivity) Plain graph + ACORN Filterable HNSW Planner + ACORN Two keywords (4%) 95.2% @ 7.7ms 63.7% @ 1.2ms 99.9% @ 13.9ms Two keywords (1%) 72.7% @ 6.8ms 70.8% @ 1.5ms 100% @ 3.7ms Two keywords (0.012%) 0.6% @ 2.6ms 1.8% @ 2.6ms 100% @ 1.3ms 2つのキーワードの交差には、