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.
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.
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