A Super Fast K-means for Indexing Vector Embeddings

Leonardo Kuffo; Sven Hepkema; Peter Boncz

cs.LGMar 20, 2026

A Super Fast K-means for Indexing Vector Embeddings

Authors: Leonardo Kuffo, Sven Hepkema, Peter Boncz

Organizations: CWI, Amsterdam, The Netherlands · Systems Group, ETH Zurich, Zurich, Switzerland

Abstract

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

Figures & tables

Figure 1. Clustering performance for all competitors in the OpenAI dataset with 1M vector embeddings of 1536 dimensions. SuperKMeans performs exceptionally well as the number of clusters increases (up to 7x faster on CPU and 4x on GPU), making it attractive for indexing large embedding collections. The evaluation framework is presented in Section 4 .

Symbol	Definition
$X$	Matrix of data vectors
$x$	A vector from $X$
$N$	Number of data vectors
$Y$	Matrix of clusters’ centroids
$y$	A centroid from $Y$
$k$	Number of clusters to compute with $k$ -means

Table 1. Terminology

Figure 2. Example of an IVF index search where only the points in the clusters closest to the query are explored. The clusters are defined via k-means. In high-dimensional vectors, the boundaries of these clusters are not well-defined. This fuzziness makes k-means++ initialization ineffective.

Figure 3. SuperKMeans divides an iteration into two phases: i) GEMM: Computes partial distances with the front d’ dimensions, and ii) PRUNING: prunes the d” dimensions of the centroids unlikely to be the assignment of a vector.

Microarchitecture	CPU Model	Freq.	L1	L2	L3	BLAS
Microarchitecture	CPU Model	GHz	KiB	MiB	MiB	Library
Intel Granite Rapids	Xeon 6975P-C	3.9	48	2	480	IntelMKL
AMD Zen 5	EPYC 9R45	4.5	48	1	32	AOCL-BLIS
AMD Zen 3	EPYC 7R13	3.6	32	0.5	16	AOCL-BLIS
AWS Graviton 4	Neoverse V2	2.8	64	2	36	OpenBlas
Apple M4 Pro	M4 Pro	4.5	128	16	-	Accelerate

Table 2. Hardware used for evaluation. All machines have 256GB of RAM and 32 threads, except Apple M4, which has 24GB of RAM and 14 threads.

Name	Embeddings	Model	# Vectors	Dim.	Size (GB) $\uparrow$
Cohere	Text	EmbedV3-EN	10,000,000	1024	40.96
arXiv	Text	InstructorXL	2,253,000	768	6.92
OpenAI	Text	OpenAI	999,000	1536	6.14
Wiki	Text	OpenAI	260,372	3072	3.20
MXBAI	Text	MXBAI	769,382	1024	3.15
Contriever	Text	Contriever	999,000	768	3.07

Table 3. Vector embedding datasets used for evaluation

Figure 4. Clustering performance (CPU) for all competitors with the number of clusters (k) set to $4*\sqrt{N}$ . SuperKMeans outperforms the competitors, particularly in high-dimensional datasets (d > 384), where it achieves 3-4x faster clustering.

Dataset	Algorithm	$k$	Build	Recall	Recall	Vectors	WCSS
Dataset	Algorithm	$k$	Time (s)	@100	@10	explored	( $\times 10^{4}$ )
Cohere	SuperKMeans	12649	610.2	0.886	0.905	109721	508.22
Cohere	FAISS	12649	2776.3	0.887	0.906	110834	506.47
arXiv	SuperKMeans	6003	69.55	0.931	0.969	24429	38.27
arXiv	FAISS	6003	224.92	0.931	0.969	24435	38.25
OpenAI	SuperKMeans	3997	33.63	0.859	0.897	10795	62.14

Table 4. Quality of the generated centroids for VSS tasks. To measure recall, we do top-10 and top-100 IVF index search and explore 1% of the total centroids (

k

). The quality of the centroids produced by SuperKMeans is on-par to the ones produced by FAISS, both in terms of recall and clusters’ balance, while providing up to 4x faster build times.

Figure 5. Speedup of SuperKMeans (CPU) against all competitors at different values of $k$ . SuperKMeans performs exceptionally well as the number of clusters increases. Conversely, for smaller values of $k$ , SuperKMeans is on par with the competitors.

