# Hybrid Inverted Index Is a Robust Accelerator for Dense Retrieval

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

## Key facts

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

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

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Neural Discrete Representation Learning](https://mlsanity.com/paper/1711.00937/) (2017)
- [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)
- [MS MARCO: A Human Generated MAchine Reading COmprehension Dataset](https://mlsanity.com/paper/1611.09268/) (2016)
- [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)
- [RocketQA: An Optimized Training Approach to Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2010.08191/) (2020)
- [Unsupervised Corpus Aware Language Model Pre-training for Dense Passage Retrieval](https://mlsanity.com/paper/2108.05540/) (2021)
- [Optimizing Dense Retrieval Model Training with Hard Negatives](https://mlsanity.com/paper/2104.08051/) (2021)
- [SPLADE v2: Sparse Lexical and Expansion Model for Information Retrieval](https://mlsanity.com/paper/2109.10086/) (2021)
- [A Survey on Learning to Hash](https://mlsanity.com/paper/1606.00185/) (2016)
- [RetroMAE: Pre-Training Retrieval-oriented Language Models Via Masked Auto-Encoder](https://mlsanity.com/paper/2205.12035/) (2022)
- [SimLM: Pre-training with Representation Bottleneck for Dense Passage Retrieval](https://mlsanity.com/paper/2207.02578/) (2022)
- [Adversarial Retriever-Ranker for dense text retrieval](https://mlsanity.com/paper/2110.03611/) (2021)
- [A Few Brief Notes on DeepImpact, COIL, and a Conceptual Framework for Information Retrieval Techniques](https://mlsanity.com/paper/2106.14807/) (2021)
- [Context-Aware Sentence/Passage Term Importance Estimation For First Stage Retrieval](https://mlsanity.com/paper/1910.10687/) (2019)
- [ERNIE-Search: Bridging Cross-Encoder with Dual-Encoder via Self On-the-fly Distillation for Dense Passage Retrieval](https://mlsanity.com/paper/2205.09153/) (2022)
- [Revisiting the Inverted Indices for Billion-Scale Approximate Nearest Neighbors](https://mlsanity.com/paper/1802.02422/) (2018)
- [A Replication Study of Dense Passage Retriever](https://mlsanity.com/paper/2104.05740/) (2021)
- [Jointly Optimizing Query Encoder and Product Quantization to Improve Retrieval Performance](https://mlsanity.com/paper/2108.00644/) (2021)
- [SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2111.08566/) (2021)
- [Pre-trained Language Model based Ranking in Baidu Search](https://mlsanity.com/paper/2105.11108/) (2021)
- [Leveraging Semantic and Lexical Matching to Improve the Recall of Document Retrieval Systems: A Hybrid Approach](https://mlsanity.com/paper/2010.01195/) (2020)
- [Complementing Lexical Retrieval with Semantic Residual Embedding](https://mlsanity.com/paper/2004.13969/) (2020)
- [UnifieR: A Unified Retriever for Large-Scale Retrieval](https://mlsanity.com/paper/2205.11194/) (2022)
- [Distill-VQ: Learning Retrieval Oriented Vector Quantization By Distilling Knowledge from Dense Embeddings](https://mlsanity.com/paper/2204.00185/) (2022)
- [LED: Lexicon-Enlightened Dense Retriever for Large-Scale Retrieval](https://mlsanity.com/paper/2208.13661/) (2022)
- [Matching-oriented Product Quantization For Ad-hoc Retrieval](https://mlsanity.com/paper/2104.07858/) (2021)
- [Faster Learned Sparse Retrieval with Guided Traversal](https://mlsanity.com/paper/2204.11314/) (2022)

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

- [Taxonomy-guided Semantic Indexing for Academic Paper Search](https://mlsanity.com/paper/2410.19218/) (2024)
- [Billion-scale Similarity Search Using a Hybrid Indexing Approach with Advanced Filtering](https://mlsanity.com/paper/2501.13442/) (2025)

## Abstract (arXiv)

Inverted file structure is a common technique for accelerating dense retrieval. It clusters documents based on their embeddings; during searching, it probes nearby clusters w.r.t. an input query and only evaluates documents within them by subsequent codecs, thus avoiding the expensive cost of exhaustive traversal. However, the clustering is always lossy, which results in the miss of relevant documents in the probed clusters and hence degrades retrieval quality. In contrast, lexical matching, such as overlaps of salient terms, tends to be strong feature for identifying relevant documents. In this work, we present the Hybrid Inverted Index (HI2), where the embedding clusters and salient terms work collaboratively to accelerate dense retrieval. To make best of both effectiveness and efficiency, we devise a cluster selector and a term selector, to construct compact inverted lists and efficiently searching through them. Moreover, we leverage simple unsupervised algorithms as well as end-to-end knowledge distillation to learn these two modules, with the latter further boosting the effectiveness. Based on comprehensive experiments on popular retrieval benchmarks, we verify that clusters and terms indeed complement each other, enabling HI2 to achieve lossless retrieval quality with competitive efficiency across various index settings. Our code and checkpoint are publicly available at https://github.com/namespace-Pt/Adon/tree/HI2.