Governing the KV Cache: Preventing Timing Side-Channel Leakage in Multi-Tenant LLM Inference
On the map: Efficient LLM inference and serving → KV cache optimization
Abstract (arXiv)
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.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Placed in KV cache optimization, one of 12 directions in Efficient LLM inference and serving. Builds on 8 of its 15 references that are in the map. First posted on arXiv 10 Aug 2026.
Builds on
8 of 15 references.
Closest ancestors · 2
Same direction, newest first
- 2024CacheBlend: Fast Large Language Model Serving for RAG with Cached Knowledge Fusion26 May
- 2023Efficient Memory Management for Large Language Model Serving with PagedAttention12 Sep
Other references · 6
- 2023Not what you've signed up for: Compromising Real-World LLM-Integrated Applications with Indirect Prompt Injectioncited by 1,339
- 2022Ignore Previous Prompt: Attack Techniques For Language Modelscited by 760
- 2019Universal Adversarial Triggers for Attacking and Analyzing NLPcited by 709
- 2016Stealing Machine Learning Models via Prediction APIscited by 602
- 2018Model Reconstruction from Model Explanationscited by 84
- 2024The Early Bird Catches the Leak: Unveiling Timing Side Channels in LLM Serving Systemscited by 29
Built on by
Citing papers per year: 2026: 1.
1 paper.
Similar, not cited
Close in wording, no citation either way
- 2025Shadow in the Cache: Unveiling and Mitigating Privacy Risks of KV-cache in LLM Inference
- 2025Selective KV-Cache Sharing to Mitigate Timing Side-Channels in LLM Inference
- 2026Agent-Assisted Side-Channel Attacks on Non-Prefix KV Cache in RAG
- 2026Comparative Characterization of KV Cache Management Strategies for LLM Inference
- 2026KV Cache Optimization Strategies for Scalable and Efficient LLM Inference
- 2026HijackKV: New Threat in Position-Independent KV Cache Reuse
- 2026The KV Cache Working Set: Online Capacity Planning for LLM Inference Systems
- 2026RKSC: Reasoning-Aware KV Cache Sharing and Confident Early Exit for Multi-Step LLM Inference