Luceneにおけるスカラー量子化の理解

Elastic認定の取得をご希望ですか？次回のElasticsearch Engineerトレーニングがいつ開催されるかご確認ください。無料のクラウドトライアルを開始するか、ローカルマシンでElasticを試すことができます。

Luceneにおける自動バイト量子化

HNSW はベクトルを保存および検索するための強力かつ柔軟な方法ですが、高速に実行するには大量のメモリが必要です。たとえば、768 次元の 1MM float32 ベクトルをクエリするには、およそ $1,000,000 * 4 * (768 + 12) = 3120000000 バイト、つまり約 3GB$ の RAM が必要です。大量のベクトルを検索し始めると、コストが高くなります。メモリ使用量を約 $75%$ 削減する方法の 1 つは、バイト量子化を使用することです。Lucene と Elasticsearch は以前から $バイト$ ベクトルのインデックス作成をサポートしてきましたが、これらのベクトルの構築はユーザーの責任でした。Lucene に $int8$ スカラー量子化が導入されたため、この状況は変わりつつあります。

スカラー量子化101

すべての量子化手法は、生データの非可逆変換であると見なされます。つまり、スペースの都合上、一部の情報が失われます。スカラー量子化の詳細な説明については、「スカラー量子化 101」を参照してください。大まかに言えば、スカラー量子化は非可逆圧縮技術です。簡単な計算により、リコールにほとんど影響を与えずに、大幅にスペースを節約できます。

建築を探る

Elasticsearch の使用に慣れている方は、これらの概念にすでに馴染みがあるかもしれませんが、ここでは検索対象ドキュメントの配布について簡単に概要を説明します。

各 Elasticsearch インデックスは複数のシャードで構成されます。各シャードは 1 つのノードにのみ割り当てることができますが、インデックスごとに複数のシャードを割り当てることで、ノード間で並列計算が可能になります。

各シャードは単一のLucene インデックスとして構成されます。Lucene インデックスは複数の読み取り専用セグメントで構成されます。インデックス作成中、ドキュメントはバッファリングされ、定期的に読み取り専用セグメントにフラッシュされます。特定の条件が満たされると、これらのセグメントをバックグラウンドでより大きなセグメントにマージできます。これらはすべて構成可能であり、独自の複雑さを伴います。ただし、セグメントとマージについて話すときは、読み取り専用の Lucene セグメントと、これらのセグメントの定期的な自動マージについて話しています。ここでは、セグメントのマージと設計上の決定について詳しく説明します。

Luceneにおけるセグメントごとの量子化

Lucene のすべてのセグメントには、個々のベクトル、HNSW グラフインデックス、量子化されたベクトル、および計算された分位数が保存されます。簡潔にするために、Lucene が量子化されたベクトルと生のベクトルを保存する方法に焦点を当てます。すべてのセグメントについて、 $vec$ ファイル内の生のベクトル、 $veq$ 内の量子化されたベクトルと単一の補正乗数浮動小数点数、および $vemq$ ファイル内の量子化に関するメタデータを追跡します。

図 1: 生のベクター保存ファイルの簡略化されたレイアウト。 $float$ 値は 4 バイトなので、 dimension $* 4 * numVectors のディスク領域を占有します。$ 量子化しているため、これらは HNSW 検索中に読み込まれません。これらは、特に要求された場合にのみ使用されます（例：再スコアリングによるブルートフォースセカンダリ、またはセグメントマージ中の再量子化に使用します。

図2: $.veq$ の簡略化されたレイアウトファイル。 $(dimension + 4)*numVectors$ のスペースを占有し、検索中にメモリにロードされます。 $+ 4$ バイトは、スコアリングを調整して精度と再現性を向上させるために使用される補正乗数浮動小数点数を表します。

図 3: メタデータファイルの簡略化されたレイアウト。ここで、このセグメントの計算された分位数とともに、量子化とベクトル構成を追跡します。

したがって、各セグメントについて、量子化されたベクトルだけでなく、これらの量子化されたベクトルの作成に使用された分位数と元の生のベクトルも保存します。しかし、なぜ生のベクトルを保存しておくのでしょうか?

あなたとともに成長する量子化

