Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Product Quantization: Vector Compression for ANN Search › Implementation with FAISS

Michael BrenndoerferJanuary 28, 202613 min read

Language AI HandbookAll chapters

Part 44 of 67Retrieval-Augmented Generation

Chapter 341Product Quantization: Vector Compression for ANN Search › Implementation with FAISS

Reading section 6 of 12 · Implementation with FAISS · 13 minSection 6 of 12 · 13 min

Section 6 of 12 · 13 min read

Product Quantization: Vector Compression for ANN Search › Implementation with FAISSOne section · Sections in this chapter6 / 12 ↓

Sections in this chapter12

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

FAISS, Meta's library for efficient similarity search, provides production-grade PQ implementations. Let us build a complete example that compresses a collection of embeddings and measures both memory savings and recall quality.

FAISS handles all the details of codebook training, vector encoding, and ADC internally. You interact with it through a clean index API that is nearly identical to the exact search API, which means you can swap PQ into an existing pipeline with minimal code changes. The main decisions you need to make are the number of subspaces $M$ and the number of bits per code, which together determine the compression ratio and the expected recall.

Setup and Data GenerationLink Copied

First, install FAISS if needed:

In[2]:

Code

# Install faiss (CPU version)
# uv pip install faiss-cpu numpy

import faiss
import numpy as np

# Reproducibility
np.random.seed(42)

# Simulate a realistic embedding distribution
# (embeddings are not uniformly distributed; they cluster)
d = 128  # dimension (use 128 for fast illustration; real embeddings are 768)
N_train = 50000  # vectors for codebook training
N_db = 100000  # database vectors to index
N_query = 1000  # query vectors
K_true = 10  # top-K neighbors to retrieve

# Generate clustered data to mimic real embedding distributions
n_clusters = 50
cluster_centers = np.random.randn(n_clusters, d).astype(np.float32)


def sample_clustered(n, centers, spread=0.5):
    assignments = np.random.randint(0, len(centers), size=n)
    noise = np.random.randn(n, d).astype(np.float32) * spread
    return centers[assignments] + noise


train_vectors = sample_clustered(N_train, cluster_centers)
db_vectors = sample_clustered(N_db, cluster_centers)
query_vectors = sample_clustered(N_query, cluster_centers)

# Normalize so exact cosine and squared-L2 rankings are equivalent
faiss.normalize_L2(train_vectors)
faiss.normalize_L2(db_vectors)
faiss.normalize_L2(query_vectors)

mem_flat = db_vectors.nbytes / (1024**2)

We generate clustered data rather than uniform noise because real embedding distributions are highly non-uniform. Embeddings cluster around semantic concepts, and k-means will find better codebooks when the training data matches this structure. Using uniform random vectors would give artificially optimistic recall results because the centroids would be evenly spread across a space with no real geometric structure, making quantization trivially good.

Building a Brute-Force BaselineLink Copied

Before compressing anything, establish ground truth nearest neighbors using an exact flat index:

In[4]:

Code

# Flat index: exact squared-L2 search, no compression
index_flat = faiss.IndexFlatL2(d)
index_flat.add(db_vectors)

# Get ground-truth top-K neighbors for all queries
_, ground_truth = index_flat.search(query_vectors, K_true)

mem_flat = db_vectors.nbytes / (1024**2)

The flat index is the exact baseline: it stores all vectors in full float32 precision and performs exhaustive search. This gives us ground-truth nearest neighbors to measure recall against the compressed indexes. Every comparison we make to PQ recall uses these results as the gold standard.

Now build a compressed PQ index. The key parameters are $M$ (number of subspaces) and the number of bits per code (which determines $K = 2^{\text{bits}}$ ):

In[7]:

Code

import time

# PQ parameters
M = 8  # number of subspaces; d must be divisible by M
nbits = 8  # bits per subcode; K = 2^8 = 256 centroids per subspace

# Create and train the PQ index using the metric derived above
index_pq = faiss.IndexPQ(d, M, nbits, faiss.METRIC_L2)

# Training: learn the codebooks from training data
t0 = time.time()
index_pq.train(train_vectors)
train_time = time.time() - t0

# Add database vectors (they are encoded and compressed during add)
index_pq.add(db_vectors)

bytes_per_vec_pq = (M * nbits + 7) // 8
mem_pq = N_db * bytes_per_vec_pq / (1024**2)

The compression ratio shows how dramatically PQ reduces memory usage compared to storing full float32 vectors. A higher ratio means more vectors fit in the same amount of RAM, enabling larger indexes on a single machine.

Measuring RecallLink Copied

Compression always trades some accuracy for space. Let us measure how much recall the PQ index loses compared to exact search:

In[10]:

Code

def compute_recall_at_k(retrieved, ground_truth, k):
    """Fraction of ground truth top-k found in retrieved top-k."""
    recalls = []
    for i in range(len(ground_truth)):
        gt_set = set(ground_truth[i][:k])
        ret_set = set(retrieved[i][:k])
        recalls.append(len(gt_set & ret_set) / k)
    return np.mean(recalls)


# Search with PQ index
t0 = time.time()
_, pq_results = index_pq.search(query_vectors, K_true)
pq_search_time = time.time() - t0

