Product Quantization: Vector Compression for ANN Search

In the previous two chapters, we explored IVF indexes and HNSW graphs, two strategies that reduce the number of comparisons needed to find approximate nearest neighbors. But there is another bottleneck we have not addressed: even when you only compare a query against a small fraction of your index, each comparison still requires loading a full 768-dimensional float32 vector from memory and computing a dot product. When your index holds tens of millions of embeddings, that memory footprint alone can exceed the capacity of a single machine.

Product Quantization (PQ) attacks this problem from a different angle: rather than reducing the number of comparisons, PQ reduces the cost and size of each comparison. It compresses each embedding from hundreds of floating-point numbers down to a handful of small integers, achieving compression ratios of 10x to 100x while preserving enough geometric structure to compute useful approximate distances. The resulting index can fit in RAM where a full-precision index would require a distributed cluster.

Think of PQ as giving each vector a compact postal address rather than GPS coordinates. Instead of storing the precise latitude and longitude of every building in a city, you store only the zip code and block number. You lose some precision, but you gain the ability to store every address in the city in a pocket notebook. When someone asks "which buildings are near this location?", you can narrow the search to a few zip codes and find good candidates without ever loading the full coordinate database.

The insight that makes PQ so powerful is the combination of two ideas. First, the high-dimensional space can be factored into independent lower-dimensional subspaces, where each subspace is much easier to quantize accurately than the full space. Second, distances in the full space decompose exactly across those subspaces, so you can estimate the full distance by summing independently precomputed per-subspace distances. This second property is what allows the entire expensive computation to happen once per query rather than once per database vector, cutting the inner loop to a series of simple memory reads.

To understand why those two ideas combine to produce such dramatic speedups, you need to understand the geometry of quantization, why the product decomposition matters, and how the resulting lookup-table machinery achieves both memory compression and fast distance estimation. This chapter covers all three: how PQ codebooks are learned, how distances are approximated efficiently with Asymmetric Distance Computation, and how PQ combines with IVF to give you both reduced comparisons and reduced memory at scale.

The practical stakes are real. A production RAG system indexing 500 million document chunks at 768 dimensions needs roughly 1.5 TB of RAM just to hold the raw embeddings, which forces a distributed deployment. The same index with PQ at $M = 96$ fits in 48 GB on a single server. This reduction can turn a distributed system that requires an infrastructure team into one that a single engineer can deploy and operate.

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.

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:

1. Each 768-dim vector is split into 8 segments of 96 dimensions each.
2. For each segment, you maintain a codebook of 256 representative centroids (learned from your data).
3. 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.
4. 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.

The quality of PQ depends entirely on how well the codebooks capture the structure of your data. A good codebook should have its centroids positioned where data points cluster in each subspace. Poorly positioned centroids (for instance, those uniformly distributed in a region where real data is sparse) lead to high quantization error and degraded recall. This is why PQ always requires a training phase: the codebooks must be fitted to the distribution of your embeddings before you can compress and search them effectively.

The training process is conceptually simple: for each subspace, collect all the corresponding subvectors from your training data, and run k-means clustering to find $K$ representative centroids. The tricky part is scale. You need enough training vectors to populate all $K$ centroids with reasonable coverage, which in practice means at least several hundred times $K$ training examples per subspace. For $K = 256$, this means at least 50,000 to 100,000 training vectors, a number easily obtained from a typical corpus but worth planning for in advance.

Think of codebook training as photographing a neighborhood to build a visual catalog. If you photograph only one street, your catalog will misrepresent the full variety of buildings. If you photograph a representative sample of every street and neighborhood, your catalog will cover the full range of architectural styles that a visitor might encounter. PQ codebooks work the same way: a training set drawn from the same distribution as your final index will produce centroids that are well-positioned for the actual data, while a mismatched training set will leave gaps in the coverage and inflate quantization error.

An important practical consideration is that the training set should match the distribution of vectors you will index. If your index will contain embeddings from a news corpus, train the codebooks on a sample from that corpus, not from a generic Wikipedia dump. The closer the match between training and indexing distributions, the lower the average quantization error will be, and the better your recall.

For each subspace $m \in \{1, \ldots, M\}$, you extract the $m$-th segment from every training vector to form a dataset of $N$ subvectors in $\mathbb{R}^{d^*}$. The goal is to find a compact set of centroids that together describe the typical shapes this subvector takes across your data. You then run k-means clustering on this dataset, seeking $K$ centroids $\mathcal{C}_m = \{c_{m,1}, c_{m,2}, \ldots, c_{m,K}\}$ that minimize the total squared distance between each subvector and its nearest centroid, called the quantization error:

where:

• $\mathcal{L}_m$: the quantization loss (total reconstruction error) for subspace $m$
• $N$: the number of training vectors
• $x_i^{(m)}$: the $m$-th subvector of training vector $i$, a point in $\mathbb{R}^{d^*}$
• $c_{m,k}$: the $k$-th centroid in the codebook for subspace $m$
• $\min_{k \in \{1,\ldots,K\}}$: the assignment step, selecting the nearest centroid for each subvector

This is standard k-means, as discussed in the context of IVF coarse quantization in the previous chapter. The difference here is that you run it $M$ separate times, each time on a lower-dimensional subspace, which makes the clustering much faster and more reliable than trying to cluster in the full 768-dimensional space. In high dimensions, k-means is notoriously difficult: the curse of dimensionality makes all points appear roughly equidistant from one another, and finding meaningful cluster boundaries becomes unreliable. By restricting each k-means run to $d^*$ dimensions, PQ turns a hard high-dimensional clustering problem into $M$ tractable low-dimensional ones. This is one of the most practically important aspects of the design: the decomposition is a compression trick and a strategy for making the learning problem statistically well-posed.

The k-means algorithm iterates between two steps: (1) assign each training subvector to the nearest centroid, and (2) update each centroid to the mean of all subvectors assigned to it. These two steps alternate until the centroid positions converge. The loss $\mathcal{L}_m$ is guaranteed to decrease or stay the same on every iteration, so the algorithm always terminates. However, k-means can converge to local optima, so it is common to run it multiple times with different random initializations and keep the result with the lowest total loss. In practice, one good initialization strategy is k-means++, which places the initial centroids far from one another to improve convergence speed and quality.

After training, the codebooks $\{\mathcal{C}_1, \mathcal{C}_2, \ldots, \mathcal{C}_M\}$ are fixed. They are the only data structure you need to store alongside the compressed codes. At search time, you do not need to keep the original training vectors in memory at all. The codebooks, which total only $M \times K \times d^*$ floating-point values, are loaded once and held in cache throughout the search session. For typical parameters, this is on the order of a few megabytes, an entirely negligible overhead compared to the index itself.

Once the codebooks are trained, encoding a database vector $x$ is straightforward. The process visits each subspace in order, extracts the corresponding slice of the vector, and finds the nearest centroid in that subspace's codebook. Split $x$ into $M$ subvectors, then for each subspace find the nearest centroid:

where:

• $k_m$: the centroid index assigned to the $m$-th subvector, i.e., the value stored in the compressed code
• $x^{(m)}$: the $m$-th subvector of database vector $x$
• $c_{m,k}$: the $k$-th centroid in the codebook for subspace $m$
• $\underset{k}{\operatorname{argmin}}$: the operator that returns the index $k$ minimizing the squared distance, selecting the nearest centroid to subvector $x^{(m)}$

The encoded vector is the tuple $(k_1, k_2, \ldots, k_M)$, storing $M$ integers each in the range $[0, K-1]$. With $K = 256$, each fits in one byte (uint8). The intuition is that instead of storing a full floating-point subvector, you store only the address of the nearest representative in a shared codebook. This is a drastic reduction from $d^* \times 4$ bytes down to 1 byte per subspace.

This encoding step only happens once at index build time. After encoding, the original floating-point vectors can be discarded entirely if memory is the primary concern, and only the compact integer codes and the codebook centroids need to be retained. At query time, every distance computation will refer exclusively to these codes and the precomputed lookup tables derived from the codebooks. The encoding process scales linearly with the number of database vectors: encoding 100 million vectors requires 100 million independent nearest-centroid lookups across all subspaces, and these can be parallelized trivially since each vector is encoded independently of all others.

The time complexity of encoding a single vector is $O(M \cdot K \cdot d^*)$: for each of the $M$ subspaces, you compute the distance from the subvector to each of the $K$ centroids and select the minimum. With $d^* = d/M$, this simplifies to $O(K \cdot d)$, which is the same order as a single full-precision distance computation multiplied by $K$. In practice, the encoding is fast enough that it is never the bottleneck in an indexing pipeline; the bottleneck is almost always generating the embeddings themselves.

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:

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:

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:

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.

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:

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.

