Adaptive Retrieval and Scalable Indexing for k-NN Search with Cross-Encoders
Authors: Nishant Yadav
Nicholas Monath
Manzil Zaheer
Rob Fergus
Andrew McCallum
Venue: ICLR 2024 poster (2024)
Keywords: cross-encoder
kNN
retrieval
nearest-neighbor search
Primary area: metric learning, kernel learning, and sparse coding

Abstract: Cross-encoder (CE) models which compute similarity by jointly encoding a query-item pair perform better than using dot-product with embedding-based models (dual-encoders) at estimating query-item relevance. Existing approaches perform k-NN search with cross-encoders by approximating the CE similarity with a vector embedding space fit either with dual-encoders (DE) or CUR matrix factorization. DE-based retrieve-and-rerank approaches suffer from poor recall as DE generalizes poorly to new domains and the test-time retrieval with DE is decoupled from the CE. While CUR-based approaches can be more accurate than the DE-based retrieve-and-rerank approach, such approaches require a prohibitively large number of CE calls to compute item embeddings, thus making it impractical for deployment at scale. In this paper, we address these shortcomings with our proposed sparse-matrix factorization based method that efficiently computes latent query and item representations to approximate CE scores and performs k-NN search with the approximate CE similarity. In an offline indexing stage, we compute item embeddings by factorizing a sparse matrix containing query-item CE scores for a set of train queries. Our method produces a high-quality approximation while requiring only a fraction of CE similarity calls as compared to CUR-based methods, and allows for leveraging DE models to initialize the embedding space while avoiding compute- and resource-intensive finetuning of DE via distillation. At test time, we keep item embeddings fixed and perform retrieval over multiple rounds, alternating between a) estimating the test query embedding by minimizing error in approximating CE scores of items retrieved thus far, and b) using the updated test query embedding for retrieving more items in the next round. Our proposed k-NN search method can achieve up to 5 and 54 improvement in k-NN recall for k=1 and 100 respectively over the widely-used DE-based retrieve-and-rerank approach. Furthermore, our proposed approach to index the items by aligning item embeddings with the CE achieves up to 100x and 5x speedup over CUR-based and dual-encoder distillation based approaches respectively while matching or improving k-NN search recall over baselines.

Published as a conference paper at ICLR 2024
ADAPTIVE RETRIEVAL AND SCALABLE INDEXING FOR K-NN SEARCH WITH
Nishant Yadav!, Nicholas Monath?, Manzil Zaheer², Rob Fergus Andrew McCallum University of Massachusetts Amherst, 2 Google DecpMind
ABSTRACT
Cross-encoder (CE) models which compute similarity by jointly encoding a query-item pair perform better than using dot-product with embedding- based models (dual-encoders) at estimating query-item relevance. Existing approaches perform k-NN search with cross-encoders by approximating the CE similarity with vector embedding space fit either with dual-encoders (DE) or CUR matrix factorization. DE-based retrieve-and-rerant approaches suffer from poor recall as DE generalizes poorly to new domains and the test-time retrieval with DE is de- coupled from the CE. While CUR-based approaches can be more accurate than the DE-based retrieve-and-rerank approach, such approaches require prohibitively large number of CE calls to compute item embeddings, thus making it imprac- tical for deployment at scale. In this paper, we address these shortcomings with our proposed sparse-matri factorization based method that efficiently computes latent query and item representations to approximate CE scores and performs k- NN search with the approximate CE similarity. In an offline indexing stage, we compute item embeddings by factorizing a sparse matrix containing query-item CE scores for set of train queries. Our method produces high-quality ap- proximation while requiring only a fraction of CE similarity calls as compared to methods, and allows for leveraging DE models to initialize the em- bedding space while avoiding compute- and resource-intensin finetuning of DE via distillation. At test time, keep item embeddings fixed and perform retrieval over multiple rounds, alternating between a) estimating the test query emhedding by minimizing error in approximating CE scores of items retrieved thus far, and b) using the updated test query embedding for retrieving more items in the next round. Our proposed k-NN search method can achieve up to 5% and 54% im- provement in k-NN recall for &o = and 100 respectively over the widely-used DE-based retrieve-and and-rerank approach. Furthermore, our proposed approach index the items by aligning item embeddings with the CE achieves up to 100x and 5x speedup over CUR-based and dual-encoder distillation based approaches respectively while matching improving k-NN search recall over baselines.
INTRODUCTION
Efficient and accurate nearest neighbor search is paramount for retrieval (Menon et al. 2022 Rosa
et al.
2022, Qu al., 2021). classification in large output spaces (e.g., entity linking (Ayoola al.
2022
Logeswaran et al. 2019 Wu et al., (0200). non-parametric models (Das et al. 2022 Wang
al.
2022), and many other such applications machine learning (Goyal et al. [022]] Izacard
et al.
2023 Bahri et al., 2020). The accuracy and efficiency of nearest neighbor search depends on combination of factors (1) the computational cost of pairwise distance comparisons between datapoints, (2) preprocessing time for constructing a nearest neighbor index (e.g., dimensionality reduction [ndyk 2000), quantization (Ge al.) 2013 Guo et al. 2222)). data structure construc- tion (Beygelzimer et al.] 2006, Malkov & Yashunin 2018) Zaheer et al. 2019),, and (3) the time taken query the index to retrieve the nearest neighhor(s).
Similarity functions such cross-encodert which take pair of data points as inputs and directly output a scalar score, have achieved state-of-the-art results on numerous tasks (e.g., QA (Qu et al.)
Now at Google DeepMind

---

Published as a conference paper at ICLR 2024
2021 Thakur et al. 2021b), entity linking (Logeswaran et al. 2019 However, these models are exceptionally computationally expensive since these are typicall parameterized by several layers of neural models such transformers (Vaswani et al. 2017). 7, and scoring each item for given query requires a forward pass of the large parametric model, making them impractical similarity functions to use directly in nearest neighhor indices (Yadav et al.] 2022). Initial work has approx search with cross-encoders (CE) for a given test query using heuristic retrieve-and-rere
approach that uses separate model retrieve a subset of items followed by re-ranking using the CE. Prior work performs the initial retrieval using dot dot-product of sparse query/item embedding from models such as BM25, or dense query/item embeddings from models such as dual-encoders (DE) which are typ- ically trained on the same task and data as the CE. To support search with CE, recent work (Yadav) et al., 2022 2023) improves upon heuristic retrieve-and-rerant approaches, by directly learning an embedding space that approximates the CE score function. These approaches use CUR decompo- sition (Mahoney & Drineas 2009) to compute (relatively) low-dimensional embeddings for queries and items. The item embeddings are computed by scoring each item against set of anchor/train queries. At test-time, the test query embedding is computed by using CE scores of the test query against set of (adaptively-chose) anchor items.
Both DE- based sarieve-anddrerank and CUR- methods are not well suited for a typical appli- cation setting in k-NN search building an index ilarity function. The DE-based approach has several disadvantages in this setting. DE models show poor generalization new domains and thus require additional fine-tuning on the target domain to improve performance Yadav et al. (2022): Thakur et al. (2021a). This can be both resource-intensive as well time-consuming Furthermore, requires access to the parameters (not just embedding out- puts) of the DE, which might not be possible if the DE is provided by an API service On the other hand, while CUR-based approaches outperform fine-tuning of DE, they require computing a dense score matrix by scoring each item against a set of anchor/train queries. This does not scale well with the number of items. For instance, for a domain with 500 anchor/train queries and 10K items, it takes around 10 hours to compute the dense query- item score matrix with a CE parameterized using bert- base (Yadav et al.) (022). By simple extrapolation, indexing 5 million items using 500 queries would take around 5000 GPU hours.
new set of targets with given (trained) sim-
serreve-and-rerann approaches without additional
In this paper, we propose a sparse-matrix of fitting embedding space to approximate the cross-encoder for k-NN search. Our proposed approach significantly reduces the offline indexing cost as compared to existing approaches by con- structing sparse matrix containing cross-encoder scores between a of training queries (Qmmin) and all the items (Z), and using efficient matrix factorization methods to produce a set of item embeddings that are aligned with the cross-encoder. At test-time, our proposed approach, AxN, computes test query embedding to approximate cross-encoder scores between the test query and items, and performs retrieval using approximate cross-encoder scores. AxN performs retrieval over multiple rounds while keeping the item embedding fixed and incrementally refining the test query embedding using cross-encoder scores of the items retrieved in previous rounds. In the first round, the cross-encoder is used to score the test query against a small number of items chosen uniformly at random or baseline retrieval methods such as dual-encoder or BM25, In each subsequent round, AxN alternates between (a) updating the test query embedding to improve the approximation of the cross-encoder score of items retrieved so far, and (b) retrieving additional items using the improved approximation of the cross-encoder, and computing the exact cross-encoder scores for the retrieved items. Finally, the retrieved items are ranked based on exact cross-encoder scores and the top-k items returned as the k-nearest neighbors for the given test query.
ieariization-based approach to improve the efficiency
We perform an empirical evaluation of our method using cross-encoder models trained for the task of entity linking and information retrieval on ZESHEL (Logeswaran al. 2019) and BEIR (Thakur) ett al. 2021bb benchmark respectively. Our proposed k-NN search method can be used together with dense item embeddings produced by any method such as baseline dual-encoder models and still yield up to 5% and 54% improvement in k-NN recall for & =1 and 100 respectively over retrieve- and-rerank style inference with the same dual-encoder. Furthermore, our proposed approach to align item embeddings with the cross-encoder achieves up to 100x and 5x speedup over CUR- based approaches and training dual-encoders via distillation-basee respectively while matching or improving test-time k-NN search recall over baseline approaches.
'On an Nvidia 2080ti GPU with 12 GB memory using hatch size=50
2

---

