Product quantization, explained

Product quantization, usually shortened to PQ, is a method for compressing a dense vector into a code of a few bytes in a way that still lets a search engine estimate distances to it. Herve Jegou, Matthijs Douze and Cordelia Schmid introduced it for nearest-neighbor search in Product quantization for nearest neighbor search, published in IEEE Transactions on Pattern Analysis and Machine Intelligence; the public preprint carries a 2010 IEEE copyright notice. The idea is to split a vector into pieces, quantize each piece separately with a small codebook, and store only the codebook indexes. A 768-dimensional float32 embedding that takes 3,072 bytes uncompressed can be stored in 8 or 16 bytes, which is what makes a corpus of a hundred million passages fit in the memory of one machine. The price is that distances are now estimates, and the rest of this post is about how the estimate is computed and how much it costs in recall.

Subvectors and codebooks

A vector quantizer maps a D-dimensional vector to the nearest of k centroids and stores the centroid's index. The paper's Section II explains why that does not scale to short codes: a 64-bit code implies k equal to 2 to the 64 centroids, which cannot be learned, stored or searched. Product quantization gets the same code length from small codebooks. The input vector x is split into m distinct subvectors u1 through um, each of dimension D-star equal to D over m. Each subvector is quantized separately by its own subquantizer qj with a codebook Cj of k-star centroids. The code for x is the list of m indexes, one per subquantizer. The implied overall codebook is the Cartesian product C1 times C2 times ... times Cm, with k equal to k-star to the power m entries, which is where the name comes from.

The code length is m times log2 of k-star bits. The paper states that k-star of 256 and m of 8 "is often a reasonable choice", which gives 8 subquantizers of 8 bits each, a 64-bit code. Each subquantizer is a Lloyd quantizer learned with k-means on the training subvectors, so the paper gives the learning cost as m times the cost of k-means clustering with k-star centroids on D-star dimensional data, and the storage for the codebooks as m times k-star times D-star floats, the same as k-star times D. Both are small: for D of 128, m of 8 and k-star of 256 the codebooks hold 32,768 floats.

The paper's Figure 1 and Section V.B show how m and k-star trade off at a fixed number of bits. For a fixed number of bits the paper finds it better to use a small number of subquantizers with many centroids than many subquantizers with few bits, though Section V.B adds that mean squared error underestimates the search quality obtained with a large number of subquantizers. The limit on k-star is cost: high values raise the computational cost of the quantizer and the memory for the centroids, and efficiency drops further once the centroid lookup table no longer fits in cache.

How the dimensions are grouped into subvectors matters. Table IV of the paper measures recall@100 for ADC with k-star of 256 and three groupings. On SIFT with m of 8, the natural order of consecutive dimensions scored 0.921 and a random order 0.859. On GIST with m of 8, natural order scored 0.338, random 0.286, and a structured grouping that put related histogram bins together scored 0.652. The authors note that a method to group components automatically "could further improve the results", which is the gap OPQ later filled.

Bytes per vector

The Faiss index table gives the per-vector storage for the PQ family. IndexPQ, built by the factory string PQM or PQMxnbits, stores ceil of M times nbits over 8 bytes per vector. IndexIVFPQ stores the same code plus 8 bytes for the vector's id. IndexIVFPQR, which keeps a second PQ code to refine the first, stores M plus M-refine plus 8 bytes. The Faiss library paper by Douze and colleagues writes the code size as M times ceil of log2 K bits and uses the notation PQ6x10 for 6 sub-vectors of 10 bits each.

The Faiss wiki's Lower memory footprint page walks through the common case: IndexIVFPQ reduces each vector to a configurable number of bytes m, the dimension d must be a multiple of m, and its example compresses 64 32-bit floats to 8 bytes, "so the compression factor is 32". The guidelines say M is typically 64 or less, because for longer codes a scalar quantizer is usually as accurate and faster, and that the 4-bit variant written PQMx4fsr stores M over 2 bytes per vector.

