e-means: Beating k-means in One-Tenth the Epochs by Borrowing Deep-Learning Mechanics Researchers at FAIR at Meta and École des Ponts have published a paper, "e-means: outperforming k-means (in one-tenth the epochs)," describing a clustering method that replaces Lloyd's full-dataset centroid recomputation with mini-batch updates smoothed by an exponential moving average, reporting 10–45x GPU wall-clock speedups over strong baselines. The e-means method matches Lloyd k-means loss at 25 epochs in just 1.4–2.6 epochs, frequently beats the k-means++ initialization baseline, converges to lower final loss, and partitions DINO10B — 10 billion embeddings — into 16 million clusters in 2.5 epochs. The authors released an implementation within Faiss and describe the hyperparameter selection as fully automated, making the method a drop-in for vector-search index building, corpus deduplication and embedding compression at billion scale. e-means: Beating k-means in One-Tenth the Epochs by Borrowing Deep-Learning Mechanics k-means is one of the oldest, most-used algorithms in machine learning — and for decades the standard way to make it faster has been to throw more compute at Lloyd’s algorithm. A new paper from FAIR at Meta with École des Ponts , titled “e-means: outperforming k-means in one-tenth the epochs ” arxiv.org/abs/2611.09501 https://arxiv.org/abs/2611.09501 , takes a different route: treat clustering as a modern optimization problem and apply the machinery we already use to train neural networks. The result is a method that converges dramatically faster and to lower loss — with reported 10–45x GPU wall-clock speedups over strong baselines. The core idea Classic Lloyd k-means does full passes over the data, recomputing every centroid from scratch each iteration. e-means instead uses mini-batch updates with an exponential moving average EMA on the centroids — the same EMA trick that stabilizes everything from optimizer momentum to teacher networks in self-supervised learning. Each small batch nudges the centroids, and the moving average smooths those updates into stable convergence without the cost of full-dataset sweeps. That’s the whole “deep-learning mechanics on a legacy algorithm” framing: nothing about the objective changes you’re still minimizing within-cluster MSE , but the optimization procedure is borrowed from how we train large models. What they report The headline numbers are striking: - Beats Lloyd k-means loss at 25 epochs in just 1.4–2.6 epochs — translating to the 10–45x GPU speedups. - Frequently beats k-means++ , the strong initialization baseline, not just vanilla Lloyd. - Converges to lower final loss , not merely faster to the same place. - At extreme scale: partitions DINO10B — 10 billion embeddings — into 16 million clusters in only 2.5 epochs. The paper’s charts show e-means converging below Faiss-GPU and Flash-KMeans on MSE-vs-epochs, and its aggregated-GPU-time curve pulling well ahead as dataset size climbs from 100K toward 10 billion points — the regime where clustering is otherwise measured in GPU-days. A nice practical touch: the authors describe the hyperparameter selection as fully automated , which matters because the usual objection to “yet another k-means variant” is that it introduces knobs. If the batch size, EMA decay, and schedule tune themselves, it’s a far easier drop-in. Why this is interesting Two things stand out to me. First, it’s a reminder that a lot of “classical” ML still has headroom — not by replacing the algorithm, but by importing optimization ideas that matured on the deep-learning side. k-means has been studied for 60+ years; getting a 45x efficiency jump “for free” by reframing the update rule is a genuinely good result. Second, it’s directly useful. Billion-scale clustering shows up everywhere now — building vector-search indices IVF partitions in Faiss , deduplicating training corpora, compressing embeddings, product quantization. If you can cluster 10B embeddings in a couple of epochs instead of days, you change what’s practical to do at retraining time. The authors have released a library within Faiss and a project site at e-means.github.io https://e-means.github.io . For anyone running large-scale clustering as part of a retrieval or data pipeline, it’s worth a look — the kind of unglamorous infrastructure win that quietly makes a lot of downstream systems cheaper. Paper: arxiv.org/abs/2611.09501 https://arxiv.org/abs/2611.09501 · Authors: Bessa, Mazaré, Szilvasy, Touvron, Picard, Douze, Jégou FAIR at Meta / École des Ponts