Published as a conference paper at ICLR 2024
2 PROPOSED APPROACH
Task Description A cross-encoder model f 2 x - R maps a query-item pair (g. E Q x I scalar similarity. We consider the task of similarity search with the cross-encoder, in particular finding the k-nearest neighbors items for given query from a fixed set of items I:
N(g) arg topk f(g, i)
VEI
where arg topk returns the indices of the top scoring items of the function. Exact k-NN search with cross-encoder would require O ([] cross-encoder calls an item needs to be jointly encoded with the test query in order to compute its score, Since cross-encoders are typically parameterized using deep neural models such as transformers (Vaswani et al. 2017p. O(I)) calls to the cross-encoder model can be prohibitively expensive at test time. Therefore, we tackle the task of approximate
k-NN search with cross-encoder models. Let ((..-) denote the approximation to the cross-encoder that is learned using exact cross-encoder scores for sample of query-item pairs. We refer to the approximate k-nearest neighbors as N(q) & arg topk (q. and measure the quality of the approximation using nearest neighbor recall: (i(g))N(e)
[N(a))
In this work, assume black-box access the cross-encode access to the set of items and train queries from the target domain, and a base dual-encoder (DE trained on the same task and source data as the cross-encoder. In $2.1 we first present proposed sparse-matrix factorization based method to compute item embeddings in an offline step. (2.2 we present an online approach to compute test query embedding approximate the cross-encoder scores and perform k-NN search using the approximate cross-encoder scores.
2.1 PROPOSED OFFLINE INDEXING OF ITEMS
In this section, we describe our proposed approach to efficiently align the item embeddings with the cross-encoder where efficiency is measured in terms of the number of training samples (query- item pairs) required to be gathered and scored using the cross-encoder and wall-clock time to fit an approximation of the cross-encoder model. We consider approximation of the cross-encoder with an inner-product space where query (ạ) and an item (i) are represented with d'dimensional vectors u, E Rd and v, E Rd respectively. k-NN search using this approximation corresponds solving the following vector-based nearest neighbor search:
Ñ(()) A arg topk v. iEI
This vector-based k-nearest neighbor search can potentially be made more efficient using data struc- tures such as cover trees (Beygelzimer et al.) (006)), HNSW (Malkov & Yashunin, 2018). or any of the many other highly effective vector nearest neighbor search indexes (Guo et al.) 2020 John- son et al., 2019). The focus of our work is not on new way to make the vector nearest neighbor search more efficient, but rather to develop efficient and accurate methods of fitting the embedded representations of uy and v! to approximate the cross cross-encoder scores.
Let G R [ denote the pairwise similarity matrix containing the exact cross-encoder the pairs of training queries (Qusin) and items (I). We assume that is partially observed or incomplete, that is only very small subset of the query-item pairs (P (Prain) observed in G. Let U E I 2xdl and V E IR [x] be matrices such that each row corresponds to the embedding of query E Qutin and an item E I respectively. We optimize the following widely-used objective for matrix completion to estimate U and V via stochastic gradient descent:
min Ue Vee Verlzi xa || - -UV-
where (.)m.. denotes projection on the set of observed entries in G. There are two important con- siderations: (1) how to select with values of G' to observe (and incur the cost of running the cross- encoder model), and (2) how to compute/parameterin the matrices U and V.
A Approximating neural scoring function by compressing, approximating, quantizing the scoring function widely studied but outside the scope of this paper.
3

---

Published as a conference paper at ICLR 2024
Given set of items (I) and train queries (Qurin), construct the sparse matrix G by selecting ka items In C I for each query 9 E Quai either uniformly at random or using top-ka items from baseline retrieval method such as the base dual-encoder (DEsac). This approach requires kid Qmain calls to the cross-encoder. We also experiment with an approach that selects ka queries Qi Qurin each item E I, and thus requires ka calls to the cross-encoder.
Constructing Sparse Matrix G
Parameterizing and Training U and V
Transductive (MFTaxs): In this setting, U and V are trainable parameters and are learned by optimizing the objective in Eq. 4 U and V can be optionally initialized using query and item embeddings from the base dual-encoder (DEssc). Note that this parameterization requires scoring each item against at least small number of queries to update the embedding of an item from its initialized value, thus requiring scoring of ([Z)) query-item pairs to construct the sparse matrix G. Such an approach may not scale well with the number of items as the number of cross-encoder calls to construct G and the number of trainable parameters are both linear in the number of items. For instance, when Z = million, d = 1000, V would contain 5 billion trainable parameters.
Inductive (MFi) In this setting, we train parametric models to produce query and item em- beddings U and V from (raw) query and item features such as textual descriptions of queries and items. Unlike transductive approaches. inductive matrix factorization approaches can produce em- beddings for unseen queries and items, and thus can be used to produce embeddings for items not scored against any train query in matrix G' as well embeddings for test queries ytast Qirain Prior work typically uses DESRE (a DE trained on the same task and source domains as the CE) and finetunes DESRc the target domain via distillation using the CE. However, training all parameters of such parametric encoding models via distillation can be compute- and resource- intensive these models are built using several layers of neural models such as transformers. Recall that our goal is to efficiently build an accurate approximation of the CE on given target domain. Thus, improve the efficiency of fitting the approximation of the CE, we propose to train a shallow MIP model (using data from the target domain) that takes query/item embeddings from DESse as input and outputs updated embeddings while keeping DEsRc parameters frozen.
2.2 PROPOSED TEST-TIME K-NN SEARCH METHOD: Axn
At test-time, we need to perform k-NN search for a test query (test & Quain and thus need to compute an embedding for the test query in order to approximate cross-encoder scores and perform retrieval with the approximate scores. Note that computing the test query embedding by factorizing the matrix G at test-time while including the test query Ites= is computationally infeasible. Thus, an ideal solution would be compute item representations in offline indexing step, and compute the test query embedding on-the-fly while keeping item embeddings fixed. A potential solution is to use parametric model such as DESRC or MF'IDd compute test query embedding, perform retrieval using inner-product scores between test query and item embeddings, and finally, re-rank the retrieved items using the cross-encoder. While such a retrieve aede--nddrrrrnn approach can work, the retrieval step on such an approach is decoupled from the re-ranking model, and thus may result in poor recall.
In this work, we propose an adaptive approach AXN, which stands for "Adaptive Cross-Encodes Nearest Neighbor Search". As described in Algorithm [ Axn performs retrieval over R rounds while incrementally refining the cross-encoder approximation for Stest by updating ug the em- bedding for eat The test-time inference latency (and throughput) depends largely on the number of cross-encoder calls made at test time as each cross-encoder call requires forward pass through a large neural model. Thus, we operate under a fixed computational budget which allows for up to Ben cross-encoder calls at test-time.
Let A, be the cumulative set of items chosen up to round r. In the first round (r = 1), we select BeE/R items either uniformly random or using separate retrieval models such as dual-encoders or BM25 and compute the exact cross-encoder scores of these items for the given test query. We compute the test query embedding Ug... by solving the following system of linear equations
VA, Ugrest a,
(4)
where VA, E Rl... contains embeddings for items in A,, and a, contains cross-encode scores for (test paired with items in A, In round > 1, we select additional Bee/R R items from I \ A,
4

---

Published as a conference paper at ICLR 2024
Algorithm AXN Test-time k-NN Search Inference
Input: q: Test query. V E | Item Embeddings. Number iterative search rounds, hy Number of items to retrieve in each round. fe: Cross-Encoder (CE) model
2: Output: S: Approximate scores of q with all items, Ag: Retrieved items with CE scores in ag-
3: A1 + ks,
+> Initial set items D CE scores of g with items in A
4: aı < [o[g, i)] Lil-inaa---eerssoonnll.itoo V,Ai, ai)
5: u, to R do
Dx Compute query embedding by solving Eq
6: for
7: 5(r) uy x VT
Update approx. scores
8: A, 1 U Varg ao
>> Retrieve k2 new items
9: a, a [fo(q: 1kke,, (A-)
D> Compute CE scores of new items
10: u, - Solve-Lincar Love--LinarRRegressionl (e
D> Compute query embedding by solving Eq
11: $ <- u-u,VV VT
D Compute approx. scores
12: return S,Ax, as
using inner-product of test query embedding U and item embeddings v; (line 8 in Alg.
A, A,
arg topk LEZVA,,,ABBB//
Uggesse V
After computing A,, we compute CE scores for new items chosen in round r, and we update the test query embedding u. by solving Eq. 4 with the latest set of items A, which includes additional items selected in round Note that solving for Ugee in Eq is akin to solving linear regression problem with embeddings of items A, as features and croos-e scores of the items as re- gression targets. We solve Eq. analytically to get ug = (VI, V where M denotes pseudo-inverse of a matrix M.
At the end of R rounds, we obtain Ax containing Bee items, all of which have been scored using the cross-encoder model. We return top-k items from this set sorted based on exact cross-encoder scores the set of approximate k-NN for given test query geest
N(qlest) = arg topk f(queat, YEAx
(6)
Regularizing Test Query Embedding The system of equation in Eq 4 in round r contains |A, equations with d variables and an under-determined system when A, < d. such a case, there exist infinitely many solutions to Eq 4 and the test query embedding Ug.... can achieve zero approximation eтror on items in A,, and may show poor generalization when estimating cross- encoder scores for items in I A,,. Since the approximate scores are used to select the additional set of items in round r++ 1 (line g in Alg. D. such poor approximation affects the additional set of items chosen, and subsequently, it may affect the overall retrieval quality in certain settings. To avoid such overfitting, we compute the final test query embedding as:
0g Aoua (1 (l (LinReg) + Au (param)
Yeast
Stast
(param) (LinReg) is the analytical solution to the linear system in Eq. 4 and Ug is the test query where Ugesst embedding obtained from a parametric model such as a dual-encoder or an inductive matrix factor- ization model. We tune the weight parameter À E [0, 1] on the dev set.
EXPERIMENTS
In our experiments, we evaluate proposed approaches and baselines on the task of finding k-nearest neighbors for cross-encoder (CE) models as well as on downstream tasks. We use cross-encoders trained for the downstream task of zero-shot entity linking and zero-shot information retrieval and present extensive analysis of the effect of various design choices on the offline indexing latency and the test-time retrieval recall.
We run experiments on two datasets/benchmarks ZESHEL Logeswaran ct al. 2019), zero-shot entity linking benchmark, and BEIR benchmark Thakur et al. 2021b), a collection of information retrieval datasets for evaluating zero-shot performance of IR models. We
Experimental Setup
5

---

Published as a conference paper at ICLR 2024
separate CE models for ZESHEL and BEIR datasets, trained using ground -rruth labeled data from the corresponding dataset. For evaluation, we use two test domains from ZESHEL dataset -YuGiOh and Star Trek with 10K and 34K items (entities) respectively, and we use SciDocs and Hotpot-QA datasets from BEIR with 25K and 5M items (documents) respectively. These domains were not part of the data used to train the corresponding cross-encoder models. Following the precedent set by previous work (Yadav et al.) 2022 (023), we create a train/test split uniformly at random for each ZESHEL domain. For datasets from BEIR, we use pseudo-queries released as part of the benchmark as train queries and test on queries in the official test split in BEIR benchmark. We use queries the train split to train proposed matrix factorization models or baseline DE models via distillation, and we evaluate on the corresponding domain's 's test split. We refer interested readers to Appendix A for more details about datasets, cross-encoder training, and model architecture.
Baselines We compare with the following strieve-and-rerank baselines, denoted by RNRx, where top-scoring items wrt baseline scoring method X are retrieved and then re-ranked using the CE.
TF-IDF: It computes the similarity score for query-item pair using the dot-product of sparse query/item vectors containing TF-IDF weights.
Dual-Encoders (DE): It computes query-item scores using the dot-product of dense embeddings produced by encoding queries and items separately. We experiment with two DE models.
-EEsc:: DE trained on the same source data and downstream task as the cross-encoder model. This model is not trained or finetuned on the target domains used for evaluation in this work.
=DEps This corresponds to DESRC further finetuned via distillation using the cross-encoder model the targel domain i.e. the domain used for evaluation.
We also compare with ADACUR (Yaday et al., 2023). a CUR-based approach that computes a dense matrix with CE scores between training queries and all items index the items, and performs adaptive retrieval at test time. We use ADACUR to denote inference with ADACUR method when items in the first round are chosen using method X E (DEsse, TF-IDF]. We refer readers to Appendix A for implementation details for all baselines and proposed approaches.
Proposed Approach We construct the sparse matrix G on the target domain by selecting top- scoring items wrt DESac for each query in Quain followed by computing the CE scores for observed query-item pairs in G. We use DESRC to initialize embeddings for train queries and all items, fol- lowed by inductive (MFIso) or transductive (MFTRNs) matrix factorization while minimizing the objective function 3 We use the same sparse matrix G when training DE via distillation (DEpsn.) on the target domain. We use AxNx, to denote the proposed k-NN search method (22.) when using method X to compute item embeddings and method Y to retrieve items in the first round.
Evaluation Metrics Following the precedent set by previous work (Ydaa et al., 2022 2023 use Top-k-Recall @m for test queries the evaluation metric which measures the fraction of k-nearest neighbors as per the CE which are present in the set of m retrieved items. For each method, we retrieve m items and re-rank them using exact CE scores. We also evaluate the quality of the retrieved K--N items wrt the CE on the downstream task. We use entity linking accuracy for ZESHEL,, and we use downstream task specific nDCG@ and recall for BEIR domains.
For each approach, we calculate the time taken for indexing a given set of items from the target domain which involves some or all of the following steps: a) computing query/item embeddings using DESEC, b) computing (dense sparse) query-item score matrix G for Qrain c) madient-bbsedd training using G to estimate item embeddings for MF or parameters of models such as DE and MF and d) for DEPSTL and MFIND. computing updated item embeddings after training.
3.1 RESULTS
Figure [ shows Top- -Recal-e Inference-Cost=lU and Top-100-Recall Inference-Cost-500 ver- sus the total wall-clock time taken to index the items for various approaches on YuGiOh and Hotpot- QA. ADACUR can control the indexing time by varying Quain the number of train queries, while MF and distillation-ban based methods
control the indexing time by varying Quain and the number of items scored per train query (ka). For YuGiOh, we use Qurain < 500 for all methods, and for Hotpot-QA, we use 1 < 1K for ADACUR and Qmain I 50K with other methods.

---

Published as a conference paper at ICLR 2024
Baselines
Proposed
ADACUR
pifert Difm
Arr Drac
RdB Rren
ADACUR Deoe
Aot wite
Ar, mire
k= 1 10m== 100
A= 1000m=500
10m==10 100
A= 1100000mmm00 500
50-
Top-- -- R-Recall@@m
Top- k- Recalll
90
80-
00
70-
80
46-
60-
40-
70-
30
50-
10-1
10
10
10P
10
10
10P
10P
100
10P
Total Indexing Time (in hours)
Total Indexing Time (in hours)
(a) Domain YuGiOh, 10K items
(b) Domain = Hotpot-QA, million items
Figure 1: Top-I-Recall and Top-100-Recall at inference cost budget (m) of 100 and 500 CE calls respectively versus indexing time for various approaches. Matrix factorization approaches (MF) can be significantly faster than ADACUR and training DE via distillation (DEpsn)) The proposed adaptive k-NN search method (AxN) provides consistent improvement over corresponding retrieve- and-rerank style inference (RNR).
Proposed Inference (AxN) vs Retrieve-and-Rerank (RNR) AxN consistently provides im- provement over the corresponding retrieve-and-rerank (RNR) baseline. For instance, AXNDE DEsc provides an improvement of 5.2% for k=1 and 54% for k=100 over RNR for domain=YuGiOh. Note that this performance improvement comes at no additional offline indexing cost and with neg- ligible test-time overhead R RNR performs poorly on YuGiOh while it serves as strong base- line for Hotpot-QA, potentially due to differences in task, data, and CE model. On Hotpot-QA, Top-k-Recal for AXN can be further improved by sampling items in the first round using TF-IDF (AXN2.1-ir) instead of DESRC (AXNZ,DE..)) for all indexing methods Z E {DEsee, DE MF].
SciDocs
Hotpot-QA
Mathod
24
50K, 1K
S DEEpTT
_ 10K, 1K
50K, 100
MP
Oraine
10K, 100
0112
10K. 100
Cost Breokdown
1K
012
1K,
CE Calls
Item Embedding
IK. 100
3,30
100
Traiting
Total Indexing Time (in hours)
Total Indexing Time (in hours)
Figure 2: Breakdown of indexing latency of MF and DEDSIL into various steps with training time shown on the right of each bar for different values of [urain| and no. of items scored per query (ka)-
Matrix Factorization vs DEDSTL Unsurprisingly, performance on the target domain can be further improved by using data from the target domain to fit an embedding space to approximate the CE. As shown in Figure
proposed matrix factorization based approaches (MF) can be significantly more efficient than the distillation based (DEpstL) approaches while matching or outperforming DE in terms of k-NN search recall in the majority of the cases. Figure shows the breakdown of total indexing time of DE and MF for different numbers of training queries (1Qmain)) D) and number of items scored per query (ka) using the CE in the sparse matrix G. As expected, both the time taken to compute G and the training time increases with the number of queries and the number of items scored per query. The training time does not increase proportionally after 10K queries as we allocated a maximum training time of 24 hours for all methods. For MF, the majority of the time is spent either in computing sparse matrix G or the initial item embeddings. While we report total GPU hours taken for CE calls to compute G and initial item embeddings. these steps can be easily parallelized across multiple GPUs without any communication overhead. Since DEDSH. trains all parameters of large parametric neural model, it requires large amounts of GPU memory and takes up to several hours In contrast, MF-approuchess require significantly less memory and training time as these approaches train the item embeddings as free parameters (MFTRss) or train
We refer readers B.I for analysis of overhead incurred by AxN
"We trained -ual-encoders on an Nvidia RTX8000 GPU with 48 GB memory for a maximum of 24 hours. We used Nvidia 2080ti with 12 GB memory for MF-hased methods.
7

---

Published as a conference paper at ICLR 2024
shallow neural network on top of fixed embeddings (MFIND) from existing DE. We report results for MFIRNN on small-scale domains (e.g. YuGiOh with 10K items) and for IND on large-scale domain Hotpot- QA (5 million items). We refer interested readers to Appendix B.3 for comparison of TF and IN on small- and large-scale datasets.
Proposed Approaches vs ADACUR Our proposed inference method (AxN) in combination with MF or DE can outperform or closely match the performance of ADACUR while requiring orders of magnitude less compute for the offline indexing stage, on both small- and large-scale datasets. For instance, ADACURDE requires 1000+ GPU hours for embedding 5 million items in Hotpot- QA, and achieves Top-l-Recall@ 100 = 75.9 and Top- hop-100-Recaa @ 500 44.8. In contrast, MFIND with 110K and 100 items per query takes less than three hours to item embeddings, and @ 500 = 42.6.
A AXNMF Dacc achieves Top-1-Recall @ 100 = 80.5 and
Baselines
Propzsed Approaches
RNR yoar
ADACUR THEP EXACT
ADOK oear miar
pileer DFom
AX8 nFan
R
pr..
ADACUB
DEin
AX8 Waar,
A38
Downstream Task Accuracy
Downstream Task Accuracy
Downstream Task nDCG010
Downstream Task nDCG@10
80.50
62.0
70
16.3
00.25
62.0
26.0-
49.70
02.0-
15.3
09.50
15.0-
55
61.3
49.25
Total Indexing Time (in hours)
Total Indexing Time (in hours)
Total Indexing Time (in hours)
Total Indexing
Time (in hours)
(a) YuGiOh
(b) Star Trek
(c) SciDocs
(d) Hotpot-QA
Figure 3: Downstream task performance versus indexing time for proposed and baseline approaches
on different domains. All methods use a fixed inference cost budget of 100 cross-encoder calls.
Downstream Task Performance Figure 3 shows downstream task performance proposed and baseline approaches including EXACT which performs exact brute-force search using CE at test- time. For -otpott-A,, we observe that improvement in k--N search accuracy results in improve- ment in downstream task performance with EXACT brute-force performing the best. We observe different trend on SciDocs YuGiOh, and Star Trek where EXACT search results in suboptimal performance as compared to RNRDE For instance, RNRDE achieves accuracy of 50.6 while the accuracy of EXACT is 49.8 on the downstream task of entity linking on YuGiOh. We believe that this difference in trends in k-NN search performance and downstream task performance could be due to differences in the training setup of the corresponding CE (i.e. the loss function and nega- tives used during training, see Appendix J..] for details) as well as the nature of the task and data. While beyond the scope of this paper, it would be interesting to explore different loss functions and training strategies such as using negative items mined using k-NN search strategies proposed in this work to improve the robustness and generalization capabilities of cross-encoders and minimize such discrepancies in A--N search and downstream task performance.
We refer readers to Appendix B for an analysis of the overhead incurred by AxN ( B son of AxN with pseudo-relevance feedback based approaches (BB.)), an analysis of design choices for our proposed approach B.4) and results on other downstream evaluation metrics for BEIR.
a compari-
4 RELATED WORK
Approximating Similarity Function Matrix factorization methods have been widely used for
computing low-rank approximation of dense distance and kernel matrices (Musco & Woodruff] 2017 Bakshi & Woodruff, [0188] Indyk et al. 2019), PPDD matrices (Ray et al. (022) as well as for estimating missing entries in sparse matrices (Koren et al. 2009 Luo et al. 2014 4 Yu et al. 2014 Mehta & Rana 2017 Xue et al. 2017). In this work, we focus on methods for factorizing sparse matrices instead of dense matrices as computing each entry in the matrix (i.e. CE score for query- item pair) requires a forward-pat pass through expensive neural model. An essential assumption for matrix completion methods is that the underlying matrix M is low-rank, thus enabling recovery of the missing entries while only observing a small fraction of entries in M (Candes & Recht 2012
8

---

Published as a conference paper at ICLR 2024
Nguyen et al. 2019). Theoretically, such matrix completion methods require ((x)) samples to cover an m x n matrix of rank r with m S n (Krishnamurthy & Singh 2013 Xu et al. 2015). The sample complexity can be improved in the presence of features describing rows and columns of the matrix, often referred to as side information (Jain & Dhillon 2013) Xu et al. 2013 Zhong et al. 2019). Inductive matrix completion (MD) approaches leverage such query and item fea- tures to improve the sample complexity and also enable generalization to unseen queries (rows) and items (columns). Training dual-encoder (DE) models via distillation using a cross-encoder (CE), where the DE consumes raw query and item features (such as query/item description) and produces query/item embeddings, can be seen as solving an inductive matrix factorization problem. A typ- ical training objective for training DE involves minimizing the discrepancy between CE (teacher model) and DE (student model) scores on observed entries in the sparse matrix (Hofstätter et al.) 2020 Reddi et al., 2021] Thakur et al., (021a). Recent work has explored different strategies for training of DE such as curriculum learning based methods (Zeng et al.) joint training of CE and DE to mutually improve the performance of both models (Liu et al. 2022
distillation-
2022).
Ren et al. 2021). Inductive MF methods (MFIsD) used in this work also share similar motivations to adapters (Houlsby et al.] 2019) which introduce small number of trainable parameters between lay- ers of the model, and may reduce training time and memory requirements in certain settings (Rückle let al. 2021). MFIND used in this work only trains a shallow MLP on top of query/item embeddings from DE while keeping DE parameters frozen, and does not introduce any parameters in the DE.
Nearest Neighbor Search K-NN search has been widely studied in applications where the inputs are described as vectors in R2d (Clarkson et al. 2006; Li al. 2019), and the similarity is com- puted using simple (dis- ttiss)simillrity functions such as inner- produproduct (Johnson et al., 2019 Guo et al.,
2020 and fz-distance (Kleinberg 1997, Chávez et al. 2001 Hjaltason Samet 2003). These ap- proaches typically work by speeding up each distance/similang
computation (Jegou et al. 2010 Hwang et al., 2012 /Zhang et al., 2014| Yu et al., 2017: [Bagaria et al. 202T) as well as constructing
tree-based (Beygelzimer et al. 2006;] Dong et al. 20.0)) or graph-based data structures (Malkov & Yashunin 2018 Wang et al. 202 la Groh et al. (2022) over the given item set to efficiently navigate and prune the search space to find (approximate) K-NN items for a given query. Recent work also explores such graph- based (Boytsov & Nyberg, 2019a Tan et al. 2020: 2021 MacAvaney et al.) 2022), or based (Boytsov & Nyberg 2019b) data structures for metrrei and parametric sim- ilarity functions. Another line of work explores model quantization (Nayak et al. 2019 Liu et al.) )021) and early-exit strategies (Xin et al. 20200a b) to approximate the neural model while speeding up each forward pass through the model and reducing its memory footprint. It would be interesting to study if such data structures and approaches to speed up cross-encoder score computation can be combined with matrix factorization based approaches proposed in this work to further improve recall-vs-cost trade-offs for k--N search with cross-encoders.
Relevd-e Feedback (PRF) Similar to PRF-based methods in information retrieval (Roc- chio Jr 1971 Lavrenko & Croft, 2001), our proposed k-NN search method AxN refines the test query representation using model based feedback. In our case, we use the cross-encoder scores of items retrieved in the previous round as feedback to update the test query representation. PRF-based approaches have been widely used in information retrieval for retrieval with sparse(Li et al.) 2018 Mao et al. 2020 202I) and dense embeddings (Yu et al. 2021 Wang et al. (2021b). We refer readers to Appendix x B.2 for comparison with a recent PRF-based method (Sung et al. (023).
5 CONCLUSION
In this paper, we present an approach to perform k-NN search with cross-encoders by efficiently ap- proximating the cross-encoder scores using dot- drodpuct of learned test query and item embeddings. In the offline indexing step, we compute item embeddings to index a given set of items from a target domain by factorizing a sparse query-item score matrix, leveraging existing dual-encoder models distillation-basee train-
to initialize the item embeddings while avoiding computationally-exeenssv ing of dual-encoder models. At test time, we compute the test query embedding to approximate cross-encoder scores of the given test query for small set of adaptively-chosen items, and perform retrieval with the approximate cross-encoder scores. We perform extensive empirical analysis on two zero-shot retrieval benchmarks and show that our proposed approach provides significant im- provement in test-time K-NN search recall-vs- vs-cost tradeoffs while still requiring significantly less compute resources for indexing items from target domain as compared to previous approaches.
9

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
We thank members of UMass IESL for helpful discussions and feedback. This work supported in part by the Center for Data Science and the Center for Intelligent Information Retrieval, in part by the National Science Foundation under Grant No. NSF1763618, 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 1668553, in part by Amazon Digital Services, and in part using highperformance computing equipment obtained under a grant from the Collaborative R&D Fund managed by the Massachusetts Technology Collaborative. Any opinions, findings, conclusions, and recommendations expressed in this material are those of the authors and do not necessarily reflect those of the sponsor(s).
REFERENCES
Tom Ayoola, Shubhi Tyagi, Joseph Fisher, Christos Christodoulopoulos, and Andrea Pierleoni. Re- FinED: An efficient zero-shot-capuble approach to end-to-end entity linking. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies: Industry Track, pp. 209-220. Association for Com- putational Linguistics, 2022.
Vivek Bagaria, Tavor Z Baharav, Govinda M Kamath, and N Tse David. Bandit-based monte carlo optimization for nearest neighbors. IEEE Journal on Selected Areas in Information Theory, 2(2): 599-610, 2021.
Dara Bahri, Heinrich Jiang, and Maya Gupta. Deep k-nn for noisy labels. In International Confer- ence on Machine Learning, pp. 540-550. PMLR, 2020.
Ainesh Bakshi and David Woodruff. Sublinear time low-rank approximation of distance matrices. Advances in Neural Information Processing Systems, 2018.
Alina Beygelzimer, Sham Kakade, and John Langford. Cover trees for nearest neighbor. In Pro- ceedings of the 23rd international conference on Machine learming, pp. 97-104, 2006.
Leonid Boytsov and Eric Nyberg. Accurate and fast retrieval for complex non-metric data via neighborhood graphs. In International Conference on Similarity Search and Applications, pp- 128-142. Springer, 2019a.
Leonid Boytsov and Erie Nyherg. Pruning algorithms for low-dimensional non-metric k-nn search: case study. In International Conference on Similarity Search and Applications, pp. 72-85. Springer, 2019b.
Emmanuel Candes and Benjamin Recht. Exact matrix completion via convex optimization. Com- munications the ACM, 55(6):111-119, 2012.
Edgar Chávez, Gonzalo Navarro, Ricardo Baeza-Yates, and José Luis Marroquín. Searching in metric spaces. ACM computing surveys (CSUR), 33(3):273-321, 2001.
Kenneth Clarkson et al. Nearest-neighhor searching and metric space dimensions. Nearest- neighbor methods for learning and vision: theory and practice, pp. 15-59, 2006.
Rajarshi Das, Ameya Godbole, Ankita Naik, Elliot Tower, Manzil Zaheer, Hannaneh Hajishirzi, Robin Jia, and Andrew McCallum. Knowledge base question answering by case-based reasoning over subgraphs. In International Conference on Machine Learning. PMLR, 2022.
Yihe Dong, Piotr Indyk, Ilya Razenshteyn, and Tal Wagner. Learning space partitions for nearest neighbor search. 2020.
Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. Optimized product quantization. IEEE transac- fions on pattern analysis and machine intelligence, 36(4):744-755 2013.
10

---

Published as a conference paper at ICLR 2024
Anirudh Goyal, Abram Friesen, Andrea Banino, Theophane Weber, Nan Rosemary Ke, Adrià Puig- domènech Badia, Arthur Guez, Mehdi Mirza, Peter C Humphreys, Ksenia Konyushova, Michal Valko, Simon Osindero, Timothy Lillicrap, Nicolas Heess, and Charles Blundell. Retrieval- augmented reinforcement learning. In Proceedings of the 39th International Conference on Ma- chine Learning, 2022.
Fabian Groh, Lukas Ruppert, Patrick Wieschollek, and Hendrik PA Lensch. Ggnn: Graph-based gpu nearest neighbor search. IEEE Transactions on Big Data, 911):667-273) 2022.
Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Cher, and Sanjiv Ku- mar. Accelerating large-scale inference with anisotropic vector quantization. In International Conference on Machine Learning, pp. 3887-3896, 2020.
Gisli Hjaltason and Hanan Samet. Index-driven similarity search in metric spaces (survey article). ACM Transactions Database Systems (TODS), 28(4):517-580, 2003.
Sebastian Hofstätter, Sophia Althammer, Michael Schröder, Mete Sertkan, and Allan Hanbury. Im- proving efficient neural ranking models with cross-architecture knowledge distillation. ArXiv, abs/2010.02666, 2020.
Neil Houlsby, Andrei Giurgiu, Stanislaw Jastrzebski, Bruna Morrone, Quentin De Laroussilhe, An- drea Gesmundo, Mona Attariyan, and Sylvain Gelly, Parameter-efficient transfer learning for nlp. In International Conference on Machine Learning, pp. 2090-22999999 PMLR, 2019.
Yoonho Hwang, Bohyung Han, and Hee-Kap Ahn. A fast nearest neighbor search algorithm by nonlinear embedding. In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pp. 3053-3060. IEEE, 2012.
Piotr Indyk. Dimensionality reduction techniques for proximity problems. In Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, pp. 371-378, 2000.
Pitor Indyk, Ali Vakilian, Tal Wagner, and David Woodruff. Sample-optimal low-rank approxi- mation of distance matrices. In Conference on Learning Theory, pp. 1723-1751. PMLR, 2019.
Gautier Izacard, Patrick Lewis, Maria Lomeli, Lucas Hosseini. Fabio Petroni, Timo Schick, Jane Dwivedi- Yu, Armand Joulin, Sebastian Riedel, and Edouard Grave. Atlas: Few-shot learning with retrieval augmented language models. Journal of Machine Learning Research, 24, 2023.
URL http: //jmr wwtpgp/ppp///////...
0037 .tmml
Prateek Jain and Inderjit S Dhillon. Provable inductive matrix completion. arXiv preprint 1rXiv:1306.0666, 2013.
Herve Jegou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(1):117-125 2010.
Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scas scale similarity search with gpus. IEEE Transactions on Big Data, 7(3):535-53 2019.
Jon M Kleinberg. Two algorithms for nearest-neighhor search in high dimensions. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pp. 599-608, 1997.
Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recommender systems. Computer, 42(8):30-37, 2009.
Akshay Krishnamurthy and Aarti Singh. Low-rank matrix and tensor completion via adaptive sam- pling. Advances in Neural Information Processing Systems, 26, 2013.
Victor Lavrenko and W. Bruce Croft. Relevance based language models. SIGIR '01, pp. 120-127. Association for Computing Machinery, 2001. ISBN 1581133316 doi: 10.1145/88955..883972 URL URL http:///oooooo1001111111 383977

---

Published as a conference paper at ICLR 2024
Canjia Li, Yingfei Sun, Ben He, Le Wang, Kai Hui, Andrew Yates, Le Sun, and Jungang Xu. NPRF: A neural pseudo relevance feedback framework for ad-hoc information retrieval. In Proceedings of the 2018 Conference Empirical Methods in Natural Language Processing, pp. 4482 4491. Association for Computational Linguistics, 2018. doi: 10. 10.18653/v1/D18-- 1-7881 URL https:
Wen Li, Ying Zhang. Yifang Sun, Wei Wang, Mingjie Li, Wenjie Zhang, and Xuemin Lin. Approx- imate nearest neighbor search on high dimensional data- experimens, analyses. and improve- ment. JEEE Transactions on Knowledge and Data Engineering, 32(8):1475-145 2019.
Fangxin Liu, Wenbo Zhao, Zhezhi He, Yanzhi Wang. Zongwu Wang, Changzhi Dai, Xiaoyao Liang, and Li Jiang. Improving neural network efficiency via post-training quantization with adaptive floating-poing point. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 52815528100 2021.
Fangyu Liu, Yunlong Jiao, Jordan Massiah, Emine Yilmaz, and Serhii Havrylov. Trans-encoder: Un- supervised sentence-pair modelling through self-and mutual-distillation.. In International Con- ference on Learning Representations, ICLR, 2022.
Lajanugen Logeswaran, Ming- Wei Chang, Kenton Lee, Kristina Toutanova, Jacob Devlin, and Honglak Lee. Zero-shot entity linking by reading entity descriptions. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 3449-3460. Association for Computational Linguisties, 2019.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Con- ference on Learning Representations (ICLR), 2019. URL https:://penrreviex net./
Forum?!d=BBççRRCGC))
Xin Luo, Mengehu Zhou, Yunni Xia, and Qingsheng Zhu. An efficient non-negative matrix- factorization- based approach to collaborative filtering for recommender systems. IEEE Trans- actions on Industrial Informatics, 10(2):1233-125 2014.
Sean MacAvaney, Nicola Tonellotto, and Craig Macdonald. Adaptive re-ranking with a corpus graph. In Proceedings of the 31st ACM International Conference on Information & Knowledge Management, pp. 1491-1500, 2022.
Michael W Mahoney and Petros Drineas. Cur matrix decompositions for improved data analysis. Proceedings of the National Academy of Sciences, 106(3):697-702,
2009. 2009.
Yu A Malkov and Dmitry A Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4):824-83) 836, 2018.
Yuning Mao, Pengcheng He, Xiaodong Liu, Yelong Shen, Jianfeng Gao, Jiawei Han, and Weizhu Chen. Generation-augmeette retrieval for open-domain question answering. arXiv preprint arXiv:2009.08553, 2020.
Yuning Mao, Pengcheng He, Xiaodong Liu, Yelong Shen, Jianfeng Gao, Jiawei Han, and Weizhu Chen. Generation-augmentii the 59th Annual Meeting of the Association for Computational Linguistics and the I I1th Interna- tional Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 4089- 4100. Association for Computational Linguistics, 2021. doi: 122053//12001..acllooro
retrieval for open-domain question answering. In Proceedings of
URL phttps://ae http:///acaatthohoooooo org/ 2021 acl 1 llogg 316
Rachana Mehta and Keyur Rana. A review on matrix factorization techniques in recommender systems. In 2017 2nd International Conference Communication Systems, Computing and IT Applications (CSCITA), pp. 269-274. IEEE, 2017.
Aditya Menon, Sadeep Jayasumana, Ankit Singh Rawat, Seungyeon Kim, Sashank Reddi, and San- jiv Kumar. In defense of dual-encoders for neural ranking. In International Conference on Ma- chine Learning. PMLR, 2022.
12

