Identities, Not Pairs: Distribution-Free False-Accept Control for Embedding-Based Verification: what it means for business leaders

A conformal test that ranks a verification pair against every pair in the calibration set gives a provable false-accept bound at levels that pair-quantile thresholds cannot reach when some identities resemble many others.

1. What the method is

COVE is a decision rule for one-to-one verification with frozen embeddings. Given a probe image, a reference image and a calibration set of n images from n distinct identities, it accepts the pair as the same identity only if the pair's similarity ranks within the top fraction alpha of all pairs formed from the n plus 2 units, calibration pairs and cross pairs included, with ties counted against acceptance. The guarantee is distribution-free: if the trial's two identities come from the same population as the calibration identities, the probability of accepting two different identities is at most alpha, averaged over calibration draws and trials. Acceptance becomes possible at a level of order one over n squared, where the paper proves any threshold set from calibration alone can only be guaranteed at order one over n once hub identities exist. The bound survives symmetric cohort normalization and was checked on 6 benchmarks and 8 encoders.

2. Why the method was developed

The standard recipe sets a false-accept threshold at a quantile of all impostor pair scores in the calibration set, often with a binomial confidence bound that treats those pairs as independent draws. They are not: every identity appears in n minus 1 pairs, and one identity that resembles many others, a wolf in biometric terms or a hub in retrieval terms, inflates many pair scores at once. The paper proves that under identity exchangeability, hubs force any calibration-only threshold to a resolution of order one over n, so reaching a false-accept rate of one in a thousand would need on the order of a thousand calibration identities rather than the few dozen that counting pairs suggests. Earlier work quantified the resulting uncertainty with bootstraps and correlated-binomial intervals, and cohort normalization heuristics reduce hub effects, but neither delivers a finite-sample guarantee on the decision itself. COVE closes that gap by using the trial's own units.

3. Who should care

This touches any team that decides same-or-different from embedding similarity: product and landmark retrieval, near-duplicate removal in dataset curation, animal re-identification, and open-set matching built on DINOv2, CLIP or SigLIP features. Applied ML leads who set and defend a false-accept target should know that a pair quantile with a binomial bound does not deliver what its nominal level claims. Data curation owners who deduplicate training sets with similarity thresholds can state a defensible rate of wrongly merged items. Risk and compliance functions get a bound that holds under one stated assumption instead of a distributional guess. Procurement and vendor management can ask suppliers whether their quoted false-accept rates were calibrated over dependent pairs. Infrastructure owners should note the per-trial cost grows with calibration size. The authors exclude face and person verification from their scope, so identity and access teams should not read this as cover for those systems.

4. How the method works

The mechanism is a rank test on a jointly exchangeable array. Relabelling the n plus 2 units permutes the pairs without changing the law of the score array, so under the impostor null the trial pair is distributed like a uniformly random pair, and at most a fraction alpha of pairs can have rank within the top alpha. Because the probe is included, the test also bounds the false-accept rate conditional on the probe, hub or not, at roughly twice alpha. Symmetry of the score function is essential; one-sided normalizations break the guarantee. To make cosine similarity a fixed symmetric function despite floating-point rounding, embeddings are quantized once to integers small enough that every partial dot product is exact in single precision, with a canary check before each run. Per trial the cost is linear in n: score the probe and reference against calibration, count exceedances, binary-search the sorted calibration pair scores. Symmetric cohort scores, CSLS and S-norm computed against an independent held-out cohort, remain valid and can be chosen for power.

5. How it was evaluated

The study used six public benchmarks with identity-disjoint calibration and test sides, ImageNet validation classes, Stanford Online Products, CUB-200-2011, Stanford Cars, DeepFashion In-shop and a Google Landmarks v2 subset, and eight frozen encoders, DINOv2 small, base and large, CLIP B/16 and L/14, SigLIP B/16, ResNet-50 and ConvNeXt-B. Each cell fixes dataset, encoder, score, split and calibration size of 60, 300 or 1000 identities; core cells ran 500 calibration draws, others 200, each draw with 500,000 impostor and 20,000 genuine trials sampled identity-uniformly. Baselines were two valid calibration-only rules, a PAC rule on disjoint pairs, three recipes that treat pairs as independent including the empirical quantile and a Clopper-Pearson upper bound, an identity bootstrap, and an oracle population threshold evaluated at COVE's exact level. Split-shift experiments on SOP tested what happens when calibration and deployment identities come from different populations. The 149 cells took 4.3 GPU-hours and the code is public.

6. How it performed

Across 903 real-data comparisons the median realised false-accept rate was 1.001 times the level and none deviated significantly, confirming the bound end to end. In the 374 combinations where both valid calibration-only rules accepted nothing, COVE kept a median 100 percent of the oracle's true-accept rate, with a minimum of 83 percent. The empirical quantile over dependent pairs reached 2.87 times its target, and the binomial upper bound missed its 95 percent conditional target in up to 55 percent of draws, worse at larger calibration sizes. Symmetric CSLS raised COVE's true-accept rate by a median factor of 2.1, but lowered it in a quarter of settings, so normalization must be chosen on held-out data. Limits: control is marginal, not per calibration draw; a population shift between calibration and deployment moved realised rates to between 0.33 and 2.48 times the level; levels below one over the pair count are unreachable; and face and person verification were not studied. Our call: pilot it on one deduplication or retrieval threshold we currently set by pair quantile. (Source: arXiv 2610.35277, 2026)