# IRLI: Iterative Re-partitioning for Learning to Index

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 29 references that are in the map.
- First posted on arXiv 17 Mar 2021.

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

- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms](https://mlsanity.com/paper/1807.05614/) (2018)
- [Spreading vectors for similarity search](https://mlsanity.com/paper/1806.03198/) (2018)
- [Practical and Optimal LSH for Angular Distance](https://mlsanity.com/paper/1509.02897/) (2015)
- [Bonsai -- Diverse and Shallow Trees for Extreme Multi-label Classification](https://mlsanity.com/paper/1904.08249/) (2019)
- [A no-regret generalization of hierarchical softmax to extreme multi-label classification](https://mlsanity.com/paper/1810.11671/) (2018)
- [Semantic Product Search](https://mlsanity.com/paper/1907.00937/) (2019)
- [Extreme Classification in Log Memory using Count-Min Sketch: A Case Study of Amazon Search with 50M Products](https://mlsanity.com/paper/1910.13830/) (2019)
- [Randomized partition trees for exact nearest neighbor search](https://mlsanity.com/paper/1302.1948/) (2013)

## Abstract (arXiv)

Neural models have transformed the fundamental information retrieval problem of mapping a query to a giant set of items. However, the need for efficient and low latency inference forces the community to reconsider efficient approximate near-neighbor search in the item space. To this end, learning to index is gaining much interest in recent times. Methods have to trade between obtaining high accuracy while maintaining load balance and scalability in distributed settings. We propose a novel approach called IRLI (pronounced `early'), which iteratively partitions the items by learning the relevant buckets directly from the query-item relevance data. Furthermore, IRLI employs a superior power-of-k-choices based load balancing strategy. We mathematically show that IRLI retrieves the correct item with high probability under very natural assumptions and provides superior load balancing. IRLI surpasses the best baseline's precision on multi-label classification while being 5x faster on inference. For near-neighbor search tasks, the same method outperforms the state-of-the-art Learned Hashing approach NeuralLSH by requiring only ~ 1/6th of the candidates for the same recall. IRLI is both data and model parallel, making it ideal for distributed GPU implementation. We demonstrate this advantage by indexing 100 million dense vectors and surpassing the popular FAISS library by >10% on recall.