Top-k on a Budget: Adaptive Ranking with Weak and Strong Oracles

arXiv:2601.20989v1 Announce Type: new
Abstract: Identifying the top-$k$ items is fundamental but often prohibitive when exact valuations are expensive. We study a two-oracle setting with a fast, noisy weak oracle and a scarce, high-fidelity strong oracle (e.g., human expert verification or expensive simulation). We first analyze a simple screen-then-certify baseline (STC) and prove it makes at most $m(4varepsilon_{max})$ strong calls given jointly valid weak confidence intervals with maximum radius $varepsilon_{max}$, where $m(cdot)$ denotes the near-tie mass around the top-$k$ threshold. We establish a conditional lower bound of $Omega(m(varepsilon_{max}))$ for any algorithm given the same weak uncertainty. Our main contribution is ACE, an adaptive certification algorithm that focuses strong queries on critical boundary items, achieving the same $O(m(4varepsilon_{max}))$ bound while reducing strong calls in practice. We then introduce ACE-W, a fully adaptive two-phase method that allocates weak budget adaptively before running ACE, further reducing strong costs.