---

Published as a conference paper at ICLR 2024
Cameron Musco and David P Woodruff. Sublinear time low-rank approximation of positive semidef- inite matrices. In IEEE 58th Anmual Symposium on Foundations of Computer Science (FOCS), pp. 672-683. IEEE, 2017.
Prateeth Nayak, David Zhang, and Sek Chai. Bit efficient quantization for deep neural networks. In 2019 Fifth Workshop on Energy Efficient Machine Learning and Cognitive Computing-Neurlle Edition (EMC2-NIPS), pp. 52-56. IEEE, 2019.
Luong Trung Nguyen, Junhan Kim, and Byonghyo Shim. Low-rank matrix completion: A contem- porary survey. IEEE Access, 7:94215-94237, 2019.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
Yingqi Qu, Yuchen Ding, Jing Liu, Kai Liu, Ruiyang Ren, Wayne Xin Zhao, Daxiang Dong, Hua Wu, and Haifeng Wang. RocketQA: An optimized training 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 Linguistics: Human Language Technologies, pp. 5835-5847, Association for Computational Linguisties, 2021.
Archan Ray, Nicholas Monath, Andrew McCallum, and Cameron Musco. Sublinear time approxi- mation of text similarity matrices. Proceedings of the AAAI Conference on Artificial Intelligence, 36(7):8022-800, 2022.
Sashank Reddi, Rama Kumar Pasumarthi, Aditya Menon, Ankit Singh Rawat, Felix Yu, Seungyeon Kim, Andreas Veit, and Sanjiv Kumar. Rankdistil: Knowledge distillation for ranking. In Inter- national Conference on Artificial Intelligence and Statistics, pp. 2376-2376. PMLR, 2021.
Ruiyang Ren, Yingqi Qu Jing Liu, Wayne Xin Zhao, QiaoQiao She, Hua Wu, Haifeng Wang, and Ji-Rong Wen. RocketQAv2: A joint training method for dense passage retrieval and passage re-ranking. In Proceedings of the 2021 Conference on Empirical Methods in Nat- ural Language Processing. Association for Computational Linguistics, 2021. URL https:
//aclanthology.
org/2021. wtwpoholloo......222000//// emnlp main. 224
Joseph John Rocchio Jr. Relevance feedback in information retrieval. The SMART retrieval system: experiments in automatic document processing, 1971.
Guilherme Rosa, Luiz Bonifacio, Vitor Jeronymo, Hugo Abonizio, Marzich Fadace, Roberto Lotufo, and Rodrigo Nogueira. In defense of cross-encoders for zero-shot retrieval. arXiv preprint arXiv:22/2.06112,, 2022.
Andreas Rücklé, Gregor Geigle, Max Glockner, Tilman Beck, Jonas Pfeiffer, Nils Reimers, and Iryna Gurevych. AdapterDrop: On the efficiency of adapters in transformers. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 7930-7946. Association for Computational Linguistics, 2021. doi: 10. 116138616/2222111111 1etp2...mmlppne waw..m22.......m URL ac http:////aaaattoooggoeo org. 2021. emn 1 p-ma in. 626
Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. Distilbert, distilled version of bert: smaller, faster, cheaper and lighter. arXiv preprint arXiv:1910.01 2019.
Mujeen Sung, Jungsoo Park, Jaewoo Kang, Danqi Chen, and Jinhyuk Lee. Optimizing test-time query representations for dense retrieval. In Findings of the Association for Computational Lin- guistics: ACL 2023, pp. 5731-5746. Association for Computational Linguistics, 2023. URL
https://aclanthoi.oo org/2023 (treee....iiiii findings acl. 354
Shulong Tan, Zhixin Zhou, Zhaozhuo Xu, and Ping Li. Fast item ranking under neural network based measures. In International Conference on Web Search and Data Mining, pp. 591-599, 2020.
Shulong Tan, Weijie Zhao, and Ping Li. Fast neural ranking on bipartite graph indices. Proceedings of the VLDB Endowment, 15(4):794-803 2021.
13

