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

Nilesh Gupta, Patrick H. Chen, Hsiang-Fu Yu, Cho-Jui Hsieh, Inderjit S Dhillon

TL;DR

ELIAS introduces an end-to-end framework for Extreme Multi-label Classification (XMC) that replaces traditional, rigid tree-based search indices with a learnable, weighted graph-based index. By optimizing the index structure jointly with the deep learning model, ELIAS significantly improves both prediction precision and recall while maintaining sub-millisecond inference speeds on datasets with millions of labels.

What Problem Does This Paper Address?

In many real-world applications—such as web search, product recommendation, and ad targeting—machine learning models must select the most relevant outputs from a pool of millions of possibilities. This setup is known as Extreme Multi-label Classification (XMC).

Because evaluating every single label for a given input is computationally impossible at scale, standard XMC methods use a "search index" to quickly shortlist a few thousand candidate labels. Typically, this index is built by clustering labels into a static, hierarchical tree structure before training begins.

However, this traditional approach has two major flaws:

  1. The Decoupling Bottleneck: Because the index is fixed during initialization, the downstream machine learning model cannot adapt or correct poor initial clustering choices.
  2. The Multi-Modal Limitation: Tree structures force each label into a single, mutually exclusive cluster. In reality, a popular label (e.g., a highly sought-after product) might be relevant to completely different user contexts, meaning it possesses a multi-modal distribution that a strict tree cannot capture.

Methods

ELIAS (End-to-end Learning to Index and Search) addresses these limitations by relaxing the rigid tree index into a specialized, sparsely connected, weighted graph-based index.

Figure 1: Traditional partition-based index vs ELIAS index; here an arrow from a cluster to a label denotes the assignment of the label to the cluster, arrow width indicates the weight of the assignment. (left) Existing partition based XMC methods use a shallow balanced tree as the index structure with a label uniquely assigned to exactly one cluster; moreover, they initialize the clusters over pre-defined features and keep them fixed throughout the training procedure. (right) ELIAS generalizes the tree based index to a sparsely connected graph-based index and learns the cluster-to-label assignments end-to-end with the task objective during training.

1. The Graph-Based Index

Instead of hard cluster assignments, ELIAS models cluster-to-label assignments as soft, learnable parameters via an adjacency matrix $A$. This allows a single label to be connected to multiple clusters, natively supporting multi-modal data distributions. To prevent the $O(CL)$ computational explosion (where $C$ is clusters and $L$ is labels), the authors enforce a strict row-wise sparsity constraint on $A$.

2. Staged Training

Training a flexible graph index from scratch poses a massive optimization challenge. ELIAS solves this using a two-stage training pipeline:

  • Stage 1: The model is trained using a standard, fixed tree index generated by balanced k-means clustering.
  • Stage 2: The trained Stage 1 model is used to initialize the sparse adjacency matrix $A$. The entire network—including the text encoder (BERT), cluster classifiers, label classifiers, and the index graph itself—is then jointly optimized end-to-end.

3. Enhanced Variant (ELIAS++)

The authors also introduce ELIAS++, which incorporates a high-capacity sparse linear ranker to re-rank the top 100 predictions. Because sparse rankers tend to underestimate tail labels, they include a decision-tree-based score calibration module to balance predictions across all label frequencies.

Datasets

The authors evaluated ELIAS on four standard, large-scale extreme classification benchmarks:

  • LF-AmazonTitles-131K: A short-text product recommendation dataset containing ~131,000 labels.
  • Amazon-670K: A full-text product recommendation dataset containing ~670,000 labels.
  • Wikipedia-500K: A document tagging dataset containing ~501,000 labels.
  • Amazon-3M: The largest benchmark used, featuring over 2.8 million labels.

Key Insights and Ideas

  • Dynamic Indexing Beats Static Clustering: Allowing the search index to evolve alongside the text encoder prevents the model from getting trapped by sub-optimal initial clusters.
  • Head Labels Need Multiple Homes: Popular "head" labels benefit the most from graph-based indexing. The data shows that ELIAS assigns head labels to significantly more clusters than tail labels, matching their multi-modal nature in real-world data.
  • Bridging the Gap to Brute-Force: ELIAS is the first indexing method that matches or marginally outperforms a brute-force, one-versus-all (OvA) baseline in recall, proving that intelligent shortlisting doesn't have to sacrifice accuracy.

Key Results

ELIAS achieves state-of-the-art performance across all evaluated benchmarks, demonstrating notable gains in both accuracy and speed:

  • Accuracy Improvements: ELIAS++ outperforms existing XMC methods by up to 2.5% in Precision@1 and up to 4% in Recall@100.
  • Inference Speed: Despite the added flexibility of a graph structure, ELIAS maintains exceptional efficiency. On a single NVIDIA A6000 GPU, it delivers sub-millisecond prediction latency (0.67 ms per data point) even on the massive Amazon-3M dataset.

Limitations and Future Work

While ELIAS marks a significant step forward, the authors note two primary limitations:

  1. Shallow Graph Structure: ELIAS currently utilizes a shallow graph structure (Root $\rightarrow$ Clusters $\rightarrow$ Labels). Scaling up to billion-scale label spaces will likely require extending this framework to support deep, multi-layered graph structures.
  2. Supervision Dependency: The current method relies on many-shot or few-shot training scenarios where labels have existing training data. Adapting ELIAS to zero-shot scenarios—where new labels appear without any prior training examples—remains an open and exciting direction for future research.

Summary updated

Abstract

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.
BibTeX
@inproceedings{gupta2022elias,
  author = {Nilesh Gupta and Patrick H. Chen and Hsiang-Fu Yu and Cho-Jui Hsieh and Inderjit S Dhillon},
  title = {{ELIAS: End-to-End Learning to Index and Search in Large Output Spaces}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=RF5Lb6NaZp},
}
Figure