Background: skip lists & small-world graphs

HNSW = skip lists (the hierarchy) + small-world graphs (the navigation). Understanding these two ideas separately makes HNSW obvious when we combine them.

Small-world graphs: navigation by greedy hops

A graph is a set of items (nodes) joined by links (edges). A small-world graph has a magic property: even with only a handful of links per node, any node can reach any other in a small number of hops. This is the "six degrees of separation" idea — you're surprisingly few handshakes from anyone on Earth.

Why does that help search? Because of greedy routing. To find the node nearest a query:

  1. Start at some node.
  2. Look at its neighbors; move to whichever neighbor is closest to the query.
  3. Repeat. Stop when no neighbor is closer than where you are.

Each hop gets you strictly closer, and small-world connectivity means you home in after only a few hops. A tiny ASCII picture — greedy walk from A toward a query near G:

A —— B —— C
|    |    |          start at A, hop to the neighbor closest to the query,
D —— E —— F          keep hopping "downhill": A -> B -> E -> F -> G
     |    |
     G —— H          (G's neighbors are all farther from the query -> stop)

The danger: greedy routing can get stuck in a local minimum — a node that's closer than all its neighbors but not the true nearest. Two things fix this:

  • adding a few long-range links so you can take big shortcuts, and
  • searching with a beam (keeping several candidates at once, not just the single best) — the ef parameter we'll meet later.

Skip lists: a hierarchy for big jumps

A skip list speeds up search in an ordered list by stacking layers of "express lanes". The bottom layer has every element; each layer above keeps only a random subset, so it's sparser. You search from the top (few elements, big jumps), drop down a layer when you'd overshoot, and refine — reaching any element in about $O(\log n)$ steps.

layer 2:  1 ───────────────► 9            (express: big jumps)
layer 1:  1 ─────► 5 ──────► 9            (regional)
layer 0:  1 → 3 → 5 → 7 → 9 → ...         (every element)

The trick that makes the layer sizes work: each element is promoted to the next layer up with some fixed probability, so layers shrink geometrically — most elements live only at the bottom, a few reach the top.

The combination = HNSW

HNSW takes the navigability of small-world graphs and the multi-layer zoom of skip lists and fuses them:

  • Instead of an ordered list, each layer is a small-world graph.
  • The top layers are sparse (few nodes, long links) for fast, coarse approach — the "highways".
  • The bottom layer (layer 0) contains every vector with denser links for precise final search — the "streets".
  • Search starts at the top, greedily routes to get close, drops down a layer, refines, and repeats until it does a careful search at the bottom.

That's the whole idea. The next chapter shows it working end-to-end before we build each piece. 👉