Automating Nearest Neighbor Search Configuration with Constrained Optimization
Authors: Philip Sun
Ruiqi Guo
Sanjiv Kumar
Venue: ICLR 2023 poster (2023)
Keywords: AutoML
Convex Optimization
Vector Retrieval
Hyperparameter Search
ANN

Abstract: The approximate nearest neighbor (ANN) search problem is fundamental to efficiently serving many real-world machine learning applications. A number of techniques have been developed for ANN search that are efficient, accurate, and scalable. However, such techniques typically have a number of parameters that affect the speed-recall tradeoff, and exhibit poor performance when such parameters aren't properly set. Tuning these parameters has traditionally been a manual process, demanding in-depth knowledge of the underlying search algorithm. This is becoming an increasingly unrealistic demand as ANN search grows in popularity. To tackle this obstacle to ANN adoption, this work proposes a constrained optimization-based approach to tuning quantization-based ANN algorithms. Our technique takes just a desired search cost or recall as input, and then generates tunings that, empirically, are very close to the speed-recall Pareto frontier and give leading performance on standard benchmarks.

Published as a conference paper at ICLR 2023
AUTOMATING NEAREST NEIGHBOR SEARCH CONFIG- URATION WITH CONSTRAINED OPTIMIZATION
Philip Sun, Ruiqi Guo & Sanjiv Kumar Google Research [sunphil] 1, guorg, san jivk] @ggoggll
ABSTRACT
The approximate nearest neighbor (ANN) search problem is fundamental to ef- ficiently serving many real-world machine learning applications. A number techniques have been developed for ANN search that efficient, accurate, and scalable. However, such techniques typically have a number of parameters that affect the speed-recall tradcoff, and exhibit poor performance when such parame- ters aren't 't properly set. Tuning these parameters has traditionally been manual process, demanding in-depth knowledge of the underlying search algorithm. This is becoming an increasingly unrealistic demand as ANN search grows in popu- larity. To tackle this obstacle ANN adoption, this work proposes constrained optimization-bast approach to tuning quantization- technique takes just a desired search cost or recall as input, and then generates tumings that, empirically, very close to the speed-recall Pareto frontier and give leading performance on standard benchmarks.
ANN algorithms. Our
INTRODUCTION
Efficient nearest neighbor search is an integral part of approaches to numerous tasks in machine learning and information retrieval; has been leveraged effectively solve a number of challenges in recommender systems (Benzi et al. 2016 Cremonesi et al. 2010). coding theory (May & Ozerov
2015). multimodal search (fflller et al. 2017 Miech et al. 2021), J. and language modeling (Guu et al.
2020 Khandelwal et al.) 2020 Kitaev al. 2020). Vector search
the dense, high- high-dimensional embedding vectors generated from deep learning models has become especially important following the rapid rise in capabilities and performance of such models. Nearest neighbor search is also increasingly being used for assisting training tasks in ML (Lindgren et al. 2021 Yen et al. 2018).
Formally, the nearest neighbor search problem is as follows: we are given n-item dataset X' Raxd composed of d-dimensional vectors, and a function for computing the distance between two vectors D gd R E. For a query vector q E Rd, our goal is find the indices of the k-nearest neighbors in the dataset to g:
k- k-arg min D(g, X;) i se.......
Common choices of D include D(g,z) x) for maximum inner product search (MIPS) and D(g. 2) ||q 21 for Euclidean distance search. A linear-time scan over X' solves the nearest neighbor search problem but doesn't 't scale to the large dataset sizes often found in modern-day applications, hence necessitating the development of approximate nearest neighbor (ANN) algorithms.
number of approaches to the ANN problem have been successful in trading off small search accuracy loss, measured in result recall, for correspondingly large increase in search speed (Aumüller cet al. 2020). However, these approaches rely on tuning a number of hyperparameters that adjust the tradeoff between speed and recall, and poor hyperparameter choices may result in performance far below what could be achievable with ideal hyperparameter tuning. This tuning problem becomes especially difficult at the billions-scale where the larger dataset size typically leads greater number of hyperparameters to tune. Existing approaches to tuning an ANN index, enumerated in Table 1 all suffer from some deficiency, such using excessive amount of computation

---

Published as a conference paper at ICLR 2023
Table 1: Our technique is the first use minimal computational and human involvement to configure an ANN index to perform very close to its speed-recall Pareto frontier.
Computational
Human
Hy Hyperparameter
Method
Cost of Tuning
Involvement
Quality
Grid search
High
Low
High
Manual tuning
Low
High
Medium
Black-box optimizer Ours
Medium
Low
Medium
Low
Low
High
during the tuning process, necessitating extensive human-in-the-loop expertise, giving suboptimal hyperparameters.
Mitigating these issues is becoming increasingly important with the growth in dataset sizes and in the popularity of the ANN-based retrieval paradigm. This paper describes how highly performant ANN indices may be created and tuned with minimal configuration complexity to the end user. Our contributions are:
Deriving theoretically-grounei models for recall and search cost for quantization based ANN algorithms, and presenting an efficient Lagrange multipliers-bant based technique for optimizing either of these metrics with respect to the other.
Showing that on millions-scale datasets, the tunings from our technique give almost identical performance to optimal hyperparameter settings found through exhaustive grid search.
Achieving superior performance on track 1 of the billions-scale big-- wegg-annn-benhaaake datasets using tunings from our technique over tunings generated by a black-box optimizer on the same ANN index, and over all existing benchmark submissions.
Our constrained optimization approach is very general and we anticipate can be extended to distance measures, quantization algorithms, and search paradigms beyond those explored in this paper.
RELATED WORK
2.1 ANN ALGORIHTM
L Literature surrounding the ANN problem is extensive, and many solutions have been proposed, drawing inspiration from a number of different fields. Below we give a brief outline of three families of approaches that have found empirical success and continued research interest, with an emphasis on the hyperparameters necessitated by each approach. Other approaches to ANN include sampling- based algorithms (Liu et 2019) and a variety of geometric data structures (Bozkaya & Ozsoyoglu
1997 Ram & Gray 2012 : we refer readers to Bhatia & Vandana (2010) RezaAbbasifard et al.
(2014)) Wang et al. 2014
2021 for more comprehensive surveys.
Hashing approaches Techniques under this family utilize locality sensitive hash (LSH) functions, which are functions that hash vectors with the property that more similar vectors are more likely to collide in hash space (Andoni & Razenshteym 2013 Datar al. 2004 Shrivastava & Li 2014). By hashing the query and looking up the resulting hash buckets, we may expect to find vectors close to the query. Hashing algorithms generally parameterized by the number and size of their hash tables. The random memory access patterns of LSH often lead to difficulties with efficient implementation, and the theory that prescribes hyperparameters for LSH-bbsed search generally cannot consider dataset-specific idiosyncrasies that allow for faster search than otherwise guaranteed for worst-case inputs; see Appendix A.I for further investigation.
Graph approaches These algorithms compute (potentially approximate) nearest neighbor graph on X. where each element of becomes graph vertex and has directed edges towards its nearest neighbors. The nearest neighbors g are computed by starting some vertex and traversing edges
2

---

