Indexing: HNSW, IVF, Product Quantization

MLOps Series RAG Systems

When your vector store grows past a few thousand documents, brute-force nearest-neighbor search becomes a bottleneck. Approximate Nearest Neighbor (ANN) algorithms trade a small amount of recall for orders-of-magnitude speed improvements. This post examines the three most important indexing families—HNSW, IVF, and Product Quantization—and shows how to compose and tune them in FAISS for production RAG systems.

ANN Overview

Exact k-NN requires comparing a query vector against every vector in the dataset. For n vectors of dimension d, that is O(n·d) per query. At 10 million vectors and d=768, each query scans ~7.6 GB of float32 data. ANN algorithms build auxiliary data structures at index time so that queries only visit a fraction of the dataset.

Key trade-off: Every ANN algorithm offers a knob between recall (accuracy) and queries-per-second (QPS). Higher recall means visiting more candidates, which costs latency.

The three families we cover are:

HNSW — graph-based; high recall, high memory usage
IVF — partition-based; lower memory, requires training
PQ — compression-based; minimal memory, lossy

In practice, production systems combine these. For example, IVF4096,PQ64 partitions the space and compresses each partition, yielding a compact and fast index.

HNSW — Hierarchical Navigable Small World

HNSW organizes vectors in a multi-layer navigable graph. The top layers contain a sparse subset of nodes for coarse navigation, while the bottom layer connects every node to its nearest neighbors. A search starts at the top layer, greedily descends, and refines at the bottom layer.

The two critical construction parameters are:

M — maximum number of bi-directional edges per node at each layer. Higher M increases recall but also memory. Typical values: 16–64.
ef_construction — size of the dynamic candidate list during build. Higher values produce a better graph but slow down index construction. Typical: 100–500.

At query time, ef_search controls how many candidates the search explores. It must be ≥ k (the number of neighbors requested).

# Building an HNSW index in FAISS import faiss import numpy as np d = 768 # embedding dimension M = 32 # edges per node ef_construction = 200 # build-time candidate list index = faiss.IndexHNSWFlat(d, M) index.hnsw.efConstruction = ef_construction # Add vectors (no training step required) vectors = np.random.randn(100_000, d).astype('float32') index.add(vectors) # Query-time: set ef_search for recall/speed balance index.hnsw.efSearch = 128 distances, ids = index.search(query_vec, k=10)

Memory warning: HNSW stores the full float32 vectors plus graph edges. For 10M vectors at d=768, expect ~35 GB RAM. If memory is constrained, consider IVF+PQ.

IVF-Flat — Inverted File Index

IVF partitions the vector space into nlist Voronoi cells using k-means clustering. At query time, only the nprobe closest cells are searched, reducing the scan from n to roughly n·(nprobe/nlist) vectors.

Unlike HNSW, IVF requires a training step — you must run k-means on a representative sample before adding vectors.

# IVF-Flat in FAISS import faiss import numpy as np d = 768 nlist = 4096 # number of Voronoi cells quantizer = faiss.IndexFlatL2(d) index = faiss.IndexIVFFlat(quantizer, d, nlist) # Training: requires a representative sample train_data = np.random.randn(200_000, d).astype('float32') index.train(train_data) # Add all vectors after training index.add(all_vectors) # At query time: nprobe controls recall vs speed index.nprobe = 64 distances, ids = index.search(query_vec, k=10)

Rule of thumb: set nlist ≈ sqrt(n) for datasets up to 10M vectors, and nlist ≈ 4·sqrt(n) for larger datasets. Training sample should be at least 30×nlist vectors.

Product Quantization (PQ)

Product Quantization compresses each vector into a compact code by splitting the d-dimensional vector into m sub-vectors and quantizing each sub-vector independently into one of 2^nbits centroids. With m=64 and nbits=8, a 768-dim float32 vector (3072 bytes) is compressed to just 64 bytes — a 48× reduction.

The distance between a query and a PQ code is approximated using Asymmetric Distance Computation (ADC): compute exact sub-vector distances from the query to each centroid, then look up and sum. This avoids decompressing the full vector.

# Product Quantization in FAISS import faiss d = 768 m = 64 # number of sub-quantizers (must divide d) nbits = 8 # bits per sub-quantizer → 256 centroids each index = faiss.IndexPQ(d, m, nbits) # PQ requires training to learn sub-space centroids index.train(train_data) index.add(all_vectors) # Searching uses ADC — fast approximate distances distances, ids = index.search(query_vec, k=10)

