PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Adam Noonan

arXiv:2608.21262v1stat.MLcs.LG

TL;DR

Quantile thresholds in machine-learning calibration lack a suitable effective-sample-size correction when examples are clustered. The paper derives a closed-form threshold-specific correction based on exceedance dependence and measures its practical impact, including 25,028 points behaving like about 1,300. It also identifies scope boundaries involving informative cluster sizes and mismatched reference constructions.

  • Problem

    Existing corrections discount clustering for averages, but threshold guarantees depend on rank and on how clustered scores fall relative to the selected quantile.

  • Method

    The paper replaces score-level dependence with the intra-cluster correlation of threshold exceedance indicators and derives a closed-form effective sample size for quantile thresholds.

  • Results

    25,028 calibration points behave like about 1,300, while threshold information varies with the operating level and naive score-correlation corrections can misstate dispersion.

  • Takeaways & Limitations

    Threshold systems should use a level-specific exceedance design effect rather than a single score-correlation correction or a single dataset-wide effective sample size.

  • Takeaways & Limitations

    The released artifact couples cluster size and score, and the paper notes that its reference arms do not match the beam data’s family size and exceedance correlation.

Abstract

from arXiv · show

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.

1 The guarantee is a statement about ranks

Threshold guarantees concern ranks and exceedances, not averages: clustered calibration scores can provide different amounts of information at different cutoff levels. The paper distinguishes this level-specific question from classical design-effect corrections for correlated averages.

  • Motivation: A quantile threshold depends on which side of the cutoff each clustered score falls, not on numerical score similarity alone.The same pair can split at one cutoff and agree at another, changing how much information they provide.
  • Contribution: A clustered dataset has no single effective sample size: its threshold-relevant count depends on the level at which the threshold is set.That count may be smaller than the row count, or larger, and is not captured by the score correlation practitioners would typically compute.
  • Measurement: 25,028 calibration points behaved like about 1,300 when reliability was measured by resampling the released process-reward calibration set.On SQuAD 2.0, same-paragraph score correlation was −0.0026 while exceedance correlation was +0.0640, producing a design effect of 1.60.
  • Rank-based guarantee: Split conformal selects the k = ⌈(n + 1)(1 −α)⌉-th smallest calibration score and uses exchangeability to bound the test-score exceedance probability by α.The guarantee follows because the test score is equally likely to occupy any rank among n + 1 exchangeable scores.
  • Coverage variability: Under i.i.d. sampling, conditional coverage is itself random with a Beta(k, n + 1 −k) distribution, while perfectly tied clusters replace points with clusters in that law.The intermediate dependence case between independent and perfectly tied calibration units is the setting addressed by the paper.

2 The coverage law, and why the density cancels

The coverage-dispersion law depends on threshold-side agreement among clustered scores, yielding an exceedance-specific effective sample size rather than a score-correlation correction. It extends to ragged families and clarifies that informative family sizes can shift coverage at first order, beyond dispersion alone.

  • Assumptions and scope: Atomic scores fall outside the theorem, with raw dispersion ratio 1.09× versus 4.46× after random tie-breaking.Random tie-breaking calibrates a randomized procedure, so its reported dispersion belongs to that procedure.
  • The coverage law: The exceedance design effect uses threshold indicators, not numerical score correlation, because pairs can agree at one cutoff and disagree at another.Across tested copulas, indicator correlation is generally below score correlation, but a valid counterexample has score correlation 0 and indicator correlation 0.44.
  • The coverage law: The limiting variance is p(1 −p)/neff, where neff = n/[1 + (m −1)ρI(p)], and coverage is approximated by a matching-mean, matching-variance beta law.The dependence enters through the threshold-level indicator correlation ρI(p), so the effective size varies with the target level.
  • The coverage law: The law remains valid for arbitrary within-family dependence through mean pairwise indicator correlation, including negative dependence that gives neff > n.A flip-copula sweep at p = 0.90 produced neff/n from 0.900 to 1.125 with dispersion matching the law at 0.997 throughout.
  • Ragged families: For ragged families, the size-biased mean ˜m predicts dispersion within 1.6%, while the average family size understates beam-like dispersion by 29%.In the beam-like profile, ¯m = 3.76 but ˜m = 8.53.
  • Informative sizes: Informative family sizes can bias coverage at first order: changing only size–score pairing shifted coverage by +6.5 or −18 percentage points.The reported design-effect contribution to the mean was well under one percentage point, while the released calibration set showed strong size–score coupling.

