HNSW Algorithm Explained for Solution Architects
A practical guide to Hierarchical Navigable Small World graphs and how they power modern vector search at scale.
If you've evaluated Pinecone, Weaviate, pgvector, or any vector database in the last two years, you've depended on HNSW without necessarily knowing it. HNSW — Hierarchical Navigable Small World — is the approximate nearest-neighbor algorithm that makes semantic search fast enough for production. This article breaks it down for solution architects who need to make informed decisions about vector search infrastructure.
What Problem Does HNSW Solve?
Vector search is fundamentally a nearest-neighbor problem: given a query vector, find the k vectors in your index that are closest to it. Brute-force search checks every single vector — O(n) — which is unusable at scale. HNSW solves this with a probabilistic multi-layer graph structure that achieves O(log n) search complexity at the cost of approximate (not exact) results.
The Multi-Layer Graph Structure
HNSW builds a hierarchy of graphs. The bottom layer (layer 0) contains all vectors. Each higher layer is a random subset of the layer below — progressively sparser. During search, you enter at the top layer, greedily navigate toward your query vector, then descend to lower layers for increasingly fine-grained search. This mimics the 'small world' network property: any node can be reached from any other in a small number of hops.
- Layer 0: All vectors, high-density connections
- Layer 1+: Random subsets, long-range links for fast traversal
- Entry point: Fixed node at the top layer
- ef_construction: Controls build-time accuracy vs speed tradeoff
- M: Number of connections per node — affects memory and recall
Key Parameters Every Architect Should Know
Three parameters dominate HNSW behavior in production:
- M (connections per node): Higher M → better recall, more memory. Typical range: 16–64
- ef_construction (build-time search width): Higher → better index quality, slower build. Typical: 100–200
- ef_search (query-time search width): Higher → better recall, slower query. Set per query or globally
HNSW vs IVFFlat vs Brute Force
For most production RAG workloads, HNSW is the right default. IVFFlat (Inverted File Index) can be more memory-efficient at very large scale (100M+ vectors) but requires cluster training upfront and delivers lower recall. Brute force (exact search) is appropriate only for small indexes (<100k vectors) or when recall must be 100%.
Architecture Decisions for Solution Architects
When designing a vector search system, you'll need to decide:
- Managed vs self-hosted: Pinecone (managed), Weaviate Cloud (managed), pgvector on RDS (managed), or self-hosted Qdrant/Milvus
- Storage-compute separation: Does your vector DB separate index storage from query compute? (Pinecone does, most self-hosted don't)
- Hybrid search: Most enterprise RAG needs keyword + semantic search. Ensure your DB supports both
- Filtering: Pre-filter vs post-filter significantly impacts recall — understand your DB's approach
- Incremental updates: HNSW supports real-time inserts; IVF needs periodic retraining
Takeaway
HNSW is the workhorse of modern semantic search. As a solution architect, you don't need to implement it — but you need to understand the tradeoffs it encodes. The M and ef parameters are knobs you'll tune during load testing. The recall vs latency curve is a conversation you'll have with product teams. Understanding the algorithm makes those conversations much sharper.