Cross-Tenant and Neighbor Leakage: The Similarity Oracle and Multi-Tenant Isolation Failures

The defining operation of a vector database — find the stored items most similar to a query — is quietly an information oracle. Every similarity response tells the querier something concrete: how close their input is to the nearest thing in the store, and often which item that is. Repeated across many crafted queries, those measurements add up to a reconstruction of the store's contents or a confirmation that a specific document is present. And when a single index is shared across tenants with only a metadata filter for separation, the oracle can answer questions about a neighbor tenant's data. This article treats neighbor and cross-tenant leakage as the measurement problem it is, and argues that isolation must be built into the index structure rather than bolted on as a post-search filter.

The similarity oracle

Nearest-neighbor search returns, for a query vector, the stored vectors closest to it, usually with a distance or similarity score. Each response is a measurement of the query's proximity to the store's contents, and that measurement carries information about what the store holds. A high similarity score means the store contains something very like the query; the returned item, or its metadata, may reveal exactly what. Even without returning documents, the score alone is a signal an attacker can exploit.

This makes the retrieval endpoint an oracle in the security sense: a function an attacker can query to learn about hidden data. Song and Raghunathan's work on embedding leakage and the OWASP guidance on vector and embedding weaknesses both point at this — the retrieval layer is not a passive lookup but an interface that discloses information about the corpus with every call. The disclosure is per-query and accumulates, exactly like the query-access model for a served model.

The defender's first recognition is that similarity scores and returned neighbors are disclosure, governed by the same lever as any oracle: what the response reveals and how many responses are allowed. Returning coarser results and capping query volume both reduce the leak, and isolating whose data a query can reach removes the cross-tenant dimension entirely.

Reconstructing a corpus from neighbors

With the oracle in hand, an attacker can reconstruct corpus contents by probing. Systematic queries that vary along semantic dimensions, guided by the returned distances, triangulate the location of stored vectors — each response narrows down where a neighbor sits in embedding space. Combined with the embedding-inversion attack, a recovered neighbor vector can then be turned back into approximate text. The pipeline is probe, observe distances, localize stored vectors, and invert to text.

The attack is a measurement estimation problem: the attacker is an estimator building a map of the store's occupied regions from distance responses, with the query budget setting the achievable resolution. More queries mean a finer map; coarser or noisier distance responses mean a blurrier one. This is why both query limits and score coarsening degrade the reconstruction, and why returning exact distances to arbitrary callers is the richest form of the leak.

For the defender, the reconstruction pipeline names the levers precisely: reduce the information per response (coarse or thresholded scores, no raw distances), reduce the number of responses (rate limits), and detect the systematic probing pattern that reconstruction requires. None makes the index secret, but together they raise the cost of mapping it.

Membership from similarity

A narrower but sharper leak is membership. If an attacker holds a candidate document and wants to know whether it is in the store, a single similarity query answers it: a near-exact match — a similarity score at the top of the range — strongly indicates the document is present. This is the retrieval-layer analog of membership inference, and it can be decisive because embeddings of identical or near-identical text land extremely close together, producing an unmistakable score.

The privacy impact mirrors membership inference: confirming that a specific document is in a corpus can itself be sensitive, revealing that a person's record, a confidential file, or a particular message was ingested. Because a single confident query suffices, this leak is cheap and hard to catch by volume alone, which makes response-side controls — not returning raw top scores, applying a distance floor so near-exact matches are not distinguishable from merely close ones — the more reliable defense.

The defender should treat a near-exact similarity response as a membership disclosure and design the response so that presence cannot be confirmed with certainty: thresholding, score bucketing, or refusing to return items above a similarity that implies identity. The goal is to deny the confident yes that makes the attack work.

Multi-tenant isolation failures

The most damaging version is cross-tenant. To save cost, many deployments store multiple tenants' vectors in one shared index and separate them with a metadata filter applied to search results. That is not isolation; it is a filter on a shared computation, and filters fail. If the filter is misapplied, bypassed by a crafted query, or simply forgotten on one code path, a tenant's query returns another tenant's documents or their similarity scores — a direct confidentiality breach across the strongest boundary a multi-tenant system has.

Even when the filter works for document return, the shared index can leak through scores and index behavior: a query's nearest-neighbor distances are computed against all tenants' vectors before filtering, so timing, ranking artifacts, or aggregate statistics can reveal the presence of another tenant's similar data. Metadata filtering addresses which documents are returned, not whether the shared computation touched a neighbor's vectors, so it leaves a residual cross-tenant signal.

The structural fix is per-tenant indexes: each tenant's vectors live in a separate index (or a cryptographically enforced partition) so a query is computed only against that tenant's data and cannot, by construction, reach another's. Isolation enforced by structure cannot be bypassed by a forgotten filter, which is exactly why it is the right control for the tenant boundary.

Shared versus per-tenant isolation

