Privacy Without Regret: Differentially Private Inference-Time Alignment

Ishi Jain; Nandini Bhattad; Sayak Ray Chowdhury

cs.LGAug 26, 2026

Privacy Without Regret: Differentially Private Inference-Time Alignment

Authors: Ishi Jain, Nandini Bhattad, Sayak Ray Chowdhury

Organizations: Indian Institute of Technology Kanpur

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 $ε$ -differential privacy and implements KL-regularized alignment. Whenever the privacy budget exceeds a critical threshold $ε^*$ , 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. (2025). Because $ε^*$ depends on an unknown coverage coefficient, we introduce Private Inference-Time Pessimism (PrivITP), which combines $χ^2$ -regularized rejection sampling with a two-phase Gaussian mechanism. PrivITP achieves ex-post $(ε,δ)$ -DP with a privacy cost independent of the number of responses $n$ , 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 critical $n$ ), and PrivITP matches or outperforms PrivBoN at equivalent privacy levels, with the largest gains in the strong-privacy regime.

Figures & tables

Panel of Figure 1 — 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.

Dataset	Algorithm	Oasst-RM	Gemma-RM	Llama-RM	Armo-RM
GSM8K	BoN	$-5.18\pm 1.23$	$-1.87\pm 1.20$	$7.64\pm 0.82$	$6.47\pm 0.86$
	PrivBoN	$0.32\pm 0.91$	$1.15\pm 0.87$	$6.90\pm 0.76$	$5.78\pm 0.78$
	PrivITP	$0.81\pm 0.89$	$1.68\pm 0.87$	$7.46\pm 0.78$	$6.63\pm 0.78$
	ITP	$0.85\pm 0.90$	$2.00\pm 0.90$	$7.61\pm 0.79$	$6.81\pm 0.79$
MMLU	BoN	$2.54\pm 2.74$	$5.45\pm 2.94$	$-12.74\pm 2.92$	$8.40\pm 4.37$
	PrivBoN	$2.32\pm 2.22$	$4.22\pm 2.25$	$1.88\pm 2.24$	$3.37\pm 3.22$

Table 1: Percentage lift in accuracy over base policy Phi-3-Mini-Instruct at

n=2^{12}

candidates. Values are mean

\pm

standard error over all prompts across the GSM8K, MMLU, and MATH test splits. Same (RM, dataset) configuration uses the same noise

\sigma

for private variants and the same regularization

\beta

for ITP variants.

Appendix figures & tables17 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	Algorithm	Oasst-RM	Gemma-RM	Llama-RM	Armo-RM
GSM8K	BoN	$-6.46\pm 0.92$	$\phantom{-}0.75\pm 0.97$	$16.70\pm 1.12$	$3.43\pm 1.07$
	PrivBoN	$\phantom{-}5.94\pm 0.88$	$10.95\pm 0.90$	$21.46\pm 0.92$	$7.65\pm 0.87$
	PrivITP	$6.77\pm 0.90$	$11.81\pm 0.91$	$25.67\pm 0.93$	$14.16\pm 0.90$
	ITP	$7.36\pm 0.90$	$12.50\pm 0.92$	$29.69\pm 0.93$	$23.16\pm 0.93$
MMLU	BoN	$10.55\pm 2.21$	$11.09\pm 2.24$	$8.59\pm 2.18$	$23.18\pm 2.89$
	PrivBoN	$10.14\pm 1.93$	$9.04\pm 1.71$	$4.01\pm 1.63$	$1.12\pm 1.48$

Appendix

Table 2: Percentage lift in accuracy over base policy Gemma-2-2B-Instruct at

n=2^{12}

candidates. Values are mean

\pm

standard error over all prompts across the GSM8K, MMLU, and MATH test splits. Same (RM, dataset) configuration uses the same noise

\sigma

for private variants and the same regularization

\beta

for ITP variants.

Dataset	Algorithm	Oasst-RM	Gemma-RM	Llama-RM	Armo-RM
GSM8K	BoN	$-0.41\pm 1.06$	$4.68\pm 1.00$	$19.96\pm 0.75$	$16.94\pm 0.14$
	PrivBoN	$3.02\pm 0.84$	$5.04\pm 0.82$	$17.71\pm 0.69$	$11.96\pm 0.11$
	PrivITP	$4.07\pm 0.85$	$6.58\pm 0.84$	$19.63\pm 0.69$	$14.26\pm 0.11$
	ITP	$3.98\pm 0.87$	$6.17\pm 0.87$	$19.75\pm 0.71$	$16.31\pm 0.11$
