HNSW gives you 5ms recall@10 on 10M vectors but eats RAM. IVF-PQ compresses a 1.5KB float32 vector down to 32 bytes with under 2% recall loss — that's how Google's ScaNN serves billion-vector indexes. The right choice depends on whether you're bottlenecked on latency, memory, or cost. This lesson is the recall–latency–memory triangle that every production vector-search team negotiates.
Learning Objectives
After this lesson, you will be able to:
Explain why exact nearest-neighbor search is impossibly slow at scale and the recall–latency tradeoff that ANN algorithms exploit
Pick HNSW for general-purpose, IVF-PQ for memory-constrained, ScaNN for Google-scale — and tune ef_search / nprobe to hit your latency target
Use product quantization to compress 1.5KB float32 vectors to 32 bytes with <2% recall loss
Build a billion-vector serving system with the right index, sharding strategy, and recall@k targets
Try it: Watch HNSW descend layers to find nearest neighborsInteractive
Open the /play/vector-search playground to see HNSW search hop from the sparse top layer down to the dense bottom layer. Push ef_search up and watch latency rise while recall@10 climbs from 0.85 → 0.99 — that's the knob production teams tune for their SLA.
The Recall-Latency-Memory Triangle
Your Reflection
Saves automatically
What’s one thing you learned? What’s still confusing?
Hierarchical Navigable Small World (Malkov & Yashunin 2016) builds a multi-layer graph where each node has long-range and short-range edges. Search greedily descends from layer L (sparse, long-range) to layer 0 (dense, short-range), each time entering the closest neighbor's neighborhood.
Build complexity: O(NlogN)Search complexity: O(logN)Memory: O(N⋅M⋅8) bytes for graph
HNSW knobs to tune
M (edges per node): higher = better recall, more memory. Default 16-32.
Inverted File + Product Quantization is the FAISS recipe for billion-vector retrieval on commodity hardware.
Step 1 — IVF: cluster all vectors into K Voronoi cells (typically K = √N). At query time, compute distance to K cell centroids; only search vectors in nprobe nearest cells. Reduces search space by N/K.
Step 2 — PQ (Product Quantization): split each d-dim vector into m subvectors, quantize each to one of 256 codebook entries (1 byte per subvector). A 1024-dim float32 vector (4096 bytes) compresses to m=32 bytes — 128x smaller.
Recall cost: typically 5-15% recall drop vs uncompressed. For most production RAG, acceptable. Use OPQ (Optimized PQ) to recover most of the lost recall via learned rotations.
ScaNN (Google 2020) outperforms HNSW and IVF-PQ on benchmarks via anisotropic loss: optimize the quantization to preserve inner products more accurately along the directions that matter most for retrieval (high-magnitude vectors get more bits).
Anisotropic loss: minimize ∥qTv−qTv^∥2 weighted by ∥v∥2
ScaNN powers Google Search and YouTube embeddings. Open-source via TensorFlow.
You have 500M vectors, each 1024-dim float32. You need 50ms p95 latency, 95% recall@10, and have a budget of 256GB RAM total across your serving fleet. What index?
The answer: IVF-PQ with PQ32. HNSW would need ~2TB RAM for raw vectors plus ~50GB for the graph. IVF-PQ gets you under 32GB total with mild recall cost. Tune nprobe to hit the 95% recall target.
PQ compression isn't free — every byte you save costs a bit of recall. The playground below derives the relationship between codebook size 2^nbits, subvector count m, and reconstruction error on synthetic embeddings, then sweeps the recall@10 vs memory Pareto frontier.
Tests · Verify HNSW recall@10 climbs as efSearch increases. Verify IVF-PQ recall@10 climbs as nprobe increases. Verify total IVF-PQ size is ~16× smaller than raw vectors.
You're storing 1B 1024-dim float32 embeddings. Raw size is ~4TB. Which index lets you serve from a single 64GB-RAM machine?
ANN gets you the right candidates fast. The next lesson — Re-ranking — explains how to use a slower, smarter model to pick the very best candidates from the top-100 ANN returned.