AdANNS: A Framework for Adaptive Semantic Search
Authors: Aniket Rege
Aditya Kusupati
Sharan Ranjit S
Alan Fan
Qingqing Cao
Sham M. Kakade
Prateek Jain
Ali Farhadi
Venue: NeurIPS 2023 poster (2023)
Keywords: Semantic Search
Approximate Nearest Neighbor Search
Large-scale search
Representation Learning
TL;DR: We introduce AdANNS, a novel design frameworks for semantic search that uses matryoshka representation across different stages of ANNS to ensure significantly better accuracy-compute trade-off than the state-of-the-art baselines.

Abstract: Web-scale search systems learn an encoder to embed a given query which is then hooked into an approximate nearest neighbor search (ANNS) pipeline to retrieve similar data points. To accurately capture tail queries and data points, learned representations typically are _rigid, high-dimensional_ vectors that are generally used as-is in the entire ANNS pipeline and can lead to computationally expensive retrieval. In this paper, we argue that instead of rigid representations, different stages of ANNS can leverage _adaptive representations_ of varying capacities to achieve significantly better accuracy-compute trade-offs, i.e., stages of ANNS that can get away with more approximate computation should use a lower-capacity representation of the same data point. To this end, we introduce AdANNS, a novel ANNS design framework that explicitly leverages the flexibility of Matryoshka Representations. We demonstrate state-of-the-art accuracy-compute trade-offs using novel AdANNS-based key ANNS building blocks like search data structures (AdANNS-IVF) and quantization (AdANNS-OPQ). For example on ImageNet retrieval, AdANNS-IVF is up to $\mathbf{1.5}$% more accurate than the rigid representations-based IVF at the same compute budget; and matches accuracy while being up to $\mathbf{90}\times$ faster in _wall-clock time_. For Natural Questions, $32$-byte AdANNS-OPQ matches the accuracy of the $64$-byte OPQ baseline constructed using rigid representations -- _same accuracy at half the cost!_ We further show that the gains from AdANNS translate to modern-day composite ANNS indices that combine search structures and quantization. Finally, we demonstrate that AdANNS can enable inference-time adaptivity for compute-aware search on ANNS indices built non-adaptively on matryoshka representations. Code is open-sourced at https://github.com/RAIVNLab/AdANNS.

AdANNS: A Framework for Adaptive Semantic Search
Aniket Rege*1
Aditya Kusupati Sharan Ranjit S Alan Fan Qingqing Cao
Sham Kakade
Prateck Jain Ali Farhadì
'University of Washington, Gooole Research, 'Harvard University (kusupati, 0li]@cs. washington edu, praj eeejain@google.oo
Abstract
Web-scale search systems learn an encoder to embed a given query which is then hooked into an approximate nearest neighbor search (ANNS) pipeline to retrieve similar data points. To accurately capture tail queries and data points, learned representations typically are rigid, high-dimensional vectors that are generally used as-is the entire ANNS pipeline and can lead to computationally expensive retrieval. In this paper, argue that instead of rigid representations, different stages ANNS can leverage adaptive representations of varying capacities to achieve significantly better securacy-comphl trade-off's, i.c., stages of ANNS that can get away with more approximate computation should use a lower-capacity
representation of the same data point. To this end, we introduce AdANNS & a novel ANNS design framework that explicitly leverages the flexibility of Ma- tryoshka Representations 13.]. We demonstrate state-of-the-an accuracy-compute trade-offs using novel AdANNS-ban key ANNS building blocks like search data structures AdANNS-IVE and quantization (AdANNS-OPO) For exam- ple on ImageNet retrieval, AdANNS-IVF is up 1.5% more accurate than the rigid representations--assee accuracy while being up to 90x faster in wall-clock time. For Natural Questions, 32-byte AdANNS-OP constructed using rigid representations- - same accuracy at half the cost! We further show that the gains from AdANNS translate to modern-dar composite ANNS indices that combine search structures and quantization. Finally, we demonstrate that AdANNS on ANNS indices built non-adaptively on matryoshka representations. Code is open-sourced at https: //gi githh....... Cwo/RAIVNLab//// AdANNS.
IVF [48] the same compute budget; and matches
matches the accuracy of the 64-byte OPQ baseline [13]
enable riference-time adaptivity for compute-aware search
1 Introduction
Semantic search [24] on learned representations [40, 41, 50] is a major component in retrieval pipelines [4, 9]. In its simplest form, semantic search methods learn neural network to embed queries as well as large number (N) of data points a d-dimensional vector space. For a given query, the nearest (in embedding space) point is retrieved using either exact search using approximate nearest neighbor search (ANNS) [21] which is now indispensable for real-time large-scale retrieval.
Existing semantic search methods learn fixed rigid representations (RRs) which are used as is in all the stages of ANNS (data structures for data pruning and quantization for cheaper distance computation; see Section 2). That is, while ANNS indices allow a variety of parameters for searching the design space to optimize the accuracy-compute trade-off, the provided data dimensionality is typically assumed to be immutable parameter. To make it concrete, let consider inverted file index (IVF) [48], a popular web-scale ANNS technique [16]. IVF has two stages (Section 3) during inference: (a) cluster mapping: mapping the query to cluster of data points [36], and (b) linear
"qqual contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

70.5
Top-1 Accuracy (%)
Top-1 Accuracy (%)
46
-3% gain
70.0
-00 real-world speed-up up
44
2x cheaper
-15% gain
69.5
42
69.0
AdANNS-IVE
AdANNS-OPQ
Rigid-IVF
40
Rigid-OPQ
0.05
0.5
10
32
48
64
96
Search Latency/Query (ms)
Compute Budget (Bytes)
(a) Image retrieval ImageNet-IK.
(b) Passage retrieval on Natural Questions.
Figure 1: AdANNS helps design search data structures and quantization methods with better accuracy-compee trade-offs than the existing solutions. In particular, (a) AdANNS-IVE improves on standard IVF by up to 1.5% in accuracy while being 90 faster in deployment and (b) AdANNS-OPQ is as accurate as the baseline at half the cost! Rigid-IVE and Rigid-OPQ are standard techniques that are built on rigid representations (RRs) while AdANNS uses matryoshka representations (MRs) [31].
sear: distance computation w.r.t all points in the retrieved cluster find the nearest neighbor (NN). Standard IVF utilizes the same high-dimensional RR for both phases, which can be sub-optimal.
Why the sub-optimality? Imagine one needs to partition a dataset into k clusters for IVF and the dimensionality of the data is d IVF uses full d representation to partition into k clusters. However, suppose have alternate approach that somehow projects the data in d/2 dimensions and learns 2k clusters. Note that the storage and computation to find the nearest cluster remains the same in both cases, i.e., when we have & clusters of d dimensions or 2 clusters of d/2 dimensions. 2k clusters can provide significantly more refined partitioning, but the distances computed between queries and clusters could be significantly more inaccurate after projection to d/2 dimensions.
So, if we can find mechanism to obtain a d/ 2 2-dimensional representation of points that can accurately approximate the topology/distances of d-dimensional representation, then we can potentially build significantly better ANNS structure that utilizes different capacity representations for the cluster mapping and linear scan phases of IVF. But how do we find such adaptive representations? These desired adaptive representations should be cheap to obtain and still ensure distance preservation across dimensionality. Post-hoc dimensionality reduction techniques like SVD [14] and random projections [25] on high-dimensional RRs are potential candidates, but our experiments indicate that in practice they are highly inaccurate and do not preserve distances well enough (Figure 2).
Instead, we identify that the recently proposed Matryoshka Representations (MRs) [31] satisfy the specifications for adaptive representations. Matryoshka representations pack information in hierarchical nested manner, i.e., the first m-dimensions of the d-dimensional MR form an accurate low-dimensional representation while being aware of the information in the higher dimensions. This allows us to deploy MRs two major and novel ways as part of ANNS: (a) fow-dimensional representations for accuracy-compute optimal clustering and quantization, and (b) high-dimensional representations for precise re-ranking when feasible.
To this effort, we introduce AdANNS 2.2 a novel design framework for semantic search that uses matryoshka representation--base adaptive representations across different stages of ANNS to ensure significantly better accuracy-computt trade-off than the state-of-the-ar baselines.
Typical ANNS systems have two key components: (a) search data structure to store datapoints, (b) distance computation map a given query to points in the data structure. Through AdANNS, we address both these components and significantly improve their performance. In particular, we first propose AdANNS-IVF (Section 1. which tackles the first component of ANNS systems. AdANNS- IVF uses standard full-precision computations but uses adaptive representations for different IVF stages. On ImageNet 1-NN image retrieval (Figure la), AdANNS-IVF up to 1.5% more accurate for the compute budget and 90x cheaper in deployment for the same accuracy IVE.

---

We then propose AdANNS-OPQ (Section 4.2) which addresses the second component by using AdANNS-basct quantization (OPQ [13]) - here we use exhaustive search overall points. AdANNS- OPQ is as accurate as the baseline OPQ on RRs while being at least 2x faster on Natural Ques- tions [32] 1-NN passage retrieval (Figure lb). Finally, we combine the two techniques to obtain AdANNS-IVFOPQ (Section 4.3) which is more accurate while being much cheaper up to 8x than the traditional IVFOPQ [24] index. To demonstrate generality of our technique, we adapt AdANNS to DisKANN [22] which provides interesting accuracy-comper tradeoff;; see Table 1.
While MR already has multi gratti-grauaarrrra representations, careful integration with ANNS building blocks is critical to obtain a practical method and is our main contribution. In fact, Kusupati et al. [31] proposed a simple adaptive retrieval setup that uses amaller-dimensien trieval followed by precise re-ranking with higher- ligher-dimensional MR. Such techniques, unfortunately, cannot be scaled to industrial systems as they require forming new index for every shortlisting provided by low-dimensional MR. Ensuring that the method aligns well with the modern-day ANNS pipelines is important as they already have mechanisms to handle real-world constraints like load-balancing [16] and random access from disk [22]. So, A is step towards making the abstraction of adaptive search and retrieval feasible at the web-scale.
MR for shortlisting in re-
Through extensive experimentation, we also show that AdANNS generalizes across search data structures, distance approximations, modalities (text& & image), and encoders (CNNs & Transformers) while still translating the theoretical gains to latency reductions in deployment. While we have mainly focused on IVF and OPQ-based ANNS in this work, AdANNS also blends well with other ANNS pipelines. We also show that ADANNS can enable compute-awar aware elastic search on prebuilt indices without making any modifications (Section 5.1); note that this is in contrast to AdANNS-IV builds the index explicitly utilizing "adaptivity" in representations. Finally, we provide an extensive analysis on the alignment of matryoshka representation for better semantic search (Section 5.2).
that
We make the following key contributions:
We introduce AdANNS a novel framework for semantic search that leverages matryoshka representations for designing ANNS systems with better accuracy-compute trade-offs.
AdANNS powered search data structure (AdANNS-IVF) and quantization AAdANNS-PP show a significant improvement in accuracy-compute tradeoff compared to existing solutions.
ANANNS generalizes to modern-day composite ANNS indices and can also enable compute-aware elastic search during inference with no modifications.
2
Related Work
Approximate nearest neighbour search (ANNS) is a paradigm to come as close as possible [7] to retrieving the "true" nearest neighbor (NN) without the exorbitant search costs associated with exhaustive search [21,5]] The "approximate" nature comes from data pruning well as the cheaper distance computation that enable real-time web-scale search. In its naive form, NN-search has a complexity of OddN); ;; d is the data dimensionality used for distance computation and N is the size of the database. ANNS employs each of these approximations to reduce the linear dependence on the dimensionality (cheaper distance computation) and data points visited during search (data pruning).
Cheaper distance computation. From a bird's eye view, cheaper distance computation is always obtained through dimensionality reduction (quantization included). PCA and SVD [14, 26] can reduce dimensionality and preserve distances only to a limited extent without sacrificing accuracy. On the other hand, quantization- based techniques [6, 15] like (optimized) product quantization (())Q) [13, 23] have proved extremely crucial for relatively accurate yet cheap distance computation and simultancously reduce the memory overhead significantly. Another naive solution is to indepen- dently train the representation function with varying low-dimensional information bottlenecks [31] which is rarely used due to the costs of maintaining multiple models and databases.
Data pruning. Enabled by various data structures, data pruning reduces the number of data points visited as part of the search. This is often achieved through hashing [8, 46], trees [3, 12, 16, 48] and graphs [22, 38]. More recently there have been efforts towards end-to-end learning of the search data structures [17, 29, 30]. However, web-scale ANNS indices are often constructed on rigid d-dimensional real vectors using the aforementioned data structures that assist with the real-time search. For more comprehensive review of ANNS structures please refer to [5, 34, 51].
3

---

Composite indices. ANNS pipelines often benefit from the complementary nature of various building blocks [24, 42]. In practice, often the data structures (coarse-quanee suasseieuuaiierr like IVF [48] and HNSW [37] are combined with cheaper distance alternatives like PQ [23] (fie-quuatizer)) for massive speed-ups in web-scale search. While the data structures are built on d-dimennsiona real vectors, past works consistently show that PQ can be safely used for distance computation during search time. As evident in modern web-scale ANNS systems like DisKANN [22], the data structures are built on d-dimensional real vectors but work with PQ vectors (32 64-byte) for fast distance computations.
ANNS benchmark datasets. Despite the Herculean advances in representation learning [19, 42], ANNS progress is often only benchmarked on fixed representation vectors provided for about a dozen million to billion scale datasets [1, 47] with limited access to the raw data. This resulted in the improvement of algorithmic design for rigid representations (RRs) that are often not specifically designed for search. All the existing ANNS methods work with the assumption of using the provided d d-dimensional representation which might not be Pareto-optimal for the accuracy-comper off in the first place. Note that the lack of raw-image and text-based benchmarks led us to using ImageNet-IK [45] (1.3M images, 50K queries) and Natural Questions [32] (21M passages, 3.6K queries) for experimentation. While not billion-scale, the results observed on ImageNet often translate to real-world progress [28], and Natural Questions is one of the largest question answering datasets benchmarked for dense passage retrieval [27], making our results generalizable and widely applicable.
trade-
In this paper, we investigate the utility of adaptive representations embeddings of different dimen- sionalities having similar semantic information in improving the design of ANNS algorithms. This helps in transitioning out of restricted construction and inference on rigid representations for ANNS. To this end, we extensively use Matryoshka Representations (MRs) [31] which have desired adaptive properties in-built. To the best of our knowledge, this is the first work that improves accuracy-compun trade-off in ANNS by leveraging adaptive representations on different phases of construction and inference for ANNS data structures.
3 Problem Setup, Notation, and Preliminaries
The problem setup of approximate nearest neighbor search (ANNS) [21] consists of a database of N data points, [2x, .2,...,, N.. and query, q. where the goal is to "approximately" retrieve the nearest data point to the query. Both the database and query embedded to R using representation function o : X + often a neural network that can be Iearned through various representation learning paradigms [2, 19, 20, 42].
Matryoshka Representations (MRs). The d-dimensional representations from & can have a nested structure like Matryoshka Representations (MRs) [31] in-built - (M(()) Matryoshka Representation Learning (MRL) learns these nested representations with simple strategy of optimizing the same training objective at varying dimensionalities. These granularities are ordered such that the lowest representation size forms prefix for the higher-dimensional representations, So, high-dimensional MR inherently contains low-dimensional representations of varying granularities that can be accessed for free first m-dimensions (m E [d]) ie., & (R( m] from the d'dimensional MR form an m-dimensional representation which is as accurate as its independently trained rigid representation (RR) counterpart @RR(m)) Training an encoder with MRL does not involve any overhead or hyperparameter tuning and works seamlessly across modalities, training objectives, and architectures.
Inverted File Index (IVF). IVF [48] is an ANNS data structure used in web- search sys- tems [16] owing to its simplicity, minimal compute overhead, and high accuracy. IVF construction involves clustering (coarse quantization through k-means) [36] on d-dimensional representation that results in an inverted file list [S3] of all the data points in each cluster. During search, d-dimensional query representation is assigned to the most relevant cluster (C;; i E (k:) by finding the closest cen- troid (11)) using an appropriate distance metric (I.2 or cosine). This is followed by an exhaustive linear search across all data points in the cluster which gives the closest NN (see Figure 5 in Appendix A for IVF overview). Lastly, IVF can scale to web-scale by utilizing a hierarchical IVF structure within each cluster [16]. Table 2 in Appendix A describes the retrieval formula for multiple variants of IVF.
Optimized Product Quantization (OPQ). Product Quantization (PQ) [23] works by splitting a d- d-dimensional real vector into m sub-vectors and quantizing each sub-vector with an independent 2

---

length codebook across the database. After PQ, each d-dimensional vector can be represented by compact m x b bit vector; we make each vector m bytes long by fixing b 8. During search time, distance computation between the query vector and PQ database is extremely efficient with only m codebook lookups. The generality of PQ encompasses scalar/vector quantization [15, 36] as special cases. However, PQ can be further improved by rotating the d-dimensional space appropriately to maximize distance preservation after PQ. Optimized Product Quantization (OPQ) [13] achieves this by learning an orthonormal projection matrix R that rotates the d-dimensional space to be more amenable to PQ. OPQ shows consistent gains over PQ across a variety of ANNS tasks and has become the default choice in standard composite indices [22, 24].
Datasets. We evaluate the ANNS algorithms while changing the representations used for the search thus making it impossible to evaluate on the usual benchmarks [1]. Hence we experiment with two public datasets: (a) ImageNet- | [45] dataset on the task of image retrieval - where the goal is to retrieve images from a database (1.33 (1.3M image train set) belonging to the same class as the query image (50K image validation set) and (b) Natural Questions (NQ) [32] dataset on the task of question answering through dense passage retrieval where the goal is to retrieve the relevant passage from database (21M Wikipedia passages) for a query (3.6K questions).
Metries Performance of ANNS is often measured using recall score [22], k-recall @ N - recall of the exact NN across search complexities which denotes the recall of h: "true" NN when N data points are retrieved. However, the presence of labels allows us to compute 1-NN (top-1) accuracy. Top-1 accuracy is harder and more fine- grainer metric that correlates well with typical retrieval metrics like recall and mean average precision (mAP@ k). Even though we report top-1 accuracy by default during experimentation, we discuss other metrics in Appendix C. Finally, we measure the compute overhead of ANNS using MFL MFL.OPS/query and also provide wall-clock times (see Appendix B.
Encoders.
For ImageNet, we encode both the database and query set using a ResNet50 (σ1) [19] trained on ImageNet- I. For NQ, we encode both the passages in the database and the questions in the query set using a BERT-Base (Φx) [10] model fine-tuned on NQ for dense passage retrieval [27].
We use the trained ResNet50 models with varying representation sizes (d = [8, 16,... 2048); default being 2048) as suggested by Kusupati et al. [31] alongside the Net-ResNet50 models trained with MRL for the same dimensionalities. The RR and MR. models are trained to ensure the supervised one-vs-all classification accuracy across all data dimensionalities nearly the same I-NN accuracy of 2048-d RR and MR models are 71.19% and 70.97% respectively on ImageNet- K. Independently trained models, 91 RR(()) output d [8, 16...... ..... 2048] dimensional RRs while single ResNe500 model, 07
MR(4) outputs a d = 2048-dimensinn
MR that contains all the 9 granularities.
We also train BERT-Base models in similar vein as the aforementioned ResNet50 models. The key diffcrence is that we take a pre-trained BERT-Base model and fine-tune on NQ as suggested by Karpukhin al. [27] with varying (5) representation sizes (bottlenecks) (d [48, 96, ... 768);
default being 768) to obtain @N RR( that creates RRs for the NQ dataset. To get the MRL-BERT- Base model, we fine-tune a pre-trained BERT-Base encoder on the NQ train dataset using the MRL
objective with the same granularities as RRs to obtain <> ((M)(()) which contains all five granularities. Akin to ResNet50 models, the RR and MR BERT-Base models on NQ are built to have similar 1 I-NN accuracy for 768-d of 52.2% and 51.5% respectively. More implementation details can be found in Appendix B and additional experiment-specifie information is provided at the appropriate places.
4 AdANNS Adaptive ANNS
In this section, we present our proposed AdANNS framework that exploits the inherent flexibility of matryoshka representations improve the eecuracy-compure trade-off for semantic search com- ponents. Standard ANNS pipeline can be split into two key components: (a) search data structure that indexes and stores data points, (b) query-point computation method that outputs (approximate) distance between given query and data point. For example, standard IVFOPQ [24] method uses an IVF structure to index points on full-precision vectors and then relies on OPQ for more efficient distance computation between the query and the data points during the linear scan.
5

---

Below, we show that AdANNS can be applied to both the menteonen ANNS components and provides significant gains on the ceapuuation-accuraae tradeoff curve. particular, we present AdANNS-IVE which is AdANNS version of the standard IVF index structure [48], and the closely related ScaNN structure [16]. We also present AdANNS-ON which introduces representation adap- tivity in the OPQ, an industry-default quantization. Then, in Section 4.3 we further demonstrate the combination of the two techniques to get AdANNS-IVFOPO - an AdANNS version of IVFOPQ [24] and A DANNNSDDDSAN,,,,, similar variant of DisKANN [22]. Overall, our experiments show that AdANNS-IVT's significantly more accuracy-compute optimal compared to the IVF indices built on RRs and LLANNS-OPG is accurate the OPQ on RRs while being significantly cheaper.
4.1 AdANNS-IVF
Recall from Section that IVF has clustering and linear scan phase, where both phase use same dimen- sional rigid representation. Now, AdANNS-IVE allows the clustering phase use the first de dimensions of the given matryoshka represen- tation (MR). Similarly, the linear scan within each cluster uses d, di- mensions, where again d, represents top de coordinates from MR. Note that setting de d, results in non- adaptive regular IVF. Intuitively, we would set de < ds. so that instead of clustering with high-dimensional representation, we can approximate accurately with a low-dimensional em- bedding of size de followed by a lin- scan with higher d, dimmensioonal representation. Intuitively, this helps in the smooth search of design space for state-of-the-art accuracy cooupcc trade-off. Furthermore, this can provide a precise operating point accuracy-compute tradeoff curve which is critical in several practical settings.
70.0
Top-1 Accuracy (%)
AdANNS-IVE
69.5
AdANNS-IVF-D
MG-IVF-RR
69.0
X MG-IVF-SVD
IVF-MR
IVF-RR
68.5
x
0.1
0.5
5
MFLOPS/Query
Figure 2: I-NN accuracy on ImageNet retricval shows that AdANNS-IVE achieves near-optimal eccuracy-compue trade-off compared across various rigid and adaptive base- lines. Both adaptive variants of MR and RR significantly outperform their rigid counterparts (IVF-XX) while post-hoc compression RR using SVD for adaptivity falls short.
Our experiments on regular IVF with MRs and RRs (IVF-MR & IVF-RR) of varying dimensionali- ties and IVF configurations (# clusters, # probes) show that (Figure 2) matryoshka representations result in significantly better accuracy-compute trade-off. We further studied and found that learned lower-dimensional representations offer better accuracy-compute trade-offs for IVF than higher- dimensional embeddings (see Appendix E for more results).
AdANNS utilizes d-dimensional matryoshka representation to get accurate de and d, dimensional vectors at no extra compute cost. The resulting AdANNS-IVE provides a much better accuracy- compute tra (Figure 2) on ImageNet- IK retrieval compared IVF-MR, IVF-RR, and MG- IVF-RR muuli-granular IVF with rigid representations (akin to AdANNS without MR) a strong baseline that uses de and d, dimensional RRs.. Finally, we exhaustively search the design space of IVF by varying de, d, E [8, 16, ... 2048) and the number of clusters & E [8, 16, ..... 2048). Please see Appendix for more details. For IVF experiments on the NQ dataset, please refer to Appendix G.
Empirical results. Figure 2 shows that AdANNS-IVE outperforms the baselines across all accuracy-comput settings for ImageNet- retrieval. AdANNS-IVE results in 10x lower compute for the best accuracy of the extremely expensive MG-IVF-RR and non-adaptive IVF-MR. Specifi- cally, as shown in Figure 1a, AdANNS-IVE is up to 1.5% more accurate for the same compute and has up to x00x lesser FLOPS/query (90x real-world speed-up!) than the status quo ANNS on rigid representations (IVF-RR). We filter out points for the sake of presentation and encourage the reader to check out Figure 8 in Appendix for an expansive plot of all the configurations searched.
The advantage of AdANNS for construction of search structures is evident from the improvements in IVF AAAANNS-VVE and can be casily extended to other ANNS structures like ScaNN [16] and

---

AdANNS-IVFOPQ HNSW [38]. For example, HNSW consists of multiple layers with graphs of NSW graphs [37] of increasing complexity. AdANNS can be adopted to HNSW, where the construction each level can be powered by appropriate dimensionalities for an optimal accuracy-compute trade-off. In general, AdANNS provides fine- fine-grained control over compute overhead (storage, working memory, inference, and construction cost) during construction and inference while providing the best possible accuracy.
4.2 AdANNS-OPQ
Standard Product Quantization (PQ) essentially performs block-wise vector quantization via cluster- ing. For example, suppose we need 32-byte PQ compressed vectors from the given 2048 dimensional representations. Then, we can chunk the representations in m 32 equal blocks/sub-vectee
of 64-d each, and each sub-vector space is clustered into 2 = 256 partitions. That is, the representation of each point essentially cluster-id for each block. Optimized PQ (OPQ) [13] further refines this idea, by first rotating the representations using a learned orthogonal matrix, and then applying PQ on top of the rotated representations. In ANNS, OPQ used extensively to compress vectors and improves approximate distance computation primarily due to significantly lower memory overhead than storing full-precision data points IVF.
AdANNS-OPQ utilizes MR representations to apply OPQ on lower-dimensional representations. That is, for given quantization budget, ANANNS allows using top d, << dimensions from MR and then computing clusters with d, /m-dimensional blocks where m is the number of blocks. Depending on d, and m, we have further flexibility of trading-off dimensionality/ccaactty for increasing the number of clusters to meet the given quantization budget. AdANNS S-QQ tries multiple d., m, and number of clusters for fixed quantization budget obtain the best performing configuration.
We experimented with 8 - 128 byte OPQ budgets for both ImageNet and Natural Questions retrieval with an exhaustive search on the quantized vectors. We compare AdANNS-OPO which uses MRs of varying granularities to the baseline OPQ built on the highest dimensional RRs. We also evaluate OPQ vectors obtained projection using SVD [14] on top of the highest-dimensional RRs.
Empirical results. Figures and lb show that AdANNS-OPQ significantly outperforms up to 4% accuracy gain the baselines (OPQ on RRs) across compute budgets on both ImageNet and NQ. In particular, AdANNS- OPQ tends match the accuracy of a 64-byte (a typical choice ANNS) OPQ baseline with only a 32-byte budget. This results in 2 reduction in both storage and compute FLOPS which translates to significant gains in real-world web-scale deployment (see Appendix D).
We only report the best AdANNS-OPQ for each budget typically obtained through a much lower- dimensional MR (128& & 192; much faster to build well) than the highest-dimensional MR (2048 & 768) for ImageNet and NQ respectively (see Appendix G for more details). At the same time, we
71
70
Top-1 Accuracy (%)
Top-1 Accuracy (%)
69
70
68
69
67
66
68
AdANNS-OPQ OPQ-RR OPQ-RR-SVD
65
Rigid-IVFOPQ
67
X
16
32
64
8
16
32
64
Compute Budget (Bytes)
Compute Budget (Bytes)
Figure 3: AdANNS-OPQ matches the accuracy of 64-byte OPQ on RR using only 32-bytes for ImageNet retrieval. AdANNS provides large gains at lower compute budgets and saturates to baseline performance for larger budgets.
Figure 4: Combining the gains of AdANNS for IVF and OPQ leads to better IVFOPQ compos- ite indices. On ImageNet retrieval, AdANNS- IVFOPQ is 8x cheaper for the same accuracy and provides 1 - 4% gains over IVFOPQ on RRs.
7

---

note that building compressed OPQ vectors on projected RRs using SVD to the smaller dimensions (or using low-dimensional RRs, see Appendix D) as the optimal AdANNS-ON OPQ does not help in improving the accuracy. The significant gains we observe in AdA information packing in MRs we hypothesize that packing the most important information in the initial coordinates results in a better PQ quantization than RRs where the information is uniformly distributed across all the dimensions [31, 49J. See Appendix D for more details and experiments.
are purely due to better
4.3
AdANNS for Composite Indices
We now extend AdANNS composite indices [24] which put together two main ANNS building blocks search structures and quantization together to obtain efficient web-scale ANNS indices used practice. A simple instantiation of composite index would be the combination of IVF and -PQ-IV where the clustering in IVF happens with full-precision real vectors but the linear sean within each cluster approximated using -oo-compesse variants of the representation since often the full-precision vectors of the database cannot fit in RAM. Contemporary ANNS indices like DiskANN [22] make this default choice where they build the search graph with a full-precision vector and approximate the distance computations during search with OPQ-compressed vector to obtain a very small shortlist of retrieved datapoints. In DisKANN, the shortlist of data points is then re-ranked to form the final list using their full-precision vectors fetched from the disk. AdANNS is naturally suited to this shortlist-rrrank framework: we use a low-d MR for forming index, where we could tune AdANNS parameters according to the accuracy-comput trade-off of the graph and OPQ vectors. We then use a high-d MR for re-ranking.
Empirical results. Figure shows that AdANNS-IVFOPQ is 4% better than the baseline at all the PQ compute budgets. Furthermore, AdANNS-IVFOPQ has the same ac- curacy the baselines at 8x lower overhead. With DiskANN, AdANNS accelerates shortlist generation by us- ing low dineeninnio representations and recoups the accuracy by re- ranking with the highest-dimensional MR at negligible cost. Table shows that AdANNS-DiskANN is more accurate than the baseline for both I-NN and ranking performance at only hal the cost. Using low-dimensional representations further speeds up inference in AdANNS-DisKANN (see Appendix F).
Table I: AdANNS-DisKANN using 16-d MR + re-ranking with the 2048-d MR outperforms DiskANN built on 2048-d RR half the compute cost ImageNet retrieval.
RR-2048
AdANNS
PQ Budget (Bytes)
32
16
Top-1 Accuracy (%)
70.37
70.56
mAP@ 10 (%)
62.46
64.70
Precision 440 (%)
65.65
68.25
These results show the generality of AdANNS and its broad applicability across a variety of ANNS indices built top of the base building blocks. Currently, AdANNS piggybacks typical ANNS pipelines for their inherent accounting of the real-world system constraints [16, 22, 25J. However, believe that AdANNS's s flexibility and significantly better accuracy-compute trade-off can be further informed by real-world deployment constraints. We leave this high-potential line of work that requires extensive study future research.
Further Analysis and Discussion
5.1 Compute-aware Elastic Search During Inference
AdANNS search structures cater to many specific large-scale use scenarios that need to satisfy precise resource constraints during construction as well as inference. However, in many cases, construction and storage of the indices are not the bottlenecks or the user is unable to search the design space. In these settings, AdANNS-D enables adaptive inference through accurate yet cheaper distance computation using the low-dimensional prefix of matryoshka representation. Akin to composite indices (Section 4.3) that use PQ vectors for cheaper distance computation, we can use the low- dimensional MR for faster distance computation on ANNS structure built non-adaptively with high-dimensional MR without any modifications to the existing index.
Empirical results. Figure shows that for given compute budget using IVF on ImageNet- K retrieval, AdANNS-IVFis is better than AdANNS-IVFD due to the explicit control during the building
8

---

of the ANNS structure which is expected. However, the interesting observation is that AdANNS-D matches or outperforms the IVF indices built with MRs of varying capacities for ImageNet retrieval.
However, these methods are applicable in specific scenarios of deployment. Obtaining optimal AdANNS search structure (highly accurate) or even the best IVF-MR index relies relatively expensive design search but delivers indices that fit the storage, memory, compute, and accuracy constraints all at once. On the other hand AdANNS-D does not require a precisely built ANNS index but can enable compute-aware search during inference. AdANNS-D is great choice for setups that can afford only one single database/index but need to cater to varying deployment constraints, e.g.. one task requires 70% accuracy while another task has a compute budget of MFLOPS/query.
5.2 Why MRs over RRs?
Quite few of the gains from AdANNS are owing the quality and capabilities of matryoshka representations. So, we conducted extensive analysis to understand why matryoshka representations seem to be more aligned for semantic search than the status-quo rigid representations.
Difficulty of NN search. Relative contrast (C,) [18] is inversely proportional to the difficulty of nearest neighbor search on given database. On ImageNet- IK, Figure 14 shows that MRs have better C, than RRs across dimensionalities, further supporting that matryoshka representations are more aligned (easier) for NN search than existing rigid representations for the same accuracy. More details and analysis about this experiment can be found in Appendix H.2.
Clustering distributions. We also investigate the potential deviation in clustering distributions for MRs across dimensionalities compared to RRs. Unlike the RRs where the information is uniformly diffused across dimensions [49], MRs have hierarchical information packing. Figure 11 in Appendix E.3 shows that matryoshka representations result in clusters similar (measured by total variation distance [33]) to that of rigid representations and do not result in any unusual artifacts.
Robustness. Figure 9 in Appendix shows that MRs continue to be better than RRs even for out- of-distribution (OOD) image queries (ImageNetV2 [44]) using ANNS. It also shows that the highest data dimensionality need not always be the most robust which is further supported by the higher recall using lower dimensions. Further details about this experiment can be found in Appendix E.
Generality across encoders. IVF-MR consistently has higher accuracy than IVF-RR across dimen- sionalities despite having similar accuracies with exact NN search (for ResNet50 on ImageNet and BERT-Bas on NQ). We find that our observations on better alignment of MRs for NN search hold across neural network architectures, ResNetl 8/34/101 delves deep into the experimentation done using various neural architectures on ImageNet-IK.
Re34ec18/34/101 [19] and ConvNeXt-Tiny [35]. Appendix H.3
Recall score analysis. Analysis of recall score (see Appendix C) in Appendix H. shows that for similar top-1 accuracy, lower-dimensional representations have better 1-Recall @ across search complexities for IVF and HNSW on ImageNet- IK. Across the board, MRs have higher recall scores and top-1 accuracy pointing to easier "searchability" and thus suitability of matryoshka representations for ANNS. Larger-scale experiments and further analysis can be found in Appendix H.
Through these analyses, we argue that matryoshka representations better suited for semantic search than rigid representations, thus making them an ideal choice for AdANNS.
5.3 Search for AdANNS Hyperparameters
Choosing the optimal hyperparameters for AdANNS, such de da, m, # clusters, # probes, is an interesting and open problem that requires more rigorous examination. As the ANNS index is formed once and used for potentially billions of queries with massive implications for cost, latency and queries- sneries-per-secee per-second, a hyperparameter search for the best index is generally an acceptable industry practice [22, 38]. The Faiss library [24] provides guidelines" to choose the appropriate index for specific problem, including memory constraints, database size, and the need for exact results. There have been efforts at automating the search for optimal indexing parameters, such as Autofaiss which maximizes recall given compute constraints.
ines- to- choose- an- index

---

In case of AdANNS, we suggest starting at the best configurations of MRs followed by a local design space search to lead to near-optimal AdANNS configurations (e.g. use IVF-MR bootstrap AdANNS-IVF). We also share some observations during the course of our experiments:
1. AdANNS-IVF: Top-1 accuracy generally improves (with diminishing returns after point) with increasing dimensionality of clustering (d.)) and search (dz), as we show on ImageNet variants and with multiple encoders in the Appendix (Figures 9 and 15). Clustering with low-d MRs matches the performance of high-d MRs as they likely contain similar amounts of useful information, making the increased compute cost not worth the marginal gains. Increasing # probes naturally boosts performance (Appendix, Figure 10a). Lastly, it is generally accepted that a good starting point for the clusters k is v N2/ where No is the number of indexable items [39]. A = vND is the optimal choice of k from a FLOPS computation perspective can be seen in Appendix B.
2. AdANNS-OPQ: we observe that for fixed compute budget in bytes (m), the top-1 accuracy reaches a peak at d < dmaz (Appendix, Table 4). We hypothesize that the better performance of AdANNS-OPQ at d < dmax is due to the curse of dimensionality, i.c. it is casier to learn PQ codebooks on smaller embeddings with similar amounts of information. We find that using an MR with d = 4 is good starting point on ImageNet and NQ. We also suggest using an 8-bit (256-length) codebook for OPQ as the default for each of the sub-block quantizer.
3. AdANNS-DisKANN: Our observations with DisKANN are consistent with other indexing struc- tures, i.e. the optimal graph construction dimensionality d < dmmes (Appendix, Figure 12). A carefull study of DiskANN on different datasets is required for more general guidelines to choose graph construction and OPQ dimensionality d.
5.4 Limitations
AdANNS's core focus is to improve the design of the existing ANNS pipelines. To use AdANNS on a corpus, we need to back-fill [43] the MRs of the data - a significant yet a one-time overhead. We also notice that high-dimensional MRs start to degrade in performance when optimizing also for an extremely oow-dimensional granularity (c.g.. < 24-d for NQ) otherwise is it quite easy to have comparable accuracies with both RRs and MRs. Lastly, the existing dense representations can only in theory be converted to MRs with an stlo-el non-linear transformation. We believe most of these limitations form excellent future work improve AdANNS further.
Conclusions
We proposed a novel framework, AdANNS 3. that leverages adaptive representations for different phases of ANNS pipelines to improve the accuracy-compe compute tradeoff. AdANNS utilizes the inherent flexibility of matryoshka representations [31] to design better ANNS building blocks than the standard ones which use the rigid representation in each phase. AdANNS achieves SOTA accuracy-compute trade-off for the two main ANNS building blocks: search data structures (AdANNS-IVF) and quantization (AP). The combination of AdANNS- based building blocks leads to the construction of better real-world composite ANNS indices with as much as 8x reduction in cost at the same accuracy as strong baselines while also enabling compute-aware elastic search. Finally, we note that combining AdANNS with elastic encoders [[]] enables truly adaptive large-scale retrieval.
Acknowledgments
We are grateful to Kaifeng Chen, Venkata Sailesh Sanampudi, Sanjiv Kumar, Harsha Vardhan Simhadri, Gantavya Bhatt, Matthijs Douze and Matthew Wallingford for helpful discussions and feedback. Aditya Kusupati also thanks Tom Duerig and Rahul Sukthankar for their support. Part of the paper's large-scale experimentation is supported through research GCP credit award from Google Cloud and Google Research. Sham Kakade acknowledges funding from the ONR award N00014-22-1-225 1-23377 and NSF award CCF-2212841. Ali Farhadi acknowledges funding from the NSF awards IIS 1652052, IIS 17303166, DARPA N66001-19-2-4033 DARPA W91 15-1-543,, and gifts from Allen Institute for Artificial Intelligence and Google.
10

---

References
[1] M. Aumüller, E. Bernhardsson, and A. Faithfull. Ann-benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems, 87:101374, 2020.
[2] Y. Bengio. Deep learning of representations for unsupervised and transfer learning. In Proceed- ings of ICML workshop on wnsupervised and transfer learning, pages 17-36. JMLR Workshop and Conference Proceedings, 2012.
[3] E. Bernhardsson. Annoy: Approximate Nearest Neighbors in C++/Python, 2018. URL hrtppiiirggprojcct/aaaoo httpppo//onnoyyy/e/// Python package version 1.13.0.
https://pypi.co org
[4] S. Brin and L.. Page. The anatomy of large-scale hypertextual web search engine. Computer networks and ISDN systems, 30(1-7):107-117, 1998.
[5] D. Cai. A revisit of hashing algorithms for approximate nearest neighbor search. IEEE Transactions on Knowledge and Data Engineering, 33(6):2337-2348, 2021. doi: 10.1 109/ TKKDE.201..295388
[6] T. Chen, L. Li, and Y. Sun. Differentiable product quantization for end-to-end embedding compression. In International Conference on Machine Learning, pages 1617-1626. PMLR, 2020.
[7] K. L. Clarkson. An algorithm for approximate closest-point queries. In Proceedings of the tenth annual symposium on Computational geometry, pages 160-164, 1994.
[8] M. Datar, N. Immorlica, P. Indyk, and V. S. Mirrokni. Locality-sensitive hashing scheme based p-stable distributions. In Proceedings of the twentieth annual symposium on Computational geometry, pages 253-262, 2004.
[9] J. Dean. Challenges in building large-scale information retrieval systems. In Keynote of the 2nd ACM International Conference on Web Search and Data Mining (WSDM), volume 10, 2009.
[10] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint 1rXiv:1810004805 2018.
[11] Devvrit S. Kudugunta, A. Kusupati, T. Dettmers, K. Chen, I. Dhillon, Y. Tsvetkov, H. Hannaneh, Kakade, A. Farhadi, and P. Jain. Matformer: Nested transformer for elastic inference. arXiv preprint arxiv:2310.07700 2023.
[12] H. Friedman, L.. Bentley, and R. A. Finkel. algorithm for finding best matches in logarithmic expected time. ACM Transactions on Mathematical Software (TOMS), 3(3):209- 226, 1977.
[13] т. Ge, K. He, Q. Ke, and J. Sun. Optimized product quantization for approximate nearest neighbor search. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages
2013.
[14] G. Golub and W. Kahan. Calculating the singular values and pseudo-inverse of matrix. Journal of the Society for Industrial and Applied Mathematics, Series B: Numerical Analysis, 2(2): 205-224, 1965.
[15] R. Gray. Vector quantization. IEEE Assp Magazine, 1(2):4-99, 1984.
[16] R. Guo, P. Sun, E. Lindgren, Q. Geng, D. Simcha, F. Chern, and S. Kumar. Accelerating large-scale inference with anisotropic vector quantization. In International Conference on Machine Learning, pages 3887-3896. PMLR, 2020.
[17] N. Gupta, H. Chen, H.-F Yu, C.-J. Hsich, and S. Dhillon. End-to-end learning to index and search in large output spaces. arXiv preprint 2rX0v:2210008410, 2022.
[18] He, S. Kumar, and S.FF. Chang. On the difficulty of nearest neighbor search. International Conference Machine Learning (ICML), 2012.

---

[19] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-
778, 2016.
[20] K. He, H. Fan, Y. Wu, S. Xie, and R. Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 7729-9738 2020.
[21] P. Indyk and R. Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 604 613, 1998.
[22] S. Jayaram Subramanya, F. Devvrit, H. V. Simhadri, R. Krishnawamy, and R. Kadekodi. Diskann: Fast accurate billion-point nearest neighbor search on a single node. Advances in Neural Information Processing Systems, 32, 2019.
[23] H. Jegou, M. Douze, and C. Schmid. Product quantization for nearest neighbor search. JEEE Iransactions on pattern analysis and machine intelligence, 33(1): 2010.
[24] J. Johnson, M. Douze, and H. Jégou. Billion-scale similarity search with GPUs. IEEE Transactions on Big Data, 7(3):535 1-7335557,222 547,,57,211 2019.
[25] W. B. Johnson. Extensions of lipschitz mappings into a hilbert space. Contemp. Math., 26: 189-206, 1984.
[26] I. T. Jolliffe and J. Cadima. Principal component analysis: review and recent developments. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 374(2065)200100200 2016.
[27] V. Karpukhin, B. Oğuz, S. Min, P. Lewis, L. Wu, S. Edunov, D. Chen, and W.-t. Yih. Dense passage retrieval for open-domain question answering. arXiv preprint arXiv:2004. 04906, 2020.
[28] Kornblith, Shlens, and Q. V. Le. Do better imagenet models transfer better? In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pages 2661-2677 2019.
[29] Kraska, A. Beutel, E. H. Chi, J. Dean, and N. Polyzotis. The case for learned index structures. In Proceedings of the 2018 international conference on management of data, pages 489-504, 2018.
[30] A. Kusupati, M. Wallingford, V. Ramanujan, R. Somani, S. Park. K. Pillutla, P. Jain, S. Kakade, and A. Farhadi. Llc: Accurate, multi-purpose learnt low-dimensional binary codes. Advances in Neural Information Processing Systems, 14:23900-23911 2021.
[31] A. Kusupati, G. Bhatt, A. Rege, M. Wallingford, A. Sinha, V. Ramanujan, W. Hooardd-nnyder K. Chen, S. Kakade, P. Jain, and A. Farhadi. Matryoshka representation learning. In Advances in Neural Information Processing Systems, December 2022.
[32] T. Kwiatkowski, J. Palomaki, O. Redfield, M. Collins, A. Parikh, C. Alberti, D. Epstein, I. Polosukhin, J. Devlin, K. Lee, et al. Natural questions: a benchmark for question answering research. Transactions of the Association for Computational Linguistics, 7:453-466, 2019.
[33] D. Levin and Y. Peres. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017.
[34] W. Li, Y. Zhang, Y. Sun, W. Wang, W. Zhang, and X. Lin. Approximate nearest neighbor search on high dimensional data experiments, analyses, and improvement. IEEE Transactions Knowledge and Data Engineering, 2020.
[35] Z. Liu, H. Mao, C.-Y. Wu, C. Feichtenhofer, Darrell, and S. Xie. convnet for the 2020s. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 11976-11986, 2022.
[36] Lloyd. Least squares quantization in pem. IEEE transactions on information theory, 28(2): 129-137, 1982.
12

---

[37] Y. Malkov, A. Ponomarenko, A. Logvinov, and V. Krylov. Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems, 45:61-68, 2014.
[38] Y. A. Malkov and D. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis & Machine Intelligence, 42(04))824 836, 2020.
[39] K. Mardia, J. Kent, and Bibby. Multivariate analysis. Probability and Mathematical Statistics, 1979.
[40] Nayak. Understanding searches better than ever before. Google AI Blog, 2019. URL https:
/ wologggooglo pacpllepproouccc products/ serouucts/serrch./ -harccheeecheeeeeaa -aahhhhannngeeeeee www.ggg-ddnderttnnnnnnnn bert/.
[41] A. Neelakantan, T. Xu, R. Puri, A. Radford, J. M. Han, J. Tworek, Q. Yuan, N. Tezak, J. W. Kim, C. Hallacy, et al. Text and code embeddings by contrastive pre-training. arXiv preprint arXiv:2201. 10005, 2022.
[42] A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, G. Goh, S. Agarwal, G. Sastry, A. Askell, Mishkin, J. Clark, et al. Learning transferable visual models from natural language supervision. In International Conference on Machine Learning, pages
PMLR, 2021.
[43] V. Ramanujan, K. A. Vasu, A. Farhadi, O. Tuzel, and H. Pouransari. Forward compatible training for representation learning. arXiv preprint 1xXiv:21/2.02000 2021.
[44] B. Recht, R. Roelofs, L. Schmidt, and V. Shankar. Do imagenet classifiers generalize to imagenet? In International Conference on Machine Learning, pages 5389-54000 PMLR, 2019.
[45] O. Russakovsky, J. Deng, H. Su, Krause, S. Satheesh, Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, et al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115(3):211-222, 2015.
[46] R. Salakhutdinov and G. Hinton. Semantic hashing. International Journal of Approximate Reasoning, 50(7))969-973 2009.
[47] H. V. Simhadri, G. Williams, M. Aumüller, M. Douze, A. Babenko, D. Baranchuk, Q. Chen, L. Hosseini, R. Krishnaswamy, G. Srinivasa, et al. Results of the neurips 21 challenge on billion-scale approximate nearest neighbor search. arXiv preprint urXiv:2205.03763. 2022.
[48] Sivic and A. Zisserman. Video google: text retrieval approach object matching in videos. In Computer Vision, IEEE International Conference on, volume 3, pages 1470-1470. IEEE Computer Society, 2003.
[49] D. Soudry, E. Hoffer, M. S. Nacson, S. Gunasekar, and N. Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1):2822-2878 2018.
[50] C. Waldburger. As search needs evolve, microsoft makes ai tools for better search available to researchers and developers. Microsoft Al Blog, 2019. URL htttss//blogg. mww.oooff..ooomoo vector http:////bing-vettoooooo seachr-
com/ai/bing
[51] M. Wang, X. Xu, Q. Yue, and Y. Wang. A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search. Proceedings of the VLDB Endowment, 14 1114:1964-1978. 2021.
[52] R. Weber, H.-J Schek, and S. Blott. A quantitative analysis and performance study for similarity- search methods in high-dimensional spaces. In VLDB, volume 98, pages 195-205, 1998.
[53] I. H. Witten, I. H. Witten, A. Moffat, T. C. Bell, T. C. Bell, E. Fox, and T. C. Bell. Managing gigabytes: compressing and indexing documents and images. Morgan Kaufmann, 1999.
13

---

A AdANNS Framework
Algorithm 1 AdANNS-IVE Psuedocode
Index database to construct clusters and build inverted file system
def adamsSonsttruttin (database, d_cluster, num clusters)
# Slice database with cluster construction dim (d_cluster) xb database [dd cluster] cluster_centroiin constructClusters((b) num_clusters)
return cluster_centroidd
def adann (qurries,,,, centroids, d_shortlist, d_search, num_probes,
k):
Slice queries and centroids with cluster shortlist dim (d_shortlist)
xq queries [:d_ shsrrtitiss]]]]
xc centroids [:d_shortistt]]
for in queries:
compute distance of query from each cluster centroid aodiidate_isttance compateDistancess@g xc) sort cluster candidates by distance and choose small number to probe
cluster cluster_candidaee candidates sortAscendinggcandidtttt (isattteedstttnssss [:num_probes database candidates getClusterMembers (cluster candidates) (
Linear Scan all shortlisted clusters with search dim (d_search) k hnearett_neighbot [q] linearScan(q, database
aatabase_candidates, candidates, d_search,
k)
return s_nearest_neighbors
ANNS
ANNS Inference
Construction
Φ: Rd
Database
Query
Construct Clusters with Rd.
Select Closest Cluster
H1 X
H4 X C,
Mk X E Ck
Linear Scan with R
Top Relevant Data Points
Figure 5: The schematic of inverted file index (IVF) outlaying the construction and inference phases. Adaptive representations can be utilized effectively in the decoupled components of clustering and searching for better accuracy-compute trade-off (AdANNS-IVF).
14

---

Table 2: Mathematical formulae of the retrieval phase across various methods built on IVF. See Section 3 for notations.
Method
Retrieval Formula during Infereace
IVF-RR
arg JeCum (()))))))))
(ary)) s.t. A(g) arg min, (())))(()) ))
IVF-MR
arg geing
(()))(((a))
(ay)) st. A(g) arg min,
(a) -MA
MR(
AdANNS-IVE
arg Jechal
(() ( (1rl)..... A(g) arg min,
(cMBRc))(s)) -Mh (
MG-IVF-RR
arg min Crin (( (e)
(aRM))(a))) A(g) argmin, (oMR)4)((0) (
AdANNS-IVF-D
arg aignin
10 (0)1 df
(a)6)0 st. stt. h(g) arg mngg (|0 d. 2. dil
IVFOPQ
min sec () - (1x))) sa. h(g) mig, (10(()) -aal
B
Training and Compute Costs
A bulk of our ANNS experimentation was written with Faiss [24], library for efficient similarity search and clustering. AdANNS was implemented from seratch (Algorithm 1) due to difficulty in decoupling clustering and linear scan with Faiss, with code available https://gg thub. , com/ RAIVELab/ AdANNS. We also provide a version of AdANNS with Faiss optimizations with the restriction that D. 2 D3 limitation of the current implementation, which can be further optimized. All ANNS experiments (AdANNS- IVFOPQ) were run on an Intel Xeon 2.20GHz CPU with 12 cores. Exact Search (Flat L2. PQ, OPQ) and DiskANN experiments were run with CUDA 11.0 on a A A100-SXXM SXM4 NVIDIA GPU with 40G RAM. The wall-clock inference times quoted in Figure la and Table are reported on CPU with Faiss optimizations, and are averaged over three inference runs for ImageNet-I K retrieval.
MG-IVF-RE IVF-MR, IVF-RR. HNSW, HNSWOPQ.
Table 3: Comparison of AdANNS-IVE and Rigid-IVF wall-clock inference times for ImageNet- IK retrieval. AdANNS-IVE has up to 1.5% gain over Rigid-IVF for a fixed search latency per query.
AdANNS-IVE
Rigid-IVF
Top-1 1
Search Latency/Query (ms)
Top-1
Search Lateney/Query (ms)
70.02
0.03
68.51
0.02
70.08
0.06
68.54
0.05
70.19
0.06
68.74
0.08
70.36
0.88
69.20
0,86
70.60
5.57
70.13
5.67
DPR [27] on NQ [32]. We follow the setup on the DPR repo": the Wikipedia corpus has 21 million passages and Natural Questions dataset for open-domain QA settings. The training set contains 79,168 question and answer pairs, the dev set has 8,757 pairs and the test set has 3,610 pairs.
B.1 Inference Compute Cost
We evaluate inference compute costs for IVF in MegaFLOPS per query (MFLOPS/query) as shown in Figures 2, 10a, and 8 as follows:
C d,k + RodaND
k
where d, is the cluster construction embedding dimensionality, de the embedding dim used for linear scan within each probed cluster, which is controlled by # of search probes np. Finally, k the number of clusters |C,| indexed over database of size Np. The default setting in this work, unless otherwise stated, is np 1, k = 1024, ND = 1281167 (ImageNet- 1K trainset). Vanilla IVF supports only d, = da while AdANNS-IVE provides flexibility via decoupling clustering and search (Section 4). AdANNS-IVT-D is a special case of AdANNS-IVE with the flexibility restricted to inference, i.e., de a fixed high-dimensional MR.
15

---

C Evaluation Metrics
In this work, we primarily use top-1 accuracy (i.e. 1-Nearest Neighbor), recall@k, corrected mean average precision (mAP@k) [30] and k-Recall @N (recall score), which are defined over all queries Q over indexed database of size ND as:
Eq correct_
top-1
[Q]
Eq correct correct_pred@k
num classes
Recall @k @k
Q
NDo
where porrect_preddie is the number of k-NN with correctly predicted labels for given query. As noted Section 3, K is the overlap between exact search nearest neighbors (considered as ground truth) and the top N retrieved documents. As Faiss [24] supports maximum of 2048- NN while searching the indexed database, we report 40-Recall 2048 in Figure 13. Also note that for ImageNet- I. which constitutes a bulk of the experimentation in this work, |Q] 50000, [ND] = 1281167 and num classes = 1000. For ImageNetv2 [44], |Q| = 10000 and num classes 1000, and for ImageNet-44 [31], Q 210100, | 4202000 and num _laasses 4202. For 3610 and NDl = 21015324. As NQ consists of question-anae answer pairs (instance- level), num_
NQ [32]. [Q] =
num_classes classes 3610 for the test set.
70
Top-1 Accuracy (%)
Top-1 Accuracy (%)
68
66
AdANNS-OPO
66
AdANNS-IVF+OPQ
OPQ-MR-2048
IVF+OPQ-MR-2048
64
Rigid-OPQ
Rigid-IVF+OPQ
64
8
16
32
64
16
32
64
Compute Budget (Bytes)
Compute Budget (Bytes)
(a) Exact Search OPQ ImageNet-IKK
(b) IVF + OPQ on ImageNet-IK
70
Top-1 Accuracy (%)
70.6
Top-1 Accuracy (%)
68
70.2
66
69.8
AdANNS-DIsKANN-OOR DiSKANN+OPQ DisKANN-OPO-MR--DAA
AGANNS-HNSW--PO
64
HNSW-OPG-MR-2048
69.4
Digd
Rigld-HNSW+OPQ
8
16
32
64
16
64
Compute Budget (Bytes)
Compute Budget (Bytes)
(c) DiskANN OPQ on ImageNet-IK
(d) HNSW + OPQ ImageNet- IK
Figure 6: Top-1 Accuracy of AdANNS composite indices with OPQ distance computation compared to MR and Rigid baselines models on ImageNet- IK and Natural Questions.
16

---

D AdANNS-OPQ
In this section, take deeper dive into the quantization characteristics of MR. In this work, restrict our focus to optimized product quantization (OPQ) [13], which adds a learned space rotation and dimensionality permutation to PQ's sub-vector quantization learn more optimal PQ codes. We compare OPQ to vanilla PQ on ImageNet in Table 4, and observe large gains at larger embedding dimensionalities, which agrees with the findings of Jayaram Subramanya al. [22].
We perform a study of composite OPQ m x indices on ImageNet- I K across compression compute budgets m (where b 8, i... 1 Byte), i.c. Exact Search with OPQ, IVF+OPQ. HNSW+OPQ. and DiskANN+OPO. as seen in Figure 6. is evident from these results:
1. Learning OPQ codebooks with AdANNS (Figure 6a) provides a 1-5% gain in top-1 accuracy over rigid representations low compute budgets (s 32 Bytes). AdANNS-OP saturates to Rigid-OPQ performance at low compression (2 64 Bytes).
For IVE, learning clusters with MRs instead of RRs (Figure 6b) provides substantial gains (1- 4%). In contrast to Exact-OPQ, using AdANNS for learning OPQ codebooks does not provide substantial top-1 accuracy gains over MR with equal MR-2048 at all compute budgets. This further supports that IVF performance generally scales with embedding dimensionality, which is consistent with our findings on ImageNet across robustness variants and encoders (See Figures 9 and 15 respectively).
2048 (highest), though it still slightly better
3. Note that in contrast to Exact, IVF, and HNSW coarse quantizers, DiskANN inherently re-ranks the retrieved shortlist with tigh-precision embeddings (d 2048), which reflected in its high top-1 accuracy. We find that AdANNS with 8-byte OPQ (Figure 6c) matches the top-1 accuracy of rigid representations using 32-byte OPQ, for a 4x cost reduction for the same accuracy. Also note that using AdANNS provides large gains over using MR-2048 at high compression (1.5%), highlighting the necessity of AdANNS's flexibility for high precisseciioon retrieval low compute budgets.
Our findings on the HNSW-OPQ composite index (Figure 6d) are consistent with all other indices, i.c. HNSW graphs constructed with AdANNS OPQ codebooks provide significant gains over R. and MR, especially at high compression (5 32 Bytes).
OPQ on NQ dataset
40
45
Top-1 Accuracy (%)
Top-1 Accuracy (%)
40
35
30
30
25
25
AdANNS-OPQ
AdANNS-IVF+OPQ
20
OPQ-MR-768
IVF+OPQ-MR-768
Rigid-OPQ
15
Rigid-IVF+OPQ
16
32
48
64
96
8
16
32
48
64
96
Compute Budget (Bytes)
Compute Budget (Bytes)
(a) Exact Search OPQ Natural Questions
(b) IVF + OPQ Natural Questions
Figure 7: Top-1 Accuracy of AdANNS composite indices with OPQ distance computation compared MR and Rigid baselines models on Natural Questions.
Our observations on ImageNet with ResNet-50 MR across search structures also extend to the Natural Questions dataset with Dense Passage Retriever (DPR with GERT-Bass MR embeddings). We note that AdANNS provides gains over R.-7768 embeddings for both Exact Search and IVF with OPQ (Figure 7a and 7b). We find that similar to ImageNet (Figure 15) IVF performance on Natural Questions generally scales with dimensionality. AdANNS thus reduces to MR-768 performance for M 2 16. See Appendix for a more in-depth discussion of AdANNS with DPR on Natural Questions.
17

---

Table Comparison of PQ-MR with OPQ-MR for exact search on ImageNet- across embedding dimensionality d E {8, 16.... )048) quantized to m E {8. 16, 32, 64) bytes. OPQ shows large gains over vanilla PQ at larger embedding dimensionalities 128. Entries with the highest top-1 accuracy for a given (d, m) tuple are bolded.
Config
PQ
OPQ
m
Top-1
mAP@ 10
P@ 100
Top-1
mAP@ 10
P@ 100
8
62.18
56.71
61.23
62.22
56.70
61.23
67.91
62.85
67.21
67.88
62.96
67.21
16
16
67.85
62.95
67.21
67.96
62.94
67.21
68.80
63.62
67,86
68.91
63.63
67.86
32
16
69.57
64.22
68.12
69.47
64.20
68.12
32
69.44
64.20
68.12
69.47
64.23
68.12
68.39
63.40
67.47
68.38
63,42
67.60
16
69.77
64.43
68.25
69.95
64.55
68.38
64
32
70.13
64.67
68.38
70.05
64.65
68.38
64
70.
64.69
68.42
70.18
64.70
68.38
67.27
61.99
65.78
68.40
63.11
67.34
16
69.51
64.32
68.12
69.78
64.56
68.38
128
70.27
64.72
68.51
70.60
64.97
68.51
64
70.61
64.93
68.49
70.65
64.98
68.51
66.06
60.44
64.09
67.90
62.69
66.95
16
68.56
63.33
66.95
69.92
64.71
68.51
256
32
70.08
64.83
68.38
70.59
65.15
68.64
64
70.48
64.98
68.55
70.69
65.09
68.64
65.09
59.03
62.53
67.51
62.12
66.56
16
67.68
62.11
65.39
69.67
64.53
68.38
512
32
69.51
64.01
67.34
70.44
65.11
68.64
70.53
65.02
68.52
70.72
65.17
68.64
64.58
58.26
61.75
67.26
62.07
66.56
16
66.84
61.07
64.09
69.34
64.23
68.12
1024
68.71
62.92
66.04
70.43
65.03
68.64
64
69.88
64.35
67.68
70.81
65.19
68.64
62.19
56.11
59.80
66.89
61.69
66.30
16
65.99
60.27
63.18
69.25
64.09
67.99
2048
67.99
62.04
64.74
70.39
64.97
68.51
64
69.20
63.46
66.40
70.57
65.15
68.51
E AdANNS-IVE
Inverted file index (IVF) [48] a simple yet powerful ANNS data structure used in web-scale search systems [16]. IVF construction involves clustering (coarse quantization often through k-means) [36] on d-dimensional representation that results in an inverted file list [53] all data points each cluster. During search, the d-dimensional query representation is first assigned to the closest clusters (# probes, typically set to 1) and then an exhaustive linear scan happens within each cluster to obtain the nearest neighbors. As seen in Figure 9, IVF top-1 accuracy scales logarithmically with increasing representation dimensionality d on ImageNet- K The learned low-d representations thus provide better accuracy-compe case for usage of AdANNS with IVE.
trade-ofT's compared to high-d representations, thus furthering the
Our proposed adaptive variant of IVE, AdANNS-IVE, decouples the clustering, with de dimensions, and the linear sean within each cluster, with d, dimensions - setting d, = d, results in non- adaptive vanilla IVF. This helps in the smooth search of design space for the optimal accuracy- compute trade-off. naive instantiation yet strong baseline would be to use explicitly trained de and de dimensional rigid representations (called MG-IVF-RR, for multi-granular IVF with
18

---

71
70
Top-1 Accuracy (%)
69
68
AdANNS-IVF
67
AdANNS-IVF-D
MG-IVE-RR
66
MG-IVF-SI SVD
IVF-MR
65
IVF-RR
64
0.1
1
10
100
MFLOPS/Query
Figure 8: Top-1 accuracy vs. compute cost per query AdANNS-IVE compared to IVF-MR, IVF-RR and MG-IVF-RR baselines on ImageNet-IK.
rigid representations). We also examine the setting of adaptively choosing low-dimensional MR to linear the shortlisted clusters built with high-dimensional MR, i.e. AdANNS-IVF-D, as seen Table 5. As seen in Figure 8, AdANNS-IVE provides pareto-optimal accuracy-compute tradeoff across inference compute. This figure is more exhaustive indication of AdANNS-IVE behavior compared to baselines than Figures la and 2. AdANNS-IVF is evaluated for all possible tuples of de, da, k |C' {8, 16,... ..... 2048). AdANNS-IVE-D is evaluated for pre-built IVF index with de 2048 and d, E (8...., 2048]. MG-IVF-RR configurations are evaluated for de E {8...., J. d, E {32,.... 2048) and k 1024 clusters. study over additional i values is omitted due to high compute cost. Finally, IVF-MR and IVF-RR configurations are evaluated for de d {8, 16, ..... 2048) and &o E (256, .... 8192). Note that for a fair comparison, we use Πp = 1 across all configurations. We discuss the inference compute for these settings in Appendix B.1.
E.1 Robustness
Top-1 Acmragge
Top- AccumMEEN
S:
IVF MR
IVE MRR IVF-RR
IVF RR
88
9
47
2066
Ruprosentation
Size
(a) ImageNet- IK
(b) ImageNetV2
(c) ImageNet-4K
Figure 9: Top-1 Accuracy variation of IVF-MR of ImageNet IK, ImageNetV2 and ImageNet-4K.
RR baselines are omitted on ImageNet-4K due to high compute cost.
As shown in Figure 9, we examined the clustering capabilities MRs both in-distribution (ID) queries via ImageNet- IK and out-of-distribution (OOD) queries via ImageNetV2 [44], as well as on larger-scale ImageNet-4K [] For ID queries on ImageNet- 1K (Figure 9a), IVF-MR
least as accurate as Exact-RR for < 256 with a single search probe, demonstrating the quality of in- distribution low-d clustering with MR. On OOD queries (Figure 9b), we observe that IVF-MR is on average 2% more robust than IVF-RR across all cluster construction and linear scan dimensionalities It also notable that clustering with MRs followed by linear sean with probes = 1 more robust than exact search with RR embeddings across all d < 2048, indicating the adaptability of MRs to distribution shifts during inference. As seen in Table 5, on ImageNetV2 A the best configuration for d < 16, and is similarly accurate to IVF-MR at all other d. AdANNS-IVF-D with
19

---

Table 5: Top-1 Accuracy of AdANNS-IVF-D on out-of-distribution queries from ImageNetV2 compared to both IVF and Exact Search with MR and RR embeddings. Note that for AdANNS- IVF-D, the dimensionality used to build clusters de 2048.
d
AdANNS-IVF-D
IVF-MR
Exact-MR
IVF-RR
Exact-RR
8
53,51
50.44
50.41
49.03
48.79
16
57.32
56.35
56.64
55.04
55.08
32
57.32
57.64
57.96
56.06
56.69
64
57.85
58.01
58.94
56.84
57.37
128
58.02
58.09
59.13
56.14
57.17
256
58.01
58.33
59.18
55.60
57.09
512
58.03
57.84
59.40
55,46
57.12
1024
57.66
57.58
59.11
54.80
57.53
2048
58.04
58.04
59.63
56.17
57.84
d = 128 is able to match its own accuracy with d = 2048, 16x compute gain during inference.
This demonstrates the potential of AdANNS to adaptively search pre-indexed clustering structures.
On 4-million scale ImageNet-4K (Figure 9c), we observe similar accuracy trends of IVF-MR compared Exact-MR in ImageNet-IK (Figure 9a) and ImageNet (Figure 9b). We omit baseline IVF-RR and Exact-RR experiments due to high compute cost at larger scale.
E.2
IVF-MR Ablations
100.0
30
87.5
85.0
25
1-Recall@NN
Top-1 (%)
82.5
80.0
1-Recilig!
IVF 1-Probe
87.5
1-RecaligZ
15
IVF 4-Probe
IVF 2-Probe
85.0
1-eecaligS
1-Recalli4
IVF P.Pbo
82.5
1eecalig20
10
16
256
812
1024
2048
MFLOPS/Query
Representation Size
(a) 4K Search Probes (r4p)
(b) Centroid Recall
Figure 10: Ablations on IVF-MR Clustering: Analysis of accuracy-compute tradeoff with in- creasing IVFMMR search probes n on ImageNet-4K compared to Exact-MR and b) k-Recall N on ImageNet-I 1 K cluster centroids across representation sizes d. Cluster centroids retrieved with highest embedding dim d 2048 were considered ground-truth -ruth centroids.
As seen in Figure 10a, IVF-MR can match the accuracy of Exact Search on ImageNet-4K with x00x less compute. We also explored the capability of MRs at retrieving cluster centroids with low-d compared to ground truth of 2048-d with k-Recall @N, seen in Figure 10b. MRs were able saturate pear-perfect 1-Recall @N for 2 32 and N 2 4, indicating the potential of AdANNS at matching exact search performance with less than 10 search probes nlp-
E.3 Clustering Distribution
We examined the distribution of learnt clusters across embedding dimensionalities d for both MR and RR models, as seen in Figure 11. We observe IVF-MR to have less variance than IVF-RR at d E {8, 16), and slightly higher variance for 2 32, while IVF-MR outperforms IVF-RR in top- across all d (Figure 9a). This indicates that although MR learns clusters that are less uniformly distributed than RR at high d, the quality of learnt clustering is superior to RR across all d. Note that uniform distribution N data points per cluster, i.e. 1250 for ImageNet- IK with k 1024. We quantitatively evaluate the proximity of the MR and RR clustering distributions with Total Variation
20

