SOAR: Improved Indexing for Approximate Nearest Neighbor Search
Authors: Philip Sun
David Simcha
Dave Dopson
Ruiqi Guo
Sanjiv Kumar
Venue: NeurIPS 2023 poster (2023)
Keywords: ann
quantization
mips
nearest neighbor search
retrieval

Abstract: This paper introduces SOAR: **S**pilling with **O**rthogonality-**A**mplified **R**esiduals, a novel data indexing technique for approximate nearest neighbor (ANN) search. SOAR extends upon previous approaches to ANN search, such as spill trees, that utilize multiple redundant representations while partitioning the data to reduce the probability of missing a nearest neighbor during search. Rather than training and computing these redundant representations independently, however, SOAR uses an *orthogonality-amplified residual* loss, which optimizes each representation to compensate for cases where other representations perform poorly. This drastically improves the overall index quality, resulting in state-of-the-art ANN benchmark performance while maintaining fast indexing times and low memory consumption.

SOAR: Improved Indexing for Approximate Nearest Neighbor Search
Philip Sun, David Simcha, Dave Dopson, Ruiqi Guo, and Sanjiv Kumar
Google Research adopson, guorq,
Abstract
This paper introduces SOAR: Spilling with Beongoonalit-Ammliiiee Residuals, a novel data indexing technique for approximate nearest neighbor (ANN) search. SOAR extends upon previous approaches to ANN search, such spill trees, that utilize multiple redundant representations while partitioning the data to reduce the probability of missing nearest neighbor during search. Rather than training and computing these redundant representations independently, however, SOAR uses arrhogonality-ampliffee residual loss, which optimizes each representation compensate for cases where other representations perform poorly. This drastically improves the overall index quality, resulting in state-of th--her- ANN benchmark performance while maintaining fast indexing times and low memory consumption.
Introduction
The k-nearest neighbor search problem is defined as follows: we are given an n-item dataset X' E Raxdd composed of d-dimensional vectors, and for query q E Rd, we would like to return the k vectors in A' closest to This problem naturally arises from number of scenarios that require fast, online retrieval from vector databases; such applications include recommender systems 7 image search [14] and question answering [10, among many others.
While nearest neighbor search may be easily implemented with linear scan the elements of X, many applications of nearest neighbor search utilize large datasets for which a brute-force approach is computationally intractable. The rapid development of deep learning and embedding techniques has been an especially strong driver for larger k- k-ncarest neighbor datasets. For instance, multiple recent large language model (LLM) works incorporate external information by using k-nearest neighbors to retrieve from longer contexts 17 or large text corpora (5]. While datasets from typical applications a decade ago (e.g. Netflix) had sizes of around 1 million [5), the standard evaluation datasets from big- ann benchaaksss [16] all have billion vectors with hundreds of dimensions.
These large datasets, in conjunction with the curse of dimensionality, phenomenon which often makes it impossible to find the exact nearest neighbors without resorting to a linear scan, has led to a focus on approximate nearest neighbor (ANN) search, which can trade off small search accuracy loss for significant increase in search throughput.
A number of indexing schemes proposed for ANN search, including spill trees 122.. assign datapoints to multiple portions of the index, such that the overall index provides a replicated, non-disjoint ("spilled"") view of the dataset. These algorithms have used partitioning schemes amenable to random analysis, so that the replication factor can be provably shown to exponentially reduce the probability of missing nearest neighbor. However, partitioning high-dimensional data is difficult, even without the constraint of doing so with a method amenable to randomized analysis; such constrained partitioning techniques have led inferior quality indices that have not yielded good compute-accuragy tradeoffs.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

On the other hand, another family of approaches, those leveraging vector quantization (VQ), have demonstrated excellent empirical ANN performance, but little research has been done exploring the use of multiple randomized initializations of VQ indices to further increase ANN search efficiency. This is partly due to the fact that multiple VQ indices initialized through different random seeds do not have strong statistical guarantees and cannot be proven independent in their failure probabilities. This paper bridges the gap between these two approaches to ANN:
We demonstrate the weaknesses of current VQ-based ANN indices and illustrate how multiple VQ indices may be used in conjunction to improve ANN search efficiency.
We show that the naive training of multiple VQ indices for single dataset leads to correlation in failure probabilities among the indices, limiting ANN search efficiency uplift, and present spilling with orthogonality-nplle
residuals (SOAR) to ameliorate this correlation.
We benchmark SOAR and achieve state-of-the-al performance, outperforming standard VQ indices, spilled VQ indices trained without SOAR, and all other approaches to ANN search that were submitted the benchmark.
2 Preliminaries and Notation
2.1 Maximum inner product search (MIPS)
SOAR applies to the subclass of nearest neighbor search known maximum inner product search, defined as follows for a query and a dataset X':
MIPS (q, X) k-arg max (q,
#EX'
Many nearest neighbor problems arise in the MIPS space naturally [6). and number of conversions exist [4] from other commonly used ANN search metrics, such as Euclidean and cosine distance, to MIPS, and vice versa. We measure MIPS search accuracy using recall @ k, defined as follows: if our algorithm returns the set of candidate nearest neighbors, its recall @ & equals [MIPs 2)SS Additionally, introduce the following notation to assist with MIPS analysis:
RANK(g, u, v, = Σ ((a))s(a))
aEX
The max inner product's RANK is I; assuming no ties, RANK(g, u, X) E [1, for E MIPS X).
2.2 Vector quantization (VQ)
Vector quantization can be leveraged to construct data structures that effectively prune the ANN search space; these data structures are commonly known as inverted file indices (IVF) or k-means trees. Vector-quantizing dataset X' produces two outputs:
C E Rexd the codebook containing the partition centers.
xu)) Rd + (1...., c), the partition assignments that map each vector in X' one of the partition centers in C. Oftentimes, <vv) is defined as arg min.e ||e - C, 2| although other assignment functions may also be used.
We can then construct an inverted index over л, for each partition i, we store the set of datapoint indices belonging to that partition: (i) = i). Then, instead of computing MIPS; X)) directly, we may first compute MIPS (q, C), which is much faster because |C| < | We can then use our inverted index data structure to further evaluate the datapoints within the top k' partitions.
2.2.1 The k-means recall (KMR) curve
The effectiveness of the VQ-based pruning approach depends on the rank of the partitions that MIPS X') are in. If these partitions rank very well, we can set k' very low, and search through few partitions while still achieving great MIPS recall. If these partitions rank poorly, however, the algorithm will have to spend lots of compute searching through many partitions order find the nearest neighbors. We may quantify this effectiveness using the k-means recall (KMR) curve (named

---

because VQ indices are commonly trained through k-means, although KMR can be computed for any VQ index, not just those trained via k-means), defined as follows:
(M: 2,
E
CRANK(g.C((,)0055
(1)
qEQ #EMISs
The KMR curve for given query sample Q. dataset X', and VQ index (C, т) quantifies the proportion of MIPS nearest neighbors present in the top VQ partitions, over varying The KMR curve is non- decreasing, with KMR; (0) = 0 and KMR = 1. A KMR curve that more quickly approaches 1 indicates superior index quality.
3
Method
The key insight of our work the use novel loss function to assign datapoint & to multiple VQ partitions, such that these additional partitions effectively recover æ: in the pathological cases when x is a nearest neighbor for a query that x's original VQ partition handles poorly. These partitions that include æ work together synergistically partition could alone. Below, we describe the motivations behind our new loss and this multiple assignment. The supplementary materials contains the source code generate this section's 's plots.
provide greater ANN search efficiency than any single
3.1 Search difficulty and quantized score error
For a datapoint x, define as the partitioning residual, equal to Ca(z)- The partition center Cr((a) is the quan- tized form of z, so the difference between the exact and the quantized inner product scores is
0.6
Mean (q.r)
0.4
(g.x) - (q, Cr(z)) = (q, - Cr(z)) = (a,r),
0.2
which we denote the quantized score error. Consider the case when is nearest neighbor for the query: x E MIPS (q, X²). In this scenario, we would like RANK(g, (x)) C) to be low, that the algorithm may search just the top few partitions and find the nearest neigh- bor æ. high RANK would lead increased search dif- ficulty, because the algorithm would have to search more partitions and therefore do more work find x.
0.0
500
1000 1500 2000 Rank(q, Croci
Figure 1: Greater search diffi- culty, as quantified by higher RANK(q, C)()).C,, is associated with highly positive (g.r).
Given that (g, C=(w)) = (g. x) - (g. r) and that, by defi- nition, (g. x) is large when æ E (ipSs X),, we know that (g, (2()) will be small (leading greater search dif- ficulty) when r) is highly positive. Indeed, this be confirmed empirically; in Figure plot the mean (g,r) as a function of RANK(y, Cx(z). C) for all query-neighbor pairs (q, in the Glove-IM IM dataset. The more difficult-to- pairs have, on average, notably higher (q, r).
SOAR increases search efficiency in these situations when z E MIPS X') and (q,r) is high.
3.2 Quantized score error decomposition By the definition of the inner product,
(q,r) = ||9|| ||||| cos
where is the angle formed between the query and the partitioning residual. Without loss of generality, may assume that |qll = 1 without any effect on the ranking of MIPS nearest neighbors. The two contributors to a highly positive (g. r) are therefore a large ||]]] and cos & being near unity; reducing (q,r) requires targeting either, both, of these contributors.
SOAR targets 6, because that term both easier reduce and has greater impact on (g. r):
The VQ training loss already aims to minimize E|| Catar) I = E] so further reductions in ||||| are difficult. In contrast, cos 0 is not directly optimized for, making more amenable to reduction.
3

