PaperlayerView exact revision on arXiv

Source-linked AI summary

Privacy Without Regret: Differentially Private Inference-Time Alignment

Ishi Jain, Nandini Bhattad, Sayak Ray Chowdhury

arXiv:2608.26324v1cs.LG

TL;DR

Best-of-N alignment can exploit proxy-reward errors while exposing sensitive preference data through deterministic selection. The paper adds calibrated noise through PrivBoN and PrivITP, showing privacy guarantees with regret at or near the information-theoretic skyline and strong empirical performance.

  • Problem

    Best-of-N suffers from reward hacking and lacks privacy protection for sensitive human preference data used to train its reward model.

  • Method

    The paper introduces PrivBoN with Gumbel-noised reward selection and PrivITP with χ2-regularized rejection sampling plus a two-phase Gaussian mechanism.

  • Results

    PrivBoN can match the information-theoretic skyline at zero additional alignment cost above a critical threshold, while PrivITP matches it up to noise inflation and performs at least as well as PrivBoN empirically.

  • Takeaways & Limitations

    Calibrated noise can jointly provide formal privacy and preserve inference-time alignment benefits, including scaling monotonicity and multi-query gains.

  • Takeaways & Limitations

    PrivITP’s bound assumes reward-model outputs lie in a bounded range [0, Rmax], and one PrivBoN threshold depends on unknown coverage.

Abstract

from arXiv · show

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.

1 Introduction

The paper addresses reward hacking and privacy leakage in inference-time Best-of-N alignment by adding calibrated noise before response selection. It introduces PrivBoN and PrivITP, establishing privacy guarantees, regret results, and empirical improvements over standard BoN.

  • Motivation: BoN increasingly selects responses whose proxy rewards overestimate true rewards as candidate count grows, degrading alignment and breaking scaling monotonicity.Its deterministic argmax can also expose training-data-attributable shifts in reward-model outputs through selected-response frequencies.
  • Motivation: Inference-time differential privacy protects selected responses with respect to the sensitive preference dataset, regardless of query budget or adversary side information.The paper targets privacy leakage from reward models trained on human preference data.
  • Contributions: PrivBoN adds i.i.d. Gumbel noise with scale σ = 2∆r/ε, simultaneously yielding ε-DP and KL-regularized alignment in the large-n limit.The same noise scale controls both privacy and KL regularization.
  • Contributions: Above a critical privacy threshold, PrivBoN’s privacy-mandated noise is regret-optimal and matches the information-theoretic skyline with zero additional alignment cost.The threshold depends on the unknown coverage coefficient Cπ∗.
  • Contributions: PrivITP combines χ2-regularized rejection sampling with a two-phase Gaussian mechanism, achieving ex-post approximate-DP with an n-independent privacy bound.Its regret matches the skyline up to noise inflation and separates alignment error from privacy cost.
  • Empirical validation: Across four reward models, two language models, and GSM8K, MMLU, and MATH, private methods eliminate reward hacking, preserve scaling benefits, and PrivITP matches or outperforms PrivBoN.The ex-post composition structure also provides multi-query deployment gains.
  • Contributions: PrivBoN and PrivITP are presented as the first inference-time alignment algorithms whose regret matches the information-theoretic skyline under formal differential privacy guarantees.

2 Preliminaries

The preliminaries define inference-time alignment around a frozen base policy, a proxy reward model, and an unknown true reward. They formalize regret, reward-model error, coverage, and differential privacy notions used to analyze the proposed mechanisms.

  • Inference-time alignment: The system samples responses from a full-support reference policy π0 and uses a dataset-trained reward model ˆrD to select a single response for prompt x.The proxy reward is intended to approximate an unknown true reward r∗.
  • Inference-time alignment: Inference-time regret measures the gap between the true-reward value of a comparator policy π∗ and the constructed policy ˆπ.Policy value is the expected true reward for a given prompt.
  • Regret and assumptions: Low regret requires assumptions on reward-model accuracy and base-policy coverage; reward-model error is defined as ε(x,y) = r∗(x,y) − ˆrD(x,y).The paper studies how algorithmic interventions can reduce regret as a function of this error.
  • Regret and assumptions: The χ2-coverage coefficient measures how well π0 covers a target policy, with larger Cπ∗ indicating a harder alignment target.Coverage supports inference-time performance gains when high-quality responses are sufficiently represented by the base policy.
  • Regret and assumptions: The regret skyline gives a lower bound that no inference-time alignment algorithm can universally beat under the stated reward-error and coverage setting.InferenceTimePessimism is identified as achieving this lower bound.
  • Differential privacy: Reward-model sensitivity ∆r is the maximum change in any reward score between adjacent training datasets differing in one individual’s data.This sensitivity determines the scale of privacy noise.
  • Differential privacy: ε-DP and (ε,δ)-DP bound output-probability changes across adjacent datasets, while εp-ex-post DP conditions the privacy cost on the realized output.Ex-post accounting can save budget on favorable outcomes for later queries.
  • Private selection: PrivBoN samples n candidates, adds independent Gumbel noise to each proxy reward, and returns the candidate with the highest noisy score.

