Chain-Preserving Subsampling for Private Multi-Hop Retrieval

Retrieval-augmented language models answer questions by looking up passages in a document collection. When that collection is private, for example clinical notes or internal records, the answers can leak what individual documents say. The standard protection is differential privacy: a guarantee that the system's output would look nearly the same whether or not any single document were in the collection. A common and cheap way to get this guarantee is privacy amplification by subsampling. The system works only on a random subset of the data, so any given document was probably not used, and its influence is diluted. The trouble is that the questions retrieval systems handle worst are exactly the ones subsampling breaks. A multi-hop question such as "where was the director of Inception born?" needs a chain of documents: one naming the director, another giving his birthplace. If each document survives the random subsample independently with probability $q$, an $H$-document chain survives with probability $q^H$, so strong privacy all but guarantees the chain is gone.

We propose to subsample the collection in correlated groups instead of document by document. A public hash of each document's entity mentions assigns it to a few "entity buckets," and whole buckets are sampled at once. The document that mentions Christopher Nolan and the document about Christopher Nolan land in the same bucket, so a sampled bucket keeps the bridge between hops intact. Each of many "voter" copies of an iterative retrieve-and-reason agent runs the full multi-hop loop on its own bucket-sampled sub-collection, and only a short final answer leaves the system, through a noisy vote. The claim is that, at a matched per-document privacy guarantee, bucket sampling keeps a chain in far more voters than independent sampling. The advantage should grow with the number of hops. It comes without the document-level blocking that current multi-query private retrieval needs.

Core Claim

Three facts together make this worth doing. The first is that multi-hop questions need iterative retrieval. IRCoT alternates reasoning sentences with new searches, and CoRAG trains such chains end to end, raising retriever recall on MuSiQue from 29.0% with single-step retrieval to 47.1%. The second is that existing private retrieval-augmented generation does not support such loops. DPSparseVoteRAG splits the corpus into disjoint parts, has one model copy per part vote on each next token, and runs out of budget after roughly 20–40 generated tokens in single-shot settings. MURAG-ADA tracks a separate privacy budget for each document across many queries and retrieves deterministically above a privately chosen threshold. Its best setting allows each document to be used once, which blocks bridge documents needed at later hops, and it uses no subsampling. The third fact is that subsampling analysis already extends to structured sampling units: image patches in random-cropping patch-level DP and bi-level windows in structured subsampling for time series. Nobody has built a structured sampling unit for text whose structure is the reasoning chain itself.

The mechanism works as follows. The designer fixes a public hash function over normalized entity-mention strings, which yields $B$ buckets. Each document $d$ joins the buckets of at most $c$ of its mentions: its title entity plus its most salient others. Because bucket membership depends only on $d$'s own text and a public function, adding or removing $d$ never changes any other document's buckets. Each of $m$ voters samples every bucket independently with probability $q$. It then runs an IRCoT-style agent over the union of its sampled buckets, and every retrieval, query and reasoning step stays internal. Finally it emits one short answer string. The released output per question is a Gaussian-noised histogram of the voters' answers, reduced to its top answer. Document $d$ is present in a given voter with probability

$$p_d = 1 - (1-q)^{c_d} \le cq,$$

where $c_d \le c$ is its number of buckets. A 2-hop chain whose documents share the bridge-entity bucket survives in a voter with probability at least $q$. Under independent document sampling at the same worst-case inclusion rate $cq$, it survives with probability $(cq)^2$. More generally, an $H$-hop chain needs its $H-1$ bridge buckets, which gives at least $q^{H-1}$ against $(cq)^H$. Bucket sampling therefore keeps more voters on the right answer whenever $q < 1/c^2$, and the gap widens by roughly a factor of $1/(c\,q)$ per extra hop.

Research Program

The first deliverable is the privacy analysis. Two properties hold here. The bucket draws are independent of whether $d$ is present, and once the bucket draw is fixed, the two neighboring collections differ in exactly one document inside the sampled sub-collection. The output distributions therefore take the shared-component mixture form $(1-p_d)X + p_d Y$ versus $(1-p_d)X + p_d Z$, where $Y$ and $Z$ are the base mechanism's outputs on inputs differing by $d$. We will prove amplification for this form with the coupling and joint-convexity tools of Balle et al., aiming for their bound $e^{\epsilon'} = 1 + p_d(e^{\epsilon}-1)$, with $\epsilon$ the base guarantee and $\epsilon'$ the amplified one. This is not a restatement of the Poisson result, because $d$'s bucket-mates are included together with it. That is the proof obligation the proposal must meet.

Across the $m$ voters, $d$ affects only the $K_d \sim \mathrm{Binomial}(m, p_d)$ voters that contain it. This is the "selected in $k$ of $t$ steps" structure handled by efficient accounting for subsampling and random allocation, which we reuse for the per-question accountant. Costs across a stream of $Q$ questions are composed with Rényi differential privacy, a privacy measure that adds up cleanly over repeated releases. Optionally we add MURAG-style per-document budgets, which charge a document only for the questions whose sampled sub-collections contained it. Documents with many mentions have the largest $p_d$. Capping $c$ plays the role gradient clipping plays in private training. We will also test the per-document calibration suggested by importance-sampling amplification, which balances privacy loss across points of unequal influence.

The second deliverable is an empirical test of a prediction taken from Subsampling is not Magic. That work shows that over long private training runs, the noise needed grows roughly in proportion to the sampling rate, so small samples buy nothing. Carried over to voting, the useful signal is about $m$ times the chain-survival probability, and the noise scales roughly with $p$. This implies that independent sampling's ratio of signal to noise grows like $p^{H-1}$, pushing the best choice toward large $p$ and little amplification. Bucket sampling's ratio should instead be roughly flat in $q$. Whether this carries over from gradients to discrete answer votes is itself an open question, and we will measure it directly.

