Contexte et objectifs
Le clustering de vecteurs denses alimente les index de recherche vectorielle (IVF, ScANN). Les méthodes classiques utilisent Lloyd’s k‑means avec dix itérations, ce qui impose un temps d’attente important avant les requêtes. e‑means propose de réduire le nombre d’époques à deux tout en maintenant la qualité, tandis que SuperKMeans supprime la lecture de dimensions inutiles, offrant un gain de 2 à 10 ×. L’article décrit la combinaison de ces deux approches sous le nom SuperEMeans, visant à réduire davantage le temps de clustering sans sacrifier la pertinence des recherches.
Mise en œuvre et jeu de données
Les expériences s’appuient sur deux jeux de données publics : 5 M d’embeddings OpenAI (1536 dimensions, 27 GB) et 10 M de passages MS MARCO (1024 dimensions, 40 GB). Un index IVF est construit avec un ratio point‑par‑cluster de 1 : 256, soit environ 20 000 centroids pour le jeu OpenAI et 40 000 pour le jeu Cohere. Le benchmark s’exécute sur une instance Zen 5 (16 cœurs, 128 GB RAM, r8a.4xlarge). La bibliothèque SuperKMeans, compatible avec tout CPU, a été étendue pour inclure e‑means et SuperEMeans.
Résultats de performance
Le tableau de temps d’exécution montre que SuperEMeans (2 époques) dépasse e‑means de 1,8 ×, tandis qu’à 5 époques le gain atteint près de 3 ×. Sur le jeu OpenAI, la mesure recall@100 atteint 0,964 avec SuperEMeans, en scannant 51 962 vecteurs, soit une amélioration du compromis qualité‑coût par rapport à Lloyd’s. Sur le jeu Cohere, le même rappel (0,918) nécessite le scan de 121 511 vecteurs, indiquant un léger désavantage de e‑means qui consomme 8 % de vecteurs supplémentaires pour le même rappel.
Analyse de l’équilibre des clusters
e‑means génère des clusters plus volumineux dans les zones fréquemment interrogées, ce qui augmente le nombre de points scannés. Cette situation provient de la mise à jour par mini‑batch : un cluster qui reçoit peu de points tôt reste petit pendant tout le processus. Le mécanisme de « revival » réinitialise les clusters sous‑utilisés toutes les cinq batches, avec un seuil de 0,1 × la moyenne d’usage. Les auteurs constatent que ce seuil est trop conservateur ; en le portant à 0,3 ×, l’équilibre des clusters se rapproche de celui de Lloyd’s, réduisant le coût de scan, notamment sur le jeu Cohere.