Product Quantization (PQ)

9 min read

Product Quantization (PQ) is a lossy compression technique that compresses high dimensional vectors for efficiently storing in DRAM — tackling the storage amplification problem in vector search. By splitting vectors into subspaces and clustering each subspace independently, PQ can compress vectors by up to $32\times$ or more, then answer nearest-neighbor queries with table lookups instead of full floating-point scans.

This post has three parts:

Storage — why raw vectors don't fit a DRAM and how they are compressed using the PQ algorithm.
Lookup — how to query this compressed store using Asymmetric Distance Computation (ADC).
Failure mode — the error that lookup introduces, and why PQ is biased.

1. Storage: Compressing Vectors into Codes

Numbers

Before compression:

Raw 1D vector = 4 bytes
128D vector = 128 x 4 = 512 bytes

After compression:

128D vector = 16 bytes

Why raw storage fails

When serving similarity search at scale, keeping raw floating-point vectors in memory becomes financially and operationally untenable.

For a production-scale dataset:

Total Vectors ( $N$ ): $1 \times 10^9$ (1 Billion vectors)
Dimensionality ( $D$ ): $128$ (standard size for lightweight embedding models)
Data Type: $32\text{-bit}$ float ( $4\text{ bytes}$ per coordinate)

The raw memory footprint of a single vector is:

\text{Raw Vector Size} = D \times 4\text{ bytes} = 128 \times 4 = 512\text{ bytes}

For $1 \text{ Billion}$ vectors:

\text{Total Raw Memory} = 10^9 \times 512\text{ bytes} = 5.12 \times 10^{11}\text{ bytes} \approx 512\text{ GB}

Under a standard cluster limit (such as a $256\text{ GB}$ RAM instance), that database does not fit in DRAM.

The bit-budget idea

Product Quantization compresses each vector into a short sequence of integer indices under a bit budget ( $k$ ):

Set $k = 8\text{ bits}$ per segment (exactly $1\text{ byte}$ ).
An $8\text{-bit}$ space addresses $2^k = 2^8 = 256$ centroid IDs (00000000 … 11111111).
Split a $128\text{-dimensional}$ vector into $M = 16$ sub-vectors, each of dimension: $d = \frac{D}{M} = \frac{128}{16} = 8$

Instead of storing $8$ raw floats ( $32\text{ bytes}$ ) per segment, store only the $8\text{-bit}$ index of the nearest codebook centroid.

In effect, we store 8(k) bits(1 byte) per segment and for a 128D vector, we split it into 16(M) segments and hence the resulting space is 16 bytes per 128D vector.

Compression ratio:

Compressed vector: $M \times 1\text{ byte} = 16\text{ bytes}$
1 Billion vectors: $10^9 \times 16\text{ bytes} = 16\text{ GB}$
Ratio: $512 / 16 = 32\times$ reduction

A $512\text{ GB}$ raw dataset now fits on a $256\text{ GB}$ machine with headroom for indexes and caches.

Training the codebooks (offline)

Unlike ZIP-style compression, PQ is data-dependent. Centroids must sit in the high-density regions of your data.

The training set is a representative sample (e.g. $100{,}000$ vectors) drawn from the database. Then:

Decompose: Split every training vector into $M$ sub-vectors of dimension $d$ .
Cluster: Run $K\text{-Means}$ in each subspace.
Fix $K = 2^k$ : For $k=8$ , each subspace learns $K=256$ centroids.
Save sub-codebooks: The cluster centers become $\mathcal{C}_m$ for subspace $m$ : $\mathcal{C}_m = \{ \mathbf{c}_{m,0}, \mathbf{c}_{m,1}, \dots, \mathbf{c}_{m, 2^k - 1} \} \subset \mathbb{R}^d$

The master codebook is the Cartesian product:

\mathcal{C} = \mathcal{C}_1 \times \mathcal{C}_2 \times \dots \times \mathcal{C}_M

These codebooks are trained once, then reused for every encode and every query.

Encoding one vector (worked example)

Trace encoding a single 4D vector ( $D = 4$ ) with $M = 2$ halves ( $d = 2$ ) and a toy bit budget $k = 2$ :

