Privacy Without Regret: Differentially Private Inference-Time Alignment

# Privacy Without Regret: Differentially Private Inference-Time Alignment
Source: [https://arxiv.org/html/2608.26324](https://arxiv.org/html/2608.26324)
Nandini BhattadAffiliation:Indian Institute of Technology KanpurEmail:[bhattadnandini13@gmail\.com](mailto:)Sayak Ray ChowdhuryAffiliation:Indian Institute of Technology KanpurEmail:[sayakrc@iitk\.ac\.in](mailto:)

###### Abstract

Best\-of\-N \(BoN\) sampling is the simplest and most widely deployed inference\-time alignment strategy, but it suffers from two distinct problems: reward hacking, in which the selected response exploits errors in the proxy reward model, and the absence of any privacy protection for the sensitive human preference data used to train that reward model\. We show that a single intervention—adding calibrated noise to reward scores before selection—resolves both\. Our first result, Private Best\-of\-N \(PrivBoN\), establishes that Gumbel noise at an appropriate scale simultaneously providesϵ\\epsilon\-differential privacy and implements KL\-regularized alignment\. Whenever the privacy budget exceeds a critical thresholdϵ∗\\epsilon^\{\*\}, the privacy\-mandated noise is the regret\-optimal regularization, and privacy imposes zero additional alignment cost—matching the information\-theoretic skyline of[Huang et al\. \[13\]](https://arxiv.org/html/2608.26324#bib.bib18)\. Becauseϵ∗\\epsilon^\{\*\}depends on an unknown coverage coefficient, we introduce Private Inference\-Time Pessimism \(PrivITP\), which combinesχ2\\chi^\{2\}\-regularized rejection sampling with a two\-phase Gaussian mechanism\. PrivITP achieves ex\-post\(ϵ,δ\)\(\\epsilon,\\delta\)\-DP with a privacy cost independent of the number of responsesnn, cleanly decouples the regularization parameter from the privacy parameter, and attains the skyline up to a noise\-inflation term\. Experiments across several language models, datasets, and reward models confirm our results: PrivBoN and PrivITP are scaling\-monotonic \(unlike BoN, which degrades past a criticalnn\), and PrivITP matches or outperforms PrivBoN at equivalent privacy levels, with the largest gains in the strong\-privacy regime\.

## 1Introduction

Aligning large language models \(LLMs\) with human preferences is a central challenge in modern AI\[[24](https://arxiv.org/html/2608.26324#bib.bib21)\]\. While training\-time methods such as RLHF\[[4](https://arxiv.org/html/2608.26324#bib.bib8)\]and DPO\[[21](https://arxiv.org/html/2608.26324#bib.bib7)\]have received extensive attention, a parallel line of work focuses on*inference\-time alignment*: improving the quality of a frozen model’s outputs at serving time, without updating its parameters\. Inference\-time alignment has become increasingly important as frontier models are deployed via APIs to millions of users, making it impractical to fine\-tune per\-user or per\-application preferences into the model weights\. The simplest and most widely deployed inference\-time strategy is Best\-of\-NN\(BoN\) sampling\[[20](https://arxiv.org/html/2608.26324#bib.bib20),[10](https://arxiv.org/html/2608.26324#bib.bib17)\], which generatesnncandidate responses from a base policyπ0\\pi\_\{0\}, scores each with a learned reward modelr^\\hat\{r\}, and returns the top\-scoring candidate\. BoN is attractive for its simplicity – it requires no gradient computation, works with any frozen model, and scales naturally with test\-time compute\[[23](https://arxiv.org/html/2608.26324#bib.bib6)\]\.

A growing body of recent work has established tight theoretical characterizations of BoN’s KL vs\. win\-rate tradeoff\[[2](https://arxiv.org/html/2608.26324#bib.bib14),[30](https://arxiv.org/html/2608.26324#bib.bib23)\]and proposed smoothed variants that interpolate between hard maximization and random selection\[[26](https://arxiv.org/html/2608.26324#bib.bib22),[1](https://arxiv.org/html/2608.26324#bib.bib13),[14](https://arxiv.org/html/2608.26324#bib.bib19)\]\. However, BoN is known to be vulnerable to*reward hacking*\[[9](https://arxiv.org/html/2608.26324#bib.bib16),[14](https://arxiv.org/html/2608.26324#bib.bib19)\]: as the number of responsesnngrows, BoN increasingly selects responses in which the learned rewardr^\\hat\{r\}overestimates the true rewardr∗r^\{\*\}, thereby degrading alignment\.[Huang et al\. \[13\]](https://arxiv.org/html/2608.26324#bib.bib18)formalizes this by showing that BoN is not scaling\-monotonic – more candidates can yield*worse*alignment and that BoN’s regret crucially depends on the quality of the learned reward modelr^\\hat\{r\}\.

Reward models are typically trained on sensitive human preference data – pairwise comparisons from crowd workers or domain experts whose judgments encode personal values and cultural context — and are increasingly shared across applications\. Each reward\-model evaluation leaks information about this training data, and over a deployment session ofTTqueries, the cumulative leakage through selected outputs is uncontrolled\. Concretely, consider a reward modelr^𝒟\\hat\{r\}\_\{\\mathcal\{D\}\}deployed as a BoN selection service\. An adversary wishing to determine whether a specific preference example\(x0,y0\+,y0−\)\(x\_\{0\},y\_\{0\}^\{\+\},y\_\{0\}^\{\-\}\)was in𝒟\\mathcal\{D\}can craft prompts whose plausible completions are structured aroundy0\+y\_\{0\}^\{\+\}andy0−y\_\{0\}^\{\-\}, query the service repeatedly, and observe shifts in the empirical distribution of returned responses\. Since BoN’s argmax is deterministic given reward scores, even small training\-attributable shifts inr^𝒟\\hat\{r\}\_\{\\mathcal\{D\}\}manifest as measurable shifts in selection frequencies—the exact signal exploited by membership\-inference attacks on LLMs\[[3](https://arxiv.org/html/2608.26324#bib.bib1)\]and downstream\-output leakage attacks\[[25](https://arxiv.org/html/2608.26324#bib.bib2)\]\.

While differential privacy has been widely applied to training\-time alignment \(SFT, reward\-model training, and RLHF\)\[[32](https://arxiv.org/html/2608.26324#bib.bib24),[27](https://arxiv.org/html/2608.26324#bib.bib4)\], inference\-time privacy remains largely unstudied\. We fill this gap by introducing*differentially private inference\-time alignment*: mechanisms ensuring that the selected response satisfiesε\\varepsilon\-DP with respect toDD, bounding the information any adversary can extract about any individual preference—regardless of query budget or side information\.

We make the followingcontributions\.

\(1\) Private Best\-of\-N\(PrivBoN,[Section3](https://arxiv.org/html/2608.26324#S3)\)\. We show that adding i\.i\.d\. Gumbel noise with scaleσ=2​Δr/ε\\sigma=2\\Delta\_\{r\}/\\varepsilonto reward scores before BoN selection yields a mechanism that simultaneously satisfiesε\\varepsilon\-DP and implements the KL\-regularized alignment optimum in the large\-nnlimit, whereΔr\\Delta\_\{r\}is the reward\-model sensitivity onDD\. When the privacy budget exceeds the critical thresholdε∗​\(x\)=2​Δr​Cπ∗​\(x\)/εRM​\(x\)\\varepsilon^\{\*\}\(x\)=2\\Delta\_\{r\}\\sqrt\{C^\{\\pi^\{\*\}\}\(x\)\}/\\varepsilon\_\{\\mathrm\{RM\}\}\(x\), the privacy\-mandated noise coincides with the regret\-optimal regularization and privacy becomes “free”—PrivBoN’s regretO⁡\(Cπ∗​εRM2\)O\(\\sqrt\{C^\{\\pi^\{\*\}\}\\varepsilon\_\{\\mathrm\{RM\}\}^\{2\}\}\)matches the information\-theoretic skyline of[Huang et al\. \[13\]](https://arxiv.org/html/2608.26324#bib.bib18)at zero additional alignment cost\. HereεRM\\varepsilon\_\{\\mathrm\{RM\}\}denotes reward\-model error andCπ∗C^\{\\pi^\{\*\}\}the coverage coefficient of a comparator policyπ∗\\pi^\{\*\}\.

\(2\) Private Inference\-Time Pessimism\(PrivITP,[Section4](https://arxiv.org/html/2608.26324#S4)\)\. PrivBoN’s “privacy is free” threshold depends on the unknown coverage coefficientCπ∗C^\{\\pi^\{\*\}\}, making it unverifiable in practice\. Our main contribution, PrivITP, resolves this by combiningχ2\\chi^\{2\}\-regularized rejection sampling with a two\-phase Gaussian mechanism\. We prove an ex\-post approximate\-DP guarantee with annn\-independent bound that depends only on the realized halting time, via a*reformulation lemma*that maps ReLU\-based rejection sampling onto a randomized\-threshold mechanism\. The regret boundO⁡\(Cπ∗​\(εRM2\+Rmax​σ\)\)O\(\\sqrt\{C^\{\\pi^\{\*\}\}\(\\varepsilon\_\{\\mathrm\{RM\}\}^\{2\}\+R\_\{\\max\}\\sigma\)\}\)cleanly separates alignment error from privacy cost and matches the skyline up to noise inflation, whereRmaxR\_\{\\max\}is the maximum reward; the analysis relies on a*smoothed\-weight policy comparison lemma*that bounds value gaps via theℓ∞\\ell\_\{\\infty\}\-distance of policy weight functions\. The ex\-post structure further enables adaptive composition via the FSRC framework\[[16](https://arxiv.org/html/2608.26324#bib.bib11)\], answering substantially more queries under a fixed privacy budget than standard composition\.

\(3\) Empirical validation\([Section5](https://arxiv.org/html/2608.26324#S5)\)\. Across four reward models and two language models of varying sizes on GSM8K, MMLU, and MATH datasets, we demonstrate that the theoretical results hold: Private algorithms eliminate BoN’s reward\-hacking pathology while preserving its scaling benefits; PrivITP consistently matches or outperforms PrivBoN at matched privacy levels; and the ex\-post composition structure translates into substantial multi\-query deployment gains\.

PrivITP and PrivBoN are, to our knowledge, the first inference\-time alignment algorithms whose regret matches the information\-theoretic skyline under formal differential privacy guarantees\.

## 2Preliminaries

Inference\-time alignment\.We consider a setting in which a user submits a promptx∈𝒳x\\in\\mathcal\{X\}and the system must return a single responsey∈𝒴y\\in\\mathcal\{Y\}\. The system has access to a base language model \(the*reference policy*\)π0:𝒳→Δ⁡\(𝒴\)\\pi\_\{0\}:\\mathcal\{X\}\\to\\Delta\(\\mathcal\{Y\}\), assumed to have full support on𝒴\\mathcal\{Y\}, and a reward modelr^D:𝒳×𝒴→ℝ\\hat\{r\}\_\{D\}:\\mathcal\{X\}\\times\\mathcal\{Y\}\\to\\mathbb\{R\}trained on a datasetDD\. The true reward functionr∗:𝒳×𝒴→\[0,Rmax\]r^\{\*\}:\\mathcal\{X\}\\times\\mathcal\{Y\}\\to\[0,R\_\{\\max\}\]is unknown, and the trained reward modelr^D\\hat\{r\}\_\{D\}serves as its proxy\. The base policyπ0\\pi\_\{0\}is a trained language model \(e\.g\., an instruction\-tuned model using SFT and/or RLHF\), the true rewardr∗r^\{\*\}captures the desired objective \(e\.g\., alignment with human preferences or correctness under a proof checker\), and proxy rewardr^D\\hat\{r\}\_\{D\}is a custom\-trained model on a \(possibly sensitive\) datasetDD\.

Given a base policyπ0\\pi\_\{0\}, reward modelr^D\\hat\{r\}\_\{D\}, and a promptx∈𝒳x\\in\\mathcal\{X\}, the goal of the algorithm designer is to construct a policyπ^\\hat\{\\pi\}, which generates high\-quality responses as measured by the true rewardr∗​\(x,y\)r^\{\*\}\(x,y\)\. This is formalized using the notion of*inference\-time regret*\[[13](https://arxiv.org/html/2608.26324#bib.bib18)\]\. The*regret*of a policyπ^\\hat\{\\pi\}relative to a comparator policyπ∗\\pi^\{\*\}is defined as

Reg⁡\(π^,x\)=J⁡\(π∗,x\)−J⁡\(π^,x\),\\mathrm\{Reg\}\(\\hat\{\\pi\};x\)=J\(\\pi^\{\*\};x\)\-J\(\\hat\{\\pi\};x\),\(1\)whereJ\(π;x\)=𝔼y∼π\(⋅\|x\)\[r∗\(x,y\)\]J\(\\pi;x\)=\\mathbb\{E\}\_\{y\\sim\\pi\(\\cdot\|x\)\}\[r^\{\*\}\(x,y\)\]denotes the value of a policyπ\\pifor a given promptxx\.

Without assumptions on the accuracy of the reward modelr^D\\hat\{r\}\_\{D\}and on the coverage of the base policyπ0\\pi\_\{0\}, achieving low regret is not possible\[[13](https://arxiv.org/html/2608.26324#bib.bib18)\]\. To this end, define the reward model errorε⁡\(x,y\)=r∗​\(x,y\)−r^D​\(x,y\)\\varepsilon\(x,y\)=r^\{\*\}\(x,y\)\-\\hat\{r\}\_\{D\}\(x,y\)\. The expected squared error under the base policy,

εRM2\(x\)=𝔼y∼π0\(⋅\|x\)\[ε\(x,y\)2\],\\displaystyle\\varepsilon\_\{\\mathrm\{RM\}\}^\{2\}\(x\)=\\mathbb\{E\}\_\{y\\sim\\pi\_\{0\}\(\\cdot\|x\)\}\[\\varepsilon\(x,y\)^\{2\}\]~,measures the mean\-squared discrepancy between proxy and rewards\. We abstract away reward model training by assuming access to a modelr^D\\hat\{r\}\_\{D\}with squared\-errorεRM2​\(x\)\\varepsilon\_\{\\mathrm\{RM\}\}^\{2\}\(x\)and study how regret depends on this error and what algorithmic interventions can make it small\. The*χ2\\chi^\{2\}\-coverage coefficient*

Cπ\(x\)=𝔼y∼π\(⋅\|x\)\[π⁡\(y\|x\)π0​\(y\|x\)\]=1\+2χ2\(π\(⋅\|x\)∥π0\(⋅\|x\)\)C^\{\\pi\}\(x\)=\\mathbb\{E\}\_\{y\\sim\\pi\(\\cdot\|x\)\}\\left\[\\frac\{\\pi\(y\|x\)\}\{\\pi\_\{0\}\(y\|x\)\}\\right\]=1\+2\\,\\chi^\{2\}\(\\pi\(\\cdot\|x\)\\\|\\pi\_\{0\}\(\\cdot\|x\)\)measures how well the base policyπ0\\pi\_\{0\}covers a given policyπ\\pi, whereχ2\(p∥q\)\\chi^\{2\}\(p\\\|q\)denotes theχ2\\chi^\{2\}\-divergence between probability distributionsp,qp,q\. A comparator policyπ∗\\pi^\{\*\}with a largerCπ∗C^\{\\pi^\{\*\}\}indicates a harder alignment target\. Empirical studies have shown that standard language models provide sufficient coverage of high\-quality responses, enabling performance gains at inference time\[[13](https://arxiv.org/html/2608.26324#bib.bib18)\]\.[Huang et al\. \[13\]](https://arxiv.org/html/2608.26324#bib.bib18)lays down the importance of coverage by establishing a regret skyline in the*sample and evaluate*framework, where, for a given promptxx, the learner can samplennresponses\{yj\}j\\\{y\_\{j\}\\\}\_\{j\}from the base policyπ0\\pi\_\{0\}, and observe their likelihoodπ0​\(yj\|x\)\\pi\_\{0\}\(y\_\{j\}\|x\)and reward scoresr^D​\(x,yj\)\\hat\{r\}\_\{D\}\(x,y\_\{j\}\)\.

###### Proposition 2\.1\(Regret skyline\[[13](https://arxiv.org/html/2608.26324#bib.bib18)\]\)\.

Fix a promptxxand base policyπ0\\pi\_\{0\}\. For any inference\-time alignment algorithmπ^\\hat\{\\pi\}, there exist a reward functionr∗r^\{\*\}and reward modelr^D\\hat\{r\}\_\{D\}with errorεRM​\(x\)\\varepsilon\_\{\\mathrm\{RM\}\}\(x\)such thatReg⁡\(π,x\)≥14​Cπ∗​εRM2​\(x\)\\mathrm\{Reg\}\(\\pi;x\)\\geq\\tfrac\{1\}\{4\}\\sqrt\{C^\{\\pi^\{\*\}\}\\varepsilon\_\{\\mathrm\{RM\}\}^\{2\}\(x\)\}\.

This lower bound is tight:[Huang et al\. \[13\]](https://arxiv.org/html/2608.26324#bib.bib18)achieves it with InferenceTimePessimism, aχ2\\chi^\{2\}\-regularized rejection sampling algorithm\. A central question of this work is whether differential privacy – which requires adding noise that ostensibly degrades performance – can be achieved without exceeding this skyline\. To this end, we first formalize the privacy definitions\.

Differential privacy\.We protect the training dataDDof the reward model\. Two datasetsDDandD′D^\{\\prime\}from a database𝒟\\mathcal\{D\}are*adjacent*, writtenD∼D′D\\sim D^\{\\prime\}, if they differ in a single individual’s data\. The*sensitivity*of the reward model isΔr=supx,ysupD∼D′\|r^D​\(x,y\)−r^D′​\(x,y\)\|\\Delta\_\{r\}=\\sup\_\{x,y\}\\sup\_\{D\\sim D^\{\\prime\}\}\|\\hat\{r\}\_\{D\}\(x,y\)\-\\hat\{r\}\_\{D^\{\\prime\}\}\(x,y\)\|, which quantifies the maximum influence of any one training point on any reward score\.

###### Definition 2\.2\.

A randomized algorithmℳ:𝒟→𝒮\\mathcal\{M\}:\\mathcal\{D\}\\to\\mathcal\{S\}satisfies:

- •ε\\varepsilon\-DP ifPr\[ℳ\(D\)=s\]≤eεPr\[ℳ\(D′\)=s\]\\,\\Pr\[\\mathcal\{M\}\(D\)=s\]\\leq e^\{\\varepsilon\}\\Pr\[\\mathcal\{M\}\(D^\{\\prime\}\)=s\]\\,for alls∈𝒮s\\in\\mathcal\{S\}and allD∼D′D\\sim D^\{\\prime\}\.
- •\(ε,δ\)\(\\varepsilon,\\delta\)\-DP ifPr\[ℳ\(D\)=s\]≤eεPr\[ℳ\(D′\)=s\]\+δ\\,\\Pr\[\\mathcal\{M\}\(D\)=s\]\\leq e^\{\\varepsilon\}\\Pr\[\\mathcal\{M\}\(D^\{\\prime\}\)=s\]\+\\delta\\,for alls∈𝒮s\\in\\mathcal\{S\}and allD∼D′D\\sim D^\{\\prime\}\.
- •εp\\varepsilon\_\{p\}\-ex\-post DP if∃\\,\\exists\\,a functionεp:𝒟→𝒮\\varepsilon\_\{p\}:\\mathcal\{D\}\\to\\mathcal\{S\}such thatPr\[ℳ\(D\)=s\]≤eεp​\(s\)Pr\[ℳ\(D′\)=s\]\\,\\Pr\[\\mathcal\{M\}\(D\)=s\]\\leq e^\{\\varepsilon\_\{p\}\(s\)\}\\Pr\[\\mathcal\{M\}\(D^\{\\prime\}\)=s\]\\,for alls∈𝒮s\\in\\mathcal\{S\}and allD∼D′D\\sim D^\{\\prime\}\.

Traditional ex\-ante privacy\[[8](https://arxiv.org/html/2608.26324#bib.bib28)\]bounds the guarantee worst\-case over outcomes, before the mechanism’s randomness is realized; ex\-post privacy\[[16](https://arxiv.org/html/2608.26324#bib.bib11)\]bounds it conditional on the realized output, allowing queries with favorable outcomes to “save” budget for later queries under a fixed total\.

## 3PrivBoN: Private Best\-of\-N

We introduce the PrivBoN \(Private Best\-of\-N\) framework, which adds calibrated noise to reward scores before selection\. The mechanism is simple: samplenncandidatesy1,…,yny\_\{1\},\\ldots,y\_\{n\}independently fromπ0\(⋅\|x\)\\pi\_\{0\}\(\\cdot\|x\), perturb each reward scorer^D​\(x,yi\)\\hat\{r\}\_\{D\}\(x,y\_\{i\}\)with independent noisegig\_\{i\}, and return the candidate with the highest noisy reward\. The noise distribution determines the privacy guarantee and the induced policy\. We use theGumbel⁡\(0,σ\)\\mathrm\{Gumbel\}\(0,\\sigma\)distribution, which has the PDFf\(x\)=1σexp\(−x/σ−exp\(−x/σ\)\)f\(x\)=\\frac\{1\}\{\\sigma\}\\exp\\\!\\left\(\-x/\\sigma\-\\exp\(\-x/\\sigma\)\\right\)and the CDFF\(x\)=exp\(−exp\(−x/σ\)\)F\(x\)=\\exp\\\!\\left\(\-\\exp\(\-x/\\sigma\)\\right\)\.

Algorithm 1PrivBoN: Private Best\-of\-NN0:Prompt

xx, base policy

π0\\pi\_\{0\}, reward model

r^D\\hat\{r\}\_\{D\}, number of candidates

nn, noise scale

σ\>0\\sigma\>0
1:for

i=1i=1to

nndo

2:Sample candidate

yi∼π0\(⋅\|x\)y\_\{i\}\\sim\\pi\_\{0\}\(\\cdot\|x\)and noise

gi∼Gumbel⁡\(0,σ\)g\_\{i\}\\sim\\mathrm\{Gumbel\}\(0,\\sigma\)
3:Compute noisy reward

r~i←r^D​\(x,yi\)\+gi\\tilde\{r\}\_\{i\}\\leftarrow\\hat\{r\}\_\{D\}\(x,y\_\{i\}\)\+g\_\{i\}
4:endfor

5:return

yi∗y\_\{i^\{\*\}\}, where

i∗=arg​maxi⁡r~ii^\{\*\}=\{\\argmax\_\{i\}\\tilde\{r\}\_\{i\}\}

###### Theorem 3\.1\(PrivBoN privacy\)\.

Letr^D​\(x,y\)\\hat\{r\}\_\{D\}\(x,y\)be a reward model trained on a datasetDDwith sensitivityΔr\\Delta\_\{r\}\. Then,[Algorithm1](https://arxiv.org/html/2608.26324#alg1)withσ=2​Δr/ε\\sigma=2\\Delta\_\{r\}/\\varepsilonsatisfiesε\\varepsilon\-DP\.

The result follows from a classical connection: adding Gumbel noise and taking the argmax is equivalent to sampling from the softmax distribution \(thanks to the Gumbel\-max trick\), which is precisely the exponential mechanism of McSherry and Talwar\[[19](https://arxiv.org/html/2608.26324#bib.bib15)\]\. It also yields a clean, closed\-form expression for the induced policy, given below\.

###### Proposition 3\.2\(PrivBoN policy\)\.

PrivBoN with Gumbel noise induces the policy

πPrivBoN\(y\|x\)=nπ0\(y\|x\)𝔼y2:n∼π0\(⋅\|x\)\[er^D​\(x,y\)/σ∑j=1ner^D​\(x,yj\)/σ\],\\pi\_\{\\mathrm\{PrivBoN\}\}\(y\|x\)=n\\,\\pi\_\{0\}\(y\|x\)\\,\\mathbb\{E\}\_\{y\_\{2:n\}\\sim\\pi\_\{0\}\(\\cdot\|x\)\}\\\!\\left\[\\frac\{e^\{\\hat\{r\}\_\{D\}\(x,y\)/\\sigma\}\}\{\\sum\_\{j=1\}^\{n\}e^\{\\hat\{r\}\_\{D\}\(x,y\_\{j\}\)/\\sigma\}\}\\right\],wherey1=yy\_\{1\}=yis fixed andy2:ny\_\{2:n\}are drawn independently fromπ0\\pi\_\{0\}\. Assuming the reward distribution underπ0\\pi\_\{0\}is continuous, \(a\) it recovers the standard BoN policy asσ→0\\sigma\\to 0and \(b\) it converges pointwise to the KL\-regularized optimumπ∞​\(y\|x\)∝π0​\(y\|x\)​exp⁡\(r^D​\(x,y\)/σ\)\\pi\_\{\\infty\}\(y\|x\)\\propto\\pi\_\{0\}\(y\|x\)\\exp\(\\hat\{r\}\_\{D\}\(x,y\)/\\sigma\)asn→∞n\\to\\infty\.

Part \(b\) is the crucial structural property: PrivBoN implements, in the large\-nnlimit, the KL\-regularized optimummaxπ𝔼y∼π\[r^D\(x,y\)\]−σKL\(π∥π0\)\\max\_\{\\pi\}\\mathbb\{E\}\_\{y\\sim\\pi\}\[\\hat\{r\}\_\{D\}\(x,y\)\]\-\\sigma\\mathrm\{KL\}\(\\pi\\\|\\pi\_\{0\}\)\. The noise scaleσ\\sigmasimultaneously controls the privacy budget \(ε=2​Δr/σ\\varepsilon=2\\Delta\_\{r\}/\\sigma\) and the KL\-regularization strength—raising the question of whether the two impose compatible demands onσ\\sigma\.

### 3\.1Regret guarantee

We now analyze how the noise required for privacy affects alignment quality within the regret framework of[Huang et al\. \[13\]](https://arxiv.org/html/2608.26324#bib.bib18)\. Our main result is that privacy\-mandated noise implements exactly the regularization needed for optimal alignment whenever the privacy budget exceeds a thresholdε∗\\varepsilon^\{\*\}\.

###### Theorem 3\.3\(PrivBoN regret\)\.

Letr∗​\(x,y\)∈\[0,Rmax\]r^\{\*\}\(x,y\)\\in\[0,R\_\{\\max\}\]be the true reward andr^D​\(x,y\)\\hat\{r\}\_\{D\}\(x,y\)be a reward model trained on a datasetDD\. Let the reward model errorϵ⁡\(x,y\)∼𝒩⁡\(0,σr2​\(x\)\)\\epsilon\(x,y\)\\sim\\mathcal\{N\}\(0,\\sigma^\{2\}\_\{r\}\(x\)\)under the base policyπ0\\pi\_\{0\}\. Letπ∗\\pi^\{\*\}be any comparator policy with finite coverageCπ∗​\(x\)<∞C^\{\\pi^\{\*\}\}\(x\)<\\infty\. Then, forn=Ω~​\(e\(Rmax\+εRM\)/σ​log⁡\(Rmax/εRM\)𝐶𝐿𝑂𝑆𝐸n=\\widetilde\{\\Omega\}\\left\(e^\{\(R\_\{\\max\}\+\\varepsilon\_\{\\mathrm\{RM\}\}\)/\\sigma\}\\log\(R\_\{\\max\}/\\varepsilon\_\{\\mathrm\{RM\}\}\\right\), the regret of PrivBoN satisfies

Reg⁡\(πPrivBoN,x\)≲σ​Cπ∗​\(x\)⏟KL\-bias\+εRM2​\(x\)/σ⏟overoptimization\+Cπ∗​\(x\)​εRM​\(x\)⏟irreducible\+Rmax​eRmax\+εRM​log⁡nσn⏟finite sample\.\\mathrm\{Reg\}\(\\pi\_\{\\mathrm\{PrivBoN\}\};x\)\\lesssim\\underbrace\{\\sigma C^\{\\pi^\{\*\}\}\(x\)\}\_\{\\textup\{KL\-bias\}\}\+\\underbrace\{\\varepsilon\_\{\\mathrm\{RM\}\}^\{2\}\(x\)/\\sigma\}\_\{\\textup\{overoptimization\}\}\+\\underbrace\{\\sqrt\{C^\{\\pi^\{\*\}\}\(x\)\}\\,\\varepsilon\_\{\\mathrm\{RM\}\}\(x\)\}\_\{\\textup\{irreducible\}\}\+\\underbrace\{\\frac\{R\_\{\\max\}e^\{\\frac\{R\_\{\\max\}\+\\varepsilon\_\{\\mathrm\{RM\}\}\\sqrt\{\\log n\}\}\{\\sigma\}\}\}\{\\sqrt\{n\}\}\}\_\{\\textup\{finite sample\}\}\.\(2\)whereεRM2\(x\)=𝔼y∼π0\(⋅\|x\)\[ϵ\(x,y\)2\]=σr2\(x\)\\varepsilon\_\{\\mathrm\{RM\}\}^\{2\}\(x\)=\\mathbb\{E\}\_\{y\\sim\\pi\_\{0\}\(\\cdot\|x\)\}\[\\epsilon\(x,y\)^\{2\}\]=\\sigma\_\{r\}^\{2\}\(x\)is the reward model variance\.

Optimal noise scale\.The third term is the skyline itself\. The first two terms exhibit a bias\-variance tradeoff inσ\\sigma: a largeσ\\sigma\(strong regularization, strong privacy\) incurs bias from under\-exploiting the reward signal, whereas a smallσ\\sigma\(weak regularization, weak privacy\) incurs overoptimization from exploiting reward model errors\. Balancing the first two terms yieldsσ∗​\(x\)=εRM​\(x\)/Cπ∗​\(x\)\\sigma^\{\*\}\(x\)=\\varepsilon\_\{\\mathrm\{RM\}\}\(x\)/\\sqrt\{C^\{\\pi^\{\*\}\}\(x\)\}, at which the regret,

Reg⁡\(πPrivBoN,x\)≤3​Cπ∗​\(x\)​εRM2​\(x\),\\mathrm\{Reg\}\(\\pi\_\{\\mathrm\{PrivBoN\}\};x\)\\leq 3\\sqrt\{C^\{\\pi^\{\*\}\}\(x\)\\varepsilon\_\{\\mathrm\{RM\}\}^\{2\}\(x\)\}~,matches the information\-theoretic skyline \(Proposition[2\.1](https://arxiv.org/html/2608.26324#S2.Thmtheorem1)\) in the large\-nnlimit\.

“Privacy is free” threshold\.Whenσ\\sigmais set by the privacy budget \(σ=2​Δr/ε\\sigma=2\\Delta\_\{r\}/\\varepsilon\), the regret becomes

Reg⁡\(πPrivBoN,x\)≤2​Δr​Cπ∗​\(x\)ε\+ε⋅εRM2​\(x\)2​Δr\+Cπ∗​\(x\)​εRM​\(x\)\.\\mathrm\{Reg\}\(\\pi\_\{\\mathrm\{PrivBoN\}\};x\)\\leq\\frac\{2\\Delta\_\{r\}C^\{\\pi^\{\*\}\}\(x\)\}\{\\varepsilon\}\+\\frac\{\\varepsilon\\cdot\\varepsilon\_\{\\mathrm\{RM\}\}^\{2\}\(x\)\}\{2\\Delta\_\{r\}\}\+\\sqrt\{C^\{\\pi^\{\*\}\}\(x\)\}\\varepsilon\_\{\\mathrm\{RM\}\}\(x\)\.\(3\)The privacy\-mandated noiseσ\\sigmais no larger than the regret\-optimal noiseσ∗​\(x\)\\sigma^\{\*\}\(x\)precisely when

ε≥ε∗​\(x\)=2​Δr​Cπ∗​\(x\)εRM​\(x\)\.\\varepsilon\\geq\\varepsilon^\{\*\}\(x\)=\\frac\{2\\Delta\_\{r\}\\sqrt\{C^\{\\pi^\{\*\}\}\(x\)\}\}\{\\varepsilon\_\{\\mathrm\{RM\}\}\(x\)\}\.\(4\)For allε≥ε∗​\(x\)\\varepsilon\\geq\\varepsilon^\{\*\}\(x\), the regret matches the skyline: the noise required for privacy is no more than what alignment already needs\. E\.g\., for a reward model withεRM=0\.35,Δr=0\.1,Cπ∗=2\\varepsilon\_\{\\mathrm\{RM\}\}=0\.35,\\Delta\_\{r\}=0\.1,C^\{\\pi^\{\*\}\}=2, this givesε∗≈0\.8\\varepsilon^\{\*\}\\approx 0\.8, i\.e\., any privacy budget above 0\.8 is free\. Belowϵ<ε∗​\(x\)\\epsilon<\\varepsilon^\{\*\}\(x\), the first term in \([3](https://arxiv.org/html/2608.26324#S3.E3)\) dominates and the regret degrades gracefully asO⁡\(Δr​Cπ∗​\(x\)ε\+Cπ∗​\(x\)​εRM​\(x\)\)O\\left\(\\frac\{\\Delta\_\{r\}C^\{\\pi^\{\*\}\}\(x\)\}\{\\varepsilon\}\+\\sqrt\{C^\{\\pi^\{\*\}\}\(x\)\}\\varepsilon\_\{\\mathrm\{RM\}\}\(x\)\\right\)\.

The regret bound \([2](https://arxiv.org/html/2608.26324#S3.E2)\) goes down withnnforn≥n0​\(σ,Rmax,ϵRM\)n\\geq n\_\{0\}\(\\sigma,R\_\{\\max\},\\epsilon\_\{\\mathrm\{RM\}\}\), confirming that*more candidates never worsen the upper bound*, which rules out the catastrophic reward\-hacking regime of BoN where the bound degrades with an increase innn\. The finite\-sample term, however, carries anRmax​e\(Rmax\+ϵRM​log⁡n\)/σ/nR\_\{\\max\}e^\{\(R\_\{\\max\}\+\\epsilon\_\{\\mathrm\{RM\}\}\\sqrt\{\\log n\}\)/\\sigma\}/\\sqrt\{n\}prefactor: for typical values \(Rmax=5R\_\{\\max\}=5,σ=1\\sigma=1\) the asymptotic rate kicks in only forn≳104n\\gtrsim 10^\{4\}, and for moderatennthe regret behaves asO⁡\(Rmax​eRmax/σ/n\)O\(R\_\{\\max\}e^\{R\_\{\\max\}/\\sigma\}/\\sqrt\{n\}\)\. PrivITP \(Section[4](https://arxiv.org/html/2608.26324#S4)\) avoids this exponential dependence via rejection sampling\.

The Gaussian\-error assumption yields the closed\-form thresholdϵ∗​\(x\)\\epsilon^\{\*\}\(x\); under a general MSE assumption, the qualitative conclusions persist, but the threshold loses its closed form\. See Appendix[B\.4](https://arxiv.org/html/2608.26324#A2.SS4)\.

### 3\.2Reward hacking robustness

[Theorem3\.3](https://arxiv.org/html/2608.26324#S3.Thmtheorem3)establishes that PrivBoN achieves low regret\. A separate and complementary question is whether PrivBoN prevents*reward hacking*—the pathology where the selected response exploits errors in the proxy reward, yielding highr^D\\hat\{r\}\_\{D\}but lowr∗r^\{\*\}\[[9](https://arxiv.org/html/2608.26324#bib.bib16),[14](https://arxiv.org/html/2608.26324#bib.bib19)\]\. We quantify this through two measures: the win\-rate against the base policy and the hacking gap𝔼π^​\[ϵ​\(x,y\)\]\\mathbb\{E\}\_\{\\hat\{\\pi\}\}\[\\epsilon\(x,y\)\], which directly measures the extent to which the selected response overfits to reward\-model errors\. For a given promptxx, the win\-rate\[[10](https://arxiv.org/html/2608.26324#bib.bib17)\]of a policyπ^\\hat\{\\pi\}againstπ0\\pi\_\{0\}is

pπ^≻π0\|x=PrY∼π^,Y0∼π0⁡\(r^D​\(x,Y\)≥r^D​\(x,Y0\)\)\.p\_\{\\hat\{\\pi\}\\succ\\pi\_\{0\}\\mid x\}=\\Pr\_\{Y\\sim\\hat\{\\pi\},\\,Y\_\{0\}\\sim\\pi\_\{0\}\}\\bigl\(\\hat\{r\}\_\{D\}\(x,Y\)\\geq\\hat\{r\}\_\{D\}\(x,Y\_\{0\}\)\\bigr\)\.High win\-rate does not imply low regret whenr^D\\hat\{r\}\_\{D\}andr∗r^\{\*\}are mismatched: BoN achieves win\-raten/\(n\+1\)n/\(n\+1\)\[[2](https://arxiv.org/html/2608.26324#bib.bib14)\]while simultaneously incurring regretΩ~​\(εRM2​n\)\\widetilde\{\\Omega\}\(\\sqrt\{\\varepsilon\_\{\\mathrm\{RM\}\}^\{2\}n\}\)\[[13](https://arxiv.org/html/2608.26324#bib.bib18)\]\. The two quantities diverge precisely because BoN’s argmax overfits tor^D\\hat\{r\}\_\{D\}’s errors\. The following proposition shows that PrivBoN’s softmax selection caps both quantities at finite limits, eliminating this pathology\.

###### Proposition 3\.6\(Win\-rate saturation and bounded hacking\)\.

Letϵ⁡\(x,y\)∼𝒩⁡\(0,σr2​\(x\)\)\\epsilon\(x,y\)\\sim\\mathcal\{N\}\(0,\\sigma\_\{r\}^\{2\}\(x\)\)underπ0\\pi\_\{0\}\. Asn→∞n\\to\\infty, we have \(a\) BoN’s win\-rate converges to11, whereas PrivBoN’s saturates atΦ⁡\(σr​\(x\)/\(σ​2\)\)<1\\Phi\(\\sigma\_\{r\}\(x\)/\(\\sigma\\sqrt\{2\}\)\)<1and \(b\) BoN’s hacking gap grows without bound asO​\(σr​\(x\)​log⁡n\)O\(\\sigma\_\{r\}\(x\)\\sqrt\{\\log n\}\), while PrivBoN’s converges to the finite limitσr2​\(x\)/σ\\sigma\_\{r\}^\{2\}\(x\)/\\sigma\.

The finite saturation limits reflect the same mechanism: the privacy/regularization noiseσ\\sigmaprevents the selection from fully exploiting the reward signal, even with unlimited candidates\. Consequently, there exists a crossovern∗​\(σ,σr\)n^\{\*\}\(\\sigma,\\sigma\_\{r\}\)beyond which PrivBoN achieves strictly higher*true*reward than BoN – BoN’s expected true reward eventually decreases withnn\(Goodhart’s law\), while PrivBoN’s converges monotonically to𝔼π∞​\[r∗\]\\mathbb\{E\}\_\{\\pi\_\{\\infty\}\}\[r^\{\*\}\]\. For typical reward models \(e\.g\., Oasst on GSM8K dataset\),n∗n^\{\*\}falls well below100100\(see[Figure1](https://arxiv.org/html/2608.26324#S5.F1)\(top row\)\)\. Proofs are deferred to Appendix[B](https://arxiv.org/html/2608.26324#A2)\.

## 4Private Inference Time Pessimism

PrivBoN’s thresholdε∗​\(x\)\\varepsilon^\{\*\}\(x\)depends on the unknown coverage coefficientCπ∗​\(x\)C^\{\\pi^\{\*\}\}\(x\)\([4](https://arxiv.org/html/2608.26324#S3.E4)\), so a practitioner cannot verify whether their privacy budget falls in the free regime\. Private InferenceTimePessimism \(PrivITP\) resolves this by combining theχ2\\chi^\{2\}\-regularized rejection sampling of[Huang et al\. \[13\]](https://arxiv.org/html/2608.26324#bib.bib18)with calibrated noise injection, decoupling reward\-hacking mitigation \(controlled by the regularization\) from privacy \(controlled by the noise\)\.

Algorithm\.PrivITP operates in two phases, each consuming independent noise\. Phase 1 drawsnncandidates fromπ0\(⋅\|x\)\\pi\_\{0\}\(\\cdot\|x\)and privately releases the normalization constantλ~\\tilde\{\\lambda\}of theχ2\\chi^\{2\}\-regularized policy by adding Gaussian noise to the solutionλ\\lambdaof the empirical normalization equation \(we omit dependence onxxfor brevity\)\. Phase 2 draws a fresh batch ofnncandidates, perturbs their rewards with Gaussian noise, and performs rejection sampling with an acceptance thresholdλ~\\tilde\{\\lambda\}from Phase 1\. Independence of the two batches is essential for both the privacy and regret analyses; pseudocode appears in[Algorithm2](https://arxiv.org/html/2608.26324#alg2)\. The ReLU in the acceptance weights implements pessimism: candidates whose noisy reward falls belowλ~\\tilde\{\\lambda\}receive zero weight, discarding responses that the reward model does not confidently rank above the population average\. This mechanism prevents reward hacking independently of the injected noise, so privacy and alignment can be tuned separately \([Theorem4\.3](https://arxiv.org/html/2608.26324#S4.Thmtheorem3)\)\.

Algorithm 2Private InferenceTimePessimism \(PrivITP\)0:Prompt

xx, base policy

π0\\pi\_\{0\}, reward model

r^D\\hat\{r\}\_\{D\}, candidates

nn, regularization

β\>0\\beta\>0, noise scales

σX,σZ\>0\\sigma\_\{X\},\\sigma\_\{Z\}\>0, truncation parameter

LL
1:Phase 1 \(private normalization\):

2:Draw

y1,…,yn∼π0\(⋅\|x\)y\_\{1\},\\ldots,y\_\{n\}\\sim\\pi\_\{0\}\(\\cdot\|x\); compute

ri=r^D​\(x,yi\)r\_\{i\}=\\hat\{r\}\_\{D\}\(x,y\_\{i\}\)
3:Find

λ\\lambdasuch that

1n​∑i=1nrelu⁡\(β−1​\(ri−λ\)\)=1\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\mathrm\{relu\}\\big\(\\beta^\{\-1\}\(r\_\{i\}\-\\lambda\)\\big\)=1
4:Set

λ~=λ\+𝒩⁡\(0,σX2\)\\tilde\{\\lambda\}=\\lambda\+\\mathcal\{N\}\(0,\\sigma^\{2\}\_\{X\}\)and

M=\(Rmax\+σZ​L−λ~\)/βM=\(R\_\{\\max\}\+\\sigma\_\{Z\}L\-\\tilde\{\\lambda\}\)/\\beta
5:Phase 2 \(private rejection sampling\):

6:Draw fresh

y1′,…,yn′∼π0\(⋅\|x\)y\_\{1\}^\{\\prime\},\\ldots,y\_\{n\}^\{\\prime\}\\sim\\pi\_\{0\}\(\\cdot\|x\); compute

r~i=r^D​\(x,yi′\)\+𝒩⁡\(0,σZ2\)\\tilde\{r\}\_\{i\}=\\hat\{r\}\_\{D\}\(x,y\_\{i\}^\{\\prime\}\)\+\\mathcal\{N\}\(0,\\sigma\_\{Z\}^\{2\}\)
7:for

i=1i=1to

nndo

8:

wi←relu⁡\(β−1​\(r~i−λ~\)CLOSEw\_\{i\}\\leftarrow\\mathrm\{relu\}\\big\(\\beta^\{\-1\}\(\\tilde\{r\}\_\{i\}\-\\tilde\{\\lambda\}\\big\); sample

ξi∼Ber⁡\(min⁡\(wi/M,1\)\)\\xi\_\{i\}\\sim\\mathrm\{Ber\}\(\\min\(w\_\{i\}/M,1\)\)
9:if

ξi=1\\xi\_\{i\}=1then

10:return

yi′y\_\{i\}^\{\\prime\}
11:endif

12:endfor

13:return

yn\+1′∼π0\(⋅\|x\)y\_\{n\+1\}^\{\\prime\}\\sim\\pi\_\{0\}\(\\cdot\|x\)

Privacy guarantee\.Each phase accesses the datasetDDthrough reward evaluations\. The injected Gaussian noise in the normalizer in Phase 1 and in the rewards in Phase 2 ensures that the released quantities \(λ~\\tilde\{\\lambda\}from Phase 1 and the selected response from Phase 2\) are differentially private\.

###### Theorem 4\.1\(PrivITP privacy\)\.

Letr^D​\(x,⋅\)∈\[0,Rmax\]\\hat\{r\}\_\{D\}\(x,\\cdot\)\\in\[0,R\_\{\\max\}\]with sensitivityΔr\\Delta\_\{r\}\.[Algorithm2](https://arxiv.org/html/2608.26324#alg2)with Phase 1 scalar Gaussian noiseσX\\sigma\_\{X\}and Phase 2 query noiseσZ\\sigma\_\{Z\}satisfies\(ε1\+ε2post​\(t\),δ\)\(\\varepsilon\_\{1\}\+\\varepsilon\_\{2\}^\{\\mathrm\{post\}\}\(t\),\\,\\delta\)\-DP*ex\-post*, wherePhase 1contributes\(ε1,δ\)\(\\varepsilon\_\{1\},\\delta\)\-DP withε1=Δr​2​ln⁡\(1\.25/δ\)/σX\\varepsilon\_\{1\}=\\Delta\_\{r\}\\sqrt\{2\\ln\(1\.25/\\delta\)\}/\\sigma\_\{X\}andPhase 2contributes*pure*ex\-postε2post​\(t\)\\varepsilon\_\{2\}^\{\\mathrm\{post\}\}\(t\)\-DP, wherettis the halting time \(index of the first accepted candidate\):

ε2post​\(t\)=\(t−1\)​log⁡𝔼u∼Unif⁡\[0,1\]​\[Φ⁡\(λ~\+β​M​u−Rmax\+ΔrσZ\)\]𝔼u∼Unif⁡\[0,1\]​\[Φ​\(λ~\+β​M​u−RmaxσZ\)\]\+log⁡𝔼u∼Unif⁡\[0,1\]​\[Φ​\(Δr−λ~−β​M​uσZ\)\]𝔼u∼Unif⁡\[0,1\]​\[Φ​\(−λ~−β​M​uσZ\)\]\.\\varepsilon\_\{2\}^\{\\mathrm\{post\}\}\(t\)=\(t\-1\)\\,\\log\\frac\{\\displaystyle\\mathbb\{E\}\_\{u\\sim\\mathrm\{Unif\}\[0,1\]\}\\\!\\\!\\left\[\\Phi\\\!\\left\(\\tfrac\{\\tilde\{\\lambda\}\+\\beta Mu\-R\_\{\\max\}\+\\Delta\_\{r\}\}\{\\sigma\_\{Z\}\}\\right\)\\right\]\}\{\\displaystyle\\mathbb\{E\}\_\{u\\sim\\mathrm\{Unif\}\[0,1\]\}\\\!\\\!\\left\[\\Phi\\\!\\left\(\\tfrac\{\\tilde\{\\lambda\}\+\\beta Mu\-R\_\{\\max\}\}\{\\sigma\_\{Z\}\}\\right\)\\right\]\}\+\\log\\frac\{\\displaystyle\\mathbb\{E\}\_\{u\\sim\\mathrm\{Unif\}\[0,1\]\}\\\!\\\!\\left\[\\Phi\\\!\\left\(\\tfrac\{\\Delta\_\{r\}\-\\tilde\{\\lambda\}\-\\beta Mu\}\{\\sigma\_\{Z\}\}\\right\)\\right\]\}\{\\displaystyle\\mathbb\{E\}\_\{u\\sim\\mathrm\{Unif\}\[0,1\]\}\\\!\\\!\\left\[\\Phi\\\!\\left\(\\tfrac\{\-\\tilde\{\\lambda\}\-\\beta Mu\}\{\\sigma\_\{Z\}\}\\right\)\\right\]\}\.

Unlike standard privacy composition overnncandidates \(which gives a worst\-case bound proportional tonn\),[Theorem4\.1](https://arxiv.org/html/2608.26324#S4.Thmtheorem1)gives a bound, which is independent ofnn, computable via one\-dimensional numerical integration and proportional to the*actual halting time*tt\. The coefficient of the linear term,

κ:=log⁡𝔼u​\[Φ⁡\(\(λ~\+β​M​u−Rmax\+Δr\)/σZ\)\]𝔼u​\[Φ⁡\(\(λ~\+β​M​u−Rmax\)/σZ\)\],\\kappa:=\\log\\frac\{\\mathbb\{E\}\_\{u\}\[\\Phi\(\(\\tilde\{\\lambda\}\+\\beta Mu\-R\_\{\\max\}\+\\Delta\_\{r\}\)/\\sigma\_\{Z\}\)\]\}\{\\mathbb\{E\}\_\{u\}\[\\Phi\(\(\\tilde\{\\lambda\}\+\\beta Mu\-R\_\{\\max\}\)/\\sigma\_\{Z\}\)\]\},is the per\-round privacy cost of rejection, which depends on the relative positions ofλ~\\tilde\{\\lambda\},RmaxR\_\{\\max\}, andσZ\\sigma\_\{Z\}\. WhenσZ\\sigma\_\{Z\}is large relative toΔr\\Delta\_\{r\}\(strong privacy\),κ\\kappais small; whenσZ\\sigma\_\{Z\}is comparable toΔr\\Delta\_\{r\},κ\\kappadominates the privacy budget\. The bound requires the reward model’s outputs to lie in a bounded range\[0,Rmax\]\[0,R\_\{\\max\}\], which is a mild assumption in practice as reward models for language alignment are typically trained with bounded output heads \(e\.g\., sigmoid or clipped outputs\)\[[13](https://arxiv.org/html/2608.26324#bib.bib18)\]\.

Regret guarantee\.We now analyze the regret of PrivITP against an arbitrary comparator policyπ∗\\pi^\{\*\}\. The central result is that PrivITP achieves the information\-theoretic skyline \(Proposition[2\.1](https://arxiv.org/html/2608.26324#S2.Thmtheorem1)\)with a noise inflation and it does so while satisfying pure ex\-postε\\varepsilon\-DP \([Theorem4\.1](https://arxiv.org/html/2608.26324#S4.Thmtheorem1)\)\.

###### Theorem 4\.3\(PrivITP regret\)\.

Letr∗​\(x,y\)∈\[0,Rmax\]r^\{\*\}\(x,y\)\\in\[0,R\_\{\\max\}\]be the true \(unknown\) reward andr^D:𝒳×𝒴→\[0,Rmax\]\\hat\{r\}\_\{D\}\\colon\\mathcal\{X\}\\times\\mathcal\{Y\}\\to\[0,R\_\{\\max\}\]be a reward model trained on a datasetDDwith mean\-squared errorεRM2​\(x\)=𝔼y∼π0​\(x\)​\[\(r^D​\(x,y\)−r∗​\(x,y\)\)2\]\\varepsilon\_\{\\mathrm\{RM\}\}^\{2\}\(x\)=\\mathbb\{E\}\_\{y\\sim\\pi\_\{0\}\(x\)\}\[\(\\hat\{r\}\_\{D\}\(x,y\)\-r^\{\*\}\(x,y\)\)^\{2\}\]\. Letπ∗\\pi^\{\*\}be any comparator policy with finite coverageCπ∗​\(x\)<∞C^\{\\pi^\{\*\}\}\(x\)<\\infty\. For regularizationβ≥2​σX\\beta\\geq 2\\sigma\_\{X\}, truncation parameterL=O⁡\(log⁡n\)L=O\(\\log n\)andn=max⁡\{Ω⁡\(Rmaxβ​log⁡\(Rmaxβ​ϵRM\)\),Ω~​\(Rmax\+σZβ\)\}n=\\max\\left\\\{\\Omega\\\!\\left\(\\frac\{R\_\{\\max\}\}\{\\beta\}\\log\\\!\\left\(\\frac\{R\_\{\\max\}\}\{\\beta\\,\\epsilon\_\{\\mathrm\{RM\}\}\}\\right\)\\right\),\\widetilde\{\\Omega\}\\left\(\\frac\{R\_\{\\max\}\+\\sigma\_\{Z\}\}\{\\beta\}\\right\)\\right\\\}, PrivITP \([Algorithm2](https://arxiv.org/html/2608.26324#alg2)\) satisfies

Reg⁡\(πPrivITP,x\)≲β⋅Cπ∗​\(x\)⏟χ2​bias\+β−1​\(εRM2​\(x\)\+Rmax​σ\)⏟overoptimization\+noise\+Cπ∗​\(x\)​εRM​\(x\)⏟irreducible\+Rmax/n⏟finite sample,\\mathrm\{Reg\}\(\\pi\_\{\\mathrm\{PrivITP\}\};x\)\\lesssim\\underbrace\{\\beta\\cdot C^\{\\pi^\{\*\}\}\(x\)\}\_\{\\chi^\{2\}\\text\{ bias\}\}\+\\underbrace\{\\beta^\{\-1\}\(\\varepsilon\_\{\\mathrm\{RM\}\}^\{2\}\(x\)\+R\_\{\\max\}\\sigma\)\}\_\{\\text\{overoptimization\+noise\}\}\+\\underbrace\{\\sqrt\{C^\{\\pi^\{\*\}\}\(x\)\}\\varepsilon\_\{\\mathrm\{RM\}\}\(x\)\}\_\{\\text\{irreducible\}\}\+\\underbrace\{R\_\{\\max\}/\\sqrt\{n\}\}\_\{\\text\{finite sample\}\},\(5\)whereσ=σX\+σZ\\sigma=\\sigma\_\{X\}\+\\sigma\_\{Z\}denotes the total noise level\.

As with PrivBoN, the bound in \([5](https://arxiv.org/html/2608.26324#S4.E5)\) is non\-increasing innnforn≥n0​\(β,σZ,Rmax,ϵRM\)n\\geq n\_\{0\}\(\\beta,\\sigma\_\{Z\},R\_\{\\max\},\\epsilon\_\{\\mathrm\{RM\}\}\), ruling out the reward\-hacking regime where adding candidates provably degrades performance\.

Optimal regularization\.The first two terms exhibit a bias\-variance tradeoff inβ\\beta: a largeσ\\sigma\(strong regularization\) incurs bias from under\-exploiting the reward signal, whereas a smallβ\\beta\(weak regularization\) incurs overoptimization from exploiting reward model errors\. Balancing the first two terms yieldsβ∗​\(x\)=\(εRM2​\(x\)\+Rmax​σ\)/Cπ∗​\(x\)\\beta^\{\*\}\(x\)=\\sqrt\{\(\\varepsilon\_\{\\mathrm\{RM\}\}^\{2\}\(x\)\+R\_\{\\max\}\\sigma\)/C^\{\\pi^\{\*\}\}\(x\)\}, at which the regret,

Reg⁡\(πPrivITP,x\)≤3​Cπ∗​\(x\)​\(εRM2​\(x\)\+Rmax​σ\),\\mathrm\{Reg\}\(\\pi\_\{\\mathrm\{PrivITP\}\};x\)\\leq 3\\sqrt\{C^\{\\pi^\{\*\}\}\(x\)\\big\(\\varepsilon\_\{\\mathrm\{RM\}\}^\{2\}\(x\)\+R\_\{\\max\}\\sigma\\big\)\}~,matches the information\-theoretic skyline \(proposition[2\.1](https://arxiv.org/html/2608.26324#S2.Thmtheorem1)\) in the large\-nnlimit \(up to the noise inflation due to privacy\)\. Proofs are deferred to Appendix[C](https://arxiv.org/html/2608.26324#A3)\.

Privacy\-mandated noise\.The Phase 2 query noiseσZ\\sigma\_\{Z\}governs the pure ex\-post pure\-DP guarantee of[Theorem4\.1](https://arxiv.org/html/2608.26324#S4.Thmtheorem1): smallerσZ\\sigma\_\{Z\}yields larger per\-query privacy costε2post​\(t\)\\varepsilon\_\{2\}^\{\\mathrm\{post\}\}\(t\)\. To quantify the trade\-off, we use the order\-of\-magnitude relation obtained by linearizing \([4\.1](https://arxiv.org/html/2608.26324#S4.Ex6)\) in the small\-Δr/σZ\\Delta\_\{r\}/\\sigma\_\{Z\}regime: the per\-round log\-ratio is of orderΔr/σZ\\Delta\_\{r\}/\\sigma\_\{Z\}, givingε2post​\(t\)≍t⋅Δr/σZ\\varepsilon\_\{2\}^\{\\mathrm\{post\}\}\(t\)\\asymp t\\cdot\\Delta\_\{r\}/\\sigma\_\{Z\}, or equivalentlyσZ≍t⋅Δr/ε2post​\(t\)\\sigma\_\{Z\}\\asymp t\\cdot\\Delta\_\{r\}/\\varepsilon\_\{2\}^\{\\mathrm\{post\}\}\(t\)\. For Phase 1 per\-query privacy cost\(ε1,δ\)\(\\varepsilon\_\{1\},\\delta\), we set noiseσX≍Δr​ln⁡\(1/δ\)/ε1\\sigma\_\{X\}\\asymp\\Delta\_\{r\}\\sqrt\{\\ln\(1/\\delta\)\}/\\varepsilon\_\{1\}\. Substituting into \([4](https://arxiv.org/html/2608.26324#S4.Ex8)\) yields the privacy\-mandated regret bound

Reg⁡\(πPrivITP,x\)≤3​Cπ∗​\(x\)​\(εRM2​\(x\)\+Rmax⋅t​Δrε2post​\(t\)\+Rmax​Δr​ln⁡\(1/δ\)ϵ1\)\.\\mathrm\{Reg\}\(\\pi\_\{\\mathrm\{PrivITP\}\};x\)\\leq 3\\sqrt\{C^\{\\pi^\{\*\}\}\(x\)\\\!\\left\(\\varepsilon\_\{\\mathrm\{RM\}\}^\{2\}\(x\)\+\\frac\{R\_\{\\max\}\\cdot t\\Delta\_\{r\}\}\{\\varepsilon\_\{2\}^\{\\mathrm\{post\}\}\(t\)\}\+\\frac\{R\_\{\\max\}\\Delta\_\{r\}\\sqrt\{\\ln\(1/\\delta\)\}\}\{\\epsilon\_\{1\}\}\\right\)\}\.\(6\)On the relationship to prior work\.PrivITP combines theχ2\\chi^\{2\}\-regularized rejection sampling of[Huang et al\. \[13\]](https://arxiv.org/html/2608.26324#bib.bib18)with the Gaussian above\-threshold mechanism of[Lebensold et al\. \[16\]](https://arxiv.org/html/2608.26324#bib.bib11)\. The technical novelty lies in the analysis of privacy and regret: \(i\) a reformulation lemma mapping PrivITP’s ReLU acceptance weights onto a randomized\-threshold mechanism, enabling annn\-independent ex\-post DP bound \(Lemma[C\.1](https://arxiv.org/html/2608.26324#A3.Thmtheorem1)\); \(ii\) a smoothed\-weight policy comparison lemma unifying regret analysis across threshold noise, query noise, and finite\-sample effects \(Lemma[C\.3](https://arxiv.org/html/2608.26324#A3.Thmtheorem3)\); and \(iii\) a regret\-optimality proof \(Theorem[4\.3](https://arxiv.org/html/2608.26324#S4.Thmtheorem3)\) showing PrivITP matches[Huang et al\. \[13\]](https://arxiv.org/html/2608.26324#bib.bib18)skyline up to anRmax​σR\_\{\\max\}\\sigmanoise\-inflation term that cleanly separates alignment error from privacy cost\.

### 4\.1Multi\-Query Deployment

In deployment, an aligned language model answers a stream ofTTprompts and produces a transcript of responses\(y∗\(1\),…,y∗\(T\)\)\(y^\{\*\(1\)\},\\ldots,y^\{\*\(T\)\}\)\. Each query consumes some privacy budget; the question is how to allocate this budget across queries to maximize alignment quality over the lifetime of the deployment\. PrivITP’s ex\-post privacy guarantee \([Theorem4\.1](https://arxiv.org/html/2608.26324#S4.Thmtheorem1)\) provides a structural advantage: the privacy cost of each query depends on the actual halting timett, not on the worst\-case budgetnn\. When rejection sampling accepts early – the typical case for informative reward models, where𝔼⁡\[t\]=O⁡\(1\)\\mathbb\{E\}\[t\]=O\(1\)– the per\-query privacy cost is much smaller than the worst\-case bound\. The FSRC framework of[Lebensold et al\. \[16, Alg\. 2\]](https://arxiv.org/html/2608.26324#bib.bib11)is designed to exploit this structure: it composes mechanisms with ex\-post privacy guarantees and halts when the cumulative privacy cost exceeds the total budget\.

###### Proposition 4\.5\(PrivITP composition via FSRC\)\.

[Algorithm3](https://arxiv.org/html/2608.26324#alg3)satisfies\(εtotal,δ\)\(\\varepsilon\_\{\\mathrm\{total\}\},\\delta\)\-DP under fully\-adaptive query selection\. The expected number of queries answered before halting is𝔼⁡\[T∗\]≥εtotal𝔼⁡\[ετ\]\\mathbb\{E\}\[T^\{\*\}\]\\geq\\frac\{\\varepsilon\_\{\\mathrm\{total\}\}\}\{\\mathbb\{E\}\[\\varepsilon\_\{\\tau\}\]\}, where𝔼⁡\[ετ\]\\mathbb\{E\}\[\\varepsilon\_\{\\tau\}\]is the expected per\-query privacy cost under the distribution of halting timestτt\_\{\\tau\}induced by the noisy reward distribution\.

In the favorable regime where𝔼⁡\[ετ\]≪εmax\\mathbb\{E\}\[\\varepsilon\_\{\\tau\}\]\\ll\\varepsilon\_\{\\max\}, whereϵmax:=ϵ1\+ϵ2post​\(n\)\\epsilon\_\{\\max\}:=\\epsilon\_\{1\}\+\\epsilon\_\{2\}^\{\\mathrm\{post\}\}\(n\)is the worst\-case per\-query cost, FSRC\-composed PrivITP answersΘ⁡\(εmax/𝔼⁡\[ετ\]\)\\Theta\(\\varepsilon\_\{\\max\}/\\mathbb\{E\}\[\\varepsilon\_\{\\tau\}\]\)times more queries than standard composition for the same total budget\. FSRC strictly dominates privacy filters\[[22](https://arxiv.org/html/2608.26324#bib.bib9)\], which must charge the worst\-case per\-query cost rather than the realized ex\-post cost \(see Remark[D\.1](https://arxiv.org/html/2608.26324#A4.Thmtheorem1)\)

## 5Experiments

Figure 1:Experiments for Phi\-3\-Mini\-Instruct policy and Gemma\-RM on the GSM8K test split\.*Top row*demonstrates reward hacking in BoN and its mitigation by PrivBoN, ITP, and PrivITP\.*Bottom left*shows privacy vs\. utility trade\-off in ITP: low noise \(low privacy\) leads to better accuracy, and vice versa\.*Bottom right*demonstrates the advantage of FSRC composition in PrivITP’s ex\-post privacy bound compared to the standard composition in ex\-ante bound\.Table 1:Percentage lift in accuracy over base policyPhi\-3\-Mini\-Instructatn=212n=2^\{12\}candidates\. Values are mean±\\pmstandard error over all prompts across the GSM8K, MMLU, and MATH test splits\. Same \(RM, dataset\) configuration uses the same noiseσ\\sigmafor private variants and the same regularizationβ\\betafor ITP variants\.We validate our theoretical results following the experimental setup of[Huang et al\. \[13\]](https://arxiv.org/html/2608.26324#bib.bib18): four reward models \(Oasst \(1\.4B\), Gemma \(2B\), Llama \(3B\), and Armo \(7B\)\) and two base LMs \(Phi3\-Mini\-Instruct and Gemma\-2\-2B\-Instruct\) evaluated on test splits of GSM8K\[[5](https://arxiv.org/html/2608.26324#bib.bib29)\], MATH\-500\[[12](https://arxiv.org/html/2608.26324#bib.bib32)\], and math, chemistry splits of MMLU\[[11](https://arxiv.org/html/2608.26324#bib.bib31)\]\. For each prompt, we sample1000010000responses from base policy at temperature11with zero\-shot CoT prompting\[[28](https://arxiv.org/html/2608.26324#bib.bib30)\], then bootstrapM=50M=50replicates of each sample to run each of the four algorithms: BoN, PrivBoN, ITP, and PrivITP\. Unless otherwise mentioned, private algorithms use the same noiseσ\\sigma\(for PrivITP, we setσX=σZ=σ/2\\sigma\_\{X\}=\\sigma\_\{Z\}=\\sigma/2\), and ITP variants use the same regularizationβ\\betaon the same \(RM, dataset\) configuration\. Ablation studies on the noise levelσ\\sigma\(equivalently, on privacy budgetϵ\\epsilon\) and regularizationβ\\betaare presented in Appendix[F](https://arxiv.org/html/2608.26324#A6)\.

Scaling behavior across algorithms \(Theorems[3\.3](https://arxiv.org/html/2608.26324#S3.Thmtheorem3),[4\.3](https://arxiv.org/html/2608.26324#S4.Thmtheorem3)\)\.[Figure1](https://arxiv.org/html/2608.26324#S5.F1)\(top row\) shows % percentage lift in accuracy over base policy Phi3\-Mini and expected proxy reward under Gemma\-RM for GSM8K as we varynn\. We observe \(i\) BoN’s accuracy rises then falls withnn, exhibiting reward hacking, while its proxy reward rises monotonically—the signature of overfitting tor^𝒟\\hat\{r\}\_\{\\mathcal\{D\}\}; \(ii\) PrivBoN and PrivITP accuracies are monotone innn, confirming hacking mitigation; \(iii\) PrivITP matches or exceeds PrivBoN at the same noise level\.[Figure1](https://arxiv.org/html/2608.26324#S5.F1)\(bottom left\) shows that PrivITP approaches the non\-private ITP skyline as noise \(and hence, privacy\) decreases\. Figures for other RMs are in Appendix[F](https://arxiv.org/html/2608.26324#A6)\.

Generalization across RMs and datasets\.Atn=212n=2^\{12\}, we report the percentage lift in accuracy over Phi3\-Mini\-Instruct base policy for each \(algorithm, RM, dataset\) configuration in[Table2](https://arxiv.org/html/2608.26324#A6.T2)\. PrivITP dominates PrivBoN on every \(RM, dataset\) configuration, and on GSM8K it recovers between 84% and 98% of the non\-private ITP skyline across all four reward models\. On MMLU and MATH, PrivITP again closely tracks ITP within standard error\. The reward\-hacking signature in BoN is most pronounced for the weaker RMs \(Oasst, Gemma\), while PrivITP recovers near\-skyline performance in each case\. For stronger RMs \(Llama, Armo\) on GSM8K and MATH, BoN remains competitive atn=212n=2^\{12\}, which indicates that reward\-hacking pressure is delayed when the base policy has lower accuracy\. Results for Gemma2\-2B\-Instruct base model are in Appendix[F](https://arxiv.org/html/2608.26324#A6)\.

Multi\-query deployment via FSRC \(Proposition[4\.5](https://arxiv.org/html/2608.26324#S4.Thmtheorem5)\)\.To validate the composition advantage of PrivITP’s ex\-post structure, we compare the number of GSM8K queries answered before budget exhaustion under \(a\) FSRC\-composed PrivITP, \(b\) PrivITP basic composition \(worst\-case per\-query costεmax=ε1\+ε2post​\(n\)\\varepsilon\_\{\\max\}=\\varepsilon\_\{1\}\+\\varepsilon\_\{2\}^\{\\mathrm\{post\}\}\(n\)\) sweeping over noiseσ\\sigma\. We fixn=16n=16,β=0\.05\\beta=0\.05and total privacy budgetεtotal=50\\varepsilon\_\{\\text\{total\}\}=50, Under Gemma\-RM and across 10 random seeds,[Figure1](https://arxiv.org/html/2608.26324#S5.F1)\(bottom right\) shows that FSRC answers∼3×\\sim\\\!3\\timesmore queries, with empirical halting timetτ≪nt\_\{\\tau\}\\ll n, confirming Remark[4\.2](https://arxiv.org/html/2608.26324#S4.Thmtheorem2)\. Similar behavior is observed for other RMs, and plots are in Appendix[F](https://arxiv.org/html/2608.26324#A6)\.

Conclusion\.We have shown that differential privacy and reward\-hacking mitigation are two instances of the same intervention: softening the hard argmax in Best\-of\-N selection\. For PrivBoN, the privacy\-mandated scale coincides with the regret\-optimal KL temperature above a thresholdε∗\\varepsilon^\{\*\}, making privacy “free”; PrivITP extends this toχ2\\chi^\{2\}\-regularized rejection sampling, decoupling the privacy and regularization parameters, and yielding ex\-post DP withnn\-independent composition\. Open directions include extending to sequential test\-time alignment\[[32](https://arxiv.org/html/2608.26324#bib.bib24)\]and connecting inference\-time privacy to training\-time private alignment\[[31](https://arxiv.org/html/2608.26324#bib.bib3)\]for end\-to\-end guarantees\.

## References

- \[1\]G\. Aminian, I\. Shenfeld, A\. R\. Asadi, A\. Beirami, and Y\. MrouehBest\-of\-n through the smoothing lens: kl divergence and regret analysis\.InES\-FoMo III: 3rd Workshop on Efficient Systems for Foundation Models,Cited by:[Appendix A](https://arxiv.org/html/2608.26324#A1.p1.1),[§1](https://arxiv.org/html/2608.26324#S1.p2.1),[Remark 3\.5](https://arxiv.org/html/2608.26324#S3.Thmtheorem5.p1.1.1)\.
- \[2\]A\. Beirami, A\. Agarwal, J\. Berant, A\. D’Amour, J\. Eisenstein, C\. Nagpal, and A\. T\. Suresh\(2025\)Theoretical guarantees on the best\-of\-n alignment policy\.InInternational Conference on Machine Learning,pp\. 3580–3602\.Cited by:[Appendix A](https://arxiv.org/html/2608.26324#A1.p1.1),[§1](https://arxiv.org/html/2608.26324#S1.p2.1),[§3\.2](https://arxiv.org/html/2608.26324#S3.SS2.p1.2)\.
- \[3\]N\. Carlini, F\. Tramer, E\. Wallace, M\. Jagielski, A\. Herbert\-Voss, K\. Lee, A\. Roberts, T\. Brown, D\. Song, U\. Erlingsson,et al\.\(2021\)Extracting training data from large language models\.In30th USENIX security symposium \(USENIX Security 21\),pp\. 2633–2650\.Cited by:[§1](https://arxiv.org/html/2608.26324#S1.p3.1)\.
- \[4\]P\. F\. Christiano, J\. Leike, T\. Brown, M\. Martic, S\. Legg, and D\. Amodei\(2017\)Deep reinforcement learning from human preferences\.Advances in neural information processing systems30\.Cited by:[§1](https://arxiv.org/html/2608.26324#S1.p1.1)\.
- \[5\]K\. Cobbe, V\. Kosaraju, M\. Bavarian, M\. Chen, H\. Jun, L\. Kaiser, M\. Plappert, J\. Tworek, J\. Hilton, R\. Nakano, C\. Hesse, and J\. Schulman\(2021\)Training verifiers to solve math word problems\.arXiv preprint arXiv:2110\.14168\.Cited by:[§F\.1](https://arxiv.org/html/2608.26324#A6.SS1.p2.1),[§5](https://arxiv.org/html/2608.26324#S5.p1.1)\.
- \[6\]D\. Durfee and R\. M\. Rogers\(2019\)Practical differentially private top\-k selection with pay\-what\-you\-get composition\.Advances in Neural Information Processing Systems32\.Cited by:[Appendix A](https://arxiv.org/html/2608.26324#A1.p2.1)\.
- \[7\]C\. Dwork and V\. Feldman\(2018\)Privacy\-preserving prediction\.InConference On Learning Theory,pp\. 1693–1702\.Cited by:[Appendix A](https://arxiv.org/html/2608.26324#A1.p2.1)\.
- \[8\]C\. Dwork and A\. Roth\(2014\)The algorithmic foundations of differential privacy\.Foundations and trends® in theoretical computer science9\(3\-4\),pp\. 211–487\.Cited by:[§C\.1](https://arxiv.org/html/2608.26324#A3.SS1.p5.1.2),[§2](https://arxiv.org/html/2608.26324#S2.p6.1)\.
- \[9\]L\. Gao, J\. Schulman, and J\. Hilton\(2023\)Scaling laws for reward model overoptimization\.InInternational Conference on Machine Learning,pp\. 10835–10866\.Cited by:[§1](https://arxiv.org/html/2608.26324#S1.p2.1),[§3\.2](https://arxiv.org/html/2608.26324#S3.SS2.p1.1)\.
- \[10\]L\. Gui, C\. Gârbacea, and V\. Veitch\(2024\)Bonbon alignment for large language models and the sweetness of best\-of\-n sampling\.Advances in Neural Information Processing Systems37,pp\. 2851–2885\.Cited by:[§1](https://arxiv.org/html/2608.26324#S1.p1.1),[§3\.2](https://arxiv.org/html/2608.26324#S3.SS2.p1.1)\.
- \[11\]D\. Hendrycks, C\. Burns, S\. Basart, A\. Zou, M\. Mazeika, D\. Song, and J\. Steinhardt\(2020\)Measuring massive multitask language understanding\.arXiv preprint arXiv:2009\.03300\.Cited by:[§F\.1](https://arxiv.org/html/2608.26324#A6.SS1.p2.1),[§5](https://arxiv.org/html/2608.26324#S5.p1.1)\.
- \[12\]D\. Hendrycks, C\. Burns, S\. Kadavath, A\. Arora, S\. Basart, E\. Tang, D\. Song, and J\. Steinhardt\(2021\)Measuring mathematical problem solving with the math dataset\.NeurIPS\.Cited by:[§F\.1](https://arxiv.org/html/2608.26324#A6.SS1.p2.1),[§5](https://arxiv.org/html/2608.26324#S5.p1.1)\.
- \[13\]A\. Huang, A\. Block, Q\. Liu, N\. Jiang, A\. Krishnamurthy, and D\. J\. Foster\(2025\)Is best\-of\-n the best of them? coverage, scaling, and optimality in inference\-time alignment\.InInternational Conference on Machine Learning,pp\. 25075–25126\.Cited by:[Appendix A](https://arxiv.org/html/2608.26324#A1.p1.1),[§C\.2](https://arxiv.org/html/2608.26324#A3.SS2.p17.1.1),[§C\.2](https://arxiv.org/html/2608.26324#A3.SS2.p2.2.1),[§C\.2](https://arxiv.org/html/2608.26324#A3.SS2.p5.1.1.1),[§F\.4](https://arxiv.org/html/2608.26324#A6.SS4.p2.1),[§1](https://arxiv.org/html/2608.26324#S1.p2.1),[§1](https://arxiv.org/html/2608.26324#S1.p6.1),[Proposition 2\.1](https://arxiv.org/html/2608.26324#S2.Thmtheorem1),[§2](https://arxiv.org/html/2608.26324#S2.p2.1),[§2](https://arxiv.org/html/2608.26324#S2.p3.1),[§2](https://arxiv.org/html/2608.26324#S2.p3.3),[§2](https://arxiv.org/html/2608.26324#S2.p4.1),[§3\.1](https://arxiv.org/html/2608.26324#S3.SS1.p1.1),[§3\.2](https://arxiv.org/html/2608.26324#S3.SS2.p1.2),[Remark 3\.5](https://arxiv.org/html/2608.26324#S3.Thmtheorem5.p1.1.1),[§4](https://arxiv.org/html/2608.26324#S4.p1.1),[§4](https://arxiv.org/html/2608.26324#S4.p4.2),[§4](https://arxiv.org/html/2608.26324#S4.p8.2),[§5](https://arxiv.org/html/2608.26324#S5.p1.1),[Abstract](https://arxiv.org/html/2608.26324#abstract1.1)\.
- \[14\]H\. Khalaf, C\. M\. Verdun, A\. Oesterling, H\. Lakkaraju, and F\. CalmonInference\-time reward hacking in large language models\.InThe Thirty\-ninth Annual Conference on Neural Information Processing Systems,Cited by:[Appendix A](https://arxiv.org/html/2608.26324#A1.p1.1),[§1](https://arxiv.org/html/2608.26324#S1.p2.1),[§3\.2](https://arxiv.org/html/2608.26324#S3.SS2.p1.1),[Remark 3\.5](https://arxiv.org/html/2608.26324#S3.Thmtheorem5.p1.1.1)\.
- \[15\]S\. Kim, J\. Shin, Y\. Cho, J\. Jang, S\. Lu, and M\. Seo\(2024\)Prometheus 2: an open source language model specialized in evaluating other language models\.arXiv preprint arXiv:2405\.01535\.Cited by:[§G\.1](https://arxiv.org/html/2608.26324#A7.SS1.p1.1)\.
- \[16\]J\. Lebensold, D\. Precup, and B\. Balle\(2024\)On the privacy of selection mechanisms with gaussian noise\.InInternational Conference on Artificial Intelligence and Statistics,pp\. 1495–1503\.Cited by:[Remark D\.1](https://arxiv.org/html/2608.26324#A4.Thmtheorem1.p1.1.1),[Appendix D](https://arxiv.org/html/2608.26324#A4.p1.1.1),[Appendix E](https://arxiv.org/html/2608.26324#A5.p2.1.1),[Appendix E](https://arxiv.org/html/2608.26324#A5.p3.1),[§1](https://arxiv.org/html/2608.26324#S1.p7.1),[§2](https://arxiv.org/html/2608.26324#S2.p6.1),[§4\.1](https://arxiv.org/html/2608.26324#S4.SS1.p1.1),[§4](https://arxiv.org/html/2608.26324#S4.p8.2)\.
- \[17\]X\. Li, T\. Zhang, Y\. Dubois, R\. Taori, I\. Gulrajani, C\. Guestrin, P\. Liang, and T\. B\. Hashimoto\(2023\)AlpacaEval: an automatic evaluator of instruction\-following models\.Note:[https://github\.com/tatsu\-lab/alpaca\_eval](https://github.com/tatsu-lab/alpaca_eval)Cited by:[§G\.1](https://arxiv.org/html/2608.26324#A7.SS1.p1.1)\.
- \[18\]H\. Lightman, V\. Kosaraju, Y\. Burda, H\. Edwards, B\. Baker, T\. Lee, J\. Leike, J\. Schulman, I\. Sutskever, and K\. Cobbe\(2023\)Let’s verify step by step\.InThe twelfth international conference on learning representations,Cited by:[§F\.1](https://arxiv.org/html/2608.26324#A6.SS1.p2.1)\.
- \[19\]F\. McSherry and K\. Talwar\(2007\)Mechanism design via differential privacy\.InIEEE Symposium on Foundations of Computer Science \(FOCS\),Cited by:[Remark 3\.4](https://arxiv.org/html/2608.26324#S3.Thmtheorem4.p1.1.1),[§3](https://arxiv.org/html/2608.26324#S3.p2.1)\.
- \[20\]R\. Nakano, J\. Hilton, S\. Balaji, J\. Wu, L\. Ouyang, C\. Kim, C\. Hesse, S\. Jain, V\. Kosaraju, W\. Saunders,et al\.\(2021\)Webgpt: browser\-assisted question\-answering with human feedback\.arXiv preprint arXiv:2112\.09332\.Cited by:[§1](https://arxiv.org/html/2608.26324#S1.p1.1)\.
- \[21\]R\. Rafailov, A\. Sharma, E\. Mitchell, C\. D\. Manning, S\. Ermon, and C\. Finn\(2023\)Direct preference optimization: your language model is secretly a reward model\.Advances in neural information processing systems36,pp\. 53728–53741\.Cited by:[§1](https://arxiv.org/html/2608.26324#S1.p1.1)\.
- \[22\]R\. M\. Rogers, G\. Samorodnitsk, S\. Z\. Wu, and A\. Ramdas\(2023\)Adaptive privacy composition for accuracy\-first mechanisms\.Advances in Neural Information Processing Systems36,pp\. 15833–15854\.Cited by:[Remark D\.1](https://arxiv.org/html/2608.26324#A4.Thmtheorem1.p1.1.1),[§4\.1](https://arxiv.org/html/2608.26324#S4.SS1.p2.1)\.
- \[23\]C\. Snell, J\. Lee, K\. Xu, and A\. Kumar\(2024\)Scaling llm test\-time compute optimally can be more effective than scaling model parameters\.arXiv preprint arXiv:2408\.03314\.Cited by:[§1](https://arxiv.org/html/2608.26324#S1.p1.1)\.
- \[24\]N\. Stiennon, L\. Ouyang, J\. Wu, D\. Ziegler, R\. Lowe, C\. Voss, A\. Radford, D\. Amodei, and P\. F\. Christiano\(2020\)Learning to summarize with human feedback\.Advances in neural information processing systems33,pp\. 3008–3021\.Cited by:[§1](https://arxiv.org/html/2608.26324#S1.p1.1)\.
- \[25\]F\. Tramèr, G\. Kamath, and N\. CarliniPosition: considerations for differentially private learning with large\-scale public pretraining\.InForty\-first International Conference on Machine Learning,Cited by:[§1](https://arxiv.org/html/2608.26324#S1.p3.1)\.
- \[26\]C\. M\. Verdun, A\. Oesterling, H\. Lakkaraju, and F\. P\. Calmon\(2025\)Soft best\-of\-nnsampling for model alignment\.In2025 IEEE International Symposium on Information Theory \(ISIT\),pp\. 1–6\.Cited by:[Appendix A](https://arxiv.org/html/2608.26324#A1.p1.1),[§1](https://arxiv.org/html/2608.26324#S1.p2.1)\.
- \[27\]L\. Wang, J\. Wang, J\. Ren, Z\. Xiang, D\. E\. Keyes, and D\. Wang\(2025\)Private training large\-scale models with efficient dp\-sgd\.InThe Thirty\-ninth Annual Conference on Neural Information Processing Systems,Cited by:[Appendix A](https://arxiv.org/html/2608.26324#A1.p2.1),[§1](https://arxiv.org/html/2608.26324#S1.p4.1)\.
- \[28\]J\. Wei, X\. Wang, D\. Schuurmans, B\. Maarten, B\. Ichter, F\. Xia, E\. Chi, Q\. Le, and D\. Zhou\(2022\)Chain\-of\-thought prompting elicits reasoning in large language models\.Advances in Neural Information Processing Systems \(NeurIPS\)35,pp\. 24824–24837\.Cited by:[§F\.1](https://arxiv.org/html/2608.26324#A6.SS1.p2.1),[§5](https://arxiv.org/html/2608.26324#S5.p1.1)\.
- \[29\]J\. Whitehouse, A\. Ramdas, R\. Rogers, and S\. Wu\(2023\)Fully\-adaptive composition in differential privacy\.InInternational conference on machine learning,pp\. 36990–37007\.Cited by:[Remark D\.1](https://arxiv.org/html/2608.26324#A4.Thmtheorem1.p1.1.1)\.
- \[30\]J\. Q\. Yang, S\. Salamatian, Z\. Sun, A\. T\. Suresh, and A\. Beirami\(2024\)Asymptotics of language model alignment\.In2024 IEEE International Symposium on Information Theory \(ISIT\),pp\. 2027–2032\.Cited by:[Appendix A](https://arxiv.org/html/2608.26324#A1.p1.1),[§1](https://arxiv.org/html/2608.26324#S1.p2.1)\.
- \[31\]D\. Yu, S\. Naik, A\. Backurs, S\. Gopi, H\. A\. Inan, G\. Kamath, J\. Kulkarni, Y\. T\. Lee, A\. Manoel, L\. Wutschitz,et al\.\(2021\)Differentially private fine\-tuning of language models\.arXiv preprint arXiv:2110\.06500\.Cited by:[§5](https://arxiv.org/html/2608.26324#S5.p5.1)\.
- \[32\]Y\. Yu, Q\. Di, Q\. Gu, and D\. Zhou\(2025\)On the limits of test\-time compute: sequential reward filtering for better inference\.arXiv preprint arXiv:2512\.04558\.Cited by:[Appendix A](https://arxiv.org/html/2608.26324#A1.p1.1),[§1](https://arxiv.org/html/2608.26324#S1.p4.1),[§5](https://arxiv.org/html/2608.26324#S5.p5.1)\.
- \[33\]Y\. Zhang, K\. Panaganti, L\. Shi, J\. Ziani, and A\. Wierman\(2025\)KL\-regularization itself is differentially private in bandits and rlhf\.arXiv preprint arXiv:2505\.18407\.Cited by:[Appendix A](https://arxiv.org/html/2608.26324#A1.p2.1)\.
- \[34\]X\. Zhou, Y\. Wu, and F\. Orabona\(2025\)A unified theoretical analysis of private and robust offline alignment: from rlhf to dpo\.InInternational Conference on Machine Learning,pp\. 79366–79388\.Cited by:[Appendix A](https://arxiv.org/html/2608.26324#A1.p2.1)\.
- \[35\]X\. Zhou, Y\. Wu, W\. Weng, and F\. Orabona\(2025\)Squareχ\\chipo: differentially private and robustχ2\\chi^\{2\}\-preference optimization in offline direct alignment\.InInternational Conference on Machine Learning,pp\. 79389–79413\.Cited by:[Appendix A](https://arxiv.org/html/2608.26324#A1.p2.1)\.

## Appendix ARelated work

*Best\-of\-NNtheory\.*Beirami et al\.\[[2](https://arxiv.org/html/2608.26324#bib.bib14)\]and Yang et al\.\[[30](https://arxiv.org/html/2608.26324#bib.bib23)\]analyze BoN’s KL\-reward tradeoff\. Verdun et al\.\[[26](https://arxiv.org/html/2608.26324#bib.bib22)\]introduce Soft BoN \(SBoN\), showingO⁡\(1/n\)O\(1/n\)convergence to the KL\-regularized optimum\. Aminian et al\.\[[1](https://arxiv.org/html/2608.26324#bib.bib13)\]derive KL and regret bounds for SBoN under proxy reward error\. Our MBON mechanisms are algorithmically equivalent to SBoN; the novelty lies in the privacy derivation ofσ\\sigma, the regret optimality proof, and the PrivITP extension\. Khalaf et al\.\[[14](https://arxiv.org/html/2608.26324#bib.bib19)\]characterize inference\-time reward hacking; our reward hacking bounds \([Section3\.2](https://arxiv.org/html/2608.26324#S3.SS2)\) complement their results by quantifying how noise injection caps the hacking gap\. Yu et al\.\[[32](https://arxiv.org/html/2608.26324#bib.bib24)\]show that sequential test\-time compute dominates parallel methods such as BoN; extending PrivITP to the sequential setting is an open direction\. Huang et al\.\[[13](https://arxiv.org/html/2608.26324#bib.bib18)\]establish the regret skylineΩ⁡\(Cπ∗​εRM2\)\\Omega\(\\sqrt\{C^\{\\pi^\{\*\}\}\\varepsilon\_\{\\mathrm\{RM\}\}^\{2\}\}\)and introduce InferenceTimePessimism, aχ2\\chi^\{2\}\-regularized rejection sampling algorithm that achieves this bound\.

*Differential privacy in LLM alignment\.*All prior work on private alignment operates at*training time*\. Zhang et al\.\[[33](https://arxiv.org/html/2608.26324#bib.bib25)\]prove that KL\-regularization itself provides DP for the trained policy\. Zhou et al\.\[[34](https://arxiv.org/html/2608.26324#bib.bib26)\]study private and robust offline RLHF under label DP\. Wang et al\.\[[27](https://arxiv.org/html/2608.26324#bib.bib4)\]propose DP\-AdamW for private DPO fine\-tuning\.[Zhou et al\. \[35\]](https://arxiv.org/html/2608.26324#bib.bib12)gives private and robust algorithms for training\-based alignment\. Prior work on private inference has studied differentially private prediction\[[7](https://arxiv.org/html/2608.26324#bib.bib5)\], private top\-kkselection\[[6](https://arxiv.org/html/2608.26324#bib.bib27)\], but the specific interaction between privacy noise and alignment quality in inference\-time methods has not been analyzed\. Our work is the first to provide formal privacy guarantees at*inference time*, protecting the reward model’s training data during deployment rather than during training\.

## Appendix BProofs for Private Best\-of\-N

We provide detailed proofs for every result stated in the main text\.

### B\.1Proof of[Theorem3\.1](https://arxiv.org/html/2608.26324#S3.Thmtheorem1): PrivBoN Privacy

###### Proof\.

Condition on the candidate sety1:ny\_\{1:n\}, drawn i\.i\.d\. fromπ0\(⋅\|x\)\\pi\_\{0\}\(\\cdot\|x\)independently ofDD\. The Gumbel\-max trick states that ifg1,…,gn​∼iid​Gumbel​\(0,σ\)g\_\{1\},\\ldots,g\_\{n\}\\overset\{\\mathrm\{iid\}\}\{\\sim\}\\mathrm\{Gumbel\}\(0,\\sigma\), then:

Pr⁡\(arg​maxi⁡\(r^D​\(x,yi\)\+gi\)=k\)=er^D​\(x,yk\)/σ∑j=1ner^D​\(x,yj\)/σ\.\\Pr\\\!\\left\(\\argmax\_\{i\}\(\\hat\{r\}\_\{D\}\(x,y\_\{i\}\)\+g\_\{i\}\)=k\\right\)=\\frac\{e^\{\\hat\{r\}\_\{D\}\(x,y\_\{k\}\)/\\sigma\}\}\{\\sum\_\{j=1\}^\{n\}e^\{\\hat\{r\}\_\{D\}\(x,y\_\{j\}\)/\\sigma\}\}\.This is precisely the exponential mechanism with score functionq⁡\(k,D\)=r^D​\(x,yk\)q\(k;D\)=\\hat\{r\}\_\{D\}\(x,y\_\{k\}\)and privacy parameterε/\(2​Δr\)=1/σ\\varepsilon/\(2\\Delta\_\{r\}\)=1/\\sigma\.

For adjacentD∼D′D\\sim D^\{\\prime\}, any candidateyky\_\{k\}, and the fixed sety1:ny\_\{1:n\}:

Pr⁡\(i∗=k∣D\)Pr⁡\(i∗=k∣D′\)\\displaystyle\\frac\{\\Pr\(i^\{\*\}=k\\mid D\)\}\{\\Pr\(i^\{\*\}=k\\mid D^\{\\prime\}\)\}=er^D​\(x,yk\)/σer^D′​\(x,yk\)/σ⋅∑jer^D′​\(x,yj\)/σ∑jer^D​\(x,yj\)/σ\.\\displaystyle=\\frac\{e^\{\\hat\{r\}\_\{D\}\(x,y\_\{k\}\)/\\sigma\}\}\{e^\{\\hat\{r\}\_\{D^\{\\prime\}\}\(x,y\_\{k\}\)/\\sigma\}\}\\cdot\\frac\{\\sum\_\{j\}e^\{\\hat\{r\}\_\{D^\{\\prime\}\}\(x,y\_\{j\}\)/\\sigma\}\}\{\\sum\_\{j\}e^\{\\hat\{r\}\_\{D\}\(x,y\_\{j\}\)/\\sigma\}\}\.\(7\)The first factor is at mosteΔr/σ=eε/2e^\{\\Delta\_\{r\}/\\sigma\}=e^\{\\varepsilon/2\}\(since\|r^D−r^D′\|≤Δr\|\\hat\{r\}\_\{D\}\-\\hat\{r\}\_\{D^\{\\prime\}\}\|\\leq\\Delta\_\{r\}\)\. For the second factor, each term in the numerator sum is at mosteΔr/σe^\{\\Delta\_\{r\}/\\sigma\}times the corresponding denominator term, so the ratio is at mosteΔr/σ=eε/2e^\{\\Delta\_\{r\}/\\sigma\}=e^\{\\varepsilon/2\}\. Combined: the likelihood ratio is at mosteεe^\{\\varepsilon\}\.

Since the outputyi∗y\_\{i^\{\*\}\}is a deterministic function ofi∗i^\{\*\}andy1:ny\_\{1:n\}\(post\-processing\), andy1:ny\_\{1:n\}is independent ofDD, the overall mechanism isε\\varepsilon\-DP\. ∎

### B\.2Proof of Proposition[3\.2](https://arxiv.org/html/2608.26324#S3.Thmtheorem2): PrivBoN Closed\-Form Policy

###### Proof\.

For brevity, we denoter⁡\(x,y\):=r^D​\(x,y\)r\(x,y\):=\\hat\{r\}\_\{D\}\(x,y\)\. Note that the event\{y∗=y\}\\\{y^\{\*\}=y\\\}decomposes as⋃i=1n\{i∗=i,yi=y\}\\bigcup\_\{i=1\}^\{n\}\\\{i^\{\*\}=i,y\_\{i\}=y\\\}\. These are disjoint \(only one index wins\), so:

πPrivBoN\(y\|x\)=𝔼y1:n\[∑i=1nPr\(i∗=i∣y1:n\)1\{yi=y\}\]\.\\pi\_\{\\mathrm\{PrivBoN\}\}\(y\|x\)=\\mathbb\{E\}\_\{y\_\{1:n\}\}\\left\[\\sum\_\{i=1\}^\{n\}\\Pr\(i^\{\*\}=i\\mid y\_\{1:n\}\)\\,\\mathbf\{1\}\\\{y\_\{i\}=y\\\}\\right\]\.By the i\.i\.d\. structure ofy1,…,yny\_\{1\},\\ldots,y\_\{n\}and symmetry, allnnterms are identically distributed\. Hence:

=n𝔼y1:n\[Pr\(i∗=1∣y1:n\)1\{y1=y\}\]\.=n\\,\\mathbb\{E\}\_\{y\_\{1:n\}\}\\left\[\\Pr\(i^\{\*\}=1\\mid y\_\{1:n\}\)\\,\\mathbf\{1\}\\\{y\_\{1\}=y\\\}\\right\]\.Apply the tower property, conditioning ony1y\_\{1\}:

=n𝔼y1\[𝟏\{y1=y\}𝔼y2:n\[er⁡\(x,y1\)/σ∑j=1ner⁡\(x,yj\)/σ\]\],=n\\,\\mathbb\{E\}\_\{y\_\{1\}\}\\left\[\\mathbf\{1\}\\\{y\_\{1\}=y\\\}\\,\\mathbb\{E\}\_\{y\_\{2:n\}\}\\\!\\left\[\\frac\{e^\{r\(x,y\_\{1\}\)/\\sigma\}\}\{\\sum\_\{j=1\}^\{n\}e^\{r\(x,y\_\{j\}\)/\\sigma\}\}\\right\]\\right\]~,where inside the inner expectation, we have used the probability of selecting candidate 1 using the Gumbel\-max trick\.

Now, sincey1∼π0\(⋅\|x\)y\_\{1\}\\sim\\pi\_\{0\}\(\\cdot\|x\), we have𝔼y1\[𝟏\{y1=y\}f\(y1\)\]=π0\(y\|x\)f\(y\)\\mathbb\{E\}\_\{y\_\{1\}\}\[\\mathbf\{1\}\\\{y\_\{1\}=y\\\}f\(y\_\{1\}\)\]=\\pi\_\{0\}\(y\|x\)\\,f\(y\)\. Applying this identity yields the stated formula\.

#### BoN Recovery \(σ→0\\sigma\\to 0\)

Note thatπPrivBoN\(y\|x\)=nπ0\(y\|x\)𝔼y2:n\[er1/σer1/σ\+∑j=2nerj/σ\]\\pi\_\{\\mathrm\{PrivBoN\}\}\(y\|x\)=n\\,\\pi\_\{0\}\(y\|x\)\\,\\mathbb\{E\}\_\{y\_\{2:n\}\}\\left\[\\frac\{e^\{r\_\{1\}/\\sigma\}\}\{e^\{r\_\{1\}/\\sigma\}\+\\sum\_\{j=2\}^\{n\}e^\{r\_\{j\}/\\sigma\}\}\\right\], wherer1=r⁡\(x,y\)r\_\{1\}=r\(x,y\)andrj=r⁡\(x,yj\)r\_\{j\}=r\(x,y\_\{j\}\)forj≥2j\\geq 2\. Inside the expectation, consider the softmax share for candidate 1:

ψ⁡\(r1\)=er1/σer1/σ\+∑j=2nerj/σ=11\+∑j=2ne\(rj−r1\)/σ\.\\psi\(r\_\{1\}\)=\\frac\{e^\{r\_\{1\}/\\sigma\}\}\{e^\{r\_\{1\}/\\sigma\}\+\\sum\_\{j=2\}^\{n\}e^\{r\_\{j\}/\\sigma\}\}=\\frac\{1\}\{1\+\\sum\_\{j=2\}^\{n\}e^\{\(r\_\{j\}\-r\_\{1\}\)/\\sigma\}\}\.LetM=maxj≥2⁡rjM=\\max\_\{j\\geq 2\}r\_\{j\}\. Factor oute\(M−r1\)/σe^\{\(M\-r\_\{1\}\)/\\sigma\}to get

ψ⁡\(r1\)=11\+e\(M−r1\)/σ​∑j=2ne\(rj−M\)/σ\.\\psi\(r\_\{1\}\)=\\frac\{1\}\{1\+e^\{\(M\-r\_\{1\}\)/\\sigma\}\\sum\_\{j=2\}^\{n\}e^\{\(r\_\{j\}\-M\)/\\sigma\}\}\.Ifr1\>Mr\_\{1\}\>M\(i\.e\.,r1r\_\{1\}is the unique maximum\), then\(M−r1\)/σ→−∞\(M\-r\_\{1\}\)/\\sigma\\to\-\\inftywhenσ→0\\sigma\\to 0, so the softmax shareψ⁡\(r1\)=→1\\psi\(r\_\{1\}\)=\\to 1\. Ifr1<Mr\_\{1\}<M, then\(M−r1\)/σ→\+∞\(M\-r\_\{1\}\)/\\sigma\\to\+\\infty, so the softmax shareψ⁡\(r1\)=→0\\psi\(r\_\{1\}\)=\\to 0\. Ifr1=Mr\_\{1\}=M\(tie\), then the limit depends on the number of ties, but ties have probability zero under continuous reward distributions\.

Therefore, the softmax share satisfies

limσ→0ψ\(r1\)=limσ→0er1/σ∑j=1nerj/σ=𝟏\{r1≥maxj≥2rj\}\\lim\_\{\\sigma\\to 0\}\\psi\(r\_\{1\}\)=\\lim\_\{\\sigma\\to 0\}\\frac\{e^\{r\_\{1\}/\\sigma\}\}\{\\sum\_\{j=1\}^\{n\}e^\{r\_\{j\}/\\sigma\}\}=\\mathbf\{1\}\\\{r\_\{1\}\\geq\\max\_\{j\\geq 2\}r\_\{j\}\\\}Taking expectation, we get

𝔼y2:n\[𝟏\{r\(x,y\)≥maxj≥2r\(x,yj\)\}\]=∏j=2nPr\(r\(x,y\)≥r\(x,yj\)\)=Fπ0\(y\|x\)n−1,\\mathbb\{E\}\_\{y\_\{2:n\}\}\[\\mathbf\{1\}\\\{r\(x,y\)\\geq\\max\_\{j\\geq 2\}r\(x,y\_\{j\}\)\\\}\]=\\prod\_\{j=2\}^\{n\}\\Pr\(r\(x,y\)\\geq r\(x,y\_\{j\}\)\)=F\_\{\\pi\_\{0\}\}\(y\|x\)^\{n\-1\},whereFπ0\(⋅\|x\)F\_\{\\pi\_\{0\}\}\(\\cdot\|x\)is the cumulative distribution function ofr⁡\(x,Y\)r\(x,Y\)whereY∼π0\(⋅\|x\)Y\\sim\\pi\_\{0\}\(\\cdot\|x\)\. Hencelimσ→0πPrivBoN​\(y\|x\)=n​π0​\(y\|x\)​Fπ0​\(y\|x\)n−1=πBoN​\(y\|x\)\\lim\_\{\\sigma\\to 0\}\\pi\_\{\\mathrm\{PrivBoN\}\}\(y\|x\)=n\\,\\pi\_\{0\}\(y\|x\)\\,F\_\{\\pi\_\{0\}\}\(y\|x\)^\{n\-1\}=\\pi\_\{\\mathrm\{BoN\}\}\(y\|x\)\.

#### PrivBoN Policy Limit \(n→∞n\\to\\infty\)

Again, consider the softmax share for candidate 1 inside the expectation:

ψ⁡\(r1\)=er1/σer1/σ\+∑j=2nerj/σ=11\+∑j=2ne\(rj−r1\)/σ\.\\psi\(r\_\{1\}\)=\\frac\{e^\{r\_\{1\}/\\sigma\}\}\{e^\{r\_\{1\}/\\sigma\}\+\\sum\_\{j=2\}^\{n\}e^\{r\_\{j\}/\\sigma\}\}=\\frac\{1\}\{1\+\\sum\_\{j=2\}^\{n\}e^\{\(r\_\{j\}\-r\_\{1\}\)/\\sigma\}\}\.DefineSn=1n−1​∑j=2nerj/σS\_\{n\}=\\frac\{1\}\{n\-1\}\\sum\_\{j=2\}^\{n\}e^\{r\_\{j\}/\\sigma\}\. By the strong law of large numbers,Sn→a\.s\.M\(σ\)=𝔼Y∼π0\(⋅\|x\)\[er⁡\(x,Y\)/σ\]S\_\{n\}\\xrightarrow\{\\mathrm\{a\.s\.\}\}M\(\\sigma\)=\\mathbb\{E\}\_\{Y\\sim\\pi\_\{0\}\(\\cdot\|x\)\}\[e^\{r\(x,Y\)/\\sigma\}\]\. Hence

ψ⁡\(r1\)→11\+\(n−1\)M\(σ\)e−r1/σ⟹n​ψ​\(r1\)→n⋅er1/σ/\(\(n−1\)​M​\(σ\)\+er1/σ\)\.\\psi\(r\_\{1\}\)\\to\\frac\{1\}\{1\+\(n\-1\)M\(\\sigma\)e^\{\-r\_\{1\}/\\sigma\}\}\\implies n\\,\\psi\(r\_\{1\}\)\\to n\\cdot e^\{r\_\{1\}/\\sigma\}/\(\(n\-1\)M\(\\sigma\)\+e^\{r\_\{1\}/\\sigma\}\)\.Hencen​ψ​\(r1\)→er1/σ/M⁡\(σ\)n\\,\\psi\(r\_\{1\}\)\\to e^\{r\_\{1\}/\\sigma\}/M\(\\sigma\)asn→∞n\\to\\infty\. ThereforeπPrivBoN​\(y\|x\)→π0​\(y\|x\)⋅er⁡\(x,y\)/σ/M⁡\(σ\)\\pi\_\{\\mathrm\{PrivBoN\}\}\(y\|x\)\\to\\pi\_\{0\}\(y\|x\)\\cdot e^\{r\(x,y\)/\\sigma\}/M\(\\sigma\)\. ∎

### B\.3Proof of[Theorem3\.3](https://arxiv.org/html/2608.26324#S3.Thmtheorem3): PrivBoN Regret

###### Proof\.

Definer⁡\(x,y\):=r^D​\(x,y\)r\(x,y\):=\\hat\{r\}\_\{D\}\(x,y\)\. We decompose the regret via the limiting tilted policyπ∞​\(y\|x\)=π0​\(y\|x\)​er⁡\(x,y\)/σ/M⁡\(σ\)\\pi\_\{\\infty\}\(y\|x\)=\\pi\_\{0\}\(y\|x\)e^\{r\(x,y\)/\\sigma\}/M\(\\sigma\), whereM⁡\(σ\)=𝔼π0​\[er⁡\(x,y\)/σ\]M\(\\sigma\)=\\mathbb\{E\}\_\{\\pi\_\{0\}\}\[e^\{r\(x,y\)/\\sigma\}\]:

Reg⁡\(πPrivBoN,x\)=J⁡\(π∗,x\)−J⁡\(π∞,x\)⏟\(A\)\+J⁡\(π∞,x\)−J⁡\(πPrivBoN,x\)⏟\(B\)\.\\mathrm\{Reg\}\(\\pi\_\{\\mathrm\{PrivBoN\}\};x\)=\\underbrace\{J\(\\pi^\{\*\};x\)\-J\(\\pi\_\{\\infty\};x\)\}\_\{\\mathrm\{\(A\)\}\}\+\\underbrace\{J\(\\pi\_\{\\infty\};x\)\-J\(\\pi\_\{\\mathrm\{PrivBoN\}\};x\)\}\_\{\\mathrm\{\(B\)\}\}\.\(8\)
Step 1: Bounding \(A\)\. Regret of PrivBoN under infinite samples\.

Define the shorthand𝔼π\[f\]:=𝔼y∼π\(⋅\|x\)\[f\(x,y\)\]\\mathbb\{E\}\_\{\\pi\}\[f\]:=\\mathbb\{E\}\_\{y\\sim\\pi\(\\cdot\|x\)\}\[f\(x,y\)\]for any functionf:𝒳×𝒴→ℝf:\\mathcal\{X\}\\times\\mathcal\{Y\}\\to\\mathbb\{R\}andKL\(π∥π′\):=KL\(π\(⋅\|x\)∥π′\(⋅\|x\)\)\\mathrm\{KL\}\(\\pi\\\|\\pi^\{\\prime\}\):=\\mathrm\{KL\}\(\\pi\(\\cdot\|x\)\\\|\\pi^\{\\prime\}\(\\cdot\|x\)\)\. Now, write the true reward in terms of the proxy:r∗​\(x,y\)=r⁡\(x,y\)−ϵ⁡\(x,y\)r^\{\*\}\(x,y\)=r\(x,y\)\-\\epsilon\(x,y\)\. Then

\(A\)\\displaystyle\\mathrm\{\(A\)\}=𝔼π∗​\[r∗\]−𝔼π∞​\[r∗\]\\displaystyle=\\mathbb\{E\}\_\{\\pi^\{\*\}\}\[r^\{\*\}\]\-\\mathbb\{E\}\_\{\\pi\_\{\\infty\}\}\[r^\{\*\}\]=\(𝔼π∗​\[r\]−𝔼π∞​\[r\]\)−\(𝔼π∗​\[ϵ\]−𝔼π∞​\[ϵ\]\)\.\\displaystyle=\\big\(\\mathbb\{E\}\_\{\\pi^\{\*\}\}\[r\]\-\\mathbb\{E\}\_\{\\pi\_\{\\infty\}\}\[r\]\\big\)\-\\big\(\\mathbb\{E\}\_\{\\pi^\{\*\}\}\[\\epsilon\]\-\\mathbb\{E\}\_\{\\pi\_\{\\infty\}\}\[\\epsilon\]\\big\)\.\(9\)Bounding the reward gap\.The tilted policyπ∞\\pi\_\{\\infty\}solvesmaxπ\{𝔼π\[r\]−σKL\(π∥πref\)\}\\max\_\{\\pi\}\\\{\\mathbb\{E\}\_\{\\pi\}\[r\]\-\\sigma\\mathrm\{KL\}\(\\pi\\\|\\pi\_\{\\mathrm\{ref\}\}\)\\\}\. By the optimality condition, for any policyπ\\pi,

𝔼π\[r\]−𝔼π∞\[r\]≤σ\(KL\(π∥π0\)−KL\(π∞∥π0\)\)≤σKL\(π∥π0\)\.\\mathbb\{E\}\_\{\\pi\}\[r\]\-\\mathbb\{E\}\_\{\\pi\_\{\\infty\}\}\[r\]\\leq\\sigma\\big\(\\mathrm\{KL\}\(\\pi\\\|\\pi\_\{0\}\)\-\\mathrm\{KL\}\(\\pi\_\{\\infty\}\\\|\\pi\_\{0\}\)\\big\)\\leq\\sigma\\,\\mathrm\{KL\}\(\\pi\\\|\\pi\_\{0\}\)\.Applying this withπ=π∗\\pi=\\pi^\{\*\}, we get

𝔼π∗\[r\]−𝔼π∞\[r\]≤σKL\(π∗∥πref\)\.\\mathbb\{E\}\_\{\\pi^\{\*\}\}\[r\]\-\\mathbb\{E\}\_\{\\pi\_\{\\infty\}\}\[r\]\\leq\\sigma\\,\\mathrm\{KL\}\(\\pi^\{\*\}\\\|\\pi\_\{\\mathrm\{ref\}\}\)\.SinceKL\(π∗∥πref\)≤χ2\(π∗∥πref\)=12\(Cπ∗\(x\)−1\)\\mathrm\{KL\}\(\\pi^\{\*\}\\\|\\pi\_\{\\mathrm\{ref\}\}\)\\leq\\chi^\{2\}\(\\pi^\{\*\}\\\|\\pi\_\{\\mathrm\{ref\}\}\)=\\frac\{1\}\{2\}\(C^\{\\pi^\{\*\}\}\(x\)\-1\)\(by the standard inequalityKL≤χ2\\mathrm\{KL\}\\leq\\chi^\{2\}\), we obtain

𝔼π∗​\[r\]−𝔼π∞​\[r\]≤σ2​\(Cπ∗​\(x\)−1\)\.\\mathbb\{E\}\_\{\\pi^\{\*\}\}\[r\]\-\\mathbb\{E\}\_\{\\pi\_\{\\infty\}\}\[r\]\\leq\\frac\{\\sigma\}\{2\}\(C^\{\\pi^\{\*\}\}\(x\)\-1\)\.\(10\)
Bounding the error terms\.For any policyπ\\piwith coverageCπ​\(x\)C^\{\\pi\}\(x\), the Cauchy–Schwarz inequality gives:

\|𝔼π​\[ϵ\]\|=\|𝔼π0​\[π⁡\(y\|x\)π0​\(y\|x\)​ϵ​\(x,y\)\]\|\\displaystyle\|\\mathbb\{E\}\_\{\\pi\}\[\\epsilon\]\|=\\left\|\\mathbb\{E\}\_\{\\pi\_\{0\}\}\\\!\\left\[\\frac\{\\pi\(y\|x\)\}\{\\pi\_\{0\}\(y\|x\)\}\\epsilon\(x,y\)\\right\]\\right\|≤𝔼π0​\[\(π⁡\(x,y\)π0​\(x,y\)\)2\]​𝔼π0​\[ϵ2​\(x,y\)\]\\displaystyle\\leq\\sqrt\{\\mathbb\{E\}\_\{\\pi\_\{0\}\}\\\!\\left\[\\\!\\left\(\\frac\{\\pi\(x,y\)\}\{\\pi\_\{0\}\(x,y\)\}\\right\)^\{\\\!2\}\\right\]\\mathbb\{E\}\_\{\\pi\_\{0\}\}\[\\epsilon^\{2\}\(x,y\)\]\}=𝔼π​\[π⁡\(x,y\)π0​\(x,y\)\]​𝔼π0​\[ϵ2​\(x,y\)\]=Cπ​\(x\)​εRM​\(x\)\.\\displaystyle=\\sqrt\{\\mathbb\{E\}\_\{\\pi\}\\\!\\left\[\\\!\\frac\{\\pi\(x,y\)\}\{\\pi\_\{0\}\(x,y\)\}\\right\]\\mathbb\{E\}\_\{\\pi\_\{0\}\}\[\\epsilon^\{2\}\(x,y\)\]\}=\\sqrt\{C^\{\\pi\}\(x\)\}\\,\\varepsilon\_\{\\mathrm\{RM\}\}\(x\)\.Applying this toπ∗\\pi^\{\*\}directly, we get

\|𝔼π∗​\[ϵ\]\|≤Cπ∗​\(x\)​εRM​\(x\)\.\|\\mathbb\{E\}\_\{\\pi^\{\*\}\}\[\\epsilon\]\|\\leq\\sqrt\{C^\{\\pi^\{\*\}\}\(x\)\}\\,\\varepsilon\_\{\\mathrm\{RM\}\}\(x\)\.\(11\)
Nowϵ⁡\(x,y\)∼𝒩⁡\(0,σr2​\(x\)\)\\epsilon\(x,y\)\\sim\\mathcal\{N\}\(0,\\sigma\_\{r\}^\{2\}\(x\)\)underπ0\\pi\_\{0\}\. So, the tilted distribution ofϵ⁡\(x,y\)\\epsilon\(x,y\)underπ∞\\pi\_\{\\infty\}has density𝒩⁡\(σr2​\(x\)/σ,σr2​\(x\)\)\\mathcal\{N\}\(\\sigma\_\{r\}^\{2\}\(x\)/\\sigma,\\sigma\_\{r\}^\{2\}\(x\)\)\. Therefore we get

𝔼y∼π∞\(⋅\|x\)\[ϵ\(x,y\)\]=σr2​\(x\)σ\.\\mathbb\{E\}\_\{y\\sim\\pi\_\{\\infty\}\(\\cdot\|x\)\}\[\\epsilon\(x,y\)\]=\\frac\{\\sigma\_\{r\}^\{2\}\(x\)\}\{\\sigma\}\.\(12\)
Combining \([9](https://arxiv.org/html/2608.26324#A2.E9)\), \([10](https://arxiv.org/html/2608.26324#A2.E10)\), \([11](https://arxiv.org/html/2608.26324#A2.E11)\), and \([12](https://arxiv.org/html/2608.26324#A2.E12)\):

\(A\)≤σ2​\(Cπ∗−1\)\+Cπ∗​εRM\+εRM2σ\.\\mathrm\{\(A\)\}\\leq\\frac\{\\sigma\}\{2\}\(C^\{\\pi^\{\*\}\}\-1\)\+\\sqrt\{C^\{\\pi^\{\*\}\}\}\\,\\varepsilon\_\{\\mathrm\{RM\}\}\+\\frac\{\\varepsilon\_\{\\mathrm\{RM\}\}^\{2\}\}\{\\sigma\}~\.\(13\)

#### Bounding \(B\): Finite\-sample gap\.

Letwk=er⁡\(x,yk\)/σw\_\{k\}=e^\{r\(x,y\_\{k\}\)/\\sigma\}andfk=r∗​\(x,yk\)f\_\{k\}=r^\{\*\}\(x,y\_\{k\}\)for candidatesy1,…,yn∼π0y\_\{1\},\\ldots,y\_\{n\}\\sim\\pi\_\{0\}\. Assume thatr⁡\(x,y\)∈\[a,b\]r\(x,y\)\\in\[a,b\]with rangec=b−ac=b\-a, we havewk∈\[ea/σ,eb/σ\]w\_\{k\}\\in\[e^\{a/\\sigma\},e^\{b/\\sigma\}\]\. Sincer∗∈\[0,Rmax\]r^\{\*\}\\in\[0,R\_\{\\max\}\], we havefk∈\[0,Rmax\]f\_\{k\}\\in\[0,R\_\{\\max\}\]\. By the Gumbel\-max trick, the selected candidateyi∗y\_\{i^\{\*\}\}is drawn from the softmax distributionPr\[i∗=k∣y1:n\]=wk/∑jwj\\Pr\[i^\{\*\}=k\\mid y\_\{1:n\}\]=w\_\{k\}/\\sum\_\{j\}w\_\{j\}, so

J\(π^PrivBoN;x\)=𝔼πPrivBoN\[r∗\]=𝔼y1:n\[∑kwk​fk∑kwk\]=𝔼\[Z^n\(r\)Z^n\],J\(\\hat\{\\pi\}\_\{\\mathrm\{PrivBoN\}\};x\)=\\mathbb\{E\}\_\{\\pi\_\{\\mathrm\{PrivBoN\}\}\}\[r^\{\*\}\]=\\mathbb\{E\}\_\{y\_\{1:n\}\}\\\!\\left\[\\frac\{\\sum\_\{k\}w\_\{k\}f\_\{k\}\}\{\\sum\_\{k\}w\_\{k\}\}\\right\]=\\mathbb\{E\}\\\!\\left\[\\frac\{\\hat\{Z\}\_\{n\}^\{\(r\)\}\}\{\\hat\{Z\}\_\{n\}\}\\right\],whereZ^n=1n​∑kwk\\hat\{Z\}\_\{n\}=\\frac\{1\}\{n\}\\sum\_\{k\}w\_\{k\}andZ^n\(r\)=1n​∑kwk​fk\\hat\{Z\}\_\{n\}^\{\(r\)\}=\\frac\{1\}\{n\}\\sum\_\{k\}w\_\{k\}f\_\{k\}are empirical means, with population counterpartsZ=𝔼π0​\[w\]≥ea/σZ=\\mathbb\{E\}\_\{\\pi\_\{0\}\}\[w\]\\geq e^\{a/\\sigma\}andZ\(r\)=𝔼π0​\[w​f\]Z^\{\(r\)\}=\\mathbb\{E\}\_\{\\pi\_\{0\}\}\[wf\], wherew=er⁡\(x,y\)/σw=e^\{r\(x,y\)/\\sigma\}andf=r∗​\(x,y\)f=r^\{\*\}\(x,y\), so thatJ⁡\(π∞,x\)=Z\(r\)/ZJ\(\\pi\_\{\\infty\};x\)=Z^\{\(r\)\}/Z\.

LetA=Z^n\(r\)−Z\(r\)A=\\hat\{Z\}\_\{n\}^\{\(r\)\}\-Z^\{\(r\)\}andB=Z^n−ZB=\\hat\{Z\}\_\{n\}\-Z\. Then:

Z^n\(r\)Z^n−Z\(r\)Z=Z^n\(r\)​Z−Z\(r\)​Z^nZ​Z^n=A​Z−Z\(r\)​BZ​Z^n\.\\frac\{\\hat\{Z\}\_\{n\}^\{\(r\)\}\}\{\\hat\{Z\}\_\{n\}\}\-\\frac\{Z^\{\(r\)\}\}\{Z\}=\\frac\{\\hat\{Z\}\_\{n\}^\{\(r\)\}Z\-Z^\{\(r\)\}\\hat\{Z\}\_\{n\}\}\{Z\\hat\{Z\}\_\{n\}\}=\\frac\{AZ\-Z^\{\(r\)\}B\}\{Z\\hat\{Z\}\_\{n\}\}\.By the triangle inequality andZ\(r\)=𝔼π0​\[w​r∗\]≤Rmax​𝔼π0​\[w\]=Rmax​ZZ^\{\(r\)\}=\\mathbb\{E\}\_\{\\pi\_\{0\}\}\[wr^\{\*\}\]\\leq R\_\{\\max\}\\mathbb\{E\}\_\{\\pi\_\{0\}\}\[w\]=R\_\{\\max\}Z\(sincer∗∈\[0,Rmax\]r^\{\*\}\\in\[0,R\_\{\\max\}\]andw\>0w\>0\), we have

\|A​Z−Z\(r\)​B\|≤Z​\|A\|\+Z\(r\)\|B\|≤Z⁡\(\|A\|\+Rmax​\|B\|\),\|AZ\-Z^\{\(r\)\}B\|\\leq Z\|A\|\+Z^\{\(r\)\}\|B\|\\leq Z\(\|A\|\+R\_\{\\max\}\|B\|\),giving\|Z^n\(r\)/Z^n−Z\(r\)/Z\|≤\(\|A\|\+Rmax​\|B\|\)/Z^n\|\\hat\{Z\}\_\{n\}^\{\(r\)\}/\\hat\{Z\}\_\{n\}\-Z^\{\(r\)\}/Z\|\\leq\(\|A\|\+R\_\{\\max\}\|B\|\)/\\hat\{Z\}\_\{n\}\.

Defineℰ=\{Z^n≥Z/2\}\\mathcal\{E\}=\\\{\\hat\{Z\}\_\{n\}\\geq Z/2\\\}\. Sincewk∈\[ea/σ,eb/σ\]w\_\{k\}\\in\[e^\{a/\\sigma\},e^\{b/\\sigma\}\]are i\.i\.d\. with meanZZ, Hoeffding’s inequality gives

Pr\[ℰc\]=Pr\[Z^n−Z<−Z/2\]≤exp\(−2​n​\(Z/2\)2\(eb/σ−ea/σ\)2\)≤exp\(−n​Z22​e2​b/σ\),\\Pr\[\\mathcal\{E\}^\{c\}\]=\\Pr\[\\hat\{Z\}\_\{n\}\-Z<\-Z/2\]\\leq\\exp\\\!\\left\(\-\\frac\{2n\(Z/2\)^\{2\}\}\{\(e^\{b/\\sigma\}\-e^\{a/\\sigma\}\)^\{2\}\}\\right\)\\leq\\exp\\\!\\left\(\-\\frac\{nZ^\{2\}\}\{2e^\{2b/\\sigma\}\}\\right\),where the last inequality useseb/σ−ea/σ≤eb/σe^\{b/\\sigma\}\-e^\{a/\\sigma\}\\leq e^\{b/\\sigma\}\.

*Bound on the good event\.*Onℰ\\mathcal\{E\},Z^n≥Z/2\\hat\{Z\}\_\{n\}\\geq Z/2, so\(\|A\|\+Rmax​\|B\|\)/Z^n≤2​\(\|A\|\+Rmax​\|B\|\)/Z\(\|A\|\+R\_\{\\max\}\|B\|\)/\\hat\{Z\}\_\{n\}\\leq 2\(\|A\|\+R\_\{\\max\}\|B\|\)/Z\. Now, via Jensen inequality \(𝔼​\|X\|≤𝔼⁡\[X2\]\\mathbb\{E\}\|X\|\\leq\\sqrt\{\\mathbb\{E\}\[X^\{2\}\]\}\), we get

𝔼⁡\[\|B\|\]≤𝔼⁡\[\(Z^n−Z\)2\]=Var⁡\(Z^n\)=Varπ0​\(w\)n≤𝔼π0​\[w2\]n≤eb/σn,\\mathbb\{E\}\[\|B\|\]\\leq\\sqrt\{\\mathbb\{E\}\[\(\\hat\{Z\}\_\{n\}\-Z\)^\{2\}\]\}=\\sqrt\{\\mathrm\{Var\}\(\\hat\{Z\}\_\{n\}\)\}=\\frac\{\\sqrt\{\\mathrm\{Var\}\_\{\\pi\_\{0\}\}\(w\)\}\}\{\\sqrt\{n\}\}\\leq\\frac\{\\sqrt\{\\mathbb\{E\}\_\{\\pi\_\{0\}\}\[w^\{2\}\]\}\}\{\\sqrt\{n\}\}\\leq\\frac\{e^\{b/\\sigma\}\}\{\\sqrt\{n\}\},usingVar⁡\(w\)≤𝔼⁡\[w2\]\\mathrm\{Var\}\(w\)\\leq\\mathbb\{E\}\[w^\{2\}\]andw≤eb/σw\\leq e^\{b/\\sigma\}\. Similarly

𝔼⁡\[\|A\|\]≤Var⁡\(Z^n\(r\)\)=Varπ0​\(w​r∗\)n≤𝔼π0​\[w2​\(r∗\)2\]n≤Rmax​eb/σn,\\mathbb\{E\}\[\|A\|\]\\leq\\sqrt\{\\mathrm\{Var\}\(\\hat\{Z\}\_\{n\}^\{\(r\)\}\)\}=\\frac\{\\sqrt\{\\mathrm\{Var\}\_\{\\pi\_\{0\}\}\(wr^\{\*\}\)\}\}\{\\sqrt\{n\}\}\\leq\\frac\{\\sqrt\{\\mathbb\{E\}\_\{\\pi\_\{0\}\}\[w^\{2\}\(r^\{\*\}\)^\{2\}\]\}\}\{\\sqrt\{n\}\}\\leq\\frac\{R\_\{\\max\}e^\{b/\\sigma\}\}\{\\sqrt\{n\}\},using\(r∗\)2≤Rmax2\(r^\{\*\}\)^\{2\}\\leq R\_\{\\max\}^\{2\}\. Therefore, we get

𝔼⁡\[\|Z^n\(r\)Z^n−Z\(r\)Z\|⋅𝟏ℰ\]≤2Z​\(Rmax​eb/σn\+Rmax​eb/σn\)=4​Rmax​eb/σZ​n\.\\mathbb\{E\}\\\!\\left\[\\left\|\\frac\{\\hat\{Z\}\_\{n\}^\{\(r\)\}\}\{\\hat\{Z\}\_\{n\}\}\-\\frac\{Z^\{\(r\)\}\}\{Z\}\\right\|\\cdot\\mathbf\{1\}\_\{\\mathcal\{E\}\}\\right\]\\leq\\frac\{2\}\{Z\}\\\!\\left\(\\frac\{R\_\{\\max\}e^\{b/\\sigma\}\}\{\\sqrt\{n\}\}\+\\frac\{R\_\{\\max\}e^\{b/\\sigma\}\}\{\\sqrt\{n\}\}\\right\)=\\frac\{4R\_\{\\max\}e^\{b/\\sigma\}\}\{Z\\sqrt\{n\}\}\.
*Bound on the bad event\.*BothZ^n\(r\)/Z^n\\hat\{Z\}\_\{n\}^\{\(r\)\}/\\hat\{Z\}\_\{n\}andZ\(r\)/ZZ^\{\(r\)\}/Zare weighted averages of values in\[0,Rmax\]\[0,R\_\{\\max\}\]\(the former is a convex combination offk∈\[0,Rmax\]f\_\{k\}\\in\[0,R\_\{\\max\}\]; the latter is𝔼⁡\[w​f\]/𝔼⁡\[w\]\\mathbb\{E\}\[wf\]/\\mathbb\{E\}\[w\]withf∈\[0,Rmax\]f\\in\[0,R\_\{\\max\}\]\)\. Hence, their difference is bounded byRmaxR\_\{\\max\}\. Thus

𝔼⁡\[\|Z^n\(r\)Z^n−Z\(r\)Z\|⋅𝟏ℰc\]≤Rmax⋅Pr⁡\[ℰc\]≤Rmax​exp⁡\(−n​Z22​e2​b/σ\)\.\\mathbb\{E\}\\\!\\left\[\\left\|\\frac\{\\hat\{Z\}\_\{n\}^\{\(r\)\}\}\{\\hat\{Z\}\_\{n\}\}\-\\frac\{Z^\{\(r\)\}\}\{Z\}\\right\|\\cdot\\mathbf\{1\}\_\{\\mathcal\{E\}^\{c\}\}\\right\]\\leq R\_\{\\max\}\\cdot\\Pr\[\\mathcal\{E\}^\{c\}\]\\leq R\_\{\\max\}\\exp\\\!\\left\(\-\\frac\{nZ^\{2\}\}\{2e^\{2b/\\sigma\}\}\\right\)\.
By the triangle inequality for expectations, we obtain

\|J⁡\(π∞,x\)−J⁡\(πPrivBoN,x\)\|≤𝔼⁡\[\|Z^n\(r\)Z^n−Z\(r\)Z\|\]≤4​Rmax​eb/σZ​n\+Rmax​exp⁡\(−n​Z22​e2​b/σ\),\|J\(\\pi\_\{\\infty\};x\)\-J\(\\pi\_\{\\mathrm\{PrivBoN\}\};x\)\|\\leq\\mathbb\{E\}\\\!\\left\[\\left\|\\frac\{\\hat\{Z\}\_\{n\}^\{\(r\)\}\}\{\\hat\{Z\}\_\{n\}\}\-\\frac\{Z^\{\(r\)\}\}\{Z\}\\right\|\\right\]\\leq\\frac\{4R\_\{\\max\}e^\{b/\\sigma\}\}\{Z\\sqrt\{n\}\}\+R\_\{\\max\}\\exp\\\!\\left\(\-\\frac\{nZ^\{2\}\}\{2e^\{2b/\\sigma\}\}\\right\),whereZ=𝔼π0​\[er/σ\]≥ea/σZ=\\mathbb\{E\}\_\{\\pi\_\{0\}\}\[e^\{r/\\sigma\}\]\\geq e^\{a/\\sigma\}\. UsingZ≥ea/σZ\\geq e^\{a/\\sigma\}, this simplifies to:

\|J⁡\(π∞\)−J⁡\(π^MBON\)\|≤4​Rmax​ec/σn\+Rmax​exp⁡\(−n2​e2​c/σ\)≤4​Rmax​ec/σn\+εRM\\displaystyle\|J\(\\pi\_\{\\infty\}\)\-J\(\\hat\{\\pi\}\_\{\\mathrm\{MBON\}\}\)\|\\leq\\frac\{4R\_\{\\max\}e^\{c/\\sigma\}\}\{\\sqrt\{n\}\}\+R\_\{\\max\}\\exp\\\!\\left\(\-\\frac\{n\}\{2e^\{2c/\\sigma\}\}\\right\)\\leq\\frac\{4R\_\{\\max\}e^\{c/\\sigma\}\}\{\\sqrt\{n\}\}\+\\varepsilon\_\{\\mathrm\{RM\}\}\(14\)forn≥2​e2​c/σ​log⁡\(Rmax/εRM\)n\\geq 2e^\{2c/\\sigma\}\\log\(R\_\{\\max\}/\\varepsilon\_\{\\mathrm\{RM\}\}\), wherec=b−ac=b\-ais the reward range\.

Adding \([13](https://arxiv.org/html/2608.26324#A2.E13)\) and \([14](https://arxiv.org/html/2608.26324#A2.E14)\), we get

Regπ∗​\(x\)≤σ⁡\(Cπ∗−1\)\+εRM2σ\+Cπ∗​εRM\+O⁡\(Rmax​ec/σn\)\.\\mathrm\{Reg\}^\{\\pi^\{\*\}\}\(x\)\\leq\\sigma\(C^\{\\pi^\{\*\}\}\-1\)\+\\frac\{\\varepsilon\_\{\\mathrm\{RM\}\}^\{2\}\}\{\\sigma\}\+\\sqrt\{C^\{\\pi^\{\*\}\}\}\\,\\varepsilon\_\{\\mathrm\{RM\}\}\+O\\\!\\left\(\\frac\{R\_\{\\max\}e^\{c/\\sigma\}\}\{\\sqrt\{n\}\}\\right\)\.
The regret bound is modulo the assumption thatr⁡\(x,y\)∈\[a,b\]r\(x,y\)\\in\[a,b\]with rangec=b−ac=b\-a\. Under the Gaussian error modelr⁡\(x,y\)=r∗​\(x,y\)\+ϵ⁡\(x,y\)r\(x,y\)=r^\{\*\}\(x,y\)\+\\epsilon\(x,y\)withϵ⁡\(x,y\)∼𝒩⁡\(0,σr2​\(x\)\)\\epsilon\(x,y\)\\sim\\mathcal\{N\}\(0,\\sigma\_\{r\}^\{2\}\(x\)\), the reward is unbounded\. We handle this by conditioning on the high\-probability eventℱ:=\{maxk\|ϵ\(x,yk\)\|≤σr2​log⁡\(n/Δr\)\}\\mathcal\{F\}:=\\\{\\max\_\{k\}\|\\epsilon\(x,y\_\{k\}\)\|\\leq\\sigma\_\{r\}\\sqrt\{2\\log\(n/\\Delta\_\{r\}\)\}\\\}, which hasPr⁡\[ℱ\]≥1−Δr\\Pr\[\\mathcal\{F\}\]\\geq 1\-\\Delta\_\{r\}by Gaussian tail and union bound\. Onℱ\\mathcal\{F\}, the rewards lie in\[−σr​2​log⁡\(n/Δr\),Rmax\+σr​2​log⁡\(n/Δr\)\]\[\-\\sigma\_\{r\}\\sqrt\{2\\log\(n/\\Delta\_\{r\}\)\},\\,R\_\{\\max\}\+\\sigma\_\{r\}\\sqrt\{2\\log\(n/\\Delta\_\{r\}\)\}\], so the bounded analysis applies with effective rangec=Rmax\+2​σr​2​log⁡\(n/Δr\)c=R\_\{\\max\}\+2\\sigma\_\{r\}\\sqrt\{2\\log\(n/\\Delta\_\{r\}\)\}\. Onℱc\\mathcal\{F\}^\{c\}, the regret is bounded trivially byRmaxR\_\{\\max\}, contributingRmax​ΔrR\_\{\\max\}\\Delta\_\{r\}\. SettingΔr=1/n\\Delta\_\{r\}=1/\\sqrt\{n\}, the effective range becomesc=O⁡\(Rmax\+σr​log⁡n\)c=O\(R\_\{\\max\}\+\\sigma\_\{r\}\\sqrt\{\\log n\}\)\. Substituting this, we get

Regπ∗​\(x\)≤σ⁡\(Cπ∗−1\)\+εRM2σ\+Cπ∗​εRM\+O⁡\(Rmax​e\(Rmax\+εRM​log⁡n\)/σn\)\\mathrm\{Reg\}^\{\\pi^\{\*\}\}\(x\)\\leq\\sigma\(C^\{\\pi^\{\*\}\}\-1\)\+\\frac\{\\varepsilon\_\{\\mathrm\{RM\}\}^\{2\}\}\{\\sigma\}\+\\sqrt\{C^\{\\pi^\{\*\}\}\}\\,\\varepsilon\_\{\\mathrm\{RM\}\}\+O\\\!\\left\(\\frac\{R\_\{\\max\}e^\{\(R\_\{\\max\}\+\\varepsilon\_\{\\mathrm\{RM\}\}\\sqrt\{\\log n\}\)/\\sigma\}\}\{\\sqrt\{n\}\}\\right\)forn=Ω⁡\(e\(Rmax\+εRM​log⁡n\)/σ​log⁡\(Rmax/εRM\)CLOSEn=\\Omega\\left\(e^\{\(R\_\{\\max\}\+\\varepsilon\_\{\\mathrm\{RM\}\}\\sqrt\{\\log n\}\)/\\sigma\}\\log\(R\_\{\\max\}/\\varepsilon\_\{\\mathrm\{RM\}\}\\right\)\. ∎

### B\.4On the Gaussian\-error assumption in Theorem[3\.3](https://arxiv.org/html/2608.26324#S3.Thmtheorem3)

The Gaussian\-error assumption in Theorem[3\.3](https://arxiv.org/html/2608.26324#S3.Thmtheorem3)gives the closed form𝔼π∞​\[ϵ⁡\(x,y\)\]=σr2​\(x\)/σ\\mathbb\{E\}\_\{\\pi\_\{\\infty\}\}\[\\epsilon\(x,y\)\]=\\sigma\_\{r\}^\{2\}\(x\)/\\sigma, which we use to derive the exactϵRM2/σ\\epsilon\_\{\\mathrm\{RM\}\}^\{2\}/\\sigmaoveroptimization term\. Under a general mean\-squared\-error assumption𝔼π0​\[ϵ​\(x,y\)2\]=ϵRM2​\(x\)\\mathbb\{E\}\_\{\\pi\_\{0\}\}\[\\epsilon\(x,y\)^\{2\}\]=\\epsilon\_\{\\mathrm\{RM\}\}^\{2\}\(x\), an application Cauchy–Schwarz inequality yields only\|𝔼π∞​\[ϵ\]\|≤Cπ∞​\(x\)​ϵRM​\(x\)\|\\mathbb\{E\}\_\{\\pi\_\{\\infty\}\}\[\\epsilon\]\|\\leq\\sqrt\{C^\{\\pi\_\{\\infty\}\}\(x\)\}\\,\\epsilon\_\{\\mathrm\{RM\}\}\(x\), whereCπ∞C^\{\\pi\_\{\\infty\}\}is the coverage of the tilted policy\. SinceCπ∞C^\{\\pi\_\{\\infty\}\}scales asexp⁡\(Rmax/σ\)\\exp\(R\_\{\\max\}/\\sigma\)in the worst case, the overoptimization term inflates, weakening the “privacy is free” threshold\.

The finite\-sample analysis conditions on a high\-probability boundedness event via a Gaussian tail bound \(the union boundPr\[maxk\|ϵ\(x,yk\)\|≤σr2​log⁡\(n/δ\)\]≥1−δ\\Pr\[\\max\_\{k\}\|\\epsilon\(x,y\_\{k\}\)\|\\leq\\sigma\_\{r\}\\sqrt\{2\\log\(n/\\delta\)\}\]\\geq 1\-\\delta\)\. For sub\-Gaussian errors with parameterσr\\sigma\_\{r\}the analysis goes through unchanged up to constants\. For bounded rewards\|r^D\|≤B\|\\hat\{r\}\_\{D\}\|\\leq B, the tail step becomes trivial, butBBreplacesσr​log⁡n\\sigma\_\{r\}\\sqrt\{\\log n\}in the effective reward range, tightening the finite\-sample term whenB≪σr​log⁡nB\\ll\\sigma\_\{r\}\\sqrt\{\\log n\}and loosening it otherwise\.

The qualitative conclusions—bias\-variance trade\-off inσ\\sigma, existence of anϵ∗\\epsilon^\{\*\}threshold above which privacy is free, and regret going down withnn—hold under the general mean\-squared\-error assumption\. The clean form of the thresholdϵ∗​\(x\)=2​Δr​Cπ∗​\(x\)/ϵRM​\(x\)\\epsilon^\{\*\}\(x\)=2\\Delta\_\{r\}\\sqrt\{C^\{\\pi^\{\*\}\}\(x\)\}/\\epsilon\_\{\\mathrm\{RM\}\}\(x\), however, is specific to the Gaussian case\.

### B\.5Proof of Proposition[3\.6](https://arxiv.org/html/2608.26324#S3.Thmtheorem6)\(Win\-Rate Bound and Reward hacking\)

###### Proof\.

\(a\) Win\-rate\.For brevity, we denoter⁡\(x,y\):=r^D​\(x,y\)r\(x,y\):=\\hat\{r\}\_\{D\}\(x,y\)\. Defineri=r⁡\(x,yi\)r\_\{i\}=r\(x,y\_\{i\}\)fori∈\[n\]i\\in\[n\]andr0=r⁡\(x,y0\)r\_\{0\}=r\(x,y\_\{0\}\)\. Letpi=Pr⁡\(ri≥r0∣yi\)p\_\{i\}=\\Pr\(r\_\{i\}\\geq r\_\{0\}\\mid y\_\{i\}\)wherey0,yi∼π0\(⋅\|x\)y\_\{0\},y\_\{i\}\\sim\\pi\_\{0\}\(\\cdot\|x\)independently\.

We know that asn→∞n\\to\\infty,πPrivBoN→π∞\\pi\_\{\\mathrm\{PrivBoN\}\}\\to\\pi\_\{\\infty\}whereπ∞​\(y\|x\)∝π0​\(y\|x\)​er⁡\(x,y\)/σ\\pi\_\{\\infty\}\(y\|x\)\\propto\\pi\_\{0\}\(y\|x\)e^\{r\(x,y\)/\\sigma\}\.

For Gaussian rewardsr⁡\(x,y\)∼𝒩⁡\(r∗​\(x,y\),σr2​\(x\)\)r\(x,y\)\\sim\\mathcal\{N\}\(r^\{\*\}\(x,y\),\\sigma\_\{r\}^\{2\}\(x\)\)underπ0\\pi\_\{0\}\. Now, the tilted distribution ofr⁡\(x,y\)r\(x,y\)underπ∞\\pi\_\{\\infty\}has density𝒩⁡\(r∗​\(x,y\)\+σr2​\(x\)/σ,σr2​\(x\)\)\\mathcal\{N\}\(r^\{\*\}\(x,y\)\+\\sigma\_\{r\}^\{2\}\(x\)/\\sigma,\\sigma\_\{r\}^\{2\}\(x\)\)\. HenceY∼π∞\(⋅\|x\)Y\\sim\\pi\_\{\\infty\}\(\\cdot\|x\)has rewardrY∼𝒩⁡\(r∗​\(x,y\)\+σr2​\(x\)/σ,σr2​\(x\)\)r\_\{Y\}\\sim\\mathcal\{N\}\(r^\{\*\}\(x,y\)\+\\sigma\_\{r\}^\{2\}\(x\)/\\sigma,\\sigma\_\{r\}^\{2\}\(x\)\)andZ∼π0\(⋅\|x\)Z\\sim\\pi\_\{0\}\(\\cdot\|x\)has rewardrZ∼𝒩⁡\(r∗​\(x,y\),σr2​\(x\)\)r\_\{Z\}\\sim\\mathcal\{N\}\(r^\{\*\}\(x,y\),\\sigma\_\{r\}^\{2\}\(x\)\)\. Then:

rY−rZ∼𝒩⁡\(σr2​\(x\)/σ,2​σr2​\(x\)\)\.r\_\{Y\}\-r\_\{Z\}\\sim\\mathcal\{N\}\(\\sigma\_\{r\}^\{2\}\(x\)/\\sigma,2\\sigma\_\{r\}^\{2\}\(x\)\)\.SoWinRate∞PrivBoN=Pr⁡\(rY≥rZ\)=Φ⁡\(σr2​\(x\)/\(σ​2​σr​\(x\)\)\)=Φ⁡\(σr​\(x\)/\(σ​2\)\)<1\\mathrm\{WinRate\}^\{\\mathrm\{PrivBoN\}\}\_\{\\infty\}=\\Pr\(r\_\{Y\}\\geq r\_\{Z\}\)=\\Phi\(\\sigma\_\{r\}^\{2\}\(x\)/\(\\sigma\\sqrt\{2\}\\sigma\_\{r\}\(x\)\)\)=\\Phi\(\\sigma\_\{r\}\(x\)/\(\\sigma\\sqrt\{2\}\)\)<1\.

\(b\) Reward hacking\.Denoter⁡\(x,y\):=r^D​\(x,y\)r\(x,y\):=\\hat\{r\}\_\{D\}\(x,y\),ri:=r⁡\(x,yi\)r\_\{i\}:=r\(x,y\_\{i\}\)andϵi:=ϵ⁡\(x,yi\)\\epsilon\_\{i\}:=\\epsilon\(x,y\_\{i\}\)\. For any fixed candidate sety1:ny\_\{1:n\}, BoN selectsi∗=arg​maxi⁡rii^\{\*\}=\\argmax\_\{i\}r\_\{i\}\. This maximizes𝔼⁡\[ri∗\]\\mathbb\{E\}\[r\_\{i^\{\*\}\}\]over all \(possibly randomized\) selection rules, since the deterministicarg​max\\argmaxis optimal\. PrivBoN’s softmax selection is a specific randomized rule, hence suboptimal:𝔼y∼πPrivBoN\(⋅\|x\)\[r\(x,y\)\]≤𝔼πBoN\(⋅\|x\)\[r\(x,y\)\]\\mathbb\{E\}\_\{y\\sim\\pi\_\{\\mathrm\{PrivBoN\}\}\(\\cdot\|x\)\}\[r\(x,y\)\]\\leq\\mathbb\{E\}\_\{\\pi\_\{\\mathrm\{BoN\}\}\(\\cdot\|x\)\}\[r\(x,y\)\]\.

For BoN, the hacking gap is𝔼y∼πBoN\(⋅\|x\)\[ϵ\(x,y\)\]=𝔼y1:n\[∑i=1n𝟏\{i∗=i\}ϵi\]≤𝔼y1:n\[maxi=1nϵi\]\\mathbb\{E\}\_\{y\\sim\\pi\_\{\\mathrm\{BoN\}\}\(\\cdot\|x\)\}\[\\epsilon\(x,y\)\]=\\mathbb\{E\}\_\{y\_\{1:n\}\}\[\\sum\_\{i=1\}^\{n\}\\mathbf\{1\}\\\{i^\{\*\}=i\\\}\\epsilon\_\{i\}\]\\leq\\mathbb\{E\}\_\{y\_\{1:n\}\}\[\\max\_\{i=1\}^\{n\}\\epsilon\_\{i\}\]\. Since eachϵi∼𝒩⁡\(0,σr2​\(x\)\)\\epsilon\_\{i\}\\sim\\mathcal\{N\}\(0,\\sigma\_\{r\}^\{2\}\(x\)\)underπ0\\pi\_\{0\}and independent, we have𝔼⁡\[maxi⁡ϵi\]=O⁡\(σr​\(x\)​log⁡n\)\\mathbb\{E\}\[\\max\_\{i\}\\epsilon\_\{i\}\]=O\(\\sigma\_\{r\}\(x\)\\sqrt\{\\log n\}\)by standard results on Gaussian maximum\.

In the limitn→∞n\\to\\infty, we haveπPrivBoN→π∞\\pi\_\{\\mathrm\{PrivBoN\}\}\\to\\pi\_\{\\infty\}, whereπ∞​\(y\|x\)∝π0​\(y\|x\)​er⁡\(x,y\)/σ\\pi\_\{\\infty\}\(y\|x\)\\propto\\pi\_\{0\}\(y\|x\)e^\{r\(x,y\)/\\sigma\}\. Nowϵ⁡\(x,y\)∼𝒩⁡\(0,σr2​\(x\)\)\\epsilon\(x,y\)\\sim\\mathcal\{N\}\(0,\\sigma\_\{r\}^\{2\}\(x\)\)underπ0\\pi\_\{0\}\. So, the tilted distribution ofϵ⁡\(x,y\)\\epsilon\(x,y\)underπ∞\\pi\_\{\\infty\}has density𝒩⁡\(σr2​\(x\)/σ,σr2​\(x\)\)\\mathcal\{N\}\(\\sigma\_\{r\}^\{2\}\(x\)/\\sigma,\\sigma\_\{r\}^\{2\}\(x\)\)\. Therefore, the hacking gap of PrivBoN becomes𝔼y∼π∞\(⋅\|x\)\[ϵ\(x,y\)\]=σr2​\(x\)σ\\mathbb\{E\}\_\{y\\sim\\pi\_\{\\infty\}\(\\cdot\|x\)\}\[\\epsilon\(x,y\)\]=\\frac\{\\sigma\_\{r\}^\{2\}\(x\)\}\{\\sigma\}in the limitn→∞n\\to\\infty\. ∎

## Appendix CProofs for Private Inference\-Time Pessimism

### C\.1Proof of[Theorem4\.1](https://arxiv.org/html/2608.26324#S4.Thmtheorem1)\(PrivITP Privacy\)

###### Proof\.

We analyze the two phases separately and combine them via basic composition\.

Phase 1\.Defineλ∗​\(D\)\\lambda^\{\*\}\(D\)as the unique solution to

FD​\(λ\):=1n​∑i=1nrelu⁡\(β−1​\(r^D​\(x,yi\)−λ\)\)=1,F\_\{D\}\(\\lambda\):=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\mathrm\{relu\}\\\!\\big\(\\beta^\{\-1\}\(\\hat\{r\}\_\{D\}\(x,y\_\{i\}\)\-\\lambda\)\\big\)=1,where the candidatesy1,…,yn∼π0\(⋅\|x\)y\_\{1\},\\ldots,y\_\{n\}\\sim\\pi\_\{0\}\(\\cdot\|x\)are drawn independently ofDD\. The functionFDF\_\{D\}is continuous and strictly decreasing inλ\\lambda, withFD​\(λ\)→∞F\_\{D\}\(\\lambda\)\\to\\inftyasλ→−∞\\lambda\\to\-\\inftyandFD​\(λ\)=0F\_\{D\}\(\\lambda\)=0forλ≥maxi⁡r^D​\(x,yi\)\\lambda\\geq\\max\_\{i\}\\hat\{r\}\_\{D\}\(x,y\_\{i\}\), so the solution exists and is unique\.

*Sensitivity ofλ∗\\lambda^\{\*\}\.*For adjacent datasetsD∼D′D\\sim D^\{\\prime\}and each candidateyiy\_\{i\}, we have\|r^D​\(x,yi\)−r^D′​\(x,yi\)\|≤Δr\|\\hat\{r\}\_\{D\}\(x,y\_\{i\}\)\-\\hat\{r\}\_\{D^\{\\prime\}\}\(x,y\_\{i\}\)\|\\leq\\Delta\_\{r\}\. Sincerelu​\(β−1​\(z−λ\)\)\\mathrm\{relu\}\(\\beta^\{\-1\}\(z\-\\lambda\)\)is monotone increasing inzz, this gives pointwise

relu⁡\(β−1​\(r^D​\(x,yi\)−\(λ\+Δr\)\)\)≤relu⁡\(β−1​\(r^D′​\(x,yi\)−λ\)\)≤relu⁡\(β−1​\(r^D​\(x,yi\)−\(λ−Δr\)\)\)\.\\mathrm\{relu\}\\\!\\big\(\\beta^\{\-1\}\(\\hat\{r\}\_\{D\}\(x,y\_\{i\}\)\-\(\\lambda\+\\Delta\_\{r\}\)\)\\big\)\\leq\\mathrm\{relu\}\\\!\\big\(\\beta^\{\-1\}\(\\hat\{r\}\_\{D^\{\\prime\}\}\(x,y\_\{i\}\)\-\\lambda\)\\big\)\\leq\\mathrm\{relu\}\\\!\\big\(\\beta^\{\-1\}\(\\hat\{r\}\_\{D\}\(x,y\_\{i\}\)\-\(\\lambda\-\\Delta\_\{r\}\)\)\\big\)\.Averaging overii, we get

FD​\(λ\+Δr\)≤FD′​\(λ\)≤FD​\(λ−Δr\)\.F\_\{D\}\(\\lambda\+\\Delta\_\{r\}\)\\leq F\_\{D^\{\\prime\}\}\(\\lambda\)\\leq F\_\{D\}\(\\lambda\-\\Delta\_\{r\}\)\.
Settingλ=λ∗​\(D′\)\\lambda=\\lambda^\{\*\}\(D^\{\\prime\}\), soFD′​\(λ∗​\(D′\)\)=1=FD​\(λ∗​\(D\)\)F\_\{D^\{\\prime\}\}\(\\lambda^\{\*\}\(D^\{\\prime\}\)\)=1=F\_\{D\}\(\\lambda^\{\*\}\(D\)\), we obtain

- •Upper bound:1≤FD​\(λ∗​\(D′\)−Δr\)1\\leq F\_\{D\}\(\\lambda^\{\*\}\(D^\{\\prime\}\)\-\\Delta\_\{r\}\), so by monotonicity ofFDF\_\{D\},λ∗​\(D′\)−Δr≤λ∗​\(D\)\\lambda^\{\*\}\(D^\{\\prime\}\)\-\\Delta\_\{r\}\\leq\\lambda^\{\*\}\(D\), i\.e\.,λ∗​\(D′\)≤λ∗​\(D\)\+Δr\\lambda^\{\*\}\(D^\{\\prime\}\)\\leq\\lambda^\{\*\}\(D\)\+\\Delta\_\{r\}\.
- •Lower bound:1≥FD​\(λ∗​\(D′\)\+Δr\)1\\geq F\_\{D\}\(\\lambda^\{\*\}\(D^\{\\prime\}\)\+\\Delta\_\{r\}\), soλ∗​\(D′\)\+Δr≥λ∗​\(D\)\\lambda^\{\*\}\(D^\{\\prime\}\)\+\\Delta\_\{r\}\\geq\\lambda^\{\*\}\(D\), i\.e\.,λ∗​\(D′\)≥λ∗​\(D\)−Δr\\lambda^\{\*\}\(D^\{\\prime\}\)\\geq\\lambda^\{\*\}\(D\)\-\\Delta\_\{r\}\.

Combining both, we get\|λ∗​\(D\)−λ∗​\(D′\)\|≤Δr\|\\lambda^\{\*\}\(D\)\-\\lambda^\{\*\}\(D^\{\\prime\}\)\|\\leq\\Delta\_\{r\}\.

*Gaussian mechanism\.*Sinceλ∗:𝒟→ℝ\\lambda^\{\*\}:\\mathcal\{D\}\\to\\mathbb\{R\}is a scalar deterministic function with global sensitivity at mostΔr\\Delta\_\{r\}, releasingλ~=λ∗​\(D\)\+ζ\\tilde\{\\lambda\}=\\lambda^\{\*\}\(D\)\+\\zetawithζ∼𝒩⁡\(0,σX2\)\\zeta\\sim\\mathcal\{N\}\(0,\\sigma\_\{X\}^\{2\}\)is the scalar Gaussian mechanism\[[8](https://arxiv.org/html/2608.26324#bib.bib28)\], yielding\(ε1,δ\)\(\\varepsilon\_\{1\},\\delta\)\-DP withε1=Δr​2​ln⁡\(1\.25/δ\)/σX\\varepsilon\_\{1\}=\\Delta\_\{r\}\\sqrt\{2\\ln\(1\.25/\\delta\)\}/\\sigma\_\{X\}\.

Phase 2\.Fixλ\\lambda\(released privately from Phase 1, treated as public for the ex\-post analysis\) and fresh candidatesy1′,…,yn′∼π0\(⋅\|x\)y^\{\\prime\}\_\{1\},\\ldots,y^\{\\prime\}\_\{n\}\\sim\\pi\_\{0\}\(\\cdot\|x\)\(independent ofDD\)\. Letqi:=r^D​\(x,yi′\)∈\[0,Rmax\]q\_\{i\}:=\\hat\{r\}\_\{D\}\(x,y^\{\\prime\}\_\{i\}\)\\in\[0,R\_\{\\max\}\]\. At each round, Phase 2 computesr~i=qi\+gi′\\tilde\{r\}\_\{i\}=q\_\{i\}\+g^\{\\prime\}\_\{i\}withgi∼𝒩⁡\(0,σZ2\)g\_\{i\}\\sim\\mathcal\{N\}\(0,\\sigma\_\{Z\}^\{2\}\), weightwi=relu⁡\(β−1​\(r~i−λ~\)\)w\_\{i\}=\\mathrm\{relu\}\(\\beta^\{\-1\}\(\\tilde\{r\}\_\{i\}\-\\tilde\{\\lambda\}\)\), and acceptanceξi∼Bernoulli⁡\(min⁡\(wi/M,1\)\)\\xi\_\{i\}\\sim\\mathrm\{Bernoulli\}\(\\min\(w\_\{i\}/M,1\)\)\. The halting time ist∗=min⁡\{i:ξi=1\}t^\{\*\}=\\min\\\{i:\\xi\_\{i\}=1\\\}\.

*Reformulation as randomized threshold\.*We show rejection sampling is equivalent in distribution to a threshold check with a randomized effective threshold\. Letui∼Unif⁡\[0,1\]u\_\{i\}\\sim\\mathrm\{Unif\}\[0,1\]be fresh independent uniform noise\.

###### Lemma C\.1\(Reformulation\)\.

Pr⁡\[ξi=1∣r~i\]=Pr⁡\[r~i≥λ~\+β​M​ui∣r~i\]\\Pr\[\\xi\_\{i\}=1\\mid\\tilde\{r\}\_\{i\}\]=\\Pr\\\!\\big\[\\tilde\{r\}\_\{i\}\\geq\\tilde\{\\lambda\}\+\\beta Mu\_\{i\}\\mid\\tilde\{r\}\_\{i\}\\big\]\.

Indeed: \(a\) ifr~i<λ~\\tilde\{r\}\_\{i\}<\\tilde\{\\lambda\}, both sides are zero; \(b\) ifλ~≤r~i≤λ~\+β​M\\tilde\{\\lambda\}\\leq\\tilde\{r\}\_\{i\}\\leq\\tilde\{\\lambda\}\+\\beta M, the LHS equalswi/M=\(r~i−λ\)/\(β​M\)w\_\{i\}/M=\(\\tilde\{r\}\_\{i\}\-\\lambda\)/\(\\beta M\), and the RHS equalsPr\[ui≤\(r~i−λ~\)/\(βM\)\]=\(r~i−λ\)/\(βM\)\\Pr\[u\_\{i\}\\leq\(\\tilde\{r\}\_\{i\}\-\\tilde\{\\lambda\}\)/\(\\beta M\)\]=\(\\tilde\{r\}\_\{i\}\-\\lambda\)/\(\\beta M\); \(c\) ifr~i\>λ~\+β​M\\tilde\{r\}\_\{i\}\>\\tilde\{\\lambda\}\+\\beta M, both sides are one\.

With this reformulation, Phase 2 accepts candidateiiiffgi≥λ~\+β​M​ui−qig\_\{i\}\\geq\\tilde\{\\lambda\}\+\\beta Mu\_\{i\}\-q\_\{i\}, where\(gi,ui\)\(g\_\{i\},u\_\{i\}\)are independent fresh noise, independent across rounds\.

*Halting probability\.*Since the noise is independent across rounds, the probability of halting at timettfactorizes:

Pr⁡\[t∗=t∣D\]=∏i=1t−1\(1−pi​\(D\)\)⋅pt​\(D\),\\Pr\[t^\{\*\}=t\\mid D\]=\\prod\_\{i=1\}^\{t\-1\}\(1\-p\_\{i\}\(D\)\)\\cdot p\_\{t\}\(D\),where the per\-round acceptance probability \(marginalizing over bothgig\_\{i\}anduiu\_\{i\}\) is

pi\(D\)=Pr\[gi≥λ~\+βMui−qi\]=𝔼ui\[Φ\(qi−λ~−β​M​uiσZ\)\],p\_\{i\}\(D\)=\\Pr\[g\_\{i\}\\geq\\tilde\{\\lambda\}\+\\beta Mu\_\{i\}\-q\_\{i\}\]=\\mathbb\{E\}\_\{u\_\{i\}\}\\\!\\left\[\\Phi\\\!\\left\(\\frac\{q\_\{i\}\-\\tilde\{\\lambda\}\-\\beta Mu\_\{i\}\}\{\\sigma\_\{Z\}\}\\right\)\\right\],usingPr\[gi≥z\]=Φ\(−z/σZ\)\\Pr\[g\_\{i\}\\geq z\]=\\Phi\(\-z/\\sigma\_\{Z\}\)\. Correspondingly,

1−pi​\(D\)=𝔼ui​\[Φ⁡\(λ~\+β​M​ui−qiσZ\)\]\.1\-p\_\{i\}\(D\)=\\mathbb\{E\}\_\{u\_\{i\}\}\\\!\\left\[\\Phi\\\!\\left\(\\frac\{\\tilde\{\\lambda\}\+\\beta Mu\_\{i\}\-q\_\{i\}\}\{\\sigma\_\{Z\}\}\\right\)\\right\]\.
*Ratio under coupling\.*Under the coupling where all noise variables\(gi,ui\)\(g\_\{i\},u\_\{i\}\)are shared betweenDDandD′D^\{\\prime\}, letqi′:=r^D′​\(x,yi′\)q^\{\\prime\}\_\{i\}:=\\hat\{r\}\_\{D^\{\\prime\}\}\(x,y^\{\\prime\}\_\{i\}\)andδi:=qi−qi′∈\[−Δr,Δr\]\\delta\_\{i\}:=q\_\{i\}\-q^\{\\prime\}\_\{i\}\\in\[\-\\Delta\_\{r\},\\Delta\_\{r\}\]\. Define

Ai​\(q,δ\):=𝔼u​\[Φ⁡\(λ~\+β​M​u−q−δσZ\)\],Bi​\(q,δ\):=𝔼u​\[Φ⁡\(q\+δ−λ~−β​M​uσZ\)\]\.A\_\{i\}\(q,\\delta\):=\\mathbb\{E\}\_\{u\}\\\!\\left\[\\Phi\\\!\\left\(\\frac\{\\tilde\{\\lambda\}\+\\beta Mu\-q\-\\delta\}\{\\sigma\_\{Z\}\}\\right\)\\right\],\\qquad B\_\{i\}\(q,\\delta\):=\\mathbb\{E\}\_\{u\}\\\!\\left\[\\Phi\\\!\\left\(\\frac\{q\+\\delta\-\\tilde\{\\lambda\}\-\\beta Mu\}\{\\sigma\_\{Z\}\}\\right\)\\right\]\.Then1−pi​\(D\)=Ai​\(qi′,δi\)1\-p\_\{i\}\(D\)=A\_\{i\}\(q^\{\\prime\}\_\{i\},\\delta\_\{i\}\)andpi​\(D\)=Bi​\(qi′,δi\)p\_\{i\}\(D\)=B\_\{i\}\(q^\{\\prime\}\_\{i\},\\delta\_\{i\}\), and similarly1−pi​\(D′\)=Ai​\(qi′,0\)1\-p\_\{i\}\(D^\{\\prime\}\)=A\_\{i\}\(q^\{\\prime\}\_\{i\},0\),pi​\(D′\)=Bi​\(qi′,0\)p\_\{i\}\(D^\{\\prime\}\)=B\_\{i\}\(q^\{\\prime\}\_\{i\},0\)\. The ratio of halting probabilities is

Pr⁡\[t∗=t∣D\]Pr⁡\[t∗=t∣D′\]=∏i=1t−1Ai​\(qi′,δi\)Ai​\(qi′,0\)⋅Bt​\(qt′,δt\)Bt​\(qt′,0\)\.\\frac\{\\Pr\[t^\{\*\}=t\\mid D\]\}\{\\Pr\[t^\{\*\}=t\\mid D^\{\\prime\}\]\}=\\prod\_\{i=1\}^\{t\-1\}\\frac\{A\_\{i\}\(q^\{\\prime\}\_\{i\},\\delta\_\{i\}\)\}\{A\_\{i\}\(q^\{\\prime\}\_\{i\},0\)\}\\cdot\\frac\{B\_\{t\}\(q^\{\\prime\}\_\{t\},\\delta\_\{t\}\)\}\{B\_\{t\}\(q^\{\\prime\}\_\{t\},0\)\}\.
*Worst\-case shifts\.*The functionAi​\(qi′,δ\)A\_\{i\}\(q^\{\\prime\}\_\{i\},\\delta\)is decreasing inδ\\delta\(largerδ\\deltashrinksΦ\\Phi’s argument\), soAi​\(qi′,δi\)/Ai​\(qi′,0\)A\_\{i\}\(q^\{\\prime\}\_\{i\},\\delta\_\{i\}\)/A\_\{i\}\(q^\{\\prime\}\_\{i\},0\)is maximized atδi=−Δr\\delta\_\{i\}=\-\\Delta\_\{r\}fori<ti<t\. The functionBt​\(qt′,δ\)B\_\{t\}\(q^\{\\prime\}\_\{t\},\\delta\)is increasing inδ\\delta, soBt​\(qt′,δt\)/Bt​\(qt′,0\)B\_\{t\}\(q^\{\\prime\}\_\{t\},\\delta\_\{t\}\)/B\_\{t\}\(q^\{\\prime\}\_\{t\},0\)is maximized atδt=\+Δr\\delta\_\{t\}=\+\\Delta\_\{r\}\.

*Worst\-case query values\.*After fixing the shifts, each ratio factor depends only onqi′q^\{\\prime\}\_\{i\}through the arguments ofΦ\\Phi\. It holds that \(see Lemma[C\.2](https://arxiv.org/html/2608.26324#A3.Thmtheorem2)\)

1. \(i\)Fori<ti<t:Ai​\(qi′,−Δr\)/Ai​\(qi′,0\)A\_\{i\}\(q^\{\\prime\}\_\{i\},\-\\Delta\_\{r\}\)/A\_\{i\}\(q^\{\\prime\}\_\{i\},0\)is non\-decreasing inqi′∈\[0,Rmax\]q^\{\\prime\}\_\{i\}\\in\[0,R\_\{\\max\}\], maximized atqi′=Rmaxq^\{\\prime\}\_\{i\}=R\_\{\\max\}\.
2. \(ii\)Fori=ti=t:Bt​\(qt′,Δr\)/Bt​\(qt′,0\)B\_\{t\}\(q^\{\\prime\}\_\{t\},\\Delta\_\{r\}\)/B\_\{t\}\(q^\{\\prime\}\_\{t\},0\)is non\-increasing inqt′q^\{\\prime\}\_\{t\}, maximized atqt′=0q^\{\\prime\}\_\{t\}=0\.

*Final bound\.*Substitutingqi′=Rmaxq^\{\\prime\}\_\{i\}=R\_\{\\max\}fori<ti<t\(with shiftδi=−Δr\\delta\_\{i\}=\-\\Delta\_\{r\}\) andqt′=0q^\{\\prime\}\_\{t\}=0\(with shiftδt=\+Δr\\delta\_\{t\}=\+\\Delta\_\{r\}\):

Ai​\(Rmax,−Δr\)Ai​\(Rmax,0\)\\displaystyle\\frac\{A\_\{i\}\(R\_\{\\max\},\-\\Delta\_\{r\}\)\}\{A\_\{i\}\(R\_\{\\max\},0\)\}=𝔼u​\[Φ⁡\(\(λ~\+β​M​u−Rmax\+Δr\)/σZ\)\]𝔼u​\[Φ⁡\(\(λ~\+β​M​u−Rmax\)/σZ\)\],\\displaystyle=\\frac\{\\mathbb\{E\}\_\{u\}\[\\Phi\(\(\\tilde\{\\lambda\}\+\\beta Mu\-R\_\{\\max\}\+\\Delta\_\{r\}\)/\\sigma\_\{Z\}\)\]\}\{\\mathbb\{E\}\_\{u\}\[\\Phi\(\(\\tilde\{\\lambda\}\+\\beta Mu\-R\_\{\\max\}\)/\\sigma\_\{Z\}\)\]\},Bt​\(0,Δr\)Bt​\(0,0\)\\displaystyle\\frac\{B\_\{t\}\(0,\\Delta\_\{r\}\)\}\{B\_\{t\}\(0,0\)\}=𝔼u​\[Φ⁡\(\(Δr−λ~−β​M​u\)/σZ\)\]𝔼u​\[Φ⁡\(\(−λ~−β​M​u\)/σZ\)\]\.\\displaystyle=\\frac\{\\mathbb\{E\}\_\{u\}\[\\Phi\(\(\\Delta\_\{r\}\-\\tilde\{\\lambda\}\-\\beta Mu\)/\\sigma\_\{Z\}\)\]\}\{\\mathbb\{E\}\_\{u\}\[\\Phi\(\(\-\\tilde\{\\lambda\}\-\\beta Mu\)/\\sigma\_\{Z\}\)\]\}\.The factors fori=1,…,t−1i=1,\\ldots,t\-1are identical \(since the expression depends oniionly throughuiu\_\{i\}, and theuiu\_\{i\}’s are i\.i\.d\.\), so their product is the first factor raised to the powert−1t\-1\. Taking logarithms yields \([4\.1](https://arxiv.org/html/2608.26324#S4.Ex6)\)\.

Composition\.By basic composition of DP mechanisms, PrivITP satisfies\(ε1\+ε2post​\(t\),δ\)\(\\varepsilon\_\{1\}\+\\varepsilon\_\{2\}^\{\\mathrm\{post\}\}\(t\),\\delta\)\-DP ex\-post\. ∎

###### Lemma C\.2\(Monotonicity of Gaussian CDF ratios under uniform averaging\)\.

Letτ∼Unif⁡\[Q,R\]\\tau\\sim\\mathrm\{Unif\}\[Q,R\]withQ<RQ<R, and letΔ\>0\\Delta\>0\. Define, forx∈ℝx\\in\\mathbb\{R\},

R1​\(x\):=𝔼⁡\[Φ⁡\(τ−x\+Δ\)\]𝔼⁡\[Φ⁡\(τ−x\)\],R2​\(x\):=𝔼⁡\[Φ⁡\(x−τ\+Δ\)\]𝔼⁡\[Φ⁡\(x−τ\)\]\.R\_\{1\}\(x\):=\\frac\{\\mathbb\{E\}\\big\[\\Phi\(\\tau\-x\+\\Delta\)\\big\]\}\{\\mathbb\{E\}\\big\[\\Phi\(\\tau\-x\)\\big\]\},\\qquad R\_\{2\}\(x\):=\\frac\{\\mathbb\{E\}\\big\[\\Phi\(x\-\\tau\+\\Delta\)\\big\]\}\{\\mathbb\{E\}\\big\[\\Phi\(x\-\\tau\)\\big\]\}\.ThenR1​\(x\)R\_\{1\}\(x\)is non\-decreasing inxxandR2​\(x\)R\_\{2\}\(x\)is non\-increasing inxx\.

###### Proof\.

The sign condition for both ratios reduces to log\-concavity of a single auxiliary function, which is then established via the Prékopa–Leindler inequality\.

WriteN⁡\(x\)=∫QRΦ⁡\(τ−x\+Δ\)​𝑑τN\(x\)=\\int\_\{Q\}^\{R\}\\Phi\(\\tau\-x\+\\Delta\)\\,d\\tauandD⁡\(x\)=∫QRΦ⁡\(τ−x\)​𝑑τD\(x\)=\\int\_\{Q\}^\{R\}\\Phi\(\\tau\-x\)\\,d\\tau, so thatR1​\(x\)=N⁡\(x\)/D⁡\(x\)R\_\{1\}\(x\)=N\(x\)/D\(x\)\. Sincedd​x​Φ​\(τ−x\+Δ\)=−ϕ⁡\(τ−x\+Δ\)\\frac\{d\}\{dx\}\\Phi\(\\tau\-x\+\\Delta\)=\-\\phi\(\\tau\-x\+\\Delta\),

R1′​\(x\)=N′​\(x\)​D​\(x\)−N⁡\(x\)​D′​\(x\)D​\(x\)2=−∫QRϕ\(τ−x\+Δ\)dτ⋅D\(x\)\+N\(x\)⋅∫QRϕ\(τ−x\)dτD​\(x\)2\.R\_\{1\}^\{\\prime\}\(x\)=\\frac\{N^\{\\prime\}\(x\)\\,D\(x\)\-N\(x\)\\,D^\{\\prime\}\(x\)\}\{D\(x\)^\{2\}\}=\\frac\{\-\\\!\\int\_\{Q\}^\{R\}\\phi\(\\tau\\\!\-\\\!x\\\!\+\\\!\\Delta\)\\,d\\tau\\cdot D\(x\)\\;\+\\;N\(x\)\\cdot\\\!\\int\_\{Q\}^\{R\}\\phi\(\\tau\\\!\-\\\!x\)\\,d\\tau\}\{D\(x\)^\{2\}\}\.HenceR1′​\(x\)≥0R\_\{1\}^\{\\prime\}\(x\)\\geq 0if and only if

N⁡\(x\)​∫QRϕ⁡\(τ−x\)​𝑑τ≥D⁡\(x\)​∫QRϕ⁡\(τ−x\+Δ\)​𝑑τ\.N\(x\)\\int\_\{Q\}^\{R\}\\phi\(\\tau\-x\)\\,d\\tau\\;\\geq\\;D\(x\)\\int\_\{Q\}^\{R\}\\phi\(\\tau\-x\+\\Delta\)\\,d\\tau\.\(15\)Substituteu=τ−xu=\\tau\-xand seta=Q−xa=Q\-x,b=R−xb=R\-x,L=R−QL=R\-Q\. Define

F⁡\(t\):=∫abΦ⁡\(u\+t\)​𝑑u,t∈ℝ\.F\(t\)\\;:=\\;\\int\_\{a\}^\{b\}\\Phi\(u\+t\)\\,du,\\qquad t\\in\\mathbb\{R\}\.Then

N⁡\(x\)=F⁡\(Δ\),D⁡\(x\)=F⁡\(0\),F′​\(t\)=∫abϕ⁡\(u\+t\)​𝑑u=Φ⁡\(b\+t\)−Φ⁡\(a\+t\),N\(x\)=F\(\\Delta\),\\qquad D\(x\)=F\(0\),\\qquad F^\{\\prime\}\(t\)=\\int\_\{a\}^\{b\}\\phi\(u\+t\)\\,du=\\Phi\(b\+t\)\-\\Phi\(a\+t\),soF′​\(0\)=∫QRϕ⁡\(τ−x\)​𝑑τF^\{\\prime\}\(0\)=\\int\_\{Q\}^\{R\}\\phi\(\\tau\-x\)\\,d\\tauandF′​\(Δ\)=∫QRϕ⁡\(τ−x\+Δ\)​𝑑τF^\{\\prime\}\(\\Delta\)=\\int\_\{Q\}^\{R\}\\phi\(\\tau\-x\+\\Delta\)\\,d\\tau\. Inequality \([15](https://arxiv.org/html/2608.26324#A3.E15)\) therefore reads

F⁡\(Δ\)​F′​\(0\)≥F⁡\(0\)​F′​\(Δ\),i\.e\.,F′​\(Δ\)F⁡\(Δ\)≤F′​\(0\)F⁡\(0\),F\(\\Delta\)\\,F^\{\\prime\}\(0\)\\;\\geq\\;F\(0\)\\,F^\{\\prime\}\(\\Delta\),\\qquad\\text\{i\.e\.,\}\\qquad\\frac\{F^\{\\prime\}\(\\Delta\)\}\{F\(\\Delta\)\}\\;\\leq\\;\\frac\{F^\{\\prime\}\(0\)\}\{F\(0\)\},which is equivalent to\(log⁡F\)′\(\\log F\)^\{\\prime\}being non\-increasing, i\.e\.*FFis log\-concave intt*\.

WriteFFas a convolution:

F⁡\(t\)=∫abΦ⁡\(u\+t\)​𝑑u=∫−∞∞Φ⁡\(t−v\)​1\[−b,−a\]​\(v\)​𝑑v=\(Φ∗𝟏\[−b,−a\]\)​\(t\)\.F\(t\)=\\int\_\{a\}^\{b\}\\Phi\(u\+t\)\\,du=\\int\_\{\-\\infty\}^\{\\infty\}\\Phi\(t\-v\)\\,\\mathbf\{1\}\_\{\[\-b,\-a\]\}\(v\)\\,dv=\\bigl\(\\Phi\\ast\\mathbf\{1\}\_\{\[\-b,\-a\]\}\\bigr\)\(t\)\.Both factors are log\-concave:Φ\\Phiis log\-concave and𝟏\[−b,−a\]\\mathbf\{1\}\_\{\[\-b,\-a\]\}is the indicator of a convex set, hence log\-concave\. By the Prékopa–Leindler inequality, the convolution of log\-concave functions is log\-concave\. ThereforeFFis log\-concave intt, which establishesR1′​\(x\)≥0R\_\{1\}^\{\\prime\}\(x\)\\geq 0\.

Similarly, setN~​\(x\)=∫QRΦ⁡\(x−τ\+Δ\)​𝑑τ\\widetilde\{N\}\(x\)=\\int\_\{Q\}^\{R\}\\Phi\(x\-\\tau\+\\Delta\)\\,d\\tauandD~​\(x\)=∫QRΦ⁡\(x−τ\)​𝑑τ\\widetilde\{D\}\(x\)=\\int\_\{Q\}^\{R\}\\Phi\(x\-\\tau\)\\,d\\tau, so thatR2​\(x\)=N~​\(x\)/D~​\(x\)R\_\{2\}\(x\)=\\widetilde\{N\}\(x\)/\\widetilde\{D\}\(x\)\. Substitutingv=x−τv=x\-\\taugives

N~\(x\)=F~\(Δ\),D~\(x\)=F~\(0\),whereF~\(t\):=∫x−Rx−QΦ\(v\+t\)dv\.\\widetilde\{N\}\(x\)=\\widetilde\{F\}\(\\Delta\),\\qquad\\widetilde\{D\}\(x\)=\\widetilde\{F\}\(0\),\\qquad\\text\{where\}\\quad\\widetilde\{F\}\(t\):=\\int\_\{x\-R\}^\{x\-Q\}\\Phi\(v\+t\)\\,dv\.Sincedd​x​Φ​\(x−τ\+Δ\)=ϕ⁡\(x−τ\+Δ\)\\frac\{d\}\{dx\}\\Phi\(x\-\\tau\+\\Delta\)=\\phi\(x\-\\tau\+\\Delta\), the same computation yieldsR2′​\(x\)≤0R\_\{2\}^\{\\prime\}\(x\)\\leq 0if and only if

F~′​\(Δ\)​F~​\(0\)≥F~​\(Δ\)​F~′​\(0\),i\.e\.,F~′​\(Δ\)F~​\(Δ\)≥F~′​\(0\)F~​\(0\)\.\\widetilde\{F\}^\{\\prime\}\(\\Delta\)\\,\\widetilde\{F\}\(0\)\\;\\geq\\;\\widetilde\{F\}\(\\Delta\)\\,\\widetilde\{F\}^\{\\prime\}\(0\),\\qquad\\text\{i\.e\.,\}\\qquad\\frac\{\\widetilde\{F\}^\{\\prime\}\(\\Delta\)\}\{\\widetilde\{F\}\(\\Delta\)\}\\;\\geq\\;\\frac\{\\widetilde\{F\}^\{\\prime\}\(0\)\}\{\\widetilde\{F\}\(0\)\}\.ButF~\\widetilde\{F\}is again a convolution ofΦ\\Phiwith an indicator, hence log\-concave inttby the same argument\. Log\-concavity gives\(log⁡F~\)′=F~′/F~\(\\log\\widetilde\{F\}\)^\{\\prime\}=\\widetilde\{F\}^\{\\prime\}/\\widetilde\{F\}non\-increasing, which is precisely the required inequality\. ThereforeR2′​\(x\)≤0R\_\{2\}^\{\\prime\}\(x\)\\leq 0\. ∎

### C\.2Proof of[Theorem4\.3](https://arxiv.org/html/2608.26324#S4.Thmtheorem3)\(DP\-ITP Regret\)

We analyze the regret of PrivITP against an arbitrary comparator policyπ∗\\pi^\{\*\}using a unified smoothed\-relu framework: both the Phase 1 threshold noise and the Phase 2 query noise induce policies whose weights differ from Huang et al\.’s idealχ2\\chi^\{2\}\-policy by a bounded pointwise amount, and the regret gap is controlled uniformly by a single*smoothed\-weight lemma*\.

###### Proof\.

Definer⁡\(x,y\):=r^D​\(x,y\)r\(x,y\):=\\hat\{r\}\_\{D\}\(x,y\)for brevity\. Letπχβ\\pi\_\{\\chi\}^\{\\beta\}denote theχ2\\chi^\{2\}\-regularized policy with clean rewardsr⁡\(x,y\)r\(x,y\)and empirical thresholdλ∗\\lambda^\{\*\}, i\.e\.,

πχβ​\(y\|x\)=1Z∗​π0​\(y\|x\)⋅w∗​\(x,y\),w∗​\(y\):=relu⁡\(β−1​\(r⁡\(x,y\)−λ∗\)CLOSE,\\pi\_\{\\chi\}^\{\\beta\}\(y\|x\)=\\frac\{1\}\{Z^\{\*\}\}\\pi\_\{0\}\(y\|x\)\\cdot w^\{\*\}\(x,y\),\\qquad w^\{\*\}\(y\):=\\mathrm\{relu\}\\bigl\(\\beta^\{\-1\}\(r\(x,y\)\-\\lambda^\{\*\}\\bigr\),whereλ∗\\lambda^\{\*\}is defined by1n​∑i=1nrelu⁡\(β−1​\(r^D​\(x,yi\)−λ\)\)=1\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\mathrm\{relu\}\\\!\\big\(\\beta^\{\-1\}\(\\hat\{r\}\_\{D\}\(x,y\_\{i\}\)\-\\lambda\)\\big\)=1\[[13](https://arxiv.org/html/2608.26324#bib.bib18), Lemma C\.1\]\. LetπPrivITP\\pi\_\{\\mathrm\{PrivITP\}\}denote the actual policy induced by[Algorithm2](https://arxiv.org/html/2608.26324#alg2), marginalizing over all Phase 1 and Phase 2 noise and over the rejection sampling randomness\.

Regret Decomposition\.Introduce two intermediate policies:

πb​\(y\|x\)\\displaystyle\\pi\_\{b\}\(y\|x\)=1Zb​π0​\(y\|x\)⋅wb​\(x,y\),\\displaystyle=\\frac\{1\}\{Z\_\{b\}\}\\pi\_\{0\}\(y\|x\)\\cdot w\_\{b\}\(x,y\),wb​\(x,y\)\\displaystyle w\_\{b\}\(x,y\):=relu⁡\(β−1​\(r⁡\(x,y\)−λ~\)\),\\displaystyle:=\\mathrm\{relu\}\\bigl\(\\beta^\{\-1\}\(r\(x,y\)\-\\tilde\{\\lambda\}\)\\bigr\),πw¯​\(y\|x\)\\displaystyle\\pi\_\{\\bar\{w\}\}\(y\|x\)=1Zw¯​π0​\(y\|x\)⋅w¯​\(x,y\),\\displaystyle=\\frac\{1\}\{Z\_\{\\bar\{w\}\}\}\\pi\_\{0\}\(y\|x\)\\cdot\\bar\{w\}\(x,y\),w¯​\(x,y\)\\displaystyle\\bar\{w\}\(x,y\):=𝔼g∼𝒩⁡\(0,σZ2\)​\[relu⁡\(β−1​\(r⁡\(x,y\)\+g−λ~\)\)\],\\displaystyle:=\\mathbb\{E\}\_\{g\\sim\\mathcal\{N\}\(0,\\sigma\_\{Z\}^\{2\}\)\}\\\!\\left\[\\mathrm\{relu\}\\bigl\(\\beta^\{\-1\}\(r\(x,y\)\+g\-\\tilde\{\\lambda\}\)\\bigr\)\\right\],whereλ~=λ∗\+ζ\\tilde\{\\lambda\}=\\lambda^\{\*\}\+\\zetawithζ∼𝒩⁡\(0,σX2\)\\zeta\\sim\\mathcal\{N\}\(0,\\sigma\_\{X\}^\{2\}\)\. The policyπb\\pi\_\{b\}uses the noisy thresholdλ~\\tilde\{\\lambda\}with clean rewards;πw¯\\pi\_\{\\bar\{w\}\}additionally marginalizes the Phase 2 Gaussian noise\.

Now, we decompose the \(expected\) regret of PrivITP as

Reg\(x\)=\[J⁡\(π∗\)−J⁡\(πχβ\)\]⏟\(A\): skyline\+\[J⁡\(πχβ\)−J⁡\(πb\)\]⏟\(B1\): Phase 1 noise\+\[J⁡\(πb\)−J⁡\(πw¯\)\]⏟\(B2\): Phase 2 noise\+\[J⁡\(πw¯\)−J⁡\(πPrivITP\)\]⏟\(B3\): finite sample\.\\mathrm\{Reg\}\(x\)=\\underbrace\{\\bigl\[J\(\\pi^\{\*\}\)\-J\(\\pi\_\{\\chi\}^\{\\beta\}\)\\bigr\]\}\_\{\\text\{\(A\): skyline\}\}\+\\underbrace\{\\bigl\[J\(\\pi\_\{\\chi\}^\{\\beta\}\)\-J\(\\pi\_\{b\}\)\\bigr\]\}\_\{\\text\{\(B1\): Phase 1 noise\}\}\+\\underbrace\{\\bigl\[J\(\\pi\_\{b\}\)\-J\(\\pi\_\{\\bar\{w\}\}\)\\bigr\]\}\_\{\\text\{\(B2\): Phase 2 noise\}\}\+\\underbrace\{\\bigl\[J\(\\pi\_\{\\bar\{w\}\}\)\-J\(\\pi\_\{\\mathrm\{PrivITP\}\}\)\\bigr\]\}\_\{\\text\{\(B3\): finite sample\}\}\.
Term \(A\): Skyline\.Sinceπχβ\\pi\_\{\\chi\}^\{\\beta\}is theχ2\\chi^\{2\}\-regularized policy with cleanr^\\hat\{r\}andλ∗\\lambda^\{\*\}, Theorem 4\.1 of[Huang et al\. \[13\]](https://arxiv.org/html/2608.26324#bib.bib18)applies and we get

J⁡\(π∗\)−J⁡\(πχβ\)≤Cπ∗​\(x\)​εRM2​\(x\)\+β⋅Cπ∗​\(x\)\+β−1​εRM2​\(x\)\\displaystyle J\(\\pi^\{\*\}\)\-J\(\\pi\_\{\\chi\}^\{\\beta\}\)\\leq\\sqrt\{C^\{\\pi^\{\*\}\}\(x\)\\varepsilon\_\{\\mathrm\{RM\}\}^\{2\}\(x\)\}\+\\beta\\cdot C^\{\\pi^\{\*\}\}\(x\)\+\\beta^\{\-1\}\\varepsilon\_\{\\mathrm\{RM\}\}^\{2\}\(x\)~\(16\)forn=Ω⁡\(Rmaxβ​log⁡\(Rmaxβ​ϵRM\)\)n=\\Omega\\\!\\left\(\\frac\{R\_\{\\max\}\}\{\\beta\}\\log\\\!\\left\(\\frac\{R\_\{\\max\}\}\{\\beta\\,\\epsilon\_\{\\mathrm\{RM\}\}\}\\right\)\\right\)\.

We now establish a lemma that will help us bound the remaining terms\.

###### Lemma C\.3\(Smoothed\-weight policy comparison\)\.

Letw1,w2:𝒴→ℝ≥0w\_\{1\},w\_\{2\}:\\mathcal\{Y\}\\to\\mathbb\{R\}\_\{\\geq 0\}be non\-negative weight functions with normalizationsZi=𝔼πref​\[wi\]\>0Z\_\{i\}=\\mathbb\{E\}\_\{\\pi\_\{\\mathrm\{ref\}\}\}\[w\_\{i\}\]\>0, and letπi​\(y\)=πref​\(y\)​wi​\(y\)/Zi\\pi\_\{i\}\(y\)=\\pi\_\{\\mathrm\{ref\}\}\(y\)w\_\{i\}\(y\)/Z\_\{i\}\. Suppose‖w1−w2‖∞≤η\\\|w\_\{1\}\-w\_\{2\}\\\|\_\{\\infty\}\\leq\\eta\. Then:

\|J⁡\(π1\)−J⁡\(π2\)\|≤2​Rmax​ηmax⁡\(Z1,Z2\)\.\|J\(\\pi\_\{1\}\)\-J\(\\pi\_\{2\}\)\|\\leq\\frac\{2R\_\{\\max\}\\eta\}\{\\max\(Z\_\{1\},Z\_\{2\}\)\}\.

###### Proof of Lemma[C\.3](https://arxiv.org/html/2608.26324#A3.Thmtheorem3)\.

Observe that

J⁡\(π1\)−J⁡\(π2\)\\displaystyle J\(\\pi\_\{1\}\)\-J\(\\pi\_\{2\}\)=𝔼πref​\[r∗​w1\]Z1−𝔼πref​\[r∗​w2\]Z2\\displaystyle=\\frac\{\\mathbb\{E\}\_\{\\pi\_\{\\mathrm\{ref\}\}\}\[r^\{\*\}w\_\{1\}\]\}\{Z\_\{1\}\}\-\\frac\{\\mathbb\{E\}\_\{\\pi\_\{\\mathrm\{ref\}\}\}\[r^\{\*\}w\_\{2\}\]\}\{Z\_\{2\}\}=Z2​𝔼​\[r∗​w1\]−Z1​𝔼​\[r∗​w2\]Z1​Z2\\displaystyle=\\frac\{Z\_\{2\}\\mathbb\{E\}\[r^\{\*\}w\_\{1\}\]\-Z\_\{1\}\\mathbb\{E\}\[r^\{\*\}w\_\{2\}\]\}\{Z\_\{1\}Z\_\{2\}\}=Z2​𝔼​\[r∗​\(w1−w2\)\]\+\(Z2−Z1\)​𝔼​\[r∗​w2\]Z1​Z2\.\\displaystyle=\\frac\{Z\_\{2\}\\mathbb\{E\}\[r^\{\*\}\(w\_\{1\}\-w\_\{2\}\)\]\+\(Z\_\{2\}\-Z\_\{1\}\)\\mathbb\{E\}\[r^\{\*\}w\_\{2\}\]\}\{Z\_\{1\}Z\_\{2\}\}\.Usingr∗≤Rmaxr^\{\*\}\\leq R\_\{\\max\},‖w1−w2‖∞≤η\\\|w\_\{1\}\-w\_\{2\}\\\|\_\{\\infty\}\\leq\\eta,\|Z1−Z2\|≤η\|Z\_\{1\}\-Z\_\{2\}\|\\leq\\eta, and𝔼⁡\[r∗​w2\]≤Rmax​Z2\\mathbb\{E\}\[r^\{\*\}w\_\{2\}\]\\leq R\_\{\\max\}Z\_\{2\}:

\|J⁡\(π1\)−J⁡\(π2\)\|≤Z2​Rmax​η\+η​Rmax​Z2Z1​Z2=2​Rmax​ηZ1\.\|J\(\\pi\_\{1\}\)\-J\(\\pi\_\{2\}\)\|\\leq\\frac\{Z\_\{2\}R\_\{\\max\}\\eta\+\\eta R\_\{\\max\}Z\_\{2\}\}\{Z\_\{1\}Z\_\{2\}\}=\\frac\{2R\_\{\\max\}\\eta\}\{Z\_\{1\}\}\.By symmetry, the same bound holds withZ1Z\_\{1\}replaced byZ2Z\_\{2\}, giving the stated result withmax⁡\(Z1,Z2\)\\max\(Z\_\{1\},Z\_\{2\}\)\. ∎

Term \(B1\): Phase 1 noise effect\.Fixτ\\tau\. Sincerelu\\mathrm\{relu\}is 1\-Lipschitz, we get

‖w∗−wb‖∞=supy\|relu⁡\(r⁡\(x,y\)−λ∗β\)−relu⁡\(r⁡\(x,y\)−λ∗−ζβ\)\|≤\|ζ\|β\.\\\|w^\{\*\}\-w\_\{b\}\\\|\_\{\\infty\}=\\sup\_\{y\}\\left\|\\mathrm\{relu\}\\\!\\left\(\\frac\{r\(x,y\)\-\\lambda^\{\*\}\}\{\\beta\}\\right\)\-\\mathrm\{relu\}\\\!\\left\(\\frac\{r\(x,y\)\-\\lambda^\{\*\}\-\\zeta\}\{\\beta\}\\right\)\\right\|\\leq\\frac\{\|\\zeta\|\}\{\\beta\}\.The normalizationZ∗=1Z^\{\*\}=1\(by definition ofλ∗\\lambda^\{\*\}\)\. Thus\|Zb−Z∗\|≤‖wb−w∗‖∞≤\|ζ\|/β\|Z\_\{b\}\-Z^\{\*\}\|\\leq\\\|w\_\{b\}\-w^\{\*\}\\\|\_\{\\infty\}\\leq\|\\zeta\|/\\beta\. Hence, by Lemma[C\.3](https://arxiv.org/html/2608.26324#A3.Thmtheorem3)withη=\|ζ\|/β\\eta=\|\\zeta\|/\\beta, andmax⁡\{Z∗,Zb\}≥Z∗=1\\max\\\{Z^\{\*\},Z\_\{b\}\\\}\\geq Z^\{\*\}=1, we get

\|J⁡\(πχβ\)−J⁡\(πb\)\|⋅𝟏𝒢1≤2​Rmax​\|ζ\|/β1=2​Rmax​\|ζ\|β\.\|J\(\\pi\_\{\\chi\}^\{\\beta\}\)\-J\(\\pi\_\{b\}\)\|\\cdot\\mathbf\{1\}\_\{\\mathcal\{G\}\_\{1\}\}\\leq\\frac\{2R\_\{\\max\}\|\\zeta\|/\\beta\}\{1\}=\\frac\{2R\_\{\\max\}\|\\zeta\|\}\{\\beta\}\.Taking expectation overζ\\zeta, we get

\|J⁡\(πχβ\)−J⁡\(πb\)\|≤2​Rmax​𝔼​\|ζ\|β≤2​Rmax​σX​2/πβ=O⁡\(Rmax​σX/β\)\.\|J\(\\pi\_\{\\chi\}^\{\\beta\}\)\-J\(\\pi\_\{b\}\)\|\\leq\\frac\{2R\_\{\\max\}\\mathbb\{E\}\|\\zeta\|\}\{\\beta\}\\leq\\frac\{2R\_\{\\max\}\\sigma\_\{X\}\\sqrt\{2/\\pi\}\}\{\\beta\}=O\(R\_\{\\max\}\\sigma\_\{X\}/\\beta\)\.\(17\)
Term \(B2\): Phase 2 noise effect\.Define the Gaussian\-smoothed reluφτ:ℝ→ℝ≥0\\varphi\_\{\\tau\}:\\mathbb\{R\}\\to\\mathbb\{R\}\_\{\\geq 0\}by

φτ​\(z\):=𝔼g∼𝒩⁡\(0,τ2\)​\[relu⁡\(z\+g\)\]=z​Φ​\(z/τ\)\+τ​ϕ​\(z/τ\),\\varphi\_\{\\tau\}\(z\):=\\mathbb\{E\}\_\{g\\sim\\mathcal\{N\}\(0,\\tau^\{2\}\)\}\[\\mathrm\{relu\}\(z\+g\)\]=z\\Phi\(z/\\tau\)\+\\tau\\phi\(z/\\tau\),whereΦ,ϕ\\Phi,\\phiare the standard Gaussian CDF and PDF\. Settingτ=σZ/β\\tau=\\sigma\_\{Z\}/\\beta, we havew¯​\(x,y\)=φτ​\(β−1​\(r⁡\(x,y\)−λ~\)\)\\bar\{w\}\(x,y\)=\\varphi\_\{\\tau\}\(\\beta^\{\-1\}\(r\(x,y\)\-\\tilde\{\\lambda\}\)\)\.

Note thatφτ​\(z\)−relu⁡\(z\)≥0\\varphi\_\{\\tau\}\(z\)\-\\mathrm\{relu\}\(z\)\\geq 0by Jensen inequality applied to the convexrelu\\mathrm\{relu\}function\. Moreover, observe that

supz\(φτ​\(z\)−relu⁡\(z\)\)=φτ​\(0\)=τ​ϕ​\(0\)=τ2​π,\\sup\_\{z\}\\bigl\(\\varphi\_\{\\tau\}\(z\)\-\\mathrm\{relu\}\(z\)\\bigr\)=\\varphi\_\{\\tau\}\(0\)=\\tau\\phi\(0\)=\\frac\{\\tau\}\{\\sqrt\{2\\pi\}\},as maximum holds atz=0z=0by standard calculus onh⁡\(z\)=φτ​\(z\)−relu⁡\(z\)h\(z\)=\\varphi\_\{\\tau\}\(z\)\-\\mathrm\{relu\}\(z\):h′​\(z\)=Φ⁡\(z/τ\)\>0h^\{\\prime\}\(z\)=\\Phi\(z/\\tau\)\>0forz<0z<0andh′​\(z\)=Φ⁡\(z/τ\)−1<0h^\{\\prime\}\(z\)=\\Phi\(z/\\tau\)\-1<0forz\>0z\>0\. Therefore, we get

‖wb−w¯‖∞≤τ2​π=σZβ​2​π\.\\\|w\_\{b\}\-\\bar\{w\}\\\|\_\{\\infty\}\\leq\\frac\{\\tau\}\{\\sqrt\{2\\pi\}\}=\\frac\{\\sigma\_\{Z\}\}\{\\beta\\sqrt\{2\\pi\}\}\.This yields\|Zb−Zw¯\|≤‖wb−w¯‖∞≤σZ/\(β​2​π\)\|Z\_\{b\}\-Z\_\{\\bar\{w\}\}\|\\leq\\\|w\_\{b\}\-\\bar\{w\}\\\|\_\{\\infty\}\\leq\\sigma\_\{Z\}/\(\\beta\\sqrt\{2\\pi\}\)\.

On the event𝒢1:=\{\|ζ\|≤β/2\}\\mathcal\{G\}\_\{1\}:=\\\{\|\\zeta\|\\leq\\beta/2\\\}, we have\|Zb−1\|=\|Zb−Z∗\|≤\|ζ\|/β≤1/2\|Z\_\{b\}\-1\|=\|Z\_\{b\}\-Z^\{\*\}\|\\leq\|\\zeta\|/\\beta\\leq 1/2\. Hence, on𝒢1\\mathcal\{G\}\_\{1\}, we haveZb≥1/2Z\_\{b\}\\geq 1/2\. Hence by Lemma[C\.3](https://arxiv.org/html/2608.26324#A3.Thmtheorem3)withη=σZ/\(β​2​π\)\\eta=\\sigma\_\{Z\}/\(\\beta\\sqrt\{2\\pi\}\)andmax⁡\(Zb,Zw¯\)≥Zb≥1/2\\max\(Z\_\{b\},Z\_\{\\bar\{w\}\}\)\\geq Z\_\{b\}\\geq 1/2, we obtain

\|J⁡\(πb\)−J⁡\(πw¯\)\|⋅𝟏𝒢1≤2​Rmax⋅σZ/\(β​2​π\)1/2=4​Rmax​σZβ​2​π\.\|J\(\\pi\_\{b\}\)\-J\(\\pi\_\{\\bar\{w\}\}\)\|\\cdot\\mathbf\{1\}\_\{\\mathcal\{G\}\_\{1\}\}\\leq\\frac\{2R\_\{\\max\}\\cdot\\sigma\_\{Z\}/\(\\beta\\sqrt\{2\\pi\}\)\}\{1/2\}=\\frac\{4R\_\{\\max\}\\sigma\_\{Z\}\}\{\\beta\\sqrt\{2\\pi\}\}\.NowPr\[𝒢1c\]=Pr\[\|ζ\|\>β/2\]≤2exp\(−β2/\(8σX2\)\)\\Pr\[\\mathcal\{G\}\_\{1\}^\{c\}\]=\\Pr\[\|\\zeta\|\>\\beta/2\]\\leq 2\\exp\(\-\\beta^\{2\}/\(8\\sigma\_\{X\}^\{2\}\)\), and the value gap is bounded trivially byRmaxR\_\{\\max\}on𝒢1c\\mathcal\{G\}\_\{1\}^\{c\}\. Then we get

\|J⁡\(πb\)−J⁡\(πw¯\)\|≤4​Rmax​σZβ​2​π\+Rmax​Pr⁡\[𝒢1c\]≤4​Rmax​σZβ​2​π\+2​Rmax​exp⁡\(−β28​σX2\)\.\|J\(\\pi\_\{b\}\)\-J\(\\pi\_\{\\bar\{w\}\}\)\|\\leq\\frac\{4R\_\{\\max\}\\sigma\_\{Z\}\}\{\\beta\\sqrt\{2\\pi\}\}\+R\_\{\\max\}\\Pr\[\\mathcal\{G\}\_\{1\}^\{c\}\]\\leq\\frac\{4R\_\{\\max\}\\sigma\_\{Z\}\}\{\\beta\\sqrt\{2\\pi\}\}\+2R\_\{\\max\}\\exp\\\!\\left\(\-\\frac\{\\beta^\{2\}\}\{8\\sigma\_\{X\}^\{2\}\}\\right\)\.This yields

\|J⁡\(πb\)−J⁡\(πw¯\)\|≤O⁡\(Rmax​σZ/β\)\+2​Rmax​exp⁡\(−β28​σX2\)\.\|J\(\\pi\_\{b\}\)\-J\(\\pi\_\{\\bar\{w\}\}\)\|\\leq O\(R\_\{\\max\}\\sigma\_\{Z\}/\\beta\)\+2R\_\{\\max\}\\exp\\\!\\left\(\-\\frac\{\\beta^\{2\}\}\{8\\sigma\_\{X\}^\{2\}\}\\right\)\.\(18\)
Term \(B3\): Finite\-sample and truncation correction\.We bound the gap between the Phase 2 target policyπw¯\\pi\_\{\\bar\{w\}\}and the actual algorithm outputπPrivITP\\pi\_\{\\mathrm\{PrivITP\}\}, which arises from the finite number of candidates and the handling of unbounded Gaussian query noise via truncation\. The analysis proceeds by conditioning on the Phase 1 noiseζ\\zeta, applying a rejection sampling argument for each fixedζ\\zeta, and then averaging\.

*Conditioning onζ\\zeta\.*

Recallλ~=λ∗\+ζ\\tilde\{\\lambda\}=\\lambda^\{\*\}\+\\zetawithζ∼𝒩⁡\(0,σX2\)\\zeta\\sim\\mathcal\{N\}\(0,\\sigma\_\{X\}^\{2\}\)\. Bothπw¯\\pi\_\{\\bar\{w\}\}andπPrivITP\\pi\_\{\\mathrm\{PrivITP\}\}depend onζ\\zetathroughλ~\\tilde\{\\lambda\}\. For each fixedζ\\zeta, define the conditional target

πw¯\(ζ\)​\(y\|x\)=π0​\(y\)​w¯\(ζ\)​\(x,y\)Zw¯\(ζ\),w¯\(ζ\)​\(x,y\)=𝔼g′​\[relu⁡\(β−1​\(r⁡\(x,y\)\+g′−λ~\)\)\],Zw¯\(ζ\)=𝔼π0​\[w¯\(ζ\)\],\\pi\_\{\\bar\{w\}\}^\{\(\\zeta\)\}\(y\|x\)=\\frac\{\\pi\_\{0\}\(y\)\\,\\bar\{w\}^\{\(\\zeta\)\}\(x,y\)\}\{Z\_\{\\bar\{w\}\}^\{\(\\zeta\)\}\},\\quad\\bar\{w\}^\{\(\\zeta\)\}\(x,y\)=\\mathbb\{E\}\_\{g^\{\\prime\}\}\\bigl\[\\mathrm\{relu\}\\bigl\(\\beta^\{\-1\}\(r\(x,y\)\+g^\{\\prime\}\-\\tilde\{\\lambda\}\)\\bigr\)\\bigr\],\\quad Z\_\{\\bar\{w\}\}^\{\(\\zeta\)\}=\\mathbb\{E\}\_\{\\pi\_\{0\}\}\[\\bar\{w\}^\{\(\\zeta\)\}\],and letπPrivITP\(ζ\)\\pi\_\{\\mathrm\{PrivITP\}\}^\{\(\\zeta\)\}denote the algorithm’s output distribution conditional onζ\\zeta\(marginalizing over Phase 2 candidates, Phase 2 noise, and rejection sampling uniform samples\)\. The full distributions satisfyJ⁡\(πw¯\)=𝔼ζ​\[J⁡\(πw¯\(ζ\)\)\]J\(\\pi\_\{\\bar\{w\}\}\)=\\mathbb\{E\}\_\{\\zeta\}\[J\(\\pi\_\{\\bar\{w\}\}^\{\(\\zeta\)\}\)\]andJ⁡\(πPrivITP\)=𝔼ζ​\[J⁡\(πPrivITP\(ζ\)\)\]J\(\\pi\_\{\\mathrm\{PrivITP\}\}\)=\\mathbb\{E\}\_\{\\zeta\}\[J\(\\pi\_\{\\mathrm\{PrivITP\}\}^\{\(\\zeta\)\}\)\]\. By the triangle inequality

\|J⁡\(πw¯\)−J⁡\(πPrivITP\)\|≤𝔼ζ​\|J⁡\(πw¯\(ζ\)\)−J⁡\(πPrivITP\(ζ\)\)\|\.\|J\(\\pi\_\{\\bar\{w\}\}\)\-J\(\\pi\_\{\\mathrm\{PrivITP\}\}\)\|\\leq\\mathbb\{E\}\_\{\\zeta\}\\bigl\|J\(\\pi\_\{\\bar\{w\}\}^\{\(\\zeta\)\}\)\-J\(\\pi\_\{\\mathrm\{PrivITP\}\}^\{\(\\zeta\)\}\)\\bigr\|\.\(19\)It suffices to bound the conditional gap for eachζ\\zetain the “good event”𝒢1:=\{\|ζ\|≤β/2\}\\mathcal\{G\}\_\{1\}:=\\\{\|\\zeta\|\\leq\\beta/2\\\}\. Under this event,Zb\(ζ\)≥1/2Z\_\{b\}^\{\(\\zeta\)\}\\geq 1/2\. Sinceφτ​\(z\)−relu⁡\(z\)≥0\\varphi\_\{\\tau\}\(z\)\-\\mathrm\{relu\}\(z\)\\geq 0\(by Jensen applied to the convexrelu\\mathrm\{relu\}\), we getw¯\(ζ\)≥wb\(ζ\)\\bar\{w\}^\{\(\\zeta\)\}\\geq w\_\{b\}^\{\(\\zeta\)\}and thusZw¯\(ζ\)≥1/2Z\_\{\\bar\{w\}\}^\{\(\\zeta\)\}\\geq 1/2\. The gap under𝒢1c\\mathcal\{G\}\_\{1\}^\{c\}can be bounded byRmaxR\_\{\\max\}\.

Phase 2 event decomposition \(fixζ∈𝒢1\\zeta\\in\\mathcal\{G\}\_\{1\}\)\.

The Phase 2 algorithm drawsnni\.i\.d\. triples\(yj′,gj′,Uj\)j=1n\(y^\{\\prime\}\_\{j\},g^\{\\prime\}\_\{j\},U\_\{j\}\)\_\{j=1\}^\{n\}whereyj′∼π0\(⋅\|x\)y^\{\\prime\}\_\{j\}\\sim\\pi\_\{0\}\(\\cdot\|x\),gj′∼𝒩⁡\(0,σZ2\)g^\{\\prime\}\_\{j\}\\sim\\mathcal\{N\}\(0,\\sigma\_\{Z\}^\{2\}\),Uj∼Unif⁡\[0,1\]U\_\{j\}\\sim\\mathrm\{Unif\}\[0,1\]\. Define the per\-trial weight

Wj:=relu⁡\(β−1​\(r⁡\(x,yj′\)\+gj′−λ~\)\),W\_\{j\}:=\\mathrm\{relu\}\\bigl\(\\beta^\{\-1\}\(r\(x,y^\{\\prime\}\_\{j\}\)\+g^\{\\prime\}\_\{j\}\-\\tilde\{\\lambda\}\)\\bigr\),and truncation level

M:=\(Rmax\+σZ​L−λ~\)/β,L:=2​log⁡\(n/δ\),M:=\(R\_\{\\max\}\+\\sigma\_\{Z\}L\-\\tilde\{\\lambda\}\)/\\beta,\\qquad L:=\\sqrt\{2\\log\(n/\\delta\)\},for a parameterδ∈\(0,1\)\\delta\\in\(0,1\)to be chosen\.

Note thatλ∗∈\[−β,Rmax−β\]\\lambda^\{\*\}\\in\[\-\\beta,R\_\{\\max\}\-\\beta\]from[Huang et al\. \[13, Lemma C\.1\]](https://arxiv.org/html/2608.26324#bib.bib18)\. On𝒢1=\{\|ζ\|≤β/2\}\\mathcal\{G\}\_\{1\}=\\\{\|\\zeta\|\\leq\\beta/2\\\}and henceλ~≤Rmax−β/2\\tilde\{\\lambda\}\\leq R\_\{\\max\}\-\\beta/2, henceM≥\(σZ​L\+β/2\)/β≥1/2\>0M\\geq\(\\sigma\_\{Z\}L\+\\beta/2\)/\\beta\\geq 1/2\>0on𝒢1\\mathcal\{G\}\_\{1\}\.

Now, the algorithm accepts at stepjjifUj≤min⁡\(Wj/M,1\)U\_\{j\}\\leq\\min\(W\_\{j\}/M,1\)\. The outputY∗Y^\{\*\}is the first accepted candidate \(or a fallbackY∗∼π0\(⋅\|x\)Y^\{\*\}\\sim\\pi\_\{0\}\(\\cdot\|x\)if no acceptance occurs\)\. Define three events on the Phase 2 randomness \(conditional on Phase 1 randomnessζ\\zeta\):

𝒯\\displaystyle\\mathcal\{T\}:=\{∃j∈\[n\]:Wj\>M\}\(truncation\),\\displaystyle:=\\\{\\exists j\\in\[n\]:W\_\{j\}\>M\\\}\\quad\\text\{\(truncation\)\},ℱ\\displaystyle\\mathcal\{F\}:=\{∀j∈\[n\]:Uj\>min\(Wj/M,1\)\}\(fallback\),\\displaystyle:=\\\{\\forall j\\in\[n\]:U\_\{j\}\>\\min\(W\_\{j\}/M,1\)\\\}\\quad\\text\{\(fallback\)\},𝒮\\displaystyle\\mathcal\{S\}:=𝒯c∩ℱc\(success: no truncation and at least one acceptance\)\.\\displaystyle:=\\mathcal\{T\}^\{c\}\\cap\\mathcal\{F\}^\{c\}\\quad\\text\{\(success: no truncation and at least one acceptance\)\}\.
BoundingPr⁡\[𝒯∣ζ\]\\Pr\[\\mathcal\{T\}\\mid\\zeta\]\.

On𝒢1\\mathcal\{G\}\_\{1\}, the eventWj\>MW\_\{j\}\>Mimpliesr⁡\(x,yj′\)\+gj′\>Rmax\+σZ​Lr\(x,y^\{\\prime\}\_\{j\}\)\+g^\{\\prime\}\_\{j\}\>R\_\{\\max\}\+\\sigma\_\{Z\}L\. Sincer⁡\(x,yj′\)≤Rmaxr\(x,y^\{\\prime\}\_\{j\}\)\\leq R\_\{\\max\}, this impliesgj′\>σZ​Lg^\{\\prime\}\_\{j\}\>\\sigma\_\{Z\}L\. By the Gaussian tail bound, for anyL\>0L\>0, we have

Pr\[Wj\>M\]≤Pr\[gj′\>σZL\]≤e−L2/2\.\\Pr\[W\_\{j\}\>M\]\\leq\\Pr\[g^\{\\prime\}\_\{j\}\>\\sigma\_\{Z\}L\]\\leq e^\{\-L^\{2\}/2\}\.SubstitutingL=2​log⁡\(n/δ\)L=\\sqrt\{2\\log\(n/\\delta\)\}, we getPr\[gj′\>σZL\]≤δ/n\\Pr\[g^\{\\prime\}\_\{j\}\>\\sigma\_\{Z\}L\]\\leq\\delta/n\. A union bound over thenntrials gives

Pr⁡\[𝒯∣ζ\]≤n⋅δ/n=δ\.\\Pr\[\\mathcal\{T\}\\mid\\zeta\]\\leq n\\cdot\\delta/n=\\delta\.\(20\)
BoundingPr⁡\[ℱ∣ζ\]\\Pr\[\\mathcal\{F\}\\mid\\zeta\]\.

The per\-trial acceptance probability is

pacc:=𝔼yj′,gj′\[Pr\[Uj≤min\(Wj/M,1\)\]\]=𝔼y′,g′\[min\(W/M,1\)\]\.p\_\{\\mathrm\{acc\}\}:=\\mathbb\{E\}\_\{y^\{\\prime\}\_\{j\},g^\{\\prime\}\_\{j\}\}\[\\Pr\[U\_\{j\}\\leq\\min\(W\_\{j\}/M,1\)\]\]=\\mathbb\{E\}\_\{y^\{\\prime\},g^\{\\prime\}\}\[\\min\(W/M,1\)\]\.Note that

pacc≥𝔼\[\(W/M\)𝟏\[W≤M\]\]=1M\(Zw¯\(ζ\)−𝔼\[W𝟏\[W\>M\]\]\)\.p\_\{\\mathrm\{acc\}\}\\geq\\mathbb\{E\}\[\(W/M\)\\mathbf\{1\}\[W\\leq M\]\]=\\frac\{1\}\{M\}\\bigl\(Z\_\{\\bar\{w\}\}^\{\(\\zeta\)\}\-\\mathbb\{E\}\[W\\mathbf\{1\}\[W\>M\]\]\\bigr\)\.
We need an upper bound on the second term𝔼\[W𝟏\[W\>M\]\]\\mathbb\{E\}\[W\\mathbf\{1\}\[W\>M\]\]\. SinceM\>0M\>0on the event𝒢1\\mathcal\{G\}\_\{1\}, the relu argument inWWis positive on the event\{W\>M\}\\\{W\>M\\\}\. Furthermore, since\{W\>M\}⊆\{g′\>σZL\}\\\{W\>M\\\}\\subseteq\\\{g^\{\\prime\}\>\\sigma\_\{Z\}L\\\}, we have

𝔼\[W𝟏\[W\>M\]\]≤𝔼\[β−1\(r\(x,y′\)\+g′−λ~\)𝟏\[g′\>σZL\]\]\.\\mathbb\{E\}\[W\\mathbf\{1\}\[W\>M\]\]\\leq\\mathbb\{E\}\[\\beta^\{\-1\}\(r\(x,y^\{\\prime\}\)\+g^\{\\prime\}\-\\tilde\{\\lambda\}\)\\mathbf\{1\}\[g^\{\\prime\}\>\\sigma\_\{Z\}L\]\]\.Usingr⁡\(x,y′\)≤Rmaxr\(x,y^\{\\prime\}\)\\leq R\_\{\\max\}, we get

𝔼\[\(Rmax\+g′−λ~\)𝟏\[g′\>σZL\]\]=\(Rmax−λ~\)Pr\[g′\>σZL\]\+σZ𝔼\[g′/σZ⋅𝟏\[g′/σZ\>L\]\]\.\\displaystyle\\mathbb\{E\}\[\(R\_\{\\max\}\+g^\{\\prime\}\-\\tilde\{\\lambda\}\)\\mathbf\{1\}\[g^\{\\prime\}\>\\sigma\_\{Z\}L\]\]=\(R\_\{\\max\}\-\\tilde\{\\lambda\}\)\\Pr\[g^\{\\prime\}\>\\sigma\_\{Z\}L\]\+\\sigma\_\{Z\}\\mathbb\{E\}\\big\[g^\{\\prime\}/\\sigma\_\{Z\}\\cdot\\mathbf\{1\}\[g^\{\\prime\}/\\sigma\_\{Z\}\>L\]\\big\]~\.UsingRmax−λ~=β​M−σZ​L≤β​MR\_\{\\max\}\-\\tilde\{\\lambda\}=\\beta M\-\\sigma\_\{Z\}L\\leq\\beta M,Pr\[g′\>σZL\]≤δ/n\\Pr\[g^\{\\prime\}\>\\sigma\_\{Z\}L\]\\leq\\delta/nand𝔼\[g′/σZ⋅𝟏\[g′/σZ\>L\]\]=ϕ\(L\)=e−L2/2/2​π=δ/\(n2​π\)\\mathbb\{E\}\\big\[g^\{\\prime\}/\\sigma\_\{Z\}\\cdot\\mathbf\{1\}\[g^\{\\prime\}/\\sigma\_\{Z\}\>L\]\\big\]=\\phi\(L\)=e^\{\-L^\{2\}/2\}/\\sqrt\{2\\pi\}=\\delta/\(n\\sqrt\{2\\pi\}\), we obtain

𝔼\[W𝟏\[W\>M\]\]≤\(β​M\+σZ\)​δβ​n=\(M\+σZ/β\)​δn\.\\displaystyle\\mathbb\{E\}\[W\\mathbf\{1\}\[W\>M\]\]\\leq\\frac\{\(\\beta M\+\\sigma\_\{Z\}\)\\delta\}\{\\beta n\}=\\frac\{\(M\+\\sigma\_\{Z\}/\\beta\)\\delta\}\{n\}\.\(21\)Sinceλ∗≥−β\\lambda^\{\*\}\\geq\-\\betaand onζ≥−β/2\\zeta\\geq\-\\beta/2on𝒢1\\mathcal\{G\}\_\{1\}, we haveλ~≥−3β/2\\tilde\{\\lambda\}\\geq\-3\\beta/2and henceM≤\(Rmax\+σZ​L\+3​β/2\)/βM\\leq\(R\_\{\\max\}\+\\sigma\_\{Z\}L\+3\\beta/2\)/\\betaon𝒢1\\mathcal\{G\}\_\{1\}\. HenceM\+σz/B≤2​MM\+\\sigma\_\{z\}/B\\leq 2M\.

On𝒢1\\mathcal\{G\}\_\{1\}, we also haveZw¯\(ζ\)≥1/2Z\_\{\\bar\{w\}\}^\{\(\\zeta\)\}\\geq 1/2and sopacc≥1M​\(12−2​M​δn\)=12​M−2​δnp\_\{\\mathrm\{acc\}\}\\geq\\frac\{1\}\{M\}\\left\(\\frac\{1\}\{2\}\-\\frac\{2M\\delta\}\{n\}\\right\)=\\frac\{1\}\{2M\}\-\\frac\{2\\delta\}\{n\}\.

Now, by independence of trials, we obtain

Pr⁡\[ℱ∣ζ\]=∏j=1n\(1−pacc\)\\displaystyle\\Pr\[\\mathcal\{F\}\\mid\\zeta\]=\\prod\_\{j=1\}^\{n\}\(1\-p\_\{\\mathrm\{acc\}\}\)≤\(1−\(12​M−2​δn\)\)n≤exp⁡\(−n2​M\+2​δ\)\\displaystyle\\leq\\left\(1\-\\left\(\\frac\{1\}\{2M\}\-\\frac\{2\\delta\}\{n\}\\right\)\\right\)^\{n\}\\leq\\exp\\left\(\-\\frac\{n\}\{2M\}\+2\\delta\\right\)≤exp⁡\(−β​n2​Rmax\+2​σZ​L\+3​β\+2​δ\)\.\\displaystyle\\leq\\exp\\left\(\-\\frac\{\\beta n\}\{2R\_\{\\max\}\+2\\sigma\_\{Z\}L\+3\\beta\}\+2\\delta\\right\)\.\(22\)
Output distribution on𝒮\\mathcal\{S\}\.

On𝒮\\mathcal\{S\}, no trial hasWj\>MW\_\{j\}\>M, so the acceptance ruleUj≤Wj/MU\_\{j\}\\leq W\_\{j\}/Mis the standard rejection sampling rule with a valid envelopeMM\. Define the*truncated*target policy

πw¯,M\(ζ\)\(y\|x\):=π0​\(y\|x\)​w¯M\(ζ\)​\(x,y\)Zw¯,M\(ζ\),w¯M\(ζ\)\(x,y\):=𝔼g\[W\(y,g\)𝟏\[W\(y,g\)≤M\]\],\\pi\_\{\\bar\{w\},M\}^\{\(\\zeta\)\}\(y\|x\):=\\frac\{\\pi\_\{0\}\(y\|x\)\\bar\{w\}\_\{M\}^\{\(\\zeta\)\}\(x,y\)\}\{Z\_\{\\bar\{w\},M\}^\{\(\\zeta\)\}\},\\qquad\\bar\{w\}\_\{M\}^\{\(\\zeta\)\}\(x,y\):=\\mathbb\{E\}\_\{g\}\[W\(y,g\)\\mathbf\{1\}\[W\(y,g\)\\leq M\]\],withW⁡\(y,g\):=relu⁡\(β−1​\(r⁡\(x,y\)\+gj−λ~\)\)W\(y,g\):=\\mathrm\{relu\}\\bigl\(\\beta^\{\-1\}\(r\(x,y\)\+g\_\{j\}\-\\tilde\{\\lambda\}\)\\bigr\)andZw¯,M\(ζ\)=𝔼π0​\[w¯M\(ζ\)\]Z\_\{\\bar\{w\},M\}^\{\(\\zeta\)\}=\\mathbb\{E\}\_\{\\pi\_\{0\}\}\[\\bar\{w\}\_\{M\}^\{\(\\zeta\)\}\]\.

###### Lemma C\.4\.

Conditional on𝒮\\mathcal\{S\}\(andζ\\zeta\), the Phase 2 outputY∗∼πw¯,M\(ζ\)\(⋅\|x\)Y^\{\*\}\\sim\\pi\_\{\\bar\{w\},M\}^\{\(\\zeta\)\}\(\\cdot\|x\)\.

###### Proof of claim\.

For a single trial, the joint density of\(yj′,gj′\)\(y^\{\\prime\}\_\{j\},g^\{\\prime\}\_\{j\}\)on the event “Wj≤MW\_\{j\}\\leq Mand accept atjj” is

p\(y,g\)=π0\(y\|x\)ϕσZ\(g\)𝟏\[W\(y,g\)≤M\]⋅\(W\(y,g\)/M\),p\(y,g\)=\\pi\_\{0\}\(y\|x\)\\phi\_\{\\sigma\_\{Z\}\}\(g\)\\mathbf\{1\}\[W\(y,g\)\\leq M\]\\cdot\(W\(y,g\)/M\),with marginal \(integrating overgg\):

∫pj\(y,g\)dg=π0​\(y\|x\)M∫ϕσZ\(g\)W\(y,g\)𝟏\[W\(y,g\)≤M\]dg=π0​\(y\|x\)​w¯M\(ζ\)​\(x,y\)M\.\\int p\_\{j\}\(y,g\)\\,dg=\\frac\{\\pi\_\{0\}\(y\|x\)\}\{M\}\\int\\phi\_\{\\sigma\_\{Z\}\}\(g\)W\(y,g\)\\mathbf\{1\}\[W\(y,g\)\\leq M\]\\,dg=\\frac\{\\pi\_\{0\}\(y\|x\)\\bar\{w\}\_\{M\}^\{\(\\zeta\)\}\(x,y\)\}\{M\}\.Normalizing, we getp⁡\(y∣accept at step​j,Wj≤M\)=π0​\(y\|x\)​w¯M\(ζ\)​\(x,y\)/Zw¯,M\(ζ\)=πw¯,M\(ζ\)​\(y\|x\)p\(y\\mid\\text\{accept at step \}j,W\_\{j\}\\leq M\)=\\pi\_\{0\}\(y\|x\)\\bar\{w\}\_\{M\}^\{\(\\zeta\)\}\(x,y\)/Z\_\{\\bar\{w\},M\}^\{\(\\zeta\)\}=\\pi\_\{\\bar\{w\},M\}^\{\(\\zeta\)\}\(y\|x\)\. Since each step conditional on acceptance and no truncation gives the same distribution, and the first\-accepted\-step stopping time does not bias this distribution, the outputY∗\|𝒮∼πw¯,M\(ζ\)Y^\{\*\}\\mid\\mathcal\{S\}\\sim\\pi\_\{\\bar\{w\},M\}^\{\(\\zeta\)\}exactly\. ∎

Bounding thew¯\\bar\{w\}vsw¯M\\bar\{w\}\_\{M\}gap\.

We bound the pointwise difference

\|w¯\(ζ\)​\(x,y\)−w¯M\(ζ\)​\(x,y\)\|\\displaystyle\|\\bar\{w\}^\{\(\\zeta\)\}\(x,y\)\-\\bar\{w\}\_\{M\}^\{\(\\zeta\)\}\(x,y\)\|=𝔼g\[W\(y,g\)𝟏\[W\(y,g\)\>M\]\]\\displaystyle=\\mathbb\{E\}\_\{g\}\[W\(y,g\)\\mathbf\{1\}\[W\(y,g\)\>M\]\]≤\(M\+σZ/β\)​δn≤\(Rmax\+σZ​\(L\+1\)\+3​β/2\)​δβ​n\\displaystyle\\leq\\frac\{\(M\+\\sigma\_\{Z\}/\\beta\)\\delta\}\{n\}\\leq\\frac\{\(R\_\{\\max\}\+\\sigma\_\{Z\}\(L\+1\)\+3\\beta/2\)\\delta\}\{\\beta n\}by the same computation as in \([21](https://arxiv.org/html/2608.26324#A3.E21)\) and usingM≤\(Rmax\+σZ​L\+3​β/2\)/βM\\leq\(R\_\{\\max\}\+\\sigma\_\{Z\}L\+3\\beta/2\)/\\betaon𝒢1\\mathcal\{G\}\_\{1\}\. The same bound applies to\|Zw¯\(ζ\)−Zw¯,M\(ζ\)\|\|Z\_\{\\bar\{w\}\}^\{\(\\zeta\)\}\-Z\_\{\\bar\{w\},M\}^\{\(\\zeta\)\}\|\. Applying Lemma[C\.3](https://arxiv.org/html/2608.26324#A3.Thmtheorem3)withη=\(Rmax\+σZ​\(L\+1\)\+3​β/2\)​δβ​n\\eta=\\frac\{\(R\_\{\\max\}\+\\sigma\_\{Z\}\(L\+1\)\+3\\beta/2\)\\delta\}\{\\beta n\}and sincemax⁡\(Zw¯\(ζ\),Zw¯,M\(ζ\)\)≥Zw¯\(ζ\)≥1/2\\max\(Z\_\{\\bar\{w\}\}^\{\(\\zeta\)\},Z\_\{\\bar\{w\},M\}^\{\(\\zeta\)\}\)\\geq Z\_\{\\bar\{w\}\}^\{\(\\zeta\)\}\\geq 1/2on𝒢1\\mathcal\{G\}\_\{1\}, we get

\|J⁡\(πw¯\(ζ\)\)−J⁡\(πw¯,M\(ζ\)\)\|≤2​Rmax​\(Rmax\+σZ​\(L\+1\)\+3/2\)​δ\(β​n\)⋅\(1/2\)=O⁡\(Rmax​\(Rmax\+σZ​L\)​δ/β​n\)\.\|J\(\\pi\_\{\\bar\{w\}\}^\{\(\\zeta\)\}\)\-J\(\\pi\_\{\\bar\{w\},M\}^\{\(\\zeta\)\}\)\|\\leq\\frac\{2R\_\{\\max\}\(R\_\{\\max\}\+\\sigma\_\{Z\}\(L\+1\)\+3/2\)\\delta\}\{\(\\beta n\)\\cdot\(1/2\)\}=O\(R\_\{\\max\}\(R\_\{\\max\}\+\\sigma\_\{Z\}L\)\\delta/\\beta n\)\.\(23\)
Assembling the conditional gap\.

Note that

J⁡\(πPrivITP\(ζ\)\)=𝔼⁡\[r∗​\(x,Y∗\)\]=𝔼⁡\[r∗​\(x,Y∗\)​𝟏𝒮\]\+𝔼⁡\[r∗​\(x,Y∗\)​𝟏𝒮c\]\.J\(\\pi\_\{\\mathrm\{PrivITP\}\}^\{\(\\zeta\)\}\)=\\mathbb\{E\}\[r^\{\*\}\(x,Y^\{\*\}\)\]=\\mathbb\{E\}\[r^\{\*\}\(x,Y^\{\*\}\)\\mathbf\{1\}\_\{\\mathcal\{S\}\}\]\+\\mathbb\{E\}\[r^\{\*\}\(x,Y^\{\*\}\)\\mathbf\{1\}\_\{\\mathcal\{S\}^\{c\}\}\]\.We know thatY∗∣𝒮∼πw¯,M\(ζ\)\(⋅\|x\)Y^\{\*\}\\mid\\mathcal\{S\}\\sim\\pi\_\{\\bar\{w\},M\}^\{\(\\zeta\)\}\(\\cdot\|x\), so𝔼⁡\[r∗​\(Y∗\)​𝟏𝒮\]=J⁡\(πw¯,M\(ζ\)\)​Pr⁡\[𝒮\]\\mathbb\{E\}\[r^\{\*\}\(Y^\{\*\}\)\\mathbf\{1\}\_\{\\mathcal\{S\}\}\]=J\(\\pi\_\{\\bar\{w\},M\}^\{\(\\zeta\)\}\)\\Pr\[\\mathcal\{S\}\]\. Therefore:

J⁡\(πw¯,M\(ζ\)\)−J⁡\(πPrivITP\(ζ\)\)\\displaystyle J\(\\pi\_\{\\bar\{w\},M\}^\{\(\\zeta\)\}\)\-J\(\\pi\_\{\\mathrm\{PrivITP\}\}^\{\(\\zeta\)\}\)=J⁡\(πw¯,M\(ζ\)\)−J⁡\(πw¯,M\(ζ\)\)​Pr⁡\[𝒮\]−𝔼⁡\[r∗​\(x,Y∗\)​𝟏𝒮c\]\\displaystyle=J\(\\pi\_\{\\bar\{w\},M\}^\{\(\\zeta\)\}\)\-J\(\\pi\_\{\\bar\{w\},M\}^\{\(\\zeta\)\}\)\\Pr\[\\mathcal\{S\}\]\-\\mathbb\{E\}\[r^\{\*\}\(x,Y^\{\*\}\)\\mathbf\{1\}\_\{\\mathcal\{S\}^\{c\}\}\]=J⁡\(πw¯,M\(ζ\)\)​Pr⁡\[𝒮c\]−𝔼⁡\[r∗​\(Y∗\)​𝟏𝒮c\]\.\\displaystyle=J\(\\pi\_\{\\bar\{w\},M\}^\{\(\\zeta\)\}\)\\Pr\[\\mathcal\{S\}^\{c\}\]\-\\mathbb\{E\}\[r^\{\*\}\(Y^\{\*\}\)\\mathbf\{1\}\_\{\\mathcal\{S\}^\{c\}\}\]\.Taking absolute values and usingr∗∈\[0,Rmax\]r^\{\*\}\\in\[0,R\_\{\\max\}\], we getJ⁡\(πw¯,M\(ζ\)\)∈\[0,Rmax\]J\(\\pi\_\{\\bar\{w\},M\}^\{\(\\zeta\)\}\)\\in\[0,R\_\{\\max\}\]and𝔼⁡\[r∗​\(Y∗\)​𝟏𝒮c\]∈\[0,Rmax​Pr⁡\[𝒮c\]\]\\mathbb\{E\}\[r^\{\*\}\(Y^\{\*\}\)\\mathbf\{1\}\_\{\\mathcal\{S\}^\{c\}\}\]\\in\[0,R\_\{\\max\}\\Pr\[\\mathcal\{S\}^\{c\}\]\]and thus

\|J⁡\(πw¯,M\(ζ\)\)−J⁡\(πPrivITP\(ζ\)\)\|≤2​Rmax​Pr⁡\[𝒮c∣ζ\]\.\|J\(\\pi\_\{\\bar\{w\},M\}^\{\(\\zeta\)\}\)\-J\(\\pi\_\{\\mathrm\{PrivITP\}\}^\{\(\\zeta\)\}\)\|\\leq 2R\_\{\\max\}\\Pr\[\\mathcal\{S\}^\{c\}\\mid\\zeta\]\.Combining with \([23](https://arxiv.org/html/2608.26324#A3.E23)\) via triangle inequality

\|J⁡\(πw¯\(ζ\)\)−J⁡\(πPrivITP\(ζ\)\)\|≤2​Rmax​Pr⁡\[𝒮c∣ζ\]\+O⁡\(Rmax​\(Rmax\+σZ​L\)​δ/β​n\)\.\|J\(\\pi\_\{\\bar\{w\}\}^\{\(\\zeta\)\}\)\-J\(\\pi\_\{\\mathrm\{PrivITP\}\}^\{\(\\zeta\)\}\)\|\\leq 2R\_\{\\max\}\\Pr\[\\mathcal\{S\}^\{c\}\\mid\\zeta\]\+O\(R\_\{\\max\}\(R\_\{\\max\}\+\\sigma\_\{Z\}L\)\\delta/\\beta n\)\.From \([20](https://arxiv.org/html/2608.26324#A3.E20)\) and \([22](https://arxiv.org/html/2608.26324#A3.Ex81)\), we havePr⁡\[𝒮c∣ζ\]≤δ\+exp⁡\(−β​n2​Rmax\+2​σZ​L\+3​β\+2​δ\)\\Pr\[\\mathcal\{S\}^\{c\}\\mid\\zeta\]\\leq\\delta\+\\exp\\left\(\-\\frac\{\\beta n\}\{2R\_\{\\max\}\+2\\sigma\_\{Z\}L\+3\\beta\}\+2\\delta\\right\)\. Settingδ≤1/n\\delta\\leq 1/\\sqrt\{n\}andnnsuch thatn/log⁡n≥\(2​Rmax\+2​σZ​3​log⁡n\+3​β\)/βn/\\log n\\geq\(2R\_\{\\max\}\+2\\sigma\_\{Z\}\\sqrt\{3\\log n\}\+3\\beta\)/\\beta, we getPr⁡\[𝒮c∣ζ\]≤O⁡\(1/n\)\\Pr\[\\mathcal\{S\}^\{c\}\\mid\\zeta\]\\leq O\(1/\\sqrt\{n\}\)\.

Therefore, on𝒢1\\mathcal\{G\}\_\{1\}, we have

\|J⁡\(πw¯\(ζ\)\)−J⁡\(πPrivITP\(ζ\)\)\|≤O⁡\(Rmax​\(Rmax\+σZ​L\)/β​n3/2\)\+O⁡\(Rmax/n\)=O⁡\(Rmax/n\)\.\|J\(\\pi\_\{\\bar\{w\}\}^\{\(\\zeta\)\}\)\-J\(\\pi\_\{\\mathrm\{PrivITP\}\}^\{\(\\zeta\)\}\)\|\\leq O\(R\_\{\\max\}\(R\_\{\\max\}\+\\sigma\_\{Z\}L\)/\\beta n^\{3/2\}\)\+O\(R\_\{\\max\}/\\sqrt\{n\}\)=O\(R\_\{\\max\}/\\sqrt\{n\}\)\.\(24\)
Averaging overζ\\zeta\.

Observe thatPr\[𝒢1c\]=Pr\[\|ζ\|\>β/2\]≤2exp\(−β2/\(8σX2\)\)\\Pr\[\\mathcal\{G\}\_\{1\}^\{c\}\]=\\Pr\[\|\\zeta\|\>\\beta/2\]\\leq 2\\exp\(\-\\beta^\{2\}/\(8\\sigma\_\{X\}^\{2\}\)\)and\|J⁡\(πw¯\(ζ\)\)−J⁡\(πPrivITP\(ζ\)\)\|≤Rmax\|J\(\\pi\_\{\\bar\{w\}\}^\{\(\\zeta\)\}\)\-J\(\\pi\_\{\\mathrm\{PrivITP\}\}^\{\(\\zeta\)\}\)\|\\leq R\_\{\\max\}for allζ\\zeta\. Combining this with \([19](https://arxiv.org/html/2608.26324#A3.E19)\) and \([24](https://arxiv.org/html/2608.26324#A3.E24)\), we get

\|J⁡\(πw¯\)−J⁡\(πPrivITP\)\|\\displaystyle\|J\(\\pi\_\{\\bar\{w\}\}\)\-J\(\\pi\_\{\\mathrm\{PrivITP\}\}\)\|≤𝔼ζ​\[\|J⁡\(πw¯\(ζ\)\)−J⁡\(πPrivITP\(ζ\)\)\|⋅𝟏𝒢1\]\+Rmax​Pr⁡\[𝒢1c\]\\displaystyle\\leq\\mathbb\{E\}\_\{\\zeta\}\\bigl\[\|J\(\\pi\_\{\\bar\{w\}\}^\{\(\\zeta\)\}\)\-J\(\\pi\_\{\\mathrm\{PrivITP\}\}^\{\(\\zeta\)\}\)\|\\cdot\\mathbf\{1\}\_\{\\mathcal\{G\}\_\{1\}\}\\bigr\]\+R\_\{\\max\}\\Pr\[\\mathcal\{G\}\_\{1\}^\{c\}\]≤O\(Rmax/n\)\+2Rmaxexp\(−β2/\(8σX2\)\)\.\\displaystyle\\leq O\(R\_\{\\max\}/\\sqrt\{n\}\)\+2R\_\{\\max\}\\exp\(\-\\beta^\{2\}/\(8\\sigma\_\{X\}^\{2\}\)\)\.\(25\)Combining \([16](https://arxiv.org/html/2608.26324#A3.E16)\), \([17](https://arxiv.org/html/2608.26324#A3.E17)\), \([18](https://arxiv.org/html/2608.26324#A3.E18)\) and \([25](https://arxiv.org/html/2608.26324#A3.Ex92)\), we obtain the regret

Reg⁡\(x\)≤Cπ∗​εRM2\+β​Cπ∗\+εRM2β\+O⁡\(Rmax​\(σX\+σZβ\+1n\+exp⁡\(−β28​σX2\)\)\)\.\\mathrm\{Reg\}\(x\)\\leq\\sqrt\{C^\{\\pi^\{\*\}\}\\varepsilon\_\{\\mathrm\{RM\}\}^\{2\}\}\+\\beta C^\{\\pi^\{\*\}\}\+\\frac\{\\varepsilon\_\{\\mathrm\{RM\}\}^\{2\}\}\{\\beta\}\+O\\left\(R\_\{\\max\}\\left\(\\frac\{\\sigma\_\{X\}\+\\sigma\_\{Z\}\}\{\\beta\}\+\\frac\{1\}\{\\sqrt\{n\}\}\+\\exp\\left\(\-\\frac\{\\beta^\{2\}\}\{8\\sigma\_\{X\}^\{2\}\}\\right\)\\right\)\\right\)\.Forβ≥2​σX\\beta\\geq 2\\sigma\_\{X\}, we can subsume the negative exponential term inσX/β\\sigma\_\{X\}/\\betaand obtain

Reg⁡\(x\)≤Cπ∗​εRM2\+β​Cπ∗\+εRM2β\+Rmax​\(σX\+σZ\)β\+Rmaxn\.\\displaystyle\\mathrm\{Reg\}\(x\)\\leq\\sqrt\{C^\{\\pi^\{\*\}\}\\varepsilon\_\{\\mathrm\{RM\}\}^\{2\}\}\+\\beta C^\{\\pi^\{\*\}\}\+\\frac\{\\varepsilon\_\{\\mathrm\{RM\}\}^\{2\}\}\{\\beta\}\+\\frac\{R\_\{\\max\}\(\\sigma\_\{X\}\+\\sigma\_\{Z\}\)\}\{\\beta\}\+\\frac\{R\_\{\\max\}\}\{\\sqrt\{n\}\}~\.Combining the requirement onnnfor Term \(A\) an \(B3\), the bounds holds forn=max⁡\{Ω⁡\(Rmaxβ​log⁡\(Rmaxβ​ϵRM\)\),Ω~​\(Rmax\+σZβ\)\}n=\\max\\left\\\{\\Omega\\\!\\left\(\\frac\{R\_\{\\max\}\}\{\\beta\}\\log\\\!\\left\(\\frac\{R\_\{\\max\}\}\{\\beta\\,\\epsilon\_\{\\mathrm\{RM\}\}\}\\right\)\\right\),\\widetilde\{\\Omega\}\\left\(\\frac\{R\_\{\\max\}\+\\sigma\_\{Z\}\}\{\\beta\}\\right\)\\right\\\}\. ∎

## Appendix DMulti\-Query Deployment: Proof of proposition[4\.5](https://arxiv.org/html/2608.26324#S4.Thmtheorem5)

Algorithm 3PrivITP with Filtered Self\-Reporting Composition0:Total privacy budget

\(εtotal,δ\)\(\\varepsilon\_\{\\mathrm\{total\}\},\\delta\); stream of prompts

x1,x2,…x\_\{1\},x\_\{2\},\\ldots; PrivITP hyperparameters

\(β,σX,σZ,L\)\(\\beta,\\sigma\_\{X\},\\sigma\_\{Z\},L\)
1:Set cumulative privacy spend

εspent←0\\varepsilon\_\{\\mathrm\{spent\}\}\\leftarrow 0
2:Compute per\-query worst\-case bound

εmax\\varepsilon\_\{\\max\}from[Theorem4\.1](https://arxiv.org/html/2608.26324#S4.Thmtheorem1)at

t=nt=n
3:for

τ=1,2,…\\tau=1,2,\\ldotsdo

4:if

εspent\+εmax≥εtotal\\varepsilon\_\{\\mathrm\{spent\}\}\+\\varepsilon\_\{\\max\}\\geq\\varepsilon\_\{\\mathrm\{total\}\}then

5:HALT

6:endif

7:Run PrivITP on

xτx\_\{\\tau\}\([Algorithm2](https://arxiv.org/html/2608.26324#alg2)\), obtaining response

y∗\(τ\)y^\{\*\(\\tau\)\}and halting time

tτt\_\{\\tau\}
8:Compute ex\-post privacy cost

ετ←ε1\+ε2post​\(tτ\)\\varepsilon\_\{\\tau\}\\leftarrow\\varepsilon\_\{1\}\+\\varepsilon\_\{2\}^\{\\mathrm\{post\}\}\(t\_\{\\tau\}\)from[Theorem4\.1](https://arxiv.org/html/2608.26324#S4.Thmtheorem1)

9:Update

εspent←εspent\+ετ\\varepsilon\_\{\\mathrm\{spent\}\}\\leftarrow\\varepsilon\_\{\\mathrm\{spent\}\}\+\\varepsilon\_\{\\tau\}
10:Release

y∗\(τ\)y^\{\*\(\\tau\)\}
11:endfor

###### Proof\.

Privacy follows directly from[Lebensold et al\. \[16, Theorem 11\]](https://arxiv.org/html/2608.26324#bib.bib11):[Algorithm3](https://arxiv.org/html/2608.26324#alg3)is an instance of their Filtered Composition framework withεmax,t=εmax\\varepsilon\_\{\\max,t\}=\\varepsilon\_\{\\max\}\(worst\-case PrivITP bound\) andεpost,t​\(ot\)=ε1\+ε2post​\(tτ\)\\varepsilon\_\{\\mathrm\{post\},t\}\(o\_\{t\}\)=\\varepsilon\_\{1\}\+\\varepsilon\_\{2\}^\{\\mathrm\{post\}\}\(t\_\{\\tau\}\)\(ex\-post PrivITP bound from[Theorem4\.1](https://arxiv.org/html/2608.26324#S4.Thmtheorem1)\)\. Since PrivITP is both\(εmax,δ\)\(\\varepsilon\_\{\\max\},\\delta\)\-pDP \(via its worst\-case bound\) andεpost,τ\\varepsilon\_\{\\mathrm\{post\},\\tau\}\-ex\-post\-DP \(via[Theorem4\.1](https://arxiv.org/html/2608.26324#S4.Thmtheorem1)\), the filter condition ensures the cumulative ex\-post cost never exceedsεtotal\\varepsilon\_\{\\mathrm\{total\}\}, and the pDP bound handles the tail risk in the final query\.

The bound is a direct consequence of the stopping rule: the algorithm halts whenεspent\+εmax≥εtotal\\varepsilon\_\{\\mathrm\{spent\}\}\+\\varepsilon\_\{\\max\}\\geq\\varepsilon\_\{\\mathrm\{total\}\}, so by Wald’s identity applied to the cumulative cost process,𝔼⁡\[T∗\]⋅𝔼⁡\[ετ\]≥εtotal−εmax\\mathbb\{E\}\[T^\{\*\}\]\\cdot\\mathbb\{E\}\[\\varepsilon\_\{\\tau\}\]\\geq\\varepsilon\_\{\\mathrm\{total\}\}\-\\varepsilon\_\{\\max\}, giving the stated lower bound \(ignoring the boundary term\)\. ∎

## Appendix EPrivBoN with Gaussian Noise

Gumbel noise in PrivBoN yields pureϵ\\epsilon\-DP and converges to a closed\-form tilted policy\. A natural question is whether Gaussian noise—standard in most DP analyses—offers comparable guarantees\. We show here that Gaussian noise has qualitatively different properties that make it a less clean match for inference\-time alignment, which motivates our choice of Gumbel noise\.

###### Lemma E\.1\(Privacy\)\.

Letr^D​\(x,⋅\)∈\[0,Rmax\]\\hat\{r\}\_\{D\}\(x,\\cdot\)\\in\[0,R\_\{\\max\}\]with sensitivityΔr\\Delta\_\{r\}\. Then,[Algorithm1](https://arxiv.org/html/2608.26324#alg1)withgi∼iid𝒩⁡\(0,σ2\)g\_\{i\}\\stackrel\{\{\\scriptstyle\\text\{iid\}\}\}\{\{\\sim\}\}\\mathcal\{N\}\(0,\\sigma^\{2\}\)satisfiespureε\\varepsilon\-DP with

ε=log⁡𝔼z∼𝒩⁡\(0,1\)​\[Φ​\(z−Rmax−2​Δrσ\)n−1\]𝔼z∼𝒩⁡\(0,1\)​\[Φ​\(z−Rmaxσ\)n−1\],\\varepsilon=\\log\\frac\{\\displaystyle\\mathbb\{E\}\_\{z\\sim\\mathcal\{N\}\(0,1\)\}\\\!\\left\[\\Phi\\\!\\left\(z\-\\frac\{R\_\{\\max\}\-2\\Delta\_\{r\}\}\{\\sigma\}\\right\)^\{n\-1\}\\right\]\}\{\\displaystyle\\mathbb\{E\}\_\{z\\sim\\mathcal\{N\}\(0,1\)\}\\\!\\left\[\\Phi\\\!\\left\(z\-\\frac\{R\_\{\\max\}\}\{\\sigma\}\\right\)^\{n\-1\}\\right\]\},\(26\)whereΦ\\Phidenotes the standard Gaussian CDF\.

###### Proof\.

PrivBon with Gaussian noise is an instance of Gaussian Report Noisy Max applied to thennreward scoresr^D​\(x,y1\),…,r^D​\(x,yn\)\\hat\{r\}\_\{D\}\(x,y\_\{1\}\),\\ldots,\\hat\{r\}\_\{D\}\(x,y\_\{n\}\), each bounded in\[0,Rmax\]\[0,R\_\{\\max\}\]with sensitivityΔr\\Delta\_\{r\}\. The result follows directly from[Lebensold et al\. \[16, Theorem 8\]](https://arxiv.org/html/2608.26324#bib.bib11), which establishes pureε\\varepsilon\-DP for Gaussian Report Noisy Max over bounded queries with the closed\-form expression in \([26](https://arxiv.org/html/2608.26324#A5.E26)\)\. The proof identifies the worst\-case reward configurations on adjacent datasetsD∼D′D\\sim D^\{\\prime\}via a monotonicity argument, then expresses the privacy loss as a ratio of Gaussian expectations over products of CDFs\. ∎

The bound is computable via numerical integration \(see[16](https://arxiv.org/html/2608.26324#bib.bib11), Section 3\.4\) and depends on the reward rangeRmaxR\_\{\\max\}, the sensitivityΔr\\Delta\_\{r\}, the noise scaleσ\\sigma, and the number of candidatesnn– but crucially does not require the approximate\-DP slackδ\\delta\. Unlike Gumbel noise, the privacy budgetϵ\\epsilondepends onnnthrough a numerical integral, though the growth is very slow in practice\.

###### Proposition E\.2\(Policy\)\.

PrivBoN with Gaussian noise induces the selection probabilitywi=𝔼Z​\[∏j≠iΦ⁡\(Z\+\(r^D​\(x,yi\)−r^D​\(x,yj\)\)/σ\)\]w\_\{i\}=\\mathbb\{E\}\_\{Z\}\[\\prod\_\{j\\neq i\}\\Phi\(Z\+\(\\hat\{r\}\_\{D\}\(x,y\_\{i\}\)\-\\hat\{r\}\_\{D\}\(x,y\_\{j\}\)\)/\\sigma\)\],i∈\[n\]i\\in\[n\], whereZ∼𝒩⁡\(0,1\)Z\\sim\\mathcal\{N\}\(0,1\)\.

###### Proof\.

Defineri:=r^D​\(x,yi\)r\_\{i\}:=\\hat\{r\}\_\{D\}\(x,y\_\{i\}\)for brevity\. The derivation follows the same symmetry argument as[Proposition3\.2](https://arxiv.org/html/2608.26324#S3.Thmtheorem2)\. The only difference is the selection probability\. Candidateiiwins ifri\+gi≥rj\+gjr\_\{i\}\+g\_\{i\}\\geq r\_\{j\}\+g\_\{j\}for allj≠ij\\neq i\. Conditioning ongi=σ⋅zg\_\{i\}=\\sigma\\cdot z, wherez∼𝒩⁡\(0,1\)z\\sim\\mathcal\{N\}\(0,1\), we get

Pr⁡\(i​wins∣gi=σ⋅z\)=∏j≠iPr⁡\(gj≤σ⋅z\+ri−rj\)=∏j≠iΦ⁡\(z\+ri−rjσ\)\.\\Pr\(i\\text\{ wins\}\\mid g\_\{i\}=\\sigma\\cdot z\)=\\prod\_\{j\\neq i\}\\Pr\(g\_\{j\}\\leq\\sigma\\cdot z\+r\_\{i\}\-r\_\{j\}\)=\\prod\_\{j\\neq i\}\\Phi\\\!\\left\(z\+\\frac\{r\_\{i\}\-r\_\{j\}\}\{\\sigma\}\\right\)\.Integrating overzz, we have

wi:=Pr⁡\(i​wins\)=∫−∞∞φ⁡\(z\)​∏j≠iΦ⁡\(z\+ri−rjσ\)​𝑑z=𝔼Z∼𝒩⁡\(0,1\)​\[∏j≠iΦ⁡\(Z\+ri−rjσ\)\]\.w\_\{i\}:=\\Pr\(i\\text\{ wins\}\)=\\int\_\{\-\\infty\}^\{\\infty\}\\varphi\(z\)\\prod\_\{j\\neq i\}\\Phi\\\!\\left\(z\+\\frac\{r\_\{i\}\-r\_\{j\}\}\{\\sigma\}\\right\)dz=\\mathbb\{E\}\_\{Z\\sim\\mathcal\{N\}\(0,1\)\}\\\!\\left\[\\prod\_\{j\\neq i\}\\Phi\\\!\\left\(Z\+\\frac\{r\_\{i\}\-r\_\{j\}\}\{\\sigma\}\\right\)\\right\]\.The rest \(symmetry reduction, tower property, marginal policy\) is identical to the Gumbel case withwiw\_\{i\}replacing the softmax weight\. ∎

This probit integral has no closed\-form simplification for generalnn\. Unlike the Gumbel case, PrivBON with Gaussian noise does not converge to a tilted policy asn→∞n\\to\\infty: Gaussian extreme value theory dominates, and the selection concentrates on the candidate with the highestr^D\\hat\{r\}\_\{D\}, recovering hard BoN in the limit rather than a smoothed distribution\.

## Appendix FDetails on Experiments

### F\.1Experimental Setup

Compute resources\.All experiments were run using 4 parallel 48GB GPU cards and one 140 GB GPU card\. The time to generate responses and score them depends on the size of the base and reward models – the larger the models, the longer the inference time\.

Datasets\.We evaluate on three benchmarks with verifiable ground\-truth correctness, assigningr⋆​\(x,y\)=1r^\{\\star\}\(x,y\)=1for correct answers and00otherwise\. GSM8K\[[5](https://arxiv.org/html/2608.26324#bib.bib29)\]is the standard11K\-prompt grade\-school math test split\. MMLU\[[11](https://arxiv.org/html/2608.26324#bib.bib31)\]covers∼100\\sim\\\!100college\-level multiple\-choice questions each in math and chemistry\. MATH\-500\[[18](https://arxiv.org/html/2608.26324#bib.bib33)\], a widely adopted, representative subset of 500 test problems from the original MATH dataset\[[12](https://arxiv.org/html/2608.26324#bib.bib32)\]\. We use zero\-shot Chain\-of\-Thought prompting\[[28](https://arxiv.org/html/2608.26324#bib.bib30)\]throughout\.

Reward models\.We use four reward models as the proxyr^𝒟\\hat\{r\}\_\{\\mathcal\{D\}\}: Oasst\-RM \(Pythia\-1\.4b\), Gemma\-RM \(Gemma\-2\-2b\), Llama\-RM \(Llama\-3\-3b\) and Armo\-RM \(Llama\-3\-8b\)\. The reference policyπref\\pi\_\{\\mathrm\{ref\}\}\(denoted interchangeablyπ0\\pi\_\{0\}\) is Gemma\-2\-2B\-Instruct and Phi\-3\-Mini\-Instruct\.

Sampling and evaluation\.For each prompt, we sample1010K responses at temperature11fromπref\\pi\_\{\\mathrm\{ref\}\}, then drawM=50M=50bootstrap replicates ofnnresponses and run each algorithm on every replicate\. Per\-prompt accuracy is the fraction of replicates yielding a correct answer; reported accuracy averages over prompts, with standard errors estimated across prompt distribution\.

### F\.2Ablation: Noise Scale for PrivBoN

The noise scaleσ\\sigmain PrivBoN controls both the privacy budget \(ε=2​Δr/σ\\varepsilon=2\\Delta\_\{r\}/\\sigma\) and the strength of KL\-regularization, with[Theorem3\.3](https://arxiv.org/html/2608.26324#S3.Thmtheorem3)predicting an optimalσ∗=εRM/Cπ∗\\sigma^\{\*\}=\\varepsilon\_\{\\mathrm\{RM\}\}/\\sqrt\{C^\{\\pi^\{\*\}\}\}balancing under\-regularization \(reward hacking\) and over\-regularization \(suppressing the reward signal\)\. SinceCπ∗C^\{\\pi^\{\*\}\}is not computable in practice, to selectσ\\sigmafor the experiments above, we sweepσ\\sigmaand report accuracy lift, and expected proxy reward in[Figure2](https://arxiv.org/html/2608.26324#A6.F2)on a held out set\. The resulting profile is single\-peaked: smallσ\\sigmaallows reward hacking \(accuracy drops as PrivBoN approaches BoN’s behavior\), while a largeσ\\sigmaover\-regularizes \(accuracy drops towardπref\\pi\_\{\\mathrm\{ref\}\}\)\. We use the empirically bestσ\\sigmafor the main results in[Table2](https://arxiv.org/html/2608.26324#A6.T2)\. The sameσ\\sigmais also taken as a total noise in PrivITP for a fair comparison\.

### F\.3Ablation: Regularization for ITP

The regularization parameterβ\\betain ITP and PrivITP plays a role analogous toσ\\sigmain PrivBoN, with[Theorem4\.3](https://arxiv.org/html/2608.26324#S4.Thmtheorem3)predicting an optimalβ∗\\beta^\{\*\}that balancesχ2\\chi^\{2\}\-bias against overoptimization and privacy noise\. Sweepingβ∈\{0\.0005,0\.001,0\.005,0\.01,0\.05,0\.1,0\.5\}\\beta\\in\\\{0\.0005,0\.001,0\.005,0\.01,0\.05,0\.1,0\.5\\\}, and reporting accuracy lift, and expected proxy reward in[Figure3](https://arxiv.org/html/2608.26324#A6.F3), we find the empirically bestβ\\betaon a held out set\. Crucially, we observe that PrivITP’s optimalβ\\betais essentially independent of the privacy budgetε\\varepsilon—validating Theorem[4\.3](https://arxiv.org/html/2608.26324#S4.Thmtheorem3)’s decoupling claim that regularization and privacy can be tuned separately\. We use the empirically bestβ\\betafor the main results in[Table2](https://arxiv.org/html/2608.26324#A6.T2)\.

### F\.4Algorithm comparison across reward models and datasets

We compare four algorithms \(BoN, PrivBoN, ITP, and PrivITP\) across four reward models \(Oasst, Gemma, Llama, Armo\) and three datasets \(GSM8K, MMLU, MATH\), fixing the base policy to Gemma\-2\-2b\-Instruct and Phi\-3\-Mini\-Instruct\. For each \(algorithm, RM, dataset\) configuration, we sweep the number of candidatesN∈\{2,4,8,16,32,64,128,256,512,1024,2048,4096\}N\\in\\\{2,4,8,16,32,64,128,256,512,1024,2048,4096\\\}\(interchangeably denoted bynn\)\. Private algorithms are calibrated to the empirical bestσ\\sigmaobtained for PrivBoN from the ablation study; non\-private ITP serves as the regret\-optimal skyline\. We report two quantities per configuration: \(a\) accuracy lift overπref\\pi\_\{\\mathrm\{ref\}\}, measuring*true\-reward*performance, and \(b\) expected proxy reward𝔼⁡\[r^𝒟\]\\mathbb\{E\}\[\\hat\{r\}\_\{\\mathcal\{D\}\}\]under each algorithm’s output distribution, measuring how aggressively each algorithm exploits the reward model\.[Figures4](https://arxiv.org/html/2608.26324#A6.F4),[5](https://arxiv.org/html/2608.26324#A6.F5)and[6](https://arxiv.org/html/2608.26324#A6.F6)present the results for the base policy Gemma\-2\-2b\-Instruct, one figure per dataset, each with a4×24\\times 2grid: rows index reward models, the left column shows accuracy lift vs\.NN, the right column shows expected proxy reward vs\.NN\. In a similar way,[Figures7](https://arxiv.org/html/2608.26324#A6.F7),[8](https://arxiv.org/html/2608.26324#A6.F8)and[9](https://arxiv.org/html/2608.26324#A6.F9)present the results for the base policy Phi\-3\-Mini\-Instruct\.[Figures10](https://arxiv.org/html/2608.26324#A6.F10),[11](https://arxiv.org/html/2608.26324#A6.F11)and[12](https://arxiv.org/html/2608.26324#A6.F12)compare % accuracy lift of ITP vs\. PrivITP for different values ofσ\\sigmaon GSM8K, MMLU and MATH datasets respectively under Gemma2\-2B\-Instruct base policy, showing privacy\-utility trade\-off\.[Table2](https://arxiv.org/html/2608.26324#A6.T2)summarizes the results atN=212N=2^\{12\}across all datasets and RMs for Gemma2\-2B\-Instruct base policy whereas[Table3](https://arxiv.org/html/2608.26324#A6.T3)summarizes the results atN=212N=2^\{12\}across all datasets and RMs for Llama\-3\.2\-3B\-Instruct base policy

Three patterns hold consistently \(except, in some cases, for the harder MATH dataset\)\.*First*, BoN’s accuracy lift exhibits the reward\-hacking signature: it rises withNNinitially, then*decreases*starts decreasing, while its expected proxy reward continues to climb monotonically\. The two curves diverge—a demonstration of Goodhart’s law—confirming that BoN exploits proxy errors at the cost of true reward\.*Second*, PrivBoN, ITP, and PrivITP are all scaling\-monotone: accuracy lift improves \(or plateaus\) withNNand proxy reward saturates rather than diverging\.*Third*, PrivITP dominates PrivBoN on every \(RM, dataset\) configuration where both provide positive lift, and on GSM8K it recovers between 60% and 95% of the non\-private ITP skyline; on MMLU and MATH, where the skyline itself is small or noisy, PrivITP closely tracks ITP within standard error\. The proxy\-reward panels make the mechanism visible: PrivITP’s expected proxy reward saturates at a level above PrivBoN’s, indicating that PrivITP’sχ2\\chi^\{2\}\-pessimism allows more aggressive exploitation of*informative*reward signals while still preventing overfitting to errors\. Similar to[Huang et al\. \[13\]](https://arxiv.org/html/2608.26324#bib.bib18), we also observe that ITP variants tend to have higher average performance than BoN variants, although in many instances this difference is not statistically significant\.

### F\.5FSRC composition

We supplement the main\-text composition experiment \([Figure1](https://arxiv.org/html/2608.26324#S5.F1)\(bottom right\)\) with sweeps across reward models using Gemma2\-2B\-Instruct base policy on GSM8K dataset withεtotal=50\\varepsilon\_\{\\mathrm\{total\}\}=50\. See[Figure13](https://arxiv.org/html/2608.26324#A6.F13)\. Three patterns hold\. \(i\) Absolute query counts increase withσ\\sigmafor both FSRC and standard composition, since larger noise lowers the per\-query privacy cost faster than it raises the expected halting time𝔼⁡\[t\]\\mathbb\{E\}\[t\]; both compositors benefit, but FSRC retains its advantage\. \(ii\) The FSRC answers∼3×\\sim 3\\timesmore queries, reflecting the gap between worst\-caseεmax\\varepsilon\_\{\\max\}and realized𝔼⁡\[ετ\]\\mathbb\{E\}\[\\varepsilon\_\{\\tau\}\]\. \(iii\) Empirical halting time admitstτ≪nt\_\{\\tau\}\\ll n, confirming faster rejection \(𝔼⁡\[tτ\]=O⁡\(1\)\\mathbb\{E\}\[t\_\{\\tau\}\]=O\(1\)\)\. These results confirm that the FSRC gain is structural – driven by the ex\-post bound’s halting\-time dependence\.

Table 2:Percentage lift in accuracy over base policyGemma\-2\-2B\-Instructatn=212n=2^\{12\}candidates\. Values are mean±\\pmstandard error over all prompts across the GSM8K, MMLU, and MATH test splits\. Same \(RM, dataset\) configuration uses the same noiseσ\\sigmafor private variants and the same regularizationβ\\betafor ITP variants\.Table 3:Percentage lift in accuracy over base policyLlama\-3\.2\-3B\-Instructatn=212n=2^\{12\}candidates\. Values are mean±\\pmstandard error over all prompts across the GSM8K, MMLU, and MATH test splits\. Same \(RM, dataset\) configuration uses the same noiseσ\\sigmafor private variants and the same regularizationβ\\betafor ITP variants\.\(a\)Oasst\-RM\(b\)Gemma\-RM\(c\)Llama\-RM\(d\)Armo\-RM
Figure 2:Ablation on noise levelσ\\sigmafor PrivBoN on GSM8K dataset with Gemma\-2\-2b\-Instruct as base model\(a\)Oasst\-RM\(b\)Gemma\-RM\(c\)Llama\-RM\(d\)Armo\-RM
Figure 3:Ablation on regularizationβ\\betafor ITP on GSM8K dataset with Gemma\-2\-2b\-Instruct as base modelFigure 4:Comparison of BoN, PrivBoN, ITP, and PrivITP in accuracy and estimated rewardr^\\hat\{r\}for GSM8K for four reward models and Gemma\-2\-2B\-Instructπref\\pi\_\{\\mathrm\{ref\}\}Figure 5:Comparison of BoN, PrivBoN, ITP, and PrivITP in accuracy and estimated rewardr^\\hat\{r\}for MMLU for four reward models and Gemma\-2\-2B\-Instructπref\\pi\_\{\\mathrm\{ref\}\}\(a\)Oasst\-RM\(b\)Gemma\-RM\(c\)Llama\-RM\(d\)Armo\-RM
Figure 6:Comparison of BoN, PrivBoN, ITP, and PrivITP in accuracy and estimated rewardr^\\hat\{r\}for MATH for four reward models and Gemma\-2\-2B\-Instructπref\\pi\_\{\\mathrm\{ref\}\}\(a\)Oasst\-RM\(b\)Gemma\-RM\(c\)Llama\-RM\(d\)Armo\-RM
Figure 7:Comparison of BoN, PrivBoN, ITP, and PrivITP in accuracy and estimated rewardr^\\hat\{r\}for GSM8K for four reward models and Phi\-3\-Mini\-Instructπref\\pi\_\{\\mathrm\{ref\}\}\(a\)Oasst\-RM\(b\)Gemma\-RM\(c\)Llama\-RM\(d\)Armo\-RM
Figure 8:Comparison of BoN, PrivBoN, ITP, and PrivITP in accuracy and estimated rewardr^\\hat\{r\}for MATH for four reward models and Phi\-3\-Mini\-Instructπref\\pi\_\{\\mathrm\{ref\}\}\(a\)Oasst\-RM\(b\)Gemma\-RM\(c\)Llama\-RM\(d\)Armo\-RM
Figure 9:Comparison of BoN, PrivBoN, ITP, and PrivITP in accuracy and estimated rewardr^\\hat\{r\}for MMLU for four reward models and Phi\-3\-Mini\-Instructπref\\pi\_\{\\mathrm\{ref\}\}\(a\)Oasst\-RM\(b\)Gemma\-RM\(c\)Llama\-RM\(d\)Armo\-RM
Figure 10:ITP vs PrivITP for differentσ\\sigmaon GSM8K dataset with Gemma\-2\-2b\-Instruct base policy\(a\)Oasst\-RM\(b\)Gemma\-RM\(c\)Llama\-RM\(d\)Armo\-RM
Figure 11:ITP vs PrivITP for differentσ\\sigmaon MMLU dataset with Gemma\-2\-2b\-Instruct base policy\(a\)Oasst\-RM\(b\)Gemma\-RM\(c\)Llama\-RM\(d\)Armo\-RM
Figure 12:ITP vs PrivITP for differentσ\\sigmaon MATH dataset with Gemma\-2\-2b\-Instruct base policy\(a\)Oasst\-RM\(b\)Gemma\-RM\(c\)Llama\-RM\(d\)Armo\-RM
Figure 13:Advantage of FSRC composition in PrivITP’s ex\-post privacy bound compared to the standard composition in ex\-ante bound for different reward models and Gemma\-2\-2b\-Instruct as base model

## Appendix GAdditional Experiments and Analysis

### G\.1Open\-Ended Evaluation \(AlpacaEval\-2\.0\)

We evaluate our method on the AlpacaEval\-2\.0 task\[[17](https://arxiv.org/html/2608.26324#bib.bib34)\]under the standard proxy/gold protocol\. In this protocol, a weaker reward model \(RM\) is used as the proxyr^\\hat\{r\}for selection, and a strong held\-out RM is used as the goldr⋆r^\{\\star\}for scoring\. Table[4](https://arxiv.org/html/2608.26324#A7.T4)reports the gold win\-rate \(%\) versus the base policy, showing the mean and standard error for Gemma\-2\-2B\-Instruct across three proxy RMs \(Gemma, Llama, and Armo\)\. We utilize Prometheus\-7B\-v2\.0\[[15](https://arxiv.org/html/2608.26324#bib.bib35)\]as the goldr⋆r^\{\\star\}and test acrossn∈\{64,512,2048,4096\}n\\in\\\{64,512,2048,4096\\\}\.

Table 4:Gold win\-rate \(%\) vs\. the base policy \(Gemma\-2\-2B\-Instruct\) on AlpacaEval\-2\.0\. We use Prometheus\-7B\-v2\.0 as the gold judger⋆r^\{\\star\}and evaluate three different proxy reward models\.Observations:First, BoN does not exhibit reward hacking within the tested range, as the gold win\-rate remains flat\-to\-rising asnnincreases \(e\.g\., Llama increases from 92\.32 to 93\.16\) rather than peaking and declining\. This behavior is expected because AlpacaEval win\-rates saturate near 90%\+, and the proxy RMs track the gold judge closely enough thatn≤4096n\\leq 4096does not produce the proxy–gold divergence that drives hacking\. Consequently, the private variants match BoN’s utility to within standard error at every\(n,RM\)\(n,\\text\{RM\}\)configuration while adding the privacy guarantee that BoN lacks\. The private–non\-private gaps are approximately 2–3 points and overlap within one standard error, demonstrating that open\-ended generation privacy is obtained at no meaningful utility cost\.

### G\.2Wall\-Clock Overhead and Compute Cost

The actual computational cost for PrivITP is well below a naive2×2\\timesoverhead because Phase 2 generation is lazy\. Rejection sampling returns at the first accepted candidate at indextt, meaning candidates only need to be generated on demand\. Therefore, Phase 2 costs𝔼⁡\[t\]\\mathbb\{E\}\[t\]generations rather thannn, and experiments show that𝔼⁡\[t\]=O⁡\(1\)\\mathbb\{E\}\[t\]=O\(1\)for informative RMs\. The net generation cost is approximatelyn\+𝔼⁡\[t\]n\+\\mathbb\{E\}\[t\]\. Table[5](https://arxiv.org/html/2608.26324#A7.T5)reports the wall\-clock time \(seconds per query\) of PrivITP compared to PrivBoN atn=256n=256on the GSM8K dataset using the Phi3\-mini\-instruct base model on a single H100 GPU\.

Table 5:Wall\-clock generation time \(seconds per query\) for PrivBoN and PrivITP atn=256n=256\. Evaluated on the GSM8K dataset using the Phi3\-mini\-instruct base model\.PrivITP’s overhead ranges from 6–14% across RMs, which is far below a2×2\\timesmultiplier\. The mechanism overhead itself is negligible in both approaches—PrivBoN drawsnnGumbel scalars, while PrivITP draws one scalar Gaussian plus per\-round noise, which cost microseconds compared to thennforward passes\. Therefore, the gap is dominated primarily by Phase 1’s scalar\-estimation pass\.

### G\.3Privacy Budgets and Sensitivity Analysis

In our practical implementation, we bound the sensitivityΔr=sup\|r^D−r^D′\|\\Delta\_\{r\}=\\sup\|\\hat\{r\}\_\{D\}\-\\hat\{r\}\_\{D^\{\\prime\}\}\|using the maximum reward rangeRmaxR\_\{\\max\}, since a single example cannot move a bounded\-output head beyond its fixed range\. This provides an assumption\-free bound when reward model training is outside of the deployer’s control\. Table[6](https://arxiv.org/html/2608.26324#A7.T6)reports the privacy budgets across different noise levels for GSM8K with Armo\-RM, evaluated atδ=10−2\\delta=10^\{\-2\}andn=16n=16\. We computeε=2​Δr/σ\\varepsilon=2\\Delta\_\{r\}/\\sigmafor PrivBoN\. For PrivITP, the total ex\-post cost isε1\+ε2post\\varepsilon\_\{1\}\+\\varepsilon\_\{2\}^\{\\mathrm\{post\}\}, where Phase 1 costsε1=Δr​2​ln⁡\(1\.25/δ\)/σX\\varepsilon\_\{1\}=\\Delta\_\{r\}\\sqrt\{2\\ln\(1\.25/\\delta\)\}/\\sigma\_\{X\}and Phase 2 costsε2post​\(𝔼⁡\[t\]\)\\varepsilon\_\{2\}^\{\\mathrm\{post\}\}\(\\mathbb\{E\}\[t\]\)calculated via one\-dimensional numerical integration at the mean halting time\.

Table 6:Privacy budgets \(ε\\varepsilon\) across varying noise levels \(σ\\sigma\) for Armo\-RM evaluated on the GSM8K dataset\. Budgets are computed atδ=10−2\\delta=10^\{\-2\}and a fallback cap ofn=16n=16\. PrivITP’s ex\-post cost \(ε1\+ε2post\\varepsilon\_\{1\}\+\\varepsilon\_\{2\}^\{\\mathrm\{post\}\}\) is evaluated at the mean halting time𝔼⁡\[t\]\\mathbb\{E\}\[t\]\.While PrivBoN spansε∈\[0\.78,7\.80\]\\varepsilon\\in\[0\.78,7\.80\], PrivITP’s worst\-case ex\-post total appears larger because it is evaluated at𝔼⁡\[t\]\\mathbb\{E\}\[t\]under conservative worst\-case query values\. However, its realized per\-query cost is lower, and FSRC composition exploits this to answer approximately3×3\\timesmore queries at a fixed total budget\. Furthermore, tightening toδ=10−5\\delta=10^\{\-5\}increasesε1\\varepsilon\_\{1\}by a factor of only≈1\.56\\approx 1\.56, andε2post\\varepsilon\_\{2\}^\{\\mathrm\{post\}\}grows at most logarithmically innnbecause the halting timettis governed by the per\-round acceptance probability where𝔼⁡\[t\]=O⁡\(1\)\\mathbb\{E\}\[t\]=O\(1\)\.