# Efficient and Effective Tail Latency Minimization in Multi-Stage Retrieval Systems

arXiv: https://arxiv.org/abs/1704.03970 · HTML: https://mlsanity.com/paper/1704.03970/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Apr 2017.

## Built on by (most cited first, 5 of 5)

- [The Expando-Mono-Duo Design Pattern for Text Ranking with Pretrained Sequence-to-Sequence Models](https://mlsanity.com/paper/2101.05667/) (2021)
- [A Proposed Conceptual Framework for a Representational Approach to Information Retrieval](https://mlsanity.com/paper/2110.01529/) (2021)
- [Policy-Gradient Training of Language Models for Ranking](https://mlsanity.com/paper/2310.04407/) (2023)
- [Unsupervised Search Algorithm Configuration using Query Performance Prediction](https://mlsanity.com/paper/2210.00767/) (2022)
- [Reranking Passages with Coarse-to-Fine Neural Retriever Enhanced by List-Context Information](https://mlsanity.com/paper/2308.12022/) (2023)

## Abstract (arXiv)

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.