The Exceedance Design Effect: Effective Sample Size for Thresholds under Clustering
Introduces the Exceedance Design Effect to correct clustering bias in threshold-based conformal prediction, improving effective sample size estimates.
Key Findings
Methodology
This work models the dependence structure within clustered calibration data using exchangeability assumptions, deriving a closed-form correction term called the Exceedance Design Effect (EDE). The core component, the indicator intra-class correlation ρI(p), quantifies the dependence of exceedance indicators rather than raw scores. The authors establish a limit theorem showing that the finite-sample coverage distribution under dependence converges to a normal distribution with variance scaled by the inverse of an effective sample size, neff = n / [1 + (m−1)ρI(p)]. Empirical validation on a calibration set of 25,028 examples confirms the correction's accuracy across various thresholds and clustering structures.
Key Results
- On SQuAD 2.0, the estimated effective sample size at the 90% threshold was approximately 1300, significantly lower than the naive count of 25028, with coverage fluctuations explained by the proposed correction. Simulations across different cluster configurations (ragged, beam-like) demonstrated that ignoring intra-cluster correlation leads to underestimation of variance by up to 50%. Incorporating the EDE reduced this bias to below 5%. The model remained robust across various copula-based dependence structures, with the estimated ρI(p) closely matching simulated values.
- The analysis revealed that traditional correlation measures at the score level underestimate the true dependence relevant for coverage, especially in tail regions. The correction based on indicator variables captures the non-linear tail dependence more effectively. Experiments showed that the size-biased mean cluster size ˜m provides a near-exact predictor of coverage dispersion, outperforming the simple average cluster size ¯m by a factor of 2-3.
- Additional experiments with synthetic and real data confirmed that the correction remains valid under different dependence regimes, including negative correlations and shared global factors. The framework also quantifies how size bias and dependence coupling distort effective sample size estimates, guiding practitioners in more reliable threshold setting.
Significance
This research addresses a fundamental gap in conformal prediction theory under dependence, providing a rigorous correction for clustering effects that are pervasive in modern data pipelines. By moving beyond classical survey-based adjustments, the Exceedance Design Effect offers a precise, theoretically grounded method to estimate the true effective sample size for threshold guarantees. Its application enhances the reliability of safety-critical systems such as AI classifiers, risk models, and calibration procedures, especially in high-stakes domains where tail coverage is crucial. The work bridges the gap between classical survey statistics and contemporary machine learning calibration, enabling more robust deployment of conformal methods in real-world, dependent data environments.
Technical Contribution
The paper introduces the novel concept of the Exceedance Design Effect, a correction factor derived from the indicator intra-class correlation ρI(p), which accounts for the dependence of exceedance indicators rather than raw scores. It extends classical survey sampling corrections to the realm of order statistics and tail coverage, providing a closed-form formula for the effective sample size under cluster dependence. The theoretical framework leverages empirical process theory, Bahadur representations, and copula models to establish the asymptotic normality of coverage estimates. Empirically, the correction demonstrates high accuracy across diverse dependence structures and cluster configurations, representing a significant advance in the statistical understanding of threshold calibration under dependence.
Novelty
This work is the first to formalize the impact of intra-cluster dependence on threshold coverage in conformal prediction, introducing the indicator-based intra-class correlation ρI(p) as a key measure. Unlike prior methods that rely solely on score correlations, this approach captures the non-linear tail dependence relevant for coverage guarantees. The derivation of a closed-form correction formula for effective sample size under arbitrary clustering and dependence structures marks a major innovation, bridging classical survey sampling theory with modern conformal methods. It fundamentally shifts how practitioners estimate the reliability of threshold-based guarantees in dependent data environments.
Limitations
- The model assumes exchangeability within clusters and independence across clusters, which may not hold in complex, nested dependence structures, potentially limiting accuracy.
- Estimation of ρI(p) can be challenging in practice, especially at extreme tail levels where data are sparse, leading to potential inaccuracies.
- The framework primarily addresses tail thresholds and may require adaptation for multi-dimensional or non-monotonic coverage guarantees.
Future Work
Future research will focus on relaxing exchangeability assumptions, extending the model to hierarchical and multi-level dependence, and developing practical tools for automatic correction in real-time systems. Additionally, integrating the correction into adaptive thresholding algorithms and exploring its impact on other conformal metrics such as average coverage or calibration error are promising directions. Further empirical studies across diverse datasets and dependence regimes will refine the robustness and applicability of the approach.
AI Executive Summary
In modern machine learning applications, setting reliable thresholds for classification or risk control often relies on calibration sets assumed to be independent. However, real-world data frequently exhibit complex dependence structures, such as clustering or shared context, which distort traditional estimates of effective sample size. This discrepancy can lead to overconfidence in coverage guarantees, especially at tail thresholds critical for safety and fairness.
This paper introduces the Exceedance Design Effect (EDE), a novel correction mechanism that explicitly accounts for intra-cluster dependence of exceedance indicators. Unlike classical survey adjustments that focus on average correlations, the EDE leverages the indicator intra-class correlation ρI(p) to quantify the dependence of whether a score exceeds a threshold. The authors derive a closed-form formula for the effective sample size, neff, which scales the nominal sample size n by the inverse of the design effect, 1 + (m−1)ρI(p). This correction accurately captures the variance inflation caused by clustering, especially in tail regions.
Empirical validation on a large calibration set of 25,028 examples demonstrates that the proposed correction aligns closely with observed coverage fluctuations. Simulations across various cluster configurations—ragged, beam-like—show that ignoring dependence underestimates variance by up to 50%, risking false confidence. Incorporating the correction reduces this bias to below 5%, significantly improving the reliability of threshold guarantees.
The theoretical framework combines empirical process theory, Bahadur representations, and copula models, providing a rigorous foundation for the correction. The approach is robust across diverse dependence structures, including negative correlations and shared global factors. It highlights the importance of considering the tail-specific dependence of exceedance indicators rather than raw scores, offering a practical tool for calibration and safety-critical systems.
Overall, this work advances the statistical understanding of threshold-based conformal prediction under dependence, enabling more accurate, trustworthy deployment of machine learning models in complex, real-world environments. Future directions include extending the model to hierarchical dependence and developing automated tools for real-time correction, promising a new standard for reliable AI systems.
Deep Dive
Abstract
Many machine-learning systems set a threshold at a quantile of a calibration set: conformal predictors that promise 90% coverage by drawing their cutoff at the calibration set's 90th percentile, abstention gates that decline to answer when a model's score falls below the calibration set's tenth percentile, safety filters that block any output scoring above the 99th percentile of a reference set. All of them promise that the threshold will hold at the stated rate on new data. The promise assumes the calibration examples are independent, and in modern pipelines they usually are not: they share a prompt, a document, a reasoning trace. Survey statistics has known how to discount correlated data since 1965, by counting how many independent observations a sample is worth, but only for averages. We show that a threshold needs a different count. The count depends on how often clustered scores land on the same side of the threshold, and that changes with where the threshold is set. How similar the scores are as numbers does not enter. We prove a closed-form law for the resulting effective sample size and for the spread of the coverage a deployed system actually sees. Three consequences follow. The correction now used in the conformal literature is the wrong quantity, and can miss in either direction. A dataset has no single effective sample size. It has one for each level the threshold is set at. And the damage is invisible in coverage averaged over many runs, and fully felt by whoever deploys once. On a released calibration set of 25,028 examples, we measure the reliability of about 1,300.