# Constructing Tree-based Index for Efficient and Effective Dense Retrieval

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 43 references that are in the map.
- First posted on arXiv 24 Apr 2023.

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

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [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)
- [Decoupled Weight Decay Regularization](https://mlsanity.com/paper/1711.05101/) (2017)
- [MS MARCO: A Human Generated MAchine Reading COmprehension Dataset](https://mlsanity.com/paper/1611.09268/) (2016)
- [ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT](https://mlsanity.com/paper/2004.12832/) (2020)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [RocketQA: An Optimized Training Approach to Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2010.08191/) (2020)
- [Overview of the TREC 2019 deep learning track](https://mlsanity.com/paper/2003.07820/) (2020)
- [Transformer Memory as a Differentiable Search Index](https://mlsanity.com/paper/2202.06991/) (2022)
- [Overview of the TREC 2020 deep learning track](https://mlsanity.com/paper/2102.07662/) (2021)
- [Optimizing Dense Retrieval Model Training with Hard Negatives](https://mlsanity.com/paper/2104.08051/) (2021)
- [A Neural Corpus Indexer for Document Retrieval](https://mlsanity.com/paper/2206.02743/) (2022)
- [Learning Tree-based Deep Model for Recommender Systems](https://mlsanity.com/paper/1801.02294/) (2018)
- [Learning Passage Impacts for Inverted Indexes](https://mlsanity.com/paper/2104.12016/) (2021)
- [T2Ranking: A large-scale Chinese Benchmark for Passage Ranking](https://mlsanity.com/paper/2304.03679/) (2023)
- [Distilling Dense Representations for Ranking using Tightly-Coupled Teachers](https://mlsanity.com/paper/2010.11386/) (2020)
- [RepBERT: Contextualized Text Embeddings for First-Stage Retrieval](https://mlsanity.com/paper/2006.15498/) (2020)
- [Best-First Beam Search](https://mlsanity.com/paper/2007.03909/) (2020)
- [Joint Optimization of Tree-based Index and Deep Model for Recommender Systems](https://mlsanity.com/paper/1902.07565/) (2019)
- [Jointly Optimizing Query Encoder and Product Quantization to Improve Retrieval Performance](https://mlsanity.com/paper/2108.00644/) (2021)
- [Learning Discrete Representations via Constrained Clustering for Effective and Efficient Dense Retrieval](https://mlsanity.com/paper/2110.05789/) (2021)
- [Learning Optimal Tree Models Under Beam Search](https://mlsanity.com/paper/2006.15408/) (2020)
- [Towards Better Web Search Performance: Pre-training, Fine-tuning and Learning to Rank](https://mlsanity.com/paper/2303.04710/) (2023)
- [Contextualized Sparse Representations for Real-Time Open-Domain Question Answering](https://mlsanity.com/paper/1911.02896/) (2019)
- [Incorporating Explicit Knowledge in Pre-trained Language Models for Passage Re-ranking](https://mlsanity.com/paper/2204.11673/) (2022)
- [Label Disentanglement in Partition-based Extreme Multilabel Classification](https://mlsanity.com/paper/2106.12751/) (2021)
- [Falconn++: A Locality-sensitive Filtering Approach for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2206.01382/) (2022)

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

- [LeCaRDv2: A Large-Scale Chinese Legal Case Retrieval Dataset](https://mlsanity.com/paper/2310.17609/) (2023)
- [LexEval: A Comprehensive Chinese Legal Benchmark for Evaluating Large Language Models](https://mlsanity.com/paper/2409.20288/) (2024)
- [THUIR@COLIEE 2023: Incorporating Structural Knowledge into Pre-trained Language Models for Legal Case Retrieval](https://mlsanity.com/paper/2305.06812/) (2023)
- [Wikiformer: Pre-training with Structured Information of Wikipedia for Ad-hoc Retrieval](https://mlsanity.com/paper/2312.10661/) (2023)
- [BLADE: Enhancing Black-box Large Language Models with Small Domain-Specific Models](https://mlsanity.com/paper/2403.18365/) (2024)
- [Taxonomy-guided Semantic Indexing for Academic Paper Search](https://mlsanity.com/paper/2410.19218/) (2024)
- [THUIR@COLIEE 2023: More Parameters and Legal Knowledge for Legal Case Entailment](https://mlsanity.com/paper/2305.06817/) (2023)
- [DELTA: Pre-train a Discriminative Encoder for Legal Case Retrieval via Structural Word Alignment](https://mlsanity.com/paper/2403.18435/) (2024)
- [textttMixGR: Enhancing Retriever Generalization for Scientific Domain through Complementary Granularity](https://mlsanity.com/paper/2407.10691/) (2024)
- [Hierarchical Indexing for Retrieval-Augmented Opinion Summarization](https://mlsanity.com/paper/2403.00435/) (2024)
- [Event Grounded Criminal Court View Generation with Cooperative (Large) Language Models](https://mlsanity.com/paper/2404.07001/) (2024)
- [Incremental IVF Index Maintenance for Streaming Vector Search](https://mlsanity.com/paper/2411.00970/) (2024)
- [REAL: A Reasoning-Enhanced Graph Framework for Long-Term Memory Management of LLMs](https://mlsanity.com/paper/2606.10694/) (2026)
- [WebANNS: Fast and Efficient Approximate Nearest Neighbor Search in Web Browsers](https://mlsanity.com/paper/2507.00521/) (2025)
- [Integrating SAINT with Tree-Based Models: A Case Study in Employee Attrition Prediction](https://mlsanity.com/paper/2604.10337/) (2026)

## Abstract (arXiv)

Recent studies have shown that Dense Retrieval (DR) techniques can significantly improve the performance of first-stage retrieval in IR systems. Despite its empirical effectiveness, the application of DR is still limited. In contrast to statistic retrieval models that rely on highly efficient inverted index solutions, DR models build dense embeddings that are difficult to be pre-processed with most existing search indexing systems. To avoid the expensive cost of brute-force search, the Approximate Nearest Neighbor (ANN) algorithm and corresponding indexes are widely applied to speed up the inference process of DR models. Unfortunately, while ANN can improve the efficiency of DR models, it usually comes with a significant price on retrieval performance. To solve this issue, we propose JTR, which stands for Joint optimization of TRee-based index and query encoding. Specifically, we design a new unified contrastive learning loss to train tree-based index and query encoder in an end-to-end manner. The tree-based negative sampling strategy is applied to make the tree have the maximum heap property, which supports the effectiveness of beam search well. Moreover, we treat the cluster assignment as an optimization problem to update the tree-based index that allows overlapped clustering. We evaluate JTR on numerous popular retrieval benchmarks. Experimental results show that JTR achieves better retrieval performance while retaining high system efficiency compared with widely-adopted baselines. It provides a potential solution to balance efficiency and effectiveness in neural retrieval system designs.