HNSW Explained: The Index Behind Most Vector Search

Hierarchical Navigable Small World (HNSW) is a multi-layer proximity graph for approximate nearest-neighbour search, and it is the default vector-index path in production RAG stores when the corpus fits in memory. Malkov and Yashunin introduced the algorithm in 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. Weaviate’s vector-index concepts page (as of September 2026) states that HNSW is the default index type, that Weaviate ships a custom CRUD-capable implementation of the algorithm, and that the trade is speed against approximation rather than an exact scan. Stores that ship HNSW as a primary path include Weaviate, Pinecone, Qdrant and Milvus. The knobs that matter are connectivity, build breadth and query breadth, and those knobs decide what the index does to recall before any generator sees a candidate.

Why does RAG need an HNSW index instead of scanning every vector?

RAG needs an HNSW index when the collection is large enough that comparing the query embedding to every stored vector breaks the latency budget. Weaviate’s vector-index documentation (as of September 2026) frames vector indexing as the structure that raises similarity-search speed with only a minimal accuracy trade for HNSW, and contrasts that with a flat list that stores every vector for small collections. Weaviate’s concepts writing sits beside Pinecone’s FAISS HNSW series, Qdrant’s essentials course, TigerData’s vector-database basics and Milvus’s HNSW explainer (all extracted September 2026) on the same problem: exact search is linear in corpus size, so approximate nearest-neighbour graphs become the serving default once embeddings number in the hundreds of thousands or millions.

Wrong neighbours become wrong answers because the generator answers the context it receives. Indexing errors therefore look like generation faults until you measure hit rate against an exact baseline on a sample of queries. Oracle’s AI Vector Search HNSW notes and Wikipedia’s HNSW article both stress that the structure is approximate: missed true neighbours are possible when the graph is sparse or the query candidate list is too small. Flat exhaustive search remains correct for tiny shards; the reason to leave it is measured latency, not fashion. Once that border is clear, the next question is how the layered graph is actually built.

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, the construction pattern Pinecone’s foundations chapter and Malkov and Yashunin both describe. The two ideas it combines are William Pugh’s probability skip list (1990) for the layered long and short edge structure, and navigable small-world greedy routing for walking neighbour lists toward the query.

Weaviate’s concepts page (as of September 2026) describes the same layered picture: an object can exist in more than one layer, every object appears in the lowest layer, and each higher layer has exponentially fewer objects with fewer connections. A typical insertion assigns a maximum layer, descends greedily from the entry point, then at each layer from the insertion layer down to 0 expands an efConstruction-sized candidate set and keeps up to M bidirectional neighbours. Weaviate exposes connectivity as maxConnections, with layer 0 allowed up to twice that value in the site’s published Weaviate resource guidance. Weaviate’s layer-0 cap of up to twice maxConnections matches the structural idea Pinecone notes in FAISS, where the layer-0 neighbour cap sits near 2 × M.

Construction quality is paid for at ingest. A larger candidate list and denser connectivity make better links and a slower build. Search will not invent edges the builder never stored, which is why raising query-time breadth cannot fully repair an underbuilt graph. Inserts update the graph in place on CRUD-capable implementations such as Weaviate’s; that is different from partitioned indexes that drift when centroids go stale. How the finished graph is walked at query time is the complementary half of the algorithm.

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 and returns the top-k. Weaviate’s layer-descent description (as of September 2026), Wikipedia’s algorithm summary, Qdrant’s search walkthrough and Pinecone’s series all state that path. Library names for the query breadth knob vary: ef, efSearch or hnsw_ef. hnswlib’s ALGO_PARAMS states the hard floor that 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 demo. Weaviate notes that higher ef values produce a more extensive search that can raise accuracy while slowing the query, and that ef can be configured explicitly or dynamically. Dynamic ef is the production default path many Weaviate collections use, and it belongs next to the other two knobs rather than as a separate product.

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’s HNSW parameter FAQ, The AI Database Blog’s tuning notes and hnswlib’s ALGO_PARAMS all teach that three-way trade rather than a single “best” setting.

Vendors rename the same three ideas. This naming map is what practitioners need when docs disagree on spelling:

Published ranges worth anchoring to, then verifying on the store’s current docs, are these. hnswlib treats a reasonable M as 2 to 100, with 12 to 48 fine for most use cases, and notes higher M for high-dimensional embeddings when you need high recall. Weaviate’s documented defaults used site-wide are maxConnections = 32, efConstruction = 128 and ef = -1 for dynamic ef, with diminishing recall gains called out for ef values above 512. Qdrant’s essentials course cites common working bands of roughly m 8 to 64, ef_construct 100 to 500, and hnsw_ef 50 to 200 or higher, with defaults in its examples at m=16 and ef_construct=200.

Weaviate’s dynamic ef (as of September 2026) sets ef to -1 and sizes the candidate list from the query limit using dynamicEfMin, dynamicEfMax and dynamicEfFactor: the list length is min(max(dynamicEfMin, queryLimit × dynamicEfFactor), dynamicEfMax), and stays at least dynamicEfMin even for tiny limits. 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 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.

Parameter maths without a memory model still leaves you surprised at serving time, because connectivity and vector storage both sit in RAM on the default path.

How much memory does an HNSW index use?

HNSW keeps the graph, and usually the vectors, in RAM, so memory scales with vector count times dimensions times bytes per component, plus the edges. Weaviate’s concepts page (as of September 2026) states that HNSW is an in-memory index where each node and each edge is stored in memory, and that size is dominated by the number of vectors. The site’s published Weaviate resource rule of thumb is Memory usage = 2 × (the footprint of all vectors): one million 384-dimensional float32 vectors are about 1.5 GB of raw vectors and about 3 GB of RAM under that rule, as worked on the Weaviate profile.

hnswlib’s ALGO_PARAMS estimates graph links alone at roughly M × 8–10 bytes per stored element on top of vector storage. Raising M / maxConnections grows persistent edge memory across the whole collection. Raising ef mainly costs per-query working memory and CPU. Weaviate’s vector-cache guidance notes that previously imported vectors need to be in memory for optimal search and import, that a disk lookup is orders of magnitude slower, and that vectorCacheMaxObjects defaults to one trillion (1e12) objects on a new collection. When RAM is the hard ceiling, compress vectors with cutting vector memory, 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.

Memory pressure is also why small collections should not pay for a dense graph they do not need. That decision sits next to the IVF and flat alternatives.

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 September 2026) recommend hnsw for most collections, flat when the object count per index is low (for example small per-tenant shards), and a dynamic index that starts flat and switches to HNSW after a threshold, defaulting to 10,000 objects when async indexing is enabled. That automation shortens early latencies; it does not remove the need to measure filtered recall after the switch.

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 and centroid partitioning rather than a proximity graph, especially when memory is tighter or rebuild windows are acceptable. That recall, latency and memory curve is owned by IVF, flat and the recall you trade for speed. 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.

Write pattern matters as much as size. HNSW absorbs continuous inserts on CRUD-capable implementations without a full rebuild. IVFFlat-style indexes can drift as the data distribution moves and often need rebuild discipline. BigData Boutique’s Syn-Hershko write-up (29 May 2026), cited across prior indexing work on this site, reports HNSW memory overhead roughly 2 to 5 times raw vectors versus IVFFlat near 1.1 times, and notes that HNSW absorbs inserts without a full rebuild while IVFFlat recall drifts as data changes. Those are vendor-reported structural claims; verify on your corpus before treating them as SLAs.

When is HNSW the wrong index?

Skip or defer HNSW when 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, and ships a full_scan_threshold default of 10,000 in its examples. Skip HNSW when you need guaranteed exact nearest neighbours on every query, because HNSW is approximate by design (Wikipedia). Skip it when RAM cannot hold vectors plus graph even after lowering M and considering quantization. Defer it when 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 in vector search. Deletes and updates leave tombstones on the graph until cleanup runs: Weaviate’s concepts page (as of September 2026) states that cleanup is an async process that rebuilds the HNSW graph after deletes and updates, and that prior to cleanup objects are marked deleted but still connected. Mutate mechanics live on updating and deleting documents in a vector index. Prove a mismatch with an exact-versus-ANN sample before rewriting the stack; the alternative mechanics live on the IVF leaf.

Oracle’s AI Vector Search notes add an operational constraint some self-hosted graphs share: when the index lives in memory, instance restarts can force a reload or rebuild window before query quality returns. Weaviate’s CRUD-capable HNSW and async cleanup path are the contrasting production story for continuous mutates, but restart and memory planning still belong in capacity design. Asynchronous indexing, named on Weaviate’s concepts page (as of September 2026) beside the dynamic flat-to-HNSW switch, is what lets large imports queue while the graph catches up rather than blocking every insert on synchronous edge assignment.

Distance metrics are orthogonal to the graph walk. Weaviate’s vector-index FAQ material asks which distance metrics work with vector indexing; cosine, dot product and other supported metrics change how “near” is scored, not whether layers exist. Pick the metric your embedding model expects, then tune HNSW on that space. Mixing a metric the embedder was not trained for with a carefully tuned ef still returns the wrong neighbours.

TigerData’s HNSW basics and Milvus’s implementation notes both emphasise that construction parameters are paid once while query parameters are paid on every request. That accounting is why production teams freeze M and efConstruction after a build-quality sweep, then leave ef (or dynamic ef bounds) as the live dial behind a latency SLO. Weaviate’s dynamic ef formula is one productised form of that dial; other stores expose efSearch or hnsw_ef as a per-query or collection default. Changing connectivity after the fact usually means a rebuild, so treat M as a capacity decision, not as a Tuesday afternoon experiment.

Skip indexing entirely only when the collection is configured not to build a vector index. Weaviate’s concepts FAQ notes that collections are indexed by default and that setting the skip flag to true avoids indexing when vectors should not be searchable that way. Skipping is a deliberate product choice for objects that are stored but never retrieved by vector search; it is not a shortcut for “HNSW was slow.”

HNSW earns its default status when the corpus is large, RAM is available and inserts keep arriving, because layered greedy search returns useful neighbours without a full scan. It fails when the set is tiny, when exactness is mandatory, when memory cannot hold the graph, or when filters and deletes were never designed into the serving path. Measure recall on your queries, tune ef before M, and open quantization, filtering or IVF when the failure is memory, permissions or partition shape rather than graph breadth.