HNSW and ANN Search: How Vector Databases Find Neighbors Fast

The Problem: Nearest Neighbors at Scale

Semantic search, RAG, and recommendation all reduce to the same operation: given a query vector, find the most similar vectors among millions or billions of stored embeddings. Doing this exactly means comparing the query against every vector — O(N) per query. At 100M vectors and thousands of queries per second, that's impossible on any reasonable budget.

Approximate nearest neighbor (ANN) search trades a tiny amount of accuracy for orders-of-magnitude speedup. You accept finding, say, 98% of the true top-10 neighbors in exchange for 100–1000x lower latency. That trade is almost always worth it — downstream models don't care about the difference between the 9th and 11th closest document.

If you're new to embeddings, start with Embeddings Explained for Engineers and From SQL to Vector Search.

The Two Big Index Families

Graph-based: HNSW

Hierarchical Navigable Small World graphs are the most widely deployed ANN index — they power pgvector, Qdrant, Weaviate, Milvus, FAISS, and most managed vector DBs.

The idea builds on "small world" networks (six degrees of separation). HNSW constructs a multi-layer graph of vectors:

• The top layer has few nodes with long-range links — like an express highway.
• Each layer down is denser, with shorter-range links.
• The bottom layer contains every vector.

A search starts at the top, greedily hops toward the query along the sparse highway, then descends layer by layer, refining as the graph gets denser — like zooming in on a map. Search cost is roughly O(log N) instead of O(N).

The knobs that matter:

• M — number of links per node. Higher M = better recall, more memory, slower build. Typical: 16–48.
• ef_construction — how hard the index works while building. Higher = better graph, slower build.
• ef_search — how many candidates to explore per query. This is your runtime recall/latency dial. Raise it for more recall, lower it for less latency.

HNSW's weakness: it's memory-hungry (the whole graph usually lives in RAM) and updates/deletes are awkward, since removing a node can fragment the graph.

Cluster-based: IVF

Inverted File Index partitions vectors into nlist clusters (via k-means). At query time you only search the nprobe clusters nearest the query, skipping the rest.

• nlist — number of clusters (often √N as a starting point).
• nprobe — clusters to search per query; your recall/latency dial.

IVF is lighter on memory than HNSW and handles very large, disk-resident datasets well, but its recall at a given latency is usually a bit lower. It's often combined with compression (below).

Compression: Product Quantization

Storing 100M × 1024-dimensional float32 vectors is 400 GB. Product Quantization (PQ) compresses each vector by splitting it into sub-vectors and replacing each with the id of the nearest centroid from a small codebook. A vector can shrink 10–50x, letting huge indexes live in RAM.

The cost is approximation error in the distances, so PQ is usually paired with a re-ranking step: use the compressed index to get a candidate shortlist, then re-score the shortlist with the full-precision vectors. IVF+PQ is the classic recipe for billion-scale search.

The One Trade-off That Governs Everything

Every ANN system lives on a recall–latency–memory triangle:

• Want higher recall? Raise ef_search / nprobe → higher latency.
• Want lower memory? Add PQ compression → lower recall.
• Want lower latency? Search fewer candidates → lower recall.

There is no free lunch. The engineering job is picking the point on this surface that fits your product. A RAG system serving an LLM can often tolerate 90–95% recall; a fraud-detection retrieval step may demand 99.9%.

Always measure recall against a brute-force ground truth on a sample of real queries. "Recall@10 = 0.97" is the number that tells you whether your index is good enough — index build time and QPS are secondary.

Choosing an Index in Practice

Situation	Start with
< 1M vectors, want simplicity	HNSW (or even brute force)
1M–100M vectors, RAM available	HNSW
100M+ vectors, memory-constrained	IVF + PQ
Frequent updates/deletes	IVF-based, or a DB with good HNSW delete handling
Filtered search (metadata + vector)	A DB with native filtered-HNSW (Qdrant, Weaviate)

Production Gotchas

• Filtering breaks graph assumptions. Combining metadata filters with HNSW can tank recall if the DB filters post-hoc. Prefer engines with native filtered search.
• Recall degrades as you add data. Re-benchmark after major ingestions.
• Build time is real. HNSW on 100M vectors can take hours; plan reindex windows.
• The embedding model matters more than the index. A better encoder beats a perfectly tuned index over weak embeddings every time.

Key Takeaways

1. ANN trades a few percent of recall for 100–1000x speedup — almost always worth it.
2. HNSW (graph) is the default: fast, high recall, memory-hungry; tune ef_search at query time.
3. IVF + PQ scales to billions on a memory budget, with a re-ranking step to recover accuracy.
4. You're always trading among recall, latency, and memory — pick the point your product needs.
5. Measure recall against brute force on real queries; it's the number that matters.

---

Ready to ship? See Vector Databases in Production and Building Production RAG Systems.