acceptodds
Under review as a conference paper at ICLR 2027

From Per-Class Summaries to Top- Decisions: Sharp Information Limits

Abstract

When deploying a classifier ahead of an expensive reranker or human expert, practitioners must choose a shortlist size that captures the true label while limiting downstream costs. Can this shortlist size be reliably chosen from standard evaluation reports containing top-1 accuracy and per-class score distributions? We show that these reports need not suffice: two evaluation sets can share identical top-1 accuracy and per-class summaries, yet yield substantially different top- coverages. This ambiguity arises because per-class summaries discard how scores across different classes co-occur on individual examples. To understand the fundamental limits of this information loss, we first analyze the idealized setting of true posterior probabilities. Even with ideal scores, the maximum coverage gap between report-compatible distributions is at top-2 and at top-3, converging to as both shortlist size and class count grow. We establish these sharp limits using dual certificates and matching constructive examples, which provide both optimistic and guaranteed shortlist bounds for any supplied report. For general uncalibrated classifiers, exact programs certify actual coverage and shortlist requirements. Across 150 benchmark reports, required shortlist sizes are uniquely determined at 90% target coverage, but 29 reports remain ambiguous at 95%—in one case swinging the required shortlist from two to five candidates. Adding joint cross-class statistics narrows this uncertainty, while a compact true-label rank histogram eliminates it entirely. Our results pinpoint when standard per-class summaries suffice for shortlist sizing and what additional statistics evaluators should report.

Primary area:
learning theory
Keywords:
model evaluation, top-(k) classification, partial identification, evaluation summaries, calibration, marginal distributions, shortlist decisions

Reviews

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

This paper focuses on a framework where a first classifier identifies a subset of candidate labels before using a larger model or human expert to consider this subset only afterwards. The authors remain in a specific setup where only the class-specific summary, top-1 accuracy are available. They show that two classifiers having identical top-1 accuracy and per class summaries can yield different top-k accuracy. Thus, they aim to obtain bounds on the top-k accuracy when both top-1 accuracy and each class marginal distribution are known. This bound then allows them to identify how many labels should be kept at a given quality (expressed using coverage, i.e., top-k accuracy) threshold. The authors first work under an idealized framework where the probabilities given by the classifier provide the exact probabilities of the true label. They also work in a more practical scenario without this assumption, where they instead rely on programming techniques to obtain the minimal value and maximal values of these bounds across the set of plausible joint distributions of probability scores and labels.

Critical strengths
  • The paper introduces theoretical bounds that are, according to the authors and to the best of my knowledge, novel
  • The paper aims to use these bounds to provide budget guarantees
Critical weaknesses
  • [W1] The practical relevance of the problem is insufficiently justified. As noted by the authors, performing a new evaluation report containing a true-label rank histogram would determine every top-k coverage and shortlist budget exactly.
  • [W2] The paper only considers a mix of toy datasets with a small number of classes. They do not evaluate their certification on tasks with large label spaces, where shortlist selection would be more useful.
  • [W3] The paper considers coarse probability score grids. The authors considered 5 neighbors, 5 votes (line 369) or rounded the probability scores to multiples of 1 / 5 (line 464) in the main body of the paper. The method becomes overly expensive when trying to reach finer evaluation. For instance, none of the tested settings with N=10N=10 and M>5M>5 managed to work according to their experiments (line 465, table 18). This constrains the use of their certificates in practice.
  • [W4] The top-1 accuracy is high in this work. I have concerns about the interest of the paper considering the tradeoff between the small increases of coverage induced by adding a new label with respect with the associated cost to be considered by the expert classifier. The work would have benefited from having a thorough analysis of the time (time to optimize + time to process an additional label) and resources needed to obtain a specific top-k coverage on each dataset.
  • [W5] The writing should be improved.
    • A) The paper does not sufficiently guide the reader through the main results. The progression between the paragraph “Pooled marginals and what the report fixes” and the start of section 4.1 would gain from clearer explanations and less reliance on supplementary material. There is not enough explanation on how to use ψ\psi or eq. 11 to build certificates without exploring the supplementary material. The connection between eq13 and eq14 could also be made clearer. Some concepts are not clearly introduced. For instance, the paper talks about columns (line 81) or row links (178) without clearly explaining which table or row/column it is talking about. Moreover, the paper sends the reader very often to the supplementary material to understand derivations, but it does not necessarily help the understanding as its structure is not linear and it can require navigating across many different sections. For example, section A relies upon theorems in section B whose proof requires section C/D.
    • B) The paper relies on a large number of notations that are not thoroughly introduced, can take different meanings across the manuscript, and make the argument difficult to follow. For instance, while the Law operator is used in eq.2, its meaning only comes at line 195; nothing is explained about ϕk\phi_k(eq.13) besides stating it describes a “1D potential determined by the report”(line 292) and providing its expression, in the main body of the paper; the meaning of R2HR_2^H and R2LR_2^L (eq 14) has to be inferred by the reader; and MM (line 464) is unclear. MM especially has different meanings: it represents the score-grid denominator in line 464 and the number of samples in line 172. ss is also used with different meanings: it is a probability score in eq. 4 or eq. 18 but represents the summary in most of the paper (line 205)
    • C) The paper is not self-contained. As identified with different examples above, the main text relies too heavily on the supplementary material to understand the argument. Moreover, line 149-150 directly sends the reader to the supplementary material to assess a statement that the authors claim to show. There are references to tables from the supplementary material in lines 377-378 and 453.
  • [W6] Some results are not explained thoroughly. For instance, the authors do not explain the decrease in ambiguous reports identified in Figure 2
