HNSW vs. IVF-PQ: when would you choose each?

30-second answer

HNSW for high recall and low latency when the vectors fit in memory and you need incremental inserts. IVF-PQ when scale or memory cost dominates (hundreds of millions to billions of vectors): IVF limits the search to a few clusters and PQ compresses vectors heavily, at some accuracy cost, often with re-ranking on full vectors.

Try answering out loud before reading on. The walkthrough below is paced for a 40-minute interview round.

0–5 min Clarify and frame

Ask about scale (millions vs. billions of vectors), memory budget, update rate, latency target and recall needs. Framing: "Both are ANN indexes optimized for different constraints: HNSW for recall and latency in memory, IVF-PQ for memory efficiency at huge scale."

5–15 min Core explanation

IVF (inverted file):

Train k-means with nlist centroids on a sample of vectors.
Assign each vector to its nearest centroid's list.
At query time, find the nprobe closest centroids and search only their lists.

PQ (product quantization):

Split each vector into m sub-vectors.
For each sub-space, learn 256 centroids (8 bits).
Store each vector as m bytes of codes. A 1024-dim float32 vector (4 KB) with m=64 becomes 64 bytes: 64× smaller.
Distances are approximated using precomputed lookup tables (fast).

IVF-PQ combines them: coarse partitioning plus compressed codes. Often followed by re-ranking candidates with full vectors stored elsewhere.

15–25 min Deep dive: comparison

Aspect	HNSW	IVF-PQ
Memory	High (full vectors + graph)	Very low (codes)
Recall	Very high	Lower; improve with re-ranking
Latency	Very low	Low; depends on `nprobe`
Build	Incremental, no training	Requires training (k-means, codebooks)
Updates	Easy inserts, awkward deletes	Easy adds; drift needs retraining
Scale sweet spot	Up to ~100M in RAM	100M to billions
GPU friendliness	Moderate	Excellent

Tuning IVF: nlist ≈ √N to 4√N as a starting point; raise nprobe until recall targets are met.

25–32 min Decision guidance

Fits in memory, need top recall, frequent inserts: HNSW (optionally with scalar quantization).
Billions of vectors or tight memory budget: IVF-PQ with re-ranking.
GPU batch search (e.g. dedup, offline similarity joins): IVF-PQ on GPU.
Data distribution shifts over time: IVF centroids go stale; schedule retraining.
Middle ground: HNSW over IVF centroids, or disk-based graph indexes for SSD-resident data.

32–37 min Production example

An image-similarity service with 1.5B embeddings couldn't afford RAM for HNSW (several terabytes). IVF-PQ on GPUs held the index in tens of GB; they retrieved the top 1,000 by PQ distance and re-ranked with full vectors fetched from SSD, reaching their recall target at acceptable latency. A separate 5M-vector "recent items" HNSW index handled fresh inserts, merged nightly.

37–40 min Likely follow-ups

What's OPQ? A learned rotation before PQ that reduces quantization error.
How do you pick m for PQ? Trade memory vs. accuracy; d must be divisible by m; measure recall.
Why re-rank with full vectors? PQ distances are approximate; re-ranking fixes ordering among candidates.

What interviewers listen for

Clear mechanics of IVF and PQ, including compression maths.
Choosing based on scale, memory, recall and updates.

Red flags

Picking one universally.
Not knowing IVF requires training.