CachedAttention / AttentionStore — L2 #

1. TL;DR #

Multi-turn LLM serving discards each session's KV cache when idle, then recomputes it on the next turn — up to 99% of prefill cost is this wasted recompute. CachedAttention keeps KV in a tiered DRAM+SSD store (AttentionStore), overlaps load/save with compute, prefetches/evicts using the scheduler's job queue, and decouples RoPE so truncated caches stay valid. Result: TTFT ↓ up to 87%, prefill throughput ↑ up to 7.8×, cost ↓ up to 70%.

2. Q1 / Q2 / Q3 #

Q1 — 痛点 (the pain) #

In a multi-turn conversation, turn $N{+}1$ must attend over the full history $q_1 a_1 q_2 a_2 \dots q_N a_N q_{N+1}$. Current engines store KV only in HBM during an active turn, then discard it when the session goes idle to free HBM for other sessions. When the user replies, the engine recomputes the entire historical KV from scratch. The waste grows linearly with turn count:

• ShareGPT: 73% of conversations are multi-turn; 30% exceed 4K tokens (§2.3).
• As turns accumulate, historical tokens become >99% of a new turn's prompt, so up to 99% of prefill time (= TTFT) is pure recompute (§2.3, Fig 4).

The naive fix — keep KV in HBM — fails on capacity. On 4×A100 running LLaMA-65B, KV generates at ~13.9 GB/s and fills the 190 GB of free HBM in 14 seconds; spilling to 512 GB host memory buys <1 minute (§2.4). So the KV must live on slower, larger tiers, which reintroduces access latency on the inference critical path.

System scope (framework §1 pin-down):

• Stage coverage: primarily the prefill stage of reactivated sessions (it turns full-history prefill into new-token-only prefill); it also indirectly shortens decode under continuous batching because a shorter prefill unblocks queued decode jobs sooner.
• Serving, not training; continuous batching enabled (Orca-style, [57]).
• Parallelism axes: TP only (LLaMA-13B on 2 GPUs, 65B/70B/Falcon-40B on 4 GPUs). No PP/EP/DP/SP claimed — it owns the KV-cache lifecycle, delegates model execution to a HF-Transformers executor.
• Deployment mode: single-node, GPU + host DRAM + local SSD; prefill and decode co-located (not disaggregated).

Q2 — 方法 (the method) #

CachedAttention = a KV-reuse attention mechanism + AttentionStore, a hierarchical KV caching system spanning HBM ↔ DRAM ↔ SSD. Four sub-techniques, each answering one challenge:

1. Overlapped access (Challenge 1: load/save latency on critical path):
2. Layer-wise pre-loading — while the GPU computes layer $i$, the read stream loads layer $i{+}1$'s KV; a sized read buffer lets pre-loading start before the previous job frees its execution buffer (§3.2.1).
3. Asynchronous saving — write KV back layer-by-layer, overlapping prefill-phase KV saving with the decode phase; a write buffer absorbs KV not yet flushed when decode ends (§3.2.2).
4. Hierarchical placement (Challenges 2&3: capacity + slow disks):
5. Scheduler-aware fetching — a look-ahead window over the job queue pre-fetches soon-to-be-used KV from SSD→DRAM (§3.3.1).
6. Scheduler-aware eviction — evicts by future access info from the job queue, not LRU/FIFO history; session-granular (§3.3.2).
7. Decoupled truncation (Challenge 4: context-overflow invalidation):
8. Cache KV before RoPE is applied; re-embed positions on load, so truncated KV stays reusable (§3.4).

核心技术壁垒 (the single hardest-to-replicate insight): the scheduler-aware placement, i.e. converting the inference job scheduler's queue into an oracle of future KV accesses and driving both prefetch (SSD→DRAM) and eviction (protect items inside the look-ahead window) from it. This is what makes tiered offloading actually win: it moves >99.6% of cache hits into DRAM while LRU/FIFO leave essentially all hits on slow disk (~0.5% DRAM). Belady-style future knowledge is normally unavailable to a cache — CachedAttention manufactures it from the serving scheduler, which is a system-integration trick, not a standalone algorithm. Everything else (layer-wise overlap, RoPE decoupling) is individually replicable; the scheduler-cache coupling is the differentiator.

Q3 — 结果 (the result) #

