📊 statistics

The Exceedance Design Effect: Effective Sample Size for Thresholds under Clustering

This paper demonstrates that when calibration data is clustered rather than independent, the effective sample size for threshold-based machine learning systems varies depending on the specific threshold level rather than being a single fixed value, necessitating a new closed-form correction to accurately predict coverage reliability and avoid the pitfalls of existing methods.

Original authors: Adam Noonan

Published 2026-08-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Adam Noonan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of modern artificial intelligence, systems are often taught to be cautious. Before an AI answers a difficult question or generates a piece of code, it runs a safety check to decide if it is confident enough to proceed. To set this safety check, engineers gather a large collection of practice examples, known as a calibration set. They look at the scores the AI gives to these examples and pick a cutoff point, usually at a specific spot in the ranking, such as the top ninety percent. The promise is that if the AI is used on new, unseen data, it will stay within that safety limit ninety percent of the time. This promise relies on a fundamental assumption: that every practice example is an independent, unique event, like rolling a die where the result of one roll has no influence on the next.

However, in the complex pipelines that power today's language models, this independence is often an illusion. When an AI reasons through a problem, it might generate several different paths or "branches" of thought from the same starting point. These branches share a common history, much like siblings who share a family background. Because they come from the same source, their scores tend to move together. If one branch is confident, the others likely will be too. For decades, statisticians have known how to handle such clustered data when calculating simple averages, but they have not known how to adjust the rules when the goal is to set a threshold or a cutoff line. This gap meant that AI systems were being calibrated with a false sense of security, believing they had more independent data than they actually possessed.

A new study by independent researcher Adam Noonan reveals exactly how this shared ancestry distorts the safety guarantees of these systems. The research demonstrates that the standard way of counting data points fails when the data comes in clusters. The study shows that the "effective" number of independent examples is not a single fixed number for a dataset. Instead, it changes depending on where the safety cutoff is set. A cluster of scores might act like a single independent point if the cutoff is high, but like two separate points if the cutoff is lower. The similarity of the scores as numbers does not matter; what matters is whether they fall on the same side of the line.

The researchers proved a mathematical law describing this phenomenon, which they call the "exceedance design effect." They found that the usual method of correcting for clustered data, which looks at how similar the scores are to each other, is often wrong. In many real-world cases, the scores might look uncorrelated, yet the decision to pass or fail the safety check is highly correlated. When the researchers tested this on a released dataset of over twenty-five thousand examples from a process-reward model, they discovered a startling reality. While the dataset contained twenty-five thousand rows, the amount of independent information it actually provided was equivalent to only about one thousand three hundred. The system was behaving as if it had twenty times less data than the spreadsheet suggested.

This discrepancy has serious consequences for anyone deploying these systems. The average performance of the system might look correct over many trials, but for a single deployment, the risk of failure is much higher than promised. The study shows that the safety margin is not just slightly off; it is significantly wider than expected, meaning the system is far less reliable in individual cases than the average numbers suggest. Furthermore, the research rules out the idea that simply collecting more data from the same sources will fix the problem. Increasing the number of reasoning branches for a single question yields diminishing returns because the branches are too similar. The only way to truly increase the reliability of the safety check is to gather more distinct questions, not more variations of the same question.

The paper also addresses a common misconception that the problem can be solved by looking at the correlation between the scores themselves. The researchers showed that this approach can be dangerously misleading. In one instance involving a standard reading comprehension dataset, the correlation between scores was so close to zero that a practitioner would conclude no correction was needed. Yet, when they looked at the actual pass-or-fail decisions, the correlation was significant, and the system was effectively much smaller than it appeared. The study provides a new recipe for practitioners: instead of counting every row in a dataset, they must count the number of independent sources, such as the number of unique questions, and adjust their expectations based on how those sources are clustered.

