Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

IVF Index: Clustering-Based Vector Search & Partitioning › IVF-PQ: Combining Clustering with Compression

Michael BrenndoerferJanuary 27, 20266 min read

Language AI HandbookAll chapters

Part 44 of 67Retrieval-Augmented Generation

Chapter 340IVF Index: Clustering-Based Vector Search & Partitioning › IVF-PQ: Combining Clustering with Compression

Reading section 7 of 12 · IVF-PQ: Combining Clustering with Compression · 6 minSection 7 of 12 · 6 min

Section 7 of 12 · 6 min read

IVF Index: Clustering-Based Vector Search & Partitioning › IVF-PQ: Combining Clustering with CompressionOne section · Sections in this chapter7 / 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

For very large datasets, even the vectors within each cell may not fit in memory. IVF can be combined with Product Quantization (PQ), a compression technique that is each vector using compact codes instead of full floating-point values. We'll cover Product Quantization in detail in the next chapter, but the combination is important enough to preview here.

IVF-PQ

An IVF-PQ index combines IVF's space partitioning with Product Quantization's vector compression. Centroids identify which cells to search, and within each cell, vectors are stored as compressed PQ codes rather than full-precision vectors. This reduces memory by 10-50 $\times$ while maintaining reasonable recall.

The FAISS implementation makes IVF-PQ straightforward to use:

In[2]:

Code

# IVF-PQ index: 100 centroids, 8 sub-quantizers, 8 bits each
m_subquantizers = 8  # Number of subvectors (d must be divisible by m)
n_bits = 8  # Bits per sub-quantizer (2^8 = 256 codes per subspace)

index_ivfpq = faiss.IndexIVFPQ(
    quantizer, d, n_centroids_faiss, m_subquantizers, n_bits
)
index_ivfpq.train(data)
index_ivfpq.add(data)

In[3]:

Code

# Compare memory usage
bytes_flat = data.nbytes  # Full vectors: n * d * 4 bytes
bytes_ivfpq = (
    index_ivfpq.ntotal * m_subquantizers
)  # PQ codes: n * m bytes (approx)

The compression is large. To appreciate just how much space is saved, we quantify the compression step by step, tracing the calculation from the original vector representation down to the compact PQ code.

Original vector size:

Each vector in float32 format requires 4 bytes per dimension. A 32-bit floating-point number can stand for a continuous range of values with roughly 7 decimal digits of precision, which is the standard representation used in most machine learning frameworks:

\begin{aligned} \text{Bytes per vector} &= d \times 4 && \text{(}d \text{ dimensions, 4 bytes per float32)} \\ &= 64 \times 4 && \text{(substitute } d = 64\text{)} \\ &= 256 \text{ bytes} && \text{(total size per vector)} \end{aligned}

where:

$d = 64$ : the dimensionality of each vector
Factor of 4: bytes required for a float32 value (32 bits = 4 bytes)

This is the uncompressed storage cost: every dimension requires a full floating-point number. For a dataset of one million vectors, this amounts to 256 megabytes just for the vector data alone.

PQ code size:

Product Quantization compresses each vector by dividing it into sub-vectors and encoding each with a single byte. Rather than storing 8 continuous floating-point values per sub-vector, PQ replaces each sub-vector with the index of the closest entry in a learned codebook. Since each index is a single byte, it can reference up to 256 different codewords.

\begin{aligned} \text{Bytes per PQ code} &= m \times 1 && \text{(}m \text{ sub-quantizers, 1 byte each)} \\ &= 8 \times 1 && \text{(substitute } m = 8\text{)} \\ &= 8 \text{ bytes} && \text{(total compressed size)} \end{aligned}

where:

$m = 8$ : the number of sub-quantizers (sub-vectors) used in Product Quantization
Each sub-quantizer uses 8 bits (1 byte) to encode its portion of the vector

Each byte can stand for 256 ( $2^8$ ) different values, so we're in effect replacing $d/m = 64/8 = 8$ continuous dimensions with a single discrete code from a learned codebook. The codebook is learned during training and shared across all vectors, so its storage cost is amortized and negligible relative to the vector data.

The PQ code is the vector in just 8 bytes compared to the original 256 bytes, a compression factor of 32. The tradeoff is some loss in recall since PQ introduces quantization error in the distance computations. The distances computed from PQ codes are approximations of the true Euclidean distances, and this approximation error can cause some nearest neighbors to be ranked incorrectly.

In[6]:

Code

# Compare recall: IVF-Flat vs IVF-PQ
nprobe_compare = 10
index.nprobe = nprobe_compare
index_ivfpq.nprobe = nprobe_compare

_, indices_flat = index.search(queries, top_k)
_, indices_pq = index_ivfpq.search(queries, top_k)

recall_flat = 0
recall_pq = 0
for i in range(n_queries):
    truth = set(gt_indices[i].tolist())
    recall_flat += len(set(indices_flat[i].tolist()) & truth) / top_k
    recall_pq += len(set(indices_pq[i].tolist()) & truth) / top_k

recall_flat /= n_queries
recall_pq /= n_queries

The results show that IVF-PQ reaches strong recall (typically 90-95% of IVF-Flat's performance) while compressing vectors by 32x. This modest accuracy drop is well worth the large memory savings and lets billion-scale deployments where storing full-precision vectors would be prohibitively expensive. The compression makes IVF-PQ the practical choice for very large collections. To quantify the scale: one billion vectors compressed to 8 bytes each requires only 8 GB of memory, versus 256 GB for uncompressed storage, making the difference between feasible and infeasible deployments.

Out[17]:

Visualization

Line chart comparing Recall@10 versus nprobe for IVF-Flat and IVF-PQ, with shaded gap region showing the modest recall drop from 32x compression. — Representative accuracy-compression tradeoff comparing IVF-Flat and IVF-PQ across nprobe settings. IVF-Flat (blue circles, 256 bytes per vector) is the uncompressed baseline, while IVF-PQ (orange squares, 8 bytes per vector) reaches 32x compression. IVF-PQ retains about 90 to 99% of IVF-Flat's recall across the displayed settings and reaches 95% recall at nprobe=20 while using about 3% of the vector memory.

The training cost increases with the number of vectors and the number of clusters. For a dataset of 10,000 vectors and 100 clusters, k-means typically converges within a few seconds on a modern laptop. For datasets with millions of vectors or hundreds of thousands of clusters, training can take minutes to hours. To speed up index construction, FAISS gives options like multi-threading and sampling-based k-means variants.