ANN Indexing Algorithms: HNSW, IVF & Product Quantization

1. The Need for Approximate Nearest Neighbors (ANN)

An Exact Nearest Neighbor (kNN / Flat) index compares the query vector against every single vector in the database sequentially (exhaustive linear scan). While recall is 100% perfect, its operational cost is prohibitive for real-time production:

• Query Latency: Scanning 5 million vectors of 1,536 dimensions takes 1,200ms to 4,000ms on multi-core CPUs.
• Throughput (QPS): A single server can process fewer than 2 queries per second before saturating all CPU cores.

Approximate Nearest Neighbors (ANN) algorithms bypass exhaustive scans by organizing vectors into geometric data structures (graphs, clusters, trees). By accepting an imperceptible recall trade-off (e.g., retrieving 97% to 99% of the true closest documents), ANN algorithms reduce query time to sub-5ms with logarithmic O(log N) complexity.

2. HNSW: Hierarchical Navigable Small World Graphs

HNSW is the gold standard vector index used by Pinecone, ChromaDB, Qdrant, Weaviate, and PostgreSQL pgvector. It combines the logarithmic navigation of Skip-Lists with the cluster connectivity of Navigable Small World (NSW) graphs.

Critical HNSW Tuning Parameters:

3. IVF: Inverted File Index & Voronoi Partitioning

While HNSW stores the entire graph in RAM, IVF (Inverted File Index) is a cluster-based index ideal for large-scale datasets with tighter memory budgets:

1. Clustering Phase (Offline Training): The database runs k-Means clustering over vector samples to compute nlist centroids, partitioning the vector space into Voronoi cells.
2. Posting Lists: Each vector is assigned to its closest centroid. Vectors belonging to the same centroid are stored together in an inverted list.
3. Query Phase (Online Search): The query vector is compared against all nlist centroids. The database selects the top nprobe closest centroids, and only searches through the vectors stored within those specific lists.

4. Product Quantization (PQ): Compressing Vector RAM by 90%

Storing 10 million vectors of 1,536 float32 values requires:

Adding HNSW graph edges increases this to over 90 GB of RAM. Product Quantization (PQ)solves this memory explosion through lossy vector compression:

• Sub-Vector Slicing: A 1,536-dimensional vector is divided into m = 96 sub-vectors of 16 dimensions each.
• Codebook Quantization: For each sub-vector subspace, k-Means builds a codebook of 256 centroids (represented by an 8-bit byte: 0 to 255).
• 8-Bit Byte Indexing: The original 6,144-byte vector is compressed into 96 bytes (a 98.4% reduction!).

5. Indexing Strategy Decision Matrix

6. Hands-On: Building HNSW and IVF Indexes with Faiss

Here is a practical Python demonstration using Meta's faiss library to compare HNSW and IVF indices:

import numpy as np
import faiss

DIMENSION = 512
NUM_VECTORS = 50000
K_NEIGHBORS = 5

np.random.seed(42)
data_vectors = np.random.random((NUM_VECTORS, DIMENSION)).astype(np.float32)
query_vector = np.random.random((1, DIMENSION)).astype(np.float32)

# Normalize for Cosine Similarity
faiss.normalize_L2(data_vectors)
faiss.normalize_L2(query_vector)

# --- 1. Building an HNSW Index ---
M = 32  # Number of bi-directional links per node
index_hnsw = faiss.IndexHNSWFlat(DIMENSION, M, faiss.METRIC_INNER_PRODUCT)
index_hnsw.hnsw.efConstruction = 128
index_hnsw.hnsw.efSearch = 64

index_hnsw.add(data_vectors)
distances_hnsw, indices_hnsw = index_hnsw.search(query_vector, K_NEIGHBORS)

print("=== HNSW Search Results ===")
for rank, (idx, dist) in enumerate(zip(indices_hnsw[0], distances_hnsw[0]), 1):
    print(f"Rank {rank}: Vector ID {idx} | Cosine Sim: {dist:.4f}")

# --- 2. Building an IVFFlat Index ---
NLIST = 100  # Number of Voronoi clusters
quantizer = faiss.IndexFlatIP(DIMENSION)  # Flat Inner Product for centroids
index_ivf = faiss.IndexIVFFlat(quantizer, DIMENSION, NLIST, faiss.METRIC_INNER_PRODUCT)

# IVF requires training to learn centroid coordinates
index_ivf.train(data_vectors)
index_ivf.add(data_vectors)

index_ivf.nprobe = 16  # Probe 16 out of 100 clusters
distances_ivf, indices_ivf = index_ivf.search(query_vector, K_NEIGHBORS)

print("\n=== IVFFlat Search Results ===")
for rank, (idx, dist) in enumerate(zip(indices_ivf[0], distances_ivf[0]), 1):
    print(f"Rank {rank}: Vector ID {idx} | Cosine Sim: {dist:.4f}")