Clustering and Median Aggregation Improve Differentially Private Inference

• URL: http://arxiv.org/abs/2506.04566v1
• Date: Thu, 05 Jun 2025 02:34:50 GMT
• Title: Clustering and Median Aggregation Improve Differentially Private Inference
• Authors: Kareem Amin, Salman Avestimehr, Sara Babakniya, Alex Bie, Weiwei Kong, Natalia Ponomareva, Umar Syed,
• Abstract summary: Differentially private (DP) language model inference is an approach for generating private synthetic text.<n>We show that uniform sampling degrades the quality of privately generated text.<n>We introduce a new algorithm that aggregates next token statistics by privately computing medians instead of averages.
• Score: 19.7873954143387
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Differentially private (DP) language model inference is an approach for generating private synthetic text. A sensitive input example is used to prompt an off-the-shelf large language model (LLM) to produce a similar example. Multiple examples can be aggregated together to formally satisfy the DP guarantee. Prior work creates inference batches by sampling sensitive inputs uniformly at random. We show that uniform sampling degrades the quality of privately generated text, especially when the sensitive examples concern heterogeneous topics. We remedy this problem by clustering the input data before selecting inference batches. Next, we observe that clustering also leads to more similar next-token predictions across inferences. We use this insight to introduce a new algorithm that aggregates next token statistics by privately computing medians instead of averages. This approach leverages the fact that the median has decreased local sensitivity when next token predictions are similar, allowing us to state a data-dependent and ex-post DP guarantee about the privacy properties of this algorithm. Finally, we demonstrate improvements in terms of representativeness metrics (e.g., MAUVE) as well as downstream task performance. We show that our method produces high-quality synthetic data at significantly lower privacy cost than a previous state-of-the-art method.

Related papers

• Benchmarking Fraud Detectors on Private Graph Data [70.4654745317714]
  Currently, many types of fraud are managed in part by automated detection algorithms that operate over graphs.<n>We consider the scenario where a data holder wishes to outsource development of fraud detectors to third parties.<n>Third parties submit their fraud detectors to the data holder, who evaluates these algorithms on a private dataset and then publicly communicates the results.<n>We propose a realistic privacy attack on this system that allows an adversary to de-anonymize individuals' data based only on the evaluation results.
  arXiv  Detail & Related papers  (2025-07-30T03:20:15Z)
• An Enhanced Model-based Approach for Short Text Clustering [58.60681789677676]
  Short text clustering has become increasingly important with the popularity of social media like Twitter, Google+, and Facebook.<n>Existing methods can be broadly categorized into two paradigms: topic model-based approaches and deep representation learning-based approaches.<n>We propose a collapsed Gibbs Sampling algorithm for the Dirichlet Multinomial Mixture model (GSDMM), which effectively handles the sparsity and high dimensionality of short texts.<n>Based on several aspects of GSDMM that warrant further refinement, we propose an improved approach, GSDMM+, designed to further optimize its performance.
  arXiv  Detail & Related papers  (2025-07-18T10:07:42Z)
• Differentially Private Random Feature Model [52.468511541184895]
  We produce a differentially private random feature model for privacy-preserving kernel machines.<n>We show that our method preserves privacy and derive a generalization error bound for the method.
  arXiv  Detail & Related papers  (2024-12-06T05:31:08Z)
• Private prediction for large-scale synthetic text generation [28.488459921169905]
  We present an approach for generating differentially private synthetic text using large language models (LLMs) In the private prediction framework, we only require the output synthetic data to satisfy differential privacy guarantees.
  arXiv  Detail & Related papers  (2024-07-16T18:28:40Z)
• Stratified Prediction-Powered Inference for Hybrid Language Model Evaluation [62.2436697657307]
  Prediction-powered inference (PPI) is a method that improves statistical estimates based on limited human-labeled data.<n>We propose a method called Stratified Prediction-Powered Inference (StratPPI)<n>We show that the basic PPI estimates can be considerably improved by employing simple data stratification strategies.
  arXiv  Detail & Related papers  (2024-06-06T17:37:39Z)
• Benchmarking Private Population Data Release Mechanisms: Synthetic Data vs. TopDown [50.40020716418472]
  This study conducts a comparison between the TopDown algorithm and private synthetic data generation to determine how accuracy is affected by query complexity. Our results show that for in-distribution queries, the TopDown algorithm achieves significantly better privacy-fidelity tradeoffs than any of the synthetic data methods we evaluated.
  arXiv  Detail & Related papers  (2024-01-31T17:38:34Z)
• Personalized Privacy Amplification via Importance Sampling [3.0636509793595548]
  In this paper, we examine the privacy properties of importance sampling, focusing on an individualized privacy analysis.<n>We find that, in importance sampling, privacy is well aligned with utility but at odds with sample size.<n>We propose two approaches for constructing sampling distributions: one that optimize the privacy-efficiency trade-off; and one based on a utility guarantee in the form of coresets.
  arXiv  Detail & Related papers  (2023-07-05T17:09:10Z)
• Conformal Language Modeling [61.94417935386489]
  We propose a novel approach to conformal prediction for generative language models (LMs) Standard conformal prediction produces prediction sets with rigorous, statistical guarantees. We demonstrate the promise of our approach on multiple tasks in open-domain question answering, text summarization, and radiology report generation.
  arXiv  Detail & Related papers  (2023-06-16T21:55:08Z)
• Dynamic Decision Boundary for One-class Classifiers applied to non-uniformly Sampled Data [0.9569316316728905]
  A typical issue in Pattern Recognition is the non-uniformly sampled data. In this paper, we propose a one-class classifier based on the minimum spanning tree with a dynamic decision boundary.
  arXiv  Detail & Related papers  (2020-04-05T18:29:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.