Support Gap: Selecting Fixed-K Candidate Sets for Retained Personalized Headroom

Abstract

Two-stage recommender systems often must choose among same-budget candidate sets before expensive reranking or online evaluation, yet Recall@K, diversity, and coverage do not measure how much fine-state-contingent choice survives retrieval. We define retained personalized headroom as the value of choosing separately for each fine-grained state rather than committing to one fixed item within the retrieved set, and introduce Support Gap (SG), a candidate-local witness estimate of this quantity. Under a uniform candidate-local approximation condition, SG approximates retained headroom within 2ε and admits a finite-sample bound. Across 16,999 held-out contexts from four public datasets, SG achieves lower normalized selection regret than Recall@K, Ridge Proxy-Ensemble, and HardProxy-GBDT on every dataset, reducing pooled regret from 0.3902 for Recall@K to 0.2839, a 27.2% relative improvement. The advantage persists across candidate budgets K ∈ {10, 20, 40} , supporting SG as an effective offline criterion for comparing fixed-budget candidate supports.