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

Certify or Refuse: A Cross-Model Map for Selective Risk Control with Coverage Floors under Covariate Shift
Aug 11, 2026Jiamiao Liu, Dewen Qiao, Yu Zhang +1Selective Prediction Covariate Shift
Department of Information, Xinqiao Hospital Army Medical University (Third Military Medical University) Chongqing 400037, China
Finite-sample certification of coverage regret for budgeted document selection under adaptive stratified auditing
Oct 13, 2026Nora SerdyukovaRegret Minimization Selective Inference
Department of Statistics, University of Concepcion, Chile
How Many Labels Does Model Choice Need? Certificates and Budgets for Selective Prediction
Sep 16, 2026Tetsuji KuboyamaModel Selection Selective Prediction
Computer Centre, Gakushuin University

Aug 11, 2026J/K move · Enter open · S save

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

Jiamiao Liu, Dewen Qiao, Yu Zhang, Xuetao Chen

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

Selective Prediction Covariate Shift

Open paper AskPDF arXiv

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.

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