---

300
d 00078
d,y-0 0012:
350
0,001,
250
0 00128
300
0.00095
Number of colls
200
MR-8 RR 8
Number celts
MR-16
Number of cells
250
MR.32
200
BR-16
200
RR-32
150
150
150
1000
100
50
500
1000
1500
2000
2500
500
1000
1500
2000
2500
1000
1500
2000
2500
Number data points per cell
Number data points per cell
Number points per cell
350
dry=0
350
drys
dry
00069
0,006
300
300
Number colls
250
RR-64
250
RR-128
Number of cels
300
MR-256
6A-
200
200
Number
1.50
150
100
100
100
1000
1500
2000
500
2000
2500
1000 1500
2000
Number of data points per cell
Number of data points per cell
Number of data points per cell
drymB 00076
400
dkym0.00075
400
diym6.00054
350
2>44
dry. 214.20
0h.:24400.00055
Number of calls
300
Number calls
300
MR-1024
Number of calls
300
MR
250
RR.512
RR-1024
RR-2048
200
200
200
150
100
100
50
500
1000
1500
2000
500
1000 1500 2000 2500
500
1000
15000
2000 2500
Number of data points per cell
Number of data points per cell
Number of data points per cell
Figure 11: Clustering distributions for IVF-MR and IVF-RR across embedding dimensionality on ImageNet-IK. IK. An IVF-MR and IVF-RR clustered with d = 16 embeddings is denoted by MR-16 and RR-16 respectively.
Distance [33], which is defined over two discrete probability distributions p, q over [n] as follows:
1 Σ 1E|m
drv 9)
p.
9ul
2
We also compute drv:204s (MRR-)) drv (MR-d, RR-2048), which evaluates the total variation dis- tance of a given low-d MR from high-d RR-2048. We observe a monotonically decreasing dyv:2048 with increasing d, which demonstrates that MR clustering distributions get closer to RR-2048 increase the embedding dimensionality d. We observe Figure 11 that drv (MR-d, RR-d) ~ 7e - 4 for d E {8, 256, .... 2048} and ~ 3e 4 for d E {16, 32, 64). These findings agree with the top-1 improvement of MR over RR as shown in Figure 9a, where there are smaller improvements for d E {16, 32, 64} (smaller drv) and larger improvements for d E (8, 256, ... 2048} (larger dyv). These results demonstrate a correlation between top-1 performance of IVF-MR and the quality of clusters learnt with MR.
F AdANNS-DisKANN
DiskANN is a state-of-the-art graph-based ANNS index capable of serving queries from both RAM and SSD. DiskANN builds greedy best-first graph with OPQ distance computation, with compressed vectors stored in memory. The index and full-precision vectors stored on the SSD. During search,
21

