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