Query-level Early Exit for Additive Learning-to-Rank Ensembles

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

In modern web search, the balance between latency and relevance is a constant struggle. Ranking models, particularly large ensembles of decision trees like LambdaMART, have become increasingly complex to capture nuanced relevance signals. However, this complexity comes at a high computational cost. Traditionally, efficiency efforts have focused on "document-level" early exits—pruning individual documents that are unlikely to reach the top ranks.

A recent study, "Query-level Early Exit for Additive Learning-to-Rank Ensembles," proposes a paradigm shift: terminating the entire ranking process for a specific query once its optimal ranking has been achieved. This approach reveals a counter-intuitive reality: for many queries, processing fewer trees doesn't just save time—it actually improves search quality.

The Bottleneck: Ensemble Traversal

Search engines typically employ multi-stage ranking pipelines. After an initial fast retrieval phase, a sophisticated "re-ranker" scores the top candidate documents using an ensemble of thousands of regression trees. The primary bottleneck is the traversal time required to score hundreds of documents against every tree in the ensemble. While document-level pruning helps, it misses a broader opportunity: the realization that the "tail" of a large ensemble often introduces noise that can degrade the ranking of specific queries.

Query Dynamics: Beyond Monotonic Improvement

The core insight of this research lies in how different queries behave as they progress through a Gradient Boosted Regression Tree (GBRT) ensemble. The authors categorize query performance into three distinct patterns:

  • Worsening Queries: These queries reach peak ranking quality (measured by NDCG@10) very early. As more trees are added, their scores actually decline, suggesting the model is "overthinking" or overfitting to global patterns that don't apply to these specific cases.
  • Flat Queries: These reach a performance plateau quickly. Additional computation yields no benefit, representing wasted resources.
  • Improving Queries: These follow the expected path, where more trees lead to better ranking quality.
Query behavior categories: (a) Worsening, (b) Flat, and (c) Improving NDCG scores as the ensemble grows.

The discovery that a significant portion of queries fall into the "Worsening" or "Flat" categories suggests that a one-size-fits-all approach to ensemble depth is inherently inefficient.

Methodology: Sentinels and the Oracle

To exploit these dynamics, the researchers propose placing "sentinels" at strategic intervals within the ensemble (e.g., after 25, 100, or 300 trees). At each sentinel, the system must decide whether to return the current ranking or continue processing.

To establish the theoretical upper bound of this approach, the authors used an "Oracle"—a hypothetical perfect decision-maker that always chooses the optimal exit point for every query. They tested this on major benchmarks, including MSLR-WEB30K and Istella-S, to determine the best sentinel placements through exhaustive validation.

Quantifying the Potential: Oracle Results

The results demonstrate that efficiency and effectiveness are not always in opposition. By identifying the ideal exit point, the system can achieve substantial gains in both speed and accuracy.

Comparison of the original model vs. the ideal early exit performance and the distribution of optimal exit points.

Key findings include:

  • Effectiveness Boost: On the MSLR-WEB30K dataset, an Oracle-based three-sentinel configuration yielded a 7.5% increase in NDCG@10.
  • Efficiency Gain: This same setup provided a 2.2x overall speedup.
  • Early Wins: Even a single sentinel placed very early (e.g., at tree 25) allowed 33% of queries to exit immediately, resulting in a 41.9x speedup for those queries while improving their individual NDCG by over 17%.

Challenges and Future Directions

The primary hurdle for real-world implementation is replacing the Oracle with a practical Classifier. This decision-making model must be extremely lightweight to avoid negating the time saved by exiting early. Furthermore, it must be conservative; the cost of a "False Positive" (exiting too early and losing relevance) is generally higher than a "False Negative" (continuing unnecessarily).

Future research is expected to focus on "listwise features"—analyzing the distribution and stability of document scores at each sentinel—to build robust, real-time classifiers that can realize the dual benefits of query-level early exiting in production environments.

Summary updated

Abstract

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.
BibTeX
@inproceedings{lucchese2020query,
  author = {Claudio Lucchese and Franco Maria Nardini and Salvatore Orlando and Raffaele Perego and Salvatore Trani},
  title = {{Query-level Early Exit for Additive Learning-to-Rank Ensembles}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2020},
  doi = {10.1145/3397271.3401256},
}
Figure