Abstract

The key-value (KV) cache is the primary throughput optimization in modern large language model (LLM) inference, enabling prefix reuse across requests. In multitenant deployments, this cache is shared across tenants, creating a timing side channel: an adversarial tenant can reconstruct another tenants private prompt by probing cache-hit latency patterns. Three independent attacks exploit this channelPROMPTPEEK (Wu et al., 2025), EarlyBird (Song et al., 2024), and InputSnatch (Zheng et al., 2024b)and reach up to 100% attack success rate (ASR) against unprotected vLLM and SGLang deployments, with reported rates varying by cache architecture and prompt structure. We present KVGov, the first unified governance layer that defends against all three attack families simultaneously. KVGovs core mechanism is HMACkeyed namespace isolation: a per-principal salt _p_ = HMAC _K_ (secret _,_ principal ~~i~~ d) seeds the block-hash chain, so that cache keys are cryptographically disjoint across principals and no cross-principal timing signal can arise. An ablation study over N=1000 simulated trials (seed=2026, deterministic judges) isolates HMAC-salt as the necessary and sufficient component: it alone accounts for the full reduction in ASR, with the remaining components contributing defense in depth. KVGov further incorporates ORIGAMI, a Stackelberg water-filling audit scheduler that achieves 12.6% reduction in adversary expected utility at realistic tenant heterogeneity (Gini = 0 _._ 63), and an evolutionary stability analysis identifying a tipping point at 31.6% adversary prevalence below which global caching remains evolutionarily 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. Finally, we show that isolation and cache efficiency are not in conflict: because identifying information resides only in the blocks where prompts diverge, injecting the salt at that boundary rather than at the chain root retains an estimated 93% of the prefix-cache benefit while leaving no cross-principal timing signal.