Questions for authors
  • Considering you are only dealing with at most 10 possible recommended labels in the experiments of this work, why not directly give them all to the expert classifier ? Would this be really that expensive in time and resources ?
  • The paper focuses on a specific framework where only top-1 accuracy and summaries of each individual class are available. I have never encountered such a framework, nor my colleagues. Which scientific community relies solely on these kinds of “reports” ? Why not change the evaluation protocol directly ?
  • In Fig.1, could you explain why the part between the k=1 and k=2 is filled with colors, while your work should only consider $ k\geq 2$? I was also wondering why you got rid of the “7” and “9” in the x-axis.
  • Can you explain what is the difference between the top-k coverage and the top-k accuracy in your work ?
  • Can you explain the difference between SS(eq1), SiS_i(eq 2), ss(line 165), sis_i(line 165) and ss(line 205). I do get that one is used to refer to summaries and the others for probability scores but I still am not sure about the notations in eq 18 ?
  • Can you explain why you used x as dummy variables in different variables such as line 201, eq 11 ? Similarly to your use of SS and ss for the scores, I was expecting to use XX and xx for the ground-truth label as in line 164. However, in the integrals, xx should take values across [0, 1]. Would it be more consistent to use ss instead there ?
  • Are you stating that the top-k coverage is the Bayes risk in line 191 ?
2 comments

Thank you for the detailed reading. The revised PDF addresses the presentation points, later version would further refine it.

W1: Who uses such reports? Why not change the protocol? We agree the protocol should change. When list sizing is expected, evaluators should report the true-label rank histogram (NN numbers). The revision says so, and no longer suggests that any community relies only on these reports (§1, §6). Our contribution is to show exactly what is lost otherwise, and which statistics avoid the loss.

W2: Large label spaces. The theory holds for any number of classes. Our exact experiments cover at most ten classes, which we now state (§6). The simple bounds discussed with Reviewer nGYN work at any size.

W3: Coarse scores. We added an experiment on the original, unrounded RepVGG scores. It will be reported in later revision (see the general response).

W4: High accuracy; why not pass all labels? For ten classes, passing all labels is feasible, and the paper says so. We have no timing study and do not claim time savings. The revision adds a simple accounting instead (§5; App. I, Table 17), assuming second-stage cost grows with list size:

  • at a 99% target, sending the guaranteed list size on the 85 ambiguous reports processes 18% more candidates than the test sets needed (up to 2.5 times as many);
  • sending the smallest possible size misses the target on 70 of those 85 test sets.

High top-1 accuracy moves the problem to strict targets; it does not remove it.