3 Related work

Prior conformal work addresses weighting and distribution shift but largely assumes away intra-cluster dependence. Nearby approaches either handle means or impose conditions that exclude the full dependence range, leaving threshold-specific effective sample size and coverage variability unresolved.

  • Gap: The conformal literature handles survey weighting and related shift problems, while its dependence half remains assumed away.Four papers address weighting, but dependence is absent or explicitly excluded; one conditional-coverage result still leaves clustering unmodeled.
  • Gap: Applied conformal pipelines record document or source grouping as distribution shift, not as a dependence structure requiring a design-effect correction.The Kotte pipeline uses document boundaries without stating the sampling unit, while its proposed repairs target shift rather than clustering.
  • Validation: A pooled re-split validity check can impose exchangeability by construction and therefore miss discrepancies in realised coverage under the original split.Its permutation mean tracks the target, while the actual split differs at all three reported levels; at α = 0.05 it lies 3.4 permutation standard deviations away.
  • Evidence: On CoNLL-2003, the measured dependence correction ranges from 4.21 to 2.26 in design effect as p increases from 0.5 to 0.95.The corresponding indicator correlation falls from 0.127 to 0.050, and every level clears its permutation null.
  • Nearest work: Ramos et al. derive a serial coverage approximation and a perfect-duplication endpoint, but their assumptions exclude the endpoint and do not provide the paper’s uniform threshold-specific law.The excluded condition becomes unsatisfiable under perfect within-cluster duplication, so transport of that framework cannot supply the full result.
  • Nearest work: Kish-style effective sample sizes reported for LLM outputs are exact for means, not for quantile thresholds or realised coverage.Prior work derives effective votes or a correlation ceiling for mean estimands, whereas threshold calibration depends on ranks among correlated scores.

4 The correction the literature writes down can vanish when the real one does not

The paper shows that score correlation can mismeasure threshold uncertainty: the naive correction may overstate or understate dispersion, while the proposed law remains accurate across tested settings and dependence structures.

  • Both endpoints are recovered: at ρ = 0, analytic and simulated standard deviations are 0.0211 and 0.0212; at ρ = 1, the law gives 0.0423 versus exact 0.0412.The remaining endpoint discrepancy is attributed to ⌈k/m⌉ ceiling discreteness.
  • 0.00552 maximum error for the naive form versus 0.00096 for the proposed law, making the naive form 5.7× worse.The naive error is largest in the mid-range; at ρ = 0.2, it would discard 20% of effective calibration size for nothing.
  • At q = 0.5, score correlation is exactly zero, but the true design effect is 1.44 and dispersion is understated by 17%.Across 1 −p < q < 0.5, the naive form can indicate a variance bonus while the true design effect exceeds one.
  • At p = 0.90 on SQuAD 2.0, raw score ICC is −0.0026 while indicator ICC is +0.0640, producing a design effect of 1.60.The indicator ICC clears a permutation null of 0.0074, whereas the raw score ICC is indistinguishable from zero.
  • Worst departure across untuned configurations is 0.17%, while nested structures match the exchangeable control within 0.15% of unity.The nested test includes differing cluster structures and verifies that deviation does not grow with structural heterogeneity.
  • The measured residual follows O(n^-2), with leading constants confirmed to 0.07%, while the next O(n^-3) term has model-dependent sign.The fitted exponents are −1.98 and −1.97 for atom-mixture and one-factor Gaussian models.

5 The design effect is level-dependent

