🤖 AI

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

This paper introduces KVGov, a governance layer that prevents timing side-channel attacks in multi-tenant LLM inference by cryptographically isolating KV cache keys across tenants via per-principal salting and an audit scheduler, thereby eliminating cross-tenant leakage while preserving 93% of prefix-cache efficiency.

Original authors: Tejasvi C. Addagada

Published 2026-08-11

📖 8 min read🧠 Deep dive

CC BY 4.0

Original authors: Tejasvi C. Addagada

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a bustling, high-tech library where a magical librarian (the AI) can answer any question you have. To be super fast, this librarian keeps a "reference sheet" of the most common story beginnings right on their desk. If you ask a question that starts with the same words as someone else's, the librarian doesn't need to re-read the whole book; they just glance at the reference sheet and jump straight to the answer. This is incredibly efficient, saving huge amounts of time. However, in a busy library with many different people (tenants) using the same desk, a sneaky person could figure out what the others are reading. They wouldn't need to see the book; they'd just watch how long it takes the librarian to find the answer. If the librarian grabs the answer instantly, the sneaky person knows, "Ah, they must have asked about the same story I just asked about!" If the librarian has to walk to the back shelves, it means the story is new. By timing these tiny delays, a bad actor could reconstruct the private secrets or prompts of other people, turning a speed feature into a security leak.

This paper tackles that exact problem in the world of Large Language Models (LLMs), the super-smart AI chatbots we use today. These models use a "KV cache" (the reference sheet) to speed up responses by remembering previous parts of a conversation. The author discovered that in shared environments, this speed trick creates a "timing side channel"—a secret signal hidden in how long things take. They found that three different groups of hackers have already shown how to use this signal to steal private prompts with nearly 100% success. The paper proposes a new system called KVGov to fix this. Instead of just trying to hide the timing (which is hard), KVGov changes the rules of the game so that the reference sheet is completely different for every single user. It's like giving every library visitor their own unique, invisible ink that makes their specific reference sheet unreadable to anyone else. The author shows through simulations and real hardware tests that this method stops all three types of attacks dead in their tracks, while still keeping the library fast enough to be useful. They also introduce a smart "security guard" system that knows exactly who to watch most closely, and they calculate a tipping point where it becomes safer to stop sharing the reference sheet entirely.

The Great Cache Heist

Think of the AI's memory as a giant, shared whiteboard. When you ask the AI a question, it writes down the key parts of your sentence on the board so it doesn't have to re-calculate them if you ask a similar question later. This is the KV cache. In a multi-tenant setup (where many different companies or users share the same AI server), everyone shares this whiteboard to save time.

The problem is that the whiteboard is too obvious. If a sneaky user (the attacker) asks, "What is the capital of France?" and the AI answers instantly, the attacker knows, "Oh, someone else must have asked that recently!" If the AI takes a long time, the attacker knows, "No one has asked that yet." By trying thousands of different questions and timing the answers, the attacker can map out exactly what other people are asking, even if they can't see the answers themselves. This is called a timing side-channel attack.

The paper highlights three specific ways hackers have used this:

PROMPTPEEK: The hacker guesses a list of possible questions and times them all. If their timing matches the victim's pattern, they know exactly what the victim asked.
EarlyBird: The hacker tries to guess the victim's question one word at a time. If the AI is fast, they know they guessed the right word.
InputSnatch: This is for structured questions, like filling out a form. The hacker knows the template (e.g., "Show transactions for account [NUMBER]") and just tries different numbers until the AI is fast, revealing the secret account number.

The author tested this on real hardware (an NVIDIA A100 GPU) and found that the timing difference is huge: a "cold" request (new info) took 149.6 milliseconds, while a "cached" request (reused info) took only 32.8 milliseconds. That's a ratio of 0.22, which is a massive, easy-to-spot signal for a hacker.

The Solution: KVGov and the Magic Ink

The paper introduces KVGov, a new layer of security that acts like a gatekeeper. Its main trick is HMAC-keyed namespace isolation.

Imagine that every user in the library has a unique, secret stamp (a "salt"). When the librarian writes a question on the whiteboard, they first stamp it with the user's secret ink. Even if two people ask the exact same question, the ink makes the whiteboard entry look completely different to everyone else.

How it works: The system takes the user's ID and a secret key to create a unique code. This code is mixed into the very first step of creating the cache key.
The Result: If a hacker tries to guess what a victim asked, their own secret stamp won't match the victim's. The hacker's probe will always look like a "miss" (slow) because their code doesn't match the victim's code on the board. The timing signal disappears.

The author ran 1,000 simulated trials and found that this "HMAC-salt" alone was enough to drop the attack success rate from 100% to 0% for all three types of attacks. It was the only part of their system that was strictly necessary; the other parts just added extra layers of safety.

Keeping the Library Fast (The Boundary Trick)

You might think, "If everyone has their own secret whiteboard, won't the library get slow?" If we made every single user have a totally separate board, we'd lose the speed benefit of sharing common questions (like "Hello, how are you?").

