HNSW (Hierarchical Navigable Small World)

HNSW organizes vectors into a multi-layer graph where each layer represents a different density of connections. The bottom layer (layer 0) contains all data points with short-range links, while higher layers contain exponentially fewer nodes with long-range connections. This mimics the structure of skip lists, enabling O(log N) search complexity.

• Layer assignment uses an exponentially decaying probability distribution
• Higher layers act as express lanes for rapid coarse navigation
• The top layer typically contains only a single entry point node

Retrieval uses a best-first greedy search that traverses the graph by always moving to the neighbor closest to the query vector. The algorithm maintains a dynamic candidate list of size ef (exploration factor) to prevent getting trapped in local minima.

• ef_search controls the beam width during query time
• Higher ef values improve recall at the cost of latency
• The search starts at the top-layer entry point and descends layer by layer

HNSW supports fully incremental indexing — new vectors are inserted one at a time without requiring global index rebuilds. Each insertion finds the nearest neighbors across layers and establishes bidirectional connections, maintaining the graph's navigability.

• M parameter controls the maximum number of outgoing connections per node
• M_max0 (typically 2 × M) sets connections at the base layer
• Insertion triggers local connection pruning to maintain the small-world property

The graph maintains the navigable small-world property where any node can reach any other node in a small number of hops. This is achieved through a heuristic that selects neighbors based on distance diversity rather than just proximity, preventing redundant connections.

• Heuristic pruning removes edges that don't shorten paths to other regions
• Maintains logarithmic diameter of the graph
• Naturally handles high-dimensional data without dimensionality reduction

HNSW provides tunable control over the memory-accuracy trade-off through its construction parameters. The M parameter directly controls graph degree and memory footprint, while ef_construction governs index build quality.

• Typical M values range from 16 to 64
• Memory scales as O(M × N) where N is the number of vectors
• Achieves 95-99% recall at sub-millisecond query latencies on million-scale datasets

HNSW natively supports soft deletion through tombstones — deleted nodes are marked as inactive but remain in the graph structure to preserve navigability for other nodes. This avoids the costly operation of repairing broken graph connectivity.

• Deleted nodes are skipped during search traversal
• Periodic compaction can physically remove tombstones
• Enables CRUD operations without degrading search performance

The algorithmic class to which HNSW belongs. ANN trades a small, controlled loss in recall for orders-of-magnitude speed improvements over exact k-NN search.

• Core trade-off: Accuracy vs. latency vs. memory
• HNSW is a leading graph-based ANN method
• Enables sub-linear search time: O(log N) complexity
• Critical for billion-scale vector databases

A vector compression technique frequently paired with HNSW to reduce memory footprint. PQ decomposes the original high-dimensional space into a Cartesian product of lower-dimensional subspaces and quantizes each independently.

• Reduces memory by 10-30x with minimal recall loss
• Often used as a secondary compression layer on top of HNSW graphs
• Enables billion-scale indices on commodity hardware
• Complements HNSW's in-memory graph structure

The primary distance metric used in HNSW-based semantic search. Measures the cosine of the angle between two non-zero vectors, providing magnitude-invariant similarity scoring.

• Range: -1 (opposite) to 1 (identical)
• HNSW supports cosine, Euclidean, and inner product spaces
• Normalized embeddings make inner product equivalent to cosine similarity
• Essential for comparing dense text embeddings

The fundamental problem HNSW is designed to solve. As dimensions increase, the concept of distance becomes less meaningful—all points appear equidistant, breaking traditional spatial indexes like k-d trees.

• HNSW's graph structure mitigates this by navigating through proximity layers
• Traditional tree structures degrade to O(N) in high dimensions
• Embedding dimensions typically range from 384 to 4096
• HNSW maintains logarithmic scaling despite dimensionality

A retrieval architecture that combines HNSW-based dense vector search with sparse keyword search (BM25). Reciprocal Rank Fusion (RRF) merges the two result sets into a single ranking.

• HNSW handles semantic understanding
• BM25 handles exact keyword matching
• RRF formula: score(d) = Σ 1/(k + rank_i(d))
• Outperforms either method alone on complex queries