The Price of Choice in Selective Prediction

Daniel Cieślak; Andrzej Czyżewski

cs.LGOct 21, 2026

The Price of Choice in Selective Prediction

Authors: Daniel Cieślak, Andrzej Czyżewski

Organizations: Gdańsk University of Technology Gdańsk, Poland

Abstract

A selective classifier may be claimed to satisfy a risk-coverage contract if some rule from a predeclared menu (a threshold or a union of $K$ score intervals) attains coverage at least $κ$ and error at most $α$ . Refuting this existential claim requires ruling out every permitted rule. The intersection-union test (IUT) achieves validity without a multiplicity correction, but its sample cost can increase with menu richness. We characterize this cost and compare it with the optimal audit. For a fixed interior risk target $α$ and gap $γ$ , the minimax sample size for K-interval menus at coverage floor $κ$ is $K(1-κ)/(κγ^2)$ , up to logarithmic factors, in the stated small-gap, large-menu regime; exact IUT attains this rate. The lower bound holds even with a known score distribution, while the upper bound extends to menus of VC dimension $d$ . Procedures that refuse to reject whenever any rule appears feasible on the audit sample can pay a linear $K$ cost even when a square-root rate is possible. Reference-free testing reaches a smaller scale under constant-risk alternatives, whereas unknown heterogeneous risks can make the linear cost unavoidable. In simulations with $K=4$ , the raw menu cost varies 7.7-fold between $κ=.5$ and $κ=.95$ ; after theorem-motivated normalization the endpoint values differ by approximately 5%. Held-out experiments with three VLM judges show positive exact-hiding windows in all 60 split-specific confidence-gate families, with 28/30 contracts chosen on audit-A remaining hidden on untouched audit-B. On a cleaner multi-annotator target, hiding is weaker and transfers in 3/10 resplits. Frozen image and multimodal classifiers show boundary behavior consistent with the IUT guarantee and strong power relative to practical certificates.

Figures & tables

Known to auditor	Power required against	Minimax sample size	EFC certificates
Menu only	$\mathcal{P}_{\gamma}$ (robust margin $\gamma$ )	$K$ intervals, fixed $\kappa$ : $\tilde{\Theta}\big(\frac{K(1-\kappa)}{\kappa\gamma^{2}}\big)$ (Thm. 1 )	IUT: $\tilde{O}\big(\frac{d(1-\kappa+\gamma)}{\kappa\gamma^{2}}\big)$ , VC dim. $d$
Reference $P_{0}$	$P_{0}$	$\Theta(\sqrt{k}/\gamma^{2})$ (Thm. 2 )	$\Omega(k/\gamma^{2})$ ; IUT: $\Theta(k/\gamma^{2})$ (Thm. 3 )
Cells only	constant risk, any marginal	$\Theta(\sqrt{B}/\gamma^{2})$ if $\gamma\leq(2B)^{-1/4}$ (Thm. 4 )	$\Omega(B/\gamma^{2})$ at $P_{0}$
Cells and marginal	heterogeneous risk	$\tilde{\Theta}(B/\gamma^{2})$ (Thm. 5 )	IUT: $O(B/\gamma^{2})$

Table 1: Minimax sample sizes of valid audits (up to constants;

\tilde{\Omega},\tilde{O}

hide logarithms). Row 1: robustly infeasible alternatives

\mathcal{P}_{\gamma}

(Section 3 ); the interval bounds need large

K

, an interior risk target

\alpha

bounded away from 0 and 1, and

\gamma\lesssim\min\{\kappa,1-\kappa\}/\log K

. Rows 2–4: the sign families of Section 4 (

\kappa=1/2

M=2B

cells,

k=B

in rows 3–4, large

B

\gamma\leq\gamma_{0}

). “Valid” means level

\delta

over the unrestricted null.

Figure 1: Menu richness costs

K

times the abstention odds. Left: menu cost of the exact IUT, scaled by

\gamma^{2}

, for five coverage floors. At

K=4

it falls 7.7-fold from

\kappa=.5

\kappa=.95

. Right: the same costs divided by

\frac{1-\kappa}{\kappa}\log\frac{e}{\min\{\kappa,1-\kappa\}}

lie within

2.32

–

2.82

K=4

and within

0.95

–

1.39

K=2

. At

\kappa\geq.9

the curves flatten for

K\geq 8

because the abstained region spans only

M(1-\kappa)\leq 6.4

cells, so extra intervals do not enlarge the realized admissible rule set in this finite benchmark. Monte Carlo crossings from 250 audits per point.

Figure 2: The IUT and the information envelope have different scales (

B=256

). Left:

\gamma^{2}n_{80}

at two gaps; the curves nearly coincide, as

\gamma^{-2}

scaling predicts. Right: local log–log slopes in

k

. The IUT’s slope rises from 0.25 to 0.72 towards the proven exponent 1, the envelope’s from 0.28 to 0.43 towards

1/2

; the range is pre-asymptotic. Crossings are in Table 7 (Appendix H.1 ).

Target	judge	pos. A/B	A $\to$ B	med. $W_{B}$
MLLM-Judge	LLaVA-Critic-7B	20/20	10/10	4.97
MLLM-Judge	Gemini 2.5 Flash	20/20	10/10	5.91
MLLM-Judge	Phi-4 reasoning vision	20/20	8/10	4.83
Polaris (multi-annotator)	LLaVA-Critic-7B	20/20	3/10	0.33

Table 2: Auditing the auditors. Held-out exact-hiding windows for six predeclared confidence gates at

\kappa=.60

and serious judge error

L=\mathbf{1}\{|\hat{y}-y_{\rm human}|>1\}

. Policies are frozen on a disjoint calibration third. “pos. A/B” counts positive windows over audit-A and audit-B; “A

\to

B” asks whether the midpoint contract selected on A remains hidden on untouched B. Widths are median audit-B windows in percentage points.

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

$L$	$E_{L}$	$2LE_{L}$	$L$	gap	$2E_{L}$	$L$	max rel. error
1	0.12500	0.2500	2	0.13524	0.13524	2	1.4e-13
2	0.06762	0.2705	3	0.09186	0.09186	3	1.8e-11
3	0.04593	0.2756	4	0.06938	0.06938	4	1.6e-09
4	0.03469	0.2775
6	0.02325	0.2790
8	0.01747	0.2795

Appendix

Table 3: Numerical checks behind Theorem 5 . Left: best-approximation error of

\sqrt{u}

[0,1]

(the monomial LP is reliable in this range; values increase towards Bernstein’s constant

\beta_{*}\approx 0.2802

). Middle: optimal moment-matched gap from the dual LP versus

2E_{L}

. Right: largest relative error between the closed-form

\chi^{2}

series and direct Poisson summation over two parameter settings.

Figure 3: Unknown heterogeneity changes the exponent and eventually dominates. Left: 80%-power crossings of the two envelopes, scaled by

\gamma^{2}

. The known-reference crossing grows with fitted exponent

0.48

(theory:

1/2

); the heterogeneity crossing grows with exponent

0.80

, approaching

1-1/(2L+2)=0.83

for fixed

L=2

(the theorem lets

L\asymp\log B

). Right: their ratio falls from 12.5 at

B=64

to 0.71 at

B=262{,}144

. Because the constant-risk reference belongs to

\mathcal{P}_{\rm het}

, the larger crossing is the operative lower bound on

N(\mathcal{P}_{\rm het},\mathcal{H})

. Envelopes bound valid audits; they are not audits.

$B$	known $n_{80}$	heterogeneity $n_{80}$	ratio	$\Pr_{0}(G_{0}^{c})$	$\Pr_{1}(G_{1}^{c})$
64	32,484	2,600	12.49	0.123	0.238
256	58,713	10,108	5.81	0.003	0.055
1,024	111,210	29,743	3.74	0.000	0.001
4,096	205,041	86,773	2.36	0.000	0.000
16,384	417,386	249,855	1.67	0.000	0.000
65,536	846,246	742,665	1.14	0.000	0.000

Appendix

Table 4: Envelope crossings behind Figure 3 . Because the constant-risk reference belongs to