Vs. recomputation (RE) baseline on 9K ShareGPT conversations (~52K turns), 4×A100:

• TTFT ↓ 85% / 61% / 87% / 86% (LLaMA-13B / 65B / 70B / Falcon-40B).
• Prefill throughput ↑ 6.8× / 2.6× / 7.8× / 7.2×.
• End-to-end GPU time ↓ (speedup) 4.0× / 1.9× / 3.3× / 3.4×.
• Cost ↓ 70% / 43% / 66% / 68%; storage is only 9–16.4% of total cost.
• Hit rate 86% / 71% / 89% / 90%, with >99.6% of hits in DRAM.
• Quality: decoupled truncation matches token-truncation within PPL <0.02 and within ~1% accuracy; naive coupled truncation (NKVT) collapses to PPL >10³.

---

3. 架构 / 方法图 #

System architecture #



Paper's Figure 5 (caption: "The system architecture of CachedAttention"). This is the load-bearing diagram: it shows the LLM inference engine on the GPU, the AttentionStore spanning host DRAM and SSDs, and the data paths in/out of HBM. The read/write streams (layer-wise preload, async save) sit on the HBM↔DRAM edge; the fetch/evict logic sits on the DRAM↔SSD edge; the job scheduler feeds hints to both. Note the KV manager is a first-class box separate from the scheduler — the scheduler decides what runs next, the KV manager decides where each session's KV physically lives.

The core mechanism: reuse vs recompute #



Paper's Figure 3 (caption: "Comparison of recomputation and CachedAttention"). Conventional attention re-prefills the whole prompt each turn; CachedAttention prefills only $q_3$ (the new turn) and loads the cached KV of $q_1 a_1 q_2 a_2$. This is the entire economic argument in one picture — the reused fraction is exactly the >99% historical-token fraction from Q1.

Request / KV lifecycle #

The scheduler → KV-manager → executor interaction is a sequence, so a redraw adds structural clarity the raster diagrams do not:

sequenceDiagram participant Sched as Job Scheduler (queue) participant KVM as KV Manager (AttentionStore) participant SSD as SSD tier participant DRAM as DRAM tier participant GPU as GPU (HBM + exec) Sched->>KVM: look-ahead window: jobs 2..k coming KVM->>SSD: prefetch KV of hit-in-disk jobs SSD-->>DRAM: migrate session KV (IO threads) Sched->>GPU: dispatch job (its KV now in DRAM) DRAM-->>GPU: layer-wise pre-load KV -> HBM read buffer GPU->>GPU: prefill new tokens (overlaps with load) GPU-->>DRAM: async save new KV (write buffer) KVM->>KVM: evict tail-of-window session DRAM->SSD if low free space

The queue is scanned two ways: a short prefetch window ($L_{pw}$ jobs, bounded by DRAM) drags KV up; a long eviction window ($L_{ew}$ jobs, bounded by DRAM+SSD) protects imminent sessions from being evicted, prioritizing the tail for eviction.

KV / memory manager details #

• Allocation unit: block-based storage for both DRAM and SSD, like vLLM's paged KV [21]; an internal allocator does on-demand alloc/dealloc.
• Fetch/evict granularity: one conversation session = one item — "the KV cache in the same session is either all used or none of it" (§3.3.2). So there is no intra-session fragmentation at the reuse layer.
• Cross-tier transport: HBM↔DRAM over PCIe Gen4 ×16 (~26 GB/s effective); DRAM↔SSD via separate IO threads. No cross-node collective — this is a single-node system.

---

4. 作者证明 #

无统一形式化模型 — 局部工程模型 + 实证为主. The paper has no single throughput/latency optimization model; instead it provides several local sizing formulas (buffer size, window lengths, capacity) plus a capacity model, and validates behavior empirically. Below is the notation table and the load-bearing equations, followed by the 6 minimum checks.

Notation table #

Symbol	Meaning
$X=[x_1,\dots,x_s]$	input token list, seq length $s$
$W_Q,W_K,W_V$	per-layer QKV projection weights
$Q,K,V$	query / key / value tensors (K,V become the cache)
$d_K$	key-vector dimension (attention scaling)
$T_{load}$	per-token KV access (transfer) time
$T_{pref}$	per-token prefill compute time
$L_{hist}$	# historical tokens in a session
$L_{new}$	# new input tokens in the turn
$B$	PCIe bandwidth
$S_{buf}$	read-buffer size (bytes)
$C_{mem}$	host-memory capacity available for prefetch
$C_{disk}$	total available disk capacity
$S_{kv}$	average per-session KV size
$L_{pw}$	look-ahead prefetch window length (jobs)
$L_{ew}$	look-ahead eviction window length (jobs)
$DSpUT$	distinct sessions served per unit time
$CCpS$	max KV capacity per session (= max context × per-token KV)
$CCpUT$	required max cache capacity per unit time

