  Scalable web search systems typically employ multi-stage retrieval
architectures, where an initial stage generates a set of candidate documents
that are then pruned and re-ranked. Since subsequent stages typically exploit a
multitude of features of varying costs using machine-learned models, reducing
the number of documents that are considered at each stage improves latency. In
this work, we propose and validate a unified framework that can be used to
predict a wide range of performance-sensitive parameters which minimize
effectiveness loss, while simultaneously minimizing query latency, across all
stages of a multi-stage search architecture. Furthermore, our framework can be
easily applied in large-scale IR systems, can be trained without explicitly
requiring relevance judgments, and can target a variety of different
efficiency-effectiveness trade-offs, making it well suited to a wide range of
search scenarios. Our results show that we can reliably predict a number of
different parameters on a per-query basis, while simultaneously detecting and
minimizing the likelihood of tail-latency queries that exceed a pre-specified
performance budget. As a proof of concept, we use the prediction framework to
help alleviate the problem of tail-latency queries in early stage retrieval. On
the standard ClueWeb09B collection and 31k queries, we show that our new hybrid
system can reliably achieve a maximum query time of 200 ms with a 99.99%
response time guarantee without a significant loss in overall effectiveness.
The solutions presented are practical, and can easily be used in large-scale
distributed search engine deployments with a small amount of additional
overhead.