The exceedance design effect changes with the threshold level, and its tail behavior depends on the dependence family. Real clustered data broadly corroborate attenuation, but direct estimation is safer than transporting a parametric correction.

  • 200 clustered points carry 102 points’ worth of information at 90% coverage but 130 at 99%.At tighter coverage levels, rare exceedances can become nearly independent even when underlying scores remain strongly correlated.
  • Tail limits: For tail-independent families, ρI(p) approaches 0 and the design effect approaches 1 in the tail.Under the Gaussian copula, ρI decreases to 1.2 × 10−3 by 1 −p = 10−10 at ρ = 0.6.
  • Tail limits: For tail-dependent families, ρI(p) has a positive floor, so the tail discount can remain unavailable throughout the operating range.For a t-copula with ν = 3 and ρ = 0.6, λU = 0.374, while ρI = 0.403 at p = 0.90 and 0.385 at p = 0.99.
  • Real clustered data: At powered levels p ≥0.95 in the fixed analyte panel, measured ρI was below Gaussian predictions, which overstated the design effect by roughly 30 to 50 per cent.The disagreement between clearing-set and fixed-panel analyses motivates estimating δ(p) directly from same-cluster pairs.
  • Real clustered data: Across ten NHANES analytes, exceedance-indicator ICC was smaller than score correlation and fell by 3–6 fold across the operating range.The ordering corroborates the Gaussian-family pattern on this clustered sample, but does not establish it generally; SQuAD 2.0 at article level reverses the ordering.

6 Two instances, measured: a released calibration set and a generated sweep

The paper measures threshold unreliability in a released calibration set and a generated decoding sweep. Clustering substantially reduces threshold-effective information, while dependence and cluster size interact in ways the standard plug-in correction misses.

  • 6.1 The live instance, measured: The released score is a proxy and atomic, so the 1.09× raw-score inflation contrasts with the 4.46× tie-broken measurement.The authors state that the actual nonconformity score was not released and would have its own exceedance correlation.
  • 6.1 The live instance, measured: 25,028 calibration rows behave like about 1,300 points, with ties broken and measured by cluster resampling.The measured dispersion ratio is 4.46×, compared with 4.39 from the subset-path estimator.
  • 6.1 The live instance, measured: [0.876, 0.905] is the released set’s 5th–95th coverage range, versus [0.888, 0.894] under exchangeability at n = 25,028.The clustered interval is 4.46× wider.
  • 6.1 The live instance, measured: Mean coverage is nearly unchanged, 0.8909 versus 0.8906, while a half-point shortfall occurs in 284.5 versus 4.0 per 1,000 deployments.The deployment-rate ratio is about 70×, showing that averaged coverage can conceal realized calibration risk.
  • 6.2 A second instance, generated, where the decode knob is ours to turn: Across beam widths 2 → 8, DEFF(0.90) rises 1.61 → 4.72 while ρI(0.90) falls from 0.606 to 0.531.The design-effect increase is driven by larger families, not by rising per-unit dependence.
  • 6.2 A second instance, generated, where the decode knob is ours to turn: Quadrupling family size reaches 943 effective points, while extrapolation to ten times the prefixes gives 1,029; doubling questions buys about eight hundred.The measured response implies breadth beats depth by roughly four, rather than the fixed-dependence reading’s factor of sixty.
  • 6.1 The live instance, measured: 30.8 = 5.55 plug-in prediction exceeds the 4.46 measured ratio because informative family sizes induce over-correction.The gap shrinks in a restricted size band and disappears in a synthetic control with the identical size profile but no size–score coupling.
  • 6.1 The live instance, measured: Family size correlates with family mean score at Spearman −0.42, and reweighting by question changes coverage from 0.891 to 0.841.The paper notes that the released procedure does not specify whether the guarantee is interpreted per prefix or per question.

7 Why the distribution has gone unnoticed

