Learning Early Exit Strategies for Additive Ranking Ensembles

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

Introduction

Modern search ranking relies on complex ensembles of gradient-boosted regression trees, such as LambdaMART. While highly accurate, these models are computationally expensive, often requiring thousands of trees to score each document. In a typical query, the system spends significant resources scoring documents that will never reach the top-k results. We present LEAR (Learned EArly exit Ranking), a framework that uses machine learning to identify and "early exit" non-promising documents, significantly reducing query latency.

The LEAR Framework

LEAR treats the decision to stop scoring a document as a binary classification problem. The ensemble is divided at a sentinel point (e.g., after 50 or 100 trees). At this checkpoint, a small, efficient classifier—consisting of just 10 trees—evaluates the document to decide if it should continue through the remaining ensemble or exit early using its current partial score.

To ensure high ranking quality, LEAR uses cost-sensitive training. Missing a document that belongs in the top-k is far more detrimental than over-scoring a low-relevance document. Consequently, the classifier is optimized for high recall on the "Continue" class.

The Importance of Dynamic Features

A key innovation in LEAR is the use of "dynamic" features generated at the sentinel point. In addition to the original document features, the classifier considers the document's current rank, its partial score, and its score relative to other candidates in the same query.

Normalized feature importance showing that document rank at the sentinel point is the most critical signal for early exit decisions.

As shown in the feature importance analysis, the document's rank at the sentinel is the most powerful predictor of its final position. These stateful features allow the model to adapt to the specific distribution of scores within a query, making it more robust than static, hard-coded heuristics.

Experimental Results

We evaluated LEAR on two major benchmarks: MSN-1 and Istella. The framework was integrated into QuickScorer, a state-of-the-art tree traversal algorithm, to measure real-world performance gains.

On the MSN-1 dataset, LEAR achieved a 3x speedup with zero loss in NDCG@10. On the larger Istella dataset, which is characterized by a high volume of non-relevant documents, the performance gains were even more pronounced.

Comparison of LEAR and the EPT heuristic on the Istella dataset, demonstrating superior speedup-effectiveness trade-offs.

As illustrated in the Istella results, LEAR consistently outperforms heuristic methods like EPT. It achieves a 5x speedup with a negligible NDCG@10 loss of less than 0.05%. Even at higher speedups, LEAR maintains a better balance between efficiency and ranking effectiveness than previous state-of-the-art approaches.

Conclusion

LEAR demonstrates that a learned approach to early exiting can dramatically improve the efficiency of additive ranking ensembles. By leveraging dynamic features at sentinel points and employing cost-sensitive classifiers, search engines can achieve significant speedups—up to 5x—without compromising the quality of results delivered to users. Future work includes exploring query-level early exits and automating the placement of sentinel points to further optimize performance.

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},
}
Figure