Meta FAIR's e-means beats k-means in 1/10 the epochs with 10-45x GPU speedups
kastnerkyle · x · 2026-11-10
Meta FAIR published e-means, rebuilding mini-batch k-means around exponential moving average (EMA) updates, beating the classic Lloyd algorithm on both speed and quality.
Results
- Across embedding datasets, e-means matches Lloyd k-means' 25-epoch loss in 1.4–2.6 epochs, a 10–45x GPU wall-clock speedup over state-of-the-art implementations (Flash-KMeans, Faiss-GPU), often beating k-means++ too
- Example: clusters DINO10B, a new 10-billion DINO embedding dataset, into 16 million clusters in just 2.5 epochs
Method & findings
- Repurposes the EMA update rule (used in VQ-VAEs for dynamic distributions) for static clustering, with cosine annealing
- Establishes scaling laws letting decay rate and batch size be set formulaically from problem dimensions (n points, k clusters, T epochs) — no hyperparameter sweeps
- Counterintuitive: k-means++'s sequential initialization is so slow on GPUs that random initialization is overwhelmingly faster with better final results
- SGD centroid updates collapse at very large batch sizes; EMA naturally constrains centroids to the convex hull, unlocking big-batch GPU utilization
- Two near-zero-cost finalization tricks: "last-epoch-mean" lowers training MSE, "slow-EMA" acts as a strong regularizer for test MSE
Code and website are released; DINO10B also serves as a new extreme-scale retrieval/clustering benchmark.
Related event: Meta FAIR's e-means Beats k-means with Up to 45x GPU Speedup(3 posts)→
More from Research
- Four Free Math Books for ML: Linear Algebra, Probability, Optimization, Information Theory — cneuralnetwork · 2026-11-10
- 4 free math books that actually matter for ML: linear algebra to information theory — cneuralnetwork · 2026-11-10
- Meta FAIR's e-means beats k-means in 1/10 epochs with 10-45x GPU speedups — burny_tech · 2026-11-10
- NeurIPS workshop paper: gradient-based data attribution can't reliably filter subliminal learning — ponguru · 2026-11-10
- Yang-Mills Working Group to Release OpenAI's Full Lean Code and Validation Tomorrow — burny_tech · 2026-11-10
- Interpretability researchers reminded: explanation matters, not just predictive power — burny_tech · 2026-11-10