HNSW: Hierarchical Navigable Small World
HNSW (Hierarchical Navigable Small World) — graph-based ANN algorithm, the most popular for vector DB. Builds a multi-layer graph: top layer sparse, bottom dense. Search: greedy descent from top to bottom. O(log N) complexity. Used in Qdrant, Pinecone, Weaviate, pgvector (opt-in). Parameters: M (connections per node, 16-64), ef_construction (build quality), ef (search quality).
Below: details, example, related terms, FAQ.
Details
- M: 16 default. Higher = better recall, more RAM
- ef_construction: 100-500. Index build quality — one-time cost
- ef: search-time param. Higher = better recall, slower. 32-200 typical
- Memory: 4-10x vector size due to graph links. 1M × 1536-dim FP32 → ~30 GB
- Recall: >95% at ef=100 for most datasets
Example
# pgvector HNSW
CREATE INDEX ON docs USING hnsw (embedding vector_cosine_ops)
WITH (m = 16, ef_construction = 64);
-- Query tuning
SET hnsw.ef_search = 100; -- runtime param
SELECT * FROM docs ORDER BY embedding <=> query_vec LIMIT 5;Related Terms
Learn more
Frequently Asked Questions
HNSW vs IVF?
HNSW: best recall + speed, but all in RAM. IVF: cheaper RAM (centroids + buckets), slower recall. For huge datasets (>100M) — IVF + re-ranking.
HNSW and filtering?
Prefilter can cut graph connectivity. Quality vector DBs (Qdrant, Weaviate) have filter-aware HNSW. pgvector added index filtering in 2024.
Is DiskANN an alternative?
DiskANN — SSD-based ANN. 10× cheaper memory, 2-3× slower. For billion-scale. Milvus, MyScale support it.