W5: Writing. Fixed in the revision:

  • the abstract defines its terms, and §1 has a formal problem statement starting on page 1;
  • short explanations at the first use of technical terms such as "laws" (probability distributions); a fuller plain-language pass will come in the final version;
  • a new Table 1 relates the report to familiar metrics (ROC, precision–recall and reliability diagrams), with a plain one-vs-rest explanation in §1;
  • the evaluation table and "row links" are defined (§3);
  • Law(⋅)\mathrm{Law}(\cdot) and the notation are defined (§3);
  • R2HR_2^{\mathsf H} and R2LR_2^{\mathsf L} are defined (§4);
  • the sentence about ϕk\phi_k is corrected (§4);
  • a three-step "Using a certificate" paragraph is added (§4);
  • the calibration example is summarized in the main text (§2).

Renaming the report symbol ss touches many appendix proofs, so we will do it in the final version.

W6: The decrease in Fig. 2. Near 100%, every compatible batch needs the same larger list, so the ambiguity disappears. The caption now explains this.

Questions.

  • Fig. 1. Coverage is defined only at whole numbers kk, and the shading was a plotting artifact. The revised figure shows separate bars at every kk from 1 to 10.
  • Coverage vs. accuracy. They are the same quantity here; this is now stated in §3.
  • Notation. SS is the random score vector and ss a value of it. The xx in the integrals was a score value; it is now written uu.
  • Bayes risk. You are right: RkR_k is the Bayes-optimal coverage, and the risk would be 1−Rk1-R_k. Fixed.

I appreciate the efforts the authors have made to improve the paper. However, despite these efforts, the paper remains difficult to read at places. For instance lines 314-328 partly describe a mathematical demonstration whose presence does not bring much besides confusion. Moreover, the paper has many statements or links to tables that are in the appendix. This keeps breaking the reading and introduces questions that may not be necessary to understand the paper. All these writing choices make the paper more complicated to read.

I would also advise the authors to take into consideration if it is possible to decompose your 72-page-long submissions into different articles to gain clarity.

On top of that I still think the paper would gain from more realistic experiments. A first step would be to show that, on top of having the theory that is working on any number of classes, we can still apply it on datasets with more than 10 classes.

Therefore, I maintain my rating.

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

The paper investigates whether complete classwise score/label marginals and top-1 accuracy determine top-kk coverage and shortlist budgets. For posterior probabilities, it derives sharp ambiguity constants E2=1/5E_2=1/5, E3=17/76E_3=17/76, and Ek→1/4E_k\to1/4, using dual certificates and matching constructions. It characterizes attainable coverage intervals and budget extrema, then validates them on 150 finite-resolution classifier reports and a rounded neural classifier.

Critical strengths
  1. The constants and matching constructions are nontrivial because they simultaneously preserve simplex normalization, classwise marginals, and top-1 accuracy. These results extend beyond existing constrained-coupling theory.
  2. The paper establishes attainable coverage and budget extrema, supported by exact certificates and integer-batch witnesses. The careful distinction between posterior and arbitrary-score guarantees strengthens its soundness.
Critical weaknesses
  1. Proposition G.1 shows that exact empirical marginals can reconstruct generic batches, so removing row identifiers need not lose information. The benchmarks instead use five-vote scores, where all ambiguity for k≥5k\ge5 arises from zero-score true labels and tie ordering. Neural-score rounding changes the actual 99% budget from 3 to 7 before producing a certified range of 6–9. Thus, the experiments do not establish the information loss caused by compressing reports while preserving the original classifier. This limits the applicability of the empirical findings beyond the studied discrete-score settings.

  2. Partial-identification evaluation and coupling optimization have precedents, notably Polo et al. [1], while rank-based fixed-kk selection appears in Angelopoulos et al. [2]. These do not subsume the sharp constants but narrow the novelty of the operational framework. Furthermore, the reported 51%–85% interval reduction uses only the weak baseline [A1,1][A_1,1], although the same report yields Ak≥max⁡A1,Pr⁡(SY>1k+1).A_k \ge \max \\{A_1,\Pr (S_Y>\frac1{k+1} )\\} . The results therefore do not isolate the additional decision value of full coupling optimization over simpler report-derived bounds.

[1] Polo et al. Weak Supervision Performance Evaluation via Partial Identification. NeurIPS, 2024.

[2] Angelopoulos et al. Uncertainty Sets for Image Classifiers using Conformal Prediction. ICLR, 2021.

