Vector HNSW Index

HNSW stands for Hierarchical Navigable Small World. It is the most widely used index in production vector databases. Pinecone, Weaviate, Qdrant, and Milvus all use HNSW or a variant of it. This topic explains how it works and how to tune it.

The Skip List Analogy

Imagine a train system with three types of routes:

• Express trains — stop at major cities only, cover large distances fast
• Regional trains — stop at medium towns
• Local trains — stop at every small village

To travel from London to a tiny village near Edinburgh, you take the express to Edinburgh, then regional to the nearest town, then local to the village. You never sit on a local train from London — that would take forever.

HNSW uses exactly this hierarchy — but for navigating vector space.

How HNSW Is Structured

HNSW LAYERS (each layer is a graph):

Layer 2 (top, sparse):     ●─────────────────●
  Few nodes, long jumps     \               /
                             \             /
Layer 1 (middle):          ●──●───────────●──●
  More nodes                   \         /
                                \       /
Layer 0 (bottom, dense): ●─●─●──●─●─●─●──●─●─●
  All nodes, short links

SEARCH: Start at top → navigate fast → drill down → find neighbors

Every vector lives in Layer 0. A randomly selected subset also appears in Layer 1, and a smaller subset in Layer 2 and above. Connections in higher layers span greater distances, enabling fast navigation. Connections in Layer 0 are precise and local.

Building the Index Step by Step

INSERT new vector V:

1. Randomly assign V to a max layer (most land in Layer 0 or 1)
2. Start at the top layer
3. Find V's nearest neighbors in that layer
4. Connect V to those neighbors with edges
5. Move down one layer, repeat
6. At Layer 0, connect V to its closest local neighbors

Result: V is now woven into the graph at every layer it occupies

Searching the Index Step by Step

SEARCH for query Q, find top-5 nearest vectors:

Layer 2: Enter at a random entry point
         Jump to whichever neighbor is closest to Q
         (big jumps, fast progress)
         ↓
Layer 1: Start near where Layer 2 ended
         Refine — smaller jumps, closer to target
         ↓
Layer 0: Fine-grained local search
         Explore all neighbors of the best candidates
         Return the 5 closest vectors found

Total comparisons: ~log(n) instead of n

The Two Key Parameters

M — Number of Connections per Node

M controls how many edges each vector gets in the graph. Higher M means more connections, more accurate search, but more memory and longer build time.

ef_construction — Build-time Search Width

ef_construction controls how carefully the index searches for neighbors during the build phase. Higher values find better neighbors and produce a higher-quality graph, but slow down index construction.

ef_construction = 64:  builds faster, slightly lower recall
ef_construction = 128: balanced (common default)
ef_construction = 256: builds slower, higher recall graph

ef_search — Query-time Search Width

ef_search controls how wide the search explores at query time. You can change this without rebuilding the index.

ef_search = 50:  faster queries, lower recall
ef_search = 100: balanced
ef_search = 200: slower queries, higher recall

RULE: ef_search must be ≥ k (the number of results you want)

HNSW Strengths and Weaknesses

Recommended Starting Parameters

For most production applications:

  M              = 16
  ef_construction = 128
  ef_search       = 100
  Distance metric = Cosine (text) or L2 (images)

Then tune:
  ↑ ef_search   to improve recall (at cost of speed)
  ↑ M           to improve recall (requires index rebuild)
  ↑ ef_construction to improve index quality (requires rebuild)

HNSW delivers an exceptional balance of speed and accuracy for datasets ranging from hundreds of thousands to tens of millions of vectors. For datasets above 100 million vectors, combining HNSW with product quantization (covered in Topic 8) becomes necessary to manage memory costs.