Glonce

e-means, a Meta FAIR k-means method, claims ~10x speedup

researchThe Glonce editorsHacker News🔥77Glonce rating77Impact55Novelty65Relevance85Surprise60Players70Credibility75

A first-person post on the e-means project page announces the open-sourcing of e-means, a k-means algorithm developed at Meta FAIR. It is pitched as a replacement for Lloyd's algorithm, the classic k-means procedure, and is said to deliver a ~10x speedup in both epochs and wall-clock time while reaching a lower loss. The post does not name its author.

The headline numbers: across a large range of scales and datasets, e-means reaches a test loss below what Lloyd reaches at 25 epochs in just 1.2 to 3 epochs. Measured end to end, that is a 10 to 45x wall-clock reduction on GPU against Flash-KMeans, which the post calls the state-of-the-art Lloyd implementation, and 8 to 15x on CPU against Faiss. The post stresses that speed and quality usually trade against each other in k-means, while e-means gets both a better speed and a better loss.

The core change is the update rule. Lloyd's algorithm assigns every point to its nearest centroid and recomputes the statistics from scratch over the full dataset, repeated a fixed number of times (typically 20 to 50 iterations). MacQueen's update accumulates statistics forever, so a centroid is the mean of every point ever assigned to it, including points assigned under earlier, possibly poor, centroid positions. Staleness-Reduction Mini-Batch K-Means, a hybrid of k-means and MacQueen, obtained important speedups but only on very low numbers of clusters. e-means instead works on mini-batches and replaces the running sum with an exponential moving average, so older assignments are forgotten at rate alpha and the centroid tracks recent assignments. Such updates are usually used for moving distributions, for example in training VQ-VAEs; the authors say they are also extremely efficient on static datasets when combined with e-means' other components and properly tuned hyperparameters. In a toy illustration with 100,000 datapoints in 200 clusters, Lloyd makes 1 update per epoch against 97 for e-means.

The project grew out of earlier Meta FAIR work by Hugo Touvron and Hervé Jégou, who had found that mini-batch k-means by gradient descent could beat Lloyd's algorithm. The post's author reproduced those results but found gradient-descent centroid updates unstable at large learning rates, unlike moving-average updates. The author only suspects the reason: moving-average updates keep a centroid inside the convex hull of its assigned points, while gradient descent may overshoot it.

Lloyd turns out to be a special case. Set the batch to the full dataset and alpha to 1, and one e-means iteration is exactly one Lloyd iteration. The authors' hyperparameter search found that this extreme setting is highly suboptimal, which they say explains why e-means largely outperforms Lloyd. The post shows loss over every batch size and step size, with Lloyd sitting in a corner well outside the lowest-loss region.

To remove the tuning burden, the authors derived two fitted scaling laws that set batch size B and step size alpha0 from the problem's characteristics (n, k, T). They report strong generalization on unseen datasets and problem scales, with held-out tests on SIFT, SPACEV, and the arXiv and AG-News datasets from VIBE. There are two laws: a default law, and a quality law that trades throughput for better clustering quality. The result, they say, is that practitioners need no additional hyperparameter compared with Lloyd.

On why e-means reaches better losses at convergence, the authors ran trainings on toy datasets over 200 seeds and found e-means much less likely than Lloyd to land in pathological configurations. Their explanation is that noisy mini-batch updates are more likely to explore the loss landscape and escape local minima, whereas Lloyd's always-decreasing loss tends to exploit a local minimum and never leave it.

The post also covers dead clusters, centroids that end up with no assigned points during mini-batch optimization, which shrinks the effective codebook. A common fix, used in EnCodec, replaces dead centroids with random samples from the incoming batch. e-means instead splits large clusters: it samples an active cluster with probability proportional to its size and splits it in two, an approach adapted from Faiss k-means that the authors found significantly more effective. Their ablation used 1 million vectors, k = 16,384, 5 epochs, averaged over 5 seeds; a cluster counted as dead if fewer than ten vectors were assigned to it at the end, a thousandth of an average cluster. Beyond the update rule, e-means also improves initialization, adds a cosine-scheduled decay rate, and adds a finalization stage that lowers training loss for a negligible runtime cost. It is described as highly parallelizable, with specialized kernels that turn the algorithmic gain into wall-clock speedups.

The authors say they validated e-means on 24 embedding and synthetic datasets and configurations, detailed in the paper (arXiv:2611.09501). For the project's video they ran 234 configurations against k-means across 16 datasets of 100k to 100M points, with an interactive results map. The code lives at faiss/contrib/e_means.

Key facts

  • e-means, developed at Meta FAIR, replaces Lloyd's k-means with mini-batch exponential-moving-average updates; the post claims about a 10x speedup in both epochs and wall-clock time with lower loss.
  • It reaches a test loss below Lloyd's at 25 epochs in 1.2 to 3 epochs, with end-to-end wall-clock reductions of 10 to 45x on GPU (versus Flash-KMeans) and 8 to 15x on CPU (versus Faiss).
  • Batch size and step size are set automatically by two fitted scaling laws (default and quality), so no extra hyperparameters are needed compared with Lloyd.
  • Dead clusters are revived by splitting large clusters, sampled in proportion to size, rather than by reinitializing from random batch samples.
  • Validation covers 24 datasets and configurations in the paper (arXiv:2611.09501); the code is at faiss/contrib/e_means.

Why it matters

k-means is a workhorse for clustering embeddings and building codebooks, and Lloyd's algorithm is still the default. The post argues that the usual trade of speed against quality is not forced: e-means reportedly gets both. It also shows that Lloyd's algorithm is one extreme corner of e-means (full batch, alpha equal to 1), and that the corner is far from the best setting. If the numbers hold up, the same clustering job would need roughly a tenth of the passes over the data.

Who it affects

Anyone who runs k-means at scale, especially on embedding datasets with many clusters. The post points to large codebooks, which it calls increasingly common today, as the case where dead clusters hurt most. Users of Faiss are the obvious audience, since the code sits under faiss/contrib and the CPU comparison is against Faiss.

How to use it

The code is at faiss/contrib/e_means, and the post asks users to cite the paper (arXiv:2611.09501). According to the authors, you set no more hyperparameters than for Lloyd's algorithm: two scaling laws pick batch size B and step size alpha0 from the problem's characteristics (n, k, T). Choose the default law, or the quality law if you will give up some throughput for better clustering quality.

How solid is it

The speedup and loss figures are the authors' own measurements, and no independent replication is mentioned. The breadth of testing is stated: 24 embedding and synthetic datasets and configurations in the paper, plus 234 configurations over 16 datasets from 100k to 100M points for the results map. The scaling laws were checked on held-out datasets (SIFT, SPACEV, and the VIBE arXiv and AG-News sets). The source does not say whether the paper has been peer reviewed or where it was published.

Risks and caveats

The ~10x figure is a headline; the detailed ranges are 1.2 to 3 epochs against 25 for Lloyd, 10 to 45x on GPU and 8 to 15x on CPU, and the source does not say the 10x holds on every dataset. It does not give the GPU or CPU models used, exact loss values or percentage loss gains, or a license for the code. The explanation for why moving-average updates beat gradient descent is only a suspicion of the author, and the local-minima account for the lower loss is the authors' own interpretation of toy-dataset runs.

“Speed and quality usually trade against each other in k-means, while e-means achieves both better speed and loss.”

— e-means project page