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

> Source: <https://themenonlab.blog/blog/e-means-faster-kmeans-deep-learning-mechanics/>
> Published: 2026-11-16 00:00:00+00:00

# 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)