Questions for authors
  1. Under what realistic report-handoff conditions is the report-compatible set an appropriate representation of uncertainty, given generic empirical reconstruction and potential model-specific constraints?
  2. Does full coupling optimization change certified shortlist budgets relative to inexpensive bounds from the same report? How do posterior-report certificates compare with applicable entropy-based list-error bounds?
2 comments

Thanks for your constructive and technical comments. They led to several concrete changes.

Reconstruction (Prop. G.1), ties, rounding. We agree with all three points, and the revision states each one:

  • exact dense scores can reveal which scores belong to the same example (G.1);
  • with five-vote scores, ambiguity at k≥5k\ge5 comes only from zero-score true labels and tie order (§5);
  • the rounded experiment certifies the rounded classifier, not the original (§5).

To test the original classifier, we ran a new experiment on unrounded RepVGG scores, binning only the report (see the general response). The 99% budget can be 2 or 4. Consistent with G.1, the range shrinks as the bins get finer.

Q1: When is the compatible set the right model? When the recipient has one of these:

  • a population-level report;
  • a coarsened one (bins, thresholds, histograms, or aggregates across datasets);
  • finite-resolution scores.

The compatible set describes what the recipient can conclude from the report alone. Extra known constraints, for example about the model, only shrink the set, so our intervals remain valid outer bounds.

Weak baseline. Thank you: your bound is valid and uses only the report. We added it (§5; App. I, Table 16). Exact optimization still certifies a smaller budget in 54 of 150 reports at 95% and 34 at 99% (none at 90%), saving up to 3 candidates.

Q2: Entropy-based bounds. The applicable ones are list-Fano bounds, as in Sason & Verdú 2018 and Béguinot et al. 2026. They give only an upper bound, and they use a single entropy value. On the same information, our interval was tighter in all 39 cases we tested.

We can also show why entropy is the wrong summary here (new result, proof would be delivered in our next upload). One entropy or log-loss value plus top-1 can leave top-2 coverage almost as uncertain as top-1 alone. By contrast, the full distribution of the true-class probability, which our report contains, limits the gap to 1/5; that is the paper's main theorem.

Prior work. Added (§2).

  • Polo et al. (2024) bound metrics by optimizing over couplings of two marginals. We do not claim partial identification as new; our contribution is the sharp constants for NN simplex-constrained marginals with a top-1 constraint.
  • Angelopoulos et al. (2021) choose a fixed kk from true-label ranks. That is the remedy we recommend when labelled data are available.

The second revision added the proof promised under Q2. Tt's now in App. M.1 (Theorem M.3, stated for every list size kk). It also gives explicit pairs with equal top-1 accuracy and equal log-loss whose top-2 coverage differs by 0.24 at 4 classes and 0.40 at 4,096 classes. The contrast is between summaries, not between one number and a whole distribution: by Remark M.4(c), the single number E∑iϕ2(Qi)\mathbb{E}\sum_i\phi_2(Q_i) reported with top-1 accuracy already limits the top-2 gap to 1/51/5. Log-loss averages a function of the scores that is not matched to a fixed-size list.

Correction to our earlier reply. Previously we wrote that our interval was tighter in all 39 cases. After re-checking, two things were wrong.

  1. There are 33 report/list-size settings, not 39: three were counted three times.
  2. Our entropy baseline used a weak lower bound. With the best lower bound that uses only the entropy (App. M.1), our certificates on their own are not tighter in 4 of the 33 settings. Because our report determines the log-loss, the report-based interval can use the entropy bounds as well. It is then strictly narrower than the entropy-and-top-1 interval in 27 settings and identical in 6 (Table 24). Theorem M.3 demonstrates the general statement.

Your bound on the unrounded RepVGG scores is reported in App. K.1: it certifies 3 candidates at 95% (the test set needs 2) and certifies 99% only with all ten classes.

Reviewer_nGYNOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper asks whether top-1 accuracy plus even very rich per-class score/label summaries are sufficient to determine the shortlist size needed to achieve a desired top-k coverage, and shows that they are not because these summaries discard cross-class score co-occurrence information.

Its main theoretical contribution is a set of sharp information limits for posterior/vector-calibrated scores: compatible reports can differ in top-2 coverage by exactly up to 1/5 and top-3 coverage by 17/76, with worst-case ambiguity approaching 1/4 for larger k, together with report-specific optimization programs that translate coverage ambiguity into exact optimistic and certified shortlist budgets.