Figure 6. The impact of early termination on VSS tasks. ETR generally results in earlier termination compared to FAISS, with minimal effect on recall. In contrast, the early termination in Scikit-Learn occurs much later, resulting in negligible improvements relative to the computational effort. Note: Scikit-Learn is not plotted in the datasets that need an angular distance, since this is an unsupported feature.

Figure 7. In terms of the number of vectors explored during VSS, the datasets exhibit two distinct patterns as iterations progress: i) the number of vectors explored increases (Cohere, OpenAI) or ii) the number of vectors explored decreases (arXiv, ImageNet). These trends are effects of the cluster-balancing and refinement properties of our algorithm. However, the relative differences in the number of vectors explored across iterations are small.

Figure 8. Sampling has minimal impact on search quality (1st and 3rd columns). However, it results in less balanced clusters (2nd and 4th columns), thus increasing the number of vectors explored during VSS. Sampling 20-30% of the data is enough to strike a balance between and balance.

Figure 9. Clustering time achieved with varying number of threads in the arXiv/768 dataset. Speedup factor between thread scaling is annotated. SuperKMeans scales almost linearly to the number of threads on the CPU.

Stage	arXiv/768	Cohere/1024	OpenAI/1536
Core Loop (25 iters.)	62.3s (94.0%)	533.4s (96.6%)	26.6s (85.9%)
- GEMM	- 29.8s (44.9%)	- 260.0s (47.1%)	- 12.2s (39.4%)
- PRUNING	- 18.9s (28.5%)	- 132.8s (24.1%)	- 8.0s (25.7%)
- 1st Iteration	- 8.8s (13.2%)	- 96.9s (17.5%)	- 5.0s (16.1%)
- L2 Identity	- 4.7s (7.2%)	- 42.4s (7.7%)	- 1.4s (4.6%)
Random Rotation	1.0s (1.6%)	5.0s (0.9%)	1.9s (6.0%)

Table 5. Profiling of SuperKMeans on three datasets. The additional work of SuperKMeans (L2 identity, Random Rotation, Norms Calculation, and PDXification) represents minimal overhead compared to the total runtime.

Variant	GEMM (s)	PRUNING (s)	Other (s)	Total (s)
Baseline (vanilla $k$ -means)	125.1	-	-	125.1
SuperKMeans	16.4	7.5	5.6	29.5
- NO Initial threshold	41.6 (2.5x $\downarrow$ )	8.3 (1.1x $\downarrow$ )	4.2	54.1 (1.83x $\downarrow$ )
SuperKMeans	16.4	7.5	5.6	29.5
- NO PDXification	16.4	8.8 (1.2x $\downarrow$ )	5.7	30.9 (1.05x $\downarrow$ )
- NO Progressive pruning	16.4	44.5 (6.0x $\downarrow$ )	5.5	66.4 (2.25x $\downarrow$ )

Table 6. Ablation study of SuperKMeans key optimizations in the OpenAI/1536 dataset. Progressive pruning and a tighter initial threshold for the PRUNING phase contribute most to SuperKMeans’s high performance.

\downarrow

indicates slowdown.

Figure 10. SuperKMeans still outperforms the competitors in classic vector datasets that do not stem from AI embedding models, showing its portability across vector datasets.

Figure 11. SuperKMeans consistently defeats competitors, achieving speedups across all CPU microarchitectures

Figure 12. The effect of initialization mechanisms on the resulting centroids for VSS tasks. $k$ -means++ proves to be excessive, as its initialization is 10-100x slower.

Figure 13. Scikit-Learn’s Lloyd’s is faster than other $k$ -means variants thanks to its use of GEMM routines. SuperKMeans is the best of both worlds: pruning distance computations while leveraging GEMM routines.

Figure 14. Speedup of SuperKMeans against all competitors at different values of $k$ in NVIDIA H100 GPU. SuperKMeans performs exceptionally well as the number of clusters increases. Conversely, for smaller values of $k$ , SuperKMeans loses to cuVS due to the preprocessing steps of SuperKMeans not being offloaded to the GPU. Note: cuVS crashes in the Cohere dataset.

