Relevance-Based Embeddings for Efficient Relevance Retrieval

RecSys (3 out of 9 scenarios reported) are a) based on proprietary, non-reproducible datasets

As we write in line 377, all these datasets will be published after the legal approval.

b) the teacher model (gradient boosting model) is not considered state-of-the-art for recommendation systems.

We note that GBDT models are known to be state-of-the-art (or at least competitive) for tabular data, see, e.g., McElfresh D. et al. “When do neural nets outperform boosted trees on tabular data?” NeurIPS 2023. We consider heavy rankers that are currently used in real recommender systems. Here the features are indeed tabular (the mixture of category, textual and numerical features) and the model we consider is empirically shown to achieve the best results among many competitors. Moreover, this GBDT model also uses neural network scores as its features and thus is quite strong.

Published recommendation literatures over the last 1-2 years have used cross encoders (acknowledged by authors in intro L47-48), deep stacked networks (eg Wang et al. HoME: Hierarchy of Multi-Gate Experts for Multi-Task Learning at Kuaishou. 2024), and/or generative approaches (eg Zhuo et al. Learning Optimal Tree Models Under Beam Search. ICML'20., Gao et al. Deep Retrieval: Learning A Retrievable Structure for Large-Scale Recommendations. 2020)

Could you please clarify how these works weaken the contribution of our study? It is not clear from the comment. Note that in our paper, we do not aim at inventing new CE approaches but use an arbitrary CE instead.

Additionally the experiment setup used goes against authors' own claim in abstract "... The relevance function is usually an expensive neural similarity model"

Note that 6 out of 9 datasets use neural networks as similarity models. In the remaining 3 RecSys datasets we use GBDT models that aggregate many features, including heavy neural-network-based rankers as features. Thus, we cannot agree that the claim in the abstract is not correct.

QuestionAnswering (last 1 of the 9 scenarios) - the paper similarly failed to compare with recent state-of-the-art approaches on MS MACRO

As discussed above, our approach is orthogonal to the developments of complex CE and DE approaches. Our main idea is that we can use an arbitrarily powerful CE and use its relevances for effective and efficient retrieval.

Overall, more solid experiments on standard datasets are needed

Could you please specify which datasets you are referring to in this comment? We believe that the list of datasets we use in our study is quite extensive (we evaluated our approach on a larger list of datasets compared to previous related research).

W3. Random choice is a weak baseline for multi-embeddings given most prior work in this area already utilize co-trained query- and item- vectors. See references in W1.

As discussed above, we note that our study does not use multi-embeddings.

W4. To achieve universal approximation property of MLPs (used in Section 3), we need a very wide hidden layer. More experiments are needed to justify how to trade off quality vs efficiency of the proposed approach for retrieval in practical scenarios, against standard baselines.

In our cases, 50K parameters are empirically shown to be enough, which is still several magnitudes smaller than any DE used in our experiments.

Thank you for a detailed review and suggested references.

Let us note that the mentioned works use a different setup compared to our work and thus we do not use them as baselines in our paper.

Recall that our setup is the following. We assume that there is a heavy ranker (cross encoder, CE) that provides relevances for query-item pairs. This heavy ranker can be an arbitrary complex model and is a standard ingredient of a recommender system. Due to the dataset size, CE cannot be computed for all user-item pairs. A standard approach then is to approximate CE with a dual encoder (DE) that embeds queries and items to a space where relevances can be (approximately) computed via, e.g., the dot product. The top items retrieved via the approximate relevance are then re-ranked by CE. We improve over this standard approach (and simplify it) by creating more efficient representations of queries and items (via support items and support queries, respectively) that do not require training a (potentially complex) DE model (RBE is several orders of magnitude smaller than DE in the number of trainable parameters). Thus, we propose to simplify the Retrieve-and-Rerank scheme using the CE model that must be trained anyway.

Let us now go through the suggested references.

• Li et al. (2019) propose “a multi-interest extractor” that сomplicates the scheme with auxiliary steps and structures (see, e.g., Figure 7, while we use the given model from the ranking service and a small (50K parameters) adapter without auxiliary entities).
• Cen et al. (2020) cite the above paper and also propose a “multi-interest extraction module”.
• Ding et al. (2024) propose to embed queries and documents with multiple trainable embeddings (Figure 1). We instead assume that we are given a powerful cross-encoder and use only its scores to embed queries and items.

To sum up, these three papers propose to complicate the retrieval stage by obtaining multiple trainable representations. In contrast, our approach is based on the fact that there is a heavy powerful ranker, which is a part of every production system, this ranker can be arbitrary and we use only this model to embed queries and items.

• Khattab et al. (2020), see Figure 2, propose the late interaction (d) method. In contrast, both DE and RBE are Representation-based Similarity (a) methods (according to the authors’ classification). In particular, to get a list of candidates for the final re-ranking, our method can utilize any near neighbor search method.
• Santhanam et al. (2022) is another variant of the late interaction approach.
• Dhulipala et al. (2024) is a follow-up of the two works above that also сomplicates the standard DE-based scheme while we aim at simplifying it.
• Chang et al. (2023): this paper seems to be misplaced. Could you please clarify which part of this work is relevant to our study?

We can add some of the above references to the related work, where we discuss different types of approaches to relevance-based search. However, we do not compare with them since our setup is very different. In this regard, we follow previous studies and experimental setup used in a series of recent papers by Yadav et al. (but we extend the list of datasets used to further support our conclusions).

The paper's main theoretical result in Section 3 - "in any relevance function can be well estimated using only such individual vectors" (based on multiple embeddings) is in principle similar to the conclusion reached by Ding et al. in Efficient Retrieval with Learned Similarities. 2024, which also proves that multi-embeddings can be used to approximate arbitrary relevance functions, albeit with different proof construction and a slightly different neural architecture.

Our approaches, assumptions and theoretical results are very different. Note that we do not use multiple embeddings, while Ding et al. (2024) do not use CE-based representations. Could you please give us more detail about which part of the analysis you find similar? Then we will be able to answer the question in more detail.

Additionally, Dhulipala et al. MUVERA: Multi-Vector Retrieval via Fixed Dimensional Encodings. 2024 also shows for a widely used relevance function in COLBERT, a single very high-dimensional vector can be constructed to approximate the relevance function, and should also be discussed as related work.

A similar comment as above applies to this work: the theoretical result concerns a different function with a different input so we cannot directly relate this result to our work.

ZESHEL (5 out of 9 scenarios reported) is not commonly used in relevance retrieval scenarios for either RecSys or NLP

Note that the two works most relevant to our study, i.e., AnnCUR (Yadav, EMNLP 2022) and AXN (Yadav, ICLR 2024) use these five datasets, so we follow the same setup (with some additional datasets).

• RBE vs the multi-embedding line of work (MIND, ColBERT, + many discussed in the initial review): RBE first computes a) the distances between query embedding and multiple item embeddings and b) the distances between item embeddings and multiple query embeddings, so in some sense RBE computes 2xN distances whereas prior work computes NxN distances (assuming equal number of multi-embeddings on the query- and item- side), and RBE utilizes a different similarity function vs prior work. I do agree that the selection of fixed support embeddings can make multi-embedding like techniques more efficient, and the paper's approach from a distillation point of view has novel ideas, but multi-embedding literature still seems like a highly relevant line of work (main difference being 2N vs NxN, different ways to combine distances, etc.) that's completely missed by the current paper.

• Experiments: the only commonly used publicly available dataset across the 9 reported is MS MARCO (the other datasets are not commonly used and can be hard to contextualize/interpret for a general academic audience). Here ColBERTv2 (2021) reported 86.8 R@50 on the dev set whereas AnnCUR achieves .5522 @100 and RBE .6022 @100 (from Table 2 in the paper). Could you explain this gap? Or what would be the results on MS MARCO if we were to use ColBERTv2 (or more recent generative retrieval approaches) as the teacher model for RBE?

• Missing comparison with distillation-based approaches: Reading through the rebuttal and the paper a bit more, I feel the paper's focus is perhaps more on distillation in the retrieval stage, in which case comparison with alternatives TwinBERT (CIKM'20), Trans-Encoder (ICLR'22) etc might be needed. It is also well-known in IR that distillation by itself boosts retrieval stage's performance (see eg ColBERTv2 paper, Table 4). So having direct comparison with CE->DE distillation is very beneficial for readers to understand RBE's contribution formulation wise.

The focus on CE as golden standard for retrieval stage actually represents another flaw in the evaluation (and maybe formulation) of the paper - it is well known that a complex neural ranking architecture (eg CE) does not necessarily improve performance of the retrieval stage. See for ex Rendle et al's classical work neural collaborative filtering vs matrix factorization revisited.

Given this, comparing relative performance on the datasets is often not meaningful by itself, and I strongly suggest the authors to conduct experiments on commonly used datasets (eg MS MARCO) with standard baselines (eg DPR for DE, ColBERTv2 for late interaction multi-embedding models, NCI etc for generative retrieval) to enable the community to contextualize and interpret the results.

The rest of the points I made in the initial review stand too, but I would appreciate it if the authors could improve the experiments first to make the discussion more meaningful.

Could you please clarify what you mean by “distance” and “N”?

RBE computes distance from the query embedding to N support item embeddings and distance from the item imbedding to N support query embeddings.

Please reread some of the multi-embedding papers I referred to in the initial review. The difference between them and RBE is a) RBE improves efficiency by using fixed support item/queries, b) RBE uses an arbitrary neural function ($f_I$, $f_Q$) to transform the obtained $2N$ distances followed by inner product, whereas prior work used fixed or learned neural architectures.

I would also like to confirm that I've read the authors' rebuttal, and would like to keep ratings as is.

Thank you for your feedback! We address the questions and concerns below.

providing the actual runtime of the relevant models in the experiments is essential. Currently, only some analysis is included.

In our setup, we assume that the most time-consuming operation is the cross-encoder (CE) computation which is the case for real production systems, including CE and DE used within RecSys/RecSysLT/RecSys2 datasets. The computation of CE is time-consuming since the model itself is complex and also some features used by CE may require additional computations (e.g., some of them are neural-network-based or even DE scores itself). Thus, in each of the experiments, the number of CE computations is fixed for all the models (and is specified in the text). We think that measuring complexity in the number of CE computations is an objective way to compare the methods in our setup. It's worth noting that the neural model used for RBE is significantly cheaper in terms of the number of trainable parameters compared with DE and thus for a fixed number of CE calls RBE-based approach cannot be slower than the DE-based. We do not report actual running time since it may depend on various factors not related to the approach itself (like hardware setup, code optimization, near neighbors search algorithm, etc.). We can add this information to Appendix if required, but re-running all the experiments might take significant time (reported experiments were carried out on different hardware, thus should be restarted).

The RBE method requires SI CE calls for each inference, which may represent a significant overhead compared to other methods.

The RBE method requires $m = |S_I|$ CE calls for computing the relevance vector. However, all the methods use the same number of CE calls in total. I.e., if $m$ CE calls are spent on the query embedding, then we use fewer CE calls for the final re-ranking for RBE.

I am not quite understand the statement “DE uses |SI| more CE calls for the re-ranking” in line 470.

As written above, all algorithms use the same number of CE calls in total. If RBE uses $m$ CE calls for the query embeddings and then $K$ CE calls for the re-ranking, then the total budget is $m + K$ which means that DE is allowed to use $m+K$ CE calls for the re-ranking.

Does the Dual Encoder actually use CE calls?

Yes, following the standard approach described in lines 13-18 in the abstract, at the final stage, the top candidates given by the dual encoder are re-ranked with the CE model.

Also, how many CE calls does AXNDE make?

The total number of CE calls is equal for all the algorithms. In the case of AXNDE, there are several iterations and the budget for CE calls is equally divided between the iterations.

Why adding 100 items is considered a fair comparison? Will these additional 100 items be re-ranked using the cross-encoder model? If it's simply expanding the evaluation range, it seems that the choice of 100 as the number is not reasonable.

These 100 (or, in general, $m$) items are used by RBE to compute query embeddings. As written above, the cost of computing these values is taken into account in our comparison and thus we believe that the comparison is fair.

We hope that our responses clarify the details of our comparison, but if any aspects are unclear, we will be happy to continue the discussion.

Why does Table 1 use the QA.small dataset while Table 2 uses the QA dataset?

By using QA.Small in Table 1, we can test more methods including those that do not scale well.

W2: Presentation: the method descriptions in Table 1 and separating the l2-greedy approach from other methods may lead to misunderstandings.

Could you please clarify what can lead to misunderstanding in the table? We will fix this in the revised version of the paper.

W3: Why the AXN model was chosen?

In Yadav et al. (2024) it is claimed that AXN outperforms AnnCUR, so we decided to add this method to our comparison.

W4. How the dimensions in θI were chosen?

The length of the RBE embeddings was chosen to match the length of the DE embeddings in order to provide adequate comparison in Tables 3, 4, 5, 6.

I acknowledge that I have read the responses and would like to keep the ratings.

We would like to thank the reviewer for the feedback and positive assessment of our work!

Regarding scalability and practical applicability, we fully agree that it is an essential question. We would like to note the following:

• Importantly, in practice, one does not have to choose between DE and RBE. As we write in line 300, for RBE, relevance vectors can be enriched with the features of the original query (or item). If a DE is available, it can also be easily combined with RBE as additional features.
• We also discuss various scalability hints in Appendix E.
• We’ve also conducted experiments and compared the results on QA.Small vs QA datasets. We observed that the results did not change significantly after we increased the dataset x10.
• Finally, it seems to be very challenging to objectively compare RBE and DE. While the RBE approach is relatively simple and requires only the CE scores, there are many different DE approaches, they require document and item features, and the best option significantly depends on a particular application.

In Line 166: Authors suggest CUR requires $O(M\cdot Q_{train})$ calls to cross-encoder, but I believe it only requires $O(S_I\cdot |Q_{train}| + S_Q \cdot M)$ calls because C and R matrices are randomly selected rows & columns? I can see $O(S_I\cdot |Q_{train}|)$ part can be reduced to $O(S_I\cdot N)$ in RBE, so I see there can be an improvement of efficiency, but it doesn't seem to be as drastic difference as authors argue.

Yes, the number of calls can be rewritten in this way, however, as we write in lines 162-163, for AnnCUR $S_Q = Q_{train}$, while for RBE we may have $S_Q \subset Q_{train}$. When $S_Q = Q_{train}$, the bounds in the question are equivalent.

Exactly in what sense is Theorem 3.2 stronger than Theorem 3.1

Theorem 3.2 uses fewer assumptions (e.g., the function $R$ is only required to be continuous) and also states stronger convergence (uniform convergence instead of L2-convergence).

Thank you for the review and detailed feedback! We address the questions and concerns below.

There is no timing information for how long it takes to run any of the method variants or the baselines.

In our setup, we assume that the most time-consuming operation is cross-encoder (CE) computation which is the case for real production systems. The computation of CE is time-consuming since the model itself is complex and also some features used by CE may require additional computations (e.g., some features in the RecSys dataset are scores produced by auxiliary neural networks). Thus, in each of the experiments, the number of CE calls is fixed for all the models (and is specified in the text). We think that measuring complexity in the number of CE computations is an objective way to compare the methods in our setup. We do not report actual running time since it may depend on various factors not related to the approach itself (like hardware setup, code optimization, near neighbors search algorithm, etc.). We can add this information to Appendix if required, but re-running all the experiments might take significant time (reported experiments were carried out on different hardware, thus should be restarted).

It's not clear what the architecture of the lightweight neural networks for RBE is? How many parameters are in this neural network?

It is a simple feed-forward MLP with two hidden layers and ELU activations (see line 997). It has about 50K trainable parameters. Note that dual encoders used in practice are typically significantly more complex, e.g., DE from RecSys has ~300M parameters.

It's not clear what the main difference between the result in Theorem 3.1 and Theorem 3.2 is.

Theorem 3.1 has stronger requirements and weaker convergence. Trainable embeddings allow us to soften the requirements (e.g., $R$ can be any continuous function) and prove stronger convergence guarantees (uniform convergence instead of L2 convergence). We will add a comment about this to the text.

It's not clear how the theory in the first part informs the method in the second part.

Could you please clarify what parts of the text you are referring to in this comment? In short, Section 3.2 discusses and formalizes the previously proposed CUR approximation. While the CUR approximation is not novel, the analysis is. Section 3.3 introduces trainable embeddings and shows that they allow us to obtain better convergence guarantees. Our approach uses such trainable embeddings and is motivated by this result.

Lots of terms are undefined. What is $n$ on line 272?

The size of $S_Q$, see line 151.

What is $\hat R$?

