e-means: 10x faster k-means at equal loss - Blog

E-means, a new mini-batch optimization method for k-means clustering, reaches the same test loss as Lloyd's algorithm in 1.2 to 3 epochs versus 25 epochs, yielding a 10–45× wall-clock speedup on GPU against the Flash-KMeans implementation and 8–15× on CPU against Faiss. The method replaces the 1967 MacQueen update rule with exponential moving-average updates, sets batch size and step size automatically via scaling laws so no hyperparameter tuning is required, and adds improved initialization, dead-cluster revival, cosine-scheduled decay, and a finalization stage. Specialized GPU kernels fuse nearest-centroid assignment to convert the algorithmic gains into measured runtime savings. The result matters because k-means speed and quality have typically traded off against each other, and e-means claims both faster convergence and lower loss across a wide range of scales and datasets. Next, watch for independent reproduction of the wall-clock benchmarks and adoption of the method in production clustering pipelines.