Those figures are the whole reason to use PQ. The guidelines open their memory section with "Keep in mind that all Faiss indexes are stored in RAM". For 100 million 768-dimensional vectors, flat storage is 307 GB, PQ64 is 6.4 GB, and PQ16 is 1.6 GB plus ids.

Asymmetric distance computation

Compressing the vectors would be useless if every distance required decompressing them. The paper's Section III gives two ways to estimate the Euclidean distance between a query x and a database vector y from codes, illustrated in its Figure 2.

Symmetric distance computation, SDC, encodes the query too and approximates d(x, y) by the distance between the two codes, d(q(x), q(y)). That distance decomposes over the subquantizers, and each term is read from a table of the squared distances between every pair of centroids of the j-th subquantizer. Asymmetric distance computation, ADC, leaves the query uncompressed and approximates d(x, y) by d(x, q(y)). Before scanning the database, the search computes the squared distance from each query subvector uj(x) to every centroid cj,i of subquantizer j, a table of m by k-star entries. Each database distance is then the sum of m table lookups, one per subquantizer, indexed by the database vector's code. No square roots are taken, since ranking by squared distance gives the same order.

The paper's Table II shows the two have the same query preparation cost and the same n times m scanning cost. The difference is accuracy. Section III.B bounds the mean squared distance error of ADC by the mean squared error of the quantizer, and that of SDC by twice the quantizer's error. The experiments agree: with m of 8, ADC with k-star of 64 matched SDC with k-star of 256. The authors conclude that "the only advantage of SDC over ADC is to limit the memory usage associated with the queries" and advocate not quantizing the query when possible. The Faiss paper states the same policy: most Faiss indexes perform ADC because it is more accurate, with no accuracy lost on the query side.

IVFPQ in FAISS

Exhaustive ADC still visits every code. The paper's Section IV combines PQ with an inverted file, calling the result IVFADC, for inverted file with asymmetric distance computation. A coarse quantizer qc with k-prime centroids, also learned by k-means, assigns each database vector y to one inverted list. The product quantizer then encodes not y itself but the residual r(y) equal to y minus qc(y), because the residual has less energy than the raw vector and quantizes more precisely. Each list entry holds a vector identifier and the residual's code. At query time the query is assigned to its w nearest coarse centroids, the query's residual against each is computed, and only the entries of those w lists are scanned with ADC. The fraction of the database visited is roughly w over k-prime.

This is exactly the structure Faiss calls IndexIVFPQ. The Lower memory footprint page builds it as IndexIVFPQ(quantizer, d, nlist, m, 8), with nlist the number of coarse lists, m the number of subquantizers, and 8 the bits per sub-vector, or through the factory string IVF100,PQ8. The Faiss paper describes the two-level PQ encoding, "a first-level coarse quantizer and a second level refinement of the residual", as what an IVFPQ index uses. Faiss's name for w is nprobe, and the guidelines give the sizing rules: K between 4 and 16 times the square root of the dataset size, and 30 to 256 times K vectors for training.

The paper's Table V, on the 960-dimensional GIST set of 1,000,991 vectors with 64-bit codes, m of 8 and k-star of 256, shows what the inverted file buys. Exhaustive SDC took 16.8 milliseconds per query at recall@100 of 0.446 and exhaustive ADC 17.2 milliseconds at 0.652. IVFADC with k-prime of 1,024 and w of 8 took 8.8 milliseconds at 0.682, scanning 27,818 codes instead of a million; with w of 64 it took 65.9 milliseconds at 0.744. Spectral hashing on the same machine took 22.7 milliseconds at 0.132. The paper's Figure 7 also shows the failure mode: raising the code length is useless if w is too small, because a true neighbor that fell in an unvisited list is lost no matter how precise the code.

