Qinco2: Vector Compression and Search with Improved Implicit Neural Codebooks

We’re happy to read that the reviewer found our paper “well-written and easy to read” and that “experiments and analysis are quite extensive and the improvements are significant.” We address comments in the weaknesses and questions section below.

W1 (“comparison of parameters”) The increased trainable parameter count indeed contributes to the improved MSE (“improved architecture“ in Table 3). We added a comparison of the parameter count in the first section of the appendix, and thank the reviewer for the suggestion. QINCo2-L uses 35.6M parameters, compared to 7.8M for the larger QINCo1. For the efficient large-scale search setting the difference is much smaller: QINCo2-S uses 1.6M parameters where QINCo1 (L=2) uses 1.4M.

W2 (“optimal convergence”) Our training procedure was designed to reduce training cost while preserving or improving the MSE compared to QINCo1. We can indeed reach lower error by increasing the training time. Following the reviewer suggestion, we ran experiments on BigANN1M and Deep1M (8 and 16 bytes) with more epochs, and observed an improvement of 0.5% up to 1% in MSE, while roughly doubling the training time. This indicates that our models are close to optimal convergence, and could have slightly improved results for a high additional training cost, which we did not deem worth for training large models compared to other improvements we studied in our paper.

Q1 (“consistent names”) We thank the reviewer for catching this, and we updated the names in the paper.

Q2 (“2M successive least-squares problems”) Some of the methods referred in Sec 4.3 and in Table 4 learn new codebooks based on combinations of two codes, as explained in the paragraph “Pairwise additive decoding” in Section 3.3. We take fixed codes i and j each indexing a vocabulary of K codewords, we combine these to create a new code indexing over a vocabulary of K^2 elements. As we have M codes, it means a maximum of M*(M-1) pairwise combinations. In our experiments we consider using pu to a maximum of 2M of such pairwise codebooks.

Q3 (“R@10 and R@100 scores”) Thank you for noticing this. In general we notice that the ordering of methods in these more relaxed metrics is similar, while the differences between them are reduced. This can also be seen in Table S2 of (Huijben et al., 2024). For sake of completeness, we added Table S4 to the appendix where we report the R@10/100 metrics for the experiments considered in Table 3 of the main paper.

We would like to thank the reviewer for acknowledging that our work “significantly improves quantization error and retrieval accuracy”. We address the points raised in the review point-by-point below.

W1 (“theoretical contribution”) We do not claim theory contributions in our paper; our contributions are methodological (pre-selection, pairwise decoding) and technical (beam search, improved architecture and training) in nature. Our contributions lead to significant advances in reconstruction and search accuracy, as demonstrated through extensive experimental results.

W2 (“paper hard to follow”) We’re sorry that some parts of the paper might have been less clear. If the reviewer can point to specific passages we’re happy to clarify those further.

W3 (pre-selection not clear) During the QINCo1 encoding process, all codewords from each codebook are forwarded through the neural network to obtain their adaptation and select the more accurate one, which significantly improves quantization accuracy. Codeword pre-selection, one of our main contributions, allows to forward only a subset of the codewords through the (computationally expensive) neural network. For this to be effective, the key is to pre-select the codewords by a technique that is more computationally efficient. We found that pre-selection using L2 distance to a learned codebook (which we compare to also using smaller networks) leads to important performance gains during the encoding process. As the encoding process (forward pass) is also the bottleneck during training, our method reduces training time, even if it has slightly more parameters to learn.

We would like to thank the reviewer for acknowledging that we report “state-of-the-art performance on several benchmarks” and that “Extensive experiments demonstrate the effectiveness of each component”. Below we address the different points raised in the review.

W1 (“task scenarios are not convincing”) Please refer to our general response to reviewers, where we address this comment together with similar ones from other reviewers.

W2+Q3 (latency) We agree with the reviewer that it is interesting to also consider the latency of different methods when processing a single query. We note that QINCo2 is implemented in python, and that the same holds true for QINCo, as compared to c++ implementations for PQ and RQ. To compare latencies we selected the operating point for BigANN1B 16 and 32 bytes where QINCo2 and IVF-RQ have approximately the same QPS & R@1. On BigANN1B (16 bytes) at a point with R@1=37 and QPS=2700, RQ has a latency of 10.78ms, and 9.10ms for QINCO2. On BigANN1B (32 bytes) at a point with R@1=62 and QPS=350, RQ has a latency of 71.54ms, and 22.25ms for QINCO2. While RQ uses larger (computationally more expensive) parameters for the Faiss query to achieve this accuracy, QINCo2 uses a less accurate and faster Faiss setting combined with a precise QINCo2 re-ranking. The smaller latency for QINCo2 might indicate that the Faiss search benefits more from batched queries, and that QINCo2 can bring substantial improvements to speed with a small number of queries. We thank the reviewer for this interesting suggestion, and we added these results to the paper.