3 PrivBoN: Private Best-of-N

PrivBoN adds calibrated Gumbel noise before Best-of-N selection, providing differential privacy while inducing KL-regularized alignment. Its privacy noise can match optimal regularization and prevent BoN’s reward-hacking degradation, while the analysis identifies finite-sample and modeling conditions.

  • Mechanism: PrivBoN perturbs each reward score with independent Gumbel noise before returning the candidate with the highest noisy reward.The noise scale determines both the privacy guarantee and the induced policy.
  • Privacy guarantee: σ = 2∆r/ε yields ε-DP for PrivBoN when the reward model has sensitivity ∆r.The guarantee follows from the Gumbel-max connection to the exponential mechanism.
  • Induced alignment: As n →∞, PrivBoN converges to the KL-regularized optimum π∞(y|x) ∝π0(y|x) exp(ˆrD(x, y)/σ), while σ →0 recovers standard BoN.The regularization strength and privacy budget are both controlled by σ.
  • Regret guarantee: For all ε ≥ε∗(x), PrivBoN’s regret matches the information-theoretic skyline because privacy noise is no larger than the regret-optimal noise.Under the stated Gaussian-error analysis, ε∗ has a closed form; under general MSE assumptions, the qualitative conclusion persists without that closed form.
  • Scaling: PrivBoN’s regret upper bound does not worsen with n beyond n0, unlike BoN’s reward-hacking regime, although finite-sample behavior can require very large n.For typical values Rmax = 5 and σ = 1, the asymptotic rate begins only around n ≳104.
  • Reward hacking: As n →∞, BoN’s win-rate approaches 1 and its hacking gap grows without bound, whereas PrivBoN saturates both quantities at finite limits.The softmax selection induced by Gumbel noise prevents unlimited exploitation of reward-model errors.

4 Private Inference Time Pessimism

PrivITP addresses PrivBoN’s unverifiable privacy-free threshold by separating reward-hacking mitigation from privacy through χ2-regularized rejection sampling and calibrated Gaussian noise. It provides ex-post privacy whose cost depends on realized halting time rather than candidate count, while retaining skyline-level regret up to noise inflation.

  • Method: PrivITP combines χ2-regularized rejection sampling with a two-phase Gaussian mechanism, decoupling regularization from privacy.Phase 1 privately releases a noisy normalization constant; Phase 2 perturbs rewards and applies rejection sampling.
  • Privacy guarantee: PrivITP satisfies ex-post (ε1 + εpost(t), δ)-DP, with privacy cost depending on realized halting time t rather than n.The bound is independent of the number of candidates and is computable through one-dimensional numerical integration.
  • Regret guarantee: PrivITP achieves the information-theoretic skyline up to a privacy-induced noise-inflation term while satisfying pure ex-post ε-DP.The regret analysis assumes bounded true rewards and finite comparator-policy coverage.
  • Regret guarantee: The regret bound is non-increasing in n beyond n0, ruling out the reward-hacking regime where adding candidates degrades performance.The regularization parameter β exhibits a bias-variance trade-off between under-exploiting rewards and overoptimizing proxy errors.
  • Technical analysis: PrivITP’s analysis combines a randomized-threshold reformulation, a smoothed-weight policy comparison lemma, and a regret-optimality proof.These components support the n-independent ex-post bound and skyline comparison up to the Rmaxσ term.
  • Multi-query deployment: FSRC composition can answer Θ(εmax/E[ετ]) times more queries than standard composition under favorable realized per-query privacy costs.The improvement follows from composing ex-post costs instead of charging the worst-case per-query cost.

5 Experiments

