HNSW: what the vector similarity search paper actually says

Reading Malkov & Yashunin (2016/2020) while debugging recall degradation in a production RAG pipeline.

The incident started with a complaint that the retrieval results were getting worse. Not wrong — worse. The system was returning chunks that were technically similar but missing the obviously-relevant documents. Recall@10 had dropped from 0.91 to 0.74 over three months without any change to the embedding model or query pipeline.

The culprit was a setting no one had revisited since the initial deploy: ef — the search-time exploration factor for the HNSW index — was set to 10, the library default. As the index grew from 200K vectors to 1.4M, the effective recall for that ef value dropped. We'd tuned for a smaller dataset and never recalibrated.

This is the failure mode of treating vector search as infrastructure you configure once. HNSW — "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs", Malkov and Yashunin, 2016 (published in IEEE TPAMI 2020) — is the algorithm underneath Pinecone, Qdrant, Weaviate, Chroma, and the IndexHNSWFlat in FAISS. Understanding what it's actually doing gives you traction on why retrieval degrades and which knobs actually matter.

The problem the paper is solving

Nearest neighbor search in high dimensions is hard in a way that flat index approaches can't escape. Brute-force search is O(N·d) — linear in the number of vectors, linear in dimension. At 1M 1536-dimensional embeddings, that's 1.5 billion floating point comparisons per query. Modern CPUs can push ~1 GFLOPS for simple dot products with SIMD; that's 1.5 seconds per query on a single thread. Unacceptable for interactive systems.

Exact nearest neighbor algorithms using tree structures (KD-trees, ball trees) avoid the brute-force scan but suffer from the curse of dimensionality: the number of nodes that need to be visited for an exact answer grows exponentially with dimension, and above ~20 dimensions these structures often perform worse than flat search. For 1536-dimensional embeddings from text encoders, they're useless.

The standard production answer is approximate nearest neighbor search: trade exact recall for speed, and accept that you might miss some true neighbors. The question is which approximation structure gives you the best recall/latency tradeoff on real-world query distributions.

HNSW is, empirically, the strongest general-purpose answer to that question. Understanding why requires understanding the navigable small world structure it's built on.

Navigable Small World graphs

Before the hierarchical version, there was NSW: Navigable Small World graphs. The idea is to build a graph where each vector is a node, and nodes are connected to neighbors that are close in the embedding space. A greedy graph traversal — start at some entry node, move to whichever neighbor is closest to the query, repeat — navigates toward the nearest neighbor without exhaustively scanning every node.

The "small world" property matters here. A random node in a small-world graph can reach any other node in O(log N) hops. Social networks have this property: any person can be reached from any other in a few introductions. NSW graphs constructed with the right edge structure have this property: a greedy traversal from any entry node can find the global nearest neighbor in logarithmic hops.

NSW construction: insert nodes one at a time. For each new node, find its ef_construction nearest neighbors among existing nodes using greedy graph search, then add edges to the M closest ones, bidirectionally. The resulting graph has a mix of short-range edges (locally similar nodes) and, as the graph grows, long-range edges connecting dissimilar nodes across the graph — the "small world" bridges that enable fast navigation.

The problem NSW doesn't fully solve: the greedy traversal is vulnerable to local minima. Early-inserted nodes accumulate many long-range connections (they were inserted when the graph was sparse and had to connect to whatever existed). Later-inserted nodes mostly get short-range connections. The search performance depends heavily on where you start, and early-inserted nodes have structural advantages as entry points.

The hierarchy that fixes this

HNSW addresses the local minima problem by building multiple layers of the NSW graph, each sparser than the one below.

Layer 0 contains all N vectors with M bidirectional edges per node — short-range connections for precise local navigation.

