HNSW explained: the algorithm powering sub-10ms vector search

Every vector database in production uses HNSW under the hood. Pinecone, Weaviate, Qdrant, Chroma, Milvus, pgvector — the algorithm is the same. What differs is how they store it, how they serve it, and how honest they are about the recall vs. latency tradeoffs.

Understanding HNSW isn’t just academic. The tuning parameters directly affect your latency, your recall, and your index size. Getting them wrong means slow queries, poor results, or both. Getting them right means sub-10ms search over a billion vectors with 95%+ recall.

This post explains how HNSW works from scratch, what the parameters mean, and how to think about tuning for your specific workload.

The problem HNSW solves

Finding the exact nearest neighbour to a query vector in a dataset of 1 billion 768-dimensional vectors requires computing 1 billion cosine similarities. At 768 dimensions, each distance computation takes around 1-2 microseconds. 1 billion × 2µs = 2,000 seconds per query. That’s not useful.

This is why approximate nearest neighbour (ANN) search exists. We accept some probability of missing the true nearest neighbour in exchange for dramatically faster search. HNSW achieves this with a data structure that makes the search problem tractable while maintaining high recall.

Navigable small worlds

Before HNSW, there was NSW (Navigable Small World) — the 2014 precursor. Understanding NSW makes HNSW’s insight obvious.

A small-world graph is a graph where most nodes are not directly connected, but any node can reach any other node in a small number of hops. Think: six degrees of separation. The key property is that you get global connectivity with local structure.

NSW builds a graph where each vector is a node. When inserting vector $v$, you find its $M$ nearest neighbours among the already-inserted vectors and add edges to them. The resulting graph has short paths between similar vectors (exploit local structure) and occasional long-range edges that enable fast traversal across the whole space (short-path property).

Search in NSW: given a query vector $q$, start from a random entry node. Greedily traverse the graph: at each node, check all neighbours and move to the one closest to $q$. Stop when you can’t improve. Return the result.

This greedy traversal works surprisingly well for high-dimensional spaces. But NSW has a problem: early insertions (when the graph is small) create few long-range connections. Late insertions (when the graph is dense) create many redundant short-range connections. The graph quality degrades over time.

The hierarchical insight

HNSW (2016, Malkov & Yashunin) adds one key idea: multiple layers.

Layer 0 contains every vector. Layer 1 contains a random subset (~36% of layer 0). Layer 2 contains a random subset of layer 1. And so on, up to some maximum layer $L_{max}$.

Each layer is a navigable small world graph, but higher layers have fewer nodes and therefore longer average edge lengths — they serve as “express lanes” across the space.

Search in HNSW:

1. Start at the entry point (top layer).
2. Greedily traverse the current layer to find the locally closest node to $q$.
3. Drop to the next layer. Use the closest node from the layer above as the starting point.
4. Repeat until you reach layer 0.
5. At layer 0, do a beam search (tracking ef candidates) to find the final top-k results.

The top layers traverse the space coarsely and cheaply (few nodes). The bottom layers provide precision (many nodes, dense graph). This is why HNSW is fast: most of the work happens in layer 0, but layer 0 search starts very close to the answer.

Construction parameters

M (edges per node, default: 16)

Each node maintains at most M edges in layer 0 and M/2 edges in higher layers (Malkov’s original uses M everywhere, but most implementations use M/2 above layer 0 to save memory).

Higher M = better connectivity, higher recall, but more memory and slower inserts. The index size grows roughly as O(N × M × D × 4 bytes) where D is the dimension. At M=16, D=768, N=100M: 100M × 16 × 768 × 4 ≈ 491GB for the graph alone, plus 100M × 768 × 4 ≈ 307GB for the vectors. You need around 800GB total.

Lower M = smaller index, faster inserts, but the graph becomes sparser and recall drops.

Typical values:

• M=8: low-memory, accept ~85-88% recall
• M=16: standard, ~90-93% recall
• M=32: high-recall, ~95%+ recall, 2x memory vs M=16
• M=64: very high recall, rarely worth the cost

ef_construction (candidate list during build, default: 200)

During construction, when inserting a node, HNSW maintains a candidate list of size ef_construction to find the best M neighbours. Larger ef_construction = better graph quality = higher recall at query time, but slower index build.

Think of it as: how hard do you look for good edges when building the graph?

ef_search (candidate list during query, default: 50-100)

At query time, layer 0 uses beam search with a candidate list of size ef_search. This is the primary recall/latency knob at query time.