Lucene は定期的にセグメントを読み取り専用にフラッシュするため、各セグメントにはすべてのデータの部分的なビューのみが表示されます。つまり、計算された四分位数は、データ全体のそのサンプルセットにのみ直接適用されます。さて、サンプルがコーパス全体を適切に代表しているのであれば、これは大した問題ではありません。しかし、Lucene ではさまざまな方法でインデックスを並べ替えることができます。したがって、セグメントごとの分位数計算にバイアスを追加する方法でソートされたデータをインデックス化することができます。また、いつでも好きなときにデータをフラッシュできます。サンプルセットは、たとえ 1 つのベクトルだけでも非常に小さい可能性があります。さらにもう一つの問題は、マージがいつ発生するかを制御できることです。Elasticsearch ではデフォルトと定期的なマージが設定されていますが、 _force_merge API を介していつでもマージを要求できます。では、どうすれば、優れた再現性をもたらす適切な量子化を実現しながら、こうした柔軟性をすべて実現できるのでしょうか?

Lucene のベクトル量子化は時間の経過とともに自動的に調整されます。Lucene は読み取り専用セグメントアーキテクチャで設計されているため、各セグメントのデータが変更されていないことが保証され、コード内で更新できるタイミングが明確に区別されます。つまり、セグメントのマージ中に、必要に応じて分位数を調整し、ベクトルを再量子化できる可能性があります。

図 4: 異なる分位数を持つ 3 つのセグメントの例。

しかし、再量子化はコストがかかるのではないですか?多少のオーバーヘッドはありますが、Lucene は分位数をインテリジェントに処理し、必要な場合にのみ完全に再量子化します。図 4 のセグメントを例に挙げてみましょう。セグメント $A$ と $B$ にそれぞれ $1,000 件の$ ドキュメントを割り当て、セグメント $C$ には $100 件の$ ドキュメントのみを割り当てます。Lucene は、四分位数の加重平均を取得し、その結果として得られる結合された四分位数がセグメントの元の四分位数に十分近い場合、そのセグメントを再量子化する必要がなく、新しく結合された四分位数を利用します。

図 5: セグメント $A$ と $B$ に $1000 件の$ ドキュメントがあり、セグメント $C$ には $100 件の$ ドキュメントしかない場合の結合された分位数の例。

図5に示されている状況では、結果として得られる統合された分位数は、 $A$ と $B$ の元の分位数と非常に類似していることがわかります。したがって、ベクトルを量子化する必要性は認められません。セグメント $C$ は、逸脱しすぎているようです。その結果、 $C$ のベクトルは、新しく結合された分位値で再量子化されます。

実際、結合された四分位数が元の四分位数と大幅に異なる極端なケースもあります。この場合、各セグメントからサンプルを取得し、四分位数を完全に再計算します。

量子化性能と数値

それで、それは高速であり、良好なリコールを提供し続けるのでしょうか?c3-standard-8 GCP インスタンスで実験を実行すると、次の数値が収集されました。 $float32$ との公平な比較を確実にするために、生のベクトルをメモリ内に保持するのに十分な大きさのインスタンスを使用しました。最大内積を使用して $400,000 個の$ Cohere Wikiベクトルをインデックスしました。

図 6: 量子化ベクトルと生のベクトルの Recall@10。量子化ベクトルの検索パフォーマンスは生のベクトルよりも大幅に高速で、さらに 5 つのベクトルを集めるだけでリコールをすぐに回復できます。これは $quantized@15$ で確認できます。

図6にそのストーリーを示します。予想通り、再現率の違いはありますが、それは大きな差ではありません。そして、さらに 5 つのベクトルを集めるだけで、再現率の差は消えます。これらすべてを、セグメントのマージが $2 倍$ 高速化し、 $float32$ ベクトルの 1/4 のメモリで実現します。

まとめ

Lucene は、難しい問題に対する独自のソリューションを提供します。量子化には「トレーニング」や「最適化」のステップは必要ありません。Lucene では、問題なく動作します。データがシフトした場合にベクトルインデックスを「再トレーニング」する必要があることを心配する必要はありません。Lucene は重要な変更を検出し、データの存続期間中これを自動的に処理します。この機能が Elasticsearch に導入されるのを楽しみにしてください。