HNSW: how a vector database finds neighbours fast
Comparing a query with millions of vectors is too slow. HNSW builds layered graphs and walks them greedily, from coarse to fine, to find a near neighbour in a handful of hops.
Interactive simulation. It needs JavaScript; the text below explains what it shows.
What you are looking at
Points in higher layers are rarer and drawn brighter. The search starts in the top layer, moves to whichever neighbour is closer to the query, drops a layer when it cannot improve, and repeats. The panel compares its distance computations with brute force.
Things to try
- Click anywhere to place a query and watch the hops.
- Raise M: more links, fewer misses, more memory.
- Use 900 points: brute force grows, the hop count barely does.
How it works in real systems
HNSW (Malkov and Yashunin, 2016) is the default index in pgvector, Qdrant, Weaviate, Milvus and FAISS. Real indexes keep a candidate list of size ef while searching, which trades speed for recall.
Code lab
The same idea in real code, step by step. Copy each block into a notebook or a file and run it in order.
Step 1 · Build an HNSW index
# pip install hnswlib numpy
import hnswlib, numpy as np
d, n = 128, 100_000
data = np.random.default_rng(0).normal(size=(n, d)).astype("float32")
index = hnswlib.Index(space="cosine", dim=d)
index.init_index(max_elements=n, ef_construction=200, M=16) # M: links per node, ef_construction: build-time beam
index.add_items(data, np.arange(n))
index.set_ef(50) # query-time candidate list: recall vs speed
labels, dist = index.knn_query(data[:5], k=10)
Step 2 · Measure recall against brute force
import time
q = np.random.default_rng(1).normal(size=(200, d)).astype("float32")
qn, dn = q / np.linalg.norm(q, axis=1, keepdims=True), data / np.linalg.norm(data, axis=1, keepdims=True)
truth = np.argsort(-(qn @ dn.T), axis=1)[:, :10]
for ef in (10, 50, 200):
index.set_ef(ef); t = time.time(); got, _ = index.knn_query(q, k=10)
rec = np.mean([len(set(a) & set(b)) / 10 for a, b in zip(got, truth)])
print(f"ef={ef:<4} recall@10={rec:.3f} {1000*(time.time()-t)/len(q):.2f} ms/query")
Step 3 · The same in FAISS and pgvector
import faiss
ix = faiss.IndexHNSWFlat(d, 32, faiss.METRIC_INNER_PRODUCT); ix.hnsw.efSearch = 64
ix.add(dn); D, I = ix.search(qn, 10)
CREATE INDEX ON items USING hnsw (embedding vector_cosine_ops) WITH (m = 16, ef_construction = 64);
SET hnsw.ef_search = 100;