hnsw (hierarchical navigable small world)

HNSW (Hierarchical Navigable Small World) is a graph-based algorithm for fast approximate nearest neighbor search. **Core idea**: Build multi-layer graph where higher layers have fewer nodes (long-range connections), lower layers are denser (local connections). Search from top, greedy descent. **Algorithm**: Start at top layer entry point, greedily move toward query, drop to lower layer, repeat until bottom layer. Returns approximate nearest neighbors. **Construction**: Insert nodes bottom-up, connect to closest neighbors at each layer. Probabilistic layer assignment. **Parameters**: **M**: Max connections per node. Higher = more accurate, more memory. **ef_construction**: Build-time search depth. **ef_search**: Query-time search depth (accuracy/speed trade-off). **Advantages**: Excellent recall/speed trade-off, no training required, supports incremental inserts. **Disadvantages**: High memory (stores graph), slower construction than some alternatives. **Comparison**: Generally outperforms IVF on accuracy at same speed. Standard choice for many vector databases. **Use by**: Pinecone, Weaviate, Qdrant, pgvector, Milvus all offer HNSW. **Best for**: When accuracy matters and memory is available. Most common choice for production similarity search.