betaFeedback

WorksComputer Science

Efficient Conformal Calibration for Paired Recommendation Decisions

Abstract

Risk control can suppress useful changes to a frozen recommendation rule. We study how to recover valid activation from the same observed fractional losses. Two specified internal calibrators can lose efficiency by compressing losses into their sum or clipping auxiliary inverse counts before averaging. We propose Averaged Conformal Risk Calibration, or ACRC, which averages before clipping. A product identity proves expected-risk validity, while pointwise bounds characterize the additional activation. For fixed populations sampled without replacement, we connect activation to signed utility under heterogeneous users and switching constraints. Near the budgets, positive population mean gain and the stated nondegeneracy conditions give positive leading-order utility increments despite sampling dependence. Across six datasets, changing only calibration improves discounted net utility by 0.0102260.010226 over raw and 0.0083370.008337 over RB. A separately frozen Jester confirmation gives 0.011025±0.0010820.011025 \pm 0.001082 over raw with the rule and filter fixed, using a five-seed approximate 95 percent paired interval. Against information-matched SCoRE selecting risk or reward scores, the mean utility difference is +0.015934±0.001440+0.015934 \pm 0.001440. These gains use more mean realized risk within the declared budgets. Upstream failures delimit the benefit: efficient calibration releases useful modifications when the proposals themselves have value.

Introduction

A postprocessing rule can change a frozen recommender’s items, order, and list length. Such modifications may improve average utility while harming some users. Conformal risk control limits this downside using held-out losses [1, 2, 3]. For a fixed proposal, we ask whether the same observed losses can permit more useful modifications under the same expected-risk guarantee.

Our starting point is information already present in fractional losses. Their magnitudes distinguish a small deterioration from a large one. Compressing them into a sum discards structure, while auxiliary Bernoulli randomization followed by clipping each inverse count introduces a different loss. ACRC averages the inverse count before clipping. This simple change needs two separate arguments. Jensen’s inequality establishes no smaller activation, and an augmented product identity proves that the larger probability remains valid. Randomization and conditional averaging are existing tools [4, 5, 6]. The new result is a specific valid operator with a characterized efficiency improvement.

Whether additional activation improves decisions is a second question. Some users have negative gains, and calibration and evaluation use complementary subsets of a fixed graph population. We retain the resulting sampling covariance and account for switching risk constraints. Near the budgets, positive population mean gain and nondegenerate auxiliary variance yield positive leading-order utility increments. This connects operator efficiency to a decision benefit under explicit conditions, rather than treating higher activation as a utility guarantee.

We separate calibration from candidate construction and selection. Same-rule raw and RB controls and a method-frozen Jester confirmation isolate calibration. Information-matched SCoRE and complete-method comparisons assess wider performance, whose gains also depend on the proposals.

Our contributions are threefold.

  1. More efficient valid calibration. For a frozen rule, we construct a fractional-loss operator, prove exchangeable risk validity, and characterize its pointwise activation improvement over two specified internal calibrators, including strictness and saturation conditions.

  1. A utility connection for fixed populations. We derive the exact sampling-covariance correction and1

positive local utility increments of order n−1n^{-1} over raw and n−1/2n^{-1/2} over RB under positive population mean gain and the stated nondegeneracy conditions, allowing heterogeneous gains and switching constraints.

3. Isolated recommendation gains. Same-rule controls and a frozen confirmation establish a calibration increment distinct from fitted heads and optional filtering. Information-matched and complete-method comparisons test its applicability beyond the scalar operator class.

Related Work

Risk control and decision policies. CRC controls expected bounded monotone losses [1], while Conformal Risk Training optimizes through calibration [7]. Reference decisions and fallback policies already appear in risk-controlled postprocessing and policy control [8, 9, 10]. Conformal Robustness Control optimizes a probability-constrained robustness certificate [11]. Joint certification covers an iid selective-risk ratio, acceptance floor, and utility lower bound [27]. We instead analyze the calibration efficiency of a frozen rule for mean downside magnitude on fixed populations.

Evidence and calibration operators. SCoRE uses risk-adjusted ee-values satisfying E[EL]≤1\mathbb{E}[EL] \le1 [6]. Our E=w+/αE = w_{+}/\alpha meets this condition, so validity belongs to that general framework. P2E, evidence averaging, and adaptive coverage provide related transformations [12, 13, 14]. SCoRE MDR makes user-specific decisions from pretrained risk scores and equals CRC on its threshold family. Our theoretical comparisons concern a specified scalar operator class. The same-information experiment tests, rather than assumes, its decision advantage over user selection.

