  Search engine ranking pipelines are commonly based on large ensembles of
machine-learned decision trees. The tight constraints on query response time
recently motivated researchers to investigate algorithms to make faster the
traversal of the additive ensemble or to early terminate the evaluation of
documents that are unlikely to be ranked among the top-k. In this paper, we
investigate the novel problem of \textit{query-level early exiting}, aimed at
deciding the profitability of early stopping the traversal of the ranking
ensemble for all the candidate documents to be scored for a query, by simply
returning a ranking based on the additive scores computed by a limited portion
of the ensemble. Besides the obvious advantage on query latency and throughput,
we address the possible positive impact of query-level early exiting on ranking
effectiveness. To this end, we study the actual contribution of incremental
portions of the tree ensemble to the ranking of the top-k documents scored for
a given query. Our main finding is that queries exhibit different behaviors as
scores are accumulated during the traversal of the ensemble and that
query-level early stopping can remarkably improve ranking quality. We present a
reproducible and comprehensive experimental evaluation, conducted on two public
datasets, showing that query-level early exiting achieves an overall gain of up
to 7.5% in terms of NDCG@10 with a speedup of the scoring process of up to
2.2x.