Load-bearing equations + physical meaning #

QKV projection & attention (why a cache exists at all):

$$Q=W_{Q}X,\quad K=W_{K}X,\quad V=W_{V}X$$

$$\mathrm{Attention}(Q,K,V)=\mathrm{softmax}\!\left(\frac{QK^{\top}}{\sqrt{d_{K}}}\right)V$$

Every token attends over all prior tokens' $K,V$; that dependency is exactly why the full historical KV must be present, hence caching is worthwhile.

Imperfect-overlap condition — overlap fails when transfer of the historical KV outruns the partial (new-token) prefill compute:

$$T_{load}\,L_{hist} > T_{pref}\,L_{new}$$

Physical meaning: the LHS is total bytes-time to fetch history, the RHS is the compute time available to hide it. It uses $L_{new}$ (not $L_{hist}$) on the RHS because CachedAttention only computes the new tokens — that asymmetry is precisely why long history + short new turn is the hard regime.

Read-buffer size — bytes that arrive during the un-hideable gap:

$$S_{buf}=B\left(T_{load}\,L_{hist}-T_{pref}\,L_{new}\right)$$

The parenthesized term is the time gap; multiplying by bandwidth $B$ converts it to the bytes the buffer must pre-stage so loading can start early.

Prefetch window (bounded by DRAM) and eviction window (bounded by DRAM+SSD):

$$L_{pw}=\frac{C_{mem}}{S_{kv}} \qquad L_{ew}=\frac{C_{mem}+C_{disk}}{S_{kv}}$$

Both divide capacity by per-session KV size to convert bytes into number of look-ahead jobs. $L_{ew}>L_{pw}$ because eviction reasons about the whole store (DRAM+SSD), while prefetch only stages into DRAM.

Capacity sizing:

$$CCpUT = DSpUT \cdot CCpS$$

Physical meaning: to guarantee a hit for every distinct session within a TTL window, hold (sessions-per-unit-time) × (per-session full-window KV). Configuring $CCpUT$ gives ~100% hit ignoring new arrivals.

6 minimum checks #

1. Denominator/exclusion check — Eq. 3/4 put $L_{new}$ (not $L_{hist}$) on the compute side because reuse means only new tokens are prefilled; this is internally consistent with the reuse premise. ✔
2. Monotonicity / boundary — $S_{buf}$ is increasing in $L_{hist}$ and decreasing in $L_{new}$; the optimum buffer is at the boundary where $S_{buf}=0$ (perfect overlap when $T_{load}L_{hist}\le T_{pref}L_{new}$). Beyond that, buffer grows linearly — no interior optimum. ✔
3. First-order plug-in (overlap) — §2.4 gives $T_{load}$: 2K-token KV = 5 GB / 26 GB/s ≈ 192 ms; $T_{pref}$ for 2K ≈ 360 ms. For a reactivated turn with $L_{hist}\gg L_{new}$, $T_{load}L_{hist}$ dominates → Eq. 3 predicts imperfect overlap → a read buffer is required. The §4.3.2 ablation confirms: PL-B0 gives 35% reduction, PF-B15 gives 61% (perfect overlap). ✔
4. First-order plug-in (capacity) — RCC/CCpUT = 0.25 → 98% hit (§4.3.6). Sub-linear: you need only ¼ of the "ideal" capacity because item hotness is skewed. The formula's 100% claim is the upper bound, matching the measured saturation. ✔
5. Window ordering — $L_{ew} \ge L_{pw}$ always (since $C_{disk}\ge 0$); the worked example uses $L_{pw}=2$, $L_{ew}=6$ (§3.3.1/§3.3.2), consistent with DRAM ⊂ DRAM+SSD. ✔
6. Unit sanity — $L_{pw},L_{ew}$ are (bytes)/(bytes/session) = sessions ✔; $S_{buf}$ = (bytes/s)·(s) = bytes ✔; $CCpUT$ = (sessions/time)·(bytes/session) = bytes/time ✔.

