Qinco2: Vector Compression and Search with Improved  Implicit Neural Codebooks
Authors: Théophane Vallaeys
Matthew J. Muckley
Jakob Verbeek
Matthijs Douze
Venue: ICLR 2025 Poster (2025)
Keywords: vector compression
large-scale retrieval
neural compression
quantization
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: 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.

Abstract: 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.

Published as a conference paper at ICLR 2025
QINCO2: VECTOR COMPRESSION AND SEARCH WITH IMPROVED IMPLICIT NEURAL CODEBOOKS
Théophane Vallaeys, Matthew Muckley, Jakob Verbeek, Matthijs Douze,
FAIR, Meta
(webal borbalorn,a mwuckey, j jivebbek,, matthi (ass)mmmtta... com
ABSTRACT
Vector quantization 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 code- books. 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 per- formance. QINCO recently addressed this inefficiency by using a neural network determine the quantization codebook in RQ based the vector reconstruction from previous steps. In this paper we introduce QINCO2 which extends and im- proves 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) 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 recon- struction MSE by 34% for 16-byte vector compression on BigANN, and search accuracy by 24% with 8-byte encodings on DeepIM.
INTRODUCTION
Vector quantization is a fundamental technique, with widespread use cases from exploratory data analysis and visualization, to self-supervise learning (Caron et al., 2018), image compression (Esser al., 2021; Careil et al., 2024) and large-scale nearest neighbor search (Jégou et al., 2010). To learn vector quantizer from data, the k-means algorithm (Bishop, 2006; MacQueen, 1967) is probably the most ubiquitous. associates each data vector with the nearest element in a learned codebook of centroids in the sense of mean squared error (MSE).
In data compression the goal to optimize the rate-distortion tradeoff (Shannon, 1948). With k- means the quantization error can be reduced by using larger number of centroids K, which nat- urally increases the bitrate of [log, K to encode the index of the centroid assigned to a particular data vector. In practice, the number of parameters and computational cost of the k-means grows linearly in the number of centroids, k-means is hard to scale beyond, say, 1M centroids. To enable lower distortion operating points, multi-codebook quantization (MCQ) methods associate each data vector with one element across each of M > 1 codebooks. Examples include Product Quantization (PQ), which slices data vectors in several pieces and applies k-means to each of them, and residual quantization (RQ), which iteratively applies k-means to the residual of previous quantization steps.
fundamental limitation of both PQ and RQ is that the M codebooks are pre-determined and independent of the vector to be quantized. This is suboptimal, as in general there are dependencies between different parts of the code, and one part of a PQ or RQ code carries information about other parts of the code. Such dependencies can be modeled using an entropy model, as e.g. explored by El- Nouby et al. (2023) for image compression, but this only reduces the bitrate and does not directly address the inherent inefficiency of the quantizer. Huijben al. (2024) introduced QINCO, neural variant of RQ, that reduces this redundancy where each codebook is computed as a function of earlier selected codes. QINCo is initialized from RQ codebooks and learns neural network to update the codewords for the current step as a function of the vector reconstruction from previous steps. This leads to large improvements in MSE reconstruction and nearest neighbor search accuracy.

---

Published as a conference paper at ICLR 2025
tode 1
oode 1
GM
Figure 1: Overview of the QINCo2 archi- tecture, as used during decoding. Top: The codes (i) (c'....,.")) (MM are mapped to code- words (cl (c.....,e"t) using look-up tables C C.M. These codes are sequentially combined using a parameterized function fam. Bottom: The function føm applied on code- word cm and the partial reconstruction a" nn from the previous step, using sequence of residual MLPs.
fe()
M fm
6"
codleword e*
partol 1
In this paper we introduce QINCO2 which extends and improves upon QINCO in several ways. (i) We improve the vector encoding using codeword pre-selection and beam-search: pre-selection reduces the number of function evaluations to update RQ centroids which makes beam search more affordable, significantly reducing the quantization error. (ii) We introduce a fast, look-up based, ap- proximate decoder for the QINCO2 codes to establish shortlists for large-scale search: the decoder works akin to RQ but uses a pair of QINCO2 codes in each step to account for their dependencies. (iii) We optimize the training procedure and network architecture: this includes configurable inter- nal feature dimension of the network and an additional residual connection, improved initialization and larger batch size. See Figure for an illustration of the QINCo2 architecture.
We conduct extensive experiments on four different common vector compression datasets: Deep B, BigANN, FB-ssmpp. and Contriever. We evaluate QINCo2 for vector compression performance in terms of reconstruction MSE and nearest neighbor accuracy on IM sized databases. In addition, evaluate in experiments in a billion-scale vector search setting, in terms of the search-speed vs accuracy trade-off. We obtain outstanding results with QINCO2 in both settings. For example, compared the recent of-te-of-thheart QINCo approach, we reduce reconstruction MSE by 34% from 0.32 x 10 to 0.18 x 10 for 16-byte compression of vectors in the BigANN dataset, and improved nearest neighbor accuracy by 24% from 36.3% to 45. for 8-byte compression of vectors in the Deep M dataset. Code is available at: https: // /i thub. com/ bacebookreseart nio
2 BACKGROUND AND RELATED WORK
Multi-codebook quantization. This family of methods builds on multiple k-means sub-quantizers, using different codebooks. With M sub-quantizers, the total code size becomes M M[log2 (K)] bits. Product Quantization (PQ) (Jégou et al., 2010) splits the vectors into M sub-vectors that are quan- tized separately. As the sub-codes are estimated independently, finding the optimal encoding is trivial. In Residual Quantization (RQ) (Liu et al., 2015) k-means quantizers are applied sequentially such that each quantizer encodes the residual left from the previous step, and decoding sums the se- lected M codewords. RQ encoding is greedy and therefore potentially suboptimal. It can, however, be improved using beam search to explore several encodings in parallel. In Additive Quantization (AQ) (Babenko & Lempitsky, 2014) the M sub-codes are estimated simultaneously for encoding, while using the same cun-oo-codewords decoding as RQ. LSQ (Martinez et al., 2018) is a state-of- the-art AQ variant that relies on annealed optimization, where the encoding accuracy depends on the number of optimization iterations. RVPQ (Niu et al., 2023) combines PQ with RQ by slicing the vectors in number of components, and applying RQ with beam search on each of them.
Neural vector quantization. Vector quantization has been used in neural networks for different purposes. For generative modeling, VQ-VAH (Oord et al., 2017; Razavi al., 2019; Esser et al., 2021) uses single-step vector quantization in the latent space of variational autoencoder (Kingma & Welling, 2014), and generates samples from an autoregressive sequence model fitted to the quan- tization indices. RQ-VAE (Lee et al., 2022) relies instead on residual quantization to better approx- imate the latents, while RAQ-VA VAE (Seo & Kang, 2024) enables rate-adaptive quantization within VQ-VAB with transformer- bassed entropy model to reduce the bitrate for image compression. Careil et al. (2024) uses quantized encoder, and couple it with diffusion-based decoder for high-realism image com-
to--nceeet--euueeee model. In a similar spirit, El-Nouby et al. (2023) uses
2

---

Published as a conference paper at ICLR 2025
pression. Closer to work, UNQ (Morozov & Babenko, 2019) considers vector compression and jointly trains an encoder-decoder model with multiple codebooks in the latent space, using a straight-through nuubel-Softmax estimator for differentiation. DeepQ (Zhu et al., 2023) similarly uses an encoder that maps the input vector to a set of independently sampled indices, but relies on REINFORCE gradient estimator, simply summing the selected codewords rather than using decoder network. In our work, we do not use an encoder-decoder pair to map the data to latent space for quantization. Instead, we directly quantize the data in the data space, thereby avoiding any data loss incurred by the encoder-decoder, and using a residual neural quantizer to encode the data. QINCO (Huijben et al., 2024) is an improved residual quantizer that uses neural networks adjust the quantization codebooks for each data vector, based on the reconstruction obtained in previous steps. In our work, we build upon QINCO and improve its performance by optimizing the network architecture and training procedure, introduce fast codeword selection in encoding to make beam search more affordable.
Large-scale nearest neighbor search. Vector quantization is fundamental component of approx- imate search methods. Rather than using exhaustive search, a promising subset of the database is determined using a coarse quantization. An inverted file index (IVF) is used to store which part of the data is present in each cluster (Jégou et al., 2010), and efficient algorithms such as HNSW (Malkov & Yashunin, 2018) determine which clusters should be accessed given query. Finally, the query is matched with the (quantized) data in the identified clusters. As decoding with QINCO is expensive, Huijben al. (2024) proposed an additional step based on an efficient approximate additive decoder, to reduce the amount of data that needs to be passed through the neural decoder. We improve upon this approach by introducing an additive decoder that leverages the dependencies of pairs of code- words to boost the shortlist accuracy. allowing to reduce their size and improve efficiency. Amara al. (2022) considered multi-layer neural network decoders to improve the accuracy of additive linear decoders, but keep the codes themselves fixed. Our pairwise decoder similarly provides an alternative decoder for given codes, but in our case we seek less accurate but faster decoder.
3 IMPLICIT NEURAL CODEBOOKS
3.1 NOTATION AND BACKGROUND
Multi-codebook quantization. We start by introducing notations describing the general framework of multi-codebook quantization. We denote the vectors that we aim to quantize as x E Rd, which follow an unknown distribution, accessed only via data sampled from it. The quantization process is characterized by a set of M codebooks C' ..... C.M with K elements each and parameterized by 0, where C {cT ..... J. and by decoding function F(c',, ..... M. Its error is measured by loss function, for which we consider the l, MSE loss defined by L(x, q) || q1l.. We define general quantization procedure as
Q x +
arg min eleCI o....MM cCM
C(x, ((.,,..,,
(I)
During training, the objective is to find parameters @ minimizing the expected reconstruction loss: En [C(x, ((x)]. The quantized vectors can then be stored with indices using M log, K' bits.
Residual Quantization (RQ) (Chen et al., 2010) defines F (c'...... .M)) = ΣM cm and couples this decoder with an approximate but efficient sequential encoding procedure 2RQ where:
m==
0 O.
====Fooe (F ....,..)) S Th
(2)
c. = arg min L(x, Fo......... c
c... m-1 cc),
(3)
in which tt is the partial reconstruction until stage m, and T m. The codeword e is selected to best approximate the residual as cm = arg min 0( c).
= is the residual at step
Quantization with implicit neural codebooks. QINCO (Huijben et al., 2024) builds on RQ by redefining the decoding function F without changing the quantization process QRY- The key insight is that in RQ the distribution of the residuals "' depends on c¹ ....... _ yet all residuals are quantized using the same codebook C In theory, one could improve this by using a codebook hierarchy CTM (c.) (c.....,c" c1-1) that depend on previously selected codewords, but this leads to an
3

---

Published as a conference paper at ICLR 2025
0
Figure 2: Overview of the en- coding process of QINCO2. At a given step m, the B beam search hypotheses are each com- bined with A pre-selected candi- dates, for which codebook ele- ments are computed with fo". and the best B hypotheses are retained for the next encoding step.
2
45
Keep candiaass each
25 Curc CUEE
KING
exponential number codebooks, which unfeasible in practice. Instead, QINCO parameterizes F using a neural network as
Fo..c'...., M) = Σ fam (c (=" m)
(4)
where the fom are modeled by the same neural network, but with separate weights 8Th for cach step. By choosing appropriate residual architecture for the network, and initializing from RQ code- books, the reconstruction error can be guaranteed to be no worse than that of the RQ initialization.
3.2 IMPROVED IMPLICIT NEURAL CODEBOOKS: ENCODING
We identify the encoding efficiency as the major bottleneck to deploy QINCO. We propose (i) mechanism to speed it up, and (ii) the use of beam search to make it more accurate. We then (iii) adjust the architecture and training procedure to further improve quantization accuracy and training speed. We use QINCo2 to refer to models benefiting from all these improvements.
Pre-selection. The RQ quantization process QRQ applied to QINCO can be expressed as a sequence of M steps, where each one consists in finding
arg min ffm (fm(())"")))))
(5)
CEC
This process requires K evaluations of the neural network føm, the complexity of which therefore scales linearly with the codebook size K. To reduce the computational cost, we propose a two-step encoding. First, we select set Am of candidates using an efficient function Jam. This function
relics on a distinct codebook CTM = {aT ..... CK ). We then compute fam over this restricted set, yielding the following quantization procedure which replaces Eq. (5) and we refer to QQI-Ai
Am = arg min L(r" 99mm m (eg [a"" [a:"
1 =D arg min L(r S (ce (m)-
KEA...
In our experiments, 9 uses the same architecture as f with much smaller depth L, and hidden dimension d, = 128. In particular, with L, = 0 we instead define g(c|x) = c, which yields Am Top, arg min C(r ..a). This setting is significantly more efficient than L, 1.
Beam search. In RQ, instead of maintaining a single partial reconstruction across encoding steps, beam search (Babenko & Lempitsky, 2014) maintains set of partial encodings. At quantization step m., each partial encoding is combined with each of the K codebook elements, creating K x B new partial encodings, and the best B ones are selected for the next step. Thus, one step of beam search here requires K x B evaluations of f. increasing compute by factor B w.r.t. greedy search. Candidate pre-selection reduces this number to A x B, defining encoding process QQi-- at the cost of adding K x B evaluations of g and of the loss function L, whereas the greedy search QINCo baseline does K evaluations of f. Therefore, depending on the setting of A, B, we can benefit from the improved search accuracy of beam search at controlled cost. See Figure for an illustration.
4

---

Published as a conference paper at ICLR 2025
Database encoding
Figure Overview of our large- scale search pipeline. We com- bine the compression accuracy of QINCo2 with efficient look-up methods to build and filter short- lists of candidates. Top part shows the encoding of the database and the creation of fast searchable in- dex. Bottom part shows the re- trieval process for given query q-
VO Kyyp
GINGu2 enooding
Crease AG and condined RD trelss
Dalabase D) tra ring data
Tacep haining
Large-scale search
Input: qJory 9
Syp
Sag Sper
Parneto acddiee socoding Sputa 8AQ
oog ulo ((d"))))
giit decoding
(foel in 68K)
[19r0] 500
UFreel 169)
Faiso soarch
Shoris dlyonaaionn Cooe
Architecture. The function fo in QINCo2 (see Figure 1) is similar to that of QINCO. The main differences are (i) the network backbone has dimension de, independent from vector dimension d (we add linear projections between Rd and Rdd, at the extremities of the network); and (ii) we add connection from the input to the output to preserve accuracy when de < d. This architecture uses (M + dd.)) FLOPs for decoding, and O(ABM (Ld,d, + dd,) BKd) for encoding.
Training. Compared to QINCO, we improve the initialization of the network and codebooks weights. the dataset normalization, the optimizer and the learning rate scheduler, and increase the batch size. We also stabilize the training by adding gradient clipping, and reduce the number of dead codewords by resetting unused ones similar to Zheng & Vedaldi (2023). Additionally, we notice that large volumes of training data are usually available for unsupervised task such as compression. Hui- jben et al. (2024) showed that more training data is beneficial to the accuracy of QINCo. Motivated by this observation, we train our models on the full training set of each benchmark (up to 100s of millions of vectors, see Table 1). Details of the training procedure can be found in App. A.2.
3.3 LARGE-SCALE NEAREST NEIGHBOR SEARCH
For approximate search, we build an index structure over a database of vectors D = fan, : n E [[]]] J. where [[]] {1. ,.. J.. Given query q. we search for its nearest neighbor in the f2 sense in D. In practice, exhaustive search in large databases is costly, and search is performed over a quantized version of the database. Overall search pipeline is shown in Figure 3.
Creating shortlists with IVF and AQ. Quantization reduces storage requirements, and can be leveraged to reduce the computational requirements for approximate nearest-neighbor search with QINCO2 by efficiently creating "shortlists" of the most promising database vectors. Following Huijben et al. (2024), we use IVF (Jégou et al., 2010) to group the database vectors into Kivr buckets (L4)) before quantizing the database with QINCo2, as shown in the "database encoding" (top) row of Figure 3. This is equivalent encoding æ as (10, 11 ,..., I.....I').. with the additional index 1 E [KivF] indexing the IVF bucket, and / ...... ldd E [K]] The reconstruction is & (19)) C.22 (I) For simplicity, we exclude the IVF codeword 1 from the beam search.
Given a query, IVF forms SivF C D from the contents of the Nprobe < KIVF nearest buckets to the query. The size |Sivel of this subset ranges from a few thousands few millions. This is too large to rank with QINCo2 efficiently, so we re-interpret the indices (12 "?,...,!!!! MM as additive quantizer codes from which approximate distances can be computed efficiently (Huijben al., 2024). The AQ codebooks are estimated by solving least-squares system on vectors and their corresponding codes from QINCo2 (Amara et al., 2022). This yields a second shortlist SAQ C SiVF. Only the vectors in SAQ are then decoded using IVF-QINCo2, and ranked by their distance to the query to provide the final search result. This is represented by the "Faiss search" and "QINCo2 decoding" blocks in the bottom row of Figure 3.
Pairwise additive decoding. Although fast, AQ decoders trained on QINCO2 codes have a much lower search accuracy than full QINCo2 decoding. This is because the AQ decoder can only sum up independent AQ codebook entries, ignoring the dependency structure between the code elements.
We notice that AQ codebooks can be trained from any sequence of codes, including combined codes and repeated codes. We consider building a decoder based on pairs of codes. To this end we use the mapping T (1--1)= 11) x K 15, with /t, T E [K] and T [ Combining codes in this way
5

---

Published as a conference paper at ICLR 2025
makes the codebooks larger (K² instead of K) so they are slower train, but also more expressive. Note that this decoder is guaranteed to be at least as good as the unitary decoder, since the codebook entries from two unitary codebooks can be combined into pairwise decoding codebook.
The most straightforward way to take advantage of joint codebooks is to map a sequence of unitary codes (T), _2, ..... I to a sequence of pairwise codes (I1,2 13.4,..., JM-- of length M/2. Associated codebooks Cy.... 1/2 are creating by solving a least-squares problem using these
fixed codes. However, combining the M original codes into M/2 does not exploit all the degrees of freedom that the scheme offers. We search for a more general subset of size M' of all M (M - 12/2
possible pairs. Inspired from RQ, given a sequence of codes (T' 12 r_...... ..... IM) ) for E Bd and
number M' of target codebooks, we recursively minimize the residuals left from previous steps by searching which pairs of codes (i.j) combine and their combined codebook C":
(1"" C...) = arg min En [ C'(TW(x))))
(8)
c.j.C"
= 0,
Tth nh + C² 1 (x)),,
T
(9)
where the expectation over x taken w.r.t. the empirical distribution of the training data. In this ap- proach, some input codes can be used several times, or not at all. Note that, as in RQ, the codebooks O'm are determined sequentially.
Integration of pairwise additive decoding with IVE. When using a pairwise additive decoder for QINCo2 without IVF, we observe that the first, and therefore most informative, code pairs are of the form (1, i) or (i, + 1), and then progressively include codes (2, i), then (3, etc. The IVF codebook of size KIvF. however, is too large to combine with other codes in our efficient pairwise decoder, since the combined codebook would be of size K x KIVE > K². Therefore, we quantize the IVF codewords using RQ into M new codebooks Õ" Ci,..., C.M each of size K, generating the new codes (x)),..., 7M (æ)) We choose M large enough to obtain near zero error, as the cost of increasing M is negligible for decoding. As we only quantize the IVF codewords, we do not need to store these codes for each æ, but only a mapping from 1 to 72 , i"" which has a size that does not depend the database size. We then train the efficient automatic re-ranking using the codes (x) and (z) together. This pairwise additive decoding ranker then used search time to find a second smaller shortlist Spairs during the search, see Figure 3. See App. B for an example.
4
EXPERIMENTAL VALIDATION
4.1 EXPERIMENTAL SETUP
Datasets and metries. Following Huijben et al. (2024), we evaluate QINCo2 against previous baselines on the four datasets described Ta- ble 1. spanning across various modalities, di- mensions and train set sizes. We use the full training split during training, and use the database split to report the compression per- formance (MSE) on IM vectors, and nearest- neighbor recall percentages at rank I (R@1) among IM database vectors with 10k query vectors. We report recall at ranks 10 (R 10)
Table 1: The datasets used in our experiments.
Datasct
Dim.
Train vees.
Data type
Deepl
Lompinsky 2015)
358
CNN cnb.
BiAANN
(legn al., 2011)
12%
100M
SIFT descriptors
Faoebook SimSeanchNeeer
(FB-suapp)
256
10M
SSCD image euth.
(Smmhad et al,, 2013)
Contrieeer
(Huglon et 2004)
768
20M
Costriever text emb.
and 100 @R@ 100) in Table S4 in the supplementary material; these metrics follow the same trends as those observed for R@1 1. Additionally, for Deep1B and BigANN, we use the 1B database for similarly search to evaluate IVF-QINCO2.
Architecture details. Unless specified other- wise, we use the model architectures listed in Table 2. We use QINCO2-L for all the vector compression experiments (Section 4.2), as we want to see the impact of large models against the best results of other methods. The smaller models used for search experiments, where
Table 2: QINCo2 model architectures.
# res. blocks (L)
emd. dim. (dl)
hid. dim. (da)
QINCo2-S
128
256
QINCo2-M
384
384
QINCO2 L.
384
384

---

Published as a conference paper at ICLR 2025
Table Comparison to state of the art methods for compression (MSE) and retrieval (R Ablation of model improvements w.r.t. QINCO are in italics, and the best results are in bold.
BigANNIM
DeepIM
ContrieverIM
FR-ssappIM
Train time
MSE (x10*)
R@I
MSE
R@1
MSE
R@
MSE
R@1
BigANN
(x10")
OPQ
2.95
21.9
0.26
15.9
1.87
8.0
9.52
2.5
RQ
2.49
27.9
0.20
21.4
1.82
10.2
9.20
2.7
L.SQ
31.9
0.17
24.6
1.65
13.1
8.87
UNQ (Morozov Babenko, 2019)
1.51
34.6
0.16
26.7
&bytes
QINCo (Huijben et al., 2024)
QINCo (reproduction)
1.13
0.12
35.6
20.6
127:38
improved training
1.14
43.4
0.12
33.9
1.39
20.7
8.63
3.8
14:53
improved architecture
1.09
45.9
0.12
36.7
1.38
21.2
8.63
4.0
21:42
condidates pre-selection
1.10
45.5
0.12
36.7
1.38
20.6
8.64
8:23
beam- search
0.85
50.6
0.10
43.9
1.34
22.7
8.18
4.4
57:39
evaluate larger beam (QINCo2)
OPQ
40.5
0.14
34.9
1.71
18.3
7.25
RQ
1.30
49.0
0.10
43.0
1.65
20.2
7.01
5.4
LSQ
0.98
51.1
0.09
42.3
1.35
25.6
6.63
6.2
UNQ (Morozov& Babenko, 2019)
0.07
16 bobyess
QINCO (Huijben et al., 2024)
0.32
71.9
0.05
59.8
1.10
31.1
6.58
6.4
QINCO (reproduction)
0.33
72.4
0.05
59.7
1,13
29.9
6.56
6.6
284:53
improved training
0.33
72.4
0.05
59.5
1.09
31.4
6.54
6.8
37:50
improved architecture
0.31
72.8
0.05
60.7
1.08
30.5
6.54
48:15
condidates pre-selection
0.30
71.9
0.05
61.1
1.08
31.1
6.55
6,8
18:57
beam-search
0.03
67.4
33.6
130:47
evaluate with larger beam (QINCO2)
0.19
79.3
0.03
67.1
1.02
34,0
5.98
7.5
time efficiency matters well. We set A= 16, B 32 during training, and A 32, B 64 during evaluation for all models. When candidate pre-selection is used without beam search (B = 1), we A = 32 during training. We fix the codebook size to K 256, which results in single byte encoding per step. Following prior work, see e.g. (Huijben et al., 2024; Morozov & Babenko, 2019), consider 8-byte and 16-byte vector encodings most of our experiments. We also experiment with 32-byte encoding for large-scale search.
Baselines. We compare QINCo2 against the results of OPQ (Ge et al., 2013), RQ (Chen et al., 2010), LSQ (Martinez et al., 2018), using the results reported by Huijben et al. (2024) which were obtained using the implementations in the Faiss library (Douze al., 2024). We also compare against the neural quantization baselines QINCO (Huijben et al., 2024) and UNQ (Morozov & Babenko, 2019), citing the results reported in the original papers. As we build upon QINCo, we also report scores of our reproduction of this quantizer.
4.2 VECTOR COMPRESSION
Main results. In Tab. we evaluate how QINCO2 improves over QINCo, by gradually introducing the changes to reproduction of QINCo, and also compare other state-of-the-art results. We report the MSE and R@ metrics, as well as the training time for the BigANNIM models. Given the same training procedure, the training time is roughly proportional the encoding time.
In general, our reproduction of QINCO closely follows the results reported by Huijben et al. (2024). When using our improved training recipe (+improved training), observe more than seven- fold reduction in training time w.r.t. QINCO (reproduction), while obtaining similar MSE. When adding our improved architecture (+improved architecture), we observed improved MSE and R@ values across all datasets at both 8-byte and 16-byte compression (except for R 1 at 16 bytes on Contriever), at the cost of increased training time (but still remaining much faster than the QINCo reproduction). Adding candidate pre-selection (A = 32, B = 1) leads to small degradation in MSE and @ in some cases, but makes training more than 2.5 times faster. Enabling beam search (A = 16, B 32) leads to a substantial improvement in MSE and R@1 1. Although this has substantial impact on the training time, training remains more than two times faster compared to QINCO (reproduction). Finally, 32, = 64) than the one used for training (A = 16, B = 32). While not impacting the training time, the larger beam consistently improves the MSE across datasets and bitrates.
a larger beam size for vector encoding evaluation (A =

---

Published as a conference paper at ICLR 2025
1.00
Decoding per vector: 0.08 us
0.315
1
Lm2 Decoding time per vector: 0.09
MSE (BigANNIM)
4
2
MSE (BIgANINIM)
1.3
Lm8 Decoding time per vector: 0.18
Decoding per vector: 0.12 us
[Decoding time per 0.27 ys
0.925
A=8,
B-16
1.-
0.900
0.815
0.850
0.825
107
107
Encoding time per vector (us, log-scale) Figure 4: Pareto fronts of quantization error on the BigANNIM dataset using 8 bytes codes. Left: Models with L = 8 blocks, and each curve using a different number of blocks L,, for pre- selection. Each curve covers models that differ in the number of pre-selected codewords A and beam size B. Models are trained using A = 8 and B E {2,.. ..)) and evaluated with A E {8..... ..4), and B {2,... 128]. Stars show models using A= 8, B = 16 for evaluation. All models have the same decoding speed. Right: models with different number of residual blocks L. For models on one curve, the decoding time is fixed, and the encoding time is varied by changing A and B.
Encoding time per vector (μر, log-scale)
Overall, we obtain results that substantially improve over earlier state-of-the-art results, reducing both the MSE and @@ I metric on all four datasets. For example, compared to UNQ (Morozov & Babenko, 2019) on the DeepIM dataset, we reduce the MSE more than two-fold from 0.07 to 0.03 for 16-byte codes, and improve the R @@1 from 26.7% to 45.1% for 8-byte codes. Compared to QINCO on the BigANN dataset, we reduce MSE from 0.32 to 0.19 for 16-byte codes, and improve nearest-neighhor search accuracy from 45.2% to 52.3% and for 8-byte codes.
Analysis of codeword pre-selection. Figure 4 (left) shows the impact of the candidate pre-selection model depth L, on the MSE as function of the encoding time, for fixed decoding time. For a given number of pre-selected candidates A and beam size B, a deeper pre-slection model (higher L.) reduces the MSE the expense of increased encoding time. However, when varying A, B settings, the models with L. 0 blocks -which just perform pre-selection based on a learned codebook- are Pareto-optimal for all settings with encoding times under ms, thanks to the faster pre-selection of candidates. We therefore use this setting of L, = 0 in all other experiments, relying on encoding parameters A, B to set speed-acee accuracy tradeoffs.
Trade-off's between encoding and decoding time. In Figure 4 (right) we consider the MSE quanti- zation error induced by models with different decoding speeds. For each model, we vary the encod- ing speed using different A, B settings. The quantization error can be reduced with models that are deeper (higher decoding time), and using more exhaustive search for encoding (more pre- pel-selected codewords and larger beam). However, for a given MSE the decoding time can be significantly reduced when compensated by higher encoding time, For example, an MSE of 1.0 can be obtained by model with L 16 residual blocks decoding 0.27 encoding 20ps- which decodes 3x faster at but encodes 50x slower - decoding 0.08ps, encoding 1 ms. These results show that QINCo2 allows trading compute between encoding and decoding, motivating the use of smaller models for large-scale retrieval experiments, where decoding time is crucial.
by L = 1 model
Architecture sweep. To obtain insight into the most effective hyperparameters settings, present the results of a joint sweep over the number of residual blocks (L), the embedding and hidden dimensions (de, da) and the encoding parameters (A, B) in Figure 5, both for training and evaluation, using 8-bytes codes on BigANN. We also include several operating points of QINCO for reference. First, we notice that for a given MSE level. QINCo2 reduces the encoding time by about one order of magnitude compared to QINCo. Additionally, our QINCo2-S model used with A = B = 8 yields substantial improvements both in MSE and speed compared to all QINCO variants. For the operating points on the Pareto front, we notice a certain degree of correlation between the encoding speed (marker shape) and decoding speed (marker color) of the points on the Pareto front, with both increasing while MSE is improved. Note that this is in line with the Pareto front observed in Figure 4 (right). The most expensive encoding settings are mostly used in combination with the heaviest networks, yielding the best MSE results. When traversing the front left-to-right, at first shallow models are more optimal (with depth L=1 or 2). and MSE is improved by expanding the encoding search. Then, the Pareto front enters phase where I. 4 models are optimal and the
8

---

Table 4: Search results using QINCo2 decoder and approx- imate decoders for QINCo2 codes. For each combination of dataset and bitrate, we report the retrieval accuracy over 1M vec- tors, as well as the accuracy of Published as a conference paper at ICLR 2025
1.
Opentt prints Jannena Froms)
AxcBu a
AocB 14
1.-
NCo (2-2)
13-
MSE (BigANNIM)
Lagk Am
1.2
Becoding 1.55pt
QINCO2-5
(L-16)
Becoding
1.3
Du Decoding 3.0..
Dua Recoding
4.0ua
4 Out Decoding ng time s 6.0gt
King And6
6 fun--c Deced time s R.S
1.0
wi soget fust and
tork av
Ohiic modes
QINCOZ-N
phrt phaterra p-p
(A= B
0.9
32 de bagg
(A-8 B-32)
QINCO2-L
(A-8 B-5)
QINCO2
0.8
(A-8
CINCOZ-L
10
10
20
10c
Encoding time (μus, log-scale)
Figure 5: Pareto-optimal front of QINCO2 operating points for MSE and encoding time. Evaluation on 10M vectors, varying the models parameters A, B, L, de and d, when encoding using M 8 bytes on BigANNIM. Models are trained with different A, E {16,32 32), and evaluated with range of values up to A = 64 and B = 32. Marker shape is set according to the product of the encoding parameters x B, and color according to the decoding time, determined by the network depth (L) and width (de, dn). Results for QINCO shown yellow stars for comparison.
BiAANNIM
Deep
RG1
Rakert
RG
Packor 10
QINCo2-5 S (no shoetlist:
47,9
38.1
AQ
12:3
31.5
10.2
26.0
12.1
31.3
10.2
25,6
code-poirs pairs
RQ, w/ optimized code pains
25.2
46.2
36.6
QINCo2 S (no shoetlist
73.2
63.1
AQ
16.6
45.2
164
42.4
RQ
44.4
41.7
QINCO2-S over a shortlist of 10 elements generated by the method.
RQ.
code-poirrs
BQ 32 optimized code palts
35.0
66.9
58.6
search span increases from A x B = 16 to 512. Finally, the lowest MSE and highest encoding times are obtained with depths ranging from 8 to 24, with search spans ultimately reaching Ax B 2, 048.
4.3 LARGE-SCALE VECTOR SEARCH
Approximate decoders. In Table 4 we consider a preliminary experiment comparing a small QINCo2 model with fast lookup-based decoders trained fixed QINCo2 codes, including AQ, RQ and our pairwise additive decoders. The AQ decoder is learned by solving a single large least- squares problem, while the other ones are learned by solving up to 2M successive smaller least- squares problems. We consider the direct recall of these decoders, as well as the recall when using them to establish shortlist of ten elements which is then re-ranked with QINCo2. We observe that the RQ decoder yields only small degradation w.r.t. the AQ which is more expensive to train. When comparing R @@ 1, both of these methods perform much worse though than the QINCo2 decoder, los- ing more than 73% of its search accuracy. However, accuracy is more than doubled when using pairwise additive decoder with 2M pairs. When used to form a shortlist of ten elements, single-code approximate methods still lag behind QINCo2 (12 points of R I for 8-bytes codes, more than 20 points for 16-bytes). But decoding using optimized code-pairs reduces the gap considerably (at most 1.7 points for 8-bytes and 6.3 points for 16-bytes), with minimal computational overhead: ten calls to Foz, compared to a million when using the QINCo2 decoder without shortlists.
Large-scale search efficiency. In Figure 6 plot the search accuracy
function of speed, reported as queries per second on a single CPU, when searching over IB database vectors from BigANN using 8, 16 and 32 byte representations. In Figure S2 in the supplementary material we
9

---

Published as a conference paper at ICLR 2025
BigANN1B bytes
BigANNIB 16 bytes
BigANN1B 32 bytes
10a
101
QPS (32 threads)
10a
107
MF-PQ
MF-RQ
MF-QINCo (L=2)
10
MV-QINCo (Lm4)
QINCo2-5
QINCO2 M
20
R@1
R@
R@1
Figure 6: Retrieval accuracy/efficiency trade-off on the Bigann IB dataset in terms of queries per second (QPS) and recall (R@ I) when combining PQ, RQ. QINCO, and QINCo2 with IVF.
provide similar results when using the DeepIB dataset. We compare PQ and RQ (with beam size = 20) baselines, using their implementation the Faiss library, as well as QINCO models with = and I 4 residual blocks, used in the experiments of Huijben
al. (2024). For QINCo2 we consider two models: QINCo2-S has a depth and width similar to the QINCO (L 2) model, striking good balance between speed and accuracy for settings, whereas QINCo2-M is slightly larger than the second QINCO model, reaching the highest overall retrieval accuracy. We plot Pareto fronts for all compared methods by changing the hyperparameters of the IVF search: the number of IVF buckets that are accessed, the shortlist size(s), and the e efSearch parameter that is used the HNSW algorithm to find the IVF centroids closest to the query.
We find that at the highest search speeds, the PQ and RQ baselines yield the best results, but also that their accuracy quickly saturates low recall values when more compute used. With QINCo2, we are able to attain significantly higher recall values: adding more than 20 recall points for each bitrate the high-compute regime. The search speed which QINCo2 starts to yield more accurate results than the PQ and RQ baselines is generally situated in the range 1,000 to 10,000 queries per second. Compared to the two QINCO models, our QINCo2-S consistently yields higher search accuracy across the full range of search speeds. Among two QINCo2 models, QINCo2-M is generally slower than QINCO2-S, but attains the highest accuracy in the high-compute regime.
5 CONCLUSION
We presented QINCo2, a neural residual quantizer in which codebooks are obtained as the output of a neural network conditioned the vector reconstruction from previous steps. Our approach improves over QINCO in several ways. First, the training procedure and network architecture are optimized, which leads similar results but reduces training time roughly by factor six. Second, we introduce a candidate pre-selection approach to determine a subset of the codewords for which evaluate the QINCo2 network, further reducing encoding and training time roughly by factor three. Third, given the accelerations, we use beam search for encoding and find it can greatly reduce the quantization eπror. Finally, for application of QINCo2 billion-scall nearest neighbor search, we introduce pairwise look-up based decoders to obtain fast approximate decoding of the QINCo2 codes, that are much more accurate than the AQ decoder used in QINCo. We conduct experiments on four different datasets, and evaluate performance in terms of MSE reconstruction and the search speed-accuracy trade-off, using different bitrates for both tasks. On both tasks and datasets, QINCo2 consistently improves over QINCO and other baselines. In particular, 34% for 16-byte compression of BigANN, and push the maximum accuracy for billion-scall nearest neighbor search of the RQ baseline from under 40% to 70% using 16-byte codes for BigANN. Beyond our contributions to implicit neural quantization, we believe it is interesting to explore the potential of our pairwise lookup-based additive decoder for other quantizers in future work.
reduce MSE by
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Kenza Amara, Matthijs Douze, Alexandre Sablayrolles, and Hervé Jégou. Nearest neighbor search with compact codes: decoder perspective. In ICMR, 2022.
Artem Babenko and Victor Lempitsky. Additive quantization for extreme vector compression. In CVPR, 2014.
Artem Babenko and Victor Lempitsky. Efficient indexing billion-scale datasets of deep descrip- tors. In CVPR, 2016.
C. Bishop. Pattern recognition and machine learning. Springer, 2006.
Marlène Careil, Matthew Muckley, Jakob Verbeek, and Stéphane Lathuilière. Towards image compression with perfect realism ultra-low bitrates. In ICLR, 2024.
Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze. Deep clustering for unsu- pervised learning of visual features. In ECCV, 2018.
Yongjian Chen, Tao Guan, and Cheng Wang. Approximate nearest neighbor search by residual 111111199112727 2010.
vector quantization. Sensors,
Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre- Emmanuel Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. The Faiss library. arXiv 2024.
preprint,
Alaaeldin El-Nouby, Matthew Muckley, Karen Ullrich, Ivan Laptev, Jakob Verbeck, and Hervé Jégou. Image compression with product quantized masked image modeling. Transactions Machine Learning Research, 2023.
Patrick Esser, Robin Rombach, and Bjorn Ommer. Taming transformers for high-resolution image synthesis. In CVPR, 2021.
Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. Optimized product quantization for approximate nearest neighbor search. In CVPR, 2013.
Iris A. M. Huijben, Matthijs Douze, Matthew J. Muckley, Ruud G. van Sloun, and Jakob Verbeek. Residual quantization with implicit neural codebooks. In ICMI., 2024.
Hervé Jégou, Matthijs Douze, and Cordelia Schmid. Product quantization nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(1):117-128, 2010.
Hervé Jégou, Romain Tavenard, Matthijs Douze, and Laurent Amsaleg. Searching in one billion vectors: Re-rank with source coding. In ICASSP, 2011.
D. Kingma and M. Welling. Auto-encoding variational Bayes. In ICLR, 2014.
Doyup Lee, Chiheon Kim, Saehoon Kim, Minsu Cho, and Wook-Shin Han. Autoregressive image generation using residual quantization. In CVPR, June 2022.
Shicong Liu, Hongtao Lu, and Junru Shao. Improved residual vector quantization for high- dimensional approximate nearest neighbor search. arXiv preprint, 1509.05195, 2015.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In ICLR, 2019.
James MacQueen. Some methods for classification and analysis of multivariate observations. In
Berkeley symposium on mathematical statistics and probability, 1967.
Yu A. Malkov and Dmitry A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4))824-836, 2018.
Julieta Martinez, Shobhit Zakhmi, Holger H. Hoos, and James J. Little. LSQ++ Lower running time and higher recall in multi-codehook quantization. In ECCV, 2018.

---

Published as a conference paper at ICLR 2025
Stanislav Morozov and Artem Babenko. Unsupervised neural quantization for compressed domain similarity search. In ICCV, 2019.
Lushuai Niu, Zhi Xu, Longyang Zhao, Daojing He, Jianqiu Ji, Xiaoli Yuan, and Mian Xue. Resid- ual vector product quantization for approximate nearest neighbor search. Expert Systems with Applications, 232, 2023.
Aaron van den Oord, Oriol Vinyals, and Koray Kavukcuoglu. Neural discrete representation learn- ing. In NeurIPS, 2017.
Ali Razavi, Aaron van den Oord, and Oriol Vinyals. Generating diverse high-fidelity images with VA-22.-.. NeurlPS, 2019.
Jiwan Sco and Joonhyuk Kang. RAQ-VAE: Rate-adaptive vector-quantized variational autoencoder. arXiv preprint, 2405. 14222, 2024.
C. E. Shannon. A mathematical theory of communication. Bell Syst. Tech. J., 27())379944, 1948.
Harsha Vardhan Simhadri, George Williams, Martin Aumüller, Matthijs Douze, Artem Babenko, Dmitry Baranchuk, Qi Chen, Lucas Hosseini, Ravishankar Krishnaswamny, Gopal Srinivasa, et al. Results of the NeurlPS'21 challenge on billion-scale approximate nearest neighbor search. In NeurIPS Competitions and Demonstrations Track, 2021.
Chuanxia Zheng and Andrea Vedaldi. Online clustered codebook. In ICCV, 2023.
Xiaosu Zhu, Jingkuan Song, Lianli Gao, Xiaoyan Gu, and Heng Tao Shen. Revisiting multi- codebook quantization. IEEE Transactions on Image Processing, 32:2399-22 1112399-2412, 2412, 2023.
A IMPLEMENTATION DETAILS
A.1 QINCO2 ARCHITECTURE
The architecture of the neural network fo, illustrated in Figure 1, is formally described by Eqs. (10) to (13). This network is parameterized by number of blocks L, and dimensions de and dn. At step m, a codeword e E Rdd projected into an embedding space of dimension de (Eq, (10)). Is it then conditioned on the previous reconstruction 2= by concatenating both variables (Eq. (11)), adding a residual connection after the projection. The output is then computed by a sequence of 2-layers residual MIPs (Eq. (12)). A residual connection is added the end (Eq. (13)) to ensure stability.
In the following equations denote by Ld linear layer from dimension d1 to d2, and pd projection from d1 to d2 which is equal to L. These layers are implicitly parameterized by 0. We then express fe (e") as follows:
da di * d2, and to the identity function otherwise.
Gomb puc(("") (c
(10)
30 Cemb + I.d. (Concat (Cebb: & 1m1)
(11)
V: U:-1 - Lo (ReLU (RL (v)
de
(12)
(a m c. = c. P (vI.
(13)
The Ld+d, layer (Eq. (11)) uses bias term, all the others don't.
The number of parameters we use for our models listed in Table 2 increase the number of trainable parameters of up to factor of 4.5 compared QINCo. We include comparison of the number of parameters between RQ, QINCO and QINCo2 in Table S1. As shown in Table 3, the increase in model parameters contributes improvement in MSE (see line improved architecture).
12

---

Published as a conference paper at ICLR 2025
Table S1: Number of parameters of RQ. QINCO and QINCO2 models on BigANNIM.
Model
RQ (1-2) QINCO (L=4) QINCo (1=166 QINCo2-5 QINCo2 QINCo2-L
Parameters 0.26M
1.4M
2.3M
7.8M
1.6
108M
35.6M
A.2 TRAINING QINCo2
We follow the same optimization approach as QINCO (Huijben et al., 2024). Using the loss function C(x, q) = | q I. training QINCo2 amounts to finding the optimal parameters 0, C C'...., C
for the quantization process Eq. (1). This defines the following optimization problem:
(1x, Fo (c' (cc....,.c())
arg min EC MMM
arg min C'EC' ...,."Mcc" ECM
(14)
ECM
where Fg is sequence of M QINC02 models, as defined by Eq. (4). We follow the optimization approach from Huijben et al. (2024) to solve Eq. (14) by alternating between solving the external and inner problems. For each batch, we first solve the inner problem by using our quantization process QQi-B (instead of QRQ for QINCo: see Section 3.2). We then use gradient- based method (AdamW, instead of Adam for QINCo, see below) optimize parameters 0 and C* ..... O.M.
Compared to QINCO, we change the training procedure in the following ways:
Like QINCO we loop over 10M samples per epoch, but with different segment of 10M vectors at each epoch to cover the full dataset. We set aside the same 10k vectors as QINCo for validation.
We reduce the number of epochs to 70, while QINCo can train for hundred of epochs, relying on its scheduler for stopping.
We normalize each dataset with mean of 0 for each feature, and standard deviation of across all features, instead of normalizing to [0; 1].
We initialize the QINCo2 codebooks using noisy RQ codebooks. We train these code- books for only 10 k-means iterations, for each of the M codebook. We then add a Gaussian noise with standard deviation, computed over the RQ codebooks.
x 0.025 where is the per-feature standard deviation
We initialize all the weights of the network using Kaiming uniform initialization, and ini- tialize to zero all biases and weights of the down-projections Id within the residual blocks.
We the AdamW optimizer (Loshchilov & Hutter, 2019) with default settings, except for a weight decay of 0.1 (instead of using Adam).
We use gradient clipping set to 0.1, and decrease it to 0.01 unstable experiments.
We use a maximum learning rate of 0.0008, and decrease 0.0001 on unstable experi- ments (compared to 0.001 for the base learning rate of QINCo).
We use cosine scheduler, with a minimum learning rate of 10-3 times the maximum learning rate (instead of reducing the learning rate on plateaus only).
We increase the batch size to 1,024 on each of the 8 GPUs, for effective batch size of 8, 191 (compared to an effective batch size of 1024 for QINCo).
At the end of each epoch, we reset every codeword that has not been used at all. We reset a codeword from the codebook m using a uniform distribution with the same mean and standard deviation as the residuals quantized by step m, i.e. and from the distribution x -- m- This is similar to the approach of Zheng & Vedaldi (2023) to re-initialize "dead" codewords.
Each of our choices increased the final results in early experiments, except for the reduced number of epochs, which we set to favor training speed. We show the effect of the revised training procedure in our experiments in the following section.
13

---

Published as a conference paper at ICLR 2025
Table S2: Encoding and decoding complexity per vector in FLOPS in "big-O" notation, and in- dicative timings on BigANNIM using 32 CPU cores (in uu) with parameters: D=128; QINCO: L=2. M-8, h=256; UNQ: h1=1024; b=256; RQ: beam size B=5; QINCo2-S: A=8, B=32, d, = 128, dh 256. In practice, at search time for OPQ and RQ rather than decoding we per-
form distance computations in the compressed domain, which takes M FLOPS (0.16 ns).
Encoding
Decoding
FLOPS
time
FLOPS
time
OPQ RQ
d² Kd KMB M(dd
1.5
A(d 1)
1.0
8,3
Md
1.3
+ MK)
I/ + M)
QINCO
K + LN)
823,4
Md(d Lh)
8.3
QINCO2-S
ABMd, Ld.) BKd
2910.7
Md.(d Ld.)
6.2
To train efficiently, we encode each batch without maintaining activations for gradient computation, and then perform another forward hewward-bacwward backward pass through fe using the codes selected by the encod- ing process. This is much faster as in this manner, the forward-bard bawarddbcckward pass is only executed for single codeword per vector per step, rather than for all codebook elements.
A.3 LARGE-SCALE SEARCH WITH FAISS
To implement IVF search with the AQ and RQ baselines we use the Faiss li- brary (Douze al., 2024). 1 The index factory names used for our experiments are IVF1048576 6__NS33,, RQ<BB>x8 B___iint,, where <BB> is replaced by 8, 16 or 32, depending on the number of bytes used per vector. It indicates the use of KIVF = 22 centroids, indexed with HNSW graph-based index (32 links per node), followed by RQ filtering using <BB> bytes. This structure is used to perform the IVF-RQ search, where the codebooks are computed by Faiss directly. For IVF- -FF-QINC2, on GPU before filling this structure with them, as the RQ and AQ decoding function are the same. During evaluation of large-scale search with IVF-QINCO2, Sno shortlist, which is re-ranked using pytorch implementations of pairwise additive decoding, and then QINCo2.
compute the IVF centroids and AQ codebooks and codes
this structure retrieve the
B ADDITIONAL RESULTS
Encoding and decoding complexity. In Table S2 we compare QINCO2 to QINCo, UNQ, RQ and PQ in terms of complexity (FLOPS) and timings obtained on CPU. As our method QINCo2 has variable encoding time depending on runtime parameters, we select values such that 256 for fair comparison with QINCo.
Bitrate reduction. In Figure S1, we show how QINCo2 contributes reducing the bitrate given reconstruction error compared to previous methods. Relative improvements in bitrate increase for lower MSE and higher number of quantization steps. For 8-bytes codes from previous methods, QINCo2 achieves similar error using at least 29% fewer bytes, but for 16-bytes codes, it achieves at least 54% reduction in bitrate.
Acessed from https: http://hhh..ccmmaccoooooooeeeeee wttpm///cccccoooeerrrccooo/cccee
14

---

Published as a conference paper at ICLR 2025
QINCo2-L (16 steps)
OPQ
RQ
UNQ
MSE (BigANNIM)
4.3
4.9
31
71
33
46%
5
6
10
11
12
13
14
15
16
Code length in bytes
Figure S1: MSE QINCo2 and previous methods different bitrates. Dotted lines show the bitrate reduction of QINCO2 compared to previous methods at a fixed MSE.
DeeplB 8 bytes
Deep 1B 16 bytes
Deep1B 32 bytes
10a
104
QPS (32 threads)
10a
102
IVFPQQ
IVF-RQ
IFFQINCC (L-2)
(L=4)
101
QINCa2.S
QINCo2-M
20
25
30
35
4085
40
45
50
55
60
60
65
70
75
80
R@1
R@1
R@1
Figure S2: Search accuracylefficiency trade-off on the DeeplB dataset in terms of queries per
second (QPS) and recall (R@1) 1) for PQ, RQ, QINCo and QINCo2 combined with IVE.
Large-scale search. In Figure S2 we report large-scale search performance on the Deep BB dataset. Overall we find the same trends as those observed for BigANN in Figure the main paper. In particular QINCO2-S strictly dominates QINCO for all operating points, and QINCo2 is able to attain significantly higher recall levels than the PQ. RQ and QINCO basclines.
Dynamic rates. In Figure S3 compare QINCo2 models trained for different numbers of steps M, from up to 16. We evaluate the MSE of these models after m = 1,..., 16 steps. We find that for given the MSE of all models trained for M the findings of Huijben et al. (2024), and makes that QINCo2 trained with large M can be used as multi-rate codec its performance is (near) optimal for usage with smaller codes.
nearly identical. This is in line with
Changing beam size at evaluation. Besides the model size, QINCo2 introduces two hyperparam- eters control the accuracy: the number of pre-selected candidate codewords A and the beam size
15

---

Published as a conference paper at ICLR 2025
train M
train_M
MSE (BigANN1M)
train M-12
train M-16
10
14 16
Quantization step m
Figure S3: MSE for QINCO2 after quantization step m, for models trained with different M values. All models L, 8, de 384, d 384, A 16 and B 32.
Table S3: Pairs generated by our pairwise additive decoder DeepIM IM for 8-bytes quantization, with corresponding MSE each step. indicates QINCo code (I'), indicates a code extracted from the IVF centroid (I*)
Step
AQ IVF
3
6
7
Pair
(1.2)
(3. 4)
(5.
(7.8)
(1. 1)
(2,1)
(3, i)
(4, i)
3.20
2.56
2.23
Step
11
12
14
15
Pair
1)
(6,
(7.1) 1)
(1,2)
(2, 2)
(8.2)
(1,3)
MSE
2,10
2.08
2,06
2.04
2.03
2.02
2.01
2.01
B. The number of evaluations of the QINCO2 network equal to the product x B, and the encoding time during and after training is roughly proportional to this quantity. Note, however, that these parameters can set differently during training, and when using the model for encoding once the model has been fully trained.
In Figure S4 we report the impact on MSE of changing A at evaluation time when using the same model trained with different A, when using fixed beam size of B 16. The results show that regardless of the A used for training, the MSE saturates around A = 24 at evaluation, ensuring that A 32 will yield close-to-optimal results for encoding. In order to obtain the best performance, A = 16 for training is a good choice: smaller values leads to worse MSE, while = 32 does not lead to noticeable improvement.
In Figure S5 we similarly consider the effect changing the beam size during evaluation for models trained with different beam sizes. In this case, we observe that most models lead similar MSE values for a given value of B for evaluation. Only the model trained with B = 2 leads to significantly worse results when using large beams for evaluation, and similarly the model trained with B = 32 yields worse results than others when using relatively small beams for evaluation (B < 16). Overall, models keep improving the MSE when increasing the beam even up to size B = 64 for evaluation. Therefore, it seems good strategy to train models with B 8, and use larger B for evaluation when more accuracy is required.
Pairwise additive decoding with IVF example. We show in Table S3 an example of code-pairs generated by our pairwise decoder (Section 3.3) on the Deep M dataset using 8-bytes quantization. We additionally show the MSE of the reconstructed codebooks each step of this decoder, starting from the reconstruction yielded by the IVF and AQ steps.
Retrieval accuracy with relaxed settings. We show in Table S4 both the exact retrieval accuracy (R@ I), and the relaxed accuracies R 10 and R@ 100 where a request is correctly answered the nearest neighbour is within the 10 or 100 first elements returned by the method. We note that the the ranking between methods stays the same for each metric, but the accuracy gaps are reduced as the metrics get less restrictive.
Latency, Figure and Figure S2, we show the speed of queries as the number of queries per sec- ond, with batched requests. In settings, it might be more interesting to look as latency instead
16

---

Published as a conference paper at ICLR 2025
1.15
B=16 A=2
B- A-4
B=16 A=8
1.10
B-16 A-16
B-16 A-32
MSE (BIgANNIM)
1.05
1.00
0.95
2
12
16
20
24 28
32
40
48
56
64
Candidates at evaluation time (A)
Figure S4: MSE of QINCo2-L models (with number of candidates A, when changing A at inference time.
and 16), trained with five different
1.10
* B-2 Am16
B=4 A=16
B=8 A=16
1.05
B-16 A=16
B-32 A=16
MSE (BigANN1M)
1.00
0.95
0.90
0.85
2
6.668
12
16
20
24
28
32
40
48
56
64
Beam size at evaluation time (B)
Figure S5: MSE of QINCo2-L models (with L 8 and 16), trained with five different beam sizes B, when changing B at inference time.
17

---

Published as a conference paper at ICLR 2025
Comparison state of the art methods for retrieval (R@1) 1, R 10 and & 100). The best results are in bold.
Table S4:
BigANNIM
Deep
ContrieverIM
FB-ssuppIM
R@10
R@100
R@10
R@100
R@1
R@
R@1
10
OPQ
21.3
64.3
95.6
15.1
51.1
87.9
8.5
24.3
50.4
2.5
5.0
11.2
RQ
75.2
64.0
bytes
LSQ
30.6
78.7
98.9
24.5
68.8
96.7
13.1
34,9
62.5
3.5
8.0
18.2
UNQ
39.7
88.3
99.6
29.2
77.5
98.8
QINCO
91.2
84.6
47.4
QINCo2-L
52.3
95.2
99.9
45.1
90.8
99.8
23.1
$1.5
77.3
4.5
11.0
24.2
OPQ
89.3
81.6
18.1
65.8
12.2
16 bytes
RQ
49.1
94.9
100.0
42.7
90.5
99.9
19.7
43.8
68.6
5.1
12.9
30.2
LSQ
49.8
95.3
100.0
41.4
89.3
99.8
55.0
16.2
UNQ
64.3
98.8
100.0
51.5
95.8
100.0
QINCO
71.9
99.6
100.0
59.8
98.0
100.0
31.1
62.0
85.9
6.4
16.8
35.5
QINCo2-1.
of queries per second. To this end, we compute the latency a single query for two operating points on the 16-bytes and 32-bytes BigANNIB large-scale search curves for IVF-QINCO2 and IVF-RQ. To ensure fair comparison, we selected points close to both pareto-optimal fronts, where IVF- QINCo2 and IVF-RQ have approximately the same QPS & @ 1. We use single CPU for timing. On BigANNIB (16 bytes) at point with R@ 1=37 and QPS=2700, RQ has a latency of 10.78ms, and 9. 9.10ms for QINCO2. On BigANNIB (32 bytes) at a point with R@ 1=62 and QPS=350, RQ has a latency of 71. 11,5ms, and 22.25ms for QINCO2. While RQ uses larger parameters for the faiss a less accurate faiss search combined with precise 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 speed with small number of queries.
query achieve this accuracy, QINCo2
18


Reviews:
[{"review_id": "2khOS6Paf4", "reviewer": "Reviewer_sWLT", "summary": "This paper introduces a variant of QINCo which predicts codebooks per step according to the previous encode part. QINCov2 develops many tricks such as a better training procedure, beam search, etc., to improve its performance. Extensive experiments across multiple benchmark datasets demonstrate its superior performance.", "questions": "- Figure 6 demonstrates the retrieval accuracy/efficiency trade-off, but only R@1 is considered. How would the QPS/task accuracy trade-off be affected if a re-rank stage is added to RQ and PQ with relaxed settings such as R@10?\n- Figure 4 only demonstrates the encoding/decoding speed of QINCov2. It is recommended to provide a more comprehensive comparison with QINCo, etc., similar to Table 3 in [1].\n- It is advised to add a latency comparison of the full retrieval pipeline with other methods.\n\n[1] Residual Quantization with Implicit Neural Codebooks", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The proposed method achieves state-of-the-art performance on several benchmarks\n- Extensive experiments demonstrate the effectiveness of each component.", "weaknesses": "- The task scenarios are not convincing. Previous work shows that QINCo [1] has significantly lower encoding and decoding speeds than PQ and RQ, and there is no obvious improvement in the paper. Figure 6 also shows nearly an order of magnitude less QPS than PQ/RQ in the low recall region. The authors should provide more explanation of why improving accuracy at the cost of QPS is necessary.\n- Latency comparison with other methods is not considered in experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BDxLesJ37A", "reviewer": "Reviewer_SSVZ", "summary": "The paper presents QINCO2, an advanced method for vector compression and large-scale nearest neighbor search, building on the QINCO framework. QINCO2 introduces several key enhancements to improve the efficiency and accuracy of vector quantization, including: (i) QINCO2 incorporates codeword pre-selection and beam search, which improve encoding precision without exhaustive evaluations of all codebook options; (ii) an approximate decoder based on codeword pairs; (iii) an optimized training approach. The paper validates QINCO2's performance on datasets such as BigANN and Deep1M, demonstrating substantial improvements.", "questions": "Please refer to Weakness.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. QINCO2’s use of beam search for vector encoding and codeword pre-selection represents a significant advancement over previous methods, optimizing both encoding time and quantization accuracy.\n2. The introduction of a fast, approximate decoder based on codeword pairs offers a novel solution to the computational challenges of large-scale vector search, enhancing speed without a major sacrifice in accuracy.\n3. The paper conducts thorough empirical evaluations across multiple datasets, showing substantial reductions in mean squared error (MSE) for vector compression and improvements in search accuracy compared to the original QINCO and other state-of-the-art models.", "weaknesses": "1. It would be beneficial to compare QINCO2 with other non-uniform quantization methods. Can QINCO or QINCO2 be extended to work with other large language models (LLMs), such as the LLaMA family?\n2. The inference time remains high, especially in large-scale applications.\n3. This method requires multiple heuristics and iterative steps to reach an optimal solution, which makes it appear more like a refinement rather than a groundbreaking improvement over QINCO. Including more mathematical analysis or theoretical proofs would strengthen the approach.\n4. In line 205, you mention that \"$g$ uses the same architecture as $f$.\" Did you experiment with alternative architectures for $g$?\n5. In Figure 2, you note \"Keep A candidates for each beam.\" Did you consider keeping a single candidate set for multiple beams?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ylkdz6tkfA", "reviewer": "Reviewer_WeRp", "summary": "QINCo2 is a deep-learning based vector quantizer that improves off of QINCo. The basic idea of both is to extend the idea of residual quantization (RQ) via deep learning. RQ is a greedy approach that quantizes a vector by doing each successive codeword selection to minimize the assignment loss so far. The QINCo family of quantizers adds a neural network that adapts the current codeword depending on the quantized representation so far, i.e. if $\\hat{x}_i$ is the quantized representation of $x$ after $i$ codes, RQ does $\\hat{x}_i=\\hat{x}\\_{i-1}+c_i$ while QINCo does $\\hat{x}_i=\\hat{x}\\_{i-1}+f(c_i,\\hat{x}\\_{i-1})$ with learned $f$.\n\nThe main improvements from the original QINCo are:\n1. Faster encoding by leveraging a faster, approximate $f$ to generate initial quantization candidates, and only re-ranking the top candidates with the full $f$.\n1. Beam search during encoding, to make up for quality loss from approximate $f$ above.\n1. Slight tweaks to model architecture and training hyperparameters.\n1. Using a pairwise codebook procedure during decoding so that the vanilla additive decoder more closely resembles QINCo's implicit codebook results.", "questions": "1. A detailed description of an ANN use case that clearly benefits from QINCo2 would strengthen this paper. This paper currently shows that QINCo2 outperforms other quantizers at iso-bitrate in terms of quantization error, but pays more in terms of decoding cost. It could perhaps be argued that using other quantization methods to compress the vectors, and storing such compressed data on a cheaper storage medium (ex. flash) could perhaps beat QINCo2 in both storage cost and decoding cost. Quantifying whether or not this is the case would be very useful.\n1. Source code?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. Figures are well-crafted and make the paper easy to understand\n1. Extensive empirical results that break down the effect on quantization quality and encode/decode time for each adjustment relative to QINCo", "weaknesses": "1. Lack of source code release: considering these are fairly small models trained on open datasets, releasing code for reproducibility shouldn't have been difficult.\n1. Limited novelty: this work only only suggests a minor change to the QINCo idea.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wwuybbhwdE", "reviewer": "Reviewer_xDMj", "summary": "QINCO2 is an improved version of the original QINCO model for residual MCQ. It improves search efficiency in large datasets and reconstruction error. Both methods use neural network to dynamically adapt codebooks after each step of residual quantization. Instead of static codebook (conventional RQ), QINCO2 (and QINCO) uses neural network to adjust the codebook based on the current approximation and base codebook values. The network inputs the residual vector and partial reconstruction and produces centroids that more accurately encode the residuals. The original QINCO dramatically increased computational complexity of the quantization process and memory usage.\nQINCO2 improves encoding speed by introducing codeword pre-selection which narrows down the search of centroids. It uses another neural network of smaller parameters to calculate top $A$ candidates (among possible centroids) which is further used for adaptive quantization. Furthermore, QINCO2 applies beam search to improve quantization quality by exploring multiple encoding paths in parallel, which helps to minimize the quantization error and refine the encoded representation more accurately.\nTo address the high computational cost during decoding, QINCO2 introduces a pairwise additive decoder, which enables faster approximate decoding by combining pairs of codewords, effectively capturing dependencies between codewords", "questions": "N/A", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- Proposed method significantly improves quantization error and retrieval accuracy\n- It is faster for retrieval tasks, which is important for industry scale applications", "weaknesses": "The theoretical contribution is rather low. Authors mainly engineered existing methods together to improve inference of the model.\nThe paper is very hard to follow, it is not completely clear why introducing another neural network for pre-selection can speed it up (furthermore, increasing training training time)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ANDPRTkT8N", "reviewer": "Reviewer_tRnB", "summary": "This paper enhances QINCo in both the encoding and decoding processes. To tackle the significant complexity of encoding, the authors introduce codeword pre-selection and beam search strategies, which improve encoding efficiency and approximation capabilities. Additionally, to mitigate the limited search accuracy of the AQ decoder, the authors propose a fast approximate decoder based on pairwise additive code, which creates accurate shortlists for fast searching. Experimental results demonstrate that QINCo2 improves both efficiency and search accuracy.", "questions": "1.\tThe dataset names in Table 3 should be consistent with other results in Sec. 4.2, i.e., BigANN1M, Deep1M, Contriever1M, and FB-ssnpp1M.\n2.\tA little confused on the “2M successive least-squares problems” in RQ-based codebook approximation (mentioned in Sec. 4.3), as there are only M steps in RQ.\n3.\tThe R@10 and R@100 results of QINCo2 are not included in this paper, despite the authors' claim in Section 4.1 that recall percentages at ranks 1, 10, and 100 have all been considered.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe proposed method seems concise and effective, especially in speeding-up the QINCo encoding and searching process.\n2.\tThe pairwise additive decoding looks like an effective tool to create more accurate approximation of non-independent neural codebooks.\n3.\tThe experiments and analysis are quite extensive and the improvements are significant. \n4.\tThe paper is well-written and easy to read.", "weaknesses": "1.\tIn Table 3, “Improved Architecture” slightly improves the search accuracy on BigANN and Deep datasets with lower vector dimension. Since the performance of original QINCo is largely affected by the network scale, the question is whether the “Improved Architecture” in QINCo2 affects the performance by improving the network parameters. It is better to provide the comparison of parameters.\n2.\tCompared to the original QINCo, the “Improved Training” approach used in this paper incorporates more training samples. Results in Table 3 shows that the introduction of large training set brings limited performance improvement. With a fixed training epoch of 70 and the sequential acquisition of each 10M splits, wonder if the model achieves optimal convergence with such a large training set.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)