Hierarchical Navigable Small World (HNSW)

Graph-based algorithm for approximate nearest neighbor search providing logarithmic search complexity with controllable precision-speed tradeoffs. Core technology enabling scalable similarity search in production document processing systems, particularly for few-shot example selection from large reference datasets.

Algorithm Overview

Graph Structure

HNSW builds a multi-layer graph where:

• Hierarchical Layers: Multiple graph layers with decreasing connectivity density
• Navigable Structure: Each layer provides increasingly fine-grained search paths
• Small World Property: Short paths between any two nodes in the graph
• Greedy Search: Efficient traversal using greedy routing through layers

Search Process

1. Entry Point: Start search at top layer with sparse connections
2. Layer Traversal: Navigate down through layers, refining search at each level
3. Local Minima: Find approximate nearest neighbors at bottom layer
4. Result Collection: Return top-k similar items based on distance metric

Performance Characteristics

Time Complexity

• Search: O(log N) average case vs O(N) for exact search
• Construction: O(N