---

Table 6: Wall clock search latency (μU) of
across graph construction dimension-
ality d E {8, 16, )048) and compute budget in terms of OPQ budget M {8, 16, 48, 64). Search lateney is fairly consistent across fixed embedding dimensionality D.
d
M=8
M=16
M=32
M=48
M=64
8
495
16
555
571
32
669
655
653
64
864
855
843
844
848
128
1182
1311
1156
1161
2011
256
1923
1779
1744
2849
1818
512
2802
3272
3423
2780
3171
1024
5127
5456
5724
4683
5087
2048
9907
9833
10205
10183
9329
when a query's neighbor shortlist is fetched from the SSD, its full- preciiseeiionn vector is also fetched single disk read. This enables efficient and fast distance computation with PQ on a large initial shortlist of candidate nearest neighbors in RAM followed by a high- precision re-ranking with full- precision vectors fetched from the SSD on much smaller shortlist. The experiments carried out in this work primarily utilize DiskANN graph index built in-memory with OPQ distance computation.
As with IVE, DiskANN is also well suited to the flexibility provided by AdANNS we demonstrate both ImageNet and NQ that the optimal PQ codebook for given compute budget is learnt with a smaller em- (see Fig-
70.2
Top-1 Accuracy (%)
70.0
69.8
bedding dimensionality ures 6c and 7a). We demonstrate the capability of AdANNS-DiskANN with a compute budget of m (32, 64] Table We tabulate the search time latency of AdANNS- DiskANN microseconds (μ8) in Table 6, which grows linearly with graph construction dimensionality We also examine DiskANN-MD with SSD graph indices on ImageNet-IK across OPQ budgets for distance com- putation m,e E {32, 48, 64), as seen in Figure 12. With SSD indices, we store PO-compressed vectors on disk with maisk mades which es- sentially disables DiskANN's implicit high-precision re-ranking. We ob-
69.4
32-Byte
69.2
48-Byte
64-Byte
69.0
32
64
128
256
512
1024
Representation Size
Figure 12: DiskANN-MR with SSD indices for ImageNet- IK retrieval, with compute budgets maiik Mdd {32, 48, 64) across graph and OPQ codebook construction dimensionalities d E (32,. ... 1024]. Note that this does not use any re-ranking after obtaining OPQ based shortlist.
serve similar trends to other composite ANNS indices on ImageNet, where the optimal dim for fixed OPQ budget is not the highest dim (d 1024 with fp32 embeddings current highest dim supported by DiskANN which stores vectors in 4KB sectors on disk). This provides further motiva- tion for for quantization and thus enables similar Top-1 accuracy to Rigid DiskANN for up to 1/4 the cost (Figure 6c).
which leverages MRs to provide flexible access the optimal dim
G AdANNS on Natural Questions
In addition to image retrieval on ImageNet, we also experiment with dense passage retrieval (DPR) on Natural Questions. As shown in Figure 6, MR representations 1 10% more accurate than their
fatep:://ggthubb.oo///cccooottt
22

---

