CS Paper Radar

PAC-Private Autoregressive Generation: Calibrating Noise to Ensemble Disagreement

Mina Mirzadehsarcheshmeh, Amir Keyvan Khandani

cs.LG cs.AI ·submitted 2026-09-04 19:16 UTC · v1
theory

Abstract

Language models adapted on private text are often served through APIs, so privacy leakage occurs through generated outputs rather than exposed weights. Private prediction protects these releases. Methods such as PMixED incur privacy cost at each release and increasingly rely on the public model over long horizons. PAC privacy instead calibrates noise to output variability across possible secrets, adding less noise when predictions are stable. To our knowledge, PAC-private prediction has not previously been extended from classification to autoregressive generation. We construct $m=128$ overlapping worlds from the private corpus, with each record appearing in exactly $m/2$ worlds, and train one adapter per world over a frozen public model. The realized world is the secret. At each token, the public model defines a candidate set, the worlds vote, and their posterior-weighted disagreement determines the PAC noise; unanimity requires no calibration noise. We prove $I(S;Y_{1:T}) \leq I(S;H_T) \leq bT$. Our contributions are extending PAC privacy to autoregressive generation, handling adaptive self-generated contexts, and introducing coupled decoding that preserves privacy accounting while avoiding greedy degeneration. On WikiText-103 with GPT-2-small, we retain 74% of the fine-tuning gain at a per-token budget of $2^{-32}$, while membership-inference success is bounded by 51.08% after $10^6$ tokens; posterior-entropy estimates of leakage are roughly 17% of the charged budget. Inference privacy is not content protection: even when membership advantage on a memorized canary is indistinguishable from zero, the canary is emitted at the same rate. Against PMixED under matched membership-inference bounds on the same data universe and test set, we retain 98% of non-private headroom from $10^2$ to $10^6$ tokens, versus at most 56%, with no crossover.

Closest papers

Nearest neighbours by meaning across the whole index.

Private Online Prediction from Experts with Small Losses

cs.LG stat.ML ·2026-10-21 ·Bo Li, Peng Ye
theory similarity 0.64
Abstract

We consider online prediction from experts, a fundamental problem in machine learning, under differential privacy constraints. Existing private algorithms achieve near-optimal regret $\tilde{O}(\sqrt{T})$, where $T$ is the time horizon. However, this bound becomes suboptimal when $L^\star$, the cumulative loss of the best expert, is significantly less than $T$. In this work, we present the first differentially private algorithm with regret $\tilde{O}(\sqrt{L^\star})$, offering a substantial improvement in the low-loss regime. Our regret bound matches the non-private lower bound up to poly-logarithmic factors for constant privacy parameters, demonstrating that privacy incurs only a small cost in this setting. Our result assumes that the input sequence is oblivious, i.e., it is fixed in advance and independent of the algorithm's outputs. We also prove that an $\tildeΩ(\sqrt{T})$ regret is inevitable for adaptively generated inputs, even when $L^\star = 0$.

0.17

Performative Privacy: When Differential Privacy Maximizes Utility

cs.LG cs.AIstat.ML ·2026-08-28 ·Uddalak Mukherjee, Edwige Cyffers, Yann Chevaleyre
published similarity 0.64
Abstract · Accepted at EuroTDP 2026

Privacy-preserving learning is often motivated by the idea that protecting users' data can preserve trust and thus participation, improving utility in the long term. However, this claim has not been formalized so far. In parallel, performative learning provides a framework for studying learning systems whose deployment affects the data they later observe. In this work, we bring these two perspectives together and introduce performative privacy, where data leakage reduces future participation. We study a simple model where agents repeatedly contribute data for mean estimation but may leave the system when their data is leaked. Privacy is implemented through differentially private mechanisms, creating a trade-off between estimation noise and future participation. We show, through a theoretical study of the dynamics and numerical experiments, that a finite privacy budget can outperform non-private estimation in the long term when the feedback loop between leakage and participation is sufficiently strong. This provides first evidence that differential privacy can be optimal not only as a protection mechanism, but also from the perspective of long-term utility.

0.28

Differentially Private Continual Release with Relative Error

cs.DS ·2026-08-20 ·Bo Li, Wei Wang, Peng Ye
theory similarity 0.64
Abstract

This work investigates several fundamental tasks, including $\mathsf{MaxSum}$, $\mathsf{MinSum}$, $\mathsf{MaxSelect}$, and $\mathsf{MinSelect}$, in the continual release model under differential privacy. Previous research has demonstrated that any algorithm for these tasks must admit a large purely additive error. We show that the error can be substantially reduced if a relative error term is allowed, provided that the input stream is generated non-adaptively. However, when input data records can be selected adaptively, we prove that a large error is inevitable for the task of selecting an attribute with a small cumulative sum, whereas small error bounds remain achievable for other tasks. This reveals a significant separation between non-adaptive and adaptive streams. We also complement our algorithms with nearly matching lower bounds.

0.16

Privacy Without Regret: Differentially Private Inference-Time Alignment

cs.LG ·2026-08-26 ·Ishi Jain, Nandini Bhattad, Sayak Ray Chowdhury
similarity 0.63
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.

0.19

Ask in the Crowd: Differentially Private LLM Inference via Dummy-Augmented Shuffling

