Product quantization

On this page 8

Product quantization (PQ) is a lossy vector compression method that splits each high-dimensional vector into several short subvectors, replaces every subvector with the identifier of its nearest learned centroid, and stores the vector as a compact sequence of those identifiers. In the retrieval & knowledge layer of artificial intelligence systems, it is the standard way to fit hundreds of millions of embeddings into memory and to compute approximate distances between a query and stored items without decompressing them.

Product quantization is rarely used alone. It typically serves as the storage and distance engine inside an approximate nearest neighbor search index, combined with a coarse partitioning structure such as an IVF index or with a graph index such as HNSW or DiskANN, and followed by exact reranking of a short candidate list.

How product quantization encodes a vector

Product quantization encodes a vector by treating its dimensions as a Cartesian product of subspaces and quantizing each subspace independently. A vector of dimension D is cut into M contiguous subvectors of dimension D/M. For each subspace, a separate codebook of K centroids is trained with k-means on a sample of the data, usually with K = 256, so that each centroid index fits in exactly one byte.

Encoding replaces every subvector with the index of its closest centroid in the corresponding codebook. The full vector therefore becomes a code of M bytes. The key insight is that the effective codebook size is K to the power M: with 8 subspaces and 256 centroids each, the scheme can represent 256^8 distinct reconstructions while storing only 8 times 256 centroids, which would be impossible with a single flat k-means codebook.

The following table shows how typical settings translate into memory use for a 768-dimensional float32 embedding, which occupies 3,072 bytes uncompressed.

Setting (M × bits)Code size per vectorCompression ratioTypical recall impact
PQ48 × 848 bytesAbout 64×Noticeable without reranking
PQ96 × 896 bytesAbout 32×Moderate, often acceptable
PQ192 × 8192 bytesAbout 16×Small
PQ384 × 4192 bytesAbout 16×Small, faster scans with SIMD
Memory footprint of common product quantization settings

Computing distances on compressed codes

Product quantization makes search fast because distances are computed directly on the codes through lookup tables, not on reconstructed vectors. In asymmetric distance computation (ADC), the query stays uncompressed. For each subspace, the system precomputes the distance from the query subvector to all 256 centroids, producing an M × 256 table. The distance to any stored vector is then the sum of M table lookups, one per byte of its code.

Symmetric distance computation (SDC) also quantizes the query and uses precomputed centroid-to-centroid distances. It is slightly cheaper but adds quantization error on both sides, so ADC is the usual default. Modern implementations such as fast-scan PQ use 4-bit codes so that the lookup tables fit in CPU vector registers, which multiplies scan throughput.

Product quantization works most naturally with squared Euclidean distance, which decomposes additively across subspaces. Inner product also decomposes and is supported, while cosine similarity is handled by normalizing vectors before training and encoding.

Variants and refinements of product quantization

Several refinements reduce the quantization error of plain PQ, mainly by rotating the data or by encoding a residual instead of the raw vector. The table summarizes the variants that practitioners meet most often.

VariantCore ideaMain benefitCost
Optimized PQ (OPQ)Learns a rotation before splittingBalances variance across subspacesExtra matrix multiply per query
IVF-PQEncodes residuals to coarse centroidsLower error, searches few listsNeeds a tuned number of probes
Additive quantizationSums full-dimension codewordsHigher accuracy per byteSlower encoding
Residual quantizationQuantizes errors in stagesProgressive refinementSequential encoding cost
4-bit fast-scan PQ16 centroids per subspaceRegister-resident lookup tablesCoarser per-subspace resolution
Main product quantization variants

IVF-PQ is the most widely deployed combination. A coarse quantizer assigns each vector to one of thousands of inverted lists, and product quantization encodes only the residual between the vector and its list centroid. Because residuals have smaller spread than raw vectors, the same code size yields noticeably lower distortion.

Product quantization compared with other compression methods

Product quantization sits between scalar quantization, which compresses each dimension separately, and binary embeddings, which keep one bit per dimension. The right choice depends on how much memory must be saved and how much recall can be lost before reranking.

MethodTypical compressionDistance computationBest fit
Scalar quantization (int8)About 4×Integer arithmetic per dimensionHigh recall with moderate savings
Product quantization16× to 64×Table lookups per subspaceVery large corpora in RAM
Binary quantizationAbout 32×Hamming distanceModels trained for binary output
Matryoshka truncation2× to 8×Standard float distanceModels trained with nested dimensions
Vector compression approaches in retrieval systems

These approaches combine well. A common design truncates Matryoshka embeddings, compresses them with PQ for the first pass, and keeps full-precision vectors on disk for the final exact rescoring of the top few hundred candidates.

Configuring product quantization in practice

Configuring product quantization means choosing the number of subspaces, the bits per code and the training sample so that memory, latency and recall targets are met together. The dimension must be divisible by M, and each subspace should keep at least a few dimensions; values of 4 to 16 dimensions per subspace are typical.

SituationRecommended choiceReason
Memory is the hard limitFewer subspaces plus rerankingSmallest codes, recall recovered later
Recall must stay above 0.95More subspaces, OPQ, rescoringLower distortion per vector
Lowest CPU latency4-bit fast-scan PQLookups stay in registers
Data distribution driftsPeriodic codebook retrainingStale centroids raise error
Under one million vectorsFlat or HNSW without PQCompression gains are small
Decision guide for product quantization settings

Codebooks should be trained on a representative sample, commonly tens to hundreds of thousands of vectors, drawn from the same embedding model and domain as the indexed data. Recall should always be measured against exact nearest neighbor search on a held-out query set rather than assumed from compression ratios.

Limitations and common mistakes

Product quantization trades accuracy for scale, and its errors are systematic rather than random. Distances on codes are approximations, so close neighbors can swap order, and very fine-grained similarity differences may disappear entirely.

  • Skipping reranking: final rankings based only on PQ distances lose relevant items that exact scoring would recover.
  • Unbalanced subspaces: without a rotation such as OPQ, a few subspaces carry most of the variance and dominate the error.
  • Training on the wrong data: codebooks learned from another embedding model or domain produce high distortion.
  • Mixing metrics: training with Euclidean distance and searching with unnormalized inner product gives inconsistent rankings.
  • Ignoring updates: adding many vectors from a shifted distribution without retraining slowly erodes recall.

Explained without jargon

An embedding is a long list of numbers that describes the meaning of a text or image. Storing millions of these lists takes a great deal of memory. Product quantization cuts each list into short pieces and replaces every piece with the number of the closest entry in a small, prepared catalog of typical pieces.

It works like describing an outfit by saying “jacket style 12, trousers style 87, shoes style 3” instead of photographing it. The description is tiny and good enough to find similar outfits quickly. The cost is some lost detail, so systems usually take a final, careful look at the best matches before answering.

A typical use case

A legal research platform indexes 200 million passage embeddings of 768 dimensions for a retrieval-augmented generation assistant. Stored as float32, the vectors would need about 600 GB of RAM. The engineering team builds an IVF-PQ index with 65,536 lists, OPQ rotation and 96-byte codes, which shrinks the in-memory index to roughly 20 GB including list overhead.

At query time the system probes 64 lists, scores candidates with lookup tables, and passes the top 500 to an exact rescoring step that reads full vectors from SSD. Measured against exact search on 5,000 test queries, recall at 10 reaches about 0.96, and median search latency stays below 20 milliseconds on a single server, which makes the assistant affordable to run.