\mathcal{P}_{\rm het}

, the larger of the two crossings is the operative lower bound on

N(\mathcal{P}_{\rm het},\mathcal{H})

. The last two columns report how often a prior draw leaves its hypothesis; this probability is charged in the heterogeneity envelope.

Evidence	Signal	Reference fluctuation	Sample scale
Best (minimum) empirical policy risk	$\gamma$	$\sqrt{k/n}$	$k/\gamma^{2}$
Quadratic family evidence	$\gamma^{2}$	$\sqrt{k}/n$	$\sqrt{k}/\gamma^{2}$

Appendix

Table 5: Two statistical scales on a

k

-plateau (constants and the residual suppressed).

Source	$n$	$k=1$	$k=4$	$k=16$
Alternative	300	42.75	16.95	0.75
Alternative	500	75.20	47.60	7.00
Alternative	750	91.80	77.00	26.85
Alternative	1000	97.45	92.95	54.75
Alternative	1400	99.90	98.90	86.50
Alternative	2000	99.95	99.95	98.35

Appendix

Table 6: Additional sign-family simulation: observed rejection percentages, 2,000 replicates per cell. Null rows refer to a feasible boundary component.

	$\gamma=.04$			$\gamma=.02$
$k$	IUT	NP	ratio	IUT	NP
1	2,342	1,001	2.34	9,216	4,030
4	3,298	1,478	2.23	13,437	5,883
16	5,370	2,363	2.27	22,386	9,374
64	12,065	4,060	2.97	48,268	15,859
256	32,796	7,384	4.44	131,679	29,637

Appendix

Table 7: Measured 80%-power sample crossings for fixed

B=256

. NP denotes the simple-mixture envelope, not a full-null-valid test. Ratios compare IUT to that envelope; no minimax constant is inferred.

Figure 4: Exact IUT power on the two risk-gap grids. Bars are pointwise Wilson 95% intervals over 1,500 audits. These are Monte Carlo uncertainties, not confidence bands over the sample-size grid.

Population	Method	$n$	$K$	$\Delta=0$	$.02$	$.05$	$.10$	median frontier
CIFAR-10	IUT	500	1	0.006	0.13	0.92	1.00	0.044
CIFAR-10	IUT	500	4	0.000	0.06	0.92	1.00	0.037
CIFAR-10	Bonferroni	500	4	0.000	0.00	0.00	1.00	0.003
CIFAR-10	DKW	500	4	0.000	0.00	0.00	1.00	0.000
CIFAR-10	Total loss	500	4	0.000	0.00	0.03	1.00	0.000
CIFAR-10	IUT	500	16	0.000	0.05	0.92	1.00	0.037

Appendix

Table 8: Semi-synthetic audits, all configurations (

\kappa=.9

; 500 audits per cell for

n\leq 5{,}000

, 300 at

n=10{,}000

, 200 at

n=20{,}000

). Entries are rejection rates at

\alpha=r^{*}-\Delta

; the column

\Delta=0

is the level at the true boundary claim. For CIFAR-10,

\Delta=.10

gives

\alpha<0

and is rejected trivially.

Output / $K$	IUT	Bonf.	DKW	Rad.	Global
CIFAR-10 / 1	6.40	5.64	0.99	0.00	1.37
CIFAR-10 / 4	6.22	4.16	0.00	0.00	1.37
CIFAR-10 / 16	6.22	3.28	0.00	0.00	1.37
CIFAR-100 / 1	24.56	23.16	18.87	8.35	22.25
CIFAR-100 / 4	24.29	20.37	0.00	4.29	22.25
CIFAR-100 / 16	24.29	18.82	0.00	1.93	22.25

Appendix

Table 9: Fixed-split structured comparison at

\kappa=.9

. All frontiers are percentages, pointwise 95% under the stated sampling assumptions. Numerical uncertainty is included for the empirical-Rademacher comparator.

