PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Salim Khazem

arXiv:2610.35277v1stat.MLcs.LG

TL;DR

Embedding-based verification thresholds are often calibrated from dependent impostor pairs, and the paper studies what can be guaranteed without distributional assumptions. It introduces COVE, which ranks the trial pair among augmented pairs, and reports controlled FAR across benchmarks with strong true-accept retention where valid calibration-only rules are trivial.

  • Problem

    Embedding-based verification often calibrates a false-accept threshold from impostor pairs that share identities, although the standard pair quantile and binomial-bound recipe treats those pairs as independent.

    Source: §1 · p. 1

  • Method

    COVE ranks the trial pair among the augmented calibration-and-trial pair array to obtain distribution-free marginal FAR control under identity exchangeability.

    Source: §1 · p. 1, §5 · p. 3

  • Results

    Across 6 benchmarks and 8 frozen encoders, COVE consistently controlled FAR; where valid calibration-only rules were trivial, it retained a median 100% of sampled-oracle true-accept rate.

    Source: §1 · p. 2

  • Takeaways & Limitations

    COVE reaches rank resolution of order 1/m^2, and a fixed symmetric cohort-normalized score within COVE retains the marginal FAR guarantee.

    Source: §1 · p. 1, §5 · p. 3, §5.2 · p. 4

    Validity requires identity exchangeability and covers zero-effort impostors, while COVE controls marginal FAR over calibration draws rather than conditional FAR for a fixed draw.

    Source: §8 · p. 7

Abstract

from arXiv · show

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 $\rho$ of the population, a calibration-only threshold with marginal false-accept rate (FAR) at most $\alpha$ under every identity-exchangeable law reaches the hub score on hub-free calibration sets with probability at most $(m+2)\alpha/(2\rho)$. Uniformly accepting near that score at levels well below $\rho/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\alpha 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$\,\alpha$ 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

1 INTRODUCTION

Embedding-based verification commonly sets thresholds from impostor pairs that share identities, so hubs can inflate many scores together. The paper contrasts calibration-only guarantees with COVE’s trial-informed procedure and reports its benchmark performance.

1 INTRODUCTION

  • Impostor pairs are dependent because each identity appears in m −1 pairs, allowing a hub that resembles many identities to inflate many scores at once.The paper frames this as a limitation of calibrating over all m(m −1)/2 impostor pairs as if they were independent.Source: §1 · p. 1
  • The paper proves a sharp calibration-only limitation under identity exchangeability, introduces COVE with distribution-free marginal FAR control and rank resolution of order 1/m^2, and supports symmetric cohort scores from an independent cohort.These are the paper’s stated theoretical contributions.Source: §1 · p. 1
  • Across 6 benchmarks and 8 frozen encoders, COVE controlled FAR, while standard pair-based calibration degraded with hubness; where valid calibration-only rules were trivial, COVE retained a median 100% of sampled-oracle true-accept rate.The abstract describes the pair-based calibration comparison and oracle retention in regimes where valid calibration-only rules accept nothing.Source: §1 · p. 2

2 RELATED WORK

The paper situates its contribution among conformal inference, biometric error-rate methods, and score normalization. It distinguishes its finite-sample decision-rule target and establishes validity for a fixed symmetric cohort-normalized score within COVE.

Conformal inference

  • Pair-indexed conformal ranks and related hierarchical or adaptive transductive settings provide context; this paper applies a known rank argument to verification and studies its contrast with calibration-only thresholds, per-probe behavior, and symmetric cohort scores.The cited PAC, conditional-coverage, and transductive-efficiency bounds address different targets.Source: §2 · p. 2

Biometric error rates

  • Prior biometric work quantifies dependence among impostor pairs with uncertainty methods and documents wolves and retrieval hubs, while this paper targets a finite-sample decision rule rather than an error-rate interval.The passage also notes prior study of synthetic identities for threshold calibration.Source: §2 · p. 2

Score normalization

  • Cohort normalization is used in speaker and face verification, while retrieval uses CSLS and query-bank variants; these normalizations alone do not establish COVE’s distribution-free marginal FAR bound.A fixed symmetric form within COVE inherits that guarantee.Source: §2 · p. 2

3 SETTING

The setting treats each image embedding as a unit and each symmetric pair score as the basis for verification. Under identity exchangeability, the trial identities are distinct from calibration identities and sampled under the same protocol.