The paper offers a clever fix called Boundary Salting.
Imagine a story where the first 2,000 words are the same for everyone (the shared preamble), and only the last 100 words are different (the private part).

Old way: Stamp the whole story with secret ink. No one can share the first 2,000 words.
KVGov way: Leave the first 2,000 words un-stamped so everyone can share them. Only stamp the very first word where the stories diverge.
The Payoff: This keeps 93% of the speed benefit while still keeping the private parts secret. The author estimates that with a 2,000-word shared intro and a 119-word private tail, the system would still be incredibly fast (around 41.2 ms for the private part), retaining most of the efficiency.

The Smart Security Guard: ORIGAMI

Even with the magic ink, the author wanted to make sure no one was trying to sneak around. They created ORIGAMI, a smart audit scheduler.

Think of the library manager having a limited budget of security guards. They can't watch everyone all the time. ORIGAMI uses a mathematical strategy (called a Stackelberg water-filling approach) to decide who to watch.

The Logic: If a user is very valuable (high risk) and has a history of suspicious behavior, they get more guards. If a user is low risk, they get fewer.
The Result: In simulations with 10 tenants and a realistic mix of user types (a "Gini coefficient" of 0.63), this smart scheduling reduced the attacker's expected success by 12.6% compared to just picking random people to watch.

When to Stop Sharing

Finally, the paper asks a big question: "When is it better to stop sharing the whiteboard entirely?"

They used a concept called Evolutionary Stability to find a tipping point. They modeled a population of users where some share the cache (fast but risky) and some don't (slow but safe).

The Finding: If the percentage of hackers in the system goes above 31.6%, it becomes mathematically better for everyone to stop sharing the cache and go back to having their own private boards. Below that number, sharing is still the winning strategy. This gives library managers a clear rule: if you suspect more than about 1 in 3 users are bad actors, stop sharing the cache.

What This Doesn't Do

The paper is very clear about what it doesn't solve.

It doesn't stop hackers from stealing the AI's brain (the model weights).
It doesn't stop hackers from tricking the AI into saying bad things (prompt injection).
It doesn't fix "semantic caches" (where the AI matches ideas rather than exact words). For those, you'd need a different kind of lock.
The EarlyBird attack (guessing word-by-word) is mostly blocked by newer AI engines that use larger "blocks" of words, but the author warns that for structured forms (like account numbers), the block size doesn't matter—the timing leak is still there.

The Bottom Line

The author proved that the speed boost we love in AI comes with a hidden cost: a timing signal that leaks private information. They showed that simply hiding the signal isn't enough; you have to break the link between the user and the cache. By using a cryptographic "magic ink" (HMAC-salt) and only applying it where the secrets begin, KVGov stops the leaks completely while keeping the AI fast. It's a win for privacy that doesn't require slowing down the future of AI.

Technical Summary: Governing the KV Cache (KVGov)

1. Problem Statement

Modern Large Language Model (LLM) inference engines (e.g., vLLM, SGLang) utilize Key-Value (KV) caches to store attention states for previously computed token prefixes. This mechanism enables significant throughput optimization by skipping recomputation for shared prefixes, reducing Time-to-First-Token (TTFT) from hundreds of milliseconds to tens of milliseconds.

In multi-tenant deployments, this cache is shared across all tenants to maximize hit rates. However, the paper identifies a critical vulnerability: the distinction between a cache hit and a cache miss is observable as a timing signal. Because cache keys are currently computed solely over token sequences without binding them to the requesting principal, an adversarial tenant can probe the cache to reconstruct another tenant's private prompts.

Three independent attack families exploit this timing side channel:

PROMPTPEEK (Wu et al., 2025): Uses TTFT fingerprinting across a known vocabulary to correlate timing vectors with pre-computed victim fingerprints, achieving up to 100% Attack Success Rate (ASR) on radix-tree caches.
EarlyBird (Song et al., 2024): Reconstructs prompts token-by-token by observing cache hits at single-token granularity (block size=1). While vLLM 0.26.0 removed block size=1, the paper argues this protection fails against template-structured prompts where the search space is bounded by the field domain rather than the full vocabulary.
InputSnatch (Zheng et al., 2024b): Targets both prefix and semantic caches. Against prefix caches, it reconstructs structured prompts field-by-field; against semantic caches, it explores embedding spaces via hierarchical clustering.

The root cause is the absence of per-principal namespace isolation in cache key computation.

2. Methodology: The KVGov Framework

The author presents KVGov, a unified governance layer designed to eliminate the root cause of these attacks without modifying model weights or generation pipelines.

2.1 HMAC-Keyed Namespace Isolation

The core mechanism binds cache resolution to the authenticated principal.

Mechanism: A per-principal salt $\sigma_p$ is derived using an HMAC function: $\sigma_p = \text{HMACK}(\text{secret}, \text{principal id})$ .
Implementation: This salt seeds the block-hash chain. For a block size $B$ , the first block hash becomes $h_0 = H(\sigma_p \parallel \text{tokens}_{0..B-1})$ . Subsequent blocks chain from this root.
Effect: Because the salt is derived from a server-side secret unknown to the adversary, cache keys for the same token sequence become cryptographically disjoint across different principals. An adversary's probes will never hit a victim's cache entries, resulting in an "all-MISS" timing pattern regardless of the victim's actual cache state.