Recommendation calibration. PerK combines user-wise probability calibration with personalized prefixes [15]. UMC learns a contextual monotone calibrator whose item-dependent context can change ranking [16]. Conformal@K controls prefix miss-risk and also considers fractional 1−Recall1-\mathrm{Recall} loss [3]. CARE treats interactive threshold adaptation [18], and ReCIRC learns conditional risk curves before CRC [19]. MIR learns reranking through interactions between history and candidates [17]. Appendix § 11.§ 4 reports its supplementary external comparison. Dynamic length, frozen-model wrapping, and fractional recommendation losses are therefore existing capabilities. Our claim concerns the final calibration operator and its finite-population utility consequences, not those capabilities themselves.

Paired Recommendation Decisions

Let π0(u)\pi_0(u) be a frozen reference list and aa a modified list of length at most KK. For observed binary relevance YuiY_{ui}, define discounted net utility with an irrelevant-item cost λ≥0\lambda\ge0.

Uλ(a,Yu)=1WK∑r=1∣a∣dr[(1+λ)Yu,ir−λ],dr=1log⁡2(r+1),WK=∑r=1Kdr.(1)\begin{aligned} U_{\lambda}(a,Y_u) &= \frac{1}{W_K}\sum_{r=1}^{|a|} d_r\left[(1+\lambda)Y_{u,i_r}-\lambda\right], \\ d_r &= \frac{1}{\log_2(r+1)}, \qquad W_K = \sum_{r=1}^{K}d_r. \tag*{(1)} \end{aligned}

Each relevant item earns one unit and each irrelevant item costs λ\lambda units before position discounting. This makes ranking and length jointly consequential: deleting an irrelevant item can help, while deleting a relevant item loses reward. The common denominator prevents shorter lists from gaining utility solely by changing normalization. We use K=20K=20 and the symmetric valuation λ=1\lambda=1. This is a declared evaluation preference, not an estimated platform cost or measured profit. Rating-derived labels represent relevance rather than clicks. NDCG, Recall, and length are reported separately, and Table 24 tests alternative costs.

λ\lambdaPoolΔU+0\Delta U_{+0} ↑Higher/tie/lowerΔU+π0\Delta U_{+\pi_0} ↑RUR_U ↓RRR_R ↓
0.2580+0.00222014/1/0+0.047960.0089870.002876
0.5080+0.00482814/1/0+0.056850.0107540.003821
0.50160+0.01082115/0/0+0.078560.0118960.004462
1.0040+0.00752615/0/0+0.059330.0121040.004410
1.0080+0.00995915/0/0+0.069140.0120420.004444
2.0080+0.00930115/0/0+0.077930.0132350.005351

Table 24. Macro means over fifteen settings. Counts compare new versus raw utility on the same selected rule, using tolerance 10−1210^{-12}. Selection and calibration are repeated for each condition.

A candidate rule jj specifies a frozen distribution νj(a∣u)\nu_j(a\mid u) over complete lists. Write the action’s paired gain as Gua=Uλ(a,Yu)−Uλ(π0(u),Yu)G_{ua}=U_{\lambda}(a,Y_u)-U_{\lambda}(\pi_0(u),Y_u) and its Recall change as RuaR_{ua}. These gains lie in [−B,B][-B,B] for B=1+λB=1+\lambda. Define

gju=∑aνj(a∣u)Gua,xju=∑aνj(a∣u)(−Gua)+,xjuR=∑aνj(a∣u)(−Rua)+.(2)\begin{aligned} g_{ju} &= \sum_a \nu_j(a\mid u)G_{ua},\\ x_{ju} &= \sum_a \nu_j(a\mid u)(-G_{ua})_{+},\\ x^R_{ju} &= \sum_a \nu_j(a\mid u)(-R_{ua})_{+}. \tag*{(2)} \end{aligned}

