acceptodds
Under review as a conference paper at ICLR 2027

How Much Evidence Is Needed to Trust Model Comparisons?

10 views

Abstract

Offline model comparisons depend on which candidates were allowed to compete. When historical membership is incomplete, a reconstructed list can turn an uncertain comparison into a seemingly precise winner. We study the evidence needed for a certified model choice. The key is shared uncertainty: membership changes can cancel between models. We prove that a comparison can require zero new records while fixing all selections requires linearly many. For single-query top- evaluation, we characterize the entire contrast through one shared boundary block. This yields an exact algorithm whose exponential dependence is local, and a linear-time regret formula for disjoint adjacent swaps. A matching search separation shows that exact computation and minimal evidence acquisition are distinct problems. For general model orders and multiple queries, joint disagreement and cutoff constraints provide efficient, monotone regret bounds. These certificates support comparison-guided acquisition and stopping before full recovery. Seven trained stock scorers exhibit 42 winner reversals across 132 pool-date comparisons; 23 incur regret exceeding 0.01. Frozen-score experiments repair all 23 above-tolerance errors while leaving more than half the candidate memberships unresolved on average. In a controlled width-two stock reranking task, the exact block certificate certifies 67/132 comparisons versus 5/132 for Cutoff and a block-span control at the same additional 25% record budget. Separate policy experiments save 53.1% of recommendation records at zero regret.

Primary area:
learning theory
Keywords:
model evaluation, certified model selection, ranking, candidate-set uncertainty, evidence complexity, active evaluation

Reviews

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

The paper asks how much evidence about the historical candidate pool is needed to certify that one ranking model beats another, when pool membership is only partially known. The main technical result is an exact algorithm for single-query top-K comparisons, based on the observation that only one shared block straddles the cutoff, with a closed form for adjacent swaps. Experiments use stock scorers on reconstructed A-share pools, a constructed reranking task, and MovieLens.

Critical strengths

The formulation is nice. Looking at the difference between the models' selections rather than at each model's value, and the boundary-block observation, are clean ideas, and the math seems to be correct. The experiments are done carefully and also report the unfavourable results.

Critical weaknesses

The paper is hard to read: Notations and discussions in the main body need the appendix constantly.

The payoff is not shown on real comparisons. The exact Block algorithm can't be run on the natural scorer pairs, whose boundary blocks have thousands of unknown bits (Table 15). It is only used in a constructed reranking, and at width 2 the exact answer is basically the closed form of Eq. (6). On natural comparisons the refinements save very little: Cutoff saves about 0.5% of records over Joint on stocks and nothing on MovieLens, and Contrast saves 1.3% over Frontier on stocks.

The central claim, that certifying a comparison needs much less evidence than recovering all selections, is not really measured on real data. "More than half the memberships unresolved" is measured against full reconstruction, not against fixing all selections. Repairing all 23 errors is guaranteed by construction once a certificate is issued (Sec. 7 says so), so it is not really an empirical finding. In the stock study all memberships are actually known, since pools are rebuilt from market-cap ranks, so the missingness and costs are simulated, and there is no simple non-certified baseline.

Questions for authors
  1. Can you report the number of records needed to fix all selections on the same trajectories? A large gap vs Joint/Cutoff would make me more positive.

  2. At the same budgets, how often would a simple plug-in winner (known memberships plus the snapshot for the rest) be wrong?

  3. Is there a natural setting where models differ only by local reranking, so that Block is actually useful?

Reviewer_yNxTOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper studied the problem of the evidence needed for a certified model choice. The authors argued that the key is shared uncertainty, where membership changes can cancel between models. The authors proved that a comparison can require zero new records while fixing all selections requires linearly many. For single-query top-evaluation, the authors characterized the entire contrast through one shared boundary block, yielding an exact algorithm whose exponential dependence is local, and a linear-time regret for disjoint adjacent swaps. The authors also conducted experiments to verify their theoretical results.

Critical strengths
  1. The problem of studying the amount of evidence needed for trusting model comparisons seems to be a new problem.

  2. This paper provides both theoretical analysis and empirical studies.

