Efficient k-NN Search with Cross-Encoders using Adaptive Multi-Round CUR Decomposition
Authors: Nishant Yadav
Nicholas Monath
Manzil Zaheer
Andrew McCallum
Venue: EMNLP 2023 Findings (2023)
Keywords: cross-encoder
nearest neighbor search
k-NN
retrieval
TL;DR: Propose a kNN search strategy that retrieves based on approximate cross-encoder scores over multiple rounds while improving cross-encoder approximation in each round using retrieved items

Abstract: Cross-encoder models, which jointly encode and score a query-item pair, are prohibitively expensive for direct k-nearest neighbor (k-NN) search. Consequently, k-NN search typically employs a fast approximate retrieval (e.g. using BM25 or dual-encoder vectors), followed by reranking with a cross-encoder; however, the retrieval approximation often has detrimental recall regret. This problem is tackled by ANNCUR (Yadav et al., 2022), a recent work that employs a cross-encoder only, making search efficient using a relatively small number of anchor items, and a CUR matrix factorization. While ANNCUR’s one-time selection of anchors tends to approximate the cross-encoder distances on average, doing so forfeits the capacity to accurately estimate distances to items near the query, leading to regret in the crucial end-task: recall of top-k items. In this paper, we propose ADACUR, a method that adaptively, iteratively, and efficiently minimizes the approximation error for the practically important top-k neighbors. It does so by iteratively performing k-NN search using the anchors available so far, then adding these retrieved nearest neighbors to the anchor set for the next round. Empirically, on multiple datasets, in comparison to previous traditional and state-of-the-art methods such as ANNCUR and dual-encoder-based retrieve-and-rerank, our proposed approach ADACUR consistently reduces recall error—by up to 70% on the important k = 1 setting—while using no more compute than its competitors.

