When Does Adaptive Reordering Help? Minimax Limits for Costly Model Comparison

Costly human labels make model comparison a sequential acquisition problem: relevance judgments, audits and expert labels are bought one at a time until the verdict between a candidate model and a deployed control is settled. An adjudicator can adapt when it stops and what it labels next. We ask what the second kind of adaptivity is worth for exact, prior-free verdicts on a fixed cohort. When unresolved cases carry no hard cross-case constraints (Cartesian feasible support, a logical condition rather than a probabilistic independence assumption), the objective is additive and the decision monotone, adaptive reordering has zero deterministic minimax value: every deterministic adaptive policy can be forced to label every decision-relevant case, while a fixed list sorted by uncertainty width labels no other case. This holds for multivalued outcomes, multi-tier decisions and arbitrary label costs, and although the optimal cost is weakly NP-hard to compute, an optimal policy needs only one sort; for two classifiers compared by accuracy, the relevant cases are exactly the disagreements. The boundary is sharp: known cross-case coupling raises the largest possible fixed-to-adaptive ratio from one to Θ(n/log n) for bounded outcome alphabets, and a non-monotone decision, a prior, or randomization each breaks the equality on three coordinates. In a retrospective replay over genuine human judgments for 108,715 fully judged run–topic comparisons from TREC-COVID, the width-ordered list reaches the exact verdict after a median of 60% of the judgments, against 79% for random order and 43% for a realized-path oracle; on small instances, even the exact expected-cost-optimal adaptive policy under a fitted cross-topic prior recovers 20.4% of this gap on average and none at the median, suggesting that much of the hindsight advantage is not exploitable.