# Search with flat index (timed for comparison)
t0 = time.time()
_, flat_results = index_flat.search(query_vectors, K_true)
flat_search_time = time.time() - t0

recall_pq = compute_recall_at_k(pq_results, ground_truth, K_true)
recall_flat = compute_recall_at_k(flat_results, ground_truth, K_true)
flat_search_time_ms = flat_search_time * 1000
pq_search_time_ms = pq_search_time * 1000

Combining IVF and PQLink Copied

As we covered in the previous chapter on IVF indexes, coarse quantization partitions the space into cells so you only search a subset of vectors. Combining IVF with PQ gives you both reduced comparisons and compressed storage. This combination is called IVFPQ and is the most widely deployed configuration in production vector databases.

The two techniques address orthogonal bottlenecks. IVF reduces the number of vectors you compare, while PQ reduces the cost of each comparison. Together they multiply their benefits: if IVF reduces the comparison count by a factor of 50 and PQ reduces the per-comparison cost by a factor of 100, the combined speedup is roughly 5,000x compared to exhaustive full-precision search. That is why IVFPQ is a standard configuration in production vector databases, including Pinecone and Weaviate. Milvus also supports it for large-scale indexes.

In[13]:

Code

# IVFPQ: coarse quantizer (IVF) + fine quantizer (PQ)
nlist = 256  # number of IVF clusters (Voronoi cells)
nprobe = 16  # cells to search at query time

# Build a flat quantizer for the coarse IVF level
coarse_quantizer = faiss.IndexFlatL2(d)

# IVFPQ combines IVF partitioning with PQ compression
index_ivfpq = faiss.IndexIVFPQ(
    coarse_quantizer, d, nlist, M, nbits, faiss.METRIC_L2
)
index_ivfpq.nprobe = nprobe

# Train (learns IVF centroids and PQ codebooks jointly)
t0 = time.time()
index_ivfpq.train(train_vectors)
ivfpq_train_time = time.time() - t0

index_ivfpq.add(db_vectors)

The training time reflects learning both the IVF coarse centroids and the PQ codebooks. With nlist=256 IVF clusters and M=8 PQ subspaces, training is fast because each subspace operates in only d/M dimensions.

In[16]:

Code

# Search and measure recall
t0 = time.time()
_, ivfpq_results = index_ivfpq.search(query_vectors, K_true)
ivfpq_search_time = time.time() - t0

recall_ivfpq = compute_recall_at_k(ivfpq_results, ground_truth, K_true)

The summary table shows the trade-offs across all three methods. IVFPQ achieves the fastest search time because it combines both fewer comparisons (IVF) and cheaper comparisons (PQ), while maintaining recall comparable to pure PQ. Its PQ codes have the same size as those in the flat PQ index, although the inverted lists also store vector identifiers and coarse-index structures. That overhead is usually small relative to the full-precision vectors that PQ replaces.

Visualizing the Recall-Compression Trade-offLink Copied

The number of subspaces $M$ controls the compression-accuracy trade-off, but the direction depends on what is held fixed. In the sweep below, nbits=8 is fixed. Every additional subspace therefore adds another byte to the stored code. Increasing $M$ gives the product codebook $K^M$ possible reconstructions and usually improves recall, but it also produces a longer code and therefore less compression.

If the total code length is held fixed instead, increasing $M$ requires fewer bits and fewer centroids per subspace. That is a different experiment, and larger $M$ is not automatically better. Always state whether nbits or the total bit budget is fixed when comparing PQ configurations.

Let us sweep several values of $M$ at fixed nbits:

In[21]:

Code

m_values = [1, 2, 4, 8, 16, 32]
recalls = []
compression_ratios = []
valid_m_values = []

for m in m_values:
    if d % m != 0:
        continue
    valid_m_values.append(m)
    idx = faiss.IndexPQ(d, m, nbits, faiss.METRIC_L2)
    idx.train(train_vectors)
    idx.add(db_vectors)
    _, res = idx.search(query_vectors, K_true)
    rec = compute_recall_at_k(res, ground_truth, K_true)
    recalls.append(rec)
    bytes_per = (m * nbits + 7) // 8
    ratio = (d * 4) / bytes_per
    compression_ratios.append(ratio)

Out[7]:

Visualization

Line chart showing PQ code size increasing from 1 to 32 bytes as M increases from 1 to 32 at fixed nbits=8; tick labels show compression falling from 512x to 16x for 128-dimensional float32 vectors. — Code size for a 128-dimensional float32 vector as M increases at fixed nbits=8. Each additional subspace adds one byte, so the compression ratio falls from 512x at M=1 to 16x at M=32.

Line chart showing measured Recall@10 increasing as M rises from 1 to 32 at fixed K=256, with M=8 highlighted as the example configuration. — Recall@10 in a deterministic 64-dimensional synthetic benchmark as M increases at fixed K=256. The longer codes provide more representational capacity, so recall rises from M=1 through M=32. The highlighted M=8 point matches the configuration used in the FAISS example.

The two plots make the direction explicit. At fixed nbits, increasing $M$ improves the approximation by spending more bits per vector. Higher recall is not free: the scan performs more table lookups and the index stores more bytes. For real 768-dimensional embeddings, configurations such as $M = 48$ or $M = 96$ use 48 or 96 bytes per vector when nbits=8, corresponding to 64x or 32x compression relative to float32.