Layer 1 contains a randomly selected subset of nodes, roughly N/e (Euler's number), with M_max0 edges — medium-range connections.

Layer 2 contains a subset of layer 1 nodes, roughly N/e², with longer-range connections.

This continues upward until you have a top layer with just a handful of nodes.

The random level assignment: when inserting a new node, draw its maximum layer from a geometric distribution with mean 1/ln(M). Most nodes get assigned to layer 0 only. A fraction 1/M get assigned to layer 1. A fraction 1/M² get assigned to layer 2. And so on. This produces the exponential sparsity at higher layers.

Search procedure:

Start at the entry point in the top layer (a fixed node with the highest layer assignment, updated during construction).
Do greedy descent: move to the closest neighbor at the current layer until reaching a local minimum.
Descend to the next layer. The local minimum at layer L becomes the entry point for layer L-1.
Repeat until reaching layer 0.
At layer 0, do a beam search with ef candidates instead of greedy descent. Maintain a priority queue of the ef closest nodes found so far; explore their neighbors; add to the queue if closer; repeat until no improvement. Return the top k results.

The intuition: the upper layers have long-range connections that let you quickly navigate to the right region of the space. The lower layers provide short-range precision. The hierarchical descent means you're never doing a fine-grained search in the wrong region.

The construction parameters, and what they trade

M — the number of bidirectional links per element at each layer. Default is 16 in most libraries.

More edges mean better recall and faster search (more connections to explore when navigating) at the cost of more memory and slower index construction. The relationship isn't linear. The paper shows diminishing returns beyond M=48 on most datasets. Halving M from 16 to 8 typically costs 5-8% recall. Doubling M from 16 to 32 gains 1-3% recall but costs ~2× index memory.

Memory footprint: each node stores M links (or up to 2M links at layer 0 in some implementations) plus the vector itself. At M=16, 1536-dimensional float32 embeddings, 1M vectors:

Vectors: 1M × 1536 × 4 bytes = 6 GB
Graph links: ~1M × 16 × 4 bytes = 64 MB
Layer assignments and entry point metadata: negligible

Memory grows roughly linearly with M. At M=64, the graph link overhead is ~256 MB for 1M vectors — still small relative to the vector data.

ef_construction — the size of the dynamic candidate list during index construction. Default is 100-200 in most libraries.

This controls index quality at build time. Higher ef_construction means better neighbors are found for each inserted node, producing a higher-quality graph. The cost is build time: ef_construction=200 takes roughly 2× the build time of ef_construction=100.

The paper recommends ef_construction ≥ M as a minimum. Below that, the construction search doesn't have enough candidates to reliably find the M best neighbors, and the resulting graph has weak edges that degrade recall.

ef_construction is a one-time cost. Once the index is built, ef_construction doesn't affect query performance — only the graph structure remains. For a static index that you query millions of times, spending 10× longer on construction with high ef_construction is usually worth it.

ef (ef_search) — the beam width during query time. Default is often 10-50 in library defaults.

This is the most important runtime parameter. Higher ef means more candidates are evaluated during the layer-0 beam search, increasing recall at the cost of latency. The recall/latency curve is approximately:

ef=10: fast, ~70-80% recall@10 on typical embedding distributions
ef=50: moderate, ~90-95% recall@10
ef=100: slower, ~97-99% recall@10
ef=200: slow, ~99%+ recall@10

These are rough figures that depend heavily on dataset characteristics, M, and embedding model. The only way to know your actual numbers is to benchmark on your specific data.

The results that matter

The paper benchmarks against competing methods including IVF (inverted file index, the FAISS default), NSW, and an earlier method called ANNG. On SIFT-1M (1 million 128-dimensional vectors, the standard benchmark):

HNSW at ef=16 achieves 0.99 recall at 1.5 ms per query with M=16. IVF requires a 10-probe search to reach 0.97 recall at ~2 ms per query. The HNSW tradeoff curve dominates IVF across the full recall range.

On high-dimensional data (GloVe 100-dimensional word vectors, 1.2M vectors), HNSW similarly dominates. The paper demonstrates that the performance advantage holds across dimension ranges from 4 to 960 dimensions.

What the paper doesn't benchmark: real-world text embedding distributions at 1536 dimensions. SIFT and GloVe are cleaner than production embeddings from models like text-embedding-3-large. Real-world embeddings from a diverse corpus have more complex cluster structure, and the effective intrinsic dimensionality varies. The benchmark numbers are a ceiling, not a floor.

Production tradeoffs

Memory is the constraint you underestimate. Teams benchmark HNSW on 100K vectors, see reasonable memory usage, and build for 100M. At 100M vectors with 1536-dim float32 embeddings:

Vectors alone: 600 GB
With M=16 graph links: ~612 GB
At M=32: ~624 GB

The vector data dominates at this scale. Memory is the binding constraint for large HNSW indexes, which is why virtually all production deployments at scale use quantized vectors (int8 or float16) and often split indexes across machines. The memory overhead from M specifically is modest at high dimension, but high M with high-dimensional quantized vectors (where the quantization error interacts with recall) requires careful tuning.

Build time scales super-linearly with ef_construction, linearly with N. For 1M 1536-dim vectors at ef_construction=200, M=16, expect 30-60 minutes on a single CPU core. Parallel construction (most libraries support it) scales well to ~8-16 cores. Beyond that, coordination overhead limits scaling. For 100M vectors, budget multiple hours of build time, and plan your re-indexing strategy accordingly.

Deletes degrade the graph. HNSW doesn't support true deletions. The standard approach is soft deletion: mark vectors as deleted and filter them from results. The deleted nodes remain in the graph structure and continue to be traversed during search — they just don't appear in results. As deleted-to-live ratio grows, you traverse more "dead" nodes per query, degrading both latency and effective recall. Most vector databases expose a "vacuum" or re-index operation that rebuilds the graph without deleted vectors. Without periodic vacuuming, a high-churn index degrades continuously.

Updates are deletions plus insertions. Updating a vector's content requires soft-deleting the old version and inserting the new one. The insert adds new edges optimized for the new vector's position; the soft-deleted old version's edges remain traversable. Under heavy update load, the graph becomes partially disconnected from the live vectors' perspective, and recall drops. For high-update workloads, consider whether HNSW is the right structure at all (IVF with periodic re-clustering handles updates better in practice).

The ef default is tuned for benchmarks, not production. Most libraries ship with ef=10 or ef=16 as default. These are chosen to make benchmark numbers look good at low latency — they're not tuned for the recall requirements of production RAG systems. For document retrieval where missing the relevant chunk means a wrong answer, ef=10 is almost certainly too low. Measure recall on your actual data distribution before choosing ef.

Failure modes in practice

Silent recall degradation at scale. This was the opening problem. HNSW's recall for a fixed ef depends on N, dataset density, and cluster structure. As your dataset grows, the optimal ef to maintain a given recall target increases. If you set ef at 100K vectors and don't revisit it at 1M vectors, recall silently drops. Add monitoring for retrieval quality (if you have any signal on which retrieved chunks were actually used), and periodically benchmark recall@k on a held-out evaluation set.

Cold start on clustered inserts. If you insert vectors in batches sorted by topic — all legal documents, then all support tickets, then all product descriptions — the graph structure develops strong topological clusters with weak cross-cluster edges. Queries that span cluster boundaries see poor recall because the traversal struggles to leave the initial cluster. Randomizing insertion order is the mitigation; if your data pipeline doesn't support this, a rebuild with shuffled data after initial load is worth considering.

Intrinsic dimensionality mismatch. Modern embedding models produce 1536-dimensional vectors, but the actual semantic information is much lower-dimensional. Different document domains have different intrinsic dimensionality: legal text might cluster in a 50-dimensional subspace; code might use 200 dimensions effectively. HNSW's performance assumes the embedding space has meaningful structure. If you're embedding noisy or low-information content — short form fields, product SKUs, numeric identifiers — the embedding space has high effective dimensionality relative to meaningful variation, and recall at reasonable ef values can be poor in ways that don't surface in generic benchmarks.

Threshold miscalibration in distance-filtered search. Many production systems add metadata filters ("only retrieve from documents authored in 2024"). HNSW doesn't natively support filtered search — the standard approach is to search HNSW for a larger candidate set, then filter by metadata. The number of candidates you need to over-retrieve to hit your target k after filtering scales inversely with the selectivity of your filter. A filter that keeps 10% of the dataset requires retrieving ~10× your target k from HNSW to get k results after filtering. Teams often implement this incorrectly, either returning too few results or issuing excessively large over-retrieval requests that negate HNSW's latency advantage.

When not to use HNSW

Below ~100K vectors. Brute-force exact search on 100K 1536-dim vectors is fast enough for most interactive applications. numpy or a GPU-accelerated flat index will handle it with lower operational complexity, zero tuning, and 100% recall. The overhead of building and maintaining an HNSW index is unjustified at this scale.

When your workload is update-heavy. High-throughput insert/delete/update patterns don't pair well with HNSW's static graph structure. For vector stores where the live dataset changes continuously — real-time news retrieval, streaming embeddings, frequently updated document corpora — consider IVF-based indexes (FAISS IndexIVFFlat) or LSH approaches that support incremental updates without whole-graph degradation. HNSW is optimized for the query path, not the update path.

When you need exact recall guarantees. HNSW is approximate by construction. "Approximate nearest neighbor" means some true neighbors will be missed, and the probability of missing them depends on ef, M, and dataset structure. If your application requires provably returning the top-k exact neighbors — compliance retrieval, duplicate detection with hard correctness requirements — HNSW is the wrong primitive. Exact MIPS or brute-force search at the cost of latency is the honest alternative.

When you're operating in severe memory constraints. HNSW's graph structure requires keeping the entire index in RAM for performant search. Disk-based HNSW exists (DiskANN, SPANN) but is a different implementation with different performance characteristics. If you're running on hardware where the full index doesn't fit in memory, standard HNSW degrades badly as the OS starts paging graph traversals. Know your memory budget before committing to HNSW at scale.

When your metadata filter selectivity is very low. If most queries are heavily filtered (returning 0.1% of the dataset), HNSW's graph traversal is traversing a large graph to find a needle. Purpose-built filtered-ANN indexes (Pinecone's implementation, Milvus's bitmap index approach, Qdrant's payload index filtering) handle this better. Generic HNSW plus post-filter becomes a bottleneck when the filter selectivity is below ~5%.

