Qinco2: Vector Compression and Search with Improved Implicit Neural Codebooks
This work addresses inefficiencies in vector compression and search for large-scale applications like billion-scale nearest neighbor search, representing an incremental improvement over prior neural-based methods.
The paper tackles the problem of suboptimal rate-distortion performance in multi-codebook vector quantization for compression and nearest neighbor search by introducing QINCo2, which improves upon QINCo with enhanced encoding, decoding, and training methods, resulting in a 34% improvement in reconstruction MSE for 16-byte compression on BigANN and a 24% increase in search accuracy with 8-byte encodings on Deep1M.
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 34% for 16-byte vector compression on BigANN, and search accuracy by 24% with 8-byte encodings on Deep1M.