FAISS, Meta's library for efficient similarity search, provides production-grade PQ implementations. Let us build a complete example that compresses a collection of embeddings and measures both memory savings and recall quality.

FAISS handles all the details of codebook training, vector encoding, and ADC internally. You interact with it through a clean index API that is nearly identical to the exact search API, which means you can swap PQ into an existing pipeline with minimal code changes. The main decisions you need to make are the number of subspaces $M$ and the number of bits per code, which together determine the compression ratio and the expected recall.

First, install FAISS if needed:

We generate clustered data rather than uniform noise because real embedding distributions are highly non-uniform. Embeddings cluster around semantic concepts, and k-means will find better codebooks when the training data matches this structure. Using uniform random vectors would give artificially optimistic recall results because the centroids would be evenly spread across a space with no real geometric structure, making quantization trivially good.

Before compressing anything, establish ground truth nearest neighbors using an exact flat index:

The compression ratio shows how dramatically PQ reduces memory usage compared to storing full float32 vectors. A higher ratio means more vectors fit in the same amount of RAM, enabling larger indexes on a single machine.

Compression always trades some accuracy for space. Let us measure how much recall the PQ index loses compared to exact search:

As we covered in the previous chapter on IVF indexes, coarse quantization partitions the space into cells so you only search a subset of vectors. Combining IVF with PQ gives you both reduced comparisons and compressed storage. This combination is called IVFPQ and is the most widely deployed configuration in production vector databases.

The two techniques address orthogonal bottlenecks. IVF reduces the number of vectors you compare, while PQ reduces the cost of each comparison. Together they multiply their benefits: if IVF reduces the comparison count by a factor of 50 and PQ reduces the per-comparison cost by a factor of 100, the combined speedup is roughly 5,000x compared to exhaustive full-precision search. That is why IVFPQ is a standard configuration in production vector databases, including Pinecone and Weaviate. Milvus also supports it for large-scale indexes.

The number of subspaces $M$ controls the compression-accuracy trade-off, but the direction depends on what is held fixed. In the sweep below, nbits=8 is fixed. Every additional subspace therefore adds another byte to the stored code. Increasing $M$ gives the product codebook $K^M$ possible reconstructions and usually improves recall, but it also produces a longer code and therefore less compression.

If the total code length is held fixed instead, increasing $M$ requires fewer bits and fewer centroids per subspace. That is a different experiment, and larger $M$ is not automatically better. Always state whether nbits or the total bit budget is fixed when comparing PQ configurations.

Let us sweep several values of $M$ at fixed nbits:

The two plots make the direction explicit. At fixed nbits, increasing $M$ improves the approximation by spending more bits per vector. Higher recall is not free: the scan performs more table lookups and the index stores more bytes. For real 768-dimensional embeddings, configurations such as $M = 48$ or $M = 96$ use 48 or 96 bytes per vector when nbits=8, corresponding to 64x or 32x compression relative to float32.

Understanding PQ's parameters helps you make good configuration decisions. The parameters do not have universal optimal values; the right choices depend on your data, your memory budget, and your latency and recall requirements. A good approach is to start with the commonly recommended defaults, measure recall on a representative query set, and then adjust from there.

The key parameters for Product Quantization with FAISS are:

• M: Number of subspaces (subvector segments). At fixed nbits, more subspaces produce a longer code, less compression, and generally higher recall. For 768-dimensional embeddings, values between 32 and 96 are common starting points, but the choice should be reported together with nbits or the resulting bytes per vector.
• nbits: Number of bits per subcode, which determines the codebook size as $K = 2^{\text{nbits}}$. Using nbits=8 gives 256 centroids per subspace and one byte of storage per subspace. Using nbits=4 halves the storage but reduces the codebook from 256 to 16 centroids, increasing quantization error.
• nlist: Number of IVF coarse clusters (Voronoi cells) in IVFPQ. More clusters means finer partitioning and faster search, but requires more training data and longer training time. A common rule of thumb is $\text{nlist} \approx \sqrt{N}$ where $N$ is the number of database vectors.
• nprobe: Number of IVF cells to search at query time. Higher values improve recall at the cost of search speed. The recall vs. nprobe curve (shown in the plots above) lets you choose the operating point that fits your latency budget.
• Training set size: The number of training vectors used to learn the codebooks. At least a few hundred times $K$ per subspace is recommended for reliable k-means convergence. For nbits=8 ($K = 256$), this means at least 50,000 training vectors in practice.

Understanding when PQ works well and when it struggles helps you configure it appropriately. The accuracy of PQ is not a fixed property of the algorithm but a function of how well the learned codebooks match your data distribution, how many subspaces you use, and whether the geometric structure of your embeddings aligns with the product decomposition that PQ assumes.

The fundamental source of error is the quantization step: by replacing each subvector with its nearest centroid, you introduce a residual error that corrupts the distance estimate. Whether this matters for recall depends on how large the residual errors are relative to the distances separating the true nearest neighbors from their non-neighbor competitors. If the true nearest neighbor is much closer to the query than the second-closest vector, PQ can afford substantial quantization error without disrupting the ranking. If many vectors are nearly equidistant from the query, even small quantization errors can flip the ranking and cause true neighbors to be missed.

When we compress a vector using PQ, the stored centroid indices only approximate the original subvectors. The quantization error measures how much information is lost: it is the total squared distance between each original subvector and the centroid used to represent it. Minimizing this error during codebook training (via k-means) directly improves the quality of approximate distance computations at search time. When quantization error is large, the centroids are poor representatives of the data points they are assigned to, and the approximate distances computed by ADC will deviate substantially from the true distances.

For a vector $x$ encoded as code $(k_1, \ldots, k_M)$, the quantization error is:

where:

• $\epsilon(x)$: the total quantization error for vector $x$, measuring how far the compressed representation deviates from the original
• $x^{(m)}$: the original (uncompressed) $m$-th subvector of $x$
• $c_{m, k_m}$: the centroid assigned to represent $x^{(m)}$, i.e., the nearest centroid found during encoding
• $\left\| x^{(m)} - c_{m, k_m} \right\|^2$: the per-subspace reconstruction error for subspace $m$

This reconstruction error is always non-negative. It does not, however, simply get added to every ADC distance. The difference between the approximate and true distances also contains a signed cross-term, derived below, so ADC can either overestimate or underestimate an individual distance. Smaller reconstruction error still tends to make the approximate distances more accurate and improve recall.

To understand how quantization error affects the approximate distance, consider that ADC computes the distance from the full-precision query $q$ to the centroid representing $x$, rather than to $x$ itself. This means the result differs from the true distance by correction terms that depend on the quantization of $x$. Specifically, the approximate distance can be written as:

where:

• $\hat{d}(q, x)$: the approximate distance returned by ADC
• $d(q, x) = \sum_{m=1}^{M} \left\| q^{(m)} - x^{(m)} \right\|^2$: the true squared Euclidean distance between $q$ and $x$
• $\epsilon_q^{\text{corr}} = 2\sum_{m=1}^{M} \langle q^{(m)} - x^{(m)},\, x^{(m)} - c_{m,k_m} \rangle$: a cross-term arising from the interaction between the true displacement and the quantization error of $x$
• $\epsilon_x^{\text{corr}} = \sum_{m=1}^{M} \left\| x^{(m)} - c_{m,k_m} \right\|^2$: the quantization error of database vector $x$, i.e., the total squared distance between $x$ and its assigned centroids

The algebraic expansion above is more than a curiosity. It shows precisely which quantities control the quality of the approximation. The term $d(q, x)$ is the true distance, which is what we want. The non-negative term $\epsilon_x^{\text{corr}}$ depends only on how well $x$ is quantized, while the signed cross-term $\epsilon_q^{\text{corr}}$ also depends on the query and can reinforce or offset it. ADC therefore has no universal overestimation guarantee for individual query-vector pairs. When the cross-term is small in expectation, lower reconstruction error makes the approximate distances more stable and reduces ranking mistakes among nearby candidates.

Several factors degrade PQ recall. Understanding these failure modes helps you diagnose poor performance and choose the right remediation:

• Too few code bits: At fixed nbits, a small $M$ gives each vector a short code. A 128-dimensional vector with $M=2$ and nbits=8, for example, receives only 16 total bits, so each 64-dimensional subvector must be represented by one of just 256 centroids. Increasing $M$ lowers this distortion by spending more bits per vector.
• Insufficient training data: K-means needs at least $K \times$ a few hundred training points per subspace to converge well. With $K = 256$ and $M = 8$, you need on the order of 200,000 training vectors minimum. With fewer, some centroids will be initialized in empty regions and never attract any training points, leaving voids in the codebook coverage.
• Non-uniform distributions: If your embeddings have strong correlations between dimensions that span subspace boundaries, independent per-subspace quantization misses that structure. Optimized PQ (OPQ) applies a rotation to the embedding space before quantization to reduce such correlations, at the cost of a rotation step at query time.
• Mismatched preprocessing or metric: Cosine search requires consistent normalization of training, database, and query vectors. For unit-normalized vectors, exact cosine and squared-Euclidean rankings agree; without that normalization, changing metrics changes the neighbor ordering that the index is trying to preserve.

ADC keeps the query in full precision, which is why it outperforms Symmetric Distance Computation (SDC), where both the query and database vectors are quantized before comparison. With SDC, you accumulate quantization error from both sides: the query contributes its own per-subspace reconstruction errors on top of those from the database vector. Looking at the error expansion above, SDC adds an additional cross-term and an additional quantization error term for the query, making the approximation systematically worse.

In practice, ADC is almost always preferred. The only advantage of SDC is that you do not need to keep the codebooks in memory during search, which rarely matters compared to the recall cost. The memory overhead of the codebooks is negligible compared to the index itself: for $M = 96$, $K = 256$, $d^* = 8$, the codebooks occupy only $96 \times 256 \times 8 \times 4 = 786{,}432$ bytes, less than 1 MB. There is virtually never a practical reason to accept the accuracy penalty of SDC when the codebooks are so cheap to store. ADC is always the right choice unless you are operating under severe memory constraints at truly extraordinary scale.

The real power of PQ shows when you scale to billions of vectors. Let us put the numbers in perspective.

Most discussions of PQ focus on the compression ratio, but the more important question is what compression enables that would otherwise be impossible. At a billion vectors, even the question of which machine architecture to use changes depending on whether you can fit the index in RAM. If you cannot, you are forced into a hybrid architecture where part of the index lives on disk or on remote machines, and you pay latency costs for every remote access. If you can, you get sub-millisecond in-process lookups with no network round-trips. PQ is often the technology that decides which side of that divide you fall on.

For a billion-vector index with 768-dimensional float32 embeddings:

• Flat index: $10^9 \times 768 \times 4 = 3.07$ TB. This requires a distributed fleet of machines and terabytes of RAM.
• PQ with M=96, nbits=8: $10^9 \times 96 \times 1 = 96$ GB (96 bytes/vector, since each of the 96 subspaces stores one byte). This fits on a single server with 128 GB RAM.
• PQ with M=48, nbits=8: $10^9 \times 48 \times 1 = 48$ GB (48 bytes/vector). This fits on a workstation.

The difference is not incremental: it is the difference between a system that requires purpose-built infrastructure and one that runs on commodity hardware. A researcher studying billion-scale retrieval can now run experiments on a single rented cloud instance instead of managing a cluster. An engineering team can ship a production retrieval system without a dedicated infrastructure team. PQ makes these deployments feasible.

When combined with IVFPQ, you get the full stack: IVF reduces the number of vectors you compare (by a factor of $\text{nlist} / \text{nprobe}$), and PQ reduces the cost of each comparison. Production systems such as Pinecone and Weaviate use variants of IVFPQ as compressed index formats, as does Milvus. The upcoming chapters on hybrid search and reranking will show how these approximate indexes fit into a larger retrieval pipeline, where you use PQ for first-pass retrieval and then apply a full-precision reranker to the top candidates.

Product Quantization is not a free lunch. Understanding its limitations helps you anticipate where it will work well and where it will require additional engineering to meet accuracy requirements.

The core limitation is the accuracy-compression trade-off: any time you compress, you lose information, and that information loss translates to missed neighbors. For applications where recall below 95% is unacceptable, PQ alone may not suffice, and you will need to pair it with a post-processing reranking step using the original full-precision vectors. This two-stage architecture, retrieve with PQ and then rerank with exact distances, is now standard in production RAG systems. The reranker takes the top candidates from the PQ search (say, the top 100) and re-scores them using the original embeddings, recovering most of the recall loss at a fraction of the full-scan cost. We will cover this in detail in the chapter on reranking.