The distribution of realized coverage has gone unnoticed because existing fields study its ingredients separately or report means and bounds rather than the deployment-level distribution. The paper frames its contribution as composing level-dependent exceedance correlation with a threshold estimated from the same clustered sample.

  • 7 Why the distribution has gone unnoticed: The paper claims novelty for composing level-dependent correlation with a threshold estimated from the sample it governs, rather than for its individual ingredients.Theorem 1 is presented as a composition of six ingredients with prior owners.
  • 7 Why the distribution has gone unnoticed: The failure is first-order in coverage dispersion but only O(1/b) in its mean.At b = 50, mean coverage moves by 0.34 percentage points while the 5th percentile moves by nearly two.
  • 7 Why the distribution has gone unnoticed: Mean coverage ranges from 0.9004 to 0.8958 across ρ values while dispersion doubles.The mean is nearly preserved in an unsafe direction, but the dispersion penalty does not shrink with added clusters.
  • 7.1 Who owns each ingredient: Design-effect work evaluates binary-outcome dependence at a fixed level, while copula work traces level dependence without converting it into effective sample size.The paper argues that each literature stopped at the ingredient required by its own question.
  • 7.1 Who owns each ingredient: Binary-outcome sample-size work relates ICC to prevalence but does not address a threshold estimated from the same sample it governs.The paper identifies this missing composition as the boundary between that literature and its own result.
  • 7.1 Who owns each ingredient: Survey sampling, generalizability theory, and standards work already contain related design-effect or variance components, but not this threshold-level composition.The paper explicitly disclaims novelty for applying design effects to AI evaluation generally.
  • 7.2 The pattern, field by field: Conformal dependence literature generally supplies coverage bounds, while the closest hierarchical results characterize bounds or restore validity procedurally rather than giving a dispersion law.The cited works include mixing-budget bounds, CDF pooling, subsampling, and second-moment bounds.
  • 7.2 The pattern, field by field: The paper does not challenge marginal validity when the test point is exchangeable with calibration units, but its target configuration is not exchangeable because the test point is an independent draw outside the clusters.Under that configuration, the cluster-permutation group leaves the test point fixed and licenses no rank guarantee.

8 What to do instead: a recipe, and when to refuse it

The paper recommends estimating effective sample size from threshold exceedance dependence, reporting uncertainty by operating level, and refusing the correction when key assumptions fail. It also identifies estimator failures, finite-cluster uncertainty, and practical sampling choices that affect reliability.

  • Recipe: Estimate the exceedance-indicator ICC at each threshold and report the resulting effective sample size alongside the raw calibration size.Threshold the scores first, then compute a one-way random-effects ICC on the resulting 0/1 variable; no distributional assumption is needed.
  • Recipe: Use the size-biased mean cluster size, because it can differ from the ordinary average by a factor of two in realistic profiles.When cluster sizes predict scores, the plug-in correction can over-correct; on the released set it predicted dispersion 5.55× versus 4.46× measured.
  • Recipe: Report coverage dispersion, not only its mean, because the 5th percentile of the effective-size Beta law reflects what a single deployment experiences.With few hundred clusters, the point estimate can be near-unbiased while the 95% interval at p = 0.99 spans about four-fifths of the estimate.
  • Recipe: Report effective sample size separately for each coverage level, since the design effect changes with α rather than belonging to the dataset alone.The rank k also matters: k = ⌊α(n + 1)⌋ can silently halve the level being run.
  • When to refuse: Refuse the correction when cluster size is informative about scores, because size–score coupling biases coverage at first order.A simple family-size versus family-mean-score check identifies whether this correction is appropriate; the released set showed a 4.99-point effect under the per-question guarantee.
  • Sampling choice: Doubling prefixes per question buys about 70 effective points under the measured response, while four prefixes are optimal when a question costs sixteen times one prefix.The released set’s 61.3 prefixes per question would require a question cost 3,682 times one prefix to be justified by the stated cost model.
  • When to refuse: Do not substitute score correlation, multiply two design effects, or trust the pair estimator with unequal family sizes.The score-correlation substitution can be wrong when score correlation vanishes but exceedance correlation does not; the pair estimator can even return ρI > 1.
  • Failure of the old correction: The published i.i.d. correction yields P(C ≥0.90) = 0.737 instead of 0.90 on the clustered released set.The guarantee it was invoked to buy is therefore void for that calibration design.

9 The result governs any threshold set at a sample quantile