Published as a conference paper at ICLR 2023
to vertices closer to 9. These algorithms are parameterized by graph construction details, such the number of edges; any cost-construction adjustments, such as improving vertex degree distribution and graph diameter (Fu et al. 2019 Iwasaki & Miyazaki 2018 Malkov & Yashumin 2020); and query-time parameters for beam search and selecting the initial set of nodes for traversal.
Quantization approaches These algorithms create a compressed form of the dataset X;; at query time, they return the points whose quantized representations generally proportional to the reduction in dataset size. These reductions can be several orders of magnitude, although coarser quantizations lead to greater recall loss. Quantization techniques include VQ. where each datapoint is assigned to the closest element in a codebook C, and a number of multi-codebook quantization techniques, where the datapoint is approximated (concatenation, addition, or otherwise) of the codebook element it was assigned to per-codebook (Babenko & Lempitsky 2015 Guo et al., 2020) Jégou et al. 20IT). Quantization- bbased approaches generally must be tuned on codebook size and the number of codebooks.
closest to the query. Speedups are
some aggregate
Growth in parameterization complexity with respect dataset size While the above ap- proaches may only each introduce a few hyperparameters, many of the best-performing ANN algorithms layer multiple approaches. leading to a higher-dimensional hyperparameter space much more difficult to tune. For example, [Chen et al. (2021) uses VQ. but also graph-based approach to search over the VQ codebook. Other algorithms (Guo et al. 2020, Johnson et al. 202T), including what discuss in this work, use VQ to perform frrst-pass pruning over the dataset and then multi-codebook quantization to compute more accurate distance estimates.
2.2 ANN HYPERPARAMETBA TUNING
Tuning in low-dimensional hyperparameter spaces may be effectively handled with grid search; however, quantization-basee ANN algorithms with few hyperparameters scale poorly with dataset size, shown in Appendix A.8 In higher-dimensional ANN hyperparameter spaces, where grid search is computationally intractable, there are two predominant approaches to the tuming problem, each with their drawbacks. The first using heuristics to reduce the search space into one tractable with grid search, in Criteo (202T) or Ren et al. (2020). These heuristics may perform well when set and adjusted by someone with expertise the underlying ANN search algorithm implementation, but such supervision is often impractical or expensive; otherwise, these heuristics may lead to suboptimal hyperparameter choices.
The second approach is to use black-box optimization techniques such Bergstra et al. (2011) or Golooin et al.] (2017) to select hyperparameters the full-dimensionality tuning space. These algorithms, however, lack inductive biases from knowing the underlying ANN search problem and therefore may require a high number of samples before finding hyperparameter tunings that are near optimal. Measurement noise from variability in machine performance further compounds the challenges these black-box optimizers face.
PRELIMINARIES
3.1 LARGE-SCALE ONLINE APPROXIMATE NEAREST NEIGHBORS
In this work we focus on the problem of tuning ANN algorithms for online search of large-scale datasets. this scenario, the search algorithm must respond to an infinite stream of latency-sensitiv queries arriving at roughly constant frequency. This setting is common in recommender and semantic systems where ANN speed directly contributes to the end-user experience. We are given sample set of queries, representative of the overall query distribution, with which
tune our data structure.
Large datasct size makes the linear scaling of exact brute-force search impractical, so approximate search algorithms must be used instead. These algorithms may be evaluated along two axes:
Accuracy: quantified by recall @ where k is the desired number of neighbors. Sometimes the c-approximation ratio, the ratio of the approximate and the true nearest-neighhor distance, is used instead; we correlate between this metric and recall in Appendix A.
2. Search cost: typically quantified by the queries per second (QPS) a given server can handle.
3

---

Published as a conference paper at ICLR 2023
An effective ANN solution maximizes accuracy while minimizing search cost.
3.2 VECTOR QUANTIZATION (VQ)
The ANN algorithm we tune uses a hierarchical quantization index composed of vector quantization
(VQ) and product quantization (PQ) layers. We first give a brief review of VQ and PQ before describing how they are composed to produce a performant ANN search index.
Vector-quantizing an input of vectors A' E IRadd which we denote VQ(X), produces codebook 21, c.i". Each element of X is quantized to the closest codebook element C, and the quantization assignments are stored in w. The quantized form the ith element of X can therefore be computed as X; C...
C' E Rexd and codewords
VQ may be used for ANN by computing the closest codebook elements to the query
S = k-arg min D(g. C.) (E.,2......f
and returning indices of datapoints belonging those codebook elements, (jlwy E S). This candidate set may also be further refined by higher-bitrate distance calculations to produce a final result set. In this manner. VQ can be interpreted as a pruning tree whose root stores C and has e children; the ith child contains the points {X' |wy = i}; equivalently, this tree is an inverted index (or inverted file index, IVF) which maps each centroid to the datapoints belonging the centroid.
3.3 PRODUCT QUANTIZATION (PQ)
Product quantization divides the full d-dimensional vector space into K subspaces and quantizes each space separately. If we assume the subspaces are all equal in dimensionality, each covering 1 [d/K] dimensions, then PQ gives K codebooks C(I) ..... C(K) and K codeword vectors w()) w (), with (1k) Rext and (k)) (1.....cc) c where eæ is the number of centroids in subspace k. The ith element can be recovered as the concatenation of {c(() Ik: E [f.....,K) K}}.
(c)
For ANN search, VQ is generally performed with large codebook whose size scales with n and whose size is significant relative the size of the codewords. In contrast, PQ generally performed with constant, small eæ that allows for fast in-register SIMD lookups for each codebook element, and its storage cost is dominated by the codeword size.
3.4 ANN SEARCH WITH MULEI-LEVEL QUANTIZATION
VQ and PQ both produce fixed-bitrad encodings of the original dataset. However, in generalization Guo et al. (2020), we would like to allocate more bitrate to the vectors closer to the query, which may achieve by using multiple quantization levels and using the lower-bitrate levels to select which portions of the higher-bitrad levels to evaluate.
To generate these multiple levels, a smaller d-dimensional dataset of codewords C. We may recursively apply VQ to for arbitrarily many levels. X' and all C are product-quantized well. As a concrete example, Figure 6 describes the five-quantization-lewe setups used in Section 5.2
we start with the original dataset X' and vector-quantize it, resulting
This procedure results in a set of quantizations Yi...., Im of progressively higher bitrate. Algorithm performs ANN using these quantizations and a length-ra vector of search hyperparameters t, which controls how quickly the candidate set of neighbors is narrowed down while iterating through the quantization levels. Our goal is to find that give excellent tradeoff's between search speed and recall.
METHOD
The following sections derive proxy metrics for ANN recall and search latency function of the tuning f, and then describe a Lagrange multipliers- basedd approach to efficiently computing to optimize for given speed-recall tradeoff.
4

---