$K$	policy count	empirical	IUT	Bonf.	DKW	Rad.
1	$1.65\times 10^{3}$	19.996%	17.783%	16.552%	12.451%	2.947%
2	$4.26\times 10^{5}$	19.410%	17.783%	15.242%	4.660%	1.085%
4	$1.96\times 10^{9}$	19.348%	17.712%	14.135%	0.000%	0.000%
8	$9.10\times 10^{13}$	19.348%	17.712%	13.321%	0.000%	0.000%
16	$1.23\times 10^{17}$	19.348%	17.712%	12.584%	0.000%	0.000%

Appendix

Table 10: Held-out ImageNetV2 audit at

\kappa=.90

. Lower frontiers are 95% valid under each method’s stated probability budget. “Rad.” is the Monte-Carlo-certified empirical-Rademacher uniform-convergence comparator.

Figure 5: Held-out ImageNetV2 audit at

\kappa=.90

. The exact IUT frontier is shown with policywise Bonferroni, structured DKW, empirical-Rademacher uniform convergence, and the empirical frontier. This illustrates Proposition 1 ; it is not a minimax-optimality comparison.

$K$ \ $\kappa$	.3	.5	.7	.8	.9	.95
1	3,832	1,958	1,070	881	755	656
2	5,764	3,092	1,847	1,402	973	839
4	8,252	4,414	2,737	1,887	1,316	977
8	11,961	6,151	3,458	2,584	1,568	1,024
16	14,050	7,389	3,921	2,732	1,580	1,024
norm., $K=2$	0.60	1.07	1.32	1.28	0.95	1.39

Appendix

Table 11: Abstention-odds simulation: 80%-power crossings

n_{80}

of the exact IUT (

M=64

equal cells, constant risk

.14

\alpha=.10

\gamma=.04

, 250 audits per grid point, log-linear interpolation), and normalized menu costs

\gamma^{2}\{n_{80}(K)-n_{80}(1)\}\big/\{\frac{1-\kappa}{\kappa}\log\frac{e}{\min(\kappa,1-\kappa)}\}

		$\Delta=.05$		$\Delta=.02$		level		independence
Population	$r^{*}$	IUT	split LR	IUT	split LR	IUT	split LR	median $p$
CIFAR-10	0.074	500	10,000	5,000	$>50{,}000$	2.0%	0.0%	2e-17
CIFAR-100	0.262	2,500	50,000	10,000	$>50{,}000$	3.0%	0.0%	3e-19
ImageNetV2	0.193	2,500	50,000	10,000	$>50{,}000$	4.0%	0.0%	3e-17
CMU-MOSEI	0.136	1,000	50,000	5,000	$>50{,}000$	3.5%	0.0%	5e-10

Appendix

Table 12: A valid non-EFC audit on the frozen populations (

\kappa=.9

K=4

, 200 audits per point,

n\in\{500,1000,2500,5000,10^{4},2\times 10^{4},5\times 10^{4}\}

). Entries give the smallest grid size at which the rejection rate of the false claim

\alpha=r^{*}-\Delta

reaches 80%. “Level” is the largest rejection rate of a true boundary claim over all

n

and

K\in\{1,4,16\}

. The last column is the median

p

-value of a

\chi^{2}

test of cell–loss independence at

n=500

Selective Prediction

Selective prediction lets models answer only when sufficiently reliable, trading coverage for lower error through abstention, referral, or extra evidence gathering.

See all 281 papers

Aug 11, 2026

Certify or Refuse: A Cross-Model Map for Selective Risk Control with Coverage Floors under Covariate Shift

Certified selective predictors attain whatever coverage they attain; operators impose an automation floor: answer at least a

β

-fraction of shifted target traffic with at most an

α

-fraction of answers wrong. Under bounded-ratio covariate shift we prove the Floor Certification Map: once that floor must be certified alongside the selection-conditioned risk

α

