IVF and product quantisation: the original method

About this article: AI-assisted writing, reviewed against the cited sources. This is source research, not a lab validation of the procedures. Check the stated versions and your own recovery requirements before making changes.

Product quantisation stores a vector as a handful of bytes by chopping it into subvectors and replacing each subvector with the id of a centroid. An inverted file, in the same paper's non-exhaustive method, first picks a coarse cell so you do not compare the query with every code. The distance you get back is an estimate. Recall is how often the true neighbour is still in the shortlist.

An AI writing system produced this article for NetLeverage's editorial studio. A "close" code means a small estimated Euclidean distance in this method. It is not a claim about meaning, and it is not a self-report.

Nothing was indexed for this article. Figures below are the definitions and the operating points in Jégou, Douze and Schmid, IEEE TPAMI 2011 (HAL inria-00514462v2, opened 10 November 2026). Their tables are SIFT and GIST, not a modern text-embedding benchmark.

Why it matters

As an illustrative storage assumption, a full vector of 128 float32 values is 512 bytes. Their common product code is 64 bits, 8 bytes, for the choice $m=8$, $k^{\backslash }*=256$. That is the compression that makes a billion descriptors fit. The cost is that the distance is no longer exact, and an exhaustive pass over every code is still a pass over every code. The inverted file is how they stop doing that pass. If you skip it, you have compressed the memory and kept the scan. If you visit too few coarse cells, you have a fast scan of the wrong lists, and the true neighbour was never decoded.

The code

The space has dimension $D$. Split the vector into $m$ subvectors, in the paper's setup of equal length, so $D$ has to be divisible by $m$. Each subspace gets its own quantizer $q_j$ with $k^{\backslash }*$ centroids, learned by k-means (Lloyd). A stored vector is the tuple of $m$ centroid ids.

The product of those small codebooks is a huge codebook. If every subspace has $k^{\backslash }*$ centroids, the number of representable concatenated centroids is $(k^{\backslash }*{)}^m$. For $k^{\backslash }*=256$ and $m=8$ that is ${256}^8$, which you never store. You store eight lists of 256 centroids, and an 8-byte code per vector. The paper says $k^{\backslash }*=256$ and $m=8$ is often a reasonable choice. The code length, when $k^{\backslash }*$ is a power of two, is $m{\log }_2{k}^{\backslash }*$ bits. That choice is 64 bits. They also note that $m=1$ with a large $k^{\backslash }*$ brings back a single big codebook, and that a sufficiently large centroid table may no longer fit in cache; they would not spend more than 16 bits in that extreme.

Learning costs $m$ small k-means runs, not one k-means over $(k^{\backslash }*{)}^m$ centres. The paper's point is that the small codebooks are still fit to the data, while the Cartesian product supplies the large set of reconstructions.

For a fixed bit budget, their distortion curves prefer fewer subspaces with more centroids over many subspaces with few bits. The same section says mean squared error underestimates search quality when you instead use more subspaces. Both sentences are theirs. Do not collapse them into "always use m = 8". Read recall at the bit budget you can afford, on your vectors.

Symmetric and asymmetric distance

Nearest neighbour needs distances from the query $x$ to each database vector $y$. The paper estimates Euclidean distance from the codes, in two ways.

Symmetric (SDC). Both sides are replaced by their centroids. The distance is the distance between $q(x)$ and $q(y)$, and because the quantizer is a product it splits into a sum of per-subspace centroid distances. Those are read from a table. Each subspace table holds the squared distances between its centroids: $(k^{\backslash }*{)}^2$ entries, or exactly $k^{*}(k^{*}-1)/2$ entries if you store one triangle and omit the zero diagonal. The query must be encoded before any lookup. Quantising the query adds a second error.

Asymmetric (ADC). The database vector is a code. The query stays a full vector. The estimate is the distance from $x$ to the reconstruction $q(y)$, again a sum over subspaces, now from each query subvector to the stored centroid. The paper's bound: the mean squared error on the distance is on average bounded by the quantisation error. ADC avoids quantising $x$, so that error is smaller. On their SIFT curves, ADC beats SDC clearly. At $m=8$ they get the same accuracy from ADC with $k^{\backslash }*=64$ as from SDC with $k^{\backslash }*=256$. They say the two have equivalent efficiency and they advocate not quantising the query when you can avoid it. Encode the database. Leave the query raw.

Exhaustive ADC is cheap per vector and still touches every vector. The paper says only $m$ additions are required per distance once the subspace terms are available. Cheap times a billion is not cheap. That is why the inverted file exists.

The inverted file

Section IV combines a coarse quantizer with ADC, which they call IVFADC. A k-means codebook $q_c$ with $k^{\prime }$ centroids assigns each database vector to a list. For SIFT they say $k^{\prime }$ typically runs from 1,000 to 1,000,000, small next to the product codebook. The list stores, not only an id, but a product code of the residual

The residual has less energy than $y$, so a product quantizer trained on residuals spends its bits on a smaller vector. The paper uses one such quantizer across cells, rather than separate residual quantizers per cell. They describe the coarse id as the most significant bits and the product code as the least significant bits. The reconstruction is the coarse centroid plus the product reconstruction of the residual. The estimated distance from a query is the distance between $x-q_c(y)$ and that residual code.

At query time you do not scan every list. You find the query's nearest coarse centroids and visit $w$ of those cells. The paper's IVFADC plots use codebook sizes such as $k^{\prime }\in \{1024,8192\}$ and $w\in \{1,8,64\}$. $w=1$ is the single nearest cell. A neighbour that the coarse quantizer put in the next cell is invisible until $w$ includes it. Raising $w$ raises the chance the true neighbour's list is opened, and it raises the number of product codes you score. That is the same shape of trade as a longer candidate list in a graph index: recall against work, on a structure you built earlier.

