Optimistic Query Routing in Clustering-based Approximate Maximum Inner Product Search
Authors: Sebastian Bruch
Aditya Krishnan
Franco Maria Nardini
Venue: NeurIPS 2025 poster ()
Keywords: maximum inner product search
clustering-based nearest neighbor search
query routing
sketching
optimism principle
Primary area: other
TL;DR: We present an optimistic query routing protocol in clustering-based approximate maximum inner product search that reaches the same accuracy as SoTA routers by probing 50% fewer data points.

Abstract: Clustering-based nearest neighbor search algorithms partition points into shards to form an index, and search only a subset of shards to process a query. Even though search efficacy is heavily influenced by the algorithm that identifies the shards to probe, it has received little attention in the literature. We study routing in clustering-based maximum inner product search, which includes cosine similarity search. We unpack existing routers and notice the surprising role of optimism. We then take a page from the sequential decision making literature and formalize that insight following the principle of ``optimism in the face of uncertainty.'' In particular, we present a framework that incorporates the moments of the distribution of inner products within each shard to estimate the maximum inner product. We then develop a practical instance of our algorithm that uses only the first two moments to reach the same accuracy as state-of-the-art routers by probing up to $50\%$ fewer points on benchmark datasets without compromising efficiency. Our algorithm is also space-efficient: we design a sketch of the second moment whose size is independent of the number of points and requires $\mathcal{O}(1)$ vectors per shard.