2.2 Boundary Salting (Efficiency Optimization)

To address the potential loss of cross-principal cache efficiency, the paper proposes Boundary Salting.

Concept: Instead of salting the chain root (which isolates every block), the salt is injected only at the divergence boundary ( $k$ ) where the shared preamble ends and the private content begins.
Logic: Blocks $0$ to $k-1$ (shared preamble) remain globally routable and shared. Blocks $k$ and beyond are cryptographically isolated.
Benefit: This retains the prefix-cache benefit for the shared portion of prompts (e.g., system instructions) while preventing timing leakage for the private portion. The paper estimates this retains ~93% of the prefix-cache benefit.

2.3 ORIGAMI: Stackelberg Audit Scheduler

To detect anomalous probing behavior, KVGov incorporates ORIGAMI, an audit scheduler based on Stackelberg game theory.

Mechanism: It allocates a finite audit budget across tenants using a "water-filling" dual algorithm.
Goal: Minimize the adversary's expected utility by auditing tenants with the highest "value-at-risk" ( $v_i$ ) in proportion to their risk, rather than auditing randomly.
Outcome: The solution equalizes the adversary's payoff across audited targets, preventing them from focusing on unmonitored high-value tenants.

2.4 Evolutionary Stability Analysis

The paper models the selection of cache scope (global vs. ephemeral) as an evolutionary game.

Finding: It identifies a tipping point at 31.6% adversary prevalence. Below this threshold, global caching is evolutionarily stable; above it, ephemeral (isolated) caching becomes the stable strategy.

3. Key Contributions

Unified Defense: KVGov is the first system to simultaneously defeat all three attack families (PROMPTPEEK, EarlyBird, InputSnatch) by addressing the root cause (lack of namespace isolation) rather than obfuscating timing.
Necessary and Sufficient Mechanism: An ablation study demonstrates that HMAC-salt alone is the necessary and sufficient component for the privacy guarantee, reducing ASR to 0% across all attacks. Other components (noise injection, admission control) provide defense-in-depth but are not strictly required for the core cryptographic fix.
Hardware Validation: The paper confirms the existence of the timing side channel on real hardware (NVIDIA A100, vLLM 0.26.0, Qwen2.5-7B), measuring a cold/cached TTFT ratio of 0.22 (well below the 0.40 breach threshold). The channel was also replicated on an independent stack (Apple M4, llama.cpp) with a ratio of 0.093.
Deterministic Judges: The evaluation replaces heuristic LLM-based judges with attack-specific deterministic judges (Pearson correlation, exact token overlap, token recovery rate), ensuring 100% accuracy in the simulated attack model.
Efficiency Preservation: The "Boundary Salting" approach demonstrates that isolation and cache efficiency are not mutually exclusive; injecting the salt at the divergence boundary retains the majority of prefix reuse benefits.

4. Results

Attack Success Rate (ASR): Under the KVGov defense (specifically HMAC-salt), the ASR for PROMPTPEEK, EarlyBird, and InputSnatch drops to 0.0% in simulation.
Partial Defenses: Session-boundary flushing (a partial defense) leaves PROMPTPEEK at 19.5% ASR and InputSnatch at 9.8% ASR, demonstrating the insufficiency of simple flushing.
ORIGAMI Performance: In enterprise workloads with high value heterogeneity (Gini = 0.63), ORIGAMI achieves a 12.6% reduction in adversary expected utility compared to random auditing.
Overhead: The cryptographic overhead of HMAC-salt derivation is negligible (~1.3 µs per request), representing less than 0.005% of the cached TTFT latency.
Evolutionary Stability: Simulations confirm that global caching dominates when adversary prevalence is below 31.6%, while ephemeral caching prevails above this threshold.

5. Significance and Claims

The paper claims that KVGov fundamentally alters the security posture of multi-tenant LLM inference by shifting from obfuscation (which is brittle and often ineffective against structured prompts) to cryptographic isolation.

Root Cause Elimination: By binding cache keys to the authenticated principal via collision-resistant hashing, the paper argues that the timing oracle is effectively removed. An adversary's probes can no longer resolve to a victim's entries, rendering the timing signal uninformative.
Scalability: The defense is lightweight and deployable alongside existing engines (vLLM, SGLang) without requiring changes to the underlying model architecture or attention mechanisms.
Governance Perspective: The paper frames cache management not just as an infrastructure optimization but as a governance problem. It provides quantitative criteria (the 31.6% tipping point) and algorithmic tools (ORIGAMI) for operators to make informed decisions about cache scope based on their threat landscape.

The author explicitly notes limitations: the defense covers hash-keyed prefix caches but requires a different instantiation (index partitioning) for semantic caches. Additionally, while boundary salting is theoretically efficient, its end-to-end measurement in production engines is identified as future work.