What a unified model would have clarified: there is no closed-form for end-to-end throughput as a function of (hit rate, tier bandwidths, arrival rate). The reported speedups are measured, not derived — so the sensitivity to PCIe/SSD bandwidth or to arrival rate (§4.3.8) is shown only by sweep, not predicted.

---

5. 实验与数据 #

Setup: 4×A100-80GB, 128 GB DRAM, 10 TB SSD, PCIe Gen4; FP16 activations; continuous batching; ShareGPT with Poisson arrivals ($\lambda=1.0$); baseline = recomputation (RE) with 0.5 truncation ratio.

Motivation evidence #



Paper's Figure 4 (caption: "Recomputation inefficiencies. (a) Average numbers of historical and new tokens ... (b) GPU time for prefilling all tokens and only new input tokens ... Mistral-7B on 1 A100"). This quantifies the premise: as turns grow, historical tokens dominate (>99%), and prefilling all tokens vs new-only diverges sharply — the gap is exactly the recompute CachedAttention deletes.

Overlapped-access ablation #



Paper's Figure 7 (caption: "(a) Layer-wise pre-loading with imperfect overlapping. (b) Perfect pre-loading with a customized larger buffer"). When per-layer KV load time exceeds per-layer compute (the $T_{load}L_{hist}>T_{pref}L_{new}$ regime), gaps appear between layers (a); a larger read buffer lets pre-loading run ahead and close them (b). This is the visual justification for Eq. 4.



Paper's Figure 19 (caption: "CA with no pre-loading v.s. CA pre-loading with various buffer sizes"). PL-B0 (no buffer) already cuts prefill time 35% vs NO-PL; PF-B15 reaches 61% (perfect overlap). The reader should notice diminishing returns after the buffer covers the gap — beyond B15 there is nothing left to hide.

Scheduler-aware placement ablation (the load-bearing result) #



Paper's Figure 21 (caption: "Comparison of the eviction algorithms under various storage settings. (a) Impact on hit rate. (b) Impact on GPU time"). At 128G/10T, CA hits 86% vs LRU 58% / FIFO 48%, up to 2.7× GPU-time speedup. The decisive detail is the breakdown: CA lands >99.6% of hits in DRAM while LRU/FIFO get ~0.5% — future-awareness doesn't just raise the hit rate, it relocates hits off the slow tier. This is the core 技术壁垒 made empirical.

Storage-tier ablation #



Paper's Figure 24 (caption: "Performance under various caching configurations"). HBM-only ≈ 0% hit (capacity-starved); HBM+DRAM only 1.7–19.1%; adding SSD jumps to 71–90%. This refutes prior HBM-only multi-turn caching (LMDeploy/RadixAttention-style) directly — the capacity, not the bandwidth, is the binding constraint at scale.

Quality of decoupled truncation #

Decoupled truncation is essentially lossless:

Dataset	Model	CA	TT	NKVT
WikiText-2	LLaMA-7B	5.47	5.48	2198.7
WikiText-2	LLaMA-13B	4.91	4.90	1647.7
PTB	LLaMA-13B	7.61	7.60	1865.8
C4	LLaMA-13B	6.44	6.45	1745.6

CA tracks token-truncation (TT) within 0.02 PPL; naive coupled truncation (NKVT) explodes to >10³, confirming the position-coupling problem is real, not hypothetical. Accuracy (Table 2): MMLU/LongEval/PIQA CA≈TT within ~1%, NKVT far below (e.g. LongEval LLaMA-7B: CA 66.0% vs NKVT 12.0%).

Workload characterization (framework §6 — where it wins/loses) #

Workload regime	CachedAttention	RE baseline	Why
Short prompts, low concurrency (1st turn, cold)	≈ RE (no history to reuse)	≈ RE	nothing cached yet; benefit needs a prior turn
Long history, later turns	huge win (TTFT ↓ up to 87%)	recomputes all history	reuse deletes >99% of prefill
Mixed prefill-decode (continuous batching)	win — short prefill unblocks queued decode	prefill blocks decode	reduced prefill time propagates to decode
High DSpUT / capacity-starved (small SSD, e.g. LLaMA-65B)	weakest (hit 71%, cost ↓ only 43%)	—	large per-token KV (2.5 MB) exhausts store; also LLaMA-65B's 2K window forces overflow after turn 1
Rising arrival rate 0.5→2.0/s	mild degradation (hit 82→77%, GPU 6.25→7.01 H)	—	higher DSpUT needs more capacity for same hit

