Where the Savings Go: The Limits of Hiding Cross-Tenant Cache Hits in LLM Serving

Bowen Sun, Chaowei XiaoarXiv 2026 · arXiv

TL;DR

This paper demonstrates that hiding cross-tenant cache hits in LLM serving is much harder than previously thought because "saved time" doesn't just disappear—it shifts every subsequent request in the queue earlier. The authors introduce a "ruler" attack that can detect cached prefixes with over 98% accuracy even under heavy load, proving a fundamental trade-off: any performance benefit a tenant gains from shared content is, by definition, a privacy-leaking signal.

What Problem Does This Paper Address?

Large Language Model (LLM) serving engines (like vLLM or SGLang) use KV caching to speed up processing. If a user sends a prompt that shares a prefix with a previous one, the engine reuses the precomputed "keys" and "values," skipping expensive computation.

While efficient, this creates a timing side-channel. If a cache is shared across different users (tenants), an attacker can send a "probe" text; if it returns quickly, the attacker knows someone else recently sent that same text. This is a major privacy risk for sensitive documents or private conversations.

Existing defenses try to "hide" these hits by adding random delays to the hit request. This paper asks: Is that enough? The authors argue that even if you make the hit request look like a miss, the GPU time saved is immediately used to process the next requests in the queue. The "savings" are passed down the line, creating a measurable shift for everyone else.

Methods

The authors introduce the Ruler Attack, which moves away from measuring the absolute latency of a single request and instead measures the "ruler" of the engine's scheduling steps.

  1. Step-Based Observation: Modern LLM engines process requests in discrete "steps" (batches). The attacker sends a burst of "listener" requests (each asking for just one token) that bracket a "probe" request for the target text.
  2. The Shift: In a "Hit World," the probe skips computation, allowing the engine to start the listeners earlier. Because the scheduler is "work-conserving" (it doesn't idle if there is work to do), the time saved by the hit is "copied" to every request queued behind it.
  3. Counting Steps: Instead of timing milliseconds, the attacker counts how many engine steps it takes for their listeners to finish. This makes the attack incredibly robust against network jitter and general system noise.
  4. Theoretical Bounds: The authors provide a formal proof showing that if a tenant receives any utility (like faster responses) from content written by others, there is a non-zero privacy leak ($\epsilon$). To reach zero leakage, the tenant must gain zero benefit.

Datasets

The researchers evaluated their attack and various defenses using:

  • Azure LLM Inference Trace (2023): A production trace used to simulate realistic "honest" background traffic.
  • BurstGPT Trace: A dataset of API calls used to test the attack under different load distributions.
  • SQuAD / Wikipedia: Used for an end-to-end "Retrieval-Augmented Generation" (RAG) attack scenario, where the attacker tries to guess which document a victim's RAG system retrieved.
  • Mainstream Engines: Evaluation was performed on vLLM, SGLang, and TensorRT-LLM across various GPU types (L40S, RTX 6000, H100).

Key Insights and Ideas

  • Savings are Copied, Not Divided: In a typical queue, if the first person finishes 100ms early, everyone behind them moves up by 100ms. The signal isn't diluted; it's broadcast to the entire queue.
  • The "Ruler" is Robust: By using a burst of requests to fill engine steps, the attacker creates a self-calibrating clock. They don't need to know the exact GPU speed; they just need to see where the "step boundaries" fall relative to their own requests.
  • Defenses are Under-Powered: Common research defenses like KVGov (which adds 20ms of Gaussian noise) are easily defeated. To actually stop the Ruler attack with random delays, a provider would need to add delays 10 to 16 times larger than the actual time saved, destroying the performance benefits of caching.
  • The Zero-Leakage Price: The only way to have zero leakage is a "Lockstep Replica" defense—running a shadow scheduler that assumes every request is a miss and releasing results only when that "miss-only" schedule says so. This requires "padding" every step to the worst-case duration, which is computationally expensive.

Key Results

  • High Accuracy: On an idle vLLM instance, just four requests are enough to detect a cache hit with 0.985 to 0.989 advantage (near-perfect detection).
  • Resilience to Load: Even when replaying production traces at 50% of the engine's capacity, a single probe could detect a 256-token cached prefix with an advantage of 0.98.
  • RAG Attack Success: In the Wikipedia/RAG scenario, the attacker correctly identified which of four candidate chunks a victim retrieved in 97% of cases when the system was idle, and 85% of cases under half-load.
  • Defense Failure: Defenses that only hide the hit request (like those proposed by Gu et al.) still left an advantage of 0.96 to 0.99 for the Ruler attack.

Limitations and Future Work

  • Multi-Instance Dilution: If a provider uses many instances behind a round-robin router, the probe might land on a different instance than the victim's cache, diluting the signal. However, "prefix-aware" routing (common for efficiency) actually helps the attacker by sending them to the exact instance where the cache hit will occur.
  • Mixture-of-Experts (MoE): While the attack worked on a DeepSeek-V2-Lite model, the theoretical proofs currently focus on "dense" models where computation time is strictly tied to token count rather than content.
  • Padding Costs: The paper notes that "zero leakage" is possible but expensive. Future work could explore more efficient ways to "pad" or "schedule" to minimize the performance hit of the Lockstep Replica approach.

Recommendation for Providers: The authors conclude that if you need true isolation, you must salt your cache per trust domain (e.g., per account or per session). Trying to share a cache globally while "hiding" the hits is a losing battle against the physics of scheduling.

Summary updated

Abstract

LLM serving engines cache prompt prefixes; a cache hit skips computation and returns faster, so a shared cache reveals whether others have sent a given text. Per-account salting closes this channel but forgoes cross-tenant reuse and isolates only whole accounts, even where access is redistributed or trust domains are subdivided below them. Defenses that share globally but hide hits promise reuse without relying on account boundaries. Hiding a hit requires everything tenants observe afterwards to be distributed as if it had missed. The defenses we examine target the hit-miss gap; we instead follow where the saved time goes. Step-based schedulers that never idle while work waits pass it in full to every request queued behind the hit, shifting each earlier by the same amount. An attacker within ordinary rate limits brackets a probe with two groups of listeners that each return one token, sends them in one short burst, and counts in how many steps they finish. Replaying a production trace on one vLLM instance at up to half capacity, a single probe detects cached texts of 256 tokens or more with advantage at least 0.98. Hiding only the hit request falls to one probe on vLLM and SGLang; random delays must reach about ten times the shift or more to cut the advantage to 0.1; narrowing what is shared gives no guarantee against this inference. Since any observable tenant benefit is also a signal, we prove that a rate-limited tenant's gain from content written by k other accounts is at most of order k times the leakage allowed, whatever the provider does with identities; at zero leakage, only the provider keeps the savings. Exact hiding is attainable in principle on one instance, but mechanisms that only pause or hold work know skipped work's duration only approximately, so under saturated prefill they must pad every step that may hold a hit, at a price that grows with time rather than with hits.
BibTeX
@misc{sun2026where,
  author = {Bowen Sun and Chaowei Xiao},
  title = {{Where the Savings Go: The Limits of Hiding Cross-Tenant Cache Hits in LLM Serving}},
  year = {2026},
  eprint = {2611.20291},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.20291},
}
Figure