All concepts

HNSW Vector Index

How graph-based approximate nearest-neighbour search finds close vectors in ~log(N) time.

RAG & Retrieval · Advanced · ~8 min

In plain English

A road network with motorways and side streets. Start on the motorway to get roughly there fast, then drop to local roads for the last mile.

Why it's worth your time

It's the index behind nearly every vector database, and its two parameters are the two ends of your latency/recall trade.

If you remember three things

  • Layered graph: sparse at the top, dense at the bottom
  • Greedy search from the top layer down
  • M controls graph density; efSearch controls how hard you look

Overview

HNSW (Hierarchical Navigable Small World) is the default index in most vector databases. It builds a layered proximity graph: sparse long-range links on top for big jumps, dense short-range links at the base for precision. Search greedily hops toward the query, descending layers, giving logarithmic search over millions of vectors.

How it works

  1. Start at the top layer Search enters at one point in the sparse top layer, where each node has only a few long-range links.
  2. Greedily hop closer Move to whichever neighbour is closest to the query; repeat until no neighbour is closer — a local best for this layer.
  3. Drop down a layer Descend to the next, denser layer and continue greedy search from where you landed.
  4. Reach the base layer The base layer holds every vector with short-range links — the finest-grained search.
  5. Collect neighbours A dynamic candidate list of size ef keeps the closest points found so far.
  6. Return top-k HNSW gives ~log(N) search over millions of vectors — the default index in most vector DBs.

In an interview

HNSW is a multi-layer graph index. The top layers are sparse with long links for coarse navigation; lower layers are dense for fine search. A query greedily hops to the closest neighbour at each layer, then drops down a layer, ending with a fine search at the base — about log(N) hops instead of scanning everything.

Production defaults

M
16 default; 32–48 for high dimensions or high recall needs. Memory scales with it
efConstruction
200. Higher builds slower but gives a better graph — a one-time cost
efSearch
100, then raise until recall@k plateaus. It is linear in query latency
Rule
efSearch must be ≥ k, and realistically several times k

What breaks

  • Recall is poor at high k — efSearch too close to k. It must exceed k by a healthy margin.
  • Memory much higher than the raw vectors — The graph itself. Lower M, or quantize the vectors and keep the graph.

Watch it explained

Vector Database Search - Hierarchical Navigable Small Worlds (HNSW) Explained — DataMListic, 8:03

Related