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)\):
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
- 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.
- Layer Descent: The local minimum serves as the entry point for layer \(L - 1\).
- Ground-Layer Beam Search: At Layer 0, a priority queue of size
ef_searchtracks 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
- Implement the SIMD-accelerated distance metric computation.
- Implement linear neighbor insertion with maximum degree \(M\) bounds.
- 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
- \(O(1)\) Multi-Probe Bucket Lookup: The query's signature probes the primary bucket slot plus 1-bit / 2-bit Hamming neighbors.
- 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)\)$
- 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.