SafeKV: Selective KV-Cache Sharing to Mitigate Timing Side-Channels in LLM Inference #

1. TL;DR #

Global prefix-cache sharing leaks user prompts via a TTFT timing channel (hit vs miss). SafeKV extends SGLang with an async 3-tier privacy classifier + a unified radix-tree that stores a per-block private_tag, defaulting blocks to Private and promoting to Shareable only after verification. It recovers most reuse benefit (up to 2.66× throughput vs full isolation) while an RDR safeguard revokes sharing under probe-like access.

2. 痛点 / 方法 / 结果 #

Q1 — 痛点. KV-cache prefix sharing is universal across vendors (OpenAI, DeepSeek, Anthropic, Gemini, vLLM, SGLang — see §5 Table 2) because it converts per-decode-step attention cost from $O(n^2)$ to $O(n)$ and slashes TTFT (context caching reportedly cuts TTFT up to 73%). But shared entries create a software-visible timing side channel: an attacker with only a standard API account issues crafted prefixes and measures TTFT; a cache-hit is faster than a miss, revealing whether some other tenant already used that prefix. Prior attacks (PromptPeek, EarlyBird, InputSnatch) reconstruct prompts at ~89–99% success for ~10² requests per token. The two "obvious" defenses both fail on the performance axis: (a) timing obfuscation (TTFT padding / jitter) must push hit-latency toward the heavy tail of the miss distribution to defeat two-sample tests, erasing the very TTFT savings that justified caching; (b) full per-user isolation (Cache-Partition) kills the side channel but forgoes cross-tenant reuse — the authors measure 8.3–38.9% TTFT inflation on Llama-2-70B. The missing middle ground: isolate only sensitive blocks, keep sharing everything else.

Q2 — 方法. SafeKV is a system-level co-design of privacy enforcement and cache management, built as an SGLang extension, structured around three principles: Privacy-Aware Reuse (visibility is first-class metadata in the cache index), Latency Transparency (classification is off the critical path; blocks are Private-by-default until verified), Scalable Lifecycle (one unified allocation/lookup/eviction policy over mixed-sensitivity blocks). Three subsystems: (1) an asynchronous three-tier hybrid detector — Tier-1 regex/blacklist rules (~0.2 ms), Tier-2 a lightweight Llama-3.2-1B semantic classifier (<125 ms), Tier-3 the in-service serving LLM for context-dependent hard cases (<8% of requests); (2) a runtime RDR safeguard that monitors per-block access dispersion and demotes Shareable→Private on probe-like bursts; (3) a unified radix-tree memory manager with per-node private_tag/creator_id, path compression of long private chains, and leaf-to-root progressive eviction. 核心技术壁垒: the enforcement is revocable and default-deny — visibility is a mutable bit on each radix node atomically flippable in both directions, so a static classifier false-negative is not a leak (the block was Private on insert and can be re-privatized by the RDR safeguard before/after promotion). This decouples "detector accuracy" from "leak probability" ($P_{\text{leak}} = \alpha_1 \alpha_{2|1} \alpha_{3|12}$ and bounded exposure window), which is the design's hardest-to-replicate insight.

Q3 — 结果. On 8×H20, across Phi-4 / Qwen3-30B/32B/235B / Llama-3.3-70B / DeepSeek-R1: avg defense success >94% (DeepSeek-R1 96.24–96.90%); ROC-AUC of the timing channel collapses to ≈0.5 once the RDR safeguard triggers and stays there under sustained probing; throughput 1.36–2.66× over Cache-Partition; TTFT overhead vs full isolation cut from 50.41%→11.74% (Qwen3-235B) and 118%→34.28% (DeepSeek-R1). Loses only in the System-Prompt scenario (slightly behind Shared-System-Prompt, which is hand-optimized for it) and Single-Request PII (no reuse, so all methods tie).

3. 架构 / 方法图 #

Paper's Figure 4 ("The Architecture Overview of SafeKV"). Two subsystems bolt onto a running serving stack: the Hybrid Detector (① Rule-Based Detector → General-Detector → Context-Aware Validation, fed by queues and a scheduler) runs off the serving path; the Unified KV-cache Index (③) with Cache Search Engine, Cache Allocator, Progressive Evictor and Path Compressor (④) holds the actual cache. The Access Monitor + RDR Safeguard (②) form the runtime feedback loop. Note that classification (①/②) is physically separated from the memory manager (③/④): the detector produces a visibility label, the index consumes it.

The unified index tree is the load-bearing data structure — one radix tree holds both private and shareable prefixes rather than two separate caches (which would duplicate common prefixes and complicate eviction):

Paper's Figure 6 ("The Unified Privacy/Shareable Cache Index Tree"). A shareable system-prompt path ("You are a helpful assistant / Hello! / Hi!") is reused across tenants, while private branches ("My Email is …", "My IP is …") are pinned to their creator and can be individually evicted. Reader should notice the visibility check happens per hop, so cross-tenant access is blocked even where a private branch shares an ancestor prefix with a shareable one.

