Skip to content
Tutorials Center
My learning

Topics

Lesson 11 of 36 ยท Indexing and ANN Search

HNSW: Navigating a Graph of Neighbors

Understand how HNSW indexes work: greedy graph search, layers, and the M, efConstruction and efSearch settings, with a runnable graph index you build yourself.

HNSW (Hierarchical Navigable Small World) is the most widely used ANN index in vector databases. Pgvector, Qdrant, Weaviate, Milvus, Elasticsearch, OpenSearch and many others offer it, and for good reason: it answers queries in a fraction of a millisecond with recall above 0.95, and it handles inserts without retraining.

The idea is the one you use when you navigate a city by asking for directions: start somewhere, move to a neighbor that is closer to your destination, repeat until nobody nearby is closer. In this lesson you will build the core of it, then add the "hierarchical" part that makes it fast on big data.

The idea: a graph where neighbors point to neighbors

Store every vector as a node. Connect each node to a handful of its nearest neighbors. To search, begin at some entry node and repeatedly jump to whichever connected node is closest to the query. When no neighbor improves on the current node, stop. That is greedy search.

Pure greedy search can get stuck at a point that is closer than all its neighbors but not the true nearest. The fix is a beam: keep the best ef candidates alive instead of just one, expanding the most promising each step. The parameter ef (often written efSearch) is the dial between speed and recall.

flowchart LR
    S["Entry node"] --> A["Neighbors of entry"]
    A --> B["Pick closest unexplored candidate"]
    B --> C["Look at its neighbors"]
    C --> D{"Any better than the worst of the best ef?"}
    D -->|yes| B
    D -->|no| E["Return the best k"]

Beam search on a proximity graph.

Build a small navigable graph

Below is a teaching version of one HNSW layer. Each new point finds its approximate neighbors by searching the graph built so far, then links to them in both directions. A node may keep at most 2 * M links.

Python A single-layer proximity graph index

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the two columns together. With ef = 10 the search computes a little over 100 distances instead of 2,000, but misses many true neighbors; raising ef adds recall and cost. This teaching version is simpler than a production HNSW (one layer, basic pruning), so its recall is lower than a real engine would reach, but the shape of the tradeoff is the same as in the previous lesson.

The hierarchy: express lanes

A single flat graph has a weakness on very large data: you may need many hops to walk from the entry node to the right region. HNSW fixes this with layers:

  • Every vector lives in the bottom layer (layer 0), which holds the full graph.
  • A random, shrinking subset of vectors also lives in layer 1, a smaller subset in layer 2, and so on. Higher layers are sparse "express lanes" with long-range links.
  • A search starts at the top layer's entry point, greedily moves closer, then drops one layer, continues from where it landed, and so on. Only at layer 0 does it run the wide beam with ef.

A node's top layer is drawn at random so that each layer has roughly 1/M of the nodes of the one below, giving about log(n) layers. You can see the shape with a few lines:

Python How many nodes live on each layer?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every layer has about 16 times fewer nodes than the one below it (the output starts 1,000,000, 62,675, 4,005, 270, 15, 1), so the top layers are tiny and cheap to navigate, and the search gets near the target in a handful of hops regardless of collection size. That logarithmic behavior is why HNSW scales.

The three settings that matter

Setting Also called What it does Higher means
M m, max_connections Links kept per node Better recall, more RAM, slower build
efConstruction ef_construct Beam width while inserting Better graph quality, slower build
efSearch ef, search_ef Beam width while querying Better recall, slower queries

Typical starting points: M between 16 and 32, efConstruction 100 to 200, and efSearch at least k, often 50 to 200. M and efConstruction are fixed at build time; efSearch can change per query. See tuning and benchmarking for how to choose them with data.

Costs and caveats

  • Memory: the graph adds M links (4 to 8 bytes each) per vector on top of the vectors themselves, and HNSW expects the index to sit in RAM for speed. Combine it with quantisation to cut the vector part.
  • Deletes are awkward: removing a node leaves holes in the graph. Most engines mark nodes deleted and rebuild or repair the graph later (updates and deletes).
  • Filtering: applying a metadata filter after the graph walk can drop most results; good engines integrate filters into the traversal. Test filtered queries separately.
  • Build time: inserting a million vectors with a high efConstruction takes minutes to hours, so plan bulk loads.

When to choose HNSW

HNSW is the default pick for in-memory search when you want high recall at low latency, have enough RAM, and update data incrementally. Choose IVF when the data is huge and memory tight or when you can rebuild periodically; add compression when RAM is the constraint.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does greedy graph search do at each step?

    Greedy search follows edges toward the query; beam search keeps ef candidates to avoid dead ends.
  2. 2. Which setting can you change per query without rebuilding the index?

    efSearch only controls the beam width at query time; M and efConstruction shape the graph while it is built.
  3. 3. Why does HNSW have several layers?

    A random subset of nodes is promoted to each upper layer, giving long links and logarithmic search depth.
  4. 4. What is a common downside of HNSW?

    The graph links add memory, and removing nodes leaves holes that engines handle lazily.
  5. 5. You raise efSearch from 20 to 200. What happens most likely?

    A wider beam visits more nodes: higher recall at higher cost.

Summary

  • HNSW builds a proximity graph and searches it by walking from node to closer node with a beam of ef candidates.
  • Upper layers are sparse express lanes that make search depth grow logarithmically.
  • M and efConstruction set graph quality and memory at build time; efSearch trades recall for speed per query.
  • Costs: RAM, build time, awkward deletes, and care with filters.

Next: IVF: Searching Only the Nearest Clusters