Meta FAIR's e-means beats k-means 10x faster
Original: E-means: Outperforming k-means in one-tenth the epochs
Why This Matters
K-means underpins vector search, compression, and clustering at massive scale across ML infrastructure.
Meta FAIR researchers open-sourced e-means, a k-means replacement using exponential moving averages that reaches lower loss than Lloyd's algorithm in 1.2–3 epochs vs. 25, delivering 10–45x GPU wall-clock speedup.
Developed at Meta FAIR and now available in the Faiss library, e-means replaces Lloyd's classic full-batch algorithm with mini-batch updates driven by exponential moving averages. The result: across a wide range of scales and datasets, e-means hits a test loss below Lloyd's 25-epoch benchmark in just 1.2 to 3 epochs.
Wall-clock gains are substantial. Against Flash-KMeans (the current GPU state-of-the-art Lloyd implementation), e-means delivers 10–45x speedup. On CPU against Faiss, that's 8–15x. Crucially, speed here doesn't come at the cost of quality—e-means achieves both lower loss and faster convergence, a combination the authors note is rare in k-means literature.
The core insight is applying modern deep learning optimization tools to a problem that has stubbornly relied on full-batch methods. Mini-batch k-means approaches have existed since MacQueen's 1967 update rule, but e-means modernizes them with exponential moving averages, automatic batch and step size selection via scaling laws (eliminating hyperparameter tuning), cosine-scheduled decay, improved initialization, dead-cluster revival, and a low-cost finalization stage. The algorithm is highly parallelizable with specialized GPU kernels. Code is live at faiss/contrib/e_means; the paper is on arXiv (2611.09501).