Compute approximate distances from compact codes

Split a d-dimensional vector into m equal coordinate groups, assuming d is divisible by m for this basic construction. Train K centroids for each group and encode the nearest centroid index in that group. Concatenating the chosen centroids reconstructs a full vector. With K equal to a power of two, each group needs log₂K bits, and m groups provide K^m possible reconstructions without storing K^m complete vectors. The actual codebooks contain only Kd coordinate values.

The codebook is shared across the corpus and must travel with the encoded data. A code such as (1,1) has no geometric meaning without the exact centroid arrays, group ordering, and any preprocessing transform. Changing a codebook while keeping the old bytes silently changes their decoded vectors. In residual IVFPQ, the encoded quantity is typically the vector minus its coarse centroid, so the selected coarse codebook and residual convention are also part of that decoding contract.

For asymmetric distance computation, construct a table of squared distances from each query subvector to every centroid in its corresponding codebook. A stored code then selects one entry from each table, and their sum is the squared distance to its reconstruction. The query keeps its original precision. This avoids adding query quantization error, but it cannot restore information discarded from the database vector. Different original vectors can share an identical code and therefore tie under the approximate score.

Reconstruction error and ranking error answer different questions. A small average reconstruction error does not ensure that the nearest two documents keep their order when their true distances are close. Conversely, a large error in an irrelevant direction might leave a particular query ranking unchanged. Measure recall under the target query distribution. If exact vectors are retained elsewhere, rerank a sufficiently broad candidate set, recognizing that exact reranking cannot recover a document omitted before that stage.

A raw float32 vector consumes four bytes per coordinate, while a PQ payload might use only a few bytes. The ratio is meaningful only after naming what is counted. Add document IDs, coarse-list structures, graph links if present, shared codebooks, query lookup tables, and any original vectors used for reranking. On a tiny corpus, shared codebooks can dominate; on a large corpus, per-document codes and identifiers usually matter more. Compression ratios should state decimal or binary byte units.

Representative training is especially important when different coordinate groups have different distributions. A codebook trained on one encoder or document population can waste its centroids on regions absent from a new corpus. Validate reconstruction error by slice and retrieval recall separately, rather than assuming one number predicts the other. If you introduce a rotation or another learned preprocessing transform, preserve that exact transform with the snapshot and apply it consistently before both encoding and querying.