The Acquisition Complexity of Exact Ordered Top-k Retrieval
Certifying an exact top-k answer is a shared-cost acquisition problem: the cheapest information for each comparison need not give the cheapest certificate. We formulate this problem for realized instances and solve it by separating ordered-answer constraints from shared physical reads. A winner path and an exclusion star reduce the logical constraints to a small conditioning interface. For point actions, this gives at most 2^(⌈k/2⌉) evaluations of any nonnegative monotone cost oracle, with a matching deterministic black-box dependence up to one call. For independent refinement and point files, each completion is a global minimum cut. Cost-preserving domain reduction sharpens the search to the minimum retained-domain product Ω over a residual comparison cover, with 2^τ ≤ Ω ≤ 3^τ. Three arbitrary-owner paid files already make top-1 verification hard, whereas coordinated layouts restore exact allocation structure. On eight SciFact instances, residual conditioning recovers every exact optimum in 13 cuts, and shared costs reverse 39 standalone precision preferences. The optimum identifies a 24.05% modeled acquisition gap in the executed cascade, with only 0.69% remaining after counterfactual consolidation and redundant-action removal. Matched execution studies independently demonstrate a 33.86% complete-CPU reduction from selective certificate work and a 39.09% source-byte reduction from jointly using fixed stored fields. The framework makes the acquisition plan an explicit optimization target and identifies where an exact retrieval system can gain from better information, acquisition scheduling or certificate computation.
Authors
- Xu Cao (ORCID: https://orcid.org/0000-0001-8739-5196)
- Wenxuan Xiao (ORCID: https://orcid.org/0009-0003-3363-0391)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-13
- DOI
- https://doi.org/10.5281/zenodo.24198965
- Primary Topic
- Advanced Database Systems and Queries
- Type
- preprint