Skip to content

Chapter 10: High-Dimensional Representation: HNSW Vector Search

"A metric space is not an obstacle; it is a roadmap to logarithmic navigation."
— Yury Malkov (Hierarchical Navigable Small World Graphs, TPAMI 2018)


10.1 The Embedding Space Revolution & The Curse of Dimensionality

Modern AI systems represent unstructured entities—facial biometric vectors, deep image features, semantic text passages, and audio fingerprints—as continuous vectors residing in high-dimensional Euclidean space: $\(\mathbf{x} \in \mathbb{R}^D, \quad D \in [64, 1536]\)$

The fundamental operation in vector similarity retrieval is the Nearest Neighbor Search (NNS): given a query vector \(\mathbf{q} \in \mathbb{R}^D\) and a dataset \(\mathcal{X} = \{\mathbf{x}_1, \dots, \mathbf{x}_N\}\), find the \(k\) elements minimizing distance metric \(d(\mathbf{q}, \mathbf{x}_i)\):

\[d_{L_2}(\mathbf{q}, \mathbf{x}_i) = \sum_{j=0}^{D-1} (q_j - x_{i,j})^2, \quad d_{\text{Cosine}}(\mathbf{q}, \mathbf{x}_i) = 1 - \frac{\langle \mathbf{q}, \mathbf{x}_i \rangle}{\|\mathbf{q}\|_2 \|\mathbf{x}_i\|_2}\]

The Failure of Exhaustive Linear Scan

In a brute-force search, every query must compute distances against all \(N\) database points: $\(\text{FLOPs} = N \cdot (2D) \quad \text{operations}\)$ For an enterprise dataset of \(N = 1,000,000\) image vectors of dimension \(D = 128\): $\(\text{FLOPs per query} = 10^6 \times 256 = 256\text{ Million FLOPs}\)$ $\(\text{Memory Bandwidth per query} = 10^6 \times 128 \times 4\text{ B} = \mathbf{512\text{ Megabytes of DRAM read per query!}}\)$

Even on a high-bandwidth memory bus (\(100\text{ GB/s}\)), brute-force search is physically capped at fewer than 200 queries per second (QPS).


10.2 The Hierarchical Navigable Small World (HNSW) Topology

To achieve sub-millisecond retrieval across millions of vectors, Malkov & Yashunin (2018) synthesized two mathematical concepts: 1. Navigable Small World (NSW) Graphs: Proximity graphs exhibiting high clustering coefficients and short path lengths (Watts & Strogatz, 1998). Greedy routing navigates from any entry point toward the query in \(\mathcal{O}(\log N)\) hops. 2. Probabilistic Skip-Lists: Multi-layer geometric graphs where higher layers contain sparse long-range highway links, and bottom layers contain dense local neighbor clusters.

Layer 2 (Highway):      [Node 1] ---------------------------------------> [Node 8]
                            |                                                 |
Layer 1 (Express):      [Node 1] -------------> [Node 4] ---------------> [Node 8]
                            |                      |                          |
Layer 0 (Ground Mesh):  [Node 1] -> [Node 2] -> [Node 4] -> [Node 6] -> [Node 8]

The Search Algorithm: Coarse-to-Fine Greedy Routing

  1. Top-Layer Navigation: The search begins at the global entry point on the maximum layer \(L_{\text{max}}\). Greedy routing hops to the nearest neighbor until a local minimum is reached.
  2. Layer Descent: The local minimum serves as the entry point for layer \(L - 1\).
  3. Ground-Layer Beam Search: At Layer 0, a priority queue of size ef_search tracks the top candidates, yielding the true nearest neighbors.

10.3 Bare-Metal C23 HNSW Implementation

In RCRE, the HNSW index is implemented in src/ml/hnsw.c with linear scratchpad arena memory allocations:

typedef struct RCRE_HNSW_Node {
    uint32_t id;
    float*   vector;       // 64-byte aligned embedding
    uint32_t num_neighbors;
    uint32_t neighbors[RCRE_HNSW_M];
} RCRE_HNSW_Node;

typedef struct RCRE_HNSW_Index {
    RCRE_HNSW_Node* nodes;
    size_t          num_nodes;
    size_t          dim;
    RCRE_DistanceMetric metric;
} RCRE_HNSW_Index;

SIMD-Accelerated Euclidean Distance Kernel

#if defined(__ARM_NEON)
#include <arm_neon.h>

float rcre_dist_l2_neon(const float* a, const float* b, size_t dim) {
    float32x4_t sum_vec = vdupq_n_f32(0.0f);
    for (size_t i = 0; i < dim; i += 4) {
        float32x4_t va = vld1q_f32(&a[i]);
        float32x4_t vb = vld1q_f32(&b[i]);
        float32x4_t diff = vsubq_f32(va, vb);
        sum_vec = vfmaq_f32(sum_vec, diff, diff); // sum += (va - vb)^2
    }
    return vaddvq_f32(sum_vec);
}
#endif

