Meta drops a 10x faster k-means algorithm that's better and quicker

Researchers at Meta's FAIR lab have open-sourced a new algorithm called 'e-means,' designed to replace the classic Lloyd's algorithm for k-means clustering. It leverages modern mini-batch optimization techniques with exponential moving averages, eliminating the need for manual hyperparameter tuning by using automatic scaling laws. The algorithm also improves upon initialization and includes a finalization stage to reduce loss.

In benchmarks, e-means achieves equal or lower loss than Lloyd's algorithm in dramatically fewer steps—often just 1.2 to 3 epochs instead of 25. This translates to a massive 10-45x speedup on GPU and 8-15x on CPU compared to state-of-the-art implementations. For data scientists and engineers working with large-scale clustering, this represents a rare win-win: a significant performance boost without sacrificing result quality.