Q1 (adding rerank stage to PQ/RQ for search, considering relaxed metrics such as R@10)
(a) Re-ranking PQ/RQ search results using additional finer codes or original data would improve accuracy at the cost of additional storage, and therefore does not fit the (standard) experimental setting with constant memory budget. We note also that in the 2021 BigANN approximate nearest-neighbor search benchmark, searching in-RAM and in RAM+flash (which is a typical setting for reranking with a more precise representation) are entirely different tracks, which highlights that these settings are not comparable.
(b) When using less restrictive metrics such as R@10 instead of R@1, we observe that all methods get closer to each other in accuracy while maintaining the ordering of results. Therefore we found it more useful to report the R@1. For sake of completeness we added Table S4 to the supplementary material where we report R@10/100 for the experiments in Table 3.

Q2 (encoding/decoding speed of QINCov2) The encoding times in Figure 4 do not compare to related work as they correspond to ablations specific to QINCo2. In L231-232 we express the encoding and decoding complexity of QINCo2 in terms of the main parameters (vocabulary size, number of encoding steps, etc.), but we agree with the reviewer that a comprehensive comparison to previous approaches, akin to Table 3 in the QINCo paper would be useful. We added it to the paper as Table S2 in the supplementary material. Compared to the small QINCo1(L=2) version reported in the table, our QINCo2-S model has a slower encoding (2910μs instead of 823μs) and a faster decoding (6.2μs instead of 8.3), which aligns with our goal of prioritizing decoding speed.

We are happy the reviewer finds our paper “easy to understand” and refers to our experiments as “Extensive”. Let us address the comments in the weaknesses and questions section below.

W1+Q2 (“Source code”) The source code will be released upon acceptance of the paper, and will include the model weights used for our results.

W2 (“Limited novelty”) We believe the work presented in our paper does have significant novelty, in particular the candidate pre-selection and pairwise approximate decoder are conceptually novel. Together with the use of beam search, this leads to runtime-controllable parameters to navigate the compute-accuracy tradeoff for neural decoders. These innovations together contribute to our substantially improved results w.r.t. the state-of-the-art results of QINCo, improving reconstruction MSE by 44% for 16-byte vector compression on BigANN, and search accuracy by 24% with 8-byte encodings on Deep1M.

Q2 (“use case that clearly benefits from QINCo2”) Please refer to our general response to reviewers, where we address this comment together with similar ones from other reviewers.

We would like to thank the reviewer for underlining the “novel solution” our work offer and the “represents a significant advancement” it represents, shown by our “empirical evaluations across multiple datasets”. We would like to address the reviewer concerns and questions below:

W1 (“other non-uniform quantization methods … extended to work with other large language models (LLMs), such as the LLaMA ”) We weren’t quite sure to fully understand this question from the reviewer. So please let us know if our answers do not provide the information the reviewer was looking for.
(a) QINCo2 as well as methods we compare to (PQ, RQ, UNQ, QINCo) all rely on non-uniform quantization with k-means, but embedded in different quantization pipelines.
(b) Regarding extension to “other LLMs”, in our experiments, QINCo2 is used to quantize text embeddings from the Contriever model. Decoder-only large languages such as the LLaMA family do not clearly provide embeddings for text. If embeddings were nonetheless extracted from such a model, then yes, QINCo2 could be used to quantize them.

W2 (“high inference time”) Please refer to our general response to reviewers, where we address this comment together with similar ones from other reviewers.

W3 (“multiple heuristics and iterative steps”) We weren’t quite sure what the reviewer was pointing to precisely. Please let us know if our response does not address your concern.
(a) Regarding our large-scale search approach: Integration of a neural decoder into a billion-scale nearest neighbor search pipeline requires intermediate steps to balance speed and precision as described in Section 3.2. Such multi-stage pipelines are customary in other vector search works. See e.g. Huijben et al., ICML’24, section 3.3 in Morozov&Babenko, ICCV’19 and section 3.4 in “Automating Nearest Neighbor Search Configuration with Constrained Optimization” by Sun, Guo, Kumar, ArXiV’19. But the core of our contribution, the improved quantization algorithm, does not rely on this pipeline, as described in detail in Section 3.2 and experimentally validated in Section 4.2.
(b) If the reviewer is pointing to Appendix A2 where we list the training details for QINCo2: our goal here was to aim for maximal transparency about all settings used to train our models, and we note that these include mostly hyper-parameter choices (such as batch size, learning rate, optimizer, etc) that have to be made anyway.

W4 (“alternative architectures for $g$”) In preliminary experiments we explored other architectures for codeword pre-selection, including linear projections, combinations with additive and multiplicative components, etc. We retrained the solution described in L205-207 where we just use a (second) trained codebook for preselection, i.e. with $g(c|x) = c$, as we found it to provide the best compute-accuracy tradeoff as compared to more complex alternatives. We compared it with using smaller models with the same architecture as they were particularly effective and the function $g(c|x) = c$ can be expressed as a special case of smaller models by setting depth to 0.

W5 (“keeping a single candidate set for multiple beams”) Using the same pre-selected candidate codewords for each hypothesis in the beam will generally lead to worse results (as the candidates are no longer selected for optimality per hypothesis). Moreover, when using shared candidates, we would still need to evaluate the neural network f(c,x_hat) for each candidate for each hypothesis – i.e. $A\times B$ evaluations –, as QINCo adapts codeword c based on the partial reconstruction x_hat (specific to each hypothesis). Therefore sharing the candidate across hypotheses would not lead to speed improvements.