Learning Early Exit Strategies for Additive Ranking Ensembles

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

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 [email protected], while on a second dataset the speedup is larger than 5x with a negligible [email protected] 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