Managing billion-scale vector similarity search for Retrieval-Augmented Generation (RAG) and recommendation systems requires indexing high-dimensional embeddings (e.g. 1,536-dimensional vectors) with sub-10 millisecond retrieval latencies. Linear k-NN scan ($O(N \cdot d)$) is computationally prohibitive at scale.

Vector search databases rely on Approximate Nearest Neighbor (ANN) indexing structures. In this engineering reference guide, we examine the internal graph topology of Hierarchical Navigable Small World (HNSW), explore out-of-core SSD indexing with DiskANN, mathematically break down Product Quantization (PQ) compression, and construct a Python Faiss benchmark pipeline.

1. HNSW Graph Architecture: Multi-Layer Skip-List Mechanics

HNSW (Malkov & Yashunin) constructs a multi-layer graph hierarchy inspired by 1D skip-lists. The top layer $L_{\text{max}}$ contains sparse long-range highway edges across cluster centroids, while the bottom layer $L_0$ contains all vectors with short-range local connections.

Search proceeds greedily from top layer $L_{\text{max}}$ down to layer $L_0$. The maximum layer level for a newly inserted vector is assigned stochastically via an exponential decay probability distribution:

$$l = \lfloor -\ln(\text{uniform}(0, 1)) \cdot m_L \rfloor$$

Where $m_L = \frac{1}{\ln(M)}$ scales the average layer height based on target degree parameter $M$ (typically $M \in [16, 64]$).

2. Product Quantization (PQ) Vector Compression Math

For a 1,536-dimensional FP32 vector (6,144 bytes per vector), storing 1 billion vectors in RAM requires over 6 Terabytes of memory. Product Quantization (PQ) compresses high-dimensional vectors by 16x–64x with minimal loss in search recall.

PQ breaks a $D$-dimensional vector into $m$ distinct sub-vectors of dimension $d' = D / m$. A k-means clustering step builds $K^*$ centroids (usually $K^* = 256$) for each sub-space:

$$x = [x_1, x_2, \dots, x_m] \implies [c_{1, i_1}, c_{2, i_2}, \dots, c_{m, i_m}]$$

Each 1,536-dim vector is replaced by $m$ 8-bit byte indices ($m$ bytes total), reducing storage from 6,144 bytes to 96 bytes!

3. DiskANN: Out-Of-Core SSD Indexing for Billion-Scale Datasets

While HNSW requires holding the entire graph in expensive RAM, DiskANN (Subramanya et al.) stores compressed PQ vectors in RAM while maintaining the full uncompressed Vamana graph on NVMe SSD drives.

RAM Footprint: Compressed PQ Codebooks + Beam Search Queue NVMe SSD Storage: Full FP32 Vector Coordinates + Vamana Graph Edge List (4KB Aligned Pages)

During query execution, DiskANN uses asynchronous `io_uring` direct I/O to fetch graph neighbor pages from SSD in a single I/O request, achieving 95%+ recall@10 at 5,000 QPS on a single workstation node.

4. Python Faiss HNSW + PQ Index Setup & Benchmark

import faiss import numpy as np import time def build_hnsw_pq_index(dim: int = 128, num_vectors: int = 100000): print(f"[INFO] Generating {num_vectors} random synthetic embeddings (Dim={dim})...") data = np.random.random((num_vectors, dim)).astype('float32') # Construct HNSW + Product Quantization Index # M=32 graph connections per node, 16 PQ sub-quantizers M = 32 code_size = 16 index = faiss.IndexHNSWPQ(dim, code_size, M) print("[INFO] Training PQ codebooks...") index.train(data) print("[INFO] Inserting vectors into HNSW graph...") index.add(data) # Query Execution query = np.random.random((1, dim)).astype('float32') index.hnsw.efSearch = 64 # Search beam size t0 = time.time() distances, indices = index.search(query, k=5) t1 = time.time() print(f"[SUCCESS] Search completed in {(t1 - t0)*1000:.3f} ms") print("Top 5 Nearest Neighbor Indices:", indices[0]) print("L2 Distance Scores:", distances[0]) if __name__ == "__main__": build_hnsw_pq_index()