The theorem applies beyond conformal prediction to any threshold chosen as a sample quantile, including latency targets, medical imaging, clinical standards, and other clustered settings. These applications share level-dependent threshold uncertainty, while some extensions remain narrower or finite-sample.

  • General scope: Theorem 1 governs any decision threshold set at a sample quantile of clustered data, not only conformal thresholds.Its scope includes multiple literatures that use finite clustered samples to set operational cutoffs.
  • Tail latency: Tail-latency objectives at p = 0.95 and p = 0.99 are especially sensitive because level-dependence is strongest there.Requests cluster by user, session, or host while metrics are measured per session, making score-correlation heuristics misleading.
  • Tail latency: General SLO and APM tooling reports pooled p95/p99 logs without clustering correction, whereas GrowthBook uses the exceedance indicator.The paper supplies a closed form for the numerically computed correction and makes its level dependence explicit.
  • Medical imaging: Clustered medical-imaging conformal prediction repeatedly identifies exchangeability violations but lacks an effective-sample-size analysis.A weighted formulation exists, but its empirical investigation in medical applications remains lacking.
  • Related settings: Two-way clustered tail-quantile results are asymptotically Gaussian, so a crossed effective sample size not represented by the two-parameter form is a finite-sample issue.This narrows the paper’s crossed-dependence extension rather than replacing its clustered result.
  • Clinical standards: Clinical reference standards set one-sided centile thresholds from finite samples, often recruited at few sites, placing them within Theorem 1’s scope.For the WHO growth reference, published variance components imply design effects between 1.9 and 4.6 for the −2 SD cutoff depending on age.
  • Clinical standards: The WHO growth-reference precision remains unresolved because six sites cannot pin down the between-site variance component.Propagating the study’s uncertainty spans design effects from 1 to about 41, without claiming the published standard is wrong.

10 What is not proved, and what is not measured

The paper’s guarantees and approximations have explicit scope boundaries: some results are asymptotic, tail accuracy degrades, unequal sizes require conditions, and informative sizes or limited copula checks restrict conclusions. One selection channel remains only partly correctable.

  • Asymptotic scope: Theorem 1 is asymptotic, while its finite-sample Beta approximation is moment-matched and the O(n−2) remainder is not bounded.A uniform first-order lattice Edgeworth expansion at the CDF level remains unproved.
  • Tail scope: The approximation error rises from within 0.1% at p ∈ {0.80, 0.90, 0.95} to 0.5% at p = 0.99.The formula is intended for regimes where the exceedance count is not itself small.
  • Cluster-size scope: The theorem’s clean single-parameter statement assumes equal cluster sizes, while ragged families require the size-biased mean and a fixed size profile.The ragged-family extension is validated to 1.6% across four profiles, but its conditioning does not survive informative sizes.
  • Validation scope: Copula validation covers four families but only a few configurations, and the Φ2 form of Corollary 2 is Gaussian-specific.The theorem itself is not restricted to Gaussian dependence.
  • Selection channel: Informative cluster sizes bias coverage at first order, and the paper provides no corrected estimator for that channel.On the PRM artifact the measured effect was 4.99 points, 69× the Conjecture 1 drift under the per-question guarantee, but identically zero under the per-prefix reading.
  • Selection channel: The paper’s selection-channel appendix addresses repair strategies, but the law in §2 does not govern that channel.The appendix concerns thresholds taken from tilted samples whose selection mechanism is not identified from that sample alone.

A.1 Label provenance and the sign rule

Self-referential label corruption can move realised coverage either above or below nominal, depending on how corruption relates to the score. The paper distinguishes this sign rule from corrections requiring assumptions that self-labelling violates.

  • Observed effect: 2.46× nominal realised error occurs when a selective-answering gate is certified against a reference model’s own labels rather than ground truth.Random label noise at the same 21% error rate instead moves the threshold to 0.08× nominal.
  • Sign rule: Fixed-rate label corruption can produce over-coverage or under-coverage according to the corruption structure.Class-uniform flipping and class-prior-driven corruption yield opposite directions in the cited prior work.
  • Scope boundary: The paper does not import existing corrections because their conditional-independence assumptions fail for self-referential labels.Those methods also require a clean labelled subset, precisely the resource motivating self-labelling.

A.2 The tilt, and the identification boundary

Selection on the score tilts the calibration distribution away from the population distribution, so a calibration quantile need not deliver the corresponding population coverage. The resulting gap is not identified when the selection mechanism is unknown.

  • The identification boundary: Selection through covariates is a covariate shift with an observed weight, whereas selection through labels is not a function of covariates.The distinction places the two channels on opposite sides of an identification boundary.
  • The tilt: The observed calibration law under score-dependent sampling is a tilted version of the population score law.Each unit enters independently with probability π(s), so the sample distribution reflects selection on the score itself.
  • The tilt: A split-conformal threshold converges to the selected-law quantile, while realised coverage is evaluated under the unselected population law.Coverage therefore composes two different distribution laws rather than one common calibration-and-test law.
  • The identification boundary: Unknown score-dependent selection prevents point identification of the population distribution and its corresponding realised coverage.Observationally equivalent selection mechanisms can produce the same calibration distribution while implying different population laws.
  • The identification boundary: A small selection correlation can dominate the error budget even when the recorded sample is very large.For the 2016 CCES, a defect correlation of −0.005 made 2.3 million respondents carry the mean squared error of a simple random sample of about 400.