Critical weaknesses
  1. This presentation and writing of this paper is poor and hard to understand. The problem in Sec. 2 is formulated in a very abstract way and never motivated clearly. Little explanation is given why this problem is interesting, why this problem is challenging, what are the open challenges, and what are the state of the art and what are their limitations.

  2. The same presentation issue also happens throughout other parts in the paper. This paper uses many terminologies that are never clearly explained or defined. There is not even a place to describe the main algorithm they proposed. Many theoretical results are stated with little explanations to provide deeper insights.

  3. The mathematical writing of this paper is also poor. Propositions 1 and 3 read like a very general vague description and don't even provide any meaningful mathematical statement.

Questions for authors
  1. Could the authors clearly motivate the problem and explain the challenges, state of the art, their limitation, and the novelty and contributions of this paper?

  2. Could the authors clearly define all the terminologies they used in this paper?

  3. Could the authors clearly restate Propositions 1 and 3?

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

The paper studies the following problem: Given several rankings of a universe of objects and a known numerical value for selecting each element (evaluation gain), the goal is to identify a ranker whose top-KK selections have the highest total value, or are within a specified tolerance of it, after restricting its ranking to a shared subset. The challenge is that this subset is only partially known, so the choice must hold for every subset consistent with the evidence. The paper treats each ranking as being produced by a model, so identifying the best ranker corresponds to identifying the best model. The paper also considers a weighted average over multiple such selections.

Some of the main technical contributions are as follows:

  1. The paper shows that certifying a winning model can require much less information than determining all models’ exact selections.

  2. They give an algorithm that computes the exact minimum and maximum score difference between two models given existing evidence. The main insight is that the rankings can be split into shared blocks at positions where the objects appearing so far are the same in both rankings. Only a block containing the top-KK cutoff can affect the difference. The algorithm checks feasible configurations of that block. Its running time is O(nG2b)O(nG2^b), where nn is the number of objects, GG is the number of groups with known membership counts, and bb is the largest block size. This is efficient when the blocks are small. They also give polynomial-time bounds that apply without assuming small blocks, though these may be less precise.

  3. The paper gives a heuristic for choosing which memberships to query based on unresolved model comparisons.

Critical strengths

None.

Critical weaknesses

W1. The paper is extremely poorly written. I had a hard time figuring out what problem it is even trying to solve. The introduction does little to explain the problem before moving into technical claims. Terminology is thrown around without enough context or intuition.

W2. The technical contributions also seem to lack meaningful depth, in my opinion. Several of the main results seem to formalize fairly simple observations.

Questions for authors

Please address W1 and W2.

Reviewer_RNH1OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies how much membership evidence is needed to 'certify' a model choice in offline comparison when the historical candidate set is incomplete. The central idea is that models share the same unknown membership state, so membership uncertainty partly cancels in their difference. The authors (1) prove a comparison can need zero new records while recovering all selections needs linearly many; (2) for single-query top-K evaluation, characterize the feasible contrast through a single shared 'boundary block', giving an exact algorithm with local exponential cost (Block) and a closed-form regret for adjacent swaps; (3) show that exact computation and minimal evidence acquisition are distinct problems; (4) give efficient, monotone regret outer bounds (Joint/Cutoff) for general model orders and multiple queries; and (5) propose a comparison-guided record acquisition policy, Contrast. Experiments: on A-share stocks, 7 models show 42 winner reversals across 132 pool-date comparisons, 23 with regret above 0.01; Cutoff certification repairs all 23 above-tolerance errors while more than half the memberships remain unknown on average; in a controlled width-2 reranking task, Block certifies 67/132 comparisons versus 5/132 for Cutoff at the same additional 25% record budget; on MovieLens, Contrast saves 53.1% of records versus Frontier at zero regret.

Critical strengths
  • The problem setting is new and practically motivated: changes in the candidate pool can reverse model winners with predictions and labels unchanged, and the paper quantifies this with 42 reversals across 132 stock comparisons.
  • The 'comparing is easier than recovering' view is clear, and the zero-versus-linear separation (Prop 1) gives an intuitive and rigorous motivation.
  • The single-query boundary-block characterization (Thm 2) is exact and attainable: every endpoint has an attaining membership completion, checked by exhaustive enumeration (360 endpoint pairs, error about 1e-16), a MILP comparison and independently rescored witness states.
  • Computation and evidence-search complexity are separated, with matching bounds (C*=1 versus D*=n/4).
  • The experiments separate interventions (distortion, certificate, acquisition policy, training budget) and use matched evidence prefixes to isolate each factor, which shows good experimental design awareness.
  • The paper honestly discloses several limits, such as Cutoff and Joint having equal cost on MovieLens, savings coming from the acquisition policy rather than the certificate, and Block's rapid decline with width.