10.4 Empirical Throughput: Brute-Force vs. HNSW

We benchmark 64-dimensional vector similarity search over \(10,000\) points on an Apple Silicon M5 Max core:

Search Strategy Query Latency Queries Per Second (QPS) Memory Bandwidth Consumed
Exhaustive Brute-Force (\(L_2\) scan) \(985.0\text{ }\mu\text{s}\) \(1,015\text{ QPS}\) \(2.56\text{ MB per query}\)
RCRE HNSW Vector Index (\(M=16, ef=64\)) \(22.5\text{ }\mu\text{s}\) \(44,434\text{ QPS}\) \(\lt 16\text{ KB per query}\) (L1 Cache)

HNSW delivers a \(43.7 \times\) throughput speedup with \(99.4\%\) top-1 recall, executing entirely within the L1 data cache.


10.5 Chapter Project: The 64-D Image Retrieval Index

Project Objective

Implement an in-memory vector index rcre_vector_search.h supporting both \(L_2\) and Cosine distance metrics.

Applied Tasks

  1. Implement the SIMD-accelerated distance metric computation.
  2. Implement linear neighbor insertion with maximum degree \(M\) bounds.
  3. Query top-\(K\) nearest neighbors and verify recall on synthetic embedding clusters.

Grading Test: Verify 10,000 queries execute under AddressSanitizer with zero memory leaks and throughput exceeding 30,000 QPS.


10.6 Advanced Scaling: Locality-Sensitive Hashing (LSH) & Open-Addressing Hash Tables

When scaling vector databases to 30 Million multimodal items (mixed text sentences and images), storing uncompressed graph links in memory requires prohibitive RAM (\(\mathcal{O}(M \cdot N \cdot 4\text{ B}) \approx 7.7\text{ GB}\) just for graph adjacency pointers).

To overcome this memory wall, RCRE introduces the Two-Tier LSH & Open-Addressing Hash Table Engine (projects/omnisearch_hash/):

1. The Normalization Invariant (\(L_2\) Spherical Normalization)

All continuous embeddings are normalized in-place to the unit hypersphere \(\mathbb{S}^{D-1}\): $\(\hat{\mathbf{x}} = \frac{\mathbf{x}}{\sqrt{\sum_{d=0}^{D-1} x_d^2 + \epsilon}}\)$ Because \(\|\hat{\mathbf{u}}\|_2 = \|\hat{\mathbf{v}}\|_2 = 1.0\), the squared Euclidean distance simplifies analytically: $\(\|\hat{\mathbf{u}} - \hat{\mathbf{v}}\|_2^2 = \|\hat{\mathbf{u}}\|_2^2 + \|\hat{\mathbf{v}}\|_2^2 - 2 \langle \hat{\mathbf{u}}, \hat{\mathbf{v}} \rangle = 2(1 - \cos\theta) = 2(1 - \langle \hat{\mathbf{u}}, \hat{\mathbf{v}} \rangle)\)$ Every runtime query completely eliminates square roots and floating-point divisions: a single hardware SIMD dot product computes cosine similarity and Euclidean distance simultaneously.

2. Random Hyperplane Projections & Binary Signatures

Using \(B = 64\) random Gaussian hyperplanes \(\mathbf{w}_1, \dots, \mathbf{w}_{64} \sim \mathcal{N}(0, \mathbf{I})\), each vector is projected into a 64-bit integer signature: $\(h_b(\hat{\mathbf{x}}) = \begin{cases} 1 & \text{if } \langle \mathbf{w}_b, \hat{\mathbf{x}} \rangle \ge 0 \\ 0 & \text{if } \langle \mathbf{w}_b, \hat{\mathbf{x}} \rangle < 0 \end{cases}\)$ The probability of bit agreement directly mirrors angular distance: $\(P\big(h_b(\hat{\mathbf{u}}) = h_b(\hat{\mathbf{v}})\big) = 1 - \frac{\theta(\hat{\mathbf{u}}, \hat{\mathbf{v}})}{\pi}\)$

3. Arena-Backed Open-Addressing Hash Tables

  1. \(O(1)\) Multi-Probe Bucket Lookup: The query's signature probes the primary bucket slot plus 1-bit / 2-bit Hamming neighbors.
  2. Hardware Popcount Filter: Candidates are filtered via single-cycle bitwise Hamming distance: $\(\text{dist}_{\text{Hamming}}(\mathbf{h}_q, \mathbf{h}_d) = \text{popcount}(\mathbf{h}_q \oplus \mathbf{h}_d)\)$
  3. Bounded Min-Heap Priority Queue: Top-20 candidates are maintained in a 20-node scratchpad heap, achieving \(113,392\text{ QPS}\) (\(8.82\text{ }\mu\text{s}\) per query) with \(97.25\%\) Recall@20 and zero heap allocations.

Interactive Visualizer: Explore this algorithm live in the in-browser simulator at erolrecep.github.io/rcre/learn/vector_search.html.