• ef_search = 10: fast but potentially poor recall (75-85%)
• ef_search = 50: good balance (~90-93% recall, ~5-15ms)
• ef_search = 200: high recall (95%+) but 3-5x slower

This is the parameter you tune per-query if your system supports it. Real-time user-facing queries might use ef_search=40. Batch RAG retrieval might use ef_search=200.

Recall math

Recall@k is defined as: what fraction of the true k nearest neighbours does your ANN search return?

For a 768-dimensional embedding space with 100M vectors:

M	ef_search	Recall@10	Latency p50
16	50	~91%	8ms
16	100	~94%	14ms
32	50	~94%	10ms
32	100	~97%	18ms
16	200	~96%	28ms

Numbers vary by dataset dimensionality, distribution, and hardware. Run your own benchmarks with your actual embeddings — the numbers above are ballpark for OpenAI-style text embeddings.

Quantization: shrinking the index

768-dimensional float32 vectors take 3KB each. 100M vectors = 300GB just for the raw vectors. HNSW graph overhead adds another 50-100%. That’s 450-600GB total — expensive in RAM.

Product Quantization (PQ) compresses vectors by a factor of 8-32x at the cost of 2-5% recall. A 768-dim float32 vector compressed with PQ to 96 bytes (8x) takes 9.6GB for 100M vectors instead of 300GB. The HNSW graph is unchanged; only the distance computations use the compressed representation.

Scalar Quantization (SQ) converts float32 to int8, giving a 4x size reduction with minimal recall loss (~0.5-1%). SQ is the safest quantization to try first.

In ManyVector, you can configure quantization per-namespace:

ns = client.namespace("my-docs", quantization="sq8")  # 4x smaller, minimal recall loss
ns = client.namespace("my-docs", quantization="pq96")  # 8x smaller, ~2-3% recall drop

Why HNSW beats the alternatives

Flat (brute force): O(N) per query. Perfect recall. Too slow above ~100K vectors.

IVF (inverted file index): Clusters vectors into centroids, searches only the nearest clusters. Fast, but requires choosing number of clusters at build time. Poorly suited to dynamic inserts. Recall degrades unpredictably if the cluster structure doesn’t match your query distribution.

LSH (locality sensitive hashing): Theoretically attractive, practically disappointing. High recall requires many hash tables (memory-intensive). Recall is unpredictable across different query distributions.

HNSW: Dynamic inserts (no rebuild required), consistent recall across query distributions, tunable at query time via ef_search, no pre-training on the data distribution. This combination of properties is why it won.

HNSW and object storage

One nuance about ManyVector’s architecture: HNSW traditionally requires the full graph in RAM for efficient traversal. Loading 600GB from S3 for every query isn’t viable.

ManyVector’s approach:

1. Hot namespaces have their HNSW index fully resident in the query layer cache. Queries are pure in-memory traversals. Latency matches or beats traditional vector databases.

2. Warm namespaces maintain a compressed (SQ8 or PQ) version in memory and fetch uncompressed vectors from S3 for the final re-ranking step. Recall is high, latency is ~50-80ms.

3. Cold namespaces fetch the relevant HNSW subgraph from S3 on first access. After the first query, the subgraph is cached. Cold-start latency: 200-800ms. Subsequent queries: 10-20ms.

This tiered model means you pay RAM prices only for the data you’re actively querying — not for everything you’ve ever stored.

Practical tuning guide

Start with M=16, ef_construction=200, ef_search=80. This is the safe default that works well across most embedding models and dataset sizes.

If your recall is below 88%: increase M to 32 or ef_search to 150. Rebuild the index if you change M.

If your latency is above 20ms on hot namespaces: decrease ef_search to 40-50. Accept ~2-3% recall drop.

If your index is too large for RAM: enable SQ8 quantization (4x size reduction, ~0.5% recall drop). If you need more, try PQ with m=96 (8x reduction, ~2-3% drop).

If you need both high recall and low latency: there’s no free lunch. Invest in larger instances with more RAM to keep more namespaces hot. Or accept that cold namespaces have a higher cold-start latency.

Conclusion

HNSW isn’t magic — it’s a carefully engineered navigable graph that trades exact correctness for practical speed. The hierarchy of layers solves NSW’s uneven quality problem. The ef_search parameter gives you runtime control over the recall/latency tradeoff.

Understanding the algorithm means you can tune it for your workload rather than accepting defaults that might be 30% slower or 5% lower recall than necessary. The defaults are reasonable starting points. The tuning is where you earn the performance headroom.