HNSW
Hierarchical Navigable Small World: a multi-layer proximity graph. Upper layers give long-range shortcuts, lower layers refine locally — log-scale search with state-of-the-art recall.
Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs
Malkov, Y. A.; Yashunin, D. A.
IEEE TPAMI 2020
Introduces a multi-layer proximity graph that achieves logarithmic-scaling ANN search with state-of-the-art recall/latency trade-offs.
Read paper at official venue →At a glance
HNSW (Hierarchical Navigable Small World) is a graph-based ANN index. Each inserted vector joins multiple layers; upper layers carry long-range edges, lower layers dense local ones. A greedy descent from the top entry point reaches the query's neighborhood in logarithmic steps. It remains the state-of-the-art recall/latency trade-off for in-memory workloads up to a few hundred million vectors.
Parameters
| Option | Default | Notes |
|---|---|---|
| m | 16 | Out-degree cap on upper layers; M0 = 2·m on layer 0. |
| ef_construction | 128 | Candidate pool size during build. Larger = better graph quality at build-time cost. |
| ef_search | 64 | Beam width at query time. Tune up for recall, down for latency. |
| quantizer | 'rabitq' | Any of flat / rabitq / pq / scann. |
Example
CREATE INDEX docs_idx ON docs USING HNSW (embedding)
WITH (metric='cosine', quantizer='rabitq', bits=3,
m=16, ef_construction=128, ef_search=64);