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

TL;DR for operators

Private examples are not harmless just because they sit inside a prompt rather than inside model weights. In-context learning lets teams adapt a general LLM by adding examples at inference time, which is convenient until those examples are medical notes, legal clauses, customer tickets, invoices, or internal decisions that should not be inferable from the model’s output.

The paper behind this article makes a precise move: it adds k-nearest-neighbor retrieval to differentially private in-context learning, then accounts for the privacy cost of retrieving and reusing sensitive examples.¹ That sounds like a small engineering patch. It is not. Existing DP-ICL methods often protect privacy by randomly sampling examples or generating private synthetic demonstrations. Random sampling helps privacy accounting, but it can feed the model irrelevant demonstrations. The model then performs badly, which is a wonderfully secure way to be useless.

The direct result: nearest-neighbor retrieval improves utility across the paper’s evaluated text classification and document question-answering benchmarks while preserving formal record-level differential privacy through individual privacy filters. The business interpretation: if an enterprise uses private context in prompts, retrieval should be treated as part of the privacy mechanism, not as an innocent search box attached before the “real” model call.

What remains uncertain: the method is demonstrated with exhaustive FLAT indexing, benchmark tasks, and record-level assumptions. It does not prove that all industrial RAG systems can become differentially private by sprinkling kNN over them like regulatory parsley.

Private prompting fails when the examples are private and irrelevant

Imagine a bank wants a language model to classify support tickets using a few examples from previous customer cases. Fine. Now imagine those examples include account disputes, transaction histories, or personally identifying details. Less fine. The model is not being trained on those examples, but the examples still shape the output. A clever observer may not need the original prompt; the response itself can carry statistical traces of what was shown.

That is the privacy problem in in-context learning. The model adapts through the prompt, and the prompt may contain private records. Prior work has shown that prompted models can expose membership signals: an attacker may infer whether a particular record was included in the prompt or private example pool.² For businesses, this is not a philosophical concern about “AI safety.” It is closer to access-control leakage dressed up as productivity software.

Differentially private in-context learning tries to make the output insensitive to the presence or absence of any single private record. In simple terms, the answer should not change too much because one customer ticket, one invoice, or one training example was included. That is the promise. The difficulty is that LLMs are unusually dependent on which demonstrations they receive. Give the model relevant examples and it behaves like it understands the task. Give it random examples and it starts performing interpretive dance with labels.

That is the likely misconception around this paper: the problem was not merely that DP added noise. The problem was that earlier private prompting pipelines often protected privacy by weakening relevance.

Existing DP-ICL protected outputs, but often starved the model of useful context

The paper positions itself against two major families of privacy-preserving ICL.

The first family generates differentially private synthetic examples. Tang and colleagues, for example, proposed generating few-shot demonstrations from private datasets with formal DP guarantees.³ The appeal is obvious: once the synthetic examples are produced, they can be reused without repeatedly spending privacy budget. The operational drawback is also obvious: generating high-quality private demonstrations can require access to logits and substantial computation, and the generated examples may not cover the exact query distribution that appears later.

The second family is “pay-per-use” DP-ICL. Wu and colleagues proposed splitting private examples into disjoint shards, prompting the model separately on those shards, then privately aggregating the responses through noisy voting for classification or private aggregation for generation.⁴ This is attractive because it works with prompt-only access and does not require fine-tuning. It also maps better to enterprise API workflows, where nobody is eager to rebuild the foundation model just to answer one compliance-sensitive query.

But the baseline pay-per-use setup uses sampling to select examples. Sampling improves privacy accounting because each record is less likely to participate. Unfortunately, it may also select examples unrelated to the query. For in-context learning, that is not a minor inconvenience. The examples are the temporary task interface.

The paper’s contribution is not “nearest neighbors are useful.” That has been true since before most vector database pitch decks discovered gradients. The contribution is showing how nearest-neighbor retrieval can be integrated into a DP-ICL pipeline without letting repeated retrieval quietly burn through the privacy budget.

The move is not “add kNN”; it is “make retrieval accountable”

The proposed system replaces random example selection with nearest-neighbor retrieval. For each query, the system retrieves the most similar examples from the sensitive dataset, then partitions those examples into disjoint batches used as demonstrations in prompts. The downstream DP mechanisms remain familiar: report-noisy-max with Gaussian noise for classification and keyword-space aggregation for question answering.

The key technical object can be read as:

Here, $R_t$ is the retrieval function for query $t$, and $M$ is the private aggregation mechanism that turns the prompted model responses into a released answer. In ordinary RAG engineering, $R_t$ is treated as plumbing. In this paper, $R_t$ is part of the privacy-relevant computation.

That distinction matters. If retrieval is query-dependent, the same private record may be selected again and again because it is highly relevant to many queries. Relevance is good for accuracy; repeated exposure is bad for privacy accounting. The system therefore keeps an active set of records and tracks cumulative privacy loss for each record. When a record’s budget is about to be exceeded, it is removed from future retrieval.

In operational language: the database gets a privacy meter per record. Some records can be used more often if their accumulated privacy cost remains low. Others are retired. This is less theatrical than “privacy by design,” but considerably more useful.

Individual privacy filters are the guardrail that lets relevance survive

The privacy accounting relies on individual Rényi differential privacy filters, extending a line of work by Feldman and Zrnic on accounting for privacy loss at the level of individual data points.⁵ The intuition is simple enough: instead of treating every record as if it always incurs the worst possible privacy loss, track how much privacy loss each record actually accumulates across adaptive analyses.

The paper needs that adaptivity because the retrieval function changes with the query. The system does not know in advance which records will be retrieved. A fixed global accounting story would either be too loose to protect records or too conservative to allow useful retrieval.

The filter removes a record $x_i$ from the active set when its accumulated privacy cost crosses the configured threshold:

There is a second, quieter condition: retrieval must have limited sensitivity. The paper focuses on FLAT exhaustive nearest-neighbor search, because changing one dataset element changes the retrieval output in a controlled way. This is mathematically convenient and commercially inconvenient. FLAT search is easy to reason about, but large production systems often use approximate indices such as IVF or HNSW because exhaustive search does not scale gracefully. Faiss, the library used in the experiments, is explicitly designed around this broader vector-search trade-off space.⁶

So the paper earns its privacy proof under a clean retrieval setting. That is perfectly respectable. It is not the same as solving every approximate vector index in the warehouse.

The experiments show relevance buying back utility, not magic privacy

The evidence is strongest when read as a mechanism test: does relevance improve DP-ICL utility once privacy is still accounted for? The answer is yes, across the evaluated benchmarks.

For text classification, the paper tests AGNews and TREC. It uses OPT-1.3B, deterministic generation, ten shards with four demonstrations each, all-MiniLM-L6-v2 embeddings, and FAISS FLAT retrieval. Each result averages five runs over 200 randomly sampled test examples, with $\delta = 10^{-5}$. In the plots, DP-ICL with nearest neighbors clearly outperforms the DP-ICL subsampling baseline. On AGNews, the kNN method moves into the high-80% accuracy range at larger privacy budgets, while the random-sampling baseline remains in the low-to-mid 70s. On TREC, the gap is also visible, with the kNN version rising toward the high 40s while the subsampling baseline stays around the high 20s to low 30s.

The paper also includes a “nearest-neighbor only” dummy comparison, where the private release is run over the labels of retrieved neighbors. This is useful because it separates two forces. Retrieval itself contributes a lot of utility. The DP-ICL mechanism then wraps that relevance in a formal privacy release process. That is the right lesson: the model is not becoming private because kNN is clever; it is becoming useful because relevant demonstrations survive the privacy mechanism.

The TREC result also shows the boundary. At very low $\epsilon$, performance deteriorates. The paper explains this through Gaussian noise: when $\epsilon = 0.5$, the required noise scale is roughly equal to the number of shards, so the voting signal is heavily randomized. This is not a failure of nearest neighbors. It is a reminder that a privacy budget can be so tight that the system has very little signal left to preserve. Differential privacy is mathematics, not a coupon code.

For document question answering, the paper evaluates a federated version of DocVQA and SQuAD v1.1. The DocVQA setting is especially relevant because the source documents are invoices containing confidential details, though the paper limits itself to textual ICL by using OCR tokens rather than image understanding. The demonstration sets contain 69,785 records for DocVQA and 18,891 for SQuAD, with 100 test queries in each case.

The pattern is more nuanced than the classification result, but the direction is consistent: DP-KSA-kNN generally beats the DP-KSA baseline, especially at higher privacy budgets. The paper notes that DP-KSA is less sensitive to $\epsilon$, while the kNN version improves more when the privacy budget allows useful signal to pass through. That is exactly what one would expect if the advantage comes from relevance rather than from a mysterious new privacy loophole.

The result is best read as an architecture lesson

