# Adaptive Retrieval and Scalable Indexing for k-NN Search with Cross-Encoders

arXiv: https://arxiv.org/abs/2405.03651 · HTML: https://mlsanity.com/paper/2405.03651/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 46 of its 78 references that are in the map.
- First posted on arXiv 6 May 2024.

## Builds on (most cited first, 30 of 46)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter](https://mlsanity.com/paper/1910.01108/) (2019)
- [Parameter-Efficient Transfer Learning for NLP](https://mlsanity.com/paper/1902.00751/) (2019)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [MiniLM: Deep Self-Attention Distillation for Task-Agnostic Compression of Pre-Trained Transformers](https://mlsanity.com/paper/2002.10957/) (2020)
- [BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models](https://mlsanity.com/paper/2104.08663/) (2021)
- [Atlas: Few-shot Learning with Retrieval Augmented Language Models](https://mlsanity.com/paper/2208.03299/) (2022)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [RocketQA: An Optimized Training Approach to Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2010.08191/) (2020)
- [DeeBERT: Dynamic Early Exiting for Accelerating BERT Inference](https://mlsanity.com/paper/2004.12993/) (2020)
- [AdapterDrop: On the Efficiency of Adapters in Transformers](https://mlsanity.com/paper/2010.11918/) (2020)
- [Generation-Augmented Retrieval for Open-domain Question Answering](https://mlsanity.com/paper/2009.08553/) (2020)
- [RocketQAv2: A Joint Training Method for Dense Passage Retrieval and Passage Re-ranking](https://mlsanity.com/paper/2110.07367/) (2021)
- [Improving Efficient Neural Ranking Models with Cross-Architecture Knowledge Distillation](https://mlsanity.com/paper/2010.02666/) (2020)
- [Augmented SBERT: Data Augmentation Method for Improving Bi-Encoders for Pairwise Sentence Scoring Tasks](https://mlsanity.com/paper/2010.08240/) (2020)
- [Zero-Shot Entity Linking by Reading Entity Descriptions](https://mlsanity.com/paper/1906.07348/) (2019)
- [A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2101.12631/) (2021)
- [ReFinED: An Efficient Zero-shot-capable Approach to End-to-End Entity Linking](https://mlsanity.com/paper/2207.04108/) (2022)
- [Training Data is More Valuable than You Think: A Simple and Effective Method by Retrieving from Training Data](https://mlsanity.com/paper/2203.08773/) (2022)
- [Deep k-NN for Noisy Labels](https://mlsanity.com/paper/2004.12289/) (2020)
- [Retrieval-Augmented Reinforcement Learning](https://mlsanity.com/paper/2202.08417/) (2022)
- [Improving Query Representations for Dense Retrieval with Pseudo Relevance Feedback](https://mlsanity.com/paper/2108.13454/) (2021)
- [Approximate Nearest Neighbor Search on High Dimensional Data --- Experiments, Analyses, and Improvement (v1.0)](https://mlsanity.com/paper/1610.02455/) (2016)
- [Low-Rank Matrix Completion: A Contemporary Survey](https://mlsanity.com/paper/1907.11705/) (2019)
- [Curriculum Learning for Dense Retrieval Distillation](https://mlsanity.com/paper/2204.13679/) (2022)
- [Provable Inductive Matrix Completion](https://mlsanity.com/paper/1306.0626/) (2013)
- [Pseudo-Relevance Feedback for Multiple Representation Dense Retrieval](https://mlsanity.com/paper/2106.11251/) (2021)
- [Knowledge Base Question Answering by Case-based Reasoning over Subgraphs](https://mlsanity.com/paper/2202.10610/) (2022)
- [Adaptive Re-Ranking with a Corpus Graph](https://mlsanity.com/paper/2208.08942/) (2022)
- [In Defense of Cross-Encoders for Zero-Shot Retrieval](https://mlsanity.com/paper/2212.06121/) (2022)

## Built on by (most cited first, 1 of 1)

- [Relevance-Based Embeddings: Lightweight Candidate Retrieval via Heavy-Ranker Calls](https://mlsanity.com/paper/2607.03515/) (2026)

## Abstract (arXiv)

Cross-encoder (CE) models which compute similarity by jointly encoding a query-item pair perform better than embedding-based models (dual-encoders) at estimating query-item relevance. Existing approaches perform k-NN search with CE 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 on new domains and the retrieval with DE is decoupled from the CE. While CUR-based approaches can be more accurate than the DE-based approach, they 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 embeddings to approximate CE scores and performs k-NN search with the approximate CE similarity. We compute item embeddings offline 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 calls as compared to CUR-based methods, and allows for leveraging DE to initialize the embedding space while avoiding compute- and resource-intensive finetuning of DE via distillation. At test time, the item embeddings remain fixed and retrieval occurs over 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. Our k-NN search method improves recall by up to 5% (k=1) and 54% (k=100) over DE-based approaches. Additionally, our indexing approach achieves a speedup of up to 100x over CUR-based and 5x over DE distillation methods, while matching or improving k-NN search recall over baselines.