HNSW,
explained.

The problem is approximate nearest neighbor (ANN) search: given a query vector, find the closest stored vectors among millions or billions. Exact search means comparing the query to every point — O(N) per query, which collapses at scale. The approximate relaxation trades a tiny bit of accuracy for an enormous speedup, and HNSW is the method that made that trade practical enough to power the whole retrieval stack.

HNSW's core move is to treat search as navigation. Connect the points into a graph — each point links to some near others — then, to answer a query, start somewhere and greedily hop to whichever neighbor is closest to the query, over and over, until no neighbor is any closer. You've walked to the query's neighborhood. The genius is entirely in which graph makes that walk both fast and accurate.

Greedy hopping only works if the graph is built right. A graph of just short local links is like a country road network with no highways: you'll reach anywhere eventually, but slowly, one town at a time. A small-world graph adds a few long-range links — highways — so you can cross the space in a handful of jumps, then use local links to refine. That mix of long and short edges is exactly what makes a graph navigable by greedy search.

The danger of pure greedy search is getting stuck in a local minimum — a node whose neighbors are all farther from the query than it is, even though a better point exists elsewhere. Good graph construction (enough neighbors, well-chosen, with diversity) makes such traps rare, so the greedy walk usually lands on the true nearest neighbor or something very close. Approximate, but reliably so — and you can dial the accuracy up by keeping a small candidate list during search instead of a single current node.

A single flat small-world graph is good, but HNSW's leap is to layer it, borrowing the idea of a skip list. Picture a pyramid of graphs: the bottom layer holds every point with dense local links; each layer above holds an exponentially smaller sample of points with longer-range links. Search runs top-down — greedily approach the query in the sparse top layer, then drop a layer and refine, repeating to the bottom.

The layers are built by assigning each inserted node a maximum level from an exponential distribution: most nodes stay at level 0, a geometrically shrinking fraction reach each higher level. That produces the pyramid automatically. The top layers act as an express lane that gets you into the right region cheaply; the bottom layer does the fine-grained work. This is the "hierarchical" in HNSW, and it's what turns a good graph search into a logarithmic one.

A node's level is sampled from an exponential rule, where u is uniform in (0,1) and mL a normalization constant:

So a fraction of nodes sit only at level 0, fewer reach level 1, fewer still level 2 — a pyramid. The highest level present among N nodes therefore grows like ln(N).

That logarithmic height is the whole payoff. The number of layers is about ln(N)·mL, and greedy search spends a bounded number of hops per layer, so the total cost is:

Squaring the dataset only doubles the number of layers, because ln(N²) = 2·ln(N) — going from a thousand points to a million barely doubles the work. That is why HNSW stays fast as collections grow into the billions. The runnable version below greedily walks a small-world graph to the nearest node and shows the layer count growing logarithmically.

HNSW set a new bar for approximate nearest-neighbor search that still stands:

The trade-offs are worth knowing: HNSW is memory-hungry (it stores many edges per node) and its graph lives best in RAM, and deletions are awkward. But for the common case — lots of vectors, fast high-recall search, occasional inserts — nothing has convincingly displaced it, which is why it became the default.

HNSW is the quiet engine under modern retrieval. When dense retrieval encodes passages into vectors, something has to find the nearest ones fast — and that something is almost always HNSW. It's the default index in vector databases like FAISS, Qdrant, Weaviate, and Milvus, and therefore the layer that makes retrieval-augmented generation fast enough to feel instant. Every "search your docs" feature you've used likely walked an HNSW graph.

It also composes with the other retrieval ideas. To cut HNSW's memory appetite you can store quantized vectors in the graph, trading a little accuracy for a lot of RAM. Its elegance is that a decades-old intuition — small-world networks, six degrees of separation — plus a skip list's logarithmic staircase, together solve a billion-scale problem with a greedy walk. Not a neural network in sight, yet it's indispensable infrastructure for the neural systems built on top of it.