Hierarchical Navigable Small World (HNSW)

HNSW constructs a hierarchy of proximity graphs where each layer represents a different density of connections. The top layers are sparse with long-range edges, enabling rapid coarse navigation across the vector space. Bottom layers are dense with short-range edges, ensuring high-precision final refinement. An exponentially decaying probability function assigns each inserted element to a maximum layer, creating a natural hierarchy where higher layers contain fewer nodes.

Search begins at the entry point in the topmost layer and performs a greedy best-first traversal. At each step, the algorithm evaluates neighbors and moves to the closest unvisited node, maintaining a dynamic candidate list of size efSearch (beam width). This parameter directly controls the recall-speed tradeoff: higher values explore more paths for better accuracy at the cost of increased distance computations. The search descends layer by layer until reaching the ground layer for final results.

During index construction, HNSW uses a pruning heuristic to select a node's neighbors rather than simply connecting to the nearest candidates. The algorithm iterates through candidates by distance and discards any that are closer to an already-selected neighbor than to the current node. This ensures diverse edge directions, prevents redundant connections, and maintains the small-world navigability property that enables logarithmic scaling. The parameter M controls the maximum number of outgoing edges per node.

HNSW supports fully dynamic indexing—new vectors can be inserted at any time without requiring a full index rebuild. Each insertion performs a search to find the nearest neighbors at the appropriate layer, then establishes bidirectional connections using the pruning heuristic. This makes HNSW ideal for streaming data and applications where the vector collection grows continuously. Deletions are supported by marking nodes as removed, though periodic compaction may be needed for optimal performance.

The hierarchical structure enables O(log N) search complexity in practice, where N is the dataset size. The top layers act as a skip list over the vector space, allowing the algorithm to jump across large distances quickly. Each descent to a lower layer reduces the search radius while increasing graph density. This scaling behavior makes HNSW one of the fastest ANN algorithms for high-recall scenarios, consistently outperforming tree-based and hashing methods on benchmark datasets.

• M: Maximum outgoing edges per node (typically 16-64). Higher values improve recall but increase memory usage and build time.
• efConstruction: Beam width during index building (typically 100-500). Larger values produce higher-quality graphs at the cost of slower construction.
• efSearch: Beam width during query time (typically 16-512). The primary knob for the recall-latency tradeoff—higher values explore more paths.
• mL: Normalization factor for the level generation probability, controlling the hierarchy height (typically 1/ln(M)).

The standard evaluation metric for ANN algorithms, measuring the fraction of true nearest neighbors found within the top K retrieved results. A Recall@10 of 0.95 means 95% of the exact 10 nearest neighbors were included in the algorithm's returned set.

• Tradeoff Axis: Recall is the primary currency exchanged for speed in approximate search
• Ground Truth: Requires computing exact distances against all vectors, feasible only for benchmarking
• Typical Targets: Production systems often target Recall@10 between 0.95 and 0.99
• HNSW Performance: Routinely achieves 0.99+ recall with only 0.1-1% of vectors visited, dramatically outperforming flat search

A critical hyperparameter in HNSW controlling the number of outgoing edges per node at each layer. Higher degree increases graph connectivity and recall but consumes more memory and slows traversal.

• Layer 0 (Bottom): Typically uses a higher degree (e.g., M=16-64) for dense local connectivity
• Upper Layers: Inherit a reduced degree (e.g., M/2) to maintain sparse, long-range shortcut structure
• Memory Impact: Each edge stores a vector ID and distance, scaling linearly with degree × dataset size
• Tuning Guidance: Increase M for higher recall targets; decrease for memory-constrained edge deployments

The exact nearest neighbor retrieval method that computes the distance between a query vector and every database vector. Guarantees perfect recall at the cost of O(N·D) time complexity, where N is dataset size and D is dimensionality.

• Flat Index: The simplest vector index with no preprocessing; vectors stored sequentially
• When Viable: Acceptable for small datasets (<100K vectors) or when perfect accuracy is non-negotiable
• HNSW Comparison: HNSW achieves sub-linear O(log N) complexity by traversing only a fraction of the graph
• Benchmark Baseline: Brute-force serves as the ground truth for computing Recall@K in ANN evaluations

A two-stage retrieval pipeline where a fast ANN index like HNSW retrieves a candidate set, and a more precise computation re-scores these candidates using full-precision vectors or a cross-encoder model.

• Candidate Generation: HNSW retrieves top-K candidates (e.g., K=100) with high recall
• Refinement Stage: Candidates are re-scored using exact distance computation or a more expensive model
• Benefit: Decouples recall from precision, allowing the ANN index to optimize for speed while the re-ranker ensures final accuracy
• Common Pattern: HNSW efSearch set lower for speed, compensated by larger K and precise re-ranking