A.3 The calibrated instance

The calibrated construction makes non-identification concrete by producing identical calibration samples from two different population-and-selection mechanisms. Their realised coverage differs by a first-order amount that can be large at a tail threshold.

  • Observational equivalence: Two mechanisms generate exactly the same calibration-sample law: uniform sampling from Uniform(0, 1), or score-dependent selection from a tilted population.Under mechanism B, f′(s) = 1 + a(2s −1) and π′(s) = (1 −a)/f′(s), yielding the same observed calibration density.
  • Coverage consequence: The coverage gap is a p(1 −p), first order in selection strength, while the design-effect contribution enters at second order.The two mechanisms satisfy F(p) = p and F′(p) = p −a p(1 −p).
  • Coverage consequence: 8.1 percentage points of coverage error occur at p = 0.90 and a = 0.90 despite indistinguishable calibration samples.With n = 200,000 draws per arm, the two-sample KS test gives D = 0.00236 and p = 0.63.
  • Calibration setting: The construction uses a finite likelihood-ratio range Γ = 19 rather than an arbitrarily adversarial departure.For a = 0.90, w(s) ranges from 1 −a to 1 + a, giving Γ = (1 + a)/(1 −a) = 19.

A.4 Three repairs, and what each costs

Three repairs address different parts of the selection problem: known positive weights, sensitivity bounds, and a clean random calibration slice. Their costs differ in assumptions, sharpness, and data requirements.

  • Known weights: Known selection probabilities bounded away from zero permit exact recovery of the population law by self-normalised inverse weighting.The known-weight estimator has consistency and a functional CLT even without graph connectedness.
  • Known weights: 1/π′ restores realised coverage to 0.9000 at a = 0.90 without supplying a sensitivity parameter.The correction closes the full 8.1-point gap, but the cost appears in dispersion rather than coverage level.
  • Known weights: The correct weighted design effect uses the weighted exceedance residual, not the raw score or unweighted indicator.At Γ = 19, within-cluster r = 0.6, and m = 4, substituting the indicator correlation overstates dispersion by 6%.
  • Known weights: At Γ = 19, the weighting design effect is 1.27 at p = 0.5, 1.79 at p = 0.90, and 1.84 at p = 0.95.At the tail level, Kish’s p = 1/2 formula understates the cost by 40%.
  • Clean slice: Hard cut-off sampling is irreparable without additional information because unsampled units have no support.A random clean slice instead avoids the tilt; at Γ = 19 its crossover is n0 = 12 against 25,000 selected observations, with n0 ≥ 9 required at p = 0.90.
  • Scope and costs: The impossibility applies when π is unknown, and positivity alone does not solve misspecified estimated weights or the absence of recorded selection information.The paper reports that no reviewed inference-time pipeline records either an auxiliary unselected sample or the acceptance probability needed for the parameter-free repair.

A.5 Four neighbours mark the boundary

Adjacent literatures address related selection problems, but they differ in whether the threshold is given, the selection weights are available, or the target law is only partially identified. These distinctions delimit where existing repairs apply.

  • Selective labels: Selective-label bounds study a given decision threshold, whereas this setting estimates the conformal threshold from a tilted calibration sample.The threshold and evaluation distribution therefore inherit different selection roles.
  • Weighted conformal prediction: Existing weighted-conformal repairs rely on selection being conditionally independent of the outcome given covariates and on weights that are functions of covariates.Outcome-dependent selection shifts the conditional distribution and invalidates that repair form.
  • Weighted conformal prediction: The paper’s score-dependent weight can be monotone, but non-monotone selection leaves the direction of coverage error unrestricted.The cited appendix supplies a direction for the monotone construction, not a general sign result.
  • Partial identification: Minimax calibration methods handle unidentified target laws by optimizing over an ambiguity set rather than assuming point identification.The paper reports this as related evidence and does not develop the partial-identification problem itself.
  • Scope boundary: The paper’s scope is narrower than a claim about all inference-time systems because reviewed pipelines do not record the auxiliary sample or acceptance probability needed for repair.Sensitivity information can buy validity without calibration, but the one-sided repair is more expensive.

