e-means: Beating k-means in One-Tenth the Epochs by Borrowing Deep-Learning Mechanics

By Prahlad Menon 3 min read

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), 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. 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 · Authors: Bessa, Mazaré, Szilvasy, Touvron, Picard, Douze, Jégou (FAIR at Meta / École des Ponts)