Revisiting Multi-Codebook Quantization
Authors: Xiaosu Zhu
Jingkuan Song
Lianli Gao
Xiaoyan Gu
Hengtao Shen
Venue: NeurIPS 2021 Submitted (2021)
Keywords: Multi-Codebook Quantization
Approximate Nearest Neighbor Search
Retrieval

Abstract: Multi-Codebook Quantization (MCQ) is a generalized version of existing codebook-based quantizations for Approximate Nearest Neighbor (ANN) search. Therefore, MCQ theoretically has the potential to achieve the best performance because solutions of other codebook-based quantization methods are all covered by MCQ's solution space under the same codebook size setting. However, finding the optimal solution to MCQ is proved to be NP-hard due to its encoding process, \textit{i.e.}, converting an input vector to a binary code. To tackle this, researchers apply constraints to it to find near-optimal solutions, or employ heuristic algorithms which are still time-consuming for encoding. Different from previous approaches, this paper takes the first attempt to find a deep solution to MCQ. The encoding network is designed to be as simple as possible, so the very complex encoding problem becomes simply a feed-forward. Compared with other methods on three datasets, our method shows state-of-the-art performance. Notably, our method is 11×-38× faster than heuristic algorithms for encoding, which makes it more practical for real scenery of large-scale retrieval. Our code is publicly available: https://github.com/DeepMCQ/DeepQ.

Revisiting Multi-Codebook Quantization
Anonymous Author(s)
Affiliation Address
email
Abstract
Multi-Codebook Quantization (MCQ) a generalized version existing codebook- based quantizations for Approximate Nearest Neighbor (ANN) search. Therefore, MCQ theoretically has the potential to achieve the best performance because so- lutions of other codebook-basd solution space under the same codebook size setting. However, finding the opti- mal solution MCQ is proved to be NP-hard due its encoding process, i.e., converting an input vector to a binary code. To tackle this, researchers apply constraints to it to find near-optimal solutions, employ heuristic algorithms which are still cine-conuuiing for encoding. Different from previous approaches, this paper takes the first attempt find deep solution MCQ. The encoding network is designed to be as simple as possible, so the very complex encoding problem becomes simply a feed-forward. Compared with other methods on three datasets, our method shows state-of of-the-ar art performance. Notably, our method is 11x-38x faster than heuristic algorithms for encoding, which makes it more practical for real scenery of large-scale retrieval. Our code is publicly available: /ttps://gitain www/DeeppCO/Deeeeeeeeeeeeeeee /Deep
3
quantization methods are all covered by MCQ's
5
10
11
12
13
14
15
16
Introduction
17
Rapidly increasing multimedia contents in recent years raise an urgent request for retrieval in short time. Unlike the exhaustive routine [3T 20). Approximate Nearest Neighbor (ANN) search significantly reduces retrieval time while preserving high recall. It has been widely applied to various scenarios, such as database indexing, fast image retrieval, and recommender systems.
19
21
22 As typical approach, vector quantization (VQ) 7 is at first developed as a compression technique, which uses codebook to approximate vectors. People further find the power of VQ to preserve 23
24 similarities between quantized features and enable VQ to perform ANN search. In order to achieve low quantization errors with limited codebook size, a multi-codebook structure introduced. The Quantization (MCQ) (2) describes the approach as combination 27 of one codeword for each sub-codebook, and previous methods [9] 19 30 TO are summarized
25
26 proposal of the Multi-Codeban
28 as exceptional cases of MCQ or constrained MCQs. The quantization codes are designed to be
29
compacted, which results in negligible storage cost and high-quality results.
30 However, the optimization of MCQ without any constraints is formally NP-hard. 14 models the minimization several fully-connected Markov Random Fields (MRFs). As result, 32 current researches aim at solving MCQ under acceptable computational costs. Other than applying
31
33 constraints on it [34 [5], another approach designs algorithms in heuristic way 2 16]. The
34 latter achieves better performance but suffers from slow encoding.
There chances employ neural networks' power to solve MCQ, where people expect obtain higher performance and encoding efficiency than previous methods. [II 28 33 27 already give the way treat codebook network parameter and update it by gradient-descent, but they
36
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

