HNSW: How Vector Databases Search at Scale (2D)

Index Parameters

Documents indexed 180

Max connections M 5

Search breadth ef 12

Search Trace

Index built. Click anywhere on the canvas to place a query point, or press "Random Query".

HNSW dist. calcs

Current layer

—

Brute-force dist. calcs

Speedup

—

Recall@10 vs brute force

—

How it works

Real vector databases (Pinecone, Weaviate, FAISS-HNSW) never scan every embedding for a RAG query — that's O(N). Instead they build HNSW: a proximity graph with several stacked layers, computed here from scratch in plain JavaScript. Each document gets a random top layer:

P(level ≥ l) = exp(-l / mL),  mL = 1 / ln(M)

so layer 0 holds every document, layer 1 holds roughly 1/M of them, layer 2 holds 1/M² and so on — a skip-list in embedding space. A query enters at the single top-layer entry point and greedily hops to whichever connected neighbor is closest, one layer at a time:

for lc = topLayer downto 1:
    ep = greedy_nearest(query, ep, layer[lc])   // ef=1, one best hop
for layer 0:
    candidates = beam_search(query, ep, layer[0], ef)
return top-k of candidates

Only at the dense bottom layer does the search widen to a beam of ef candidates for accuracy. This turns an O(N) linear scan into roughly O(log N) hops — watch the "HNSW dist. calcs" counter next to the "brute-force dist. calcs" counter (every one of the N points, always) to see the gap grow as you raise the document count.

M — max graph connections per node; higher M means a denser, more accurate but heavier index.
ef — how many candidates the layer-0 beam keeps; higher ef trades speed for recall.
Recall@10 — the fraction of the true 10 nearest neighbors (brute-force ground truth) that HNSW actually found.

Click canvas to set query point

Graph edges (per layer) Query / greedy path HNSW top-k result Brute-force scan (all points)