Question about IVFADC pre-computed table

[Luciferre]

In https://github.com/facebookresearch/faiss/blob/main/faiss/IndexIVFPQ.cpp#L361

/** Precomputed tables for residuals
*

• During IVFPQ search with by_residual, we compute

• d = || x - y_C - y_R ||^2
  

• where x is the query vector, y_C the coarse centroid, y_R the
• refined PQ centroid. The expression can be decomposed as:
• d = || x - y_C ||^2 + || y_R ||^2 + 2 * (y_C|y_R) - 2 * (x|y_R)

•    ---------------   ---------------------------       -------
  

•         term 1                 term 2                                       term 3
  

• When using multiprobe, we use the following decomposition:
• • term 1 is the distance to the coarse centroid, that is computed
• during the 1st stage search.
• • term 2 can be precomputed, as it does not involve x. However,
• because of the PQ, it needs nlist * M * ksub storage. This is why
• use_precomputed_table is off by default
• • term 3 is the classical non-residual distance table.
• Since y_R defined by a product quantizer, it is split across
• subvectors and stored separately for each subvector. If the coarse
• quantizer is a MultiIndexQuantizer then the table can be stored
• more compactly.
• At search time, the tables for term 2 and term 3 are added up. This
• is faster when the length of the lists is > ksub * M.
  */

I don't quite understand the last sentence - This is faster when the length of the lists is > ksub * M. Is length of the lists means the length of posting list in each coarse centroid? The term 2 is not related with query x, so it can be computed when system initialized. So why it's faster when the length of the lists is > ksub * M?
Thank you for the help.

[onestardao]

You're asking a very good question, and you're absolutely right to pause at this term split.

From your quote:

the table for term 2 is not related with query x

Exactly — and that’s the key insight.
The second term is purely a function of the quantizer codebook itself, so once the residuals are encoded, that portion becomes query-independent.

So what you're observing is a classical optimization known as pre-computed codebook distances, where term 2 is factored out and stored ahead of time to reduce runtime compute. This works because:

• Term 1 depends on the current query x → must be computed at runtime
• Term 2 depends only on the codebook + PQ codes → can be pre-computed
• Term 3 is a standard lookup (table distance from PQ)

You also asked:

So why is it faster that the length of the table is ksub * M?

Because each subquantizer (M) encodes one chunk of the vector, and each has its own table of distances to centroids (ksub).
So your lookup is essentially: