Auditing Privacy in Multi-Tenant RAG under Account Collusion

Florian Burnat · 2026

Read Auditing Privacy in Multi-Tenant RAG under Account Collusion by Florian Burnat (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-19847.txt.

Introduction

Burnat audits privacy in multi tenant retrieval augmented generation under account collusion. Services often treat each account as the privacy boundary, with a differential privacy guarantee. Burnat shows coordinated accounts compose to joint leakage growing with the square root of coalition size, with a membership inference attack validated across scalar, top-K, embedder and production settings. An audit protocol attests noise then select retrieval and reports pass or fail with an audit epsilon for coalitions up to a declared cap, without disclosing the index.

Catalog record

CREATORFlorian Burnat
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE91736
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.19847

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Auditing Privacy in Multi-Tenant RAG under Account Collusion Florian Burnat Abstract Multi-tenant RAG services often treat the account as the privacy boundary: each account receives an ( ε acc , δ acc ) (\varepsilon_{\text{acc}},\delta_{\text{acc}}) -DP retrieval guarantee against the tenant index. We show that this framing understates leakage under same-index account collusion. For Gaussian noise-then-select retrieval, k k coordinated same-tenant accounts compose to joint leakage Θ ⁡ ( k ​ ε acc ) \Theta(\sqrt{k}\,\varepsilon_{\text{acc}}) , not ε acc \varepsilon_{\text{acc}} ; we give a matching membership-inference attack and validate the predicted k \sqrt{k} AUC trend in scalar, top- K K , trained-embedder, and production-scale HNSW settings. We then give a verifier-runnable audit protocol that attests noise-then-select retrieval and reports ( PASS , ε audit ) (\textsf{PASS},\varepsilon_{\text{audit}}) for coalitions up to a declared cap k max k_{\max} , without disclosing the index or changing the retrieval decision rule. The claim is retrieval-channel only: generation-channel leakage and adversarially robust coalition-size estimation are complementary audit predicates. 1 Introduction Production retrieval-augmented generation services, including Microsoft 365 Copilot, OpenAI Assistants, Anthropic Files API, and the managed-RAG products built atop Pinecone, Weaviate, and similar vector databases, are overwhelmingly multi-tenant. A single deployed embedder, a single deployed generator, and a fleet of per-tenant indices serve thousands to millions of customer accounts under a shared infrastructure. The DP-RAG designs proposed and audited at this architecture reason at per-account granularity: each account is rate-limited, each query is scored against only that account’s tenant index, and retrieval scores are noised to deliver an (\varepsilon_{\text{acc}},\delta_{\text{acc}}) -differential-privacy guarantee per account over an audit window ( 3 ; 24 ) . Our concern is the adequacy of the per-account framing where it applies, not that every named service formally advertises such a guarantee. This per-account framing is computationally convenient and aligns with how providers reason about API contracts. It is also the framing implicit in the recent wave of single-attacker membership-inference work ( 11 ; 22 ; 7 ; 12 ; 16 ; 8 ) , in which one isolated attacker is treated as the unit of analysis, competing on AUC at a fixed query budget under a k=1 threat model. Existing defenses ( 3 ) likewise modify the deployment to leak less per query; however, none formalize the changes when the assumption of a single attacker is relaxed. The gap Production RAG accounts are cheap. An adversary with a budget for k disposable accounts, whether a malicious customer creating sock puppets, a malicious bystander tenant probing across the boundary, or an external attacker buying API access through resellers, can pool k accounts’ query budgets against a single target tenant. The provider’s per-account DP guarantee provides no direct information about what the coalition observes jointly. Worse, the correct benchmark is unclear: a basic group-privacy bound provides \varepsilon_{\text{joint}}\leq k\cdot\varepsilon_{\text{acc}} , but this is loose; a naive “per-account independence” reading provides \varepsilon_{\text{joint}}\approx\varepsilon_{\text{acc}} , but this is incorrect. Neither extreme is the right benchmark: our results show the correct rate is \Theta(\sqrt{k}\cdot\varepsilon_{\text{acc}}) . Concretely, a service advertising \varepsilon_{\text{acc}}=1 per account can in fact leak as if \varepsilon\approx 3.16 to a ten-account coalition at realistic \delta_{\text{acc}}=10^{-6} , even though no single account exceeds its budget; for a fifty-account coalition the joint \varepsilon rises to {\approx}7.07 at the same per-account budget — the privacy debt the provider implicitly takes on by failing to bound coalition size. Contributions C1. Threat model: same-index multi-account collusion ( Sections 2 and 3 ). We formalize same-index multi-account collusion for multi-tenant RAG, define (\varepsilon,\delta,k) -collusion DP, and show that per-account DP structurally understates coalition leakage: for Gaussian noise-then-select retrieval, joint leakage scales as \Theta(\sqrt{k}\cdot\varepsilon_{\text{acc}}) ( Theorems 3.5 , 3.6 and 3.7 ), unconditional for same-tenant collusion and under M4 ( Remark 2.1 ) otherwise. The composition rate specializes prior DP theory ( 6 ; 10 ; 21 ) ; the contribution is the threat model and the bridge to RAG-specific MIA. C2. Falsifiable empirical predictions ( Sections 3 and 4 ). The DP-to-MIA reduction ( Corollary 3.12 ) predicts membership-inference AUC of \tfrac{1}{2}+\Theta(\sqrt{k}\cdot\varepsilon_{\text{acc}}) at fixed per-account budget. We commit to two falsification gates (P1, P3, Section 3.8 ) and validate the \sqrt{k} trend across scalar, top- K , trained-embedder, and production-scale HNSW settings. C3. Verifier-runnable audit protocol ( Section 5 ). We give a four-phase protocol that attests noise-then-select retrieval and issues a (\textsf{PASS},\varepsilon_{\text{audit}}) verdict without changing the retrieval decision rule or disclosing index, model, or pipeline. Theorem 5.3 shows that, if the true coalition size is at most the declared cap k_{\max} , the verdict implies (\varepsilon_{\text{audit}},\delta_{\text{policy}}) -collusion-DP. The coalition-size estimator is an operational gate: 5.2 calibrates it on P-A/B/C coalition patterns, while adversarially diversified coalitions remain a stated limitation. We also identify and correct a subtle \delta -accounting error in naive multi-account composition. 2 Threat Model We formalize multi-tenant retrieval-augmented generation (RAG) under coordinated account collusion as a Stackelberg-like game between a service provider \mathcal{P} and an adversary \mathcal{A} controlling k accounts. The provider commits to a privacy policy, namely, per-account rate limits and a differentially private retrieval scoring mechanism, and the adversary best-responds with a coordinated query strategy. Our analysis ( Section 3 ) shows that the provider’s per-account composition bound understates the total leakage, and the audit protocol ( Section 5 ) closes the resulting gap. 2.1 System model A multi-tenant RAG service is a tuple \mathcal{P}=(D,\mathsf{Emb},\mathsf{LLM},\mathsf{Policy}) where: • D=\{D_{t}\}_{t\in T} is a family of per-tenant indices, D_{t}\subseteq\mathcal{X} , partitioned by tenant identifier t\in T . • \mathsf{Emb}:\mathcal{X}\to\mathbb{R}^{d} is a shared embedder. • \mathsf{LLM}:\mathcal{Q}\times\mathcal{X}^{K}\to\mathcal{Y} is a shared generator that conditions on a query q and the top- K retrieved documents. • \mathsf{Policy}=(r,\varepsilon_{\text{acc}},\delta_{\text{acc}},\sigma) specifies the per-account rate limit r (queries per audit window), per-account privacy budget (\varepsilon_{\text{acc}},\delta_{\text{acc}}) , and noise parameter \sigma on retrieval scores. Figure 1 sketches the data flow. Accounts (rounded squares) live under tenants (dashed boundary boxes) and issue queries through a shared service; the service embeds each query, scores it against the requesting tenant’s index, perturbs the scores with Gaussian noise before top- K selection, and feeds the selected documents to the LLM. A k -coalition (red dashed link) is a subset of accounts that pool their responses through a shared output channel after the LLM has returned them, which the service cannot observe and the per-account rate limiter does not constrain. tenant t_{1} tenant t_{2} RAG service \mathsf{Emb}\rightarrow\mathsf{Score}\rightarrow+\mathcal{N}(0,\sigma^{2})\rightarrow\mathsf{TopK} LLM output channel top- K coalition k per-account rate limit r Figure 1 : Multi-tenant RAG with a k -account coalition. The service applies the rate limit per account and adds DP noise before top- K ; coalitions pool outputs across per-account rate limits and privacy budgets after retrieval (red dashed link). For a query q from account a with tenant t(a) , the service runs the retrieval mechanism \mathsf{Retr}(q,a)=\mathsf{TopK}\bigl(\mathsf{Score}(q,D_{t(a)})+\mathcal{N}(0,\sigma^{2}I)\bigr), (2.1) adding Gaussian noise before top- K selection, 1 1 1 Top- K on noisy scores is a post-processing step over the DP output, so the privacy loss is non-increasing. Selecting first and noising only the K winners breaks this — the unnoised ordering leaks through the selected indices. The audit protocol attests the correct ordering. and then returns \mathsf{RAG}(q,a)=\mathsf{LLM}(q,\mathsf{Retr}(q,a)) . Here \mathcal{N}(0,\sigma^{2}I) denotes i.i.d. Gaussian noise on each coordinate of the |D_{t(a)}| -dimensional score vector; the scalar

Read the complete text