In its comparison with FLANN on the SIFT set, the paper reports that the IVFADC indexing structure occupied less than 25 MB where FLANN required more than 250 MB of RAM, and notes that both are negligible next to the memory the vectors occupy on large datasets. The paper then runs a scale test on about 2 billion SIFT descriptors extracted from one million images, searched with 30,000 query descriptors. The GPU implementation that became Faiss followed the same design; Johnson, Douze and Jegou's 2017 paper Billion-scale similarity search with GPUs describes optimized brute-force, approximate and compressed-domain search based on product quantization and a graph connecting 1 billion vectors built in under 12 hours on 4 Maxwell Titan X GPUs.

OPQ, briefly

The Jegou, Douze and Schmid paper showed that the grouping of dimensions into subvectors changes recall substantially. Tiezheng Ge, Kaiming He, Qifa Ke and Jian Sun turned that observation into an optimization in Optimized Product Quantization for Approximate Nearest Neighbor Search at CVPR 2013, with a publication page at Microsoft Research. The abstract states the gap: optimal space decomposition "is important for the performance of ANN search, but still remains unaddressed". OPQ multiplies the data by an orthonormal matrix R before splitting, and minimizes quantization distortion jointly over R and the codebooks.

The paper gives two solvers. The non-parametric one alternates between fixing the codebooks and solving for R, then fixing R and running k-means for the codebooks. The parametric one assumes the data is Gaussian, aligns it with PCA, and uses an eigenvalue allocation step that distributes the principal components across subspaces so that each subspace carries a balanced share of variance; the paper proves this reaches the distortion lower bound under the Gaussian assumption. Against baselines of PQ with randomly ordered dimensions, PQ after PCA and a random rotation, transform coding and iterative quantization, on SIFT1M, GIST1M and MNIST, the paper reports that both solutions outperform the original PQ and the alternatives, and that the non-parametric solver further improves on the parametric one on SIFT1M and MNIST. The authors also found PQ with a random rotation disappointing, because the rotation destroys the independence between subspaces that PQ relies on.

In Faiss, OPQ is a vector transform applied before the PQ index. The guidelines describe OPQ as "a linear transformation of the vectors to make them easier to compress", written as a prefix such as OPQM_D, where the output dimension D must be a multiple of M and should preferably be at most d and 4 times M. The Faiss paper calls it a rotation that decorrelates the distribution of each sub-vector. The guidelines' recipes for when memory is quite important or very important both begin with that prefix.

The recall cost

Every PQ distance is an estimate, so a PQ index returns some wrong neighbors even when it scans every code. The Lower memory footprint page shows this with a toy search: the distances returned are approximations, the nearest neighbor of a database vector is still found correctly, but its estimated distance to itself is not 0, and for the example's queries on uniform random data "most results are wrong, but they are in the correct area of the space". The page adds that the situation is better for real data, because uniform data is very difficult to index and for natural data the semantic nearest neighbor is often much closer than the irrelevant results.

The paper's recall@R measure is the right lens. Recall@R is the proportion of queries for which the true nearest neighbor is ranked within the first R estimated results. A system that takes the top R codes and then re-ranks them with exact distances recovers the true neighbor exactly when recall@R is 1. The paper's Figure 6 plots recall@100 against code length for SIFT: at 64 bits exhaustive ADC sits well above SDC, and recall climbs with more bits. The cost is therefore a function of bytes spent, of whether the query is kept uncompressed, and of how many lists are probed.

Two Faiss mechanisms lower the cost. The first is re-ranking, which the wiki's Pre- and post-processing page implements as IndexRefineFlat: it fetches k_factor times k candidates from the PQ index, 4 times 10 in the page's example, recomputes their real distances and keeps the best 10. The page warns that IndexRefineFlat "has to store the full vectors, so it is not memory-efficient". IndexIVFPQR instead refines with a second, longer PQ code. The second mechanism is FastScan, which the wiki's FastScan page describes as keeping the ADC lookup tables in CPU vector registers and reading them with SIMD shuffle instructions. The tables must be short, so sub-quantizers drop to 4 bits with 16 centroids each, table entries are quantized to 8 bits, and codes are packed in batches of 32. The page reports that with re-ranking the 4-bit PQ reached 280,000 queries per second at 1-recall@1 of 0.9, about twice HNSW's 140,000, while using 2.7 times less memory, and up to 1 million queries per second without re-ranking.