What the paper actually gives you

The theoretical contribution of HNSW is a proof that the greedy search complexity on the hierarchical graph is O(log N) for the upper layers and O(1) per "hop" in the dense lower layers for fixed-dimensionality data. In practice, empirical performance on real datasets depends heavily on the embedding model, document distribution, and parameter choices in ways the theory doesn't fully characterize.

The practical contribution is the construction algorithm that naturally produces the hierarchical structure from random level assignment, without needing to explicitly manage the exponential sparsity. The geometric distribution with parameter 1/ln(M) is not an arbitrary choice — it's chosen to produce exactly the right decay in layer density for the navigation properties to hold. Using M=16 and sampling from this distribution gives you a top-layer with ~2 nodes, a second-to-top layer with ~30 nodes, and so on down to layer 0 with all N nodes. The traversal starts with long strides and progressively shortens them as it approaches the target region.

For the incident at the start: the fix was profiling recall on a sampled evaluation set, finding that ef=10 gave recall@10 of 0.74 at our current dataset size, identifying ef=64 as the value that restored recall to 0.92, and adding recall monitoring to alert before it next drifted. We also added a post-deploy check that runs the recall benchmark after each index rebuild. It's a 20-line script that's caught two more regressions since.

The mental model worth carrying: HNSW is a layered skip list for vector space, where each layer navigates at a different scale. The build parameters control how much you invest in graph quality at construction time. The query parameter ef controls how much you invest in graph traversal at query time. These are independent levers, and production systems need to tune both, not just pick library defaults and move on.

Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs — Malkov, Yashunin. IEEE TPAMI 2020 (originally arXiv 2016).