A second limitation is the static codebook. Once trained, the codebooks are fixed. If your data distribution shifts significantly, for example if you swap out your embedding model or index a new domain, the old codebooks become suboptimal and you need to retrain from scratch. Unlike HNSW graphs, which can be incrementally updated by inserting new nodes without retraining, PQ codebooks reflect a snapshot of your data distribution at training time. For systems that periodically replace their embedding model (which happens every time a better model is released), this means a full index rebuild, including codebook retraining and re-encoding all vectors. The rebuild process is well-parallelized and fast in practice, but it requires planning and downtime management.

Training cost is another consideration often overlooked in benchmarks. Running k-means with $K = 256$ over 50,000 training vectors in each of $M = 96$ subspaces is fast per subspace, but the overall training can take minutes on a CPU for large $M$. This is not prohibitive for most pipelines, but it means you cannot rebuild the index on every data update. Systems that require low-latency index updates (such as real-time document indexing) need to queue updates and batch-rebuild periodically, or maintain a separate uncompressed buffer for recently added vectors that is merged into the main PQ index at regular intervals.

The product structure assumption is a more fundamental limitation. PQ assumes that the dimensions of your embeddings are organized such that the correlations between dimensions mostly fall within subspaces rather than across them. In practice, most embedding models produce representations where correlations do span subspace boundaries. Optimized PQ (OPQ) addresses this by learning a rotation matrix that redistributes the variance so that more of the structure can be represented within the chosen subspaces. This improves recall at a given compression ratio, but adds the cost of applying the rotation at both encoding and query time. It is especially useful when the original dimension ordering splits strongly correlated features across subspace boundaries.

Finally, PQ distance estimates are always approximate. The error is bounded by the quantization quality, which depends on the total bit budget, the number of training samples, the intrinsic dimensionality of your data, and how well the data distribution matches the product structure assumed by independent per-subspace quantization. Datasets where nearby vectors share strong cross-subspace correlations tend to see lower recall for a given compression ratio. The heatmap in the previous section gives you a way to measure this: if you see high quantization error at fixed $K$, consider increasing $M$, increasing $K$, or applying OPQ. If the total code length must remain fixed, tune $M$ and nbits together rather than treating either parameter in isolation.

Despite these limitations, PQ remains one of the most practical tools in the retrieval engineer's toolkit. No other technique achieves comparable compression ratios with comparable retrieval quality. It reduces a previously intractable problem, fitting billions of high-dimensional vectors in RAM, to a manageable one by recognizing that distances decompose across subspaces. Every major production vector database in use today relies on some form of PQ or a closely related technique, and the original 2011 paper's core design choices remain essentially unchanged in modern implementations.

Product Quantization compresses high-dimensional vectors into compact codes by splitting each vector into $M$ subvectors and replacing each with the index of its nearest centroid in a learned codebook:

• Codebook learning runs k-means independently in each of the $M$ subspaces on a sample of your training data. Each subspace gets $K$ centroids (typically $K = 256$ for one-byte codes). The codebooks must match your data distribution; mismatched codebooks inflate quantization error and reduce recall.
• Encoding replaces each subvector with its centroid index, compressing a float32 vector of $d$ dimensions (which requires $d \times 4$ bytes) to $M$ bytes (one byte per subspace when nbits=8), giving a compression ratio of $4d/M$. Encoding happens once at index build time and the result is stored as compact integer codes.
• Asymmetric Distance Computation precomputes a lookup table of distances from the query to all centroids in each subspace, then reduces each database comparison to $M$ table lookups and additions. The lookup tables fit in CPU cache, making ADC limited by memory bandwidth rather than arithmetic throughput.
• The recall-compression trade-off is governed by the total code length $M \cdot \text{nbits}$. At fixed nbits, more subspaces mean more bytes, less compression, lower reconstruction error, and generally higher recall. For 768-dimensional embeddings with nbits=8, $M = 48$ and $M = 96$ correspond to 48-byte and 96-byte codes respectively.
• IVFPQ combines coarse partitioning (IVF) with compression (PQ), achieving both fewer comparisons and smaller memory footprint. This is the dominant configuration in production vector search systems, used by Pinecone, Weaviate, Milvus, and the FAISS library.
• At scale, PQ is what makes billion-vector indexes feasible on a single server, transforming a distributed-computing problem into one that runs on commodity hardware. The practical difference between a 3 TB flat index and a 48 GB PQ index is the difference between a cluster deployment and a single machine.

Ready to test your understanding? Take this quick quiz to reinforce what you've learned about Product Quantization.