acceptodds
Under review as a conference paper at ICLR 2027

Certify or Abstain: Auditing Thresholded Decisions Under Dependence

10 views

Abstract

Decisions to raise an alarm, withhold an answer, or refer a case for human review are commonly made by comparing a score against a calibrated cutoff. Claims about the resulting population operating rate are typically assessed under independence, although evaluation units may share a patient, time series, or prompt. We formulate a certify-or-abstain audit that identifies the independence conditions required for valid certification. Under -wise independence, symmetrisation reduces the analysis of any procedure to a randomised rule based on the total count. For each null rate, its maximal certification probability is a discrete moment problem. The corresponding primal and dual solutions yield exact rational certificates of feasibility and impossibility. This formulation gives exact minimum sample requirements for randomised rules, certified deterministic gates, and a scaling law across independence orders. For independent clusters, we characterise a strong criterion with unrestricted intracluster dependence and give finite-sample moment and Bernstein audits when average intracluster correlation is bounded. The -wise hierarchy is used as a conditional sensitivity analysis rather than as a fitted model of positive intracluster dependence. Applications to clinical referral, spacecraft telemetry, and language model reliability demonstrate how the framework separates conclusions warranted by the sampling design from those that rely on unjustified independence at the observation level.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
calibration, uncertainty quantification, distribution-free inference, finite-sample guarantees, selective prediction, equivalence testing, anomaly detection

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_kDRGOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
2(+1)
Read review
Paper summary

The paper studies the statistical validity of certifying threshold-based decisions when evaluation observations are not fully independent. The authors consider two dependence structures: (r)-wise independence and independent clusters with potentially dependent observations. Using symmetrisation and discrete moment problems, they derive finite-sample certification procedures, exact sample-complexity results, and primal-dual certificates of validity or impossibility.

Critical strengths

The paper addresses a fundamental weakness of many ML evaluation protocols: treating correlated outcomes as independent observations and consequently overstating the statistical evidence supporting performance claims.

The experiments demonstrate that a large number of observations does not necessarily imply a large effective evaluation sample. The LLM example, with 9,000 generations from only 180 prompts, is particularly relevant to current evaluation practices.

Critical weaknesses

1/ there is a huge litterature in the statistical community about assumptions that weaken independence. None is studied here.

2/. The results rely heavily on common Bernoulli marginals and specific independence assumptions across clusters. Heterogeneous populations, unequal cluster sizes, adaptive evaluation designs, and dependence across clusters are important in practice but are not fully covered by the proposed guarantees.

3/T he theoretical analysis is compelling, but (r)-wise independence is difficult to justify empirically. In realistic applications, dependence is generally induced by shared latent factors, prompts, patients, or temporal structure. The paper acknowledges this limitation, but it considerably reduces the direct operational relevance of the central hierarchy.

Questions for authors

1/ How should practitioners justify an independence order?

2/Why optimise nominal retention under full independence?

3/What is the precise boundary of theoretical novelty? Since moment-constrained minimax tests, polynomial duality, and limited-independence concentration bounds are established, could the authors more clearly identify which mathematical results are genuinely new and which follow from adaptations of known techniques?

1 comment

Thank you for the review and for recognising that the paper addresses a fundamental weakness of many ML evaluation protocols. Your questions helped us sharpen the paper, and one of them led to a new result.

Question 1:

How should practitioners justify an independence order?

Answer: In practice, the guarantees come from the cluster audits of Propositions 2 and 3. These only ask that clusters, such as patients or prompts, are independent of each other, which is a matter of how the evaluation was designed. Within a cluster, the dependence can be anything. Therefore, a practitioner does not have to argue for a particular independence order. An order can be justified directly when units are selected with a k-wise independent hash (Carter & Wegman, 1979), as described in the introduction and Section 5, because the outcomes are then k-wise independent by construction. The hierarchy of orders plays a different role, as a sensitivity analysis. By Lemma 1, the worst case at each order is a hidden common factor that matches independence in its first r moments, and the robustness order tells us how many of these moments a conclusion actually depends on. We will make this clearer in the introduction.

Question 2:

Why optimise nominal retention under full independence?

Answer: Thank you for this question. It made the paper stronger. We asked for validity in the worst case because that is what a certificate promises. Retention is different. It describes how useful the audit is when the system does meet its target, so we first measured it under the design the evaluator actually intends to use, which also gives every independence order the same benchmark and makes their sample sizes comparable. Your question led us to go one step further and certify the sample sizes when retention is also required in the worst case. As the table shows, this costs at most 13% more units. For clustered designs, Proposition 2 already asks for retention under every cluster law.

Retention requirementindependent4-wise3-wisepairwise
nominal (Table 1)9361,5187,9588,173
worst case (new)9361,7168,3238,590

Question 3:

