e-means reaches k-means convergence in one-tenth the epochs, clustering 10 billion embeddings 9.5 to 45.5 times faster on GPUs

The clustering algorithm e-means needs only 1.4 to 2.6 epochs to reach the loss Lloyd k-means attains after 25 epochs, whereas earlier mini-batch k-means converged faster but settled at a higher approximation error, and full-batch Lloyd remained the default for static datasets. Mini-batch k-means typically has a higher approximation error than Lloyd, and Lloyd reaches the lowest mean squared error when run with enough iterations or combined with k-means++ initialization, so the literature keeps Lloyd as the default for static fixed datasets. On DEEP, DINO10B, SPACEV and SimSearchNet++ at scales from 1 million to 1 billion points and 16384 to 1048576 clusters, e-means needs 1.4 to 2.6 epochs to reach the Flash-KMeans loss at iteration 25, a 9.5 to 45.5 times wall-clock speedup, and converges to a lower loss.

Centroids are no longer stored as coordinates: each cluster keeps a count and a sum, both updated by an exponential moving average over mini-batches, and the centroid is read off as their ratio. Exponential moving average updates were previously used in VQ-VAEs to track a shifting embedding distribution, with the decay usually treated as an inherited constant, and were never compared directly with Lloyd's full-batch k-means. The method is evaluated on image and text embedding datasets from 1 million to 1 billion vectors with 16384 to 1048576 clusters, with no hyperparameter tuned in any experiment; batch size and decay come from scaling laws fitted on DEEP.

Decay rate and batch size are computed directly from the number of points, the number of clusters and the epoch budget by two scaling laws that are linear in log space, so a practitioner need not guess a step for an unfamiliar dataset. Earlier mini-batch methods supplied no way to adapt batch size and step to a given problem, leaving a practitioner facing an unfamiliar dataset to guess, which reduced their practicality. The two laws were fitted on 75k optimization runs, incur a median excess mean squared error close to the targeted 1% on held-out datasets, and remain usable at settings several orders of magnitude above the fitting scale.

The demonstrated setting is offline clustering of image and text embedding datasets from 1 million to 10 billion vectors with 16384 to 16777216 clusters, with GPU experiments on H100 80GB hardware and CPU comparisons against Faiss. In the 10-billion-vector DINO10B result, the exact-assignment version needs 32 machines, while switching to IVF approximate assignment reaches the same test loss in 23 GPU-hours on a single machine.

The scaling laws are tuned for relatively high-dimensional datasets and are not optimal on very low-dimensional and tiny datasets; the authors note that the local intrinsic dimensionality of the data, which is the one that matters, is generally unknown. The batch law incurs a median excess mean squared error close to the targeted 1% on held-out datasets rather than hitting it exactly. At the 1-billion scale the authors divide the batch law by 2, because throughput was equivalent with smaller batches at that scale.