Qinco2: Vector Compression and Search with Improved  Implicit Neural Codebooks
Théophane Vallaeys Matthew J. Muckley Jakob Verbeek Matthijs Douze
Vector quantization is a fundamental technique for compression and large-scale nearest neighbor search. For high-accuracy operating points, multi-codebook quantization associates  data vectors with one element from each of multiple codebooks. An example is residual quantization (RQ), which iteratively quantizes the residual error of previous steps. Dependencies between the different parts of the code are, however, ignored in RQ, which leads to suboptimal rate-distortion performance. Qinco recently addressed this inefficiency by using a neural network to determine the quantization codebook in RQ based on the vector reconstruction from previous steps. In this paper we introduce Qinco2 which  extends and improves Qinco with (i) improved  vector encoding using  codeword pre-selection and beam-search, (ii) a fast  approximate decoder leveraging codeword pairs to establish  accurate short-lists for search, and (iii) an optimized training procedure and network architecture. We conduct experiments on four datasets to evaluate Qinco2 for vector compression and billion-scale nearest neighbor  search. We obtain outstanding results  in both settings, improving the state-of-the-art reconstruction MSE by 44% for 16-byte vector compression on BigANN, and search accuracy by 24% with 8-byte encodings on Deep1M.
vector compression, large-scale retrieval, neural compression, quantization
We introduce a new quantization process for the QINCo neural quantizer, combining beam search with fast approximation, alongside a improved search pipeline and model architecture, improving both accuracy and speed for large-scale retrieval.