MetaのFaiss 1.16.0、大規模クラスタリングを高速化するE-Meansを追加

MetaのFaissメンテナーは2026年11月10日、FAIR at Metaのe-meansクラスタリングアルゴリズムをCPU、GPU、分散環境向けの実装とともに収録したバージョン1.16.0をリリースしました。研究者らによると、比較対象の実装に対し、GPUの実時間で10～45倍の高速化を達成し、25エポック実行したLloydのk-meansを1.4～2.6エポックで上回る損失を実現しました。

このソフトウェアリリースは、研究プレプリントのarXivへの投稿（2026年11月6日）に続くものであり、アルゴリズムが初めて公に明らかにされたことを意味するものではない。この研究は、FAIR at MetaとÉcole Nationale des Ponts et Chausséesの研究者によるものだ。

バージョン1.16.0では、e-meansの参照実装、分散トレーニングとセントロイド分割トレーニング、TritonおよびCuTeの割り当てバックエンド、低精度割り当て、研究結果を再現するためのベンチマークが追加されました。また、データをメモリ上に保持する方法と、SSDからストリーミングする方法を示すDINOのデモも含まれています。

e-meansによるセントロイドの更新方法

k-meansは、ベクトルと最も近いセントロイドとの平均二乗距離を最小化するセントロイドを求める手法で、検索、量子化、データキュレーションに利用されます。Lloydのアルゴリズムでは、すべての点を最も近いセントロイドに割り当て、データセット全体から各クラスタの合計と件数を再計算します。一方、e-meansはミニバッチを使って、指数関数的に減衰する合計値と件数を更新します。そのため、過去の割り当ての影響は徐々に小さくなります。各セントロイドは、累積ベクトル合計を累積件数で割った値として保たれます。データセット全体を1つのバッチとして使い、ステップサイズを1にすると、Lloydの反復を1回実行した場合と同じ結果になります。

2つの適合済みスケーリング則により、データセットのサイズ、クラスタ数、エポック数の予算からバッチサイズと初期ステップサイズを算出できるため、従来のミニバッチ方式で必要だった個別のハイパーパラメーター探索は不要になります。コサインスケジュールでは、ステップサイズを開始時の10分の1まで小さくします。リリースされたクラスでは、学習パスの既定値は5回で、端数を含む回数も指定できます。

著者らは、DEEP構成で75,000回の最適化を実行してスケーリング則を適合させました。テスト時に使わないデータセットにおける後悔値の中央値、すなわち最良のグリッド設定に対する誤差の増加分は、ステップサイズの法則で0.07%、既定のバッチサイズの法則で0.19%だったと報告しています。また、この手法では、ドナーとなるクラスタを分割して利用率の低いクラスタを再活性化し、その後、最終エポックの割り当てに基づいて各クラスタの正確な平均を求めて処理を終えます。これとは別に、動きの遅い移動平均を使う最終化手法もあり、こちらはサンプル外誤差の低減を目指します。

ベンチマークを100億ベクトルまで拡大

論文全文では、埋め込みデータセットと合成データセットを使った検証について説明しています。主なGPU比較には80GBのH100 GPUを、CPU実験には64コアのXeon Platinum 8462Y+を使用しました。11件のVIBE埋め込みテストでは、e-meansは1.6～2.6エポックで、Lloydを25エポック実行した場合の誤差に到達したと著者らは報告しています。テストごとに20個のシードを使った結果、H100を1基使用した場合、Flash-KMeansに対して8.0～22.8倍、CPUコアを64個使用した場合、Faissに対して9.0～15.0倍の高速化が得られました。

最大規模の実験では、10億ではなく100億個の1,024次元DINOパッチ埋め込みを含むDINO10Bを、正確な割り当てを用いて約1,670万個のクラスタに2.5エポックで分割したと著者らは報告しています。テスト誤差は、Lloydを25エポック実行したベースラインをわずかに下回りました。この実行では、32台のマシンで合計779 GPU時間を使用しました。別の実行では、反転ファイル（IVF）インデックスを使った近似最近傍セントロイド検索により、8基のGPUを搭載した1台のマシンで23.2 GPU時間を使用し、3エポック後にベースラインを上回りました。IVF方式では、すべての点とすべてのセントロイドを比較するのではなく、選択したセントロイドのバケットを検索します。

論文によると、100億ベクトルの規模ではIVFによる割り当てのコストは正確な割り当ての34分の1ですが、1億ベクトルでは利点がありません。この違いは、エポック数だけでは必要なインフラが決まらない理由を示しています。実装と割り当て方法によって、実行に必要なハードウェアの規模が変わります。

利用方法と文書に記載された制限

公式のユーザーガイドでは、 NumpyEmeans NumPyデータ向けのものと、 Emeans PyTorchテンソル向けのものが提供されています。Faiss単体で対応するのはCPU実行のみです。GPU実行にはCUDA対応のPyTorchが必要で、H100とH200ではCuTeカーネル、その他の対応する比較的新しいNVIDIA GPUではTritonを利用できます。GPU上で低精度が使われるのは最近傍セントロイドの割り当てだけで、セントロイド、累積合計、返される距離はFP32のままです。複製型および分割型のセントロイドクラスは、複数GPUでのトレーニングに対応しています。論文によると、セントロイドが1,600万個の場合、FP32の合計値だけで64 GiBを占めるため、この規模では分割が有効です。

このスケーリング則は比較的高次元のデータを想定して調整されており、非常に低次元のデータや小規模なデータセットには最適ではありません。そのため、リリース版の既定設定では、次元数が16以下の場合に品質重視のバッチサイズ則を選び、次元数が2以下の場合はクラスタの再活性化を無効にします。またガイドでは、返される学習ラベルは最後のパスで得られたものであり、最終的なセントロイドへの割り当てとは限らないこと、GPUの処理経路では入力にNaNや無限値が含まれていないかを確認しないことにも注意を促しています。

大規模な埋め込みデータをクラスタリングするAIパイプラインにとって、今回のリリースはトレードオフを明確に示しています。メンテナンスが続くライブラリで学習パスを減らせる一方、GPU消費量を大幅に削減できるかどうかは、データ規模やハードウェアに加え、近似割り当てが処理内容に適しているかどうかに左右されます。