Request/label lifecycle (paper describes this in prose across §4.1–§4.2.3; redrawn as a sequence diagram for clarity the raster figures do not provide):

The scheduler here is not a request batcher (SGLang owns that); it is a classification scheduler with a load-aware promotion threshold: under heavy load or probe alerts it tightens the boundary and promotes fewer blocks (favoring isolation); under normal load it relaxes to recover more reuse. Allocation unit is the SGLang radix-tree prefix node; cross-node communication is out of scope (single-node prototype).

4. 作者证明 #

SafeKV's formalization lives in §6 Security Analysis. It is not a throughput/latency performance model (no λ/μ/B queueing model) — it is a security argument, so the framework-specific "reproduce the cost model" ask is answered by 无形式化性能模型 — 性能仅实证; the formal content is the leakage bound below.

Notation table:

Leakage-surface property. A cross-tenant hit-timing signal can appear only when the block is Shareable:

$$\text{TTFT}(r_a) \in \{\,T_{\text{hit}} \text{ if } C(t_1,\dots,t_k)=\text{True},\; T_{\text{miss}} \text{ otherwise}\,\}$$

Physical meaning: forcing sensitive blocks to $C=\text{False}$ (Private) removes the hit branch entirely — there is no residual latency gap to pad, unlike obfuscation which only narrows it.

Leak probability. A sensitive block leaks only via a false-negative that survives all three tiers and gets promoted:

$$P_{\text{leak}} \triangleq P(C=\text{True}\mid S) = \alpha_1 \cdot \alpha_{2\mid 1} \cdot \alpha_{3\mid 12}$$

Why a product (not min/sum): the tiers are a serial escalation — a block reaches Tier-3 only if Tiers 1&2 both passed it, so the conditioning composes multiplicatively. This is the mathematical reason a hybrid pipeline of individually imperfect detectors yields a much smaller joint FN than any single tier.

Exposure control. Even a promoted false-negative is time-bounded:

$$\text{RDR}_b = \frac{u\_cnt}{hit\_cur}$$

Physical meaning / monotonicity: probe-heavy single-account traffic raises $hit\_cur$ faster than $u\_cnt$, driving RDR down; broad legitimate reuse keeps it up. The demotion rule is history-aware — low RDR is treated as an attack only when historical $u\_pre \approx 1$ (a block that was already broadly reused is presumed benign even if dispersion shifts). This makes the optimum a boundary decision (demote / keep) gated on a configurable threshold, not an interior optimum.

6-minimum checks:

1. Dimensional sanity — RDR is a dimensionless ratio (tenants / hits ∈ (0,1]); $P_{\text{leak}}$ is a product of probabilities ∈ [0,1]. ✓
2. Boundary — perfect detector — if all $\alpha \to 0$, $P_{\text{leak}} \to 0$: no promotion, degenerates to full isolation (max privacy, min reuse). ✓
3. Boundary — no detection — if all $\alpha \to 1$, $P_{\text{leak}} \to 1$: reduces to global SGLang sharing (max reuse, no privacy). ✓ The design spans exactly the interpolation between the two evaluated extremes.
4. RDR limit under Sybil — as an attacker spreads probes across $u\_cnt$ distinct accounts, RDR rises toward 1, evading demotion; the paper's history-gate ($u\_pre\approx1$) partially mitigates but does not eliminate this (see 全篇 surprise in §7). ✓ (identified as a gap)
5. Async-safety — Private-by-default means the window between insert and promotion is never a leak window (block is un-shareable throughout); only a promoted block can leak. ✓ consistent with equation.
6. Revocability — RDR demotion re-imposes $C=\text{False}$, returning to the safe branch of the TTFT equation, so leak duration ≤ (detector promotion time + one safeguard window). ✓

5. 实验与数据 #

Motivation — the isolation penalty being paid.



Paper's Figure 2. Full isolation (Cache-Partition) inflates TTFT by 2.3–8.9% on Llama-2-13B and 8.3–38.9% on Llama-2-70B versus global sharing, across ShareGPT / Multiturn / Multitask. This quantifies the cost SafeKV is trying to claw back and shows the penalty grows with model size (bigger prefill).

Detector accuracy — why three tiers.



Paper's Figure 9. On simple PII prompts (a) the 1B Tier-2 detector is competitive with or beats large in-service models; on complex/long-context prompts (b) Tier-2 accuracy collapses (~50%) while an in-service model like DeepSeek-R1 (Tier-3) lifts it above 90%. This is the empirical justification for escalating hard, context-dependent cases to the serving LLM rather than trusting the cheap detector everywhere.

Detector cost distribution — why async is affordable.



Paper's Figure 11. Across all backends, Tier-1 handles ~38–40% and Tier-2 ~55–58%, leaving Tier-3 with only ~1.8–7.2% (DeepSeek-R1 highest at 4.0%). Because >92% of requests never touch the expensive tier and the whole pipeline is off the critical path, Tier-3's long tail only delays promotion, never token generation.

