# Clustering and Median Aggregation Improve Differentially Private Inference

arXiv: https://arxiv.org/abs/2506.04566 · HTML: https://mlsanity.com/paper/2506.04566/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 42 references that are in the map.
- First posted on arXiv 5 Jun 2025.

## Builds on (most cited first, 30 of 34)

- [Character-level Convolutional Networks for Text Classification](https://mlsanity.com/paper/1509.01626/) (2015)
- [MAUVE: Measuring the Gap Between Neural Text and Human Text using Divergence Frontiers](https://mlsanity.com/paper/2102.01454/) (2021)
- [Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data](https://mlsanity.com/paper/1610.05755/) (2016)
- [Scalable Private Learning with PATE](https://mlsanity.com/paper/1802.08908/) (2018)
- [Synthetic Text Generation with Differential Privacy: A Simple and Practical Recipe](https://mlsanity.com/paper/2210.14348/) (2022)
- [Privacy-Preserving In-Context Learning with Differentially Private Few-Shot Generation](https://mlsanity.com/paper/2309.11765/) (2023)
- [Flocks of Stochastic Parrots: Differentially Private Prompt Learning for Large Language Models](https://mlsanity.com/paper/2305.15594/) (2023)
- [Gecko: Versatile Text Embeddings Distilled from Large Language Models](https://mlsanity.com/paper/2403.20327/) (2024)
- [Differentially Private Synthetic Data via Foundation Model APIs 2: Text](https://mlsanity.com/paper/2403.01749/) (2024)
- [Differentially Private Language Models for Secure Data Sharing](https://mlsanity.com/paper/2210.13918/) (2022)
- [Differentially Private Synthetic Data via Foundation Model APIs 1: Images](https://mlsanity.com/paper/2305.15560/) (2023)
- [Harnessing large-language models to generate private synthetic text](https://mlsanity.com/paper/2306.01684/) (2023)
- [DP-OPT: Make Large Language Model Your Privacy-Preserving Prompt Engineer](https://mlsanity.com/paper/2312.03724/) (2023)
- [Privacy-Preserving In-Context Learning for Large Language Models](https://mlsanity.com/paper/2305.01639/) (2023)
- [Privacy-preserving Prediction](https://mlsanity.com/paper/1803.10266/) (2018)
- [Privacy-Preserving Instructions for Aligning Large Language Models](https://mlsanity.com/paper/2402.13659/) (2024)
- [Differentially Private Decoding in Large Language Models](https://mlsanity.com/paper/2205.13621/) (2022)
- [Submix: Practical Private Prediction for Large-Scale Language Models](https://mlsanity.com/paper/2201.00971/) (2022)
- [Differentially Private k-Means Clustering](https://mlsanity.com/paper/1504.05998/) (2015)
- [Private prediction for large-scale synthetic text generation](https://mlsanity.com/paper/2407.12108/) (2024)
- [Differentially Private Next-Token Prediction of Large Language Models](https://mlsanity.com/paper/2403.15638/) (2024)
- [Locating a Small Cluster Privately](https://mlsanity.com/paper/1604.05590/) (2016)
- [Accuracy First: Selecting a Differential Privacy Level for Accuracy-Constrained ERM](https://mlsanity.com/paper/1705.10829/) (2017)
- [Prompt Public Large Language Models to Synthesize Data for Private On-device Applications](https://mlsanity.com/paper/2404.04360/) (2024)
- [Differentially Private Tabular Data Synthesis using Large Language Models](https://mlsanity.com/paper/2406.01457/) (2024)
- [Synthesizing Privacy-Preserving Text Data via Finetuning without Finetuning Billion-Scale LLMs](https://mlsanity.com/paper/2503.12347/) (2025)
- [Differentially Private Synthetic Data via APIs 3: Using Simulators Instead of Foundation Model](https://mlsanity.com/paper/2502.05505/) (2025)
- [KnowledgeSG: Privacy-Preserving Synthetic Text Generation with Knowledge Distillation from Server](https://mlsanity.com/paper/2410.05725/) (2024)
- [Scalable Differentially Private Clustering via Hierarchically Separated Trees](https://mlsanity.com/paper/2206.08646/) (2022)
- [Synthetic Query Generation for Privacy-Preserving Deep Retrieval Systems using Differentially Private Language Models](https://mlsanity.com/paper/2305.05973/) (2023)

## Built on by (most cited first, 5 of 5)

- [InvisibleInk: High-Utility and Low-Cost Text Generation with Differential Privacy](https://mlsanity.com/paper/2507.02974/) (2025)
- [Differentially Private Synthetic Text Generation for Retrieval-Augmented Generation (RAG)](https://mlsanity.com/paper/2510.06719/) (2025)
- [Private-RAG: Answering Multiple Queries with LLMs while Keeping Your Data Private](https://mlsanity.com/paper/2511.07637/) (2025)
- [EPSVec: Efficient and Private Synthetic Data Generation via Dataset Vectors](https://mlsanity.com/paper/2602.21218/) (2026)
- [Private Training & Data Generation by Clustering Embeddings](https://mlsanity.com/paper/2506.16661/) (2025)

## Abstract (arXiv)

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.