The positive part must precede the action average. In general xju≠(−gju)+x_{ju}\ne(-g_{ju})_{+}. If the calibrated activation probability is pCp_C, the target risks are E[pCxju]≤ϵU\mathbb{E}[p_Cx_{ju}]\le\epsilon_U and E[pCxjuR]≤ϵR\mathbb{E}[p_Cx^R_{ju}]\le\epsilon_R. They control mean downside magnitude, not the probability of any loss or the loss of every user.

We condition on the historical graph, the trained backbone, and the observed feedback array. Users are assigned without replacement to a fitting set FF, a selection set SS, a final calibration set CC, and evaluation set TT. The heads use FF, candidate selection uses SS, and final probabilities use CC. The test labels do not enter these decisions. This protocol permits graph dependence because its randomness is the user-role assignment. It does not identify unobserved feedback or responses to changed online positions.

What is randomized in graph recommendation. Graph users share embeddings and neighborhoods, so disjoint labels do not imply independence. After fitting and selection, each remaining user has fixed losses and gain. Randomly assigning CC and evaluating its complement gives the design in Theorem 5.1. Algorithms read only their assigned labels. Repeated assignments vary allocation, while training seeds vary the backbone.

ACRC with Fractional Losses

Consider a frozen rule with losses l=(l1,…,ln)∈[0,1]nl=(l_1,\ldots,l_n)\in[0,1]^n. Let n≥1n\ge1, 0<α<10<\alpha<1, N=n+1N=n+1, and A=αNA=\alpha N. Introduce conditionally independent auxiliary variables Bi∼Bernoulli⁡(li)B_i\sim\operatorname{Bernoulli}(l_i). They are a calculation device and do not assume independent user feedback. With KB=∑iBiK_B=\sum_i B_i, compare

w0(l)=min⁡{1,A1+∑ili},(3)w_0(l)=\min\left\{1,\frac{A}{1+\sum_i l_i}\right\}, \tag*{(3)}
wRB(l)=EB∣lmin⁡{1,A1+KB},(4)w_{\mathrm{RB}}(l)=\mathbb{E}_{B\mid l}\min\left\{1,\frac{A}{1+K_B}\right\}, \tag*{(4)}
a(l)=AEB∣l11+KB=A∫01∏i=1n(1−tli) dt,(5)a(l)=A\mathbb{E}_{B\mid l}\frac{1}{1+K_B} =A\int_0^1\prod_{i=1}^{n}(1-tl_i)\,\mathrm{d}t, \tag*{(5)}
w+(l)=min⁡{1,a(l)}.(6)w_+(l)=\min\{1,a(l)\}. \tag*{(6)}

The proposed w+w_+ is the ACRC calibrator. We call w0w_0 the raw internal calibrator and wRBw_{\mathrm{RB}} the Rao-Blackwell internal calibrator. They are specified operator comparisons, not reproductions of complete external methods. The difference is the placement of the final clipping operation.

What the loss magnitudes retain. Binary indicators count small and large deteriorations alike, whereas our budget charges their magnitudes. Equal loss sums can also conceal different opportunities. Consider n=2n=2 and α=0.4\alpha=0.4. The loss vectors (1,0)(1,0) and (0.5,0.5)(0.5,0.5) both have sum one. The binary vector makes every operator equal to 0.60.6. For the fractional vector, the auxiliary count has probabilities 0.250.25, 0.50.5, and 0.250.25 at zero, one, and two, giving

w0=0.6,wRB=0.65,w+=0.7.w_0=0.6,\qquad w_{\mathrm{RB}}=0.65,\qquad w_+=0.7.

Raw discards the fractional structure. RB retains it but clips the zero-count outcome before averaging. Clipping only the final average recovers another 0.05 from the same observed losses.

Validity and pointwise efficiency

The next identity controls all leave-one-out risks at once. Its comparison statements concern activation probability, not signed utility.

Theorem 4.1. For any exchangeable (L1,…,LN)∈[0,1]N(L_1,\ldots,L_N)\in[0,1]^N,

E[LNw+(L1:n)]≤α.(7)\mathbb{E}[L_Nw_+(L_{1:n})]\le\alpha. \tag*{(7)}

For every observed vector ll, w+(l)≥max⁡{w0(l),wRB(l)}w_+(l)\ge\max\{w_0(l),w_{\mathrm{RB}}(l)\}. Moreover,

∑i=1Nlia(l−i)=A[1−∏i=1N(1−li)]≤A.(8)\sum_{i=1}^{N}l_i a(l_{-i})=A\left[1-\prod_{i=1}^{N}(1-l_i)\right]\le A. \tag*{(8)}

