Privacy by Proximity: How Nearest Neighbors Made In-Context Learning Differentially Private

Opening — Why this matters now

As large language models (LLMs) weave themselves into every enterprise workflow, a quieter issue looms: the privacy of the data used to prompt them. In‑context learning (ICL) — the art of teaching a model through examples in its prompt — is fast, flexible, and dangerously leaky. Each query could expose confidential examples from private datasets. Enter differential privacy (DP), the mathematical armor for sensitive data — except until now, DP methods for ICL have been clumsy and utility‑poor.

The new paper from Nokia Bell Labs proposes a clean solution: integrate k‑nearest neighbor (kNN) retrieval into the DP framework. Instead of random sampling (which may select irrelevant or harmful examples), the system privately retrieves the most relevant context examples while staying within a strict privacy budget. The result: a significant performance leap without compromising privacy guarantees.

Background — The brittle trade‑off of private prompting

Traditional DP‑ICL methods come in two flavors:

Both approaches protect privacy but often at the cost of task performance. When examples are randomly chosen, the LLM’s understanding can degrade so much that its “private” output is barely useful. This randomness — rather than the privacy noise — is often the real villain.

Meanwhile, in non‑private retrieval‑augmented generation (RAG), similarity search via embeddings has become standard. So why not borrow that logic for private prompting? That’s the Nokia team’s insight.

Analysis — Privacy‑aware retrieval meets adaptive accounting

The researchers modify the existing DP‑ICL Pay‑per‑use framework by adding a kNN search layer over the sensitive dataset. Each query retrieves the k most similar examples (by embedding distance) instead of random samples. These examples are then partitioned into prompt batches, ensuring both contextual relevance and diversity.

However, kNN retrieval complicates privacy accounting — each query might reuse parts of the private dataset multiple times. To handle this, the authors employ individual Rényi Differential Privacy (RDP) filters, a technique that tracks per‑record privacy loss. When any sample’s cumulative privacy exposure exceeds a predefined threshold, it’s retired from future retrievals.

This adaptive filtering ensures that the total privacy budget remains intact, while the algorithm can continue operating across many queries. It’s privacy as a renewable resource — used carefully, refilled probabilistically.

Findings — Accuracy restored, privacy maintained

The paper evaluates the method on both text classification (AGNews, TREC) and document question answering (SQuAD, DocVQA). In every case, DP‑ICL with kNN outperformed the non‑retrieval DP baselines by a wide margin.

Crucially, these gains came without using subsampling (which traditionally amplifies privacy). In other words, the team achieved better privacy–utility trade‑offs by improving relevance, not by relaxing protection.

Visually, the performance improvement across ε (privacy budget) levels shows a clear divergence — as ε grows, the kNN method approaches near‑non‑private performance while maintaining bounded privacy cost.

Implications — From compliance box‑checking to trust by design

This research reframes privacy‑preserving AI from a compliance checkbox into an engineering optimization. It suggests that organizations can deploy retrieval‑augmented models trained on sensitive text (legal, financial, or medical) without access leakage — as long as they manage per‑record privacy accounting.

For business leaders, this means retrieval‑based AI systems can be made both useful and certifiably private. For regulators, it provides a measurable bridge between algorithmic privacy proofs and audit‑ready implementations.

Future extensions — such as differential privacy applied to hierarchical retrieval structures (HNSW, IVF) — could scale this method to industrial search systems like Milvus or FAISS.

Conclusion — Relevance as the new regulator

The Nokia team’s framework shows that privacy and relevance need not be opposites. When managed through adaptive filters and proximity‑based retrieval, differentially private ICL becomes not just defensible, but deployable. In an age when enterprise AI systems are only as trustworthy as their context, privacy by proximity might be the next frontier.

Cognaptus: Automate the Present, Incubate the Future.