Advanced8 min read

What is HNSW?

HNSW is the most popular approximate-nearest-neighbor index: a layered graph you search top-down — big jumps in sparse upper layers, fine refinement in the dense bottom layer.

Explain like I'm new to AI

HNSW (Hierarchical Navigable Small World) is the index behind most fast vector search today. The idea is a multi-layer map of shortcuts.

The top layer has only a few points connected by long-distance links — great for covering ground quickly.
Each layer below adds more points and shorter links.
The bottom layer contains every point with fine-grained local links.

Search starts at the top, jumps close to the target, then drops down layer by layer to zero in. Step through it:

Step 1/6: Enter at the top layer — few nodes, long jumps.

HNSW searches top-down: sparse upper layers make big jumps, dense lower layers refine — fast search over millions of vectors.

Mental model

Think of travel: first take a plane across the country (top layer, long jumps), then a train to the city (middle layer), then walk to the exact address (bottom layer). Each level gets you closer with finer movements — far faster than walking the whole way.

How it works

Enter at a single point in the top (sparsest) layer.
Greedily move to whichever neighbor is closer to the query.
When no neighbor is closer, drop down one layer and continue.
At the bottom layer, the greedy walk lands on the nearest neighbors → return top-k.

This "coarse-to-fine" navigation is why HNSW is both fast and high-recall.

Real-world example

HNSW (via the popular open-source implementation used by many vector databases) powers low-latency semantic search over millions of documents. You typically get 95–99%+ recall with millisecond queries — the reason it's the default index in so many systems.

Technical explanation

HNSW generalizes the skip-list idea to a graph. Key parameters:

M — links per node. Higher M → better recall and connectivity, but more memory.
efConstruction — search breadth while building the graph; higher → better graph quality, slower build.
efSearch — candidate list size at query time; higher → better recall, higher latency.

Strengths: excellent recall/latency, supports incremental inserts. Trade-offs: it's memory-hungry (the graph lives in RAM) and deletions are awkward. That memory cost is often addressed by combining HNSW with quantization. Complexity is roughly O(log N) search vs. brute force's O(N).

Common mistakes

Common mistake

Leaving efSearch at its default and wondering why recall is low (or latency is high). This one knob directly trades recall for speed at query time — tune it to your target.

Ignoring HNSW's RAM footprint when planning capacity.
Expecting cheap deletions — heavy churn may require periodic rebuilds.

When to use it

The default choice for fast, high-recall vector search when data fits in memory.

When NOT to use it

Extremely memory-constrained or billion-scale settings where IVF + quantization is more economical.

Alternatives

IVF (cluster-based) and quantization (PQ) — often combined for very large, memory-tight indexes.

Quick quiz

Related concepts

Exact vs Approximate Nearest Neighbor — Exact search compares every vector and is always right but slow; approximate (ANN) search checks a smart subset for huge speed with a small recall trade-off.
IVF & Product Quantization — IVF narrows search to a few clusters; Product Quantization compresses vectors into compact codes — together they make billion-scale vector search fit in memory.