Ultimately, this work provides a clear, closed-form law for understanding how clustered data affects safety thresholds. It moves beyond vague warnings to offer a precise measurement of the risk. The findings confirm that the damage caused by ignoring these dependencies is invisible in the average results but fully felt by the user who deploys the system once. By understanding that a dataset has a different effective size for every level of safety it aims to achieve, engineers can finally calibrate their AI systems with a realistic view of their limitations, ensuring that the promises made to users are actually kept.

Technical Summary: The Exceedance Design Effect

1. Problem Statement

Machine learning systems frequently rely on thresholds set at specific quantiles of a calibration set (e.g., conformal predictors guaranteeing 90% coverage, abstention gates, or safety filters). These guarantees assume that calibration examples are independent and identically distributed (i.i.d.). However, in modern pipelines—such as Large Language Model (LLM) inference, beam search, or reasoning traces—calibration units often share a common prompt, document, or reasoning history, creating clusters of dependent data.

While survey statistics has long addressed the reduction in effective sample size ( $n_{eff}$ ) for averages under clustering via the design effect (Kish, 1965), this paper argues that the standard correction is inappropriate for thresholds (order statistics). The standard design effect relies on the correlation of raw scores. The author demonstrates that for a threshold, the relevant correlation is not between the scores themselves, but between the exceedance indicators (whether a score falls above or below the threshold). Furthermore, this correlation is not constant; it depends on the specific level at which the threshold is set.

2. Methodology and Theoretical Framework

Core Definitions

Exceedance Indicator: For a threshold $q_p$ (the $p$ -quantile), the indicator is $I = \mathbb{1}\{S \le q_p\}$ .
Exceedance Correlation ( $\rho_I(p)$ ): The intra-cluster correlation of these binary indicators.
Exceedance Design Effect (DEFF): Defined as $1 + (\tilde{m} - 1)\rho_I(p)$ , where $\tilde{m}$ is the size-biased mean cluster size.
Effective Sample Size ( $n_{eff}$ ): $n / \text{DEFF}$ .

Theoretical Derivation

The paper derives a closed-form law for the distribution of realized coverage ( $C$ ) under clustering.

Setup: Calibration scores arrive in $b$ clusters of size $m$ (total $n=bm$). Clusters are i.i.d., and scores within a cluster are exchangeable. The test score is independent of the calibration clusters.
Variance of the Empirical CDF: The variance of the empirical CDF at the quantile is derived by treating the cluster-level empirical CDFs as i.i.d. averages. The variance of the sum of indicators within a cluster introduces the term $1 + (m-1)\rho_I(p)$ .
Bahadur Representation: Using the Bahadur representation for quantiles, the author shows that the density of the score distribution cancels out when mapping the quantile error to the coverage probability. This is a critical step: it implies that the dispersion of coverage depends only on the correlation of the indicators, not the correlation of the raw scores or the shape of the underlying density.
Limit Law (Theorem 1): As $b \to \infty$ , the coverage $C$ converges in distribution to a Normal distribution (or a matched Beta distribution for finite samples) with variance:
$\text{Var}(C) \approx \frac{p(1-p)}{n_{eff}} = \frac{p(1-p)}{n / [1 + (m-1)\rho_I(p)]}$
This establishes that the design effect acts as a reduction in sample size specifically for the dispersion of the coverage.

Extensions

Ragged Families (Proposition 2): For clusters of unequal size $m_j$ , the theorem holds if $m$ is replaced by the size-biased mean $\tilde{m} = \frac{\sum m_j^2}{\sum m_j}$ .
Informative Sizes (Section 2.5): The paper warns that if cluster sizes are correlated with the scores (e.g., harder questions generate longer reasoning traces), the calibration marginal differs from the test marginal, introducing a first-order bias in the mean coverage that the design effect does not correct.
Mean Drift (Conjecture 1): Under clustering, the mean coverage is not exactly the nominal level $p$ but drifts by an $O(1/b)$ term dependent on the derivative of $\rho_I(p)$ .

3. Key Contributions