Safeguard effectiveness — the security headline.



Paper's Figure 12 (window $W=5$s). Without the safeguard, hit/miss TTFT stays separable (AUC persistently high); with it enabled, once RDR drops below threshold the block is demoted and AUC collapses to ≈0.5 (random guessing) and stays there under continued probing. The flat post-trigger line is the key claim: the channel is closed, not merely weakened.

Performance recovery — the framework headline.



Paper's Figure 14. Single-Request PII (a): reuse is scarce, all methods tie. Multi-Turn (b): SafeKV tracks near global SGLang and far below Cache-Partition (overhead 50.41%→11.74% on Qwen3-235B; 118%→34.28% on DeepSeek-R1). System Prompt (c): SafeKV is strong but slightly behind the purpose-built Shared-System-Prompt baseline. This is the win/lose breakdown — SafeKV's advantage is concentrated in cross-tenant-reuse-rich workloads.

Detector latency detail.



Paper's Figure 10. Mean/P95/P99 detection latency; the tail is dominated by Tier-3 on the largest models (Figure 13 breaks this out), consistent with Table 7's Tier-1 ≈0.1 ms / Tier-2 ≈113–125 ms figures. Confirms Tier-1+2 are cheap enough to run inline in the async worker and only Tier-3 needs long-tail tolerance.

6. 论证链 #

#	步骤	依据
1	KV prefix sharing is universally deployed and gives large TTFT savings ($O(n^2)\to O(n)$, up to 73% TTFT cut).	§2.1, Table 2
2	Shared entries expose an API-visible hit/miss TTFT channel that reconstructs prompts (89–99% success).	§1, Table 1
3	Both cheap fixes fail: obfuscation erases the savings from step 1; full isolation forgoes cross-tenant reuse (up to 38.9% TTFT inflation).	§1, §2.3, Figure 2
4	Therefore classify blocks by sensitivity and isolate only sensitive ones, keeping the rest shareable.	§2.3, §4 principles
5	Do classification off the critical path, Private-by-default, so latency is untouched and a static miss is not an instant leak.	§4.1, §4.2.3, TTFT equation
6	Compose three imperfect detectors serially so joint FN = $\alpha_1\alpha_{2\mid1}\alpha_{3\mid12}$, with the expensive tier reserved for <8% of cases.	§4.2.1, §6, Figure 11
7	Store visibility as a mutable per-node bit in one unified radix tree, and monitor RDR to revoke sharing under probing, bounding the exposure window.	§4.3, §4.2.2, Figure 12
8	Net: recover most reuse benefit (up to 2.66× throughput) while collapsing the timing channel (AUC→0.5).	§7.4, §7.2, Figures 14/15

7. 实现 cross-reference #

Implemented as an SGLang extension (§5): the model execution path and request API are left unchanged, and privacy isolation is toggled by configuration — so a shop already running SGLang adopts it via a config flag plus the patched radix-cache manager, not a fork of the executor. Concretely (§5, §4.3):

• SGLang's radix-tree prefix cache is extended with per-block private_tag (0 shareable / 1 private) and creator_id; the visibility rule is checked at every lookup hop.
• Insert defaults private_tag=1; a dedicated off-path manager batches blocks through Tier-1/2/3 and atomically flips the bit on promotion.
• Path compression collapses a long private chain into a pri_root composite node holding an address vector with is_compressed=true; descendants stay in metadata marked after_compress=true linked back to pri_root. Progressive eviction uses a global epoch_counter, pruning inactive leaves first and freeing pri_root only after its whole address vector is released.



Paper's Figure 7. A private chain (nodes k, k+1, k+2 each with its own kv_addr) is compressed into one pri_root aggregating the three addresses; eviction then removes stale descendant addresses from the vector one at a time rather than tearing down the whole tenant branch. This is the 关键实现细节 that makes selective isolation scalable: private paths are single-tenant and tend to be long/linear, so without compression they would cause deep pointer-chasing, and without leaf-to-root eviction they would be reclaimed in coarse chunks that destroy still-useful prefix context.

Second 关键实现细节: the load-aware promotion threshold (§4.2.3) — the classification scheduler tightens the promote boundary under load or probe alerts and relaxes it under normal load, so the private/shareable split self-adjusts to the current risk/throughput trade-off rather than being a fixed policy.

The public SafeKV repository is not cited in the paper — treat the SGLang integration points above as the reference; the exact upstream commit/patch is [实现未公开].

Deployment context (实践上下文): serving-side, both prefill and decode (the defended signal is TTFT, i.e. prefill-dominated); single-node prototype (8×H20, no multi-node collective). It is a pure software framework (radix prefix cache + classifier + monitoring), so it does not trigger a software→hardware reverse implication — no persistent megakernel, cache-scope control, or interconnect-aware scheduling is involved. Easiest to adopt in stacks that already keep a structured KV index (radix-tree or block-based); the enforcement layer is model-agnostic and transferable, while the detector is the workload/policy-specific pluggable piece.