PrefixWall: Mitigating Prefix Cache Side Channels in Shared LLM Systems

A multi-tenant service with shared APC turns cache hits into a TTFT side channel that can be used to steal other people's prompts; PrefixWall isolates only suspicious prefixes.

• Scenario: The authors say APC has been used by OpenAI, DeepSeek, Google Gemini, MoonShot Kimi, vLLM, and SGLang to reuse the KV state for text that is identical at the start of a request. A hit is faster than a miss; the authors relay the literature, where in data such as ShareGPT, prefix sharing within the same user is 9–60%, and cross-user reuse is at most 30%.
• Limitations: Existing approaches include per-user isolation or disabling cross-request reuse, injecting noise, and SafeKV, which uses rules and an LLM to classify sensitive versus non-sensitive content before isolating. The authors believe the first two categories are costly or do not address the leakage source, and SafeKV's semantic analysis does not scale well, and misclassification leaves unprotected requests.
• Observation: The authors believe isolating the entire user is unnecessary; limiting shared prefixes that could enable attacks is sufficient. Exploitability depends on prefix length, model size, RPS, and hardware, and is not uniformly exploitable.
• Approach: PrefixWall monitors cross-user reuse, marks suspicious prefixes, and stops non-owners from continuing to reuse them in subsequent requests; isolation is not enabled when latency is indistinguishable.
• Threat model:
  • Goal: prompt stealing, reconstructing secret items in another person's prompt item by item.
  • Knowledge: The example in Section 2.3 assumes the template is known; Section 4 assumes probing a known shared prefix pre, changing only the last item.
  • Capability: Submit requests and measure TTFT; can be a single user or colluding users, probing can be interleaved with other requests; cannot directly read the cache. The example in Section 2.3 uses a classifier to distinguish hits from misses.
  • Victim system: A multi-tenant LLM service that shares prefix caches across users or security domains. A hit indicates the candidate matches a cached prefix.

论文按服务优化、侧信道和 APC 防御来组织相关工作，并写出与按用户隔离的差别。

计时泄漏与提示词窃取

• Song et al.（2025）：指出服务中缓存命中与未命中的时延差可用来重建提示词。论文称其增大每个缓存项 token 数的做法并不消除泄漏，只是要求一次猜中整项。
• InputSnatch 与 API 审计：Zheng et al.（2024）给出利用时延差窃取多租户输入的探测；Gu et al.（2025）讨论商业 API 中共享缓存在不能直接读内存时仍可能泄漏提示词。论文把二者同时列入按用户隔离。
• 其他泄漏面：Carlini 与 Nasr（2024）讨论推测解码等在加密信道上的远程计时泄漏。Wu et al.（2025）不靠时延，而观察 Longest Prefix Match 等调度下服务顺序的变化，逐 token 重建。

针对 APC 的防御

• 按用户隔离：Cache Partitioning（Pang et al., 2024）、InputSnatch、Auditing Prompt Caching 取消跨用户前缀命中。作者称这样能挡住泄漏，但放弃跨请求复用。
• 时延混淆：Carlini 与 Nasr 注入噪声，使命中与未命中的执行时间难以区分。作者指出这不处理跨安全域共享，会对正常请求加统一延迟，并援引历史上混淆可被放大微小时差。
• SafeKV（Chu et al., 2025）：用规则和 LLM 语义把请求分成敏感与非敏感，只隔离敏感请求。作者指出语义分析重、不利于高吞吐，误分类的请求仍可能泄漏。

服务优化与经典侧信道

• APC 与精确优化：论文称前缀共享用于长文档和多轮对话；另列举分页 KV 管理、调度、prefill 与 decode 拆分，目标是降延迟而不改结果。
• 近似优化：修改注意力、复用或压缩 KV 被作者称为以精度换速度，并非所有场景可接受。这些方法不是本文实验基线。
• 经典侧信道：论文用 CPU cache、DRAM、分支预测、TLB，以及浏览器、操作系统和协议中的优化泄漏，类比性能优化带来的资源用量差。

基线与本文位置

• 基线：Prefix Caching 是开启 APC、无隔离的 vLLM；User Cache Isolation 由作者按所引工作实现，给每个用户请求前加一个唯一 token。指标为 TTFT 与 cache hit rate，负载来自 ShareGPT。
• 位置：作者称不必隔离整个用户，跟踪跨用户复用并只隔离可疑前缀即可，且不需要语义或事先知道敏感内容。Table 1 用勾叉把隔离类标为不能复用且 TTFT 不高，把混淆和 SafeKV 标为能复用但 TTFT 不高，把 PrefixWall 标为两者都有；这是归类，不是测量值。

PrefixWall adds metadata to the prefix cache on the serving path, with a Detector cutting off cross-user continuation by ownership and an Activator deciding when isolation is enabled.

Goals and Cache Entries

• Three goals: Block timing attacks on APC; preserve cache reuse and inference speed across different workloads and models; operate in real time with low overhead, without requiring semantic analysis or prior knowledge of sensitive content, and integrate into existing serving systems.
• Metadata: Each entry adds an OwnerID (the first writer, unchanged after assignment) and an AttackFlag (set when multiple users reuse the entry, requiring isolation). The design section states that each entry adds only a few bytes and does not change the tensor layout.
• Miss: A new entry is created, OwnerID is set to the current user, and AttackFlag is cleared. The authors claim that a miss does not leak timing information, so no isolation action is taken.

Detector

• Unmarked hit: If the requester is the owner, reuse directly. If the owner differs, mark the entry for isolation; non-owners can no longer continue reusing along that prefix, and subsequent tokens create new cache entries.
• Marked hit: If the next entry belongs to the requester, continue reusing; otherwise stop at the marked point and recompute the remainder through the LLM. The result is a partial hit, and the shared prefix remains reusable.
• Owner exception: The authors emphasize that the owner can always extend along their own path, even if a node is marked, to avoid slowing normal requests. Figure 5 illustrates branching with three users over consecutive time steps, without looking at prompt semantics.

Activator

• When to enable: Section 2.2 states that the latency difference grows with longer shared prefixes and larger models, is masked by batching and queuing at higher RPS, and hardware also affects measurement. Always-on over-protects under high load.
• Decision: Each request uses recent sliding-window TTFT samples to estimate the KDE overlap between hits and misses. When the overlap exceeds an administrator threshold θ, selective isolation is disabled, but metadata is still updated; below θ, detection and isolation are enabled. The paper does not give the window length.
• Threshold: Left to the administrator, and should reflect the point where hits and misses are statistically indistinguishable, as well as the trade-off between security and overhead.

Guarantees and Implementation

• Covered probes: For pre·secret owned by user u, if pre contains at least one entry, and the last entry of pre is marked, or the first entry of the probe is not equal to secret, then when other users execute the sequence, the changed entries are all misses. Collusion, interleaved disjoint requests, and the initial cache state do not change this guarantee.
• Not covered: When there is no markable parent node, theft of the first entry of a prompt is not protected; on an unmarked prefix, a first-try correct guess of secret is also not protected. The authors claim that treating all prefixes as marked would degrade to user-level isolation.
• Implementation: Based on the V1 engine of vLLM 0.8.5. Extends KVCacheBlock; the Detector updates metadata in the Scheduler before scheduling; the Activator computes in the asynchronous execution layer. The implementation section uses field names owner_id and attacker_flag, with a footnote writing under_attack. The authors plan to open-source the code.

Comparison of unprotected APC, PrefixWall, and user-level isolation on vLLM; the text gives summary numbers, not a per-model table.

Experimental Setup

• Platform: NVIDIA A100 (40 GB), vLLM 0.8.5, block size 16, V1 engine. Section 5.2 sets the processing rate to 1 request per second and states that the side channel is easy to exploit at this rate; the Detector is always on. Arrival times are otherwise described as a Poisson distribution. The paper does not report the number of repetitions.
• Models: gemma-3-4b-it, llava-onevision-qwen2-0.5b-ov-hf, llava-onevision-qwen2-7b-ov-chat-hf, Llama-2-7b-chat-hf, Llama-2-13b-chat-hf, Qwen2-VL-2B-Instruct, Qwen2.5-VL-3B-Instruct, Qwen2-VL-7B-Instruct, Qwen2.5-VL-7B-Instruct. Parameter counts range from 0.5B to 13B; Table 2 gives model memory usage and remaining KV cache.
• Workload: 5 groups constructed from ShareGPT, each with 10 users and 100 requests per user. BERT marks sensitive words at different positions and replaces them with placeholders, then fills in different candidates to vary within-user and between-user overlap. One user probes popular templates as in Section 4. The averages in Figure 7 exclude this attacker.
• Baselines: Prefix Caching is vLLM with APC enabled; User Cache Isolation prepends a unique user token to each request. Section 5 does not report measurements for SafeKV or noise obfuscation.
• Metrics: TTFT and cache hit rate. No LLM judge; attacker experiments directly look for spikes in these two metrics.

Main Results

Per-model bar heights for the nine models are not listed in the text, so no per-model rows are filled in. The table below only includes summaries written in the text.

Comparison	Value	Source
Cache reuse relative to user-level isolation	Authors claim up to 70%	Abstract, contributions
Inference latency relative to user-level isolation	Authors claim 30% lower	Abstract, contributions
Per-model TTFT relative to Prefix Caching	Authors claim within 6%	Figure 8 text
Average across five workloads relative to Prefix Caching	Authors claim approximately 5–10%	Figure 7 text
TTFT difference between Llama-2-13b and Prefix Caching	2 ms	Figure 8 text
User-level isolation hit rate on Workload 5	0	Figure 7 text

• Workload shape: Workload 1 has only within-user reuse; all three have comparable hit rates and TTFT. Workload 5 has only between-user reuse; user-level isolation has a hit rate of 0 and the highest TTFT; the authors claim PrefixWall remains close to Prefix Caching. On average, the authors claim PrefixWall has higher hit rate and lower TTFT, but still worse than unprotected APC.
• Models: The authors claim that as models get larger, the gap between unprotected and user isolation grows, and it varies by model family. The KV cache for Llama-2-13b-chat-hf is 15.7 GB in Table 2; the authors claim it is almost only half of the other models, so eviction is more frequent and misses are more numerous.
• Two sets of numbers: 70% and 30% are relative to user-level isolation and are not broken down by workload in Section 5.2; 5–10% and 6% are relative to Prefix Caching. The main experiment is not the setting with the Activator turning off isolation.

Attacker-Observable Results

• Setup: A secret sits in the middle of a normal user's public prompt; the attacker sends 20 requests with different candidate values, and the 9th guesses correctly. The victim request runs first, then Figure 9 is measured on both systems.
• Unprotected: The authors claim that except for the 9th request, hit rate and TTFT are stable; the 9th request reaches a 100% hit rate, and they claim this corresponds to a TTFT drop. The same passage also writes that both hit rate and TTFT show a spike. The curve values in the figure are not listed in the text.
• PrefixWall: The authors claim that hit rate and TTFT are uniform across all 20 requests, with no spike at the 9th, so on this workload TTFT cannot indicate which request matched. The secret is in the middle, and the correct guess is not the first, so it does not correspond to the two uncovered cases in Section 4.

When the Side Channel Is Distinguishable

• What was measured: Figure 2 compares hit (red) and miss (blue) for LLava-0.5B, Qwen2.5-3B, Gemma3-4B, and Llama2-7B at RPS=1, and measures Llama-13B at RPS of 10, 20, 30, 40 with prefixes of 100–500 tokens. Figure 3 summarizes 5 models, prefix lengths, and request rates using KDE overlap.
• Results: Except for the smallest LLava-0.5B, the authors claim that beyond a certain prefix length the TTFT difference becomes noticeable, and the gap grows with longer prefixes and larger models; the difference for LLava-0.5B is negligible. The gap narrows as RPS increases. The Figure 3 text states that overlap decreases as prefixes lengthen, more clearly for LLaMA-13B and LLaMA-7B, while Llava-0.5B remains high; at high RPS the models are almost indistinguishable. The figure has no per-point readings.
• Authors' interpretation: Exploitability is jointly determined by prefix length, model size, workload, and hardware; under high load, batching and queuing mask cache latency. The Figure 3 legend writes Gemma-4B, LLama2-7B, etc., which do not exactly match the abbreviations in Table 2.

Activation Threshold

• Setup: Llama2-13B, Workload 4 (which the authors claim has high reuse), KDE threshold from 0% to 100%. Figure 10 marks Prefix Caching, User Cache Isolation, and PrefixWall with the Detector always on.
• Results: Near a threshold of 0%, the authors claim performance is comparable to Prefix Caching because selective isolation is almost always off. Near 100%, hit rate and performance approach selective isolation always on. At all listed KDE values, the authors claim it is better than user-level isolation. Specific TTFT and hit rate values for intermediate thresholds are not given in the text.

Other Ablations and Analyses

• Detector: 0.004 ms/request, 32 bytes/cache entry (Table 3); the design section also states metadata is only a few bytes.
• Activator: 0.003 ms, 16 bytes per request within the window (Table 3).
• Combined: the authors write an average of 0.007 ms per request (Section 5.2.4).
• Workload 2: within-user reuse remains high, between-user is moderate; user isolation has lower hit rate and higher TTFT, while PrefixWall is close to Prefix Caching (Figure 7, no specific millisecond values).
• A footnote attributes the 32 bytes to two int objects in Python and counts the Activator's float as 16 bytes.
• Section 5.2 does not report main results with only the Activator on and the Detector off.

