Research map / Label-efficient and robust learning / Recognition and long-tail
Adaptive Retrieval and Scalable Indexing for k-NN Search with Cross-Encoders
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes adaptive cross-encoder k-NN search that factorizes a sparse matrix of cross-encoder scores to build item embeddings offline and refines test query embeddings over rounds via linear regression on CE scores, reducing indexing cost versus CUR and distillation baselines.
Problem
Efficient and accurate k-NN search with expensive cross-encoder similarity over large item sets, where dual-encoder retrieve-and-rerank has poor recall and CUR-based methods need prohibitively many CE calls for indexing.
Approach
Index items by factorizing a sparse matrix of CE scores between train queries and a subset of items (initialized from a dual-encoder, optionally with a shallow MLP), and at test time keep item embeddings fixed while iteratively solving a least-squares problem for the query embedding from CE scores of previously retrieved items, retrieving new items each round.
Key results
- Proposed inference with DE gives up to 5.2% Top-1 and 54% Top-100 recall gains over retrieve-and-rerank with the same DE on YuGiOh.
- On HotpotQA (5M items), MF-Ind with 10K queries and 100 items per query indexes in under three hours and achieves Top-1-Recall@100 of 80.5, versus 75.9 for AdaCUR-DE which needs 1000+ GPU hours.
- Matrix factorization indexing is up to 100x faster than AdaCUR and up to 5x faster than DE distillation while matching or improving recall.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use adaptive retrieval instead of retrieve-and-rerank with the base dual-encoder | Base dual-encoder retrieval · YuGiOh | Top-1-Recall: +5.2% | Helped |
| Use adaptive retrieval instead of retrieve-and-rerank with the base dual-encoder | Base dual-encoder retrieval · YuGiOh | Top-100-Recall: 54% | Helped |
| Use inductive matrix factorization with adaptive retrieval instead of AdaCUR | Hotpot-QA · Hotpot-QA | Top-1-Recall@100: 75.9 -> 80.5 | Helped |
| Use inductive matrix factorization with adaptive retrieval instead of AdaCUR | Hotpot-QA · Hotpot-QA | Top-100-Recall@500: 44.8 -> 42.6 | Hurt |
| Use TF-IDF rather than the base dual-encoder to select first-round items | Adaptive retrieval · Hotpot-QA | Top-k-Recall | Helped |
| Use exact cross-encoder search rather than retrieve-and-rerank | YuGiOh entity linking · YuGiOh | entity linking accuracy: 50.6 -> 49.8 | Hurt |
| Remove the skip connection from the 2-layer MLP (ablation) | Inductive matrix factorization · Unseen queries and items | generalization | Hurt |
| Increase the number of adaptive retrieval rounds (ablation) | Adaptive retrieval with the base dual-encoder · Hotpot-QA and SciDocs | Top-k-Recall | Helped |
| Set the query-embedding interpolation weight to 0.8 rather than 0 (ablation) | Adaptive retrieval · SciDocs and Hotpot-QA, k=1 | Top-1-Recall | Helped |
| Set the query-embedding interpolation weight to 0 rather than 0.8 (ablation) | Adaptive retrieval · SciDocs and Hotpot-QA, k=100 | Top-100-Recall | Helped |
| Use inductive rather than transductive matrix factorization (ablation) | Matrix factorization · Hotpot-QA | Top-k-Recall | Helped |
| Use transductive rather than inductive matrix factorization (ablation) | Matrix factorization · SciDocs | Top-k-Recall | Mixed |
Surprising findings
- Exact CE search underperforms retrieve-and-rerank with the DE on downstream entity linking (49.8 vs 50.6 on YuGiOh), suggesting the CE's k-NN quality does not always translate to downstream accuracy.
- A plain 2-layer MLP without a skip connection generalized poorly for inductive matrix factorization.
Limitations
- Matrix factorization with transductive parameters scales poorly to millions of items due to sparsity and parameter count, so inductive variant is needed for large domains.
- Score normalization needed for BeIR where CE and DE score ranges differ; Hotpot-QA search restricted to top-10K items shortlisted by DE/TF-IDF.
Experimental setup
Datasets: ZeShEL BEIR SciDocs BEIR HotpotQA
Benchmarks: ZeShEL (YuGiOh, Star Trek) BEIR SciDocs BEIR HotpotQA
Metrics: Top-k-Recall@m entity linking accuracy nDCG@10 downstream recall indexing wall-clock time
Baselines: retrieve-and-rerank with dual-encoder AdaCUR distilled dual-encoder TF-IDF / BM25 retrieve-and-rerank TouR
Builds on: AdaCUR dual-encoder distillation inductive matrix completion TouR
Closest papers by meaning
- Hierarchical Retrieval: The Geometry and a Pretrain-Finetune Recipe (NeurIPS 2025 · similarity 0.87)
- NUDGE: Lightweight Non-Parametric Fine-Tuning of Embeddings for Retrieval (ICLR 2025 · similarity 0.86)
- Semi-Parametric Retrieval via Binary Bag-of-Tokens Index (ICLR 2025 · similarity 0.86)
- USTAD: Unified Single-model Training Achieving Diverse Scores for Information Retrieval (ICML 2024 · similarity 0.85)
- MUVERA: Multi-Vector Retrieval via Fixed Dimensional Encoding (NeurIPS 2024 · similarity 0.85)
- How to Make Cross Encoder a Good Teacher for Efficient Image-Text Retrieval? (CVPR 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.