HNSW Explained: Hierarchical Navigable Small World Graphs for Vector Search

TL;DR — HNSW (Hierarchical Navigable Small World) is a graph-based ANN algorithm with O(log n) search, 95%+ recall, and multi-layer greedy routing. Pinecone: "Navigable small world models — logarithmic complexity using greedy routing. Traverse edges greedily, moving to nearest neighbor. Efficiency breaks down for large networks when not navigable." Wikipedia: "HNSW builds on small-world networks and navigable graphs. Most nodes reachable through short chains. Search uses local information to move toward target." KeyurRamoliya: "Introduced by Malkov and Yashunin in 2016. Multi-layer greedy traversal from coarse to fine granularity with bounded computational complexity." Medium: "Search implements multi-layer greedy traversal. Routing follows greedy strategy." MongoDB: "Coarse-to-fine search makes HNSW powerful for high-dimensional data." Learn more with HNSW vs IVFFlat, vector databases, pgvector tutorial, and semantic search.

KeyurRamoliya provides the definitive introduction: "The Hierarchical Navigable Small World algorithm represents a fundamental breakthrough in approximate nearest neighbor search for high-dimensional vector spaces. Introduced by Yury Malkov and Dmitry Yashunin in 2016, HNSW addresses the critical limitation of existing similarity search methods that scale poorly with high-dimensional data."

Wikipedia explains the foundation: "HNSW builds on research into small-world networks and navigable graphs. In a small-world graph, most nodes can be reached from other nodes through a short chain of links. In a navigable graph, a search procedure can use local information to move toward a target."

HNSW Architecture

HNSW Parameter Guide

Complexity Comparison

Implementation

from dataclasses import dataclass
from typing import Optional
from enum import Enum
import math
import random

class LayerAssignment(Enum):
    EXPONENTIAL = "exponential"
    UNIFORM = "uniform"

