HNSW Hierarchical Navigable Small World
Hierarchical Navigable Small World — the dominant graph-based algorithm for approximate nearest-neighbor search among vectors. It builds a multi-layer "small world" graph where the search hops from coarse to fine layers. Fast and accurate, but memory-hungry.
Mechanic: vectors are linked in a graph where each node has neighbors; the top layer is sparse (long hops), the bottom dense (fine-tuning). A search starts high up, "glides" toward the target, and refines downward → logarithmic search time. Parameters: M (neighbors per node) and ef (search breadth) control the speed/memory/accuracy trade-off. Win: excellent recall at high speed, incremental inserts. Trade-off: high memory use (the whole graph in RAM) and a more expensive build than IVF. The default choice in pgvector, Qdrant, Weaviate, FAISS for most workloads. Distinct from IVFFlat (cluster-based, less memory but usually lower recall). The most common vector index type in 2024.