Choosing m: m must divide d. Larger m gives better recall (each sub-vector is shorter, so quantization error is lower), but the code is longer. Common choices: m=48 for d=768, m=64 for d=1024.

Composite Indexes: IVF + PQ

The real power of FAISS comes from composing index types. IVFn,PQm first partitions the space with IVF, then compresses residual vectors within each cell using PQ. This yields fast search (only nprobe cells scanned) and low memory (vectors are PQ-compressed).

# Composite IVF+PQ index via factory string import faiss d = 768 index = faiss.index_factory(d, "IVF4096,PQ64") # OPQ pre-rotation improves PQ accuracy index_opq = faiss.index_factory(d, "OPQ64,IVF4096,PQ64") # Train on representative data index.train(train_data) index.add(all_vectors) # Tune at query time index.nprobe = 128 distances, ids = index.search(query_vec, k=10) # Measure recall against brute-force ground truth gt_index = faiss.IndexFlatL2(d) gt_index.add(all_vectors) _, gt_ids = gt_index.search(query_vec, k=10) recall = len(set(ids[0]) & set(gt_ids[0])) / 10 print(f"Recall@10: {recall:.2%}")

FAISS factory strings make it easy to experiment:

Flat — brute force, perfect recall
IVF4096,Flat — IVF partitioning, no compression
IVF4096,PQ64 — IVF + product quantization
OPQ64,IVF4096,PQ64 — optimized PQ rotation + IVF + PQ
HNSW32 — HNSW with M=32
IVF4096,HNSW32,PQ64 — IVF coarse quantizer is HNSW, cells use PQ

Tuning Parameters for Production

Tuning an index for a production RAG pipeline means finding the sweet spot between recall@k, latency (p99), memory footprint, and index build time. Here is a systematic approach.

Step 1: Establish a ground-truth baseline

Build a IndexFlatL2 (or IndexFlatIP for cosine similarity with normalized vectors) and compute ground-truth top-k results for a query set of 1,000–10,000 representative queries.

Step 2: Sweep nprobe / ef_search

For a fixed index structure, sweep the query-time parameter and plot recall vs QPS. This is cheap and doesn't require rebuilding the index.

import time import numpy as np def sweep_nprobe(index, queries, gt_ids, k=10): results = [] for nprobe in [1, 4, 16, 64, 128, 256]: index.nprobe = nprobe t0 = time.perf_counter() _, pred_ids = index.search(queries, k) elapsed = time.perf_counter() - t0 # Compute mean recall@k recalls = [] for i in range(len(queries)): hit = len(set(pred_ids[i]) & set(gt_ids[i])) recalls.append(hit / k) avg_recall = np.mean(recalls) qps = len(queries) / elapsed results.append((nprobe, avg_recall, qps)) print(f"nprobe={nprobe:4d} recall@{k}={avg_recall:.3f} QPS={qps:.0f}") return results

Step 3: Memory budget check

Estimate memory for your index type:

Flat: 4·d·n bytes (float32)
HNSW(M): 4·d·n + 8·M·n bytes (vectors + graph edges)
IVF,PQ(m): m·n bytes (PQ codes) + 4·d·nlist (centroids)

Step 4: GPU acceleration

FAISS supports GPU for IVF-family indexes. Wrap your CPU index with index_cpu_to_gpu:

# Move IVF index to GPU for 5-10× throughput res = faiss.StandardGpuResources() gpu_index = faiss.index_cpu_to_gpu(res, 0, cpu_index) distances, ids = gpu_index.search(queries, k=10)

Production checklist: (1) Always measure recall against ground truth. (2) Use OPQ pre-rotation when using PQ — it often adds 3-5% recall for free. (3) Pre-warm the index with a dummy query before benchmarking. (4) Store your FAISS index with faiss.write_index() and version it alongside your embedding model.

Choosing the right index structure is one of the highest-leverage decisions in a RAG pipeline. HNSW gives you the best recall out of the box, IVF+PQ gives you the best memory efficiency, and composites let you find the Pareto frontier for your specific recall, latency, and memory constraints.

Continue with worked examples

Continue with these focused notes: