HNSW (Hierarchical Navigable Small World) is the most widely used index for approximate nearest-neighbor search in vector databases. It builds a multi-layer proximity graph: sparse upper layers act as express lanes for covering distance fast, and dense lower layers refine locally. A search greedily hops toward the query through the top layer, then descends, finding near-neighbors in roughly logarithmic time instead of scanning every vector.

Why not just compare the query to every vector?

Brute-force (exact) search compares the query to all N vectors — perfect recall, but O(N) per query. At millions or billions of vectors that is too slow and expensive for real-time retrieval. HNSW trades a tiny bit of recall for a massive speedup: it visits only a small fraction of vectors by navigating the graph, returning results in milliseconds.

What is the recall vs latency trade-off in HNSW?

HNSW is approximate: it may occasionally miss the true nearest neighbor. Parameters tune the trade-off — a larger search width (efSearch) explores more candidates for higher recall at higher latency, while more connections per node (M) build a richer graph that improves recall but costs more memory and build time. Production systems tune these to hit a recall target (e.g. 95%) at the lowest latency.

In essentially every modern vector database and retrieval system — powering semantic search, RAG retrieval, recommendation, and deduplication over embeddings. It is the default index in libraries and databases like FAISS, hnswlib, Qdrant, Weaviate, Milvus and pgvector because it offers an excellent recall-latency-memory balance.

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 (or focus + Enter) 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 (or focus + Enter) to drop a query · then Race

Brute force · comparisons

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 — the numbers below are a teaching model of that shape, not a benchmark off a real index.

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 / 61 Labs done

Explore the topic

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

RAG & Retrieval

The Skip-List
of Space.

Why a graph, and why layers

The knobs that matter

Why it's everywhere

Check yourself

Explore the topic

More Labs

Explore more from Vibe Engines

Why a graph, and why layers

The knobs that matter

Why it's everywhere

Check yourself

Keep going

Vector Database →

Vector Databases →

Embedding Cost Calculator →

Top-K Retrieval →

Explore the topic

More Labs

Explore more from Vibe Engines