PMC: Build-Time Per-Modality Centroid Correction for Cross-Modal Binary-Quantized Retrieval

Abstract

Approximate nearest neighbor search is a core operator in large-scale retrieval, where vector quantization is widely used to reduce memory cost. Binary quantization methods encode each dimension as a single bit, but they assume queries and database vectors share a common centroid. This assumption fails in cross-modal retrieval, where each modality clusters around a different centroid, producing a modality gap that corrupts the centroid's dual role as inverted-file routing pivot and sign-bit decision boundary. We propose Per-Modality Centroid Correction (PMC), which shifts database vectors toward the query centroid at build time, rewriting routing and code boundaries at the source rather than merely adjusting queries at serving time. A selective variant confirms that concentrated gap energy in a few dimensions drives most recall loss. PMC adds no index memory or serving overhead; at ?=1, the correction is fully absorbed into the index with zero query-time cost. Experiments on five cross-modal benchmarks, three encoders, and four binary-quantized index types show gains over uncorrected and query-shifted baselines that scale with modality-gap magnitude, up to a 400M-vector deployment. Code: https://github.com/sehoon787/PMC.