# Lexically-Accelerated Dense Retrieval

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 56 references that are in the map.
- First posted on arXiv 31 Jul 2023.

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

- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models](https://mlsanity.com/paper/2104.08663/) (2021)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Approximate Nearest Neighbor Negative Contrastive Learning for Dense Text Retrieval](https://mlsanity.com/paper/2007.00808/) (2020)
- [Overview of the TREC 2019 deep learning track](https://mlsanity.com/paper/2003.07820/) (2020)
- [SPLADE: Sparse Lexical and Expansion Model for First Stage Ranking](https://mlsanity.com/paper/2107.05720/) (2021)
- [Pretrained Transformers for Text Ranking: BERT and Beyond](https://mlsanity.com/paper/2010.06467/) (2020)
- [Efficiently Teaching an Effective Dense Retriever with Balanced Topic Aware Sampling](https://mlsanity.com/paper/2104.06967/) (2021)
- [Overview of the TREC 2020 deep learning track](https://mlsanity.com/paper/2102.07662/) (2021)
- [A Deep Relevance Matching Model for Ad-hoc Retrieval](https://mlsanity.com/paper/1711.08611/) (2017)
- [RetroMAE: Pre-Training Retrieval-oriented Language Models Via Masked Auto-Encoder](https://mlsanity.com/paper/2205.12035/) (2022)
- [Leveraging Semantic and Lexical Matching to Improve the Recall of Document Retrieval Systems: A Hybrid Approach](https://mlsanity.com/paper/2010.01195/) (2020)
- [Expansion via Prediction of Importance with Contextualization](https://mlsanity.com/paper/2004.14245/) (2020)
- [Learning Optimal Tree Models Under Beam Search](https://mlsanity.com/paper/2006.15408/) (2020)
- [Adaptive Re-Ranking with a Corpus Graph](https://mlsanity.com/paper/2208.08942/) (2022)
- [Predicting Efficiency/Effectiveness Trade-offs for Dense vs. Sparse Retrieval Strategy Selection](https://mlsanity.com/paper/2109.10739/) (2021)
- [Joint Learning of Deep Retrieval Model and Product Quantization based Embedding Index](https://mlsanity.com/paper/2105.03933/) (2021)
- [A Study of MatchPyramid Models on Ad-hoc Retrieval](https://mlsanity.com/paper/1606.04648/) (2016)
- [Faster Learned Sparse Retrieval with Guided Traversal](https://mlsanity.com/paper/2204.11314/) (2022)
- [Composite Code Sparse Autoencoders for first stage retrieval](https://mlsanity.com/paper/2204.07023/) (2022)
- [Efficient Neural Ranking using Forward Indexes](https://mlsanity.com/paper/2110.06051/) (2021)
- [Multi-Perspective Semantic Information Retrieval](https://mlsanity.com/paper/2009.01938/) (2020)

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

- [Guiding Retrieval using LLM-based Listwise Rankers](https://mlsanity.com/paper/2501.09186/) (2025)
- [Improving Retrieval in Theme-specific Applications using a Corpus Topical Taxonomy](https://mlsanity.com/paper/2403.04160/) (2024)
- [A Reproducibility Study of PLAID](https://mlsanity.com/paper/2404.14989/) (2024)
- [Shallow Cross-Encoders for Low-Latency Retrieval](https://mlsanity.com/paper/2403.20222/) (2024)
- [QDER: Query-Specific Document and Entity Representations for Multi-Vector Document Re-Ranking](https://mlsanity.com/paper/2510.11589/) (2025)
- [Democratizing GraphRAG: Linear, CPU-Only Graph Retrieval for Multi-Hop QA](https://mlsanity.com/paper/2602.23372/) (2025)
- [PLAID-PRF: Pseudo-Relevance Feedback with Centroid-like Tokens in PLAID](https://mlsanity.com/paper/2607.18626/) (2026)

## Abstract (arXiv)

Retrieval approaches that score documents based on learned dense vectors (i.e., dense retrieval) rather than lexical signals (i.e., conventional retrieval) are increasingly popular. Their ability to identify related documents that do not necessarily contain the same terms as those appearing in the user's query (thereby improving recall) is one of their key advantages. However, to actually achieve these gains, dense retrieval approaches typically require an exhaustive search over the document collection, making them considerably more expensive at query-time than conventional lexical approaches. Several techniques aim to reduce this computational overhead by approximating the results of a full dense retriever. Although these approaches reasonably approximate the top results, they suffer in terms of recall -- one of the key advantages of dense retrieval. We introduce 'LADR' (Lexically-Accelerated Dense Retrieval), a simple-yet-effective approach that improves the efficiency of existing dense retrieval models without compromising on retrieval effectiveness. LADR uses lexical retrieval techniques to seed a dense retrieval exploration that uses a document proximity graph. We explore two variants of LADR: a proactive approach that expands the search space to the neighbors of all seed documents, and an adaptive approach that selectively searches the documents with the highest estimated relevance in an iterative fashion. Through extensive experiments across a variety of dense retrieval models, we find that LADR establishes a new dense retrieval effectiveness-efficiency Pareto frontier among approximate k nearest neighbor techniques. Further, we find that when tuned to take around 8ms per query in retrieval latency on our hardware, LADR consistently achieves both precision and recall that are on par with an exhaustive search on standard benchmarks.