3 SETTING

  • A unit is one image of one identity represented by a frozen embedding, and a pair score is any measurable symmetric function of two units, with cosine similarity as the canonical choice.The score may also depend on auxiliary data independent of all units, such as an impostor cohort.Source: §3 · p. 2
  • A verification trial is a probe-reference pair; it is an impostor when its units belong to different identities and genuine otherwise.Source: §3 · p. 2
  • Calibration contains one unit from each of m distinct identities, and the trial adds a probe and reference to form the augmented pair array.The unordered pairs in the augmented set include the trial pair.Source: §3 · p. 2
  • Under the impostor null, the trial identities are distinct from calibration identities and the full vector of m + 2 units is exchangeable.The assumption does not require pair scores to be independent.Source: §3 · p. 2
  • Identity exchangeability requires calibration and trial identities to follow the same sampling protocol, including image capture; it excludes targeted look-alikes and fails under calibration-deployment population shift.The assumption also fails if a probe identity occurs in calibration.Source: §3 · p. 2
  • FAR is the impostor acceptance probability over calibration and trial, whereas TAR is acceptance probability on genuine trials.A calibration-only rule thresholds the trial score using a threshold computed from calibration units alone.Source: §3 · p. 2

4 WHAT CALIBRATION-ONLY THRESHOLDS CAN GUARANTEE

The section establishes a worst-case limit on calibration-only thresholds when identity-level hubs are possible. It contrasts that limit with a valid calibration-only rule and shows why its resolution remains coarser than the transductive scale.

4 WHAT CALIBRATION-ONLY THRESHOLDS CAN GUARANTEE

  • A ρ-hub at level c̄ has probability at least ρ of scoring at least c̄ against a Q unit and against an independent H unit.The hub law H is diffuse, and ρ_Q(c̄) is the supremum such hub strength for Q.Source: §4 · p. 3
  • A calibration-only rule required to control conditional FAR has hub-level threshold probability bounded by δ(1 −α/ρ)^−m/2, approximately δ exp{mα/(2ρ)(1 + O(α/ρ))}.The bound applies for 0 < α < ρ under contaminated i.i.d. calibration at every contamination rate.Source: §4 · p. 3
  • For a ρ-hub law, a valid calibration-only threshold reaches the hub score on hub-free calibration sets with probability at most (m + 2)α/(2ρ).This is a minimax statement over laws with hubs, not a claim about a particular encoder.Source: §4 · p. 3
  • With ρ of order one, uniformly lowering a calibration-only threshold to the hub level requires α of order ρQ(c̄)/m rather than 1/m^2, even with more images per identity when hubness is identity-level.Theorem 1’s hub construction gives the limitation; its proof places a hub in the trial with probability 2/(m + 2) while calibration is hub-free.Source: §4 · pp. 2–3
  • For ρ = 1, the bound is tight for even m: split conformal on ⌊m/2⌋ disjoint calibration pairs first accepts at α ≥1/(⌊m/2⌋+1).A randomized version attains the bound at smaller α.Source: §4 · p. 3
  • A valid threshold based on all calibration pairs uses kα = ⌊αN⌋−2m and can accept for some score arrays only when α ≥(2m + 1)/N, which is less than 4/(m + 2).If kα < 1, the rule rejects all trials.Source: §4 · p. 3

5 COVE: A FINITE-SAMPLE TRANSDUCTIVE TEST

COVE uses the trial units in a transductive rank test over all pairs in the augmented set. Under identity exchangeability and a symmetric score, it controls marginal FAR while allowing a finer rank resolution than calibration-only thresholds.

5 COVE: A FINITE-SAMPLE TRANSDUCTIVE TEST

  • COVE ranks the trial among all N pairs formed from the calibration units and trial units, accepting when its rank-based p-value is at most α.Its resolution is 2/m^2 when the trial score is uniquely largest; ties can delay acceptance.Source: §5 · pp. 3–4
  • Under Assumption 1, COVE’s FAR is at most ⌊αN⌋/N for every symmetric score, with equality when pair scores are almost surely distinct.Here N is the number of pairs in the augmented set.Source: §5 · p. 3
  • When the trial score exceeds S(kα), COVE accepts every trial accepted by the U-conformal rule of Proposition 1.At most kα − 1 calibration pairs and 2m cross pairs then score at least as high as the trial.Source: §5 · p. 4
  • For almost every probe, COVE’s conditional FAR is at most ⌊αN⌋/(m + 1), while a calibration-only threshold can accept a hub probe’s impostor trials with probability up to ρ.The per-probe bound is useful when mα is small.Source: §5 · p. 4

