IVF and Product Quantization
How clustering (IVF) cuts the number of vectors each query compares against, how product quantization compresses vectors 16–64×, and when to prefer IVF-PQ over HNSW.
Two separate problems
At large scale a vector index has two costs:
- Compute: how many vectors each query compares against.
- Memory: how many bytes each stored vector takes.
IVF attacks the first and PQ the second. Combined, they let a single machine search hundreds of millions to billions of vectors.
IVF: inverted file index
Build:
- Run k-means on a sample of vectors to find
nlistcentroids. A common rule of thumb is nlist ≈ √N, which gives about 10,000 clusters for 100M vectors. - Assign every vector to its nearest centroid, storing it in that centroid's list (the "inverted file").
Search:
- Compare the query with all centroids, which is cheap: 10,000 comparisons.
- Scan only the
nprobeclosest clusters, for example nprobe = 32.
With 10,000 clusters and nprobe = 32, each query scans about 0.3% of the data.
Trade-off: a true neighbour sitting just across a cluster boundary is missed unless you probe that cluster too. Raising nprobe raises recall and cost, just like ef_search in HNSW.
Operational notes:
- IVF needs a training step. If your data distribution shifts, for example a new product category or language, clusters become unbalanced and recall drops, so retrain periodically.
- Inserts are cheap: assign the new vector to the nearest centroid.
- IVF scans are sequential reads of lists, which suits SSDs and GPUs better than random graph hops.
Product quantization (PQ)
A 768-dim float32 vector is 3,072 bytes. PQ compresses it:
- Split the vector into m sub-vectors, for example m = 96 sub-vectors of 8 dims each.
- For each sub-space, learn 256 centroids with k-means (a "codebook").
- Replace each sub-vector with the id of its nearest centroid, which fits in 1 byte.
Now each vector is stored as m bytes: 96 bytes instead of 3,072, 32× smaller.
Searching with PQ codes: for a query, precompute a small table of distances from each query sub-vector to all 256 centroids in its sub-space. The approximate distance to any stored vector is then m table lookups and additions, which is very fast.
Rescoring (refinement)
PQ distances are approximate, so the top results can come in the wrong order. The standard fix:
- Use the compressed index to fetch the top 100–1,000 candidates.
- Load their full-precision vectors from SSD or a separate store.
- Recompute exact distances and return the true top k.
This recovers most of the recall lost to compression, while RAM holds only the codes. The same pattern works for int8 and binary quantization.
Other quantization schemes
| Scheme | Size vs float32 | Notes |
|---|---|---|
| Scalar (float16 / int8) | 2× / 4× | Simple, small recall loss. Works with HNSW |
| Binary (1 bit per dim) | 32× | Hamming distance is extremely fast. Needs rescoring. Works best with high-dim models trained for it |
| Product quantization | 16–64× typical | Tunable. Classic partner for IVF |
HNSW or IVF-PQ?
| Situation | Prefer |
|---|---|
| Up to ~50–100M vectors, RAM budget OK, highest recall and lowest latency | HNSW (maybe with int8) |
| Hundreds of millions to billions of vectors, memory cost dominates | IVF-PQ with rescoring, or a disk-based graph |
| Heavy real-time inserts | HNSW (IVF needs occasional retraining) |
| GPU-accelerated batch search | IVF variants (e.g. FAISS, cuVS) |
Key takeaways
- IVF clusters vectors around centroids (k-means) and searches only the nprobe nearest clusters.
- Product quantization splits each vector into m sub-vectors and stores a 1-byte centroid id for each, so a vector costs m bytes.
- IVF-PQ is the classic billion-scale index. It is compact and fast, but distances are approximate, so rescore the top candidates.
- Choose HNSW for best recall in RAM, and IVF-PQ or disk-based indexes when memory cost dominates.