acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
learning theory
Keywords:
adaptive evaluation, model evaluation, structured uncertainty, minimax certification, sequential decision making

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_iQH8OpenReview ↗
Rating
1
Confidence
1
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The authors study a setting where an annotator, given a fixed set of data points (called a “cohort”) with predictions from two different models but missing ground-truth labels, wants to determine which model performs better efficiently. To do so, they can acquire ground-truth labels sequentially. Their goal is using the models’ predictions and the labels acquired so far to decide which point to label next and when to stop. The main result says that an adversary can force any deterministic adaptive policy to inspect every decision-relevant example.

Critical strengths
  • The problem motivation is strong and it uses a useful distinction between adaptive stopping and adaptive reordering. It could be a good contribution given a cleaner exposition and evaluation.
Critical weaknesses
  • The paper is almost impossible to parse as an self-contained manuscript. It contains a lot of jargon even in the Introduction and Problem Set Up section where one expects to be exposed to the technical problem in a clean and coherent order. That makes it very hard to understand the main question it answers and being able to evaluate it for its technical contributions.
    Examples: The very first sentence of the introduction: A candidate model is ready to replace the deployed control.
    What is this sentence serving? What is a control?
    The very first sentence of Problem Setup and Identification is Consider a fixed control f0f^0 and a fixed candidate f1f^1 evaluated on n cases from a fixed cohort. What is the control ff? Is it a function? What is the domain and what is the output?

  • The theoretical novelty is unclear. The paper should distinguish which results require genuinely new technical arguments from those obtained by combining or extending established results, and explain why these extensions constitute a substantive contribution.

  • In the TREC-COVID analysis, prior-guided adaptive selection improves expected labeling cost over the optimal fixed order under the same prior, but the improvement is minor. This limits the empirical evidence for a substantial practical benefit from adaptive reordering

Questions for authors
  • The main theoretical comparison concerns worst-case labeling cost. However since this problem is of practical interest, the implications need clarification: how should a practitioner use this result to decide which examples to label under a limited budget?
  • The Cartesian-support assumption does not itself exclude statistical correlations between labels; (it excludes hard cross-example constraints that make some combinations of individually feasible outcomes jointly impossible), can you explain how predictive correlations could inform label selection, even when the feasible support remains Cartesian?
Reviewer_KKwCOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies efficient sequential information acquisition --- motivated in particular by soliciting human labels to data that could help compare two models' performance. On an axis complementary to a lot of recent work (which often focused on adaptive stopping rules as an efficiency-enhancing mechanism), it asks whether rotating the order of the unlabeled points adaptively can help determine the model comparison "reliably faster", for several notions of "reliably faster". In particular, the paper distinguishes "guaranteed", "exploitable", and "hindsight" advantage, and studies the "guaranteed"/minimax question theoretically and the other two kinds empirically, on real-world "TREC-COVID" comparison data. In particular, on the theoretical front, it rigorously shows that under some natural assumptions (i.e. when no "information externalities" are created), the switched order cannot help in the minimax sense, while under other natural assumptions ("dependent" structures), a gap of a factor of n/log n is possible by contrast (along with auxiliary results).

Critical strengths

I do believe that the setting and research question that this paper takes up --- on whether the "reordering" dimension is worth considering towards enhancing information acquisition efficiency and when --- are both theoretically meaningful and potentially relevant to ML/AI systems practice. The experiments are somewhat practical and are a good counterpoint to the theoretical results.

As another (unfortunately also a bit lukewarm) strong point, this manuscript has somewhat decent exposition compared to the ubiquitous AI slop papers of today --- the writing and presentation bear the signs of substantive human author involvement. As such, the paper is readable, with some effort. In the same vein, I would like to commend the authors' honest account of how their contribution compares to (a lot of) related prior theoretical work; in fact, due to this enthusiastic literature comparison, the paper's references end up spanning a wide gamut of literatures, from fundamental TCS/algorithms to statistics, which is just added confirmation that the paper's proposed endeavor can be considered useful and timely.

Critical weaknesses

