A Super Fast K-means for Indexing Vector Embeddings

Leonardo Kuffo, Sven Hepkema, Peter Boncz
3/20/2026
cs.LGcs.DBcs.IR

Official code: cwida/SuperKMeans (91 stars, MIT, last commit 2026-04-29).

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

View on arXivView PDF

Code Implementations(1)

cwida/SuperKMeansOfficial100%
MIT

⚡ Super fast clustering for high-dimensional vectors on CPUs (x86, ARM) and GPUs — for Python and C++. 100x faster clustering of vector embeddings than FAISS

919C++, CMakeOct 22, 20255 months agoMIT
approximate-nearest-neighbor-searchclusteringivfk-meanskmeans+4 more

Similar Papers

MODE: Mixture of Document Experts for RAG

83% match2025

Ranking Vectors Clustering: Theory and Applications

81% match2025

Large-Scale Data Parallelization of Product Quantization and Inverted Indexing Using Dask

81% match2026

LeanVec: Searching vectors faster by making them fit

80% match2 repos2292023

SPINEX-Clustering: Similarity-based Predictions with Explainable Neighbors Exploration for Clustering Problems

80% match2024

Geometric-k-means: A Bound Free Approach to Fast and Eco-Friendly k-means

79% match2025

Cite this paper

@article{kuffo2026super,
  title  = {A Super Fast K-means for Indexing Vector Embeddings},
  author = {Leonardo Kuffo and Sven Hepkema and Peter Boncz},
  year   = {2026},
  eprint = {2603.20009},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2603.20009v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2603.20009.svg)](https://codeofpaper.com/paper/2603.20009)

Discussion