Reproduce “A Super Fast K-means for Indexing Vector Embeddings” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Leonardo Kuffo, Sven Hepkema, Peter Boncz

Researchers at CWI and ETH Zurich developed SuperKMeans, a k-means variant engineered for rapid clustering of high-dimensional vector embeddings to build vector similarity search indexes. It achieves up to 7x faster clustering than FAISS on CPU while maintaining equivalent retrieval quality and introduces a novel Early Termination by Recall mechanism.

Key insights

  • Efficiently combining GEMM routines for initial partial distance calculations with progressive, adaptive sampling-based pruning significantly reduces data access and compute overhead in high-dimensional k-means.
  • Monitoring VSS recall as a termination criterion allows for quality-driven early stopping, optimizing computational resources without compromising the effectiveness of the generated centroids.
  • For high-dimensional vector embeddings in VSS contexts, simpler random initialization is substantially faster and achieves comparable retrieval quality to more complex k-means++ methods.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.