Comparing Neighbors Together Makes it Easy: Jointly Comparing Multiple Candidates for Efficient and Effective Retrieval (2024)

Abstract: A common retrieve-and-rerank paradigm involves retrieving relevant candidates from a broad set using a fast bi-encoder (BE), followed by applying expensive but accurate cross-encoders (CE) to a limited candidate set. However, relying on this small subset is often susceptible to error propagation from the bi-encoders, which limits the overall performance. To address these issues, we propose the Comparing Multiple Candidates (CMC) framework. CMC compares a query and multiple embeddings of similar candidates (i.e., neighbors) through shallow self-attention layers, delivering rich representations contextualized to each other. Furthermore, CMC is scalable enough to handle multiple comparisons simultaneously. For example, comparing ~10K candidates with CMC takes a similar amount of time as comparing 16 candidates with CE. Experimental results on the ZeSHEL dataset demonstrate that CMC, when plugged in between bi-encoders and cross-encoders as a seamless intermediate reranker (BE-CMC-CE), can effectively improve recall@k (+6.7%-p, +3.5%-p for R@16, R@64) compared to using only bi-encoders (BE-CE), with negligible slowdown (<7%). Additionally, to verify CMC’s effectiveness as the final-stage reranker in improving top-1 accuracy, we conduct experiments on downstream tasks such as entity, passage, and dialogue ranking. The results indicate that CMC is not only faster (11x) but also often more effective than CE, with improved prediction accuracy in Wikipedia entity linking (+0.7%-p) and DSTC7 dialogue ranking (+3.3%-p).

## introduction the two-stage approach of retrieval and reranking has become a predominant method in tasks such as entity linking (el) @xcite @xcite , open-domain question answering (odqa) (nogueira and cho, * corresponding author 2019; @xcite @xcite , and dialogue systems @xcite . typically, bi-encoders (be) are used to efficiently retrieve relevant candidates from a large set of documents (e.g., knowledge base), and then cross-encoders (ce) effectively rerank only a limited subset of candidates already retrieved by be @xcite ; figure 1 .a-b). the current be-ce approach, although widely adopted, has an efficiency-effectiveness trade-off and is susceptible to error propagation. when less accurate be retrieves candidates, the whole framework risks the error propagation of missing the gold candidates due to inaccuracies from the retriever. simply increasing the number of candidates is not a viable solution considering the slow serving time of ce 12 . consequently, users are faced with the dilemma of deciding which is worse: error propagation from be versus the slow runtime of ce. to resolve this issue, various strategies have been proposed to find an optimal balance in the efficiency-effectiveness trade-off. prior works @xcite ; @xcite ; @xcite ; @xcite ) have enhanced bi-encoder architectures with a late interaction component. however, these models only focus on single query-candidate pair interaction. also, they sometimes require storing entire token embeddings per candidate sentence which results in tremendous memory use (figure 1 .c). our proposed comparing multiple candidates (cmc) makes reranking easy by comparing similar candidates (i.e., neighbors) together. by jointly contextualizing the single vector embeddings from each candidate through shallow bi-directional selfattention layers, cmc achieves high prediction accuracy and runtime efficiency that are comparable to, or better, than existing methods which require single or multiple vector embeddings. in other words, cmc only takes a single forward pass for input (query, candidate 1 , ..., candidate k ) with a pre-computed single vector embedding. in contrast, models such as ce and other late interaction models take k separate forward passes for input pairs (query, candidate 1 ), ..., (query, candidate k ), sometimes requiring multiple vector embeddings per each candidate. cmc maintains both the efficiency of be with pre-computed single-vector candidate embeddings, and the effectiveness of ce with interactions between query and multiple candidates (figure @xcite . practitioners can plug in cmc as the seamless intermediate reranker (be-cmc-ce) which can enhance retrieval performance with negligible extra latency. this improvement is crucial for preventing error propagation from the retrieval process, resulting in more reliable candidates for the final stage (figure 2 3 ). on the other hand, cmc also can serve as a fast and effective final-stage reranker improving top-1 accuracy (be-cmc). if there's a time constraint, using cmc as the final reranker can be a good option, as running a cross-encoder requires significantly more time ( in experiments, we evaluate cmc on zero-shot entity-linking dataset (zeshel; @xcite ) to investigate how much cmc seamlessly enhances a retriever's performance when plugged in to be (be-cmc). the results show cmc provides higher recall than baseline retrievers at a marginal increase in latency (+0.07x; the main contributions of the paper are as follows: ## conclusion in this paper, we present a novel and intuitive retrieval and reranking framework, comparing multiple candidates (cmc). by contextualizing the representations of candidates through the selfattention layer, cmc achieves improvements in prediction performance with a marginal increase in speed and memory efficiency. experimental results show that cmc acts as a seamless intermediate reranker between bi-encoders and cross-encoders. the retrieval pipeline of be-cmc-ce is not only