---

cos is typically much more strongly correlated with (g, r) than ||r]] is, so its reduction has greater impact on search difficulty. Qualitatively, this stronger correlation can be explained by the far greater range of values cos / may take on, compared to ||r||- The latter's values are concentrated between and ||=r]] with not very large ratio between the largest and smallest value. In comparison, cos 0 can take on any value in the range [-1, 1]; only this large multiplicative dynamic range can explain the variance in (q, r). Empirically, this can be seen demonstrated on Glove- MM in Figure below.
0.6
0.986
Quantized Score Error (q. n-
0.6
Corr=0.451
Quantized Score Error (q.
0.4
0.4
0.2
0.2
0.0
0.0
-0.2
-0.4
-0.2
0.0
0.2
0.4
0.6
0.2
0.4
1.0
1.2
Query-Residual Angle cose
Partitioning Residual Norm [r]l
Figure 2: The cosine the query query-residual angle, cos 9 (left), is far more correlated with (g,r) than the residual norm |r| (right), making the former more promising target for reducing (g.
3.3 Spilled VQ assignment
We may attempt to mitigate the increase in search difficulty presented by high cos 9 by assigning each datapoint æ to a second VQ partition (zx), resulting in second partitioning residual r' that forms an angle 0' with the query. We denote this second assignment spilled assignment.
This gives our ANN algorithm a "second chance"; assum- ing 9 and 0' are independently distributed, the situations where cos B is high, thereby leading to high (g. r) and greater search difficulty, are unlikely also have high cos 0'. A low cos 0' should lead to a low (g, r') and should allow the ANN algorithm find fairly efficiently. This idea can be extended to further (>2) assignments as well.
C2
C1
x
er
This approach leads to implementation intricacies, discussed in Section 3.5) but for now we focus on problems concerning theory when the spilled assignment n n'xx) is chosen so as to minimize ||?
C3
Figure 3: Naive spilled VQ assignment may be ineffective; selecting the two closest centroids C₁ and C2 provides no benefit over using just C1.
This proposed approach fails when there is correlation between cos and cos 0', shown to the extreme Figure
In this figure, if ((r) = 1, we may pick (x:) 2 because Cg is the second-closest centroid to z. However. C2 is collinear with C₁ and resulting in
0'. This leads to C2 acting strictly worse version of C for quantizing æ: (g.7") = (1+ +1++ e) (g. r). The choice n (x) = would've been more effective, despite ||. Csl I --CC C2 due to Cy's position giving 0' of
Experiments show that more than theoretical concern, this is also real-world issue. On the Glove 1M dataset, if we choose (Φ)) and <zx to be the closest and second-closest centroids by Euclidean distance, respectively, to æ, we find a noticeable correlation between cos 0 and cos 0', shown in Figure 4a An even stronger correlation occurs between two VQ indices trained separately with different random seeds (Figure 4b). This correlation diminishes the benefit of spilled assignment, and reducing this correlation is critical to improving ANN search performance.

---

0.6
0.6
0.4
0.4
cos0,
cos
0.2
0.2
0.0
0.0
-0.2
-0.2
Corr=0.483
Corr=0.786
0.4
-0.4
-0.2
0.0
0.4
0.6
-0.4
-0.2
0.0
0.2
cose
cos0;
(a) f come from single VQ index, are closest and second-closest centroids, respectively.
(b) 01 and 02 come from two VQ indices, trained with different random seeds.
Figure 4: On Glove-IM, both naive top-2 spilled assignment and two separately trained VQ indices exhibit noticeable correlation in query- query-residual angles; this reduces spilled assignment efficacy.
3.4 Spilling with orthogonnlliy-ampliiee residuals
We now derive spilling with aathooonalit-amppiifee residuals (SOAR), novel VQ assignment loss that directly confronts the problem of correlated query-residual angles. To derive this loss, assume that the VQ centroids and assignments и fixed. The goal of further spilled assignments x' is to achieve low quantized score eтror (g, r') specifically when the original spilled assignment has high cos leading high (g. r). cases where 0 is low, the original assignments already achieve low quantized score error, so in such cases, it is less important to also have low (g. r').
We now modify assignment loss function reflect this emphasis; rather than selecting c' C to minimize Eyeg (o0e(((1220) .r) (1) EgE 1/4 r') we now also add weighting term for cos O: (q, r)
C(r', r, Q) = E
(q, r") = (cos (q. r²)
(2)
|r|l ||
where the weight function w(-) IR + R=20 should be chosen to give greater emphasis to higher cos 0. To utilize this loss function in VQ assignment, we must evaluate the expectation, which leads to the following result:
Theorem 3.1. For the weight function w(t) |t| and a query distribution Q that is uniformly distributed over the unit hypersphere,
C(r' r. Q) x ||r + Al[proj, 7112.
Proof. See Appendix A.I
By leveraging Theorem we may efficiently perform spilled VQ assignment using our new loss by computing the squared & distance to each centroid, adding penalty term for parallelism between the original residual and the candidate residual r', and taking the arg min among all centroids. We present the following statements to help develop intuition about the SOAR loss:
Corollary 3.1.1. For the uniform weight function w(t) = |t the SOAR loss equivalent to standard Euclidean assignment: C(r', r. Q) x ||r'
The parameter À controls how much the spilled assignment xL should prioritize quantization perfor- mance when the original assignment performs poorly, relative to general quantization performance. As increased, the former is further emphasized; at X 0, only the latter considered, leading to standard Euclidean assignment. See Figure in Experiments for a visualization of this tradeoff.
Corollary 3.1.2. For a fixed ||r'|] C minimized when and r' are orthogonal, in which case Al|proj, r1 and L(r', r, Q) x ?|?
Our technique's name originates from the observation that residuals are encouraged to be orthogonal. Lemma 3.2. ||proj, r'll = ||r'||| (igxx).(rr"' where p is the Pearson correlation coefficient, and the correlation is computed over q uniformly distributed over the hypersphere.
5

---

The above lemma shows that in addition to the weighted quantization error derivation in Equation 2 we may also interpret the SOAR loss adding a penalization term for correlation quantized score enror, scaled by the magnitude of the quantization error.
Proof.
r) (g,r") El( (g, Bi(a, Bl
Plarr)(arr")
(ggr)) ((..))((grr)) (g.r")
and by symmetry over the hypersphere, [B[g, r)] El(g, r
so our expression simplifies to r' "'gg"']r"
El(g.)) r4) Eir" qq' Trl
P(ar).(ar") (g.r)) (g.r") (g.r) ( (g.r1)
a (1.r))
It's well known that for uniformly distributed, unit-norm g E Id that Elgg"] = La/d, where la the d-dimensional identity matrix, and that (g.n) = =|vil// V for any fixed v. We leverage this to get
, (La/d)r' (|H1)//\\((*///))))
( |||l
1 ||]
Iprooj r'll-
P(a.))laar))
||]| |M]
|r||
3.5 Implementation considerations
SOAR comes with some memory overhead relative to non-spilled VQ MIPS index, due to its multiple assignments causing some duplication of data. The overhead quite negligible because only the
bitrate (PQ) [9] datapoint representation, not the datapoint's highest-bitrate representation (usually int8 or float32). duplicated. Since PQ much more compressed than int8 or float32, duplicating the PQ data for each of datapoint's 's spilled assignments only marginally increases memory footprint, as illustrated in Figure 5 This can be quantified analytically:
SOAR increases memory consumption by + d bytes/datapoint, assuming 16 centers per 2a
subspace (usually chosen for amenability to SIMD) and dimensions per PQ subspace.
The datapoint's s original assignment already contained PQ representation occupying 4 + d bytes, and its highest-bitrate representation requires bytes (int8) or bytes (float32).
When the ANN index's 's highest- bitrate datapoint representation is int8 float32, the relative index
size growth is therefore 4 d
4 d
d
1
d d+4+ d 2s
2s+1
4d 4 d 4d +
d 2s
2s
respectively. Table emmprically corroborates these estimates and shows memory cost is indeed quite low (5%% relative increase over non-spilled VQ index).
Partition
VQ Partition 3
Height memory footprint per datapoint
PQ representation: d/2s bytes per ciatapoint
Legend
data for original datapoint
rescoring bytes per dataaoint
data for spilled detapoint
original PO to rescoring mapping
Rescoring data: intà or floet32 representation; bytes per datapoint
spilled rescoring mapping
Figure 5: Memory layout changes for a SOAR-enabled ANN index. Memory footprint is proportional area of colored cell. VQ centroid data (not shown) remains unchanged. We can see that the additional memory occupied by SOAR (dark blue) is low relative to the total memory consumption.

