Meta ajoute E-Means à Faiss 1.16.0 pour accélérer le clustering à grande échelle

Les responsables de la maintenance de Faiss chez Meta ont publié la version 1.16.0 le 10 novembre 2026, qui intègre l’algorithme de clustering e-means de FAIR chez Meta, avec des implémentations pour CPU, GPU et systèmes distribués. Les chercheurs indiquent que l’algorithme atteint une erreur inférieure à celle de Lloyd k-means après 25 époques en seulement 1,4 à 2,6 époques, avec des accélérations de 10 à 45× du temps d’exécution sur GPU par rapport aux implémentations comparées.

La publication du logiciel fait suite au dépôt sur arXiv du préprint de recherche, le 6 novembre 2026, et ne constitue donc pas la première divulgation publique de l’algorithme. Les travaux sont le fruit de recherches menées par des chercheurs de FAIR chez Meta et de l’École Nationale des Ponts et Chaussées.

La version 1.16.0 ajoute des implémentations de référence d’e-means, l’entraînement distribué et avec partitionnement des centroïdes, des backends d’affectation Triton et CuTe, l’affectation en précision réduite et des benchmarks permettant de reproduire les résultats de recherche. Elle comprend également des démonstrations avec DINO qui conservent les données en mémoire ou les lisent en flux depuis des SSD.

Comment e-means met à jour les centroïdes

K-means cherche des centroïdes qui minimisent la distance quadratique moyenne entre les vecteurs et leur centroïde le plus proche, ce qui facilite la recherche, la quantification et la sélection des données. L’algorithme de Lloyd affecte chaque point au centroïde le plus proche, puis recalcule la somme et le nombre de points de chaque cluster à partir de l’ensemble des données. E-means met plutôt à jour les sommes et les nombres à l’aide de mini-lots et d’une décroissance exponentielle, de sorte que les affectations plus anciennes perdent progressivement de leur influence ; chaque centroïde reste le rapport entre la somme courante des vecteurs et le nombre courant de points. Utiliser l’ensemble des données en un seul lot avec un pas de 1 reproduit une itération de Lloyd.

Deux lois d’échelle ajustées déterminent la taille des lots et le pas initial en fonction de la taille du jeu de données, du nombre de clusters et du budget d’époques, évitant ainsi le balayage distinct des hyperparamètres requis par les approches antérieures par mini-lots. Un calendrier cosinus réduit le pas à un dixième de sa valeur initiale. La classe publiée utilise par défaut cinq passes d’entraînement et accepte les passes fractionnaires.

Les auteurs ont ajusté les lois à partir de 75 000 exécutions d’optimisation sur des configurations DEEP. Ils indiquent un regret médian de 0,07 % sur les jeux de données mis de côté pour la loi du pas et de 0,19 % pour la loi par défaut concernant la taille des lots ; le regret désigne ici l’erreur supplémentaire par rapport au meilleur réglage de la grille. La méthode réactive également les clusters sous-utilisés en scindant un cluster donneur, puis termine en calculant la moyenne exacte de chaque cluster à partir des affectations de la dernière époque. Une autre méthode de finalisation, fondée sur une moyenne mobile lente, vise plutôt l’erreur hors échantillon.

Les benchmarks vont jusqu’à dix milliards de vecteurs

L’article complet décrit une validation sur des jeux de données d’embeddings et des jeux de données synthétiques. Les principales comparaisons sur GPU ont été réalisées avec des GPU H100 de 80 Go, et les expériences sur CPU avec un Xeon Platinum 8462Y+ à 64 cœurs. Sur 11 tests d’embeddings VIBE, les auteurs indiquent qu’e-means a nécessité de 1,6 à 2,6 époques pour atteindre l’erreur obtenue par Lloyd en 25 époques, avec des accélérations de 8,0× à 22,8× par rapport à Flash-KMeans sur un H100 et de 9,0× à 15,0× par rapport à Faiss sur 64 cœurs CPU, à raison de 20 graines par test.

À la plus grande échelle, les auteurs indiquent avoir réparti DINO10B, qui contient 10 milliards d’embeddings de patches DINO de 1 024 dimensions, en environ 16,7 millions de clusters en 2,5 époques avec une affectation exacte, obtenant une erreur de test légèrement inférieure à celle de la référence Lloyd après 25 époques. Cette exécution a mobilisé 779 heures-GPU sur 32 machines. Lors d’une autre exécution, qui utilisait une recherche approximative du centroïde le plus proche au moyen d’un index à fichiers inversés (IVF), la référence a été dépassée après trois époques, en 23,2 heures-GPU sur une machine équipée de huit GPU. L’approche IVF recherche dans certains compartiments de centroïdes plutôt que de comparer chaque point à tous les centroïdes.

L’article indique qu’à l’échelle de dix milliards de vecteurs, l’affectation IVF coûte 34× moins cher que l’affectation exacte, mais qu’elle n’apporte aucun gain avec 100 millions de vecteurs. Cette différence montre que le nombre d’époques ne suffit pas à déterminer les besoins en infrastructure : l’implémentation et la méthode d’affectation déterminent la quantité de matériel nécessaire à une exécution.

Disponibilité et limites documentées

Le guide officiel de l’utilisateur fournit NumpyEmeans pour les données NumPy et Emeans pour les tenseurs PyTorch. Faiss seul prend en charge l’exécution sur CPU ; l’exécution sur GPU nécessite PyTorch compatible avec CUDA. Les noyaux CuTe sont disponibles sur H100 et H200, et Triton sur les autres GPU NVIDIA récents pris en charge. Seule l’affectation au centroïde le plus proche utilise une précision réduite sur GPU ; les centroïdes, les sommes cumulées et les distances renvoyées restent en FP32. Les classes à centroïdes répliqués ou partitionnés prennent en charge l’entraînement sur plusieurs GPU ; l’article note que les sommes FP32 de 16 millions de centroïdes occupent 64 Gio, ce qui motive le partitionnement à cette échelle.

Les lois d’échelle ont été ajustées pour des données de dimension relativement élevée et ne sont pas optimales pour les jeux de données de très faible dimension ou de très petite taille. Par conséquent, les valeurs par défaut de la version publiée choisissent la loi de qualité pour la taille des lots à 16 dimensions ou moins et désactivent la réactivation à deux dimensions ou moins. Le guide précise également que les étiquettes d’entraînement renvoyées proviennent de la dernière passe et ne correspondent pas nécessairement aux affectations par rapport aux centroïdes finaux, et que le chemin GPU ne vérifie pas si les entrées contiennent des valeurs NaN ou infinies.

Pour les pipelines d’IA qui regroupent de grands ensembles d’embeddings, cette publication concrétise le compromis : une bibliothèque maintenue permet de réduire le nombre de passes d’entraînement, tandis que les plus fortes réductions de la consommation GPU dépendent de l’échelle, du matériel et de l’adéquation de l’affectation approximative à la charge de travail.