TLDR
Meta's FAIR team introduced e-means, a K-Means variant that replaces the centroid update rule with exponential moving averages (EMA), reducing required epochs to ~1/10th and achieving up to 45.5x speedup on billion-scale vectors while matching or beating Lloyd's algorithm in error. The method automates hyperparameter selection via power-law formulas fitted on one dataset but transferable to others, and includes practical engineering like fused kernels and dead-cluster revival.
For you
PRO members can sign in and request more information — or their own version of this digest, tuned to what they care about.
Sign in to unlockSurprising Insights
The classic Lloyd algorithm's monotonic error decrease actually traps it in bad local optima, while the noise from mini-batch updates lets e-means correct course.
Power-law hyperparameter formulas fitted on a single dataset (DEEP) transfer to diverse image and text datasets with near-optimal performance, despite unknown intrinsic dimensionality.
e-means achieves lower error than Lloyd even with random initialization and no k-means++, because k-means++ is serial and too costly at scale.
Key takeaways
e-means keeps the classic K-Means objective but changes the centroid update to EMA on per-cluster counts and sums, letting centroids adapt quickly early on and stabilize later without accumulating stale statistics.
The EMA decay rate is scheduled via cosine annealing, and a final recomputation of centroids from the last epoch's assignments yields zero-cost error reduction; an optional slower EMA can improve generalization to new data.
Dead clusters are revived every five batches by splitting the largest cluster, which ablation shows is critical: without it, 26% of clusters get fewer than 10 points; with it, only 0.3%.
Stochastic mini-batch updates help e-means escape poor local optima: on imbalanced two-cluster data, Lloyd gets stuck 26% of the time vs. 3.5% for e-means; on five linear clusters, 46% vs. 0%.
Hyperparameters (batch size, learning rate) are predicted by power-law formulas fitted on 75k runs on the DEEP dataset, transferring to SIFT, SPACEV, and text vectors with median error increase of only 0.19% over per-dataset tuning.
On 10 billion DINO vectors (16.77M clusters), e-means reaches Flash-KMeans' 25-epoch error in 2.5 epochs (779 GPU hours on 32 machines) vs. 6,784 GPU hours (64 machines) for Lloyd, with lower final error.
Engineering optimizations—block-wise centroid processing, fused distance/assignment kernels, low-precision (BF16/FP8/INT8) assignment, and IVF approximation for huge cluster counts—multiply the algorithmic speedup.
Notable quotes
“K-Means 大概是机器学习里最不起眼的算法了”
▸ Notable quotes · 0:03“目标函数一个字没动,只是重写了聚类中心的更新方式,就将达到同等聚类质量需要的训练轮次压到了原来的十分之一左右”
▸ Notable quotes · 0:24“在 10 亿条向量的实验里,实际耗时快了 45.5 倍”
▸ Notable quotes · 0:34“它把 K-Means 的更新当成了一种硬分配的 EM,只是统计量带了衰减”
▸ Notable quotes · 3:30“调参也被省掉了”
▸ Notable quotes · 7:04“少一轮是算法层面的事,而少一次显存读写是系统层面的事,两个叠加才有了最后那个数字”
▸ Notable quotes · 11:12Chapters
0:00 — Introduction and Motivation: Host introduces K-Means as an old but ubiquitous algorithm; Meta FAIR's e-means rewrites the centroid update to achieve 10x fewer epochs and 45.5x speedup on 1B vectors.
1:01 — Classic Lloyd Algorithm and Its Bottleneck: Explains Lloyd's two-step loop (assign, recompute mean) and its linear cost per epoch; Faiss defaults to 25 epochs, costing thousands of GPU hours at 10B scale.
2:03 — Mini-Batch K-Means and Its Unsolved Problems: Reviews mini-batch history (MacQueen, Sculley) and its issues: accumulated stale statistics, higher final error, and manual tuning of batch size and learning rate per dataset.
3:00 — e-means: EMA-Based Centroid Updates: Describes e-means' EMA on per-cluster counts and sums, decay scheduling, connection to hard-assignment EM, and advantages over SGD (centroids stay in convex hull).
4:26 — Escaping Local Optima and Reviving Dead Clusters: Shows e-means' stochasticity escapes bad local optima (Lloyd 26% vs 3.5% failure on imbalanced clusters) and details the dead-cluster revival mechanism that splits large clusters.
6:18 — Training Stabilization and Final Polish: Covers random init with tiny weight, cosine annealing, zero-cost final centroid recomputation, and optional slower EMA for generalization.
7:04 — Automated Hyperparameter Selection via Power Laws: Authors fit power laws for batch size and learning rate from 75k experiments on DEEP; formulas transfer to other datasets with median 0.19% error increase.
8:52 — Large-Scale Experiments and Retrieval Impact: Reports 9.5–45.5x speedup on 1M–10B vectors, lower error than Lloyd and Flash-KMeans; on 10B DINO vectors, 2.5 epochs vs 25; IVF approximation further cuts cost; retrieval recall improves at same training time.
Speakers
大飞 — Host