cs.AI cs.CR ·2026-11-19 ·Zhihao Liu, Zixiong Guo, Shuo Shao, Yu He, Wenli Wang +3 more
similarity 0.63
Abstract

Large language models are increasingly deployed as LLM-as-a-Service (LLMaaS), where user queries are sent to remote LLMs for inference, raising severe privacy concerns about the exposure of sensitive user inputs. Differentially private inference mitigates these risks by injecting noise into input embeddings. However, existing methods struggle to balance privacy and utility, as stronger privacy protection often leads to substantial accuracy degradation in LLM inference. In this work, we propose DP-SPD, a differentially private LLM inference framework that protects user queries by hiding the real query among client-generated dummy queries. All queries are randomly shuffled before being sent to the server, preventing direct identification of the user's true intent. To improve inference efficiency, we exploit the shared-prefix structure among queries and reuse transformer key--value (KV) caches during decoding. We analyze the privacy guarantee of DP-SPD and evaluate its utility on classification and generation tasks, as well as its privacy protection under QIA, EIA, and GPT-based attacks. Experimental results show that our method achieves strong inference-time privacy protection and near-plaintext utility while improving inference efficiency through shared-prefix KV-cache reuse.

0.07

Propose-Filter-Release: Scaling Noise to Typical Sensitivity via Private Filtering

cs.LG ·2026-10-29 ·Moshe Shenfeld, Eliad Tsfadia, Katrina Ligett
similarity 0.63
Abstract

Differential privacy requires that algorithms be stable to the change of any record in their input, even to an extreme outlier. Private algorithms thus commonly introduce noise scaled to the worst-case possible influence of any single record. This work studies how to build differentially private algorithms that can effectively tailor their noise to the typical case rather than the worst case. We introduce the general \emph{propose-filter-release} (PFR) framework, which, by privately filtering its input, turns a mechanism that protects the addition or removal of a \emph{typical} record into one that is differentially private in the standard sense, on \emph{every} input. We show how to instantiate PFR with a novel filtering step to obtain a general meta-algorithm. Given only a concave friendliness score (which measures how typical a record is with respect to a dataset) and a release mechanism that is friendly-DP (that is, private conditioned on the changed record being typical of the remaining data), it guarantees differential privacy on sufficiently large datasets. The FriendlyCore [TCK+22] and Propose-Test-Release [DL09] algorithms can be viewed as instantiations of our general approach. We illustrate the generality of PFR by instantiating it for scalar statistics, principal subspace estimation with a dimension-independent sample size, the KL divergence of user histograms, the effective resistances in a resistor network, and treatment-rule selection.

0.18

Reward-Driven Learning under Prompt-Level Differential Privacy

cs.LG cs.CR ·2026-10-05 ·Jiachen Zhao, Antonia Januszewicz, Taeho Jung
similarity 0.63
Abstract

Reinforcement learning with verifiable rewards (RLVR) trains a language model on problems that may themselves be confidential, and the trained model can reveal which problems it saw. We study RLVR under prompt-level differential privacy: the released weights must be (ε,δ)-differentially private with respect to the presence of any one training problem. Taking the group of responses to one prompt as the privacy record, our method aggregates their gradients, clips the prompt's contribution once, adds Gaussian noise, and composes the privacy loss across updates, so the budget depends on neither the number of responses per prompt nor the clipping norm; to our knowledge this is the first differential privacy guarantee for RLVR training. We train Qwen2.5-1.5B-Instruct with LoRA at a per-run budget of ε=8 and compare, on the same prompts and at the same budget, a control that removes only the reward signal and two private supervised fine-tuning recipes. The reward signal improves accuracy over the control by 2.65 points on MATH and 3.24 on GSM8K, in every seed; the improvement survives a format-robust scorer, at 1.3 points on MATH, and is not explained by response length. At the same budget the private model outperforms both supervised recipes on MATH and GSM8K by 2.3 to 3.8 points, retains 85--90% of the gain of non-private GRPO on these tasks, and on MATH the noise of an eightfold tighter budget costs at most 1.2 points. The reward effect also carries to CommonsenseQA, an exploratory non-mathematical task. Verifier feedback thus remains a usable learning signal under prompt-level privacy.

0.20

Certification-Based Differentially Private Learning

cs.LG ·2026-09-30 ·Mihnea Ghitu, Matthew Wicker
similarity 0.63
Abstract

Differential privacy (DP) in machine learning is typically achieved by adding noise to model parameters (private learning) or to model outputs (private prediction). Recent work uses formal methods, namely abstract interpretation, to provide tighter privacy guarantees, but only for private prediction in classification settings. In this work, we investigate the use of formal methods as a general tool for tighter privacy analysis. First, we generalize the abstract gradient training (AGT) framework to private prediction in continuous, unbounded regression. Second, by reducing learning in parameterized models to a regression problem over the parameter space, we introduce Abstract Gradient Sampling (AGS), an algorithm that enables reachability-based analysis to provide guarantees for private learning. In both private prediction and private learning, we provide tightened privacy accounting for the AGT framework and a theoretical analysis demonstrating when our smooth sensitivity upper-bounds yield favourable privacy-utility trade-off. In practice, we validate that our regression bounds are tighter than global-sensitivity baselines on regression benchmarks, and, notably, yield the first finite privacy guarantees in settings where global prediction sensitivity is a priori unbounded. We also find that under matched conditions, our private learning algorithm can outperform standard private learners.

0.28