Accelerating Large-Scale Inference with Anisotropic Vector Quantization
Ruiqi Guo* Google Research Philip Sun* Google Research Erik Lindgren* Google Research Quan Geng Google Research David Simcha Google Research Felix Chern Google Research Sanjiv Kumar Google Research
Abstract
Quantization based techniques are the current state-of-the-art for scaling maximum inner product search to massive databases. Traditional approaches to quantization aim to minimize the reconstruction error of the database points. Based on the observation that for a given query, the database points that have the largest inner products are more relevant, we develop a family of anisotropic quantization loss functions. Under natural statistical assumptions, we show that quantization with these loss functions leads to a new variant of vector quantization that more greatly penalizes the parallel component of a datapoint’s residual relative to its orthogonal component. The proposed approach, whose implementation is open-source, achieves state-of-the-art results on the public benchmarks available at ann-benchmarks.com.
中文速览
大规模向量检索（Maximum Inner Product Search, MIPS）的核心难题在于：面对数百万甚至数十亿条数据，如何快速找到与查询向量内积最大的那些条目？现有量化压缩方法都以最小化数据点的重建误差为目标，但这篇论文指出这个目标本身就是次优的——对于给定查询，内积得分越高的数据点对检索结果影响越大，理应在量化时获得更高的惩罚权重。为此，作者提出了一类"分数感知量化损失函数"（score-aware quantization loss），并从理论上证明：在自然的统计假设下，这类损失函数等价于一种各向异性（anisotropic）加权方案——数据点残差中平行于自身方向的误差分量，比垂直方向的误差分量受到更重的惩罚。将这一思路应用到乘积量化和向量量化等主流方法后，新方案在ann-benchmarks.com的公开大规模基准测试（如Glove-1.2M）上取得了当时最优的检索精度，同时也显著提升了内积值本身的近似准确度。这项工作的意义在于，它从理论层面厘清了"重建误差最小化"与"检索性能最优化"之间的本质差距，并给出了一个有理论保证、可开源复现、适用范围广泛的改进方向。
原文 arXiv:1908.10396;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1908.10396v5