Product Quantization: Vector Compression for ANN Search › Approximate Distance Computation

Encoding achieves compression, but the real payoff comes from how PQ enables fast approximate distance computation at query time. Without a clever distance estimation strategy, compressed codes would be useless: you would have to decompress every vector back to full precision before comparing it to a query, negating all the memory savings. PQ avoids this by exploiting the subspace decomposition to precompute everything that depends on the query, so that the per-vector comparison reduces to a handful of integer-indexed memory reads.

The central design choice in PQ distance computation is to invest computation upfront, before scanning the database, and then amortize that investment across every subsequent comparison. This is the same philosophy behind building an index: you do expensive work once so that repeated queries are cheap. The lookup table construction is the "index build" of the distance computation, and it reduces the inner loop from hundreds of floating-point multiplications to a small number of addition operations.

Think of the lookup table as a price list prepared before going shopping. Instead of computing the cost of each item from scratch as you encounter it in the store, you write down the price of each category of item before you enter. Once inside, you just look up prices and add them, without doing any arithmetic. PQ's lookup tables serve exactly this purpose: they precompute the cost (distance contribution) of every possible centroid assignment, so the inner loop is nothing but lookups and additions.

The key insight is that the query is fixed for an entire search, but the database vectors are what you scan. Any computation that depends only on the query can be done once and reused for every database vector. The subspace decomposition makes this possible: the per-subspace query-to-centroid distances depend only on the query and the codebook, neither of which changes during a scan. So you build the lookup tables once and then spend zero arithmetic in the inner loop.

When a query vector $q$ arrives, you want to estimate $\| q - x_i \|^2$ for each database vector $x_i$. If both $q$ and $x_i$ were quantized, you would call this Symmetric Distance Computation (SDC). But PQ uses a smarter approach called Asymmetric Distance Computation (ADC) that keeps the query in full precision.

The key insight that makes ADC possible is that squared Euclidean distance decomposes across subspaces exactly when the subvectors partition the dimensions without overlap. This follows from the fact that for non-overlapping index sets $S_1, S_2, \ldots, S_M$ that together cover all dimensions, $\|u\|^2 = \sum_{m=1}^{M} \|u^{(m)}\|^2$ where $u^{(m)}$ is the restriction of $u$ to the dimensions in $S_m$. Applied to $u = q - x_i$, this gives the exact decomposition of squared Euclidean distance into a sum of per-subspace squared distances:

$$\| q - x_i \|^2 = \sum_{m=1}^{M} \left\| q^{(m)} - x_i^{(m)} \right\|^2$$

where:

• $q$: the full query vector in $\mathbb{R}^d$
• $x_i$: the $i$-th database vector in $\mathbb{R}^d$
• $q^{(m)}$: the $m$-th subvector of $q$, a slice of dimensions corresponding to subspace $m$
• $x_i^{(m)}$: the $m$-th subvector of $x_i$
• $M$: the number of subspaces, where the sum telescopes the full distance into independent per-subspace distances

This decomposition holds exactly because the subvectors partition the dimensions with no overlap, so the squared norms add up to the total squared norm. This is the key property that makes PQ work. If the subspaces shared dimensions, the decomposition would fail and you could not independently precompute per-subspace distances. The non-overlap requirement is therefore a mathematical necessity rather than a convenience: the entire ADC framework rests on this identity, and any architecture that violates it would require fundamentally different distance estimation logic.

Instead of computing $\| q^{(m)} - x_i^{(m)} \|^2$ exactly (which would require decompressing $x_i$), you approximate it as $\| q^{(m)} - c_{m, k_m^{(i)}} \|^2$, the distance from the query's $m$-th segment to the centroid that represents $x_i$'s $m$-th segment. The approximation is good whenever the centroid is close to the actual subvector it stands in for, which is precisely what the k-means training is designed to ensure.

Before scanning the database, you precompute a lookup table for each subspace. For each subspace $m$ and each centroid index $k$, you store:

$$T_m[k] = \left\| q^{(m)} - c_{m,k} \right\|^2 \quad \text{for all } k \in \{0, \ldots, K-1\}$$

where:

• $T_m[k]$: the precomputed squared distance from the query's $m$-th subvector to the $k$-th centroid of subspace $m$
• $q^{(m)}$: the $m$-th subvector of the query, kept in full float32 precision
• $c_{m,k}$: the $k$-th centroid in the codebook for subspace $m$
• $K$: the number of centroids per subspace (typically 256, one per possible byte value, since each code fits in a single byte)

This gives you $M$ tables, each with $K$ entries. Building all tables costs $O(M \cdot K \cdot d^*)$ operations, which for typical parameters is in the tens of thousands of multiplications. Think of each table $T_m$ as a translation layer: given any centroid index for subspace $m$, it instantly tells you how far the query is from that centroid, without any further arithmetic. Once these tables are built, the expensive floating-point work is entirely finished. Every subsequent comparison against a database vector is purely a matter of reading integers and summing precomputed values.

Now, the approximate distance to any database vector $x_i$ (stored as code $(k_1^{(i)}, \ldots, k_M^{(i)})$) is found by summing the precomputed table entries corresponding to each centroid index. No floating-point arithmetic is needed at this stage because all the expensive distance computations happened during the table-building step. The approximate distance is therefore:

$$\hat{d}(q, x_i) = \sum_{m=1}^{M} T_m\!\left[k_m^{(i)}\right]$$

where:

• $\hat{d}(q, x_i)$: the approximate squared distance from query $q$ to database vector $x_i$
• $T_m[\cdot]$: the precomputed lookup table for subspace $m$ (built once per query)
• $k_m^{(i)}$: the centroid index stored in the $m$-th byte of $x_i$'s compressed code
• $\sum_{m=1}^{M}$: the summation operator that accumulates $M$ table lookups, replacing all $d$ floating-point multiplications with $M$ integer-indexed array lookups. This is the key computational saving: instead of operating on raw floats, we simply add precomputed values

This requires $M$ table lookups and $M$ additions. For $M = 8$, each distance computation requires 8 array lookups and 8 additions. This is enormously faster than computing a full dot product over 768 dimensions and changes which hardware can sustain the required throughput. With ADC, the bottleneck shifts from floating-point compute to memory bandwidth, and even the memory access pattern is cache-friendly: the lookup tables are tiny enough to reside entirely in L1 or L2 cache across the entire scan.

To read the diagram above: the query vector enters from the top left in full float32 precision. It is sliced into $M$ subvectors, each of which is compared against the corresponding subspace codebook (the purple box in the center) to populate the lookup tables shown in green on the right. This table-building phase is the only moment when floating-point arithmetic occurs. Meanwhile, each database vector arrives as a compact sequence of integer centroid codes. To compute an approximate distance, those codes simply index into the precomputed lookup tables, and the resulting values are summed. The entire comparison path for a database vector, from reading its bytes to producing a distance estimate, involves no multiplication and no subtraction: only integer-indexed array reads and additions.

You might wonder: if you are scanning millions of vectors, does building the lookup tables at query time even matter? Yes, significantly. Consider the arithmetic:

• Without PQ: Computing $\| q - x_i \|^2$ for one vector requires 768 multiplications, 768 subtractions, and 767 additions. For 10 million vectors, that is roughly $1.5 \times 10^{10}$ floating-point operations.
• With PQ (ADC): The lookup table build costs $8 \times 256 \times 96 \approx 200{,}000$ operations, performed once. Each of the 10 million comparisons then costs 8 lookups and 8 additions, totaling $80{,}000{,}000$ additions. The overall compute is about 200x less.

The memory bandwidth savings are equally dramatic. Instead of reading 3,072 bytes per vector, you read only 8 bytes, a 384x reduction that substantially improves cache efficiency. On modern hardware, memory bandwidth is often the binding constraint for large-scale search: the CPU can perform arithmetic faster than it can fetch data from RAM. By compressing each vector to 8 bytes, PQ ensures that the entire database can cycle through the CPU's cache hierarchy far more efficiently, and the lookup tables themselves (only a few kilobytes) stay warm in L1 cache across the entire scan. This cache-resident lookup table is one of the most elegant aspects of the ADC design: it turns a memory-bound workload into one that is bottlenecked by the tiny, fast cache rather than the large, slow DRAM.