Proof. Integrate the negative derivative of ∏i(1−tli)\prod_i(1-tl_i) on [0,1][0,1]. Since w+≤aw_+\le a, divide the leave-one-out identity by NN and use exchangeability. Convexity of the reciprocal gives the raw comparison. Concavity of z↦min⁡{1,z}z\mapsto\min\{1,z\} gives the RB comparison. □\square

Why the larger probability remains valid. Jensen’s inequality compares probabilities but does not control their product with future loss. Equation (8) supplies that control uniformly over augmented loss vectors.

A finite-sample boundary for the improvement. The unquantized scalar operators admit a directly computable bound. Write s=∑ilis=\sum_i l_i and V=∑ili(1−li)V=\sum_i l_i(1-l_i). The exact reciprocal identity yields

a−A1+s=A(1+s)2EB∣l[(KB−s)21+KB].(9)a-\frac{A}{1+s}=\frac{A}{(1+s)^2}\mathbb{E}_{B\mid l}\left[\frac{(K_B-s)^2}{1+K_B}\right]. \tag*{(9)}

Consequently,

0≤w+−w0≤min⁡{1−w0,AV(1+s)2}.(10)0\le w_+-w_0\le\min\left\{1-w_0,\frac{AV}{(1+s)^2}\right\}. \tag*{(10)}