Optimistic Query Routing in Clustering-based Approximate Maximum Inner Product Search
Sebastian Bruch
Aditya Krishnan Microsoft New York, NY, USA
Northeastern University
Boston, MA, USA
bruchhhortheasterm.co
adkrishnan holkrisshaanmmmicoooot...ooom
Franco Maria Nardini ISTI-CNR
Pisa, Italy
francomaria mardini@isti. wetasti.cnr.tt cnr.it
Abstract
Clustering- nearest neighbor search algorithms partition points into shards to form an index, and search only a subset of shards to process query. Even though search efficacy is heavily influenced by the algorithm that identifies the shards to probe, it has received little attention in the literature. We study routing in clustering based maximum inner product search, which includes cosine similarity search. We unpack existing routers and notice the surprising role of optimism. We then take a page from the sequential decision making literature and formalize that insight following the principle of "optimism in the face of uncertainty." In particular, we present a framework that incorporates the moments of the distribution of inner products within each shard to estimate the maximum inner product. We then develop a practical instance of our algorithm that uses only the first two moments reach the 50% fewer points on benchmark datasets without compromising efficiency. Our algorithm is also space-efficient: design a sketch of the second moment whose size is independent of the number points and requires O(1) vectors per shard.
accuracy tfate-of-the-art routers by probing up
Introduction
fundamental operation in many applications of machine learning is nearest neighbor search [Bruch 2024]: Given m points denoted X' C Rd it finds the & closest points to a query q E Rd where closeness is by vector similarity distance. We focus inner product, giving the problem of Maximum Inner Product Search (MIPS), which includes Cosine Similarity search as a special case:
(k) S = arg max uEX
(q. u).
(I)
As m or grows, an exact solution often difficult obtain within reasonable budget. The problem is thus relaxed to its approximate variant, where we tolerate enror to gain speed. The effectiveness of Approximate Nearest Neighbor (ANN) search is characterized by recall or accuracy, defined as the fraction true nearest neighbors recalled: |Š SS/k: S being the set returned by the ANN algorithm.
Clustering- based ANN search: ANN algorithms come in various flavors, from trees [Bentley 1975
Dasgupta and Sinha 2015 LSH Indyk and Motwani 1998 graphs [Malkov and Yashunin, 2020 Jayaram Subramanya et al. 2019 Refer to [Brcch] 2024 for a review of this subject. The method
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

relevant to us is the clustering- based approach, also known as Inverted File, which has received much attention in the literature Auvolat et al. 2015 Babenko and Lempitsky, 2012 Chierichetti et al.
2007 Bruch et al. 2024 Douze et al.) 2024 and is widely adopted in industrial applications |
In this paradigm, X' is partitioned into C' shards using a clustering function Ç IR + [C] [C]-typically KMeans with C = O( (y))). Accompanying this index is a router T I2 + [C]', which returns shards likely to contain q' is nearest neighbors. If μu is the mean of the i-th shard, a common router is:
(e)
(()) arg max (g. Mi).
cE(C]
Processing a query involves two independent subroutines. The first, "routing," returns shards using r(g). and the subsequent step. "scoring," computes inner products between q and the points in the l' shards. While the literature has focused on scoring (Jégou et al., [011] Ge et al., 2014 Wu Norouzi
al. 2017 Andre et al. [202]] Kalantidis and Avrithis 2014 Johnson et al. [ | and Fleet
And7
2013 routing has received little attention. This work turns squarely to the routing step.
We emphasize that, routing is independent of the scoring algorithm. For example, we may route using Equation (2) or our novel router to be introduced later. This choice has no algorithmic bearing on scoring whatsoever. In other words, scoring can be accomplished by linear scan of the chosen shards, computing inner products with Product Quantization (PQ) [Jégou et al. [011], or searching each shard using graph ANN algorithm Dayaram Subramanya et al. 2019 Malkov and Yashunin 2020). All these choices are independent of the type of router utilized in the earlier stage.
The importance of routing: The historical focus on scoring makes sense. Even though routing narrows down the search space, selected shards may contain a large number of points. Scoring must thus be efficient and effective.
We argue that the routing step is important in its own right. First, a more accurate router leads to fewer data points being scored. For example, if shards are balanced in size, access an oracle router (i.e., one that identifies the shard with the true nearest neighbor) means that the scoring stage must only compute inner products for m/C points find the top-1 point.
The second reason pertains to scale. As size and dimensionality grows, it is often infeasible to keep the entire index in memory, compression techniques such as PQ notwithstanding. Much of the index must instead rest on secondary storage cheaageeeeeepppp but high-latency storage such as disk or blob storage-and accessed when necessary. That line of reasoning has led the emergence of based graph indexes [Jayaram Subramanya et al. 2019 Singh et al., 22021] Jaiswal et al. 2022].
Translating the same rationale to the clustering- -hasedd paradigm implies that shards rest outside of memory, and when a router identifies subset of shards, scoring must first fetch those shards from storage. This paradigm has gained traction in real-world database systems This is the context in which we present our research: backee-backkd, clustering- -bsed ANN search systems.
In this framework, more accurate router lowers the volume of data transferred between storage and memory with implications for storage bandwidth and in in-memory cache space utilization, and retrieval throughput. We have included an illustrative example in Appendix to support this statement.
Existing routers and the role of optimism: We review the relevant literature on routers Ap- pendix B Among existing routers, Equation (2). which we call MEAN, is the most prominent. It summarizes each shard by its mean point (μ43 's). This is not an unreasonable choice as the mean is the minimizer of the sum of squared deviations from the mean, and is, in fact, natural if ( is KMeans.
Another common router, which we call NORMALIZEDDMANT belongs to the same family, but its shard representatives are the noromlile means, rather than the unnormalized mean vectors:
(2)
r(g) = arg max (q.
|0.l12
iE[O)
'See for http::///ubboouute....coo//o//ep google/blog//neee
https://www. htsp:://www.innecoe..ou and https://researe:
WW quantify router's accuracy by the ANN recall in setup where scoring by a linear sean over the identified shards, so that the only source of errrr is the routing procedure.
c..f, documents linked in the footnote above.
2

---

0.975
NomsAtaronilee MEAN
0.950
NUMBER OF POINTS
PorthocuuT
NUMBER OF POINTS
ToP-1 RECALL
0.925
0.900
10
0.850
10
1.0
2.0
% POINTS PRODED
SCORE
SCORE
(a)
(b)
(c)
Figure 1: (a) Top-1 recall vs. percentage of points probed on TEXT2IMAGE where points have
varying norms; (b) and (c) Distribution of inner products between a shard and query on GLOVE. Overlaid are scores computed by MEAN and NORMALIZEDMEAN.
This formulation is inherited from spherical KMeans [Dhillon and Modha 2001]. which identical standard K.Manns except that cluster centroids normalized after every iteration. Because can assume that ||ql|2 = without loss of generality, Equation routes by the angle between g and ss.s.
seems appropriate for search over sphere: When norms are constant, only angles matter in Equation ( making it reasonable to rank shards by the angle between means and g. Intriguingly, in many circumstances that deviate from that situation, NORMALIZEDMENN performs more accurately than MEAN, as evidenced in Figure I(a)
Let us unpack this phenomenon.
Consider and a single shard P with mean Figure [(b) visualizes the distribution of inner products of q and all points in P. Overlaid the inner product of q and μ., as well their normalized mean. We observe that (q. w/llell2) lands in the right tail of the distribution.
That is not surprising when ||u]22 (q, /)//lll 2 14:: NORMALIZEDMEAY amplifies MEAN by a factor of 1/11/4/22 What is interesting, however, is that the magnitude of this "boost" correlates with the variance of The more concentrated P is around the direction of jr, the closer is to the surface of the sphere, making ||и||2 larger, so that NORMALIZEDMEAN applies smaller boost (g, p). The opposite is true when points are spread out: shards with a higher variance receive a larger lift by NORMALIZEDMEAN,
for all P. Clearly ||a||2 S 1, that (q, p///lllll
There few caveats. First, it is hard to explain the behavior on sets with varying norms. Second, as we observe in Figure [(c] CORMALIZEDMEEA. insight that router's score for shard can be influenced by the shard's variance is worth exploring.
estimate can be overly aggressive. Nonetheless, the
Contributions and outline: From the exercise above, we learned that NORMALIZEDMEAA paints an optimistic picture of what the maximum inner product of q and could be. MEAN, however, gives conservative estimate. We investigate the ramifications of that insight in this work.
In particular, the research question study is whether more principled approach to designing optimistic routers leads to more accurate routing on vector sets with variable norms. This question is unlike those asked in the online learning literature [Lattimore and Szepesvári 2020), it is surprising that our answer draws from the "principle of optimism in the face of uncertainty."
We apply the Optimism Principle to routing in clustering blused MIPS. Our method, presented in Section 2 uses the concentration of inner products between a query q and points in a shard. In particular, we estimate score, 0,, for the i-th shard such that, with some confidence, the maximum inner product of with points in that shard is at most 0, Shards are then ranked by this score. When 0, 14, recover the MEAN router, and when 0; > (4; routing is optimistic with controllable degree of optimism. Importantly, our routing function is independent how shards are formed.
We outline general framework that can incorporate much information is available about the data distribution to estimate 0, s. We then present concrete, assumption-free instance of our algorithm that uses the first and second moments of the empirical inner product distribution only.
3

---

Furthermore, we make the resulting algorithm space-efficient by designing a sketch [Woodruff] 2014] of the second moment. The end-result is a practical algorithm that is straightforward to implement.
We test our proposal in Section 3 on a variety of ANN benchmark datasets. As our experiments show, our optimistic router achieves the same recall state-of-the-art routers but with up 50% reduction in the total volume of points evaluated per query. We conclude this work in Section 4
2 Routing by the Optimism Principle: our proposal
As we observed, NORMALIZEDMEAN is an optimistic estimator, though its behavior is unpredictable. Our goal is to design an optimistic estimator that is statistically principled, thus well-behaved. Throughout this section, all discussions are in the context of fixed unit-vector q. We denote the i-th shard by P,, and write S; for the set of inner products of and points in Pa: S; = {(g, u) E Pi).
2.1 Formalizing the notion of optimism
We wish find the smallest threshold 0, 2 (g, (4;) for the i-th shard such that the probability that sample from S; falls to the left of 0g is at least (1+ 60)22. for some arbitrary 8 E [0, 1]. Formally, we aim compute a solution 0, the the following optimization problem:
Problem 1 (Optimistic estimator of the maximum inner product in S,).
S 0.) 2 1
inf 0g 2 (g. p4) such that
Pr [a ar
The optimal 0; is a probabilistic upper-bound bound on the maximum attainable value in SN that is, with some confidence, can assert that value in S; is greater than 0,. We then route q by sorting P,'s by their 0; in descending order and select the top shards. Our router, OPTIMIST, is defined as follow:
(2) arg max 8,. iE[C]
7 T44)
Suppose that we have the solution Problem 1 As + O, the optimal solution approaches 0, = (g, pt), (g. M,)), where M, is the median of P,. That is a conservative estimate of the maximum inner product. As 8 + 1, 0g becomes larger, rendering Equation (4) optimistic. At the extreme, the optimal 0; is the maximum inner product itself the most optimistic we can get.
Clearly 5 controls the degree of optimism. When the distribution is fully known, 5 1 is an appropriate choice: If we know the distribution of inner products, we can expect to be fully confident about the maximum inner product. But when very little about the distribution is known, then ó 0s a sensible choice. In effect, the value of ō reflects our knowledge of the data distribution.
What is left address is the solution to Problem [ which is the topic of the remainder of this section. We first describe a general approach that uses as much information as available about the data distribution. We then present practical approach that is the foundation of the rest of this work.
2.2 General solution
Let 'D be an unknown distribution over IR. from which P, is sampled. clear that, if we are able to accurately approximate the quantiles of S;, we can obtain an estimate 0, satisfying Problem [
We motivate our approach by considering a special case where D is N(u,, E.), Gaussian with mean M4s Rd and covariance Σ, Rdd In this case, S; follows univariate Gaussian distribution with mean (g. (5) and variance E,g, so that the solution to Problem is simply:
1+
0: = (g. pa) + V Eig & (((1)))
(5)
2
which follows by writing the cumulative distribution function (CDF) of S; in terms of the CDF of a unit Gaussian, denoted ()(...)) Notice that, we first modeled the moments of S: using the moments of D. then approximated the CDF (equivalently, the quantile function) of the distribution of S, from its moments-in this special case, the approximation with the first two moments is, in fact, exact.

---

Our general solution follows that same logic. In the first step, we can obtain the first moments of the distribution of S, denoted ms();) for j E [r]. from the moments of D, denoted my(D). In subsequent step, we use my (Si) is to approximate the CDF of S,.
It is easy to see that the j-th moment of S can be written follows:
(S = q 0) (D( n
85
Σ
M
where 8/ is the j-fold tensor product, and @ tensor inner product.
In a second step, we find a distribution S. such that my (S:) = my((:)) for all j E [r]. This can be done using the "method of moments" Pearson [1936] which offers guarantees [Kong and Valiant 2017 Braverman et al. 2022) in terms of a distributional distance such as the Wasserstein-1 distance.
While using higher-order moments leads to a better approximation, computing m,(.) (.) for j >> 2 can be prohibitive considering the dimensionality of real datasets, as the space requirement to store my (D) grows as di, We leave an exploration of an efficient version of this two-step approach as future work.
2.3 Practical solution via concentration inequalities and sketching
Noting that Problem | is captured by the concept of concentration of measure, we resort to results from that literature to find acceptable estimates of 0,'s. In particular, obtain solution via application of the one-sided Chebyshev's 's inequality, resulting in the following lemma.
Lemma 1. Denote by μ1; and E, the mean and covariance of the distribution of Ps An upper-hound on the solution to Problem 7 for 5 E (0, 1) is:
1
0. = (q: P4)
1 1-8 q T.g.
Proof. The result follows immediately by applying the one-sided Chebyshev's inequality to the distribution, S;, of inner products between and points in P::
E. q + =
1
1 1 T
Pr [s - (g. p1) S c 2 S
= =
1 = 2-
2
Rearranging the terms to match the expression of Problem ggiess 6: (q. (4)
desired.
We emphasize that Lemma T gives a loose upper-bound on the optimal value of 0, Because we make assumptions about the data distribution, the gap between the optimal and estimated 0g cannot be expressed in closed form. Had we assumed S; is sub-Gaussian, it would be easy to bound the gap between 0; obtained from Lemma I and the one obtained from sub-Gaussian concentration bounds. Nonetheless, we find that in practice even this sub-optimal solution proves effective.
There is still one challenge with Equation 6 Σ, can be too large to store the matrix grows as d? for each partition. Contrast that with the cost of MEAN and NORMALIZEDMEAN which only need one d-dimensional vector per partition. To remedy this, design compact approximation of Σ; that can be plugged into Equation to replace Σ, We describe that next to complete our algorithm.
2.3.1 Approximating the covariance matrix
Since the procedure describe is independently applied to each partition, we drop the subscript in Σ, and focus single partition. We seek matrix E' E IR dxd that approximates the positive semi-definite (PSD) matrix Σ, by minimizing the following standard approximation error:
err( Σ, Σ²) A sup
||]||==1
As we seek compact V", we constrain the solution space to rank-f matrices: rank()")) = t, t << d.
standard solution is result of the Eckhart- Youthrr--Yuugg-Mirss Theorem: Let Σ = VAVT be the cigendecomposition of Σ. Then, E = (V where [:], selects the first columns of its argument, optimally approximates Σ under the stated constraints. We denote this solution by L
5

---

Algorithm Indexing and scoring single partition with OPTIMIST
Input:
Partition and target rank t & d.
I: procedure WOR.LRROUTERFFRPPRTTTTTO
2:
P Euep"
1 - Pi 4: Rs -E=
b D the diagonal of Σ
Find eigendeconmooition R. QAQ
6: Sort columns of Q. A in non-increasing order
7: A + [A]r, Q: + [Q]e
8:
return {/4, Ar, Q:)
Input: Query 9 E TR and optimism parameter 6 >> O. D,,,,
procedure ECCORPPARTIIONNFRQURRYYY
10: q diag( 1/3
Element-wiss product
11:
return (q. 1 (l@ll + Q.AQQN
We could stop here and use Σt in lieu of E in Equation (6. However, while that would be the optimal choice in the general case, for real-world datasets, we show that we can find a better approximation.
Definition (Masked Sketch Rank t). Rewrite E as follows, with D diagonal and R Σ D:
= + D
D
R
Let QAQT be Ro 's eigendecoomposition. We call the following the Masked Sketch of Rank t of E::
D = D Då [Q)] D
(8)
We next establish that, under certain assumptions, err(2, 225) is lower than err(2,, 2%
Lemma 2. Let Idd be a PSD matrix with diagonal D for which mingela Dis/ 5//maxqejd Di 1 for some >> O. For every 1 < 1 & d d-1 1 such that the (t + 1)-th eigenvalue of D D-1/2 1/2 greater than 1, we have that: err(E., X25 S err(E. E ) - c).
We give the proof in Appendix C and show that for datasets in this work the assumptions hold.
2.3.2 The final algorithm
Using our solution from Lemma and our sketch defined in (8). we describe our full algorithm in Algorithm for building our router and scoring partition. Notice that, since we only store μ., D, [A]e and [Q],, the router requires & + 2 vectors*] in Rd per partition. In our experiments, we choose I for all datasets except one and show that much of the performance gains from using the whole covariance matrix be preserved even by choosing small value of independent of d.
2.3.3 Time complexity analysis
The time complexity of Algorithm 1 is dominated by eigendecomposition which takes (nd d3) time. However, because we only need the top eigenvectors and values to build the router, we may use highly-efficient algorithms for computing low-rank approximations of PSD matrices such as the randomized Block Krylov Method (see [Tropp] 2018 Section 6.3] and [Musco and Musco 2015)).
The time complexity of these algorithms is proportional Ond faster than naïve eigendecomposition. Since is usually small constant in our setting, Algorithm can be implemented near linear time complexity in the size of the data.
t). making them much
Experimental evaluation
We put arguments to the test and evaluate OPTIMIST.
"Since [A]r be "absorbed" into [Q] with some taken for the signs of the eigenvalues.

---

Table 1: Dataset statistics (size m dimensions d), along with the number of partitions (C) and OPTIMIST'S default rank configuration (t) in our main experiments.
Table Relative savings during search to achieve a fixed recall. A saving of a% means that OPTIMIST searches x% fewer points than NORMALIZEDMFAN
DATASET
d
C
RECALL
90%
95%
TEXT2IMAGE
10M
200
3,000
MUSIC
1M
100
1,024
2
TEXT2IMAGE
23%
22%
DEEPÍMAGE
10M
96
3,000
MUSIC
38%
54%
GLOVE
1.2M
200
1,024
GLOVE
11%
5.5%
MSMARCO-MINILMM
8.8M
384
3,000
MSMARCC-MINILM
22%
7.7%
NQ-ADA2
2.7M
1,536
1,600
30
NQ-ADA2
18%
20%
3.1 Setup
Datasets: Table Tablee|summn [ummmarizes in the leftmost block the main properties of the datasets used in our experiments. A complete description can be found in Appendix D
Clustering: For our main results, we partition the datasets with spherical KMeans [hillon and Modha 2001]. We include in Appendices G resultss from similar experiments but where the clustering algorithm is standard KMeans and Gaussian Mixture Model (GMM). We cluster each dataset into C' = m shards, where m is the number of data points in the dataset.
The independence routing from scoring simplifies the evaluation protocol: By additivity of latency, efficiency gains from router translate directly into efficiency gains in the end-to-end search (i.e., routing followed by scoring). We can therefore fix the scoring algorithm and examine routers in isolation compare their accuracy, latency, and other characteristics.
Evaluation:
Once dataset has been partitioned, we fix the partitioning and evaluate all routers on to facilitate fair comparison. We evaluate each router as follows. For each test query. we identify the set of shards to probe using т. We then perform an exact search over the selected shards, obtain the top-k points, and compute recall with respect to the ground-trutt -tuth top-k set. Because the only source of error router's 's inaccuracy, the measured recall gauges the effectiveness of
We report recall as a function of the number of data points probed, rather than the number of shards probed. this way, comparison of the efficacy of different routers unaffected by any imbalance in shard sizes, so that a router cannot trivially outperform another by simply prioritizing larger shards.
Routers: We evaluate the following routers our experiments:
MEAN and NORMALIZEDMEAN: Defined in Equations and
SCANN (T): Similar MEAN and NORMALIZEDMEAN, but where routing is determined by
inner product between query and the SCANN centroids (c.f., Theorem 4.2 in [Guo et al. 20200) SCANN has single hyperparameter T, which set 0.5 after tuning.
SUBPARTITION (f): OPTIMIST stores + 2 vectors per partition, where is the rank in Algorithm Following the KRT method of Gottesbüren al. [2024). introduce another baseline where partition each shard into + 2 sub-shards and use the their centroids as the shard's representatives. Routing based on the maximum inner product of the query with shard's representatives.
OPTIMIST (t, 8): and 8 are parameters of Algorithm ! By default, we set d = 0.8 and t to values in Table but study their effect in Appendix E If unspecified, should be understood that default parameters are used. We write OPTIMIST (t = d, -) to indicate the use of the full covariance matrix.
Code: We have implemented all baseline and proposed routers in the Rust programming language. We have open open- sppen-soureed] code along with experimental configuratioo facilitate reproducibility.

---

0.90
0.977
Top- RECALL
Top- 100 RECALL
0..000
Top- 120 RECALLL
0.88
0.950
0.875
0.925
0.86
0.850
MESAN
MISAN
MIsAN
SCARK (.5)
SCARK (.5)
0.900
SCAAN (.5)
0.84
SunPArrmmooN
0.875
Orrmvar 66,
OPrnarr 66,
0.875
Ourmanr 66,
Oprnae (4.3)
0.800
OIrnne 8)
0.82
1.0
2.0
% POINTS PRODED
% POINTS PRODED
% POINTS PRODED
(a) GLOVE
(b) DASMARCO-MINILL.
(c) MUSIC
Figure 2: Top-100 recall vs. volume of probed points, Partitioning is by spherical KMeans. SCANN has parameter T', SUBPARTITION t, and OPTIMIST rank and degree of optimism 6.
3.2 Main results
Effectiveness:
Figure 2 plots recall versus the volume of points examined for select datasets us- ing spherical KMeans. See Appendix F for full results; Appendix G for standard KMeans; and Appendix H for GMM.
Among baselines, NORMALIZEDMEAN generally outperforms MEAN and SCANN, except on MUSIC. OPTIMIST with the full covariance (t = d) generally does least as well NORMALIZEDMEAN, but often outperforms it significantly. Interestingly, the gains from OPTIMIST widen as A increases. Finally, while OPTIMIST with a rank-t Masked Sketch shows some degradation, it still yields a higher recall than baselines for larger k. SUBPARTITION (t) becomes strong competitor when k is small.
OPTIMIST shines when data points have varying norms. On MUSIC, at 95% top-100 recall, OPTIMIST needs to probe 54% fewer points than NORMALIZEDMEAN; on average OPTIMIST probes 6,666 points reach 95% t0p-100 recall whereas NORMALIZEDM examines 14,463 points.
Table 2 presents savings on all datasets. On DEEPIMAGE, OPTIMIST scans 9% more points than NORMALIZEDMEAN to reach 90% recall (55,000 vs 60,000), and 10% more to reach 95% (95,000 vs 105,000). We suspect this is an artifact of the dataset's construction: each point is represented by the top 96 principal components of its original features, leading to unusual partition statistics.
Latency: We now turn to latency which includes routing, fetching the chosen shards from storage, and scoring using PQ with 4-dimensional codebooks. Figure reports latencies for OPTIMIST and NORMALIZEDMEAN
OPTIMIST's gains are more pronounced when shards are stored on blob storage, but even on SSD the gains are substantial. Full results are in Appendix [
We experiments on AWS c5 c5.xlarge (4 vCPUs, 8GB memory). Baseline bandwidth of the SSD attached to this machine is 1,150Mbps 6 Finally, using 4 threads, transferring 4MB of data from blob storage (hosted on Amazon S3) to main memory has P50 latency of 45 milliseconds (ms)
Let us next present in Table Ba a unified view of Figure 3. which reports a breakdown of latency at 95% recall, and Table 2, which shows the relative savings (in terms of the number of data points probed) between OPTIMIST and NORMALIZEDMEANN It is clear that, with a few exceptions, the overall lateney savings are roughly equal to the reduction in the number of points probed. As such, change in the number of points probed is a reasonable proxy to change in overall latency.
Hardware plays an outsize role in latency improvements. For example, more limited storage bandwidth would boost OPTIMIST's standing. If bandwidth is abundant and number of threads limited, however, OPTIMIST's advantage would become less significant. Other factors that affect latency comparisons include: target recall level; type compression; and algorithm used for scoring.
Router size: On most datasets, the router size difference between NORMALIZEDMEAN (1 vector) and OPTIMIST (t vectors) is negligible. On GLOVE, for example, it is 0.8MB versus 7MB 4)
See https:///ocs... aws amazon http://wwwaaaaaac/////cc//a//a/a http:////wetteeeeeeeestptpiaaaaa html
"ee http://ghhu..oo////aaaaaal////s/
for independent benchmark.

---

Table 3: Difference between OPTIMIST and NORMALIZEDMEAN in terms of number of points probed and latency. Negative percentages means OPTIMIST leads to gains.
DATASET
# POINTS PROBED
LATENCY (BLOB)
LATENCY (SSD)
TEXT2IMAGE
-22%
-24.8%
-23%
MUSIC
-54%
-55%
-46.5%
DEEPIMAGE
+ +10%
+11
+15.6%
GLOVE
-5.5%
-6%
-6%
MSMARCO-MINILL
-7.7%
-7.6%
-5.8%
NQ-ADAZ
-20%
19.1% %
-11%
ROUTING
SeORING
RoUTING
Ferch
SCORING
DIRE
TRA Drar
--1.13%
TEXT TEXT TEMAGE BLOVE MUSIC
5.5%
GLo GLoVe V6
5315
MUsic
sefC
20
100
200
MoMA MoMARcO
MrMaRcO
No. NQ-Anag Anag
11.0
Nq- Ana2
19.14
50
100
500
1000
(a) SSD
(b) Blob Storage
Figure 3: Mean latency (ms) to reach 95% recall when PQ-compressed shards are on SSD and blob storage. For each dataset, plot the latency breakdown for NORMALIZEDMEAN (top bar) and OPTIMIST (bottom), and report relative gains (negative value indicates gain by OPTIMIST).
in total. Statistics on other datasets are follows: MsMARCO-MINILM 4.4MB vs. 44MB (f = 8);
MUSIC, 0.4MB vs. 1.6MB (f 2); TEXT2IMAGE, 2.3MB vs. 13. 7MB (t 4); DEEPIMAGE,
1.1MB vs. 4.4MB (t = 2). The difference is larger on NQ-ADA2: 9. 9.4MB vs 300MB (t = 30).
3.3
Maximum inner product prediction
Mexx
PREdiCtion ERAOR
0.8
PREDIET PREDICTION eTION ERSOR
0.8
PREDIE CTEDICTIOON ERSOR
0.8
0.4
0.4
0.4
0.0
10"
10
10r
10
10
10a
10r
10
10"
10
10
%
SHARDS
%
SHARDS
%
SHARDS
(a) GLOVE
(b) DEEPIMAGE
(c) TEXT2IMAGE
Figure 4: Mean prediction error Ex(T, -) of Equation
versus & (percent shards).
We claimed that OPTIMIST is statistically principled. should thus give more accurate estimates of the maximum inner product for all query-partition pairs. We examine that claim in this section.
Fix dataset with partitions Pt. router т, and query q. Write r; for the score computed by for P, and g. 7 's induce ordering т among P, ss that Txx Tw--1- We quantify the inner product

---

prediction enror as follows, for l' E [C]:
Ee(T, = 1 Σ
T
max (g. u)
This enror is 0 when 7;'s perfectly match the maximum inner product of 9 and Pt's. l allows to factor in the rank of partitions: we can measure the error only for the top shards according to r. In this way, if we decide that it is not imperative for router to accurately predict the maximum inner product in low-ranking shards, we can reflect that choice in our calculation.
We measure Equation (9) on all datasets partitioned by spherical KMeans, and all routers considered in this work. Figure reeporss of L, we plot (T, q)] for all queries. For most routers error grows as l + C. OPTIMIST( d,-) degrades less severely. Remarkably, MUSIC excepted, when < d, the same pattern persists.
reports the results for select datasets see Appendix Oopendix[--aa - for each choice
Concluding remarks
We studied clustering-basee based maximum inner product search where points clustered into shards during indexing. Search involves two independent subroutines: a rouler computes score for each shard with respect the query and returns the top shards probe; then a scorer computes (approximate) scores for points in those é shards. We considered a storage-backed system where shards do not rest in memory, but are stored external storage and must be fetched into memory when a router identifies them. This is an important paradigm for nearest neighbor search at scale.
Within this framework, focused routing. We motivated behavior: NORMALIZEDMEAN computes a score that over-estimates the maximum inner product between query and points in shard. Interestingly, the extent of over-estimation correlates with the variance of the shard: The more spread-out the points are, the more optimistic the router becomes.
work by unusual routing
We took the insight that variance should play role in routing and developed principled optimistic algorithm, called OPTIMIST, whose score for a shard more accurate estimate of the maximum inner product as confirmed in Figure resulting in smaller f's to achieve fixed recall. As Figure shows OPTIMIST is particularly attractive when shards rest on some external, high-lateng, storage.
OPTIMIST has implications beyond latency. Transferring a smaller volume of data to memory means that each query needs a smaller in-memory cache. As result, cache can be shared among more queries, leading to higher throughput in systems where memory availability is the main bottleneck.
Our research takes first step in exploring unsupervised routing for clustering-basee based MIPS, and identifies trade-off space that has not been explored before. We have more to do, however. We leave future work exploration of more compact sketch of the covariance; and, efficient realization of our general solution outlined in Section 2.2
10

---

Acknowledgements. This work was partially supported by the Horizon Europe RIA "EFRA Extreme Food Risk Analytics" (grant agreement n. 101093026) and the PNRR M4C2 Investimento 1.3, Partenariato Esteso PF00000003- "FAIR Future Artificial Intelligence Research" Spoke 1 "HHuman-centreed AT Horizon Europe and the PNRR programs are funded by the European Commission under the NexiGeneration EU program. The views and opinions expressed are solely those of the authors and do not necessarily reflect those the European Union, nor can the European Union be held responsible for them.
References
Nir Ailon and Bernard Chazelle. The fast johnson--indeestrauss transform and approximate nearest neighbors. SIAM Journal on computing, 39(1):302-322, 2009.
Nir Ailon and Edo Liberty. An almost optimal unrestricted fast johnson-lindenstraue transform.
ACM Transactions on Algorithms (TALG), 9(3):1-12, 2013.
Fabien Andre, Anne-Marie Kermarrec, and Nicolas Le Scouarnec. Quicker adc: Unlocking the hidden potential of product quantization with simd. IEEE Transactions on Pattern Analysis and Machine Intelligence, 4365):1666-1677) 5 2021.
Alex Auvolat, Sarath Chandar, Pascal Vincent, Hugo Larochelle, and Yoshua Bengio. Clustering is efficient for approximate maximum inner product search, 2015.
Artem Babenko and Victor Lempitsky. The inverted multi-index. In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pages 3069-3076 2012.
Jon Louis Bentley. Multidimenssonaal binary search trees used for associative searching. Communica- tions of the ACM, 18(9):509-517, 9 1975.
Vladimir Braverman, Aditya Krishnan, and Christopher Musco. Sublinear time spectral density estimation. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1144-1157, 2022.
Sebastian Bruch. Foundations of Vector Retrieval. Springer Nature Switzerland, 2024.
Sebastian Bruch, Franco Maria Nardini, Amir Ingher, and Edo Liberty. Bridging dense and sparse maximum inner product search. ACM Transactions Information Systems, 42(6):1-38, August 2024.
Flavio Chierichetti, Alessandro Panconesi, Prabhakar Raghavan, Mauro Sozio, Alessandro Tiberi, and Eli Upfal. Finding near neighbors through cluster pruning. In Proceedings of the 26th ACM STGMOD-SIGACT-SICARR Symposium on Principles of Database Systems, pages 103-112, 2007.
Chih-Yt Yi Chiu, Amorntip Prayoonwong, and Yin-Chih Liao. Learning index for nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1249111942-1 2020.
Sanjoy Dasgupta and Kaushik Sinha. Randomized partition trees for nearest neighbor search. Algorithmica. 72(1):237-263, 2015.
Inderjit S. Dhillon and Dharmendra Modha. Concept decompositions for large sparse text data using clustering. Machine Leurning, 42(1):143-175, January 2001.
Yihe Dong, Piotr Indyk, Ilya Razenshteyn, and Tal Wagner. Learning space partitions for nearest neighbor search. In International Conference on Learning Representations, 2020.
Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre-Emmanue Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. The faiss library, 2024.
Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. Optimized product.quantization. on Pattern Analysis and Machine Intelligence, 36(4):744-755, 2014.
quantization. IEEE Transactions
Lars Gotteshüren, Laxman Dhulipala, Rajesh Jayaram, and Jakub Lacki, Unleashing graph partition- ing for large-scale nearest neighbor search, 2024.

---

Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. Accelerating large-scale inference with anisotropic vector quantization. In Proceedings of the 37th International Conference Machine Learning, 2020.
Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: Towards removing the curse of dimensionality. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing. pages 604-613, 1998.
Shikhar Jaiswal, Ravishankar Krishnaswamy, Ankit Garg, Harsha Vardhan Simhadri, and Sheshansh Agrawal. Ood-diskann: Efficient and scalable graph anns for out-of-distribution queries, 2022.
Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. Diskann: Fast accurate billion-point nearest neighbor search single node. In Advances in Neural Information Processing Systems, volume 32, 2019.
Herve Jégou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE Transactions Puttern Analysis and Machine Intelligence, 33(1):117-228, 2011.
Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with gpus. IEEE Transactions Big Data, 7(3):535-547, 2021.
Yannis Kalantidis and Yannis Avrithis. Locally optimized product quantization for approximate nearest neighbor search. In 2014 IEEE Conference on Computer Vision and Pattern Recognition, pages 2329-23336 2014.
Weihao Kong and Gregory Valiant. Spectrum estimation from samples. The Annals of Statistics, 45 (5):2218 2247, 2017.
Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, Kristina Toutanova, Llion Jones, Matthew Kelcey, Ming- Wei Chang, Andrew M. Dai, Jakob Uszkoreit, Quoc Le, and Slav Petrov. Natural questions: A benchmark for question answering research. Transactions of the Association for Computational Linguistics, 7:452-466, 2019.
Tor Lattimore and Csaba Szepesvári. Bandil algorithms. Cambridge University Press, 2020.
Yu A. Malkov and Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Puttern Analysis and Machine Intelligence, 42(4):824-836, 4 2020.
Stanislav Morozov and Artem Babenko. Non-metric similarity graphs for maximum inner product search. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
Cameron Musco and Christopher Musco. Randomized block krylov methods for stronger and faster approximate singular value decomposition. Advances neural information processing systems, 28, 2015.
Tri Nguyen, Mir Rosenberg, Xia Song, Jianfeng Gao, Saurabh Tiwary, Rangan Majumder, and Li Deng. Ms marco: A human generated machine reading comprehension dataset, November 2016.
Mohammad Norouzi and David J. Fleet. Cartesian k-means. In Proceedings of the 2013 IEEE Conference Computer Vision and Patlern Recognition, pages 3017-3024, 2013.
Karl Pearson. Method of moments and method of maximum likelihood. Biometrika, 28(1/2):34-59, 1936.
Jeffrey Pennington, Richard Socher, and Christopher Manning. GloVe: Global vectors for word representation. Proceedings of the 2014 Conference on Empirical Methods Natural Language Processing, pages 1532-1543, Doha, Qatar, October 2014.
12

---

Harsha Vardhan Simhadri, George Williams, Martin Aumüller, Matthijs Douze, Artem Babenko, Dmitry Baranchuk, Qi Chen, Lucas Hosseimi, Ravishankar Krishnaswamny, Gopal Srinivasa, Suhas Jayaram Subramanya, and Jingdong Wang. Results of the neurips" 21 challenge on billion- scale approximate nearest neighbor search. Proceedings of the NeurIPS 2021 Competitions and Demonstrations Track, volume 176 of Proceedings of Machine Learning Research, pages 177-189, Dec 2022.
Aditi Singh, Suhas Jayaram Subramanya, Ravishankar Krishnaswamy, and Harsha Vardhan Simhadri. Freshdiskann: A fast and accurate graph-based ann index for streaming similarity search, 2021.
Yao Tian, Tingyun Yan, Xi Zhao, Kai Huang, and Xiaofang Zhou. A learned index for exact similarity search in metric spaces. IEEE Transactions on Knowledge and Data Engineering, 35(8): 7624-7638, 2023.
Joel Tropp. Analysis of randomized block krylov methods. ACM Report, 2, 2018.
Thomas Vecchiato, Claudio Lucchese, Franco Maria Nardini, and Sebastian Bruch. learning-to- rank formulation of clustering- based approximate nearest neighbor search. In Proceedings the 47th International ACM SIGIR Conference on Research and Development Information Retrieval, 2024.
David P. Woodruff. Sketching tool for numerical linear algebra. Foundations and Trends in Theoretical Computer Science, 10(1-2):1-157, Oct 2014. ISSN 1551-305X.
Xiang Wu, Ruiqi Guo, Ananda Theertha Suresh, Sanjiv Kumar, Daniel N Holtmann-Rice David Simcha. and Felix Yu. Multiscale quantization for fast similarity search. In Advances in Neural Information Processing Systems, volume 30, 2017.
Artem Babenko Yandex and Victor Lempitsky. Efficient indexing of billion-scale datasets of deep descriptors. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, pages 2055-2063, 2016.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We are explicit in our abstract and introduction about the prior research that motivated this work and describe precisely what our novel contributions are.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings. It is fine include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We noted our discussion the limitations of our work. First, we emphasized the sub-optimality of the solution obtained from Lemma | but justified its efficacy through that our router, in isolation, is computation-
empirical experiments. Second, we pointed ally more expensive and requires a larger amount of storage, but explained and demonstrated why this increase in costs can be appropriate depending on the end-to-en setup. Finally, our method performs better when data is stored in a high-latency storage medium, rather than in-memory; we have made a note that our discusison.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
14

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We state all assumptions and complete proofs for all claims made in this work. For some results, we move the proof to the appendix due to space constraints.
Guidelines:
The answer NA means that the paper does not include theoretical results, All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We have included all the details of our experiments (including all hyperparam- eters) as well as complete description of datasets to facilitate reproducibility. Furthermore, when the work is ready for publication, we plan release our code and configuration files to open-source.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to hosted model (e.g., in the of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
15

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We have created double-blind review-compliant Git repository host all the required code to reproduce every experiment reported in this work (including have also included links processed supplementary figures). In the repository, datasets. These links point to data that is stored in a Google Storage Bucket, and made available in such way that neither reveals the identity of the authors, nor does it reguire viewers to log into Google services. The repository can be found at https //github.com com
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
Sublic/guides httpg//de/e/oeeeumiieeeeeeeeeeee (CodeeSummssiioooollllae
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ cttppsscccppulccc/ecccccc wtt.uuddeeeeeeeuuusassssooeeelee
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We give all details including hyperparameters. As for train-test splits, the benchmark datasets used in our work come with a test query set that is separate from the data points.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
16

---

Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: While we do not explicitly mention the results of statistical significance tests to avoid clutter, we note here that wherever OPTIMIST performs better than the baselines, the differences are statistically significant with p-value that is often less than 0.001.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Most of our experiments are compute-heay and are run on a commercial laptop with standard configuration. For experiments that study the latency of different methods, we state the specifications of the hardware used.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http::///horrrpp.ccpppaaah/hhhce
Answer: [Yes]
Justification: We acknowledge that we have reviewed the NeurIPS code of ethics and that our research conforms, in every respect, with the code.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
17

---

If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work does not have any societal impact that we could identify.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymentt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work does not involve the development of models or the release of new data.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
18

---

Answer: [Yes]
Justification: We have included this information in our full description of datasets used in our experiments.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwwppsppppeaaaaeeeee thcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Our research does not result in new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
Justification:
Our research does not involve crowdsourcing human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
19

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our research does not involve human subjects and as such does not require IRB review.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: We do not use LLMs in any shape or form (including for writing, editing, or formatting) in our work.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non sta-dtandard components.
Please refer to our LLM policy (https :ootps:/nnnt ///purip// cc/Conferreces//2000 /LLM) for what should or should not be described.
20

---

A An illustrative example
Interestingly. depending on operational factors such as data transfer rates and memory utilization, would be acceptable for routing to be computationally more expensive as long as it identifies shards more accurately. Let us consider an example to support this statement and motivate our research.
Take Natural Questions Kwiatkowski et al. 2019] embedded with ADA-002 denoted NQ-ADA2, containing 2.7 million ..536ddimeniional points. Applying KMMaan and compressing with the typical 4-bit PQ codebooks give shards with about 1,650 points each and 1MB in size. Consider next commercial machine: AWS c5 .llarge (4 vCPUs, 8GB of memory). Using 4 threads, moving 4MB of data from storage (hosted on Amazon's 's S3) to memory has a mean latency of 45 milliseconds (ms)
Given this setup, moving 16 NQ-ADA2 shards from blob storage the machine's memory takes 180ms (P50 latency). On this same machine, routing using Equation (2) takes 06ms. As such, so long more complex router can achieve the same accuracy Equation (2) by fetching 16 fewer shards, but by introducing a latency of no greater than 1 179ms, the overall efficinccy of ANN search improves. As we show later, our router on the same dataset with the same configuration takes only about 10.1ms to identify shards, leading to a saving of 170.6ms per query in the given example.
As this example illustrates, storage-backed, clustering-basee ANN search offers trade-off between not just accuracy and speed, but also other efficiency factors such as I/O bandwidth, and memory and cache utilization. This opens the door more nuanced research. Our work is step in that direction.
B Related work
As we argued in Section T. routing accuracy in clustering-basee approximate nearest neighbor search is increasingly relevant. Surprisingly, it has received little attention in the literature and most practical implementations of routing do not go beyond the naïve form of Equation (2). In this section, we briefly review the relevant methods that explore this particular topic.
The literature on routing functions can be split into two categories: supervised and unsupervised methods. In the supervised regime, routing function is learned using training query distribution. This is best demonstrated by the work of Vecchiato et al. (2024). which formulates the problem of routing as learning- to-kkkkk task: Given query the function learns to rank shards, and subsequently uses the learned routing function during search for a test distribution.
That work is similar in spirit to the supervised methods put forth by Chiu et al. 2000 Dong et al. 2020), and Tian al. [2023). The difference is that, this set of methods attempt to learn to partition the data and form representatives based on the learned functions.
Supervised methods have caveat: While the methods differ in their approach to the problem, they require a training distribution. Our method, on the other hand, is completely unsupervised and does not have this limitation. Because of this fundamental difference, or theoretical comparison between supervised methods and our method is warranted. In fact, in many instances, the benchmark datasets do not come with training distribution or have very limited number of training queries.
do not believe an empirical
There are, however, other unsupervised methods in the literature that we have included in our experiments as baselines per Section[.IIam that we review next in more detail. The first two are the MEAN and NORMALIZEDMEAN routers. which are the de facto routing functions in all open-source approximate nearest neighbor search software. These follow the simple form of Equations (2) and (3).
While SCANN is proposed as quantization method for maximum inner product search [Guo et al., 2020), implicitly introduces a novel (supervised and unsupervised) routing function we focus on the unsupervised function. SCANN is based on the idea that, points in shard should not count equally towards the quantization error. That is unlike Product Quantization Jégou et al. [2011]. Instead, every point is weighted based on how likely it is to maximize inner product with arbitrary query.
'See httt::///gtthub.cc///vvvssaaaal hanp:///..../caaaaaaaooooaaaaaaa benchmark for an independent and comprehensive bench-
mark.
21

---

What is relevant to this work is that the SCANN quantization method produces shard representative that is a single vector, but that is not the centroid or normalized centroid (c.f., Theorem 4.2 [Guo et al. 2020 We use this representative to route queries to shards.
Another relevant work is the routing functions proposed by Gottesbüren et al. two routing protocols: KRT and HRT. The latter has strong theoretical guarantees, but both methods perform equally well, with KRT having slight advantage. As such, our review focuses on KRT.
2024
They introduce
KRT, which we call SUBPARTITION in Section 3 for clarity, is based on the idea of partitioning each shard into multiple sub-shards and extracting representative from each sub-shard. This is particularly useful for shards that are far larger than a conventional configuration clustering based ANN search would produce. At query time, shards are ranked by statistic based on the inner products between the query and the shard representatives. our instantiation of this routing function, that statistic to be the mean of the sub-shards.
C Proof of Lemma 2 and justification of its assumptions
Let Σ D R be the decomposition of the PSD covariance matrix E into its diagonal D and residual R = Σ D. Let QAQ' be the orthogonal eigendecomposition of R. DD1122DD-30 Recall that we define 2,, for some S ( S d, as
MMS
D D [Q]AA]][Q); D
We start by proving Lemma then justify the assumptions of the lemma.
C.1 Proof of Lemma 2
We state few technical results that will simplify the proof of the lemma.
Fact 1. For any symmetric matrix M E gaxd with eigendecomposition US we have that for any Rd.
M = Σ S, (v. U.) ==1
Fact 2. Assuming the eigenvalues A of Ro are sorted non-increasing order, we have that I R. Q(I + T In words, the eigenvectors of I + Ro are the same as Ro, and the i-th eigenvalue is A4 As corollary, since + R. PSD, have that A; -1 for all [d].
Proof. This follows easily after noticing that T= QQ because Q is a d x d matrix with orthonormal columns (and rows).
Fact 3. For diagonal matrix S dxd with bounded positive entries, i.e. 0 O<ls Su S u for all i [d], and arbitrary vector E Rd,, we have that 1||v|l2 S ||Sr|l2 I w//1/12.
Proof of Lemma
First, note that, by the definition of emr(. from Equation 77.
write:
1v D 1/2 - EEM* 1/2
err( AED D- A D- = sup
||
vERd
Since D has strictly positive entries the diagonal, D2/2p. Denoting maxield Di, by ||D], this gives us:
do change of variables, setting
( Σ yul
sup ar(D-tED D s Dー
|| 11/22/1
veRd TT(S
Σ )vl
err E,, ΣMS)
sup vRRd
D
00
|e||
D
where the inequality follows by Fact
22

---

Next, consider the following:
err(
ED D $ INS D- +) = sup
10 DTD (Σ D= 1
||
sup |=||==1
10 T (Ro - [Q]+[A] )ol
(10)
d Σ
sup
A, (Q,
(11)
|vl|==1
/=++
max 1E(+1.d
|Ax]
(12)
where the second equality follows by the definition of M and the third by Fact] |
Putting arguments thus far together, have established that:
(E,E,,
max |A//-
(13)
| 50
[E[++1.d]
Using this result, and noting that, 1 A4+1 by assumption, that A441 0; and A -1 for all I E [d] by F we can derive the following:
err(E. E, IMS)
I max
|Ai| 1 A++1 & max
11 + Arl
(14)
D
1E[(+1,4]
le|++1.d]
eer((
I+ Rg
(15)
D-1/2DD-122
All that is left to do bound the right-hand side of Equation 15
We do so as follows:
err(D-1/2ED 1/2 [Q][ +1000==0111100 )
(16)
D0,.D-1/220 <e D 1-112)
(17)
sup
D-12/// - ) 11/2g
(18)
||+||==1
sup
Σ 1, (E - E/"),// D
(19)
||
sup
Urtly
Σ(R) 113 (1 c) D
(20)
||||===
1
sup
1T Σ1 yu|
(21)
D
|v||==1
er )
(22)
(1 [1=
where the first inequality is because the left-hand side the optimal error by the Eckhart- Eckhart-Young. Mirsky Theorem, and the second incquality is due to the fact that Dü 2 (1 DIl Putting everything together, we have shown that:
err(E, 2M5)
S
err(E, Ef) Σ(R),
||
(1 - D|]
as desired.
C.2 Assumptions of Lemma] 2
Recall that make two assumptions about the covariance matrix E and the cigendecomposition of its symmetrization, D-1/2gD-112
23

---

600
150
NOMPER OF SHARDD
NUMBER OF SHARDS
NUMBER OF SHARDS
800
400
100
600
400
200
200
0g
4
6
2
5
10
(a) DEEPIMAGE
(b) GLOVE
(c) SEAMARCO-MINLLA
NEMBER OF SBARDS
125
NUMBER OF SHARDS
800
NEMBER OF SHARDS
400
100
600
300
75
400
200
50
200
100
0
2.5
10.0
0-
0
2.5
5.0
10.0
Ax(1) 11522-
Aa( 1/95: 1/9)
Ag(O)
(d) MUSIC
(c) NQ-ADA2
(f) TEXT2IMAGE
Figure 5: Histogram of the (t + 1)-th eigenvalue. For each dataset, we pick the partitioning and I from Table Plots show that almost all shards for datasets have (t + 1)-th eigenvalue bounded away from I, except for few shards for NQ-ADA2.
1. The (t 1)-th eigenvalue of D D-1/2ED-112 is greater than equal 1. In particular, letting D D-1/2ED- 1/2 Q A)Q T be the orthogonal eigendecomposition of the sym- metrization, we assume 1 + A4+1 2 1.
2. The diagonal of Σ has the property that minte(d En 2 (1 cc) maxie[d] En for some 6 E (0.1).
First assumption. Notice that D-1/2 = = is symmetric PSD, so have that tr( D D-1//-DD111))
Σí 1+ d. Hence by definition there must exist some for which 1 + A4+1 2 1. While in the worse case we cannot hope for the existence of an eigenvalue larger than this, practice, including for the datasets we consider in this work, can be shown that in fact the eigenvalues of D D-1/25 1/2 are larger than across shards and datasets-see Figure 5
Second assumption. While in the worst case, the diagonal of Σ can have arbitrarily large entries compared to its smallest entries, in practice this is rarely the case. While we do not explore how to remove this assumption, there are several mechanisms to do so in practice such applying random rotations or pseudo-random rotations Ailon and Chazelle 20099 Woodruff (014). Ailon and Liberty [2033] to the data points in each shard before using Algorithm is well known (e.g. Lemma I in Ailon and Chazelle (2009) that after applying such transforms, the coordinates of the vectors "roughly equal," thereby ensuring that the diagonal of the covariance has entries of comparable magnitude. We leave the exploration of removing this assumption to future work.
D Datasets
The following is complete description of the datasets used in this work:
24

---

TEXT2IMAGE: A cross-modal dataset, where data and query points may have different dis- tributions in a shared space (Simhadri et al. 2022]. We use subset consisting of 10 million 200-dimensional data points along with a subset of 10,000 test queries. 'hee dataset is available under the terms the Creative Commons Attribution 4.0 International license.
MUSIC: million 100-dimensional points [Morozov and Babenko, 2018 with 1,000 queries. To the best of our knowledge, the dataset comes with no information on the license under which is made available (per
nsw "tab=readmm--o-iiie))
Subset of 10 million 96-dimensional points from the billion deep image features dataset Yandex and Lempitsky. 2016) with 10,000 queries. The dataset is available under the
DEEPIMAGE:
terms of Apache license 2.0.
GLOVE: 1.2 million, 200-dimensional word embeddings trained on tweets [Pennington et al. 2014] with 10,000 test queries. The dataset is available under the terms of the Public Domain Dedication and license v1.0.
MSMARCO-MINILNN MS MARCO Passage Retrieval vl [guyyen et al. 2016 is a question- answering dataset consisting of 8.8 million short passages English. We use the "dev" set of queries for retrieval, made up of 6,980 questions. We embed individual passages and queries using the MLLL-MINILM-LL v2 mode [o to form 384-dimensional vector collection. The dataset available under the terms of the Creative Commons Attribution 4.0 International license. The model used to embed the dataset is available under the terms Apache license 2.0.
NQ-ADA2: 2.7 million, 1.536-dimensional embeddings of the Natural Questions
dataset Kwwatkowski et al. 2019 with the ADA-002 model |1 The dataset is available under the terms Apache license 2.0.
We note that the last four datasets are intended for cosine similarity search. As such we normalize these collections prior to indexing, reducing the task to MIPS of Equation (Tp.
E Effect of hyper-parameters on OPTIMIST
Recall that OPTIMIST takes two parameters: the rank of the covariance sketch, and ó, the degree of optimism. We examine the effect of these parameters on the performance of OPTIMIST.
Figure O visualizes the role played by t. It comes as surprise that larger values of lead to better approximation of the covariance matrix. What we found interesting, however, the remarkable effectiveness of sketch that simply retains the diagonal of the covariance, denoted by OPTIMIST(O,)) -), the settings we experimented with (i.e., & E 10, 100)).
In the same figure, we have also included two configurations of SUBPARTITION: one with 2 sub- partitions, SUBPARTITION()) and another with largest t. These help put the performance of OPTIMIST with various ranks in perspective. In particular, we give the SUBPARTITION baseline the same amount of information and contrast its recall with OPTIMIST.
sub-partitions, SUBPARTITION(), for the
We turn to Figure understand the impact of 8. It is clear that encouraging OPTIMIST to be too optimistic can lead to sub-optimal performance. That is because of our reliance on the Chebyshev's 's inequality, which can prove too loose, leading overestimation of the maximum value. Interestingly, E (0.6, 0.8) appears to yield better recall across datasets.
at ottpr//mmmttttt/////////e/////er httpp////woaaaaccc.///////////aa
25

---

0.50
0.92
0.00
Top-10 10p-100 ROCALL
Top-100 ReGAL.
0.88
00.85
0.00
Top-
18.80
Oriite 4]
0.80
Orauur (k,d)
T--Oreerr Jt
Orsuue (4
Orrnarr (16.3)
0.58
Ormoar 3..5
0.84
Orisue X.5
1.81
SeaPammaa 10
Baaaaamm 191
Staaaamao (5)
% POINTS PROBED
POINTS PROBED
% POINTS PROBED
(a) NQ-ADA2
(b) GLOVE
(c) MSMARCO MMMMCO
10.88
0.98
Top- 100 ReCALL
Tan (0 RECALE
0.96
0.07
0.07
0.94
TOP
0.90
Orraatir 66.5
cobir (x.2)
Orisoo 3..5
Urssoo 24
Germanes 18
Ortsur 2.35
Girnanes 14
Ortsuse 3.35
0.95
0.92
1.5
2.0
1.5
2.0
POINTS PROBED
POINTS PROBED
% POINTS PROBRD
(d) DEEPIMAGE
(c) MUSIC
(f) TEXT2IMAGE
Figure 6: Top-100 recall volume of probed data change the rank parameter (t).
OPTIMIST(O,. is a sketch that is the diagonals only. Partitioning is with Spherical KMeans.
0.92
Top RECALL
Top-10 100 RECALL
Top- 100 RECALL.
0.91
0.88
OFtiue 24.51
0.80
.T Orrnnen (4 Cornect
-Th Oemmonm (6.3)
Cemmoer
0.80
OonTEeT 34.4 41.
Cemmoer
24.21
Orianaa (4.4)
Oemaaon (2.5)
Orimsn 24.3
0.81
Ormaaan 62.0
POINTS PROBED
POINTS PROBED
% POINTS PROBED
(a) NQ-ADA2
(b) GLOVE
(c) MSMARCO -MMMLC
0.98
0.985
Top-100 RECALL
Tap- (0) RECALL
0.96
8.96
0.960
0.91
Top
0.94
0.975
Oranse 24.41
+ Oriasas (4.
Oenaanr 66.0
Oranor 24.40
-Drussas (2.
Ornasnn 60.5)
0.90
Ortunt 24.41
Ortnnan
Ortmnen (2.3)
62.31
0.92
Cemaaner (6.00
Oemsoet 6d.b)
0.070
2.0
1.0
1.5
2.0
1.5
2.0
PROBED
PROBED
%
PROBED
(d) DEEPIMAGE
(e) MUSIC
(1) TEXT2IMAGE
Figure 7: Top-100 recall volume of probed data, comparing range of values of 6. As + OPTIMIST becomes more optimistic. Partitioning is with Spherical KMeans.
26

---

Experiments with spherical KMeans
0.95
Too-1 AEEAAL
Top-10 RECALL
0.90
Top- 100 RECALL
0.90
0.85
------
0.85
Scaan
OUTIaSS (d,
OPTINIT
0.5
0.5
1.0
1.5
1.
1.5
2.0
% POINTS PRORED
% POINTS PROBED
POINTS PROBED
(a) NQ-ADA2
0.98
0.98
0.975
Top-1 RECATH
0.96
Top-10 RECALL
0.96
Top- 1000 ROCALL
0.950
0.91
0.94
0.925
0.92
0.92
0.900
+ SCARK
STORPARTITOO
0.90
0.875
Chrmane (4.3)
OPTIEST (2.8)
0.5
1.0
2.0
0.5
1.0
1.5
2.0
0.5
1.0
1.5
2.0
%.
POINTS PRODED
%
POINTS PRODED
%
POINTS PROBED
(b) MUSIC
0.94
0.94
RECALL
ToP-10 RECALL
0.02
Top-100 100 RECALL
0.88
0.92
0.00
0.86
MPAK
0.90
0.88
ScuPARmITON
8]
0.88
OPTINST
0.82
%
PRORED
POINTS PROBED
PROBED
(c) GLOVE
Figure 8: Top-k recall vs. volume of probed data. Partitioning is with Spherical KMeans. SCANN has parameter T, SUBPARTITION / (leading to + sub-partitions per shard), and OPTIMIST rank and degree of optimism 8.
27

---

0.90
0.95
0.95
'To-11 IECCALL
Top-10 RECAALL
Top- 100 RoCALL
0..00
0.90
0.90
ATRAN
0.815
0.85
SCAAN
SURPARTIIOO
OUTIBSST (A.3)
0.80
0.80
OPTINIT
0.5
1.0
1.5
2.0
0.5
1.0
1.5
2.0
0.5
1.0
1.5
2.0
%
POINTS PRORED
% POINTS PROBED
POINTS PROBED
(d) TEXT2IMAGE
0.925
0.96
Top-1 RECALL
Top-10 RECALL
Top- 1/0 RECALL
0.900
0.92
0.94
0.875
0.90
0.850
0.92
0.88
SCANN (3)
0.825
STOPPARTIIOO
0.86
Orrmise (4,
0.90
0.500
OOFIIST (8.5
1.0
1.5
2.0
1.5
2.0
1.0
L.5
% POINTS PRODED
% POINTS PRODED
%
POINTS PROBED
(c) RISMARCO-MINILN
0.975
REeALL
Top- 10 RECALL
Top-100 RECALL
0.95
0.95
0.950
0.90
0.925
0.90
MPAA
SCAMK
0.900
0.85
ScuPARIITION
Oprister 8]
0.875
0.85
Cleminnee
0.5
1.0
1.5
2.0
0.5
1.0
1.5
2.0
0.5
1.0
1.5
2.0
% POINTS PRORED
POINTS PROBED
(f) DEEPIMAGE
Figure 8: Top-k recall vs. volume of probed data. Partitioning is with Spherical KMeans. SCANN has parameter T, SUBPARTITION / (leading to + sub-partitions per shard), and OPTIMIST rank and degree of optimism 5.
G Experiments with standard KMeans
28

---

0.95
0.00
RECALL
Top-10 RECALL
0.90
Top-100 100 RECALL
0.90
0.85
0.85
0.50
0.85
SCANK (,3:
0.80
SURPARITIION
0.75
OPTINEST (d.3)
OrrmIES (3L,
0.5
1.0
0.5
1.0
1.5
1.5
2.0
% POINTS PRODED
% POINTS PRODED
% POINTS PROBED
(a) NQ-ADA2
0.96
0.96
Ton-1 RECALL
0.94
Top-10 RECALLL
0.94
Top- 100 ReCALL
0.94
0.02
0.92
0.92
0.90
MPAK
0.90
0.90
SCAMN
0.58
STIEPARTIIION
0.88
0.85
(4.8)
0.96
Olrrseee (2
0.5
1.0
1.5
2.0
0.5
1.0
1.5
2.0
0.5
1.0
1.5
2.0
%
PRORED
% POINTS PRORED
(b) MUSIC
0.94
0.90
Top-1 RECALL
ToP-10 RECALL
0.92
Top-100 RECALL
0.92
0.88
0.00
0.90
0.86
YOREAAREEMRAA Maaa
0.88
ScArn (.))
0.88
SoMPARTTTION
Orrmase (d,
0.86
0.80
OPTISST (4.5)
% POINTS PROBED
% POINTS PROBED
% POINTS PROBED
(c) GLOVE
Figure Top-k recall vs. volume probed data. Partitioning is with Standard KMeans. SCANN has parameter T, SUBPARTITION I (leading to / + sub-partitions shard), and OPTIMIST rank and degree of optimism
29

---

0.95
Top-1 RecALL
0.95
Top-10 RECALL
0.95
Top- 100) RECALL
0.00
0.90
0.90
0.85
0.85
SCANK (.5)
SURPARITTION
0.50
OPTISIST (4.2)
0.80
0.80
0.5
1.0
1.5
2.0
2.0
2.0
% POINTS PRODED
% POINTS PRODED
% POINTS PROBED
(d) TEXT2IMAGE
0.950
0.925
0.96
RECALL
Top-10 RECALLL
0.925
Top-100 100 RECALL
0.900
0.94
0.875
0.92
0.800
MPAK
0.875
0.90
0.825
SHIPPARTTION (8)
SCAMK
0.850
0.500
0.88
OPTISES
0.5
1.0
1.5
2.0
0.5
1.0
1.5
2.0
0.5
1.0
1.5
2.0
%
PRORED
%
%
(e) MSMARCO-MINILM
1.000
RECALL
0.975
Top-11 RECALL
0.95
Top-100 RECALL
0.95
0.950
-YYoncuuumMRuu Mtaa
0.90
Scans (.5
0.900
SomPARirTION
Ormmase (d, JI
0.875
0.85
OrnssS
2.0
1.5
2.0
96 POINTS PROBED
% POINTS PROBED
% POINTS PROBED
(f) DEEPIMAGE
Figure Top-k recall vs. volume probed data. Partitioning is with Standard KMeans. SCANN has parameter T, SUBPARTITION I (leading to / + sub-partitions shard), and OPTIMIST rank and degree of optimism
30

---

H Experiments with GMM
L.00
1.000
Toz. RaDaLL
0.95
Tur-jo 10 RICAAL
0.98
Top- (00) RBCAAA
0.975
0.33
88.66
0.050
0.94
0.925
0.92
0.52
0.90
0.50
Oemmess (4,
0.815
-.0
1.5
2.0
1:3
2.1
1.0
1.5
2.0
56 POUNTS PRODIED
06 POINES PROIIE
POINTS PROBED
(a) MUSIC
0.94
0.95
0.90
Top.1 RECALL
Tor-10 RUCALL
0.52
Top- 110) RDCALL
0.88
0.91
0.90-
0.88
0.30
Sicaaa (.4)
0.88
SuRPARETIOO
0.82
0.50
56 POINTS PRONKD
% POINTS PROBEN
% POINTS PRORED
(b) GLOVE
0.95
0,95
0.95
Top-1 RECAAL
Tor-10 RUCALL
T'P- 100 RoCAA.
0.90
0.50
0.90
0.85
0.85
-
0.80
0.80
CONEEE (8.8)
0.75
0,75
56 POINTS
%% POINTS
%
(c) TEXT2IMAGE
0.950
0.35
Top- RDCALL
Tor-10 RucALA
Toor-1 1101 RtCAALL.
0..00
0.94
0.900
0.92
0.85
Mraa
0.90
0.575
Oemmner (4.
0.83
1.0
1.5
2.0
2.0
2.01
0.5
1.5
20
56
POINTS PROBED
POINTS PROBED
POINTS PROBED
(d) RIMMARO--MNILLE
Figure 10: Top-k recall vs. volume of probed data. Partitioning with Gaussian Mixture Model. SCANN has parameter T, SUBPARTITION t (leading to t + 2 sub- aub-partitions per shard), and OPTIMIST rank and degree of optimism 8. We note that, due the dimensionality of NQ-ADA2, we were unable to complete GMM clustering on this particular dataset.
31

---

1,00
0.95
Tor- RECAIL
0.33
Tor-10 RUCALL
0.95
1op-- 10P-1101 RECCALL
0.00
E-.00
0.85
0.55
0.80
Oemert (4.
1.0
1.5
1.0
1.5
2.0
1.0
1.5
200
56 POINTS PROURD
0E POINES PROIEC
76 POINTS PROIED
(c) DEEPIMAGE
Figure 10: Top-k recall vs. volume of probed data. Partitioning with Gaussian Mixture Model. SCANN has parameter T, SUBPARTITION t (leading to t + 2 sub- partitionn per shard), and OPTIMIST rank and degree of optimism 6. We note that, due the dimensionality of NQ-ADA2, we were unable to complete GMM clustering on this particular dataset.
I Latency comparison
Tershser Dirr Steey Mirre
PRYystus Toue MU GLOfEE
Terrhhue Dier Mo Caech
10
20
10
20
MIMLAN MBMAROO
MaMates
NO ATAATN
NO AZILZ
130
100
PEYcHtuM Bros Mo Mogero
Chulle
Morio
100
200
2041
200
1001
200
MAMANIN
No Anng
No AOLS
NO Aou
50
10:00
(a) thread
(b) 2 threads
(c) threads
Figure 11: Mean latency (ms) reach 95% recall, using different number of threads (columns), when PO-compressed shards are on SSD (top row) and blob storage (bottom row). For each dataset, we plot the latency breakdown NORMALIZEDMEAN (top bar) and OPTIMIST (bottom bar), and report relative gains (negative value indicates gain by OPTIMIST).
32

---

J Maximum inner product prediction
0.20
1.0
1.50
SUsPaEmTOO 201
PREDICTION ERROR
Orrnuser (3) 9)
Orenssr 16.50
PREDICTION ERROR
PREDICTIO ERROR
1.25
Ortaren
Ortousa ia
0.15
1,00
0.6
0.10
0.75
0.50
0.05
0.2
0.25
0.000
10
0.00
10
% SHARDS
% SHARDS
% SHARDS
(a) NQ-ADA2
(b) GLOVE
(c) SAMMRCC-MMNILL.
Necmuaanmbite SesPaemoo
PREDICTION ERROR
0.8
Scaae
PREDICTION ENROR
PREDICTION ERROR
0.8
Scazs
0.6
0.6
0.1
0.4
0.5
10
10P
10
10
10
10
10"
10
%
SHARDS
% SHARDS
%
SHARDS
(d) MEGE
(c) MUSIC
(f)
TEXT2IMAGE
Figure 12: Mean prediction error (T(T, )), defined in Equation versus & (expressed as percent of total number of shards), for various routers and datasets.
33


Reviews:
[{"review_id": "q7XiN0nyXy", "reviewer": "Reviewer_VzZi", "summary": "Suppose that a large dataset is stored across many shards. The goal, given a query point, is to find the k nearest neighbor (or more specifically, the data points with the top k inner product with the query point). This paper studies the problem of routing, which is the problem of how to summarize the shards and choose which shards to look for the top k data points.\n\nPrior approaches are to summarize each shard by the mean or normalized mean (unit vector) of the data points in the shard, and then search within shards whose mean has maximal inner product with the query point. This paper proposes a simple refinement, where what is stored in not just the mean of shard, but its covariance (or an approximation of it). Using a concentration inequality a la Chebyshev, it is possible to compute an estimate of how large the dot product of the query vector with the top data point in a shard is.\n\nAnother contribution that may be of independent interest was an efficient decomposition for PSD matrices as a sum of a diagonal matrix and a low rank matrix.", "questions": "See above section under weaknesses. I think it may be good to include discussion about the cover tree and related exact and ANN data structures.\n\n[Pre-rebuttal:] Currently, I will recommend a 4: Borderline Accept. I think the problem studied is quite interesting and is worth publishing for a simple solution. But there is a lot left that could be said that would be reasonable to expect this paper to include.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\nThe paper studies a fundamental problem and provides a simple heuristic to solve it. It was also written pretty clearly, with nice intuition given throughout. I think this paper raises a problem area that is worth further research, especially motivated by how data is stored and queried in practice.\n\n**Weaknesses**\n\nI think the paper has sufficient material for publication, and worthwhile in that it points out a perhaps understudied problem that arises with extremely large-scale data. But I also think it leaves a lot of fairly obvious questions unanswered, and I think it is also reasonable if the paper were to be published in a future venue with more developed results. Some immediate points that come to mind:\n\n1. Another algorithm this paper may want to compare against is the cover tree [Beygelzimer et. al. 2006], which performs exact nearest neighbor search using O(log m) query time, where m is the number of data points. It seems that the query time for this algorithm achieving approximate nearest neighbor search is on average O(C + m/C), where C is the number of shards. This is optimized to O(sqrt(m)). Of course, there may be real trade-offs between these two approaches, which might mean that the proposed approach is still viable in practice. Perhaps the authors could comment on when they think the proposed approach would have benefits? I can partially answer this question: the cover tree might not admit sharding. Also, the approaches might not be mutually exclusive (the cover tree data structure could be used within the shard, leading to an overall query complexity of O(C + log m / C), or the optimized O((log m)^{1/2})).\n\n2. I think it would be reasonable to also study the case where the algorithm has control over how the shards are generated. For example, is there a large benefit if the shards are guaranteed to have bounded diameter (and so have subgaussian concentration)? Or, is it often the case that the router is constructed independently of the sharding process?\n\n3. White it is fairly clear, it may be nice to have a brief but explicit section on the computational complexity of constructing, updating, and querying this data structure.", "was_revised": true, "final_justification": "The rebuttal was helpful in making clear the relationship to other data structures and prior work. Also, the authors stated that they will include a section that explicitly describes the complexity of the algorithm.", "rebuttal": "We appreciate your taking the time to carefully review our submission and your on-point questions! We have included below our response to the concerns you raised in your feedback, but would be happy to expand if necessary.\n\n> Another algorithm this paper may want to compare against is the cover tree [Beygelzimer et. al. 2006], which performs exact nearest neighbor search using O(log m) query time, where m is the number of data points. It seems that the query time for this algorithm achieving approximate nearest neighbor search is on average O(C + m/C), where C is the number of shards. This is optimized to O(sqrt(m)). Of course, there may be real trade-offs between these two approaches, which might mean that the proposed approach is still viable in practice. Perhaps the authors could comment on when they think the proposed approach would have benefits? I can partially answer this question: the cover tree might not admit sharding. Also, the approaches might not be mutually exclusive (the cover tree data structure could be used within the shard, leading to an overall query complexity of O(C + log m / C), or the optimized O((log m)^{1/2})).\n\nLet us unpack your question into its parts and answer them separately.\n\nCover Tree’s query time complexity: We’d like to make a very minor and rather tangential point first: The original paper by Beygelzimer, Kakade, and Langford (“Cover trees for nearest neighbor” ICML 2006) claims and proves that the query time is $\\mathcal{O}(\\log m)$. Many years later, in 2022, Elkin and Kurlin (“Counterexamples expose gaps in the proof of time complexity for cover trees introduced in 2006”) presented a counter-example, exposing a gap in the proof presented in the original work. In a follow-on work in ICML 2023 (“A New Near-linear Time Algorithm For k-Nearest Neighbor Search Using a Compressed Cover Tree”), the two authors rectified the algorithm so that it admits a time complexity of $\\mathcal{O}((k+ \\log m) \\log k)$ where $k$ is the number of nearest neighbors to find.\n\nWhy LSH, Trees, Graphs, and IVF: The ANN literature is vast (c.f., Bruch “Foundations of Vector Retrieval”). The story began with LSH and Trees. Many of these methods have been adapted to high dimensionalities and modern hardware [Ram and Sinha, “Revisiting kd-tree for nearest neighbor search” 2019; Gu et al. “Parallel Cover Trees and their Applications” 2022; Lv et al. “Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search”]. Nonetheless, they struggle to scale in practice, either due to build-time complexity or query time complexity – constants in the big-O notation become too large in practice.\n\nThat is in fact why IVF and Graphs have become the focus of intense research in the ANN search literature, and have been widely adopted in practice. There is a very recent study that offers a comparative analysis speaking to why one would use IVF over graphs and vice versa [Kuffo and Boncz “Bang for the Buck: Vector Search on Cloud CPUs”]. We should note that, there are many other publications that support our statement that IVF and graphs are popular choices at scale; we cited some of them on the first page, along with links to blogs from industry researchers.\n\nOne particular advantage of IVF is exactly what you pointed out: Each shard can use whichever ANN search method suitable to the application setup to return its top-k points! That can be Product Quantization based score computation; a graph index such as HNSW or the Vamana graph; or LSH and Trees (including Cover Trees).\n\nComparison with other classes of ANN search algorithms: Our work is concerned with a particular subroutine within the IVF framework. The aim of our study is not to compare IVF with other methods, or the merits of IVF against other classes of algorithms. Instead, we show that the routing subroutine is underexplored and offer an insight and a solution to that particular problem.\n\nOur contributions are only meaningful in the context of IVF, and are relevant to those who (for one reason or another) choose IVF as their method of performing ANN search. We are in no way opposed to conducting a comprehensive comparative analysis of IVF (w/ different routing functions) and other algorithms, but we find that to be a rather orthogonal question that either has been addressed in the past or is best addressed in a separate study.\n\nWe hope we were able to answer your questions. But if there are any points that remain unclear, we’d be delighted to address them.\n\n\n> I think it would be reasonable to also study the case where the algorithm has control over how the shards are generated. For example, is there a large benefit if the shards are guaranteed to have bounded diameter (and so have subgaussian concentration)? Or, is it often the case that the router is constructed independently of the sharding process?\n\nThat’s an excellent question and one that is worth investigating in and of itself. Indeed, many existing routers are tied to clustering, which is the subroutine that generates the shards. Mean and NormalizedMean rise from standard and spherical KMeans respectively. ScaNN has its own clustering objective that is a modification of the KMeans iterative algorithm.\n\nWe isolated routing from clustering to remove a confounding variable: By fixing the shards themselves, we can directly compare the routing protocols. Had we allowed each router to dictate how the shards are produced, we would not have been able to perform an apples-to-apples comparison of routers.\n\nNow, would it benefit Optimist if it had a say in how the shards are produced? First, each shard’s inner product distribution is subgaussian simply because it has bounded support. But that detail aside: It is likely that by modifying the clustering objective to align with Optimist’s routing logic (similar to what ScaNN does, for instance), its performance might improve or its covariance matrix might become sparser and thus more compact. We give a more detailed explanation of why we do not believe coupling Optimist to a clustering loss is a trivial problem in our response to Reviewer HqdC.\n\nWhile we find that question fascinating, we believe the scope of the paper is to establish whether optimism, formalized as we do in Problem 1, offers any advantage in and of itself. Our study gives an affirmative answer to that question. Can we improve the algorithm now that we know it has merit? Of course! We do not claim this is the end of the road, and encourage research in this space. But we strongly believe that research would be more appropriate in a separate study.\n\nWe’d be happy to elaborate further should you find our response inadequate. \n\n> White it is fairly clear, it may be nice to have a brief but explicit section on the computational complexity of constructing, updating, and querying this data structure.\n\nThank you for the suggestion! Yes, we admit we should have included a note on that with proper time complexity analysis. Sorry. We will add that to a revised draft.\n\n> See above section under weaknesses. I think it may be good to include discussion about the cover tree and related exact and ANN data structures. Currently, I will recommend a 4: Borderline Accept. I think the problem studied is quite interesting and is worth publishing for a simple solution. But there is a lot left that could be said that would be reasonable to expect this paper to include.\n\nThank you for your transparent reasoning for the recommended rating! We hope our answers to your questions above remedy some of your concerns. We’re happy to answer any further questions you may have to convey more clearly why we think our work offers lessons that should be shared with the research community."}, {"review_id": "XBE8pp2XFR", "reviewer": "Reviewer_HqdC", "summary": "The paper studies clustering-based nearest neighbor search. Data structures for this purpose partition the data points into shards, and a query for a point $q$ proceeds in two steps: First, in a routing phase, a set of promising shards is selected. Second, inside each shard, a scoring mechanism is applied to identify the nearest neighbors.\n\nThe submission proposes a novel algorithm for the routing part (the first step above). The algorithm is based on the \"principle of optimism\" from online learning. In a nutshell, it takes an \"optimism parameter\" $\\delta>0$ and assigns thresholds $\\theta_i$ to shards such that with probability at least $(1+\\delta)/2$ all data points in the shard have similarity at most $\\theta_i$ with the query point.\n\nThe new algorithm is based on a one-sided Chebyshev inequality and then it is shown how it can be implemented more efficiently using low-rank approximation of the covariance matrix. This is achieved via SVD and via another, more efficient approach, that employs sketching. This method is motivated through multivariate Gaussians and some additional theoretical guarantees are derived.\n\nIn the experiments, the method is evaluated with data stored on SSDs and on blob storage. It is shown that it outperforms state-of-the-art methods substantially on different real-world datasets.", "questions": "1. To remove the second assumption, would a random rotation as used, e.g., in the fast-JL transform work out of the box when applied to the data points?\n2. If the shards were not given as input, is there some hope to compute shards that provide better guarantees for Problem 1?", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. Nearest neighbor search is an important and still highly active research topic.\n2. The paper is very well-written and easy to follow.\n3. The new method is well-motivated and easy to implement.\n4. Theoretical guarantees are obtained. While I was initially a bit skeptical about the assumptions of Lemma 2, the appendix contains a short discussion about them. It also provides some properties of real-world datasets, showing the validity of the first assumption.\n\nWeaknesses:\n1. As pointed out in Appendix C.2, it might be possible to remove the second assumption through random rotations. I think this direction could have been explored a bit more (and it also does not seem overly difficult to me).", "was_revised": true, "final_justification": "For my final assessment, I have carefully read the other reviews and in particular the discussion with Reviewer uLpi. Given the concerns raised by Reviewer uLpi, I believe the paper would benefit from further improvements. Therefore, I lowered my rating.", "rebuttal": "We appreciate your feedback and your recognition of the strengths of our work! We wish to give our response to your questions below, but please let us know should you have further questions or concerns.\n\n> To remove the second assumption, would a random rotation as used, e.g., in the fast-JL transform work out of the box when applied to the data points?\n> If the shards were not given as input, is there some hope to compute shards that provide better guarantees for Problem 1?\n\nThese are good suggestions. A random rotation or JL Transform could certainly be used out of the box in this algorithm  as a pe-processing step on the vectors. It could also work to remove this assumption - some care will be required in choosing the transform and proving the minimum bound on the entries since the JL transform bounds do not provide a bound on the minimum value of the entries; but, we believe that this is possible and a nice future contribution to this line of investigation.\n\nOne could potentially compute the shards by clustering points in a way that makes it more efficient to solve Problem 1 or makes it possible to solve it more accurately. There are a couple of obstacles with doing this however. One, it is not obvious what the right clustering loss function here is. Since Problem 1 is well-defined and can be solved independently of how the shards are computed, we need to decide how to “couple” the loss function and Problem 1. This is an interesting problem that deserves future investigation. Second, in production systems for ANN, building the index needs to be as efficient as possible - in IVF-based indexes, clustering is the most expensive part of this computation. Doing clustering using a more complicated loss function is likely to make this process much slower. That said, investigating this tradeoff is worth investigating in future work."}, {"review_id": "6Ob7zmFtmg", "reviewer": "Reviewer_oyGp", "summary": "This paper aims to optimize the clustering-based Maximum Inner Product Search (MIPS) and proposed an optimism principle based solution that calculates the scoring function of each cluster more effectively. Finally, experiments are conducted on multiple datasets to test the proposed solution.", "questions": "Q1. Regarding the algorithm design, please explain how to support dynamic updates and conduct experiments on this practical issue.\n\nQ2. Time complexity of Algorithm 1 should be analyzed.\n\nQ3. Section 2.2 starts with an assumption of Gaussian distribution. To support this assumption, it may be better to present a figure on the data distribution.\n\nQ4. The evaluation mainly assesses recall. However, the major concern seems to be time efficiency. The results would be more convincing if the authors directly report the search time (ie latency as did in the appendix).\n\nQ5. Based on the experimental setup, it seems all compared methods must linearly scan each shard. However, in practice, each shard can be indexed by graph-based MIPS index (eg HNSW [R1]). Since HNSW is highly scalable, the improvement may become marginal when HNSW indexes each shard. Please conduct an additional experiment.  \n[R1] Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE TPAMI.\n\nQ6. In both the Introduction and Experimental Setup, the number of clusters is assumed to be $O(\\sqrt{m})$ without references for this setting. When handling many clusters, construction time may be slow. Please report the construction time.\n\nQ7. Some presentation issues:  \n(1) In the references, the venue for \"Unleashing Graph Partitioning for Large-Scale Nearest Neighbor Search\" should be reported.  \n(2) Discussion on the limitations of the proposed solution is missing.  \n(3) Overall, this paper may be a little hard to follow for readers without enough background knowledge.", "limitations": "The paper didn’t point out the limitations.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths:**     \n>S1. The paper studies a meaningful problem.  \n>S2. The proposed solution has some new ideas.  \n>S3. Experiments are conducted on multiple datasets.  \n\n**Weaknesses:**  \n>W1. Practical issues are not sufficiently considered in the algorithm design.  \n>W2. Some experimental setups are unclear.  \n>W3. More experiments are suggested.  \n>W4. The presentation requires further improvements.", "was_revised": true, "final_justification": "In the rebuttal, most of my concerns have been addressed through either justifications or additional results. Therefore, I have increased my initial score.", "rebuttal": "Thank you for your detailed review of our work! We appreciate your balanced feedback and your excellent questions. Below is our response to your questions and concerns, but we hope to engage in a discussion should our note prove inadequate.\n\n> Q1. Regarding the algorithm design, please explain how to support dynamic updates and conduct experiments on this practical issue.\n\nWe agree that addressing dynamic updates is an important, practical question. But the main question there is: How does one add points to existing clusters, and when does one create new clusters? That question is naturally orthogonal to how queries are routed. When a new cluster is formed, or a cluster is updated, all that must happen to route queries correctly is to update the routing logic for that cluster. In Mean or NormalizedMean routers, the centroid must be recalculated; in ScaNN, the weighted centroid must be recomputed; in Optimist, it’s the mean and covariance that must be estimated.\n\n> Q2. Time complexity of Algorithm 1 should be analyzed.\n\nWhen computed using naive algorithms, the time complexity of the algorithm is dominated by the eigendecomposition step which takes $\\mathcal{O}(nd^2 + d^3)$ time. However, since we only need the top $t$ eigenvectors and values to build the router, we can use highly-efficient algorithms designed to compute low-rank approximations of PSD matrices - such as the randomized Block Krylov Method. The survey by Tropp (2018) [1] gives an overview of these methods in Section 6.3 and Musco & Musco (2015) give a theoretical analysis of this algorithm. The time complexity of these algorithms is proportional to $\\mathcal{O}(n d \\log(d) * t)$ making them much faster than naive eigendecomposition. Since $t$ is usually a small constant in our setting, Algorithm 1 can be implemented in near linear time complexity in the size of the data.\n\n[1] Tropp, J. A. (2018). Analysis of randomized block Krylov methods.\n[2] Musco, C., & Musco, C. (2015). Randomized block Krylov methods for stronger and faster approximate singular value decomposition. In Advances in Neural Information Processing Systems (Vol. 2015‑January, pp. 1396–1404).\n\n> Q3. Section 2.2 starts with an assumption of Gaussian distribution. To support this assumption, it may be better to present a figure on the data distribution.\n\nGaussian distribution is a toy example to ease our way into a discussion of the general solution. It’s an example of how moments can be used to find an exact solution to Problem 1. It has no other significance whatsoever.\n\n> Q4. The evaluation mainly assesses recall. However, the major concern seems to be time efficiency. The results would be more convincing if the authors directly report the search time (ie latency as did in the appendix).\n\nWe report recall as a function of the number of data points probed to enable a fair comparison of the efficacy of different routers. The desiderata here is to show how our proposed router is able to decrease the number of points probed while keeping recall high. The evaluation in terms of data points is done to decouple it from possible imbalance in shard sizes, so that a router cannot trivially outperform another by simply prioritizing larger shards. The evaluation in terms of search time is done end-to-end, i.e., we consider the total time required by the search operation, which is the sum of routing, fetch, and scoring. We report the results in Figure 3. Full results about search time are in Appendix I. Please also see our response to Q4 from Reviewer uLpi\n\n> Q5. Based on the experimental setup, it seems all compared methods must linearly scan each shard. However, in practice, each shard can be indexed by graph-based MIPS index (eg HNSW [R1]). Since HNSW is highly scalable, the improvement may become marginal when HNSW indexes each shard. Please conduct an additional experiment.\n\nWhether or not each shard uses PQ to compute scores or IP-HNSW/any other graph algorithm to find the top-k from the shard is immaterial. Studying Figure 3 explains why: Most of the time spent processing a query is on fetching the data from disk, especially in the Blob storage setup, while scoring is a fraction of the total time. Replacing PQ with IP-HNSW (or any “faster” method) would only shrink the scoring time, making it an even smaller fraction of the total cost.\n\nAs you can see from the extent of experimental results reported throughout our work, we are not resistant to the idea of conducting additional experiments so long as they shed light on what we cannot definitively conclude from the current set of experiments. In this case, we can state the above definitively.\n\n\n> Q6. In both the Introduction and Experimental Setup, the number of clusters is assumed to be $\\mathcal{O}(\\sqrt{m})$  without references for this setting. When handling many clusters, construction time may be slow. Please report the construction time.\n\nWe apologize for leaving out the references. Please see Section 5.1 (subsection “Setting the number of lists”) in Douze et al.’s “The Faiss Library.”  That work explains why $\\sqrt{m}$ is a good choice. There are many subsequent studies that adopt that choice - which we’d be happy to list here if necessary.\n\n> Q7. Some presentation issues:\n(1) In the references, the venue for \"Unleashing Graph Partitioning for Large-Scale Nearest Neighbor Search\" should be reported.\n(2) Discussion on the limitations of the proposed solution is missing.\n(3) Overall, this paper may be a little hard to follow for readers without enough background knowledge.\n\nThank you for this feedback! We’ll be sure to address (1) and (2) in a revised draft. As for (3), if you have specific sections that you found confusing or not friendly to the uninitiated, we would gladly revise to make the work more accessible."}, {"review_id": "HvbGEG3Oej", "reviewer": "Reviewer_uLpi", "summary": "This paper considers the k-MIPS problem in the external memory setting.\nThe authors specifically focus on the IVF-based approach and proposed how to rank each cluster (or shard).\nThe representative existing approach computes the inner product of a given query and a cluster center for each cluster, and it accesses the $l$ clusters with the maximum inner products.\nOn the other hand, the proposed approach uses $\\theta_i$ to estimate the maximum inner product obtained from $\\mathcal{P}_i$ by considering its distribution.\nThe first practical solution requires $O(d^{2}|C|)$ space, which can be prohibitive for large $d$ and $|C|$.\nTherefore, the authors proposed to approximate the covariance matrix to reduce the space to $O(t^{2}|C|)$ where $t \\ll d$.\nUnder some assumption, the proposed sketch provides a lower error than Eckhart-Young-Mirsky Theorem.\nExperiments were conducted on real-world datasets, and the results demonstrate that the proposed approach yields a better performance than the baseline approaches.", "questions": "- Q1: Why did this work consider an IVF-based algorithm?\nIt is well known that IVF-based algorithms were outperformed by graph-based algorithms (e.g., DiskANN [Subramanya et al., 2019]).\nI agree that IVF-based algorithms are easy to fit into the disk-based setting, but this is not specific to IVF.\nYou can see that DiskANN can deal with MIPS (https://github.com/microsoft/DiskANN), so the authors need to use it as a baseline.\nFrom that paper, DiskANN can obtain high recall (e.g., 95%) within about 5 milliseconds on Deep1B, while OPTIMIST took more on Deep10M.\nThis paper does not claim the merit of IVF compared to the other approaches successfully and thus fails to motivate the IVF work.\n\n- Q2: Section 2.1 uses the $(1+\\delta)/2$ success probability as its objective without justification.\nFrom the application perspective, it is hard to understand why this probability is involved in the problem setting.\nClearly, this setting is derived from the theoretical bounding procedure, and it is not convincing why we need to address Problem 1.\nThis work needs a more convincing setting.\n\n- Q3: In my understanding, the general solution (in Section 2.2) is not available in practice because it uses unknown distribution $\\mathcal{D}$.\nSection 2.3 overcomes this issue by ignoring the data distribution, which is good.\nMy concern here is that, in both cases, the pre-processing needs more computational cost than the original IVF.\nHowever, its (BuildRouterForPartition's) cost has not been analyzed theoretically and empirically.\nBecause eigendecomposition requires a high computational cost (i.e., $O(nd^2 + d^3)$ for $n \\times d$ matrix), the pre-processing would incur a high cost for high-dimensional vectors.\n\n- Q4: The main experimental results show \"recall and \\% points probed.\"\nThe difference of #points probed however does not guarantee to show the difference of running time directly.\nTherefore, the authors need to use time-recall curves.\nIn addition, comparing with state-of-the-art disk-based graph indices is missing.", "limitations": "yes", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strong points\n* The proposed routing is available for all IVF-based MIPS algorithms (generally).\n* The proposed algorithm is designed from theory to practice.\n* Experiments were conducted on real datasets.\n\nWeak points\n* It is well known that IVF-based algorithms are slower than graph-based ones.\n* The setting of Problem 1 is arbitrary.\n* Important experiments are missing.", "was_revised": true, "final_justification": "Thank you for your discussion after the rebuttal.\nThe author-reviewer discussion revealed that this paper needs improvements/clarifications in most sections, i.e., Sections 1, 2, and 3. \nHowever, they are minor and fixable.\nAlthough I do not champion this paper for acceptance, I'm fine with acceptance.", "rebuttal": "Thank you for taking the time to review our work and give us your thoughts on the current draft! We also appreciate the in-depth questions. We have included below a note with responses to your questions. We hope that clarifies some of the points and resolves some of your concerns.\n\n> Q1: Why did this work consider an IVF-based algorithm? It is well known that IVF-based algorithms were outperformed by graph-based algorithms (e.g., DiskANN [Subramanya et al., 2019]). I agree that IVF-based algorithms are easy to fit into the disk-based setting, but this is not specific to IVF. You can see that DiskANN can deal with MIPS (https://github.com/microsoft/DiskANN), so the authors need to use it as a baseline. From that paper, DiskANN can obtain high recall (e.g., 95%) within about 5 milliseconds on Deep1B, while OPTIMIST took more on Deep10M. This paper does not claim the merit of IVF compared to the other approaches successfully and thus fails to motivate the IVF work.\n\nIVF and graph-based approaches to ANN search are two prominent paradigms that are widely adopted in practice. There are many examples of both of these in the (still very much active) academic literature as well as industry solutions. We cited some that speak to both, and why one may choose IVF over graphs and vice versa. But if you find those references insufficient, a very recent study [Kuffo and Boncz “Bang for the Buck: Vector Search on Cloud CPUs”] performs a comparative analysis and explains why one may adopt IVF over graphs and vice versa.\n\nOur work is a study of routing in IVF, a subproblem that is specific to IVF. We do not claim IVF is “better” than graphs in any shape or form, and have no qualms about whether one chooses DiskANN or IVF in practice. The problem we studied is an underexplored research topic within the IVF method, and we show there is room for research. To give you an analogy, the equivalent problem in DiskANN (or graph methods in general) is how to traverse the graph; the current practice is a greedy search. Our research presented in this work is equivalent to research on other ways of traversing the graph during search. We therefore do not agree that a comparison with DiskANN adds any value whatsoever to the merits or conclusions of our work.\n\n> Q2: Section 2.1 uses the $(1 + \\delta) / 2$  success probability as its objective without justification. From the application perspective, it is hard to understand why this probability is involved in the problem setting. Clearly, this setting is derived from the theoretical bounding procedure, and it is not convincing why we need to address Problem 1. This work needs a more convincing setting.\n\nSection 1 Subsection “Existing routers and the role of optimism” shows why we hypothesize that the principle of optimism plays a role in the efficacy of routing in IVF. That motivated us to formalize the notion of optimism for IVF, which is our definition presented in Problem 1. We do not claim that Problem 1 is the only way to formalize that notion; we instead offer it as a reasonable definition of optimism: Depending on how much information is available to us, we can, with some confidence (i.e., $(1 + \\delta)/2$) estimate that the probability of the maximum inner product within a shard is no greater than a threshold ($\\theta_i$). A larger $\\delta$ makes the formulation more optimistic. This message should come across in the discussion that immediately follows Problem 1 (Lines 122 through 129).\n\nAs for why $(1 + \\delta) / 2$: The choice is for notation purposes only. The expression was chosen to (a) allow $\\delta$ to be between 0 and 1, and (b) make expression (6) “cleaner.” You are free to change the right-hand-side of the inequality to $\\delta$ in Problem 1, and that would simply change the expression in (6), nothing less, nothing more.\n\nAs for how one should interpret $\\delta$ in practice: We have included extensive experiments that study this hyperparameter. Please see Figure 7 in Appendix E.\n\n> Q3: In my understanding, the general solution (in Section 2.2) is not available in practice because it uses unknown distribution $\\mathcal{D}$ . Section 2.3 overcomes this issue by ignoring the data distribution, which is good. My concern here is that, in both cases, the pre-processing needs more computational cost than the original IVF. However, its (BuildRouterForPartition's) cost has not been analyzed theoretically and empirically. Because eigendecomposition requires a high computational cost (i.e., $\\mathcal{O}(nd^2 + d^3)$  for  matrix), the pre-processing would incur a high cost for high-dimensional vectors.\n\nYou are correct in noticing that when computed using naive algorithms, the time complexity of the algorithm is dominated by the eigendecomposition step which takes $\\mathcal{O}(nd^2 + d^3)$ time. However, as highlighted in our response to reviewer oyGp, since we only need the top $t$ eigenvectors and values to build the router, we can use highly-efficient algorithms designed to compute low-rank approximations of PSD matrices - such as the randomized Block Krylov Method. The survey by Tropp (2018) [1] gives an overview of these methods in Section 6.3 and Musco & Musco (2015) give a theoretical analysis of this algorithm. The time complexity of these algorithms is proportional to $\\mathcal{O}(nd \\log(d) * t)$ making them much faster than naive eigendecomposition. Since t is usually a small constant in our setting, Algorithm 1 can be implemented in near linear time complexity in the size of the data.\n\n[1] Tropp, J. A. (2018). Analysis of randomized block Krylov methods.\n[2] Musco, C., & Musco, C. (2015). Randomized block Krylov methods for stronger and faster approximate singular value decomposition. In Advances in Neural Information Processing Systems (Vol. 2015‑January, pp. 1396–1404).\n\n\n> Q4: The main experimental results show \"recall and % points probed.\" The difference of #points probed however does not guarantee to show the difference of running time directly. Therefore, the authors need to use time-recall curves. In addition, comparing with state-of-the-art disk-based graph indices is missing.\n\nThis is a great question with an answer that is nuanced. Let us elaborate.\n\nAs we explain in the submission, there are three main subroutines that contribute to ANN search latency: (a) routing, (b) fetching, and (c) scoring. The routing latency is a function of the number of clusters. The fetch latency depends on the number of identified clusters, which in turn is proportional to the number of points in the union of those clusters. The scoring latency is a function of the number of points that need to be scored.\n\nFollowing the reasoning above, it is appropriate to measure recall vs. the number of points probed. However, for completeness, in Figure 3, we provide a breakdown of the search time as a sum of its three main operations when indexes are on SSD or blob storage. The analysis is provided as mean latency (msec.) to reach 95% recall. In Appendix I, we extend the same analysis by introducing the number of threads used in a multi-threading search (1, 2, and 4 threads).\n\nAs for a comparison with disk-based graph indices, please see our response to Q1."}]

Author rebuttal:

Meta-review: Based on my reading the reviews, author responses and discussion, I see the following strengths of this manuscript:

- **S1.** The submission focuses on an underexplored area of the routing scheme in IVF based max-inner-product-search or MIPS, and proposes a new routing scheme that results in significant reduction of the number of points that need to be probed.

- **S2.** The presentation is very clear, and the proposed scheme is well positioned against existing literature on similarity (both in the original submission and in the author-reviewer discussion).

I also see the following limitations of this manuscript:

- **L1.** One significant limitation appears to be the specific focus on IVF based schemes, as that can limit the impact of the proposed scheme. However, the authors have attempted to address this concern in the author response by highlighting situations where IVF based schemes are the right way to go, and the proposed scheme would provide benefits in such situations.

- **L2.** Another limitation appears to be the empirical evaluation that focuses on the number of points probed as a surrogate for latency. However, in the response to reviewers, the authors provide evidence that this metric is an appropriate surrogate for latency, thereby justifying their choice.

I believe while this paper has limitations, the limitations have been appropriately addressed through the author-reviewer discussion.
Decision: Accept (poster)