Residual Vector

A residual vector r is computed as the difference between the original vector x and its assigned coarse centroid c:

r = x - c

This subtraction removes the global, large-scale structure captured by the centroid, isolating only the local displacement within the Voronoi cell. The resulting residual has significantly lower energy and a more symmetric distribution, making it far easier to compress with Product Quantization (PQ) than the original vector.

In the Inverted File with Product Quantization (IVFPQ) architecture, residual vectors serve as the critical bridge between coarse partitioning and fine compression:

• Coarse Quantizer: Assigns the query to the nearest centroid(s), defining the search scope.
• Residual Calculation: The centroid is subtracted from all vectors in that partition.
• Product Quantization: The low-variance residuals are encoded using distinct sub-codebooks.

This two-level encoding is the foundation of billion-scale vector search in libraries like FAISS.

The primary benefit of encoding residuals instead of raw vectors is variance minimization. Raw vectors in high-dimensional space are widely dispersed, requiring large codebooks for accurate quantization. By centering each partition at its local mean (the centroid), the residual distribution becomes tightly clustered around zero. This allows Product Quantization to achieve a much lower quantization error for the same bitrate, directly improving recall in approximate nearest neighbor search.

During search, distances are computed asymmetrically to maximize accuracy:

• The query vector remains in full precision (not compressed).
• The database residuals are approximated via their PQ codes.

The distance between a query q and a database vector x is approximated as:

d(q, x) ≈ d(q - c, PQ(r))

This avoids compounding quantization errors from compressing both the query and the database vectors, yielding higher recall than symmetric computation.

Residual encoding is a core strategy within the broader field of vector compression. It is not a standalone compression algorithm but a preprocessing step that enhances techniques like:

• Product Quantization (PQ): Encodes residuals as short codes.
• Scalar Quantization (SQ): Maps residual dimensions to integer values.
• Additive Quantization: Approximates residuals as a sum of multiple codebook entries.

By reducing the dynamic range of the data, residuals allow these methods to allocate bits more efficiently to the information that actually discriminates between neighbors.

Encoding residuals directly impacts the recall-speed-memory tradeoff. Empirical benchmarks in FAISS demonstrate:

• Indexing raw vectors with PQ: Significant recall degradation at low bitrates.
• Indexing residuals with PQ: Maintains >90% recall@10 even with aggressive compression (e.g., 64 bytes per vector).

The residual's lower entropy means that the quantization error introduced by PQ primarily affects the noise floor rather than the relative ordering of true nearest neighbors, preserving the ranking quality essential for high recall.