IVF Index: Clustering-Based Vector Search & Partitioning › Summary

The IVF index partitions the vector space using k-means clustering, organizing vectors into cells defined by their nearest centroid. At query time, only the $\texttt{nprobe}$ closest cells are searched, sharply reducing the number of distance computations from $n$ to roughly $\texttt{nprobe} \times n/k$. The key takeaways from this chapter are:

• Clustering as partitioning: K-means divides the space into Voronoi cells, and each cell maintains an inverted list of its member vectors. The number of centroids $k$ (typically between $4\sqrt{n}$ and $16\sqrt{n}$, where $n$ is the number of vectors) controls the granularity of the partitioning.
• nprobe controls the tradeoff: Searching more cells improves recall but increases latency linearly. The sweet spot depends on your data distribution and accuracy requirements.
• IVF-PQ for scale: Combining IVF with Product Quantization compresses vectors from full precision to compact codes (often 8 to 32 bytes per vector) and lets billion-scale search with limited memory.
• IVF vs HNSW: IVF excels in large-scale, memory-constrained, and disk-based scenarios. HNSW gives better latency-recall tradeoffs when the dataset fits in memory. Many production systems use elements of both.

In the next chapter, we'll explore Product Quantization, understanding how it compresses high-dimensional vectors into compact codes while maintaining sufficient distance information for effective approximate search.