RR counterparts across PQ compute budgets with Exact Search + OPQ on NQ. We also demonstrate that IVF-MR on NQ. IVF loses ~ 10% accuracy compared to exact search, even with the RR-768 baseline. We hypothesize the weak performance IVF owing to poor clusterability of the BERT-Base embeddingg fine-tuned on the NQ dataset. A more thorough exploration of AdANNS-IVE on NQ is an immediate future work and is in progress.
2.5% better than IVF-RR for Precision @ k, k {1, 20, 100, 200). Note that
H
Ablations
H.1
Recall Score Analysis
100
100.0
40-Rocall @2008 (2204 (%)
1-Rocall@
16
32
32
87.5
128
129
258
85.0
512
1024
82.5
2348
2048
10
2
10
Probes (Np)
IVF Search Probes (np)
100
I0-Recall@2048 (%)
90
d
80
8
1-Recall@1
70
64
80
256
256
512
612
50
2048
2048
10
20
HNSW Search Probes (efSearch)
HNSW Search Probes (efSearch)
100
95
95
(D-Recal@@248 (%)
90
90
85
1-Recall@1
85
80
MR-8
80
MR-8
75
MR-64
MR-64
70
MR-256
MR-256
MR-2048
MR-2048
65
70
2
10
2
10
IVF Search Probes (na)
IVF Search Probes (ng)
Figure 13: k-Recall @N of d-dimensional MR for IVF and HNSW with increasing search probes np on ImageNet- K and ImageNet-4K, ImageNet-4K, we restrict our study to IVF-MR with d' E {8, 64, 256, 2048). Other embedding dimensionalities, HNSW-MR and RR baselines are omitted due to high compute cost. We observe that trends from ImageNet- K with increasing d and n, extend to ImageNet-4K, which is 4x larger.
23

---

22.5
MR
20.0
RR
Relative Contrast
17.5
15.0
12.5
10.0
7.5
5.0
2.5
8
16
22
64
128
256
512
1024
2048
Representation Size
Figure 14: Relative contrast of varying capacity MRs and RRs on ImageNet- IK corroborating the findings of He et al. [18].
In this section also examine the variation of k- K-Recall@N with by probing larger search space with IVF and HNSW indices. For IVF, search probes represent the number of clusters shortlisted for linear scan during inference. For HNSW, search quality controlled by the ef "earch parameter [38], which represents the closest neighbors to query at level le of the graph and is analogous to number of search probes in IVF. As seen in Figure 13, general trends show a) intuitive increase in recall with increasing search probes
n2)) for fixed search probes, b) decrease in recall with increasing search dimensionality d c) similar trends in ImageNet-1K and 4x larger ImageNet-4K.
H.2 Relative Contrast
We utilize Relative Contrast [18] to capture the difficulty of nearest neighbors search with IVF-MR compared to IVF-RR. For given database X {z, E 12 1,... NDD, a query E Igd and distance metric ((..)) we compute relative contrast C, as a measure the difficulty in finding the 1-nearest neighbor (I-NN) for query q in database X as follows:
1. Compute D min min D(g, x;). i.e. the distance of query to its nearest neighbor 24,m E X
i=
Compute Dg Deean [D( æ)] the average distance of query q from all database points E X
3. Relative Contrast of a given query C = Daean which is a measure of how separable the
D min
query's nearest neighbor ahn is from an average point in the database x
Compute expectation over all queries for Relative Contrast over the entire database as
C, [2(Da Eg [ m
It is evident that C, captures the difficulty of Nearest Neighbor Search in database X, as C,- 1 indicates that for an average query, its nearest neighbor almost equidistant from random point in the database. As demonstrated in Figure 14, MRs have higher R. than RR Embeddings for an Exact Search on ImageNet- IK for all 16. This result implies that a portion of MR's improvement over RR for I-NN retrieval across all embedding dimensionalities [31] is due to a higher average separability of the MR 1-NN from random database point.
H.3 Generality across Encoders
We perform an ablation over the representation function Φ X + Rd learnt via a backbone neural network (primarily ResNet50 in this work), as detailed in Section We also train MRL models [3]] o R(d) on ResNe118/34/101 [19] that accurate their independently trained RR baseline models RR(()) where d is the default max representation size of each architecture. We also train

---

MRL with a ConvNeXt-Timy backbone with [d] {48, 96, 192, 384, 786). MR-768 has a top-1 accuracy 79.43 19.45% compared to independently trained publicly available RR-768 baseline with top-1 accuracy 82. 82.1% (Code and RR model available on the official repo"). We note that this training had no hyperparameter tuning whatsoever, and this gap can closed with additional model training effort. We then compare clustering the MRs via IVF-MR with A = 2048, " on ImageNet- IK to Exact-MR, which is shown Figure 13. IVF-MR shows similar trends across backbones compared to Exact-MR, i.e. maximum top-1 accuracy drop of ~ 1.6% for a single search probe. This suggests the clustering capabilities of MR extend beyond an inductive bias of ø MR(d) E ResNee50, though we leave a detailed exploration for future work.
75
Top-1 Accuracy (%)
70
65
60
ResNet18
55
ResNet32
IVF-MR
ResNet101
ExacI-MR
ConvNeXI-Tiny
50
8
16
32
64
128
256
512
1024
2048
Representation Size
Figure 15: Top-1 Accuracy variation of IVF-MR on ImageNet- 1K with different embedding rep- resentation function MR(d) (see Section 3), where & (ResNet 8/34/101, ConvNeXt-Time We observe similar trends between IVF-MR and Exact-MR on ResNet18/34/10 when compared to ResNet50 (Figure 9a) which is the default in all experiments in this work.
25


Reviews:
[{"review_id": "x2NE0QdJiQ", "reviewer": "Reviewer_i99a", "summary": "The author introduced an adaptive method for searching near-neighbors called AdANNS, which employs different representations of the same item at various stages of the engine. Rather than relying on traditional fixed vector representations, the authors utilized Matryoshka representations, creating a nested representation with varying dimensions for each item.", "questions": "1)  How are the vector sizes $d_c$ and $d_s$ decided for a particular dataset? A grid search is not practical. Similarly how the parameter $k$ is set? Is there any rule?", "limitations": "The authors have discussed the limitations in section 5.3. There are no potential negative societal impacts. ", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1) AdANNS beats the traditional IVF and OPQ on accuracy and compute-resource tradeoff by proposing two main ANNS building blocks: search data structures (AdANNS-IVF) and quantization (AdANNS-OPQ).\n2) The comparisons are made against the standard NN approaches IVF and OPQ.\n\n", "weaknesses": "1) Limited datasets: The authors have only used ImagNet-1K and NQ datasets for vector-based retrieval. Many standard open-source datasets are available for this purpose (ANN benchmark and BigANN benchmark). A simple MLP/autoencoder can be trained for varying embedding sizes, or dimensionality reduction (like PCA, random projection) methods can be used.\n2) The paper is weak in novelty. It uses the existing method Matryyoshika Representations of each vector for the near neighbor retrieval. I do acknowledge that the modern composite ANNS index framework is being modified to support the Matryyoshika Representations. This provides a gain in top-1 accuracy for a given compute budget. However, I see this as a trivial change.\n3) There is no comprehensive theoretical analysis that compares the AdANNS-IVF, AdANNSOPQ, and AdANNS-DiskANN over their baseline counterparts. \n4) Baselines: The baselines comparison are limited. As AdANNS can be adapted to HNSW and Scann as well, it will be good to analyze the performance improvement there. \n5) Marginal gains: (Table 3 Appendix) It seems like AdANNS-IVF provides marginal accuracy gains over IVF with similar query times. This is good but not very convincing in favor of Matryoshka representations against single rigid representations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and feedback. Below, we answer the questions raised in the review:\n\n1) **Limited datasets**: We discuss our reasoning to experiment on only ImageNet and Natural Questions datasets in more detail in Related Works (L130-140). To summarize: \n- *Existing ANNS benchmarks*: BigANN benchmarks [1] and ANN benchmark datasets [2] **do not provide raw data**, and we thus cannot encode MRs for AdANNS. Also they are in general datasets with <10M points. Results on ImageNet and NQ demonstrate the potential of AdANNS across modalities (image, text) and scale (1M to 21M). Finally, dense retrieval community uses NQ as benchmark and similarly, non-trivial gains on ImageNet benchmarks often generalize (Kornblith et al. [3]), even to web-scale. \n- *Training MLP/Autoencoder*: As both  BigANN [1] and ANNS benchmarks [2] do not have ground truth labels, we would need to train an MLP/autoencoder with a reconstruction loss on the embeddings, which is not ideal to learn optimal information packing of MRs. We would also require raw data to finetune a RR encoder to an MR encoder, as we do for BERT-Base on Natural Questions train set (used for all passage retrieval experiments on NQ in this work) and is also shown by Kusupati et. al [4], Appendix K.1\n- *Dimensionality reduction*: We would like to point out that PCA or Random projections do not work well in practice as shown in our experimentation (see MG-IVF-SVD in Section 4.1, Figure 2) and Table 2 in Kusupati et al. [4]. \n\n2) **Novelty**: We strongly disagree that the AdANNS framework is a trivial change over MRL. Despite vast amount of literature on ANNS going back decades, existing methods all used a fixed representation size for all building blocks. We are proposing a shift in this paradigm, where different blocks can use different parts of MR representations thus providing one more point of control in ANNS pipeline. Given the significance of ANNS in search, retrieval augmented LLMs, we believe the improved compute-accuracy trade-offs by AdANNS can have significant downstream impact.  We discuss this in more detail in the Introduction (L077-085) and are happy to discuss further. \n\n3) **Theoretical analysis**: Thanks for the comments on potential theoretical analysis. Generally, ANNS field itself lacks significant rigorous analysis due to challenges in modeling the data and query. In particular, even famous techniques like IVF, HNSW do not have solid theoretical analysis which is mostly limited to methods like KD-trees which do not scale. Having said that, we agree that further investigation on theoretical front of ANNS is needed, and we leave it for future work. \n\n\n4) **Baseline evaluation**: We respectfully disagree that our baseline evaluations are limited. We in fact already evaluated HNSW+AdANNS:  show results on AdANNS-HNSW with OPQ in Appendix D (Figure 6d), where we find that AdANNS provides gains over using MRs and RRs in high compression regimes (<= 32 bytes). We further evaluate AdANNS-HNSW with a recall score analysis in Appendix I (Figure 12).  \nSimilarly, ScANN is essentially a search space partitioning with anisotropic vector quantization, which is analogous to IVF with OPQ which we have experimented with. Lastly, we have discussed the future extension of AdANNS to HNSW and ScANN in Section 4 (L278-284) and are happy to discuss in more detail.\nWe would like to highlight that both IVF and DiskANN are state-of-the-art techniques used in billion-scale data regimes, and OPQ is a ubiquitous quantization scheme for ANNS. \n\n5) **Marginal accuracy gains**: We strongly disagree with the reviewer that the accuracy gains for AdANNS over rigid IVF are marginal. \nNote that even gains of 0.5% are potentially significant for web-scale long tail data and also translate to other real-world tasks [4]. In contrast, we are able to gain up to 1.5% ground truth accuracy over rigid representations for the same query time (Appendix B, Table 3).\n\n6) **Hyperparameter search ($d_c$, $d_s$)**: We acknowledge that choosing the optimal hyperparameters for AdANNS is an interesting and open problem that requires more rigorous examination, though we would like to point out that tuning for constraints is not a new problem in the ANNS community [3]. We find that generally speaking, the highest dimensionality that fits within a compute budget is optimal for IVF (Figure 14, Appendix I.3; Figure 7c, Appendix E.1). For OPQ, we find that across ANNS strategies the best performance comes from learning quantization on a smaller dimensionality (Section 4.2, L310-312). Lastly, we also monitor the accuracies of low-d representations on the downstream dataset to ensure only a minimal loss in information from high-d representations. We shall add these takeaways as a guide for setting the right $d_c$ and $d_s$ for a given dataset. \n\n7) **Number of Clusters ($k$)**: It is generally accepted that a good starting point for the number of clusters $k$ is $\\sqrt{N_D/2}$ where $N_D$ is the number of indexable items [5]. And $k=\\sqrt{N_D}$ is the optimal choice of $k$ from a FLOPS computation perspective as can be seen in Appendix E.4. We thank the reviewer for bringing up this point, and will discuss this in the next revision.\n\nWe hope that the rebuttal clarifies the questions raised by the reviewer. We would be very happy to discuss any further questions about the work, and would really appreciate an appropriate increase in the score if the reviewer’s concerns are adequately addressed to facilitate acceptance of the paper.\n\n[1] Simhadri et al., Big ANN Benchmarks, Github repository\n\n[2] Aumüller et al., Information Systems 2019 ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms\n\n[3] Paltz et al., 2023 criteo/autofaiss, Github repository\n\n[4] Kornblith et al., CVPR 2019 Do Better ImageNet Models Transfer Better?\n\n[5] Mardia et al., 1979 Multivariate Analysis p.365\n"}, {"review_id": "h1p3VySpK4", "reviewer": "Reviewer_kQzU", "summary": "The authors introduced AdANNS, a framework that effectively harnesses the flexibility of Matryoshka Representations. This approach is applied to two fundamental components of typical ANNS systems: (a) the search data structure that stores datapoints, and (b) the distance computation that maps a given query to points within the data structure. To incorporate matryoshka representations with each of these ANNS building blocks, the authors proposed AdANNS-IVF and AdANNS-OPQ.\n\nExtensive experiments demonstrated that AdANNS achieves a state-of-the-art accuracy-compute trade-off for the two primary ANNS building blocks. Moreover, when combining AdANNS-based building blocks, superior real-world composite ANNS indices can be constructed.\n\nDespite these findings, it should be noted that the authors conducted their research on small-scale open-source datasets only. Nevertheless, they assert that the primary contribution of this research is the proposal of AdANNS, which they claim is applicable to web-scale industrial systems.", "questions": "Why didn't you include a larger dataset for the experiments? Was it due to data availability or limitations in your implementation?", "limitations": "The authors have discussed the limitations of this work in section 5.3: To use AdANNS on a corpus, one need to back-fill the MRs of the data – a significant yet a one-time overhead.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) Although Matryoshka Representations (MR) already contain multi-granular representations, meticulous integration with ANNS building blocks is paramount to develop a functional method, representing the key contribution of this work.\n(2) Through extensive experiments, it has been demonstrated that AdANNS achieves a state-of-the-art accuracy-compute trade-off for the two primary ANNS building blocks. Furthermore, the combination of AdANNS-based building blocks results in the creation of superior real-world composite ANNS indices.", "weaknesses": "(1) It may be beneficial for the authors to restructure the introduction. For instance, in the second paragraph, the authors delve into the details of IVF, explaining its two phases and why using the same high-dimensional Rigid Representation (RR) for cluster mapping and linear scanning could be sub-optimal. While I understand the authors' intent to introduce adaptive representations followed by matryoshka representations, I believe it would be more logical to first describe each component of ANNS and explain how adaptive representations could serve as a replacement for rigid representations.\n\n(2) It's important to acknowledge that the authors conducted their research exclusively on small-scale open-source datasets. Despite this limitation, they maintain that the main contribution of their study is the introduction of AdANNS, which they assert can be applied to web-scale industrial systems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and feedback. We are glad the reviewer acknowledged our work’s potential to provide superior real-world ANNS indices. Below, we answer the questions raised in the review:\n\n1) **ANNS components in the Introduction**: Thanks for the valuable suggestion on restructuring the introduction. We agree that fleshing out ANNS and its fundamental components. We shall add it in the next revision. \n\n2) **Evaluation of AdANNS**: We respectfully disagree with the reviewer that the evaluation was done on small scale datasets. While not Billion scale like in the industry, ImageNet (image, 1.3M database) and Natural Questions (text, 21M database) are strong benchmark datasets for retrieval evaluation with publicly available raw data to train new representations from scratch (which is needed for strong adaptive representations and new variants like MRs). Most of the ANNS progress was on pre-built representations with around a Million points in the database, such as in ANN-Benchmarks [1]. The more recent larger benchmarks released (Big ANN Benchmarks [2]) have about 10M database points. Both these standard benchmarks rarely have publicly available raw data – which is unlike ImageNet and NQ that are of similar scale. Further, none of the ANNS benchmarks have ground truth labels for evaluation, instead considering exact search NN as ground truth for evaluation. Because our implementations easily scale to NQ, they should work for most of these ANNS benchmarks; as shown previously [3], the nontrivial gains achieved on ImageNet-based datasets often generalize to other datasets and to web-scale.\n\n    In summary, it is primarily due to the lack of publicly available raw data for the other datasets and not the limitations in implementation. We discuss this in more detail in Related Work (L130-140) and are happy to discuss this further.\n\n\nWe hope that the rebuttal clarifies the questions raised by the reviewer. We would be very happy to discuss any further questions about the work, and would really appreciate an appropriate increase in score if reviewer's concerns are adequately addressed to facilitate acceptance of the paper.\n\n[1] Aumüller et al., Information Systems 2019 ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms\n\n[2] Simhadri et al., Big ANN Benchmarks, Github repository\n\n[3] Kornblith et al., CVPR 2019 Do Better ImageNet Models Transfer Better?\n\n"}, {"review_id": "4Ioxi5Y90x", "reviewer": "Reviewer_V9Qf", "summary": "Matryoshka Representation representations have the advantage that the first m-bits of the d-dim vector can as-is serve as a good m-dim representation of the original d-dim vector. This paper demonstrates how Matryoshka Representations (MR) can be used together with approximate nearest neighbor search indices to speed up test-time inference as well as optimize for indexing cost and storage budgets for semantic search applications. The authors run extensive experiments on two datasets with up to 21 million items, carefully exploring the design space.\n\nUpdate: I have updated my score to 7 after reading clarifications provided by authors.", "questions": "- Is ground-truth 1-NN (as per the dense representations) used or ground-truth label (as per labelled data for downstream task) used for eval?\n- Can authors elaborate on why using 2k clusters with d/2 dim vectors is just as costly as using k clusters with d-dim vectors? What cost is being referred in this statement? Is it test-time inference cost or is it indexing cost?\n- In Fig.2, why does AdANNS-IVF perform better than AdANNS-IVF-D? Why does using a smaller dim MR embedding give better results than using full 2048-dim embedding for clustering?", "limitations": "Yes", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper is very well-written and easy to follow (although it requires quite a few jumps to and from the appendix to really understand the results :) ).\n- The papers presents a clever use of properties of Matryoshka Representations for semantic search. Unlike standard dimensionality reduction methods like SVD or random projection, use of MR representations allows use of lower-dim representations when needed without additional computation to get low-dim representations.\n- Extensive experiments and analysis of the proposed approach.", "weaknesses": "- Too many hyper-parameters to optimize — This might limit wide scale adoption of proposed methods.\n    - A major chunk of performance boost observed comes from merely using Matryoshka Representations (MR) instead of traditional dense representations (RR). For instance, in Fig. 2, IVF built with MR gives significant improvement over IVF built with RR. While proposed adaptive IVF outperforms fixed-IVF with MR, it may require an non-trivial exhaustive search of hyper-parameters. And, as show in Fig. 10, only a small fraction of these hyper-parameter settings for adaptive-IVF-MR outperform fixed-IVF with MR representations.\n    - It would be helpful to also include a practical guide of how to choose these hyper-parameters in practice. In my opinion, this can significantly help wide-scale adoption of ideas in this work.\n- (Minor) The proposed adaptive search methods only work with Matryoshka Representations and can not be applied directly to any dense vector representations. This might limit the impact of the paper as the user may not have the budget or infrastructure to train MR representations especially when such embeddings are obtained form some large pre-trained vision/language models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and feedback. We are glad the reviewer found our work easy to follow and clever. Below, we answer the questions raised in the review:\n\n1) **Jumps to Appendix**: Thanks for letting us know of requiring jumps to the appendix, we shall improve readability to minimize this in the next revision.\n\n2) **Too many hyperparameters**: As mentioned in the general comment, forming optimal index can have a massive impact on cost, QPS, latency at industry scale. So, it is an industry practice to have a careful parameter search for all the hyperparameters in ANNS. So AdANNS doesn't fall beyond that practice. \nHowever, we acknowledge that choosing the optimal hyperparameters for AdANNS is an interesting and open problem that requires more rigorous examination.  \n- *Existing solution*: Autofaiss [1] optimizes hyper-parameters of ANNS indices for the constraints at hand (i.e. the optimal compute-accuracy model for a given use case). We will publish a similar guide on top of AdANNS in the next revision.\n- *Hyperparameter selection guide*: We agree with the reviewer that only a small fraction of the hyperparameter space of AdANNS is above IVF-MR – Fig. 10 was intended to show the entire design search space, which is not feasible in real-world deployment. Hence, we suggest starting with IVF-MR configs and moving towards AdANNS based on the use case. \nWe would like to mention that the gains of AdANNS-IVF come from both simple adaptivity (e.g. MG-IVF-RR is 1-1.5% more accurate than IVF-RR) and better clustering of MRs (IVF-MR is 1-1.5% more accurate than IVF-RR), resulting in an overall boost of up to 2% ground truth top-1 accuracy; even a bump of 0.5% is potentially significant in searching web-scale long tail data. We thank the reviewer for bringing up this interesting point, and shall add a brief discussion on selecting hyperparameters for AdANNS in the next revision.\n\n3) **Requirement for Matryoshka Representations**: We acknowledge that a current disadvantage of full-potential AdANNS is the requirement to backfill MRs (Section 5.3, L405-410). We address this issue in two ways:\n- *Adaptivity*: As we demonstrate with the MG-IVF-RR baseline in Section 4.1 (Figure 2), where we “replicate” AdANNS with existing dense vector representations (RRs) for gains of more than 1% ground truth accuracy. This is a strong method, but is several times more expensive during both training and inference than AdANNS using MRs. E.g. MG-IVF-RR requires training 10 independent rigid models, each of which require independent inference to obtain dense vectors for ANNS. Further we can also leverage adaptivity through post-hoc compression (e.g. MG-IVF-SVD), albeit not as well as explicitly trained RRs.\n- *Inducing MR behavior through fine-tuning*: We agree with the reviewer that pretraining large models with MRL is expensive to train, such as in the case of large vision/language models. We have shown that Matryoshka behavior can be induced in pretrained models by fine-tuning the BERT-Base encoder on Natural Questions train set, which we use for all Natural Questions passage retrieval in this work. A more detailed study on fine-tuning to induce MR behavior is discussed in Appendix K.1 in [2]. \n\n4) **Evaluation metric**:  For all the main experiments, we use the ground-truth label to compute top-1 accuracy (available for ImageNet and NQ datasets).  However, we also used ground-truth NN (w/ exact search) in k-recall@N to be consistent with the literature (defined Appendix C, L570-572) in experiments (Appendix E.2, Figure 8b and Appendix I.1, Figure 12). Overall, ground-truth label based top-1 is a harder and more representative metric than the widely used exact search NN based metrics. We will make this point more clear in the next revision.\n\n5) **Clustering and cluster selection costs**: The complexity of both training a k-means clustering with d-dim vectors and the cluster selection for a given query scale as *O(kd)*. So both the training and cluster selection costs remain the same as k-clusters with d-dim vectors for 2k-clusters and d/2-dim vectors. We shall make this more clear in the next revision of the manuscript.\n\n6) **AdANNS-IVF-D**: We discuss this in more detail in Section 5.1 (L363-373), but to summarize, AdANNS-D is an “emergent” behavior that has not been explicitly designed for, which leverages the properties of MRs to enable elastic search during inference. AdANNS-IVF provides more flexibility by making the entire design search space available for compute-aware deployment, and thus allows to find configurations that are more accurate than AdANNS-IVF-D. \n\n7) **Low-dim clustering**: Due to the efficient information packing of MRs, for a majority of the data, we have sufficient information in d/2 dimensions when compared to the full d dimensions. This can be seen by the high top-1 classification accuracy of low-dim MRs on ImageNet. So when a pair of high-d and low-d representations contain similar information, it is easy to converge to a better clustering using low-d vectors owing to the curse of dimensionality. As k-means scales *O(kd)* and when k remains constant, low-d representations with similar accuracy converge faster and to a better solution in practice. We are happy to further discuss this aspect.\n\nWe hope that the rebuttal clarifies the questions raised by the reviewer. We would be very happy to discuss any further questions about the work, and would really appreciate an appropriate increase in score if reviewer's concerns are adequately addressed to facilitate acceptance of the paper.\n\n[1] Paltz et al., 2023 criteo/autofaiss, Github repository\n\n[2] Kusupati et al., NeurIPS 2022 Matryoshka Representation Learning\n"}, {"review_id": "LUdWKMnR6w", "reviewer": "Reviewer_kCbM", "summary": "This paper proposes to use the Matryoshka Representations for approximate nearest neighbor search (ANNS). Matryoshka Representations provide the flexibility to adjust the budget for index search, index storage, and distance computation by changing the dimension of the used embedding. The paper instantiates the idea using IVF and OPQ, two popular techniques for ANNS, and shows impressive experiment results. ", "questions": "NA", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I like that this paper focuses on the end-to-end performance of ANNS, i.e., the top-1 accuracy of ANNS applications. This differs from the widely used recall, which only considers distance in the embedding space, and could be inspiring for the field. \n1. The property of Matryoshka Representations is interesting and using it to make ANNS flexible makes sense. However, the authors could introduce more about Matryoshka Representations, e.g., how are they trained and what is the training cost compared with standard embedding.\n2. Two examples of using the Matryoshka Representations are provided.\n3. The experiment results are comprehensive and impressive. \n4. The gains of Matryoshka Representations and limitations are discussed in Section 5.\n", "weaknesses": "The labels of the figures need to be enhanced to make them self-content. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and feedback and are glad they found our work impressive and well suited for ANNS. We address the reviewer’s feedback below:\n\n1) **Details on Matryoshka Representations**: We have briefly discussed the details of Matryoshka Representations in L154 - 163 and shall add more details to make it much more accessible to readers. In our experience, Matryoshka Representation Learning does not add any training overhead or hyperparameter tuning on top of a chosen representation learning setup (across models, dataset and modalities). \n2) **Labels of the figures**: We thank the reviewer for their feedback on figure labels. We will address these in the next revision.\n\nWe hope that the rebuttal clarifies the questions raised by the reviewer. We would be very happy to discuss any further questions about the work, and would really appreciate an appropriate increase in score if reviewer's concerns are adequately addressed to facilitate acceptance of the paper.\n"}]

