# Learning Early Exit Strategies for Additive Ranking Ensembles

**Authors:** Francesco Busolin, Claudio Lucchese, Franco Maria Nardini, Salvatore Orlando, Raffaele Perego, Salvatore Trani  
**arXiv:** [2105.02568](https://arxiv.org/abs/2105.02568)  
**Date:** 2021-05-06  
**Summary page:** https://www.summarizepaper.com/en/paper/2105.02568v1/

## Key points

- Large machine-learned ensembles of regression trees commonly used in search engine ranking pipelines
- LEAR technique proposed to enhance efficiency and reduce query response time by leveraging a classifier to predict early exit from ensemble
- Augmented representation for documents used in training classifier includes additional information like rank, accumulated score, normalized value, and number of candidates for the query
- Comparison between LEAR and EPT on MSN-1 dataset showed up to 3x speedup with no degradation in effectiveness when placing sentinel after 50th tree
- Adjusting confidence threshold allows for different levels of aggressiveness with varying speedups and ranking quality degradation
- LEAR demonstrated significant improvements in query processing efficiency without compromising ranking quality on public datasets

## Summary

, , , , 

In the realm of modern search engine ranking pipelines, large machine-learned ensembles of regression trees are commonly utilized. However, to enhance efficiency and reduce query response time, a novel technique called LEAR has been proposed. LEAR leverages a classifier that predicts whether a document can exit the ensemble early, thus reducing the number of trees traversed. This decision is made at a sentinel point after evaluating a limited number of trees, using partial scores to filter out non-promising documents. To train the classifier with examples of both continuing and exiting documents, an augmented representation for documents is employed. This representation includes additional information available at the sentinel point such as the document's rank, accumulated score, normalized value, and number of candidates for the query. Handling imbalance in the training set where continue documents are a minority is addressed by exploiting quality metrics like NDCG@k.

 between LEAR and EPT (existing method) were compared on the MSN-1 dataset. The results showed that placing the sentinel after the 50th tree yielded no degradation in effectiveness with up to 3x speedup for small confidence thresholds. By adjusting the confidence threshold, different levels of aggressiveness can be achieved with varying speedups and ranking quality degradation. Further comparisons were made with existing methods in related research areas such as pruning ensembles during or after training phases, budget-aware learning-to-rank algorithms, and early termination heuristics for reducing scoring process costs. Overall, LEAR demonstrated significant improvements in query processing efficiency without compromising ranking quality on public datasets. In conclusion, LEAR presents a promising approach to optimizing search engine ranking pipelines by efficiently filtering out non-relevant documents early in the scoring process while maintaining high-quality rankings for top-k results. Through comprehensive experimental evaluations and comparisons with existing methods, LEAR showcases its potential to significantly enhance query response times in production-like settings.