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

Nishant Yadav, Nicholas Monath, Manzil Zaheer, Rob Fergus, Andrew McCallum

Abstract

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.

Introduction

In information retrieval, a fundamental tension exists between the high accuracy of Cross-Encoders (CE) and the computational efficiency of Dual-Encoders (DE). While CEs capture complex semantic interactions by processing query-item pairs jointly, their $O(N)$ inference cost per query makes them unsuitable for direct retrieval from large collections. Conversely, DEs allow for efficient $O(\log N)$ k-NN search via pre-computed embeddings but often fail to capture the nuanced relevance modeled by CEs.

Existing approximation methods like CUR matrix factorization attempt to map CEs into a vector space but require an impractical number of CE calls for indexing. This paper introduces a scalable alternative using sparse-matrix factorization and an iterative retrieval strategy called AXN (Adaptive Cross-Encoder Nearest Neighbor Search).

Methodology

The proposed framework addresses both the indexing and retrieval bottlenecks of CE-based search.

Scalable Indexing via Sparse-Matrix Factorization

Instead of the dense query-item scoring required by CUR, the authors propose factorizing a sparse matrix of CE scores. By scoring only a small fraction of items per training query, the method learns high-quality item embeddings that are aligned with the CE's logic. To further reduce costs, an inductive variant ($MF_{IND}$) utilizes a shallow MLP to project existing DE embeddings into the CE-aligned space, bypassing the need for expensive full-model distillation.

Figure 2: Breakdown of total indexing time for SciDocs and Hotpot-QA datasets, illustrating the efficiency of the sparse-matrix factorization approach.

Adaptive Retrieval (AXN)

At inference time, AXN treats the query embedding as a dynamic variable. Retrieval proceeds in rounds:

  1. Initial Retrieval: A candidate set is retrieved using a base method (e.g., BM25 or a base DE).
  2. CE Scoring: The "gold standard" CE scores the retrieved items.
  3. Query Refinement: The query embedding is updated by solving a linear regression problem to minimize the error in approximating the CE scores obtained so far.
  4. Iterative Search: The refined query embedding is used to retrieve a better set of candidates in the next round.

Experimental Results

The researchers evaluated AXN on benchmarks including ZESHEL (entity linking) and BEIR (document retrieval).

Performance Gains

AXN demonstrates substantial improvements in recall. On the YuGiOh domain of ZESHEL, it improved $k=100$ recall by 54% over standard retrieve-and-rerank baselines. These gains are consistent across different values of $k$ and $m$, showing that the adaptive refinement effectively "closes the loop" between retrieval and ranking.

Figure 3: Top-k Recall vs. Total Indexing Time. AXN (Proposed) consistently achieves higher recall at lower indexing costs compared to CUR and DE-distillation baselines.

Efficiency and Scalability

The sparse factorization approach provides a 100x speedup over CUR-based indexing and is 5x faster than traditional DE distillation. Notably, the method successfully indexed the 5-million-item Hotpot-QA dataset, a feat that would require over 5,000 GPU hours using previous state-of-the-art approximation techniques.

Conclusion

This work presents a practical path for deploying Cross-Encoders at scale. By leveraging sparsity in indexing and adaptivity in retrieval, the proposed method achieves state-of-the-art recall while maintaining the efficiency required for real-world production systems. Future work may explore automated normalization techniques to handle distributional shifts between CE and DE scores more robustly.

Summary updated

Abstract

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.
BibTeX
@inproceedings{yadav2024adaptive,
  author = {Nishant Yadav and Nicholas Monath and Manzil Zaheer and Rob Fergus and Andrew McCallum},
  title = {{Adaptive Retrieval and Scalable Indexing for k-NN Search with Cross-Encoders}},
  booktitle = {International Conference on Learning Representations},
  year = {2024},
  url = {https://openreview.net/forum?id=1CPta0bfN2},
}
Figure