ScaNN指数の簡単な紹介

ScaNNは、大規模ベクトル検索におけるお馴染みの課題に対するGoogleの回答である。それは、結果の品質に許容できないほどの打撃を与えることなく、いかにクエリのスループットを向上させ、メモリ使用量を削減するかというものである。概念的には、ScaNNは古典的なIVF+PQのレシピ-粗いクラスタリングと積極的な積の量子化-から始まるが、性能のフロンティアを有意義にシフトする2つの重要な革新が重ねられている：

• スコアを考慮した量子化目的により、真の近傍の相対的な順序をより良く保持し、高圧縮下でもランキングの質を向上させる。

• FastScanは、SIMDに最適化された4ビットPQルックアップ・パスであり、CPUレジスタ内でより多くの作業を維持することで、従来のメモリ負荷のボトルネックを軽減します。

実際には、高いQPSとはるかに小さいメモリフットプリント（多くの場合、ベクタを元のサイズの1/16に圧縮する）のために、多少のリコールと引き換えにしても構わない場合に、FastScanは強力な選択肢となります。

この記事では、IVFPQ をベースラインとして再検討し、その上に ScaNN が導入する主要な最適化について検討し、最後に実測性能に基づいた実験結果で議論を締めくくります。

IVFPQ のまとめ

ScaNNは2020年にGoogleによって提案され、論文ではGloVeデータセットでHNSWに対して3倍の性能向上が報告されている。詳細は元の論文と オープンソースの実装を参照されたい。

ScaNNを紹介する前に、ScaNNは同じ全体的なフレームワークの上に構築されているため、IVFPQについて簡単に復習しておこう。

IVFPQ は Inverted File with Product Quantization の略で、高次元ベクトルデータベースにおける効率的かつ大規模な近似最近傍（ANN）探索に使用されるアルゴリズムである。IVFPQは、反転ファイルインデックス(IVF)と積量子化(PQ)という2つの手法を組み合わせたハイブリッドアプローチで、検索速度、メモリ使用量、精度のバランスをとることができます。

IVFPQの仕組み

IVFPQは、インデックス作成と検索において主に2つのステップを経る：

• IVF層：ベクトルはnlist の転置リスト（クラスタ）にクラスタ化される。クエリー時には、リコールとレイテンシー/スループットをトレードオフするために、クラスタのサブセット（nprobe ）のみを訪問します。

• PQ層：訪問した各クラスタ内で、各D次元ベクトルはm個のサブベクトルに分割される。各サブベクトルは、そのサブコードブック内の最も近いセントロイドに割り当てることで量子化される。サブ・コードブックが256個のセントロイドを持つ場合，各サブ・ベクトルはuint8 コード（[0, 255]のID）で表現できる．

距離計算は，サブベクトル上の和として書き直すことができる．

D(q, X) = D(q, u0) + D(q, u1) + D(q, u2) + ... + D(q, un)

= L(q, id1) + L(q, id2) + L(q, id3) + ... + L(q, idn)

ここで、Lはルックアップテーブルを表す。クエリ時にルックアップテーブルが構築され、クエリと量子化された各サブベクトルとの間の距離が記録される。それ以降の距離計算はすべてテーブルのルックアップに変換され、その後に合計が行われる。

例えば、128次元のベクトルをそれぞれ4次元の32個のサブベクトルに分割した場合、各サブベクトルをuint8 IDでエンコードすると、ベクトルあたりのストレージコストは(128 x 4)バイトから(32 x 1)バイトになり、これは1/16の削減となる。

IVFPQに基づくScaNNの最適化

要約すると、ScaNN は IVFPQ を以下の 2 点で改善する：

1. 量子化：量子化：ScaNN は、単に各サブベクトルを最も近い k-means のセントロイドに置き換える（すなわち、再構成誤差を最小化する）以上の目的を提案する。

2. ルックアップ効率：ScaNNは、SIMDフレンドリーのFastScanパスにより、しばしばメモリに縛られるLUTベースの探索を高速化する。

スコアを考慮した量子化ロス

分析はIPメトリックに基づいているため、ScaNNが量子化誤差を平行成分と垂直成分に分解した後、平行成分のみが結果に影響するため、より大きなペナルティ項を適用する必要があります。その結果、損失関数は以下のように書き換えられる：