---

SOAR also results in a small amount of query-time CPU overhead over a non-spilled VQ index, due to SOAR's need for deduplication: a single datapoint may now appear in multiple partitions that are all searched. This overhead is low, though, because VQ inverted index performance is primarily bottlenecked by memory accesses to the VQ partition data, and this access pattern remains the same.
Finally, SOAR requires a minor tweak to the indexing pipeline. Creating a SOAR-enable, index first requires training standard, non-spilled VQ index as usual. This gets used to populate the primary assignments, but is also used to calculate the residual т. which is then used in the SOAR loss to select further, spilled assignments. Other parts of the ANN indexing pipeline remain unchanged.
Overall, SOAR's s search efficiency gains greatly outweigh its memory, CPU, and indexing overheads.
3.5.1 Spilling to further centroids
The analysis conducted in Section 3.4 focused specifically the case of assigning two partitions, v and This can be generalized to an arbitrary number of further assignments, where each subsequent assignment is done with loss considering the distribution of quantized score errors from all prior assignments. We forgo this generalization in experiments and focus on the two-assignment setup because further assignments have diminishing return;; the first spilled assignment is generally sufficient to handle the cases where the primary assignment has high quantized score error, so further assignments are only needed in rare, doubly pathological situations. Meanwhile, the additional memory and indexing cost increases linearly with further assignments; two assignments strikes a good balance between these costs and KMR benefits while also keeping implementation simple.
4 Related Works
4.1 Spill trees
Spill trees (or sp-trees) were originally introduced in [[2], and also assign datapoints to multiple vertices at the same level of the tree, just as SOAR may assign datapoint to multiple VQ partitions. However, there are significant differences; spill trees were searched using defeatist search, a greedy, no-backtracking strategy that took the most promising root-to-leaf path. SOAR indices utilize backtracking in their search procedure; multiple partitions, not just the top one, are evaluated further.
Spill trees also differ in how they perform assignment; their multiple assignments occur at cach level of the tree, such that single datapoint could appear in exponentially many leaves, with respect to the tree depth (which was significant, as spill trees are binary and therefore rather deep). This led to large (sometimes >100x (T]) storage overhead, which was very costly. In contrast, SOAR performs the multiple assignments at individual levels of the tree, leading to a storage overhead that is constant with respect to the tree depth, and much lower (typically 10%-20%; see Table [T. Finally, SOAR leverages its custom, spilling-awar to spill to, while the spill tree, as a consequence of its binary structure, only had to make the binary decision of whether to spill all.
assignment loss to decide which among the many VQ partitions
4.2 Graph-based algorithms
traph-based approaches to ANN search, such as 13,, have received significant amounts of recent research attention, and number of such algorithms are featured in comparisons in Section 5.4 If one considers datapoints and partition centers to be vertices, and natapoint-to-partitin assignments to be edges, a traditional VQ index would form tree structure, while spilled VQ assignment (including SOAR) would transform the tree into a cycle-containing general graph data structure. In this sense, SOAR makes VQ indices more closely resemble graph-based ANN indices.
However, grsph-based ANN algorithms (as defined in the traditional sense) have no concept of partition centers, and only add edges between datapoints themselves, leading to a lack of hierarchy and linearizability. SOAR inherits the linearizability of bree-based approaches, leading to predictable and sequential memory access patterns that are necessary for achieving maximal performance on modern hardware. SOAR also inherits the small index sizes more easily achievable with tree-based methods. When viewed as a graph, SOAR index only uses two edges (two partition assignments) per datapoint, while traditional graph-based indices typically use dozens of edges per datapoint, which incurs significant storage overhead that SOAR avoids.
7

---

Experiments
5.1 KMR curve comparison
The KMR curve is deterministic and easily computable metric for VQ-style ANN indices that's highly predictive of real-world performance. Below, we plot (t) as defined in Equation [ but rather than plotting with respect to t, we plot with respect to the sum of the sizes of the i top- ranked partitions. This partition size weighting is necessary because spilled VQ data structures have more points per partition due their multiple assignments, making each individual partition more expensive to search. The results are shown Figure 66 further details are given Appendix A.2
100
Recalig100 (Percent)
Rocali@100 (Percent)
95
Reciiig100 100 (Percent)
95
95
90
90
No spilling Spilling, no SOAR SOAR
spilling
No spilling
80
Spilling, no SOAR SOAR
80
Spilling, no SOAR SOAR
05
75
300000
20000
40000 60000 Detapoints Searched
80000
50000
100000
150000
Datapoints Searched
Datapoints Searched
Glove-IM
(b) Microsoft SPACEV
(c) Microsoft Turing-ANNS
Figure 6: SOAR allows a VQ index to achieve a given recall target while reading fewer total datapoints and therefore utilizing less memory bandwidth, increasing ANN search performance. SOAR's 's improvements are especially large on Microsoft SPACEV and Microsoft Turing-ANNS, the billion-scale datasets this experiment; see Section 5.3 for further analysis of dataset size.
5.2 Correlation analysis
Here, we look at a number of statistics relating to the quantized score error that shed light on how SOAR improves KMR and overall VQ index quality. These statisties computed the Glove- 1M dataset with the SOAR À set to I; see source code in supplementary materials for more details.
Figure 7 looks at the query-residual angle, where the residuals are taken from the nearest neighbor results for each query. The scatterplot looks at cos from the primary VQ assignment and cos 6' from the spilled VQ done with SOAR. In comparison with the equivalent scatterplots in Figure done without SOAR, we can see that SOAR significantly reduces the correlation between the cosines of the two angles, thus increasing the efficacy of multiple VQ assignments.
1400
SOAR
0.6
1200
SOAR
0.4
1000
Rank(a, Grid
cose
800
0.2
600
0.0
400
-0.2
200
Cor1=0.197
-0.4
-0.2
0.0
0.2
0.4
0.6
0
500
1000
1500
2000
cos
Rank(g, Caoo C)
Figure 7: Scatter plot, analogous Figure 4a but with spilled assignments performed using SOAR loss; angular correlation is much lower.
Figure 8: The nearest neighbors most difficult to find under partitioning RANK (g, Cx(ee), C), also tend to be difficult to find under n' when SOAR isn't isn't used.
quantified by
The end result of this reduced correlation can seen in Figure which plots the mean rank of nearest neighbor's spilled centroid against the rank of that neighbor's primary centroid. We can

---

see that without SOAR, when nearest neighbor's primary partition <(x) ranks poorly, the nearest neighbor's spilled partition r' (xx) tends also rank poorly, meaning the spilled assignment is doing little to help ANN performance; the ANN algorithm will still have to search through many partitions to find x. With SOAR, RANK (z((z)) C) remains low, allowing the ANN algorithm to search significantly fewer partitions to find the nearest neighbors.
Next, in Figure 2 we investigate the effect of SOAR's À parameter on the resulting VQ index. We can see that as À increased, the resulting partitioning n' from SOAR will have quantized score error (q. r') less and less correlated with the quantized score error (g. r) from x. This is ben- eficial for ANN search efficiency, but on the other hand,
0.6
Correlation
1.0
Distortion
0.4
0.5
0.2
|| |] = ||]]]]] increases with respect
0.0
to A. The diminishing relative importance of ||r" A increases natural consequence of Theorem 3.1 but nonetheless results in general increase in magnitude of (q, r') and is detrimental to ANN search accuracy; setting the optimal À requires balancing these effects.
SOAR
Figure 9: Raising SOAR À increases VQ distortion [[[[]'||), but lowers score cor- relation P(a.r).la.r)
5.3 Effects of dataset size and recall target
In Figure TO we take various size samples from
the ann ann-benchmarks com DEEP dataset and compare the ratio of how many datapoints SOAR VQ index must access compared to standard VQ index to achieve the same recall. This ratio is the dependent variable in Figure T0] a higher ratio indicates a greater improvement from SOAR. We see that higher recall tar- gets, and larger samples, lead to greater ratios.
1.4
100K
3M 9.99M
300K
KMR Efficiency Gain
1M
1.0
We maintain ratio of 400 datapoints tition across all sample sizes (for example, the 1M datapoint sample was trained with 2500 par- titions). This sampling-bast over using various datasets of differing sizes, to eliminate effects due to varying search diffi- culties among datasets.
par-
85.0%
90.0%
95.0%
Recall Target (R01100)
approach was cho-
Figure 10: SOAR's s ANN search efficiency benefit grows SOAR is applied to larger datasets, and as the ANN recall target rises.
5.4 End-to-end recall-speed benchmarks
ANN search algorithms are ultimately compared by their ability to trade off ANN search accu- racy (measured by recall), and speed, measured by perrres-per-eeond throughput. Here we per- form this comparison between SOAR and state- of-the-art algorithms in two standardized bench- marking frameworks.
12000
Speed (Queries Second)
hipplls
annoy
10000
hnowifaisn
hnswtib
8000
glass NGT-onng
6000
ScaNN
First, we modify ScaNN to utilize SOAR and benchmark its performance on a standard- ized testing environment with an Intel Xcon W-2135 processor and the test setup from ann- benchmarks.com [ The algorithms for com- parison were installed, configured, and tuned according to their respective benchmark submis- sions, and run on the same environment; see Appendix A.3 for more details. As shown in Figure TT SOAR improves upon ScaNN's al- ready state-of-the-art performance.
4000
2000
0
0.86 0.88 0.92 0.94 0.96 0.98
Accuracy (Recall@10)
Figure 11: SOAR + ScaNN on Giove-IM.

---

Next, we benchmark an ANN search implementation using SOAR on multi-level k-means clustering against submissions Track of of Biig-ann-bencheen custom hardware, enabling greater flexibility in approaches to ANN search, but also complicating direct comparison due to the difficulty in accounting for varying hardware costs. In an effort to present existing benchmark submissions in fair light, we compare SOAR against these submissions in two ways:
[6]. These benchmarks allow the use of
1. We compare the ratio of search throughput to hardware price. The ratios for competing algorithms were taken directly from the benchmark leaderboard, which was straightforward. but SOAR's results were from virtualized cloud compute, so the capital expenditure of buying a server with equivalent power had to be estimated. Hardware prices now may be slightly lower than prices used by other submissions in 2022, their time of submission; on the other hand, SOAR likely would' ve performed better if run on dedicated hardware, where other jobs competing for the processor's 's various shared resources.
2. We compare the ratio of search throughput to estimated monthly cloud billing cost for each submission's 's hardware. One benefit of this method is that hardware costs are completely equalized; in contrast, the alternate method of comparison rewarded contestants for finding especially discounted offerings for the same memory or compute. Additionally, the popular- ity of cloud infrastructure over self-hosting implies this ratio is what truly matters for many deployers of ANN search algorithms. However, we can't 't compare against submissions that use proprictary or deprecated hardware, and benchmark contestants never directly optimized for this ratio, because cloud cost was never used in any original benchmark leaderboard.
Although neither comparison alone is perfect, the two in aggregate provide a solid characterization of SOAR's 's performance. Further experimental details are provided Appendix A.4 and results are shown in Figure 12 below; our index leads under both cost metrics, and SOAR is critical for our index's 's performance, roughly doubling throughput over a traditional, non-spilled VQ index.
Baseine
DiskANN
CUANNS-IVPPQ
Baseline
DisKANN
CuANNS-IVFPO
CuANNS-Mutt
Optane
Ours
Ours SOAR)
CuANNS-Mulli
Ours
Ours [no SOAR)
20
GPS Righ l'Moniblyy Cloud Coel)
40
QPS at 90% Right/ (Hardware Cost)
10
20
MS-SPACEV
MS-Turing
MS-SPACEV
MS-Turing
(a) Throughput-to-capex ratio (higher is better)
(b) Throughput-to-cloud bill ratio (higher is better)
Figure 12: SOAR leads
performance under both methods of comparison.
Finally, we present memory consumption figures for the ANN indices in these benchmarks in Table The minor increase in memory usage is discussed and analyzed in Section 3.5 and find that analysis corroborates well with the empirical measurements below. For all three datasets, the index size increase very minor, and the throughput gains from SOAR could allow the same query traffic to be served by fewer server replicas, in fact potentially reducing net memory consumption.
Dataset
Memory Usage, No SOAR
Memory Usage with SOAR
Glove-Io I M
453.5 MB
488.4 MB (+7.7%)
Microsoft Turing-ANNS
120.03 GB
140.23 GB (+16.8%)
Microsoft SPACEV
120.85 GB
141.80 GB (+17.3%)
Table 1: ANN index memory consumption beforc/after SOAR.
10

---

References
[1] Compute engine pricing. http:////..ooogggooooooccccc//ca
Accessed: 2023-03-16.
[2]
Intel()) optane TM business update: What does this mean for warranty and support. https::/ww..ing intel com/ cont http:///ww.///ooppttttttt/////// cessed: 2023-05-15.
and and-storage... html
Ac-
[3] Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. Ann-benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems, 87:101374, 2020.
[4] Yoram Bachrach, Ychuda Finkelstein, Ran Baaad-Bachrach, Liran Katzir, Noam Koenigstein, Nir Nice, and UIrich Paquet. Speeding up the xbox recommender system using a euclidean transformation for inner-product spaces. In Proceedings of the 8th ACM Conference on Recommender Systems, RecSys '14, page 257-264, New York, NY, USA, 2014, Association for Computing Machinery.
[5] Scbastian Borgeaud, Arthur Mensch, Jordan Hoffmann, Trevor Cai, Eliza Rutherford, Katic Millican, George Bm Van Den Driessche, Jean- Ban-taptstte Lespiau, Bogdan Damoc, Aidan Clark, Diego De Las Casas, Aurelia Guy, Jacob Menick, Roman Ring. Tom Hcnnigan, Saffron Huang. Loren Maggiore, Chris Jones, Albin Cassirer, Andy Brock, Michela Paganini, Geoffrey Irving, Oriol Vinyals, Simon Osindero, Karen Simonyan, Jack Rae, Erich Elsen, and Laurent Sifre. Improving language models by retrieving from trillions of tokens. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 2206 2240. PMLR, 17 23 Jul 2022.
[6] Thomas Dean, Mark A. Ruzon, Mark Segal, Jonathon Shlens, Sudheendra Vijaannaraiimhan, and Jay Yagnik. Fast, accurate detection 100,000 object classes on a single machine. In 2013 IEEE Conference on Computer Vision and Puttern Recognition, pages 18 1814-1821, 2013.
[7] Miao Fan, Jiacheng Guo, Shuai Zhu, Shuo Miao, Mingming Sun, and Ping Li. Mobius: Towards the next generation of query-ad matching in baidu's sponsored search. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 11,, page 2509-2517, New York, NY, USA, 2019. Association for Computing Machinery.
[8] Ruiqi Guo, Philip Sun, Frik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. Accelcrating large-scale inference with anisotropic vector quantization. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 3887-3896. PMLR, 13-18 Jul 2020.
[9] Herve Jégou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEER Transactions on Pattern Analysis and Machine Intelligence, 33(1):1 (:3(1):117112)) 17-128, 2011.
[10] Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. Dense passage retrieval for open-domain question answering. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 6769-6786 Online, November 2020. Association for Computational Linguisties.
[11] Herwig Lejsek, Björn Pór Jónsson, and Laurent Amsaleg. Nv-tree:
Nearest neighbors at the billion scale. In Proceedings of the 1st ACM International Conference Multimedia Retrieval, ICMR '11, New York, NY, USA, 2011. Association for Computing Machinery.
[12] Ting Liu, Andrew Moore, Ke Yang, and Alexander Gray. An investigation of practical approximate nearest neighbor algorithms. In L. Saul, Y. Weiss, and L. Bottou, editors, Advances in Neural Information Processing Systems, volume 17. MIT Press, 2004.
[13] Yu A. Malkov and D. A. Yashunin. Efficient and robust approximate nearest neighbor search using hicrarchical navigable small world graphs. IEEE Trans. Pattern Anal. Mach. Intell., 42(4):824-836, apr 2020.
[14] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. Learning transferable visual models from natural language supervision. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine I Learning Research, pages 9768. PMLR, 18-24 Jul 2021.
[15] Anshumali Shrivastava and Ping Li. Asymmetric Ish (alsh) for sublinear time maximum inner product search (mips). In Z. Ghahramani, M. Welling, C. Cortes. N. Lawrence, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
11

