Identities, Not Pairs: Distribution-Free False-Accept Control for Embedding-Based Verification

Salim Khazem

stat.MLOct 26, 2026

Identities, Not Pairs: Distribution-Free False-Accept Control for Embedding-Based Verification

Authors: Salim Khazem

Organizations: Talan Research Center

Abstract

Embedding-based verification often calibrates a false-accept threshold from all impostor pairs among $m$ identities, although these pairs share identities. We characterize a worst-case limit: when hub identities score highly against a fraction $ρ$ of the population, a calibration-only threshold with marginal false-accept rate (FAR) at most $α$ under every identity-exchangeable law reaches the hub score on hub-free calibration sets with probability at most $(m+2)α/(2ρ)$ . Uniformly accepting near that score at levels well below $ρ/m$ therefore requires trial information. We propose COVE, which ranks the trial pair among all $N=\binom{m+2}{2}$ pairs formed by augmenting the calibration units with the probe and reference. Under identity exchangeability, its marginal FAR is at most $\lfloorαN\rfloor/N$ , with first possible acceptance at $1/N=O(1/m^2)$ . The rule also retains this guarantee with a fixed symmetric cohort-normalized score using an independent cohort. On 6 benchmarks and 8 frozen encoders, realised FAR was consistent with the exact bound. Where both valid calibration-only baselines accepted nothing, COVE retained a median $100\%$ of the sampled oracle's true-accept rate over reliable comparisons. In contrast, an empirical quantile over dependent pairs reached 2.87 $\,α$ FAR, and a binomial upper confidence bound over pairs missed its nominal 95% conditional-FAR target in up to 55% of calibration draws. Symmetric CSLS raised COVE's true-accept rate by up to 4.3-fold in the tested settings. The code is available in https://github.com/salimkhazem/Cove.git

Figures & tables

Figure 1: Identities, not pairs. Left: smallest level at which each valid rule can accept for some score arrays (lines), and on SOP/DINOv2-B (markers: smallest grid level with non-zero TAR); below the shaded boundary Theorem 1 bounds the probability that a calibration-only threshold reaches the hub score when

\rho=1

. Right: true-accept rate against the target level at

m=1000

; crosses mark levels at which the empirical quantile’s realised FAR exceeds

1.1\alpha

; dotted lines mark

1/N

and

(2m+1)/N

dataset	encoder	$m$	$\alpha$	FAR/level	COVE	oracle	id. boot.	FAR $/\alpha$	bin. UCB	id. boot.	$>$ level
				COVE	TAR			quantile	% cond. FAR $>\alpha$		% FAR
Cars	CLIP-B/16	60	$10^{-3}$	1.03 $\pm$ 0.08	0.074	0.080	0.085	1.3	–	26	41
Cars	DINOv2-B	60	$10^{-3}$	0.94 $\pm$ 0.08	0.057	0.064	0.059	1.4	–	20	32
Cars	ResNet-50	60	$10^{-3}$	0.99 $\pm$ 0.09	0.015	0.016	0.017	1.4	–	24	34
CUB	CLIP-B/16	60	$10^{-3}$	0.91 $\pm$ 0.08	0.063	0.069	0.067	1.3	–	21	34
CUB	DINOv2-B	60	$10^{-3}$	0.97 $\pm$ 0.09	0.167	0.178	0.169	1.2	–	24	34

Table 1: Core results, one level per core pair (random identity split; 500 draws per cell, the first 200 for the identity bootstrap); at each level both valid calibration-only rules accept nothing. COVE: realised FAR over its level

\lfloor\alpha N\rfloor/N

, 95% interval. TAR: true-accept rates (oracle at COVE’s level). Quantile: realised FAR

/\alpha

. Cond. FAR: % of draws whose conditional FAR exceeds

\alpha

for the two rules claiming 95% conditional control (nominal 5%; “–”: accepts nothing). Last column: % of draws whose sampled FAR exceeds COVE’s level (COVE claims marginal control only).

Figure 2: Evidence. (a) Realised FAR against the target level for every random-split real-data cell and level (approximate 95% intervals for the mean over draws): COVE against its level, the empirical quantile and the conformal p-value over pairs against

\alpha

; the hub model is in Appendix C . (b) Fraction of draws with estimated conditional FAR above

\alpha

for nominal 95% recipes, against

m

(median and range over dataset/encoder pairs,

\alpha=10^{-3}

; nominal 5% dashed). (c) Probability that COVE accepts a genuine trial the oracle accepts, by the trial’s hub load, pooled over the encoders of each dataset; 50 draws,

m=60

\alpha=10^{-2}

(CUB, Cars),

m=300

\alpha=3\cdot 10^{-4}

(ImageNet),

m=1000

\alpha=10^{-4}

(SOP).

data	encoder	$m$	$\alpha$	raw	CSLS	S-norm
ImageNet	CLIP-B/16	300	$10^{-4}$	0.073	0.092	0.095
ImageNet	DINOv2-B	300	$10^{-4}$	0.272	0.257	0.254
ImageNet	ResNet-50	300	$10^{-4}$	0.294	0.313	0.299
SOP	CLIP-B/16	1000	$10^{-5}$	0.058	0.220	0.083
SOP	CLIP-B/16	1000	$10^{-4}$	0.128	0.402	0.190
SOP	DINOv2-B	1000	$10^{-5}$	0.099	0.156	0.068

