# Differentially Private In-Context Learning with Nearest Neighbor Search

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 48 references that are in the map.
- First posted on arXiv 6 Nov 2025.

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [SQuAD: 100,000+ Questions for Machine Comprehension of Text](https://mlsanity.com/paper/1606.05250/) (2016)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Character-level Convolutional Networks for Text Classification](https://mlsanity.com/paper/1509.01626/) (2015)
- [HuggingFace's Transformers: State-of-the-art Natural Language Processing](https://mlsanity.com/paper/1910.03771/) (2019)
- [What Makes Good In-Context Examples for GPT-3?](https://mlsanity.com/paper/2101.06804/) (2021)
- [Fantastically Ordered Prompts and Where to Find Them: Overcoming Few-Shot Prompt Order Sensitivity](https://mlsanity.com/paper/2104.08786/) (2021)
- [How Can We Know What Language Models Know?](https://mlsanity.com/paper/1911.12543/) (2019)
- [The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks](https://mlsanity.com/paper/1802.08232/) (2018)
- [Quantifying Memorization Across Neural Language Models](https://mlsanity.com/paper/2202.07646/) (2022)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Large Language Models Can Be Strong Differentially Private Learners](https://mlsanity.com/paper/2110.05679/) (2021)
- [Differentially Private Fine-tuning of Language Models](https://mlsanity.com/paper/2110.06500/) (2021)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Scalable Private Learning with PATE](https://mlsanity.com/paper/1802.08908/) (2018)
- [Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising](https://mlsanity.com/paper/1805.06530/) (2018)
- [Commonsense Knowledge Mining from Pretrained Models](https://mlsanity.com/paper/1909.00505/) (2019)
- [In-context Examples Selection for Machine Translation](https://mlsanity.com/paper/2212.02437/) (2022)
- [Counterfactual Memorization in Neural Language Models](https://mlsanity.com/paper/2112.12938/) (2021)
- [Hyperparameter Tuning with Renyi Differential Privacy](https://mlsanity.com/paper/2110.03620/) (2021)
- [Preventing Verbatim Memorization in Language Models Gives a False Sense of Privacy](https://mlsanity.com/paper/2210.17546/) (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)
- [Individual Privacy Accounting via a Renyi Filter](https://mlsanity.com/paper/2008.11193/) (2020)
- [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)
- [Membership Inference Attacks Against In-Context Learning](https://mlsanity.com/paper/2409.01380/) (2024)
- [Privacy-Preserving Retrieval-Augmented Generation with Differential Privacy](https://mlsanity.com/paper/2412.04697/) (2024)
- [On the Privacy Risk of In-context Learning](https://mlsanity.com/paper/2411.10512/) (2024)
- [Private prediction for large-scale synthetic text generation](https://mlsanity.com/paper/2407.12108/) (2024)

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

- [Efficient Provably Private Classification with a Tabular Foundation Model](https://mlsanity.com/paper/2610.10068/) (2026)

## Abstract (arXiv)

Differentially private in-context learning (DP-ICL) has recently become an active research topic due to the inherent privacy risks of in-context learning. However, existing approaches overlook a critical component of modern large language model (LLM) pipelines: the similarity search used to retrieve relevant context data. In this work, we introduce a DP framework for in-context learning that integrates nearest neighbor search of relevant examples in a privacy-aware manner. Our method outperforms existing baselines by a substantial margin across all evaluated benchmarks, achieving more favorable privacy-utility trade-offs. To achieve this, we employ nearest neighbor retrieval from a database of context data, combined with a privacy filter that tracks the cumulative privacy cost of selected samples to ensure adherence to a central differential privacy budget. Experimental results on text classification and document question answering show a clear advantage of the proposed method over existing baselines.