Hierarchical Navigable Small World (HNSW)

Hierarchical Navigable Small World (HNSW) is the most widely used graph-based index for approximate nearest neighbor search, and the default similarity index in many vector stores. Introduced by Malkov and Yashunin, it combines two ideas: navigable small-world graphs, where any two nodes are reachable in a few hops through a mix of short- and long-range links, and the skip list, which stacks multiple layers so a search can take long jumps before homing in. The result is a structure that finds near-neighbors among millions of vectors in a handful of graph hops.

How the layered graph works

HNSW builds several layers of graph over the same set of vectors. The top layer holds only a few nodes connected by long-range edges for coarse, fast navigation; each lower layer adds more nodes with shorter edges; the bottom layer contains every vector with the shortest, most local connections. A search starts at the sparse top layer, greedily walks toward the query's nearest node, then drops a layer and repeats, refining the candidate set until it reaches the dense bottom layer and returns the closest matches. Each inserted vector is assigned a maximum layer drawn from an exponentially decaying distribution, which is what reproduces the skip-list character and gives search its roughly logarithmic behavior.

Trade-offs and tuning

HNSW delivers excellent recall and very low query latency, which is why it dominates production semantic search. The costs are higher memory use — it stores the graph edges alongside the vectors — and slower index construction than simpler methods. Three parameters do most of the tuning work: the number of edges per node (often called M) trades memory for graph quality; the construction-time candidate list (efConstruction) trades build time for recall; and the search-time candidate list (efSearch) is the live dial between speed and accuracy that you can adjust per query without rebuilding. Deletions are awkward for graph indexes, so stores typically mark vectors dead and rebuild periodically. If memory is the binding constraint, quantized or disk-backed variants exist, at some cost in recall or latency.

Why it matters for a private stack

For a sovereign operator, HNSW is what makes a large private corpus of embeddings searchable in milliseconds on your own box, so a local LLM can retrieve context for RAG without ever calling out to a hosted service. Every embedded document, note, or repair log stays on hardware you control; the index is just a file or an in-process structure inside your vector database. A practical example: embed a few thousand pages of miner documentation and firmware notes, index them with HNSW, and your local assistant can pull the relevant passage on an ASIC error code in the time it takes to render the prompt — no API key, no usage log on someone else's server.

Practical guidance

Defaults in mainstream libraries are sensible; most users never need to touch M or efConstruction. When recall matters more than latency — legal documents, safety-critical lookups — raise efSearch and measure. When the corpus is small (under a few tens of thousands of vectors), brute-force exact search is often fast enough that no index is needed at all, and skipping HNSW removes a moving part. That is worth remembering in a self-hosted world: the best infrastructure is the least infrastructure that meets the requirement.

One integration detail deserves attention: filtered search. Real queries are rarely pure similarity — you want the nearest neighbors among documents matching a tag, date range, or source — and combining metadata filters with graph traversal is an active engineering area, handled differently across vector stores. Highly selective filters can degrade HNSW's efficiency, so when a filter narrows candidates to a small set, exact search over that set often wins. Knowing when to bypass your own index is part of running one well.

Find local vector stores in the self-hosting catalog.