$$\begin{array}{r}{\displaystyle \mathrm{\ell }({\mathrm{xi}}_{},{\mathrm{x~i}}_{},w)}\end{array}$$$$∥2begin{aligned}\ullellleft(x_i, ∥tilde{x}_i, w=h_{\|}\left(w,\left\|x_i\right\|\right)\left\|r_{\|}\left(x_i, \tilde{x}_i\right)\right\|^2 +h_{\perp}\left(w,\left\|x_i\right\|\right)\left\|r_{\perp}\left(x_i,$$\$$tilde{x}_i\right)￤right￤|^2 ￤end{aligned}$$ ℓ$$\begin{array}{r}(x\end{array}$$i, x~i,w) =h∥ $$\begin{array}{l}(w、\end{array}$$∥xi$$\begin{array}{l}\Vert ）\end{array}$$ $$\begin{array}{l}r\end{array}$$∥ $$\begin{array}{l}（x\end{array}$$i, x~i) 2+h⊥ $$\begin{array}{l}（w,\Vert x\end{array}$$i$$\begin{array}{l}\Vert ）\Vert r\end{array}$$⊥ $$\begin{array}{l}（x\end{array}$$i,

下図は2次元の例で、並列成分による誤差がより大きく、不正確な最近傍結果につながる可能性があるため、より厳しいペナルティが必要であることを示しています。

左の図はパラレルオフセットが最終結果に影響するため、量子化が不十分であることを示しており、右の図は量子化が良好であることを示しています。

4ビットPQ FastScan

まずPQ計算プロセスについて説明します。クエリ実行中に、クエリとサブベクタークラスター中心間の距離が事前に計算され、ルックアップテーブルが構築されます。その後、テーブルのルックアップを通じて距離計算が実行され、セグメント距離を取得し、それらを合計する。

しかし、頻繁なメモリ読み出しがパフォーマンスのボトルネックとなる。ルックアップテーブルをレジスタに収まるほど小さくすることができれば、メモリ読み出し操作を効率的なCPUのSIMD命令に変換することができる。

まず、各サブベクターは16のクラスにクラスタ化されるため、4ビットの値でクラスタの中心を表すことができる。"4ビットPQ "という名前の由来はここにある。次に、通常は浮動小数点数で表現される距離を、スカラー量子化（SQ）を使ってさらにuint8に変換する。こうすることで、1つのサブベクトルのルックアップテーブルを16×8＝128ビットのレジスタに格納することができる。

最後に、レジスタの格納レイアウト（AVX2命令セットを例にして）を見てみましょう。32個のベクタのサブベクタは、ルックアップテーブルと組み合わされて128ビットのレジスタに格納されます。ルックアップ」操作は、1つのSIMDシャッフルCPU命令で効率的に完了します。

レジスタレイアウト

ルックアップのためのSIMDシャッフル

ScaNNの論文は、最初の最適化に完全に焦点を当てており、数学的な導出を強調したアルゴリズム論文と考えられるので、これは妥当である。しかし、この論文で示された実験結果は驚くほど印象的である。

ScaNN論文で示された実験結果。

直感的には、損失を最適化するだけではこれほど劇的な効果は得られないはずだ。別のブログでも指摘されているが、本当に違いを生むのは4ビットPQ FastScanの部分である。

実験結果

ベクトルデータベースベンチマークツールVectorDBBenchを使い、簡単なテストを行った。従来のIVFFLATやIVF_PQに対するScaNNの性能優位性は極めて明白である。Milvusに統合した後、同じ想起率でCohere1Mデータセットにおいて、QPSはIVFFLATの5倍、IVF_PQの6倍に達する。

しかしながら、QPSはHNSWのようなグラフベースのインデックスよりも若干低いため、QPSの高いユースケースにおいては最初の選択肢とはならない。しかし、想起が低いシナリオでは許容範囲内であり（推薦システムなど）、生データをロードせずにScaNNを使用することで、非常に低いメモリフットプリント（元データの1/16）で印象的なQPSを達成することができ、優れたインデックスの選択肢となる。

インデックスタイプ	ケース	QPS	レイテンシー(p99)	リコール	メモリ
IVFFLAT	パフォーマンス1M	266	0.0173s	0.9544	3G
HNSW	パフォーマンス1M	1885	0.0054s	0.9438	3.24G
IVF_PQ	パフォーマンス1M	208	0.0292s	0.928	0.375G
ScaNN（with_raw_data：真）	パフォーマンス1M	1215	0.0069s	0.9389	3.186G
ScaNN（生データあり：false）	パフォーマンス1M	1265	0.0071s	0.7066	0.186G

結論

ScaNN は、お馴染みの IVFPQ フレームワークをベースに、量子化と低レベルのルックア ップ・アクセラレーションの両面で深いエンジニアリングを施すことで、それを大幅に推し進め たものである。量子化の目的をランキングの質と一致させ、内部ループのメモリボトルネックを排除することで、ScaNN はスコアを考慮した量子化と 4 ビット PQ FastScan パスを組み合わせ、従来メモリに縛られていたプロセスを効率的で SIMD フレンドリーな計算に変えている。

これにより、ScaNN は明確なニッチを持つことになる。ScaNNは、高リコール設定においてHNSWのようなグラフベースのインデックスを置き換えることを意図していない。その代わり、メモリ予算が厳しくリコールに敏感でないワークロードに対して、ScaNNは非常に小さなフットプリントで高いスループットを提供する。Milvus VectorDB に統合した後の実験では、ScaNN は Cohere1M データセットで IVFFLAT の約 5 倍の QPS を達成し、完全な想起よりも圧縮と効率が重要な高スループット、低レイテンシーの ANN 検索に最適な選択肢となりました。

ScaNNのさらなる探求や、実世界のシステムにおけるインデックス選択についての議論に興味がある方は、Slackチャンネルに参加して、当社のエンジニアやコミュニティの他のAIエンジニアとチャットしてください。また、Milvusオフィスアワーを通して、20分間の1対1のセッションを予約し、洞察やガイダンス、質問への回答を得ることもできます。