KV-Cache and Prompt-Cache Leakage: Prefix Caching as a Membership Oracle

The key-value cache is what makes autoregressive generation fast: instead of recomputing attention over the whole prompt for every new token, the model stores the keys and values it already computed and reuses them. Prompt-prefix caching extends this across requests — if two prompts share an opening prefix, the second request can reuse the first's cached computation for that prefix and skip straight to the new part. It is an enormous efficiency win. It is also, the moment the two requests belong to different tenants, a side channel, because the second tenant can feel the speedup and infer that the prefix was already there. What was an optimization becomes an oracle answering a question the platform never meant to answer: did someone else just send this?

How prefix caching creates an oracle

When a request arrives, the serving system checks whether the prompt's prefix is already in the cache. If it is (a hit), the expensive prefill computation over that prefix is skipped and the request starts generating sooner; if it is not (a miss), the full prefill runs and the request is slower. The latency gap between hit and miss is the leak: it is a directly observable, secret-dependent timing difference. If caching is shared across tenants, the secret that determines hit versus miss includes other tenants' recent prompts.

This makes the cache a membership oracle. An attacker forms a candidate prefix, sends it, and measures the response latency. A hit-speed response implies the prefix was already cached — which, in a cross-tenant cache, implies another tenant recently sent a prompt with that prefix. The attacker learns a single bit about the global state (this prefix is present or not) per probe, and by choosing which prefixes to probe they can test hypotheses about what other tenants are doing.

The root cause is unchanged from classic shared-cache attacks: a resource shared across a trust boundary whose state is observable through timing. The defense is correspondingly classic — scope the cache to the trust boundary so a hit can only ever reflect the same tenant's own history, never anyone else's.

What an attacker can learn

The oracle answers membership questions, and membership questions about prompts are surprisingly sensitive. Prompts frequently contain a stable, reusable prefix: a proprietary system prompt, a template with an organization's name, a session header carrying a user or tenant identifier, a document being repeatedly queried. Confirming that a specific such prefix is cached tells the attacker that a particular customer, template, or document is active on the platform — information the platform sells isolation to protect.

Because the attacker chooses the candidate prefixes, they can turn membership into search. If they suspect a competitor uses a particular system-prompt template, they probe for it; a hit confirms the competitor is a co-tenant and reveals the template's presence. If a prefix embeds a predictable identifier, the attacker can enumerate candidates and use hit-timing to confirm which are live. Each probe is one bit, but a sequence of well-chosen probes composes into meaningful intelligence about other tenants.

The severity therefore depends on how guessable and how sensitive the cached prefixes are. The defense has two prongs: remove the cross-tenant observability (partitioning), and reduce what a confirmed hit reveals by not placing secrets in shared, cacheable prefixes — though the primary control is partitioning, since one should not rely on prompts never containing anything sensitive.

Quantifying the leak in bits

To decide how much this matters, measure it. An unmitigated prefix-cache oracle leaks close to one clean bit per probe: the latency distributions for hit and miss are well separated, so a single timed request classifies the prefix as present or absent with high confidence. The number of probes an attacker needs to recover a secret of interest is then roughly the number of bits in that secret divided by the per-probe leak, which for a clean one-bit oracle is small.

Noise changes the arithmetic but not the conclusion. If hit and miss distributions overlap — because of jitter, contention, or deliberately added noise — a single probe yields less than a bit, but the attacker recovers the lost precision by probing repeatedly and averaging, so the per-probe leak falls while the queries-needed rises proportionally. This is why timing noise alone is a weak defense: it raises the query count but does not close the channel, and a patient attacker simply probes more.

The robust defense combines masking with metering. Reduce the per-probe leak with partitioning (ideally to zero, since a per-tenant cache hit carries no cross-tenant information) and cap the total probes with per-tenant rate limits so that even a residual channel cannot be averaged down to a confident answer. The gauge of success is the residual mutual information times the allowed query rate, kept below a chosen threshold.

Deciding how to cache safely