The experiments evaluate BoN, PrivBoN, ITP, and PrivITP across language models, reward models, and datasets. They show that private methods mitigate reward hacking while preserving scaling, with PrivITP generally matching or exceeding PrivBoN and FSRC improving multi-query deployment.

  • Experimental setup: Experiments use four reward models, two base language models, and GSM8K, MATH-500, and MMLU test splits.For each prompt, the study samples 10,000 responses and bootstraps 50 replicates for each algorithm.
  • Scaling behavior: BoN accuracy rises then falls with n while proxy reward rises monotonically, whereas PrivBoN and PrivITP accuracy increase monotonically.The pattern identifies BoN reward hacking and its mitigation by the private methods.
  • Scaling behavior: PrivITP matches or exceeds PrivBoN at the same noise level and approaches the non-private ITP skyline as noise decreases.The figure reports the privacy-utility trade-off through the relationship between noise and accuracy.
  • Generalization across reward models and datasets: At n = 212, PrivITP dominates PrivBoN on every reward-model and dataset configuration and recovers 84%–98% of the non-private ITP skyline on GSM8K.On MMLU and MATH, PrivITP closely tracks ITP within standard error.
  • Generalization across reward models and datasets: At n = 212, BoN remains competitive for stronger Llama and Armo reward models on GSM8K and MATH, while reward hacking is most pronounced for weaker Oasst and Gemma models.The reported comparison indicates delayed reward-hacking pressure for stronger reward models in those settings.
  • Multi-query deployment: FSRC answers approximately 3× more queries than basic composition under a total privacy budget of εtotal = 50.This experiment uses n = 16, β = 0.05, Gemma-RM, and 10 random seeds; empirical halting time is much smaller than n.

B.4 On the Gaussian-error assumption in Theorem 3.3

The Gaussian-error analysis yields a clean privacy-free threshold, while broader error assumptions preserve qualitative conclusions but alter the threshold’s form. Bounded rewards can tighten the finite-sample term when their range is sufficiently small relative to the Gaussian-error scale.

  • Gaussian-error analysis: Under the Gaussian-error assumption, the tilted-policy overoptimization term has a closed form proportional to σ^2_RM/σ.The supplied passage identifies this as the closed-form expectation under the tilted policy.
  • General error assumptions: Under a general mean-squared-error assumption, the overoptimization term depends on Cπ∞(x) εRM(x).Because Cπ∞ can scale as exp(Rmax/σ) in the worst case, the privacy-free threshold becomes weaker.
  • Finite-sample assumptions: For sub-Gaussian errors, the finite-sample analysis continues to hold up to constants.For bounded rewards, the tail step is trivial, but the reward range B replaces σr√log n in the effective reward range.
  • Finite-sample assumptions: When B ≪ σr√log n, bounded rewards tighten the finite-sample term; otherwise, they loosen it.The comparison concerns the effective reward-range contribution to the finite-sample bound.
  • Conclusion: The qualitative conclusions persist under general mean-squared error: a σ bias-variance trade-off, a threshold above which privacy is free, and regret decreasing with n.The clean threshold expression ε∗(x) = 2Δr… is specific to the Gaussian-error analysis.

B.5 Proof of Proposition 3.6 (Win-Rate Bound and Reward hacking)

The analysis compares hard BoN with PrivBoN, showing that randomized softmax selection sacrifices proxy-reward maximization while converging to a tilted policy whose reward-hacking gap is controlled by the noise scale.

  • Reward hacking: BoN’s deterministic argmax maximizes expected learned reward over all selection rules, making PrivBoN’s randomized softmax selection proxy-reward suboptimal.The proof establishes E[r(x,y)] under PrivBoN ≤ E[r(x,y)] under BoN.
  • Reward hacking: O(σ_r(x)√log n) bounds BoN’s maximum reward-model error over n candidates.The bound follows from standard Gaussian-maximum results under independent candidate sampling.
  • Win-rate bound: π_PrivBoN converges as n →∞ to the tilted policy π∞(y|x) ∝ π0(y|x)e^{r(x,y)/σ}.The limiting distribution is a reward-tilted version of the reference policy.
  • Reward hacking: σ²_r(x)/σ is the limiting reward-hacking gap for PrivBoN as n →∞.PrivBoN’s limiting gap is determined by the reward-error variance and Gumbel noise scale.

C.1 Proof of Theorem 4.1 (PrivITP Privacy)