5.1 Algorithm, cost, and exact arithmetic

  • Quantizing embeddings makes dot-product scores exact under standard FP32 matrix-product kernels, avoiding summation-order differences that could undermine the fixed-score guarantee.The reported per-trial raw-score cost is O(md + log m); cohort-normalized scores also require O(|Z|d) work per new unit unless cohort statistics are cached.Source: §5.1 · p. 4

5.2 Cohort normalization with a guarantee

  • With calibration and trial units exchangeable conditionally on an independent cohort, fixed symmetric cohort scores such as CSLS and S-norm retain the FAR bound; one-sided normalization is not covered.Normalization changes which trials are accepted and may be chosen for power using independent data.Source: §5.2 · p. 4

6 POWER AND THE ZOO INDEX

This section relates COVE’s power to impostor-rate heterogeneity and calibration variability. It introduces a zoo index for the variability in per-unit impostor rates and gives a one-sided comparison with an oracle threshold under stated conditions.

6 POWER AND THE ZOO INDEX

  • COVE’s expected rank includes a finite-rank self-count correction and an excess-rate term, while its realised rank also varies with the calibration draw.The oracle global threshold accepts when the impostor tail probability is at most α.Source: §6 · p. 4
  • The zoo index κ measures the squared coefficient of variation of per-unit impostor rates, and the relative standard error at an impostor tail of α depends on κ and m.The variance expression separates heterogeneity in per-unit impostor rates from the ordinary Bernoulli component.Source: §6 · p. 5
  • Pairs represent about m^2/2 independent trials only while κ ≪ 1/(mα); otherwise the effective count is about m/(4κα).The text identifies κ with heterogeneity in unit-specific impostor rates.Source: §6 · p. 5
  • When αm^2 ≥ 8/η, the stated one-sided bound compares COVE’s TAR with the oracle TAR at α(1 − 2η), subtracting excess-rate and calibration-variability terms.The bound holds under the passage’s additional conditions on excess impostor rates and ζ1, and COVE can exceed the best global threshold at the same marginal level by adapting to the calibration draw.Source: §6 · p. 5

7 EXPERIMENTS

Across six benchmarks and eight frozen encoders, COVE controlled marginal FAR and retained true-accept performance where valid calibration-only rules accepted nothing. Pair-based methods could miss their nominal FAR targets, while cohort normalization and non-exchangeable splits revealed important trade-offs and scope boundaries.

Setup

  • The evaluation covered six public benchmarks and eight frozen encoders, using identity-disjoint calibration and test sides and up to 500 calibration draws per core-tier cell.Each draw sampled m identities and one image per identity, then impostor and genuine trials from remaining identities.Source: §7 · p. 5

Q1–Q2: validity and power

  • Across 374 reliable combinations where both valid calibration-only rules accepted nothing, COVE retained median 100% of sampled-oracle TAR; across 903 comparisons, its median realised FAR-to-level ratio was 1.001.COVE can accept from 1/N, while the valid calibration-only rules have higher acceptance floors.Source: §7 · pp. 5–6, Figure 1 · p. 6

Q3: pair-based calibration

  • The empirical quantile exceeded 1.1α in 36% of cases and reached 2.87α FAR; the binomial UCB’s conditional FAR exceeded α in up to 55% of draws.Pair-conformal without COVE’s cross pairs reached 1.61α FAR despite median TAR equal to COVE’s.Source: §7 · p. 6

Q4: mechanism

  • Among genuine trials accepted by the oracle, COVE accepted 96% with hub load 0 but 65% with hub load at least 3.The measured zoo index rose from 0.4–3 at α = 10^-2 to 4.9–76 at α = 10^-4 across eight dataset/encoder pairs.Source: §7 · p. 6

Q5: cohort normalization

  • CSLS with a 20% held-out cohort raised COVE’s TAR by a median factor of 2.1, but lowered it in 24% of cohort combinations; realised FAR stayed at the level.The result supports choosing normalization on held-out data.Source: §7 · pp. 6–7

Q6: non-exchangeable identities

  • Under SOP split shifts, COVE’s realised FAR ranged from 0.50 to 1.44 times its level for official splits and 0.33 to 2.48 times for super-category splits.The pair-based recipes also failed under these non-exchangeable splits.Source: §7 · p. 7

