Skip to content

Where the saved time goes: limitations of hiding cross-tenant cache hits in LLM serving

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

arXiv: 其他 AI 安全论文· arXiv:2611.20291· Bowen Sun, Chaowei XiaoJohns Hopkins UniversityIndexed by this site · 2 days ago· Originally publishedSelected Attacks· Its place in the scan record →SelectedAttention40

Quick read

Attacks

Based on the paper PDF (AI-generated); refer to the original

The authors propose that cross-tenant KV cache hits replicate the savings to subsequent requests, that a single probe reads out membership with an advantage of at least 0.98 under vLLM at half load, and they prove that with zero leakage only the provider retains the savings.

Threat modelThe attacker holds a few ordinary accounts, stays within the provider's rate limits, knows the candidate text and engine configuration, does not control or know about other tenants' traffic, and observes only the output events, status codes, and billing of their own requests; the victim account uses secret text, and the attacker asks a membership question: whether that text is in the cache.

Questions
When an LLM serving engine shares a prefix cache across tenants, a hit leaks whether someone else has sent a given text; per-account salting closes this channel but gives up cross-tenant reuse, and isolation only goes down to account granularity. The authors ask: how far can a defense that shares a global cache but hides hits go.
Methods
The authors point out that hiding hits requires everything observable afterward to be distributed as in the miss world, and they trace where the savings go: the step scheduler copies the time saved by a hit in full to each request queued behind it. The attacker brackets a probe with a group of listener requests that each return one token and reads the shift by counting at which step each completes; the paper also classifies and evaluates published defenses along three dimensions—scope, release, reaction—and gives a leakage upper bound and a zero-leakage construction.
Experiments and results
Replaying Azure production traces to half load on a single vLLM instance, a single probe has an advantage of at least 0.98 for texts of 256 tokens or more; defenses that only hide hit requests are read out by a single probe on vLLM and SGLang (advantage 0.96–0.99); random delay needs about 10 times the shift or more to bring advantage down to 0.1; the authors prove that the benefit a rate-limited tenant obtains from k other accounts' content is at most on the order of kε, and that under zero leakage only the provider retains the savings.
Limitations and future work
The authors point out: no deployed service was measured; the shortest readable secret grows with the per-step token budget; failures under high load stem from the victim's chunk being evicted; only membership is attacked, and per-token reconstruction is not covered; the theorems do not cover mixture-of-experts models; the zero-leakage construction assumes a single instance and batch-invariant kernels, and is not proven for multiple instances. Experiments are 1–4 instances, three kinds of GPU, and models up to 70B.
Experimental setupLlama-3.1-8B-Instruct、Qwen3-8B et al. · Azure LLM inference trace 2023 (conversation part)、BurstGPT trace et al. · one-shot advantage、false-positive rate et al.
Evaluated models
Llama-3.1-8B-InstructQwen3-8BDeepSeek-V2-LiteLlama-3.1-70B
Benchmarks
Azure LLM inference trace 2023 (conversation part)BurstGPT traceSQuAD (48 Wikipedia articles, 429 chunks, via LlamaIndex 0.14.25)
Metrics
one-shot advantagefalse-positive rateend-to-end accuracy
AI summaryand selection rationaleBowen Sun and Chaowei Xiao propose a timing side-channel attack against cross-tenant KV cache in LLM serving: a stepwise work-conserving scheduler fully transfers the time saved by a cache hit to each request queued after it, and an attacker can sandwich a probe request between two sets of their own listening requests and count the steps in which the listening requests complete to determine whether a piece of text has been cached by another tenant. On a single vLLM instance replaying Azure production traces at up to half capacity, a single probe can determine whether text of 256 tokens or more is cached with an advantage of at least 0.98; the attack can likewise read cache state on SGLang, Llama-3.1-70B, DeepSeek-V2-Lite, and production routed multi-instance deployments. Defenses that only hide the hit request are broken by a single probe on vLLM and SGLang (advantage 0.96 to 0.99), and random delays need to reach about 9 to 16 times the offset (0.15 to 4.9 seconds per response on average) to suppress the advantage to 0.1.

Bowen Sun and Chaowei Xiao propose a timing side-channel attack against cross-tenant KV cache in LLM serving: a stepwise work-conserving scheduler fully transfers the time saved by a cache hit to each request queued after it, and an attacker can sandwich a probe request between two sets of their own listening requests and count the steps in which the listening requests complete to determine whether a piece of text has been cached by another tenant. On a single vLLM instance replaying Azure production traces at up to half capacity, a single probe can determine whether text of 256 tokens or more is cached with an advantage of at least 0.98; the attack can likewise read cache state on SGLang, Llama-3.1-70B, DeepSeek-V2-Lite, and production routed multi-instance deployments. Defenses that only hide the hit request are broken by a single probe on vLLM and SGLang (advantage 0.96 to 0.99), and random delays need to reach about 9 to 16 times the offset (0.15 to 4.9 seconds per response on average) to suppress the advantage to 0.1.

Why it was selectedThe paper points out that the time saved by cache hits is fully transferred to subsequent requests, and defenses that only hide the hit request itself cannot block this kind of side-channel inference.

Paper analysis

6 questions; open one to read the full answer

  1. What problem does this paper attempt to solve?

    Whether hiding hits when KV caches are shared across tenants can both preserve reuse and prevent membership inference: the authors give a negative answer.

    Core question: an LLM serving engine sharing a prefix cache across tenants leaks "whether a given text has been sent by someone else"; how far can hiding hits go while preserving cross-tenant reuse.

    • Setting and importance: a cache hit skips prefill computation and makes the response faster, so a shared cache exposes whether other tenants have sent a given text, and existing attacks use this to detect sharing or recover prompts. Commercial APIs therefore restrict caching to organization/account granularity, and vLLM offers per-request salting, but this gives up cross-tenant reuse, and isolation stops at the account boundary.
    • Isolation gap below the account boundary: relays, resellers and applications serve multiple end users under one account, and the authors say they and others have observed production relays merging customer identities; teams, users and sessions within an account may also need to be isolated from one another, and finer-grained isolation gives up more reuse.
    • Shortcomings of existing defenses: the authors say the defenses they found all evaluate leakage as the gap between hit requests and miss requests, without analyzing where the resources saved by a hit flow (Appendix A cites each defense's threat model).
    • Core observation: hiding hits requires everything a tenant can observe afterward to be distributed as in the miss world; a step scheduler is work-conserving—it does not idle as long as there is waiting work—and copies the time saved by a hit in full to each request queued behind it, advancing each by the same amount (shift).
    • The paper proposes: a step-counting attack, a defense evaluation classified along three dimensions, a proof of a leakage upper bound of "visible benefit is signal," a zero-leakage construction and its cost, and a two-world replay audit method.
    • Threat model:
      • Goal: membership inference—determining whether a given candidate text is in the cache; the authors point out that if the mechanism reads content only through cache lookup, membership security bounds inference over all equal-length candidates.
      • Knowledge: the attacker knows the candidate text and the engine configuration (measurable with their own requests), and does not control or know other tenants' traffic.
      • Capability: a few ordinary accounts, in total within the provider's rate limits; they observe only the output event times, content, usage fields, status codes, headers and billing of their own requests.
      • Victim system: a victim account using a secret text (with fixed output length and stop condition); the provider's mechanism is an arbitrary admission, scheduling, caching, routing and release algorithm that can read all content and use identity.
  2. What related research exists?

    Related work falls into three categories: cache timing attacks, shared-queue timing channels, and defenses that hide hits; the authors state that no one has analyzed where the saved time goes.

    Timing attacks on LLM cache sharing

    • PromptPeek (NDSS 2025) and OptiLeak (2026)—send dummy requests before and after a probe and exploit longest-prefix-match scheduling to make hits return early, reconstructing the prompt token by token; Table 5 notes that they require 20 dummies plus 20 candidates per side, or a dummy batch exceeding the batch limit, respectively.
    • SpliceLeak (2026)—reads the step-wave pattern in the probe's own first-token time, targets non-prefix reuse, and needs at least 63 requests per token; Early Bird (2025)—reads the probe's own TTFT, uses 112.72 queries per token with a fine-tuned predictor, and targets system prompts and semantic caching.
    • InputSnatch (2026)—reads the probe's prefill time and reconstructs field by field, requiring 300–600 profilings; Gu et al. (ICML 2025)—audit the scope of cache sharing with 250 samples per test; Wang et al. (NeurIPS 2026)—read global KV occupancy from the token inter-arrival times of their own probes to carry out denial of service.

    Classic timing channels on shared queues

    • Loophole (2017) and Tramèr et al. (2020)—sandwich their own short tasks in a shared event loop or transaction and read out whether the victim is running and its workload.
    • Beams et al. (2021) and Kadloor, Kiyavash et al. (2013, 2016)—under FIFO and arbitrary work-conserving scheduling, packets queued behind the victim leak its bursts, and the leakage has been quantified; the authors point out that these channels read the victim's own activity, whereas this paper's listeners read the savings that another tenant's cached text brings to a probe.

    Defenses that hide hits and the privacy cost of caching

    • Hiding hit requests: Gu et al. propose delaying hits so they look like misses, InputSnatch suggests uniform response times, and PromptPeek proposes hiding KV activity from clients; the authors point out that none of the three was implemented, and the paper evaluates them with oracles.
    • Noise and rate limiting: KVGov (2026) adds 20 ms Gaussian noise and reports that it blocked PromptPeek's timing model in its simulation; SpliceLeak considers random padding but points out that the noise can be averaged out; Fonseca et al. (2026) quantize responses to the upper edge of time bins.
    • Narrowing sharing and post-hoc reaction: SafeKV, CachePrune, KVGov scope, Early Bird, SpliceDefense, PrivKV-Sched, CacheSolidarity, random thresholds (Harnik et al. 2010); classic defenses that "keep the savings inside the system" include predictive mitigation (2010, 2011), deterministic execution (2010), StopWatch (2014), VUsion (2017).
    • Privacy cost of caching and deduplication: client-side deduplication, named-data caching, differentially private cache sequences ([37]–[39]); the authors say this paper's bound instead measures the benefit the tenant itself obtains, and holds for a rate-limited attacker holding multiple accounts.

    Baselines and positioning: the paper does not implement baseline attacks for comparison; instead it groups published defenses along three dimensions—scope, release, reaction (Table 4)—and evaluates the closest published design or its oracle version for each group; the attack comparison is against the request counts and scheduling requirements reported for each attack in Table 5. The authors position this paper as: all defenses evaluate leakage through the probe's own response, and no one analyzes where the savings from a hit go; this paper reads the savings copied to subsequent requests, requiring only FCFS step scheduling.

  3. How does the paper address this problem?

    Probes are bracketed with listener requests, and the step at which they complete is counted to read out the replicated savings; defenses are then evaluated by classification along three dimensions, and theoretical bounds are given.

    Overall idea: hiding hits requires that everything a tenant can observe be identically distributed in the hit world and the miss world; the authors trace where the time saved by a hit goes and find that work-conserving step scheduling copies it in full to every request queued behind, so an attacker need only count at which step its own listener requests complete in order to read it out. The method includes the ruler attack construction, a three-dimensional defense classification, and leakage upper bounds and a zero-leakage construction.

    System model and security definition

    • The engine stores the KV cache in blocks (16 tokens per block in vLLM); a request hits the longest cached prefix of its prompt; a block written by another account that is hit is a cross-tenant hit. Mainstream engines schedule by step: each step first serves running requests, then admits waiting requests in arrival order; each step has a token budget B and a sequence-count limit K, and the scheduler is work-conserving.
    • The authors assume a step's duration depends only on its shape (number of tokens, number of sequences, context length of each sequence) plus noise independent of cache contents; the authors note this holds for dense models and does not hold for mixture-of-experts models.
    • Security definition (Definition 1): a mechanism is (β, ε)-secure if, for any workload, the total variation distance between the view of any set of accounts O within rate budget β under the original workload and under the workload with shared text replaced by random tokens is at most ε. A single-trial advantage ε*(β) corresponds to one membership probe.

    Conditions under which the attack holds

    • The attack sends one group of listeners before and one after the probe; the reading window must satisfy three window conditions: no other request enters service within the window, no request jumps the queue, and the engine has not reached sequence or memory limits and the victim's block is still cached.
    • The attacker sends the requests within the window as a short burst to make the first condition more likely to hold. Proposition 2 gives: when other requests arrive as a Poisson process at rate λ, the probability that no other request enters the window is e−λ w, where w is the window length; this gives a lower-bound formula for the required burst rate.
    • On the L40S, w0 is about 22 ms; at half load (2.27 requests/s), reading a 1,024-token secret requires sending 51 requests within about 76 ms at 655 requests/s, while the average rate remains low; one reading costs 20 to 176 requests and about 17,000 to 22,000 input tokens for a 4,096- to 256-token secret.

    Ruler construction and correctness

    • The four exits for the saving (Table 2): the hit request itself, requests queued behind, shared state, and hardware. Lemma 1 (copied saving) proves: on an engine with only the attacker's requests, after a hit of h tokens, (i) the engine always completes h more tokens in world H; (ii) when the probe occupies a step alone, every request behind it is later in world M by the same amount; (iii) when the probe and the first listener fill a step and subsequent requests are B tokens each, every request is later in world M by exactly one full step, for any 1 ≤ h ≤ B.
    • The ruler is sent in order: a head of fresh tokens, the pre-probe listener group, the probe (candidate text plus fresh tokens), the post-probe listener group, and a tail of at least B tokens; listeners have ℓ fresh tokens each, each request outputs one token, the whole ruler is sent as one burst, with a few milliseconds between groups. Listeners completing in the same step receive their first token at the same time; the attacker counts step boundaries by arrival group, compares boundary positions with the phase predicted for each world, or directly counts the steps between two boundaries.
    • Theorem 1 gives the correctness conditions: when the window conditions hold, each segment is long enough to fill each step, and the timestamp error is within a quarter of a full step interval, the decision rule is correct on every path, and does not need the probe's own response or absolute latency. The ruler as actually run: a 4,096-token secret uses 20 requests (listeners 560 tokens), 1,024 uses 52 (176 tokens), 256 uses 176 (48 tokens); with B = 2,048 the separation condition is met for hits of about 144 tokens or more.

    Defense classification and theoretical results

    • Three dimensions (Section 4.1): scope (which blocks can be hit across accounts), release (when each response is released), reaction (how to react after a suspected probe); Table 4 sorts the defenses found into four groups, and for each group evaluates the closest published design plus its strongest oracle version.
    • Theorem 3 (benefit is a signal): if a mechanism is (β, ε)-secure, then within the rate budget the change in the view account b obtains from the contents of V sharing accounts is at most Vε; when the single-trial advantage is at most ε, the change in view obtained from text x written by k other accounts is at most kε; when ε = 0, b gains nothing from others' content.
    • Proposition 4 (lockstep replica): on a single instance, the replica runs the scheduler treating every cross-tenant hit as a miss, with a fixed step duration D, and the engine skips cache work but releases all output on the replica's timing; under the premises that output tokens depend only on their own request (requiring batch-invariant kernels) and release is exact, the mechanism is (β, 0)-secure for any β.
    • Theorem 4 (price of padding): a mechanism that only pauses or suspends output work must, under saturated prefill, pad every step that may contain a potential hit to a pre-fixed width, and the release delay accumulates at least these widths; the cost grows with time rather than with the number of hits.
  4. What experiments did the paper conduct?

    The ruler attack is tested on vLLM/SGLang under multiple GPUs and multiple loads, and defenses are evaluated category by category: all can be read out or their cost grows with time.

    Experimental Setup

    • Systems under test: vLLM 0.26 (default scheduler, B = 2,048, K = 256 on L40S), SGLang 0.5.16 (4,096-token blocks), CacheSolidarity using the authors' vLLM 0.8.5; models are Llama-3.1-8B-Instruct, Qwen3-8B, Llama-3.1-70B (FP8, dual GPU), DeepSeek-V2-Lite (MoE), Qwen3.5-9B (hybrid attention, Appendix D).
    • GPUs: L40S 48GB, RTX PRO 6000 96GB, H100 NVL 94GB; context limit 16,384 tokens (32,768 for the latter two), 85% of GPU memory, seed 0.
    • Load: replay of the conversation portion of the Azure LLM inference trace 2023, at 0, 1/4, 1/2, 0.75, 0.9 of the rate that saturates the engine; half load is 2.27–2.93 requests/s, median in-flight requests 39–53; also a replay of the busiest 6 hours of BurstGPT (99,345 requests).
    • Metric: one-shot advantage (the probability of answering "cached" when the text is in the cache minus the probability when it is not), one probe per secret; each trial is a cache epoch, and the world is drawn with probability 1/2; Table 7 gives 30–172 trials per world for each result and 95%/90% intervals.
    • Repetition: the main load experiments were run three times—the first run's ruler lacked a tail (a design flaw), the second fixed the design before data collection, and the third froze all parameters and repeated with a new seed.
    • Defense evaluation method: defenses that act only on release timing (random delay, predictive mitigation) are replayed on unmodified engine logs in both worlds; CacheSolidarity runs the authors' public code.

    Main Results

    According to Table 3 (one-shot advantage under other deployments; 0.25/0.5 are load as a fraction of capacity) and the main text:

    Swipe horizontally to read the table

    SettingSecret length0.25 load0.5 load
    2 instances, cache affinity1,024 / 4,0960.88 / 0.980.87 / 0.94
    4 instances, cache affinity1,024 / 4,0960.71 / 0.900.60 / 0.98
    2 instances, round robin, single probe1,0240.450.45
    4 instances, round robin, single probe1,0240.020.11
    4 instances, round robin, one probe per instance4,0960.620.74
    RTX PRO 6000, 2 instances, affinity4,096 / 16,3840.90 / 0.930.75 / 0.78
    70B, single instance dual GPU4,096 / 16,3840.98 / 1.000.44 / 0.46
    H100, single instance4,096 / 16,3841.00 / 0.980.85 / 0.66
    • Single-instance Azure trace replay (second and third runs): from no load to half load, the ruler's advantage for reading 256-, 1,024-, and 4,096-token secrets is 0.980–1.000 (Figure 4); the authors state this corresponds to the abstract's "single-instance half-load single-probe advantage of at least 0.98."
    • The probe's own time to first token is already weak under load: for a 1,024-token secret the advantage is −0.03 to 0.19 at 1/4 and 1/2 load, and only the 4,096-token secret holds at 0.79–0.97; the authors state that the listener read out information that the probe's own timing no longer reveals.
    • Among trials where all log-checkable conditions held, 1,919/1,931 were judged correctly; when answering only "cached," 732/733 hit-world trials were correct and 1 of 782 miss-world trials was a false positive, giving a false positive rate below 0.61% at 95% confidence within half load.

    Defense Evaluation: Hiding Hit Requests and Random Delays

    • Hiding hit requests (the oracle of Gu et al., InputSnatch, PromptPeek): when scheduling is unchanged and only probes are made to follow the miss-world distribution, the listener reads out with a single probe at an advantage of 0.96–0.99 on vLLM and SGLang (Table 4); the authors state this is because the savings are still replicated to subsequent requests.
    • Random delay: under KVGov's 20 ms Gaussian noise, hits of 1,024 tokens and above and the alignment-constructed listener hold at 0.986–0.989; under load, the ruler stepped by cycle interval holds at 0.987–1.000 up to half load. Figure 6: independent exponential delays require a mean 9–16 times the shift to reduce the advantage to 0.1 (0.15–4.9 s per response); against an attacker comparing earliest release, 38 times is required.
    • Quantized release and rate limiting: the bin quantization of Fonseca et al. can be crossed by a listener sitting at the bin boundary; per-account rate limiting is ineffective because an attacker can spread requests across multiple accounts.

    Defense Evaluation: Narrowing Sharing, Reaction, and "Staying in the System"

    • Narrowing sharing: content that SafeKV, CachePrune, KVGov scope, Early Bird, SpliceDefense, and PrivKV-Sched each deem shareable (such as templates, retrieved documents, very long candidates) can still be read out per Section 3; the authors state that none of these defenses provides a guarantee against membership.
    • CacheSolidarity: after fixing the stale flag flaw in its public code, the first cross-tenant hit is read out by the ruler at 0.979–0.983; the block ownership flag itself becomes a new channel, read directly at 0.973, via the alignment listener at 0.980, and via the decoy at 0.981 (Table 4).
    • Staying in the system: after replaying predictive mitigation, the strongest predictor under the most conservative setting pushes 1,024/4,096-token secrets below 0.1 (95% upper confidence limits 0.074/0.028), but hit-world responses are 10–12 ms later than salted ones, and the bounds for 16/256-token alignment constructions are 0.17/0.32 (167/298 ms later); in the deterministic execution microbenchmark, 0% and 2% slack leave advantages of 0.98 and 0.55, and 5% slack is unreadable but makes each step 2.3% longer.
    • Theoretical results: Theorem 3 gives a gain ≤ kε; Proposition 4 gives a zero-leakage construction; Theorem 4 gives a padding cost that grows over time—the authors give the example that at a width of 0.13%–0.77% of a full step, padding offsets the savings of one 1,024-token hit within 0.4–50 s and continues to grow.

    Other Ablations and Analyses

    • The first run (ruler lacking a tail) read 256-token secrets at only 0.50, 0.87, 0.94 (no load, 1/4, 1/2 load), and the second and third runs recovered after the design was fixed.
    • At 0.75 capacity the advantage is 0.66–0.98, with failures stemming from eviction of victim blocks (at 94% cache occupancy, 26%–32% of hit-world trials missed); above 0.9 capacity the engine is overloaded.
    • BurstGPT trace (0.86–5.84 requests/s): advantage 0.980–1.000, with no misjudgments among 1,119 trials where all conditions held; on the MoE model DeepSeek-V2-Lite, 0.948–1.000 within half load.
    • End-to-end RAG case (LlamaIndex + SQuAD, 48 articles, 429 chunks): the attacker guesses which of 4 candidate chunks the victim retrieves first, with accuracy 97%, 95%, 85% at idle, 1/4, and 1/2 load (chance level 25%).
    • Window condition validation (Figure 5): in 58 of 61 settings the clean-window fraction is within ±0.1 of the predicted value e to the power −λw; the advantage never exceeds 2q − 1 by more than 0.05.
    • Behind a TLS reverse proxy: 1,024/4,096-token secrets give 0.882–0.975 within half load, but the false positive rate rises from 0.13% to 2.5%–2.9%, and the authors state they did not isolate the cause.
  5. What are some points that can be further explored?

    The authors list the boundaries of the attack and the theorems; experiments cover 1–4 instances, three kinds of GPU, and models up to 70B, and no deployed service was tested.

    Limitations and future directions noted by the authors

    • No deployed service was measured; its per-step budget, routing, batching and retention policy are unknown, and a larger budget lengthens the shortest readable secret (Section 5.2).
    • The attack reads only the second exit in Table 2; other exits are entered only through specific defenses (Section 5.2).
    • In hybrid attention models under a shared cache, requests with empty hits also cost 11–25 ms more; the two worlds do not overlap (Section 5.2, Appendix D).
    • When multiple instances share one KV pool, a hit can occur on any instance; the authors did not measure the ruler in that setting (Section 5.2).
    • The theorem does not cover mixture-of-experts models (which route tokens by content), but a few-step attack read a secret on one MoE model (Sections 2.1, 3.3).
    • The zero-leakage construction assumes a single instance and batch-invariant kernels (which vLLM 0.26 does not have), and is not proven for multiple instances; whether a provider can keep the benefit for tenants exceeding the rate budget while hiding it from others is an open question (Section 4.5).
    • Only membership is attacked: under load the theorem does not cover block-by-block prompt reconstruction, nor token-by-token reconstruction (Section 3.5).

    Scope of experiments

    • The models tested are Llama-3.1-8B-Instruct, Qwen3-8B, Llama-3.1-70B (FP8), DeepSeek-V2-Lite and Qwen3.5-9B, 5 in total; the engines are vLLM 0.26, SGLang 0.5.16 and the CacheSolidarity authors' vLLM 0.8.5 (Appendix C).
    • Deployment forms cover 1–4 instances, cache-affinity and round-robin routing, three GPUs (L40S, RTX PRO 6000, H100 NVL), a TLS proxy and dual API servers (Section 3.4, Appendix D).
    • Loads come from Azure traces (up to 0.9 capacity), BurstGPT traces and synthetic Poisson requests; main results use 30–172 trials per world (Table 7).
    • Defense evaluation covers the four groups in Table 4: hiding hit requests, random delay, narrowing sharing and reaction, and staying in the system; random delay and predictive mitigation are replayed from records, and CacheSolidarity runs the authors' code.
    • The paper reports no measurements against a real online API; request-side reordering on wide-area network paths is not measured (Section 3.5).
  6. Summarize the main content of the paper

    Copying the savings from a hit to subsequent requests defeats hiding hits; the authors give an attack, a defense evaluation, and a theoretical bound of "benefit is signal."

    A paper on attacks and theoretical analysis of cache side channels in multi-tenant LLM serving, with the conclusion: sharing a global cache while hiding hits cannot both preserve reuse and prevent membership inference.

    • Problem: prefix cache hits skip prefill, so a shared cache exposes whether someone else has sent a given text; per-account salting gives up cross-tenant reuse and isolation stops at the account, while existing defenses only make hit requests themselves look like misses.
    • Method: work-conserving step scheduling copies the time saved by a hit in full to each request queued behind it (shift); the attacker, within rate limits, brackets a probe with two groups of listeners that each return one token, issues them in one short burst, and reads the result by counting at which step the listeners complete, without relying on the probe's own response.
    • Attack results: on idle vLLM, advantage 0.985–0.989 with 4 requests; replaying Azure production traces to half load, single-probe advantage 0.980–1.000 for secrets of 256 tokens or more; under 2–4 instance cache-affinity routing, 0.90–0.98 for a 4,096-token secret; in an end-to-end RAG case, guessing the victim's retrieved chunk 97%/95%/85% (idle/1/4/1/2 load).
    • Defense evaluation: defenses that only hide hit requests are read out by a single probe on vLLM and SGLang (0.96–0.99); random delay needs a mean of about 10 times the shift or more to bring advantage down to 0.1; defenses that narrow sharing give no guarantee on membership; CacheSolidarity's chunk-owner flags become a new channel (0.973–0.981).
    • Theoretical results: the authors prove that the benefit a rate-limited tenant obtains from k other accounts' content is at most on the order of kε, and that under zero leakage only the provider retains the savings; zero leakage is achievable under premises such as a single instance and batch-invariant kernels, but the padding cost grows with time rather than with the number of hits.
    • The authors' recommendation: providers that need isolation should salt by trust domain, with the isolation key passed in by a layer that knows the boundaries; sharing across trust domains should be an opt-in option with an explicit cost, not described as a defense that hides hits.

Related papers

Read originalarxiv.org