Not every deployment needs the same control, so a decision procedure helps allocate cost. If a cache is never shared across tenants — each tenant has its own cache namespace — then a hit reveals nothing cross-tenant and prefix caching is safe to use freely. If caching is shared, the question becomes whether the prefixes can carry sensitive or guessable content; if they can (which is the safe assumption), cross-tenant sharing must be disabled for those prefixes or the cache partitioned. Only truly public, non-sensitive shared prefixes (a common instruction everyone uses) are safe to share.

The decision below routes a deployment to the right control. The guiding principle is that shared caching is an optimization you opt into for non-sensitive shared content, not a default you apply to all traffic — because the default of cross-tenant sharing turns every sensitive prefix into a probeable secret. Making this an explicit decision, rather than an implicit consequence of enabling a fast-path, is what prevents the oracle from existing by accident.

Where partitioning's memory cost is prohibitive, the fallback hierarchy is: share only public prefixes, disable sharing for anything tenant-specific, and add timing masking plus rate limits as a backstop for whatever residual sharing remains. Each step trades some cache efficiency for isolation, and the trade should be chosen against the sensitivity of the prefixes involved.

Why this matters for agent platforms

Agent platforms are especially exposed because their prompts are prefix-heavy and sensitive: a long, stable system prompt encoding tools and policy, a session header with user identity, a retrieved document repeatedly queried. These are exactly the reusable prefixes prefix caching targets for speedup and exactly the secrets a membership oracle can confirm. A co-tenant probing for a specific system-prompt template or user identifier is probing for the platform's most sensitive, most cacheable content.

The synthesis is that prompt-prefix caching must be scoped to a trust boundary, because a shared cache is a shared secret. The controls are concrete — per-tenant cache namespaces, cross-tenant sharing limited to public prefixes, timing masking and rate limits as backstops — and each trades cache efficiency for isolation. The classic shared-cache lesson applies unchanged to model serving: if a hit is faster than a miss and the cache spans a trust boundary, you have built an oracle, so either remove the sharing or accept that co-tenants can query it.

Practitioner Toolkit

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

# DEFENSIVE PROBE — does prefix-cache timing reveal membership?
function membership_leak(service, prefix):
    miss = median(time(service.fresh_request(prefix)))   # forced cold
    hit  = median(time(service.request(prefix)))          # now cached
    d_prime = (miss - hit) / pooled_std(service)
    if d_prime > DETECTABLE:
        flag("prefix-cache membership oracle", d_prime)
    # High d' == an attacker can classify hit vs miss per probe.

prefix_cache_policy:
  scope: per_tenant_namespace
  cross_tenant_sharing:
    allowed_for: public_prefixes_only
    sensitive_prefixes: never
  timing:
    mask_hit_miss_gap: true_for_shared_paths
  metering:
    per_tenant_probe_rate_limit: enforced
    leakage_budget_bits: defined

Glossary

Key-value (KV) cache

Stored attention keys and values from processed tokens, reused so generation need not recompute them.

Prompt-prefix caching

Reusing the KV cache of a shared prompt prefix across requests so a repeated prefix is processed almost for free.

Prefill

The initial computation over a prompt before generation, which prefix caching can skip on a hit.

Membership oracle

A channel revealing whether a specific input was recently processed, here via cache-hit timing.

Cache hit / miss

Whether a prefix is already cached (hit, fast) or must be computed (miss, slow), the timing gap being the leak.

Bits per probe

The information a single timed request reveals about whether a chosen prefix is present.

Cache partitioning

Isolating caches per tenant so a hit can only reflect the same tenant's prior requests.

Rate limiting

Capping the number of probes a tenant can issue, bounding the total information extractable from a residual channel.

References

1. Kwon et al., Efficient Memory Management for LLM Serving with PagedAttention (arXiv 2309.06180)
2. Kocher, Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems (CRYPTO 1996)
3. Leviathan et al., Fast Inference from Transformers via Speculative Decoding (arXiv 2211.17192)
4. Shumailov et al., Sponge Examples: Energy-Latency Attacks on Neural Networks (arXiv 2006.03463)
5. NIST AI 100-2 e2023, Adversarial Machine Learning: A Taxonomy and Terminology