Dataset	$k$	SuperKMeans			FAISS
Dataset	$k$	CPU	GPU	Speedup	CPU	GPU	Speedup
Cohere	10,000	747.2	116.5	6.4 $\times$	2459.5	261.9	9.4 $\times$
arXiv		144.0	17.0	8.4 $\times$	345.7	45.6	7.6 $\times$
OpenAI		74.7	13.4	5.6 $\times$	301.6	39.9	7.6 $\times$
Wiki		33.8	9.0	3.8 $\times$	194.0	17.3	11.2 $\times$
MXBAI		53.9	7.7	7.0 $\times$	188.8	20.6	9.1 $\times$

Table 7. Comparison of clustering time (s) on CPU and GPU

Dataset	Algorithm	$k$	Build	Recall	Vectors	WCSS	PPC	PPC
Dataset	Algorithm	$k$	Time (s)	@100	explored (%)	( $\times 10^{5}$ )	Mean	Std. Dev.
ImageNet	Vanilla	4527	10.50	0.975	1.01	2.93	283.0	110.5
ImageNet	Hierarchical	4527	1.68	0.969	0.96	3.01	283.0	119.7
MXBAI	Vanilla	3508	8.12	0.920	1.12	1014.68	219.3	97.1
MXBAI	Hierarchical	3508	1.84	0.903	1.01	1047.21	219.3	91.9
Wiki	Vanilla	2041	5.76	0.863	1.09	1.61	127.6	69.9

Table 8. Quality of the generated centroids for VSS tasks between Vanilla and Hierarchical SuperKMeans. The quality of the centroids produced by Hierarchical SuperKMeans is slightly inferior in terms of recall. However, it results in more balanced clusters. PPC stands for Points per Cluster.

Clustering

Clustering groups data points by shared structure, developing methods to discover, validate, and interpret groups across diverse data and constraints.

See all 345 papers

Efficient Multivector Retrieval with Token-Aware Clustering and Hierarchical Indexing
Apr 30, 2026Silvio Martinico, Franco Maria Nardini, Cosimo Rulli +1Clustering Vector Quantization
University of Pisa & ISTI–CNR · Pisa, Italy · ISTI–CNR +1
No More K-means: Single-Stage Sparse Coding for Efficient Multi-Vector Retrieval
May 28, 2026Lixuan Guo, Yifei Wang, Tiansheng Wen +3Learned Sparse Retrieval Multi-Vector Retrieval
Stony Brook University · Xidian University · Amazon AGI SF Lab +4
Panorama: Fast-Track Nearest Neighbors
Oct 1, 2025Vansh Ramani, Alexis Schlomer, Akash Nayar +3Product Quantization Approximate Nearest Neighbor Search
IIT Delhi & CMU & UCPH · Carnegie Mellon University · Indian Institute of Technology Delhi +1

Apr 30, 2026J/K move · Enter open · S save

Efficient Multivector Retrieval with Token-Aware Clustering and Hierarchical Indexing

Silvio Martinico, Franco Maria Nardini, Cosimo Rulli, Rossano Venturini

University of Pisa & ISTI–CNR · Pisa, Italy · ISTI–CNR+1

Clustering Vector Quantization Multi-Vector Retrieval Product Quantization

Open paper AskPDF arXiv

Multivector retrieval models achieve state-of-the-art effectiveness through fine-grained token-level representations, but their deployment incurs substantial computational and memory costs. Current solutions, based on the well-known k-means clustering algorithm, group similar vectors together to enable both effective compression and efficient retrieval. However, standard k-means scales poorly with the number of clusters and dataset size, and favours frequent tokens during training while underrepresenting rare, discriminative ones. In this work, we introduce TACHIOM, a multivector retrieval system that exploits token-level structure to significantly accelerate both clustering and retrieval. By accounting for tokens' distribution during centroid allocation, TACHIOM easily scales to millions of centroids, enabling highly accurate document scoring using only centroids, avoiding expensive token-level computation. TACHIOM combines a graph-based index over centroids with an optimized Product Quantization layout for efficient final scoring. Experiments on MS-MARCOv1 and LoTTE show that TACHIOM achieves up to

247\times

faster clustering than k-means and up to

9.8\times

retrieval speedup over state-of-the-art systems while maintaining comparable or superior effectiveness.

Abstract

Clustering

Explore similar work

Efficient Multivector Retrieval with Token-Aware Clustering and Hierarchical Indexing

No More K-means: Single-Stage Sparse Coding for Efficient Multi-Vector Retrieval

Panorama: Fast-Track Nearest Neighbors