Small Is Not Dead: Distance-Aware Cluster Revival for e-means
Organizations: Robotics Institute, Carnegie Mellon University
Abstract
e-means (Bessa et al., 2026) is a recent mini-batch k-means algorithm, now part of the FAISS library, that reaches the error of Lloyd's algorithm about an order of magnitude faster on large embedding datasets. Every five mini-batches, it removes every cluster whose running point count falls below a tenth of the average and reuses its centre to split a large cluster. In the authors' ablation, removing this mechanism, called dead-cluster revival, raises the error more than removing any other component added to the moving-average update. The rule, however, considers only cluster size: it cannot distinguish a cluster that is small because it is redundant from one that covers a rare, isolated group of points, and on data with such groups it repeatedly removes centres whose removal is costly. We add a second condition, based on the distance between centres: a small cluster is removed only if its centre is close to another centre, relative to a running estimate of the mean squared error. When a centre equals the mean of its points, this squared distance is an upper bound on the average increase in squared error, per point of the cluster, caused by removing the centre. The condition costs one nearest-centre search for the small clusters every five mini-batches and adds no measurable running time. On the e-means paper's embedding benchmarks, it never prevents a removal, so the results are identical to those of FAISS. On datasets with small isolated groups not used during development, it reduces the test error after two epochs by roughly 10% to 80% relative to count-based revival, and it preserves the advantage of k-means++ initialization; on the other evaluation datasets, it stays within about 1% of the better of revival enabled and disabled. We also report two failure modes that the analysis predicts. This is a CPU proof of concept; GPU implementations are left to future work.
Figures & tables
| Test MSE / Lloyd@25 | ||||||
|---|---|---|---|---|---|---|
| Dataset | Epochs | Identical runs | count | off | distance | Splits per run |
| DEEP 1M | 1 | 10/10 | 1.0115 | 1.0420 | 1.0115 | 9010 |
| DEEP 1M | 2 | 10/10 | 0.9989 | 1.0315 | 0.9989 | 9726 |
| DEEP 1M | 3 | 10/10 | 0.9968 | 1.0180 | 0.9968 | 6892 |
| DEEP 1M | 5 | 10/10 | 0.9938 | 1.0161 | 0.9938 | 7454 |
| SIFT 1M | 1 | 10/10 | 1.0091 | 1.0330 | 1.0091 | 6902 |
| Median test MSE / median test MSE of Lloyd@25 | distance vs. count | distance vs. off | ||||||||||
| Dataset | Seeds | count | off | distance | estimate | W/T/L | W/T/L | |||||
| Held-out datasets | ||||||||||||
| KDD Cup 99 | 256 | 30 | 1.121 | 0.550 | 0.526 | 0.524 | 51.8% | 30/0/0 | 3.1% | 22/0/8 | 1.000 | |
| KDD Cup 99 | 1024 | 30 | 2.837 | 0.629 | 0.561 | 0.562 | 81.2% | 30/0/0 | 8.7% | 27/0/3 | 0.007 | |
| KDD Cup 99 | 4096 | 30 | 1.174 | 0.982 | 0.916 | 0.960 | 23.6% | 26/0/4 | 5.6% | 23/0/7 | 0.108 | |
| Census 1990 | 256 | 30 | 0.991 | 0.992 | 0.991 | 0.991 | +0.0% | 3/19/8 | 1.000 | 0.0% | 16/2/12 | 1.000 |
| Dataset | Library ( count ) | distance | estimate |
|---|---|---|---|
| DEEP 1M, | 32.9 | 32.9 | 90.3 |
| KDD Cup 99, | 11.9 | 12.0 | 27.6 |
Appendix figures & tables15 assets
Supplementary material from the paper’s appendix.
Appendix
| Median test MSE / median test MSE of Lloyd@25 | distance vs. count | distance vs. off | ||||||||||
| Dataset | Seeds | count | off | distance | estimate | W/T/L | W/T/L | |||||
| Held-out datasets | ||||||||||||
| KDD Cup 99 | 256 | 10 | 1.194 | 0.812 | 0.840 | 0.853 | 30.4% | 10/0/0 | 0.504 | +3.4% | 3/0/7 | 1.000 |
| KDD Cup 99 | 1024 | 10 | 3.341 | 1.150 | 0.993 | 1.000 | 70.8% | 10/0/0 | 0.504 | 3.7% | 6/0/4 | 1.000 |
| KDD Cup 99 | 4096 | 10 | 2.061 | 1.434 | 1.338 | 1.501 | 27.9% | 10/0/0 | 0.504 | 2.0% | 6/0/4 | 1.000 |
| Census 1990 | 256 | 10 | 0.997 | 0.996 | 0.998 | 0.997 | +0.0% | 2/7/1 | 1.000 | 0.1% | 7/0/3 | 1.000 |
| Median test MSE / median test MSE of Lloyd@25 | distance vs. count | distance vs. off | ||||||||||
| Dataset | Seeds | count | off | distance | estimate | W/T/L | W/T/L | |||||
| Held-out datasets | ||||||||||||
| KDD Cup 99 | 256 | 10 | 1.003 | 0.523 | 0.497 | 0.528 | 51.6% | 10/0/0 | 0.504 | 7.7% | 7/0/3 | 1.000 |
| KDD Cup 99 | 1024 | 10 | 2.489 | 0.552 | 0.419 | 0.420 | 82.2% | 10/0/0 | 0.504 | 20.3% | 9/0/1 | 1.000 |
| KDD Cup 99 | 4096 | 10 | 1.084 | 1.007 | 0.908 | 0.922 | 17.2% | 9/0/1 | 1.000 | 8.0% | 9/0/1 | 1.000 |
| Census 1990 | 256 | 10 | 0.993 | 0.997 | 0.992 | 0.993 | +0.0% | 1/9/0 | 1.000 | 0.4% | 9/0/1 | 0.508 |
| Median test MSE / median test MSE of Lloyd@25 | distance vs. count | distance vs. off | ||||||||||
| Dataset | Seeds | count | off | distance | estimate | W/T/L | W/T/L | |||||
| Held-out datasets | ||||||||||||
| KDD Cup 99 | 256 | 10 | 1.027 | 0.616 | 0.583 | 0.579 | 41.2% | 10/0/0 | 0.504 | 2.9% | 7/0/3 | 1.000 |
| KDD Cup 99 | 1024 | 10 | 2.068 | 0.580 | 0.419 | 0.421 | 78.5% | 10/0/0 | 0.504 | 17.0% | 10/0/0 | 0.504 |
| KDD Cup 99 | 4096 | 10 | 1.092 | 0.779 | 0.690 | 0.713 | 36.1% | 10/0/0 | 0.504 | 9.6% | 9/0/1 | 0.508 |
| Census 1990 | 256 | 10 | 0.992 | 0.994 | 0.991 | 0.992 | +0.0% | 1/9/0 | 1.000 | 0.3% | 9/1/0 | 0.504 |
| Median test MSE / median test MSE of Lloyd@25 | distance vs. count | distance vs. off | ||||||||||
| Dataset | Seeds | count | off | distance | estimate | W/T/L | W/T/L | |||||
| Held-out datasets | ||||||||||||
| KDD Cup 99 | 256 | 10 | 0.938 | 0.578 | 0.521 | 0.547 | 41.9% | 10/0/0 | 0.504 | 4.3% | 7/0/3 | 1.000 |
| KDD Cup 99 | 1024 | 10 | 1.428 | 0.585 | 0.435 | 0.443 | 59.6% | 10/0/0 | 0.504 | 15.4% | 10/0/0 | 0.504 |
| KDD Cup 99 | 4096 | 10 | 1.145 | 0.755 | 0.670 | 0.681 | 38.9% | 10/0/0 | 0.504 | 9.9% | 10/0/0 | 0.504 |
| Census 1990 | 256 | 10 | 0.994 | 0.996 | 0.994 | 0.994 | +0.0% | 0/10/0 | 1.000 | 0.2% | 8/1/1 | 1.000 |
| Dataset | count | off | distance | estimate | |
|---|---|---|---|---|---|
| KDD Cup 99 | 256 | 10 | 1 | 1 | 1 |
| KDD Cup 99 | 1024 | 2 | 1 | 2 | |
| KDD Cup 99 | 4096 | 2 | 2 | 2 | |
| Census 1990 | 256 | 1 | 1 | 1 | 1 |
| Census 1990 | 1024 | 2 | 1 | 1 | 2 |
| Census 1990 | 4096 | 2 | 2 | 2 | 2 |
| Median test MSE / median test MSE of Lloyd@25 | distance vs. count | distance vs. off | ||||||||||
| Dataset | Seeds | count | off | distance | estimate | W/T/L | W/T/L | |||||
| Held-out datasets | ||||||||||||
| KDD Cup 99 | 256 | 10 | 14.582 | 1.026 | 1.027 | 1.027 | 93.0% | 10/0/0 | 0.504 | +0.0% | 0/9/1 | 1.000 |
| KDD Cup 99 | 1024 | 10 | 30.804 | 1.007 | 1.007 | 1.005 | 96.7% | 10/0/0 | 0.504 | +0.0% | 3/2/5 | 1.000 |
| KDD Cup 99 | 4096 | 10 | 9.445 | 1.013 | 1.013 | 1.020 | 88.5% | 10/0/0 | 0.504 | +0.0% | 3/1/6 | 1.000 |
| Census 1990 | 256 | 10 | 1.001 | 1.001 | 1.001 | 1.001 | +0.0% | 3/5/2 | 1.000 | +0.1% | 3/0/7 | 1.000 |
| Median test MSE / median test MSE of Lloyd@25 | distance vs. count | distance vs. off | ||||||||||
| Dataset | Seeds | count | off | distance | estimate | W/T/L | W/T/L | |||||
| Held-out datasets | ||||||||||||
| KDD Cup 99 | 256 | 10 | 13.073 | 1.016 | 1.016 | 1.014 | 92.2% | 10/0/0 | 0.504 | +0.0% | 1/9/0 | 1.000 |
| KDD Cup 99 | 1024 | 10 | 25.672 | 1.006 | 1.006 | 1.005 | 96.1% | 10/0/0 | 0.504 | 0.0% | 6/1/3 | 1.000 |
| KDD Cup 99 | 4096 | 10 | 4.466 | 1.008 | 1.007 | 1.007 | 77.6% | 10/0/0 | 0.504 | 0.0% | 6/1/3 | 1.000 |
| Census 1990 | 256 | 10 | 0.996 | 0.996 | 0.996 | 0.996 | +0.0% | 4/5/1 | 1.000 | +0.0% | 3/1/6 | 1.000 |
| Median test MSE / median test MSE of Lloyd@25 | distance vs. count | distance vs. off | ||||||||||
| Dataset | Seeds | count | off | distance | estimate | W/T/L | W/T/L | |||||
| Held-out datasets | ||||||||||||
| KDD Cup 99 | 256 | 10 | 12.796 | 1.009 | 1.009 | 1.013 | 92.1% | 10/0/0 | 0.504 | +0.0% | 1/9/0 | 1.000 |
| KDD Cup 99 | 1024 | 10 | 23.796 | 1.004 | 1.003 | 1.002 | 95.8% | 10/0/0 | 0.504 | 0.1% | 8/0/2 | 1.000 |
| KDD Cup 99 | 4096 | 10 | 3.884 | 1.006 | 1.006 | 1.009 | 74.1% | 10/0/0 | 0.504 | 0.0% | 6/0/4 | 1.000 |
| Census 1990 | 256 | 10 | 0.998 | 0.998 | 0.998 | 0.998 | +0.0% | 0/9/1 | 1.000 | +0.0% | 4/3/3 | 1.000 |
| Median test MSE / median test MSE of Lloyd@25 | distance vs. count | distance vs. off | ||||||||||
| Dataset | Seeds | count | off | distance | estimate | W/T/L | W/T/L | |||||
| Held-out datasets | ||||||||||||
| KDD Cup 99 | 256 | 10 | 11.748 | 1.014 | 1.014 | 1.014 | 91.2% | 10/0/0 | 0.504 | +0.0% | 0/10/0 | 1.000 |
| KDD Cup 99 | 1024 | 10 | 19.774 | 1.004 | 1.003 | 1.003 | 94.9% | 10/0/0 | 0.504 | 0.1% | 6/3/1 | 1.000 |
| KDD Cup 99 | 4096 | 10 | 4.204 | 1.000 | 1.000 | 1.005 | 76.4% | 10/0/0 | 0.504 | 0.0% | 7/1/2 | 1.000 |
| Census 1990 | 256 | 10 | 0.998 | 0.998 | 0.998 | 0.998 | +0.0% | 0/9/1 | 1.000 | +0.0% | 4/1/5 | 1.000 |
| Median test MSE / median test MSE of Lloyd@25 | distance vs. count | distance vs. off | ||||||||||
| Dataset | Seeds | count | off | distance | estimate | W/T/L | W/T/L | |||||
| Held-out datasets | ||||||||||||
| KDD Cup 99 | 256 | 10 | 11.516 | 1.019 | 1.019 | 1.017 | 91.2% | 10/0/0 | 0.504 | +0.0% | 0/10/0 | 1.000 |
| KDD Cup 99 | 1024 | 10 | 6.495 | 0.997 | 0.996 | 0.996 | 84.0% | 10/0/0 | 0.504 | 0.1% | 7/2/1 | 1.000 |
| KDD Cup 99 | 4096 | 10 | 4.605 | 1.002 | 1.004 | 1.010 | 78.4% | 10/0/0 | 0.504 | +0.1% | 3/1/6 | 1.000 |
| Census 1990 | 256 | 10 | 0.998 | 0.998 | 0.998 | 0.998 | +0.0% | 0/8/2 | 1.000 | +0.0% | 4/1/5 | 1.000 |
| Dataset | count | off | distance | estimate | |
|---|---|---|---|---|---|
| KDD Cup 99 | 256 | ||||
| KDD Cup 99 | 1024 | 10 | 10 | 10 | |
| KDD Cup 99 | 4096 | 5 | |||
| Census 1990 | 256 | 2 | 2 | 2 | 2 |
| Census 1990 | 1024 | 2 | 2 | 2 | 2 |
| Census 1990 | 4096 | 5 | 2 | 2 | 3 |
| Dataset | test ( ) | test ( ) | W/T/L ( ) | Time ratio | |
|---|---|---|---|---|---|
| KDD Cup 99 | 256 | +0.1% | +0.1% | 13/0/17 | 0.72 |
| KDD Cup 99 | 1024 | 0.1% | 0.9% | 16/0/14 | 0.53 |
| KDD Cup 99 | 4096 | 1.6% | 2.8% | 20/0/10 | 0.48 |
| Census 1990 | 256 | +0.0% | +0.0% | 3/19/8 | 0.82 |
| Census 1990 | 1024 | 0.1% | +0.0% | 22/4/4 | 0.57 |
| Census 1990 | 4096 | 0.1% | 0.1% | 26/0/4 | 0.71 |
| Dataset | 2 | 3 | 4 | 6 | 8 | 16 | 32 | No clause | off | ||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Covertype (z-score) | 2 | +0.0 | 0.2 | 0.2 | 0.3 | 0.3 | 0.3 | 0.3 | 0.1 | 0.3 | 0.3 | 0.3 | +0.6 |
| Covertype (z-score) | 5 | 0.2 | 0.3 | 0.2 | 0.1 | 0.2 | 0.4 | 0.3 | 0.1 | 0.2 | 0.1 | 0.1 | +0.6 |
| Covertype (z-score) | 10 | 0.4 | 0.5 | 0.6 | 0.6 | 0.6 | 0.5 | 0.5 | 0.2 | 0.5 | 0.4 | 0.3 | +0.5 |
| KDD Cup 99 | 2 | 80.7 | 82.5 | 81.3 | 82.3 | 82.3 | 82.2 | 82.0 | 81.6 | 82.1 | 82.3 | 82.3 | 79.0 |
| KDD Cup 99 | 5 | 79.3 | 79.6 | 78.9 | 78.5 | 78.3 | 78.3 | 78.3 | 78.3 | 76.8 | 78.5 | 78.5 | 72.6 |
| KDD Cup 99 | 10 | 62.7 | 58.9 | 58.9 | 59.6 | 58.5 | 58.8 | 57.3 | 52.3 | 57.2 | 59.6 | 59.6 | 47.7 |
| Imbalance | Mean of the worst 0.1% errors | ||||
| Dataset | count | distance | count | distance | |
| KDD Cup 99 | 256 | 2.08 | 2.09 | 2.4e+04 | 1.09e+04 |
| KDD Cup 99 | 1024 | 1.57 | 1.57 | 1.93e+04 | 4.16e+03 |
| KDD Cup 99 | 4096 | 1.75 | 1.76 | 1.42e+04 | 2.48e+03 |
| Census 1990 | 256 | 1.36 | 1.37 | 151 | 151 |
| Census 1990 | 1024 | 1.29 | 1.30 | 129 | 127 |
| Far groups kept (of 5), by group size | Heterogeneous, MSE | |||||||
| Initialization | Method | 50 | 100 | 150 | 250 | 400 | ||
| Random | Lloyd@25 | 2.3 | 2.7 | 2.8 | 3.3 | 4.7 | 0.822 | 180 |
| Random | count | 0.0 | 0.0 | 0.0 | 0.7 | 5.0 | 0.562 | 152 |
| Random | off | 2.8 | 2.5 | 3.0 | 3.4 | 5.0 | 0.622 | 198 |
| Random | distance | 2.5 | 2.4 | 2.9 | 3.4 | 5.0 | 0.611 | 152 |
| Random | distance , no abandonment | 2.5 | 2.4 | 2.9 | 3.4 | 5.0 | 0.611 | 152 |
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