Governing the KV Cache: Preventing Timing Side-Channel Leakage in Multi-Tenant LLM Inference

arXiv: 2608.09225v1 [cs.CR] 10 Aug 2026

Modern LLM inference engines—vLLM, SGLang, and LMCache—cache the key-value (KV) attention states of previously computed token prefixes. When a new request shares a prefix with a cached one, the engine skips recomputation, reducing the time-to-first-token (TTFT) from hundreds of milliseconds to tens. On an NVIDIA A100 with Qwen2.5-7B-Instruct and a 2119-token shared prefix, the authors measure a cold TTFT of 149.6 ms versus a cached TTFT of 32.8 ms—a ratio of 0.22.

In multi-tenant deployments, this cache is shared across tenants to maximize hit rates and throughput. The problem is that the hit/miss distinction is observable by any tenant as a timing signal. Three independent research groups have shown how to exploit this:

• PROMPTPEEK (Wu et al., 2025, NDSS): An adversary can fingerprint a victim tenant's cached prompts by probing TTFT across a known vocabulary and correlating their observed timing vector with a pre-computed victim fingerprint, achieving 99–100% ASR on SGLang's radix-tree cache.

• EarlyBird (Song et al., 2024): Token-level reconstruction is possible via TTFT timing at the single-token cache granularity (block size=1), achieving 100% ASR on vLLM and SGLang. vLLM 0.26.0 (V1 engine) dropped block size=1, which raises the cost of free-text reconstruction to infeasibility—at B=16 an attacker must guess sixteen tokens simultaneously. However, this protection does not extend to template-structured prompts, where the unknown is a bounded field rather than an open vocabulary.

• InputSnatch (Zheng et al., 2024b): Attacks both cache mechanisms. Against prefix caching (vLLM, TGI, TensorRT-LLM) they reconstruct structured prompts field by field, reporting 62% success on disease extraction and 13.5% on symptom descriptions under real-world rate and time limits. Against semantic caching (GPTCache and managed cloud offerings) they explore the embedding space by hierarchical clustering, reporting 43–100% extraction across thirteen legal domains.

Root cause: All three inference engines compute cache keys over token sequences alone, without binding them to the issuing principal. Any tenant can therefore probe or read cache entries created by any other tenant. The paper states: These attacks share a common root cause: the absence of per-principal namespace isolation in the cache key computation.

KVGov binds cache resolution to the authenticated principal by seeding the block-hash chain with a per-principal salt:

σ p = HMAC K(secret, principal id),

h 0 = H(σ p ∥ tokens 0..B−1),

with h j for j > 0 chained as before. K is a server-side secret and ∥ denotes concatenation. Because every block inherits its predecessor's hash, salting h 0 makes the entire chain principal-specific, at a cost of one HMAC evaluation per request rather than per block. This is the mechanism vLLM exposes as cache salt (vLLM Project, 2025).

Why this works: "Each principal's salt is derived from a secret the adversary cannot know. An adversary probing p i on their own principal computes k(A, p i) ≠ k(V, p i) with overwhelming probability (SHA256 collision resistance). The adversary's probes therefore never hit the victim's cache entries—they only populate their own namespace. The adversary's timing fingerprint is all-MISS regardless of what the victim has cached, giving Pearson ρ ≈ 0 and ASR = 0."

Seeding the chain root isolates every block, which also destroys the cross-principal reuse that prefix caching exists to provide. The paper argues this cost is avoidable because "Identification is a function of divergence. If m principals share a preamble occupying blocks 0...k−1, every candidate hits those blocks, so their hit/miss pattern is constant across principals and carries no discriminating signal."

The salt is injected at the divergence boundary rather than the root:

h j = H(h j−1, tokens j) for j < k (shared, routable)

h j = H(σ p ∥ h k−1, tokens k) for j = k (boundary)

h j = H(h j−1, tokens j) for j > k (principal-private)

Efficiency retained: "Extrapolating from the measurements of Section 5.7 (cold 149.6 ms, fully cached 32.8 ms, 2119 tokens, 69.0% MFU), a 2000-token shared preamble with a 119-token private tail requires prefilling 8 blocks rather than 133, for an estimated 41.2 ms — retaining 92.8% of the benefit of full sharing. The trade-off degrades gracefully: a 1500-token preamble retains 62.6%."

Even with HMAC-salt isolation, a governance layer must detect anomalous probing behavior. ORIGAMI allocates a finite audit budget K across n tenants using a Stackelberg water-filling dual.

Game formulation: The defender commits to an audit probability p i for each tenant i with value-at-risk v i. The adversary, knowing p i, chooses the target that maximizes their expected payoff: max i v i(1 − p i). The defender minimizes adversary utility subject to ∑p i = K, p i ∈ [0, 1].

Theorem 1 (ORIGAMI water-filling solution): The optimal audit probabilities are:

p* i = max(0, 1 − λ/v i),

where λ > 0 is the unique value satisfying ∑p* i = K, obtained by binary search. The solution equalises the adversary's payoff v i(1 − p i) across every audited tenant—the defining property of a water-filling allocation—so no target is left disproportionately attractive.