References

  1. [1]Angelopoulos A N, Bates S, Fisch A, Lei L, Schuster T. Conformal Risk Control. ICLR, 2024. https://arxiv.org/abs/2208.02814.
  2. [2]Angelopoulos A N, Krauth K, Bates S, Wang Y, Jordan M I. Recommendation Systems with Distribution-Free Reliability Guarantees. COPA, PMLR 204:175–193, 2023. https://proceedings.mlr.press/v204/angelopoulos23a.html.arxiv.org/abs/2207.01609
  3. [3]Fan G, Liu D, Pan L. Conformal@K: Distribution-Free Top-K Miss-Risk Control for Recommendation with Overlapping-Group and Two-Stage Guarantees. ACM Transactions on Information Systems, 44(6), article 138:1–138:42, 2026. doi:10.1145/3828550.
  4. [4]Schlag K H. How to Attain Minimax Risk with Applications to Distribution-Free Nonparametric Estimation and Testing. European University Institute, Economics Working Paper ECO2007/04, version of 12 March 2007. Author manuscript.
  5. [5]Koning N W, van Meer S. Fuzzy Prediction Sets: Conformal Prediction with E-values. arXiv:2509.13130v3, 2026. First version 2025. https://arxiv.org/abs/2509.13130v3.
  6. [6]Bai T, Jin Y. Conformal Selective Prediction with General Risk Control. arXiv:2603.24704v1, 2026. https://arxiv.org/abs/2603.24704v1.
  7. [7]Yeh C, Christianson N, Wierman A, Yue Y. Conformal Risk Training: End-to-End Optimization of Conformal Risk Control. Advances in Neural Information Processing Systems, 38, 2025. Official paper.arxiv.org/abs/2510.08748
  8. [8]Joshi S, Wang T, Hassani H, Dobriban E. Risk-Controlled Post-Processing of Decision Policies. arXiv:2605.06479v1, 2026. https://arxiv.org/abs/2605.06479v1.
  9. [9]Overman W, Bayati M. Conformal Arbitrage: Risk-Controlled Balancing of Competing Objectives in Language Models. Advances in Neural Information Processing Systems, 38, 2025. Official paper page.arxiv.org/abs/2506.00911
  10. [10]Prinster D, Fannjiang C, Park J W, Cho K, Liu A, Saria S, Stanton S D. Conformal Policy Control. ICML, PMLR 306:99772–99824, 2026. https://proceedings.mlr.press/v306/prinster26a.html.arxiv.org/abs/2603.02196
  11. [11]Hu Y, Tan J, Zou C, Bao Y, Ren H. Conformal Robustness Control: A New Strategy for Robust Decision. ICLR, 2026. Official proceedings.
  12. [12]Alami N, Zakharia J, Ben Taieb S. Set-Preserving Calibration from Conformal P-Values to E-Values. ICML, PMLR 306:1680–1705, 2026. https://proceedings.mlr.press/v306/alami26a.html.arxiv.org/abs/2606.03600
  13. [13]Gauthier E, Bach F, Jordan M I. E-Values Expand the Scope of Conformal Prediction. arXiv:2503.13050v3, 2025. https://arxiv.org/abs/2503.13050v3.
  14. [14]Gauthier E, Bach F, Jordan M I. Adaptive Coverage Policies in Conformal Prediction. AISTATS, PMLR 300:3196–3204, 2026. https://proceedings.mlr.press/v300/gauthier26a.html.arxiv.org/abs/2510.04318
  15. [15]Kweon W, Kang S, Jang S, Yu H. Top-Personalized-K Recommendation. The Web Conference, 2024:3388–3399. doi:10.1145/3589334.3645417.DOI
  16. [16]Bai Y, Zhang S, Zhang Y, Liu H, Bao W, Yu E, Feng F, Ou W. Unconstrained Monotonic Calibration of Predictions in Deep Ranking Systems. SIGIR, 2025:937–947. doi:10.1145/3726302.3730105.DOI
  17. [17]Xi Y, Liu W, Zhu J, Zhao X, Dai X, Tang R, Zhang W, Zhang R, Yu Y. Multi-Level Interaction Reranking with User Behavior History. SIGIR, 2022:1336–1346. doi:10.1145/3477495.3532026.DOI
  18. [18]Bisht N, Huo H, Gong X, Xu G. CARE: Adaptive Calibration for Reliable Recommendations. ICML, PMLR 306:8340–8372, 2026. https://proceedings.mlr.press/v306/bisht26b.html.
  19. [19]Marcondes e Resende B, Graziadei H, Ramos T R, Izbicki R. ReCICRC: Rectified Conformal Risk Control. arXiv:2609.38112v1, 2026. https://arxiv.org/abs/2609.38112v1.
  20. [20]Gao C, et al. KuaiRec: A Fully-observed Dataset and Insights for Evaluating Recommender Systems. CIKM, 2022:540–550. doi:10.1145/3511808.3557220.DOI
  21. [21]Gao C, Li S, Zhang Y, Chen J, Li B, Lei W, Jiang P, He X. KuaiRand: An Unbiased Sequential Recommendation Dataset with Randomly Exposed Videos. CIKM, 2022:3953–3957. doi:10.1145/3511808.3557624.DOI
  22. [22]Chen S, Chen J, Zhou S, Wang B, Han S, Su C, Yuan Y, Wang C. SIGFormer: Sign-aware Graph Transformer for Recommendation. SIGIR, 2024:1274–1284. doi:10.1145/3626772.3657747.DOI
  23. [23]Harper F M, Konstan J A. The MovieLens Datasets: History and Context. ACM Transactions on Interactive Intelligent Systems, 5(4), article 19, 2015. doi:10.1145/2827872. MovieLens-25M stable release: https://grouplens.org/datasets/movielens/25m/.DOI
  24. [24]He X, Deng K, Wang X, Li Y, Zhang Y, Wang M. LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation. SIGIR, 2020:639–648. doi:10.1145/3397271.3401063.DOI
  25. [25]Yu J, Xia X, Chen T, Cui L, Nguyen Quoc Viet Hung, Yin H. XSimGCL: Towards Extremely Simple Graph Contrastive Learning for Recommendation. IEEE Transactions on Knowledge and Data Engineering, 36(2):913–926, 2024. Early access 2023. doi:10.1109/TKDE.2023.3288135.DOI
  26. [26]Goldberg K, Roeder T, Gupta D, Perkins C. Eigentaste: A Constant Time Collaborative Filtering Algorithm. Information Retrieval, 4(2):133–151, 2001. doi:10.1023/A:1011419022209. Jester dataset: https://eigentaste.berkeley.edu/dataset/.
  27. [27]Yu X, Liu J. A Joint Finite-Sample Certificate for Adaptive Selective Conformal Risk Control. arXiv:2606.08517v1, 2026. https://arxiv.org/abs/2606.08517v1.
  28. [28]Li X, Ding P. General Forms of Finite Population Central Limit Theorems with Applications to Causal Inference. Journal of the American Statistical Association, 112(520):1759–1769, 2017. doi:10.1080/01621459.2017.1295865.DOI

Paper details

vlnc:W_7z34jagd
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents