Advanced 26 min read ANNHNSWIVF-PQquantizationretrieval

Embeddings + ANN Serving Deep-Dive

HNSW vs IVF-PQ, the recall–latency knob, index build/refresh, quantization

Once retrieval is a dot product between a query embedding and every item embedding, the bottleneck is search, not the model. Exact nearest-neighbor over 100M vectors of dimension 256 is 100M·256 ≈ 25.6 billion multiply-adds per query — that's 51.2 billion FLOPs (each multiply-add counts as 2), and even a well-optimized multi-core CPU sustaining ~50 billion FLOP/s of dot-product throughput needs ≈1 second per query, ~100× over the 10ms budget, before counting the ~100GB of vectors (100M × 256 × 4 bytes) that would have to stream from memory on every query — hopeless in 10ms. Approximate nearest-neighbor (ANN) trades a sliver of recall for two-to-three orders of magnitude speedup.

HNSW builds a navigable graph; IVF-PQ partitions and compresses. HNSW (hierarchical navigable small world) links each vector to a few neighbors across layered graphs, so a query "greedily walks" from an entry point to its neighborhood in ~log(N) hops — very fast, very high recall, but the full float vectors sit in RAM (100M × 256 × 4 bytes ≈ 100GB). IVF-PQ instead clusters vectors into, say, 4096 cells (search only the nearest few), and product-quantizes each vector — splitting 256 dims into 32 sub-vectors, each mapped to one of 256 centroids — so a vector shrinks from 1024 bytes to 32 bytes, a 32× compression that fits 100M vectors in ~3GB.

Recall and latency are one knob, turned at query time. HNSW's `efSearch` (how many candidates to keep on the walk) and IVF's `nprobe` (how many cells to scan) both trade recall for latency continuously: nprobe=8 might hit 0.92 recall at 3ms, nprobe=64 hits 0.99 recall at 12ms. You don't pick "an index" — you pick an operating point on its recall–latency curve, and that point is a product decision (how many good candidates can the funnel afford to lose?).

Build cost and staleness are the operational tax. HNSW graph construction is O(N·log N) and expensive to mutate, so high-churn catalogs favor periodic rebuilds or a small "fresh" index searched alongside the main one. Quantization (PQ) is lossy: the 32× compression that saves RAM also blurs fine distances, costing a few points of recall — acceptable at retrieval (the ranker re-scores anyway) but never in the final ranker.

Key points

Exact NN is infeasible at scale; ANN buys ~100–1000× speedup for a few points of recall. 100M × 256-dim exact search ≈ 25.6B MACs/query — impossible in budget. ANN is not an optimization, it's the only way retrieval runs in real time.
HNSW = graph walk (fast, high recall, RAM-heavy); IVF-PQ = partition + quantize (compact, tunable, mildly lossy). HNSW keeps full float vectors (~100GB for 100M×256); IVF-PQ compresses 1024B → 32B (~32×, ~3GB) by splitting into sub-vectors and centroid-coding each. Choose by whether RAM or recall is the binding constraint.
Recall and latency are a single tunable knob (efSearch / nprobe), set at query time. More candidates scanned → higher recall, higher latency. You select an operating point on the curve, not a fixed index — and that point is a business call about how many good candidates the funnel can lose.
Build cost and quantization loss are the operational reality. HNSW is costly to mutate → high-churn catalogs use rebuilds or a side "fresh" index; PQ's compression is lossy, tolerable at retrieval (the ranker re-scores) but not in final ranking.

Takeaway

ANN serving turns retrieval's dot-product-over-millions into a tunable recall–latency tradeoff: HNSW greedily walks a navigable graph (fast, high-recall, RAM-heavy) while IVF-PQ partitions and product-quantizes vectors (32× smaller, mildly lossy), and in both you pick an operating point (efSearch/nprobe) rather than a fixed index.

Recap

Once retrieval is a dot product, the bottleneck is search, not the model: exact NN over 100M vectors of dim 256 is 100M·256 ≈ 25.6B multiply-adds/query — hopeless in 10ms. ANN (approximate nearest-neighbor) trades a sliver of recall for 100–1000× speedup; it's not an optimization, it's the only way retrieval runs in real time.
HNSW builds a navigable graph: each vector links to a few neighbors across layered graphs, so a query greedily walks from an entry point to its neighborhood in ~log(N) hops — very fast, very high recall, but the full float vectors sit in RAM (100M × 256 × 4B ≈ 100GB).
IVF-PQ partitions and compresses: cluster vectors into ~4096 cells (search only the nearest few), and product-quantize each — splitting 256 dims into 32 sub-vectors, each mapped to one of 256 centroids — so a vector shrinks 1024B → 32B (32×), fitting 100M vectors in ~3GB, mildly lossy. Choose HNSW vs IVF-PQ by whether recall or RAM is the binding constraint.
Recall and latency are one knob, turned at query time: HNSW's efSearch and IVF's nprobe both trade recall for latency continuously (nprobe=8 → 0.92 recall at 3ms; nprobe=64 → 0.99 at 12ms). You don't pick "an index," you pick an operating point on its recall–latency curve — a product decision about how many good candidates the funnel can afford to lose.
Build cost and quantization loss are the operational tax: HNSW graphs are O(N·log N) to build and expensive to mutate, so high-churn catalogs use periodic rebuilds or a small "fresh" index searched alongside the main one. PQ's compression is lossy — acceptable at retrieval (the ranker re-scores anyway), never in the final ranker.

Check your understanding

Q1. Select the two correct statements about indexing 200M 256-dim vectors with only 8GB RAM per serving node.

A) IVF-PQ clusters vectors into cells and product-quantizes each one, shrinking memory footprint drastically (~6.4GB for 200M).
B) The recall loss from PQ's lossy quantization is generally acceptable at retrieval since the downstream ranker re-scores anyway.
C) Reducing the embedding dimension all the way down to 4 keeps recall high because low-dimensional spaces are easier to search.
D) Storing all vectors on disk and doing exact brute-force search per query is viable, since SSD read latency is negligible here.

Q2. Retrieval recall is 0.92 at nprobe=8 and 3ms. The latency budget allows 12ms and the ranker keeps missing relevant items. What's the correct single-knob change?

A) Rebuild the index nightly instead of weekly — the real issue here is staleness, not the recall number itself.
B) Raise nprobe from 8 to 64 so more IVF cells are scanned, lifting recall toward ~0.99 within the 12ms budget.
C) Lower nprobe down to 2 to speed up the search further, freeing extra time for the ranker to compensate.
D) Switch from dot-product similarity to cosine similarity instead; recall improves automatically at no cost.

Q3. A catalog adds and removes thousands of items per minute. Retrieval keeps returning deleted items and missing brand-new ones, even though HNSW recall benchmarks are excellent. What's the underlying issue?

A) HNSW recall degrades sharply above roughly 10M vectors; sharding the index into smaller pieces resolves it.
B) efSearch is set too high, causing the graph walk to keep revisiting deleted nodes; simply lowering it fixes this.
C) Product quantization is silently corrupting only the newly-added vectors each cycle; disabling PQ entirely resolves the freshness problem.
D) HNSW graphs are costly to mutate, so a periodic rebuild goes stale between builds; fix with a small refreshed side index.

Try it interactively

ML Systems Lab is a free interview-prep platform for ML engineers — work through the full interactive module, quizzes, and drills.

Open ML Systems Lab →