arxiv6.0 / 10

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

Bowen Sun, Chaowei Xiao

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.

Research area

Model Reliabilityprivacysecurity
Published
15 Nov 2026
Source
arxiv
Org
Johns Hopkins University
View paper
Sign in to read and join the discussion.