38
all still under constraints that hinder performance. Morozov and Babenko [18] and Sablayrolles er al. [22 map datapoints learned space, which are not flexible, especially when performing the reconstruction. Therefore in this paper, we give our first attempt to solve MCQ in a deep learning approach, without constraints and work-arounds. Our contributions can be summarized as three-folds:
39
40
41
42
Our novel approach, Deep Multi-Codebook Quantization (DeepQ), fully considers encoding difficulty and time complexity in MCQ. With the high efficient and parallelized encoding networks, our method significantly reduces encoding time.
43
44
45
To tackle the NP-hard encoding problem and con-differentiable gradient estimation, we employ and further revise policy gradient method. is proposed to speed up convergence in the training phase.
Proximal Policy Optimization (VC-PPO)
47
48
Experiments conducted on a benchmark dataset validate our proposed method. Furthermore, to evaluate the scalability of the method, it is tested on million-scale datasets to show the effectiveness of our proposed algorithm.
49
50
2 Related Works
51
Vector quantization is a routine to approximate vectors by codebook. Typical applications include clustering, compression, and Approximate Nearest Neighbor (ANN) search. The famous proposal k-means 171, also known Lloyd's algorithm [13], clusters the dataset into uniformly sized convex cells. When it is applied to ANN search, datapoints from the base set are quantized into their nearest centriods and represented by indices. The distance from given query to any datapoint is approximated by the distance from the query to the datapoint's s centriod, which is effectively pre-computed and stored in lookup table. To perform gra-ggrined clustering as well reducing the space and time complexity, they 9 6 k-means in each subspace concurrently. Meanwhile, the introduced sub-codebook structure reveals the prototype of MCQ. Formally, 2 gives a well definition of MCQ, and previous works are all summarized into constrained MCQs. Specifically, subspace i--maans must keep orthogonality among sub- codebooss..... Zhang et al. (34) loosens the orthogonality constraint, but sub- cub-codebooks are still orthoooal Chen et al. 4 and Martinez et al. (15] propose hierarchical k-means, where vectors are quantized coarse-to-fine If constraints are moved, MCQ is not easy to solve. Current state-of-the-ar methods develop heuristic algorithms to help to encode. Specifically, Babenko and
53
55
56
57
59
19 10 30 divide the feature space orthogonally by performing
80
61
62
63
64
85
66
67
Lempitsky 2 employs beam search, Martinez et al. [14, [6] give algorithm based on Iterated Conditional Modes (ICM). However, the above methods do not achieve satisfied time complexity in encoding yet.
68
When neural networks and gradient descent become a fashion, few attempts to integrate quantization 71 into deep retrieval networks are proposed. Klein and Wolf [T]] and Song el al. (5] propose Deep
70
72 Product Quantization (DPQ) and Deep Progressive Quantization (DPgQ) which update codebook by
73 soft relaxation, but they are still under the same constraints as (9 [3]. Sablayrolles et al. [22) and
74 Morozov and Babenko [8] give pipelines encode compact representations for compressed-domee
75
search, but they do not strictly follow the paradigm of MCQ.
3
Preliminaries
76
Given a vector a E R.D, its quantized vector á are composed by several codewords in a codebook
77
78 C. More Specifically. C. (Cm), Cm E kxD 1 < m <. M contains M sub-codebooks and K
79 codewords for each. Quantization codes are formed by b = (bm), bm E 21,2..... K}. 1 < m <
M. which indicates the picked codeword in each sub-codebook. For the whole training set X = {x}
81 with N datapoints, MCQ aims at finding the optimal quantization codes B = {b} and codebook C
82 to minimize following objective:
min E. C.B x DEB
Q
min
E x
C mbb...
C.B
DEB
83 where Cmb.,, E 2 is the -th codeword of the m-th sub-codebook. The sum of picked codewords 84 Σ Cmbb.,, tries to approximate æ. C' and are stored for further retrieval. Some of the previously
mentioned methods [9] 6 4 15 34 are treated as constrained MCQs, as they are all represented

---

86
Therefore, 8, or proposed IndepNet is illustrated in Figure We first build a basic structure called IndepBlock and duplicate this block for M times as 8,, f2 ,0 We try to keep the basic structure really simple to achieve high efficiency during as special cases of ( Specifically, when M 1, becomes VQ. Or if any two sub-codebooks C, Cj are orthogonal, it will be PQ OPQ.
87
88
The optimization of T without any constraints is proved to be NP-hard 14] To tackle this, we propose a Exxpectatonn-Maxiiizatii style solution. Following sections will explain the deep neural network for encoding (Section 4.1). the way to solve C' (Section 4.2) and how to conduct retrieval
90
91
(Section 4.3 respectively.
Methodology
92
Lincer liser
4.1
Expectation: Encoding B with neural networks
FC
ReLl
LN
ReL activation
Layeeoarm
Laue-Group
Our first step, is to find potential code b by given and fixed C. A policy parameterized by 0 is employed to 96 take possible solution by feeding æ:
94
Silp-coneccian
(mm) π (x 0m). 1s mmmSA M.
(2)
More specifically, π produces M Categorical distribu- tions Categorical((* Pml. the probability pick the j-th codeword in the m-th 99
Sample
98
Pmk), where Pmj is
IndepBlock 9,
100
sub-codebook. A potential encoding bm is generated by drawing samples from Ty. which then helps us to pick codeword Cmb... Therefore:
101
pinky
102
bm ~ Fm (xc mm) = Categorical(K, Pm.
(3)
Dibbu
Since the independence among different sub-codebooks is a prerequisite of MCQ. bn should be drawn from Tm independently. Intuitively, the probability of to be specific b* is derived by conditional independence:
M--nndoBooela Indep
104
105
Figure 1: Our proposed IndepNet for producing probabilities of choosing each codeword. IndepBlock is duplicated for M times without shared parameters, in order to keep independence between dif- ferent IndepBlocks. Categorical distribu- tion is built upon output from the Indep- Block. Then, quantization code bn as- sociated with sub-codebook C'n. is sam- pled from distribution.
106
M
Pr (r = II Pr (bm =bn) m=1
II Pmo:. m=1
(4)
107 We adopt the power of neural networks to model Tm- Specifically, 8n produces K unnormalized log- probabilities fm and Pmj is obtained by Softmax. To 110 keep the independence, Om will share parameters with each other.
109
113
115 training and encoding. As the figure shows, IndepBlock is an hourglass network contains 6 layer-
groups (consists of linear layer with ReLU activation and nayer-normalization) with skip-connections.
117 The last three outputs are concatenated and further fed into a final linear layer with K outputs as Lm (bmls-... kmk), and therefore:
118
Pmj Softmax (em), where lm 6m (x).
(5)
4.1.1 Gradient estimation
The objective of training 0 is formed as:
min
E xEX b--
Q (xx, C)..
(6)
However, the optimization faces two problems: 1) The encoding of involves sampling from discrete 122 distributions, which is con-differentiable, 2) All possible encoding of O (K.)). Exhaustive search becomes impracticable.

---

124
Therefore, gradient estimation over discrete, stochastic computation graph is required to train B. include score function gradient estimator, pathwise gradient estimator, etc. Meanwhile, minimizing (6) is also faced with the high-variance problem during gradient estimation. To tackle this, the advantage function is introduced [22 25]. Specifically in our work, value network called QENer parameterized by is proposed to model value function
125
Mainstream methods [23 32
127
V (+I It performs a regression task to minimize the following objectives:
129 V
min
E
[Q (x, b, C 7)112-
IEE
( 0)
Advantages Å is then estimated by
À (x. C) ((r,b,
(8)
The detailed architecture of QENer is shown in Figure 132 We reuse the IndepBlock to generate v by M + blocks: (T TM ) Specifically, latent representation 134 for each selected-codewoodd mbn. is obtained by:
km Tm (C
M*Sub Codebooks
Mix IndepBlecks
The last IndepBlock Tu introduced transform æ. Then, 136 all the outputs from IndepBlocks are summed up to get scalar value (denoted as "reduce-sum").
135
Codebook
137
IndepBlock
Reduce-sum
V sum(41 LMM 4x)
(10)
Figure 2: Our proposed QENer for ad- vantage estimation. First M Indep- Blocks fed by M selected codewords and the last one is fed by æ. Outputs are summed up to get scalar value v.
138
Value-corrected proximal policy optimization We
139
propose a variant of score function gradient estimator called Value Corrected Proximal Policy Optimization (VC- PPO) based on PPO to get simple but efficient Trust Re- gion updates 26 24 In the real scenario of large-scale ANN search, the training size N is usually larger than 10k. Conventional PPO still does not satisfy revise and propose the Corre-Codeetted PPO (VC-PPO) to achieve fast training. Firstly in the sampling stage, b, and v. is produced from datapoint over whole training set X by freezing current policy network and value network as O,, Toi
141
143
us due the speed of convergence. Therefore,
145
by (xr 0o) to (x, bo. C To).
(11)
147 The probability of producing the sampled b, is denoted P. Pr (b, 2,,,), calculated by equation 4 Finally, our surrogate objectives of VC-PPO is defined as [8:
148
Pr x; 0) A,
Co = =min
Pr x, 0.)
(12)
(b x. 0)
clipl 1+c
A
Pr (bo 0.0.))
149
C, = max ((Q b., C*) (x, b.. C 1)) |
(13)
(Q (x, b.. C) - clip (V (z, b. C C - -) v.))
150
Here, The clip (-) forces the policy and value to be not too far from old ones and c is the clip-range. In both equations, prevents a large update ratio leading an unstable policy. The key difference between the original PPO and our VC-PPO is, we use V (x, b.. C | other than the recorded old value v, from sampling stage to estimate advantage. This modification is treated as value-correction process. Correcting value leads to precise estimation on advantage, which is based two reasons:
151
152
153
155 a) Biases are introduced into advantage estimation we use Uo. since the policy is getting better and
better during training but To is froze, and 2) The calculation of V (x, b., C' can be done instantly

---

157
without introducing significant computational overhead. To further encourage the network choose codewords uniformly, a regularization is applied maximize the entropy of x:
158
M
K
Pmj log pmj
(14)
159
which forces network to try more codeword combinations.
180
4.2
Maximization: Solve C' by least-squares
To give the closed-form derivation of solving C' by given X and We will firstly rewrite Equation
162
① to matrix formulation. Since b = (bI, b2 ... bM) and bn {1,2. ........ K} is the index of selected codeword in the i-th sub-codebook, one-hot encoding and a concatenation on each b
163
by one-hot(bm.) b' (b)... bym) will convert the quantization code to a M-hot vector i.e.
184
165
vector that contains M segments, and each segment contains exactly one and remaining O, where
C
C2
166
is the entry of picked codeword. Correspondingly, a reshape applied to C: C'
C
(MMXK)XD
will become:
min X - B'C
(15)
This equation is formally a linear least-squares regression, where B' {0, 1] is known 169 and X target. Although there is a bunch of algorithms to solve it, we finally choose gelsy (Р] which in experiments shows the best results. The solution is to first apply QR factorization with column permutation on B':
171
Ru
R12 PT R
B'=QQ
(16)
R1
R12
172
where Q and
R22
is the factorization matrix and P an orthogonal matrix that
173 permutes columns of until R1 is well-conditioned (its estimated condition number approaches
0). With the permutation, Ro2 becomes negligible. Moreover, R12 is erased by another orthogonal
175 transformation:
RR11
R12
R11 0
R12
T 0
0) Z
(17)
0
176
where T and Z are from the orthogonal transformation of R. Then, C' is derived by:
Tı (Ti
0
B' = Q
ZPT,
(18)
T ( x
C C' PZT
177 where Q is the top rank(B') (B') columns of Q. In brief, overall training approach is summarized into algorithm I
179
4.3
Fast retrieval
After training, we are able to encode the base set for retrieval. Other than sampling from codewords are simply rolled out by greedy assignments:
181
b% = arg max (x:).
(19)
182 We firstly use the greedy roll-out strategy to obtain in the training set in order to solve the final codebook. Then, we employ the same strategy to encode the base set.
5

---

184
To further refine assignments, we add an extra step that randomly selects and alters b, while fixing others:
185
6 t arg min Q (æ. b,, bC
by
(20)
MI
188
Since this refinement only causes negligible overhead referred the implementation by 14. in practice, we benefit from it not only to get lower quantization error but also to obtain acceptable performance from a fast training, Le.. training within a very few steps before the network converged.
187
188
189
The encoded and refined base set, combined with the codebook, is finally employed for retrieval. The LSQ-style lookup table [14) is utilized to speed up similarity search.
190
191
4.4
Discussion
Algorithm 1: VC-PPO for Training
192
Our work aims at solving Multi-Codebont Codebook Quanti- zation via neural networks. Similar works include
Inputs:
Training set X, max step T. hyper-
195
194
Unsupervised Neural Quantization (UNQ) [18] and
parameters a, c, learning rates 1h, 72-
195
Spreading Vectors [22]. But ours has several key advantages compared to previous works: 1) Unlike UNQ, which reconstructs features by an encoder- decoder structure, we follow the paradigm of MCQ to directly give binary codes and codebooks for the benefit of speed and storage, for UNQ needs extra decoding stage during retrieval. 2) UNQ and Spreading Vectors both project original features into a learned space. Although similarities between features are preserved, they still have biases in quan-
Outputs: Policy æ. Initialize codebook C, parameters @ and T;
196
i f- 0:
197
while <
/* Training loop +/
199
for x in X do
/* Sampling stage */
201
Sample b, ~ т (x 0,) into B; Compute vo. Po into V. Pr; end for b. to: Po in X,B.V V, Pr do
203
204
205
tized results. This causes several issues, especially when we want to perform reconstruction to ap- proximate original features, e.g. data compression.
/* Updating stage */
208
T 71 V V.C.;
207
Compute Å by
Compared to LSQ [4), the state-of-the-art heuris- tic algorithm, our work is the first to tackle MCQ in 209
t 0 + 7/2 Vo Lo ta
end
deep learning fashion. The policy network is de- signed to be very simple to get fast encoding speed and comparable retrieval performance.
C' -- Solved by 15 ~ (8
211
+ i +
212
end return π (- ())
Experiments
213
Our proposed Deep Multi-Codehook Quantization (DeepQ) is compared against the state-of-the-arts on a visual-feature dataset (LabelMe22K) to evaluate retrieval performance and encoding speed. Then, we scale up make comparisons on commonly used large-scale datasets (SIFTIM and DEEPIM), whose base sets include 1 million vectors for retrieval. Furthermore, ablation study on SIFTIM investigates the effectiveness of each component our proposed pipeline.
215
216
217
218
219
5.1
Datasets and evaluation metrics
LabeIMe22K 29 This dataset collects images by the LabelMe annotation too T and uses Convolu-
221
tional Neural Network (CNN) to extract them into 512-d features. It has 22, 019 vectors for training and 2, 000 vectors for test.
SIFTIM and DEEPIM Both datasets contain 104, 103, 10 vectors in query, training and base Feature Transform (128-d)
223
224 set, respectively. Vectors from SIFTIM is extracted by while DEEPIM contains 96-d vectors from outputs of CNN.
225
http://corpus-teeeeeee www.:peeeteeeeeeeeeeeeieeeeeeeee

---

228
@ (1, 10, 100) and quantization error are adopted as evaluation metrics, These two metrics indicate not only the retrieval performance but also the reconstruction accuracy. Because LebeIMe22K does not have base set, its training set is adopted as base set. We train on the training set, and then encode the base set for evaluations with queries. When calculating recall, groundtruth defined as the nearest neighbor of each query in the base set (sorted by 12 distance). As for quantization error, the average value of Q (xx b, C) is reported over all æ in the base set.
227
229
230
231
232
We compare our proposal with both shallow and deep methods, including three classic quantiza- tion: OPQ 6 SQ [5] and LSQ++ [14 [6] (denoted as LSQ for simplicity. Also, these two in
233
our experiments have similar performance), as well as three graident- based methods: DPQ [I]]
234
235
DpgQ [5] and DRQ (28). DPQ and PQNet [33] have basically the same architecture that extend
236
PQ with gradient- so we only report the performance of DPQ. Additionally, UNQ [18] is
237
also included, although they introduce an extra decoder and re-ranking trick for retrieval.
238
5.2
Implementation details
239
Our method is implemented with Py- the popular deep learning package in Python. Codebook C' is solved by Intel MKL. that has been fully optimized for speed. As for net- work training, we adopt Adam opti- mizer with AMSGrad [21] and hyper- parameters are tuned by grid search. Specifically, learning rates 1/1 = 7/2
Torch [
240
LabelMe22K
Method
32 bits
64 bits
242
R@D
R@ 10
R@ 100
R@l
R@ 10
R@ 100
OPQ
18.70
57.25
90.10
32.30
80.40
98.00
244
SQ
18.45
57.60
90.85
32.65
82.05
99.05
LSQ
21.20
60.85
94.35
36.45
86.25
99.15
246
DPQ
8.60
32.80
77.50
15.35
48.75
90.75
248
2 X 10-4, with an exponetial learning
DPgQ
19.85
57.80
90.70
35.05
84.10
98.90
rate decay 7 0.9999. Batch-size in updating stage is 2000, while other hyper-parameters e 0.2, a 0.05. Additionally, during training, we in- sert dropout layers after every layer- normalization in all layer-groups to tackle overfitting. More detailed set- tings as well as specifications of In- depNet 0 and QENet T on each dataset (LabeIMe22K, SIFTIM, DEEP IM) can be found in supplementary material.
DRQ
9.65
34.15
80.15
30.75
77.35
97.10
UNQ
22.25
61.20
89.30
37.10
85.55
98.80
250
Ours
24.45
69.05
97.65
39.60
87.60
99.80
252
Table 1: Recall(R) @ (1, 10, 100) on LabelMe22K dataset (%). Ours outperforms of by least 2.20%. 7.85%, 3.30% (32 bits), and 2. 2.70%, 1.45%, 0.65% (64 bits), respectively.
253
254
255
256
257
258
As for quantization code-lengths, K 256 codewords for each sub-codebook and M = {4.8) sub-codebooks are employed in total. We follow [2] to report "effective" code-lengths (additional lengtt for storing ||a||| for lookup table is ignored). Therefore code-lengths become (32, 64) bits, respectively.
280
262
For fair comparison, experiments are conducted single machine, equipped with Intel Xeon E5- 26783 CPU, 256 GiB RAM, and NVIDIA RTX 3090 GPU. For other methods, we re-run on all datasets under unified settings with implementations provided by the authors.
264
5.3
Comparisons with state-of-the-arts
287
Under the small training set and base set settings on LabeIMe22K, we get the results placed in Table I Our method takes the highest recall on this dataset, outperforming the state-of-the-art by 2. 2.20% 7.85%, 3.30% on 32 bits for R @ 1, @ 10 and R@ 100. also outperforms the best competitor by 2.70%, 1.45%, 0.65% on 64 bits. In brief, All methods except for UNQ are generally split into three styles: 1) like: OPQ and DPQ. 2) SQ-like: SQ. DPgQ and DRQ. 3) MCQ: LSQ and ours. Generally, DPQ, DPgQ, and DRQ achieve similar results compared to their shallow versions. However, since they are still constrained MCQs, they show worse performances than 3).
269
271
273
274
The performance of LSQ is worse than ours, shows the effectiveness of neural networks for modeling the MCQ encoding problem. As for UNQ, it takes several extra tricks i.e., another network for decoding and re-ranking in retrieval. Although it beats LSQ, our network still shows the power of
275
276
277
MCQ to win the competition.
https://pytorch.oo org/
7

---

SIFTIM
DEEPIM
Method
32
64 bits
bits
bits R@
R@1
R@10
R@ 100
R@1
R@ 10
RØ 100
R@
R
R@100
R@1
R@ 100
OPQ
5.34
22.03
56.72
22.84
60.27
92.19
3.07
16.39
48.40
15.31
50.06
87.96
SQ
9.45
34.88
70.07
24.41
65.48
93.17
6.41
26.79
70.25
19.95
56.31
91.27
LSQ
11.43
40.48
80.52
33.23
78.37
98. 72
7.29
28.96
72.93
21.12
61.47
93.98
DPQ
5.41
22.97
58.57
21.87
59.39
91. .6
1.59
8.96
33.09
9.53
33.45
72.80
DPgQ
9.71
35.03
74.19
27.96
69.98
96.04
6.36
26.16
70.02
18.98
55.80
90.95
DRQ
1.40
8.87
35.27
18.56
53.06
88.45
4.48
22.46
62.57
16.10
52.76
89.31
UNQ
10.01
33.92
73.39
26.37
69.15
95.99
5.19
23.55
65.09
16.12
52.06
90.10
Ours
11.02
37.73
76.79
28.02
70:22
96.43
7-43
30.03
72.48
20.87
62.06
94.07
Table 2: Quantitative comparisons with state-of-the-arts on SIFTIM and DEEPIM datasets. Recall(R) @ (1, 10, 100} are reported (%). Ours shows comparable performance with stact-of-the-arts on SIFTIM, while achieving the highest recall in most cases on DEEPIM.
278
5.3.1
Large-scale retrieval performance
279
Our evaluations on SIFTIM and DEEPIM datasets presented Table The training set and base set are scaled up, and retrievals on these datasets become more difficult. We observe expected results on two datasets. Compared to our main competitor, L.Q,, our method achieves comparable SIFT IM, and outperforms LSQ on DEEPIM, 1M in most cases. Our method achieves higher recall on DEEPIM than SIFTIM. A potential reason is that DEEP IM is under a nearly normal distribution that, in practice, is casier to converge than SIFTIM, which has larger variance between datapoints. The performance of UNQ in our experiments is lower than expected, possibly due to
281
performance
283
285
different dataset settings.
287
Another key advantage of our method is that, different from shallow methods, which are hand-crafted algorithms that find possible solutions manually or with constraints, our DeepQ encodes vectors by only a feed-forward.
289
290
5.3.2
Encoding efficiency
200
291
In order to verify the encoding efficiency of
100
our method, evaluations of encoding time
293
SIFTIM with the 10 base set are conducted
Toal time (Jogaritam,
50-
QNN
1.9)
DPQ
DPsQ
by checking the total time spent. All of them are run under GPU-acceleration. Additionally, evaluate the time with and without the extra codewords refinement that introduced in section
295
20-
297
4.3
(128 bits results are simulated). As Figure shows, our network is significantly faster than LSQ since it needs to perform local search it- eratively for 25 or even 100 rounds. Specifi-
299
3
301
302
cally, to encode SIFTIM base set, LSQ takes 52.84s. 96.99s, 256.866 and 639.18s for 16, 32,
Code-length (bit)
303
304
64 and 128 bits respectively. By contrast, our method takes 4.46s. 5.46s. 8.26s and 16.64s, which is 11.8x, 17.8x, 31.1x and 38.4x faster than LSQ. Moreover, our method is even faster than most of the constrained MCQs. We also notice that the refinement takes negligible over- head. Although UNQ takes the fastest encoding speed, it still needs to decode and re-rank during retrieval, which slows down its retrieval speed.
Figure 3: Total encoding time w.r.t. code-length on SIFTIM dataset. For 128 bits, we illustrate the simulated results. The variant Ours* removes ex- tra refinement step show its overhead. Our two variants are significantly faster than LSQ while achieving similar performance. Furthermore, our method is slightly faster than most of the con- strained MCQs. Our method achieves high per- formance as well as superior encoding efficiency. UNQ has the shortest time encode the whole set, however during retrieval, they still need to decode and re-rank that slow down the speed.
305
306
307
308
309
310
312
313
5.3.3
Reconstruction accuracy
314
The comparisons of quantization error on three datasets are stated in Table Basically, when the quantization error gets lower, recall will be higher.
8

---

SIFTIM
DEEPIM
LabeIMe22K
Method
32 bits
64 bits
32 bits
64 bits
32 bits
64 bits
OPQ
4.03 x 10
2.51 x 10*
4.25 x 10
2.70 10
1.25 x 10
9.25 x 10 2
SQ
3.42 x 10
2.13 x 104
3.24 x 10
2.10 10-1
1.25 x 10-1
9.10 x 10-2
LSQ
2.90 104
1.12 104
3.04 10-1
1.99 10-1
1.21 10
8.57 x 10
DPQ
4.01 x 10*
2.48 10
1.58 x 10
3.54 10
1.77 x 10
1.60 x
DPgQ
3.30 x 10a
2.10 x 10
3.29 x 10
2.12 x 10-1
1,31 x 10-1
8.74 x 10
DRQ
1.75 104
2.88 104
3.52 10-1
2.54 10-1
1.61 10
1.01 x 10
UNQ
4.14 x 10a
2.33
x 10
3.52 x 10
2.39 x 10
1.48 x 10
1.08 x 10"
Ours
2.92 x 10"
1.91
X 10*
2.92 x 10 1.93 x 10
1.02 X 10-1 6.72 X 10-²
Table 3: Comparisons of quantization error with state-of-the-arts on three datasets (lower is better). Ours achieves the lowest quantization error in most cases. This gives benefits of feature recon- struction. Observe that UNQ performs poorly, we believe it focuses more on ranking and similarity preservation, other than reconstruction.
Ours get the 2nd place SIFTIM, and the lowest remaining datasets in most cases. Quantization error indicates reconstruction accuracy and further shows the quality of codebook generation and quantization codes selection. Notably, ours significantly outperforms UNQ, which has a strong bias
317
318
319
on the reconstruction task. This is because they focus more on ranking, not the quantization error.
320
The result shows that our method can be applied to other areas, e.g. vector compression.
5.4 Ablation study
SIFTIM@ 32 bits R@1
Method
QE
R@10
R@ 100
322
Our ablation study conducted on the SIFTIM dataset, with the code-length of 32 bits, which in our experiments is suf- ficient to show how does each component affects our model. We choose the following variants perform ablation:
w/o regularization
3.38 x 10*
7.60
29.96
68.73
w/o return-norm
3.06 x 104
10.57
36.44
76.04
324
w/o correction
3,10 x 10
10.09
35.30
75.16
w/o refinement
3.17 x 10*
9.91
30.39
68.28
326
DeepQ
2.92 x 104
11.02
37.73
76.79
328
w/o regularization: which removes ep the losses, and the output distributions will
Table 4: Ablation study conducted SIFTIM with 32 bits code-length. Entropy regularization forces network to try more codeword combinations, which help to jump out of local-optima. Return normalization and value correction help for fast convergence. The extra refine- ment leads to low quantization error and high recall with negligible costs.
330 not be forced to be uniform.
331
w/o return-norm: which does not normal- ize R. and therefor advantage is computed by R other than R.
332
333
w/o correction: which removes value cor- rection. So our VC-PPO falls back to the original PPO.
335
336
w/o refinement: which directly encode the base set without extra refinement.
337 Quantization error and recall are evaluated and placed in Table 4 We report the best value they 338
ever met during the training procedure. Specifically, when regularization is removed, it seems that the network trapped in optima and the performance drops. Meanwhile, although return normalization and value correction give only subtle improvements, we find they help the network
339
340
341
to converge quickly. The extra refinement gives us lower quantization eиror and higher recall, specially
342
when we want to perform fast training before the network is converged.
6 Conclusion and Future Work
344
In this paper, we first review previous works of constrained MCQs, and investigate solutions to unconstrained ones. Since finding the global-optima of MCQ is NP-hard, researchers apply constraints to find near-optimal solutions or employ heuristic algorithms that are still time-consuming This paper takes the first attempt to find deep solution to MCQ. The proposed IndepNet is designed to be simple enough to encode vectors extremely fast. Furthermore, our network shows sfate-of-the-art performance in retrieval and reconstruction tasks. Our method is slow to converge in large dataset, which hinders our performance. So, our future work will focus on training speedup.
345
346
347
348
350

---

References
351
[1] Anderson, E., Bai, Z., Dongarra, J. J., Greenbaum, A., McKenney, A., Croz, J. D., Hammarling, S., Demmel, J., Bischof, C. H., and Sorensen, D. C. (1990). LAPACK: a portable linear algebra library for high-performance computers, In SC, pages 2-11.
353
354
355
[2] Babenko, A. and Lempitsky, V. (2014). Additive quantization for extreme vector compression. In CVPR, pages 931-938.
357 [3] Babenko, A. and Lempitsky, V. (2015). Tree quantization for large-scale similarity search and classification. In CVPR. pages 2240-4248.
358
359
[4] Chen, Y., Guan, T., and Wang, C. (2010). Approximate nearest neighbor search by residual vector quantization. Sensors, 10(12):11299-1122)
360
[5] Gao, I.., Zhu, X., Song, J., Zhao, 7., and Shen, H. T. (2019). Beyond product quantization: Deep progressive
362
quantization for image retrieval. In IJCAI, pages 723-729.
363
[6] Ge. T., He, K., Ke, Q.. and Sun, J. (2013). Optimized product quantization for approximate nearest neighbor search. In CVPR, pages 2946-2953.
384
385
[7] Gray, R. (1984). Vector quantization. IEEE Assp Magazine, 1(2)4 29.
388
[8] llyas, A., Engstrom, L.. Santurkar, S., Tsipras, Janoos, F., Rudolph, L.,, and Madry, A. (2020). A closer look at deep policy gradients. In ICLR.
368
99] Jégou, H., Douze, M., and Schmid, C. (2010). Product quantization for nearest neighbor search. IEEE Trans. Pattern Anal. Mach. Intell., 33(1):117-128.
369
[10] Kalantidis, Y. and Avrithis, Y. (2014). Locally optimized product quantization for approximate nearest neighbor search. CVPR, pages 2329-2336.
371
372
[II] Klein, B. and Wolf, L. (2019). End-to-end supervised product quantization for image search and retrieval. In CVPR, pages 5041-5050.
374
[12] Konda, V. R. and Tsitsiklis, J. N. (2000). Actor-critic algorithms. In NeurlPS, pages 1008-1014.
[13] Lloyd, S. (1982). Least squares quantization in pem. IEEE transactions on information theory, 28(2):129- 137.
376
377
[14] Martinez, J., Clement, J., Hoos, H. H., and Little J. J. (2016). Revisiting additive quantization, In ECCV, pages 137-153. Springer.
378
379
[15] Martnnez, J., Hoos, H., and Little, J. (2014). Stacked quantizers for compositional vector compression. Xiv preprint arXiv:1411.2173.
380
[16] Martinez. J.. Zakhmi, S.. Hoos. H. H., and Little, J. J. (2018). Lsq++: Lower running time and higher recall in multi-codebook quantization. ECCV, pages 491-506.
382
383
[17] Mohamed, S., Rosca, M., Figurnov, M., and Mnih, A. (2020). Monte carlo gradient estimation in machine learning. J. Mach. Learn. Res., 21:132:1-132:6:
384
385
[18] Morozov, S. and Bahenko, A. (2019). Unsupervised neural quantization for compressed-domain similarity search. In ICCV, pages 3036-3045.
386
[19] Norouzi, M. and Fleet, D. J. (2013). Cartesian k-means. In CVPR, pages 3017-3024.
388
[20] Radenovic, F., Iscen, A., Tolias, G., Avrithis, Y., and Chum, O. (2018). Revisiting oxford and paris: Large-scale image retrieval benchmarking, In CVPR, pages 7706-5715.
389
380
[21] Reddi, Kale, S., and Kumar, S. (2018). On the convergence of adam and beyond. In ICLR.
391
[22] Sablayrolles, A., Douze, M., Schmid, C., and Jégou, H. (2019). Spreading vectors for similarity search. In ICLR.
382
383
[23] Schulman, J., Heess, N., Weher, T., and Abheel, (2015a). Gradient estimation using stochastic computa- tion graphs. In NeurlPS, pages 3528-3536.
394
[24] Schulman, J., Levine, S., Abbeel, P., Jordan, M. I., and Moritz, P. (2015b). Trust region policy optimization. In ICML, pages 1889-1897.
396
387
[25] Schulman, J., Moritz, P., Levine, S., Jordan, M. I., and Abbeel, P. (2016). nigh-dimensional continuous control using generalized advantage estimation. In ICLR.
398
399
[26] Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. (2017). Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06321
400
[27] Song, J., Lang, R., Zhu, X., Xu, X., Gao, L., and Shen, H. T. (2020). 3d self-attention for unsupervised video quantization. ACM SIGIR, pages 1061-1070.
402
403 [28] Song, J., Zhu, X., Gao, L.. Xu, X.-S., Liu, W., and Shen, H. T. (2019). Deep recurrent quantization for generating sequential binary codes. In IJCAI, pages 912 918.
10

---

405
Torralba, A., Fergus. R., and Weiss, Y. (2008). Small codes and large image databases for recognition. In [29]
CVPR, pages 1-8. IEEE.
407
[30] Wang. J., Wang. J., Song. J., Xu, X., Shen, H. I., and Li. S. (2015). Optimized cartesian k-means. JEEE Transactions on Knowledge and Data Engineering, 27(1):180 ((11))180-122 192.
408
[31] Weyand, T., Araujo, A., Cao, B., and Sim, (2020). Google landmarks dataset v2 large-scale benchmark for instance-level recognition and retrieval. CVPR, pages 2572-2581.
410
[32] Williams, R. J. (1992). Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning. 8(3-4):229) 256.
413
[33] Yu, T., Yuan, J., Fang, C., and Jin, (2018). Product quantization network for fast image retrieval. In ECCV, pages 186-201.
414
[34] Zhang, T., Du, C., and Wang, (2014). Composite quantization for approximate nearest neighbor search. In ICML, volume 2. 3.
416
Checklist
417
418
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], or [N/A] . You are strongly encouraged include justification your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
419
420
Did you include the license the code and datasets? [Yes] See Section ??.
423
Did you include the license to the code and datasets? [No] The code and the data are proprietary.
424
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
426
428
1. For all authors...
429
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
430
(b) Did you describe the limitations of your work? [Yes] See Section
432
(c) Did you diseuss any potential negative societal impacts of your work? [N/A]
433
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them?
[Yes]
435
2. If you are including theoretical results...
436
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
438
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [Yes] See https: com/ DeepMCq/DeepQ
440
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 5 and supplementary materials.
443
444
(c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [No]
446
(d) Did you include the total amount of compute and the type of resources used (c.g.. type of GPUs, internal cluster, or cloud provider)? [Yes] See Section
447
448
If you are using existing assets (c.g., code, data, models) or curating/relcasing new assets...
449
(a) If your work uses existing assets, did you cite the creators? [Yes] See Section 5
450
(b) Did you mention the license of the assets? [N/A]
451
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] See
452
https://githi: thub. www.cco//Deeeeeee Deepp)
453
(d) Did you discuss whether and how consent was obtained from people whose data you're 're
using/curating? [N/A]

---

456
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
456
5. If you used crowdsourcing or conducted research with human subjects...
458
(a) Did you include the full text of instructions given to participants and screenshots, if applica-
459
ble? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
481
462
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "fHtKpautPo8", "reviewer": "Reviewer_w7H4", "summary": "This paper introduces DeepQ, a multi-codebook quantization framework with NN-based methods. \n\nIn DeepQ, code b is encoded by neural networks. To tackle the non-differentiable gradient estimation issue, a revised policy gradient method has been adapted here to accelerate convergence. \n\nThe effectiveness of the proposed methods is well demonstrated on multiple datasets.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "### Pros\n\n+ This paper is clearly written and easy to follow.\n\n+ The main contribution of this work is to formulate an NN-based pipeline for multi-codebook quantization, which seems to be a simple yet effective framework for the MCQ problem.\n\n+ Sufficient running latency analysis is included. \n\n### Cons\nMuch thanks to the authors' efforts for this issue.  I still have some experimental concerns about this work and I may adjust my ratings after receiving feedback. \n\n+ Although I agree with the efficiency of DeepQ, its performance improvements seem not to be significant in some cases. For instance, according to the results in Table.2,  DeepQ may yield about 5 lower Recall@1 than LSQ (28.0 \\vs 33.2, 64-bits) on the SIFT1M dataset,   making it's hard for me to recognize DeepQ is \"comparable\" to LSQ.  Besides, on the DEPP1M dataset, the improvements of DeepQ are also marginal (usually 0.1~0.5).\n\n+  The authors propose VC-PPO based on PPO to speed up model convergence. To demonstrate the effectiveness of VC-PPO, more ablation studies are encouraged. \n\n+ Minor issues:  some typos need to be corrected. eg,  \"staet-of-the-arts\" in Table.2 caption.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "YZbEvTokxiO", "reviewer": "Reviewer_AdTS", "summary": "This paper proposes a multi-codebook quantization method (aka additive quantization). \n\nIn this setting vectors are decoded as x = sum_i C(i, b_i) with C a codebook matrix. \nThere is no clear optimal algorithm to train the codebook and optimize the b_i (the strongest competitor that this paper compares with is LSQ [16]). \n\nThis paper proposes to train a neural net that computes the b_i's in a forward pass together with the codebook matrices. \nAt encoding time, the neural net outputs a probability distribution for the code components (a policy) from which several codes are sampled randomly, and the best one is kept (after computing the quantization error).\n\nThe training is based on a policy optimization, that is able to handle noisy gradients that result from the code sampling procedure. \n\nThe experiments show promising results, that sometimes outperform the SOTA LSQ at a much lower encoding cost. \n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Strengths: \nS1: interesting and promising approach\nS2: it seems that the gradient optimization is an elegant way to short-circuit the non-differentiable quantization operations\n\nWeaknesses: \nW1: un-natural loss functions\nW2: reporting of results is biased\n\n\n------------ \nS1: building a neural net that could perform the encoding in a single forward pass would be ideal. \n\n\nW1: [Caveat, I am in no ways a specialist of policy optimization]. \n\nThe notations in eq (7) - (10) are confusing, it took me some time to realize the Q() and V() are actually scalar and (10) is just a simple sum. But then it seems not very natural to to compare Q and V that are derived from vector encodings only in the scalar domain, since they could be compared directly in dimension d. A bit more explanations would be appreciated here. \n\nAlso the clip function included in (12)-(13) looks like a hack and anyways in eq (12) it does not look like the first term of the min is useful at all given the second term. \n\nThe explanation of dgelsy in L169-L177 is a paraphrase of the Lapack documentation, it could be left out.\n\nW2: the results are honest and the comparison seems fair. It is all the more surprising that the authors say things like\n\nL280 \"Compared to our main competitor, LSQ, our method achieves comparable performance on SIFT1M, and outperforms LSQ on DEEP1M in most cases\" \n\nwhen (tab 2, LSQ vs. ours, 64 bits) shows that LSQ outpeforms \"ours\" by a much larger margin on SIFT1M than the reverse on Deep1M.\n\nThe argument about encoding time is relevant though.\n\nTable 3 is quite unreadable, please indicate the scale 10^4 in the table header once. \n\nThe paper is well written in general, but please check grammar (L325). \"a bunch of\" is familiar language (L169). \"state-of-the-arts\" does not exist.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"ethical_concerns": "-", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "GuEqZHUh-8M", "reviewer": "Reviewer_M8gn", "summary": "The present work considers Multi-Codebook Quantization problem, and propose new deep learning based coding methods for reducing computational complexity.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "The problem being considered is old, with many existing methods. The current work proposed a new method based on deep learning which is novel. Paper is well written and results ate clearly stated.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "It is unclear the advantage of deep learning beyond existing method. Section provides some rough background on the motivation of using deep learning for vector quantization. Can the authors explain more clearly their motivations?", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "2E5RU-dUAMp", "reviewer": "Reviewer_GpZW", "summary": "This paper proposes DeepQ, which uses a deep neural network to map a vector to its vector code in multi-codebook quantization. The experiment results show that DeepQ matches the accuracy of LSQ++ and outperforms LSQ++ in encoding efficiency.\n", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "I think improving multi-codebook quantization with deep learning is a good direction. However, the paper has several big problems.\n  \n1. Writing needs to be significantly improved to be more accurate and rigorous.\nFor example, “The quantization codes are designed to be compacted, which results in negligible storage cost and high-quality results” This is not true as the storage cost is still a problem for large datasets (e.g., SIFT1B).     \n “However, the above methods do not achieve satisfied time complexity in encoding yet.” What is satisfied time complexity? \n “The training set and base set are scaled up”. How do you scale up the training set and base set exactly? Similar errors are all over the paper.\n\n2. Please also report the results of 128 or 256 bits as using 16 or 32 codebooks are also common.\n\n3. For the comparison with LabelMe22K, DeepQ is trained on the base set, which DeepQ encodes. This is unfair as the training set is the same as the test set. In fact, there are many larger datasets you can use, such as GIST and Glove, which are commonly used in similarity search. \n\n4. Please include the model training time in the overall encoding time. \n\n5. “additional code-length for storing \\Vert x \\Vert for lookup table is ignored”. This is unfair when comparing with OPQ as it does not need to store norm. Please use one codebook to encode norm when comparing with OPQ.\n\n6. For Figure 3, I fail to understand why DeepQ is more efficient than SQ in encoding. SQ only needs to compute the distance to 256 codewords for each codebook while DeepQ needs to run neural network inference for each codebook.  \n\nMy biggest concern is the limited impact of the paper. The accuracy advantage of DeepQ over LSQ++ is not obvious and LSQ++ is already quite fast (e.g., taking several ms for each vector as reported in its original paper). \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers Multi-Codebook Quantization and proposes a new deep learning based coding methods for reducing algorithmic complexity. There was a diversity of reviews.  The  improvements of the DeepQ are marginal and addressing issues about the increased cost of importing deep learning modules will help.  Several reviewers saw merits, and addressing the concerns raised by several of the authors should help position the paper to make it more helpful for the community.
Decision: Reject