Approximate nearest neighbour indexes (HNSW, IVF, PQ)

How vector databases find similar embeddings fast: why exact search does not scale, HNSW graphs, IVF clustering, product quantisation and other compression, the recall versus latency versus memory trade-off, filtering, updates and deletes, sharding, and choosing parameters.

Reading is half of it. See this used in a real interview: walk through Design an LLM Inference Service →

Semantic search, recommendations, retrieval for LLMs and image similarity all reduce to one operation: given a query vector, find the most similar vectors among millions or billions. Comparing against every vector is too slow, so systems use approximate nearest neighbour (ANN) indexes that trade a little accuracy for orders of magnitude of speed. Knowing the main index types and their trade-offs lets you size and tune a vector store in an interview instead of treating it as magic.

Why exact search fails at scale

A brute-force scan of 100 million 768-dimension float vectors reads about 300 GB per query. Even with fast hardware, that is far too slow for interactive use. Exact search is fine for small sets (up to around a million vectors, especially on GPUs) or as a final re-ranking step over candidates. See vector search and RAG.

HNSW (hierarchical navigable small world)

A multi-layer graph:

• Each vector is a node connected to its near neighbours.
• Upper layers contain few nodes with long-range links; lower layers contain all nodes with short links.
• Search starts at the top, greedily moves toward the query, drops a layer, and repeats, keeping a candidate list (size controlled by ef_search).

Properties:

• Excellent recall and low latency; the default in many vector databases.
• Memory heavy: vectors plus graph links (controlled by M, neighbours per node) must sit in RAM.
• Inserts are incremental; deletes are typically marked and cleaned up later.
• Build time grows with M and ef_construction.

IVF (inverted file index)

• Cluster vectors into many lists (for example 10,000) with k-means; each vector belongs to its nearest centroid.
• At query time, find the closest centroids and scan only their lists (nprobe controls how many).

Properties:

• Less memory overhead than HNSW; works well with compression and on disk.
• Recall depends on nprobe (higher is more accurate and slower).
• Needs training on representative data; clusters drift as data changes, so rebuild periodically.

Compression: product quantisation and friends

Storing full float vectors is expensive. Product quantisation (PQ) splits each vector into sub-vectors and replaces each with the id of its nearest code in a small codebook, compressing a 3 KB vector to tens of bytes. Distances are approximated from lookup tables. Variants and alternatives include scalar quantisation (float32 to int8), binary quantisation, and storing compressed vectors in memory with full vectors on disk for re-ranking.

Common combination: IVF-PQ for billion-scale collections, or HNSW with quantised vectors, followed by exact re-ranking of the top few hundred candidates using full-precision vectors.

The trade-off triangle

Measure recall@k against exact search on a sample of real queries, and tune parameters to hit a recall target within the latency budget.

Filtering

Real queries combine similarity with filters ("restaurants within 5 km, open now"). Options:

• Pre-filter: restrict candidates by metadata, then search; can be slow or break graph navigation if the filter is very selective.
• Post-filter: search more results, then filter; may return too few results if the filter is selective.
• Filtered index traversal supported by the engine, or partitioning the index by a common filter (per tenant, per category, per region).

See search ranking and relevance and Design Yelp.

Updates and deletes

• HNSW supports inserts but deletes leave tombstones that degrade performance until compaction or rebuild.
• IVF needs periodic retraining as the distribution shifts.
• Many systems keep a small, fresh index for recent inserts alongside a large, periodically rebuilt main index, merging results at query time (similar in spirit to LSM trees). See storage engines.

Sharding

For collections beyond one machine:

• Shard vectors across nodes (randomly or by tenant), query all shards in parallel, and merge top-k results. Latency follows the slowest shard. See tail latency.
• Replicate shards for throughput and availability.
• Per-tenant indexes avoid scatter-gather and simplify filtering and deletion. See multi-tenancy.

Memory estimate

100 million vectors of 768 dimensions in float32 is about 300 GB; HNSW links with M = 16 add roughly 100 million × 16 × 2 × 4 bytes ≈ 13 GB (upper layers add a little more). Quantising to int8 cuts the vectors to about 75 GB; PQ to 64 bytes per vector brings them to about 6.4 GB. These numbers decide between RAM, disk-based indexes and compression. See back-of-envelope estimation.

In the interview

"Embeddings go into an HNSW index per shard, with int8 quantised vectors in memory and full vectors on disk for re-ranking the top 200; ef_search is tuned for 95 % recall@10 within 20 ms; metadata filters partition the index by tenant; new items go to a small fresh index merged at query time, and the main index is rebuilt nightly." Relevant for retrieval in Design LLM Inference style systems and candidate generation in Design a News Feed.

Checklist

• Exact search only for small sets or re-ranking.
• HNSW for low latency and high recall in memory; IVF for lower memory and disk.
• Quantisation or PQ to fit large collections; re-rank with full vectors.
• Recall@k measured against exact search; parameters tuned to targets.
• A filtering strategy that matches filter selectivity.
• Fresh plus main index for updates; tombstone cleanup and rebuilds.
• Sharding with parallel queries and memory estimated up front.