---

Published as a conference paper at ICLR 2024
Nandan Thakur, Nils Reimers, Johannes Daxenberger, and Iryna Gurevych. Augmented SBERT: Data augmentation method for improving bi-encoders for pairwise sentence scoring tasks. In Pro- ceedings of the 2021 Conference of the North American Chapter the Association for Computa- tional Linguisties: Human Language Technologies, pp. 296-310. Association for Computational Linguistics, 2021a.
Nandan Thakur, Nils Reimers, Andreas Rücklé, Abhishek Srivastava, and Iryna Gurevych. BEIR: A heterogeneous benchmark for zero-shot evaluation of information retrieval models. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021b. URL httpttttt.//ppeeeeiiiitee http::/weee//rerreeeeeee L 1d=CC6655xF jea
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Informa- tion Processing Systems, 2017.
Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. A comprehensive survey and experimental comparison of graph-hased approximate nearest neighbor search. arXiv preprint MrXi::2101.12631, 2021a.
Shuohang Wang. Yichong Xu, Yuwei Fang, Yang Liu, Siqi Sun, Ruochen Xu, Chenguang Zhu, and Michael Zeng. Training data is more valuable than you think: A simple and effective method by retrieving from training data. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics ( (Volume 1: Long Papers), 2022.
Wenhui Wang, Furu Wei, Li Dong, Hangbo Bao, Nan Yang, and Ming Zhou. Minilm: Deep self- attention distillation for task-agnostic compression of pre-trained transformers. Advances in Neu- ral Information Processing Systems, 33:5776-3 -7888 2020.
Xiao Wang, Craig Macdonald, Nicola Tonellotto, and Iadh Ounis. Pseudo-relevance feedback for multiple representation dense retrieval. In Proceedings of the 2021 ACM SIGIR International Conference on Theory of Information Retrieval, pp. 297-306, 2021b.
Ledell Wu, Fabio Petroni, Martin Josifoski, Sebastian Riedel, and Luke Zettlemoyer. Scalable zero-shot entity linking with dense entity retrieval. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 6407. Association for Computational Linguistics, 2020.
Ji Xin, Rodrigo Nogueira, Yaoliang Yu, and Jimmy Lin. Early exiting BERT for efficient document ranking. In Proceedings of SustaiNLP: Workshop on Simple and Efficient Natural Language Processing, pp. 83 88. Association for Computational Linguisties, 2020a. doi: 10.18653/v1/ 2020.sustai 1.11.
wwtp://oooooo..../o//e////e// 0000
Ji Xin, Raphael Tang, Jaejun Lee, Yaoliang Yu, and Jimmy Lin. DeeBERT: Dynamic early exiting for accelerating BERT inference. In Proceedings of the 58th Annual Meeting of the Associa- fion for Computational Linguistics, pp. 2246-2251. Association for Computational Linguistics, 2020b. doi: (0.18653/11/2220.aal mww.ammmmm.................... 204. URL httph:tpp////m hel.ltttss///aaaattoooooo.////// acl wwi...n00.......................
Miao Xu, Rong Jin, and Zhi-Hua Zhou. Speedup matrix completion with side information: Appli- cation to multi-label learning. Advances in neural information processing systems, 26, 2013.
Miao Xu, Rong Jin, and Zhi-Hua Zhou. Cur algorithm for partially observed matrices. In Interna- tional Conference on Machine Learning, pp. 1412-1421. PMLR, 2015.
Hong-Jian Xue, Xinyu Dai, Jianbing Zhang, Shujian Huang, and Jiajun Chen. Deep matrix fac- torization models for recommender systems. In IJCAI, volume 17, pp. 3203-3209. Melbourne, Australia, 2017.
Nishant Yaday, Nicholas Monath, Rico Angell, Manzil Zaheer, and Andrew McCallum. Efficient Nearest Neighbor Search for Cross-encoder Models using Matrix Factorization. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. 2171-2194, 2022. URL htt.t:t/p//accccc wtw.aaccaantttooooooooooooooo wogg o 2222. emn cammlp-manne 140
14

---

Published as a conference paper at ICLR 2024
Nishant Yadav, Nicholas Monath, Manzil Zaheer, and Andrew McCallum. Efficient k-NN Search with Cross cross-encoders using Adaptive Multi-Roun CUR Decomposition. In Findings of the Asso- ciation for Computational Linguistics: EMNLP, 2023.
HongChien Yu, Chenyan Xiong, and Jamie Callan. Improving query representations for dense re- trieval with pseudo relevance feedback. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 3592-3596 2021.
Hsiang-Fu Fu Yu, Cho-Jui Hsich, Si, and Inderjit Dhillon. Parallel matrix factorization for recom- mender systems. Knowledge and Information Systems, 41:793-8133 819, 2014.
Hsiang-Fu Fu Yu, Cho-Jui Hsieh, Qi Lei, and Inderjit S Dhillon. A greedy approach for budgeted maximum inner product search. Advances in Neural Information Processing Systems, 30, 2017.
Manzil Zaheer, Guru Guruganesh, Golan Levin, and Alex Smola. Terrapattemn: A nearest neighbor search service. Pre-print, 2019.
Hansi Zeng, Hamed Zamani, and Vishwa Vinay. Curriculum learning for dense retrieval distillation. In Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 1979-1983, 2022.
Ting Zhang, Chao Du, and Jingdong Wang. Composite quantization for approximate nearest neigh- bor search. In International Conference Machine Learning, pp. 838 846. PMLR, 2014.
Kai Zhong, Zhao Song, Prateek Jain, and Inderjit Dhillon. Provable non- linear inductive matrix completion. Advances in Neural Information Processing Systems, 32, 2019.
A TRAINING AND IMPLEMENTATION DETAILS
Dataset
Domain
[Z]
( //eeel)) Splits
Train Query (Qrein) Type
ZESHEL
YuGiOh
10,031
(100/3274), (500/2874), (2000/1374)
Real Queries
ZESHEL
Star Trek
34,430
(100/4127), (500/3727), (2000/2227)
Real Queries
BEIR
SciDocs 25,657
{IK, 10K, 50K //000
Pseudo-Queries Pseudo-Queries
BEIR
Hotpot-QA
5,233,329
[IK, 10K, 50K //100/
Table 1: Statistics on number of items (I), number of queries in train (Quain) and test (Quea) splits for each domain. Following the precedent set by Yadav et al.) (2022). we create train/test split by splitting the queries in each ZESHEL domain uniformly at random, and experiment with three values of 1uminn| E {100, 500, 2000]. For BEIR domains, we use pseudo-queries released as part of the benchmark train queries (Quain) and run k-NN evaluation 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 all 1K test queries for SeiDocs.
A.1 TRAINING
MODELS
In experiments, [FMB] JCE, cross-encoder model variant proposed by Yadav et al. (022) that jointly encodes a query-item pair and computes the final score using dot-product of contextualized query and item embeddings extracted after joint encoding.
ZESHEL Dataset For ZESHEL, we use the cross-encoder model checkpoin released by Yadav al. (2022) We refer readers Yadav et al. (2022) for further details parameterization and training of the cross-encoder.
http://uughihaacccccosssaaayyaa crossene zeshel
15

---

Published as a conference paper at ICLR 2024
BEIR Benchmark For BEIR,
the cross-encoder model checkpoin trained MS-
MARCO dataset and released by Yadav et al. (2023) The cross-encoder model is parameterized modeel
using a 6-layer MINI-LM model (Wang et al. 2020) and uses the dot dot-product based scoring mech-
anism for cross-encoders proposed by) Yadav et al. 2022
A.2 TRAINING DUAL- AND MATRIX FACTORIZATION MODELS
For BEIR datasets, we train matrix factorization models and DERST. using sparse matrix G con- taining number of train queries Qrain E {1K, 10K, 50K) with number of items per query ka E {100, 1000}. For ZESHEL datasets, we use 1rainl E {100, 500, 2000} with the number of items per query ka E {100, 1000} for matrix factorization models and ka E (25, 100} for train- ing DEPSIL model. Table 1 shows train/test splits used for each domain.
A.2.1 TRAINING DUAL-ENCODER MODELS
We train dual-encoder models on Nvidia RTX8000 GPUs with 48 GB GPU memory.
ZESHEL dataset We report results for DE baselines as reported in Yadav et al. 2022)) The DE models were initialized using bert www.e-bucaseeeeee
and contain separate query and item encoders, thus resulting in total of 2 x 110M parameters. The DE models are trained using cross- entropy loss to match the DE score distribution with the CE score distribution. We refer readers to Yadav et al. (2022) for details related to training of DE models on ZESHEL dataset.
BEIR benchmark For BEIR domains, we use a dual-encoder model checkpoin 2 released as part of sentence-trane fornsfformes rmer repository as DÉSRC, unless specified otherwise. This DE model was initialized using distill 1 beebebbaass (Sanh et al., (019) model and trained on MS- MARCO dataset which contains 40 million (query, positive document (item), negative document (item)) triplets using triplet ranking loss. This DESRC is not trained and Hotpot-QA used for running k-NN experiments in this paper. We finetune DESRC via distil- lation the target domain to get the DEDSI 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-encoder by minimizing cross-entropy loss between predicted query-item scores (using DE) and target query-item scores (obtained using CE). We train DEnsm. using AdamW (Loshchilov & Hutter 2019) optimizer with learning rate 1e-5 and accumulating gra- dient over 4 steps. We trained for 10 epochs when using top-100 items per query and for 4 epochs when using 1001 items per query. We allocate maximum time of 24 hours for training.
target domains SciDocs
A.2.2 MATRIX-FACTORIIZATON MODELS
We train both transductive (MFTRss) and inductive (MFIND) matrix factorization models on Nvidia 2080ti GPUs with 12 GB GPU memory for all datasets with the exception that trained MFTRNS for Hotpot-QA on Nvidia A100 GPUs with 80 GB GPU memory. We use AdamW op- timizer (Loshchilov & Hutter, 2019) with learning rate and number of epochs as shown in Ta- 2 Training MFTANS on Hotpot-QA required 80 GB GPU memory as it involved training 768- dimensional embeddings for 5 million items which roughly translates to around 4 billion trainable parameters, and we used Adam W optimizer with stores additional memory for each trainable pa- rameter. For smaller datasets with the number of items of the order of 50K, smaller GPUs with 12 GB memory sufficed.
For inductive matrix factorization (MFIND), we train 2-layer MLP with connneconnt on top of query and item embeddings from DEsac. For given input embedding Fin E Rd, we compute the output embedding Tout Rdd as
2 = by + W (eelu(bb + WTT
Tout a (Wskpp) "our (1 a (Wxki)) )
http://wwggiinnaceccccmhaaaaaaaa crossenc msmarco miniLM
msmarco-disse
v2: hwwps//wwwwww..ooooooooooocceeee
16

---

Published as a conference paper at ICLR 2024
where W1 Rdx2d b1 R2dd, W2 R2dxd, by R Wakip E R are learnable parameters and (.) the sigmoid function. We initialize Wakip with -5 and use default PyTorch initialization for other parameters. We trained separate MLP models for queries and items. We would like highlight that a simple 2-layer MLP without the skip connection i.e. using oour as the final output embedding performed poorly in experiments and it did not generalize well to unseen queries and items.
Domain
MF Type
Learning Rate
Number Epochs
SciDocs
MFrass
0.005
if ((Qrain] ki) E {(1OK, IK), (50K, 1K) else
SciDocs
MFIND
0.005
( (Qriii)) ka) E {(10K, (I), (50K, IK) ) clse 20
Hotpot-QA
MFNN
0.001
if 1rain ka) E {(10K, IK), (50K, IK) else
Hotpot-QA
MFIND
0.001
10 if ( Qrain kd) E ((10K,IK), (50K. IK) clse 20
YuGiOh
TRNS
0.001
20
Star Trek MF
0.001
20
Table 2: Hyperparameters for transductive (MFrass) and inductive (MFInD) matrix factorization models for different number of training queries (1 ([Qirain)) 1) and number of items per train query (kia) in sparse matrix G.
A.3 TF-IDF
For BEIR datasets, we use BM25 with parameters as reported in Thakur et al. (2021b) and for ZESHEL, TF-IDF with default parameters from Scikit-learn (Pedregosa al. 2011), as reported in Yadav et al. 20022).
A.4 TEST- TIME INFERENCE WITH AXN, ADACUR AND RNR
For RNRx. we retrieve tco-scoring items using dot- fot-prrduct of query and item embeddings computed using baseline retrieval method X and re-rank the retrieved items using the cross-encoder model. For RN we use dense query embedding from base dual-encoder model DEsac for test- queries Ttest & Qwain along with item embeddings learnt using transductive matrix factorization to retrieve-and-reramm items for the given test query.
For both ADACUR and AxN, we use R = 10 for domains BEIR and = for domains in ZESHEL unless stated otherwise. For BEIR datasets, we tune AxN weight parameter À (in eq 7 on the dev set. We refer interested readers to (B.2 for the effect À on final performance. For ZESHEL, report results for À 0. For Hotpot-QA QA, we restrict our k-NN search with AxNx, and ADACURy to top-10K do not any such heuristic and search over all items.
10K items wrt method Y, Y E (DEsRc, TF-IDF). For other domains, we
Cross-Encodee Score Normalization for Axn Figure 4al shows query-item score distribution for the cross-encoder model and DEsRe on SciDocs datasets from BEIR benchmark. For cross-encoder models trained BEIR dataset, observe that the cross-encoder and DESRe model produce query- item scores in significantly different ranges. Since DEsRc is used to initialize the embedding space for matrix factorization approaches, this resulted in a mismatch in the range of the target score distribution from the cross-encoder in sparse matrix G and the initial predicted score distribution from DESRe. Consequently, using raw cross-encoder scores while training MF models and while computing test query embedding by solving the linear regression problem in Eq | approximation of the cross-encoder. To alleviate this issue, we normalize the cross-encoder scores to match the score distribution from DESEc model using two parameters a, 8 E IR.
leads to poor
Sinal (q. i) 3 siii (g, i) a))
where (g, i) and Stma initial and normalized cross-encone cross-encoder scores, and and 3 are esti- mated by ne-normalizing cross-encode distribution to match dual-encoder score distribution using 100 training queries. Note that such score normalization does affect the final ranking of items.
We do not perform any such normalization for ZESHEL datasets the cross-encoder and DEsRc model output scores in similar ranges shown in Figure
17

---

Published as a conference paper at ICLR 2024
0.20
BouseEnn Excoera
DeAs-Bossu Choes Roconen
0.15
Score Density
Score Density
0.15
0.10
0.10
0.05
0.00
2.00
50
Query-Item Score
Query-Item Score
(a) SciDocs
(b) YuGiOh
Figure 4: Score distribution for cross-encoder (CE) and dual-encoder (DE) models on SciDocs for BEIR and YuGiOh from ZESHEL. For each domain, we use cross-encoder and dual-encoder models trained on the corresponding task. See A for details on cross- cross-encoder training and {A.2.1 for dual-encoder training.
B
ADDITIONAL RESULTS AND ANALYSIS
B.1 OVERHEAD OF ADAPTIVE RETRIEVAL WITH AXN
Total
Cross Enc
Matrix Inverse
Manik Mahiply
Total
Cross Calls
Liner Regression
Muliplyy
Ca
Cala-110
CE Call--50c
CE Cals-110
CE Call-500
Inferrra Laterry X)
Infeerza Libnay (inx)
Iif
0.70
0.50
415
10
10
0.00
Number Rounds
Rounds
(a) ADACURDE
(b) A
Figure 5: Breakdown of inference latency for ADACUR DE and A AXNDE DEue under different
test-time CE call budgets for Ho See B.J for detailed discussion.
# Rounds
10
50
100
# Rounds
10
100
k=1
k=100
I==1
k=100
70
80
90
Top-é-Racall
Top Top-k-Res Recall
Top-k-Recall R-cacalll
.p-i--P Recall
73-
Top-k
70-
50
200
500
100
200
500
1000
100
200
500
100
200
500 1000
Inference Cost (Total Number of CE calls)
Inference Cost (Total Number of CE calls)
(a) SciDocs
(b) Hotpot-QA
Figure 6: Top-k-Recall versus number of rounds for AXN DEsse under different test-time cross- encoder call budgets for domains Hotpot-QA and SciDocs. Number of rounds (R) = corresponds to retrieve-and-rerant style inference with DESie i.e. RNR Top-k- generally improves with the number of rounds and saturates around 10 rounds.
Figures 5a and 5h show total inference latency for ADACUR and AxN for varying number of rounds (R) at different cross-encoder (CE) calls budgets. The secondary y-axis in 5 the breakdown of the inference latency into three main steps in Algorithm - (a) CE Calls: computing
CE scores for retrieved items (line 9 (b) solving linear regression problem to update test query embedding for AxN (line 10 (c) Matrix Multiply: updating approximate scores for all items (line
followed by retrieving items using approximate scores. In case of ADACUR computing query embedding in step (b) involves computing the pseudo-inverse matrix instead solving linear regression problem.
18

---

Published as a conference paper at ICLR 2024
As shown in Figure 5 the overhead of adaptive retrieval is negligible for R 5 to 10, and the overhead increases linearly with the number of rounds. AXNDEac for R = 1 corresponds to R retrieve-and-rerank style inference using DEsRe. We observe that AxN incurs less overhead than ADACUR under the same test-time CE call budget. Each CE call takes an amortized time of ~2 _ when computing CE scores with a batch-size of up 50 for domain=Hotpol-OA While the time complexity of updating the approximate scores is linear in the number of items, we observe that this step can be significantly sped up using GPUs/TPUs, and use of efficient vector- based k-NN search methods. In this work, to get an efficient implementation for large domains such as Hotpot-QA, we first shortlist 10K items for the test query using the baseline retrieval method (e.g. DEsRc). and only update the approximate scores for those 10K during inference using brute-force computation of scores for all 10K items. Further, note that the approximate scores are only used for retrieving items (line [ in Alg. D and this operation can also be implemented on CPUs using efficient sector-based k-NN search methods (Malkov Yashunin 2018; Guo et al. 2020) without the need for brute-force computation of approximate scores for all items.
B.2 COMPARING DIFFERENT QUERY EMBEDDING METHODS
DE
AxN
Ax
ToUR-CB
TToURMME
km1
X-100
70-
16.20
Top -Rocall
Top- Rocall
Downstream Task
16.05
Downstream Task
35
nDCG@10
50
118.00
Recal
15.70
50
100
200
500
100
200
500
1000
100
1000
50
100
200
1000
Cost (Total Number calls)
Inference
Inforence
SciDocs
Am1
10-00
65
Downstrraa Task
Downstress Task
k Rocal
Top-k Top-t-Past Recall
nDCGe11
601
65
Rezall
60-
50
500
500
300
Inference Cost (Total Number CE calls)
Inforence
Cost
Inference Cost
(b) Hotpot-QA
Figure 7: Top-ks-Recal versus inference cost for different test query embedding methods on domains SciDocs and Hotpot- QA. See BB. for detailed discussion.
Our proposed N-NN search method shares a similar motivation to pseudo-relevance feedback (PRF) methods that aim to improve the quality of retrieval by updating the initial query representation using heuristic or model-based feedback on retrieved items. We show results for ToUR (Sung et al. 2023), recent pRF-based method that, similar to our method, also optimizes the test query representations using retrieval results while utilizing the CE call budget Bee CE calls over R rounds. However, unlike AxN, ToUR uses single gradient-basse based update to query embedding to minimize KL-Divergence (TOUR-CH) or mean-squared error (TOUR-MSE) between approximate and exact scores for top-Bee/R items in each round. In contrast, Axn computes the analytical solution to the least-square problem in Eq. 4 in each round, and optionally computes a weighted sum with the test query embedding from a dense parametric model such dual-encoder using weight À E [0, 1] in Eq. 7 For TOUR-CE, we use learning rate =0.1 (chosen from {0.1, 0.5, 1.0)) and for ToUR-MSE MSE, we learning rate 1e-3 (chosen from { [1e-2, 1e-3, 1e-4)).
On Nvidia 2080ti GPU with 12 GB memory for 6-layer Mini-I. Wang 2020) based model.
19

---

Published as a conference paper at ICLR 2024
k= 100
Ax (76.2)
50-
Ax (77.1)
nz (77.6)
Top k ReRaall
Ax (79.1)
Top-k-Rech
60
- (79.1)
Ax (00:4)
75
30-
ox (01.0)
A (80.6)
as (81.0)
65-
-x (80.5)
50
100
200
500
100
200
500
1000
DE AxR (79.2)
Inference Cast (Total Number of CE calls)
Figure 8: Top-k-Recall for AXNDE for different values of parameter eq We use 200 queries from the validation set in Hotpot-QA -apoot-QAuuo and the value in parentheses in the legend denotes average Top-l-Recall, averaged over different test-time inference cost budgets. For k = 1, using A = 0.8 yields the best performance and for k 100, we use À 0 unless specified otherwise.
Figure 7 shows Top-k-Recall and downstream task metrics versus test-time inference CE cost bud- get (Bez) for AXNDE....Es.. under settings of the weight parameter,
and 0.8, and for DEsse and ToUR baselines. For both SciDocs and Hotpot-QA, AXNx=0.5 performs better than AxNx=o for k-NN search when & while A 0 works better for searching for k=100 near- est neighbors. ToUR and AXN achieve similar Top-1 -Recall at smaller inference costs with AxN performing marginally better than ToUR at larger cost budgets. However, for achieves significantly better recall than TOUR. We observe mixed trends for downstream task met- rics. For instance, AXNx=0.8 and ToUR baselines yield similar performance for nDCG@ 10 on both SciDocs and Hotpot-QA and for downstream task recall Hotpot-QA while AxNx=o performs better than baselines on downstream task recall for SciDocs.
100, AxNx=0
B.3 TRANSDUCTIVE VERSUS INDUCTIVE MATRIX FACTORIZATION
Ax DEge
ANN DEgc
MrN DEgar
Rs R DRave
RNRMP
RNR
10m=1000 100
1500m=500
h= 10m=100
1000m=500
Top- K- R
80+
Top- lo-k-Roo A--eccall@@n
87.5
80
70-
80.0
78
80.5
20
60+
80.0
76-
300
10P
100
102
Total Indexing Time (in hours)
Total Indexing Time (in hours]
(a) SciDocs
(b) Hotpot-QA
Figure 9: Topak-Recall versus indexing time for transductive (MFTRNs) and inductive (MF ma- trix factorization for SciDocs and Hotpot-QA QA. We report Reecll and Top-100-Re Rec-lR at fixed inference cost budget (m) of 100 and 500 CE calls respectively. See B.3 for detailed discussion.
Figure shows Top-k-Recal versus indexing time for DEsRe, and transductive (MFTRNS) and in- ductive (MFisn) matrix factorization in combination with two test-time inference methods: pro- posed inference method (AxN) and getrieve-and-rerant style (RNR) inference. We construct the sparse matrix G by selecting top-ka items for each train query using DESRc, and report results for [Qrainl E {1K, 10K, 50K} and ka E {100, 1000). We use DESRe to initialize the query and item embeddings for MF methods.
Recall that MFTRNS trains item embeddings as free- sice-parameter, and thus requires scoring an item against small number of train queries in order update the item embedding. For this reason, MF performs marginally better than or at par with MF on scall-scale data SciDocs with 25K items, as selecting for Qrrinl 1000, ka 100, results in each item being scored with
20

---

Published as a conference paper at ICLR 2024
four queries average. However, TFTSS performs poorly for large-scale data Hotpot-QA (with 5 million items) due to the increased sparsity of matrix G, providing marginal to no improvement over DES In contrast, IND provides consistent improvement over DESRc on Hotpot-QA.
B.4 EFFECT OF SPARSE MATRIX CONSTRUCTION STRATEGY
Holpol- QA
SciDocs
Sparse Matrix
Qiinn Kit
Time to compuile G
Train-Time
Time to compute
Train-Time
Construction Siralegy
MF
MFrrss
MF
MF
IK. 100
3 mins
5 mins (20)
10 mins
5 mins (10)
1.5 mins (10)
1000
(20)
1.6 has
(20)
(10)
10K, 100
30 mins
20 mins (20)
1.2 hrs (10)
1.6 hrs
20 mins (20)
7.5 mins (10)
ka items per query
10K, 1000
5.2 hrs
3 hrs (20)
3.2 has
16.7 hrs
3.2 hrs (20)
1.1 hrs 4)
S0K, 100
2.6 hrs
1.2 hrs (20)
4.1 hrs
8.3 hes
1.3 hrs (20)
0.6 hes (10)
50K, 1000
26.3 hrs
9 hrs (10)
16 hrs ( 4)
82 hrs
14 hrs (10)
3.7 hrs 4)
S0K,
5.8 hrs
3hrs (20)
7.5 hrs (10)
S mins
3 mins (20)
6.5 mins (20)
Ra queries per item
50K,
8hrs (20)
(20)
9 (20)
50K. 10
23 hrs
9hrs (10)
16 hrs
26 mins
mins (20)
10 mins (20)
Table 3: Breakdown of indexing latency for transductive MFTRNN and inductive MF matrix fac- torization methods on SciDocs and Hotpot-QA. For each setting, show the number of epochs for training the model in parentheses. Total indexing time also includes the time taken to compute initial query and item embeddings using DESRc- Computing item embeddings takes 90 seconds for SciDocs (with 25K items) and ~2 hours for Hotpot-QA (with million items) on an Nvidia 2080ti GPU with 12 GB GPU memory.
Figure 10 shows Top-k-Recall versus indexing time for and MF with two different strategies to construct sparse matrix G and Table the time taken to construct the sparse matrix G and the time taken to train the matrix factorization model. fixed number of ka items per query in Qinin and I * indicates that G' is constructed by selecting fixed number of ka queries per item in I. When selecting a fixed number of items per query, we experiment with Quain E {IK, 10K, 50K and ka {100, 1000]. When selecting fixed number of queries per item, we first create a pool of 50K queries and then select ka queries per item for ka {2, 5, 10).
* indicates that constructed by selecting
Transductive Matrix Factorization For MFTRNS. both Q Q-x and strategies yield similar Top- Recelll at given indexing cost SciDocs both strategies result in each item being scored with at least a few queries. However, on Hotpot-QA, selecting a fixed number of items per query may not result in each item being scored against some queries, and thus (if any) improvement over DESRC- I * variants perform better than DEsRe and corresponding Q variants as each item is scored against a fixed number of queries. Note that this performance improvement comes at the cost of an increase in time required to compute sparse matrix G, as shown in Table
variants yield marginal
Inductive Matrix Factorization For MFIND. we observe that Q variants consistently provide better recall-vs-ing -indelxinnn time trade-offs as compared to corresponding variants on both Sci- Docs and Hotpot-QA.
21

---

Published as a conference paper at ICLR 2024
Q AXN
I AXN AXN MF, DEoR
RxR RNR DEsnc
RNR MEF
I RxR MF
18m 100
1000m 500
1-10mmBi 100
1000m 500
80
Top-k: Rl-Rocalleem
Top-k- Rellleeclllmmm
67.8
65.0
70-
62.5
74
80.0
20F
Indesing hours)
Indexing hours)
(a-1) SciDocs
(a-2) Hotpot-QA
(a) Transductive Matrix Factorization (MFrass)
A= @my== 100
A= 1000m=500
1= 1m 100
I= 1000m=500
715
Top-I- J-Recalleem
Cop---Recallemm m
82
PPC
65+
80
78-
30
75+
70
Total Indexing Time hours)
Total Indexing Time (in hours)
(b-1) SciDocs
(b-2) Hotpot-QA
(b) Inductive Matrix Factorization (MF
Figure 10: Top-l-Recall and Top- at fixed inference cost budget (mn) of 100 and 500 cross- encoder calls respectively versus indexing time (in hours) for different strategies of constructing sparse matrix G. Q * indicates that G is constructed by selecting fixed number of items per query in Quain and
indicates that G is constructed by selecting fixed number of queries per item in I. For Q approaches, the text annotations indicate ( (iQuran), ka) pairs where @mmin is the number of anchor/train queries and kig the number of items per query the sparse matrix G. For
I approaches, the text annotations indicate the number of queries per item in the sparse matrix G. See [B.4 for detailed discussion.
22

---

Published as a conference paper at ICLR 2024
Baselines
RNR DEsnc
RNR DEasn
ADACUR DEsac
EXACT
Proposed
AxN DEsac DEsac
AxN DEpSrL. DEosm.
AXN MF, DESac
RNR MF
k= 10m=100
A: 1=100m==500
Downstream Task Accuracy
50.50
Top-k- Re-alllmmm
85
50.25
50.000
49.75
76-
49.50
19.25
10
10
10-1
10"
Total Indexing Time (in hours)
Total Indexing Time (in hours)
(a) Qmain
100, Queul
3274
k= 100
k= 100
80
Downstream Task Accuracy
50.50
90-
Top-k-Recall@nn
50.25
85-
50.00
80
49.75
75-
40
49.50
10
10a
10a
10
10"
10a
49.25
10a
10
Total Indexing Time (in hours)
Total Indexing Time (in hours)
(b) 1umin
500, 2
2874
1- 10m--00000 100
100@m:500
Downstream Task Accuracy
90
49.25
Top-k Top-k-RReclll Recall@m
90
80
49.00
18.75
85
48.50
50
48.25
10
10a
10
10
10P
10a
48.00
10-1
109
101
Total Indexing
Time (in hours)
Total Indexing Time (in hours)
(c) |Quial = 2000, Qual
1374
Figure 11: Top-k-Reeat Recall and downstream task accuracy versus indexing time for various approaches on domain=YuGioh. We report Top-1-Recal and Top- 10p-100-Recall at fixed inference cost budget (m) of 100 and 500 CE calls respectively, and downstream task accuracy for fixed inference cost 100 CE calls. Each subfigure shows results for different train/test splits.
23

---

Published as a conference paper at ICLR 2024
Baselines
RNR DEsnc
RNR DEasn.
ADACUR DEsac
EXACT
Proposed
AxN DEsce DEsac
AxN DEberL. DEosm.
AXN DEsac
RNR MF
10m=100
k=1000m=500 500
Downstream Task Accuracy
Top-k- Re-Recall@@m
63.4
50
63.2
90-
63.0
88
30
62.8
10-1
10P
10
10a
10
10"
Total Indexing Time (in hours)
Total Indexing Time (in hours)
(a) Qmain
100, Queul
4127
k= 100
100@m=500
Downstream Task Accuracy
94-
70-
63.0
Top-k- Remaleemllmmmmm
92-
62.5
50-
62.0
40-
61.5
86
10
10P
10¹
10
10P
10
Total Indexing Time (in hours)
Total Indexing Time (in hours)
(b) 1
500, 1
3727
1- 10mm-100
100
Task Accuracy
Top-k- Top-k-RRealliee Recall@m.
94-
80
63.5
70
63.0
92-
62.5
Downstream
50
62.0
88
40
10
10a
10A
10P
61.5
10"
16
Total Indexing Time (in hours)
Total Indexing Time (in hours)
(c) [Quiil 2000, Q
2227
Figure 12: Tep-k-Recall and downstream task accuracy versus indexing time for various approaches on domain=Star Trek. We report Top-1-Rechs and Top- 10p-100-RRecall at fixed inference cost budget (m) of 100 and 500 CE calls respectively, and downstream task accuracy for fixed inference cost of 100 CE calls. Each subfigure shows results for different train/test splits.
24

---

Published as a conference paper at ICLR 2024
Baselines
RSS
HNR pat
RNR
ADACU Fllaa:
ADACUR,
EXACT
Proposed
AxN DFsio. DEsae
AxN Deam.. DEpar
AxN MF, DEsac
RNR MF
AxN DEsac. TR-DF
AxN DESSLL TT-IPP
AxN MF, TF-IFF
k=10m=100
k = 150
80
Top- Lop-k-B k- Recall@n
90
70
80
60
70
100
102
100
102
Total Indexing Time (in hours)
Downstream Task nDCG@10
Downstream Task Recall
35
16.5
16.0
30
15.5
25
15.0
10
102
10
102
Total Indexing Time (in hours)
Total Indexing Time (in hours)
Figure 13: Top-k-Recall and downstream task performance metrics versus indexing time for var- ious approaches on domain=SciDocs. We report Top-I-Recall and Top-100-Recall at fixed ference cost budget (m) of 100 and 500 cross-encoder (CE) calls respectively, and downstream task metrics for fixed inference cost of 100 cross-encoder calls. We report results for transduc- tive matrix factorization (MFTass) in these plots. The base dual-encoder (DEsac) in these plots a 6-layer distilbert model finetuned on MS-MARCO dataset. The DESRc model is available at
25

---

Published as a conference paper at ICLR 2024
Baselines
INR P
RNR RNR pptmm.
RNR
ADACUT DFa
ADACUR
EXACT
Proposed
DE DEme
AXN DEaBT. DE
AXN DEaue
RNR MF
AxN DEmue 19-17
AXN DEamL.
AXNME TE-DD
k=10m=100
h 1000
50
-op-k-B k- mm
90
45
40
80
Top-
35
70
30
10
102
103
10a
102
10a
Total Indexing Time (in hours)
Downstream Task nDCG@10
Downstream Task Recall
70
80
65
60-
55
50
50
10
102
103
101
102
103
Total Indexing Time (in hours)
Total Indexing Time (in hours)
Figure 14: Top-k-Recall and downstream task performance metrics versus indexing time for var- ious approaches OA We report Top-I-Recall and 1op-l00-Recall at fixed in- ference cost budget (m) of 100 and 500 cross-encoder (CE) calls respectively, and downstream task metries for fixed inference cost of 100 cross-encoder calls. We report results for induc- tive matrix factorization (MFinn) in these plots. The base dual-encoder (DEssc) in these plots 6-layer distilbert model finetuned MS-MARCO dataset. The DEsRc model is available
26

---

Published as a conference paper at ICLR 2024
Baselines
RSS
RNR
ADACU Di
ADACUR,
EXACT
Proposed
AxN DESoe DEsac
DEsto.
AxN DEam.. DEpar
AxN MF. DEsac
RNR MF
AxN DEsac. TF-DF
AxN DESIL. TT-IPP
AxN MF. TF-IFF
== 100
k 1000m=500
85
Top- fop-k-Bn k- Ne-RRecalle Trcall@m
95
80
75
90
70
85
65
80
60
10-1
10
10'
10
100
10
Total Indexing Time (in hours)
Downstream Task nDCG@10
Downstream Task Recall
16.6
35
16.4
16.2
30
16.0
25
15.8
10
10"
10
10
100
10
Total Indexing Time (in hours)
Total Indexing Time (in hours)
Figure 15: Top-k-Recall and downstream task performance metrics versus indexing time for various report Top-l-Recall and Yop-100-Reecll fixed inference
approaches on domain=SciDocs. cost budget (m) of 100 and 500 cross-encoder (CE) calls respectively, and downstream task metrics for fixed inference cost 100 cross-encoder calls. We report results for transductive matrix factor- ization (MFTRss) in these plots. The base dual-encoder (DEgrc) in these plots is 1 12-layer bert-base model finetuned on MS-MARCO dataset. The model is available at attttss/huuggingfac.oo///// cot.s//ecccc///tencc.e..c. Shankommees/msmnarr---errrsassss
27

---

Published as a conference paper at ICLR 2024
Baselines
RNR RNR pptmm
RNR
ADACUT DFa
ADACUR
EXACT
Proposed
DEan.. DEme
AXN DEaBT. DEPSVL
AXN DEaue
RNR MF
AxN DEsne, 19-17
AXN DEamL.
AXN MF, TE-DD
k= 1==10m1100
k=1000m=500
55
95.0
Top-k- R-
92.5
50
90.0
45
87.5
40
85.0
35
10a
102
10a
10
102
103
Total Indexing Time (in hours)
Downstream Task nDCG@10
Downstream Task Recall
72
85
70
80
68
75
66
70
64
65
10a
102
103
10
102
103
Total Indexing Time (in hours)
Total Indexing Time (in hours)
Figure 16: Top-k-Recall and downstream task performance metrics versus indexing time for var- ious approaches OA We report Top-I-Recall and Top-100-Recall at fixed in- ference cost budget (m) of 100 and 500 cross-encoder (CE) calls respectively, and downstream task metrics for fixed inference cost of 100 cross-encoder calls. We report results for inductive matrix factorization (MFIND) in these plots. The base dual-encoder (DEssc) in these plots is 12-layer bert-base model finetuned on MS-MARCO dataset. This DEsge model is available
28


Reviews:
[{"review_id": "6NDRBrMXrt", "reviewer": "Reviewer_fa41", "summary": "This paper considers a new approach to retrieval and indexing that attempts to match the accuracy of cross encoders with lesser training time. Cross-encoders based retrieval allows for computing a relevance function over query and each point in the retrieval corpus and finding the point(s) most relevant. As this are expensive for inference, in practice, dual encoders with separate encoding stacks for query and corpus are used with k-NN used to quickly find the most relevant documents. A compromise on cross-encoder is a CUR decomposition of the relevance signal. This paper proposed a method (AXN) that improves upon recall of dual encoder methods and is much faster than CUR based approaches.\n\nAXN starts with a dual encoder (treated as black box) and iteratively mines for items near a query using the query's representation. Then it uses a cross encoder to score the limited set of items retrieved. It uses this to refine the query representation, search for another limited set of items and so on. The method limits the cross attention to far fewer items than the corpus size. Experiments show that AXN improves the recall of dual encoder and can match the recall of CUR methods.", "questions": "1. would a large dual encoder with same inference time as AXN match it's recall? Or would DE saturate well before AXN.\n2. What is the unit on x-axis in Figure 6?\n3. Could you talk about the scaling properties of your algorithm as the corpus grows larger? \n4. Why are not all methods not represented on each sub-figure in Figure 3?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. AXN yields better recall than dual encoders with faster training times compared to CUR methods\n2. They can build on any dual encoder methods (although experiments don't say if they improve on DE encoders)", "weaknesses": "1. The inference time and its comparison to simple DE+kNN approaches is not made clear. Would a large dual encoder with same inference time as AXN match its recall? Some of this is tucked away in the appendix in Fig 5 and 6 which seems to suggest the margins between DE and AXN are low normalized for inference cost.\n2. The choice of DE is not discussed. Is it completely irrelevant? Is it being compared to state-of-the-art encoders?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PZAGEhJkhX", "reviewer": "Reviewer_ja98", "summary": "The authors proposed a sparse-matrix factorization-based approach to improve the efficiency of fitting an embedding space to approximate the cross-encoder for k-NN search. Unlike DE-based and CUR-based methods, which lack good generalizations and computation efficiency, the new AXN method constructs a sparse matrix containing a cross-encoder score of training queries and all items.  The item embeddings are learned from matrix factorization. During test time, AXN alternates between updating the query embedding and retrieving more items for k-NN indexing.", "questions": "1. In the experiment section it was not clear how many rounds of updates are performed in all AXN experiments. \n2. Consider fixing max of CE calls B_{CE}, but varying the number of iterative search rounds and the number of items to retrieve in each round. Will it affect AXN's performance and total indexing time?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The authors proposed AXN, a novel cross-encoder-based k-NN search algorithm. By learning item embeddings from sparse matrix factorization and fixing them during query time, the algorithm is more computationally efficient than other methods.\n2. The authors explained their method very clearly in section 2.\n3. The extensive experiments and ablation studies supported their claims.", "weaknesses": "1. Figure 1's legends and corresponding subplots are hard to read. The subplots are too small, and hard to map points to the legends.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KXvVpCSOZj", "reviewer": "Reviewer_ujET", "summary": "Cross-encoder (CE) models outperform Dual-encoder (DE) models (especially at zero-shot problems) in the ranking task but are very expensive to use during inference. To alleviate this usually a retrieve then re-rank approach is used where a set of items are first retrieved using a DE model and then further ranked by CE. This paper proposes an alternate approach where the CE model is first distilled into a lightweight factorized model and at test time query representation is iteratively fine-tuned such that the dot product between test query embedding and indexed item embeddings gets closer and closer to the CE assigned relevance. This approach helps in reducing the CE calls required to accurately rank items for the test query.", "questions": "- It is a bit surprising that RnR DE models are performing worse than TF-IDF on Hotpot, is it because this CE model was trained on triplets mined using TF-IDF?\n- CE model is trained conditioned on some specific negativing mining distribution so maybe for RnR baselines we should also compare with a retrieval model which is the same as the retrieval model used for the negative mining so that the train and test-time behaviours are same\n- For a given budget $X$ of CE calls, how should one distribute $X$ calls in the number of rounds and $K$ CE calls inside each round in AXN inference", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The approach is simple to plug into existing retrieval and ranking frameworks\n- The paper is in general well-written and easy to follow\n- The proposed approach is compared against relevant baselines and the evaluation is thorough", "weaknesses": "- The proposed approach is evaluated only on zero-shot tasks, does this approach also benefits standard retrieval tasks\n- Gains are primarily under fixed index time scenario which is usually a one-time cost", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Xz27KPogcN", "reviewer": "Reviewer_hzee", "summary": "The paper proposes AXN, a test-time multi-run query embedding adaptation approach that leverages KNN search to approximate cross-encoder scores. This method successfully reduces the expensive computational costs associated with cross-encoder calculations, surpassing the performance of DE-based and CUR-based alternatives.", "questions": "1)\t“CUR” appears without any definition.\n2)\tWhat is the topk search method? Is it brute-force search?\n3)\tPlease address the above weaknesses.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper presents a novel adaptive retrieval technique that utilizes a limited number of cross-encoder (CE) calls to approximate the quality of cross-encoder results. This approach is scalable to handle a large volume of items.", "weaknesses": "1)\tThis paper uses K nearest neighbor search to iteratively update query embedding and approximate cross-encoder results. However, many references of nearest neighbor search are missing.\n2)\tAXN utilizes sparse matrix to reduce index costs. The paper lacks detailed analysis regarding this technique's impact on results concerning varying degrees of sparsity.\n3)\tBoth AXN and CUR-based methods need to compute low-dimensional embeddings for queries and items. AXN uses sparse matrix to reduce the cost. This can also be applied to CUR-based methods to reduce the index time. It is unclear if other techniques of AXN generate substantial improvements over CUR-based methods. It would be great if the authors can add more ablation study experiments.\n4)\tThe paper only covers the total index time as a benchmark, and future exploration could include query latency measurements since various steps are executed many times, including Solve-Linear-Regression and topk search.\n5)\tIt introduces lambda to ensemble the generated query embedding with a query embedding from DE or inductive matrix factorization. However, it fails to conduct an analysis of lambda impact on evaluation. It is the same for all experiments, or should be tuned in each experiment?\n6)\tIt runs R times Solve-Linear-Regression and topk search. How to choose R? It is fixed in all experiments or should be tuned in each experiment? Should it be large in large dataset?\n7)\tThe same problem for hyper-parameter Ks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)