@dataclass
class HNSWExplained:
    """Explain and simulate HNSW algorithm internals."""

    def get_layer_assignment(self, m: int = 16,
                             method: LayerAssignment =
                             LayerAssignment.EXPONENTIAL) -> dict:
        """Explain layer assignment in HNSW."""
        if method == LayerAssignment.EXPONENTIAL:
            ml = 1.0 / math.log(m)
            probabilities = []
            for layer in range(6):
                prob = math.exp(-layer / ml) * (1 - math.exp(-1/ml))
                probabilities.append({
                    "layer": layer,
                    "probability": round(prob, 4),
                    "expected_nodes": None,
                })
            return {
                "method": "exponential decay",
                "ml": round(ml, 4),
                "formula": "layer = floor(-ln(uniform(0,1)) * ml)",
                "layer_probabilities": probabilities,
                "notes": (
                    "Top layer has fewest nodes. "
                    "Bottom layer has all nodes. "
                    "Exponential decay ensures "
                    "coarse-to-fine navigation."
                ),
            }
        return {"method": "uniform", "notes": "Not standard for HNSW."}

    def get_search_simulation(self) -> dict:
        """Simulate HNSW search process."""
        return {
            "step_1": {
                "action": "Start at entry point on top layer",
                "description": (
                    "Begin at a fixed entry point node "
                    "on the highest layer."
                ),
            },
            "step_2": {
                "action": "Greedy search on top layer",
                "description": (
                    "Move to the neighbor closest to query. "
                    "Repeat until no closer neighbor found. "
                    "This is the local minimum."
                ),
            },
            "step_3": {
                "action": "Descend to next layer",
                "description": (
                    "Carry the best node from current layer "
                    "as entry point for next layer down."
                ),
            },
            "step_4": {
                "action": "Greedy search on next layer",
                "description": (
                    "Repeat greedy search with more nodes. "
                    "More connections available at lower layers."
                ),
            },
            "step_5": {
                "action": "Reach bottom layer (L0)",
                "description": (
                    "Bottom layer contains all nodes. "
                    "Switch from greedy to beam search "
                    "with ef_search width."
                ),
            },
            "step_6": {
                "action": "Beam search on L0",
                "description": (
                    "Maintain ef_search candidates in priority queue. "
                    "Explore neighbors of all candidates. "
                    "Stop when no improvement found."
                ),
            },
            "step_7": {
                "action": "Return top-k results",
                "description": (
                    "From ef_search candidates, "
                    "return k nearest to query. "
                    "Typically 95%+ recall vs exact search."
                ),
            },
        }

    def get_insertion_simulation(self) -> dict:
        """Simulate HNSW insertion process."""
        return {
            "step_1": {
                "action": "Assign random layer",
                "description": (
                    "layer = floor(-ln(uniform(0,1)) * ml). "
                    "Most nodes assigned to L0 only. "
                    "Few nodes assigned to higher layers."
                ),
            },
            "step_2": {
                "action": "Search to insertion layer",
                "description": (
                    "Greedy search from top layer down "
                    "to the assigned layer. "
                    "Carry best node at each descent."
                ),
            },
            "step_3": {
                "action": "Find ef_construction neighbors",
                "description": (
                    "At insertion layer, beam search "
                    "with ef_construction width to find "
                    "nearest neighbors."
                ),
            },
            "step_4": {
                "action": "Select m neighbors (heuristic)",
                "description": (
                    "Heuristic neighbor selection: "
                    "prefer neighbors that provide "
                    "diverse connections, not just closest. "
                    "Avoids isolated clusters."
                ),
            },
            "step_5": {
                "action": "Connect bidirectionally",
                "description": (
                    "Add edges between new node and "
                    "selected m neighbors. "
                    "If neighbor exceeds max connections, "
                    "prune weakest connection."
                ),
            },
            "step_6": {
                "action": "Descend and repeat",
                "description": (
                    "Move to next lower layer. "
                    "Repeat neighbor finding and connecting. "
                    "Until reaching L0."
                ),
            },
            "notes": (
                "HNSW absorbs inserts without quality loss. "
                "Graph adapts as new nodes arrive. "
                "No rebuild needed. "
                "This is the key advantage over IVFFlat."
            ),
        }

    def get_pgvector_sql(self) -> str:
        """pgvector HNSW SQL examples."""
        return (
            "-- Create HNSW index\n"
            "CREATE INDEX CONCURRENTLY docs_hnsw_idx\n"
            "ON documents USING hnsw (embedding vector_cosine_ops)\n"
            "WITH (m = 16, ef_construction = 200);\n"
            "\n"
            "-- Query with ef_search tuning\n"
            "BEGIN;\n"
            "SET LOCAL hnsw.ef_search = 100;\n"
            "SELECT id, title,\n"
            "       1 - (embedding <=> '[0.1,...]'::vector)\n"
            "           AS similarity\n"
            "FROM documents\n"
            "ORDER BY embedding <=> '[0.1,...]'::vector\n"
            "LIMIT 5;\n"
            "COMMIT;\n"
            "\n"
            "-- Monitor index size\n"
            "SELECT pg_size_pretty(\n"
            "    pg_relation_size('docs_hnsw_idx'));\n"
            "\n"
            "-- Check recall vs exact\n"
            "-- Compare HNSW results with:\n"
            "-- SELECT id FROM documents\n"
            "-- ORDER BY embedding <=> query\n"
            "-- LIMIT 100;  -- exact (no index)"
        )

    def get_tuning_guide(self) -> dict:
        """HNSW parameter tuning guide."""
        return {
            "fast": {
                "m": 12,
                "ef_construction": 48,
                "ef_search": 40,
                "use_case": "Low latency, acceptable recall",
                "expected_recall": "90-93%",
            },
            "balanced": {
                "m": 16,
                "ef_construction": 200,
                "ef_search": 100,
                "use_case": "Production default",
                "expected_recall": "95-97%",
            },
            "high_recall": {
                "m": 32,
                "ef_construction": 400,
                "ef_search": 200,
                "use_case": "Maximum recall, more memory",
                "expected_recall": "98-99%",
            },
            "tuning_rules": [
                "Start with balanced preset",
                "Increase ef_search first (query-time, no rebuild)",
                "Increase m if ef_search doesn't help (requires rebuild)",
                "Increase ef_construction for better build quality",
                "Always benchmark recall on your own data",
                "Use SET LOCAL for per-query ef_search tuning",
            ],
        }

HNSW Checklist

