HNSW: The Algorithm That Makes Vector Search Feel Instant

You have 10 million document embeddings. A user searches "how to deploy ML models on Kubernetes." You need to find the 10 most similar vectors — in under 50 milliseconds.

Brute force? Compare the query against all 10 million vectors. That's 10 million cosine similarity calculations. At 768 dimensions each. Every single query.

It works for 10,000 vectors. At 10 million, you're waiting seconds. At a billion, forget it.

You need approximate nearest neighbor (ANN) search. And the algorithm that dominates the field right now is HNSW — Hierarchical Navigable Small World. It's what powers Qdrant, Pinecone, Weaviate, pgvector, and basically every serious vector database.

The Small World Idea

Before HNSW, let's understand the insight it's built on: small world networks.

You've heard of "six degrees of separation" — any two people on Earth are connected through at most six friendships. That's a small world property.

The key insight: in a small world network, you can reach any node from any other node in very few hops — even though each node only has a few connections.

HNSW builds this kind of network for vectors. Each vector is a node. Edges connect similar vectors. To find the nearest neighbor to a query, you don't check all vectors — you navigate the graph, hopping from node to node, getting closer with each hop.

The Navigation Problem

Imagine you're in Mumbai and need to reach a specific gully in Bangalore. Two strategies:

Strategy 1: Check every gully in India. Correct but impossibly slow.

Strategy 2: Navigate.

Take a flight to Bangalore (long-distance jump)

Take a cab to the neighborhood (medium-distance)

Walk through the lanes to the exact gully (short-distance)

Each step narrows your search. You never check every location — you use the structure of the network to zoom in efficiently.

HNSW does exactly this, but with vectors and graph layers.

🔧

How HNSW Works: The Layers

HNSW builds a multi-layer graph where each layer has different density:

Layer 2 (sparse): A ——————————— F ——————————— K

Express highways — few nodes, long connections

Layer 1 (medium): A —— C —— F —— H —— K —— M

State roads — more nodes, medium connections

Layer 0 (dense): A B C D E F G H I J K L M N

Gully lanes — all nodes, short connections

The Rules

Every vector exists in Layer 0 (the bottom, densest layer)

Fewer vectors exist in higher layers — each layer has roughly 1/M of the layer below

Connections in higher layers span longer distances — like express highways

Connections in lower layers are short-range — local neighborhood links

The Search Algorithm

When a query comes in:

1. Start at the TOP layer (Layer 2)

→ Find the closest node using the sparse, long-distance connections

→ "Take the express highway to the right region"

1. Drop to Layer 1

→ Starting from the entry point found above

→ Navigate the medium-density graph, getting closer

→ "Take state roads to the right neighborhood"

1. Drop to Layer 0

→ Starting from the entry point found above

→ Navigate the dense graph, finding the exact nearest neighbors

→ "Walk through the lanes to the right doorstep"

At each layer, the algorithm does a greedy search: look at all neighbors of the current node, jump to the one closest to the query, repeat until no neighbor is closer than the current node.

Why This Is Fast

Instead of checking 10 million vectors, you check maybe:

Layer 2: 5-10 nodes

Layer 1: 20-50 nodes

Layer 0: 100-300 nodes

Total comparisons: ~200-400 out of 10 million. That's why it's fast. O(log n) instead of O(n).

📊

Building the Index

The index is built by inserting vectors one at a time:

For each new vector:

1. Randomly assign it to a layer level

(most get Layer 0, few get Layer 1, fewer get Layer 2)

1. Starting from the top layer, find its nearest neighbors
2. Create bidirectional edges to those neighbors
3. Repeat for each layer the vector exists in

The random layer assignment follows an exponential distribution — probability decreases exponentially with layer height. This naturally creates the sparse-to-dense hierarchy.

The Key Parameters

Parameter What It Controls Typical Value Trade-off

M = 16 means each vector connects to at most 16 neighbors per layer. More connections = higher recall but more memory.