The identifier stored beside the code is overhead. The paper says the inverted file adds a few bits or bytes per descriptor and, on their data, slightly improves accuracy because the residual is easier to encode than the original vector. The accuracy gain and the pruning are different effects. You can get the residual gain and still visit every list. You only get the speed when $w$ is a small fraction of $k^{\prime }$.

What the numbers mean, and what they do not

Their quality plots use recall at a shortlist, including recall@100, on SIFT and GIST image descriptors. A point on those curves is "the true Euclidean neighbour appeared in the top 100 estimated distances", not "a language query was answered". Copying $m=8$, $k^{\backslash }*=256$, $k^{\prime }=1024$, $w=8$ onto text embeddings because a 2011 figure looked smooth is how a corpus gets a fast index and a quiet recall failure.

The distance in the paper is Euclidean. On vectors that have already been scaled to unit length, the squared Euclidean distance and the cosine are linked by $\Vert x-y{\Vert }^2=2-2⟨x,y⟩$, so the ranking matches. On vectors that have not, a Euclidean product code is not a cosine code. Normalise first, and use the same normalisation the coarse quantizer and the subspaces saw at training time, or accept that you changed the geometry the codebooks were fit to.

Training the codebooks on a sample and encoding a later distribution that has drifted is a second silent failure. The paper learns on a separate learning set drawn from the same kind of data, rather than the database vectors it encodes. A codebook fit to one embedding model is not a property of the index software. Rebuild it when the vectors change.

The original paper also shows that pruning can cost more than scanning. On one million GIST vectors with 64-bit codes, Table V reports exhaustive ADC at 17.2 ms and recall@100 of 0.652. IVFADC with 1,024 coarse cells took 1.5 ms at w=1 (0.308 recall), 8.8 ms at w=8 (0.682), and 65.9 ms at w=64 (0.744). Higher recall did not mean higher speed. Table IV reports GIST recall@100 of 0.286 with random component ordering, 0.338 with natural ordering and 0.652 with structured grouping. Subspace composition matters as well as bit count. These are historical image-descriptor results, not text-retrieval measurements; OPQ and current library settings are outside this article.

What to choose and why

Our recommendation, not a line in the paper: measure recall@R on a sample with known Euclidean neighbours, sweep $w$, and only then freeze $m$ and $k^{\backslash }*$. A faster index that misses the neighbour is a different system from the one you timed.

The safe order

1. Fix the distance. If the application wants cosine, L2-normalise before you train $q_c$ and the subspace codebooks, and keep that as part of the index definition. The paper's estimator is Euclidean.

2. Train on a representative learning sample. For IVFADC, train the product quantizer on residuals. $m$ subspace k-means runs, equal subvector width, $D$ divisible by $m$. Record $m$, $k^{\backslash }*$ and the training sample. The code length is $m{\log }_2{k}^{\backslash }*$ bits when $k^{\backslash }*$ is a power of two.

3. Decide exhaustive or inverted. Exhaustive ADC scores every code. IVFADC scores the codes in $w$ coarse cells, and the code is of the residual. If recall collapses when $w=1$ and recovers when $w$ grows, the coarse quantizer is splitting true neighbours across cells. That is a $w$ problem or a $k^{\prime }$ problem, not a reason to abandon the product code first.

4. Compare ADC with SDC only if you truly cannot keep the query raw. Their result says ADC is the one to keep. Encoding the query as well should be a constraint you can name, such as a constraint on query memory. The paper identifies limiting query memory as SDC's advantage but says it is usually not relevant.

5. Budget memory as codes plus codebooks plus list ids. Eight bytes per vector is the 64-bit code, not the centroids and not the inverted-list overhead. The centroids are $m\times k^{\backslash }*$ subvectors. The warning concerns a very large flat codebook: for m=1 the authors would not exceed 16 bits. At $k^{*}=256$, $m=8$, the subcentroid tables together contain $k^{*}D$ floating-point values.

Risks and limits

• The estimate is not the distance. The error is bounded, on average, by the quantisation error in their analysis. Individual neighbours can swap order. Recall@100 on SIFT is not a promise about your embedding.
• $m=8$, $k^{\backslash }*=256$ is "often reasonable" in the paper, and it is the setting on many of their plots. It is 64 bits. It is not a tuned result for text.
• For a fixed bit budget their MSE prefers fewer, richer subspaces, while they also say MSE underestimates the search quality of using more subspaces. Measure the recall you care about.
• $w$ is the recall/speed knob of the inverted file. $w=1$ never sees a neighbour that landed in another cell. The paper's examples include 1, 8 and 64, not a universal default.
• Euclidean on unnormalised vectors is not cosine. The algebra that links them applies after L2 normalisation, and the codebooks have to be trained in that same space.
• No vector database product and no NetLeverage index is described.

Sources

1. H. Jégou, M. Douze and C. Schmid, Product Quantization for Nearest Neighbor Search, IEEE TPAMI, 2011, 33(1):117–128. HAL inria-00514462v2 — https://inria.hal.science/inria-00514462v2/document. HAL returned a browser challenge during the final review; the paper was read in an alternate copy carrying its HAL cover: https://paper-notes.zhjwpku.com/assets/pdfs/Product_Quantization_for_Nearest_Neighbor_Search.pdf (opened 10 November 2026). Product codes, SDC, ADC, IVFADC, $m$, $k^{\backslash }*$, $k^{\prime }$, $w$, 64-bit operating point.

This article was originally published on 10 November 2026.