---

[16] Harsha Vardhan Simhadri, George Williams, Martin Aumüller, Mathhij Douze, Artem Babenko, Dmitry Baranchuk, Qi Chen, Lucas Hosseini, Ravishankar Krishnaswamny, Gopal Srinivasa. Suhas Jayaram Subramanya, Jingdong Wang. Results of the neurips'? 21 challenge billion-scale approximate nearest neighbor search. In Douwe Kiela, Marco Ciccone, and Barbara Caputo, editors, Proceedings of the NeurlPS 2021 Competitions and Demonstrations Track, volume 176 of Proceedings of Machine Learning Research, pages 177-189. PMLR, 06 14 Dec 2022.
[17] Yuhuai Wu, Markus N. Rabe, DeLesley Hutchins, and Christian Szegedy, Memorizing transformers, 2022.
12

---

A
Appendix
A.1 Proof of Theorem 3.1
We may expand our expectation as follows:
(1 (g.r)
(a, m22
[(r', 22 = Eyee
w
(Irl |rll -191111//
= Lo w(cos Byee (
(g.r) ||||| |lal|
(g.r) |||||
cos dP
< cos 0
||ql|
To evaluate this integral, first decompose g and into components parallel and orthogonal to r: let us call these components Q1, ry, and r' respectively. This allows us to simplify the inner expectation:
(g,r) |r|
E
(g.
cos
E ('g,')² ||aall| = cos 0
||l||
Ener (on + qu, vi + r11) )² || = cos 0
[((1))1)) + (aa (el r1) ? || || = cos 0
EgER
E (cos
rril + (rp r1 ) |l = cos 0]
cos² 0
0/|r//
cos o |r (Blg ||ln|| cos 0), r'_)
+ Blal ) ||ln || cos
cos² 0
2
sin? 0 11 /(d 1).
Meanwhile, dP (g.r)
< cos 0
proportional to the surface area of (d -)-dimensional
||||| ||
hypersphere of radius sin 0, which we may express as d-n for some constant A. Our integral then becomes
C(r', .r Q) = L'" w(cos coo' 0|rrl]" + sin? anl 112 (d- - 1) A Asind=2 Ad0
A / wrcos 0) 2- a cos? 0) |ill"
=
A / w(cos 0) sin 0) || 112 /(d 1).
Now define Ia A 5 w:cos 0) sin 8: note that L(r rr Q) (Ja-2 (Ta-2-ta)| + /1
For the weight function w(() = > we find that La has recursive definition if we utilize integration by parts with cos and cos 8 sin d-1 0:
13

---

La = A /
1oos 0 sin 0d0
T/2
2A
cos Osin 4 0d0
Isin 0 7/2
coA
2A !
1x) cos 0
- (- 1) cos 0sin 0 - -ssinn cos 0) do
-A(d - 1) [o cos d-n 0d0
1/2
22A /mr cos sin 0d0
/=/2
/'/
1/2
2AA(d - 1)
cos - sin 0)0 sin d-2 0d0 Ala
= (d- 111--1112--6 1)ld Ala-
Combining terms, have (ALa (d 2) this implies for our loss that
Q) = (Ia-2 - Ia) |ril|" + Iallr1111/(() ((d-)
d
d -1-1 1 -1) Ta |' 112 + Tallr' 112/(d - 1)
Ia
(A 1)/11///il + +111 11
d d-1 1
Ia
[X]/ril] + +1M11²)
d-1
x |ril |1rr"1
Note that ri proj, r', this our desired result. This is very similar the analysis behind Theorem 3.3 of (8.
A.2
KMR curve comparison: further details
The Glove- 1M dataset came from unn-benchmarks.com Microsoft Turing-ANNS datasets came from beggaammbeenchaars..comm
while the Microsoft SPACEV and 3
Glove 1M was trained on an anisotropic loss with 2000 partitions, and SOAR was run with 1.
The two billion-datapoin datasets were trained anisotropic loss with approximately 7.2 million partitions, and SOAR was run with = 1.5.
Table 2 below presents the approximate number of datapoints needed to search in order achieve various recall targets on these datasets, as well as SOAR's 's KMR gain over non-spilled VQ indices.
14

---

Recall Target (R @ 100)
Spilling, No SOAR
KMR gain, SOAR
Dataset
No Spilling
SOAR
over No Spilling
80%
19983
21126
18352
1.09x
85%
32639
34109
29369
1.11x
Glove-IM IM
90%
59063
61392
52292
1.13x
95%
127819
135612
112488
1.14x
80%
2850
2700
2450
1.16x
Microsoft SPACEV
85%
5550
4650
3700
1.50x
90%
14350
10850
6950
2.06x
95%
69050
47050
20550
3.36x
80%
4500
3950
3400
1.32x
Microsoft Turing-ANNS 90%
85%
9350
7250
5600
1.67x
26700
17800
11150
2.39x
95%
145900
82100
33800
4.32x
Table KMR curve results in tabulated form; see Figure for graphs of this data.
A.3 ann-benchmarks. com Glove- 1M benchmark details
The hann-bechhmarks. com benchmark results came from VQ-PQ index; the VQ index had 2000 partitions and used SOAR À 1. Both VQ and PQ were trained with anisotropic loss. The PQ quantization was configured with subspaces and bitrate representation of the datapoints was encoded in 32-bit floats. By the analysis from Section 3.5 we would therefore expect SOAR to increase index size by 1/17 5.9%, which is quite close the empirical measurement in Table [
dimensions per subspace, and the highest-
A.4
End-to-end recall-speed benchmarks: further details
A.4.1 General index setup
The big-ann- ann--bencmmarss com results used a multilayer VQ index; the lower VQ index had approximately 7.2 million partitions, and these partition centers were vector-quantized again to 40000 partitions. PQ-quantized forms of the VQ residuals were used intermediate scoring stages. The highest-bitrate form of the dataset stored by the index was an INT8-quantized representation. All VQ. PQ, and INT8 quantizations were trained with anisotropic loss.
A.4.2 Estimated cost of SOAR benchmark hardware
The SOAR benchmark results came from running server using 32 vCPU (16 physical cores) on an Intel Cascade Lake generation processor with 150GB of memory. The Supermicro (SSS5510-MM configured with:
x Intel Xcon Silver 4314 Processor 16-Core 2.40 GHz 24MB Cache (135W)
32GB DDR4 3200MHZ ECC RDIMM Server Memory (2Rx8 16Gb)
1 ITB 3.5" MG04ACA 7200 RPM SATA3 6Gb/s 128M Cache 512N Hard Drive
should provide an upper bound for the cost of the SOAR benchmark setup, because the Supermicro server as configured has a newer generation and higher-clocked processor, and more memory, than the actual virtualized hardware used in benchmarking SOAR. At the time of writing, such a Supermicro server costs $2740.60. Combining this with the big-ann can--enchmarde com results gives us the following table, used to produce the plots in Figure 12a
15

---

MS-SPACEV
MS- MS-Turing
Queries/Sec (90% @ 10,
Queries/Sec
Algorithm
Hardware Cost
(90% @ 10,
from here)
from here)
FAISS Baseline
$22021.99 1.90
3265
2845
DiskANN
$11742
6503
17201
Gemini
$55726.66
16422
21780
CUANNS-IVFPQ
$150000
108302
109745
CuANNS- Mullii
$150000
839749
584293
OptANNe GraphANN
$14664.20
157828
161463
Ours
$2740.60
46712
32608
A.4.3 Cloud cost details
The monthly cloud infrastructure costs derived from Google Compute Engine's on-demand pricing in the us- centrallllll 1 region. At the time writing, the costs were [
Item vCPU
Monthly Cost (USD)
$24.81
1GB Memory
$3.33
IGB Local SSD
$0.08
A100 80GB
$2868.90
V100 16GB
$1267.28
Using this information, we computed the monthly cloud spend required for each of the entries to Track of the big-aun-benchmarke competition:
Algorithm
vCPU
RAM (GB)
Other
Total Monthly Cost (USD)
FAISS Baseline
32
768
Ix V100 16GB
$4617.57
DisKANN
72
64
3276.8GE SSD
$2261.18
CUANNS-IVFPO
256
2048
1x A100 80GE
$16036.46
CuANNS-Mult 256
2048
8x A100 80GB
$361 18.76
Two submissions from the original big- ann-benchmarke competition could not included in this comparison: Intel's OptANNe GraphANN submission, and GSI Technology's Gemini submission. The former relied on Intel Optane storage technology. which has been discontinued (2) and therefore isn't available any mainstream cloud compute provider, and can't be priced. The latter leverages proprietary hardware not available to cloud providers. However, both of these entries are present in the throughput-per-capee ranking featured earlier.
Our own results came from 32 vCPU, 150GB machine, which would cost $1293.09 per month. achieved 32608 QPS Microsoft Maring-ANNY and 467 12 QPS on Microsoft SPACEV, leading to the numbers presented in Figure These results are also reproduced in tabular form below.
MS-SPACEV Queries/Sec (90% R @ 10,
MS-Turing Queries/Sec (90% R 10,
MS-SPACEV Throughput / Cost
MS-Turing Throughput Cost
Algorithm
from here)
from here)
FAISS Baseline
3265
0.707
2845
0.616
DiskANN
6503
2.876
17201
7.607
JUANNS-IVFPO
108302
6.753
109745
6,843
CuANNS-
839749
23.25
584293
16.18
Ours
46712
36.12
32608
25.22
The benchmarked machine had eight GPUs, but only used, only account for GPU's cost.
16


Reviews:
[{"review_id": "ARkBibxS0H", "reviewer": "Reviewer_J7HP", "summary": "The paper revists the \"vector quantization\" technique for nearest neighbor search. In the VQ technique, points are represented by their closest centroid in a partition schema, typically based on k-means. Answering a query consists of finding the nearest centroids to the query and enumerating points represented by each centroid in the nearest centroid list.\n\nGiven that the nearest neighbor of a query need not be in the centroid closest to the query, one typicall has to explore a few centroids to find the right answer. In this paper, the authors study alternate schemes to reduce the number of centroids to explore.\n\nTheir contention is that centroids should be designed to minimize <q,r> where r is the residual x-C(x), of x, the nearest neighbor of q and its centroid C(x). They further focus on cos \\theta, where \\theta is the angle between q and r. Apart from the first eucliden residual minimizing partition scheme, the authors design a second cos \\theta minimizing partition scheme.\n\ncollectively the intention is to reduce the depth of exploration.\n\nThe results are constrasted with existing techniques FAISS and DiskANN and on benchmark datasets.", "questions": "1. Can you please provide more details of the index and query algorithms\n\n2. Can you please provide more details about how your arrived at plot 10b and what care was taken to prepare baselines.\n\n3. How does this idea compare this idea with ScaNN which optimizes for angular metrics too, on large datasets.\n\n4. What is the performance on other (non-Glove)datasets on ann-benchmarks.com\n\n5. Can your ideas also be applied to product quantization (in each chunk) and improve PQ's error (normalized for total bytes)?", "limitations": "na", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "A clear explanation of the techniques involved and visualization of why alternate spill over schemes dont work.\n\nEmpirical measurements indicated the rank of target vectors is improved by new design (Fig. 5.1)\n\nExperiments comparing to ann-benchmarks and also cost-normalized metric on big-ann-benchmark. Strong results overall.", "weaknesses": "The index design  5.4 is unclear. line 276-278 need a bit more explanation -- what is the exact index and query path design.\n\nThe results in Fig 10b needs more explanation and information to be verifiable. There is no plot of QPS alone. Nor a report of the parameters used for baselines for others to judge if they are the best config. For DiskANN, I suspect the IO/s of a GCP local SSD (680K for 3.2TB ssd: https://cloud.google.com/compute/docs/disks/local-ssd) is not enough for 72 cores. Performance might saturate below what 72 cores issuing queries might need (in which case DiskANN must be priced in table A.3 with fewer cores). ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. To answer your questions point-by-point:\n1. We’ve added Figure 2 in the rebuttal PDF to better describe the implementation details and space complexity. Also see Section 3.5 and Appendix A.3 for details. We also plan on adding algorithm blocks to the appendix to more fully describe our indexing and query-time changes. At a high level, though, the indexing change is simply using our new loss to pick a second centroid assignment for each datapoint, and the only querying change is deduplicating results. We also already provide indexing source code, and plan on upstreaming our changes to ScaNN.\n1. To summarize our response to your concerns about Figure 10b, our baseline points of comparison were taken directly from the official big-ann-benchmarks site, so they (including their configs) are exactly explained and verified by the official procedure. To provide some more detail:\n   * The QPS numbers were taken directly from [here](https://github.com/harsha-simhadri/big-ann-benchmarks/blob/8a2947a3c1dca5c9f41bac4cde71a001698e44cc/neurips21/t3/LEADERBOARDS_PUBLIC.md#msspace-throughput-rankings) and [here](https://github.com/harsha-simhadri/big-ann-benchmarks/blob/8a2947a3c1dca5c9f41bac4cde71a001698e44cc/neurips21/t3/LEADERBOARDS_PUBLIC.md#msturing-throughput-rankings). Table 1 in the rebuttal includes a copy of that data so that our throughput/cost ratio calculations can be more easily verified.\n   * Regarding DiskANN performance: we took hardware details directly from the big-ann-benchmarks submission, and the DiskANN submission chose to use a setup with 2x18=36 physical cores (=72vCPU); see [here](https://github.com/harsha-simhadri/big-ann-benchmarks/blob/f146969aab6e524b7a5a11900d9eaa91c9c412d3/t3/diskann-bare-metal/README.md). Given that the submission author is a lead DiskANN contributor, we assume this hardware selection was an intelligent choice that caters to the strengths of the algorithm. Had less CPU power been sufficient, they could’ve submitted with less CPU and achieved better rankings on the power and cost leaderboards.\n1. We see our work as an extension of ScaNN (we continue to use the anisotropic vector quantization technique introduced by ScaNN, and add SOAR on top), and have comparisons to vanilla ScaNN as a baseline. ScaNN without SOAR is shown in Figure 10a and a no-SOAR comparison is also present in Figure 10b.\n1. With the scarce amount of extra space given in the rebuttal, we’ve decided to demonstrate performance on Yandex Text-to-Image rather than an ann-benchmarks dataset. This was because the Yandex dataset is more novel (unnormalized MIPS distance, not angular distance), and larger scale, where ANN research is most important (ann-benchmarks size datasets are easily solved with accelerators like TPUs at extremely high throughput and low cost). Furthermore, our supplementary materials include source code that allows anyone to easily perform explorations on additional ann-benchmarks datasets if they so wish.\n1. We do not believe this is applicable to PQ. In PQ, one can (for example) double the bitrate by halving the size of each chunk, or squaring the number of centers per chunk. In VQ, neither of the above works (there are no such things as chunks; squaring, for example, 1M VQ centers would lead to 1T centers, which is totally impractical because that’s far greater than the number of datapoints) so the spilling idea is needed."}, {"review_id": "4fcwOK1Qix", "reviewer": "Reviewer_ixrh", "summary": "The paper discusses how a data index is built for Approximate Nearest Neighbor Search (ANNS). However, existing methods train and compute redundant representations independently, leading to inefficiency and inaccuracy. The paper proposes a novel data indexing technique called SOAR for approximate nearest neighbor (ANN) search, which utilizes multiple redundant representations and an orthogonality-amplified residual loss, drastically improving the overall index quality, resulting in state-of-the-art ANN benchmark performance.", "questions": "1. Why use the L2 datasets to study the efficiency of MIPS methods? maybe more details on datasets are needed (How to use datasets? Which metric are datasets based on? )\n2. Include more results on different datasets which are based on inner product metrics (such as Yandex Text-to-Image) or explain the reasonability of existing datasets.\n3. Discuss the space cost of spilled VQ assignment with relative notations. \n4. Please add more details about the loss function. How to generalize the loss function if the spilled assignments are above 2 ? (mentioned on line 126: This idea can be extended to further (>2) assignments as well.)", "limitations": "Please refer to Paper Weakness.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper studies a very important and a very fundamental problem that finds a lot of applications in search tasks.\n2. This paper has a clear motivation, i.e., increasing search efficiency when <q,r> is high. This idea is technically sound. \n3. Many analyses and experiments have been conducted.", "weaknesses": "1. Both Preliminary and Method are based on the MIPS problem. However, the billion datasets of the experiment are not focused on the inner product completely (Microsoft SPACEV and Microsoft Turing-ANNS are L2 datasets).\n2. Results of recall-QPS curves on more datasets (such as Yandex Text-to-Image, whose metric is the inner product) are needed.\n3. Lack of discussion on the complexity of storage under spilled VQ assignment. Statistics in Tab. 1 are not detailed enough.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. W1/W2 + Q1/Q2 are all with regards to datasets chosen for experiments, so we will address this first.\n* Our initial paper involved experiments on four datasets, and we believe this is more than sufficient to prove our point. L2 and angular datasets are simply more common and widely benchmarked, with more points of comparison; we didn’t include Yandex Text-to-Image initially because it didn’t have results from the CuANNS-Multi algorithm, and we wanted to maximize our number of points of comparison.\n* We have now added Yandex Text-to-Image to our results as requested, and they’re shown on Figure 1 of the rebuttal. We achieve top performance there, too.\n\nW3/Q3: Figure 2 from the rebuttal should address your concerns about space complexity analysis. Also see Section 3.5 of the paper.\n\nQ4: Although we don’t have the space to explain in this rebuttal, the loss can be generalized by summing projective penalties to all previous assignments, when there’s more than two assignments. This generalizes the correlative penalty expounded in Section 3.4. This is generally not worth doing due to linearly increasing storage cost, compared to the diminishing returns in the positive effects of further assignments. >2 assignments is not used in any experiment."}, {"review_id": "1XQqmSH5gi", "reviewer": "Reviewer_LtdJ", "summary": "This paper introduces an innovative technique for constructing a vector index to perform approximate nearest neighbor search, building upon the foundations of vector quantization and redundancy through spill trees. The authors propose a novel loss function aimed at identifying k-alternate centroids in the vector quantization process, thereby minimizing the failure correlation between assignments to the original and alternate centroids. This reduction in correlation effectively decreases the likelihood of missing a nearest neighbor during the search phase. Notably, the authors substantiate their approach by showcasing improved recall@k scores on benchmark datasets, all achieved with minimal computational overhead.", "questions": "* It would be useful to know if only one alternate centroid is used for each data point or if multiple alternate centroids are employed. If multiple centroids are utilized, it would be informative to see the effect of increasing the number of alternate centroids on the recall performance.\n* In Figure 8, it would be beneficial if the authors provided a proper definition of \"distortion\" and explained why it matters. Additionally, offering more details on how to effectively choose the parameter λ would enhance the comprehension of the research findings.\n* Suggestion: Authors can highlight the fact that decreased correlation between r and r’ means probability of misses decreases exponentially as you add more and more redundancy, through some formal analysis?\n* Suggestion: The community would benefit from incorporating soar into common open-source tools like FAISS and ScaNN and increase it’s adoption", "limitations": "Yes the authors have adequately addressed limitations", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* The ideas introduced in the paper are about spilling and redudancy in cluster assignments which have been previous explored in different capacities in the past. But the paper gives meaningful improvements on this task of approximate nearest neighbor(ANN) search which is a critical real world application. \n* The authors' approach is characterized by its simplicity and ease of implementation, supported by a solid theoretical foundation. The motivation behind the proposed loss function is well articulated, emphasizing the necessity of reducing the correlation between <q,r> and <q,r'> while promoting orthogonality among the residuals.\n* The paper is well-written and effectively conveys its ideas, providing adequate background information for readers to comprehend the research context.\n* The recall@100 results achieved by the proposed method are notably strong, particularly on larger-scale datasets, underscoring its efficacy in handling real-world scenarios.\n* The benchmarks conducted demonstrate satisfactory throughput results, indicating that the approach imposes minimal memory and computation overhead. This attribute enhances the practical viability of the method for deployment in real-world applications.\n* The effectiveness of the proposed method scales well with increasing dataset sizes, as evidenced by the more pronounced improvements observed when dealing with larger datasets where the probability of failure in cluster assignments tends to rise.\n* The authors further enhance the credibility of their findings by providing a compelling correlation analysis, elucidating the reasons behind the success of their proposed method (referred to as SOAR).\n\nOverall, the paper presents a valuable contribution to the field, offering practical enhancements to approximate nearest neighbor search while maintaining simplicity in implementation. The results obtained through rigorous experimentation and analysis demonstrate the effectiveness and scalability of the proposed method.", "weaknesses": "* Section 3.5 lacks a lot of details and paper could heavily benefit from providing a more structured and detailed explanation of the final algorithm. For eg. clarifying whether the spilling is done hierarchically and addressing corresponding memory considerations.\n* The improvement over previous SOTA ScaNN is marginal, and it would be helpful to if authors could elaborate more on the trade-offs and benefits over ScaNN\n* The paper would also benefit from including more details in Section 4.1 about the comparison with spill trees and referencing relevant literature, making it more comprehensive and easier to read.\n* A formal theoretical analysis of the time and space complexity would be valuable, providing a deeper understanding of the computational requirements of the proposed algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. We’ll address the weaknesses and questions point-by-point:\n### Weaknesses\n1. We’ve added Figure 2 in the rebuttal PDF to better describe the implementation details and space complexity. We also plan on adding algorithm blocks to the appendix to more fully describe our indexing and query-time changes. At a high level, though, the indexing change is simply using our new loss to pick a second centroid assignment for each datapoint, and the only querying change is deduplicating results. We also already provide indexing source code, and plan on upstreaming our changes to ScaNN.\n1. We see SOAR as not an alternative to ScaNN, but rather an add-on. For example, we continue to use the anisotropic vector quantization introduced by ScaNN, but additionally add our SOAR-loss spilled assignment. The primary tradeoff, as described in Table 1, is memory consumption; in Glove, we use +7.7% (submitted version says +12.7%, but this was measured incorrectly) additional memory, but get better performance. On Glove, the gain is small, but it’s also a small dataset, and as explained in Section 5.3, SOAR increases in efficacy as dataset size grows. That’s in part why the SOAR/no-SOAR gain is so much larger in Figure 10b.\n1. We strived to include as much detail as possible while obeying the page limit; are there specific points in the comparison that you found confusing, or important characteristics of spill trees from literature that you felt should be included? While we likely won’t have the space to expand significantly upon this section, we could re-prioritize its exposition to focus on details you may believe to be more important.\n1. Addressed in #1.\n### Questions\n1. Just one alternate centroid is used. Due to the linearly increasing storage cost of further assignments, but the diminishing benefits in terms of search efficiency gain (as measured by KMR; further alternate centroids by definition will have greater $||r’||^2$ or greater correlation, and will naturally be inferior), we found one alternate centroid strikes the best tradeoff. Also see the end of our rebuttal for Reviewer ixrh.\n1. We implicitly define distortion in Figure 8’s caption: “Raising SOAR $\\lambda$ increases VQ distortion $E[‖r’‖^2]$.” This matters because the naive way of choosing a spilled assignment would be to minimize $||r’||^2$. As demonstrated in Theorem 3.1, our loss includes the $||r’||^2$ term, but also an additional “orthogonality” term, and Figure 8 makes it clear how $\\lambda$ adjusts the tradeoff between the two.\n   * To emphasize the $||r’||^2$ meaning, we’ve amended the third paragraph of Section 3.3 to now read: “This approach leads to some implementation intricacies, as discussed in Section 3.5, but for now we focus on problems concerning theory when the spilled assignment $\\pi′(x)$ is chosen so as to minimize $||r′||^2$.\n1. This would be a nice result, but we see it as a non-trivial and separate research endeavor, primarily because proving results regarding order statistics (which the top-k neighbors fundamentally boils down to) is difficult; even if $\\langle q,r\\rangle=0$ for a nearest neighbor, other non-nearest neighbors could have negative $\\langle q,r\\rangle$ that result in even higher approximate inner products, so the nearest neighbor may still be missed. The dependence of each vector on every other vector’s quantization residuals makes analysis challenging.\n1. We have already released a fair amount of source code in the supplementary materials that can reproduce our results and shed light on implementation. Our results in Figure 10a came from patching the ScaNN source code and we're quite confident we can integrate those patches into the library, too."}, {"review_id": "ABV8QkQSIN", "reviewer": "Reviewer_jSJp", "summary": "The paper proposes a neat variant of spill trees for approximate nearest neighbor search (ANN). The idea is to reduce correlation between the set of points retrieved from each of the partition elements in a spill tree (where the partitions elements overlap or \"spill over\") by adding a penalty term in the assignment function that involves the expectation of the angle between the query $q$ and the quantization residual $r$ (see Eq. (2)).\n\nThe idea is logical and the empirical results indicate state-of-the-art performance in large-scale benchmarks.", "questions": "detailed comments:\n\np. 2: \"top k' partition\": the use of the term partition to refer to the parts that make up the partitioned set is a bit problematic. I would prefer to use the term 'partition element' (or perhaps 'part' or 'cell') to distinguish the parts from the partition which includes them.\n\np. 4: is the axis label \"quantized score error $\\langle q,r \\rangle$\" (also mentioned in the heading of Sec. 3.2) a definition of a new term? if yes, it should be given in the main text", "limitations": "Yes, the authors have adequately addressed limitations.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "+ important problem\n+ clear and sound idea\n+ rigorous theory\n+ outstanding empirical results\n+ a pleasure to read", "weaknesses": "- the theoretical assumption underlying the derivation of the practical assignment formula (Thm. 3.1) assumes that the query distribution is uniform over a d-dimensional unit sphere, which is an unrealistic assumption -- however, the resulting method seems to perform well enough, so apparently the performance isn't sensitive to this", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. We’ll address the weaknesses and questions point-by-point:\n### Weakness\n* We agree, this assumption isn’t entirely accurate. However, we’ve found this assumption to still be very effective, because it’s somewhat of a worst-case; the hardest queries tend to be those far from any datapoint, which a uniform query distribution produces. Real queries tend to have some correlation with the dataset distribution, but targeting improvement on the most difficult queries evidently seems to improve general performance as well.\n### Questions\n* Just to make sure we understand this correctly, you are referring to distinguishing between the geometric concept of a partition (roughly, some sort of Voronoi cell), as opposed to the partitioned set of datapoints, and you prefer “partition” be used for the former idea? We can tweak that line to say “datapoints ***within*** the top k’ partitions” to emphasize the geometric nature of containment; would that help?\n* We will amend Section 3.1 to explicitly define quantized score error as $\\langle q,r\\rangle$ in the beginning of line 85; thanks for the suggestion."}]

Author rebuttal:
Thank you all for taking the time to review our work. The two most common points of contention and confusion among the reviews were with regards to our experiments and with implementation details (especially memory footprint). We believe we have addressed both in our rebuttal. Our added material for the rebuttal consists of three components:
* The first describes exactly how our points of comparison for Figure 10b of the experiment in Section 5.4 were computed.
* The second adds a new dataset, Yandex Text-to-Image, an unnormalized billion-vector MIPS dataset from big-ann-benchmarks.
* The third describes the memory layout for a SOAR-enabled index and the memory overhead incurred by SOAR.

We naturally plan on including the above figures in the final version of our paper, as well as additional expository text which, due to the rebuttal rules, we were unallowed to showcase here. Individual critiques are addressed per-review; please feel free to ask additional questions or clarifications.

Meta-review: Two reviewers recommend clear Accept (one strong accept) citing that the paper has a clear motivation, i.e., increasing search efficiency when the distance of the query to the residual of the closest centroid is high, and propose a novel solution. 

The ACs agree that the paper presents a novel approach and recommend acceptance. They however also agree with Reviewer J7HP who concerned about the main comparissons of the paper in Figure 10b. Fir the final version, the authors are strongly urged to:

* Clearly and extensively explain the experimental setup for 10b: a complete account (details can be in supplementary) on the experimental setup for all methods, including cost calculations and any new info from the discussions during rebuttal. 

* Cite more top results from big-ann-benchmarks, including top entries that might not publicly available. The ACs agree that such results should be in the table, with proper notation when there are differences in setup or where the numbers are sourced from (if models not publicly available).
Decision: Accept (poster)