| title | e-means: outperforming k-means (in one-tenth the epochs) |
|---|---|
| authors | Swann Bessa, Pierre-Emmanuel Mazaré, Gergely Szilvasy, Hugo Touvron, David Picard, Matthijs Douze, Hervé Jégou |
| date | 2026-11-06 |
| venue | arXiv (preprint, not peer reviewed) |
| id | arXiv:2611.09501 |
| affiliation | Meta |
| upvotes | 8 (Hugging Face Daily Papers, 2026-11-12) |
| links | abs pdf hf code |
| cite | |
| related | Sharpening Tax in Post-Training World Action Modeling with Progressive Visual Planning Native Action-Prior Learning from Videos for World Action Models InteractiveWorld: A Verifiable Human-Centric Environment for Building Better Interactive MLLM Assistants Context Language Models |
| abstract | 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. |
bibtex
@misc{bessa2026e,
title={e-means: outperforming k-means (in one-tenth the epochs)},
author={Swann Bessa and Pierre-Emmanuel Mazaré and Gergely Szilvasy and Hugo Touvron and David Picard and Matthijs Douze and Hervé Jégou},
year={2026},
eprint={2611.09501},
archivePrefix={arXiv},
url={https://arxiv.org/abs/2611.09501}
}