# A Super Fast K-means for Indexing Vector Embeddings

arXiv: https://arxiv.org/abs/2603.20009 · HTML: https://mlsanity.com/paper/2603.20009/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 74 references that are in the map.
- First posted on arXiv 20 Mar 2026.

## Builds on (most cited first, 21 of 21)

- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms](https://mlsanity.com/paper/1807.05614/) (2018)
- [A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2101.12631/) (2021)
- [A Survey on Locality Sensitive Hashing Algorithms and their Applications](https://mlsanity.com/paper/2102.08942/) (2021)
- [ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data](https://mlsanity.com/paper/2403.04871/) (2024)
- [SPFresh: Incremental In-Place Update for Billion-Scale Vector Search](https://mlsanity.com/paper/2410.14452/) (2024)
- [High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations](https://mlsanity.com/paper/2303.09855/) (2023)
- [PDX: A Data Layout for Vector Similarity Search](https://mlsanity.com/paper/2503.04422/) (2025)
- [Incremental IVF Index Maintenance for Streaming Vector Search](https://mlsanity.com/paper/2411.00970/) (2024)
- [Flash-KMeans: Fast and Memory-Efficient Exact K-Means](https://mlsanity.com/paper/2603.09229/) (2026)
- [MicroNN: An On-device Disk-resident Updatable Vector Database](https://mlsanity.com/paper/2504.05573/) (2025)
- [VIBE: Vector Index Benchmark for Embeddings](https://mlsanity.com/paper/2505.17810/) (2025)
- [CANDY: A Benchmark for Continuous Approximate Nearest Neighbor Search with Dynamic Data Ingestion](https://mlsanity.com/paper/2406.19651/) (2024)
- [SAQ: Pushing the Limits of Vector Quantization through Code Adjustment and Dimension Segmentation](https://mlsanity.com/paper/2509.12086/) (2025)
- [Cloud-Native Vector Search: A Comprehensive Performance Analysis](https://mlsanity.com/paper/2511.14748/) (2025)
- [Curator: Efficient Vector Search with Low-Selectivity Filters](https://mlsanity.com/paper/2601.01291/) (2026)
- [On the Efficiency of K-Means Clustering: Evaluation, Optimization, and Algorithm Selection](https://mlsanity.com/paper/2010.06654/) (2020)
- [B+ANN: A Fast Billion-Scale Disk-based Nearest-Neighbor Index](https://mlsanity.com/paper/2511.15557/) (2025)
- [Accelerating k-Means Clustering with Cover Trees](https://mlsanity.com/paper/2410.15117/) (2024)
- [Scalable Distributed Vector Search via Accuracy Preserving Index Construction](https://mlsanity.com/paper/2512.17264/) (2025)

## Built on by (most cited first, 2 of 2)

- [Dynamic Cluster Data Sampling for Efficient and Long-Tail-Aware Vision-Language Pre-training](https://mlsanity.com/paper/2604.27932/) (2026)
- [Stop Indexing at Full Precision: Revisiting Clustering for Vector Embeddings](https://mlsanity.com/paper/2608.14648/) (2026)

## Abstract (arXiv)

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