Exact nearest-neighbour search in high dimensions is hopeless — the tree-based methods that work in 2D degrade to scanning everything once you’re at 768 dimensions (the “curse of dimensionality”). HNSW sidesteps it with a graph instead of a partition.

The idea

HNSW = Hierarchical Navigable Small World. Build a multi-layer graph where:

  • Every node is a vector, linked to a few near neighbours.
  • Upper layers are sparse (long-range “express lanes”); lower layers are dense.
  • Search starts at the top, greedily hops toward the query, then drops a layer and refines.
search(q):
  enter at top-layer node
  for layer in top..0:
      greedily move to the neighbour closest to q
      (carry the best candidates down to the next layer)
  return the closest found in layer 0

It’s the skip-list intuition applied to a proximity graph: coarse jumps first, fine steps last.

The knobs

  • M — links per node. Higher = better recall, more memory.
  • efConstruction — how hard you search while building. Higher = better graph, slower build.
  • efSearch — candidate list size at query time. The recall/latency dial you actually tune in production.

The catch

It’s approximate — you trade a few percent recall for orders-of-magnitude speed, which is the right trade for retrieval and RAG. And the graph lives in RAM; HNSW is memory-hungry, so at very large scale people reach for IVF-PQ or a hybrid. But for “millions of vectors, low latency, good-enough recall”, it’s the default for a reason.