ORIGAMI achieves 12.6% reduction in adversary expected utility over random audit at Gini = 0.63 (enterprise workload) with n = 10, K = 5.

The paper models cache scope selection as a two-population evolutionary game between global-cache users (sharing cache across sessions) and ephemeral-cache users (per-session isolated cache). Let x denote the fraction of the population using global cache.

Proposition 1 (ESS tipping point): Let τ be the adversary prevalence. Ephemeral caching is an evolutionarily stable strategy against invasion by global-cache mutants precisely when τ > τ*, where:

τ* = (V glb − V eph) / (C glb,eph − C eph + V glb − V eph)

With V glb = 0.45, V eph = 0.15, C glb,eph = 0.70 and C eph = 0.05, this gives τ = 0.30/0.95 = 31.6%*.

Replicator dynamics simulations are consistent with this threshold: global caching dominates at low adversary prevalence (94% share at convergence) and ephemeral caching prevails above it. The tipping point is robust across the realistic parameter space (τ* ∈ [24%, 40%] across all tested configurations).

Attack No defense Flush KVGov

PROMPTPEEK 100.0% 19.5% 0.0%

EarlyBird 100.0% — 0.0%

InputSnatch 100.0% 9.8% 0.0%

The 100% and 0% columns are analytic controls: "Under a shared cache the adversary's probe resolves to the victim's entry by construction, so the two fingerprints share a hit/miss structure and ρ ≈ 1 on every trial; under namespace isolation the probe never resolves, so the adversary observes an all-MISS vector whose zero variance drives ρ ≈ 0."

HMAC-salt alone achieves 0% ASR for both PROMPTPEEK and InputSnatch, confirming it is the necessary and sufficient mechanism. Admission control alone reduces InputSnatch ASR to 90.5% (by preventing PII prompts from entering the cache) but does not affect timing-based attacks. Gaussian noise injection (σ = 20 ms) nearly breaks PROMPTPEEK fingerprinting (0.5% ASR) but has no effect on InputSnatch, which relies on direct cache membership rather than timing magnitude.

ORIGAMI is equivalent to random audit at uniform value distribution (Gini = 0) and increasingly outperforms it as value heterogeneity grows. Under adversarial load (N=50 tenants, K=10, T=500 rounds), ORIGAMI reduces breach rates by 58–67% and expected damage by 66–72% across all adversary fractions. Convergence in 21–39 rounds confirms the Stackelberg equilibrium is reached quickly.

With a 2119-token shared prefix, the cold/cached TTFT ratio of 0.22 falls well below the breach threshold of 0.40. Shortening the shared prefix to 1447 tokens raises the ratio to 0.37, still a breach but much closer to threshold. The measurement passes five preregistered gates, including a server-side check that the cold arm's prefix-cache hit rate stayed below 5% (observed: 0.7%), a gate rejecting any cold arm whose latency implies more than 100% of the GPU's peak FLOPs (observed: 69.0% model-FLOPs utilisation), and a third requiring two independent blocks to agree (observed drift: 1.14%).

The channel was replicated on a deliberately dissimilar stack: llama.cpp (via Ollama) on Apple M4 with Metal, serving Qwen2.5-3B—a different inference engine, accelerator vendor, memory architecture, and model scale. Using a 781-token shared prefix, cold TTFT is 1861 ms against 173 ms cached, a ratio of 0.093—a breach by a wider margin than on the A100. The paper notes: "The convergence matters more than the magnitude. Two stacks with nothing in common but the idea of reusing a shared prefix both expose the hit/miss distinction as a timing signal, which is what one expects if the channel follows from prefix caching itself rather than from an implementation detail."

HMAC derivation adds 1.33 µs per cache key lookup—0.0041% of the 32.8 ms cached TTFT and 0.00089% of the 149.6 ms cold TTFT. The breach observer and ORIGAMI scheduler run in background threads and do not add to request latency. The PII admission gate (Presidio) costs 50–150 ms but is invoked only on cache-miss paths.

1. First unified defense: Binding cache resolution to the authenticated principal defeats all three attack families' prefix-cache paths simultaneously, by collision resistance rather than by obfuscation.

2. ORIGAMI audit scheduler: A Stackelberg water-filling dual allocates audit budget across tenants in proportion to their value-at-risk, achieving 12.6% reduction in adversary expected utility over random audit at realistic workload heterogeneity.

3. Evolutionary stability analysis: Replicator dynamics analysis identifies a closed-form tipping point at 31.6% adversary prevalence.

4. Gate-verified hardware validation: Timing side channel confirmed on Qwen2.5-7B-Instruct / vLLM 0.26.0 / NVIDIA A100 (cold/cached ratio 0.22), with replication on an independent stack.

5. Deterministic ASR judges: Replacing LLM-based heuristic judges (which the internal audit measured at 40% accuracy) with attack-specific deterministic judges: Pearson correlation for PROMPTPEEK, exact token overlap for InputSnatch, token recovery rate for EarlyBird.