What is the precise boundary of theoretical novelty? Since moment-constrained minimax tests, polynomial duality, and limited-independence concentration bounds are established, could the authors more clearly identify which mathematical results are genuinely new and which follow from adaptations of known techniques?

Answer: The novelty lies in the problem and its exact solution. We pose certification under limited independence as a test design problem over a continuum of null rates and solve it exactly. This yields exact minimum sample sizes with matching rational certificates in both directions (Theorems 1 and 2), the scaling law in α, whose lower bound holds for every procedure (Proposition 4), the fact that odd orders help only through the range of the count (Theorem 3), and the exact characterisation of clustered designs (Proposition 2), which pairs a lower bound from perfectly dependent clusters with a one unit per cluster design. These results are new. They build on established tools, such as moment problem duality (Prékopa, 1990), moment constrained minimax tests (Magesh et al., 2023) and tail bounds under limited independence (Schmidt et al., 1995). Those tools bound the tail of a statistic chosen in advance, whereas we use them to design the test itself. The introduction and Section 6 draw this distinction, and we will sharpen it in the list of contributions and extend the comparison in Section 6 with other ways of weakening independence, such as mixing and association.

Every result is proved in the appendix, and every exact claim can be checked with the verifier we released. If any step still raises a concern, we would be glad to go through it.

References

Carter, J. L. and Wegman, M. N. (1979). Universal classes of hash functions. Journal of Computer and System Sciences, 18(2), 143–154.

Magesh, A., Sun, Z., Veeravalli, V. V. and Zou, S. (2023). Robust hypothesis testing with moment constrained uncertainty sets. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP).

Prékopa, A. (1990). The discrete moment problem and linear programming. Discrete Applied Mathematics, 27(3), 235–254.

Schmidt, J. P., Siegel, A. and Srinivasan, A. (1995). Chernoff–Hoeffding bounds for applications with limited independence. SIAM Journal on Discrete Mathematics, 8(2), 223–250.

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

This paper studies how to verify whether the population event rate under a fixed-threshold decision rule falls within a pre-specified acceptable range when audit samples may exhibit dependency. The authors formulate this problem as an equivalence test and propose a “certify-or-abstain” framework: certification is granted only when the evidence is sufficient. Otherwise, the authors abstain. Under the finite-order independence assumption, the authors transform the problem into a moment-constrained optimization problem for the event-count distribution through symmetrization and, utilizing the primal-dual structure of linear programming, construct a worst-case distribution and a polynomial certificate. This framework controls the worst-case probability of false certification under permitted dependency structures and determines the minimum sample size required for a randomized certification rule to achieve the prespecified nominal retention target under the independent nominal model. The relevant conclusions can be precisely verified via rational-number certificates.

The paper further analyzes the impact of the strength of the independence assumption on certification costs, characterizes the differing sample complexities under finite-order independence and complete independence, and provides deterministic certification rules. For clustered data, the authors analyze the constraints imposed by the number of independent clusters on a uniform performance guarantee under arbitrary intra-cluster dependencies and construct corresponding certification bounds given an upper bound on intracluster correlation. Through simulations and case studies using electrocardiogram (ECG), aerospace telemetry, and language model data, the authors demonstrate the impact of dependency structures on certification results, illustrating that a large sample size or low pairwise correlation is insufficient to guarantee the validity of certification based on the independence assumption.

Critical strengths

1.The paper addresses an important and well-motivated statistical problem concerning the validity of threshold-based decisions under dependent observations. The theoretical analysis is technically substantial, particularly the characterization of exact minimum sample sizes and the construction of verifiable primal-dual certificates. 2.The paper includes diverse real-world applications, including ECG, spacecraft telemetry, and language model evaluations, which demonstrate the practical relevance of the proposed framework. The simulations and case studies also illustrate how dependence can substantially affect certification results.

Critical weaknesses

In this paper, the exact minimum sample sizes are derived by requiring nominal retention under the independent Bernoulli model, while validity is guaranteed over all distributions satisfying the specified independence assumptions. Consequently, achieving the target nominal retention does not necessarily guarantee the same certification probability under dependent alternatives, even when the true event rate equals the nominal rate.

Questions for authors

1.Could the authors further discuss whether the sample-complexity analysis can be extended to require worst-case retention over all distributions satisfying the specified r-wise independence assumption? 2.In applications involving heterogeneous patients, prompts, or telemetry channels, could the framework be extended to accommodate cluster-specific event rates? 3.Is it possible to characterize the exact minimum sample sizes for deterministic count certification rules more generally, especially for independence orders where only restricted optimality results are currently available?

3 comments

Thank you for your positive assessment. We greatly appreciate your questions, which led to new results that we believe strengthen the paper.

Question 1:

Could the authors further discuss whether the sample-complexity analysis can be extended to require worst-case retention over all distributions satisfying the specified r-wise independence assumption?

