Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Product Quantization: Vector Compression for ANN Search › The Core Idea: Divide and Quantize

Michael BrenndoerferJanuary 28, 20265 min read

Language AI HandbookAll chapters

Part 44 of 67Retrieval-Augmented Generation

Chapter 341Product Quantization: Vector Compression for ANN Search › The Core Idea: Divide and Quantize

Reading section 2 of 12 · The Core Idea: Divide and Quantize · 5 minSection 2 of 12 · 5 min

Section 2 of 12 · 5 min read

Product Quantization: Vector Compression for ANN Search › The Core Idea: Divide and QuantizeOne section · Sections in this chapter2 / 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

The fundamental challenge of compressing a high-dimensional vector is that you cannot simply round each floating-point coordinate to an integer independently. A 768-dimensional embedding lives in a geometric space where distance relationships encode semantic meaning. Crude per-coordinate quantization destroys those relationships because it treats every dimension as equally and independently important, ignoring the geometric correlations that give the embedding its meaning.

PQ sidesteps this problem with a clever observation. You do not need to quantize the full vector at once. Instead, you split the vector into several shorter subvectors and quantize each subspace independently. Each subspace is small enough that you can learn a good codebook for it, and the independently learned codebooks capture local structure in each region of the full space.

The key insight is that while quantizing all 768 dimensions at once would require an astronomically large codebook to represent the space faithfully, quantizing small slices of, say, 96 dimensions each is a tractable problem. K-means clustering can solve it reliably with a modest number of centroids. And because the subspaces do not overlap, distances in the full space decompose exactly into sums of per-subspace distances, which is the property that makes efficient distance estimation possible.

Think of the subspace decomposition like dividing a long sentence into short phrases for translation. Translating a 100-word sentence directly is difficult because you have to hold the entire meaning in mind at once. Breaking it into five 20-word phrases lets you translate each phrase independently without losing the overall meaning, and the translations can be reassembled afterward. PQ applies the same divide-and-conquer logic: handle each segment of the vector independently, then reassemble the distance estimate by summing up the per-segment contributions.

Product Quantization

Product Quantization is a vector compression method that splits each $d$ -dimensional vector into $M$ subvectors of dimension $d^* = d/M$ , then replaces each subvector with the index of its nearest centroid in a learned codebook of $K$ entries. The full vector is represented by $M$ small integers. The subvector dimension is:

d^* = d / M

If each subspace index uses nbits bits, so that $K = 2^{\text{nbits}}$ , the complete PQ code has length

L = M \log_2 K = M \cdot \text{nbits}

bits. FAISS therefore stores $\lceil M \cdot \text{nbits}/8 \rceil$ bytes per vector. Relative to a float32 vector, the compression ratio is

\text{compression ratio} = \frac{32d}{M \cdot \text{nbits}}.

where:

$d$ : the dimensionality of the original vector
$M$ : the number of subspaces (subvector segments)
$d^* = d/M$ : the dimensionality of each subvector
$K$ : the number of centroids (codewords) in each subspace codebook
$L$ : the total number of bits in the compressed code

To understand why this works, it helps to define a codebook. A codebook for a subspace is a finite set of representative points, or centroids, learned from your training data. When you encode a subvector, you are essentially saying: "instead of storing these exact floating-point coordinates, I will store only the address of the centroid that is closest to this subvector." This is a form of lossy compression, similar in spirit to how a palette of 256 colors can represent a rich image. The quality of the approximation depends on how well the centroids cover the space of typical subvectors encountered in your data. A good codebook positions its centroids where data points cluster, so that most subvectors are close to their assigned centroid and the reconstruction error stays small.

Let us make this concrete. Suppose your embeddings are 768-dimensional float32 vectors. You decide to use $M = 8$ subspaces and $K = 256$ centroids per subspace. Here is what happens:

Each 768-dim vector is split into 8 segments of 96 dimensions each.
For each segment, you maintain a codebook of 256 representative centroids (learned from your data).
Each segment of a database vector is replaced by the index of its closest centroid, a value from 0 to 255 that fits in a single byte.
The original vector, which needed $768 \times 4 = 3{,}072$ bytes as float32, is now stored in just $8 \times 1 = 8$ bytes.

That is a 384x compression ratio. The name "product quantization" comes from the fact that the full codebook is the Cartesian product of the $M$ subspace codebooks, giving you $K^M = 256^8 \approx 1.8 \times 10^{19}$ distinct representable vectors from only $8 \times 256 = 2{,}048$ stored centroids. The economy is striking: a small set of stored centroids spans a space large enough to represent any realistic high-dimensional embedding collection with low reconstruction error. You are exploiting the redundancy of the embedding space, where nearby vectors tend to have similar structure in each subspace, to represent the full diversity of vectors with far fewer numbers than you would need if every dimension were independent.