Hierarchical Navigable Small Worlds (HNSW) | Pinecone

Abstraction: HNSW graph algorithm for approximate nearest-neighbor vector search

Key points:

• HNSW combines probability skip lists (Pugh, 1990) with navigable small world graphs to achieve (poly-)logarithmic search complexity.
• Multi-layer structure: top layers have long-range links for fast traversal; bottom layer (layer 0) has dense short-range links for accuracy. Entry always starts at the top (zoom-in first).
• Key parameters: M (neighbors per vertex), efConstruction (candidates during build), efSearch (candidates during query), M_max0 = M*2 for layer 0.
• Level multiplier m_L = 1/ln(M); ~97% of vectors land at layer 0, creating a sparse upper structure.
• Trade-offs: recall improves with higher M and efSearch but memory scales steeply with M (low M=2 already >0.5GB for Sift1M); product quantization can reduce memory at cost of recall.

Connections: Pinecone · Faiss · Approximate Nearest Neighbor · Vector Search · Hnsw

Source: https://www.pinecone.io/learn/series/faiss/hnsw/