Advanced8 min read

IVF & Product Quantization

IVF splits vectors into clusters so search only scans a few of them; Product Quantization shrinks each vector into a tiny code — together they let huge indexes fit in memory and search fast.

Explain like I'm new to AI

HNSW is fast but memory-hungry. At billions of vectors, two other techniques take over — often combined.

IVF (Inverted File index) groups vectors into clusters. At query time you only search the few nearest clusters, not everything.
Product Quantization (PQ) compresses each vector into a handful of bytes, so far more vectors fit in RAM.

Mental model

IVF is like a library organized into sections: to find a book you go to the right sections, not every shelf.
PQ is like replacing each detailed book with a short summary card — much smaller to store, still enough to find what you need.

How it works — IVF

Cluster all vectors into k groups (via k-means); each group has a centroid.
Store each vector in the "inverted list" of its nearest centroid.
At query time, find the nprobe nearest centroids and search only those lists.

More nprobe → higher recall, slower; fewer → faster, more misses.

How it works — Product Quantization

1. Split the vector into sub-vectors

0.21-0.44

0.870.12

-0.630.35

-0.090.52

2. Replace each with its nearest centroid ID

#37#12#200#88

Original

32 bytes

8 floats × 4B

Compressed

4 bytes

4 codes × 1B

Smaller

8×

less memory

Product Quantization compresses vectors into compact codes — huge memory savings for a small accuracy cost.

Split each vector into several sub-vectors.
For each slice, learn a small codebook of representative centroids.
Replace each sub-vector with the ID of its nearest centroid — the vector becomes a few bytes.
Compare using the codes (with precomputed distance tables) — approximate, but tiny and fast.

Real-world example

To serve a billion vectors on limited RAM, a common recipe is IVF + PQ: IVF restricts the search to a few clusters, and PQ makes each stored vector ~8–32× smaller. You trade a little accuracy for the ability to run massive search economically — often with an exact re-rank of the finalists to recover precision.

Technical explanation

IVF cost/recall is set by the number of clusters and nprobe.
PQ trades accuracy for compression: more sub-quantizers/bits → better accuracy, less compression. Scalar quantization (e.g. float32 → int8) is a simpler cousin.
These compose with graph indexes too (e.g. HNSW over PQ-compressed vectors). Matryoshka embeddings offer a complementary axis: shrink dimensions before quantizing.
Standard practice: shortlist with the compressed/approximate index, then re-rank the top candidates with full-precision vectors.

Common mistakes

Common mistake

Cranking compression too high and destroying recall. PQ is lossy — validate accuracy, and re-rank the shortlist with full-precision vectors when precision matters.

Setting nprobe too low and silently missing relevant clusters.
Assuming compression is free — it always costs some accuracy.

When to use it

Very large (tens of millions to billions) or memory-constrained indexes where HNSW alone is too big.

When NOT to use it

Small/medium datasets where HNSW (or even exact search) is simpler and accurate.

Alternatives

HNSW for in-memory, high-recall search; scalar quantization for simpler compression.

Quick quiz

Related concepts

What is HNSW? — HNSW is a graph-based ANN index that searches from sparse top layers down to dense bottom layers, giving fast, high-recall nearest-neighbor search.
What are Matryoshka Embeddings? — Matryoshka embeddings pack the most important information into the first dimensions, so you can shorten the vector to save space and speed with minimal quality loss.