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

arXiv: https://arxiv.org/abs/2608.09225 · HTML: https://mlsanity.com/paper/2608.09225/

## Key facts

- Cited by 1 papers in the map (data through 14 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.

## Placed in

- Efficient LLM inference and serving / [KV cache optimization](https://mlsanity.com/inference/kv-cache-optimization/)

## Builds on (most cited first, 8 of 8)

- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Not what you've signed up for: Compromising Real-World LLM-Integrated Applications with Indirect Prompt Injection](https://mlsanity.com/paper/2302.12173/) (2023)
- [Ignore Previous Prompt: Attack Techniques For Language Models](https://mlsanity.com/paper/2211.09527/) (2022)
- [Universal Adversarial Triggers for Attacking and Analyzing NLP](https://mlsanity.com/paper/1908.07125/) (2019)
- [Stealing Machine Learning Models via Prediction APIs](https://mlsanity.com/paper/1609.02943/) (2016)
- [CacheBlend: Fast Large Language Model Serving for RAG with Cached Knowledge Fusion](https://mlsanity.com/paper/2405.16444/) (2024)
- [Model Reconstruction from Model Explanations](https://mlsanity.com/paper/1807.05185/) (2018)
- [The Early Bird Catches the Leak: Unveiling Timing Side Channels in LLM Serving Systems](https://mlsanity.com/paper/2409.20002/) (2024)

## Built on by (most cited first, 1 of 1)

- [Characterizing Contention-Induced Reliability Collapse in KV-Cache Timing Side Channels for Multi-Tenant LLM Serving](https://mlsanity.com/paper/2609.06853/) (2026)

## 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.