Table 2: True-accept rate of COVE with the raw score and with two cohort normalizations (Corollary 1 ), at the same guaranteed level, on the same 200 calibration draws and trials (random identity split).

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 3: Realised FAR against the target level for every random-split cell: real data (left) and the hub model (right), with 95% confidence intervals for the mean over calibration draws.

data	encoder	FAR/level med.	max	TAR % med.	min	$n$
Cars	CLIP-B/16	1.01	1.03	99	90	9
Cars	DINOv2-B	0.99	1.02	99	89	9
Cars	ResNet-50	0.99	1.03	100	92	8
CUB	CLIP-B/16	1.00	1.04	100	90	9
CUB	DINOv2-B	1.00	1.08	97	89	9
CUB	ResNet-50	1.01	1.06	102	91	9

Appendix

Table 3: All datasets and encoders (raw score, random identity split). COVE’s realised FAR over its level (median and maximum over

m

and

\alpha

), and COVE’s true-accept rate as a percentage of the oracle’s where both valid calibration-only rules are trivial and the sampled oracle is reliable (median, minimum, number of (cell, level) combinations).

split	data	encoder	median	range	median	max	% draws
			COVE FAR/level		quantile FAR $/\alpha$		binomial
category	SOP	CLIP-B/16	0.78	0.61–1.16	0.86	2.74	2
category	SOP	DINOv2-B	0.40	0.33–0.77	0.40	1.10	0
category	SOP	ResNet-50	1.47	0.81–2.48	1.47	3.20	58
fixed	ImageNet	CLIP-B/16	0.76	0.64–0.90	0.83	1.16	2
fixed	ImageNet	DINOv2-B	1.00	0.40–1.07	1.01	1.08	10

Appendix

Table 4: Realised FAR when calibration and test identities are not exchangeable: the official fixed split, and calibration on six SOP super-categories with testing on the other six. COVE: realised FAR over its level (median, range over

m

and

\alpha

). Quantile: the empirical quantile’s realised FAR over

\alpha

where

\alpha\binom{m}{2}\geq 1

(median, max). Binomial: median percentage of draws whose calibration-conditional FAR exceeds

\alpha

(binomial UCB).

Biometric Identification

Biometric identification matches or verifies people and animals using distinctive physical, physiological, or behavioral signals.

See all 129 papers

Certified by Abstention: Distribution-Free Guarantees for Chain-of-Thought Verifiers at Small Calibration Budgets
Oct 7, 2026Arjun BalajiSelective Prediction Conformal Prediction
Columbia University
Conformal Prediction under Partial Verification
Oct 7, 2026Zijun Yu, Yu Gu, Vahid Partovi Nia +1Conformal Prediction
McGill University · Polytechnique de Montréal
JuryProbe: An Empirical Consensus-Risk Diagnostic for Routing Reference-Free Factuality Judge Panels to Grounded Verification
Aug 20, 2026Tianxin Zhou, Ruixi LinCorrelated Errors in Language Models LLM-as-a-Judge
Independent Researcher

Oct 7, 2026J/K move · Enter open · S save

Certified by Abstention: Distribution-Free Guarantees for Chain-of-Thought Verifiers at Small Calibration Budgets

Arjun Balaji

Columbia University

Selective Prediction Conformal Prediction LLM Abstention CoT Evaluation FDR Control

Open paper AskPDF arXiv

Signals that predict whether a chain-of-thought (CoT) trace is correct are compared by AUC, but deploying one requires a threshold with a guarantee. We ask what distribution-free selective guarantees deliver for CoT verifiers at realistic calibration budgets of tens to a few hundred labelled problems, using seven open models, five verifier signals and 37,000 graded traces. The central observation is validity by abstention: an

(α,δ)

-valid procedure that issues a certificate with probability

P_{\rm fire}

bounds the failure probability of an issued certificate only by

δ/P_{\rm fire}

, so a certificate that rarely fires can be valid and wrong every time it is used. In a simulation with known risk the standard certificate fails in at most 0.3% of calibration draws but in up to 69% of those in which it fires. A certification floor and a lattice condition for Benjamini-Hochberg conformal selection explain why certificates abstain at these budgets, and the data bear them out: the standard certificate returns nothing or a large accepted set, and an unreadable residual-stream probe buys two to three times the coverage of the readable signals, an edge a cross-fitted reconstruction cannot recover linearly from the readable features. We then give a floor-started fixed-sequence certificate, valid without monotonicity assumptions, that covers more than the Bonferroni certificate on every model-signal pair and raises coverage at the non-vacuous target

0.75π_0

from 0.05 to 0.16, although the floor keeps absolute coverage small. Finally, a certificate cannot see what matters after deployment: under benchmark shift the error among accepted traces tracks the new task's base error, and under best-of-

n

selection against the verifier it rises past the target while the empirical failure frequency stays below

δ

, because abstention absorbs the failures.

Abstract

Biometric Identification

Explore similar work

Certified by Abstention: Distribution-Free Guarantees for Chain-of-Thought Verifiers at Small Calibration Budgets

Conformal Prediction under Partial Verification

JuryProbe: An Empirical Consensus-Risk Diagnostic for Routing Reference-Free Factuality Judge Panels to Grounded Verification