Relevance-based embeddings for efficient relevance retrieval

We just noticed that the initial rating changed from 8 while we were writing the answers, although the review remained the same - we would be very grateful if you could clarify the motivation.

Thank you for your review and suggestions!

W: The 7 datasets that you are using are extremely small in size (the largest has only 104K items)

And

W: You should add as additional datasets at least one large-size Question Answering domain; this would show that (i) your approach can scale, and (ii) your approach also applies to one of the most-studied problems of the last few decades

We agree that adding a larger dataset would be useful for the paper. We are working on adding the MsMarco dataset, as suggested by Reviewer UmnS. However, there is a question of whether we will manage it during the discussion period since time limitations are quite challenging.

W: Related to the issue above, please explain whether (and how) your approach can scale to 10 B items (i.e., up to 5 orders of magnitude)

Let us consider separately the selection of the key elements, training and inference:

Key Selection:

Since different clusterization approaches have shown near-optimal quality, there are different options for scalable clustering:

• Clusterization on downsampled datasets: for extremely large (and dense) datasets it is natural to expect that cluster structure could be inferred from a significantly smaller subsample (according to the authors' experience, on the data of ads recommendation systems with billions of banners and downsampling to millions, this is so)

Even for our research (small) datasets downsampling 75% of data reduces the quality of key selection in a discussable way:

We are going to provide a detailed trade-off in the supplemental materials.

• Using data-driven clusterization: as shown in the third row of Table 2, choosing popular items from different categories/genres (in our case the global top of popular items is almost uniformly diversified) works extremely well.

• Using a distributed clustering algorithm

Training:

As discussed in Sections 3.3 and 4.1.4, the training of such a model does not significantly differ from any dual-encoder-like models (which are commonly used in production recommendation services) with relevance vectors as inputs. The only major difference is that relevances to fixed support items should be provided. Let us also note that efficient sampling of negative samples for the loss function should be used in order to train on such large datasets.

Inference:

It is also similar to dual-encoders: the item representations are precalculated and placed in the Approximate Nearest Neighbours index like HNSW, which accepts the embedding of the query as input. The other comments are about readability, text and language issues. We will correct the corresponding parts in the revised text. Thank you for the extremely detailed feedback, it really allows you to make the text better!

Q:Please explain why are you using only 5 of the 16 domains in ZESHEL

In our experiments on public datasets, we follow the setup of Yadav et al. (2022) and use the same datasets - please, see Section B.3 of their paper.

We hope that our response addresses the concerns.

Thank you again for your detailed feedback! We updated the paper accordingly. This comment summarizes our updates. We also conducted the experiments on the MsMarco dataset, the results are consistent with those reported in the paper, see this comment for the details.

We will be happy to hear your thoughts regarding our reply and updates.

Thank you for your review and suggestions!

How to make the work practical seems to be the number one weakness. Though it's proved that such decomposition exists, finding those embedding mapping for Q and I can be very difficult. I'm looking for a more rigorous way to do that. For example, how to set the right dimension and have the confidence that the dimension is good enough the meet the approximation error \epsilon. How to set the right \epsilon and knowing it's small enough to ensure the retrieval quality is better than existing method e.g. from a set of embedding learned just for the retrieval stage.

In practice, the overall time limitations (i.e., the CE call budget, since the overall time complexity depends on it) are set externally and are determined, for example, by the response timeout of a recommendations service. Given the overall CE call budget, the number of key items could be selected similarly to any other hyperparameters like the dual encoder embedding size. In our experiments, we fixed the embedding size to 100 which already gives performance improvements.

Rewriting the paper into the standard retrieve-and-rank language would help.

Thank you for the suggestion, we can add such an interpretation to the text or use this terminology if required. Could you, please, specify, what terminology you suggest (i.e., what do you think we should use instead of "queries", "items", and "relevance").

In the experiment part, the latency or other system related metrics should be reported as well. The number of items retrieved could be tuned based on the retrieval stage quality as well as the system constraint. Directly comparing the proposed embedding with other baselines may not be helpful. They can easily be used to retrieve different number of items before reranking.

In both ZESHEL and RecSys data, t(heavy ranker/cross encoder call) > t(dual encoder part call) >> t(dot product or tiny $f_Q$, $f_I$ MLPs). The item/document representations for AnnCUR/RBE and the dual encoder are offline-precalculated and do not cost any additional time per query. Once the dual encoder or AnnCUR/RBE query part is calculated, the calculation of relevance for any item is just a dot product calculation, which is much faster than one CE call.

Finally, if we have K items on the final stage of ranking, the overall time consumption is equal to:

• K CE calls
• 1 DE/RBE/AnnCUR query representation calculation: for RBE and AnnCUR it includes several CE calls that we take into account in our comparisons
• Dot product calculations that are altogether significantly cheaper than CE calls for any reasonable K (~hundreds-thousands)

That's why we and the authors of AnnCUR measure the overall performance in terms of “fixed CE calls budget”. For our Tables 2-3, we compare the methods with the same CE calls (top size). For our Tables 4-5, we also evaluate both methods with the same CE calls: the top size for DE is larger since RBE uses 100 calls per query for the relevances calculation. We could provide the exact timings for each model, but in both cases the overall complexity of recommendations will be equal to the CE calls time + eps.

The writing in section 4 seems much worse compared to the previous sections. There are details or intuitions lacking (potentially due to page limit).

We will update this section in the revised version of the paper.

Also adding multi-modal datasets e.g. video-language retrieval could help strengthen the paper.

Let us note that the items in RecSys/RecSysLT datasets are described by texts, table data and images. All these sources of information are used as inputs for both DE and CE. If we misunderstood your comment, please correct us.

Please note that we updated the paper according to the comments from the reviewers. This comment summarizes our updates. We also conducted the experiments on the MsMarco dataset, the results are consistent with those reported in the paper, see this comment for the details.

We will be happy to hear your feedback regarding our reply and updates.

Thank you for your review and suggestions!

W: Is it feasible to apply the author's method to different types of datasets, such as "question-answer datasets"?

Since we applied the method to a recommendation task (RecSys/RecSysLT datasets), it seems to be suitable for any similar information retrieval task. Moreover, we are working on adding the MsMarco dataset suggested by Reviewer UmnS. However, there is a question of whether we will manage to finalize it during the discussion period. Otherwise, we will add the results to the camera-ready version.

W: …the performance improvement shown in the table from AnnCUR+KMeans to RBE+KMeans is somewhat modest…

First, let us note that AnnCUR+KMeans is already a strong baseline - the original AnnCUR uses the random selection of key items and we show that it can be significantly improved, which is an important part of our contribution (together with the theoretical analysis). When comparing the proposed method with previous works (i.e., with AnnCUR), we see that, e.g., on the Star Trek dataset, RBE+KMeans has almost 1.5 times greater performance than AnnCUR (0.23 -> 0.34 HiteRate), on other datasets the improvements are also noticeable.

We add AnnCUR+KMeans to our experiments in order to show that both our improvements (selection of key items and aggregation of their relevance using $f_Q$, $f_I$) give some profit. As we write on page 6, the purpose of the experiments with relevance aggregation is to show that even the use of trivial transformations $f_Q$ and $f_S$ allows one to get some profit. Since we use really simple MLP-based transformations and do not aim to find the best practical option (over a proof-of-concept), we consider this result acceptable. Some options for increasing this profit in practical applications are described in Section 3.3, but since they are more practical than theoretical and depend significantly on the data set and subject area, we have not experimented with them.

W: Although efficiency is a noted advantage of dual-encoder based methods, employing a large set of support items can also lead to substantial computational complexity. Would it be possible to conduct a comparison of efficiency between the author's method, dual-encoder, and cross-encoder, along with a comparison of their respective accuracies?

In both ZESHEL and RecSys data, t(heavy ranker/cross encoder call) > t(dual encoder part call) >> t(dot product or tiny $f_Q$, $f_I$ MLPs).

The item/document representations for AnnCUR/RBE and the dual encoder are offline-precalculated and do not cost any additional time per query.

Once the dual encoder or AnnCUR/RBE query part is calculated, the calculation of relevance for any item is just a dot product calculation, which is much faster than one CE call.

Finally, if we have K items on the final stage of ranking, the overall time consumption is equal to:

• K CE calls
• 1 DE/RBE/AnnCUR query representation calculation: for RBE and AnnCUR it includes several CE calls that we take into account in our comparisons
• Dot product calculations that are altogether significantly cheaper than CE calls for any reasonable K (~hundreds-thousands)

That's why we and the authors of AnnCUR measure the overall performance in terms of “fixed CE calls budget”. For our Tables 2-3, we compare the methods with the same CE calls (top size). For our Tables 4-5, we also evaluate both methods with the same CE calls: the top size for DE is larger since RBE uses 100 calls per query for the relevances calculation.

We could provide the exact timings for each model, but in both cases the overall complexity of recommendations will be equal to the CE calls time + eps.

Q: At the conclusion of page 6, I found myself confused about the necessity for concatenating R(SI, q) with F(R(SI, q), θ). What is the rationale behind not solely utilizing the second term?

The initial intuition was that the <$f_I$(...), $f_Q$(...)> expression splits into two terms - the prediction of AnnCUR and the trainable prediction of its error (thank you for pointing out that we forgot to specify this in the text - it will be added). In the experiments, such additions improved the convergence and training stability. Moreover, since we have used $|S_I$| CE calls to calculate R(S_I, q), the computational complexity of this term is insignificant.

As you suggested, we trained RBE without the first term on the RecSys dataset and achieved better test quality (~ +0.01 HR, all other parameters are the same), so, in some cases, it may even improve the quality. We will try to add a similar comparison for other datasets in the final version of the paper.

Note that many other improvements can be proposed here, but, as mentioned earlier, our goal was to show the possibility of making a profit for the idea as a whole, and not to go into the search for various modifications of the architectures allowed here.

Q: Regarding Theorem 1, is there any limitation on the sizes of SQ and SI? The guarantee of expressivity may become insignificant if SQ or SI encompasses the entire dataset.

As mentioned in Section 3.3, there are practical examples, where the query set Q is infinite - text search or any recommendation tasks with floating number factors in query/user. Under this setting, the result is non-trivial. We need more time to think about estimates of the sizes, if we come up with some new results - we will extend our reply.

Thank you for your review and suggestions!

Q: There can be certain tail queries that are highly relevant to non support items. How does their representation get affected?

To check the performance on such tail queries, we explicitly sorted the test queries from the RecSysLT dataset by their maximal relevance to key items (selected by the KMeans algorithm) and measured the quality on four different parts of the test data. The obtained results for different algorithms are presented in the table below (HitRate@100 on subsample / HitRate@100 on the entire test sample * 100%):

Note that for the more relevant half, the quality is better for all algorithms, including Dual Encoder, which does not use key elements in any way. This may be a consequence of the fact that the less relevant half is represented by those queries that we generally know less about and thus give worse recommendations. Another observation is that in the best quarter, the quality of 3 algorithms becomes worse than average, which is an unexpected result.

We hope these results address the question and we plan to add a similar analysis for all the datasets to the supplemental material.

Q: How does RBE based embedding works for ranking in MsMarco query-passage/document datasets?

Thank you for this suggestion. We are currently working on additional experiments with this dataset. This would take some time, we hope that it will be finished during the author feedback period, but otherwise we will add the results to the camera-ready version of the paper.

Q: It will be nice to have a detailed differentiation and comparison between RBE and matrix factorization.

Most matrix factorization methods (for example, the matrix factorizations of user-to-item ratings matrix) could not operate with new queries/users effectively since new rows require factorization of this new matrix which is not applicable to online recommendations, while RBE can handle new queries since it the relevances to key items (according to the heavy ranker) can be evaluated online.

We could evaluate a matrix factorization method by masking all relevances of test queries except for the key (support) items and trying to reconstruct the rest. Do you think that this experiment will be helpful for supporting our claims?

If we misunderstood your question, please correct us.

Thank you for suggesting the MsMarco dataset. We conducted preliminary experiments on this dataset and plan to add the complete results to the final version of the paper. The results are consistent with those reported in the paper, see this comment for the details. We also updated the paper according to the comments of the reviewers, this comment summarizes our updates. We will be happy to hear your feedback regarding our reply and updates.