Back to Devoured - November 12, 2026
DEVOURED
e-means: Outperforming k-means in One-Tenth the Epochs

e-means: Outperforming k-means in One-Tenth the Epochs

Data Arxiv
Meta researchers developed e-means, a clustering algorithm that uses exponential moving averages to reach higher accuracy than k-means in a fraction of the time.
What: Swann Bessa and team at Meta FAIR report that e-means achieves lower clustering loss in under 3 epochs compared to 25 epochs for Lloyd's k-means. The method provides 10–45x speedups on GPU hardware.
Why it matters: Efficiency gains in clustering are critical as the scale of embedding datasets (e.g., 10 billion DINO embeddings) grows beyond the practical limits of traditional, full-dataset iteration.
Deep dive
  • Methodology: Uses mini-batch updates with exponential moving averages (EMA) for centroid updates.
  • Performance: Achieves lower loss than Lloyd's k-means in 1.4 to 2.6 epochs.
  • Scaling: Provides consistent results across different problem sizes and embedding datasets.
  • Hyperparameters: Includes a formulaic rule to set decay rate and batch size without needing parameter sweeps.
  • Benchmarks: Successfully partitioned 10 billion DINO embeddings into 16 million clusters in 2.5 epochs.
Decoder
  • Lloyd's Algorithm: The standard iterative method for solving the k-means clustering problem.
  • Centroid: The central point or 'mean' of a cluster in a dataset.
  • Embeddings: Vector representations of data (images, text) used in machine learning models.
Original article

e-means: outperforming k-means (in one-tenth the epochs)

Lloyd's k-means algorithm is a long-running standard for clustering, with applications in data analysis, retrieval, quantization and data curation. In this paper, we introduce an exponential moving average optimization procedure for k-means with mini-batch updates, powered by modern deep learning machinery and new insights. We also establish scaling laws on how decay rate and batch size impact final performance. This gives us a formulaic rule to fix them for multiple problem sizes and embedding datasets, without the need for any hyperparameter sweep. The resulting clustering algorithm, coined e-means, is much faster than Lloyd k-means and converges to lower losses, frequently even beating k-means++. On a wide array of embeddings datasets, it beats the loss of Lloyd k-means at 25 epochs in 1.4 to 2.6 epochs, which translates to 10-45x GPU wall-clock speedups compared to state-of-the-art k-means implementations. As an example, e-means partitions DINO10B, a dataset of 10 billion DINO embeddings, into 16 million clusters in only 2.5 epochs, reaching a loss below Lloyd's at 25 epochs.

Explore all 61 articles in today's digest

Fresh dev news, AI-digested daily. Never miss a trend at devoured.fyi