Summary
This paper investigates approximate nearest neighbor (ANN) search, where, given a collection $\mathcal{X}$ of points in $\mathbb{R}^d$, the task is to find the top $k$ data points that are closest to a query point $q$ according to some similarity or dissimilarity measure (denoted by $\delta(\cdot, \cdot)$), such as inner product. There are many classes of algorithms in existence[1], with this particular work falling into the clustering-based paradigm.
In clustering-based (aka Inverted File or IVF) ANN search, $\mathcal{X}$ is partitioned into a set number of clusters, often using a geometric clustering algorithm such as (spherical) KMeans, with every cluster represented using some sketch of the cluster such as its mean. When presented with $q$, the algorithm first identifies $\texttt{nprobe}$ clusters to search by ranking the clusters according to the distance between $q$ and their representative points. It then computes $\delta(q, \cdot)$ with points within the $\texttt{nprobe}$ clusters, and returns the top $k$ points from that set.
This work concerns the second step. Typically the computation of $\delta(q, \cdot)$ uses Product Quantization (PQ) to reduce memory consumption and to perform the distance computation efficiently. Instead, this work reduces the dimensionality of the data matrix within each cluster using its low-rank approximation. The key insight is that, the low-rank approximation is constrained to the space of rank $r$ matrices that predict the inner products well on a specific query distribution.
[1] "Foundations of Vector Retrieval" by S. Bruch. Springer.
Strengths
* The proposed method relies on a very simple yet effective method for supervised dimensionality reduction in the context of ANN search
* The paper is easy to read and arguments straightforward to follow
* Results are encouraging
Weaknesses
Post-discussion Update: The authors have addressed my concerns around the experimental setup, and have expressed interest in adopting a more clear narrative and framing of their contributions.
-----------------
* Presentation:
- I think the authors can shed quite a bit of fluff by positioning the work as I did in my summary. This work's contribution is very much in the speeding up and improving the accuracy of the score computation phase in clustering-based/IVF ANN search. Presented that way, the authors can immediately focus on the regression problem instead, and not introduce distractions such as the details of clustering, the importance of MIPS (section 2.1), and more. It'd make for a cleaner presentation of your idea, and lets your readers understand the scope of your contributions more clearly.
- As a minor point, Theorem 1 is a vacuous statement. It's neither necessary to explain the findings of the paper, nor is it insightful enough to birth new research directions. Perhaps you can move it entirely to the appendix if you insist on including it in the work.
- It must be noted that the method presented in this work is supervised. That is a critical differentiating factor between LoRANN and existing methods such as PQ and Scann.
* Methodology: One of the interesting insights that led to Scann is that not all inner products are equally important. For a quantization method to be successful, it needs to preserve the inner product between $q$ and high-ranking data points better than inner product between $q$ and low-ranking points. In your work, you model the problem as regression, and attempt to minimize the error of inner production approximation equally for all data points. What motivates this uniform weighting? Have you considered a ranking formulation of the problem rather than regression? There is a vast literature on learning-to-rank which, in fact, is very relevant to your idea, but where Scann's insight is baked into its machinery/objective.
* Experiments: Because the methodology is very straightforward and the novelty is minimal, I expect a much stronger experimental evaluation of the proposed method. Here are a few points to consider:
- Your main experiments conflate two orthogonal axes of evaluation: effect of clustering vs effect of score computation; this I believe stems from the way you present your work. Your contribution, as I noted above, is to the score computation phase of IVF-based ANN search. To evaluate your contributions fairly against SOTA IVF methods, you must partition the data once. Given this fixed set of partitions, you can directly compare the efficacy of LoRANN against PQ and Scann's quantization protocol. By running each method independently as you do now, such that each produces its own partitioning of the data separately, you run the risk of conflating the effect of clustering on IVF's accuracy with the effect of the specific choice of dimensionality reduction/quantization. As it stands, I cannot deduce the exact reason why your method should work better.
- You are also comparing a supervised method that adapts to a query distribution, with unsupervised baselines. Not only is it not a fair comparison, your results are also not informative. It is not surprising that your method does well: you give it an unfair advantage (as confirmed by Figure 1 - left) by finding a matrix that can predict inner products on *a specific query distribution*. A more reasonable experiment would be to (a) compare a variant of LoRANN that's trained on the data points only (i.e., without training queries) with other IVF methods, and (b) incorporating the query distribution into Scann (its objective can use information about the query distribution). There are other methods that can use a query set to improve quantization ([2,3] are a couple of examples).
- As a very simple baseline, consider partitioning the data using centroids obtained from a partitioning of queries!
- Frankly, a comparison with graph methods is nice, but is rather tangential. I encourage you to contrast your method with other IVF methods first, focus your discussion to justifying your proposal against SOTA IVF methods, and then conclude your work with a comparison with graph methods for completeness.
[2] "Query-Aware Quantization for Maximum Inner Product Search" by Zhang et al. AAAI 2023.
[3] "A Learning-to-Rank Formulation of Clustering-Based Approximate Nearest Neighbor Search" by Vecchiato et al. SIGIR 2024.
Questions
My questions mainly concern your experimental evaluation:
* Setup: What's the training set used to train LoRANN? You have kindly given statistics about each dataset, but sadly did not include any information about the size of the query sets.
* Figure 1: What is the size of the initial candidate set in the right figure, where reranking is enabled? It is important to know this because the size of the initial set can explain the small difference between the different curves (e.g., if you retrieve a very large set followed by re-ranking, the accuracy of each method pre-reranking becomes less and less important)
* PQ is obviously sensitive to the bitrate, a hyper-parameter. Can you elaborate how LoRANN holds up against PQ as you sweep the rank parameter and PQ's code size, in terms of speed and memory usage?
Limitations
I really like this work and the simplicity of the idea. I'd love to see this work in print, but I think it can be so much more complete with a proper set of experiments. As it stands, the incomplete experiments limit the reach of this work. A stronger formulation (using ranking, e.g.) can even enhance the results too. I hope my feedback proves helpful in strengthening the arguments of this work.