Author rebuttal:
We thank the reviewers for their time and valuable feedback. We are happy to know that the reviewers found the paper to be very well written, easy to follow, and clever along with extensive experimentation and analysis showcasing state-of-the-art accuracy-compute tradeoff for ANNS building blocks and composite indices. However, there were some general comments we want to address here briefly before diving deep in each individual rebuttal. 

1) **Further improving readability**: We shall fix the remaining few issues with the flow of the paper and try to reduce dependency on referring to external papers and the appendix for the readers when focusing on the fundamental and primary contributions. 
2) **Hyperparameter search guide**: Most reviewers found a need for a hyperparameter search guide for AdANNS and we completely agree with them. While the hyperparameter search for AdANNS might seem expensive, it is not a new problem in the ANNS community which has potential solutions like Autofaiss [1]. Furthermore, because the index is formed once and is used for potentially billions of queries thus having massive implications for cost, latency and query-per-second, generally hyperparameter search for the best index is an acceptable industry practice. 
In case of AdANNS, starting at the best configurations of MRs followed by a local design space search would lead to near-optimal AdANNS configurations (e.g. use IVF-MR to bootstrap AdANNS-IVF). We shall add a section on this in the next revision of the paper.
3) **Limited datasets**: Another common question is regarding the evaluation of AdANNS on only ImageNet (1M and 4M) and Natural Questions (21M) datasets. We discuss this in detail as part of our Related Work (L130-140), but a short answer is that all the standard ANNS benchmarks [2,3] *do not provide raw data* to allow for the training of new representations. This makes evaluation near impossible with new representation learning paradigms. At the same time, using post-hoc compression techniques to obtain adaptive representations results in extremely poor performance as shown in this paper and MRL [4]. Lastly, even the benchmark datasets are often in the scale of 1-10M and are similar to what we have evaluated – note that ImageNet and NQ have ground truth labels allowing us to compute the hard and more representative ground truth top-1 accuracy, unlike most benchmarks. We are happy to discuss in more detail during the discussion phase.
4) **Novelty and baselines**: While most reviewers agree that enabling adaptive semantic search in ANNS is a hard problem, we want to re-emphasize that without meticulous integration of adaptive representations into ANNS building blocks and composite indices, the utility of adaptive representations is severely limited. While MRL [4] proposed a simple variant of adaptive retrieval, in practice it does not scale to any large-scale problems due to various systems issues often already addressed in modern-day ANNS pipelines. We believe that AdANNS is a non-trivial contribution that shows the utility of adaptive representations across core building blocks (that form the baselines) along with a scalable implementation.

We hope that the individual rebuttals clarify the questions raised by the reviewers. We are happy to discuss any other concerns further during the discussion phase and appreciate your support for the acceptance of the paper.

[1] Simhadri et al., Big ANN Benchmarks, Github repository

[2] Aumüller et al., Information Systems 2019 ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms

[3] Paltz et al., 2023 criteo/autofaiss, Github repository

[4] Kusupati et al., NeurIPS 2022 Matryoshka Representation Learning



Meta-review: The paper explores the use of Matryoshka Representations in approximate nearest neighbor search indices to enhance test-time inference speed, indexing cost, and storage budgets.

All reviewers agree that AdANNS demonstrates strong performance on both accuracy and compute-resource trade-offs in comparison to traditional methods like IVF and OPQ. The system is found to have state-of-the-art accuracy-compute trade-offs for the two main ANNS building blocks (kQzU, V9Qf). The paper's unique application of Matryoshka Representations is highly regarded (kQzU, V9Qf, kCbM). Reviewers appreciate how MRs offer flexibility and semantic richness to the ANNS system.
Reviewer kCbM specifically mentions that the paper brings a fresh perspective by focusing on the end-to-end performance of ANNS, which diverges from the traditional focus on recall metrics.
Overall, the reviewers found the paper to be strong in its novel approach, extensive validation, and its shift of focus towards a more holistic evaluation of ANNS systems.

Some common weaknesses raised by reviewers include: The paper's evaluations are constrained to a limited set of datasets like ImageNet-1K and NQ, missing out on other standard benchmarks (i99a, kQzU). Baseline comparisons are also considered insufficient (i99a). V9Qf highlights that the many hyper-parameters required for optimization could impede wide adoption. The system's dependency on Matryoshka Representations also limits its broader applicability.
Decision: Accept (poster)