• EarlyBird scope: Results use a reference simulation (block size=1) because vLLM 0.26.0 removed that configuration. Block-size hardening should not be treated as a substitute for namespace isolation in deployments whose prompts are templated.

• Cache efficiency trade-off: Root salting eliminates cross-principal prefix sharing; boundary salting's efficiency figures are extrapolated rather than measured directly.

• Semantic caches require a different instantiation: KVGov's salt construction isolates the key-equality rows of Table 1, but does not cover InputSnatch's semantic-cache variant, which resolves by nearest-neighbour search over embeddings. Isolation there must be enforced by partitioning the retrieval index per principal.

• Simulation vs. production: ASR experiments use a discrete-event simulation with fixed hit/miss latencies (5 ms / 50 ms); extended field experiments with real adversarial tenants remain future work.

"Prior work has established that shared KV caches in multi-tenant LLM serving create a timing side channel that three independent attacks—PROMPTPEEK, EarlyBird, and InputSnatch—exploit to reconstruct victim prompts with 100% ASR. These attacks share a common root cause: cache keys are computed over token sequences alone, with no binding to the issuing principal. KVGov eliminates this root cause by binding cache resolution to the authenticated principal, which by collision resistance leaves an adversary's probes unable to resolve to a victim's entries."

KVGov is designed as a governance layer deployable alongside existing inference engines without modification to model weights, attention mechanisms, or generation pipelines. All experimental scripts and data are released to support reproducibility.

Based on this paper, here are the specific improvements I can implement in AI systems:

Implementation: Add HMAC-keyed salting to all KV cache key computations, where the salt is derived from the authenticated tenant ID and a server-side secret. This means modifying the cache lookup function to include HMAC K(secret, principal id) in the initial block hash, ensuring cache entries are only accessible by their creator.

Improved capability: The AI system can now serve multiple tenants from a shared cache infrastructure without any tenant being able to probe or infer another tenant's cached prompts. An adversary attempting to fingerprint victim prompts will observe all cache misses, making timing-based reconstruction attacks mathematically impossible (0% ASR).

Implementation: Instead of salting the entire cache chain (which destroys cross-tenant reuse), detect the divergence point where tenant-specific content begins and inject the principal salt only at that boundary. This requires tracking which prefix blocks are shared across tenants versus tenant-private.

Implementation: Deploy a background scheduler that allocates audit probability p i = max(0, 1 - λ/v i) across tenants, where v i is each tenant's value-at-risk and λ is solved via binary search to meet the audit budget. The scheduler continuously monitors cache access patterns and flags anomalous probing behavior.

Implementation: Replace LLM-based heuristic judges with deterministic detection rules: Pearson correlation for fingerprinting attacks, exact token overlap for reconstruction attempts, and token recovery rate for block-level attacks. These run as lightweight background checks on cache access patterns.

Implementation: Add a Presidio-based gate on cache-miss paths that checks whether incoming prompts contain personally identifiable information (PII) before allowing them to enter the shared cache. This is invoked only when a new prompt is being cached, not on cache hits.

Implementation: Implement a policy that dynamically chooses between global caching (shared across sessions) and ephemeral caching (per-session isolated) based on the measured adversary prevalence τ in the deployment. The tipping point is τ* = 31.6% as derived from the evolutionary game analysis.

Implementation: Add a real-time monitor that measures cold-to-cached TTFT ratios for incoming requests, flagging any ratio below 0.40 as a potential breach. This uses the validated measurement methodology from the paper (including the five preregistered gates for accuracy).

The key-value (KV) cache is the primary throughput optimization in modern large language model (LLM) inference, enabling prefix reuse across requests. In multi-tenant deployments this cache is shared across tenants, creating a timing side channel: an adversarial tenant can reconstruct another tenant's private prompt by probing cache-hit latency. Three published attacks exploit it -- PROMPTPEEK, EarlyBird and InputSnatch -- reaching up to 100% attack success rate against unprotected vLLM and SGLang, with rates varying by cache architecture and prompt structure. We present KVGov, a governance layer addressing all three attack families' prefix-cache paths under one mechanism. A per-principal salt sigma p = HMAC K(secret, principal id) seeds the block-hash chain, making cache keys cryptographically disjoint across principals. An ablation (N=1000 trials, seed 2026, deterministic judges) isolates this salt as the necessary and sufficient component. KVGov adds ORIGAMI, a Stackelberg water-filling audit scheduler that reduces adversary expected utility by 12.6% at realistic tenant heterogeneity (Gini 0.63), and an evolutionary stability analysis giving a 31.6% adversary-prevalence tipping point below which global caching remains stable. On real hardware (Qwen2.5-7B-Instruct, vLLM 0.26.0, NVIDIA A100) we measure a gate-verified cold/cached TTFT ratio of 0.22, confirming the channel is exploitable at production scale; the defense itself is evaluated in simulation calibrated to those measurements. We replicate the channel on an independent stack (llama.cpp on Apple Metal, ratio 0.093). Finally, isolation and cache efficiency need not conflict: identifying information resides only where prompts diverge, so injecting the salt at that boundary rather than the chain root retains an estimated 93% of the prefix-cache benefit with no cross-principal signal.