In line 320, $R$ is the actual relevance and $\hat R$ is the predicted relevance. We will specify this in the text, thanks for bringing this to our attention.

Explicitly specify what $X$ and $K$ are in tables 4 and 5.

$X$ and $K$ are used to compute HitRate, as specified in the table itself. These parameters range from 100 to 900 (the first row of the table).

The notation in section defining the metric HitRate(P,T) is also very hard to read.

The name HitRate itself is intuitive: it is the hit rate, which means that we retrieve top-P items according to the predicted relevance and check how many of them are in the true top-T list. When used with only one argument $K$, HitRate is computed for $P=T=K$. Do you have any specific questions or suggestions regarding this notation? We are happy to discuss and clarify in the text.

How does this method perform on other retrieval benchmarks like BEIR and NQ?

We have not experimented with these datasets. Note that our experiments cover all datasets used in the related work by Yadav et al. (2022) and also include the QA dataset based on MSMarco and three new datasets based on real recommender services.

Will the RecSys and RecSys2 datasets be publicly released?

Yes, as written in line 377, the data will be released with the final version of the paper.

Why is RBE so much better on Recsys2 when compared to any other dataset?

Note that RecSys2 significantly differs from the other datasets. In particular, it is obtained from a different source compared to RecSys/RecSysLT datasets and thus some difference in performance can be expected. However, we have not investigated this subject deeper. Note that on Yugioh and QA, the difference is also noticeable.

The CUR approximation requires computing the matrix $R(I,Q_{train})$. This is very expensive. RBE doesn't need to compute this matrix, right? Does that mean RBE can scale to larger datasets?

Yes, as mentioned in line 1114, RBE with learnable document vectors can be trained similarly to DE on sparse data and thus can scale to larger datasets. We will add a more detailed comment to the text.

For the l2-greedy approach isn't it very expensive to optimize over all possible choices of $S_I$. How long does this take in practice?

Note that l2-greedy is a greedy algorithm thus it does not perform exhaustive search over all possible choices of $S_I$. As written in lines 256 and 266, it greedily selects items one by one. A detailed procedure of how each item is selected is described in Appendix B. In l2-greedy experiments, the choice of support items takes tens of minutes on our hardware, but we have not measured or optimized it as we used different hardware for different experiments. Also, l2-greedy is a part of the pre-processing stage and thus does not affect the query time.

Dear Reviewer Ujqc,

We would like to ask whether our response addresses your concerns. Also please note that we updated the paper taking into account the comments of the reviewers. If you have any additional questions or concerns, we will be happy to address them.

Thank you for suggesting these references. However, while these works may seem similar to our study (due to somewhat similar keywords), they are not relevant to our setup.

Recall that our setup is the following. We assume that there is a heavy ranker (cross encoder, CE) that provides relevances of query-item pairs. This heavy ranker can be an arbitrary complex model and is a standard ingredient of a recommender system. Due to the dataset size, CE cannot be computed for all user-item pairs. A standard approach then is to approximate CE with a dual encoder (DE) that embeds queries and items to a space where relevances can be (approximately) computed via, e.g., the dot product. We improve over this standard approach (and simplify it) by creating more efficient representations of queries and items (via support items and support queries, respectively) that do not require training a (potentially complex) DE model (RBE is much smaller, several orders of magnitude in the number of trainable parameters).

Now, consider the work by Sukhbaatar et al. (2015). Here, supporting facts are used but they significantly differ from our support items. Indeed, supporting facts are obtained externally and they are different for different queries. In our case, support items are taken from a given set of items and they are fixed for all the queries (thus, they allow us to create a common representation for all queries). See Figure 2 and Appendix B in Sukhbaatar et al (2015) for illustrations.

Regarding Mohan et al. (2024), this work uses external information to enrich document representations, while we only use CE which is a part of any recommender system. As above, this external information is different for different documents, while we use a fixed set of 100 queries to describe each document. See the abstract and Table 2 of Mohan et al. (2024) for details.

In summary, we cannot relate the referred papers to the setup considered in this paper (both general setup and algorithm details). We will be happy to provide a more detailed discussion and comparison if you could give us more details on why these works are relevant and in what form they can be applied to our setup.

If you have any feedback, concerns, or questions regarding our work, we will be happy to address them.