Researchers have introduced e-means, a clustering algorithm developed at Meta FAIR, with code available in Faiss. Their paper, submitted November 6, reports beating the error reached by Lloyd's k-means after 25 passes through a dataset in just 1.4 to 2.6 passes. For developers grouping large collections of embeddings, that could cut a costly preparation step.
The authors report GPU speedups of 10 to 45 times against the k-means implementations they compared. These are research results, not measurements by MrKeyoor. The implementation documentation also makes clear that hardware and numerical precision affect which execution path runs.
More updates within each pass
K-means groups vectors around representative points called centroids. The project explanation describes how Lloyd's algorithm assigns the full dataset to centroids before updating them. E-means instead updates running statistics on smaller batches, using exponential moving averages so older assignments gradually lose weight.
The method also uses scaling laws to choose batch size and the initial step size. That matters because an optimization method that requires a separate parameter search can spend some of its savings on tuning. The paper says its rules work across multiple problem sizes and embedding datasets without a hyperparameter sweep.
Check the execution path before comparing speed
The Faiss documentation says CPU runs can use Faiss alone. GPU execution goes through PyTorch with Triton or CuTe kernels, rather than calling Faiss. A CPU build of Faiss therefore doesn't mean the clustering must run on a CPU.
Precision deserves attention in a comparison. The same documentation says GPU input in FP32 is converted to BF16 by default for the nearest-centroid search. Running sums and centroids stay in FP32. If your baseline searches in full FP32, compare clustering error alongside elapsed time and record the precision settings. A runtime number alone won't tell you whether the two configurations meet the same accuracy requirement.
There is also a label caveat: training returns assignments from the final epoch, during which centroids were still moving. Those labels aren't always assignments to the nearest final centroid. The documented remedy is to call assign on the training vectors, which adds work that a benchmark should include if its downstream task requires those exact labels.
For a team considering adoption, the next useful evidence is a comparison on its own embeddings, using the required label semantics and recorded hardware settings. The authors provide code and reproduction scripts; MrKeyoor has read the paper abstract and project documentation but has not run those benchmarks. Whether the reported savings survive that workload-specific check is the result to watch.