Across 150 finite-resolution benchmark reports, shortlist budgets are uniquely determined at 90% coverage but ambiguous for 29 reports at 95% and 85 at 99%, demonstrating that the missing information can materially affect high-coverage deployment decisions.

Critical strengths

1. Strong and sharp theoretical characterization of information lost by per-class reporting. The paper goes substantially beyond showing a counterexample: it characterizes worst-case ambiguity when cross-class score associations are removed, proving sharp top-2 and top-3 coverage gaps of 1/5 and 17/76, respectively, and showing that the general-rank ambiguity approaches 1/4. The matching constructions, separable dual certificates, and extension showing nonidentification even when lower-rank accuracies are retained make this a substantive theoretical contribution rather than an isolated observation. This is consequential to my assessment because it establishes a fundamental information limit for a natural evaluation-summary format.

2. The paper successfully connects the theoretical ambiguity to an actionable downstream decision. Rather than stopping at coverage nonidentification, the paper defines optimistic and certified shortlist budgets and characterizes exactly when uncertainty in top-k coverage changes the deployment decision. The benchmark evaluation shows that this distinction matters: none of the 150 reports are decision-ambiguous at 90% coverage, whereas 29 are ambiguous at 95% and 85 at 99%, with budget gaps reaching five candidates. The follow-up analysis further shows that a compact true-label rank histogram eliminates the ambiguity entirely. This makes the theoretical information-loss result operationally interpretable and gives evaluators a concrete recommendation about what additional information to retain.

Critical weaknesses

1. The practical importance of the assumed reporting boundary is not fully established. The central question assumes that a model recipient receives top-1 accuracy and complete per-class score/label summaries but not top-k metrics, true-label ranks, or individual predictions. The paper explicitly acknowledges that it does not claim existing routing or retrieval systems commonly use this exact export policy. Moreover, if shortlist sizing is known to be a downstream requirement, directly reporting the top-k coverage curve or the true-label rank histogram solves the problem very cheaply. Thus, while the information-limit result is theoretically strong, I am less convinced that the particular missing-information scenario is common enough to make the practical impact as broad as the paper’s extensive treatment might suggest.

2. Exact certification currently depends strongly on finite/coarse score support and does not yet scale to realistic dense classifier outputs. The main 150-report experiments intentionally use five-tree or five-neighbor scores, which restrict scores to {0, 1/5, ..., 1} and make exhaustive certification tractable. In the neural experiment, RepVGG-A0 softmax outputs must be rounded to denominator-five scores, materially changing the evaluated ranking behavior: for example, top-2 accuracy drops from 98.35% to 96.43%. At N=10, increasing the denominator to 20 yields over 90 million admissible states, beyond the implementation limit, and dense unrounded scores remain unsupported. This is consequential because the exact practical methodology is currently most tractable precisely in settings with unusually coarse score outputs, while modern neural classifiers commonly produce dense continuous scores.

Questions for authors
  1. Clarification: Can the authors provide stronger evidence that the reporting regime studied in the paper arises in realistic model handoff or evaluation workflows where shortlist selection is a downstream requirement? In particular, are there representative APIs, benchmark formats, or production evaluation pipelines that expose rich per-class diagnostics while omitting top-k coverage or true-label rank information? Demonstrating that this information boundary occurs naturally, rather than primarily as a constructed reporting scenario, would materially strengthen my assessment of the paper’s practical significance.

  2. Clarification: How do the authors envision applying the report-specific certification framework to modern classifiers with dense, high-precision score vectors? The RepVGG experiment suggests that discretization can itself substantially change the relevant top-k behavior, while increasing score resolution rapidly makes exhaustive state enumeration infeasible. Is there a relaxation, approximation, or alternative optimization formulation that can provide useful certified bounds directly for dense scores without altering the ranking rule? A credible path toward this regime would materially strengthen my assessment of the practical contribution.

Suggestion for future work, not required for the current assessment: It would be valuable to develop scalable approximate certificates with explicit approximation error and to study reporting formats that optimally trade storage/privacy against preservation of multiple downstream decisions.

1 comment

Thank you for the positive review.

Q1: Is the reporting regime realistic? Only in part, and the revised paper no longer claims more (as reported in the general response).

