プロダクト量子化は大規模なプライベートベクトルコレクションをどのように高速化するのか？

プロダクト量子化は、埋め込みを部分空間に分割し、各部分ベクトルを学習済みの小さなセントロイドコードに置き換えることで、大規模なプライベートベクトルコレクションを高速化します。

これは、より広いベクトル量子化ファミリーに含まれる具体的な仕組みです。各座標を個別に縮小するのではなく、PQは複数の小さなコードブックを学習し、高次元の埋め込みをコードIDの列として表現します。ホーム検索サーバーでは、より多くのコードをメモリに保持し、事前計算したテーブルからクエリ距離を推定できます。その結果、保存するベクトルのバイト数と、候補を広範囲に走査する際に必要なフル精度演算の量を削減できます。

PQは1つの高次元埋め込みを複数の部分ベクトルに分割する

埋め込みの次元数が `d` だとします。PQは `M` 個のサブ量子化器を選び、座標を `M` 個の低次元ブロックに分割します。これにより、各ブロックを個別にモデル化できます。

サブ量子化器の数によって、元の埋め込みがいくつの低次元ブロックに分割されるか、そして1つのPQ表現を構成するコードIDの数が決まります。

この因数分解が、プロダクト量子化という名前の由来です。完全なベクトル全体に対する巨大な1つのコードブックではなく、複数の部分空間で独立して行われた選択から全体の近似を組み立てます。部分空間は、ベクトルの次元を適切に分割できなければなりません。部分空間のサイズと数は、圧縮率、コードブックの学習コスト、距離の精度、データ分布が因数分解された表現にどの程度適合するかに影響します。

各部分空間は代表的なセントロイドのコードブックを学習する

PQは通常、コレクションを代表するサンプルを使って学習します。各部分空間では、クラスタリングによって、類似した部分ベクトルのグループを代表するセントロイドベクトルを見つけます。

一般的なプロダクト量子化器はk-meansを使って各部分空間内のセントロイドを学習し、学習用部分ベクトルと割り当てられた代表値との近似誤差を最小化します。

学習後、データベースは圧縮された検索コード内に元の座標をすべて保存する必要がなくなります。各部分空間で最も近いセントロイドの識別子だけを保存すれば済みます。

学習サンプルが将来の家庭内ドキュメントを適切に代表していない場合、学習済みのセントロイドは後から追加されるベクトルをうまく近似できないことがあります。そのため、コードブックの品質は実装上の重要な境界条件であり、一度決めたら無視できるような細部ではありません。

保存されるベクトルは短いコードIDの列になる

各部分ベクトルについて、エンコーダーは最も近いセントロイドを探し、そのセントロイドのインデックスを保存します。`M` 個のインデックスを連結すると、完全な埋め込みのPQコードになります。

設定可能なビット数を持つm個の部分ベクトルコードを保存することで、長い浮動小数点配列を、セントロイド識別子の短い列と共有コードブックに置き換えられます。

たとえば、サブ量子化器あたり8ビットなら、その部分空間で256個のセントロイド候補を表現できます。ベクトルコード全体のサイズは、元の各次元を32ビット精度で保存する場合ではなく、サブ量子化器の数に応じて増加します。ただし、コードブックとインデックスのオーバーヘッドにもメモリが必要なため、コレクション全体のサイズはコードのバイト数だけを合計したものより大きくなります。共有コードブックのコストを十分な数のベクトルで分散できる場合に、削減効果が最も大きくなります。

-15% OFF

ZimaBoard 2 - あなたの大きなアイデアのためのミニホームサーバー

Single board computer zimaboard2

$339.00 - $519.00

Buy Now

クエリは各部分空間の距離ルックアップテーブルを作成する

クエリが到着すると、システムはそれを同じ部分空間に分割し、各コードブック内のすべてのセントロイドとの距離を計算します。これらの値が小さなルックアップテーブルになります。

クエリとセントロイド間の距離テーブルは、各部分空間にある各セントロイドへのクエリ距離を事前計算します。これにより、候補との距離を完全なベクトル演算ではなく、小さなルックアップから組み立てられます。

保存されたデータベクトルとの距離を推定する際、検索で各ベクトルの完全な座標を再構成する必要はありません。各コードIDを読み取り、対応する部分空間の距離を参照して、それらの値を合計します。

このテーブル駆動の方式は、非対称距離計算と呼ばれることがよくあります。クエリは高精度のままにできる一方、データベース内のベクトルは量子化コードで表現されるためです。

コンパクトなコードはコレクションの増加に伴うキャッシュ局所性を改善する

大規模なベクトル走査では、1回の距離計算の数学的な複雑さよりも、候補データをメモリ上で移動させることが制約になる場合がよくあります。

短いコードなら、より多くの候補をCPUキャッシュに収められ、比較ごとのメモリ帯域幅も削減できます。

圧縮距離計算の経路は、SIMDに適したテーブル参照によって高速化できます。プロダクト量子化検索では、コンパクトなコードを繰り返し読み取り、部分空間の距離を累積するためです。

プライベートなホームコレクションでは、これにより、アクティブな検索表現をRAM内に維持できるインデックスと、ローカルLLM、データベース、ファイルシステムキャッシュと絶えずメモリを奪い合うインデックスとの差が生まれることがあります。

コレクションが非常に小さい場合、メタデータフィルタリングによって各クエリの対象が少数のベクトルに絞られる場合、または別のインデックス層がレイテンシの大部分を占める場合は、効果が小さくなります。

PQは通常、圧縮と速度のために一部の再現率をトレードオフにする

セントロイドコードは元の部分ベクトルを近似するため、真の距離が近い2つの候補では順位が入れ替わることがあります。一般に、より積極的に圧縮するほど、候補を区別するための情報が少なくなります。

プロダクト量子化を非可逆圧縮として扱うと、この境界が明確になります。小さなコードはベクトルメモリを削減しますが、量子化誤差によって近傍候補の順位が変わる可能性があります。

サブ量子化器の数やビット数を増やせば、より多くの詳細を保持できますが、各コードとルックアップ構造が大きくなります。小さなコードはより多くのメモリを節約しますが、量子化誤差が発生する可能性を高めます。適切な設定はコーパスによって異なります。関連性の高いマニュアル、重複したドキュメントのバージョン、細粒度のコード検索では、多様な家庭内メモを対象とした幅広いセマンティック検索よりも高い精度が必要になることがあります。

コンパクトな第1段階の後にフル精度で再スコアリングできる

PQを使う場合でも、最終結果を圧縮距離による順位だけに盲目的に任せる必要はありません。システムはPQでより広い候補集合を取得し、その後、別の場所に保存した元のベクトルを使って候補だけを再スコアリングできます。

セマンティックなベクトル検索では、PQは候補比較に使う表現を変更します。一方で、出典情報、メタデータフィルタリング、再ランキング、RAGは引き続きそのベクトル処理段階の周囲で機能します。

この2段階方式では、メモリと計算を非対称に割り当てます。圧縮コードで大規模な候補空間を処理し、完全精度のベクトルに触れるのは小さな候補リストだけに限定します。

プロダクト量子化は、コンパクトなコードによってワーキングセットと距離計算に伴うデータ転送を大幅に削減しながら、ローカルRAGシステムが必要とする根拠品質を下回らない測定済みの再現率を維持できる場合に、プライベートコレクションを高速化します。