Product Quantization: Vector Compression for ANN Search › Worked Example

Let us trace through PQ with a tiny example to make the mechanics concrete before looking at code. Suppose your embeddings are 4-dimensional (just to keep numbers small) and you use $M = 2$ subspaces, $K = 4$ centroids each.

Working through a small example is valuable for understanding the mechanics and for building intuition about the error properties of PQ. In this example we will see exactly where approximation error enters and why it tends to be small for true nearest neighbors while still being large enough to occasionally produce ranking errors for borderline cases.

Training data (6 vectors):

Notice that the training data has a clear geometric structure: vectors a and b have small values in subspace 1 and large values in subspace 2, while c and d are the reverse. Vectors e and f occupy a middle region. K-means in each subspace will naturally discover these clusters, and the resulting centroids will be positioned to cover the data distribution efficiently. Each centroid ends up representing a cluster of points, and the centroid's coordinates are the mean of all the points in its cluster.

After k-means in subspace 1, suppose we get centroids $c_{1,0} = [0.05, 0.25]$, $c_{1,1} = [0.85, 0.85]$, $c_{1,2} = [0.45, 0.55]$.

After k-means in subspace 2, suppose we get centroids $c_{2,0} = [0.75, 0.85]$, $c_{2,1} = [0.05, 0.15]$, $c_{2,2} = [0.55, 0.45]$.

Step 1: Encode database vectors. We find the nearest centroid in each subspace for each vector:

Encoding vector a = [0.1, 0.2, 0.8, 0.9]:

• Subspace 1: $[0.1, 0.2]$ is closest to $c_{1,0} = [0.05, 0.25]$, so $k_1 = 0$.
• Subspace 2: $[0.8, 0.9]$ is closest to $c_{2,0} = [0.75, 0.85]$, so $k_2 = 0$.
• Code for a: $(0, 0)$.

The code $(0, 0)$ is just two integers, but it carries meaningful geometric information: it tells us that this vector lives in the region of subspace 1 near centroid 0 and the region of subspace 2 near centroid 0. Any query that is also near those centroids will receive a low approximate distance estimate, correctly reflecting the true proximity.

Encoding vector c = [0.9, 0.8, 0.1, 0.2]:

• Subspace 1: $[0.9, 0.8]$ is closest to $c_{1,1} = [0.85, 0.85]$, so $k_1 = 1$.
• Subspace 2: $[0.1, 0.2]$ is closest to $c_{2,1} = [0.05, 0.15]$, so $k_2 = 1$.
• Code for c: $(1, 1)$.

Encoding vector e = [0.5, 0.5, 0.5, 0.4]:

• Subspace 1: $[0.5, 0.5]$ is closest to $c_{1,2} = [0.45, 0.55]$, so $k_1 = 2$.
• Subspace 2: $[0.5, 0.4]$ is closest to $c_{2,2} = [0.55, 0.45]$, so $k_2 = 2$.
• Code for e: $(2, 2)$.

Step 2: Build lookup tables for query. Suppose $q = [0.12, 0.18, 0.82, 0.87]$:

Build lookup tables by computing the distance from each query subvector to every centroid:

• $T_1[0] = \| [0.12, 0.18] - [0.05, 0.25] \|^2 = 0.0049 + 0.0049 = 0.0098$
• $T_1[1] = \| [0.12, 0.18] - [0.85, 0.85] \|^2 \approx 0.5329 + 0.4489 = 0.9818$
• $T_1[2] = \| [0.12, 0.18] - [0.45, 0.55] \|^2 \approx 0.1089 + 0.1369 = 0.2458$
• $T_2[0] = \| [0.82, 0.87] - [0.75, 0.85] \|^2 = 0.0049 + 0.0004 = 0.0053$
• $T_2[1] = \| [0.82, 0.87] - [0.05, 0.15] \|^2 \approx 0.5929 + 0.5184 = 1.1113$
• $T_2[2] = \| [0.82, 0.87] - [0.55, 0.45] \|^2 \approx 0.0729 + 0.1764 = 0.2493$

Step 3: Compute approximate distances. Now use the lookup tables to estimate the distance from $q$ to each encoded database vector:

• Distance to a (code $(0, 0)$): $T_1[0] + T_2[0] = 0.0098 + 0.0053 = 0.0151$
• Distance to c (code $(1, 1)$): $T_1[1] + T_2[1] = 0.9818 + 1.1113 = 2.0931$
• Distance to e (code $(2, 2)$): $T_1[2] + T_2[2] = 0.2458 + 0.2493 = 0.4951$

The ranking is: a is closest, then e, then c. This matches the true ranking based on the raw vectors (which you can verify by computing exact distances from $q$ to each vector). Vector a, which shares a similar geometric structure to the query in both subspaces, receives the lowest approximate distance. Vector c, which is far in both subspaces, receives the highest.

Step 4: Verify the approximation error. The true distance from $q$ to $a$ is:

$$\| [0.12, 0.18, 0.82, 0.87] - [0.1, 0.2, 0.8, 0.9] \|^2 = 0.0004 + 0.0004 + 0.0004 + 0.0009 = 0.0021$$

The approximate distance was 0.0151, so the absolute error is 0.013. This is larger than the true distance itself, but the relative ranking is correct. The approximation overestimates the distance to $a$ because both centroids are slightly displaced from $a$'s actual position, and both displacements add positive contributions to the estimated distance. However, because $q$ is also close to $a$'s centroids, the lookup table values $T_1[0]$ and $T_2[0]$ are still much smaller than the values for the other centroids, so the ranking is preserved. This is the fundamental property that makes PQ useful: even though the absolute distances are approximate, the relative ordering among the closest candidates is preserved well enough for top-$K$ retrieval to succeed with high probability.