\mathbf{o} = [0.15, \ 0.85, \ 0.45, \ -0.25]

Split into subspaces:

$\mathbf{o}_1 = [0.15, \ 0.85]$
$\mathbf{o}_2 = [0.45, \ -0.25]$

Use trained sub-codebooks (output of K-Means on the training set — not invented from $\mathbf{o}$ itself). With $k = 2$ , each codebook has $2^k = 4$ centroids:

$\mathcal{C}_1$ :
- $\mathbf{c}_{1,0} = [0.0, \ 0.0]$ (index 0)
- $\mathbf{c}_{1,1} = [0.1, \ 0.9]$ (index 1)
- $\mathbf{c}_{1,2} = [0.8, \ 0.8]$ (index 2)
- $\mathbf{c}_{1,3} = [-0.5, \ 0.5]$ (index 3)
$\mathcal{C}_2$ :
- $\mathbf{c}_{2,0} = [0.0, \ 0.0]$ (index 0)
- $\mathbf{c}_{2,1} = [0.5, \ -0.2]$ (index 1)
- $\mathbf{c}_{2,2} = [-0.8, \ -0.8]$ (index 2)
- $\mathbf{c}_{2,3} = [0.9, \ 0.9]$ (index 3)

Pick the nearest centroid in each half (squared Euclidean distance):

For $\mathbf{o}_1 = [0.15, \ 0.85]$ vs $\mathcal{C}_1$ :

vs $\mathbf{c}_{1,0}$ : $0.745$
vs $\mathbf{c}_{1,1}$ : $\mathbf{0.005}$ (nearest → index 1)
vs $\mathbf{c}_{1,2}$ : $0.425$
vs $\mathbf{c}_{1,3}$ : $0.545$

For $\mathbf{o}_2 = [0.45, \ -0.25]$ vs $\mathcal{C}_2$ :

vs $\mathbf{c}_{2,0}$ : $0.265$
vs $\mathbf{c}_{2,1}$ : $\mathbf{0.005}$ (nearest → index 1)
vs $\mathbf{c}_{2,2}$ : $1.865$
vs $\mathbf{c}_{2,3}$ : $1.525$

What gets stored: throw away the floats; keep only the index pair:

\text{code}(\mathbf{o}) = [1, \ 1] \implies \text{binary } \mathbf{0101}_2

	Size
Original	$128\text{ bits}$ ( $4$ floats × $32$ bits)
Stored code	$4\text{ bits}$ ( $2$ indices × $2$ bits)
Reduction	$32\times$

That is the storage contract: RAM holds codes + codebooks, not the original vectors.

2. Lookup: Finding Neighbors with ADC

Storage solved the DRAM problem. Lookup answers: given a query, which stored codes are closest?

The query and the compressed database

Query:

\mathbf{q} = [0.2,\ 0.8,\ 0.4,\ -0.3]

Split like storage did:

$\mathbf{q}_1 = [0.2,\ 0.8]$
$\mathbf{q}_2 = [0.4,\ -0.3]$

Three documents in the compressed DB (only codes are present at search time):

ID	Original vector (not in RAM)	Stored code
A	$[0.15,\ 0.85,\ 0.45,\ -0.25]$ (from Storage)	`[1, 1]`
B	some vector that quantized to far centroids	`[2, 2]`
C	some vector that quantized to a mixed pair	`[1, 0]`

Decoding a code into a stand-in vector

$\bar{\mathbf{o}}_A = [0.1,\ 0.9,\ 0.5,\ -0.2]$ is not a rewrite of A's original floats. It is the decode of the only thing left for A: code [1, 1].

From the Storage encode step:

Half of A	Nearest centroid	Index kept
$[0.15,\ 0.85]$	$\mathbf{c}_{1,1} = [0.1,\ 0.9]$	`1`
$[0.45,\ -0.25]$	$\mathbf{c}_{2,1} = [0.5,\ -0.2]$	`1`

Lookup reconstructs by concatenating those codebook entries:

[1,\ 1] \;\rightarrow\; \mathbf{c}_{1,1}\,\|\,\mathbf{c}_{2,1} = [0.1,\ 0.9]\,\|\,[0.5,\ -0.2] = [0.1,\ 0.9,\ 0.5,\ -0.2] = \bar{\mathbf{o}}_A

True A (gone): $[0.15,\ 0.85,\ 0.45,\ -0.25]$
Stand-in $\bar{\mathbf{o}}_A$ (what lookup scores): $[0.1,\ 0.9,\ 0.5,\ -0.2]$

Same decode for the others:

[2, 2] → $[0.8,\ 0.8,\ -0.8,\ -0.8] = \bar{\mathbf{o}}_B$
[1, 0] → $[0.1,\ 0.9,\ 0.0,\ 0.0] = \bar{\mathbf{o}}_C$

Why ADC adds two LUT values

Squared distance over all 4 coordinates is the sum of the two half-distances:

\begin{aligned} \text{distance}^2(\mathbf{q}, \bar{\mathbf{o}}_A) &= \underbrace{(0.2-0.1)^2 + (0.8-0.9)^2}_{\text{first half}} + \underbrace{(0.4-0.5)^2 + (-0.3-(-0.2))^2}_{\text{second half}} \\ &= 0.02 + 0.02 \\ &= 0.04 \end{aligned}

So 0.02 + 0.02 is not an arbitrary trick — it is the full stand-in distance, split across subspaces. ADC precomputes every half-distance into look-up tables, then scores each code with lookup + lookup + add.

LUT₁ (distances from $\mathbf{q}_1$ to $\mathcal{C}_1$ ):

0 → $0.68$ · 1 → $0.02$ · 2 → $0.36$ · 3 → $0.58$

LUT₂ (distances from $\mathbf{q}_2$ to $\mathcal{C}_2$ ):

0 → $0.25$ · 1 → $0.02$ · 2 → $1.69$ · 3 → $1.69$

Scoring codes and returning neighbors

Document	Code	ADC score
A	`[1, 1]`	LUT₁[`1`] + LUT₂[`1`] = `0.02 + 0.02 = 0.04`
B	`[2, 2]`	`0.36 + 1.69 = 2.05`
C	`[1, 0]`	`0.02 + 0.25 = 0.27`

Ranked by ascending score:

Rank	Returned?	Document	Score
1	yes (top-1 and top-2)	A	`0.04`
2	yes (top-2 only)	C	`0.27`
3	no	B	`2.05`

Top-1 returns A
Top-2 returns A, then C
B is not returned

“Match” here means lowest ADC score against stand-ins, not exact distance to the original floats.

3. Failure Mode: The Error Lookup Introduces

Lookup returned A because ADC reported distance 0.04. That number is distance to the stand-in $\bar{\mathbf{o}}_A = [0.1,\ 0.9,\ 0.5,\ -0.2]$ , not to the true vector $[0.15,\ 0.85,\ 0.45,\ -0.25]$ .

True distance from $\mathbf{q}$ to real A:

Differences: $[-0.05,\ 0.05,\ 0.05,\ -0.05]$
Squared distance: $4 \times 0.0025 = 0.01$

What ranking used (ADC)	What we actually wanted
`0.04` (query ↔ stand-in)	`0.01` (query ↔ true A)

ADC was $4\times$ too large. In this tiny DB, A still won — but the score the system trusted was biased. Heuristic PQ ranks “query ↔ centroid reconstruction,” while the user asked for “query ↔ real vector.” Vectors far from their centroids are systematically mis-scored, and classic PQ has no error bound on how bad that gap can get.

On datasets like MSong, relative distance error can exceed 50%, and recall can fall below $60\%$ even after re-ranking.

How later systems harden this

Methods like RaBitQ (used in systems such as Turbopuffer) still compress, but they correct for the gap between the real vector and its stand-in instead of treating the ADC score as truth. In this example: do not trust 0.04 when A was actually at 0.01. That correction yields an unbiased estimate and much stabler recall (often $>90\%$ ) without silent ranking collapses.

RaBitQ — the unbiased-bounds fix to PQ's failure mode
Storage Amplification in Vector Search — the problem PQ exists to solve
DRAM — the expensive tier PQ compresses vectors to fit