The contrast between the two designs is stark on the security axis even when they look similar operationally. A shared index with metadata filtering is cheaper and simpler to operate but places the tenant boundary at a filter applied after a computation that already touched every tenant's data; its isolation is only as strong as the correctness of that filter on every code path. A per-tenant index computes each query against a single tenant's vectors, so cross-tenant leakage is structurally impossible regardless of filter bugs.

The trade is cost and operational complexity against the strength of the boundary. Per-tenant indexes multiply the number of indexes to manage and can be less resource-efficient, which is the reason shared indexes are tempting. But the tenant boundary is typically the highest-stakes boundary in a multi-tenant product, and a boundary enforced by a filter is a boundary one bug away from breach — a poor trade for the cost saved.

The principled position is that the tenant boundary deserves structural enforcement. Where per-tenant indexes are infeasible, the shared index must be treated as a shared trust domain with compensating controls — strict, tested filtering on every path, score masking, and monitoring — and the residual risk acknowledged, not assumed away.

Defenses that follow

The defenses combine structural isolation with oracle-reduction. Structurally, use per-tenant indexes so queries cannot reach other tenants' data, and where sharing is unavoidable, apply strict filtering on every path and test it adversarially. On the oracle, reduce disclosure: return coarse or thresholded similarity rather than raw distances, apply a distance floor so near-exact matches cannot confirm membership, and return the minimum result detail the application needs. On volume, rate-limit and detect the systematic probing that reconstruction requires.

These layers target the two dimensions of the leak: whose data a query can reach (isolation) and how much each response reveals (disclosure and volume). Isolation removes the cross-tenant dimension outright; disclosure and volume controls raise the cost of single-tenant reconstruction and membership confirmation. As elsewhere in the retrieval-security family, the structural control is the strong one and the disclosure controls are the tunable complement.

The measured posture is to enforce the tenant boundary structurally, add distance-floor and score-coarsening to blunt reconstruction and membership, cap query volume, and monitor for probing. Then verify by attempting the oracle attacks against your own index and measuring how much they recover.

Limits and honest framing

The limits are real on both sides. Score coarsening and distance floors reduce reconstruction and membership fidelity but also degrade retrieval quality, since the application needs the very proximity signal the attacker exploits — so oracle-reduction is a trade, sharpest where it conflicts with ranking accuracy. Per-tenant isolation is structurally strong but costs operational complexity and resource efficiency, which is why shared indexes persist and why the residual risk of the shared design must be stated plainly rather than assumed away.

Detection has the familiar caveat: systematic probing can be spread across accounts and time to evade volume-based anomaly detection, so the load must fall on isolation and disclosure controls that reduce leakage per response and per boundary regardless of who queries. And membership confirmation from a single near-exact query is inherently hard to catch by volume, making response-side thresholding the more dependable control against it.

Held honestly, the contribution is a boundary correction: the retrieval endpoint is an oracle and a shared index is a shared trust domain, so isolation must be structural and disclosure must be minimized. Isolate by construction, coarsen the oracle, cap the volume, and verify by attacking your own index — that is defensible retrieval security.

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

# DEFENSIVE / MOCK ONLY — audits your own index, no other tenant's data
function audit_retrieval(index, own_probes, own_candidate):
    # 1) reconstruction pressure: how much do distances reveal?
    recon = estimate_localization(index, own_probes)
    # 2) membership: does a near-exact query confirm presence?
    top = index.query(embed(own_candidate)).top_score
    membership_confirmable = top > NEAR_EXACT_T
    # 3) isolation: does a tenant-A query ever touch tenant-B ids?
    cross = probe_cross_tenant(index, tenant='A')
    return RetrievalReport(localization=recon,
                           membership_confirmable=membership_confirmable,
                           cross_tenant_hits=cross)

Glossary

Similarity oracle

The retrieval endpoint viewed as a queryable function that discloses proximity of a query to stored data.

Corpus reconstruction

Estimating a store's contents by triangulating stored vectors from many distance responses.

Similarity membership

Confirming a specific document is stored via a single near-exact similarity match.

Metadata filtering

Restricting returned results by tenant tag after a search over a shared index — a filter, not isolation.

Per-tenant index

A separate index or partition per tenant so queries compute only against that tenant's vectors.

Distance floor

A threshold that prevents near-exact matches from being distinguished, denying membership confirmation.

Shared trust domain

A shared index treated as accessible to all its tenants for risk purposes when true isolation is absent.

References

1. Song & Raghunathan, Information Leakage in Embedding Models (ACM CCS 2020)
2. Morris et al., Text Embeddings Reveal (Almost) as Much as Text (arXiv 2310.06816)
3. OWASP Top 10 for LLM Applications: LLM08 Vector and Embedding Weaknesses
4. NIST AI 100-2 e2023 — Adversarial Machine Learning: A Taxonomy and Terminology