Lloyd's k-means algorithm is a long-running standard for clustering, with applications in data analysis, retrieval, quantization and data curation. In this paper, we introduce an exponential moving average optimization procedure for k-means with mini-batch updates, powered by modern deep learning machinery and new insights. We also establish scaling laws on how decay rate and batch size impact final performance. This gives us a formulaic rule to fix them for multiple problem sizes and embedding datasets, without the need for any hyperparameter sweep. The resulting clustering algorithm, coined e-means, is much faster than Lloyd k-means and converges to lower losses, frequently even beating k-means++. On a wide array of embeddings datasets, it beats the loss of Lloyd k-means at 25 epochs in 1.4 to 2.6 epochs, which translates to 10-45x GPU wall-clock speedups compared to state-of-the-art k-means implementations. As an example, e-means partitions DINO10B, a dataset of 10 billion DINO embeddings, into 16 million clusters in only 2.5 epochs, reaching a loss below Lloyd's at 25 epochs.
Figures & tables
Figure 1: e-means vs Faiss-GPU and Flash-KMeans on the DINO10B dataset (1024 dimensions). Left: Test loss as a function of the number of epochs (passes over the 100M training vectors). e-means converges to a lower loss than the two implementations of k-means, and outperforms their loss at 25 epochs in just 2 epochs. Right: aggregated GPU runtime to reach k-means’ loss at 25 epochs on H100 GPUs for various dataset sizes ( k≈n/500 is a power of 2). Flash-KMeans is limited to one node, so we used our own implementation of k-means to run it above 100M scale. e-means saves about 10× compute relatively to the state-of-the-art implementations. On very large datasets, combining e-means with an IVF yields further speedups, see Appendix M .
ablation
train MSE
test MSE
our recipe
0.3613
0.3880
no cosine schedule
0.3623(+0.26%)
0.3877(−0.06%)
no revival
0.3721(+2.97%)
0.3967(+2.24%)
revival by resampling
0.3688(+2.06%)
0.3925(+1.15%)
no finalization
0.3618(+0.14%)
0.3881(+0.02%)
slow EMA
0.3618(+0.14%)
0.3877(−0.08%)
Table 1: Ablation of e-means contributions. DEEP*, n=106 , k=16,384 , T=3 epochs; medians over 30 seeds. Lower is better. Almost all ablations cost on training loss. Training error is measured on the codes the final epoch itself produced, over a fixed 200,000 -vector subset, and both columns are recomputed in double precision. The constant-step arm is retuned and selected on validation.
c
k
B
n
T
OOD (%)
LOSO (%)
R2
step α0 , Equation 6
0.824
−0.46
0.90
−0.45
−0.11
0.07
0.07
0.95
batch B , knee at 0.2%
0.035
0.13
—
0.88
0.81
0.19
0.20
0.96
batch B , knee / 8
0.0044
0.13
—
0.88
0.81
0.07
0.06
n/a
Table 2: Scaling laws: power values obtained for the decay rate α0 and the batch size B .
Figure 2: The curve families the two laws are fitted to (DEEP, n=106 , k=1024 ; validation error). Left ( T=4 ): one curve per batch size; stars mark each curve’s best step, which the step law fits, and move right as B grows. Right (each point at its own best step): one curve per epoch budget; diamonds mark where each curve rises 0.2% above its own floor, the knee the batch law fits.
n=100 M
n=1 B
n=10 B
k=218
k=221
k=224
exact assignment
0.028
4.56
779
IVF assignment
0.030
1.05
22.8
Table 3: GPU hours for e-means to reach Lloyd’s test loss at 25 epochs on DINO10B subsets. For IVF assignment, each cell reports the fastest of 3 IVF settings tried (Appendix M ).
Figure 3: Loss as a function of the number of epochs on 4 datasets. The top row provides results on the training loss, the bottom row is held-out test error. The loss is normalized by Lloyd’s error after 25 iterations on the same experiments, so 1.0 is the default Faiss run. Mean over 10 seeds. The dotted curve is regular Faiss Lloyd initialized with the greedy scikit-learn k-means++ init, which works better than the original k-means++, see Appendix G.2 .
Figure 4: Test error against wall-clock time . (a) on CPU, 64 cores. (b) on one GPU, at ten million points (upper) and then at a hundred million (lower). The y axis is test MSE as a percentage difference from the reference each half is measured against at 25 iterations: Faiss in (a) and Flash-KMeans in (b) . For e-means, every marker is an independent run with a fixed T , batch and step. Curves are the median over 10 seeds. The numbers on some of the curves indicate the epoch counts for the corresponding points.
(a) Epochs to Flash@25 MSE
(b) Wall-clock speedup vs Flash-KMeans
n
k
DEEP*
DINO10B
SPACEV
SimSearchNet++
DEEP*
DINO10B
SPACEV
SimSearchNet++
1M
16,384
2.0
2.0
2.4
1.4
12.8 ×
12.7 ×
9.5 ×
12.9 ×
10M
65,536
2.0
1.4
2.0
1.6
27.8 ×
23.3 ×
19.2 ×
23.8 ×
100M
262,144
2.0
1.6
1.4
2.6
27.0 ×
31.3 ×
35.9 ×
19.9 ×
1B
1,048,576
1.6
1.6
1.4
2.0
36.0 ×
45.5 ×
37.9 ×
21.2 ×
Table 4: How many epochs to match Flash-KMeans at several dataset scales? (a): We increase the number of epochs by steps of 0.2 until the test MSE drops below that of Flash-KMeans at 25 epochs. (b) the wall-clock speedup at that number of epochs. Medians of the per-seed values over 10 seeds up to 100M, and a single seed at 1B. The experiments at scales 1M-100M are run on 1 GPU, 8 GPU for 1B.
e-means
Flash-KMeans
Flash-KMeans
random init
random init
greedy k-means++ init
dataset
n
k
scale
3 ep.
5 ep.
10 it.
25 it.
10 it.
25 it.
DEEP*
1M
16,384
10−1
3.8788
3.8692
3.8997
3.8926
3.8752
3.8715
SIFT
1M
16,384
10−1
1.9641
1.9600
1.9750
1.9710
1.9653
1.9631
SPACEV
1M
16,384
103
7.2012
7.1703
7.2556
7.2304
7.2050
7.1913
SimSearchNet++
1M
16,384
105
1.1314
1.1297
1.1362
1.1357
1.1338
1.1334
Table 5: Test MSE at a fixed epoch budget. We report the median MSE over 10 seeds.
Figure 5: Loss over 40 seeds, three datasets, on both train and test. We run Lloyd to convergence with Faiss (training error varying by less than 10−6 across 2 epochs).
Appendix figures & tables40 assets
Supplementary material from the paper’s appendix.
Appendix
Dataset
Content
d
N used
Eval set
BigANN 2021 challenge ( Simhadri et al., 2022 )
SIFT
Image descriptors ( Jégou et al., 2011 )
128
1M–1B
provided queries
DEEP
Image embeddings ( Babenko and Lempitsky, 2016 )
96
1M–1B
provided queries
SPACEV
Text embeddings ( Microsoft, 2021 )
100
1M–1B
index holdout
SimSearchNet++
Image embeddings ( Douze et al., 2021 )
256
1M–1B
provided queries
VIBE benchmarks ( Jääsaari et al., 2025 )
Appendix
Table 6: Summary of datasets used in our paper. Index holdouts are carved from the original dataset, with deduplication to avoid contamination. We group the datasets by collections they were included in. We include only VIBE datasets that appear in the main body.
Figure 6: The step valley, one curve per batch size (DEEP, n=106 , k=1024 , T=4 ). Stars are each curve’s lowest measured point, which is what Equation 6 fits; they move right as B grows.
Figure 7: The batch curve, one curve per epoch budget (DEEP, n=106 , k=1024 , each point at its own best α0 ). Diamonds are the +0.2% crossing Equation 7 fits, 40,464 at T=2 rising to 220,202 at T=25 .
median regret, held out by
model
free parameters
n
dataset
T
the full law CαkakBaBnanTaT
5
0.067%
0.068%
0.065%
without k
4
0.232%
0.174%
0.168%
without B
4
0.571%
0.560%
0.530%
without n
4
0.222%
0.134%
0.132%
without T
4
0.074%
0.076%
0.083%
Appendix
Table 7: Regret of our decay power law when removing variables. Each row drops one or two variables from the decay power law. We report median regret measured against each configuration’s optimal decay value. The three columns differ in what is held out. n : one size is left out at a time and the law is refitted on the rest, pooled over the four sizes the grid carries. dataset : the law is fitted on DEEP alone (this is thus our canonical law) and scored on the four evaluation datasets. T : one budget left is out at a time.
log inputs, raw target α0=c0+aklogk+aBlogB+anlogn+aTlogT
5
0.158%
0.161%
0.161%
raw inputs, log target α0=Cαexp(akk+aBB+ann+aTT)
5
0.799%
0.444%
0.414%
raw inputs, raw target (fully linear) α0=c0+akk+aBB+ann+aTT
5
0.787%
0.473%
0.440%
Appendix
Table 8: Regret of alternative regressions compared to our power law on the decay. Every row fits the same five free parameters on the same training data as our decay law and is clipped to α0≤1 as in Equation 6 . Only the law form differs. The tegret that is report corresponds to the median over the evaluation datasets. It is measured against the optimal decay, i.e., the same reference used in Table 7 .
Baseline
Implementation
Swept over
Flash-KMeans
flash_kmeans 0.3.1, one public-API call, forced to the full count (max_iters=T, tol=-1)
scikit-learn 1.7.2 MiniBatchKMeans, with its early stopping switched off (max_no_improvement=None, tol=0) so every run completes its full budget
Batch size: 256, 512, 1024, 2048, 4096, 65536, 262144, 524288. Dead-cluster threshold (reassignment_ratio): 0, 0.001, 0.01, 0.05, 0.1, 0.5, where 0 is the published algorithm, which has no dead-cluster revival
SuperKMeans
Authors’ library ( Kuffo et al., 2026 ) .
Not swept — one setting
Appendix
Table 9: Baseline methods we compare with, and their parameters.
test
train
Dataset
N=105
N=106
N=107
N=105
N=106
N=107
SIFT
3.0
2.0
2.0
3.0
3.0
3.0
DEEP*
2.0
2.4
2.0
3.0
2.6
3.0
SPACEV
2.0
3.0
2.0
3.0
3.0
3.0
SimSearchNet++
3.0
3.0
2.2
4.0
3.4
4.0
DINO10B
1.6
2.0
2.0
2.0
3.0
3.0
Appendix
Table 10: Number of epochs for e-means to reach Lloyd at 25 epochs on a wide array of datasets, taken as the median over 5 seeds. Non-applicable cells are because the datasets did not go up to 107 dataset vectors.
Figure 8: The table above, as % difference from Lloyd at 25 iterations; blue means e-means is better. Left, both at 25 epochs; right, e-means at its best test budget, shown in the cell.
Figure 9: Synthetic datasets: Number of epochs to reach Lloyd@25 on training error ( left ) or test error ( right ), as a function of dataset size and data distribution. d=128 , ten seeds, with K=4n rounded to a power of two, thus growing from 512 to 16,384 .
Figure 10: Synthetic datasets: relative final MSE of e-means vs. Lloyd at 25 epochs each, against dataset size. d=128 . The few red cells correspond to overfitting : even though e-means reaches Lloyd’s final test MSE in a few epochs, because these cells are high-dimensional e-means’s test MSE grows in last epochs resulting in higher test MSE than Lloyd.
Figure 11: Synthetic data distributions, e-means epochs to reach Lloyd@25 as a function of dimension . Here n=106 , K=4,096 . Bars are the median over seeds, whiskers one standard deviation. Top: matched training error, bottom: matched test error.
Figure 12: Synthetic datasets: Training MSE (top) and test MSE (bottom) relative difference (%) at 25 epochs each, as a function of the dimension. Blue is e-means ahead. Both arms are scored on the same fixed 200,000 training rows. n=106 , K=4,096 , seven synthetic distributions, ten seeds.
Figure 13: Sample convergence curves on four synthetic configurations
GooAQ
CodeSearchNet
arXiv
ImageNet-CLIP
GloVe-200
AG-News
Landmark-DINO
Landmark-Nomic
CC-News
SimpleWiki
CelebA
N (millions)
1.48
1.37
1.34
1.28
1.19
0.77
0.76
0.76
0.50
0.26
0.20
d
768
768
768
512
200
1024
768
768
768
3072
2048
K
16k
16k
16k
16k
16k
16k
16k
16k
8k
8k
8k
GPU: seconds to Lloyd@25 — baseline Flash-KMeans, fp16 against our bf16, one H100
Flash-KMeans (s)
1.77
1.41
1.12
0.83
0.49
1.18
0.81
1.09
0.54
1.37
0.50
e-means (s)
0.16
0.13
0.14
0.07
0.05
0.10
0.06
0.08
0.04
0.06
0.03
Appendix
Table 11: Time and epochs to reach Lloyd@25 on the eleven VIBE datasets, each at its full row count with K=16N rounded to a power of two. The objective is fixed and external: Lloyd — classical k-means, here Faiss — run for twenty-five iterations, the canonical result quoted against throughout this paper. 20 seeds are run, error and time are a median over them.
Figure 14: Test error against wall-clock time on one H100 , eleven VIBE datasets, e-means and Flash-KMeans only, median over twenty seeds.
Figure 15: Test error against wall-clock time on 64 physical CPU cores , the same eleven datasets. Down and to the left is better.
Figure 16: Distortion against batch size, every optimizer at its optimal tuned step on validation error. The configurations are at T=5 epochs. Curves are the median over three seeds.
Figure 17: Relative test MSE against effective learning rate. Measurements are done at T=5 , median over 3 seeds.
Figure 18: Train error against wall-clock time on one H100 , one panel per dataset, n=107 , K=65,536 . Every arm is scored the same way, by a fresh nearest-centroid search over a fixed subset of the training rows using the centroids it finished with. Faiss-GPU and Flash-KMeans are two implementations of one algorithm, so both are given one shared error curve — our own Lloyd at the matching iteration count, measured once on our kernels — while each keeps the wall-clock time it actually took. e-means is measured on its own.
Figure 19: Train error against wall-clock time on one H100 , one panel per dataset, n=108 , K=262,144 . Scored as in the figure above: Flash-KMeans carries our own Lloyd’s error at the matching iteration count and its own measured time, and e-means is measured on its own.
Figure 20: Train error against wall-clock time on CPU , n=106 , K=16,384 , 64 physical cores.
train MSE
test MSE
init (s)
dataset
scale
T
rand.
k-m++
Δ%
rand.
k-m++
Δ%
rand.
k-m++
train (s)
DEEP*
10−1
5
3.5896
3.5840
−0.16
3.8727
3.8667
−0.15
0.1
2,852
22.3
DEEP*
10−1
10
3.5727
3.5673
−0.15
3.8667
3.8608
−0.15
0.1
2,852
39.2
SIFT
10−1
5
1.9332
1.9315
−0.09
1.9577
1.9614
+0.19
0.1
3,516
21.9
SIFT
10−1
10
1.9241
1.9222
−0.10
1.9606
1.9593
−0.07
0.1
3,516
40.0
SPACEV
103
5
6.8715
6.8639
−0.11
7.1756
7.1654
−0.14
0.1
3,151
22.6
Appendix
Table 12: Random against k-means++ initialization
Figure 21: Both k-means++ variants on the same axes , test error over 40 restarts.
train MSE
test MSE
dataset
N
K
scale
cosine
best fixed
Δ
cosine
best fixed
Δ
DEEP*
1M
16,384
10−1
3.6135
3.6228
+0.26
3.8797
3.8773
−0.06
DINO10B
1M
16,384
105
1.8826
1.8967
+0.75
2.0554
2.0666
+0.54
SPACEV
1M
16,384
103
6.9275
6.9666
+0.56
7.2064
7.2055
−0.01
SimSearchNet++
1M
16,384
105
1.0886
1.1026
+1.29
1.1309
1.1312
+0.03
DEEP*
10M
65,536
10−1
3.3078
3.3266
+0.57
3.4193
3.4183
−0.03
Appendix
Table 13: The cosine schedule against a fixed decay rate chosen to minimize validation error, T=3 epochs, median over 10 seeds.
dataset
N
policy
dead clusters
as %
imbalance
test MSE
DEEP*
1M
on (e-means)
47
0.3%
1.194
0.38762
resample from batch
2343
14.3%
1.423
0.39124
off
4313
26.3%
1.647
0.39448
SIFT
1M
on (e-means)
10
0.1%
1.186
0.19623
resample from batch
750
4.6%
1.233
0.19684
off
2080
12.7%
1.404
0.19797
Appendix
Table 14: Impact of dead-cluster revival strategy on centroid health
Train MSE
Test MSE
K
n/K
No finalizer
Last-epoch mean
Slow EMA
No finalizer
Last-epoch mean
Slow EMA
32,768
305.2
0.348557 [-1pt] (0.000%)
0.348518 [-1pt] (-0.011%)
0.348729 [-1pt] (+0.049%)
0.356406 [-1pt] (0.000%)
0.356416 [-1pt] (+0.003%)
0.356343 [-1pt] (-0.018%)
65,536
152.6
0.329474 [-1pt] (0.000%)
0.329371 [-1pt] (-0.031%)
0.329863 [-1pt] (+0.118%)
0.341573 [-1pt] (0.000%)
0.341551 [-1pt] (-0.007%)
0.341430 [-1pt] (-0.042%)
131,072
76.3
0.309877 [-1pt] (0.000%)
0.309468 [-1pt] (-0.132%)
0.312040 [-1pt] (+0.698%)
0.328351 [-1pt] (0.000%)
0.328396 [-1pt] (+0.014%)
0.328080 [-1pt] (-0.082%)
Appendix
Table 15: Impact of each finalization strategy on train and test MSE. DEEP* results at n=107 , T=3 . Entries are five-seed medians; parentheses report the percentage change relative to Main EMA (negative is better). Slow EMA is selected using validation MSE from speeds {1/16,1/4,1,4} times the final cosine-floor step size. The selected speeds are 1/4× for K=131,072 and 1× for the other two rows. Its test-MSE improvement increases from 0.018% to 0.082% as K increases.
Figure 22: Test MSE vs train MSE on DEEP* at n=106 with K=65536 , T∈[1,5] and different finalization methods. Main EMA refers to using the centroids as predicted by the algorithm’s cosine-law EMA. Closing-mean replaces these centroids by the average of their last-epoch assigned datapoints. Slow EMA lines show the span of regimes that can be achieved by smoothing out the final centroids using a constant-speed EMA, where the EMA speed spans between 128x slower and 4x faster than the cosine law’s final value.
T=3
T=5
Dataset
n
BF16
FP8
INT8
BF16
FP8
INT8
Flash@25
SIFT
106
0.19631
0.19651
0.19625
0.1961
0.19585
0.19607
0.1971
SIFT
107
0.19578
0.19568
0.19574
0.19557
0.19545
0.19561
0.19618
DEEP*
106
0.38805
0.3879
0.38809
0.38702
0.38695
0.3869
0.38926
DEEP*
107
0.34148
0.3416
0.3415
0.34066
0.34102
0.34097
0.34224
SPACEV
106
7206.0
7206.3
7203.1
7172.3
7171.5
7171.9
7230.5
Appendix
Table 16: Test MSE under reduced-precision assignment. Each entry is the mean over ten runs that use the same seeds for BF16, FP8, and INT8. We assign every test point to its nearest final centroid and compute the resulting MSE in double precision. FP8 and INT8 remain within 0.13% of BF16 in every configuration shown. Every BF16, FP8, and INT8 entry is lower than the corresponding Flash-KMeans result after 25 iterations. † For SimSearchNet++, we compute the Flash-KMeans centroid norms in FP32 because their median squared norm ( 4.3⋅106 ) exceeds the FP16 maximum ( 65,504 ).
T=3
T=5
Dataset
n
BF16
FP8
INT8
BF16
FP8
INT8
SIFT
106
0.29%
3.16%
1.82%
0.19%
2.13%
1.20%
SIFT
107
0.43%
4.54%
2.61%
0.35%
3.74%
2.14%
DEEP*
106
0.18%
2.95%
2.91%
0.12%
1.95%
1.91%
DEEP*
107
0.27%
4.17%
4.09%
0.22%
3.41%
3.36%
SPACEV
106
0.13%
2.49%
1.59%
0.07%
1.51%
0.94%
Appendix
Table 17: Fraction of assignments changed by reduced precision. For every batch in the final epoch, we repeat the nearest-centroid search in double precision using that run’s centroids from the start of the batch. The table reports the percentage of points for which each reduced-precision assignment differs from that double-precision reference, averaged over ten runs with the same seeds.
different assignments
test MSE
Dataset
n
rescaled
direct
rescaled
direct
SPACEV ( T=3 )
106
1.59%
2.90%
7203.1
7206.0
SPACEV ( T=5 )
106
0.94%
1.76%
7171.9
7172.3
SPACEV ( T=3 )
107
1.80%
3.20%
6352.7
6353.6
SPACEV ( T=5 )
107
1.44%
2.58%
6334.3
6336.2
SimSearchNet++ ( T=3 )
106
8.08%
3.83%
113157
113133
Appendix
Table 18: Direct versus rescaled INT8. Both methods use INT8 arithmetic on datasets stored as 8-bit integers. Direct maps the stored integers exactly into signed INT8, subtracting 128 from unsigned values. Rescaled subtracts the mean of each coordinate and applies a fitted power-of-two multiplier before rounding. For each method and run, different assignments are measured against double-precision reassignment using that run’s centroids from the start of the batch, following Table 17 . Each entry is averaged over 10 runs.
Figure 23: A batch of 1000 images is cropped into 14×14 patches per image and passed through the DINOv3 model, producing 1000×196 vectors of dimension 1024.
Figure 24: Search accuracy against index build time at 1% selectivity. We measure Recall@10 on the test query set, the horizontal axis is training over the dataset. We use a median over twenty seeds. Labels in the first panel are epoch budgets, and the dashed line is Flash-KMeans after twenty-five epochs.
Figure 25: Search accuracy against index build time at 0.1% selectivity. We measure Recall@10 on the test query set, the horizontal axis is training over the dataset. We use a median over twenty seeds. Labels in the first panel are epoch budgets, and the dashed line is Flash-KMeans after twenty-five epochs.
Figure 26: Convergence plot for different types of assignment, for the first n=109 vectors of DINO10B, k=221 and 30 epochs of optimization. Training and testing MSE are computed at the end of each epoch with the current state of the centroids. The batch MSE is computed just on the points in the batch before the update step. The approximate assignment types ivf1024.np4 ( KIVF=1024 , LIVF=4 , coarse) and ivf4096.np16 ( KIVF=4096 , LIVF=16 , more accurate) are defined above. The training time (in GPU-hours) for the different types of assignment is indicated in parentheses.
Figure 27: Tradeoffs between MSE and training time for approximate assignment with different IVF sizes.
Ablation
Training
MSE ( ×104 )
time (s)
Train
Test
Baseline
10.1
17.02
18.72
Retrain
558.1
16.94
18.72
Period 4
8.216
17.02
18.71
Period 16
7.926
17.05
18.72
Period 64
7.780
17.32
18.78
Appendix
Table 19: Ablation on ANNS assignment. All runs are with IVF1024, LIVF =4 and 2 epochs. The baseline rebuilds the index at each iteration (period 1) and trains the IVF partition only once.
Figure 28: Per-batch MSE during the training iterations. The period indicates how often the index is rebuilt: with period 4 the IVF index is rebuilt every 4 iterations. The vertical line indicates the end of the first epoch (out of 2 epochs).
n
n/500
k actually used
rows per centroid
100K
200
256
391
1M
2,000
2,048
488
10M
20,000
16,384
610
100M
200,000
262,144
382
1B
2,000,000
2,097,152
477
10B
20,000,000
16,777,216
596
Appendix
Table 20: Number of centroids k actually used in the scaling experiments. It is the power of two nearest to n/500 , where n is the training set size.
method
assignment
epochs
test MSE
vs Lloyd
train MSE
GPU
nb
×104
(test)
×104
hours
machines
Lloyd
exact
25
12.987
–
12.468
6,784
64
e-means
exact
2
12.994
+0.055%
12.513
885
32
e-means
exact
2.5
12.985
−0.014%
12.489
779
32
e-means
exact
3
12.965
−0.170%
12.464
961
32
e-means
exact
3.5
12.980
−0.053%
12.478
794
32
Appendix
Table 21: Experiments on the full DINO10B dataset, with k =16Mi centroids. The objective of the e-means runs is to outperform the Lloyd test MSE.
method
assignment
epochs
test MSE
vs Lloyd
train MSE
GPU
nb
×104
(test)
×104
hours
machines
Lloyd
brute-force
25
14.712
—
13.984
43.54
16
e-means
brute-force
2.8
14.704
-0.053%
13.927
4.56
1
e-means
IVF1024, LIVF =4
2
14.722
+0.070%
14.089
1.2
1/2
e-means
IVF1024, LIVF =4
3
14.712
-0.000%
14.045
1.05
1/2
e-means
IVF1024, LIVF =4
4
14.702
-0.063%
14.026
2.0
1/2
Appendix
Table 22: Experiments on the first 1B vectors of DINO10B dataset, with k =2Mi centroids. The e-means experiments are run on 4 GPU (=half a 8-GPU machine).
e-means (Bessa et al., 2026) is a recent mini-batch k-means algorithm, now part of the FAISS library, that reaches the error of Lloyd's algorithm about an order of magnitude faster on large embedding datasets. Every five mini-batches, it removes every cluster whose running point count falls below a tenth of the average and reuses its centre to split a large cluster. In the authors' ablation, removing this mechanism, called dead-cluster revival, raises the error more than removing any other component added to the moving-average update. The rule, however, considers only cluster size: it cannot distinguish a cluster that is small because it is redundant from one that covers a rare, isolated group of points, and on data with such groups it repeatedly removes centres whose removal is costly. We add a second condition, based on the distance between centres: a small cluster is removed only if its centre is close to another centre, relative to a running estimate of the mean squared error. When a centre equals the mean of its points, this squared distance is an upper bound on the average increase in squared error, per point of the cluster, caused by removing the centre. The condition costs one nearest-centre search for the small clusters every five mini-batches and adds no measurable running time. On the e-means paper's embedding benchmarks, it never prevents a removal, so the results are identical to those of FAISS. On datasets with small isolated groups not used during development, it reduces the test error after two epochs by roughly 10% to 80% relative to count-based revival, and it preserves the advantage of k-means++ initialization; on the other evaluation datasets, it stays within about 1% of the better of revival enabled and disabled. We also report two failure modes that the analysis predicts. This is a CPU proof of concept; GPU implementations are left to future work.
We present SuperKMeans: a k-means variant designed for clustering collections of high-dimensional vector embeddings. SuperKMeans' clustering is up to 7x faster than FAISS and Scikit-Learn on modern CPUs and up to 4x faster than cuVS on GPUs (Figure 1), while maintaining the quality of the resulting centroids for vector similarity search tasks. SuperKMeans acceleration comes from reducing data-access and compute overhead by reliably and efficiently pruning dimensions that are not needed to assign a vector to a centroid. Furthermore, we present Early Termination by Recall, a novel mechanism that early-terminates k-means when the quality of the centroids for retrieval tasks stops improving across iterations. In practice, this further reduces runtimes without compromising retrieval quality. We open-source our implementation at https://github.com/cwida/SuperKMeans
Leonardo Kuffo, Sven Hepkema, Peter Boncz
CWI, Amsterdam, The Netherlands · Systems Group, ETH Zurich, Zurich, Switzerland
Hartigan's k-means algorithm has theoretical advantages over the standard Lloyd's variant, which has become synonymous with "k-means". Yet, Hartigan's algorithm is far slower in practice due to its inherently sequential calculations. We devise a Batched Hartigan's method that enables vectorized calculation by exploiting the triangle inequality to expose a set of parallel-safe updates and a smaller set of sequential updates. This makes Hartigan's method competitive with Lloyd's in execution speed for the first time.
Edward Raff, Michael Slawinski
CrowdStrike · University of Maryland, Baltimore County · Syracuse University