The Exceedance Design Effect: The paper proves that the effective sample size for a threshold is governed by the correlation of exceedance indicators ( $\rho_I$ ), not the correlation of raw scores ( $\rho$ ).
Level-Dependence: It demonstrates that $\rho_I(p)$ is a function of the threshold level $p$ . A dataset does not have a single effective sample size; it has one for every threshold level. In many cases (e.g., Gaussian copulas), $\rho_I(p)$ attenuates in the tails, meaning the design effect is smaller at stricter coverage levels (e.g., 99%) than at looser ones (e.g., 90%).
Failure of Standard Corrections: The paper shows that applying the standard Kish design effect using raw score correlation $\rho$ is incorrect. In many realistic scenarios, $\rho_I(p) < \rho$ , leading to an overestimation of the design effect (wasting data) or, in specific copula structures, an underestimation (unsafe deployment).
Ragged Cluster Correction: It provides the correct substitution for unequal cluster sizes using the size-biased mean $\tilde{m}$ , showing that average cluster size $\bar{m}$ significantly understates the penalty of raggedness.
Empirical Validation:
- Released PRM Dataset: On a released process-reward model calibration set (25,028 examples), the author measures an effective sample size of $\approx 1,300$ . The standard score correlation suggested a much smaller penalty, while the indicator correlation revealed a design effect of $\approx 30.8$ (before correcting for informative sizes).
- Generated Sweep: Using beam search vs. independent sampling, the author isolates the "shared ancestry" mechanism, showing that beam search induces high $\rho_I$ while independent sampling does not, even when conditioned on the same prompt.

4. Results and Measurements

Dispersion vs. Mean: The primary impact of clustering is on the dispersion of realized coverage (first-order effect), not the mean (second-order effect). A system deployed once may experience coverage far below the nominal guarantee, even if the average over many runs appears correct.
Magnitude of Error: On the PRM dataset, the realized coverage distribution was $4.46\times$ wider than the i.i.d. prediction. The probability of a deployment falling short by 0.5 percentage points increased from 0.4 per 1,000 (i.i.d.) to 284.5 per 1,000 (clustered).
Standard vs. Correct: Using raw score correlation to estimate the design effect resulted in errors up to $5.7\times$ worse than the correct indicator-based law. In some cases (e.g., SQuAD 2.0), raw score correlation was near zero, suggesting no correction was needed, while the indicator correlation was positive, requiring a significant correction.
Tail Behavior: For tail-independent copulas (like Gaussian), the design effect decreases as the threshold moves into the tail. For tail-dependent copulas (like Student-t or atom-mixtures), the design effect hits a floor determined by the tail dependence coefficient.

5. Significance and Claims

The paper claims to close a gap between survey sampling theory and conformal prediction. While the components (design effects, indicator correlations, size-biased means) exist in separate literatures (survey sampling, econometrics, copula theory), this paper is the first to compose them into a specific law for thresholds estimated from clustered data.

Modest Claims:

The paper does not claim to solve the problem of informative cluster sizes (where size correlates with score); it diagnoses it and notes that it requires a different correction (weighted conformal prediction).
The mean drift (Conjecture 1) is presented as a well-tested conjecture with a measured remainder, not a fully proved theorem, though the dispersion law (Theorem 1) is proved.
The paper does not claim that all clustering is bad; it provides the tools to quantify exactly how much "information" a clustered set retains, allowing practitioners to decide if the trade-off is worth it.

Practical Implications:

Practitioners must estimate $\rho_I(p)$ directly from same-cluster pairs rather than relying on raw score correlations.
Effective sample size must be reported per coverage level, not as a single global number.
"Buying depth" (more samples per prompt) yields diminishing returns compared to "buying breadth" (more prompts), as $n_{eff}$ is bounded by the number of clusters $b$ .
Reporting the number of clusters $b$ and the effective sample size $n_{eff}$ is essential for interpreting the reliability of a single deployment.

The paper concludes that the "damage" of clustering is invisible in average coverage metrics but fully felt by individual deployments, and that the standard tools for averaging (Kish's formula on scores) are insufficient for the rank-based guarantees of conformal prediction.