Coordinate Heterogeneity Governs Binary Quantization: From InfoNCE to Recall
For practitioners building binary quantization systems for nearest neighbor search, this provides the first principled design guide explaining when to use random rotation versus preserving coordinate axes.
Binary quantization (BQ) achieves competitive recall on contrastive embeddings but fails on others, with no common theory explaining when random rotation or preserving coordinate axes is appropriate. The authors resolve this by showing that coordinate heterogeneity governs BQ performance, deriving closed-form expressions for ranking fidelity and a two-parameter scaling law validated across 13 datasets and 6 embedding families.
Binary quantization (BQ) compresses high-dimensional embeddings into one or two bits per coordinate, enabling nearest neighbor search at extreme speed. Yet a striking puzzle persists: BQ achieves competitive recall on contrastive embeddings but fails on others -- and two leading systems adopt diametrically opposite strategies (random rotation vs. preserving coordinate axes) without a common theory explaining when each is appropriate. We resolve this puzzle by connecting the Gaussian structure recently established for InfoNCE-trained representations to a complete analytical framework for BQ quality. The key insight is that coordinate heterogeneity -- the non-uniformity of per-coordinate variances -- governs the key aspects of BQ performance. We derive closed-form expressions for ranking fidelity, prove that the magnitude bit carries information proportional to heterogeneity, and show that random rotation destroys precisely the signal that one paradigm exploits while creating the isotropy that the other requires. A two-parameter scaling law predicts fidelity across models and dimensions. Experiments on 13 datasets and 6 embedding families validate all predictions and provide the first principled design guide for binary quantization systems.