AdANNS: A Framework for Adaptive Semantic Search

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.

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. 1. 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. 2. Two examples of using the Matryoshka Representations are provided. 3. The experiment results are comprehensive and impressive. 4. The gains of Matryoshka Representations and limitations are discussed in Section 5.

Weaknesses

The labels of the figures need to be enhanced to make them self-content.

Questions

NA

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Yes

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. Update: I have updated my score to 7 after reading clarifications provided by authors.

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 :) ). - 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. - Extensive experiments and analysis of the proposed approach.

Weaknesses

- Too many hyper-parameters to optimize — This might limit wide scale adoption of proposed methods. - 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. - 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. - (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.

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? - 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? - 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?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

Yes

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. Extensive 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. Despite 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.

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. (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. (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.

Questions

Why didn't you include a larger dataset for the experiments? Was it due to data availability or limitations in your implementation?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

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.

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.

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). 2) The comparisons are made against the standard NN approaches IVF and OPQ.

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. 2) 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. 3) There is no comprehensive theoretical analysis that compares the AdANNS-IVF, AdANNSOPQ, and AdANNS-DiskANN over their baseline counterparts. 4) 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. 5) 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.

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?

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

The authors have discussed the limitations in section 5.3. There are no potential negative societal impacts.

Acknowledging author response

Thank you for answering my questions! I have read the author response and have increased my score from `6:Weak Accept` to `7: Accept` and I would vote in favor of accepting the paper. I would encourage authors to a) update the presentations so as to minimize the need to oscillate between the appendix and the main paper and b) add more details on hyper-parameter tuning, maybe even a set of default hyper-parameters that the authors would suggest using for new applications/datasets.

Further questions or concerns?

We are happy to discuss if anything in the rebuttal needs more clarification or if the reviewer has further questions regarding the paper.

Further questions or concerns?

We are happy to discuss if anything in the rebuttal needs more clarification or if the reviewer has further questions regarding the paper.

Further questions or concerns?

We are happy to discuss if anything in the rebuttal needs more clarification or if the reviewer has further questions regarding the paper.