Efficient '-NN Search with Cross-Encoders using Adaptive Multi-Round CUR Decomposition
Nishant Yadav!, Nicholas Monath 9 Manzil Zaheer and Andrew McCallum
University of Massachusetts Amherst Google Research (nishantyadav, mccallum)@cs, umass. edu
[nmonaat, www.aaaaaaaaae.a Jogoolee..co
Abstract
Approcimate
1-10
101-500
Ancher here
Top & Items
11-100
301+
Cross-encoder models, which jointly encode and score a query-item pair, are prohibitively expensive for direct k--earest neighbor (k-NN) search. Consequently, k-NN search typically employs fast approximate retrieval (e-g- using BM25 or dual-encoder vectors), followed by reranking with a cross-encoder; however, the retrieval approximation often has detrimental recall regret. This problem tackled by AN- NCUR (Yadav et al., 2022), recent work that employs a cross-encoder only, making search efficient using relatively small number of an- chor items, and a CUR matrix factorization. While ANNCUR's one-time selection of an- chors tends to approximate the cross-encon enssder distances on average, doing forfeits the ca- pacity to accurately estimate distances to items near the query, leading to regret the crucial end task: recall of top-k items. In this paper, propose ADACUR, method that adaptively, it- eratively, and efficiently minimizes the approxi- mation error for the practically important top-k neighbors. does so by iteratively performing k-NN search using the anchors available so far, then adding these retrieved nearest neighbors to the anchor set for the next round. Empirically, on multiple datasets, comparison to previous traditional and wate-of-the-ate methods such as ANNCUR and dual-encoder- based retrieve- and-rerank, our proposed approach ADACUR consistently reduces recall error-by up to 70% on the important more compute than its competitors.
Approsimate Scores
Approximate, Scores
Exact Scores
Exact Scores
(a) Uniformly random
(b) Biased sampling
Figure Exact versus approximate cross-encoder scores (computed using ANNCUR) of all items for test-query in domain=YuGioh, ANNCUR incurs high approximation error on k-NN items wrt exact scores when using 50 anchor items sampled uniformly at ran- dom (Fig. la). In contrast, sampling 50 anchor items with probability proportional to exact cross-encoder scores (Fig. lb) sigmificantly improves approximation of top-scoring items.
given query-item pair. However, computing a sin- gle query-item score using cross-encoder requires forward pass of the model which can be compu- tationally expensive cross cross-encoders typically parameterized using deep neural models such transformers (Vaswani al., 2017). For this rea- son, N-NN search with cross-encoder typically invol ves retrieving candidate items using additional models such dual-encoders BM25 (Robertson et al., 2009), followed by re-ranking items using the cross-encoder (Logeswaran al., 2019; Zhang and Stratos, 2021; Qu al., 2021). However, the accuracy of such retrieve-ande aaneevev-nddrerann approaches is upperbound by the recall of first-stage retrieval and may require computationally expensive distillation- based training dual-encoders to improve recall.
setting-wiin while using
1 Introduction
k-nearest neighbor (k-NN) search is core sub- routine of variety of tasks in NLP such as en- tity linking (Wu al., 2020), passage retrieval for QA (Karpukhin et al., 2020), and more generally. in retrieval- auggentte machine lcarning models (Guu et al., 2020; Izacard et al., 2023). For many these applications, the state-of-the-art similarity function a cross-encoder that directly outputs a scalar similarity score after jointly encoding a
Recent work by Yadav et (2022) proposed ANNCUR, a CUR factorization (Mahoney and Drineas, 2009) based method, that approximates cross-encodes using dot-product of latent query and item embeddings and performs k-NN retrieval using approximate scores followed by option- ally re-ranking retrieved items using exact cross-

---

encoder scores. The latent item embeddings are computed by comparing each item against set of anchor queries, and the latent query embedding is computed using the query's cross-encoder scores
Algorithm 1 ADACUR K-NN Search
1: Input: (frest? Ruse NR, Bee.
2: Grest" Test query
3: Ran: Matrix containing CE scores between Qenin and I
4: Bes: Total cross-encode (CE) call budget.
against fixed set of anchor items. As shown in Figure I, when ANNCUR selects the anchor items uniformly at random (Fig la), incurs higher ap- proximation error on the top-scoring items than the rest of the items, resulting in poor k-NN recall, and including some k-NN items as part of anchor items (Fig. 1b) can significantly improve approxi- mation error for top-scoring items.
5: A: Algorithm to use for selecting (anchor) items.
6: NR: Number of iterative search rounds
7: Output: S: Approximate scores of lustt with all items,
Lane: Retrieved (anchor) items with CE scores in Cus-
he + Bee/NR E Num. of items to sample per round Zane +- INIT(Z, ki)
D> Initial set anchor items
10: Gun + [Sa(uust i]kk Fure Do CE scores of Tane for Prst
11: for j + 2to NR. do
12: U + Raad [Tane]
Do U E ER [g] | $C) +- Cus x U x Pune Do Update approx. scores
In this work, we propose ADACUR, a search strategy that improves k-NN search recall by im- proving the approximation of top-scoring items. ADACUR performs retrieval over multiple rounds, retrieving the first batch of items either uniformly at random or using heuristic or auxiliary mod- els such as dual-encoder or BM25 to get a first coarse approximation of item scores for the test query. In subsequent rounds, it alternates between a) performing retrieval using approximate scores and scoring retrieved items using cross-encoder and b) using all retrieved items as anchor items to improve the approximation and hence retrieval of relevant items in the subsequent rounds. Our proposed approach provides significant improve- ments k-NN search recall over ANNCUR and approaches
13:
14:
T SAMPLEITEMS(AL Ke, Tone, Ione; 861)
15: Iane + Inn U UI
16: Ciea + Cuu @ [fol Me
D Update Clea
17: U Rume [Ime]]
U E Rl
18: $ + Cwe x U x Rax
D Compute approx, scores
19: return S, Jones Crest
Al Algorithm 2 SAMPLEITEMS
1: Input: (A,, Tarek
2: A: Algorithm for sampling items
3: k.: Number of items to sample
4: Toas : Set of items to mask
5: S: (Approximate) Scores for all items
6: Output: Irarett Set of sampled k, items
+ SOFTMAX(S)
S [[aaa]] <
D> Mask items in Tanck
if Topk then
dual-encoder based when performing k-NN search with cross-encoder models trained for the task of entity linking and information retrieval.
10: Isolect <- TOPK(S, k.))
11: else if Sof then
12: Iaalect <- k. items sampled using 5
13: AA Random then
14: Ircrect + ke items uniformly sampled from Taask
15:
return Ieclect
2 Proposed Method: ADACUR
Task Given a scoring function fo: Q IR that maps query-item pair scalar score, and query g Q, the k-nearest neighbor search task is retrieve top-k scoring items from fixed item set I according to the given scoring function fe.
[Tace] -imeendimeaio vector containing cross-encoder
scores of Itest with a set anchor items (Ianc) as:
Cotest
[fe(Icest i))
Cxrest
Cftest
x
2.1 ADACUR: Offline Indexing of Items
where U E aanc (Quaial is the pseudo-inverse of Rane [Tane]. the subset of columns of Rane cor- responding (anchor) items Ianc- Finally, AN- NCUR approximates the score for a query-item pair (ftest i) using dot-product of the query em- bedding e Btett and item embedding E
The indexing step of ADACUR involves using the cross-encoder model (fe) to score each item against fixed set of ki anchor/train queries (Qurain), get score matrix Rane
Rane (g, i) = -e(gg i), ((g,z) Quein x I
Each column of ET = Rane X corre- sponds to a kig dimdennniooa latent item embedding.
folotest 1)
- G9tsst
FT [1
The main bottleneck at test-time inference is the number of items scored using the cross-encoder for the given test-query. For given budget of cross- encoder calls, ANNCUR splits the budget (Ber)
2.2 ADACUR: Test-time inference
The baseline method ANNCUR computes the la- tent test-query embedding Grest using Catest" a
C

---

into two parts it uses &; cross-encoder calls to compare against anchor items (chosen uniformly at random or using heuristic methods) and retrieves BEE k items using approximate scores and re- ranks them using exact cross-encoder scores.
ing k-NN cross-encoder items, For each ZESHEL domain, we randomly split the query set into a train/anchor set (Qtrain) and a test set (Qtest while for BEIR domains, we use pseudo-queries released as part of the benchmark as train/anchor queries and evaluate on queries in the official test split. We refer the reader to Table 1 for additional details.
In contrast, our proposed approach ADACUR uses the cross-encoder call budget to adaptively retrieve and score items over NR rounds, re- purposing the retrieved items as anchor items as shown in Algorithm 1. ADACUR begins by sam- pling the first batch of kg = BCE/NR (anchor) items uniformly at random. The first batch of items can also be selected using baseline retrieval meth- ods such as BM25 and dual-encoders. In the jth round, the items retrieved up to round j-1 are used as anchor items to revise the test-query embedding. which in turn is used to update the approximate scores (line 13 in Algorithm 1). Finally, the items selected so far are masked out and the next batch of ks items in round j is retrieved using the updated approximate scores in the following two ways: Topk: Greedily pick top-ks items according to approximate scores.
We compare our proposed approach with the following baseline retrieval methods.
Baselines
Dual-Encoders (DE): Query-item scores are com- puted using dot-product of embeddings produced by learned deep encoder model. DE is used for initial retrieval followed by re-ranking using the cross- cross-encoder. We report results for DEBASE, a dual dual-encoder trained on training domains in the corresponding dataset, and the following two dual- encoder models trained on the target domain via distillation using the cross-encoder.
DEBERT' DE initialized with BERT (Devlin et al., 2019) and trained only the target do- main via distillation using the cross-encoder.
tMat Convert approximate item scores into probability using softmax and sample k, items without replacement.
DE DEBASE model further fine-tuned on the target domain via distillation.
ANNCUR: k-NN search method proposed by Ya- dav et al. (2022) where anchor items chosen uniformly at random. We additionally experiment with ANNCUR which uses top-scoring items retrieved using DE anchor items.
Finally, ADACUR returns top-k items based on ex- act cross-encoder scores' from the set of retrieved (anchor) items as approximate k-NN items. We refer interested readers to Appendix B.5 for a dis- cussion on the time complexity of ADACUR.
Evaluation Metric Following the precedent set by previous work (Yadav al., 2022), evaluate all approaches using Top-k-Recall BeE which is defined as the fraction of k-NN items retrieved under test-time cost budget BeE where the cost is defined as the number of cross-encoder calls made during inference. DE baselines will use the entire budget of BeF calls for re-ranking retrieved items using exact cross-encoder scores, ANNCUR splits the budget between scoring anchor k; items and using exact cross-encoder scores for re-ranking BeE - k, retrieved items, and ADACUR use the budget to adaptively search for K-NN items.
3 Experiments
In our experiments, evaluate the proposed ap- proach and baselines on the task of finding k- nearest neighbor items per a given cross-encoder. We experiment with two cross-encoders one trained for the task of zero-shot entity linking, and another trained on information retrieval datasets.
We run evaluation on do- mains YuGiOh, StarTrek, and Military from ZESHEL-a zero-shot entity linking dataset (Lo- geswaran et al., 2019), and domains SciDocs and HotpotQA from BEIR-a zero-shot information re- trieval benchmark (Thakur et al., 2021). We use two cross-encoder models trained on labeled training data from the corresponding benchmark and evalu- ate separately on each domain on the task of find-
Experimental Setup
For ADACUR, unless noted otherwise, we use NR = with Topk method for retrieving items us- ing approximate scores, and retrieve the first batch of items uniformly at random (ADACUR) or using DESSS (ADACURgewe)) We refer readers to Ap- pendix for implementation details and details on training and parameterization of cross-encoder and dual-encoder models used in our experiments.
'Sorting retrieved items based exact cross-encoder scores does not require any additional pross-encoder calls as cross-encoder scores for these items have already been computed (see line 16 in Algorithm 1).

---

DE
DE
ANNCUR
ANNCUR Repser
Proposed
ADACUR
ADACUB
k=
A=10
k 100
Top- Top-A-Red I--Recall
50
100
200
500
50
100
200
500
200
500
1000
Inference Cost (Total Number of Cross-Encoder Calls)
Figure 2: Top-k-Recal for ADACUR and baselines for domain=YuGioh, Qmian 500. ADACUR consistently outperforms corresponding ANNCUR variant and ADACUR outperforms all DE-based retrieve-and-rerant approaches including DE a DE model trained via distillation on the target domain using the cross-encoes eoosee..
3.1 Results
Rounds
10
k==0
ADACUR versus baselines Figure 2 shows Top-k-Recall for ADACUR and basclines do- main=YuGiOh. ADACUR, which uses adaptively re- trieved items as anchor items over NR rounds, consistently outperforms ANNCUR which selects all anchor items uniformly random. ADACUR also outperforms strong DE baseline DE for all values of k and outperforms DEBASE & DE for large values of k 10, 100.
100
Top Recall
500
Inference Cost (Total Number of Cross-Encoder Calis)
Figure 3: Top-k-Recall for ADACUR different num- ber of rounds for domain=YuGiOh, |Qrain
500.
Total
CroosEnn Call
Matric Multiply
Matrix Insems
Sampling anchor items using DEBASK For
#
Cals-500
Infeemee Laterry (jn=)]
k = 10, Top-k-Recall for both ANNCUR and ADACUR can be further improved by leveraging baseline retrieval models such as DE for re- trieving all and the first batch of anchor items respectivcly instead of sampling them uniformly at random. ADACURpE UpESs always performs better than ANNCUR DERAS which in turn performs better than re-ranking items retrieved using DEBASE Thus, for given cost budget (Bсr), even when strong baseline retrieval model such DEBASE is avail- able, using the baseline retrieval model to select the first batch of BCE/NR items followed by using the proposed approach to adaptively retrieve more items over remaining NR. rounds performs better than merely re-ranking BeE top-scoring items retrieved using DEBASE- Finally, note that ADACURDF outperforms all baselines including DE which requires additional compute- and resource-intensive. distillation-baal fine-tuning of DEBASE on the target domain.
10f
0.76
0,30
2
10
1
10
20 50
100
5 10
20
50
100
0.00
Number of Rounds
Figure 4: ADACUR inference latency versus number of rounds for domain=YuGioh, @
500.
Effect of number of rounds Figure 3 shows Top- k-Recall and Figure 4 shows total inference latency of ADACUR on primary y-axis for various values of the test-time cross-encoder call budget (BEE). The secondary y-axis in Figure 4 shows the frac- tion of total inference time spent on each one of the three main steps Algorithm ing U as pseudo-invers of R [ane (line 12), (b) updating approximate scores for all items (line 13), and (c) computing exact cross-encoder scores for retrieved items (line 16). Since ADACUR selects items uniformly at random the first round, ADACUR with NR performs poorly as it sim- ply returns a subset items sampled uniformly at random. As expected, Top-k-Reco Recalll for ADACUR increases with the number of rounds and saturates
(a) comput-
We refer the reader to Appendix for results on other domains, training data size ( (uraii)) values, oracle-based sampling experiments ($C.2), and ad- ditional results for mulli-vector encoder ($C.3) and TF-IDF (SC.4) baselines.

---

around 5-10 rounds while incurring negligible overhead in inference latency. As shown in Fig- ure 4, crosseencoder score computation is the main bottleneck in lest-time inference, taking ~ per score?. Increasing NR. to large values such as 100 can incur up to 25% overhead with step (a) con- tributing significantly to this overhead. Although the time taken by matrix multiplication step (b) is linear in the number items in the domain, we observe that it is a negligible fraction of overall latency on GPUs even for Hotponn with 5 million items (see Figure 5) as GPUs can enable significant speedup even for brute-force computa- tion this step.
and error tendencies, and it is unclear if pro- posed method to approximate cross-encoder scores exacerbates or mitigates such biases.
Acknowledgments
We thank members of UMass IESL for helpful dis- cussions and feedback. This work was supported in part by the Center for Data Science and the Cen- ter for Intelligent Information Retrieval, in part by the National Science Foundation under Grant No. NSFI763618, 8,, in part by the Chan Zuckerberg Initiative under the project "Scientific Knowledge Base Construction", in part by International Busi- ness Machines Corporation Cognitive Horizons Network agreement number W W1668553, in part by Amazon Digital Services, and part using high- performance computing equipment obtained under a grant from the Collaborative R&D Fund managed by the Massachusetts Technology Collaborative. Any opinions, findings, conclusions, and recom- mendations expressed in this material are those of the authors and do not necessarily reflect those of the sponsor(s).
4 Conclusion
In this paper, we presented an adaptive search strat- egy that incrementally builds a query embedding to approximate cross-encoder scores and performs k-NN search using approximate scores over several rounds. Our approach is designed to reduce approx- imation error for the top-scoring items and hence improves N-NN search recall when retrieving items based on the approximate scores. We perform an in- depth empirical analysis of the proposed approach in terms of both retrieval quality and efficiency.
References
Payal Bajaj. Daniel Campos, Nick Craswell, Li Deng. Jianfeng Gao. Xiaodong Liu, Rangan Majumder, Andrew McNamara, Bhaskar Mitra, Tri Nguyen, et al. 2016. MS-MARCO: A human generated ma- chine reading comprehension dataset. arXiv preprint 1rXiv:1611.099
Limitations
Building the index for the ADACUR is more ex- pensive than the traditional dual-encoder index due to the computation of dense cross-encoder scores matrix (see $2.1). We have successfully our approach on up million items, but scaling to billions of items is an interesting direction for fu- ture work. mual-encoder-based retrieve-and-rerae baseline approaches can benefit from training the not clear
Jacob Devlin, Ming-Wes Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: Pre-training of deep bidirectional transformers for language under- standing. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Tech- nologies.
dual-encoder on multiple domains. if data from multiple domains can be leveraged to improve performance of the proposed approach on a given target domain; although in any case, cross- encoders tend to be more robust to domain shift than using only dual-cncoders for retrieval.
Kelvin Guu, Kenion Lee, Zora Tung, Panupong Pasu- pat, and Mingwei Chang. 2020. Realm: retrieval- augmented language model pre-training. In Interna- tional Conference on Machine Learning.
Sebastian Hofstätter, Sophia Althammer. Michael Schröder, Mete Sertkan, and Allan Hanbury. 2020. Improving efficient neural ranking models with cross-architecture knowledge distillation. ArXiv. abs/2010.02666.
Ethics Statement
this paper we tackle the task of finding k-nearest neighbor items for given query when query-items items scores are computed using a black-box -bx similarity function such as a cross-encoder model. The cross- encoder scoring function may have certain biases
Gautier Izacard, Patrick Lewis. Maria Lomeli, Lucas Hosseini, Fabio Petroni, Timo Schick, Jane Dwivedi- Yu, Armand Joulin, Sehastian Riedel, and Edouard Grave. 2023. Atlas: Few-shot learning with retrieval augmented language models. Journal of Machine Learning Research, 24.
FFor a 12-layer transformer model on an Nvidia 2080ti

---

Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov. Danqi Chen, and Wen-tau Yih. 2020. Dense passage retrieval for open- domain question answering. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP).
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. Advances in Neural Information Process- ing Systems.
Wenhui Wang, Furu Wei, Li Dong, Hangbo Bao, Nan Yang, and Ming Zhou. 2020. Minilm: Deep self- attention distillation for task-agnostic compression of pre-trained transformers. Advances in Neural In- formation Processing Systems.
Omar Khattab and Matei Zaharia. 2020. ColBERT: Effi- cient and effective passage search via contextualized late interaction over bert. In ACM SIGIR Confer- ence on Reseurch and Development in Information Retrieval.
Ledell Wu, Fabio Petroni, Martin Josifoski, Sebastian Riedel, and Luke Zettlemoyer. 2020. Scalable zero- shot entity linking with dense entity retrieval. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP).
Zhenzhong Lan, Mingda Chen, Sehastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. 2020. Albert: A lite bert for self-supervised learning of language representations. In International Confer- ence on Learning Representations, ICLR.
Nishant Yadav, Nicholas Monath, Rico Angell, Manzil Zaheer, and Andrew McCallum. 2022. Efficient near- est neighbor search for cross-encoder models using matrix factorization. In Proceedings of the 2022 Con- ference on Empirical Methods in Natural Language Processing.
Lajanugen Logeswaran, Ming-Wes Wei Chang, Kenton Lee, Kristina Toutamova, Jacob Devlin, and Honglak Lee. 2019. Zero-shot entity linking by reading entity de- scriptions. Proceedings of the 57th Annual Meet- ing of the Association for Computational Linguistics.
Nya Loshchilov and Frank Hutter. 2019. Decoupled weight decay regularization. In International Confer- ence on Learning Representations, ICLR.
Wenzheng Zhang and Karl Stratos. 2021. Understand- ing hard negatives in noise contrastive estimation. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computa- tional Linguistics: Human Language Technologies.
Xinyin Ma, Yong Jiang, Nguyen Bach, Tao Wang. Zhongqiang Huang, Fei Huang, and Weiming Lu. 2021. MuVER Improving first-stage entity retrieval with multi-vien entity representations. In Proceed- ings of the 2021 Conference on Empirical Methods in Natural Language Processing.
A
Appendix A
B
Training and Implementation Details
All the code for reproducing experiments is avail- able at
Michael W Mahoney and Petros Drineas. 2009. Cur matrix decompositions for improved data analysis. Proceedings of the National Academy of Sciences, 106:697-702.
com//es///nmmurrr
B.1 Training Cross-Encoder Models
In our experiments, we use [EMB]-CE, a cross- encoder model variant proposed by Yadav et al. (2022) that jointly encodes a query-item pair and computes the final score using dot- not-product of con- textualized query and item embeddings extracted after joint encoding.
Yingqi Qu, Yuchen Ding, Jing Liu, Kai Liu, Ruiyang Ren, Wayne Xin Zhao, Daxiang Dong, Hua Wu, and Haifeng Wang. 2021. RocketQA: An optimized train- ing approach to dense passage retrieval for open- domain question answering. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguisties: Hu- man Language Technologies.
B.1.1 ZESHEL Dataset
ZESHEL dataset is a zero-shot entity linking con- taining set of 16 domains, each containing a dis- joint set of items (entities). Each domain contains a set of queries (mention) paired with their ground- truth items (entities). For ZESHEL, we use the cross-encoder model checkpoint released by Ya- dav et al. (2022). The cross-encoder model was trained by first training a dual-encoder model on ZESHEL training data using hard negatives, and then training a cross-encoder model for the task of zero-shot entity-linking on all eight training do- mains using cross-entropy loss with ground-truth
Stephen Robertson, Hugo Zaragoza, al. 2009. The
probabilistic relevance framework: Bm25 and be- yond. Foundations and Trends in Information Re- trieval, 3(4).
Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. 2019. DistilBERT, distilled version of BERT: smaller, faster, cheaper and lighter. arXiv preprint 19Xiv:1910.01
Nandan Thakur, Nils Reimers, Andreas Rücklé, Ab- hishek Srivastava, and Iryna Gurevych. 2021. BEIR: A heterogeneous benchmark for zero-shot evaluation of information retrieval models. In Thirty-fifth Con- ference on Neural Information Processing Systems Datasets and Benchmarks Track (Round2 2).
Phtps:/hugginngfice.om www.saaeccc..csssaaaaaaawceem wttp:////mmmmccccccccceam zeshel

---

Dataset
Domain
(1 Qrain [eexx] Splits
Train Query (Qrm) Type
ZESHEL
YuGiOh
10,031
(100/3274), (500/2874), 1770)
Real Queries
7ESHEI.
StarTrek
34,430
(1004127), (500/3727), (2000/2227)
Real Queries
ZESHEL
Military
104,520
(100/300), (500/1900), (2000/0400)
Real Queries
BEIR
SciDocs
25,657
(1000/1000) (1000/1000)
Pseudo-Querts
BEIR
HotpotQA
5,233,329
Pseudo-Queries
Table 1: Statistics on the number of items (Z) and the number of queries in train and test splits for each domain. The train-query (Quain) split refers to queries used for distilling dual-encoder models or for indexing items using ADACUR and ANNCUR. For ZESHEL domains, we create train-test splits by splitting the queries in each domain uniformly at random and test with three different splits by putting 100, 500, or 2000 queries in train split. For BEIR domains, use pseudo-queries released as part of the benchmark train queries (Quain) and run k--N evaluation on test queries from the official test split (as per BEIR benchmark) of these domains. For HotpotQA, we use the first IK queries out of total of 7K test queries and we all IK test queries for SciDocs.
entity and negative entities mined using the dual- encoder. We refer readers to Yadav et al. (2022) for further details on cross-encoder training.
x 110M parameters. We refer readers to Yadav et al. (2022) for details related to the training of all DE model variants on ZESHEL dataset.
We perform k-NN experiments on domains YuGiOh, StarTrek, and Military from ZESHEL of which only Military was part of the train- ing data used to train the cross-encodes model and YuGiOh and StarTrek are part of the origi- nal ZESHEL test domains and the cross-encoder model was not trained on these domains.
B.2.2 BEIR benchmark
For BEIR domains, we use a dual-encoder model released as part of sentence-transformee repos- itory as DE This dual-encoder model was initialized using distillbert
(Sanh et al., 2019) and trained on MS-MARCO dataset. This DE is not trained on target domains SciDocs and HotpotQA used for running k-NN experiments.
B.1.2 BEIR
We follow the training setup used by Hofstätter et al. (2020). We first train three teacher cross- encoders initialized with albert-Large--2 (Lan et al., 2020), pert--erge-hholl--wwrdd-n-skkk and bert bast-baae- (Devlin et al., 2019), and compute soft labels on 40 million (query, posi- tive item, negative item) triplets in MS-MARCO dataset (Bajaj et al., 2016). We then train our cross-encoder model parameterized using a 6- layer MINI-LM model (Wang et al., 2020) via distillation using average scores of the three teacher models as target signal and minimizing mean-square-error between predicted and target scores. We use training scripts available as part of sentence-transformee repository to train the cross-encoder model and use dot-product based scoring mechanism for cross-encoders proposed by Yaday al. (2022)..
We finetune DÉsASE via distillation on the tar- get domain get DE model. Given set of training queries Quain from the target domain, we retrieve top-100 100 or top-1000 items for each query, score the items with the cross-encoder model, and train the dual- mual-encoder by minimizing cross-entropy loss between predicted query-item scores (using DE) and target query-item scores (obtained using cross-encoder). Training DE with 1K queries and 100 or 1000 items per query takes around 2 hrs and 10 hrs respectively on an Nvidia RTX8000 GPU with 48GB memory. We train DE s for epochs when using top-100 items per query and for 4 epochs when using top-1000 items per query using AdamW (Loshchilov and Hutter, 2019) opti- mizer with learning rate 1e-5.
CE
B.3 ANNCUR Implementation details
B.2 Training Dual-Encoded Models
For ANNCUR, we report results for the optimal split of cross-encoder call budget (BeF) between scoring k; anchor items followed by retrieving BeE ky items for re-ranking. We experiment with ky E [iBcE/10 /0: 1 < i 9). If the retrieved items contain a subset of anchor items for which exact
B.2.1 ZESHEL dataset
We report results for DE baselines as reported in Ya- dav et al. (2022). The DE models were initialized using bert-base-uncased and contain separate query and item encoders, thus containing total of

