Small clusters no longer cleared on size alone: a distance check for e-means revival cuts test error by 10% to 80% on isolated groups
Synopsis
In FAISS, e-means removes small clusters every five mini-batches and reuses their centres, but a small cluster may simply cover a rare group far from other points, and removing it is costly. The new rule adds a distance test to the size test: a small cluster is removed only if the squared distance from its centre to the nearest other centre is at most a few times a running mean-squared-error estimate. On held-out datasets with isolated small groups, test error after two epochs falls by roughly 10% to 80% relative to count-based revival, while results on the e-means paper's embedding benchmarks are identical to the library implementation.
Interpretation
The revival rule in e-means now uses a second piece of evidence: whether a small cluster is removed depends not only on how small it is but also on how close its centre sits to the nearest other centre. The original rule flagged as candidates, every five mini-batches, clusters whose count fell below a tenth of the average count, and removed them on size alone, so it could not separate redundant small clusters from those covering rare isolated groups. On UCI Covertype with standardized features, e-means with the original rule ends 58% above the test error of 25 Lloyd iterations after two epochs, while disabling revival ends 24% below it, locating the gap in the removal rule rather than the moving-average update.
The method keeps the size-based candidate set and adds a moving average of each cluster's batch distortion, then gates removal on the ratio of the candidate's squared distance to its nearest other centre over a global mean-squared-error estimate. When a centre equals the mean of its points, that ratio bounds the average per-point increase in squared error caused by removing the centre, so the threshold limits removal to cases whose cost stays within a few times the current error scale. On the three embedding datasets of the e-means paper, in four configurations with up to ten million points and centres, the distance test never blocked a removal, and every run matched the library implementation bit for bit.
On held-out datasets with isolated small groups, the new rule keeps centres that the count-based rule repeatedly removes, and test error drops substantially. Count-based revival moves the centres of rare groups away and pulls their points to a distant centre, which raises the error. Relative to count-based revival after two epochs, test error falls by roughly 25% to 80% on KDD Cup 99, 20% to 75% on Shuttle and 10% to 25% on GeoNames, depending on the number of centres; on the other evaluation datasets it stays within about 1% of the better of revival enabled and revival disabled.
Perspective
Results come from the NumPy CPU implementation of e-means in FAISS 1.16, with tabular datasets of at most two million points and embedding evaluations covering the paper's configurations up to ten million points and centres, where the ten-million configuration only verified identity with the library. The rule needs no new GPU kernel, but GPU and multi-GPU implementations and larger datasets were not run.
Two failure modes predicted by the analysis are reported: the test ignores the error reduction from the split that replaces a removed cluster, and on YearPredictionMSD test error relative to count-based revival is up to about 3% higher; and the test uses a single global error scale, so on a two-dimensional mixture with widely differing cluster scales the median mean-squared error rises by about 7% relative to count-based revival under random initialization. The abandonment clause rarely acts, and removing it changes results negligibly; thresholds between 2 and 8 give nearly the same results, while larger values give up part of the gain.