The regime where CachedAttention loses its edge is explicit: LLaMA-65B (largest per-token KV and smallest 2K context) — 43% cost saving vs 66–70% elsewhere. The paper surfaces this rather than hiding it.

---

6. 论证链 #

#	Claim	Internal support
1	Multi-turn recompute wastes up to 99% of prefill cost.	ShareGPT: 73% multi-turn, history >99% of new-turn tokens → 99% of TTFT is recompute (§2.3, Fig 4).
2	Therefore KV must be reused, but cannot fit in HBM.	KV fills 190 GB free HBM in 14 s at 13.9 GB/s; host memory <1 min (§2.4). ⇒ need slower/larger tiers.
3	Slower tiers add latency on the critical path.	Loading 2K-token KV (5 GB) over PCIe = 192 ms vs 360 ms prefill — non-negligible (§2.4 Ch.1).
4	Layer-wise preload + async save hide that latency.	Eq. 3 predicts imperfect overlap for long history; read buffer (Eq. 4) closes gaps → 61% prefill-time cut at PF-B15 (§3.2, §4.3.2).
5	Most KV lives on SSD, so placement determines effective speed.	Disks tens of TB but <5 GB/s; random arrivals ⇒ likely disk hits (§2.4 Ch.3).
6	Scheduler-aware fetch/evict moves hits to DRAM.	Job-queue look-ahead ($L_{pw},L_{ew}$) beats LRU/FIFO; >99.6% of CA hits in DRAM vs ~0.5% (§3.3, §4.3.3).
7	Context overflow would invalidate cached KV.	Token truncation shifts positions; 30% (LLaMA-2 4K) / 47% (OPT 2K) of sessions overflow (§2.4 Ch.4).
8	Decoupling RoPE keeps truncated KV valid & lossless.	Cache before position-embed, re-embed on load; PPL within 0.02 of TT, NKVT >10³ (§3.4, §4.3.5).
9	Net effect: large TTFT/throughput/cost wins.	End-to-end: TTFT ↓87%, prefill ↑7.8×, cost ↓70% vs RE (§4.2).

---

7. 实现 cross-reference #

[实现未公开] — no public code repository is cited in the paper; it states only that CachedAttention is implemented "in Pytorch and Python" over HuggingFace Transformers [51], with block-based storage similar to vLLM [21], dedicated CUDA streams for HBM↔DRAM movement, and separate IO threads for DRAM↔SSD (§4.1). No file:line citations are possible.

核心技术壁垒 (§7 deep dive): the reproduction-critical piece is not any single kernel but the coupling between the serving job scheduler and the KV tier manager. To rebuild it you must (a) expose the scheduler's waiting-job queue to the cache layer, (b) key the cache by session id (session-granular items, since a session's KV is all-or-nothing), and (c) run two look-ahead scans over the same queue — a short one bounded by DRAM ($L_{pw}=C_{mem}/S_{kv}$) that drives SSD→DRAM prefetch, and a long one bounded by DRAM+SSD ($L_{ew}=(C_{mem}+C_{disk})/S_{kv}$) that vetoes eviction of imminent sessions and prioritizes the tail. Getting the tail-priority eviction right (evict the furthest-future session, not the least-recently-used) is what produces the >99.6% DRAM-hit inversion; a straightforward LRU port will silently regress to disk-bound hits.

关键实现细节 (easy-to-miss tricks):

1. Save is per-phase, not uniform. Prefill-phase KV (produced in bulk) is overlapped with the decode phase; decode-phase KV is written layer-by-layer during decode, with a write buffer catching whatever isn't flushed when decode ends — otherwise the next job blocks on the write (§3.2.2). Missing this makes the async-save gains (13–15%) disappear.
2. *RoPE decoupling requires caching KV before the positional rotation* and re-applying it on load; it only works with relative/rotary PE, not absolute PE (§3.4). Truncation then operates directly on stored KV (e.g. keep KV[0:1536]), and it composes with a token-discarding list for KV compression — but silently assumes an RPE model.