e-means: outperforming k-means (in one-tenth the epochs)
Organizations: FAIR at Meta · École Nationale des Ponts et Chaussées
Abstract
Lloyd's k-means algorithm is a long-running standard for clustering, with applications in data analysis, retrieval, quantization and data curation. In this paper, we introduce an exponential moving average optimization procedure for k-means with mini-batch updates, powered by modern deep learning machinery and new insights. We also establish scaling laws on how decay rate and batch size impact final performance. This gives us a formulaic rule to fix them for multiple problem sizes and embedding datasets, without the need for any hyperparameter sweep. The resulting clustering algorithm, coined e-means, is much faster than Lloyd k-means and converges to lower losses, frequently even beating k-means++. On a wide array of embeddings datasets, it beats the loss of Lloyd k-means at 25 epochs in 1.4 to 2.6 epochs, which translates to 10-45x GPU wall-clock speedups compared to state-of-the-art k-means implementations. As an example, e-means partitions DINO10B, a dataset of 10 billion DINO embeddings, into 16 million clusters in only 2.5 epochs, reaching a loss below Lloyd's at 25 epochs.
Figures & tables
| ablation | train MSE | test MSE |
|---|---|---|
| our recipe | ||
| no cosine schedule | ||
| no revival | ||
| revival by resampling | ||
| no finalization | ||
| slow EMA |
| c | k | B | n | T | OOD (%) | LOSO (%) | ||
|---|---|---|---|---|---|---|---|---|
| step , Equation 6 | ||||||||
| batch , knee at 0.2% | — | |||||||
| batch , knee / 8 | — | n/a |
| M | B | B | |
|---|---|---|---|
| exact assignment | 0.028 | 4.56 | 779 |
| IVF assignment | 0.030 | 1.05 | 22.8 |
| (a) Epochs to Flash@25 MSE | (b) Wall-clock speedup vs Flash-KMeans | ||||||||
| DEEP* | DINO10B | SPACEV | SimSearchNet++ | DEEP* | DINO10B | SPACEV | SimSearchNet++ | ||
| 1M | 16,384 | 2.0 | 2.0 | 2.4 | 1.4 | 12.8 | 12.7 | 9.5 | 12.9 |
| 10M | 65,536 | 2.0 | 1.4 | 2.0 | 1.6 | 27.8 | 23.3 | 19.2 | 23.8 |
| 100M | 262,144 | 2.0 | 1.6 | 1.4 | 2.6 | 27.0 | 31.3 | 35.9 | 19.9 |
| 1B | 1,048,576 | 1.6 | 1.6 | 1.4 | 2.0 | 36.0 | 45.5 | 37.9 | 21.2 |
| e-means | Flash-KMeans | Flash-KMeans | |||||||
|---|---|---|---|---|---|---|---|---|---|
| random init | random init | greedy k-means++ init | |||||||
| dataset | scale | 3 ep. | 5 ep. | 10 it. | 25 it. | 10 it. | 25 it. | ||
| DEEP* | 1M | 16,384 | |||||||
| SIFT | 1M | 16,384 | |||||||
| SPACEV | 1M | 16,384 | |||||||
| SimSearchNet++ | 1M | 16,384 | |||||||
Appendix figures & tables40 assets
Supplementary material from the paper’s appendix.
Appendix
| Dataset | Content | used | Eval set | |
| BigANN 2021 challenge ( Simhadri et al., 2022 ) | ||||
| SIFT | Image descriptors ( Jégou et al., 2011 ) | 128 | 1M–1B | provided queries |
| DEEP | Image embeddings ( Babenko and Lempitsky, 2016 ) | 96 | 1M–1B | provided queries |
| SPACEV | Text embeddings ( Microsoft, 2021 ) | 100 | 1M–1B | index holdout |
| SimSearchNet++ | Image embeddings ( Douze et al., 2021 ) | 256 | 1M–1B | provided queries |
| VIBE benchmarks ( Jääsaari et al., 2025 ) | ||||
| median regret, held out by | ||||
| model | free parameters | dataset | ||
| the full law | 5 | 0.067% | 0.068% | 0.065% |
| without | 4 | 0.232% | 0.174% | 0.168% |
| without | 4 | 0.571% | 0.560% | 0.530% |
| without | 4 | 0.222% | 0.134% | 0.132% |
| without | 4 | 0.074% | 0.076% | 0.083% |
| median regret, held out by | ||||
|---|---|---|---|---|
| model | free parameters | dataset | ||
| log inputs, log target (ours) | 5 | 0.067% | 0.068% | 0.065% |
| log inputs, logit target | 5 | 0.098% | 0.123% | 0.103% |
| log inputs, raw target | 5 | 0.158% | 0.161% | 0.161% |
| raw inputs, log target | 5 | 0.799% | 0.444% | 0.414% |
| raw inputs, raw target (fully linear) | 5 | 0.787% | 0.473% | 0.440% |
| Baseline | Implementation | Swept over |
|---|---|---|
| Flash-KMeans | flash_kmeans 0.3.1, one public-API call, forced to the full count (max_iters=T, tol=-1) | Not swept — one setting |
| cuML | RAPIDS cuML 25.02.01, KMeans(n_init=1, max_iter=T, tol=1e-30) | Not swept — one setting |
| Faiss-GPU | Faiss 1.12.0 | Not swept — one setting |
| Faiss-CPU | Faiss 1.12.0 | Not swept — one setting |
| Sculley | scikit-learn 1.7.2 MiniBatchKMeans, with its early stopping switched off (max_no_improvement=None, tol=0) so every run completes its full budget | Batch size: 256, 512, 1024, 2048, 4096, 65536, 262144, 524288. Dead-cluster threshold (reassignment_ratio): 0, 0.001, 0.01, 0.05, 0.1, 0.5, where 0 is the published algorithm, which has no dead-cluster revival |
| SuperKMeans | Authors’ library ( Kuffo et al., 2026 ) . | Not swept — one setting |
| test | train | |||||
|---|---|---|---|---|---|---|
| Dataset | ||||||
| SIFT | ||||||
| DEEP* | ||||||
| SPACEV | ||||||
| SimSearchNet++ | ||||||
| DINO10B | ||||||
| GooAQ | CodeSearchNet | arXiv | ImageNet-CLIP | GloVe-200 | AG-News | Landmark-DINO | Landmark-Nomic | CC-News | SimpleWiki | CelebA | |
| (millions) | 1.48 | 1.37 | 1.34 | 1.28 | 1.19 | 0.77 | 0.76 | 0.76 | 0.50 | 0.26 | 0.20 |
| 768 | 768 | 768 | 512 | 200 | 1024 | 768 | 768 | 768 | 3072 | 2048 | |
| 16k | 16k | 16k | 16k | 16k | 16k | 16k | 16k | 8k | 8k | 8k | |
| GPU: seconds to Lloyd@25 — baseline Flash-KMeans, fp16 against our bf16, one H100 | |||||||||||
| Flash-KMeans (s) | 1.77 | 1.41 | 1.12 | 0.83 | 0.49 | 1.18 | 0.81 | 1.09 | 0.54 | 1.37 | 0.50 |
| e-means (s) | 0.16 | 0.13 | 0.14 | 0.07 | 0.05 | 0.10 | 0.06 | 0.08 | 0.04 | 0.06 | 0.03 |
| train MSE | test MSE | init (s) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| dataset | scale | rand. | k-m++ | rand. | k-m++ | rand. | k-m++ | train (s) | |||
| DEEP* | 5 | ||||||||||
| DEEP* | 10 | ||||||||||
| SIFT | 5 | ||||||||||
| SIFT | 10 | ||||||||||
| SPACEV | 5 | ||||||||||
| train MSE | test MSE | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| dataset | scale | cosine | best fixed | cosine | best fixed | ||||
| DEEP* | 1M | 16,384 | |||||||
| DINO10B | 1M | 16,384 | |||||||
| SPACEV | 1M | 16,384 | |||||||
| SimSearchNet++ | 1M | 16,384 | |||||||
| DEEP* | 10M | 65,536 | |||||||
| dataset | policy | dead clusters | as % | imbalance | test MSE | |
|---|---|---|---|---|---|---|
| DEEP* | 1M | on (e-means) | 47 | 0.3% | 1.194 | 0.38762 |
| resample from batch | 2343 | 14.3% | 1.423 | 0.39124 | ||
| off | 4313 | 26.3% | 1.647 | 0.39448 | ||
| SIFT | 1M | on (e-means) | 10 | 0.1% | 1.186 | 0.19623 |
| resample from batch | 750 | 4.6% | 1.233 | 0.19684 | ||
| off | 2080 | 12.7% | 1.404 | 0.19797 |
| Train MSE | Test MSE | ||||||
|---|---|---|---|---|---|---|---|
| No finalizer | Last-epoch mean | Slow EMA | No finalizer | Last-epoch mean | Slow EMA | ||
| 32,768 | 305.2 | 0.348557 [-1pt] (0.000%) | 0.348518 [-1pt] (-0.011%) | 0.348729 [-1pt] (+0.049%) | 0.356406 [-1pt] (0.000%) | 0.356416 [-1pt] (+0.003%) | 0.356343 [-1pt] (-0.018%) |
| 65,536 | 152.6 | 0.329474 [-1pt] (0.000%) | 0.329371 [-1pt] (-0.031%) | 0.329863 [-1pt] (+0.118%) | 0.341573 [-1pt] (0.000%) | 0.341551 [-1pt] (-0.007%) | 0.341430 [-1pt] (-0.042%) |
| 131,072 | 76.3 | 0.309877 [-1pt] (0.000%) | 0.309468 [-1pt] (-0.132%) | 0.312040 [-1pt] (+0.698%) | 0.328351 [-1pt] (0.000%) | 0.328396 [-1pt] (+0.014%) | 0.328080 [-1pt] (-0.082%) |
| Dataset | BF16 | FP8 | INT8 | BF16 | FP8 | INT8 | Flash@25 | |
|---|---|---|---|---|---|---|---|---|
| SIFT | ||||||||
| SIFT | ||||||||
| DEEP* | ||||||||
| DEEP* | ||||||||
| SPACEV | ||||||||
| Dataset | BF16 | FP8 | INT8 | BF16 | FP8 | INT8 | |
|---|---|---|---|---|---|---|---|
| SIFT | |||||||
| SIFT | |||||||
| DEEP* | |||||||
| DEEP* | |||||||
| SPACEV | |||||||
| different assignments | test MSE | ||||
|---|---|---|---|---|---|
| Dataset | rescaled | direct | rescaled | direct | |
| SPACEV ( ) | |||||
| SPACEV ( ) | |||||
| SPACEV ( ) | |||||
| SPACEV ( ) | |||||
| SimSearchNet++ ( ) | |||||
| Ablation | Training | MSE ( ) | |
|---|---|---|---|
| time (s) | Train | Test | |
| Baseline | 10.1 | 17.02 | 18.72 |
| Retrain | 558.1 | 16.94 | 18.72 |
| Period 4 | 8.216 | 17.02 | 18.71 |
| Period 16 | 7.926 | 17.05 | 18.72 |
| Period 64 | 7.780 | 17.32 | 18.78 |
| actually used | rows per centroid | ||
|---|---|---|---|
| 100K | 200 | 256 | 391 |
| 1M | 2,000 | 2,048 | 488 |
| 10M | 20,000 | 16,384 | 610 |
| 100M | 200,000 | 262,144 | 382 |
| 1B | 2,000,000 | 2,097,152 | 477 |
| 10B | 20,000,000 | 16,777,216 | 596 |
| method | assignment | epochs | test MSE | vs Lloyd | train MSE | GPU | nb |
| (test) | hours | machines | |||||
| Lloyd | exact | 25 | 12.987 | – | 12.468 | 6,784 | 64 |
| e-means | exact | 2 | 12.994 | 12.513 | 885 | 32 | |
| e-means | exact | 2.5 | 12.985 | 12.489 | 779 | 32 | |
| e-means | exact | 3 | 12.965 | 12.464 | 961 | 32 | |
| e-means | exact | 3.5 | 12.980 | 12.478 | 794 | 32 |
| method | assignment | epochs | test MSE | vs Lloyd | train MSE | GPU | nb |
|---|---|---|---|---|---|---|---|
| (test) | hours | machines | |||||
| Lloyd | brute-force | 25 | 14.712 | — | 13.984 | 43.54 | 16 |
| e-means | brute-force | 2.8 | 14.704 | -0.053% | 13.927 | 4.56 | 1 |
| e-means | IVF1024, =4 | 2 | 14.722 | +0.070% | 14.089 | 1.2 | 1/2 |
| e-means | IVF1024, =4 | 3 | 14.712 | -0.000% | 14.045 | 1.05 | 1/2 |
| e-means | IVF1024, =4 | 4 | 14.702 | -0.063% | 14.026 | 2.0 | 1/2 |
Clustering
Clustering groups data points by shared structure, developing methods to discover, validate, and interpret groups across diverse data and constraints.
See all 370 papers