e-means: outperforming k-means (in one-tenth the epochs)
Bessa et al.
A mini-batch k-means with exponential moving average updates, whose decay rate and batch size are fixed by fitted scaling laws, beats the loss of 25 epochs of Lloyd’s algorithm in 1.4 to 2.6 epochs, a 10–45 times speed-up on GPUs.
Source published · In the Weekly Review of 15 November 2026
Filed under Optimization, Large language models
Lloyd’s algorithm alternates assigning every point to its nearest centre and recomputing the centres, so each round reads the whole dataset. The authors replace the full recomputation with mini-batch updates of an exponential moving average per centre, and fits scaling laws for how the decay rate and batch size affect the final loss, which removes the need for a hyperparameter sweep.
On a range of embedding datasets the method reaches a lower loss than 25 epochs of Lloyd’s algorithm in 1.4 to 2.6 epochs, and often beats k-means++. As a demonstration it splits 10 billion DINO embeddings into 16 million clusters in 2.5 epochs. Clustering at this scale sits underneath retrieval, quantisation and data curation for large models, so a tenfold saving in passes matters in practice.