HNSW

HNSW (Hierarchical Navigable Small World) is one of the most effective algorithms for approximate nearest neighbor search in high-dimensional vector spaces. It constructs a multi-layer graph where each layer is a navigable small-world network with progressively fewer nodes, enabling fast hierarchical search from coarse to fine granularity.

The algorithm works by starting the search at the top layer (fewest nodes, longest-range connections) and greedily navigating toward the query vector. At each layer, it finds the closest node, then descends to the next layer where more nodes and shorter-range connections allow finer search. This hierarchical approach achieves O(log n) search complexity with high recall.

HNSW is the default index type in many vector databases (including Pinecone, Weaviate, and FAISS) because it offers the best balance of search speed, accuracy, and memory efficiency for most use cases. Key tuning parameters include M (the number of connections per node, affecting memory and accuracy) and efConstruction/efSearch (controlling the search thoroughness during index building and querying). Higher values improve accuracy at the cost of speed and memory.