Meta FAIR open-sources e-means, a k-means it says runs 10x faster

Meta FAIR has open-sourced e-means, a reworked k-means algorithm that its authors say reaches a lower clustering loss than the classic Lloyd's method while running about ten times faster. Because k-means quietly underpins work as varied as embedding search, vector quantization and dataset compression, a drop-in replacement that needs no extra tuning would matter well beyond the paper it arrived in.

What did Meta FAIR release?

According to the project's blog post, e-means is a "modern, robust k-means algorithm" developed at Meta FAIR and positioned as a replacement for Lloyd's algorithm, the standard iterative method for the problem. The post is authored by Swann Bessa with coauthors Pierre-Emmanuel Mazaré, Gergely Szilvasy, Hugo Touvron, David Picard, Matthijs Douze and Hervé Jégou.

The team has released the code inside the Faiss library, at faiss/contrib/e_means, alongside a paper posted on arXiv (2611.09501), an interactive browser playground and a video. The headline claim is a roughly 10× speedup in both epochs and wall-clock time compared with Lloyd's method, achieved while also reaching a lower loss — a combination the authors note is unusual, since speed and clustering quality normally trade against each other.

How does e-means get its speedup?

The k-means task is to place k centroids so that the mean squared distance from every data point to its nearest centroid is as small as possible. Lloyd's algorithm, the textbook approach, assigns every point to the closest centroid and then recomputes each centroid from scratch using the entire dataset, repeating this full-batch pass a fixed number of times — typically 20 to 50.

e-means instead works on mini-batches and updates each cluster's running sum and count with an exponential moving average, so older assignments fade at a fixed rate and each centroid tracks recent points rather than the whole history. The authors point out that this moving-average rule is normally used for shifting distributions, such as when training VQ-VAEs, and that applying it to a static dataset — combined with the rest of their machinery — is what makes it efficient here.

Several other pieces support the core update. The method sets its batch size and step size automatically from scaling laws, adds a cosine-scheduled decay on the step, revives "dead" clusters by splitting a large one, uses a new initialization and finalization stage, and ships GPU kernels that fuse the nearest-centroid assignment step. According to the post, e-means drops below Lloyd's loss at 25 epochs in just 1.2 to 3 epochs, which measured end to end works out to a 10–45× wall-clock reduction on GPU against the Flash-KMeans implementation and 8–15× on CPU against Faiss.

Why does e-means reach a lower loss?

Beyond raw speed, the authors argue e-means is less likely to get trapped in poor solutions. On small synthetic datasets, they ran hundreds of training starts and compared how often each method ended stuck. On two blobs of very different sizes with k = 8, Lloyd stayed stuck on 26% of starts while e-means stayed stuck on 3.5%. On five blobs arranged in a line with k = 5, Lloyd was stuck on 46% of starts and e-means on none.

Their explanation is that mini-batch updates are noisier, which helps the search explore the optimization landscape and climb out of bad configurations, whereas Lloyd's steadily decreasing loss makes it prone to settling into a local minimum and staying there. The team also revisited an earlier Meta FAIR finding that mini-batch k-means by gradient descent could beat Lloyd, but reports that gradient-descent updates were unstable at large learning rates; in their tests, gradient descent ended 1.6% above the moving average on the DEEP dataset and 0.4% above on SIFT at its best setting. Notably, Lloyd turns out to be a special case of e-means — set the batch to the full dataset and the step to 1, and one e-means iteration becomes exactly one Lloyd iteration.

Does e-means really need no hyperparameter tuning?

One of the stated goals is that practitioners should not have to set anything beyond what Lloyd's algorithm already requires. To do that, the authors fitted two scaling laws that derive the batch size and the initial step size from a problem's basic characteristics — the number of points, the number of clusters and the epoch budget. They report that these laws generalize to unseen datasets and scales, listing held-out sets including SIFT, SPACEV, the VIBE datasets, arXiv and AG-News, with low median regret against the best loss found by an exhaustive grid search. In their framing, Lloyd sits in a corner of the hyperparameter space — full batch, step of 1 — that their search found to be far from optimal.

How can you try e-means?

The most direct route is the code: e-means is available in Faiss at faiss/contrib/e_means, so anyone already using Faiss for similarity search or clustering can pull it in, and the full method is described in the arXiv paper. The project page also hosts a browser playground and a short video for readers who want to see the convergence behavior before installing anything.

For exploring the ideas rather than the code, Grafy offers a few genuine entry points. You can drop the arXiv paper into Reader and question it directly — asking, for instance, how the scaling laws were fit or how the dead-cluster revival works — with answers tied to the passages they come from. If you want to actually run the released implementation, Grafy Code is an AI coding studio that can install packages and execute code, which fits a task like setting up Faiss and calling the e_means module. And to build intuition on the algorithmic side, you could ask several models side by side in Grafy Chat to explain how exponential-moving-average updates differ from Lloyd's full-batch recompute.

Frequently asked questions

Is e-means a neural-network training method?

No — e-means is a clustering algorithm, not a neural-network training method. It replaces Lloyd's algorithm for the k-means problem: placing k centroids to minimize the mean squared distance from each point to its nearest centroid. The "epochs" reported in the results are passes over the dataset used to fit those centroids, not training steps for a neural network.

Did e-means arrive at lower loss than Lloyd, or only at equal loss?

According to the Meta FAIR team, e-means reaches a lower loss than Lloyd's algorithm, not merely an equal one, while also running faster. The post states that across a range of scales and datasets e-means drops below Lloyd's loss at 25 epochs in about 1.2 to 3 epochs, and that it achieves both better speed and better loss — a combination the authors describe as unusual for k-means.

Is e-means available in Faiss, and does it need tuning?

Yes — the code ships in Faiss at faiss/contrib/e_means. On tuning, the authors say e-means requires no additional hyperparameters beyond what Lloyd's algorithm needs, because two fitted scaling laws set the batch size and step size automatically from the number of points, the number of clusters and the epoch budget, and they report these laws generalize to unseen datasets.

---

Source: Hacker News — front page — E-means: 10x faster k-means at equal loss