Evaluation outputs with per-class diagnostics and no top-k metric do exist among the kinds you list:

  • MLflow's default multiclass evaluation logs accuracy, F1, log-loss, per-class metrics and ROC/PR curves, but no top-k metric.
  • The ISIC 2018 skin-lesion leaderboard publishes per-class ROC curves, threshold metrics, AUC and balanced accuracy for every entry, but no top-k.

What we have not found is a documented workflow in which someone sizes a shortlist from such an output alone.

Where list sizes are planned in advance, practitioners already record ranks. TFMA reports top-3, and keyboard suggestion is evaluated by top-3 recall. That is exactly the remedy we recommend. Our contribution is to measure what is lost when the recorded statistics don't match the decision.

Q2: Dense scores without changing the ranking.

  1. New experiment. We used the original, unrounded RepVGG scores (reported in the general response). Identical binned reports allow a 99% budget of either 2 or 4.
  2. Bounds that already work at any resolution.
    • Reviewer tfBr's bound Ak≥max⁡{A1,Pr⁡(SX>1/(k+1))}A_k \ge \max\{A_1, \Pr(S_X > 1/(k+1))\} certifies a 95% budget of 3 for RepVGG, against a true value of 2, but it cannot certify 99%.
    • Our one-dimensional certificates also work at any resolution when scores are calibrated.
  3. A sound route to exact bounds. Bin the report but keep the original ranking, treating the order inside a bin as unknown. This gives valid bounds for the original classifier. An efficient implementation for fine bins is future work.

We agree with your suggestion about approximate certificates and storage/privacy trade-offs, and will discuss it in the final version.

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

The paper studies shortlist sizing from an evaluation report: given only top 1 accuracy and per class score/label distributions, pick the smallest kk whose top kk coverage meets a target τ\tau. Such a report omits which classes score high together on the same example, so it identifies neither top kk coverage nor the required kk. For calibrated posteriors the paper proves sharp limits: identical reports allow top 2 coverages differing by up to 1/51/5 and top 3 by 17/7617/76, approaching 1/41/4 for large kk and class count. For finite support uncalibrated scores, exact linear programs give the attainable coverage interval and the optimistic and certified shortlist sizes. On 150 benchmark reports with five vote scores, the decision is unique at a 90% target but ambiguous for 29 reports at 95% and 85 at 99%; a true label rank histogram resolves it.

Critical strengths
  • The question is natural and deserves a formal treatment: a recipient of an evaluation report (top 1 accuracy plus complete per class score/label distributions) must size a fixed size shortlist for a downstream stage

  • The paper combines theory and experiments. Theoretically it gives sharp dimension uniform constants with matching constructions and report specific interval certificates. Empirically it evaluates a systematic cohort of 150 benchmark reports (5 datasets, 3 model families, 10 splits) with exact rational primal/dual certificates and a reproducibility package.

Critical weaknesses
  • Presentation. The abstract uses "coverage gap", "report compatible distributions" and "per class summaries" without defining them, and the body switches to "shortlist budget" (first used on page 1) for what the abstract calls "shortlist size".

  • Positioning of the mathematical core. The central object is the range of E[sum of the k largest coordinates]\mathbb{E}[\text{sum of the } k \text{ largest coordinates}] over joint laws with prescribed one dimensional marginals and a prescribed expected maximum. This is a classical type of extremal problem.

  • Practical consequences are not demonstrated. The paper quantifies information loss (coverage width) and the resulting budget gap in candidates, but "workload" is only kk itself: there is no second stage cost model, no second stage accuracy, and no end to end system (Section I states that neither second stage runtime nor final accuracy is measured).

Questions for authors
  • could you formally define the studied problem in the abstract or on page 1 and state whether it has an established name?

  • Can the authors provide any evidence, even a stylized cost model, that the observed budget gaps translate into material downstream cost or accuracy loss?

1 comment

Thank you for the review. Each of your three points led to a change in the revised manuscript.

