4. HNSW: Hierarchical Navigable Graphs

Overview

HNSW (Hierarchical Navigable Small World) is the most used index in modern vector databases (Pinecone, Weaviate, Qdrant). Here you'll understand how it works conceptually: it's a multi-layer graph where you "navigate" by hopping from nearby node to nearby node until you reach the right region.

The core idea

Analogy: Finding a house in a big city:

The slow method (brute force):

Visit EVERY house, measure the distance to each one
Return the closest

The fast method (HNSW):

Start on the highway (the top layer: big hops)
Take the exit closest to your destination
Drop down to local streets (the bottom layer: small hops)
Navigate street by street to the specific house

HNSW does the same thing with vectors: multiple layers from "highways" to "streets" to "houses".

The layer structure

Layer 2 (Highway):
•────────────────•────────────────•
(Few nodes, big hops)

Layer 1 (Avenues):
•─────•─────•─────•─────•─────•─────•
(More nodes, medium hops)

Layer 0 (Streets):
•─•─•─•─•─•─•─•─•─•─•─•─•─•─•─•─•─•
(Every vector, small hops)

Each node = one vector from the dataset

Edges = connections to nearby neighbors

The search algorithm (simplified)

1. Start at the top layer (the highway)
   - Entry point: a random node

2. For each layer (from top to bottom):
   - Navigate to the neighbor closest to the query
   - Repeat until there's no closer neighbor
   - Drop down to the next layer

3. At layer 0 (every vector):
   - Navigate looking for the K nearest neighbors
   - Return the top-K

Visual example (simplified in 2D)

Query: ⭐

Layer 2 (highway):

A•─────────────•B
              ╱
             ╱
Entry→    •C

You navigate: C → B (B is closer to ⭐)

Layer 1 (avenues):

A•───•D───•E───•B
     │    │
     •F───•G
           ↑ ⭐ is near G

You navigate: B → E → G (G is closer to ⭐)

Layer 0 (streets - every vector):

•D───•H───•E───•I
│    │    │    │
•F───•J───•G───•K
     │    ↑│   │
     •L───⭐•M─•N

From G, you find M (the nearest neighbor to ⭐) → Result! ✅

Advantages of HNSW

1. Very fast:

Complexity: O(log N) instead of O(N)
With 1M vectors: ~20 hops vs 1M computations

2. High precision:

Typically ~98-99% of the true top-K

3. Scalable:

It works with millions/billions of vectors

4. No retraining needed:

You can add vectors dynamically (though a periodic rebuild improves quality)

Disadvantages of HNSW

1. Memory usage:

Each node stores connections to its neighbors (the graph's edges)
Typically 2-3x more memory than just storing the vectors

2. Build time:

Building the graph takes time (hours for billions)
Trade-off: a slow build once, very fast searches afterward

3. Not optimal for bulk inserts:

Adding 1M new vectors → a full rebuild is better than inserting them one by one

Configuration parameters

ef_construction (build):

ef_construction = 100 → A lower-quality graph, a fast build
ef_construction = 400 → A high-quality graph, a slow build

ef_search (search):

ef_search = 50  → A fast search, ~95% precision
ef_search = 200 → A slow search, ~99% precision

M (the number of connections per node):

M = 16 → Less memory, lower precision
M = 64 → More memory, higher precision

A typical trade-off: ef_construction=200, ef_search=100, M=32

HNSW in production

Pinecone:

HNSW by default
Parameters optimized automatically

Weaviate:

HNSW with manual configuration (ef_construction, M)
Recommendation: ef_construction=128, M=32

Qdrant:

Optimized HNSW with a quantization option
Recommendation: ef_construct=200, M=16

Summary

Key points:

HNSW: A multi-layer graph (highways → streets)
Navigation: Hopping from neighbor to neighbor until you find the right region
Advantages: Very fast (O(log N)), high precision (~99%)
Disadvantages: More memory, an upfront build time
Use: The standard in modern vector databases

Next capsule: 05-ivf-and-clustering.md — The alternative: IVF (clustering + search).