Certified Error Control of Candidate Set Pruning for Two-Stage Relevance Ranking (2022)

Abstract: 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 against computational efficiency in an empirical fashion, missing 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 reduces the average candidate set size from 1000 to 27, increasing reranking speed by about 37 times, while keeping MRR@10 greater than a pre-specified value of 0.38 with about 90% empirical coverage. In contrast, empirical baselines fail to meet such requirements. Code and data are available at: https://github.com/alexlimh/CEC-Ranking.

## introduction a two-stage relevance ranking architecture has been an indispensable component for knowledgeintensive natural language processing tasks such as information retrieval (ir) @xcite and open-domain question answering (openqa) @xcite . such a system usually consists of a high-recall first stage that retrieves a set of documents from a massive corpus and a high-precision reranker that improves the ranking of the retrieved candidate sets. the first-stage retrieval, often implemented by approximate nearest neighbour search @xcite or inverted index search @xcite , is quite efficient while the second-stage reranking usually has high latency due to the trend of using overparameterized pre-trained language models and large candidate set sizes. previous work in early exiting proposed to predict the ranking score using only a partial model @xcite @xcite or prune the candidate set before reranking @xcite to trade accuracy off against speed. however, such methods lack accurate error control which can not provide guarantees to satisfy the exact accuracy constraints specified by users. in this paper, we focus on candidate set pruning methods of early exiting for two-stage relevance ranking, and we show that a simple scorethresholding method can yield predictions with certified error control using the prediction sets theory @xcite @xcite . instead of predicting a single target, prediction sets will yield sets that contain the desired fraction of the population with high probability. moreover, we allow users to specify the error tolerance of their custom metrics and our method will return the pruned set of candidates that satisfies the constraints with a finite sample guarantee. our method makes no assumption about the data distributions and models, except that the calibration data are exchangeable with the test data. fig. 2 illustrates the calibration and test procedures for certified error control of candidate set pruning. challenges. however, directly applying prediction set methods to relevance ranking can be problematic. unlike classification, where the true label will be eventually included in the predicted set as the set size grows, in relevance ranking, users care more about the rank of the positives. therefore, a rank requirement from users might not always be satisfied as the ranking system might not be good enough to rank the positive documents correctly no matter how large the candidate set is. ## conclusion we present a theoretically principled method for candidate set pruning of two-stage ranking systems, allowing users to control a customized loss under the desired threshold with high probability. we further propose to correct the risk threshold or confidence level if the desired risk cannot be achieved given the ranking system. experiments performed under in-domain (ms marco passage v1) and out-of-domain (quora) settings show that our method provides a consistent performance guarantee to candidate set pruning across multiple ranking systems.