For a given time budget, which k-means implementation and settings give the lowest inertiaWhat k-means minimizes: the squared distance of each sample to its nearest center, here averaged over all samples. Lower is better.? Each plot shows the fitTraining a model on data. More in the scikit-learn glossary time against the inertia of the returned centers, for one dataset and one number of clusters, with one Pareto frontThe settings that no faster setting beats: each point of the front is the best result reachable within its time. per implementation and machine, as ann-benchmarks does for nearest neighbor search. Lower left is better.
Comparing the time of a Lloyd iteration is not enough: inits differ in cost and quality (random, k-means++Init that picks each new center at random, more likely far from the centers already picked (greedy variant: the best of a few candidates). Slower than a random init, usually better centers. More, k-means||Parallel variant of k-means++ (scalable k-means++, cuML's default): it oversamples candidates in a few rounds, then reduces them to k centers.), and e-meansMini-batch k-means with an exponential moving average update of the centers and a random init (Meta FAIR, 2026). Its budget is a number of passes over the data (epochs). More trades iterations for quality differently. The settings of each implementation (init, number of inits, iterations or epochs, tolerance) sweep the time budget.
How to read
A point is one setting of one implementation: the median over 3 seeds of the fit time and of the relative inertiaInertia divided by the lowest one any run reached on the same dataset and number of clusters, minus 1. 1e-3 means 0.1% above the best known inertia., with whiskers from the best to the worst seed. The line is the Pareto front of the implementation on that machine: with a time budget t, the best it gets is the last step left of t. Faded points are off the front. Hover a point for its settings, iterations and empty clusters.
The fit time includes the init, with the data already in host memory for CPU implementations and in device memory for GPU ones (except FAISS on the GPU, whose training loop runs on the host). The inertia is the mean squared distance of every sample to its nearest center, computed in float64 from the returned centers by the same code for every implementation. Everything runs in float32 with TF32 off, and CPU implementations get the same number of threads: one per physical core, at most 64. Machines with more cores run on their first 64 physical cores.
The best known inertia of a dataset and number of clusters is the lowest of any run on any machine, including long reference runs, implementations and builds that are not plotted. Points and whiskers on the dotted line at 1e-4 are within 1e-4 of it, and the hover gives their exact relative inertia, or "best" below 1e-6 (rounding differences between machines are ~1e-7).
Implementations
- scikit-learn Lloyd:
KMeans(algorithm="lloyd")of scikit-learn main, which includes the faster k-means++ of #35140. - scikit-learn-intelex KMeans:
KMeansof scikit-learn-intelex 2026.1, Lloyd in oneDAL, with the same greedy k-means++ andtolas scikit-learn. Only on the x86 CPUs, and a fit that falls back to scikit-learn fails the case. - scikit-learn Elkan:
KMeans(algorithm="elkan"), only on the 3D Road Network, since it only pays off in low dimension. - sklearn-contrib-emeans:
EMeansof sklearn-contrib-emeans 0.2.1, e-means in Cython, with a random or k-means|| init. The runs withrevival="greedy"use 0.4.0: a cluster is replaced by half of another one only when this is estimated to lower the inertia, for a longer fit. Its GEMMs go through SciPy's BLAS: MKL (conda-forge NumPy and SciPy) on the Intel CPUs, and OpenBLAS (PyPI wheels) on the others. - sklearn-contrib-emeans (PyTorch): the same
EMeans(0.3.0, 0.4.0 withrevival="greedy") on PyTorch tensors on the GPU, through the array API (array_api_dispatch=True): XPU on the Intel GPUs, MPS on the Apple M2. The k-means|| init ends with a k-means++ on the host. - FAISS Lloyd (GPU):
faiss.Kmeans1.16, Lloyd with a random init and a fixed number of iterations (niter). By default FAISS subsamples to 256 samples per cluster: here it trains on all the samples, unless the settings showmax_points_per_centroid=256. Its training loop runs on the host and only the nearest center search runs on the GPU, so its time includes the transfers of every iteration. - FAISS e-means (NumPy):
NumpyEmeansoffaiss.contrib.e_means1.16, the reference implementation of the paper, in NumPy with FAISS's nearest neighbor search. - FAISS e-means (Triton, FP32):
QuantizedEmeans(quantizer=None), e-means on PyTorch tensors with FAISS's Triton kernels, in float32. - FAISS e-means (BF16):
Emeanswith its defaults, which turn the float32 input into bfloat16 operands (reduced precision). - cuML KMeans: RAPIDS cuML
KMeans. Its"k-means++"init is greedy k-means++, and"scalable-k-means++"is k-means||. - CuPy k-means (fused kernels): Lloyd of
kmeans_lloyd,
one CUDA kernel per iteration compiled by CuPy: a tiled float32 GEMM with a running
argmin over the centers, so the distance matrix is never written, then atomic adds
of each sample to the sum of its new center. Greedy k-means++ or random init, and
tolas in scikit-learn. Its version with plain CuPy array operations is ~1.7x slower and not plotted.
Settings don't mean the same thing everywhere, which is why the hover shows the
iterations next to the time. tol is relative to the mean feature
variance in scikit-learn, and an absolute change of the inertia in
cuML. FAISS Lloyd and e-means have no tolerance: their budget is
niter or n_epochs (passes over the data, fractional
allowed). The batch size and step size of e-means come from the paper's scaling
laws, and batch_law="quality" uses 8x smaller batches.
20 Newsgroups and RCV1 are text, as sparse CSR matrices with 130k and 47k
features. Only scikit-learn Lloyd and sklearn-contrib-emeans take sparse input, so
they are the only ones on these plots. scikit-learn-intelex accepts CSR input but
makes it dense during the fit when tol isn't 0 (151 GB on RCV1,
#3559),
so it doesn't run there. Lloyd gets
slow there (~50 s per iteration on RCV1 with 1024 clusters on 24 cores), so it only
runs up to 30 iterations, and not on RCV1 with 1024 clusters.
Where these results come from (46 sources)
| Recorded | Hardware | Records | Source | Envs | Config |
|---|---|---|---|---|---|
| 2026-11-18 | Intel Core Ultra desktop | 108 |
Manual run
· 93352b87 by Arthur Lacote
|
intel |
configs/kmeans_pareto.py |
| 2026-11-17 | Intel Core Ultra desktop | 144 |
Manual run
· 602114ca by Arthur Lacote
|
intel |
configs/kmeans_pareto.py |
| 2026-11-17 | Intel Core Ultra laptop | 168 |
Manual run
· 8a8f154a by Arthur Lacote
|
intel |
configs/kmeans_pareto.py |
| 2026-11-17 | High-end Intel Xeon server | 252 |
Manual run
· 4340e4ff by Arthur Lacote
|
intel |
configs/kmeans_pareto.py |
| 2026-11-15 | Apple M2 laptop | 140 |
Manual run
· be37d402 by Arthur Lacote
|
sklearn-contrib-emeans, sklearn-contrib-emeans-mps |
configs/kmeans_pareto.py |
| 2026-11-15 | Intel Core Ultra desktop | 210 |
Manual run
· 769a44f1 by Arthur Lacote
|
sklearn-contrib-emeans-mkl, sklearn-contrib-emeans-xpu |
configs/kmeans_pareto.py |
| 2026-11-15 | High-end Intel Xeon server | 120 |
Manual run
· 9f7a3444 by Arthur Lacote
|
sklearn-contrib-emeans-mkl |
configs/kmeans_pareto.py |
| 2026-11-15 | 64-core AMD EPYC VM | 120 |
Manual run
· 901cddb5 by Arthur Lacote
|
sklearn-contrib-emeans |
configs/kmeans_pareto.py |
| 2026-11-15 | Intel Core Ultra laptop | 140 |
Manual run
· 850f4bbc by Arthur Lacote
|
sklearn-contrib-emeans-mkl, sklearn-contrib-emeans-xpu |
configs/kmeans_pareto.py |
| 2026-11-13 | Apple M2 laptop | 64 |
Manual run
· 013028dc by Arthur Lacote
|
sklearn-contrib-emeans, sklearn-dev@scikit-learn:main |
configs/kmeans_pareto.py |
| 2026-11-13 | 64-core AMD EPYC VM | 90 |
Manual run
· c8d838d5 by Arthur Lacote
|
sklearn-contrib-emeans, sklearn-dev@scikit-learn:main |
configs/kmeans_pareto.py |
| 2026-11-13 | Intel Core Ultra desktop | 78 |
Manual run
· b22240a7 by Arthur Lacote
|
sklearn-contrib-emeans-mkl, sklearn-dev@scikit-learn:main |
configs/kmeans_pareto.py |
| 2026-11-13 | Intel Core Ultra laptop | 53 |
Manual run
· 155d09f9 by Arthur Lacote
|
sklearn-contrib-emeans-mkl, sklearn-dev@scikit-learn:main |
configs/kmeans_pareto.py |
| 2026-11-13 | High-end Intel Xeon server | 90 |
Manual run
· 5be1cfcf by Arthur Lacote
|
sklearn-contrib-emeans-mkl, sklearn-dev@scikit-learn:main |
configs/kmeans_pareto.py |
| 2026-11-13 | Apple M2 laptop | 1 |
Manual run
· e48d86c6 by Arthur Lacote
|
sklearn-contrib-emeans-mps |
configs/kmeans_pareto.py |
| 2026-11-13 | Apple M2 laptop | 119 |
Manual run
· 8396aa90 by Arthur Lacote
|
sklearn-contrib-emeans-mps |
configs/kmeans_pareto.py |
| 2026-11-13 | Intel Core Ultra laptop | 131 |
Manual run
· 8b50e4ca by Arthur Lacote
|
sklearn-contrib-emeans-xpu, sklearn-dev@scikit-learn:main |
configs/kmeans_pareto.py |
| 2026-11-13 | Intel Core Ultra desktop | 192 |
Manual run
· a1527ea8 by Arthur Lacote
|
sklearn-contrib-emeans-xpu, sklearn-dev@scikit-learn:main |
configs/kmeans_pareto.py |
| 2026-11-13 | NVIDIA L4 VM | 96 |
Manual run
· a7163970 by Arthur Lacote
|
faiss-gpu |
configs/kmeans_pareto.py |
| 2026-11-13 | High-end Intel Xeon server | 163 |
Manual run
· e9d0bbfc by Arthur Lacote
|
sklearn-contrib-emeans-mkl |
configs/kmeans_pareto.py |
| 2026-11-13 | Intel Core Ultra desktop | 116 |
Manual run
· 476757e3 by Arthur Lacote
|
sklearn-contrib-emeans-mkl |
configs/kmeans_pareto.py |
| 2026-11-13 | 64-core AMD EPYC VM | 115 |
Manual run
· a3000624 by Arthur Lacote
|
sklearn-contrib-emeans-mkl |
configs/kmeans_pareto.py |
| 2026-11-13 | NVIDIA L4 VM | 294 |
Manual run
· 4c41b5e0 by Arthur Lacote
|
cuml, faiss-gpu, skl-nvidia |
configs/kmeans_pareto.py, configs/kmeans_pareto_reference.py |
| 2026-11-13 | Intel Core Ultra laptop | 103 |
Manual run
· 4091bf4a by Arthur Lacote
|
sklearn-contrib-emeans-mkl |
configs/kmeans_pareto.py |
| 2026-11-13 | Intel Core Ultra desktop | 190 |
Manual run
· e2836185 by Arthur Lacote
|
emeans-rs, sklearn-contrib-emeans-mkl |
configs/kmeans_pareto.py |
| 2026-11-13 | High-end Intel Xeon server | 143 |
Manual run
· 65c1c68f by Arthur Lacote
|
emeans-rs, sklearn-contrib-emeans-mkl |
configs/kmeans_pareto.py |
| 2026-11-13 | 64-core AMD EPYC VM | 191 |
Manual run
· 8e704ad7 by Arthur Lacote
|
emeans-rs, sklearn-contrib-emeans-mkl |
configs/kmeans_pareto.py |
| 2026-11-13 | Intel Core Ultra laptop | 101 |
Manual run
· 1084974c by Arthur Lacote
|
emeans-rs, sklearn-contrib-emeans-mkl |
configs/kmeans_pareto.py |
| 2026-11-13 | Apple M2 laptop | 84 |
Manual run
· 84de34a9 by Arthur Lacote
|
emeans-rs |
configs/kmeans_pareto.py |
| 2026-11-12 to 2026-11-13 | Apple M2 laptop | 275 |
Manual run
· ab9d1500 by Arthur Lacote
|
sklearn-contrib-emeans, sklearn-dev@cakedev0:emeans, sklearn-dev@scikit-learn:main |
configs/kmeans_pareto.py |
| 2026-11-12 to 2026-11-13 | High-end Intel Xeon server | 180 |
Manual run
· 5038b0ff by Arthur Lacote
|
sklearn-contrib-emeans |
configs/kmeans_pareto.py |
| 2026-11-12 to 2026-11-13 | Intel Core Ultra desktop | 180 |
Manual run
· 20c08e9a by Arthur Lacote
|
sklearn-contrib-emeans |
configs/kmeans_pareto.py |
| 2026-11-12 | 64-core AMD EPYC VM | 180 |
Manual run
· 47b5b48b by Arthur Lacote
|
sklearn-contrib-emeans |
configs/kmeans_pareto.py |
| 2026-11-12 | Intel Core Ultra laptop | 120 |
Manual run
· b30a3584 by Arthur Lacote
|
sklearn-contrib-emeans |
configs/kmeans_pareto.py |
| 2026-11-12 | NVIDIA L4 VM | 840 |
Manual run
· fcab2256 by Arthur Lacote
|
cuml, faiss-gpu, skl-nvidia |
configs/kmeans_pareto.py, configs/kmeans_pareto_reference.py |
| 2026-11-12 | Intel Core Ultra laptop | 239 |
Manual run
· c019760c by Arthur Lacote
|
faiss-cpu, sklearn-dev@cakedev0:emeans, sklearn-dev@scikit-learn:main |
configs/kmeans_pareto.py |
| 2026-11-11 to 2026-11-12 | Apple M2 laptop | 155 |
Manual run
· 75650273 by Arthur Lacote
|
sklearn-dev@cakedev0:emeans, sklearn-dev@scikit-learn:main |
configs/kmeans_pareto.py |
| 2026-11-12 | High-end Intel Xeon server | 389 |
Manual run
· 9c416e03 by Arthur Lacote
|
faiss-cpu, sklearn-dev@cakedev0:emeans, sklearn-dev@scikit-learn:main |
configs/kmeans_pareto.py |
| 2026-11-12 | Intel Core Ultra desktop | 359 |
Manual run
· 9c416e03 by Arthur Lacote
|
faiss-cpu, sklearn-dev@cakedev0:emeans, sklearn-dev@scikit-learn:main |
configs/kmeans_pareto.py |
| 2026-11-12 | 64-core AMD EPYC VM | 73 |
Manual run
· 9c416e03 by Arthur Lacote
|
sklearn-dev@cakedev0:emeans |
configs/kmeans_pareto.py |
| 2026-11-12 | 64-core AMD EPYC VM | 316 |
Manual run
· 79117a86 by Arthur Lacote
|
faiss-cpu, sklearn-dev@cakedev0:emeans, sklearn-dev@scikit-learn:main |
configs/kmeans_pareto.py |
| 2026-11-11 to 2026-11-12 | Intel Core Ultra laptop | 239 |
Manual run
· af6b7497 by Arthur Lacote
|
faiss-cpu, sklearn-dev@cakedev0:emeans, sklearn-dev@scikit-learn:main |
configs/kmeans_pareto.py |
| 2026-11-12 | Intel Core Ultra desktop | 185 |
Manual run
· adab1293 by Arthur Lacote
|
faiss-cpu |
configs/kmeans_pareto.py |
| 2026-11-11 to 2026-11-12 | Intel Core Ultra desktop | 190 |
Manual run
· 001b6c52 by Arthur Lacote
|
sklearn-dev@scikit-learn:main |
configs/kmeans_pareto.py |
| 2026-11-11 to 2026-11-12 | High-end Intel Xeon server | 418 |
Manual run
· 1423a183 by Arthur Lacote
|
faiss-cpu, sklearn-dev@scikit-learn:main |
configs/kmeans_pareto.py |
| 2026-11-11 to 2026-11-12 | 64-core AMD EPYC VM | 418 |
Manual run
· 1423a183 by Arthur Lacote
|
faiss-cpu, sklearn-dev@scikit-learn:main |
configs/kmeans_pareto.py |
GloVe-200, 64 clusters
1,183,514 samples x 200 features, best known inertia 33.0413 per sample
median over seeds; whiskers: min to max over seeds; faded: off the front; hover a point for its settings
GloVe-200, 256 clusters
1,183,514 samples x 200 features, best known inertia 31.6486 per sample
median over seeds; whiskers: min to max over seeds; faded: off the front; hover a point for its settings
GloVe-200, 1024 clusters
1,183,514 samples x 200 features, best known inertia 30.265 per sample
median over seeds; whiskers: min to max over seeds; faded: off the front; hover a point for its settings
SIFT1M, 64 clusters
1,000,000 samples x 128 features, best known inertia 65691.4 per sample
median over seeds; whiskers: min to max over seeds; faded: off the front; hover a point for its settings
SIFT1M, 256 clusters
1,000,000 samples x 128 features, best known inertia 57302.3 per sample
median over seeds; whiskers: min to max over seeds; faded: off the front; hover a point for its settings
SIFT1M, 1024 clusters
1,000,000 samples x 128 features, best known inertia 50257.6 per sample
median over seeds; whiskers: min to max over seeds; faded: off the front; hover a point for its settings
CLIP ViT-B/32, 64 clusters
1,000,000 samples x 512 features, best known inertia 0.229413 per sample
median over seeds; whiskers: min to max over seeds; faded: off the front; hover a point for its settings
CLIP ViT-B/32, 256 clusters
1,000,000 samples x 512 features, best known inertia 0.198713 per sample
median over seeds; whiskers: min to max over seeds; faded: off the front; hover a point for its settings
CLIP ViT-B/32, 1024 clusters
1,000,000 samples x 512 features, best known inertia 0.173024 per sample
median over seeds; whiskers: min to max over seeds; faded: off the front; hover a point for its settings
SUSY, 64 clusters
5,000,000 samples x 18 features, best known inertia 3.60871 per sample
median over seeds; whiskers: min to max over seeds; faded: off the front; hover a point for its settings
SUSY, 256 clusters
5,000,000 samples x 18 features, best known inertia 2.53221 per sample
median over seeds; whiskers: min to max over seeds; faded: off the front; hover a point for its settings
SUSY, 1024 clusters
5,000,000 samples x 18 features, best known inertia 1.78601 per sample
median over seeds; whiskers: min to max over seeds; faded: off the front; hover a point for its settings
YearPredictionMSD (standardized), 64 clusters
515,345 samples x 90 features, best known inertia 60.765 per sample
median over seeds; whiskers: min to max over seeds; faded: off the front; hover a point for its settings
YearPredictionMSD (standardized), 256 clusters
515,345 samples x 90 features, best known inertia 54.0912 per sample
median over seeds; whiskers: min to max over seeds; faded: off the front; hover a point for its settings
YearPredictionMSD (standardized), 1024 clusters
515,345 samples x 90 features, best known inertia 48.131 per sample
median over seeds; whiskers: min to max over seeds; faded: off the front; hover a point for its settings
3D Road Network (10x oversampled), 64 clusters
4,348,740 samples x 3 features, best known inertia 20.4843 per sample
median over seeds; whiskers: min to max over seeds; faded: off the front; hover a point for its settings
3D Road Network (10x oversampled), 256 clusters
4,348,740 samples x 3 features, best known inertia 4.10498 per sample
median over seeds; whiskers: min to max over seeds; faded: off the front; hover a point for its settings
3D Road Network (10x oversampled), 1024 clusters
4,348,740 samples x 3 features, best known inertia 0.856148 per sample
median over seeds; whiskers: min to max over seeds; faded: off the front; hover a point for its settings
20 Newsgroups (sparse), 64 clusters
18,846 samples x 130107 features, best known inertia 0.577417 per sample
median over seeds; whiskers: min to max over seeds; faded: off the front; hover a point for its settings
20 Newsgroups (sparse), 256 clusters
18,846 samples x 130107 features, best known inertia 0.54476 per sample
median over seeds; whiskers: min to max over seeds; faded: off the front; hover a point for its settings
20 Newsgroups (sparse), 1024 clusters
18,846 samples x 130107 features, best known inertia 0.480526 per sample
median over seeds; whiskers: min to max over seeds; faded: off the front; hover a point for its settings
RCV1 (sparse), 64 clusters
804,414 samples x 47236 features, best known inertia 0.894752 per sample
median over seeds; whiskers: min to max over seeds; faded: off the front; hover a point for its settings
RCV1 (sparse), 256 clusters
804,414 samples x 47236 features, best known inertia 0.831641 per sample
median over seeds; whiskers: min to max over seeds; faded: off the front; hover a point for its settings
RCV1 (sparse), 1024 clusters
804,414 samples x 47236 features, best known inertia 0.742813 per sample
median over seeds; whiskers: min to max over seeds; faded: off the front; hover a point for its settings