, certification acquires a feasibility frontier and a two-resource complexity map, additive up to constants: risk in labeled source, the floor in unlabeled target samples. The rates are local, needing a regular frontier margin, slack below the local-regime threshold, and lattice conditions: pre-registered with a lattice margin for the upper bounds, compatible per-slack for the lower. The displayed split is the operational route; oracle weights also allow a labeled-source floor estimate. Three model-tagged results: a lower bound (Model-B), a matching oracle-weight upper bound (Model-A), and an implementable upper bound (Model-B') valid under a pre-registered exact stratified-shift model with nuisance cost priced explicitly. The match is across these models rather than a single-model minimax theorem, and necessarily so: over the full bounded-ratio class no unknown-weight procedure matches at any sample size (Model-B is inconsistent, witnessed at

α=β=1/2

). The nuisance's necessity is only partially settled. Complexity tracks a localized accepted-region functional, not global effective sample size (ESS), on both sides, though a fixed-ESS separation theorem is left open; both lower-bound axes vanish as

β\to0

, so the floor creates the map. Empirically, the registered bite family diverges with log-log slope

-2.002

within its pre-registered band; a 1,024-cell audit records 0 violations where the formal certificates fire; and a single-corpus SQuAD-to-NewsQA feasibility audit returns honest refusal.

Jiamiao Liu, Dewen Qiao, Yu Zhang +1

Department of Information, Xinqiao Hospital Army Medical University (Third Military Medical University) Chongqing 400037, China

Selective Prediction Covariate Shift

Ask PDF

Oct 13, 2026

Finite-sample certification of coverage regret for budgeted document selection under adaptive stratified auditing

Selecting a budget-constrained set of documentary fragments, for instance the knowledge base of a retrieval-augmented generation system, raises a statistical question: how much expected query coverage is lost relative to the best feasible selection when the query distribution is unknown? We construct finite-sample, distribution-free upper confidence bounds for this coverage regret that remain valid after data-dependent selection. A pilot stage may select the document set, screen competitors, build comparison networks and learn an annotation policy. Then an independent audit acquires relevance labels with probabilities that are constant within observable strata. The main result is a simultaneous bound for all retained coverage contrasts. The bound is made observable by empirical-Bernstein variance calibration or by a one-stage construction without calibration, and it accounts for estimated stratum proportions. For maximum-type coverage we prove variance contractions for swaps of redundant fragments, give a condition under which multiscale radii improve on a direct union bound, and show that such redundancy cannot be certified from samples alone. A simulation study confirms validity and quantifies the gains from variance calibration and certified redundancy.

Nora Serdyukova

Department of Statistics, University of Concepcion, Chile

Regret Minimization Selective Inference Confidence Region Estimation Algorithmic Auditing

Ask PDF

Sep 16, 2026

How Many Labels Does Model Choice Need? Certificates and Budgets for Selective Prediction

Classifiers can make identical predictions yet require labels to compare their selective performance: confidence ranks weight the same errors differently. We quantify this requirement for the area under the generalized risk-coverage curve (AUGRC). A prelabel lower bound rules out insufficient budgets. With all labels known, a covering linear program bounds the minimum number of labels sufficient to fix the winner (the certificate size) within

K-1

labels for

K

candidates. For fixed

K

, independent uniform orders and identical predictions, the prelabel bound approaches one quarter of the pool. With iid Bernoulli errors independent of the orders, every exact acquisition policy reads almost all labels asymptotically, although a two-candidate certificate needs only half. Across 108 feature-panel comparisons on nine datasets, disagreement labels settle every accuracy choice but no AUGRC choice. A 20% budget is ruled out in 96 conditions; certificates need 56-57% on average. On ten conditions with pretrained image classifiers, confidence-score choice reads 68-91% of 10,000 labels for exact selection and 50-67% with AUGRC tolerance

5\times10^{-4}

. An exact stopping test works with any acquisition order. Together, these results link confidence ranks to label budgets and certified model comparison.

Tetsuji Kuboyama

Computer Centre, Gakushuin University

Model Selection Selective Prediction Classification Statistical Learning Theory

Ask PDF

Abstract

Selective Prediction

Explore similar work

Certify or Refuse: A Cross-Model Map for Selective Risk Control with Coverage Floors under Covariate Shift

Finite-sample certification of coverage regret for budgeted document selection under adaptive stratified auditing

How Many Labels Does Model Choice Need? Certificates and Budgets for Selective Prediction