IVF-PQ

Overview

IVF-PQ is an approximate nearest-neighbour (ANN) index that makes very large vector collections searchable on modest hardware. It combines two ideas. An inverted file (IVF) groups vectors into clusters so that a query only looks at a few of them. Product quantization (PQ) compresses each vector into a short code, often a few dozen bytes instead of a few kilobytes.

Together they cut both the work per query and the memory per vector. That is why IVF-PQ is a standard choice when data reaches hundreds of millions or billions of embeddings, and why it appears in FAISS, Milvus and GPU vector search libraries.

An everyday analogy: a large library first sorts books into sections (the clusters), so you only walk to the two or three sections that match your topic. Then, instead of reading each book, you read a short catalogue card for it (the compressed code). You find likely candidates quickly, then pull a few real books off the shelf to check.

What it is

IVF-PQ is not a product but an index design. Its parts are:

With m = 32 and 8 bits per sub-code, every vector becomes 32 bytes, whatever its original size. A 768-dimension float32 vector takes 3,072 bytes, so the compression is about 96 times.

Where it came from

Product quantization for nearest-neighbour search was introduced by Hervé Jégou, Matthijs Douze and Cordelia Schmid in a paper published in IEEE Transactions on Pattern Analysis and Machine Intelligence in 2011. The paper split vectors into sub-spaces, quantized each separately, and estimated distances directly from the codes. It also showed that the method works especially well combined with an inverted file, which the paper called IVFADC, and validated it on a dataset of two billion vectors.

The inverted file itself is an older idea from text retrieval and from image search with visual words, where documents are listed under the terms they contain.

Later work refined both halves. Optimised product quantization learned a rotation before splitting the vector, so information spreads more evenly across sub-spaces. Fast-scan variants used very small codebooks that fit in CPU registers. GPU implementations, first described in the 2017 FAISS GPU paper by Johnson, Douze and Jégou, made IVF-PQ practical for billion-scale batch search. Graph and disk-based methods such as DiskANN later became strong alternatives, but IVF-PQ remains a common baseline.

How it works

1. Train the coarse quantizer

Run k-means on a sample of vectors to find nlist centroids. Each centroid is the centre of one cluster. See clustering for k-means itself.

2. Compute residuals

For each training vector, subtract its nearest centroid. The residual is usually smaller and more uniform than the raw vector, so it compresses better.

3. Train the product quantizer

Split each residual into m equal parts. For a 768-dimension vector and m = 32, each part has 24 dimensions. For each part, run k-means again to learn a codebook of 256 entries (8 bits). Now any 24-dimension part can be replaced by the one-byte index of its closest codebook entry.

4. Add vectors

For each vector: find its nearest centroid, compute the residual, encode it as m bytes, and append the id and code to that centroid's inverted list.

5. Search

For a query:

1. Find the nprobe nearest centroids.
2. For each chosen cluster, compute the query's residual and build m small tables of distances from each query part to all 256 codebook entries.
3. For every code in the cluster, add up m table lookups. This estimates the distance without decompressing anything. Comparing a raw query against compressed database vectors like this is called asymmetric distance computation.
4. Keep the best candidates across all probed clusters.
5. Optionally re-rank the top few hundred with exact distances, using full vectors kept on disk.

import faiss
quantizer = faiss.IndexFlatL2(768)
index = faiss.IndexIVFPQ(quantizer, 768, 4096, 32, 8)  # d, nlist, m, nbits
index.train(sample)
index.add(vectors)
index.nprobe = 32
D, I = index.search(queries, 10)

Key concepts and terms

A worked example

This is an illustrative calculation.

A team holds 1 billion 768-dimension embeddings. Raw float32 storage is 1,000,000,000 × 3,072 bytes, about 3.1 TB. That will not fit in memory on any normal server.

With IVF-PQ at m = 64 (64 bytes per vector), the codes take about 64 GB, plus 8 bytes per id, about 8 GB more. That fits on one large-memory machine.

