Certified Error Control of Candidate Set Pruning for Two-Stage Relevance
  Ranking
  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.