Answer: Yes, and we have now carried out this extension. Requiring retention in the worst case over all laws in ℒᵣ(p₀) keeps the problem a single linear program. The symmetrisation argument of Lemma 1 applies unchanged, so count rules remain optimal, and worst case retention is certified by a degree r polynomial that lies below the rule and has expectation at least 0.75 at p₀, in the same way that validity is certified by one that lies above it. As in Theorem 2, each sample size is certified exactly in both directions.

Retention requirementindependent4-wise3-wisepairwise
nominal (Table 1)9361,5187,9588,173
worst case (new)9361,7168,3238,590

The stronger guarantee costs at most 13% more units, and the ordering across independence orders is unchanged. The code and exact certificates are included in the updated supplementary material, and we will add this row to Table 1 in the revised paper.

Question 2:

In applications involving heterogeneous patients, prompts, or telemetry channels, could the framework be extended to accommodate cluster-specific event rates?

Answer: Yes. When each cluster has its own fixed rate and one prespecified unit per cluster is audited, as in Proposition 2, the audited outcomes are independent with heterogeneous rates, and the audit certifies their equally weighted average. By a classical result of Hoeffding (1956, Theorems 4 and 5), the tails of such a count are bounded by those of the binomial count with the same average, provided the cutoff lies at least one unit from the mean, and the probability of an interval that contains the mean is smallest when all rates are equal. Every exact TOST gate [a, b] in the paper satisfies a − 1 ≥ NL and b ≤ NU − 1 and contains Np₀, so heterogeneity never increases their error or reduces their retention. The table gives the worst case over all heterogeneous rates for two of them.

DesignLargest error over the nullSmallest retention
Primary contract, N = 9430.00980.754
PTB-XL, N = 18770.00940.983

We will add this result with its short proof next to Proposition 2 and update Section 7 accordingly.

Question 3:

Is it possible to characterize the exact minimum sample sizes for deterministic count certification rules more generally, especially for independence orders where only restricted optimality results are currently available?

Answer: Proposition 5 gives a certified deterministic gate at every independence order, and its minimality over all deterministic rules, not only intervals, can be established with the mixed integer program of Appendix E. In the submitted version we had completed this search at order four. Following your question, we have now run it at every sample size below the gate at orders two and three, about 8,000 programs in total. At order two no deterministic rule reaches the target retention below the reported gate of 12,223. At order three the solver returned such a rule only at the two sample sizes just below the gate of 11,929, and in both cases an exact law shows that this rule exceeds the error level, by 5×10⁻⁶ and 7×10⁻⁷. When the error level is lowered by 10⁻⁵, the best rule at these sizes has retention at most 0.739. The reported gates are therefore minimal over all deterministic rules at orders two, three and four, in the same numerical sense as at order four. We will add these results to Appendix E.

Reference. Hoeffding, W. (1956). On the distribution of the number of successes in independent trials. The Annals of Mathematical Statistics, 27(3), 713–721.

Thanks for the detailed response. I maintain my score.

Thank you for reading our response and for your continued support of the paper.

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

This paper studies how to verify whether a machine-learning system satisfies a desired operating rate when the evaluation samples may be dependent. The authors propose a framework that either certifies the system's performance or abstains when the available evidence is insufficient. They provide theoretical results on sample requirements and evaluate the approach on medical data, spacecraft data, and language-model outputs.

Critical strengths

1- The paper addresses an important and practical problem. Dependence between evaluation samples is common in real applications, and ignoring it can lead to unreliable conclusions.

2- The proposed framework provides theoretical guarantees and identifies how many samples are needed under different independence assumptions. This is a useful contribution.

3- The authors include several real-world applications from different fields, which helps demonstrate the possible uses of the framework.

4- The paper compares the proposed approach with existing statistical methods and discusses situations where certification is not possible.

Critical weaknesses

1- The method relies on assumptions about dependence between samples. In practical applications, these assumptions may be difficult to verify, which could limit the usefulness of the theoretical guarantees.

2- The proposed approach appears conservative in some experiments. In several cases, it abstains even when the true operating rate satisfies the target. It would be useful to investigate how to improve certification without losing the statistical guarantees.

3- Although the paper presents applications in different areas, most examples focus on evaluating a single operating rate. It is not clear how easily the framework could be extended to more complex performance requirements.

4- The numerical results show the importance of dependence, but more discussion of the practical advantages over existing methods would help readers understand when the proposed approach should be preferred.

Questions for authors

1- How can users determine which independence assumptions are reasonable for a real dataset? Is there any practical procedure to help select them?

2- When the method abstains, is there a way to determine whether additional samples would help? Could the method estimate how many more independent samples are needed?

3- In Table 13, the proposed method is conservative in several settings. Can the authors explain whether this is mainly due to the theoretical requirements or the particular statistical bounds used?