The safety analysis states that two types of probing are not covered by the guarantee, and that activation thresholds also determine whether defenses are enabled.

Limitations and future directions noted by the authors

• Guarantee is not unconditional: Section 4 states that probes are only blocked under given conditions, and lists two uncovered cases; the authors say this is a deliberate choice in the trade-off between safety and performance.
• First item: Without a non-empty prefix, there is no markable parent node, so theft targeting the first item of a prompt is not protected. The authors argue that even for the largest model considered, the hit and miss distributions for a single item still overlap (Figure 2d), making exploitation harder; they also state that real deployments often only enable caching for longer prefixes, e.g., OpenAI reuses only for prompts over 1024 tokens.
• First guess: On an unmarked pre·secret, a correct guess on the first try is not protected. The authors argue this becomes a problem when the secret space is small, and the risk decreases with a larger space; treating everything as marked would revert to the overhead of user-level isolation.
• Threshold too low: Section 4 states that if the overlap threshold is set too low, an attacker may still exploit the APC latency difference while the system does not enable isolation.
• Traffic shaping: The same section states that an attacker may use burst requests to raise the KDE overlap and disable isolation, or lower the request rate to trigger isolation. The authors then state that the sliding window requires sustained conditions, decisions use system-level rather than per-user measurements, and short-term manipulation is not easy to succeed; marks are still updated when isolation is off, so cache metadata cannot be rewritten via thresholds.
• Future directions: The paper has no dedicated Future Work section, and Section 7 does not list future research directions either.

Experimental coverage

• Performance experiments were run on one NVIDIA A100 40GB with vLLM 0.8.5, using the 9 models in Table 2, with parameter sizes from 0.5B to 13B.
• The workload consists of 5 groups constructed from ShareGPT, each with 10 users × 100 requests; in Section 5.2, RPS=1 and the Detector is always on. The paper does not report the number of repetitions, the Activator sliding window length, or the θ used in the main experiments.
• Experimental baselines are Prefix Caching and the authors' implementation of User Cache Isolation. Table 1 also lists Remote's latency obfuscation and SafeKV; the paper does not report TTFT or hit rates for these two.
• The attacker empirical study uses a separate workload: the secret is in the middle of the prompt, 20 probes, and the guess succeeds on the 9th; it observes hit rate and TTFT, not a classifier or ASR. Section 2.2 lists hardware as an exploitability factor, but the main text does not report comparison numbers on a second hardware platform.
• The threshold sweep uses Llama2-13B and Workload 4, with KDE from 0% to 100%. The models in Figure 2 and Figure 3 are LLava-0.5B, Qwen2.5-3B, Gemma3-4B, Llama2-7B, and Llama2-13B, and the written prefix lengths and RPS are given.

PrefixWall is a system-level defense on multi-tenant LLM services that limits the TTFT side channel of Automatic Prefix Caching while preserving prefix reuse.

• Problem: Shared prefix caching makes hits faster than misses. Attackers submit probes and measure TTFT, allowing them to reconstruct secrets in other users' prompts item by item. The authors argue that per-user isolation, adding noise, or semantic classification would cause non-attacking users to lose APC benefits or leave misclassified requests.
• Method: Each cache entry records its first owner; when other users reuse an entry, it is marked as isolated. The owner can still extend along the original path, while non-owners stop reusing at the marked point and recompute subsequent tokens. Whether to perform this check depends on whether the KDE overlap of recent hit and miss TTFTs is below an administrator threshold θ. The implementation is based on vLLM 0.8.5. The authors plan to open-source it. In Section 7, there is a system name written as CacheSentinel.
• Results: The authors claim up to 70% higher cache reuse and 30% lower inference latency compared to user-level isolation. The text also states that across five ShareGPT workloads, the average difference from unprotected Prefix Caching is approximately 5–10%, and TTFT across nine models is within 6%; on Llama-2-13b, the difference is 2 ms. The Detector and Activator together average 0.007 ms per request. In 20 probes, the unprotected system reaches a 100% hit rate on the 9th successful guess, while PrefixWall shows no corresponding spike.
• Conclusion: The authors claim that without isolating entire users, cutting off cross-user continuation of suspicious prefixes can block the probes covered by their analysis and avoid disabling sharing entirely. The guarantee does not cover the first entry on a never-before-seen prefix, nor a single guess on an unmarked prefix; if the threshold is too low, isolation may not be enabled.