Appendix B: Proofs, remarks and derivations deferred from §2

The appendix supplies technical qualifications behind the paper’s main results, including atomic-score handling, finite-sample approximation, and level-centering details.

  • Atomic scores fall outside the theorem, and random tie-breaking instead analyzes the augmented score S + εU.The resulting dispersion describes the randomized procedure rather than the original atomic-score procedure.
  • The limiting variance may be evaluated at p0 while finite-n approximations are centered at pn, because their difference vanishes at rate √n/(n + 1).Continuity of ρI makes replacing ρI(pn) with ρI(p0) asymptotically harmless.
  • The Beta distribution used throughout is moment-matched to Theorem 1 rather than proved as the exact finite-sample law.At ρI = 0, the exact Beta law differs slightly from the matched approximation, and accuracy away from that case is measured by simulation.

B.4 Step 3 of the proof in detail

The detailed proof derives the clustered quantile representation and identifies the level-dependent exceedance design effect as the source of threshold dispersion and mean drift.

  • Step 3 of the proof in detail: The Bahadur representation for the clustered sample quantile follows from the cluster-level CLT and regularity of the score density near qp.The proof applies Ghosh’s result after establishing the needed empirical-process behavior across independent clusters.
  • Step 3 of the proof in detail: Within-cluster dependence inflates shrinking-interval empirical-process variance by 1 + (m −1)ρπn, remaining bounded by m for fixed cluster size.This bound permits the substitution required in the quantile proof.
  • Step 3 of the proof in detail: The correction applies to realised coverage at a data-chosen order statistic, using the level-indexed exceedance ICC ρI(t), not continuous-error correlation for regression coefficients.The distinction is the paper’s contribution beyond the classical design-effect substitution.
  • Step 3 of the proof in detail: The drift extension to unequal cluster sizes is supported by measurement rather than covered by Proposition 2’s fixed-m proof.Ragged cluster sizes create a genuine triangular-array problem, and the paper labels the extension a conjecture.
  • Step 3 of the proof in detail: Coverage is represented as the k-th order statistic of probability-transformed scores, with count variance nt(1 −t)D(t) and D(t) = 1 + (m −1)ρI(t).The level dependence of D(t) generates the formal second-order drift expansion.

B.8 Corollary 3 and the marginal upper bound

The marginal upper-bound corollary shows that positive coverage drift can eventually exceed split conformal’s finite-sample slack, while the released artifact provides mixed empirical evidence for the required level trend.

  • Corollary 3 and the marginal upper bound: 5.1 × 10−5: at m = 48, positive drift exceeds the split-conformal upper bound under ρI(p) = 0.474.The bound holds through m = 12, lies within the ceiling remainder at m = 16 and 20, and is exceeded from m = 24 onward.
  • Corollary 3 and the marginal upper bound: The bound’s failure is driven by the sign of ρ′I, while increasing m only reduces the slack that the drift must overcome.Matched constructions with ρ′I < 0 remain inside the bound at every m.
  • Corollary 3 and the marginal upper bound: The paper recommends estimating ρI at adjacent achievable levels and checking the sign of their difference before relying on the safe-direction reading.This follows because cached prefixes and deterministic decoding branches are described as tail-dependent.
  • Corollary 3 and the marginal upper bound: Across eight released levels, estimated ρI rises from 0.436 at p = 0.674 to 0.537 at p = 0.834, then falls to 0.427 at p = 0.915.Bootstrap intervals overlap throughout, and Spearman’s rank correlation is −0.19 at p = 0.65, so the trend is not decisive.
  • Corollary 3 and the marginal upper bound: The computational archive checks preconditions, reproduces exact independent-cluster controls, cross-validates implementations, and records negative computational results.These checks include deterministic exact computation and independent reproduction of the released instance’s family structure and design effect.
Loading 2608.21262v1…