MMLU	BoN	$7.66\pm 2.68$	$7.83\pm 2.88$	$-2.08\pm 2.71$	$13.80\pm 3.08$
	PrivBoN	$3.26\pm 1.94$	$6.70\pm 2.09$	$2.55\pm 1.97$	$13.78\pm 3.08$

Appendix

Table 3: Percentage lift in accuracy over base policy Llama-3.2-3B-Instruct at

n=2^{12}

candidates. Values are mean

\pm

standard error over all prompts across the GSM8K, MMLU, and MATH test splits. Same (RM, dataset) configuration uses the same noise

\sigma

for private variants and the same regularization

\beta

for ITP variants.

Panel of Figure 2 — Figure 2: Ablation on noise level $\sigma$ for PrivBoN on GSM8K dataset with Gemma-2-2b-Instruct as base model

Panel of Figure 3 — Figure 3: Ablation on regularization $\beta$ for ITP on GSM8K dataset with Gemma-2-2b-Instruct as base model

Panel of Figure 4 — Figure 4: Comparison of BoN, PrivBoN, ITP, and PrivITP in accuracy and estimated reward $\hat{r}$ for GSM8K for four reward models and Gemma-2-2B-Instruct $\pi_{\mathrm{ref}}$

Panel of Figure 5 — Figure 5: Comparison of BoN, PrivBoN, ITP, and PrivITP in accuracy and estimated reward $\hat{r}$ for MMLU for four reward models and Gemma-2-2B-Instruct $\pi_{\mathrm{ref}}$

Panel of Figure 6 — Figure 6: Comparison of BoN, PrivBoN, ITP, and PrivITP in accuracy and estimated reward $\hat{r}$ for MATH for four reward models and Gemma-2-2B-Instruct $\pi_{\mathrm{ref}}$

Panel of Figure 7 — Figure 7: Comparison of BoN, PrivBoN, ITP, and PrivITP in accuracy and estimated reward $\hat{r}$ for GSM8K for four reward models and Phi-3-Mini-Instruct $\pi_{\mathrm{ref}}$

Panel of Figure 8 — Figure 8: Comparison of BoN, PrivBoN, ITP, and PrivITP in accuracy and estimated reward $\hat{r}$ for MATH for four reward models and Phi-3-Mini-Instruct $\pi_{\mathrm{ref}}$

Panel of Figure 9 — Figure 9: Comparison of BoN, PrivBoN, ITP, and PrivITP in accuracy and estimated reward $\hat{r}$ for MMLU for four reward models and Phi-3-Mini-Instruct $\pi_{\mathrm{ref}}$

Panel of Figure 10 — Figure 10: ITP vs PrivITP for different $\sigma$ on GSM8K dataset with Gemma-2-2b-Instruct base policy

Panel of Figure 11 — Figure 11: ITP vs PrivITP for different $\sigma$ on MMLU dataset with Gemma-2-2b-Instruct base policy

Panel of Figure 12 — Figure 12: ITP vs PrivITP for different $\sigma$ on MATH dataset with Gemma-2-2b-Instruct base policy

Panel of Figure 13 — 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

RM	n	BoN	PrivBoN	ITP	PrivITP
Gemma	64	90.82 $\pm$ 1.91	88.35 $\pm$ 2.08	90.56 $\pm$ 1.99	87.89 $\pm$ 2.23
	512	92.19 $\pm$ 1.72	89.65 $\pm$ 1.97	90.30 $\pm$ 1.97	89.78 $\pm$ 1.95
	2048	92.06 $\pm$ 1.81	89.39 $\pm$ 1.98	90.82 $\pm$ 1.89	89.97 $\pm$ 2.07
	4096	92.38 $\pm$ 1.84	90.17 $\pm$ 2.02	90.36 $\pm$ 1.95	91.15 $\pm$ 1.84
Llama	64	92.32 $\pm$ 1.87	89.39 $\pm$ 1.90	92.32 $\pm$ 1.78	89.19 $\pm$ 2.03
	512	91.73 $\pm$ 1.82	89.32 $\pm$ 2.03	91.93 $\pm$ 1.66	90.62 $\pm$ 1.92

Appendix

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 judge

r^{\star}

and evaluate three different proxy reward models.