Published as a conference paper at ICLR 2023
Algorithm 1 Quantization-Basel ANN
1: procedure QUANTIZEDSEARCHHCE
Computes the Im nearest neighbors to
2: So [I....,n)
3: for - 1 to m do
Iterate over quantizations in ascending bitrate order
4: S: - ara min D X)) JES.-1
Narrow candidate set to elements, using 20
5: end for
6: return S.
7:
end procedure
4.1 PROXY LOSS FOR ANN RECALL
For a given query set Q and hyperparameter tuning i, the recall may be computed by simply performing approximate search over Q and computing the recall empirically. However, such an approach has no underlying mathematical structure that permits efficient optimization over t. Below we approximate this empirical recall manner amenable our constrained optimization approach.
First fix the dataset X' and all quantizations (+) Define functions So .)....,, Sm (1- t) denote the various S computed by Algorithm for query and tuning t. and let (q)) be the set of ground-
truth nearest neighbors for q. Note our recall equals (g, t) g for given query and tuning
[g(4)
t. We decompose this into telescoping product and multiply among all queries in Q derive the following expression for geometric- mean recall:
II ( q 1=1 ())
1/R1
GeomeeticcMeanRecal((..///
where the telescoping decomposition takes advantage of the fact that [So(g, () n ((() = 19(() due So containing all datapoint indices. We choose the geometric mean, despite the arithmetic mean's more frequent use in aggregating recall over query set, because the geometric mean allows for the decomposition log-space that perform below. Note that the arithmetic mean is bounded from below by the geometric mean.
Maximizing Equation is equivalent to minimizing its negative logarithm:
m
(1,
((2,1)
= 2
log
(S.-1(..))g(())
gEQ
1=1
((((,)t)n(a) [8,-1(4, (g())
EnE 2
log
Now we focus on the inner quantity inside the logarithm and how compute it efficiently. The chief problem is that S,(g, t) has an implicit dependency on S (g, because S is the candidate set from which we compute quantized distances using (²)+) in Algorithm | This results in Sz I) depending on all 4,..., I4 and not just 4 itself, making difficult to efficiently evaluate. To resolve this, define the single-layer candidate set
(4) t-arg min D(g, (()0)
jE(L.....)
which computes the closest t, neighbors to g according to only (0) irrespective other quantizations their tuning settings. We leverage this definition by rewriting our cardinality ratio
() S ( Eperre) 49ES.-1(94)
Eneg(o) AgeS((1)))
(4)
5

---

Published as a conference paper at ICLR 2023
ges((tt))) This is roughly equivalent to assuming most near-neighbors to q included in S (q. t); see Appendix A.2 for further discussion. If we furthermore assume zero covariance between Il 3ES._.(0.1) and (0.t)) then transform the sum of products into product of sums:
and making the approximation (g.t)((.))
)
Σ 1 ges, sla.)) (EE)((AA) ~ gE9(g)
Σ gE9(a)
Jes, 1(a.))
Σ L9ES((A)))
[g(a]]
(Eg(4)
Combining this result from Equations per-quantization loss Li defined as
2 and
our final loss function > (,(2, (;). with the
([g.,4) [g(g]
C.) =
-log
(5)
See Appendix A.4 for how L; may be efficiently computed over Q for all i E (1,...,m) 4 e (1...., n),, resulting in a matrix I. E mmmx,. This allows us to compute the loss for any tuning t by summing m elements from L.
4.2 PROXY METRIC FOR ANN SEARCH COST
Similar ANN recall, search may be directly measured empirically, but below we present simple yet effective search cost proxy compatible with our Lagrange optimization method.
Let P denote the storage footprint of ( At quantization level i, for i < m, selecting the top top & candidates necessarily implies that a t proportion of ((++) will need to be accessed in the next level. Meanwhile, (2) is always fully searched because it's encountered at the beginning of the search process, where the algorithm has no prior on what points are closest to q. From these observations, we can model the cost of quantization-bant based ANN search with tuning as
J(L) A
1 [2
1100++
+
T
(6)
J gives the ratio of memory accesses performed per-query when performing approximate search with tuning / to the number of memory accesses performed by exact brute-force search. This gives good approximation
real-world search cost because memory bandwidth is the bottleneck for quantization-basse ANN in the non-batee betchatced case. We emphasize that this cost model is effective for comparing amongst tunings for quantization- based ANN index. which is sufficient for our purposes, but likely lacks the power compare performance among completely different ANN approaches, like graph- solutions. Differences memory read size, memory request queue depth, amenability to vectorization, and numerous other characteristics have large impact on overall performance but are not captured this model. Our model is, however, compatible with query batching, which we discuss further in Appendix A.3
4.3 CONVEXIFICATION OF THE LOSS
We take the convex hull of each per-quantization loss C, before passing it into the constrained optimization procedure. This results in better-behaved optimization result but is also justified from an ANN algorithm perspective. For any quantization level i, consider some two choices of t; that lead to loss and cost contributions (41.21) and (12.j2). Any (loss, cost) tuple on the line segment between these two points can be achieved via randomized algorithm that picks between our two choices of 4 with the appropriate weighting, which implies the entire convex hull is achievable. Empirically, we find that L. is extremely close to convex already, so this is more of a theoretical safeguard than a practical concern.
Note that S, C S,-1 so this is emphatically false for Ages.-1(0.)) and 1gs but with 1 1968((..)) we may reasonahly assume little correlation with 1 1988-1(94))-

---

Published as a conference paper at ICLR 2023
4.4 CONSTRAINED OPTIMIZATION
Formally, our tuning problem of maximizing recall with a search cost limit Jma can be phrased as arg min
arg min
Σ ((())
[0,m)]
J(L) Jmax
4 2 Im-
The objective function is sum of convex functions and therefore convex itself. while the constraints are linear and strictly feasible, strong duality holds. We can therefore utilize the Lagrangian
-J((1) + Σ (444)
==1
s.t. 4 tm
to find exact solutions to the constrained optimization, using À to adjust the recall-cost tradeoff. We show in Appendix A.5 an algorithm that uses (nn)) preprocessing time to solve the minimization for given value of À in (m log n) time.
Furthermore, because the objective function is sum of m functions, each a convex hull defined by points, the Pareto frontier itself will be piecewise, composed of most nm points. It follows then that there are at most nm relevant À that result different optimization results, namely those obtained by taking the consecutive differences among each L, and dividing by (/n+)|/n By performing binary search among these candidate X, loss target, or the minimum-lue tuning for a given cost constraint, in O log n log nm) time.
find the minimum-cost tuning for a given
In practice, even for very large datasets, optimizations used to generate the tunings in Section 5.2 ran in under one second on Xeon W-2135: computation of L contributed marginally the indexing runtime, described further in Appendix A.6
10, so this routine runs very quickly. The constrained
EXPERIMENTS
5.1 MILLION- -CALE BENCHMARKS AND COMPARISON TO GRID SEARCH
To see how closely our algorithm's resulting hyperpa- rameter settings approach the true optimum, pare its output to tunings found through grid search. We compare against the grid-searched parameters used by ScaNN (Guo et al.) 2020) in its leading per- formance the public G1 clve 1M benchmark from
12000
ScaNN Optimal
Speed (Queries per Second)
(Grid- Saric-Searched] Tunings
ScaNN Ours
8000
Aumüller et al. (2020). As shown in Figure [ be- low, our method" s tunings are almost exactly on the speed-recall frontier.
4000
While the resulting tunings are of roughly equivalent quality, grid search takes far longer to identify such tunings; searched 210 configurations in 22 minutes. In comparison, on the same machine, our method took 53 seconds to compute L and run the constrained optimization to generate tunings.
0.86
0.88 0.9
0.92
0.94
0.96
0.98
Accuracy [Recalli 10)
Figure 1: Our technique's tunings compared to grid-searched tunings, applied ScaNN on G1 ove.M.
5.2 BILLION-SCALE BENCHMARKS
We now proceed to lcrger-scale datasets, where the tuning space grows significantly; the following benchmarks five-level quantization index (see Appendix A.6.T for more details), resulting
7

---

Published as a conference paper at ICLR 2023
100000
20000
Spood (0.o0/0etioe 20.e/cs Sccond
80000
XST Toort
Ru56
Outs
50000
50003
50000
50000
40000
40000
30003
10000
20000
20003
20000
10000
10000
10000
0.5
0.55
0.6
9:65
0.7
0.75
08
0.6
0:65
0.7
0.75
0.8
0.55
0.05
6.1
0.15
0.2
0.25 033
8:35 0.4
(Reculga0)
(1acallgg0)
(Neeatip2))
(a) DEEPIB
(b) Microsoft Turing-ANe ANNS
(c) Yandex Text-to-Image
Figure 2: Speed-recall tradeoff's of our tuning algorithm plus ANN search implementation, compared to others from track of the standardized https: htaps://bisse ann bern-bbbnchhrrsss... comm datasets.
in a Your-dimensional hyperparameter space. Even with very optimistic assumptions, this gives hundreds of thousands of tunings to grid search over, which is computationally intractable, so we compare to heuristic, hand-tuned, and black-box optimizer settings instead. Here we use our own implementation of multi-level quantization ANN index, and benchmark three datasets from sese--nnn-enchhhe big-ann ann ben chma com (Simhadri et al. 2022), following the experimental setup stipulated by track of the competition; Appendix A.6 for more details. Our results are shown in Figure 2
We find that even in this much more complex hyperparameter space, our technique manages to find settings that make excellent speed-recall tradeoffs, resulting in leading performance on these datasets.
5.2. COMPARISON AGAINST BLACK- Box OPTIMIZERS
To see if black-box optimizers can effectively tune quantization--ase ANN indices, we used Vizier (Golovin al. 2017) to tune the same DEEPIB in-
100000
90000
Trials Qurs
80000
dex used above. Our Vizier setup involved an in-the- loop ANN index serving online requests, with Vizier generating candidate configurations, measuring their resulting recall and throughput, and then using those measurements to inform further candidate selections. We ran the Vizier study for hours, during which it con- ducted over 1800 trials; their recall and performance measurements are plotted to the right in Figure 3
70000
Speed (Queries
50000
40000
30000
20000
10000
We see that Vizier found several effective tunings close to the Pareto frontier of our technique, but then failed to interpolate or extrapolate from those tunings. Our technique not only generated better tunings, but did so using less compute; notably, the computation of statistics L; and the constrained optimization procedure were done with low-priority, preemptible, batch com- pute resources, while in contrast Vizier requires instances of online services in a carefully controlled environment in order to get realistic and low-variance throughput measurements.
0.5
0.55
0.6
0.65
0.7
0.75
0.8
Accuracy (Recal(@10)
Figure 3: On DEEPIB, our hyperparameter tunings achieve significantly better speed- recall tradeoff' than those found by Vizier.
5.3 RECALL AND COST MODEL ACCURACY
We desire linear, predictable relationships between the modeled and the corresponding real-world values for both recall and search cost. This is important both so that the optimization can produce tunings that are effective in practice, and so that users can easily interpret and apply the results.
In Figure 4 we take the DEEPIB hyperparameter tunings used above in Section 5.2 and plot their respective modeled recalls against empirical recall @ 10, and modeled search costs against measured reciprocal throughput. Recall was modeled exp(- Σ L,) while J was simply used for cost. We can conclude from the square of their sample Pearson correlation coefficients (r²) that both relationships between analytical values and their empirical measurements are highly linear.
8

---

Published as a conference paper at ICLR 2023
0.3
1/ //Thhougghut (ms/query)
Empirical Recall @ 10
0.8
0.7
0.2
0.6
22 99.7%
99.8%
0.1
0.5
0.2
0.3
0.4
0.5
0.2
0.4
0.6
0.8
Modeled Recall
Modeled Cost
Figure 4: Modeled costs and recalls have highly linear relationship with their true values.
5.4 OUT-OF-SAMPLE QUERY PERFORMANCE
Our hyperparameter tunings were optimized based on statisties calculated on query sample O, but in order to fulfill their purpose, these tunings must generalize and provide good performance and re-
30000
In Sample
Out Sample
25000
Queries per Second
call on the overall query stream. We test gener-
20000
alization capability by randomly splitting the 10 queries in the DEEPIB dataset into equal-sized halves 2 and 22. Then we compare the result- ing Pareto frontiers of training Q and testing versus training and testing both on Q2 (in-sample). The resulting Pareto fron- tiers, shown in Figure are aear-indistinguishabb and within the range of measurement error from machine performance fluctuations, indicating excel- lent generalization. Qualitatively, the in-sample and out-of-sample tuning parameters differ only very slightly, suggesting our optimization is robust.
15000
10000
on Q2
5000
0.55
0.60
0.65
0.70
0.75
0.80
1ecal
Figure 5: Speed-recall frontiers for tunings derived from in-sample and out-of-sample query sets the DEEPIB IB dataset.
5.5 ADDITIONAL EXPERIMENTS
In Appendix A.7 analyze the effects of query sample size and find even small (1000) query sample is sufficient to provide effective tuning results. Appendix A.8 shows that grid-searching shallow quantization index (similar what done in Section 5.1) fails perform well billion-scale datasets.
CONCLUSION
As adoption of nearest neighbor search increases, does the importance of providing ANN frame- works capable of providing good performance even to non-experts unfamiliar with the inner details of ANN algorithms. We believe our work makes a significant step towards this goal by providing a theoretically grounded, computationally efficient, and empirically successful method for tuning quantization-ban based ANN algorithms. However, our tuning model still relies on the user to pick the VQ codebook size, because VQ indexing is prerequisite needed to compute the statistics with which we generates tunings from. A model for how VQ codebook size impacts these statistics would allow for a completely hands-off, efficient, ANN solution. Additional work could refine the search cost model to more accurately reflect caches, account for network costs in distributed ANN solutions, and support alternative storage technologies such flash. In general, strategy of computing offline statistics from a query sample to model online ANN search behavior may generalize to non-guantization-baae based ANN algorithms well.
also optimistic that the

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
We would like thank David Applegate, Sara Ahmadian, and Aaron Archer for generously providing their expertise in the field of optimization.
REFERENCES
Alexandr Andoni and Ilya Razenshteyn. Optimal data-dependent hashing for approximate near neighbors. In Proceedings of the Forty-Seventh Annual ACM Symposium Theory of Computing, STOC '15, pp. 193-801, New York, NY, USA, 2013. Association for Computing Machinery. doi: 10. 24114452776639.7765533.
ISBN 978 274 2746553
httptttps://o..orppppp/o 1145/
Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. Ann-benchmarks: bench-
marking tool for approximate nearest neighbor algorithms. Information Systems, 87:101374, 2020. ISSN 0306-4379. doi: http:://obloooo/o....ollii222000 URL https://ww/
sciencedirect. wwt./c//cccc..eeeee.ea wttp:///...iaaaaaaa.aaa/////////
Artem Babenko and Victor Lempitsky. Tree quantization for large-scale similarity search and classification. In Proceedings of the IEEE Conference on Computer Vision and Pottern Recognition
(CVPR), June 2015.
Kirell Benzi, Vassiis Kalofolias, Xavier Bresson, and Pierre Vandergheynst. Song recommendation with non-negative matrix factorization and graph total variation. In 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 2439-2443, 2016. doi: 10.11091CAASP::211..77222
James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for hyper- parameter optimization. J. Shawe- Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K.Q. Wein- berger (eds.), Advances Neural Information Processing Systems, volume 24. Curran Asso- ciates, Inc., 2011. URL httpt:tt///// htttpss:/procceediiii
pdf
Nitin Bhatia and Vandana. Survey of nearest neighbor techniques. International Journal of Computer Science and Information Security, 8, 07 2010.
Tolga Bozkaya and Meral Ozsoyoglu. Distance-basedd indexing for high-dimensional metric spaces. In Proceedings of the /997 ACM SIGMOD International Conference on Management of Data, SIGMOD '97, pp. 357-368. New York, NY, USA, 1997. Association for Computing Machinery. ISBN 0897919114. doi: 10. 221144/2532202553344
URL https: org/ 1145/
253260. 2533415
Qi Chen, Bing Zhao, Haidong Wang. Minggin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, and Jingdong Wang. Spann: Highly-efficient billion-scale approximate nearest neighborhood search. In M. Ranzato, Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Ad- vances in Neural Information Processing Systems, volume 34, pp. 5212. Curran Asso- ciates, Inc., 2021. URL https: / http:///////oe//eeeeeeeeo newripe htcpssccc//eee http:/cappppp//2//LLLL. 299dc35e 74 7eb 7 771 (tt.:/11//1e11011/e
Paper. pdf
Paolo Cremonesi, Yehuda Koren, and Roberto Turrin. Performance of recommender algorithms on top-n recommendation tasks. Proceedings of the Fourth ACM Conference on Recommender Systems, RecSys 10, pp. 39-46, New York, NY, USA, 2010. Association for Computing Machinery, ISBN 978 100558900. doi: 10.1145/1864706 1111118677878...17111 UR//ttppss//dol.org//0011111111. 1864708. 864721
Criteo. Autofaiss: Automatically create faiss knn indices with the most optimal similarity search parameters., 2021. URL URL.htttss:///iithb.. com wwt.o////r////t////////aaee
Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni. Locality-sensitive hashing scheme based on p-stable distributions. In Proceedings of the Twentieth Annual Symposium
Computational Geometry, SCG '04, pp. 253-262 New York, NY, USA, 2004. Association for Computing Machinery. ISBN 1581138857. doi: 10.1145/997817.999785 URL https
//doi.org .rrg/ 10.0g//...115/9772000 997857
10

---

Published as a conference paper at ICLR 2023
Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. Fast approximate nearest neighbor search with the navigating spreading out graph. Proc. VLDB Endow., 12(5):461 jan 2019. ISSN 2150- 8097. doi: 10.14778/33337553333333 3303754
URL
Beat Gfeller, Blaise Aguera-Arcas, Dominik Roblek, James David Lyon, Julian James Odell, Kevin Kilgour, Marvin Ritter, Matt Sharifi, Mihajlo Velimirovié, Ruiqi Guo, and Sanjiv Kumar. Now playing: Continuous low-power music recognition. In NIPS 2017 Workshop: Machine Learning on the Phone, 2017.
Daniel Golovin, Benjamin Solnik, Subhodeep Moitra, Greg Kochanski, John Karro, and D. Sculley, Google vizier: service for black-box optimization. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '17, 1 1487-1495, New York, NY, USA, 2017. Association for Computing Machinery. ISBN 9781450348874, doi: /RLtts:s:///oi http:///ooooorg/1//// 11411 309993330993333 091199998833388884 3098043
10.1145/3097983
Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simeha, Felix Chern, and Sanjiv Kumar. Accelerating large-scale inference with anisotropic vector quantization. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 3887-3896 PMLR, 13-18 Jul 2020. URL
htttps://proceediii
mlr press/pes////e vww./v1119// quo20h. html
Kelvin Guu, Kenton Lee, Zora Tung, Panupong Pasupat, and Ming- Wei Chang. Realm: Retrieval- augmented language model pre-training. In Proceedings of the 37th International Conference on Machine Learning, ICML' 20. JMLR.org 2020.
Masajiro Iwasaki and Daisuke Miyazaki. Optimization of indexing based on k-nearest neighbor graph for proximity search in high-dimensional data. CoRR, abs/1810.07355, 2018. URL http:
//axxiv.org//bs////.
07355
Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with gpus. IEEE Transactions Big Data, 7(3):535- 547, 2021. doi: 10.1 (T1.://BDAAA..19.99222...
Herve Jégou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(1):117-128, 2011. doi:
10.1109/PAAM..2100.57
Urvashi Khandelwal, Omer Levy, Dan Jurafsky, Luke Zettlemoyer, and Mike Lewis. Generalization through memorization: Nearest neighbor language models. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 60-0, 2020. OpenReview.net, 2020. URL Btllattts///ppeereeee
CEERH
Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer:
The efficient transformer. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020, URL VK
net/ forum?id
Erik Lindgren, Sashank Reddi, Ruiqi Guo, and Sanjiv Kumar. Efficient training of retrieval models using negative cache. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 4134 4146. Curran Associates, Inc., 2021. URLLtttps:///poooeeeee /owp:////.///.oo.eeggg.......... www.ine...... wtw.iiss.c.paaaee cc/paper/ 2021
hot.ecccceeoooooooeeeeeee222eeed wetooleee662222222 Paper.
Rui Liu, Tianyi Wu, and Barzan Mozafari. A bandit approach to maximum inner product search.
Proceedings of the AAAI Conference on Artificial Intelligence, 33(01)4336-4388, Jul. 2019.
doi: 10. 1609/aaaii 133001.330143333333 .33014376.
aaai. wtt.://......a...oooeooooooooea /
article/view/433 4334
Yu A. Malkov and D. A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Trans. Pattern Anal. Mach. Intell., 42 (4):82 836, apr 2020. ISSN 0162-8828, doi: 10.1 109//PAAM.201882889447.. URL https:
7/doi Paaiiorg/1000 wtt..o..../....////./.. 11109/999/PTTT TMAMT 201 2889473
11

---

Published as a conference paper at ICLR 2023
Alexander May and Ilya Ozerov. On computing nearest neighbors with applications to decoding of binary linear codes. Elisabeth Oswald and Mare Fischlin (eds.), Advances in Cryptology EUROCRYPT 2015, pp. 203-228, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg. ISBN 978-3-662-46800-55
Antoine Miech, lean-Baptiste Alayrac, Ivan Laptev, Josef Sivic, and Andrew Zisserman. Thinking fast and slow: Efficient text-to-visual retrieval with transformers. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 9826-9836, June 2021.
Parikshit Ram and Alexander G. Gray. Maximum inner-product search using cone trees. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '12 pp. 931-939, New York, NY, USA, 2012. Association for Com- puting Machinery. ISBN 978 0781450314626 doi: 10.1445/233950022336677 URL https
7/doi 111.1...11111319300 2t1.55/2333333.33337773 2339677
Jie Ren, Minjia Zhang, and Dong Li. Hm-ann: Efficient billion-point nearest neighbor search on heterogeneous memory. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 10672- 10684. Curran As- sociates, Inc., 2020. URL /
meurips piss-ipp-- ctt wwwpppppppppppppppcccccccct..aat ccc/papprr/222//11ee 22000/F122///
Mohammad RezaAbbusifard, Bijan Ghahremani, and Hassan Naderi. Survey on Nearest Neighbor
Search Methods. International Journal of Computer Applications, 95(25):39 -2, June 2014. doi:
Anshumali Shrivastava and Ping Li. Asymmetric Ish (alsh) for sublinear time maximum inner product search (mips). In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Wein- berger (eds.). Advances in Neural Information Processing Systems, volume 27. Curran Asso- ciates, Inc., 2014. URL https: /ttp:////ccocccoeg.eeeooee new.ipsee.pppppppe wwt.:uisscccaaapeee..tt..c /ttpp/a//////////.l.ll.
pdf
Harsha Vardhan Simhadri, George Williams, Martin Aumüller, Matthijs Douze, Artem Babenko, Dmitry Baranchuk, Qi Chen, Lucas Hosseini, Ravishankar Krishnaswamy, Gopal Srinivasa, Suhas Jayaram Subramanya, and Jingdong Wang. Results of the neurips' 21 challenge on billion- scale approximate nearest neighbor search, 2022. URL htttss://aar.:t. hev.vorrggg org/ ab2/220 03763
Jingdong Wang, Heng Tao Shen, Jingkuan Song, and Jianqiu Ji. Hashing for similarity search: survey. CoRR, abs/1408.2927, 2014.
Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search. Proc. VLDB
Endow., 14(11::1944-197, jul 2021. ISSN 2150-8097. doi: 10.1477813476249.4477555 URL 14w0001.1111330 11w.:///.00111177777777777113111 1777777777722294977768
Ian En-Hsu Yen, Satyen Kale, Felix Yu, Daniel Holtmann- Rice, Sanjiv Kumar, and Pradeep Raviku- Loss decomposition for fast learning in large output spaces. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5640-5649, PMLR, 10-15 Jul 2018. URL https::/proceeeinngg wwr. press wtwpa/..peeeeeeeeeellllalcc http://///yeeeemnmmmmmm
12

---

Published as a conference paper at ICLR 2023
A APPENDIX
A.1 LSH GUARANTEES IN PRACTICE
LSH based approaches nearest neighbor search provide number of rigorous guarantees regarding memory usage and query time complexity as function of the approximation factor c, defined as follows: if the true nearest neighbor is distance of d from the query, the approximate algorithm is considered to have succeeded if it returns a point whose distance to the query is at most cd.
LSH algorithms are capable prescribing hyperparameter settings (size and number of hash tables) to provide optimal worst-case performance for given value of c. To see what these hyperparameter settings would imply for given recall, we take 90% recall@ 10 setting for Gl ove Section 5. and compute the resulting e for each query, giving us 10 ratios. In Table 2 below, we plot various statistics of these ratios and their implications for the resulting ANN hyperparameters, using the results from Andoni & Razenshteyn 2015):
Table 2: Statistics on empirically measured
Statistic on
Value of c
p 1/(2c² - 1)
Space Complexity
Estimated Space for Glove1M
Mean
1.00262
0.98962
O 1.99 + nd)
1.2TB
Median
1
1
O(n² + nd)
1.4TB
t5th Percentile
1
1
O(n² + nd)
1.4TB
90th Percentile
1
1
O(n² + nd)
1.4TB
99th Percentile
1.07024
0.77470
O( + nd)
60GB
We that even if we take the 99th percentile value, this leads to hash table hyperparameters that result over 60GB of memory usage, under the conservative assumption that the constant factor for the n 1.77 term is one byte. This is 128 times the size of the original dataset and already somewhat impractical; for scalle datasets, this would be completely intractable.
While LSH may perform better in practice this dataset than what the theory guarantees, and may not need such high memory consumption to reach this level of accuracy, such result would imply that the hyperparameters for hashing-based ANN algorithms difficult tune and model, not unlike the hyperparameter-tunigg challenges that other ANN algorithms face.
A.2 FACTORIZED RECALL ASSUMPTION
Here we describe in detail the approximation (9E5.(a.1) ~ (ee) used simplify Equation The event g E S,(q, t) is equivalent requiring both g E S,-1(q. t) and finding fewer than t; points closer to q than datapoint according to quantization i, which we can express as:
L LgeS((a.t) AgES
I JES.
Σ
<t sti.
Now define S,-1(q,t) to (I....,m]] SS-1199, t), and consider some element j E (g-1(g.t) t). For the following section, we assume y E S,-1(g, t), which implies D(g, X (()-1)) < D(g, (((-))), We split our analysis into two cases:
1. j & G(q): this is by far the common case, where quantization i correctly removed non-nearest-neighbor from the candidate set. This means quantization - 1 has already ranked the relative distances of and g correctly; given that quantization higher bitrate than i - and is therefore even less likely to mis-rank the relative distances, we know almost surely that D(g. x(()) D(q. 2()).
2. j E G(q): quantization are picked uniformly without replacement from ((z), then with the original dataset X,
has dropped a nearest neighbor. If we assume j and
13

---

Published as a conference paper at ICLR 2023
PiD(q, Xg)
D(q. 1/2. However, quantization 209, we approximate that
P(D(g, Xg (0))
< D(g, X3 = 1 with the following justifications:
Given that (g,, x ) < 2(1, g is likely closer to than j is, so the uniform sampling model used above for g and j leads to an underestimated probability. Even if is in fact the closer neighbor, the hierarchical nature of multi-layer quantization training implies that there is some correlation between distance mis-rankings among the different quantization layers. If Dgg, X ) < D(g, XJ. R(1-1) then there is higher chance that (g,, ) < D 2)
g
Combining the results from our two cases, we see that if g E S t), then the number of elements in (1 1) that will rank closer to y than y according to 8() is approximately zero:
Σ
965.-1(9.1))
)ESL-1(9.1)
We can add this expression to Equation and utilize definition from Equation to conclude
(ES)(())) 10.0)
(E8--1n (
Σ
Lges 1(a,t) (gES((a))))
A.3 EXTENSION OF COST MODEL TO BATCHED QUERYING
The main speedup from query batching in quantization- ANN algorithms arises from the fact that the same quamtized data may be reused to score multiple queries. This conserves memory bandwidth, resulting in better performance, because memory bandwidth is scarce relative to arithmetic throughput in modern hardware. To account for this in our cost model, we first rewrite Equation as
m-
((t) 4
|200
+
Σ
(804121)
X
06 1(0)
X
where a; is the proportion of 800)) that is searched; amount of memory bandwidth consumed in searehing this quantization level for batch of size B is approximately min(1, a; (,)), while the number of arithmetic operations performed is a, B) ())) Applying the roofline model to this algorithm, where we are bandwidth-bon bound in the small-batch regime and compute-bon bound in the large-batch regime, gives the following new cost model:
and a; f:-1/n for i > 1. The
[t, B) A
max(a, min(1, a, B))
X
where p is the ratio of the hardware's arithmetic performance to memory bandwidth. In practice. query batching is of limited utility in large-scale ANN because a; is so small that the algorithm will still be bandwidth-limen limited,, resulting no performance boost.
A.4 SINGLE- SINGLE-LAYER CANDIDATE SET RECALL CURVE COMPUTATION
Our goal is to efficiently compute L: from Equation 5 reproduced below:
14

---

Published as a conference paper at ICLR 2023
-log S (() [9(4)
(((2 Eg
We want compute this quantity for all 4 {l...., n and for all quantization levels. As a prerequisite, we first require the ground truth ((q) for all q E Q. Note this ground truth is required to compute the recall of any ANN algorithm and therefore should be computed regardless of whether our technique is used. We can store the ground truth results in matrix G {l,..., ...,, m where n is the number of elements the dataset, Nig is the number of elements in the Q, and k the number of neighbors want to retrieve per query.
Now for each ground truth element, we compute its distance from the query for every dataset g())
quantization. This may be expressed as computing U E Rm..xxxk where Ua,b.c D(Q,, Ga.e We then sort each Ua.b so that Ua,be Uabb for all {l,..., k...,,k11p 13. From U we then compute a matrix V E No, xmxk where Va,b.c stores the number of distances between query 2a and ( that are less than Ma Ma.hci
12
Va Σ
D(Q Di 2/9)
Note that because Ua.5 was sorted, Va, will be sorted as well. The entry Va,ae indicates the search depths at which recall for query 2, with quantization ()) increase. For example, if Va, = [1, 8). we can conclude that recall for this query-quantiationn combination will be 0 when returning only the top index, 1/3 when returning the top or indices, 2/3 when returning the top 3 through indices, and 1 when returning the top 8 more indices. Once we have V, it is simple matter of taking logarithms and aggregating over queries to compute Lt.
The computational bottleneck to this routine is computing V; must compute the query- distance for all queries over all dataset quantizations, which takes O Th E (2((0) time, where
| denotes the memory footprint of quantization i. For each distance must then decide how many of Ma, b it is less than, which takes Ollgg k) time per distance using binary search. We can
estimate the number of distances (mn)) although this an overestimate because VQ-quantized layers will result in fewer than n distances being materialized. Overall, this gives our routine runtime of
O
Phg
[(00| + n. mn
mmamlogi log
To analyze this expression further, let (200 n rs. where ra is the compression ratio for quantization Our runtime then be expressed as mn Ed T3 m k:); the first term tends to dominate due to the presence of d.
This routine relatively cheap; to compare, the computation of ground truth nearest neighbors, which is generally done as part of any ANN indexing routine, takes (n) time. Assuming as above that the first term of our runtime dominates, our routine is multiplicative factor of Σ P' as expensive, which in practice with typical quantization hierarchies is below 2.
A.5 FAST MINIMIZATION ALGORITHM FOR DYNAMIC LAGRANGE MULTIPLIERS
Our goal is to quickly perform the optimization
arg min -J((1) Σ (.(1)) mm
s.t. 41 2 t.m
15

---

Published as a conference paper at ICLR 2023
quickly for dynamic values of X. with all other inputs constant. We first describe the zero- preprocessing, ((m) time dynamic programming solution to this problem, which we then optimize to arrive at our final O(m log n) approach.
A.5.1 BASIC DYNAMIC PROGRAMMING APPROACH
For fixed X, our optimization is equivalent to selecting non -occencegg indices t Ei...., ,.....,t............ f. such that Σx=1 My,,, minimized, where the matrix M Rmxxn defined as Maj = -J Now we define our dynamic programming subproblem as selecting the first a indices .1,...:4 La such that all indices are at least equal to b. We can store these subproblem answers another matrix M':
Ma.b A
min rE(b,]
Mi
S.L. 1 ... La-
Using the state transition Ma, = min(M) 0,641 Ma.6 + M Ma11,a) allows us to compute all of M' and receive the resulting minimum, located at M in (mm) time. The approach may be augmented with cost and history matrices so that Jt), Σ Lis and the selected indices I; may be recovered as well.
A.5.2 FASTER ALGORITHM LEVERAGING CONVEXITY
Recall that all L. are convex, and is linear, every row of M is convex. Inductively, that this leads to the rows of M' being convex as well, which we take advantage to accelerate algorithm. First, define j* (i) as the rightmost index in row achieving the row-wise minimum in M"; (i) = max(j M = ming - Due to the convexity of M', we know that My, is strictly increasing with respect to j for all j > (i). Combined with this equivalent expression for computing M"
Ma.
min je
Ma.j Ma-1.
(8)
it's clear that M/ is equivalent to M, + M. in the column range (1), n). Meanwhile, Mi, Mi Mia00) for j (i).
Now let's inductively assume that M is composed of number of piecewise components, where the ktth component equals the sum of the most recent rx rows of M plus a constant and is responsible for the columns j E [L,, rx]. From Equation we can see that upon the transition from M,-1 to M all pieces to the right of (i) will be incremented by M,. All pieces left of j ji() will be replaced with constant offset equalling ()) maintaining our inductive hypothesis. The base case for this hypothesis is also easily verified, as we see Mí equals Mj in the range j E (1), n). and left of that range it equals the constant M M1)-(1))
This realization allows for faster approaches our minimization problem by allowing M' to be implicitly represented rather than explicitly computed. We maintain the set of piecewise components as we traverse from row to m. At each row, we have to find ji(i) and update our set of components accordingly. The search for j (i) may be done efficiently by taking advantage of the convexity of M' via binary search. We first binary search over our components to find the one containing the global that component. Computing
minimum, and then binary searching among the indices belonging the value within a component may be done in ((1) time once prefix sum array over L and are created; these data structures allow contiguous sums over M with dynamic X. The component list update then takes (11) amortized cost per row, because only one component is added per row.
There at most min(m- 1, components and any component may have range of at most indices, so the resulting minimization takes (m log n) time. Calculating the prefix sums over L and J result in ((m) preprocessing time for this algorithm.
16

---

Published as a conference paper at ICLR 2023
X;: Level
X1: Level 2 PQ
X1: Level
4 100 x bytes; ~ 480KB
4- 10 x 12.5 bytes; 500KB
4 10 bytes; ~ 1MB
.g Level 2 Centroids 8)
Pg Level Centroids nt
8g Level 2 Centroids (t
x 96 bytes, 3.84MB
4 10 100 bytes; 1MB
x 200 bytes: 8MB
Rs Level PQ
Xs Level 1 PQ
R Level PQ 4 10 34 bytes; 13GMB
10 x 16 bytes, 64MB
4 10 bytes; 68MB
24: Level Centroids (: 8)
Rg: Level Centroids (: (:nt8)
X4 Level Centroids (: 8)
4 10 96 bytes; 384MB
4 10 100 bytes; 400MB
10 200 bytes: 800MB
Rs: Dataset PQ
Xs: Dataset PQ
Xy: Dataset PQ
108 48 bytes; 48GB
10a x 50 bytes; 50GB
10a 50 bytes; 50GB
Dataset (int&, stored) 10 x 96 bytes; ~ 96GB
Dataset 8int8, not stored) x 100 hytes; ~ 100GB
Dataset (int&, stored) 102 200 bytes; ~ 200GB
(a) DEEPIB
(b) Microsoft Turing-ANNY
Yandex Text-to- --aa-
Figure 6: Multi-level quantization hierarchies used for the three billions-scall datasets of Section 5.2
A.6
BILLION-SCALE SEARCH EXPERIMENTAL SETUP DETAILS
Track of the https: ann henn-bbhchaakss com competition stipulates that:
Query-time benchmarking is done on Azure VMs with 32 vCPUs and 64GB RAM.
Indexing takes place on Azure VMs with 64vCPUs, 128GB RAM, and 4TB SSD, and must finish within 4 days.
Our query-time serving was performed on 16 physical cores from an Intel Cascade Lake-generation CPU, and peak memory usage was measured to under 58GB. Azure counts one physical core as equal to 2 vCPUs, so setup matches the competition requirements.
For indexing time, our index was constructed via a distributed computing pipeline. For DEEPIB, the pipeline ran in approximately 1.5 hours and in total consumed approximately 538.0 vCPU-hours of compute power. Approximately 16.3 VCPU-hours, or 2.7% 7% of the overall indexing job's resource consumption, was spent on computing L for in our convex optimization routine. Other datasets were comparable in runtime. They were all significantly under the 6144 vCPU-hours available under the competition specifications, and furthermore the VQ and PQ training involved in the pipeline have low peak memory and disk requirements, so our indexing procedure comfortably qualifies under the competition rules.
A.6.1 HIERARCUICAL QUANTIZATION INDEX DETAILS
The three diagrams below describe in detail the quantization hierarchy used for the three billions-scale datasets in Section 5.2 We would like to emphasize that all three datasets used the same VQ and PQ settings-ti the datasets are first quantized to 10 centroids, and then again x 10* centroids. The PQ was performed with 16 centers (4 bits) per subspace, 4 dimensions per subspace at the X1 level, and dimensions per subspace (rounding up) at the X's level. Only the Yandex Text-to-Image dataset differs at the X level with its PQ setting (using dimensions per subspace instead of 1), but dataset into the same RAM footprint.
this was only to fit the higher-dimension
Even though technique cannot set these VQ and PQ parameters, the fact that we achieve excellent performance on all three datasets using the same VQ and PQ parameters, despite these datasets giving drastically different speed/recall Pareto frontiers, suggests the VQ and PQ parameters are not as difficult a part of the tuning problem and have more predictable good settings than the hyperparameters our technique deals with.
17

---

Published as a conference paper at ICLR 2023
IMPACT OF QUERY SAMPLE SIZE ON HYPERPARAMETER TUNING QUALITY A.7
100 Queries Queries
10000 Queries
45000
Queries per Second
40000
35000
30000
25000
20000
15000
0.68
0.70
0.72
0.74
0.76
0.78
0.80
Recall@110
Figure 7: Achieved search throughput and recall for tunings generated from different query sample sizes on the Microsoft Turing-ANNS billion-scale dataset.
larger query sample should lead to our optimization finding better hyperparameter tunings, but would also lead to greater cost in computing 4, whose runtime is linear in the query sample size. In this section, we explicitly measure the effect of increasing query sample size by taking the 10a queries from the MS-Turing dataset of wig--nn--eern -bnnchhacss,,s, holding out 10 queries as test set, and sampling subsets of 100, 1000, and 10000 queries from the remaining each subset size, nine samples were taken, all disjoint from other subsets of the same size.
10 queries. For
For each query subset, we run our constrained optimization technique to generate low, medium, and high search cost ANN algorithm hyperparameter tunings, and measure the resulting recall and search throughput on the holdout query set. The search cost targets for the low, medium, and high settings were (t) 2 x 10 5 10 and 1.2 x 10-5, respectively. The resulting recalls and throughputs are plotted in Figure 7
We can see that increasing the query sample size from 100 to 1000 leads to considerably less variance, with the resulting hyperparameters more consistently approaching the global cost-recall Pareto frontier. However, increasing the sample size further from 1000 10000 has very marginal impact. The query sample size was kept at 1000 for the experiments in Section 5.2 and is reflected in the vCPU-hour measurement in Appendix A.6
A.8 PERFORMANCE OF FEW-LEVEL QUANTIZATION HIERARCHIES ON DEEPIB
In Section 5.2 use a five-level quantization hierarchy search the DEEPIB, Microsoft Turing- ANNS, and Yandex Text-to- Text-to-Image datasets from -er-ann--ee..haaaee Our hyperparameter tuning technique was necessary because the dour-dimensional hyperparameter search space was impractically large for grid search. If we had built an ANN search index with fewer quantization levels, a simpler grid search approach could be used to find effective hyperparameters; in this section, confirm that such shallow search indices perform poorly on DEEPIB, thereby ruling out grid search as a viable option.
To test this, we take the original quantization hierarchy, described in Figure 6 and modify it in two ways. In one, we keep only the top-level x 10t VQ centroids and remove the intermediate layer of 4 x 10 centroids, to create the Shallow-Smal 11 quantization index; in the other, remove the tep-level centroids and only keep the x 10 centroids from the middle layer of the hierarchy. These two modified quantization indices are illustrated in Figure
18

---

Published as a conference paper at ICLR 2023
X1: Level 1 PQ
L1: Level PQ
4- 10 12 bytes; 480KB
4 10t 16 bytes; 64MB
Zy: Level Centroids (int 8)
X2 Level 1 Centroids (int B)
4 10 x 96 bytes; 3.84MB
4 10 x 96 bytes; ~ 384MB
Rz: Dataset PQ
Az. Dataset PQ
10 x 48 bytes; ~ 48GB
10 x 48 bytes; ~ 48GB
Dataset (int 8, not stored)
Dataset (int8, not stored) 109 x 96 bytes; 96GB
100 x 96 bytes; ~ 96GB
(a) Shall Soalloow-Smlll quantization index
(b) Shal wwwlooowwarrrr quantization index
Figure 8: The two quantization hierarchies we compare in this experiment against the original one used in Section 5.2 and described in Figure
The Shallow-Small and Shallow-Larg indices both have three quantization levels and therefore two-dimensional hyperparameter search space. We use grid search to explore this space, and plot in Figure the resulting speed-recall Pareto frontiers against the original frontier from Section 5.2
We see that both Shallow-Smal and Shallow- perform extremely poorly relative to the original five-layer index. Qualitatively, of its 4 x 10a centroids, which implies the search cost of further searching any centroid is high; in addition, any given datapoint is unlikely be quantized well by its centroid (due the relatively low number of centroids), so the quality of results also tends to be low. Mcanwhile, Shall aollowwoaae Large has so many centroids that always spends large fixed on level PQ distance computation.
has many datapoints assigned each
100000
90000
Shallow-Small Shallon-Large
Speed (Quertes per Second)
80000
Original
70000
60000
50000
40000
30000
20000
10000
Accuracy (Recall@(10)
Figure 9: Both three-level quantization indices perform very poorly relative to the original five-layer quantization index DEEPIB.
19


Reviews:
[{"review_id": "g9c57FW1oo", "reviewer": "Reviewer_vMnt", "summary": "", "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": "", "summary_of_the_paper": "The paper uses the recursive vector quantization ANN method, which can also be seen as a hierarchical VQ approach. The proposed method provides an optimization-based approach to fine-tune this ANN method. The analysis was made on million-scale and billion-scale ANN datasets. ", "summary_of_the_review": "The constraint optimization formulation is based on the search time and recall is intuitive, however, the applicability of the optimizer is questionable for the unseen query data. ", "strength_and_weaknesses": "Strengths:\n\n1) The paper is novel and shows a performance improvement over baselines with negligible optimization cost.\n2) The optimization cost is carefully designed. The method is based on maximizing the geometric mean recall for maximizing the ANN recall. It maximizes the arithmetic mean lower bound. To minimize the ANN search time, it minimizes memory accesses during the query phase. The overall constrained optimization maximizes the recall with the given search time constraints. \n3) The authors have shown the benchmark against the grid search and one black box search method- Vizier.\n\nQuestions and weaknesses:\n1) Overhead of the parameter tuning: How does the parameter tuning time compare with the Black- box optimizers such as Vizier?\n2) What is the rationale behind choosing the recall rate as the objective?:  The objective function is the recall rate, and the constraint is the search cost. Does the opposite, where the objective function is the search cost, and the constraint is the recall rate, results in a similar performance? \n3) Please correct me if I am wrong here: What query set is used for computing the objective function- $\\mathcal{L}_i (t_i)$? As mentioned in 5.4, it looks like the query set is being used for optimization. However, this will not suit well for the real-time near-neighbor search, where the queries are unseen and seen one-by-one or batch-by-batch as a stream. The optimization cost should be negligible to achieve a real-time performance here.\n4) With an assumption of an in-distribution query set (same distribution of index and query points), this can even use a fraction of index data to optimize the parameters.\n5) Are there any other black box optimizers available for the ANN parameter tuning?\n6) Section 5.4: The random split of the query set $Q_1$, and $Q_2$ is not the best way to see the out-of-sample performance. A better split where $Q_1$ and $Q_2$ are itself out of distribution to each other may be a better way to test the out-of-sample performance. Please clarify if I am missing something here.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "PllT6RwRVkN", "reviewer": "Reviewer_F6KH", "summary": "", "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": "", "summary_of_the_paper": "ANNS algorithms, especially those involving quantization, have many hyperparameters to tune. Careful tuning can yield significantly better accuracy and query throughput. However, tuning can be expensive, especially for large indices, if done naively (build the index and search). Therefore, the authors design a proxy loss metric to guide the hyperparameter search using a simple linear-scan based algo. This loss is an approximation of the metrics that matter in practice. Using this they show that on billion scale datasets, the tuning can outperform baselines by a margin and improve upon blackbox optimizers. Further, the authors entry won Track 1 of a recent NeurIPS challenge on large scale ANNS.", "summary_of_the_review": "The results presented in the paper are a great improvement over baselines, however the paper could be stronger if it generalizes to interactive query processing or to other algorithms rather than the linear scan. It could be that the techniques are applicable, but couldn't ascertain this in my reading of this paper. I would rate the paper higher if this was the case.", "strength_and_weaknesses": "Strengths:\n1. Good empirical results -- improves significantly on baselines, outperforms blackbox tuning (e.g. Vizier) and on small scale datasets closely matches exhaustive tuning\n2. Results demonstrated on multiple large scale datasets.\n\n\nWeakness:\n1. Not much discussion on applicability to tuning algorithms other than the linear scan in the paper. \n2. Its not clear that the techniques can be applied for interactive query processing.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "JvupWHi_6r", "reviewer": "Reviewer_cFiP", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "This paper looks at the problem of hyperparameter tuning for the Approximate Nearest Neighbor (ANN) search. The authors propose a constrained optimization-based approach for tuning the quantization-based ANN methods. They only require a search cost or recall as input, then the Lagrange multipliers-based approach can provide a configuration such that the performance reaches the speed-recall pareto frontier. Extensive results confirm the superior performance of their proposed method. \n", "summary_of_the_review": "In summary, I think the motivation is clear, the idea is sound, and the paper is written well enough. Thus, I tend to initially give acceptance to this paper.", "strength_and_weaknesses": "The paper has the following strengths:\n\nS1. The motivation is clear. As the dataset size increases significantly, tuning the parameters (manually or using traditional methods like grid search and black box optimizer) becomes computationally prohibitive. It is in significant demand to have a theoretically grounded yet computationally lightweight approach that can produce excellent performance.\n\nS2. The proposed method is novel and easy to use. The input is simply the search cost or recall, which is friendly for fresh users unfamiliar with the ANN methods' details. The authors also provide sufficient insights and theoretical analysis when they introduce their idea.\n\nS3. This paper is well written with clear clarity and thus is easy to read.\n\nThe paper has the following weaknesses:\n\nW1. In the last paragraph of the introduction section, they claim their approach is very general and can be extended to distance measures, quantization algorithms, and search paradigms. It would be nice if they could simply illustrate how to extend such a claim, e.g. for different search paradigms.\n\nW2. In Section 5.2, they claim they compare to heuristic, hand-tuned, and black-box optimizer settings. However, I cannot find such settings in Figure 2, and Figure 3 only depicts the comparison with a black-box optimizer Vizier. Moreover, the baselines that are shown in Figure 2 lack explanations. \n\nW3. In Section 5.3 and Figure 4, could you explain what $R^2$ is?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "FFjDGnx8So", "reviewer": "Reviewer_DrxR", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "The paper covers a new method for approximate nearest neighbour search aimed at very large datasets where hyper-parameter optimisation can be achieved efficiently.  The hyper-parameter optimisation uses some clever approximations that then allow very efficient optimisation.  The performance is measured empirically and shown to give better results than current methods.", "summary_of_the_review": "This is a well written paper with a nice idea that looks well motivated and technically sound.  The empirical results back up the claims (there is one approximation about independence that needs empirical justification).  In my view this is a good paper that deserves publication.", "strength_and_weaknesses": "This is a well written paper.  The idea is elegant and sophisticated.  The empirical evaluation looks very convincing.\n\nAlthough this is not my research field I see no obvious weaknesses.  Two very minor points that can be easily corrected.  The first is the Pareto should be capitalised as it refers to a proper name (Vilfredo Pareto).  Secondly, I might be wrong but I could not see a reference to Figure 2 in the text.  I think this should be referenced in Section 5.2.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster