Efficient K-nn Search With Cross-encoders Using Adaptive Multi-round CUR Decomposition

Abstract

Cross-encoder models, which jointly encode and score a query-item pair, are prohibitively expensive for direct k-nearest neighbor (k-NN) search. Consequently, k-NN search typically employs a fast approximate retrieval (e.g. using BM25 or dual-encoder vectors), followed by reranking with a cross-encoder; however, the retrieval approximation often has detrimental recall regret. This problem is tackled by ANNCUR (Yadav et al., 2022), a recent work that employs a cross-encoder only, making search efficient using a relatively small number of anchor items, and a CUR matrix factorization. While ANNCUR's one-time selection of anchors tends to approximate the cross-encoder distances on average, doing so forfeits the capacity to accurately estimate distances to items near the query, leading to regret in the crucial end-task: recall of top-k items. In this paper, we propose ADACUR, a method that adaptively, iteratively, and efficiently minimizes the approximation error for the practically importa

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyyadav2023efficient

Related papers

• Adaptive Retrieval And Scalable Indexing For K-nn Search With Cross-encoders (2024)0.00
• Efficient Nearest Neighbor Search For Cross-encoder Models Using Matrix Factorization (2022)4.52
• Knn-embed: Locally Smoothed Embedding Mixtures For Multi-interest Candidate Retrieval (2022)3.58
• NUDGE: Lightweight Non-parametric Fine-tuning Of Embeddings For Retrieval (2024)0.00
• Comparing Neighbors Together Makes It Easy: Jointly Comparing Multiple Candidates For Efficient And Effective Retrieval (2024)4.52
• Efficient Data-aware Distance Comparison Operations For High-dimensional Approximate Nearest Neighbor Search (2024)5.24
• MICE: Minimal Interaction Cross-encoders For Efficient Re-ranking (2026)0.00
• Roargraph: A Projected Bipartite Graph For Efficient Cross-modal Approximate Nearest Neighbor Search (2024)8.09