Patterns

Pattern

Hierarchical Navigable Small World (HNSW)

Multi-layer graph index for approximate nearest neighbour search. De-facto default for vector databases when latency matters more than perfect recall.

Taxonomy

patterns.indexing

Category

indexing

Complexity

medium

When to use

Sub-10ms ANN queries on 100k-100M vectors, memory budget allows the index to stay in RAM.

When NOT to use

Workloads needing exact recall, frequent rebuilds on tiny datasets, or strict memory caps.

What it is

HNSW builds a layered proximity graph: upper layers are sparse and used for coarse navigation; lower layers are dense and used for refinement. A query starts at the top layer, greedy-walks toward the target, descends, and refines. Recall is tuned with ef_search; build cost is tuned with ef_construction and M.

Where you see it

Default ANN index in Qdrant, Milvus, Weaviate, pgvector (vector_hnsw_ops), Chroma.

Trade-offs

• Memory-heavy. The graph lives in RAM; budget ~1.5x raw vector size.
• Insert/delete is non-trivial. Most vector DBs implement soft-delete + periodic rebuild rather than true in-place updates.
• Recall is tunable but not free. Raising ef_search improves recall linearly, costs latency linearly.

Common mistakes

• Picking HNSW for a 10k-vector demo where flat (exact) search is faster and trivially correct.
• Ignoring M during build, then complaining about recall at query time. M=16 is usually fine; M=32-48 for high-dim text embeddings.