Breadth and cost

  • On In-shop and GLDv2 and with five further encoders, conclusions were unchanged, with median 100% of the oracle’s TAR; raw-score trials cost 0.7 µs at m = 1000 on one GPU.The reported trial cost was amortized over batches and included all baselines.Source: §7 · p. 7

8 LIMITATIONS

The guarantees depend on identity exchangeability and provide marginal rather than fixed-calibration conditional FAR control. The results also have worst-case, resolution, computational, and application-scope boundaries.

8 LIMITATIONS

  • Identity exchangeability requires calibration and deployment identities to follow the same sampling protocol, with the probe identity absent from calibration.The guarantee covers zero-effort impostors, not targeted look-alikes or presentation attacks.Source: §8 · p. 7
  • COVE controls FAR averaged over calibration draws, not the conditional FAR of a fixed draw; a conditional version remains open.Theorem 1(b) also limits calibration-only PAC rules well below 2ρ/m.Source: §8 · p. 7
  • The lower bound concerns a class of hub laws, and its tightness for real encoders is unknown.The reported separation uses the achievable floors of calibration-only baselines.Source: §8 · pp. 7–8
  • Figure 2 organizes evidence around realized FAR, conditional-FAR exceedances, and COVE acceptance of oracle-accepted genuine trials by hub load.Its panels cover random-split comparisons and several benchmark-specific settings.Source: Figure 2 · p. 8
  • Levels below 1/N ≈ 2/m^2 are unreachable, while α = 10^-6 requires roughly 1.4 × 10^3 calibration identities.Raw-score trials require m stored-unit scores; cohort scores also require statistics against Z for new units.Source: §8 · p. 8
  • The evaluation covers one-to-one verification of objects, birds, cars, garments, and landmarks with frozen encoders, not one-to-many identification or face and person verification.In-shop garment images show models; person-verification consent and fairness questions are outside the FAR guarantee.Source: §8 · p. 8

AI use statement

Generative AI tools assisted with language editing, readability, and minor rephrasing. The authors state that they reviewed and verified the assisted content and take responsibility for the final work.

AI use statement

  • Generative AI tools were used for language editing, readability improvements, and minor rephrasing, with all assisted content reviewed, edited, and verified by the authors.The tools were not used to formulate research questions, develop theoretical results, design or implement the method, generate data, or determine conclusions.Source: AI use statement · p. 10
  • The authors take responsibility for the final content, including text, claims, analyses, and artifacts produced with AI assistance.Source: AI use statement · p. 10

CHECKLIST

The checklist records the paper’s documentation of methods, assumptions, proofs, evaluation materials, and reproducibility artifacts, and marks human-subject research as not applicable.

CHECKLIST

  • The paper states that its mathematical setting, assumptions, decision rules, and COVE algorithm are described, with complete theoretical proofs in Appendix A.It also says assumptions and their practical implications are discussed across the paper.Source: CHECKLIST · pp. 10–11
  • The supplementary material provides code, datasets, experimental protocols, audit procedures, and reproduction instructions.Appendix B describes datasets, encoders, splits, calibration protocols, hyperparameters, baselines, and evaluation procedures.Source: CHECKLIST · p. 11
  • The checklist says reported metrics, confidence intervals, significance tests, and error bars are defined, with computing infrastructure, GPU models, runtime, and memory usage reported in Appendix E.Source: CHECKLIST · p. 11
  • The checklist reports citations and available license and usage information for external assets, and says implementation and reproduction artifacts are included in the supplementary material.It marks crowdsourcing and human-subject research as not applicable.Source: CHECKLIST · p. 11

A.1 Theorem 2 (finite-sample validity)

The appendix establishes finite-sample rank validity under exchangeability, characterizes calibration-only limits and COVE’s conditional behavior, and gives variants, power analysis, and implementation details.

A.1 Theorem 2 (finite-sample validity)

  • Under identity exchangeability, the trial pair’s rank among all augmented pairs yields marginal p-value control at ⌊tN⌋/N, with equality when ties occur with probability zero.The proof uses invariance under relabeling and a rank-counting lemma; pair scores need not be independent.Source: §A.1 · p. 12

A.2 Theorem 1 (calibration-only thresholds)

  • For ρ-hub laws, a valid calibration-only threshold reaches the hub score on hub-free calibration sets with probability at most (m+2)α/(2ρ).The proof constructs an exchangeable law with one randomly placed hub; its calibration-free event has probability 2/(m+2).Source: §A.2 · pp. 12–13

A.3 COVE’s FAR conditional on the probe

  • Conditioned on almost every probe, COVE’s acceptance probability is at most ⌊αN⌋/(m+1), which is bounded by (m+2)α/2.Source: §A.3 · p. 13

A.4 A variant robust to a probe identity present in calibration

  • A variant remains valid when the probe matches a calibration identity chosen independently of images, provided the other units are exchangeable.It removes the least-crowded calibration unit and is reported as unevaluated empirically.Source: §A.4 · p. 13

A.5 Proposition 1 (a valid calibration-only threshold)

  • A calibration-only threshold accepting when the trial exceeds the k-th highest calibration-pair score has FAR at most ⌊αN⌋/N.It can accept for some score arrays only when kα ≥ 1, and ties may still force rejection.Source: §A.5 · p. 14

A.6 Proposition 3 (power)

  • The power bound controls rejection probability using the expected rank margin ηα and a variance bound; its stated asymptotic conditions include αm^2 → ∞ and m^-1 sup_{Ḡ(s)≤α} ζ1(s)/α^2 → 0.The condition is on ζ1(s)/α^2, not κ(s) alone.Source: §A.6 · p. 14

A.7 Proposition 2 (zoo index)

  • For i.i.d. units, the zoo index is a U-statistic with a symmetric threshold kernel, and its variance decomposition includes variation in the per-unit rate h(U; τ).The stated formula is exact for i.i.d. units.Source: §A.7 · p. 14

A.8 Exact integer similarity

  • The implementation makes pair scores a fixed, exactly symmetric integer-valued function, as required by the finite-sample rank argument.It uses rounded embeddings and checks matrix products against an int64 reference; ties are rare and only make the test more conservative.Source: §A.8 · p. 14

B EXPERIMENTAL PROTOCOL

The protocol samples calibration and trial identities to realize identity-level exchangeability, then compares FAR and acceptance performance across calibration rules. The additional results, asset documentation, and compute section describe reported visual summaries, data and model provenance limits, and resource use.

B EXPERIMENTAL PROTOCOL

  • Calibration draws sample distinct identities uniformly, while trials sample impostor identities uniformly and genuine identities with two distinct images; all rules share the same draws and trials.The random identity split realizes Assumption 1; fixed and category splits instead calibrate and test on separate identity sets.Source: B EXPERIMENTAL PROTOCOL · p. 15
  • Realised FAR averages accepted-impostor fractions over calibration draws, while threshold rules also report conditional-FAR exceedance rates against a sampled population of impostor pairs.The oracle threshold is a sampled population quantile, and its true-accept rate is measured on sampled genuine trials; power ratios exclude unreliable oracle comparisons.Source: B EXPERIMENTAL PROTOCOL · p. 15
  • The baseline suite includes empirical-quantile and pairwise binomial-UCB thresholds, conformal variants, identity bootstrap, disjoint-pairs PAC, and a population-threshold oracle.The PAC guarantee is stated for i.i.d. identity draws and is approximate under sampling without replacement from a finite pool.Source: B EXPERIMENTAL PROTOCOL · p. 15
  • The hub-model experiment varies hub prevalence across 0, 0.01, and 0.03, while the mechanism diagnostic estimates per-unit impostor rates and a zoo index.Directional cap occupancy is reported separately and is not interpreted as the theoretical hub parameter.Source: B EXPERIMENTAL PROTOCOL · pp. 15–16

C ADDITIONAL RESULTS

  • Figure 3 plots realised FAR against target level for real data and the hub model, with 95% confidence intervals over calibration draws; Table 3 covers all datasets and encoders.Table 3 caption specifies FAR-over-level summaries and oracle-relative true-accept rates for settings where valid calibration-only rules are trivial and the oracle is reliable; no table values are supplied here.Source: Figure 3 · p. 16, Table 3 · p. 17

D ASSETS AND LICENSES

  • The supplement records dataset snapshots and feature-array hashes, but not immutable checkpoint revisions for every pretrained model, so exact feature extraction outside the cache is not established.The GLDv2 mini mirror’s per-image license terms are unverified, and source images are not distributed in the supplement.Source: D ASSETS AND LICENSES · pp. 17–18

E COMPUTE

  • Reported runs used one GPU each with a 24-GiB cap; feature extraction took 0.6 GPU-hours and reported evaluations took 4.3 GPU-hours.No model was trained or fine-tuned.Source: E COMPUTE · p. 18

Related papers

Loading 2610.35277v1…