---

Total
Cross-Enc Cals
Matrie Muliily
Matrix Invers
Tocal
Cress-Enc Call
Matris Multiply
Matric Inverse
CE Call-110
100
CE Calls-100
Cals-5000
Inforors Laberry (in s)
10
H0.00
10.70
10-4
100 100
10
20
100
2 10:20
2 10 20 50100
50.000
Number of Rounds
Number Rounds
Domain-Military (100K items), Quainl 500. Each CE call takes ~7m on an Nvidia 2080ui GPU cross-encoder parameterized using 12-layered transformer model.
(b) Domain=HotpotQQ. Million items), (Qeinl 1000. Each takes ~22ms an Nvidia RTX8000 encoder parameterized using 6-layered transformer model.
cross-
Figure 5: ADACUR inference latency versus number of rounds for two different domains. The primary bottleneck at inference time is the time taken compute cross-encoder (CE) scores for query-item pairs test time, and the overhead for ADACUR accumulates linearly as the number of rounds increases. See $B.5 for detailed discussion.
cross-encoder score has already been computed, we retrieve more than BeB k; items using ap- proximate scores and compute exact cross-encoder scores for them until we have exhausted the entire cross-encoder call budget for the re-ranking step.
which takes O time. The time taken to update the approximate scores in each round is OC + C 127 and the time taken to com- pute cross-encoder scores for the batch of k; items O(k,Cra) Thus, the total inference latency for retrieving items over NR rounds under given budget of BEE cross-encoder calls
B.4 ADACUR Implementation details
For all our k--N search experiments, we used Nvidia 2080ti GPUs with 12GB memory for do- mains YuGiOh (10K items), StarTrek (34K items), Military (100K items), and SciDocs (25K items), and we used Nvidia RTX8000 GPUs with 48GB memory for HotpotQA (5 million items). For HotpotQA, we restrict our K-NN search to top-108 items wrt DE for DD For ZESHEL domains and Docs, we not use any such heuristic and search over all the items in the corresponding domain.
NR
(kiC + Chickke + Chul chorskallZl)
Nx.
-0 OBBBCBaa
(Chiuska + chiosttiolZ
+
Overhead of ADACUR
Figure 5 shows the breakdown of ADACURTS 's in- ference latency in terms of time spent on computing cross cross-encoder scores, and the overhead of comput- ing matrix inverse in line 12 and updating approxi- mate scores by multiplying matrices in line 13 of Algorithm 1. Empirically, we observe that the pri- mary bottleneck at inference time is the time taken to compute cross-encoder scores for query-item pairs at test time, and the overhead for ADACUR accumulates linearly as the number of rounds in- creases. The overhead is mostly dominated by com- puting pseudo-inverss (see line 12 in Algorithm 1) and this step is independent of the target domain size. The matrix multiplication step (line 13 in Al- gorithm 1) has linear dependence the number of items in the target domain but it is negligible fraction of the overall running time as it can be significantly sped up using GPUs.
B.5 Time Complexity of ADACUR
The offline indexing step for ADACUR takes Okg time it involves computing exact cross-encoder scores for all [Z] items in the target domain against ky anchor queries, and computing each cross-encoder score takes Cfn units of time.
At test time, we are given a budget BeE on the number of cross-encoder calls. Each one of the NR rounds during inference with ADACUR in- volves approximating all item scores for the test query (9test) followed by sampling the next batch h = B items using the updated approxi- mate scores. In the jth round, the score approxima- tion step involves computing the pseudo-inverse of kg x jk, -dimensional matrix (line 12 in Algo. 1), which takes OCtivite) time, followed by a matrix multiplication step to compute up- dated approximate scores (line 13 in Algo. I)
For ZESHEL domains, we use a cross crosseencoder parameterized using bert-base (Devlin et al., 2019), and observe that each cross-encoder call takes amortized time of 7ms on an Nvidia 2080ti

---

GPU when the scores are computed in batches of size 50. Computing each cross-encoder score se- takes ~I 3ms
hence subsequent retrieval based on the approx- imate scores, We experiment with the following strategies for sampling Ky anchor items for a given test query:
quentially i.e. with batch-size per score. We did not observe any further reduc- tion in amortized time to compute each score when increasing the batch size beyond 50.
Topk km. Mask out top-km items wrt ex- act cross-encoder scores and select ky anchor items by greedily picking (1 (1-e)k; items start- ing from rank km + 1, and sample remaining ek; anchor items uniformly at random.
The amortized time per cross-encoder call is approximately 6ms and 2ms for SciDocs and HotpotQA respectively when using batch size=50 and MINI-LM-based (Wang et al., 2020) cross- encoder. The difference in time per cross-encoder score for SciDocs and HotpotQA is due to the dif- ference in average query-item pair sequence length.
Sof tMax km Mask out top-hin items wrt ex- act cross-encoder scores and select k; anchor items by sampling (1 c)k; anchor items us- ing softmax over exact cross-encoder scores, and sample remaining ek₃ anchor items uni- formly at random.
Additional Results and Analysis
C.1 TopK vs SoftMax for ADACUR
For a given test-time cross-encoder call budget BeE, we select k; anchor items, compute approx- imate cross-encoder scores using the chosen an- chor items, and then retrieve BeF. - k; items based on the approximate scores. We experiment with h E {iBCE/ 10: i 9} and report results for the best budget split.
Figure 6 shows Ropak-Recall for ADACUR on do- main=YuGioh, Quriil 500, when using Topk and SoftMax strategies for sampling items based on approximate scores (see $2.2 for details), Topk sampling strategy which greedily picks top-k items based on approximate scores results in superior re- call as compared sampling items using softmax over approximate scores.
CARCUR
Tamt: Tunk-
ADACUR Tops
Approximation Error
AnACUR Soctmax
109
TopK
ADXCUR Topk
1=1
1=100
10-2
Top A- RRRaall
Top-1
Top-10
Top-100
Anchor
All
Types of Items
Figure 7: Average approximation error for CUR ma- trix factorization on test-queries for domain=YuGióh and |Quain = 500 when choosing ks 50 anchor items uniformly at random (ANNCUR), using oracle strategies from $C.2 and for ADACUR when sampling anchor items over five rounds. Approximation error is computed as the average of absolute difference between approximate and exact item scores.
50
100
200
500
200
500
1000
Inference Cost (Total Number of
Calls)
Top-k-Recal for ADACUR on YuGiOh, Quiil 500 for different strategies for sampling items based on approximate scores descrihed in $2.2.
Figure 6:
Effect of adding k-NN items to anchor items Figure 8a shows Tep-k-Recall of anchor item sampling strategies Topk km and toftMa for kim {0, k}. domain=YuGioh. Sampling strategies Sof tMax and Topk which mask out top-k items, perform significantly worse than Sof tMax and Topk respectively when searching for 1, 10 nearest neighbors. This indicates that the sig- nificant improvement in Top-l-Recall and Top-10- Recall for Topk and Sof tMfi, sampling strate- gies can be attributed to the presence of top-k items in the anchor item set. This is because CUR matrix
C.2 Anchor Item Sampling with Oracle
ADACUR performs retrieval over multiple rounds using approximate cross-encoder scores and uses the items retrieved based on the approximate scores as anchor items to improve the approximation and hence retrieval in subsequent rounds. In this sec- tion, we run experiments where the anchor item sampling method has oracle access to exact cross- encoder scores of all items for the given test query to better understand the effect of anchor items on the approximation of cross-encoder scores and

---

ANSOUR ADAOUR Popk
Torks
S
Approximate Top-k Items
1:10
201-500
Anchor heme
11-100
501+
Torksp
MoriMAa
Approximate Scores
Approximan Scores
k= 100
100
Top-k- Recall
%
%
15
25 (B1
65
Exact Scores
Exact Scores
10
50
100
50
100
200
200 500 1000
(a) Topk = 0.0
(b) Sof LMax
0.0
Inference Cost (Total Number of Cross Rrcodenncoder Calls)
Approximate Scores
Approsimate Spores
(a) Sampling with and without ground-truth truth top-k items
Epsilon
0:25
10
A= 100
100
Top-k J--ecalll
50-
35
Exact Scores
Exact
Scores
(c) Topke... 0.0
(d) Sof Sof
0.0
10
50
100
50
100
200
200 500 1000
Approsimate Scores
Approsimate: Scores
Inference Cost (Total Number of Cross Encoder Calls)
(b) Sampling using Topk strategy with exact CE scores while varying e. the fraction of items sampled uniformly at random
L0-00
5 1
Epailon
C2E
6.75
10
A= 100
dh
100
Exact Scores
Exact Scores
Top-k- k- R-Recall
(c) Topk 0.75
(f) Sof SoftMaxe,.. 0.75
50
Figure 9: Scatter plot showing approximate versus exact cross-encoder scores for query from domain=YuGiOh, when choosing k = 50 anchor items using oracle strategies from SC.2 and 1main| = 500. Top-k for k=1, 100, wrt exact cross-encoder scores are anno- tated with text along with vertical lines, different color bands indicate the ordering of items wrt approximate scores, and anchor items are shown in blue.
10 50
100
50
100
200
200 500 1000
Inference Cost (Total Number of Encoodn Calls)
(e) Sampling using SoftMax of exact CE scores while varying c, the fraction of items sampled uniformly at random
Figure& 8: Top-k- Top-k-RRcall for ADACUR, ANNCUR, and oracle sampling strategies ($C.2) that have oracle ac- cess to exact cross-encoder scores for all items for do- main=YuGiOh, Iariin| 500.
score distribution whereas greedily selecting top- scoring items using exact scores results in an an- chor set with items having similar cross-encoder scores. However, as shown in Figures 9e and 9d, both of these sampling strategies can result in over- estimating scores for all items, even the irrelevant ones (i.e. items beyond top-k items) due to insuf- ficient representation of the irrelevant items in the anchor set. Thus retrieving based approximated scores may struggle to retrieve relevant k-NN items, especially for larger values of i such as k 100 when the anchor items are chosen using oracle strategies such as Topk km
factorization which is used to compute the approxi- mate scores incurs negligible approximation error on anchor items, and hence on top-k items when these items are part of the anchor set as shown in figures 7 and 9. For Topk 1.0 and Sof tMax sam- pling strategies, since the top-k items are not part of the anchor set, CUR incurs a much higher ap- proximation error for the top-k items (see examples in Figures 9a and 9b) thus resulting in poor Top- k Recall as shown in Figure 8a.
Effect of diversity in anchor items Figure 8a shows that sampling items based on softmax of exact cross-encoder scores tMo per- forms better than greedily picking top-scoring items (Topk?...). for both km = 0, The rea- behind Soat . performing better than Topk km.. is that sampling based on softmax of ex- act scores yields an anchor set with a more diverse
Figures and 9f, where c = 75% of 50 items are sampled uniformly at random, show that over- estimating scores of irrelevant items can be avoided by sampling a fraction of anchor items uniformly at random to increase the diversity of the anchor item set. As shown in Figures 8b and 8c, Top-k- Recall for both Sof tMax O and Topko. generally improves with an increase in e, the fraction of ran-

---

dom items in the anchor set, due to increased di- versity in the anchor item set. Since tMft,. already samples diverse set of anchor items, in- creasing yields only marginal improvement while for Topk increasing e yields significant improve- ments due to increased diversity of the anchor set. A small drop in performance is observed for larger values of e as increasing e beyond a threshold re- sults in some of the top-A items to be excluded from the anchor item set. This results in a poorer approx- imation of scores for the missing top-k items and hence poor retrieval recall as the retrieval is done using the approximate scores.
DE
MUVER
ADACU Riren
k
100
60-
Top- As Recall
601
411
20-
200
200
Inference Cost (Total Number Cross Pross-Encoder Calls)
(a) YuGiOh
A-1
k= 50
Finally, the optimal strategy for choosing the set of anchor items is the one that strikes balance between selecting anchor items with diverse cross- encoder scores and greedily picking top-k items. Our proposed strategy ADACUR improves over ANNCUR greedily picking top-scoring items according approximate scores to expand set of anchor items increases the likelihood of picking ground-trute k--N items to be part of the anchor set, with this likelihood improving after each round with improvement in the score approximation, and ADACUR achieves diversity in the anchor items as a result of sampling items uniformly at random in the first round and due to error in the approximate scores, as shown in Figure 11.
80-
Top- k R--all
40
50
100
200
100
200
Inference Cost (Total Number of Cross-Encode Encoder Calls)
(b) StarTrek
Figure 10: Rop-k-Recall for ADACUR and base- lines including multi-vector vector models on ZESHEL do- mains, 1 2000. See $C.3 for discussion.
such multi-vector models incur significant mem- ory overhead for storing query/item embeddings. For instance, using 15 embeddings per item with (68-dimensional embeddings would take around 250GB space for 5 million items for HotpotQA.
C.3 Comparison with Multi- Vector Models
Multi-vector models (Khattab and Zaharia, 2020; Ma et al., 2021) produce multiple embeddings for each query and item. For given query and item i, the query-item score is computed using simple functions such as average similarity or sum-of- maximum similarities between the set of embed- dings for query q and item i.
C.4 Results for TF-IDF baseline
TF-IDF: All queries and items are embedded using TF-IDF vectorizer trained on item descriptions and top-k items are retrieved using the dot-product of sparse query and item embeddings.
For domains in ZESHEL, we report re- sults for TF-IDF baseline, for ANNCUR when anchor items chosen using TF-IDF base- line (ANNCURT--10F) and for ADACUR when the first batch of anchor items is chosen using TF-IDF baseline (ADACURTF-IOF). Fig- ures 13, 14, and 15 show Top-k-Recall for domains YuGiOh, StarTrek, and Military respectively for Quain E {100,, 500, 2000). For each baseline trieval method, ADACUR always performs better than ANNCUR which turn generally performs better than merely re-ranking items retrieved us- ing the corresponding baseline retrieval method. In most cases, Top-k-Recall for ADACURDESSE > AN- <CURDFaSS: DERASE. and ADACURTF-IOO AN- N CURTFF-DE>> TE-IDE.
Figure 10 shows Top-k-Recall for DEBASE- CE
DE ADACURDE and MUVER (Ma et al., 2021), a recent multi-vector model trained on ZESHEL dataset. For MUVER, we use the pre- trained checkpoint released by Ma et al. (2021) with the view-merging inference strategy as de- scribed in Ma et al. (2021). While MUVER can be more accurate than DEBASE DE obtained by finetuning DÉEASE model on the target domain outperforms MUVER and our proposed method ADACURD yields the best Hop-k-Recal versus inference cost trade-offs for all values of k.
We would also like to note that while multi- vector models such as MUVER can be more accu- rate than embedddnn models such as DEBASE:

---

Approximate Top-k Items
1-10
101-500
Anchor Items
11-100
501+
Approximate Scores
Approximatt Scores
Approximate Scores
60-
651
66
60+
600
65-
R-100
68
100
168
50
501
50
55
60
65
50
65
60
65
50
55
60
65
Exact Scores
Exact Scores
Exact Scores
(a-1) ADACUR Round 1.
(a-2) ADACUR Round 2.
(a-3) ADACUR Round
Total 10 anchor items.
Total 20 anchor items.
Total 30 anchor items.
Approximate Scores
Approximate Scores
2-1
Approximate Scores
63-
63-
80-
100
00-
60-
55
65-
100
53-
100
50
80
50
55
60
65
50
55
00
65
30
60
66
Exact Scores
Exact Scores
Exact Scores
(a-4) ADACUR Round 4. Total 40 anchor items.
(a-5) ADACUR Round S. Total 50 anchor items.
(a-6) ANNCUR- Sampling all 50 an- chor items uniformly at random.
(a) Sampling anchor items adaptively ADACUR (over five rounds)
ANNCUR (uniformly at random).
Approximate Scores
Approximate Scores
Approximate Scores
60
60
60
65
100
66-
65
60+
50-
50
30
55
60
65
Exact Scores
Exact Scores
Exact Scores
(b-1) ADACUR Round
(b-2) ADACUR Round
(b-3) ADACUR Round Total 120 anchor items.
Total 40 anchor items.
Total anchor items.
Approsimate Scores
Approximate Scores
Approximate Scores
65-
65
80
60
80
-00
1100
65-
55-
30.
50
55
60
65
30
33
(0)
65
30
60
66
Exact Scores
Exact Scores
Exact Scores
(b-4) ADACUR Round 4. Total 160 anchor items.
(b-5) ADACUR Round 5. Total 200 anchor items.
(b-6) ANNCUR- Sampling all 200 an- chor items uniformly random.
(b) Sampling anchor items adaptively ADACUR (over rounds) and ANNCUR (uniformly at random).
Figure 11: Scatter plot showing approximate versus exact cross-encoder scores for a query from do- main=YuGiOh. /umin 500 when choosing k, 50 and 200 anchor items with ADACUR over five rounds, and uniformly at random with ANNCUR. Top-k for 1=1,10, 1,11011000 100 wrt exact cross-encoder scores are annotated with text, different color bands indicate the ordering of items wrt approximate scores, and anchor items are shown in blue. With ADACUR, the first batch containing anchor items in Figure laal1 and 1lb-1 is chosen uniformly at random and subsequent rounds, items with highest approximate scores are chosen. Note the approximation error for top-scoring items improves significantly when the 50 anchor items chosen adaptively (see Figure 1a-5) with the improvement being much more significant than merely increasing the number of anchor items sampled uniformly at random from 50 in Figure 1a-6 to 200 in Figure 1 llb-6.

---

D
FRASE
ANNCUR
ANNCUP DEWEx
Proposed Approaches
ADA CUR
ADACU CUU.U
10
k 100
100
Top-l-RRecal
80
40
50
100
200
500
50
100
200
500
200
500
1000
Inference Cost (Total Number of Cross-Encodes Calls)
(a) SciDocs
k=1
10
k= 100
Top-f- K-Recall
80
40
20
50
100
500
50
100
500
500
1000
Inference Cost (Total Number of Eroos-Encoder Calls)
(b) HotpotQA
Figure 12: Top-k-Recall for ADACUR (using ten rounds) and baselines for SciDocs and HotpotQA, [Quiil 1000.

---

TF-IPP
DR
D P
ANNCUR
ANNCUR
TFEE
ANNCUR
DENEr
Proposed Approaches
ADACUR
ADA CUR
ADACUR
TFIEF
A=
Top- R-Recall
26F
20
80
60
40
:20
50
100
200
500
50
100
200
500
200
500
1000
Inference Cost (Total Number of Cross-Encoder Calls)
(a) Number of train/anchor queries
Quain
100.
1=10
100
100
R83
Top-k-Recall
60
201
100
200
500
100
200
500
200
500
1000
Inference Cost (Total Number of Cross-Encoder Calls)
(b) Number of train/anchor queries Quain 500.
k= 10
k= 100
100
222
Yop-k-Recal
80
60
60
50
100
200
500
50
100
200
500
200
500
1000
Inference Cost (Total Number of Cross Encoder Calls)
Number train/anchor queries Quain 2000.
Figure 13: Top-k-Recall for ADACUR (using five rounds) and baselines for domain=YuGioh. Each subfigure corresponds different value of the number of train/anchor queries (raini)))

---

TF-IDP
DR
D Faaaee
ANNCUR
ANNCUR
TFEE
ANNCUR
Proposed Approaches
ADACUR
ADA DUR
ADACUR
TFIE
A 1=100
Top-k- E-Recall
80
60
35
40
:20
50
100
200
500
50
100
200
500
200
500
1000
Inference Cost (Total Number of ErooseEncoder Calls)
(a) Number of train/anchor queries
Quain
100.
1=10
100
100
92
Top-k-Recall
60
201
100
200
500
100
200
500
200
500
1000
Inference Cost (Total Number of Cross-Encoder Calls)
(b) Number of train/anchor queries Quain 500.
k= 10
k= 100
100
05
Top-k-Recall
80
60
60
50
100
200
500
50
100
200
500
200
500
1000
Inference Cost (Total Number of Cross Encoder Calls)
Number train/anchor queries Quaia 2000.
Figure 14: Top-k-Recall for ADACUR (using five rounds) and baselines for domain=StarTred Each subfigure corresponds different value of the number of train/anchor queries (irann))

---

TE-IF
D
ANNCUR
ANNCUR
ANNCUR
Proposed Approaches
ADACUR
ADACUR TFID
ADACUR ADACURReue
k= 10
h= 100
100
Top-k-Rech Reck-ll
60
10
20
200
500
100
200
500
200
1000
Inference Cost (Total Number of Cross Encoder Calls)
(a) Number of train/anchor queries Quain
100.
k==1
1=
1=100
2.2
Top-k-Recall ReRclll
80
Top-k-
40
50
100
200
500
50
100
200
500
200
500
1000
Inference Cost (Total Number of Calls)
(b) Number train/anchor queries Quain| 500.
10
1=100
EBR
Top-k-Recall
80
60
40
20
50
100
200
500
50
100
200
500
200
500
1000
Inference Cost (Total Number of Cross Cross-Encoder Calls)
(c) Number of train/anchor queries Qrain = 2000.
Figure 15: Rop-k-Recall for ADACUR (using five rounds) and baselines for domain=Militar Each subfigure corresponds to different value of the number of train/anchor queries (raia ). Note that DEBASE has high Top- I- Recall values domain=Mi li tary is included in the of train domains in ZESHEL which used train both DE and the cross cross-encoder model.


Reviews:
[{"review_id": "LIfzqmGgzs", "reviewer": "Reviewer_zs87", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments and time reviewing our work. \n\n**Analysis of the latency - Clarifications** \n* Figure 4 reports the total time of each round (thin blue bar) on primary y-axis and the fraction of that time spent in cross-encoder (CE) calls and the other parts of AdaCUR (matmul, pseudo-inverse) on secondary y-axis\n* The reported numbers already batch/parallelize the CE calls as the reviewer suggests. They are not scored one-by-one.\n* The batch size used is 50 (pairs of query-item to score with the CE).\n* Increasing batch size beyond 50 did not yield any improvement in amortized time per score computation on Nvidia 2080ti GPU.\n* Batch Parallel takes: ~310ms to score a batch of size 50 resulting in an amortized time of 6-7ms per query-item pair. Scoring each query-item pair sequentially (with batch size=1) would have taken ~13ms per query-item pair, and effectively ~650ms to score 50 query-item pairs.\n\n\n*AdaCUR compared to Retrieve & Rerank - Single GPU Machine* \n\nConsider cross-encoder (CE) call budget = 500\n\n* Time taken by retrieve-and-rerank based approaches to re-rank 500 retrieved items using cross-encoder = 3100ms (in 10 batches of size 50 each)\n\n* AdaCUR will perform retrieval over 5 rounds, requiring computation of 100 CE scores per round.\n* Time taken for 100 CE calls per round =  620ms (in 2 batches of size 50 each)\n* Total time taken for 500 CE calls over 5 rounds = 3100ms\n\n* Total overhead of AdaCUR over 5 rounds = 42ms \n* Thus, total time taken by AdaCUR = 3100 +  42 = 3142ms \n\n* AdaCUR incurs less than 2% overhead over retrieve-and-rerank based approaches.\n\n*Analysis of the latency - AdaCUR compared to Retrieve & Rerank - Multiple GPUs* \n\nUsing multiple machines, say `M`, can further bring down per-query latency by a factor of `M` for retrieve-and-rerank approaches. \nSimilar improvement can be observed for AdaCUR when number of CE calls per round > `batch_size*M` i.e. for the same query,  multiple batches of items can be scored in parallel.\n\nIn case number of CE calls per round < `batch_size*M`, then some fraction of the machines will be under-utilized. In such cases, we can increase the overall throughput by performing k-NN search multiple queries in parallel.\n\n\n**Impact of model size on inference latency**\n\nWe used 12-layer transformer-based models in our experiments which took an amortized time of around 6-7ms per query-item pair when the scores are computed in batches of size=50. \n\nFor larger, billion-parameter sized models, the cost of cross-encoder calls increases further and thus the overhead of our proposed adaptive sampling would be further dwarfed in comparison to the cost and latency of each cross-encoder call.\n\nWe will add this clarification in the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The proposed method is well-motivated by conceptual argument (multiple rounds of adaptive anchors should be better than one round of anchors) as well as empirical analysis of the problem (Figure 1). This improves the understanding on annCUR and also justifies the design of the proposed approach.\n\nAuthors compare the proposed method against strong baselines, in particular dual encoders distilled from cross-encoders. This helps readers to understand the practical utility of the proposed method against well-established and strong alternative methods.", "reasons_to_reject": "I find the analysis of the latency to be a bit confusing or misleading. Authors argue that the main bottleneck is CE computation, and thus using a multiple rounds of retrieval in adaCUR doesn't impact latency much. However, CE calls shall be parallelized, if needed across multiple devices/hosts. Hence, given sufficient compute budget, 100 CE calls shall be run in the latency close to 1 CE calls, whereas 100 rounds of adaCUR will require the latency of 100 one-by-one calls. Therefore, the latency analysis in Figure 4 seems to be conducted in a very unrealistic assumption that only one CE call shall be made at a time. \n\n---\n\nAuthors argue that batch parallelization (of batch size 50) only provides 2x speedup. I am a bit surprised by this, but increasing the score based on the assumption the baseline implementation is sufficiently optimized.", "questions_to_authors": "", "paper_topic_and_main_contributions": "Authors propose to improve upon previously proposed method of annCUR. This is achieved by improving the set of anchor items over multiple rounds of retrieval, rather than using a one round of randomly sampled items. Experiments on zero-shot entity linking dataset (ZeShEl) and BeIR against annCUR as well as other strong dual encoder-based baselines demonstrate that the proposed method more effectively utilize the computation budget for cross-encoder calls than baselines do.", "excitement": 3, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "5rvr8oVs3g", "reviewer": "Reviewer_6YK8", "summary": "", "questions": "Since the proposed method needs serval rounds, can you provide experiment metrics in terms of average inference time in addition to inference CE calls?", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their time and consideration!\n\n* We observe recall-vs-inference cost trends _similar_ to those currently reported in the paper even when the inference cost is measured as the total inference latency instead of total cross-encoder (CE) calls. \n  * This is because inference latency for AdaCUR (at 5-10 rounds) and other retrieve-and-rerank baselines largely depends on the number of cross-encoder calls made at test-time to score query-item pairs.\n  * Figure 4 shows inference latency (in seconds) of our proposed approach AdaCUR at different CE call budgets. \n  * Thin blue bars in Figure 4 show per-query inference latency (in seconds) on primary y-axis. We show breakdown on inference latency into different components such cross-encoder (CE) score computation and overhead incurred by our proposed approach AdaCUR on secondary y-axis.\n  * Figure 4 shows that AdaCUR has very small overhead when using 5-10 rounds for inference with the time taken to compute cross-encoder scores dominating the overall inference latency.\n\nWe would be happy to further discuss and clarify any concerns that the reviewer may have regarding the soundness of our paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The anchor method is neat for a short paper.", "reasons_to_reject": "The novelty is at boderline.", "questions_to_authors": "Since the proposed method needs serval rounds, can you provide experiment metrics in terms of average inference time in addition to inference CE calls?", "paper_topic_and_main_contributions": "The authors propose ADACUR, a method that effectively minimizes the approximation error for the practically important top-k neighbors by iteratively performing k-NN search using the anchors.", "excitement": 3, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "OSMXayDw3p", "reviewer": "Reviewer_sVVR", "summary": "", "questions": "**A.** Please add experiment results of more recently proposed methods for comparison. The list of missing references below includes some candidate methods.\n\n**B.** Not sure if I missed it, but why is the improvement when k=10 often more prominent than the improvement when k=1 and k=100? Also, why is AnnCUR even worse than TF-IDF in Figures 14 and 15 in the appendix?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your thoughtful suggestions, comments and time reviewing this paper. We will revise the paper to fix presentation and writing related issues pointed out by the reviewer.\n\n### **Re: Comparison with suggested baselines**\n\nThanks for the suggested references.\n \nIn our work, we make following assumptions about models/data:\n- We are given a trained cross-encoder model \n- We are given data from target domain to index\n- Optionally, we are given a dual-encoder model trained on _same_ task and source domains as cross-encoder\n- Do not assume access to source domain data (which was used to train cross-encoder)\n- Do not assume any special structures or relations amongst queries or amongst items\n\nWe report results for additional experiments with models from _MuVER_ (Ma et al. 2021) below. To the best of our understanding, references other than Ma et al. (2021) \n- either focus solely on the task of entity linking and do not apply to the general task of k-NN search with a given cross-encoder model (which is the focus of our work)\n- or require training both dual-encoders or cross-encoders _jointly_, thus are not compatible with our setting where we assume that we are given a trained cross-encoder.\n\nWe present a more detailed response for each paper below.\n\n* _MuVER: Improving First-Stage Entity Retrieval with Multi-View Entity Representations, EMNLP 2021_\n\n  * We run kNN search evaluation using the MuVER checkpoint released by Ma et al. (2021). \n  * For brevity, we show Top-1-Recall for MuVER and other models (from Fig 2 in our paper) at different test-time costs for doman=YuGiOh.\n   * While MuVER performs better than base dual-encoder (DE), it performs worse as compared to dual-encoders finetuned on the target domain and AdaCUR, our proposed approach. We will add these additional results to the paper.\n\n\n| Model\\Inference Cost | 50     | 100   | 200   |\n| ---           | ---           | ---   | ---   |\n| Base DE       \t\t|  74.5\t| 79.4\t| 83.8  |\n| MuVER         \t\t|  78.3\t| 83.5  \t| 88.1  |\n| Distilled DE \t \t|  88.0\t| 90.9\t| 93.6  |\n| AdaCUR (Ours) \t|  88.8\t| 93.9\t| 96.4  |\n\n\n\n * *Memory overhead for MuVER and multi-vector models*\n\n    - While models that generate multiple embeddings per query and item (eg. MuVER) can be more accurate than models that generate a single embedding (eg. dual-encoder), such multi-vector models incur significant memory overhead for storing the query and item representations, and require special index structure for efficient inference even at moderate scale. \n    - For instance, using 15 embeddings per item, as used by Ma et al. (2021), would take around 250GB space to store 768-dim embeddings for 5 million items for HotpotQA domain. \n    - Moreover, training such multi-vector models also require more compute resources and time as compared to training single-embedding dual-encoder baselines. \n    - This makes training and using such multi-vector models in order to perform first stage retrieval for a given cross-encoder model a less attractive option.\n\n\n**As mentioned before, to the best of our understanding, following references are _not suitable_ baselines for our work. We present a detailed response for each paper below.**\n\n  * _Modeling Fine-grained Information via Knowledge-aware Hierarchical Graph for Zero-shot Entity Retrieval_\n    * This paper focuses on entity linking and the proposed ideas do not apply to general kNN search/information retrieval settings. \n    * In particular, this paper extracts subject-verb-predicate triplets from surrounding text to improve mention embedding and such an approach can not be used for improving query embedding general k-NN search setting such as passage retrieval setting. \n\n  * _EntQA: Entity Linking as Question Answering_\n    * This paper links mentions in a document to entities by first shortlisting some entities and then finding potential mention span for each shortlisted entity. \n    * Such an approach cannot be generalized to a more general kNN search setting. For eg, it cannot be applied to finding documents/passages for a given query.\n\n  * _Entity Linking via Explicit Mention-Mention Coreference Modeling (NAACL 2022)_\n    * This paper assumes access to mention-mention coreference decisions while training the dual-encoder model. \n    * Such method can not be used for training dual-encoders in the general information retrieval settings eg. passage retrieval given a query. \n\n  * _TempEL: Linking Dynamically Evolving and Newly Emerging Entities (NeurIPS 2022)_\n    * The primary contribution of this paper is a new dataset to study how entities evolve and emerge in a KB. \n    * To the best of our understanding, it _does not propose_ a new approach/model for entity linking.\n\n  * _Towards Better Entity Linking with Multi-View Enhanced Distillation (Liu et al. ACL 2023)_\n    * Thanks for pointing us to this paper. We missed this as it was published only a month before the EMNLP deadline. \n    * Nevertheless, models proposed in Liu et al. (2023) paper _may not be suitable baseline_ as best results in Liu et al. (2023) correspond to a setting where \n      * both cross-encoder and dual-encoder are trained jointly – Not compatible with our setting where we are given a trained cross-encoder\n      * cross-encoder trained on multi-view data – thus may _not_ work well with general cross-encoders.\n    * In fact, as shown in ablations in Liu et al. (2023), using a cross-encoder trained separately and without multi-view data results in a dual-encoder with entity linking recall@64 of 88.5%. \n      * In our work, we use the dual-encoder checkpoint released by Yadav et al. (2022) which has entity linking recall@64 ~88%, and we also compare with stronger baselines such dual-encoders finetuned on the target domain.\n      * Also note, that our evaluation metrics use _top-k items/entities wrt cross-encoder_ as ground-truth for evaluation while evaluation in Liu et al. (2023) focus on entity linking where the goal is finding the single ground-truth entity (item) which is specified as part of the dataset annotation.\n\n\n  * _A Transformational Biencoder with In-Domain Negative Sampling for Zero-Shot Entity Linking (Sun et al. ACL 2022)_\n    * The ideas proposed in this paper are geared towards improving performance of a dual-encoder in _zero-shot domain transfer_ setting. \n    * The transformational biencoder idea may not yield any improvement for our use-case when we finetune the dual-encoder on the target domain and then use it for kNN search for test-query on the _same target_ domain.\n    * Ideas from Sun et al. (2022) could be used to train better base dual-encoder models on the source data which can be then finetuned on the target data. \n    * However, for fair comparison with prior work, in this work we use and finetune publicly available dual-encoder models released by Yadav et al. (2022) for ZeShEL data and dual-encoders available on huggingface for BeIR dataset which do not use the transformational biencoder idea.\n\n\n### **When is AdaCUR favored over retrieve-and-rerank?**\n\nLet’s begin by reviewing consistent empirical trends in our results:\n\n* For k=100, AdaCUR consistently provides improvement over retrieve-and-rerank and all other baselines including strong dual-encoder based fine-tuning approaches.\n* For k=1, AdaCUR consistently outperforms AnnCUR under all settings and outperforms strong dual-encoder based retrieve-and-rerank approaches at inference cost budgets >= 100. \n\n* We agree that the total number of items and number of anchor queries affect the performance of AdaCUR as well as baselines.  \n    * For this reason, we presented results for multiple datasets/domains containing varying number of items (from 10K items in domain=YuGiOh to 5 Million items in HotpotQA dataset).\n    * We also show results for different number of anchor queries in Figure 13, 14 and 15 for domains in ZeShEL dataset, and as expected performance of AdaCUR over retrieve-and-rerank baselines generally improves with the number of anchor/training queries.\n \n* A few combinations where retrieve-and-rerank approaches perform better than AdaCUR\n    * In Fig 14a, when AdaCUR uses _only_ 100 anchor queries for indexing the items, dual-encoder based retrieve-and-rerank performs better than AdaCUR at small cost budgets (e.g. cost=50). \n    * But even in these settings, AdaCUR _closely matches or outperforms_ dual-encoders at larger cost budgets.\n\n\n**Why is the improvement when k=10 often more prominent than the improvement when $k=1$ and $k=100$?**\n\n  * We would like to note that AdaCUR offers consistent improvements over baselines for all values of $k=1, 10, 100$ as shown in Figure 2. \n  * The improvements for $k=10$ might appear to be more prominent than for $k=1$ and $k=100$ as the trends for relative improvements over baselines vary by baseline and are also affected by the inference cost.\n    * For instance, the improvements provided by $\\text{AdaCUR}_{\\text{DE-Base}}$ over dual-encoder (DE) baselines consistently increase as we go from $k=1$ to $k=100$.\n    * The improvement provided by AdaCUR over the corresponding AnnCUR baseline tends to be larger at smaller cost budgets and the marginal improvement tends to diminish for larger cost values and for larger values of $k$.\n\n\n**Why is AnnCUR baseline even worse than TF-IDF in Figures 14 and 15?**\n  * Performance of AnnCUR baselines (Yadav et al. 2022) depends on number of anchor queries used for indexing, number of anchor items chosen at test-time and method for choosing anchor items.\n  * Generally performance of CUR-based methods improve with the number of anchor queries and when using 500 or more queries for indexing the items ( see purple bars in Fig. 14b, 14c, 15b, 15c), $\\text{AnnCUR}_\\text{TF-IDF}$ which uses TF-IDF to sample anchor items, outperforms TF-IDF.\n  * Vanilla variant of AnnCUR baseline (which samples anchor items uniformly at random) sometimes performs worse than TF-IDF baseline under some configurations such as for small values of inference cost budget for the following reason:\n    * Recall that AnnCUR has to split the cost budget between choosing the anchor items and re-ranking items retrieved based on approximate scores. \n    * For instance, at cost=50, AnnCUR uses around 20 to 30 CE calls to score anchor items chosen uniformly at random, and uses the remaining budget of at most 30 CE calls for re-ranking items retrieving based on approximated cross-encoder scores. \n    * Such a small number of anchors chosen at random result in poor approximation of cross-encoder and consequently poor performance when re-ranking up to 30 items retrieved with the approximate scores. \n    * In comparison, TF-IDF based retrieve-and-rerank baselines get to use the entire budget to re-rank 50 items and may perform marginally better than the AnnCUR baseline. \n    * However, note that AnnCUR baseline matches or outperforms TFIDF at larger cost budgets and larger values of $k$", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "Overall the CUR factorization presents an interesting view of how cross-encoder approaches can be accelerated in practice. The proposed method has proper motivation to better approximate the cross-encoder scores of the nearest items. Experiment shows AdaCUR has higher recall than AnnCUR with the same cross-encoder model.", "reasons_to_reject": "In the experiments, the authors compared AdaCUR with AnnCUR, dual-encoder methods (probably by Zhang and Stratos, 2021; the authors didn't specify), and TF-IDF baselines. But more recent methods are not included in the experiments. Please see the missing references for a list of potential papers for comparison.\n\nWhile this paper pays good attention on keeping the cost fixed, i.e. having the same number of cross-encoder inferences, real-world time costs will depend on the size of the item collection, the number of anchor queries, and the number of anchor items. When is AdaCUR favored against the retrieve-and-rerank strategy and other methods that avoid cross-encoder models, in terms of the problem size? And when is AdaCUR not favored? These are the questions that might be more interested to readers, rather than merely an improvement of the recall metric. Maybe the current writing is limited by the page length of a short paper, but I believe it could even be converted to a regular paper if the above questions are addressed.\n\nThe current paper writing is not self-contained. I have to go through the previous AnnCUR paper in order to understand what is happening.", "questions_to_authors": "**A.** Please add experiment results of more recently proposed methods for comparison. The list of missing references below includes some candidate methods.\n\n**B.** Not sure if I missed it, but why is the improvement when k=10 often more prominent than the improvement when k=1 and k=100? Also, why is AnnCUR even worse than TF-IDF in Figures 14 and 15 in the appendix?", "paper_topic_and_main_contributions": "AdaCUR is an extension of AnnCUR, a method of efficiently leveraging cross-encoders for KNN search in the context of entity linking, passage retrieval, etc. AdaCUR has meaningful yet incremental improvement over AnnCUR. The key insight is that while the anchor queries are selected in the offline indexing stage and considered as fixed, the anchor items may change at test-time based on the test query.", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {"Missing_References": "1. MuVER: Improving First-Stage Entity Retrieval with Multi-View Entity Representations, EMNLP 2021.\n2. Towards Better Entity Linking with Multi-View Enhanced Distillation, ACL 2023.\n3. A Transformational Biencoder with In-Domain Negative Sampling for Zero-Shot Entity Linking, ACL 2022.\n4. EntQA: Entity Linking as Question Answering, ICLR 2022.\n5. Entity Linking via Explicit Mention-Mention Coreference Modeling, NAACL 2022.\n6. TempEL: Linking Dynamically Evolving and Newly Emerging Entities, Neurips 2022.\n7. Modeling Fine-grained Information via Knowledge-aware Hierarchical Graph for Zero-shot Entity Retrieval, WSDM 2023.", "Typos_Grammar_Style_and_Presentation_Improvements": "The abstract is unnecessarily long. Without the context of anchor queries, anchor items, and CUR, the description of the shortcoming of AnnCUR and the mechanism of AdaCUR doesn't make too much sense for a reader.\n\nThe introduction section needs to be more self-contained. As of now, it never introduced the concept of anchors and CUR properly. Figure 1 would be of great insight if the CUR framework was introduced first; otherwise, the discussion of approximating the average scores well and the need for biased sampling don't have the right context.\n\nLine 84: q_test is used here while the definition of test-time queries doesn't appear until Line 112.\n\nLines 103-123 are actually AnnCUR. AdaCUR starts from Line 124. I suggest changing the titles of sections 2.1 and 2.2 accordingly.\n\nLine 126: \"for a given budget B_CE of CE calls\". I would really appreciate a rephrase for easier understanding: \"for a given budget B_CE, the number of total CE calls\".\n\nAlgorithm 1, Line 16: This plus operator is not defined in the paper; I can only guess it.\n\nOverall, I think the writing should be reorganized."}}]

Author rebuttal:

Meta-review: This paper presents ADACUR to improve upon previously proposed method of annCUR  by improving the set of anchor items over multiple rounds of retrieval. The motivation of this paper is mostly acknowledged by the reviewers, however, there are major concerns on the novelty, comparison or discussion with recent literature, and the presentation (many parts are unclear and there are numerous grammars). Significant improvement over the quality of this paper is required.
Decision: Accept-Findings