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: KMeans of scikit-learn-intelex 2026.1, Lloyd in oneDAL, with the same greedy k-means++ and tol as 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: EMeans of sklearn-contrib-emeans 0.2.1, e-means in Cython, with a random or k-means|| init. The runs with revival="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 with revival="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.Kmeans 1.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 show max_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): NumpyEmeans of faiss.contrib.e_means 1.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): Emeans with 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 tol as 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)
RecordedHardwareRecordsSourceEnvsConfig
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
CPU implementations
GPU implementations
Machines

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