They set nlist = 65,536. On average each cluster holds about 15,000 vectors. With nprobe = 64, a query scans roughly 1 million codes, about 0.1% of the data. Each code costs 64 table lookups and additions, which is cheap.

They measure recall@10 against exact search on 1,000 sampled queries. PQ error lowers recall, so they keep the top 200 candidates and re-rank them with full vectors read from SSD. Recall improves noticeably at a small latency cost. They then raise nprobe step by step until recall meets their target and stop there.

Strengths and limitations

Strengths:

• Very low memory per vector, set directly by m.
• Scans only a small fraction of the data per query.
• Scales to billions of vectors on a single machine or GPU.
• Well understood, with mature CPU and GPU implementations.
• Clear tuning knobs: nlist, nprobe, m and re-ranking depth.

Limitations:

• Compression lowers precision; high recall usually needs re-ranking.
• Requires training, and quality depends on a representative sample.
• Clusters can become unbalanced if data drifts after training.
• Recall at a given speed is often lower than graph indexes such as HNSW when memory is not a constraint.
• Deletes and updates are less natural than in a database.

How it compares with alternatives

Practical guidance and best practices

1. Start from a memory budget and pick m so that codes fit with room to spare.
2. Choose nlist near a small multiple of the square root of the dataset size, then test.
3. Train on a sample that represents the data you will add, ideally tens of times larger than nlist.
4. Check that the dimension divides evenly by m.
5. Consider a learned rotation (optimised PQ) when dimensions carry very uneven information.
6. Always measure recall against exact search; never tune by speed alone.
7. Add re-ranking with full vectors when the top results must be precise.
8. Retrain when the data distribution shifts, for example after changing embedding models.

Common mistakes

• Training on too small a sample, which gives poor centroids and codebooks.
• Leaving nprobe at 1 and concluding the index is inaccurate.
• Comparing speed between indexes at different recall levels.
• Using inner product on unnormalised vectors when the model expects cosine.
• Forgetting that adding much new data after training can unbalance clusters.

Frequently asked questions

What does nprobe control?

It sets how many clusters are searched for each query. Higher values find more true neighbours but scan more codes, so queries get slower. It is the main knob for trading speed against recall at query time.

How many bytes per vector should I use?

That depends on memory and accuracy needs. More bytes (a larger m) keep more detail and raise recall but use more memory. Many systems start between 16 and 64 bytes and then test on real queries.

Why encode residuals instead of raw vectors?

Vectors in the same cluster share a common centre. Subtracting it leaves smaller differences that a fixed number of codebook entries can describe more accurately. This improves distance estimates at the same code size.

Is IVF-PQ still used now that graph indexes exist?

Yes. Graph indexes usually win when everything fits in memory, but IVF-PQ is attractive when memory is the binding constraint, for GPU batch search, and as a compressed first stage before re-ranking.

Does IVF-PQ work with cosine similarity?

Yes, if you normalise vectors and use inner product or L2, which give the same ranking for unit vectors. Check how your library handles the metric.

Glossary

• Centroid: the mean point of a cluster.
• k-means: an algorithm that groups points around a chosen number of centroids.
• Quantization: replacing a value with the nearest entry from a fixed set.
• Sub-vector: a slice of a vector's dimensions.
• Code: the compact integer representation of a vector.
• Lookup table: precomputed distances reused for every code in a cluster.
• Coarse quantizer: the first-level clustering that decides which list a vector goes into.

Summary

IVF-PQ searches huge vector collections by combining clustering with compression. The inverted file limits each query to a few clusters, and product quantization stores each vector as a short code whose distance to the query can be estimated with table lookups. It trades some precision for large savings in memory and compute, and re-ranking recovers much of that precision. Tune nlist, nprobe, m and re-ranking depth by measuring recall on your own data, and see k-nearest neighbours for the exact problem it approximates.

Related

It belongs to Vector indexes in my stack, under Generative AI and LLMs. Others in the same group: