Lloyd's k-means algorithm requires a full pass over a dataset for every centroid update, while standard mini-batch k-means converges early to higher quantization error:

Adapting vector-quantized autoencoder moving averages to static MSE minimization, Meta's e-means updates running cluster counts and vector sums on a cosine decay schedule down to 10% of peak step size, splits donor clusters every 5 batches whenever a cluster's count drops below 10% of the mean, and sets batch and step sizes directly from scaling laws with 0 per-dataset tuning. On 1 billion 1,024-dimensional DINO embeddings (1,048,576 centroids), e-means reaches 25-epoch Flash-KMeans test error in 1.6 epochs for a 45.5x wall-clock speedup; on the full 10-billion-vector dataset with 16 million centroids, exact e-means finishes in 2.5 epochs (779 GPU-hours vs. 6,784 for 25-epoch Lloyd) with 0.014% lower test MSE, while an inverted-file approximate variant reaches 0.033% lower MSE in 23.2 GPU-hours on 1 machine.