• [ ] HNSW = Hierarchical Navigable Small World, introduced by Malkov and Yashunin in 2016
• [ ] Graph-based approximate nearest neighbor (ANN) algorithm for high-dimensional vector search
• [ ] Multi-layer graph: top layer has few nodes (coarse), bottom layer has all nodes (fine)
• [ ] Layer assignment: exponential distribution, most nodes at L0, few at higher layers
• [ ] Search: greedy routing from top to bottom, beam search at L0 with ef_search width
• [ ] Insert: find insertion point via greedy search, connect to m neighbors with heuristic
• [ ] Navigable small world: most nodes reachable through short chains, search uses local info
• [ ] Greedy routing: move to neighbor closest to query, repeat until local minimum
• [ ] Coarse-to-fine navigation: prune search space exponentially at each layer
• [ ] O(log n) average search complexity — logarithmic pruning
• [ ] O(n * m) space complexity for graph edges plus O(n * d) for vectors
• [ ] O(log n * ef_construction) insert complexity
• [ ] O(n * log n * ef_construction) build complexity
• [ ] 95%+ recall with default parameters (m=16, ef_construction=200, ef_search=100)
• [ ] Memory: 2-5x more than IVFFlat due to graph structure
• [ ] m: max connections per node per layer (default 16, range 4-64)
• [ ] ef_construction: build-time search depth (default 64, range 32-512)
• [ ] ef_search: query-time search depth (default 40, range 1-1000)
• [ ] ml: level generation normalization factor (default 1/ln(m))
• [ ] Tuning: start with m=16, ef_construction=200, ef_search=100
• [ ] Increase ef_search first (query-time, no rebuild needed)
• [ ] Increase m if ef_search doesn't help (requires index rebuild)
• [ ] Increase ef_construction for better build quality (slower build)
• [ ] Use SET LOCAL hnsw.ef_search = 100 for per-query tuning in transactions
• [ ] Heuristic neighbor selection: prefer diverse connections, not just closest
• [ ] Bidirectional connections: new node connects to m neighbors, neighbors connect back
• [ ] Prune weakest connection if neighbor exceeds max connections
• [ ] HNSW absorbs inserts without quality loss — graph adapts, no rebuild needed
• [ ] Deletions: mark as tombstone, skip during search, physical removal requires rebuild
• [ ] pgvector: CREATE INDEX USING hnsw (embedding vector_cosine_ops) WITH (m=16, ef_construction=200)
• [ ] Operator class must match distance: vector_cosine_ops (<=>), vector_l2_ops (<->), vector_ip_ops (<#>)
• [ ] Use CREATE INDEX CONCURRENTLY to avoid locking production table
• [ ] SET maintenance_work_mem = '2GB' before building HNSW index
• [ ] Monitor index size: pg_size_pretty(pg_relation_size(...))
• [ ] Monitor recall: compare HNSW results with exact search on sample queries
• [ ] Efficiency of greedy routing breaks down for large networks when graph is not navigable
• [ ] Coarse-to-fine search makes HNSW powerful for complex, high-dimensional data
• [ ] HNSW addresses critical limitation of methods that scale poorly with high-dimensional data
• [ ] Small-world graph: most nodes reachable through short chain of links
• [ ] Navigable graph: search procedure uses local information to move toward target
• [ ] HNSW struggles with: very high dims (>2000), highly clustered data, low ef_search
• [ ] Fix high-dim issues: use halfvec, increase ef_search, ensure diverse training data
• [ ] Fix clustered data: increase m for better connectivity between clusters
• [ ] Fast preset: m=12, ef_construction=48, ef_search=40 (90-93% recall)
• [ ] Balanced preset: m=16, ef_construction=200, ef_search=100 (95-97% recall)
• [ ] High recall preset: m=32, ef_construction=400, ef_search=200 (98-99% recall)
• [ ] Read HNSW vs IVFFlat for index comparison
• [ ] Read vector databases for ANN fundamentals
• [ ] Read pgvector tutorial for setup
• [ ] Read semantic search for implementation
• [ ] Read embedding dimensions for dimension optimization
• [ ] Test: HNSW achieves 95%+ recall with balanced preset
• [ ] Test: O(log n) search — query time grows logarithmically with dataset size
• [ ] Test: inserts don't degrade recall (unlike IVFFlat)
• [ ] Test: ef_search tuning improves recall at query time without rebuild
• [ ] Test: layer assignment follows exponential distribution
• [ ] Document parameter choice, tuning strategy, recall benchmarks, and monitoring plan

FAQ

What is HNSW and how does it work?

HNSW (Hierarchical Navigable Small World) is a graph-based approximate nearest neighbor algorithm that uses multi-layer greedy routing from coarse to fine granularity. Pinecone: "Navigable small world models are defined as any network with logarithmic complexity using greedy routing. We traverse edges in each layer greedily, moving to the neighbor closest to the query. The efficiency of greedy routing breaks down for larger networks (1-10K+ vertices) when a graph is not navigable." Wikipedia: "HNSW builds on research into small-world networks and navigable graphs. In a small-world graph, most nodes can be reached through a short chain of links. In a navigable graph, a search procedure can use local information to move toward a target." KeyurRamoliya: "Introduced by Yury Malkov and Dmitry Yashunin in 2016, HNSW addresses the critical limitation of existing similarity search methods. The search algorithm implements a multi-layer greedy traversal strategy that efficiently navigates from coarse to fine granularity while maintaining bounded computational complexity." How it works: (1) Build multi-layer graph with exponentially decreasing node counts. (2) Top layer has few nodes (coarse), bottom layer has all nodes (fine). (3) Search starts at top layer, greedily moves to nearest neighbor. (4) Descend to next layer, repeat greedy search. (5) At bottom layer, collect k nearest neighbors with ef_search beam width.

What are the HNSW parameters m, ef_construction, and ef_search?

m controls max connections per node, ef_construction controls build-time search depth, and ef_search controls query-time search depth. Medium: "The search algorithm in HNSW implements a multi-layer greedy traversal strategy. The routing process in NSW graphs follows a greedy strategy." MongoDB: "By optimizing the path toward the most similar nodes based on data structure and distance metric, HNSW enables efficient, precise navigation through massive datasets." Parameters: (1) m: max connections per node per layer (default 16). Higher = more memory, better recall, slower build. Range 4-64. (2) ef_construction: search depth during index build (default 64). Higher = better quality graph, slower build. Range 32-512. (3) ef_search: search depth during query (default 40). Higher = better recall, slower query. Set at query time with SET LOCAL hnsw.ef_search = 100. Range 1-1000. Tuning: start with m=16, ef_construction=200, ef_search=100. Increase m for higher recall. Increase ef_search for better query-time recall.

What is the time and space complexity of HNSW?

HNSW achieves O(log n) search complexity for most queries, with O(n * m) space complexity for the graph structure. Pinecone: "Navigable small world models are defined as any network with logarithmic complexity using greedy routing." KeyurRamoliya: "HNSW maintains bounded computational complexity while navigating from coarse to fine granularity." Complexity: (1) Search: O(log n) average case for navigable graphs, O(n) worst case. (2) Insert: O(log n * ef_construction) — search for insertion point then connect to m neighbors. (3) Space: O(n * m) for graph edges, plus O(n * d) for vector storage. (4) Build: O(n * log n * ef_construction) — insert all n vectors. (5) Memory: 2-5x more than IVFFlat due to graph structure. At 1M vectors with 1536 dims: ~6GB raw vectors + ~15GB HNSW graph = ~21GB total. The logarithmic search complexity is what makes HNSW fast — it prunes the search space exponentially at each layer.

How does HNSW handle insertions and deletions?

HNSW handles insertions by finding the insertion point via greedy search, then connecting to m nearest neighbors. Deletions mark nodes as deleted without removing from graph. Pinecone: "We traverse edges in each layer greedily, moving to the neighbor closest to the query." Wikipedia: "In a navigable graph, a search procedure can use local information to move toward a target." Insertion: (1) Assign random layer based on exponential distribution. (2) Search from top layer to insertion layer using greedy routing. (3) At insertion layer, find ef_construction nearest neighbors. (4) Connect to m closest neighbors using heuristic. (5) Descend to lower layers, repeat. HNSW absorbs inserts without quality loss — graph adapts. Deletion: (1) Mark node as deleted (tombstone). (2) Skip deleted nodes during search. (3) Physical removal requires graph rebuild. (4) Frequent deletions cause graph degradation over time. pgvector HNSW: supports concurrent inserts, no rebuild needed for inserts.

Why does HNSW achieve 95%+ recall and when does it struggle?

HNSW achieves 95%+ recall because the multi-layer graph preserves navigability while pruning the search space efficiently. It struggles with very high-dimensional data, highly clustered data, and when ef_search is too low. Pinecone: "The efficiency of greedy routing breaks down for larger networks when a graph is not navigable." MongoDB: "This combination of coarse-to-fine search capability makes HNSW a powerful tool for complex, high-dimensional data." KeyurRamoliya: "HNSW addresses the critical limitation of existing similarity search methods that scale poorly with high-dimensional data." Why 95%+ recall: (1) Multi-layer structure ensures coarse-to-fine navigation. (2) m connections per node maintain graph connectivity. (3) ef_search beam width explores multiple paths. (4) Heuristic neighbor selection avoids isolated clusters. When it struggles: (1) Very high dimensions (>2000) — distance calculations become less meaningful (curse of dimensionality). (2) Highly clustered data — graph may not connect clusters well. (3) ef_search too low — insufficient exploration. (4) m too low — poor connectivity. (5) Very selective metadata filtering — may need adaptive approach. Fix: increase ef_search, use halfvec for high dims, ensure diverse training data.

Want a self-hosted AI company brain that does all of this out of the box?
Book a demo →