Residual Quantization with Implicit Neural Codebooks
Iris Huijben Matthijs Douze Matthew Muckley Ruud van Sloun Jakob Verbeek
Vector quantization is a fundamental operation for data compression and
vector search. To obtain high accuracy, multi-codebook methods increase the
rate by representing each vector using codewords across multiple codebooks.
Residual quantization (RQ) is one such method, which increases accuracy by
iteratively quantizing the error of the previous step. The error distribution
is dependent on previously selected codewords. This dependency is, however, not
accounted for in conventional RQ as it uses a generic codebook per quantization
step. In this paper, we propose QINCo, a neural RQ variant which predicts
specialized codebooks per vector using a neural network that is conditioned on
the approximation of the vector from previous steps. Experiments show that
QINCo outperforms state-of-the-art methods by a large margin on several
datasets and code sizes. For example, QINCo achieves better nearest-neighbor
search accuracy using 12 bytes codes than other methods using 16 bytes on the
BigANN and Deep1B dataset.