Meta's e-means Beats 25-Pass Clustering in Just 3 Passes at 45x Speedup

Meta FAIR researchers have released e-means , a mini-batch clustering method that combines exponential moving average updates, dead-cluster revival, fitted hyperparameter rules, and fused GPU kernels. Across the paper’s benchmarks , it matches or beats the test loss of Lloyd’s algorithm after 25 epochs using 1.2 to 3 epochs. One epoch represents a full pass over the dataset, although e-means updates centroids from mini-batches.

The implementation is available in the Faiss repository . Reported wall-clock gains range from 10–45× on GPUs and 8–15× on CPUs when measured against the Lloyd baseline at the target loss.

The cost hides in repeated assignments

K-means partitions vectors into k groups by minimizing the average squared distance between each vector and its assigned centroid. Lloyd’s algorithm, circulated at Bell Labs in 1957, performs two operations per iteration: it assigns every vector to its nearest centroid, then recomputes each centroid as the exact mean of its assigned vectors. Lower loss indicates tighter clusters.

Every Lloyd iteration processes all n vectors, so repeated nearest-centroid assignments dominate runtime on large embedding sets. Mini-batch methods reduce the work per update by processing subsets of the data, but widely used implementations still rely on MacQueen’s 1967 running-average rule, which gives early assignments a lasting influence.

Mini-batch clustering can also produce dead clusters. A centroid that receives no assignments cannot update from the current batch and may remain unused, reducing the effective codebook size. That loss of capacity becomes costly when a quantizer contains millions of centroids.