Critical weaknesses
  • The exact results have narrow scope: single query only, shared block structure and small blocks (cost O(nG·2^b)). General orders and multiple queries get only outer bounds that need not be tight; the authors also admit that with several reachable blocks, coordinate possibilities do not correspond to one common state.
  • The strongest empirical result (Block 67 versus Cutoff 5) comes from an artificial 'Ridge base order plus LightGBM bucket reranking' setup built to satisfy the theoretical assumptions; at width 8 only 6/132 are certified. It is not shown that naturally trained models fall in this local regime.
  • In natural settings the gain from a tighter certificate is tiny: Cutoff saves only 0.43% (or 0.55%) of records over Joint on stocks, 0.19% on Hong Kong, and nothing on MovieLens. Whether the certificate contribution is meaningful in practice is doubtful.
  • The headline 53.1% saving comes from the heuristic Contrast acquisition policy, which has no optimality or approximation guarantee and is compared with weak baselines (fixed order, Frontier, Count-frontier). The MovieLens experiment has only 4 catalogs, 32 queries and 6 models, limiting external validity.
  • Key modeling assumptions are strong: one shared membership vector z across all models and queries, fixed gains and eligibility, predictions frozen under membership change, and evidence in the form of exact group counts or snapshot overlap. Availability of such evidence in practice, and robustness to its errors, are tested only through limited weakened-evidence checks.
  • The 'zero new records' case (Prop 1) is constructed for the separation; the paper does not say how frequent such cases are in real evaluations.
  • The 132 pool-date comparisons are strongly correlated across time and pools; there are no confidence intervals, significance tests or sensitivity analysis for near-tied models, so how many of the 42/132 reversals are substantive is unclear.
Questions for authors
  • For naturally trained model pairs without an artificially constrained reranking structure, what fraction satisfies the small-block condition (Appendix O.1)? What certification rate does Block achieve there, and how large is its improvement over Cutoff?
  • What are the confidence intervals for the 42/132 winner reversals once temporal correlation is accounted for? How many of them occur between near-tied models with gaps below 0.005?
  • Which components of Contrast produce the savings? Can it be compared with stronger baselines (uncertainty-based active sampling, greedy information gain, acquisition that directly minimizes the Joint upper bound)? Is there any near-optimality guarantee?
  • How robust is certification when the snapshot overlap or group counts are wrong or only available as intervals? Please provide a more systematic evaluation than removing overlap or relaxing to intervals.
  • How loose are the Joint/Cutoff outer bounds relative to exact regret for multiple queries and general orders? Beyond the small 72-family grid, can exact values be given on subsets of real data?
  • How often does 'zero-record certification' occur on real data? With the initial 25% evidence, what fraction of the 132 stock comparisons and the MovieLens catalogs is already certified?
  • How does Block's per-pair, per-query time behave for n above 4,096 and for growing block width?
Reviewer_55wYOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This manuscript studies the how much evidence is required to properly support conclusion regarding model comparisons in AI benchmark evaluations, in an offline setting which picks the model whose top-KK selection score the best, where the score depends on which candidates were in the candidate pool and the historical pool membership is only partially known. An evaluation query is associated with a subset of the reference catalogue as well as an integer rank cutoff, and a model selects the top models above the rank cutoff that are eligible and in the pool. The evaluation score of a given model with respect to a candidate pool is the weighted sum of the gain of identities it selects. The results showed that across the interventions (Table 2) on the fixed benchmarks, the winner is generally a function of the candidate pool and not just the models themselves and that comparing models requires less evidence than scoring them.

Critical strengths
  • The experimental setup is more or less intuitive and well-defined, and touches upon a useful topic in AI evaluation.
Critical weaknesses
  • While the research questions are well-motivated by real-world applications, the validation is not quite there yet: the most worrying issue is that the per-pool date winner may be a good instrument for measuring membership distortion but not for certifying the model choices.
Questions for authors
  • L134: what does mentioning NP-hardness really motivate?
  • More detail on the cost of evidence in Table 4 with different ϵ\epsilon values.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.