Meta Researchers Release e-means, a Faster Replacement for k-means Clustering in FAISS

Clustering is often the slowest offline step in building the vector indexes, quantisers and data curation pipelines behind retrieval systems and AI training sets, so a faster method saves compute for companies working at that scale. In the authors' own tests, e-means reached the loss that Lloyd's k-means achieves in 25 passes over the data in between 1.4 and 2.6 passes, across 24 dataset configurations.

All the performance figures are self-reported. The researchers report wall-clock speedups of 10 to 45 times on GPUs compared with Flash-KMeans at equal loss, and 8 to 15 times on CPUs compared with FAISS's existing k-means. On the largest test, a set of 10 billion 1,024-dimension embeddings called DINO10B, the method split the data into 16.7 million clusters in 2.5 epochs. The paper's GPU runs used Nvidia H100s.

The method works on small batches of data rather than the full dataset. Each cluster keeps a running sum and count, and e-means lets older statistics fade with an exponential moving average, so centroids follow more recent assignments. Lloyd's algorithm recomputes those statistics from the whole dataset every iteration. The team also fitted two scaling laws that set batch size and initial step size from the dataset size, the number of clusters and the number of epochs, which removes most hyperparameter tuning. A revival step splits large clusters to replace ones that have gone empty, a common problem when the number of clusters is very large.

The approach has limits. Runs with 16 million centroids need 64 GiB of float32 accumulators, so the centroids have to be spread across several GPUs. Independent benchmarks have not yet been published, and the gains will need to hold up on other teams' workloads before e-means replaces existing k-means implementations in production systems.