Learning Early Exit Strategies for Additive Ranking Ensembles

Francesco Busolin, Claudio Lucchese, Franco Maria Nardini, Salvatore Orlando, Raffaele Perego, Salvatore Trani

TL;DR

LEAR (Learned EArly exit Ranking) is a machine learning framework that speeds up search engine ranking by predicting which documents are unlikely to make the top-$k$ results. By using a tiny, efficient classifier to "early exit" non-promising documents at specific checkpoints, the system achieves up to a 5x speedup with virtually no loss in ranking quality.

What Problem Does This Paper Address?

Modern search engines use "Learning to Rank" (LtR) models—specifically large ensembles of gradient-boosted regression trees (like LambdaMART)—to provide highly accurate results. However, these ensembles often contain thousands of trees. Scoring every candidate document against every single tree is computationally expensive and increases query latency.

While we only care about the top-$k$ (e.g., top 10) results, the system spends a massive amount of time scoring documents that will eventually end up at the bottom of the list. Previous solutions relied on simple heuristics (like "if a document's rank is > 20 after 50 trees, stop scoring it"). This paper argues that these hard-coded rules are sub-optimal and proposes a "learned" approach to decide when to stop.

Methods

The authors introduce LEAR, which treats the decision to stop scoring a document as a binary classification problem.

  1. Sentinel Points: The ensemble is divided at a "sentinel" point (e.g., after the 50th or 100th tree).
  2. The Classifier: At the sentinel, a small, high-speed classifier (a forest of just 10 trees) examines the document. It predicts one of two labels:
  3. Continue: The document is likely to be in the final top-$k$ and should be scored by the remaining trees.
  4. Exit: The document is unlikely to make the cut; stop scoring it now and use its current partial score.
  5. Augmented Features: To make this decision, the classifier uses the original document features plus "dynamic" features available at the sentinel: the document's current rank, its current partial score, and its score normalized against other candidates in the same query.
  6. Cost-Sensitive Training: Since missing a top-ranked document is much worse than accidentally scoring a "loser," the authors use a weighted loss function. This forces the classifier to prioritize accuracy for high-relevance documents that belong in the Continue set.

Datasets

The researchers evaluated LEAR on two standard large-scale Learning-to-Rank benchmarks:

  • MSN-1: A Microsoft dataset with ~31,000 queries and 136 features.
  • Istella: A larger dataset with ~33,000 queries and 220 features, characterized by a very high percentage of non-relevant documents (96%).

Key Insights and Ideas

  • The "Aha" Moment on Features: The most critical features for the early-exit decision aren't the original data points, but the rank and score accumulated at the sentinel. These "stateful" features provide a powerful signal of a document's trajectory.
  • Efficiency vs. Accuracy: Accuracy isn't the primary goal for the classifier; recall for the Continue class is. The system needs to be nearly 100% sure it doesn't accidentally discard a document that would have been in the top 10.
  • Heuristics vs. ML: Hard-coded thresholds (like ERT or EPT) are "short-sighted." A learned model can adapt to the specific distribution of scores in a query, making it much more robust across different types of search results.

Key Results

The authors integrated LEAR into QuickScorer, a state-of-the-art tree traversal algorithm, and found:

  • MSN-1 Dataset: Achieved a 3x speedup with zero loss in ranking quality (NDCG@10).
  • Istella Dataset: Achieved over 5x speedup with a negligible quality loss of less than 0.05%.
  • Superiority over Heuristics: LEAR consistently outperformed previous state-of-the-art heuristic methods, providing better trade-offs between speed and effectiveness across all tested configurations.

Limitations and Future Work

  • Document-Level Focus: This paper focuses on exiting individual documents. However, if an entire query is "easy," it might be possible to stop the whole process early. The authors suggest query-level early exits as a promising future direction.
  • Sentinel Placement: While the paper explores different sentinel points (50, 100, 200 trees), the optimal placement is currently determined experimentally. Automating the selection of these checkpoints could further optimize performance.
  • Classifier Overhead: While the 10-tree classifier is small, it still adds a slight computational cost at the sentinel point. Optimizing the implementation of this "gatekeeper" is essential for maximizing the net speedup.

Summary updated

Abstract

Modern search engine ranking pipelines are commonly based on large machine-learned ensembles of regression trees. We propose LEAR, a novel - learned - technique aimed to reduce the average number of trees traversed by documents to accumulate the scores, thus reducing the overall query response time. LEAR exploits a classifier that predicts whether a document can early exit the ensemble because it is unlikely to be ranked among the final top-k results. The early exit decision occurs at a sentinel point, i.e., after having evaluated a limited number of trees, and the partial scores are exploited to filter out non-promising documents. We evaluate LEAR by deploying it in a production-like setting, adopting a state-of-the-art algorithm for ensembles traversal. We provide a comprehensive experimental evaluation on two public datasets. The experiments show that LEAR has a significant impact on the efficiency of the query processing without hindering its ranking quality. In detail, on a first dataset, LEAR is able to achieve a speedup of 3x without any loss in NDCG1@0, while on a second dataset the speedup is larger than 5x with a negligible NDCG@10 loss (< 0.05%).
BibTeX
@inproceedings{busolin2021learning,
  author = {Francesco Busolin and Claudio Lucchese and Franco Maria Nardini and Salvatore Orlando and Raffaele Perego and Salvatore Trani},
  title = {{Learning Early Exit Strategies for Additive Ranking Ensembles}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2021},
  doi = {10.1145/3404835.3463088},
}

Loading related content...

Figure