RM	Oasst	Gemma	Llama	Armo
PrivBoN	0.4145	0.9003	1.1804	0.4530
PrivITP	0.4704	0.9827	1.2838	0.4812
Overhead	+13.5%	+9.2%	+8.8%	+6.2%

Appendix

Table 5: Wall-clock generation time (seconds per query) for PrivBoN and PrivITP at

n=256

. Evaluated on the GSM8K dataset using the Phi3-mini-instruct base model.

$\sigma$	$\varepsilon$ (PrivBoN)	$\varepsilon_{1}$	$\varepsilon_{2}^{\mathrm{post}}$	$\varepsilon_{1}+\varepsilon_{2}^{\mathrm{post}}$ (PrivITP)
0.10	7.80	24.25	23.25	47.50
0.25	3.12	9.70	8.49	18.19
0.50	1.56	4.85	3.48	8.33
0.75	1.04	3.23	2.22	5.45
1.00	0.78	2.42	1.43	3.85

Appendix

Table 6: Privacy budgets (

\varepsilon

) across varying noise levels (

\sigma

) for Armo-RM evaluated on the GSM8K dataset. Budgets are computed at

\delta=10^{-2}

and a fallback cap of

n=16

. PrivITP’s ex-post cost (

\varepsilon_{1}+\varepsilon_{2}^{\mathrm{post}}

) is evaluated at the mean halting time

\mathbb{E}[t]

Inference-Time Language Model Alignment

Inference-time language model alignment steers or selects outputs during generation to better meet safety, preference, and task goals without retraining.

See all 75 papers

Revisiting the (Sub)Optimality of Best-of-N for Inference-Time Alignment
Mar 5, 2026Ved Sriraman, Adam BlockBest-of-N Sampling Inference-Time Language Model Alignment
Department of Computer Science, Columbia University · Department of Electrical Engineering, Columbia University
Best-of-Tails: Bridging Optimism and Pessimism in Inference-Time Alignment
Mar 6, 2026Hsiang Hsu, Eric Lei, Chun-Fu ChenReward Over-Optimization Inference-Time Language Model Alignment
JPMorganChase Global Technology Applied Research
ExpBoN: Exponential-Noise Best-of- $n$ for Efficient Test-Time LLM Alignment
Sep 18, 2026Yanxiao Liu, Sicheng Wan, Deniz GündüzBest-of-N Sampling Inference-Time Language Model Alignment
Imperial College London · University of Washington

Mar 5, 2026J/K move · Enter open · S save

Revisiting the (Sub)Optimality of Best-of-N for Inference-Time Alignment

Ved Sriraman, Adam Block

Department of Computer Science, Columbia University · Department of Electrical Engineering, Columbia University

Best-of-N Sampling Inference-Time Language Model Alignment Reward Hacking

Open paper AskPDF arXiv

Best-of-N (BoN) sampling is a widely used inference-time alignment method for language models, whereby N candidate responses are sampled from a reference model and the one with the highest predicted reward according to a learned reward model is selected. Despite its widespread practical use, recent theoretical work has suggested that it is statistically suboptimal and vulnerable to reward hacking, the process by which models exploit weaknesses in the learned reward model to achieve high estimated reward without genuinely improving performance. We revisit this question under assumptions that more closely reflect practice than that of prior work. In particular, in contradistinction to earlier analyses that focused on expected true reward, which may not be meaningful in many practical settings, we investigate how inference-time alignment affects the win-rate, a pairwise comparison-based metric more closely aligned with how reward models are trained and evaluated in practice. We demonstrate that, under minimal conditions on the quality of the reference model and learned reward model, properly tuned BoN is both computationally and statistically optimal in achieving high win-rate, partially explaining its widespread practical success. Because BoN remains susceptible to reward-hacking in this setting, we propose a simple and practical variant that provably eliminates reward-hacking while maintaining optimal statistical performance. Finally, we show that prior approaches are provably suboptimal when considering win-rate, highlighting the importance of choosing appropriate objectives when analyzing inference-time alignment methods.

Abstract

Inference-Time Language Model Alignment

Explore similar work

Revisiting the (Sub)Optimality of Best-of-N for Inference-Time Alignment

Best-of-Tails: Bridging Optimism and Pessimism in Inference-Time Alignment

ExpBoN: Exponential-Noise Best-of-nnn for Efficient Test-Time LLM Alignment

ExpBoN: Exponential-Noise Best-of- $n$ for Efficient Test-Time LLM Alignment