The PrivITP privacy proof reformulates rejection sampling as randomized thresholding, bounds threshold sensitivity under adjacent datasets, and applies Gaussian mechanism privacy with ex-post cost determined by the realized halting time.

  • Privacy guarantee: PrivITP’s privacy guarantee is (ε²(t),δ)-DP ex-post, with privacy cost indexed by the realized halting time t.The proof combines the two phases using composition and obtains an n-independent ex-post bound.
  • Sensitivity: |λ*(D) − λ*(D′)| ≤ ∆r for adjacent datasets, so the learned threshold has global sensitivity at most the reward sensitivity.Monotonicity of F_D yields both upper and lower threshold-shift bounds.
  • Gaussian mechanism: Releasing λ̃ = λ*(D) + ζ with Gaussian noise yields (ε1,δ)-DP through the scalar Gaussian mechanism.The mechanism treats λ* as a scalar deterministic function with sensitivity at most ∆r.
  • Phase 2 reformulation: PrivITP’s Phase 2 rejection sampling is equivalent to accepting candidate i when g_i ≥ λ̃ + βM u_i − q_i.The reformulation uses fresh independent Gaussian and uniform noise, turning acceptance probabilities into randomized threshold checks.
  • Halting analysis: The Phase 2 halting probability factorizes over rounds because the noise is independent across trials.This factorization supports the ex-post privacy analysis based on the realized stopping time.

C.2 Proof of Theorem 4.3 (DP-ITP Regret)

The PrivITP regret proof compares noisy and finite-sample policies with the ideal χ²-regularized policy, decomposing the gap into skyline, phase-noise, and finite-sample corrections.

  • Policy comparison: PrivITP’s analysis uses a unified smoothed-ReLU framework to control deviations from Huang et al.’s ideal χ²-policy.A bounded pointwise weight difference is converted into a regret gap through a smoothed-weight comparison lemma.
  • Policy comparison: |J(π1) − J(π2)| ≤ 2R_maxη max(Z1,Z2) whenever the two nonnegative policy weights differ uniformly by at most η.The lemma bounds objective differences using the maximum normalization constant.
  • Phase 1 noise: Phase 1 Gaussian threshold noise perturbs the policy weights by at most |ζ|/β before normalization.The bound follows from ReLU’s 1-Lipschitz property and the normalization Z*=1.
  • Phase 2 and finite-sample corrections: Phase 2 Gaussian smoothing, truncation, and finite sampling create additional gaps between the target policy and the actual PrivITP output.The proof conditions on Phase 1 noise, analyzes rejection sampling, and bounds truncation and fallback events.

D Multi-Query Deployment: Proof of proposition 4.5

The deployment proof composes PrivITP’s worst-case and ex-post privacy guarantees across queries using a filtered self-reporting rule, while contrasting Gumbel and Gaussian noise behavior.

  • Multi-query composition: Filtered Self-Reporting Composition halts when cumulative ex-post privacy spend plus the worst-case per-query bound reaches the total budget.The algorithm computes each query’s realized cost from its halting time before updating cumulative spend.
  • Deployment bound: The expected number of deployed queries is lower-bounded through Wald’s identity applied to the cumulative privacy-cost process.The bound relates E[T*] and E[ε_τ] to ε_total − ε_max, ignoring the boundary term.
  • Comparison with privacy filters: FSRC can yield tighter deployment budgets than privacy filters because it uses actual ex-post costs rather than worst-case per-query costs.The paper states that this advantage is relevant when PrivITP’s realized costs are typically much smaller than its worst-case bound.
  • Gaussian-noise comparison: Gaussian-noise PrivBoN has privacy depending on n through a numerical integral, unlike the cleaner Gumbel formulation.Its privacy bound depends on reward range, sensitivity, noise scale, and candidate count, without approximate-DP slack δ.
  • Gaussian-noise comparison: Gaussian-noise PrivBoN does not converge to a tilted policy as n →∞; selection instead concentrates on the highest learned-reward candidate, recovering hard BoN.The probit-integral selection rule has no closed-form simplification for general n.

F.1 Experimental Setup

