e-means speeds up large-scale k-means clustering
The authors introduced e-means, a mini-batch k-means algorithm based on exponential moving averages, with scaling laws that set decay rate and batch size across problem sizes and embedding datasets. They report that e-means reaches lower loss than Lloyd k-means in 1.2–3 epochs, with 10–45× GPU wall-clock reduction against Flash-KMeans and 8–15× CPU reduction against Faiss; the code is available in Faiss's contrib directory.
e-means could reduce the compute cost of large-scale embedding clustering and vector quantization by replacing repeated full-batch Lloyd updates with an automatically parameterized mini-batch method, though the reported gains remain author-measured.
An order of magnitude less epochs
Across a large range of scales and datasets, e-means reaches a test loss below Lloyd's at 25 epochs, in 1.2 to 3 epochs. Measured end to end, that is a 10–45× wall-clock reduction on GPU against the state-of-the-art Lloyd implementation (Flash-KMeans[2]), and 8–15× on CPU against Faiss[1]. Speed and quality usually trade against each other in k-means, while e-means achieves both better speed and loss.

The k-means problem
Given a fixed dataset of n points X = {x 1, ..., x n} ⊂ R d and an integer k, the k-means problem is to find k centroids C = (c 1, ..., c k) minimizing the mean squared distance between each point and its nearest centroid:
$$ M S E \left(\right. X , C \left.\right) = \frac{1}{n} \sum_{i = 1}^{n} \parallel x_{i} - c_{a \left(\right. i \left.\right)} \parallel^{2} , a \left(\right. i \left.\right) = arg \underset{j \in \left{\right. 1 , \ldots , k \left.\right}}{min } \parallel x_{i} - c_{j} \parallel^{2} $$
#e-means#Faiss#Flash-KMeans#DINO10B#VIBE#Lloyd k-means#k-means++