Baselines

The floor is a closed-book model that answers from its own parameters with no private retrieval. It uses the same Llama-3.1-8B-Instruct used by CoRAG, and it costs no privacy. The ceiling is non-private IRCoT over the full corpus with the same model and retriever. The file gives CoRAG's non-private MuSiQue recall of 47.1% as a reference for how much an iterative loop recovers. There is no reported result on Lacuna for any differentially private method on MuSiQue, HotpotQA or 2WikiMultihopQA answer accuracy.

The strongest existing competitor is MURAG-ADA run inside an IRCoT loop. It is strongest because it is the only method in the file built for sequences of dependent private queries and already evaluated on MQuAKE chains. There it answers 100 queries at a total $\varepsilon = 10$, where naive composition needs $\varepsilon = 1000$ (Beyond Per-Question Privacy). The file reports no MQuAKE answer-accuracy figure for it, so we will reproduce it. Each hop's retrieval will be its private release, with its access limit $M$ tuned over the same grid we give our $q$ and $c$.

The second competitor is DPSparseVoteRAG, the disjoint-partition token-voting method, which is the closest sample-and-aggregate design. We run it in two forms. One is as published, with single-shot retrieval and token voting. The other is modified so that each partition runs IRCoT internally and only the final answer is voted on. The modified form is exactly our pipeline with a disjoint partition in place of bucket sampling.

The key ablation is independent document sampling at a rate chosen so the maximum inclusion probability equals $cq$. Everything else stays fixed: voters, agent, vote noise and accountant. This isolates the one ingredient we claim matters, which is correlated inclusion along bridge entities. All methods share the model, retriever, corpora, total $(\varepsilon, \delta)$ over the same question stream, a compute budget measured in generated tokens per question, and the same number of tuning trials on a held-out development split. Beating a baseline means higher exact match at equal accounted $\varepsilon$, for $\varepsilon \in \{1, 4, 10\}$, across three seeds. It also means an empirical privacy audit showing no more leakage than the baseline.

Why not just…?

Why not just partition the corpus into disjoint pieces, as DPSparseVoteRAG does, and put the multi-hop agent inside each piece? With disjoint pieces, each document sits in exactly one voter. The evidence for a specific fact is therefore held by at most one voter, and the noisy vote drowns it out. Random pieces also split chains: an $H$-hop chain lands whole in one of $m$ pieces with probability $(1/m)^{H-1}$. Partitioning by hyperlink communities would keep chains together, but the partition would then depend on the private documents themselves, so removing one document could reshuffle everything. The one-voter-per-fact problem would also remain. The modified-DPSparseVoteRAG baseline tests this head on. If it matches us, the overlap from subsampling is not earning its keep.

Why not just run MURAG-ADA at every hop? This is the most serious competitor, because charging each document only when it is actually retrieved is very efficient. Its weakness in agent loops is structural. Every hop's retrieval is a separate private release that is composed with the others. With the single-use setting that paper found best, a bridge document retrieved at hop one cannot be retrieved again later. Our design releases one answer per question however many internal hops the agent takes. If MURAG-ADA with tuned $M$ matches us on 3- and 4-hop MuSiQue questions, the correlated-sampling idea is not needed and we will report that.

Why not just use large samples and more noise, since "subsampling is not magic"? Räisä et al.'s result suggests exactly this for independent sampling, and we expect it to hold there. Our experiment sweeps $q$ from 0.01 to 0.5 at fixed $\varepsilon$ for both sampling schemes. The prediction that separates the two: independent sampling's best $q$ rises with the hop count, while bucket sampling performs about as well at small $q$, where amplification is strongest and where more questions fit in a fixed budget.

Why not just use encryption? Private dense retrieval with homomorphic reranking hides the user's query from the server. It gives no guarantee about what the generated answer reveals about documents in the corpus, which is the threat here, so it complements this work rather than competing with it.

Proposed Experiments

The primary benchmark is MQuAKE. Its counterfactual fact edits mean that correct answers must come from the corpus rather than the model's memory, which removes the main confound of using Wikipedia-derived questions. MuSiQue-Ans provides the hop-count analysis because it spans 2 to 4 hops with single-hop shortcuts filtered out (MuSiQue). HotpotQA (HotpotQA) and 2WikiMultihopQA serve as secondary sets. For each, the paragraph pool is the private corpus, and we report exact match and F1 minus the closed-book score.

Beyond accuracy, we measure the chain-survival rate per voter against its predicted value and the number of voters that agree on the gold answer. For the privacy audit, we plant fabricated two- and three-document canary chains about fictional entities, then run membership and extraction attacks. We report attack AUC and an empirical lower bound on $\epsilon$, which must stay below the accounted value.

Three checks settle the idea. First, at matched $\varepsilon$, bucket sampling's accuracy gain over independent sampling must grow from 2- to 4-hop MuSiQue questions. A flat gap means correlation is not the mechanism. Second, measured chain survival must track the predicted $q^{H-1}$ versus $(cq)^H$ ratio, including on MuSiQue questions whose bridges are paraphrased rather than string-matched. That is where mention hashing may fail, and a failure there would call for fuzzier bucket keys. Third, the planted-canary audit must not exceed the accounted $\epsilon$, which is the empirical backstop for the correlated-inclusion proof.