# Efficient Nearest Neighbor Search for Cross-Encoder Models using Matrix Factorization

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 52 references that are in the map.
- First posted on arXiv 23 Oct 2022.

## Builds on (most cited first, 28 of 28)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation](https://mlsanity.com/paper/1609.08144/) (2016)
- [ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT](https://mlsanity.com/paper/2004.12832/) (2020)
- [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)
- [Sparse, Dense, and Attentional Representations for Text Retrieval](https://mlsanity.com/paper/2005.00181/) (2020)
- [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)
- [Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares](https://mlsanity.com/paper/1410.2596/) (2014)
- [ReFinED: An Efficient Zero-shot-capable Approach to End-to-End Entity Linking](https://mlsanity.com/paper/2207.04108/) (2022)
- [Energy-Based Reranking: Improving Neural Machine Translation Using Energy-Based Models](https://mlsanity.com/paper/2009.13267/) (2020)
- [Cross-Architecture Knowledge Distillation](https://mlsanity.com/paper/2207.05273/) (2022)
- [Understanding Hard Negatives in Noise Contrastive Estimation](https://mlsanity.com/paper/2104.06245/) (2021)
- [Improving CUR Matrix Decomposition and the Nystr"om Approximation via Adaptive Sampling](https://mlsanity.com/paper/1303.4207/) (2013)
- [Trans-Encoder: Unsupervised sentence-pair modelling through self- and mutual-distillations](https://mlsanity.com/paper/2109.13059/) (2021)
- [Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices](https://mlsanity.com/paper/1704.03371/) (2017)
- [Sample-Optimal Low-Rank Approximation of Distance Matrices](https://mlsanity.com/paper/1906.00339/) (2019)
- [DiPair: Fast and Accurate Distillation for Trillion-Scale Text Matching and Pair Modeling](https://mlsanity.com/paper/2010.03099/) (2020)
- [Sublinear Time Low-Rank Approximation of Distance Matrices](https://mlsanity.com/paper/1809.06986/) (2018)
- [On the Effect of Low-Frequency Terms on Neural-IR Models](https://mlsanity.com/paper/1904.12683/) (2019)
- [Sublinear Time Approximation of Text Similarity Matrices](https://mlsanity.com/paper/2112.09631/) (2021)
- [Accurate and Fast Retrieval for Complex Non-metric Data via Neighborhood Graphs](https://mlsanity.com/paper/1910.03534/) (2019)
- [Pruning Algorithms for Low-Dimensional Non-metric k-NN Search: A Case Study](https://mlsanity.com/paper/1910.03539/) (2019)

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

- [Pearl: Personalizing Large Language Model Writing Assistants with Generation-Calibrated Retrievers](https://mlsanity.com/paper/2311.09180/) (2023)
- [Automated Evaluation of Retrieval-Augmented Language Models with Task-Specific Exam Generation](https://mlsanity.com/paper/2405.13622/) (2024)
- [EmbedDistill: A Geometric Knowledge Distillation for Information Retrieval](https://mlsanity.com/paper/2301.12005/) (2023)
- [Efficient k-NN Search with Cross-Encoders using Adaptive Multi-Round CUR Decomposition](https://mlsanity.com/paper/2305.02996/) (2023)
- [Comparing Neighbors Together Makes it Easy: Jointly Comparing Multiple Candidates for Efficient and Effective Retrieval](https://mlsanity.com/paper/2405.12801/) (2024)
- [Can Cross Encoders Produce Useful Sentence Embeddings?](https://mlsanity.com/paper/2502.03552/) (2025)
- [Adaptive Retrieval and Scalable Indexing for k-NN Search with Cross-Encoders](https://mlsanity.com/paper/2405.03651/) (2024)
- [Interactive Topic Models with Optimal Transport](https://mlsanity.com/paper/2406.19928/) (2024)
- [Bridging Personalization and Control in Scientific Personalized Search](https://mlsanity.com/paper/2411.02790/) (2024)
- [Relevance-Based Embeddings: Lightweight Candidate Retrieval via Heavy-Ranker Calls](https://mlsanity.com/paper/2607.03515/) (2026)

## Abstract (arXiv)

Efficient k-nearest neighbor search is a fundamental task, foundational for many problems in NLP. When the similarity is measured by dot-product between dual-encoder vectors or ℓ2-distance, there already exist many scalable and efficient search methods. But not so when similarity is measured by more accurate and expensive black-box neural similarity models, such as cross-encoders, which jointly encode the query and candidate neighbor. The cross-encoders' high computational cost typically limits their use to reranking candidates retrieved by a cheaper model, such as dual encoder or TF-IDF. However, the accuracy of such a two-stage approach is upper-bounded by the recall of the initial candidate set, and potentially requires additional training to align the auxiliary retrieval model with the cross-encoder model. In this paper, we present an approach that avoids the use of a dual-encoder for retrieval, relying solely on the cross-encoder. Retrieval is made efficient with CUR decomposition, a matrix decomposition approach that approximates all pairwise cross-encoder distances from a small subset of rows and columns of the distance matrix. Indexing items using our approach is computationally cheaper than training an auxiliary dual-encoder model through distillation. Empirically, for k > 10, our approach provides test-time recall-vs-computational cost trade-offs superior to the current widely-used methods that re-rank items retrieved using a dual-encoder or TF-IDF.