Presentation, and Q1: define the problem; does it have a name?

  • Abstract. It now defines its terms. The shortlist budget is the smallest kk whose top-kk coverage reaches a target. Per-class summaries are, for each class, the joint distribution of its score and whether it is the true label. "Report-compatible distributions" is now "distributions consistent with the same report". "Coverage gap" is replaced by a plain statement of what can differ. The abstract and the body now both say "shortlist budget".
  • Formal statement (§1, starting on page 1). The report is ρ=(N,(γi)i=1N,a1)\rho=(N,(\gamma_i)_{i=1}^N,a_1): top-1 accuracy a1a_1 and, for each class ii, the distribution γi\gamma_i of the pair (score SiS_i, indicator of X=iX=i). We determine the range of Ak=Pr⁡{X∈Topk(S)}A_k=\Pr\{X\in\mathrm{Top}_k(S)\}, and of the budget min⁡{k:Ak≥τ}\min\{k: A_k\ge\tau\}, over all joint distributions of (S,X)(S,X) that produce ρ\rho.
  • Name. To our best knowledge, no established name for this shortlist question exists before. Its type is standard: partial identification (Manski 2003), that is, an extremal problem over joint distributions with prescribed marginals (Kellerer 1984; Rüschendorf 2013). §1 now says so.

Positioning of the mathematical core. We agree the problem belongs to a classical type, and we do not claim the type new. §2 places our work next to complete mixability, rank-marginal bounds and duality for marginal problems. Your description is accurate with one addition, which is what separates this problem from the classical ones. Three things are specific to our setting:

  • each example's scores sum to one. Classical rank-marginal relaxations drop this constraint, and on our two worked reports they then give lower bounds that are too low (App. G.3);
  • top-1 accuracy is fixed as an additional linear constraint;
  • we solve this case exactly: the constants 1/51/5, 17/7617/76 and 1/41/4, with matching constructions, for any number of classes.

Practical consequences, and Q2: a stylized cost model. We have no deployed second stage, and the paper says so. We added the accounting you suggest (§5; App. I, Table 17). It assumes that second-stage cost is proportional to list size, and that the second stage must choose from the list, so end-to-end accuracy cannot exceed coverage. A recipient of an ambiguous report then has two options:

Option95% target (29 ambiguous reports)99% target (85 ambiguous reports)
Send the guaranteed size: candidates processed, relative to what the test set needed1.73× (up to 2×)1.18× (up to 2.5×)
Send the smallest possible size: test sets that miss the target5 of 2970 of 85
Largest miss on the actual test set1.7 points2.3 points
Largest miss on any test set consistent with the report3.3 points3.8 points

At 99%, a 3.8-point miss is a miss rate 4.8 times the 1% the target allows, and each missed label is an error the second stage cannot repair. A true-label rank histogram removes both costs. This is an accounting on benchmarks with at most ten classes, not a measured system.

Comments on the paper

3 comments
AuthorsOpenReview ↗

General response: revised manuscript, summary of changes and plan for later updates

We thank all reviewers for their careful assessment and comment. We have uploaded a revised manuscript.

The shared concern: is the scenario realistic? We agree it was overstated. "top-1 accuracy plus per-class metrics, without ranks" is not a common reporting format, and we leaned on it too heavily to motivate the mathematical result. The paper now asks a broader question: which reported statistics are enough for which list decisions?

Per-class reports fully determine the coverage and size of score-threshold sets. They fall short only for fixed-size top-kk lists, and our results measure exactly how much they miss. When list sizing is expected (like retrieval models), evaluators should simply report the true-label rank histogram (NN numbers). The revision says so.

What changed in the manuscript:

  • the framing above (§1, §3, §6);
  • an abstract that defines its terms, and a formal problem statement starting on page 1 (Reviewer 6cec);
  • a stronger baseline that uses only the report, suggested by Reviewer tfBr (§5; App. I, Table 16);
  • a stylized cost accounting of the budget gaps, requested by Reviewers 6cec and xWmd (§5; App. I, Table 17);
  • related work: Polo et al. 2024, Angelopoulos et al. 2021, Béguinot et al. 2026 (§2); Manski 2003 and Rüschendorf 2013 for the problem class (§1);
  • a new Table 1 showing how the report relates to common metrics: per-class ROC, precision–recall and reliability diagrams are in it; top-k accuracy, the confusion matrix and confidence histograms are not (§1, §3);
  • the clarity fixes requested by Reviewer xWmd: defined terms and notation, a worked example of using a certificate (§4), and clearer Figures 1–2;
  • short plain-language explanations for important but unintuitive terms. We are simplifying the terminology further and will include this in a later revision.

