HNSW Algorithm — Interactive Visualization

Hierarchical Navigable Small World graphs for Approximate Nearest Neighbor search

🏗️
1. Build the Graph
The page starts with 30 points. Add more with + Add 10 Points or by clicking a layer. Each point gets a random top level, so higher layers hold exponentially fewer points.
🔍
2. Run a Search
Click Search Nearest to drop a random query (◆), or switch the canvas to search mode and click where you want it.
👣
3. Step Through
Use Prev / Next, ▶ Play or the ← → keys. The result is checked against an exact brute-force search.
highway levels
links/node
build beam
query beam
Canvas click:
Entry point Node Distance computed Being expanded In result list (ef) Query Edge taken Edge checked, rejected

What's Happening

Loading…
Distance: Euclidean
√((x₁−x₂)² + (y₁−y₂)²)
How HNSW Works

HNSW builds a multi-layer graph. Think of it like a city's transport network: highways (top layers) let you travel far quickly, then local roads (bottom layer) take you exactly where you need to go.

  • Layer 0 (bottom): contains all points, each linked to up to 2M near neighbours.
  • Higher layers: each point's top level is drawn as ⌊−ln(U)·mL⌋ with mL = 1/ln(M), so every layer keeps about 1/M of the one below.
  • Insertion: greedily descend to the new point's top level, then on each lower layer run a beam search (efConstruction) and link to M neighbours picked by a diversity heuristic. Neighbours that exceed their degree cap are pruned.
  • Search: greedy (ef = 1) on upper layers to find a good starting point, then a beam search with efSearch on layer 0. The search stops once the closest unexplored candidate is farther than the worst result.

Result: roughly logarithmic search cost even for millions of points, with high recall.

Understanding the Parameters
  • Layers: a display cap on the number of levels. Real HNSW has no cap; the number of levels grows like log(n) on its own.
  • M: links per node (2M on layer 0). Higher M means a denser graph, better recall, more memory and slower inserts. Typical production values: 8–48.
  • efConstruction: beam width used while inserting. Higher gives better links (and better recall later) at the cost of build time.
  • efSearch: beam width on layer 0 at query time. This is the main speed/recall knob: try efSearch = 1 and watch the search get stuck in a local minimum.

Changing Layers, M, efConstruction or the distance metric rebuilds the index from the same points, so you can compare settings on identical data.

Why is HNSW Useful?

Exact nearest neighbor search in high-dimensional spaces (like embeddings from LLMs) is extremely slow — you'd have to compare every point. HNSW trades a tiny bit of accuracy for massive speed gains:

  • Search cost grows roughly as O(log n) instead of O(n)
  • Typically reaches 95–99% recall with well-chosen M and ef
  • Used by FAISS, hnswlib, pgvector, Qdrant, Weaviate, Milvus and many other vector stores