Skip to content
AI360Xpert
Gen AI

IVF and Product Quantization (IVF-PQ)

IVF clusters vectors to narrow the search space, while PQ chops vectors into chunks and compresses them to save massive amounts of memory.

IVF partitions vectors into Voronoi cells, while Product Quantization splits high-dimensional vectors into smaller sub-vectors for efficient compression.
IVF partitions vectors into Voronoi cells, while Product Quantization splits high-dimensional vectors into smaller sub-vectors for efficient compression.

Why Does This Exist?

When searching through millions or billions of high-dimensional vectors, holding the entire dataset in RAM uncompressed is extremely expensive. Graph-based indexes like HNSW are incredibly fast and accurate, but they have a massive memory footprint because they store raw vectors alongside complex pointer networks.

To perform Approximate Nearest Neighbor (ANN) search at massive scale (e.g., billions of vectors) on hardware with limited memory, you need compression. This is where Inverted File Index (IVF) paired with Product Quantization (PQ) comes in. IVF-PQ is a composite algorithm that attacks the problem from two angles: IVF shrinks the search space, and PQ shrinks the memory required to store the vectors.

By combining these two techniques, vector databases can serve queries across massive datasets using a fraction of the RAM, trading off a slight reduction in recall accuracy for tremendous infrastructure savings.

Think of It Like This

Searching a massive physical library

Imagine you are looking for a specific book in a library containing millions of volumes.

IVF (Inverted File Index) is like having the library divided into distinct genre sections (Sci-Fi, History, Cooking). When you walk in, you don't check every book; you first identify the section that best matches what you're looking for, and you only search within that section. IVF clusters vectors into partitions and only searches the partitions closest to your query.

PQ (Product Quantization) is like replacing the heavy, full-text books with tiny, standardized summary cards. Instead of storing a 500-page book on the shelf, you store a small card that says "Code 42", which maps to a known summary in a master catalog. You lose some of the fine detail of the book, but you can fit 10,000 times as many books in the same physical space.

Together, IVF-PQ means you only check a few sections of the library, and the items you are checking are tiny summary cards, making the search both fast and incredibly space-efficient.

How It Actually Works

The IVF (Inverted File) Component

IVF is a clustering technique designed to reduce the number of distance calculations needed during a search.

  1. Training (Clustering): During index creation, the algorithm runs k-means clustering on a sample of the dataset to find nlist cluster centroids. These centroids partition the vector space into Voronoi cells.
  2. Indexing: Every vector in the dataset is assigned to the nearest centroid. The index maintains an "inverted list"—a mapping from each centroid to all the vectors that belong to its cluster.
  3. Searching: When a query vector arrives, the algorithm calculates its distance to all nlist centroids. It selects the nprobe closest centroids. Then, it only calculates distances against the vectors inside those specific clusters, completely ignoring the rest of the dataset.

Increasing nprobe improves recall (accuracy) but slows down the search, as more vectors must be evaluated.

The PQ (Product Quantization) Component

While IVF reduces how many vectors you search, PQ reduces how big those vectors are. Standard scalar quantization might convert 32-bit floats to 8-bit integers, but Product Quantization is far more aggressive.

  1. Splitting (Sub-vectors): A high-dimensional vector (e.g., 1024 dimensions) is split into m smaller chunks or sub-vectors (e.g., 8 chunks of 128 dimensions each).
  2. Sub-clustering (Codebooks): K-means clustering is run independently on each of the chunks across the dataset. For each chunk position, this produces a codebook of centroids (typically 256 centroids, so they can be indexed with an 8-bit integer).
  3. Quantization: The original vector is replaced by a sequence of short IDs. For each of its m chunks, the algorithm finds the closest centroid in the corresponding codebook and stores its ID.

A 1024-dimension vector of 32-bit floats takes 4096 bytes. With PQ using 8 chunks and 256 centroids per chunk, the vector is compressed down to just 8 bytes!

Asymmetric Distance Computation (ADC)

When a query arrives, you don't decompress the entire database to calculate distances. Instead, IVF-PQ uses Asymmetric Distance Computation. The query vector (which remains uncompressed) is compared against the pre-calculated codebook centroids. The distance to a compressed vector is estimated by looking up the distances to its constituent centroids. This allows for lightning-fast distance estimation without ever reconstructing the original massive vectors.

Show Me the Code

The Faiss library (developed by Meta) is the gold standard for implementing IVF-PQ. Here is how you construct and query an IVF-PQ index.

import faissimport numpy as np
dim = 128          # Dimension of the original vectorsnum_elements = 50000
# Generate random training and database vectorstrain_data = np.float32(np.random.random((10000, dim)))data = np.float32(np.random.random((num_elements, dim)))query_data = np.float32(np.random.random((1, dim)))
# IVF parametersnlist = 100        # Number of clusters (Voronoi cells)
# PQ parametersm = 8              # Number of sub-vectors to split the original vector intobits_per_code = 8  # Number of bits per sub-vector (2^8 = 256 centroids)
# Create the quantizer for the IVF clusteringquantizer = faiss.IndexFlatL2(dim)
# Initialize the IVF-PQ index# metric=faiss.METRIC_L2 specifies Euclidean distanceindex = faiss.IndexIVFPQ(quantizer, dim, nlist, m, bits_per_code)
# The index must be trained on a sample of data to find the IVF and PQ centroidsassert not index.is_trainedindex.train(train_data)assert index.is_trained
# Add the vectors to the indexindex.add(data)
# Set nprobe: how many clusters to search during query timeindex.nprobe = 5
# Perform the searchdistances, indices = index.search(query_data, k=3)
print(f"Nearest neighbor IDs: {indices[0]}")# -> Nearest neighbor IDs: [14213 38921 41045]

Watch Out For

Training on unrepresentative data

Unlike HNSW, IVF-PQ requires a "training" phase to establish its cluster centroids. If the data used to train the index has a different distribution than the data you eventually add to it, the clusters will be severely imbalanced. Most of your vectors will end up stuffed into a few Voronoi cells, destroying the performance benefits of IVF. Always train your index on a large, representative sample of your actual production data.

Over-compressing with PQ

Product Quantization is inherently lossy. If you split a 1536-dimensional embedding into only 4 sub-vectors (m=4), the compression ratio is massive, but the vector loses so much detail that your semantic search results will degrade into noise. Finding the right balance of m (number of chunks) is critical for maintaining acceptable recall.

The Quick Version

  • Storing raw embeddings for billion-scale search consumes too much RAM.
  • IVF (Inverted File Index) reduces search time by grouping vectors into clusters and only searching the clusters nearest to the query.
  • PQ (Product Quantization) reduces memory usage by chopping vectors into smaller chunks and replacing those chunks with short centroid IDs.
  • IVF-PQ combines both, offering massive memory savings and fast queries at the cost of some accuracy (recall) due to the lossy compression.
  • Read HNSW to learn about the non-compressed, highly-accurate alternative to IVF-PQ.
  • Read Approximate Nearest Neighbor Search for an overview of why exact search fails at scale.
  • Read Vector Databases to see how Faiss indexes are wrapped in production-ready databases with APIs and persistent storage.

Related concepts