New experiment on unrounded scores (update in progress, to be added in our next upload). We used the original RepVGG-A0 CIFAR-10 outputs with no rounding, and reweighted the 10,000 test images (no weight more than doubled). Every per-class 50-bin histogram of scores and labels stays exactly the same, and so does top-1 accuracy.

  • Under these identical reports, the smallest list reaching 99% coverage can be 2 or 4; the test set itself needs 3.
  • At 95% coverage, the budget never changed.

A second revision, with updated supplement, is uploaded. They add the two items mentioned in our first response. New contents are mainly in supplementary, the main text changes only by three sentences that point to them (§2, §3, §5).

1. Unrounded scores (App. K.1, Table 23). We described this experiment the first general response, now the full protocol updated.

  • The classifier and its ranking are untouched, only the report is binned (50 equal-width bins per class).
  • Two reweightings of the 10k test images, with no weight more than doubled, have exactly the same binned report and top-1 accuracy as the test set. They need 2 and 4 candidates at 99% coverage; the test set needs 3.
  • The reweightings are large: in each, about 47% of the images get weight zero (total-variation distance 0.475 from the test set). They show that the report does not fix the list size; they are not a model of natural distribution shift.
  • At 95%, all 72 reweightings we checked need 2 candidates; we do not show this for every law with the same report.
  • The range narrows as the bins get finer, and widens if larger reweightings are allowed (Table 23).

The appendix also states that 4 is reached but not shown to be the largest possible size. The 72 weight vectors and an exact checker are in the supplement.

2. One scalar summary (App. M.1, Theorem M.3). Requested by Reviewer tfBr. For posterior (full-vector calibrated) scores, suppose the report is replaced by top-1 accuracy and one number, and consider the worst-case top-kk gap.

  • With the Brier score (or the mean true-class probability), the gap is exactly the same as with top-1 accuracy alone, for every number of classes.
  • With log-loss (equivalently conditional entropy or, at a uniform prior, mutual information), it is strictly smaller for each number of classes, but it tends to the same value as the number of classes grows: 1/21/2 for top-2.
  • With our report, the top-2 gap is at most 1/51/5, the smallest bound that holds for every number of classes.

We're still working on language refinement and replacing symbols. They will come in the final version.

We would be glad to hear whether these additions address your concerns, and we are happy to answer any remaining questions before the discussion closes.

We have uploaded a third revision and it should, if no new problems, be the final revision. It contains the items our earlier comments mentioned.

  • Notation (Reviewer xWmd). The posterior summary (N,ξ,r)(N,\boldsymbol\xi,r) is now written ρˉ\bar\rho instead of ss, so ss only denotes a score value. §3 notes that, for posterior scores, ρˉ\bar\rho is equivalent to the report ρ\rho.
  • Plainer wording in the main text (Reviewer xWmd; general response). "Law" is now "distribution", "compatible" is "consistent with the report", "identified" is "determined", and "rank kk" is "list size kk". Figures 1–2 use the same words. Considering workload, the appendix keeps the formal terms with the Appendix Navigation maps one to the other. Theorem statements are unchanged.
  • Framing (all reviewers). The abstract, introduction and conclusion no longer present the classifier as the first stage of a pipeline. They start from list-based uses in general, and the conclusion opens with the contrast from our general response: per-class reports determine every threshold set but can leave fixed-size top-kk coverage undetermined. The stylized second-stage cost accounting in §5 is unchanged.
  • Approximate certificates and compact reports (Reviewer nGYN). New App. K.2, with a pointer in §6. It collects what the paper already shows. For posterior scores, dual certificates give valid bounds at any score resolution. For top-2, Theorem Q.1 shows that errors δ\delta in top-1 accuracy and ε\varepsilon (one-Wasserstein) in the true-class score distribution move each end of the certificate interval by at most 25δ+85ε\tfrac25\delta+\tfrac85\varepsilon. Exact dense reports can reveal individual rows (Prop. G.1), while coarser bins widen the coverage ranges (App. K.1). Which formats serve several decisions at a given storage or privacy level is left open.

Thank you again for your reviews. We are happy to clarify anything before the discussion closes.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.