4- How easily could the method be extended to evaluate several performance measures simultaneously, such as failure rate, accuracy, and false-alarm rate?

5- Could the authors provide clearer guidance on when their approach is preferable to existing cluster-based methods, particularly when only a small number of independent clusters are available?

1 comment

Thank you for the review and for recognising the importance of the problem and the value of our theoretical guarantees. Your comments will greatly improve the structure of our work.

Question 1:

How can users determine which independence assumptions are reasonable for a real dataset? Is there any practical procedure to help select them?

Answer: The procedure for choosing the assumption is given in Section 5 under “Operational use”. We will make this more visible by adding it to the introduction. In short, the choice follows from how the evaluation was designed and never has to be verified from data. When units were sampled independently, the independent audit applies. When they share a common source, such as a patient or a prompt, the cluster audit applies. If nothing can be assumed about dependence within clusters, the audit uses one prespecified unit per cluster or the Bernstein audit with κ = 1, and both remain valid under any such dependence.

Question 2:

When the method abstains, is there a way to determine whether additional samples would help? Could the method estimate how many more independent samples are needed?

Answer: Yes. Proposition 2 gives the exact number of independent clusters required when nothing is assumed about dependence within clusters, which is 936 for our main contract and 943 for the deterministic exact TOST gate. For example, our language model study, with 180 prompts, is 756 prompts short of 936. When a correlation bound can be justified, Table 12 gives the smaller numbers needed. Every abstention therefore comes with a concrete answer to how much more data is needed. We will report this number next to each abstention in Table 3.

Question 3:

In Table 13, the proposed method is conservative in several settings. Can the authors explain whether this is mainly due to the theoretical requirements or the particular statistical bounds used?

Answer: This behaviour comes mainly from the theory rather than from our particular bounds. Every setting in Table 13 has between 20 and 150 clusters, and Proposition 2 proves that with so few clusters no valid procedure can reach 75% retention when dependence within clusters is unrestricted. The standard methods certify more often only because they exceed their error level, reaching 3.2% for cluster-t and 3.4% for the pairs bootstrap against the nominal 1%. When a correlation bound can be justified, our Bernstein audit uses it, and with 150 clusters of 50 units and a cap of 0.02 it already reaches 74% retention while keeping its guarantee.

Question 4:

How easily could the method be extended to evaluate several performance measures simultaneously, such as failure rate, accuracy, and false-alarm rate?

Answer: The framework extends directly to several measures. Certifying only when every individual audit certifies controls the error of the joint claim at the same level, with no multiplicity correction and regardless of how the measures are related (Berger & Hsu, 1996). The reason is that if any measure misses its target, the joint claim can pass only if that measure is falsely certified. For a joint retention of at least ρ across K measures, it is enough to plan each audit for retention 1 − (1 − ρ)/K. We will add this extension to Section 5.

Question 5:

Could the authors provide clearer guidance on when their approach is preferable to existing cluster-based methods, particularly when only a small number of independent clusters are available?

Answer: Our audit is designed for the settings where standard practice fails, namely evaluations with few clusters, small rates and a need for a guarantee. Language model benchmarks that draw many generations from a limited set of prompts are a typical example, such as our study with 9,000 generations from 180 prompts. Table 13 shows that conventional cluster methods lose error control there, while all of our audits maintain it. When clusters are plentiful, conventional methods work well, and Proposition 2 tells the evaluator which situation they are in. We will state this guidance explicitly in the introduction.

Reference. Berger, R. L. and Hsu, J. C. (1996). Bioequivalence trials, intersection-union tests and equivalence confidence sets. Statistical Science, 11(4), 283–319.

Comments on the paper

1 comment

We thank the reviewers for their feedback. We have uploaded a revised manuscript, with all changes highlighted in blue, and an updated supplementary archive. The main additions are summarised below.

Worst case retention (nnuq, kDRG). We now also certify the minimum sample sizes when retention must hold under every r-wise independent law. They are 1,716, 8,323 and 8,590 at orders four, three and two, against 1,518, 7,958 and 8,173, so at most 13% more (Table 1, Appendix A.7).

Heterogeneous cluster rates (nnuq, kDRG). By a classical result of Hoeffding (1956), every exact TOST gate in the paper keeps its level and retention when clusters have different fixed rates (Proposition 2(c)).

Deterministic gates (nnuq). A search over all deterministic rules at every sample size below the gate, about 8,000 programs, confirms that the gates of the primary contract at orders two and three are minimal (Appendix E).

Other additions (qEQU, kDRG). The introduction now explains how to choose the audit, Table 3 reports the clusters needed after each abstention, Section 5 covers several measures at once, and Section 6 discusses weaker forms of independence.

All new results come with code and exact certificates in the supplementary material. Detailed responses to each reviewer are below.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.