What is HNSW (Hierarchical Navigable Small World)?
HNSW (Hierarchical Navigable Small World) is a graph-based approximate nearest neighbor (ANN) index used by many vector databases. It builds a multi-layer graph where each node is a vector: the top layer has few nodes and long “skip” links for fast coarse search, and lower layers add more nodes and local links for fine-grained nearest-neighbor search.
Summary
- Search starts at the top layer, follows the graph toward the query, then drops layer by layer; at the bottom, greedy or beam search returns approximate k-NN. Good balance of recall and latency.
- Combines small-world graphs and skip-list–style hierarchy. Key parameters: M, efConstruction, efSearch.
- Supports L2 and inner product (cosine via normalized vectors); graph structure assumes a metric for pruning. Incremental insertions supported without full rebuild.
- Pipeline: build graph with chosen M and efConstruction; at query time set efSearch to tune recall vs. latency; higher efSearch improves recall at higher cost.
- Trade-off: high recall and low latency vs. memory and build time; use when in-memory graph is feasible; consider IVF or disk-backed options at very large scale.
How search works
Search starts at the top layer from an entry point, follows the graph to get closer to the query vector, then drops to the next layer and repeats. At the bottom layer, a greedy or beam search finds the approximate k nearest neighbors.
This gives a good balance of recall and latency and is one of the most widely used ANN algorithms in production. Practical tip: start with default M (e.g. 16) and efConstruction (e.g. 100–200); tune efSearch at query time (higher = better recall, slower). See trade-off between recall and latency in HNSW for the recall–latency curve.
Pipeline summary: create a collection with HNSW and your chosen metric (L2 or IP/cosine); set M and efConstruction at build time. At query time, set efSearch to balance latency and recall; measure recall@k and p99 latency on your workload. Memory consumption of HNSW indexes and how HNSW handles high-dimensional data affect scaling; for very large or disk-bound datasets, consider combining with IVF or disk-ANN.
Design and parameters
HNSW combines ideas from small-world graphs (short paths between distant nodes) and skip lists (hierarchical levels). Key parameters include M (links per node), efConstruction (candidate list size during build), and efSearch (candidate list size during query), which control index quality, build time, and query speed.
Trade-off: larger M and efConstruction improve recall and graph quality but increase build time and memory; efSearch trades query latency for recall. For memory and high-dimensional behavior, see memory consumption of HNSW indexes and how HNSW handles high-dimensional data.
When to use HNSW
HNSW is a strong default when you want high recall at low latency and can afford in-memory graph storage. It supports incremental insertion, so you can add vectors over time without rebuilding. For comparison with cluster-based methods and when to choose graph vs. IVF, see comparing graph-based vs. cluster-based indexes and what is IVF (inverted file index).
Frequently Asked Questions
Is HNSW exact or approximate?
Approximate. It returns neighbors that are usually among the true k-NN but doesn’t guarantee it; recall depends on M, efConstruction, and efSearch.
What distance metrics does HNSW support?
Typically L2 and inner product (cosine when vectors are normalized). The graph and search use the same metric; see metric properties.
How does HNSW compare to IVF?
HNSW is graph-based; IVF is cluster-based. HNSW often gives better recall for a given latency but uses more memory; IVF can scale to very large datasets with quantization.
Can I add vectors after building?
Yes. HNSW supports incremental insertion; no full rebuild required, though insertion order can affect graph quality. See incremental building of HNSW graphs.