# Certified Error Control of Candidate Set Pruning for Two-Stage Relevance Ranking

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 52 references that are in the map.
- First posted on arXiv 19 May 2022.

## Builds on (most cited first, 24 of 24)

- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [MS MARCO: A Human Generated MAchine Reading COmprehension Dataset](https://mlsanity.com/paper/1611.09268/) (2016)
- [BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models](https://mlsanity.com/paper/2104.08663/) (2021)
- [ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT](https://mlsanity.com/paper/2004.12832/) (2020)
- [Approximate Nearest Neighbor Negative Contrastive Learning for Dense Text Retrieval](https://mlsanity.com/paper/2007.00808/) (2020)
- [Reading Wikipedia to Answer Open-Domain Questions](https://mlsanity.com/paper/1704.00051/) (2017)
- [DeeBERT: Dynamic Early Exiting for Accelerating BERT Inference](https://mlsanity.com/paper/2004.12993/) (2020)
- [Distribution-Free, Risk-Controlling Prediction Sets](https://mlsanity.com/paper/2101.02703/) (2021)
- [SPLADE: Sparse Lexical and Expansion Model for First Stage Ranking](https://mlsanity.com/paper/2107.05720/) (2021)
- [FastBERT: a Self-distilling BERT with Adaptive Inference Time](https://mlsanity.com/paper/2004.02178/) (2020)
- [Sparse, Dense, and Attentional Representations for Text Retrieval](https://mlsanity.com/paper/2005.00181/) (2020)
- [Multi-Stage Document Ranking with BERT](https://mlsanity.com/paper/1910.14424/) (2019)
- [Simple Entity-Centric Questions Challenge Dense Retrievers](https://mlsanity.com/paper/2109.08535/) (2021)
- [COIL: Revisit Exact Lexical Match in Information Retrieval with Contextualized Inverted List](https://mlsanity.com/paper/2104.07186/) (2021)
- [A Few Brief Notes on DeepImpact, COIL, and a Conceptual Framework for Information Retrieval Techniques](https://mlsanity.com/paper/2106.14807/) (2021)
- [Learning Passage Impacts for Inverted Indexes](https://mlsanity.com/paper/2104.12016/) (2021)
- [PAC Confidence Sets for Deep Neural Networks via Calibrated Prediction](https://mlsanity.com/paper/2001.00106/) (2019)
- [Calibrated Prediction with Covariate Shift via Unsupervised Domain Adaptation](https://mlsanity.com/paper/2003.00343/) (2020)
- [A Proposed Conceptual Framework for a Representational Approach to Information Retrieval](https://mlsanity.com/paper/2110.01529/) (2021)
- [PAC Confidence Predictions for Deep Neural Network Classifiers](https://mlsanity.com/paper/2011.00716/) (2020)
- [The Cascade Transformer: an Application for Efficient Answer Sentence Selection](https://mlsanity.com/paper/2005.02534/) (2020)
- [Query-level Early Exit for Additive Learning-to-Rank Ensembles](https://mlsanity.com/paper/2004.14641/) (2020)
- [Learning Early Exit Strategies for Additive Ranking Ensembles](https://mlsanity.com/paper/2105.02568/) (2021)

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

- [Ranked List Truncation for Large Language Model-based Re-Ranking](https://mlsanity.com/paper/2404.18185/) (2024)

## Abstract (arXiv)

In information retrieval (IR), candidate set pruning has been commonly used to speed up two-stage relevance ranking. However, such an approach lacks accurate error control and often trades accuracy off against computational efficiency in an empirical fashion, lacking theoretical guarantees. In this paper, we propose the concept of certified error control of candidate set pruning for relevance ranking, which means that the test error after pruning is guaranteed to be controlled under a user-specified threshold with high probability. Both in-domain and out-of-domain experiments show that our method successfully prunes the first-stage retrieved candidate sets to improve the second-stage reranking speed while satisfying the pre-specified accuracy constraints in both settings. For example, on MS MARCO Passage v1, our method yields an average candidate set size of 27 out of 1,000 which increases the reranking speed by about 37 times, while the MRR@10 is greater than a pre-specified value of 0.38 with about 90% empirical coverage and the empirical baselines fail to provide such guarantee. Code and data are available at: https://github.com/alexlimh/CEC-Ranking.