The paper directly shows a DP framework for ICL that integrates nearest-neighbor retrieval with privacy filters, plus experiments showing better utility than existing baselines on selected classification and QA tasks. It does not directly show a turnkey enterprise privacy platform. Cognaptus’ inference is that the retrieval layer needs to become auditable infrastructure.

The practical implication is less glamorous than “private AI unlocked.” It is more like this: if an enterprise keeps a private demonstration store for LLM prompting, each record should have an exposure budget. Retrieval should be logged. Query-dependent reuse should be accounted for. Records should expire from retrieval when their privacy budget is spent. This is not the usual RAG demo architecture, where embeddings go into a vector database and governance is added later with a slide that says “secure.”

The ROI case is also narrower than vendors may prefer. This method is valuable when the organization needs both task adaptation and formal privacy guarantees over the private demonstration set. Examples include regulated support workflows, document QA over sensitive operational records, internal classification of legal or compliance documents, and cases where prompt examples are too sensitive to expose directly but too valuable to discard.

It is less compelling when the dataset is public, when ordinary access control is sufficient, when the output does not need formal privacy guarantees, or when the main risk is hallucination rather than leakage. Not every problem needs differential privacy. Some merely need fewer interns pasting customer data into chat windows.

The business value is governed relevance, not compliance theatre

A useful way to read the paper is as a correction to a common enterprise instinct. Many teams treat privacy as a downstream filter: retrieve whatever helps, prompt the model, then redact the output. That may reduce obvious leakage, but it does not provide a formal guarantee about whether a private record influenced the answer.

The paper moves privacy upstream. It says the selection of context is already part of the disclosure process. That is uncomfortable because retrieval is where modern LLM systems get much of their usefulness. The more relevant the retrieved examples, the more they may expose about sensitive records. The answer is not to abandon relevance. The answer is to meter it.

For operators, this suggests three design shifts.

First, private example stores should be managed differently from generic knowledge bases. A policy document and a customer complaint may both become embeddings, but they do not carry the same privacy semantics.

Second, retrieval logs need to become privacy accounting inputs. In many systems, retrieval logs are treated as debugging artefacts. In a DP-ICL setting, they are closer to financial transaction logs: each retrieval spends something.

Third, privacy budgets should be tied to records and data subjects, not merely to model calls. The paper assumes record-level DP. In real enterprises, one person or company may appear across many records. That pushes the design toward group-aware accounting, entity resolution, and data governance that can survive contact with messy databases. A small detail, then. Only the whole organisation.

The boundaries are where deployment teams should pay attention

The most important limitation is the indexing assumption. The paper uses FLAT exhaustive search because it satisfies the stability requirement cleanly. Production vector systems often rely on approximate search methods such as IVF or HNSW for speed and memory efficiency. The paper identifies those as future directions, possibly with additional DP machinery such as private clustering. Until that work is done, “works with FAISS FLAT” should not be silently upgraded into “works with our billion-vector approximate search stack.”

The second boundary is the privacy unit. The experiments protect the presence of a single record, such as one document-question-answer triplet. In DocVQA and SQuAD, the authors sample a single question-answer pair per paragraph or image and assume each record belongs to a single user. Real enterprise data does not always behave so politely. A patient, supplier, employee, or customer may appear across many records. Record-level DP may then understate entity-level exposure.

The third boundary is the interaction model. The paper assumes a controlled DP-ICL server and privacy-accounted use of a private demonstration dataset. It does not solve confidentiality of the user’s query, provider-side logging, prompt injection, broader model memorisation, or leakage from non-private documents retrieved elsewhere in the pipeline.

The fourth boundary is task scope. Classification and extractive-style document QA are useful tests, but they are not the same as long-form advisory generation, open-ended legal reasoning, or multi-step agentic workflows. As the output becomes more complex, aggregation and privacy accounting become less tidy. Naturally, the mess waits patiently in production.

Private context needs a meter, not a slogan

The paper’s real contribution is to make a familiar enterprise trade-off explicit. Privacy-preserving prompting is not just about adding noise to outputs. It is about deciding which private examples may influence which answers, how often they may do so, and when their participation should stop.

Nearest-neighbor retrieval helps because useful prompts need relevant demonstrations. Individual privacy filters help because relevant demonstrations create repeated exposure. Put together, they sketch a more realistic architecture for private LLM systems: not “retrieve first, govern later,” but retrieval as a privacy-accounted operation from the start.

That is the useful lesson for businesses. Formal privacy and practical relevance do not have to be enemies. But they do have to be engineered together, which is usually where the slogans begin to look slightly underdressed.

Cognaptus: Automate the Present, Incubate the Future.