Experiments use verifiable math and knowledge benchmarks, multiple reward models and base policies, and bootstrap evaluation. Noise σ and regularization β are selected through held-out ablations to balance utility, reward hacking, and privacy.

  • Datasets: Experiments use GSM8K, MMLU, and MATH-500 with verifiable correctness rewards and zero-shot Chain-of-Thought prompting.GSM8K uses 1K prompts, MMLU covers math and chemistry questions, and MATH-500 contains 500 test problems.
  • Models: Four reward models and two instruction-tuned reference policies provide variation across proxy-model and base-model quality.The reward models are Oasst-RM, Gemma-RM, Llama-RM, and Armo-RM; reference policies are Gemma-2-2B-Instruct and Phi-3-Mini-Instruct.
  • Sampling and evaluation: For each prompt, the evaluation samples 10K responses and runs 50 bootstrap replicates of n-response selections.Responses are sampled at temperature 1, and accuracy is averaged over prompts with standard errors estimated across the prompt distribution.
  • Hyperparameter selection: PrivBoN’s noise scale σ jointly controls privacy ε = 2∆r/σ and KL-regularization strength.Theoretical tuning balances under-regularization, which permits reward hacking, against over-regularization, which suppresses the reward signal.
  • Hyperparameter selection: Held-out σ sweeps produce a single-peaked PrivBoN accuracy profile, while β sweeps identify PrivITP settings that are essentially independent of ε.The empirically best σ and β are used for the main comparisons, with the same σ as total noise in PrivITP for fairness.

F.4 Algorithm comparison across reward models and datasets

Across reward models and datasets, private and pessimistic methods avoid BoN’s reward-hacking pattern while retaining scaling benefits. PrivITP generally outperforms PrivBoN and approaches the non-private ITP skyline, while FSRC composition improves multi-query deployment.

  • Algorithm comparison: BoN accuracy initially rises with N then declines as expected proxy reward continues increasing, revealing reward hacking and proxy–true-reward divergence.This pattern is excepted in some cases on the harder MATH dataset.
  • Algorithm comparison: PrivBoN, ITP, and PrivITP are scaling-monotone: accuracy lift improves or plateaus with N while proxy reward saturates.This contrasts with BoN’s diverging accuracy and proxy-reward curves.
  • Algorithm comparison: PrivITP dominates PrivBoN whenever both methods provide positive lift and recovers 60%–95% of the non-private ITP skyline on GSM8K.On MMLU and MATH, where the skyline is small or noisy, PrivITP closely tracks ITP within standard error.
  • Algorithm comparison: PrivITP’s proxy reward saturates above PrivBoN’s, consistent with χ2-pessimism exploiting informative reward signals while preventing overfitting to errors.The proxy-reward panels make this mechanism visible across the algorithm comparisons.
  • Composition: At εtotal = 50, FSRC retains an advantage over standard composition as both answer counts increase with σ.The passage reports that FSRC answers approximately 3× more queries under the fixed total budget.

G.1 Open-Ended Evaluation (AlpacaEval-2.0)

The open-ended evaluation examines privacy–utility behavior through AlpacaEval and supporting ablations, comparisons, and efficiency analyses. It reports near-equivalent private and non-private utility in the tested AlpacaEval range, alongside favorable PrivITP deployment costs and composition behavior.

  • AlpacaEval-2.0: AlpacaEval-2.0 uses a weaker proxy reward model for selection and Prometheus-7B-v2.0 as a held-out gold judge.Gold win-rate is reported against Gemma-2-2B-Instruct across Gemma, Llama, and Armo proxy models and n ∈ {64, 512, 2048, 4096}.
  • AlpacaEval-2.0: Within the tested AlpacaEval range, BoN’s gold win-rate remains flat-to-rising, while private variants match BoN within standard error.For example, the Llama proxy increases from 92.32 to 93.16 as n grows.
  • AlpacaEval-2.0: The private–non-private gaps are approximately 2–3 points and overlap within one standard error in the AlpacaEval evaluation.The authors characterize privacy as being obtained at no meaningful utility cost in this setting.
  • Ablations: PrivBoN’s σ ablation displays a single-peaked accuracy profile: small σ permits reward hacking, whereas large σ over-regularizes toward the reference policy.The empirically best σ is used in the main results and as total noise for PrivITP.
  • Efficiency: PrivITP’s computational overhead ranges from 6–14% across reward models, with lazy Phase 2 generation making cost approximately n + E[t].The mechanism overhead is negligible relative to forward passes, and informative reward models show E[t] = O(1).
  • Composition: At fixed total privacy budget, FSRC composition answers approximately 3× more queries than standard composition.The ex-post cost grows at most logarithmically in n because the halting time is governed by per-round acceptance probability with E[t] = O(1).
Loading 2608.26324v1…