When to use it

The Faiss library paper gives the decision rule. Graph indexes are a good option where there is no constraint on memory, typically below 1 million vectors; beyond 10 million, graph construction time becomes the limit; and for larger indexes, "where compression is required to even fit the database vectors in memory, IVF indexes are the only option". PQ is the compression those IVF indexes use. The guidelines' recipes for when memory is quite or very important are OPQ followed by IVF and a PQ code, with the 4-bit fast-scan variant that encodes the residual, PQMx4fsr, when memory is quite important and the 8-bit code when it is very important.

Below that scale, PQ costs recall for no reason. A flat index is exact, and an HNSW graph over full vectors loses nothing to quantization; the companion post on vector search and Faiss covers those index types. PQ also needs training data drawn from the same distribution as the corpus, both for the coarse quantizer and for the codebooks, and the original paper's grouping results and OPQ's whole premise show that the codebooks are specific to the data they were trained on. A PQ index trained on one embedding model's output is not reusable for another's.

When PQ is the right tool, the parameters to record are the transform, the number of coarse lists, the number of subquantizers and bits, nprobe, and whether and how results are re-ranked. A recall figure for a PQ index means nothing without them.

What to check

• How many bytes per vector does the index store, and does the figure include the 8-byte id per IVFPQ entry and any refinement code?
• Is the query compressed or kept in full? Symmetric distance computation is cheaper on query memory and worse on accuracy.
• What recall@R against exact search was measured, at which R and nprobe, and on which embedding model's vectors?
• Were the coarse quantizer and the PQ codebooks trained on a sample from this corpus, with the 30 to 256 training vectors per cluster the Faiss guidelines ask for?
• Is there a re-ranking stage, and if it uses IndexRefineFlat, is the memory for full vectors budgeted?
• Was an OPQ transform applied, and was recall compared with and without it on this data?

Azcuna's TRACE is one offline viewer for S1000D, MIL-STD-3001 XML, and PDF technical manuals. It keeps the source location and the markings of everything it shows and never modifies the source. It was proposed to NAVAIR under Navy SBIR Phase I topic DON26BZ05-NV078, and the proposal was submitted on September 23, 2026.

Questions people ask

What is product quantization?

Product quantization is a way to compress a high-dimensional vector into a short code. The paper by Jegou, Douze and Schmid splits a D-dimensional vector into m subvectors of D over m dimensions, quantizes each subvector separately with a codebook of k-star centroids learned by k-means, and stores the m centroid indexes. The implied codebook is the Cartesian product of the m small ones, with k-star to the power m entries, which is why the method is called product quantization.

How many bytes per vector does PQ use?

The code length is m times log2 of k-star bits, per the Jegou, Douze and Schmid paper. The paper says k-star of 256 and m of 8 is often a reasonable choice, which gives 64 bits, or 8 bytes, per vector. The Faiss index table gives IndexPQ as ceil of M times nbits over 8 bytes per vector and IndexIVFPQ as the same plus 8 bytes for the id. A 768-dimensional float32 vector takes 3,072 bytes uncompressed, so an 8-byte code is a 384 to 1 compression.

What is asymmetric distance computation?

Asymmetric distance computation, or ADC, compares an uncompressed query against compressed database codes. The Jegou, Douze and Schmid paper computes, before scanning, the squared distance from each query subvector to every centroid of the matching subquantizer, a table of m by k-star entries, and then estimates each database distance as the sum of m table lookups. The paper shows the resulting error is statistically bounded by the quantizer's mean squared error, against twice that for the symmetric version.

What is IVFPQ in FAISS?

