What it is
Embeddings turn text, images, and users into vectors (for example 768 numbers), where similar items are close together. Nearest neighbor search finds the vectors closest to a query vector. Exact search compares the query against every stored vector, which is O(N × d) per query: for a billion 768-dimension vectors that is seconds of work and about 3 TB of data to read. Approximate nearest neighbor (ANN) indexes give up a small amount of recall (the share of the true nearest neighbors found) for orders of magnitude less work.
Important
Key takeaway: Three families, one trade-off. HNSW (a layered graph) gives the best recall and latency for in-memory indexes with live inserts, at a high memory cost. IVF (clusters) is simple and cheap on memory. Product quantization compresses vectors 8 to 16× so huge corpora fit, at a recall cost. Choose by which resource binds: latency, memory, or update rate.
When you care
Semantic search, retrieval-augmented generation, recommendation retrieval, and deduplication all rest on a vector index. The interview question is not “name HNSW” but “when would you pick something else, and what does it cost?”
Note
Interview signal: The signal is not “HNSW beats IVF”. It is reasoning about when each wins: HNSW for recall and latency when memory is affordable, IVF with product quantization when memory is the binding constraint. Picking HNSW without naming its memory bill (about 4.5 TB for a billion 768-dimension vectors) is the right answer for the wrong reasons.
The families
| Index | How it works | Strengths | Weaknesses |
|---|---|---|---|
| IVF (inverted file) | Cluster the vectors (k-means) into K cells; at query time search only the nprobe nearest cells | Simple; low memory overhead; good for batch workloads | Recall depends on tuning nprobe; live inserts are awkward (which cluster?); unbalanced clusters |
| HNSW (hierarchical navigable small world) | A multi-layer graph; each vector links to its approximate nearest neighbors; queries walk the graph greedily | Best recall and latency in practice; natural live inserts; no clustering step | High memory (graph edges stored with the vectors); the graph must be in RAM; build time is O(N log N) |
| Product quantization (PQ, ScaNN) | Compress each vector into a short code; search the compressed space; re-rank the top candidates with full vectors | 8 to 16× less memory; enables disk-based indexes | Recall drops with compression; needs tuning; weaker than HNSW at high recall |
How HNSW search works
HNSW is a multi-layer analog of a skip list, applied to a graph.
- Build. Each inserted vector gets a random top layer (higher layers are exponentially rarer, like a skip list). At every layer it joins, it connects to its
Mapproximate nearest neighbors in that layer. The top layer has very few nodes; the bottom has all of them. - Search. Start at a fixed entry point in the top layer. At each layer, hop greedily to whichever neighbor is closest to the query. When no neighbor improves, drop to the next layer, which has more nodes and finer neighborhoods. At the bottom layer, keep a priority queue of the
ef_searchbest candidates seen, and return the top k. - Why it works. Upper layers are long-range highways (coarse navigation); lower layers are local search. The walk takes about O(log N) hops to reach the right neighborhood, then a local search of
ef_searchcandidates buys recall.
Worked example. A billion vectors and 5 layers: the top layer has about 100 nodes. A query enters there and makes 2 to 3 hops, drops to
layer 4 (about 10,000 nodes), refines, then descends through the layers; at the bottom it explores ef_search = 128 candidates. The
total is about 500 to 1,000 distance computations, versus a billion for brute force.
The parameters, and what each trades:
| Parameter | Meaning | Typical | Raising it |
|---|---|---|---|
M | Connections per node | 16 | Better recall, more memory |
ef_construction | Beam width while building | 200 | Better graph, slower build |
ef_search | Beam width while querying | Tuned to the recall target | Better recall, higher latency |
A common target is “95% recall at 10 (recall@10) under 50 ms”, and ef_search is the knob you turn to reach it.
Live inserts. Compute the new vector’s neighbors at each layer with the same greedy search and connect it. This takes fine-grained locks (or compare-and-swap) on the neighbors’ lists, and is designed for concurrent reads and writes. IVF cannot do this as gracefully.
Memory arithmetic
Raw size = N × d × bytes per value. A billion 768-dimension vectors in float32 is 10⁹ × 768 × 4 bytes ≈ 3 TB. HNSW’s graph overhead (about 1.5× at M = 16) makes it about 4.5 TB, around 4.5 KB per vector. With 256 GB of usable memory per node, that is roughly 57 million vectors per node, so about 18 shards at minimum, and the index must stay in memory to meet a 50 ms latency target. If that is too expensive, compression (PQ) cuts the memory 8 to 16× at a recall cost, or a disk-based index trades latency for capacity.
Filtering
Real queries combine similarity with attributes (“nearest products in this category for this tenant”). Two approaches:
- Post-filter: search for the top K, then drop non-matching results. If 90% of vectors fail the filter, you must fetch far more than K candidates and recall collapses.
- Filter inside the index: apply the predicate during the graph traversal or on a pre-filtered subset, so the search is over matching vectors only.
Warning
Production reality: Filters must live in the index. Search-then-filter looks fine in a demo and destroys recall at scale for selective filters. Also expect to rebuild or compact HNSW periodically after many deletes, since deleted nodes stay as graph waypoints until removed.
Sharding and replication
At billions of vectors the index is sharded. Shard by partition of the vector set (by id or by tenant): a query is sent to every shard, each returns its local top K with scores, and a coordinator merges, the same scatter-gather as a search index. Replicate each shard for availability and throughput. Hybrid search blends the vector score with a keyword score (a weighted combination), because keywords catch exact terms that embeddings blur.
When to pick what
| Constraint | Choose | Why |
|---|---|---|
| High recall at low latency, memory affordable, live inserts | HNSW | Best recall and latency trade-off |
| Memory is the binding constraint | IVF with product quantization | 8 to 16× compression |
| Mostly batch, static data | IVF | Simple |
| Huge corpus on disk | A disk-based PQ index | Capacity over latency |
| Filtered queries | A filter-aware index, never post-filter alone | Preserves recall |
| Small dataset (under about a million) | Exact search, perhaps on a GPU | An index may not be worth it |
Caution
Common mistake:
Reporting recall at one setting and calling it “the” recall. Recall is a dial: ef_search or nprobe trades it against latency.
State the target (recall@10 at a latency) and measure it on your own data and filters.
Related
- Walkthrough: Designing a Vector Database — the full vector database design built on these indexes.
- Walkthrough: Designing a RAG System — vector retrieval as the first stage of a generation pipeline.
- Reference: Two-Stage Ranking and the Retrieval Funnel — where ANN retrieval sits in a ranking funnel.