LABS · 15  /  RETRIEVAL

The Skip-List
of Space.

A billion vectors, and you need the closest few in milliseconds. You can't compare them all. HNSW builds express lanes over a proximity graph — sparse layers to cover distance fast, dense layers to home in — and a greedy hop rides them to the answer. Drop a query and watch it navigate.

Act 1 · The greedy hop
Navigate the layers
Click anywhere to drop a query. Search enters at the top layer (sparse express lanes), greedily hops to the nearest node it can see, then descends a layer and refines — until it lands on the nearest neighbors at the bottom.
click to drop a query · then Search
Layer 2 (express) Layer 1 Layer 0 (all vectors) Query Nearest found
The top layer holds only a few nodes, so one hop covers huge distance. Each descent adds detail. That's the skip-list idea, in space: cross the continent on the highway, find the house on the side street.
Act 2 · Approximate vs exact
Race it against brute force
Brute force compares the query to every vector — perfect, but it scans all of them. HNSW visits only a handful. Drop a query and run both: watch brute force sweep the whole field while HNSW darts to the answer.
click to drop a query · then Race
0
Brute force · comparisons
0
HNSW · comparisons
Speedup
Same answer (almost always), a fraction of the work. Scale this from 200 points to a billion and the gap becomes the difference between milliseconds and minutes.
Act 3 · The dials
Recall vs speed vs memory
HNSW is approximate — it can miss the true nearest. Two dials tune it: efSearch widens how many candidates it explores (recall ↑, latency ↑), and M sets connections per node (richer graph, more memory). Move them and watch the trade.
efSearch (search width)32
M (connections / node)16
Recall @10
Relative latency
Relative memory
Production tuning is a target game: pick a recall floor (say 95%), then find the smallest efSearch and M that clear it — because every extra point of recall past "good enough" is paid in latency and RAM.

Why a graph, and why layers

Embeddings turn meaning into geometry: similar things sit close in a high-dimensional space, so "find similar" becomes "find nearest." The exact answer means measuring distance to every vector — fine for thousands, hopeless for billions. Approximate nearest-neighbor search buys enormous speed by accepting the occasional miss.

HNSW's insight borrows from the skip list. A skip list adds express lanes over a sorted list so search skips ahead instead of stepping one-by-one. HNSW does the same in space: build a proximity graph (each node linked to its near neighbors), then stack sparse upper layers over it. Search starts at the top — few nodes, huge jumps — and greedily walks toward the query, descending a layer each time it can't get closer, refining as the graph gets denser.

The payoff

Search cost drops from O(N) to roughly O(log N). That logarithm is why the same query is milliseconds whether your index holds a million vectors or a billion — you visit a tiny, near-constant fraction either way.

The knobs that matter

M — connections per node — sets graph richness: higher M means more paths to the right neighborhood (better recall) but more memory and slower builds. efConstruction controls build-time quality; efSearch controls query-time width — how many candidates the greedy search keeps in play. Bigger efSearch explores more, recovers more true neighbors, and costs more time. Tuning HNSW is choosing where on the recall-latency-memory surface you want to live.

Why it's everywhere

Every serious vector database — FAISS, hnswlib, Qdrant, Weaviate, Milvus, pgvector — defaults to HNSW because that balance is hard to beat. When your RAG pipeline retrieves in single-digit milliseconds over millions of chunks, this graph is doing the walking.

Check yourself

Four questions. Navigate them like the graph.

Finished this one? 0 / 22 Labs done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

More Labs