HNSW Explained: The Index Behind Most Vector Search

Hierarchical Navigable Small World (HNSW) is a multi-layer proximity graph for approximate nearest-neighbour search (Malkov and Yashunin, arXiv:1603.09320 / IEEE TPAMI 2018). Each vector is a node; edges link nearby vectors; upper layers give long-range shortcuts; layer 0 holds every vector for fine search. It lets RAG vector stores skip a full scan at query time; the price is approximation plus RAM for the graph. Stores that ship HNSW as a primary path include Weaviate, Pinecone, Qdrant and Milvus. This page covers how the graph is built and traversed, what M, efConstruction and ef actually trade away, and when another index fits better.

How does HNSW build its layered graph?

HNSW builds the index by inserting vectors one-by-one into a hierarchy of proximity graphs. Every vector lands in layer 0; a probabilistic skip-list-style rule also places some vectors in higher layers that carry longer-range links (Pinecone’s HNSW foundations; Malkov and Yashunin). The two ideas it combines are William Pugh’s probability skip list (1990) for the layered long/short edge structure, and navigable small-world (NSW) greedy routing for walking friend lists toward the query.

A typical insertion does three things:

1. Assign a maximum layer. A random draw decides how high in the hierarchy the new vector appears; lower layers always include it.
2. Descend from the entry point. From the current top of the graph, the builder greedily walks toward nearer neighbours until a local minimum, then drops a layer — the same descent search will later use.
3. Link neighbours from the insertion layer down to 0. At each of those layers the builder expands an efConstruction-sized candidate set and keeps up to M bidirectional neighbours. FAISS sets layer-0’s cap near 2 × M; Weaviate’s docs (as of July 2026) expose the same idea as maxConnections, with layer 0 allowed up to 2 × maxConnections.

Construction quality is paid for at ingest: a larger candidate list and denser M make better links and a slower build. Search will not invent connectivity the builder never stored.

How does HNSW search find nearest neighbors?

At query time HNSW starts at an entry point on the top layer, greedily walks to nearer neighbours until it cannot improve, then drops one layer and repeats until layer 0 — where it expands an ef-sized candidate list (also called efSearch or hnsw_ef depending on the library) and returns the top-k (Wikipedia’s algorithm summary; Qdrant’s search walkthrough; Pinecone). hnswlib’s ALGO_PARAMS states the hard floor: ef cannot be set lower than k.

The result is approximate. A sparse graph or a too-small ef can miss true neighbours even when they exist in the collection. The honest check is an exact nearest-neighbour baseline on a sample of your queries — not a recall percentage copied from someone else’s blog.

What do M, efConstruction, and ef actually trade away?

Three knobs dominate HNSW behaviour. M (Weaviate: maxConnections) sets how many graph links each node may keep. efConstruction sets how broadly the builder searches for those links. ef sets how broadly each query explores the finished graph. Higher values usually improve recall; the cost lands on memory, build time, or query latency depending on which knob moved (Milvus HNSW parameter FAQ; The AI Database Blog’s tuning guide; hnswlib ALGO_PARAMS).

Vendors rename the same three ideas. The table below is the mapping practitioners need when docs disagree on spelling:

Published ranges and defaults worth anchoring to (verify on your store’s current docs — APIs move):

• hnswlib treats a reasonable M as 2–100, with 12–48 fine for most use cases, and notes higher M for high-dimensional embeddings when you need high recall (ALGO_PARAMS).
• Weaviate defaults (docs as of July 2026): maxConnections = 32, efConstruction = 128, ef = -1 (dynamic ef). The same docs note diminishing recall gains for ef values above 512.
• Qdrant’s essentials course cites common working bands of roughly m 8–64, ef_construct 100–500, and hnsw_ef 50–200+.

Tune in this order: sweep query-time ef first (often mutable without a rebuild), raise efConstruction if the graph looks underbuilt, and raise M last because it grows persistent RAM. hnswlib’s author diagnostic is useful here without becoming a fake production SLA: when you measure recall for an M-nearest-neighbour search with ef = ef_construction, a result below 0.9 means there is still room to improve construction — that is a build-quality check, not a published Recall@10 for your corpus.

How much memory does an HNSW index use?

HNSW keeps the graph — and usually the vectors — in RAM, so memory scales with vector count × dimensions × bytes per component, plus the edges. Two published models are enough to plan with:

• Weaviate’s resource rule of thumb — memory ≈ 2 × the footprint of all vectors. The worked example on Weaviate is one million 384-dimensional float32 vectors ≈ 1.5 GB of raw vectors and ≈ 3 GB of RAM.
• hnswlib’s graph-edge estimate — roughly M × 8–10 bytes per stored element for links alone, on top of vector storage (ALGO_PARAMS).

Raising M / maxConnections grows persistent edge memory across the whole collection. Raising ef mainly costs per-query working memory and CPU. When RAM is the hard ceiling, compress vectors with quantization, or use a store-specific disk-oriented index if one exists (Weaviate documents HFresh as that class of escape hatch — without inventing a speed or recall delta here).

When should you use HNSW instead of IVF or flat?

Choose HNSW when you need sublinear approximate search over a large embedding corpus and can hold the graph in memory. Weaviate’s vector-index docs (as of July 2026) recommend hnsw for most collections and flat when the object count per index is low — for example small per-tenant shards.

Prefer a flat / exhaustive scan when the set is small enough that comparing the query to every vector already meets latency: you get exact neighbours and skip graph construction. Prefer an IVF-style partitioned index when you want inverted-list / centroid partitioning rather than a proximity graph — that recall–latency–memory curve is owned by IVF and flat indexes. Do not pick a winner from an unsourced Recall@k table; pick from measured recall@k and p95 retrieve latency on your own queries, then read the trade-off map on the indexing hub.

When is HNSW the wrong index?

Skip or defer HNSW when any of these hold:

• The collection is small and brute-force or flat search already meets latency — Qdrant’s essentials course notes small collections may stay on full scan until indexing helps.
• You need guaranteed exact nearest neighbours on every query — HNSW is approximate by design (Wikipedia).
• RAM cannot hold vectors plus graph even after lowering M and considering quantization.
• Build or insert cost dominates a write-heavy corpus and you have not yet measured whether a lower efConstruction — or a different index type — fits the write path better.

Metadata filters can also collapse effective recall even when the unfiltered graph looks fine — that failure mode is documented at metadata filtering. Prove the mismatch with an exact-versus-ANN sample before rewriting the stack; the alternative mechanics live on IVF and flat.