HNSW (Hierarchical Navigable Small World) Implementation.

Based on the paper by Yu. A. Malkov, D. A. Yashunin: "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs" (2016).

Many implementation details not covered in the original paper were derived from antirez's practical optimizations for Redis vector-sets. Reference: https://antirez.com/news/156

Algorithm Overview

HNSW builds a multi-layer graph where each layer is a navigable small-world graph. Higher layers have fewer nodes and act as "express lanes" for fast navigation, while layer 0 contains all nodes.

Search proceeds top-down: starting from the entry point at the highest layer, we greedily descend until reaching layer 0, then perform a more thorough beam search to find the k nearest neighbors.

Insert assigns each new node to a random layer L (exponentially distributed), then connects it to neighbors at layers 0..L using the same search mechanism.

Implementation Features

1. Bidirectional links only. When a new node is inserted, we add connections from the new node to its neighbors AND from each neighbor back to the new node. This maintains graph navigability and enables proper deletion.

2. 8-bit scalar quantization. Vectors are quantized to signed int8 values using per-vector scaling:

quantized[i] = round(vector[i] * 127 / max_abs_value)

The scale factor (max_abs_value) is stored with each quantized vector. This provides 8x memory reduction compared to float64 with minimal recall loss (~1-2% for typical embeddings).

Storage format: <<Scale:32/float-little, Components/binary>> where each component is a signed 8-bit integer.

3. Norm caching. The L2 norm of each vector is computed once at insertion time and stored in the node record. This eliminates redundant norm calculations during cosine distance computation:

cosine_distance = 1 - (A·B) / (||A|| * ||B||)

Without caching: 3 dot products per comparison (A·B, A·A, B·B) With caching: 1 dot product + 2 lookups (A·B, cached norms)

4. Integer domain dot product. Distance calculations between quantized vectors use integer arithmetic:

int_dot = sum(a[i] * b[i]) -- integer multiplication real_dot = int_dot * scale_a * scale_b / (127 * 127)

This is faster than floating-point operations and SIMD-friendly.

5. Priority queue using gb_trees. The search algorithm maintains candidates in a balanced tree (Erlang's gb_trees) providing O(log N) insert and extract-min operations, versus O(N log N) for repeated lists:sort calls.

6. Direct graph serialization. The full graph structure (nodes, vectors, neighbors, metadata) is serialized to binary format for persistence. On startup, the index is deserialized directly without rebuilding the graph, providing ~100x faster loading compared to re-inserting all vectors.

Serialization format (version 2): <<Version:8, Size:32, MaxLayer:8, Dim:16, EntryPoint/binary, Config/binary, Nodes/binary>>

7. True deletion. Nodes are actually removed from the graph, not just marked as deleted. The deleted node is removed from all its neighbors' adjacency lists. A new entry point is selected if the deleted node was the entry point.

Configuration Parameters

- M: Maximum number of connections per node per layer (default: 16). Higher values improve recall but increase memory and build time.

- M_max0: Maximum connections at layer 0 (default: 2*M). Layer 0 typically needs more connections for good recall.

- ef_construction: Beam width during index construction (default: 200). Higher values improve index quality but slow down insertion.

- ef_search: Beam width during search (default: max(K, 50)). Higher values improve recall at the cost of search latency.

- ml: Level multiplier = 1/ln(M). Controls the probability distribution for assigning nodes to layers.

Complexity

- Insert: O(log N) average, O(ef_construction * M * log N) work - Search: O(log N) average for finding entry, O(ef_search * M) at layer 0 - Delete: O(M * layers) to update neighbor lists - Memory: O(N * M * layers) for graph + O(N * dim) for vectors