ef_construction controls how many candidates you consider when inserting a new vector. Higher = better quality connections but slower indexing.

ef_search controls how many candidates you explore during a query. This is the knob you turn at runtime to trade speed for accuracy.

Approximate vs Exact: The Trade-off

HNSW is an approximate algorithm. It doesn't guarantee finding the absolute nearest neighbor — it finds one that's very close, very fast.

Exact search: 100% recall, 500ms latency

HNSW (ef=50): 95% recall, 5ms latency

HNSW (ef=200): 99% recall, 15ms latency

HNSW (ef=500): 99.9% recall, 40ms latency

Recall = what percentage of the true top-K nearest neighbors did we actually find?
For most applications, 95-99% recall is indistinguishable from perfect. The user won't notice if result #8 should have been result #7. But they'll absolutely notice if search takes 500ms instead of 5ms.

HNSW vs Other ANN Algorithms

HNSW isn't the only game in town:

Algorithm How It Works Strengths Weaknesses

HNSW wins for most use cases because:

No training phase — add vectors and go

Best recall-to-speed ratio

Supports dynamic inserts and deletes

Every major vector DB implements it

The catch? Memory. HNSW needs the entire graph in RAM. For 10 million 768-dim vectors with M=16:

Vector storage: 10M × 768 × 4 bytes = ~30 GB
Graph edges:    10M × 16 × 2 layers × 8 bytes = ~2.5 GB

Total: ~32.5 GB RAM

That's a lot. For billion-scale search, you need either very beefy machines or disk-based alternatives like DiskANN.

🔬

How Vector Databases Use HNSW

Every major vector DB puts its own spin on HNSW:

Qdrant: HNSW + scalar/product quantization + on-disk option

Pinecone: Modified HNSW (proprietary)

Weaviate: Custom HNSW with dynamic ef

Chroma: HNSW via hnswlib (open source)

pgvector: HNSW + IVFFlat in PostgreSQL

Milvus: HNSW + IVF + DiskANN options

The core algorithm is the same. The differences are in memory management, quantization, filtering, and distributed operation.

🛡️

Try It Yourself

Build a mini HNSW index with Python:

python

import hnswlib

import numpy as np

Generate 10,000 random 768-dim vectors

dim = 768
num_elements = 10000
data = np.random.randn(num_elements, dim).astype('float32')

Build the index

index = hnswlib.Index(space='cosine', dim=dim)

index.init_index(max_elements=num_elements, ef_construction=200, M=16)

index.add_items(data, list(range(num_elements)))

Set search parameters

index.set_ef(50)  # Higher = better recall, slower

Query

query = np.random.randn(1, dim).astype('float32')

labels, distances = index.knn_query(query, k=10)

print(f"10 nearest neighbors: {labels[0]}")
print(f"Distances: {distances[0]}")

bash

pip install hnswlib numpy

python hnsw_demo.py

Indexes 10,000 vectors in ~0.5s

Queries in ~0.1ms

📦

Practical Takeaways

HNSW is THE algorithm for vector search — used by every major vector database

It works like navigating a city — start with highways (sparse upper layers), end with gully lanes (dense bottom layer)

It's approximate, not exact — but 99% recall at 10x speed is a great trade-off

ef_search is your runtime knob — tune it for your speed vs accuracy needs

Memory is the bottleneck — the entire graph needs to fit in RAM (or use disk-based variants)

No training required — unlike IVF, you just add vectors and start searching

🚀

What's Next?

Episode 18: Vector Databases — HNSW is just the search algorithm. A real vector database adds storage, filtering, metadata, replication, and APIs on top. Qdrant, Pinecone, Weaviate, Chroma — what's inside them, and how do you choose?

← Previous

Ep 16: Vector Similarity

Next →

Ep 18: Vector Databases

Next: Episode 18 — Vector Databases

You can't dump 50 million vectors into a Python list and call it a day. You need a vector database.

This is part of a 98-episode series covering AI engineering from tokens to production deployment.