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

Eyal WeissarXiv 2026 · arXiv

In the world of large-scale vector quantization, e-means has emerged as a high-speed successor to the classic Lloyd’s algorithm. By processing data in mini-batches and using moving averages, it achieves similar error rates up to ten times faster. However, e-means has a "ruthless" side: a mechanism called dead-cluster revival that kills off small clusters to split larger ones.

A new paper from Eyal Weiss at Carnegie Mellon University, titled "Small Is Not Dead: Distance-Aware Cluster Revival for e-means," argues that this mechanism is too aggressive. By making the revival process "distance-aware," Weiss shows we can drastically improve accuracy on diverse datasets without losing the speed that makes e-means attractive.

TL;DR

The e-means algorithm often accidentally deletes small but important clusters (like rare data categories) because it only looks at cluster size. By adding a simple "distance-aware" check—only removing a small cluster if it is also close to another center—this work reduces test error by 10% to 80% on non-uniform datasets with zero measurable impact on running time.

What Problem Does This Paper Address?

The original e-means algorithm includes a "revival" rule: every five mini-batches, any cluster with fewer than 10% of the average number of points is deleted. Its center is then reused to split a larger, more "crowded" cluster.

This works great for uniform embedding datasets where small clusters are usually just redundant. But in the real world, data is often "long-tailed." A cluster might be small because it represents something rare but distinct—like an unusual sensor reading, a remote village in a geographic dataset, or a rare soil type.

When e-means deletes these "rare but far" centers, the points in those groups are forced to join distant clusters, causing the total error (Mean Squared Error) to skyrocket. On the UCI Covertype dataset, this behavior caused e-means to end up with 58% higher error than the baseline.

Figure 1: Two-dimensional example: 20 Gaussian blobs of 2,000 points and three far groups of 80 points (dotted circles), k = 23 centres initialized by k-means++ (orange circles), and 5 epochs of e-means. Left: count-based revival removes the centres of the three far groups and reuses them inside the main mass of points. Right: with the distance test, all three are kept. Seed 0 is shown; the outcome (0 of 3 and 3 of 3 far groups kept) is the same in all 10 seeds. The size threshold is the e-means paper’s τcount = 0.1; since version 1.16, the library disables revival by default for d ≤2.

Methods

The author proposes a more surgical revival rule. Instead of just checking size, the algorithm now checks utility.

A candidate cluster $j$ is only removed if:

  1. Size Test: It falls below the population threshold (the original e-means rule).
  2. Distance Test: Its center is "close" to another center. Specifically, the squared distance to its nearest neighbor center must be less than 4 times the current global Mean Squared Error ($\delta_j \le 4 \cdot \widehat{MSE}$).

Why this works: Mathematically, the squared distance to the nearest center serves as an upper bound on how much the error will increase if that cluster is deleted. If a center is far from everything else, deleting it is "expensive" for the model's accuracy, so the new rule protects it.

The author also includes an abandonment clause: if a center receives zero points for two full epochs, it is removed regardless of distance, ensuring that truly "dead" centers don't hang around forever.

Datasets

The study evaluated the new rule across three categories of data:

  • Original e-means Benchmarks: Large-scale embedding datasets (DEEP 1M/10M, SIFT 1M, SPACEV 1M).
  • Held-out Tabular/Geographic Data: KDD Cup 99 (network intrusion), US Census 1990, GeoNames (lat/long), and others.
  • Synthetic Data: Gaussian blobs designed to simulate rare, isolated groups.

Key Insights and Ideas

  • Small $\neq$ Redundant: The core "aha" moment is that cluster size is a poor proxy for cluster utility. A cluster of 10 points 100 miles away is more important to keep than a cluster of 10 points 1 foot away from a giant cluster.
  • Cheap Information: The distance check requires only one nearest-center search for the small number of candidate clusters. Since this happens only every five mini-batches, the computational cost is effectively zero.
  • Preserving Initialization: Standard e-means often "undoes" the smart work of initializers like k-means++ by deleting the very centers k-means++ specifically placed on isolated outliers. The distance-aware rule preserves these high-utility placements.
  • Dataset Separation: As shown in Figure 3, different datasets have very different distributions of center distances. The embedding datasets (blue/green lines) have almost no centers far from others, explaining why the original e-means worked there but failed elsewhere.
Figure 3: Cumulative distribution of the distance-to-MSE ratio. Tabular datasets (like KDD Cup and Covertype) have many candidates far above the threshold.

Key Results

  • Massive Accuracy Gains: On KDD Cup 99, the new rule reduced test error by 25–80% compared to the original e-means. On the Shuttle dataset, gains were 20–75%.
  • No Speed Penalty: In timed CPU runs, the distance-aware version was indistinguishable from the original FAISS implementation in terms of wall-clock time.
  • Backward Compatibility: On the original embedding benchmarks used to develop e-means, the new rule never triggered a "save," meaning it produced results identical to the current FAISS library. It offers "gain without pain."

Limitations and Future Work

  • Global vs. Local Scale: The rule uses a global MSE to decide if a distance is "large." In datasets with wildly different cluster scales (some very tight, some very broad), a global threshold might still fail to protect some redundant clusters or delete some important ones.
  • Ignoring Split Benefit: The rule looks at the cost of removing a cluster but doesn't account for the benefit of the split that follows. A more advanced rule might compare these two values directly.
  • Hardware: This work is a CPU-based proof of concept. While the logic is simple, implementing it efficiently within GPU-accelerated frameworks like FAISS (which uses CUDA graphs) remains for future engineering.

Summary updated

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.
BibTeX
@misc{weiss2026small,
  author = {Eyal Weiss},
  title = {{Small Is Not Dead: Distance-Aware Cluster Revival for e-means}},
  year = {2026},
  eprint = {2611.18238},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.18238},
}
Figure