First, unfortunately I did not find the theoretical contributions of the paper to be impressive enough to reliably clear the bar. To begin with, generally speaking the intuition about the results is clear from the onset --- adaptivity/active approaches can help when later decisions can be favorably constrained by earlier ones. So there is not much that I've learned from the paper at this level. At the next level, formalizing this intuition is not particularly hard either, and I did not find any remarkable proof ideas. Finally, indeed, similar proof approaches/arguments abound e.g. in the theoretical computer science/sequential algorithms literature --- e.g. the authors rightfully recalled the notion of evasiveness that, while it does not cover this setting wholesale without modifications, still gives the short blueprint for how such results can be shown.

While I didn't find the substance of the paper very exciting, the paper would benefit from de-slopping regardless. Currently, the exposition appears to be AI-generated to a nonnegligible degree, thwarting human readers in various places: I am referring to e.g. terminology/sentences such as "Under Cartesian feasible support, additive utility and a monotone decision rule, adaptive reordering has zero deterministic minimax value: every deterministic adaptive policy can be forced to reveal every decision-relevant case, while a fixed width-sorted list reveals no irrelevant case". Words like "Cartesian feasible support" mean little to a reader just starting to parse the paper without having understood the rest of it yet --- and such peculiarly detailed accounts of the details of the proof intuition, etc., are somewhat mistimed.

On the AI topic, appendices E and F are somewhat weird --- F offers an account of the authors' verification efforts, which apparently included numerically verifying the theoretical results of the paper; while E similarly contains a lengthy exploratory scan paragraph with some numerical verification details that were not, in my opinion, necessary.

Questions for authors

While I cannot currently promise to necessarily increase my rating of the paper if this gets done, but as pointed out above, the paper needs to be further de-slopped to seriously enhance its readability. If/once that is done, the discussion can then fully shift to its theoretical/empirical contributions.

Reviewer_A7iJOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper analyzes the cost of manually labeling a set of inputs when we would like to compare the performance of two models. Both models make predictions on the inputs, and we identify the inputs on which the two models disagree. Since manually labeling the inputs is costly, we need to prioritize them. After labeling a subset of the inputs, we can decide the relative quality of the models. The paper shows that a fixed policy for choosing the order of inputs can perform worse than a policy that decides the next input to label based on the history seen so far (Equation 3). The authors prove a theoretical gap between the two choices (Proposition 3). Under stricter assumptions, the performance of a fixed “width-order” policy matches the performance of any adaptive policy (Theorem 1). The paper also shows, in passing, that computing the optimal cost is NP-hard, even though the optimal order is obtained by a single sort (paragraph above Section 3.1). The paper briefly discusses the impact of randomized policies.

The authors analyze the TREC-COVID dataset. They find that random ordering of manual labeling is worse than width ordering. However, a “realized oracle,” which knows the labels in hindsight, needs far fewer labels, and a prior-guided adaptive policy closes only a small part of this gap.

Critical strengths
  1. The paper tackles an important question and proves a theoretical gap.
  2. The authors demonstrate the performance of the width-order policy.
Critical weaknesses
  1. The writing is terse. For example, the inputs are referred to as “cases” and “coordinates” interchangeably. The stopping condition for manual evaluation is defined in the text in lines 147–148, which was very difficult to follow; it could have been defined formally using the primitive Cert. It is also not made clear what d is; it is referred to as a “world” without much formal introduction.
  2. The mathematical results are shallow and easy to prove.
  3. In Section 3.1, Propositions 2–3 are mixed with counterexamples and the proof of the gap, without clear separation.
  4. Proposition 4 moves in the direction of randomized policies, but the paper does not build on it, and the theoretical discussion stops there.
  5. The prior-guided adaptive policy is not explained in sufficient detail in the main paper. Since adaptive reordering is the subject of the paper’s title (“When Does Adaptive Reordering Help?”), I think this policy should be an important aspect of the paper.
  6. The experiments in the paper do not demonstrate that this gap can be observed in practice.

Overall, I think that the paper is sound with limited novelty.

Questions for authors
  1. Why did you analyze only a single case study (apart from the additional study in the appendix)?
  2. What is the “realized oracle”? Table 1 says it is not a policy. Why are we comparing against this oracle?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.