# ELIAS: End-to-End Learning to Index and Search in Large Output Spaces

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 39 references that are in the map.
- First posted on arXiv 16 Oct 2022.

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

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [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)
- [Transformer Memory as a Differentiable Search Index](https://mlsanity.com/paper/2202.06991/) (2022)
- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [Pre-training Tasks for Embedding-based Large-scale Retrieval](https://mlsanity.com/paper/2002.03932/) (2020)
- [DiSMEC - Distributed Sparse Machines for Extreme Multi-label Classification](https://mlsanity.com/paper/1609.02521/) (2016)
- [Fast Multi-Resolution Transformer Fine-tuning for Extreme Multi-label Text Classification](https://mlsanity.com/paper/2110.00685/) (2021)
- [Bonsai -- Diverse and Shallow Trees for Extreme Multi-label Classification](https://mlsanity.com/paper/1904.08249/) (2019)
- [LightXML: Transformer with Dynamic Negative Sampling for High-Performance Extreme Multi-label Text Classification](https://mlsanity.com/paper/2101.03305/) (2021)
- [PECOS: Prediction for Enormous and Correlated Output Spaces](https://mlsanity.com/paper/2010.05878/) (2020)
- [DeepXML: A Deep Extreme Multi-Label Learning Framework Applied to Short Text Documents](https://mlsanity.com/paper/2111.06685/) (2021)
- [NGAME: Negative Mining-aware Mini-batching for Extreme Classification](https://mlsanity.com/paper/2207.04452/) (2022)
- [Extreme Regression for Dynamic Search Advertising](https://mlsanity.com/paper/2001.05228/) (2020)
- [Learned Indexes for a Google-scale Disk-based Database](https://mlsanity.com/paper/2012.12501/) (2020)
- [Label Disentanglement in Partition-based Extreme Multilabel Classification](https://mlsanity.com/paper/2106.12751/) (2021)

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

- [Scaling Image Geo-Localization to Continent Level](https://mlsanity.com/paper/2510.26795/) (2025)
- [Dual-Encoders for Extreme Multi-Label Classification](https://mlsanity.com/paper/2310.10636/) (2023)
- [Incremental IVF Index Maintenance for Streaming Vector Search](https://mlsanity.com/paper/2411.00970/) (2024)
- [LLM-guided Hierarchical Search for End-to-end Reasoning Intensive Retrieval](https://mlsanity.com/paper/2510.13217/) (2025)
- [AdANNS: A Framework for Adaptive Semantic Search](https://mlsanity.com/paper/2305.19435/) (2023)
- [Large Language Models Meet Extreme Multi-label Classification: Scaling and Multi-modal Framework](https://mlsanity.com/paper/2511.13189/) (2025)
- [Large Language Model as a Teacher for Zero-shot Tagging at Extreme Scales](https://mlsanity.com/paper/2406.09288/) (2024)
- [Prototypical Extreme Multi-label Classification with a Dynamic Margin Loss](https://mlsanity.com/paper/2410.20401/) (2024)
- [Labels in Extremes: How Well Calibrated are Extreme Multi-label Classifiers?](https://mlsanity.com/paper/2411.04276/) (2024)
- [EHI: End-to-end Learning of Hierarchical Index for Efficient Dense Retrieval](https://mlsanity.com/paper/2310.08891/) (2023)
- [Label Embedding via Low-Coherence Matrices](https://mlsanity.com/paper/2305.19470/) (2023)
- [On the Necessity of World Knowledge for Mitigating Missing Labels in Extreme Classification](https://mlsanity.com/paper/2408.09585/) (2024)
- [ASTRA: Accurate and Scalable ANNS-based Training of Extreme Classifiers](https://mlsanity.com/paper/2409.20156/) (2024)
- [Extreme Meta-Classification for Large-Scale Zero-Shot Retrieval](https://mlsanity.com/paper/2606.25237/) (2026)

## Abstract (arXiv)

Extreme multi-label classification (XMC) is a popular framework for solving many real-world problems that require accurate prediction from a very large number of potential output choices. A popular approach for dealing with the large label space is to arrange the labels into a shallow tree-based index and then learn an ML model to efficiently search this index via beam search. Existing methods initialize the tree index by clustering the label space into a few mutually exclusive clusters based on pre-defined features and keep it fixed throughout the training procedure. This approach results in a sub-optimal indexing structure over the label space and limits the search performance to the quality of choices made during the initialization of the index. In this paper, we propose a novel method ELIAS which relaxes the tree-based index to a specialized weighted graph-based index which is learned end-to-end with the final task objective. More specifically, ELIAS models the discrete cluster-to-label assignments in the existing tree-based index as soft learnable parameters that are learned jointly with the rest of the ML model. ELIAS achieves state-of-the-art performance on several large-scale extreme classification benchmarks with millions of labels. In particular, ELIAS can be up to 2.5% better at precision@1 and up to 4% better at recall@100 than existing XMC methods. A PyTorch implementation of ELIAS along with other resources is available at https://github.com/nilesh2797/ELIAS.