Skip to content

LearnIndex & store

HNSW

Hierarchical navigable small world

A vector index made of layered neighbor graphs: sparse upper layers for long jumps, a dense bottom layer holding every vector for the final, precise steps.

In DocSlurpIllustrated explainer

On this page
HNSW search descends through layers of neighbor graphsThree stacked layers hold the same vectors. Layer 2, at the top, has 3 nodes joined by long links; layer 1 has 7; layer 0 has all 18 joined to their near neighbors. A query star sits at the same spot on every layer. Search enters at the top layer's leftmost node and makes one long jump across the layer to the node nearest the query there. It drops to that same node on layer 1, hops once to a closer node, drops to layer 0, and hops once more to the true nearest neighbor. Each layer narrows the search before the next, denser layer refines it.Layer 23 nodes · long jumpsLayer 17 nodes · medium jumpsLayer 018 nodes · every vectorenternearest
Sparse layers make the long jumps, dense layers make the precise ones. The top layer crosses the whole space in one hop. Each drop lands on the same vector one layer down, where more neighbors let the search close in. Every vector lives on layer 0, and each one appears higher up with shrinking probability, much like the express lanes of a skip list.

The problem: a graph walk that starts too far away

The simplest graph index links every vector to a few near neighbors and searches by walking: from the current point, hop to whichever neighbor is closest to the query, and stop when none is closer. (See the walk in approximate nearest neighbor search.)

On a large collection, that walk has two problems. Short links mean small steps, so crossing a million vectors from a random starting point takes many hops. And a greedy walker stops at the first point with no closer neighbor, which may be a local dead end, nowhere near the true nearest vector.

The idea: express lanes

HNSW (hierarchical navigable small world, Malkov and Yashunin, 2016) fixes both by stacking graphs, like the express and local lines of a subway, or the levels of a skip list.

  • Layer 0 holds every vector, each linked to its near neighbors.
  • Each higher layer holds a random subset of the layer below, about a constant fraction of it. A vector’s top layer is drawn at random when it is inserted, so most vectors live only on layer 0, a few reach layer 1, and very few reach the top.
  • Links on the sparse upper layers are long, because the nodes there are far apart. They are the express lanes.

How a search descends

The figure has 18 vectors: 3 on layer 2, 7 on layer 1, all 18 on layer 0.

  1. Enter at the top. The search starts at a fixed entry point on layer 2, at the far left.
  2. Walk greedily on that layer. Of its two neighbors, the one at the far right is closest to the query. One hop crosses nearly the whole space.
  3. Drop down. The same vector exists on layer 1. The search continues from it, now with more neighbors to choose from, and hops to a closer one.
  4. Drop again and finish. On layer 0 every vector is present, and one more hop reaches the true nearest neighbor.

Each layer narrows the region before a denser layer refines it. On average the number of hops grows with the logarithm of the collection size, which is why HNSW can search millions of vectors while measuring only a small fraction of them.

The candidate list keeps it from getting stuck

The figure follows a single best point. Real HNSW keeps a list of the ef best candidates found so far on layer 0 (the search breadth). It expands the closest unexplored candidate, adds any of its neighbors that beat the worst in the list, and stops when no candidate can improve the list. A larger ef explores more of the neighborhood, so fewer true neighbors are missed, at the cost of more distance computations. ef must be at least k to return k results.

Two build-time settings shape the graph:

  • M: how many neighbors each vector links to. More links give better recall and use more memory.
  • efConstruction: how wide the search is when inserting a vector and choosing its links. Wider builds better graphs, more slowly.

Where it breaks

  • Memory. The graph stores M links per vector on layer 0 and more on upper layers, on top of the vectors themselves. HNSW is usually kept in memory or a fast cache, and is often paired with quantization to shrink the vectors.
  • Deletes and updates are awkward. Removing a node leaves holes in its neighbors’ link lists. Many systems mark deleted rows and rebuild periodically.
  • Builds are slow compared with queries. Every insert runs a search. Bulk loads and rebuilds of large tables take noticeable time and CPU.
  • Filters can disconnect the graph. If a filter excludes most nodes, the remaining ones may not be linked to each other, and the walk can’t reach them. Engines either search wider, fall back to exact search, or filter during traversal.
  • Recall is high, not perfect. Settings that give 99% recall on one dataset may give less on another. Check recall against exact search on your own data.

When to use it

HNSW is a strong default for in-memory vector search from tens of thousands to many millions of vectors when query latency matters most. For very large collections where memory is the limit, cluster-based indexes (IVF) with product quantization trade more recall for much smaller footprints.

In DocSlurp

When a project’s LanceDB table reaches 1,000 rows, maintenance builds IVF_HNSW_SQ: HNSW graphs over 8-bit scalar-quantized vectors, using L2 distance, with one IVF partition per million rows. Below a million rows that is a single HNSW graph. DocSlurp keeps LanceDB’s default of 20 neighbors per vector. New rows are added as extra index segments during routine maintenance, and when segments pile up, tables of up to 100,000 rows have them consolidated into one index. When a search is scoped to specific documents, DocSlurp raises ef to 1.5 × min(max(10 × limit, documents × limit), 1,000), so 20 results from 3 documents search with ef = 300.

In DocSlurp

In DocSlurp

LanceDB builds Index.hnswSq (HNSW over 8-bit scalar-quantized vectors) with L2 distance once a table holds 1,000 rows, using one partition per million rows (core/worker/src/stages/lancedb-maintenance.ts). Scoped queries raise the search breadth ef (core/server/src/search/lancedb-query-tuning.ts).

Sources

Jump to