IVFPQ is an inverted file index whose entries are product-quantized codes. The Faiss Lower memory footprint page describes IndexIVFPQ as reducing each vector to a configurable number of bytes m, built as IndexIVFPQ(quantizer, d, nlist, m, 8) with 8 bits per sub-vector. The construction is the IVFADC system of the Jegou, Douze and Schmid paper: a coarse k-means quantizer assigns each vector to a list, and the product quantizer encodes the residual between the vector and its coarse centroid. Queries visit nprobe lists.

What is OPQ?

Optimized Product Quantization, from Ge, He, Ke and Sun at CVPR 2013, rotates the vector space before splitting it so that the subvectors carry balanced, decorrelated information. The paper optimizes quantization distortion with respect to the space decomposition, an orthonormal matrix, and the codebooks, offering a non-parametric alternating solver and a parametric one that is optimal under a Gaussian assumption. The Faiss guidelines describe OPQ as a linear transformation that makes vectors easier to compress, used as a prefix like OPQ16_64,IVF...,PQ16.

How much recall does product quantization lose?

The cost depends on the bytes spent. In the Jegou, Douze and Schmid paper's GIST experiment with 64-bit codes, exhaustive ADC reached recall@100 of 0.652, where recall@100 is the share of queries whose true nearest neighbor appears in the top 100 estimated. More subvectors or more centroids raise it: the paper's Figure 6 shows recall@100 against code length on SIFT. The Faiss Lower memory footprint page notes that compressed distances are approximations and that a vector's estimated distance to itself is not 0.

Does product quantization need training?

Yes. The codebooks are learned with k-means on a training set, and the Jegou, Douze and Schmid paper says learning costs m times the k-means clustering of k-star centroids on D over m dimensional vectors. For IVFPQ the coarse quantizer is trained too, and the Faiss guidelines say an IVF index with K clusters needs between 30 times K and 256 times K training vectors. Training vectors should come from the same distribution as the data to be indexed.

When should you use product quantization?

When the uncompressed vectors do not fit in memory. The Faiss guidelines open their memory section by saying all Faiss indexes are stored in RAM, and the Faiss library paper says that for indexes where compression is required to fit the database vectors in memory, IVF indexes are the only option. Below that scale, the same paper recommends a graph index such as HNSW, which stores full vectors and does not lose accuracy to quantization. Re-ranking a PQ shortlist with full vectors recovers some of the loss.

What is PQ fast scan in FAISS?

The Faiss FastScan page describes a variant that keeps the ADC lookup tables in CPU vector registers instead of memory, using SIMD shuffle instructions. The tables must be short, so it uses 4-bit sub-quantizers with 16 entries each, quantized to 8 bits, and packs codes in batches of 32. The index classes are IndexPQFastScan and IndexIVFPQFastScan, written in factory strings with the suffix fs, as in PQ32x4fs. The page credits the method to a 2015 VLDB paper by Andre and colleagues.

Sources

1. 1Product quantization for nearest neighbor search · IRISA (Jegou, Douze and Schmid, IEEE TPAMI preprint)
2. 2Optimized Product Quantization for Approximate Nearest Neighbor Search · CVF Open Access (Ge, He, Ke and Sun, CVPR 2013)
3. 3Optimized Product Quantization for Approximate Nearest Neighbor Search · Microsoft Research
4. 4Guidelines to choose an index · Faiss wiki
5. 5Faiss indexes · Faiss wiki
6. 6Lower memory footprint · Faiss wiki
7. 7Fast accumulation of PQ and AQ codes (FastScan) · Faiss wiki
8. 8Pre- and post-processing · Faiss wiki
9. 9The Faiss library · arXiv (Douze et al.)
10. 10Billion-scale similarity search with GPUs · arXiv (Johnson, Douze and Jegou)

Where this shows up in our work

• TRACE, the offline S1000D and IETM viewer opens S1000D, MIL-STD-3001 and PDF technical manuals on a tablet with every marking intact.
• BABEL, offline multilingual translation and search translates and searches foreign-language documents on-device, every fact tied to its source passage.