cs.LGNov 13, 2026

Small Is Not Dead: Distance-Aware Cluster Revival for e-means

Authors: Eyal Weiss

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

Appendix figures & tables15 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. e-means: outperforming k-means (in one-tenth the epochs)

    Nov 6, 2026Swann Bessa, Pierre-Emmanuel Mazaré, Gergely Szilvasy +4ClusteringScaling Laws

  2. An interpretable Good--Turing restart criterion for k-means++

    Jul 9, 2026Renato Cordeiro de AmorimEarly StoppingClustering

  3. A Super Fast K-means for Indexing Vector Embeddings

    Mar 20, 2026Leonardo Kuffo, Sven Hepkema, Peter BonczClustering