CacheWise: Optimizing KVCache Management for Serving LLM Coding Agents — L2 #

1. TL;DR #

Coding agents are long-running, closed-loop LLM sessions (median 36 min, ~20× more tool-driven than user-driven turns) that reuse large, growing prefixes. Default FCFS+LRU serving thrashes their KVCache. CacheWise adds prefix-aware scheduling (dispatch min missing-prefix request) + metadata-predictive eviction (tool-call → reuse-time predictor), cutting evictions 2–2.6× and session completion time up to ~3.5× in vLLM.

2. Q1 / Q2 / Q3 #

Q1 — 痛点 (pain point). Coding-agent serving had never been characterized as a workload. Existing serving systems (vLLM, Mooncake) use FCFS batching and LRU KVCache eviction — policies tuned for chatbot request-latency, not multi-turn sessions. Two properties break them: (a) requests from one session share a large, growing prefix already resident in memory; (b) time-to-next-reuse depends on external tool execution, which LRU cannot see. FCFS interleaves many sessions → expands the working set → evicts prefixes that will soon be reused; LRU cannot tell a session whose tool call is about to return from one idle for hours. Result: KVCache thrashing, low token goodput (useful tokens/sec after excluding recompute + movement).

Q2 — 方法 (method). CacheWise is an agent-aware KVCache management layer inside a general serving system (vLLM), requiring no changes to the coding agents. Two ideas: (1) Prefix-aware request scheduling — at time $t$, dispatch the request $r_i$ that requires the fewest additional (non-resident) blocks $a_i(t)$; this minimizes reclaim/restore and approximates shortest-job-first. (2) Predictive KVCache eviction — replace LRU with a Belady-style rule that evicts the session whose blocks are furthest from reuse, using a lightweight predictor $\mathbb{E}[\tau_i(t)]$ over tool-call metadata (tool name + args). The 核心技术壁垒 (single hardest-to-replicate insight): you do not need accurate per-session reuse-time prediction — only the relative order of $\tau$ across sessions (indeed just the single highest-$\tau$ session), and TF-IDF + KMeans clustering of tool arguments provides enough signal to recover that order.

Q3 — 结果 (results). Implemented in ~2,500 LoC on vLLM, evaluated on the collected CATraces (Qwen2.5-Coder-32B, 2× H200). At load $N>10$: session completion time 2.7–3.5× lower vs vLLM/InferCept, token goodput 1.64–2×, evictions and KVCache transfer volume down 2–2.6×, throughput 1.5–2×, P50 latency 13–14× lower. CacheWise matches (sometimes marginally beats) an oracle CacheWise* with ground-truth tool latencies.

3. 架构 / 方法图 #

The agent loop is a closed loop: one user task expands into a chain of LLM requests and tool calls, each turn extending the resident KVCache prefix.

The system-level workflow places CacheWise at the inference node behind a prefix-match load balancer.

Paper's Figure 11 (caption: "(A) End-to-end workflow of a session through a typical LLM serving system. (B) Prefix-aware request scheduling prioritizes requests by degree of overlap with KVCache resident on the XPU memory... (C) Demonstration of predictive KVCache eviction choosing the block with the highest predicted reuse probability, rather than purely recency-based heuristics like LRU.").

Panel (A) shows the load balancer routing same-session requests to the same node via largest-resident-prefix matching, so the growing prefix stays local. Panel (B) is the scheduler choosing the highest-overlap (lowest-$a_i$) request; panel (C) is the eviction heap choosing the block least likely to be reused soon — the two mechanisms operate independently at each node.

The formal memory model motivating the notation:

Paper's Figure 10 (caption: "XPU memory layout during LLM serving. After reserving memory for model weights, the remaining capacity $M$ holds KVCache blocks for active sessions... When a new request $r_5$ requires $a_5$ additional blocks that exceed $M$, the system must evict blocks from an existing session.").

This schematic grounds the whole analysis: capacity $M$ after weights, per-session resident blocks $k_i(t)$, and the eviction trigger $W(t)+a_5 > M$. Note the caption defines $W(t)=\sum_i k_i(t)$ (resident blocks), which differs from the §4 prose definition $W(t)=\sum_i d_i$ (total prefix demand) — an internal inconsistency in the source.

4. 作者证明 #

无形式化作者证明 — 仅实证. CacheWise offers no convergence/success guarantee; its eviction target (Belady) is provably optimal only under perfect future knowledge, which the predictor approximates empirically. What could have been bounded: the competitive ratio of predicted-order eviction vs Belady-optimal (the theory exists in Lykouris & Vassilvitskii 2021, cited but not instantiated here). The paper instead offers a lightweight formal model + empirical sweeps.

Notation table:

方程物理意义:

Working set and memory budget (no eviction while it fits):

$$W(t)=\sum_{i\,\in\,\mathcal{S}_{t}}d_{i}, \quad W(t)\leq M$$

Admission cost — only the missing prefix incurs allocation; evict if it overflows:

$$a_{i}(t)=d_{i}-k_{i}(t)$$

Optimal (Belady) eviction — evict the session furthest from reuse:

$$j^{}=\operatorname{arg\,max}_{j\,\in\,\mathcal{S}_{t},\;j\neq i}\tau_{j}$$

Prefix-aware dispatch — pick the request minimizing missing-prefix cost:

$$\text{dispatch } r_i \text{ minimizing } a_i(t)$$

Predictor — conditional (survival-style) remaining tool-execution time given the call is still outstanding after elapsed $t-T_i$:

$$\mathbb{E}[\tau_{i}(t)\mid\tau_{i}(t)-T_{i}>t-T_{i}]$$

Agent-specific checks (6 minimum):

1. Success-rate model — N/A (systems paper); the analog is the predictor-granularity sweep (§6.5), monotone: Point→ToolName→C20→C50→C100 monotonically lowers evictions & session time (up to 19% at C100), then saturates (data can't support >100 clusters).
2. Latency budget per turn — session completion time = sum of LLM request latencies excluding tool durations (env-determined). CPU scheduling overhead ≤ ~9% of request time (§6.6); the paper does not claim per-request interactive latency (P99 deliberately worse).
3. Failure-mode / cost classes — two limitation classes identified: FCFS thrashing (Impl. #1) and LRU priority inversion (Impl. #2); the two mechanisms target one each, verified independent in ablations (§6.3).
4. Sweep over load — swept $N$; gains appear only at $N>10$ (memory contention onset), monotone increase with load. Reproducible (deterministic trace replay).
5. Backbone sensitivity — prototype runs any model incl. GQA/MQA without weight changes; evaluated only on Qwen2.5-Coder-32B, so backbone sensitivity is untested.
6. Oracle gap — CacheWise ≈ CacheWise* (ground-truth latencies), confirming relative-order prediction suffices; the near-zero oracle gap is the key empirical guarantee substitute.

5. 实验与数据 #

Workload characterization. The core motivation is that coding agents are a distinct workload class, quantified against prior datasets:



Paper's Figure 2 (caption: "Comparing LLM serving request characteristics across datasets" — (a) prefill lengths, (b) decode lengths).

Coding agents prefill far more tokens per request (large accumulated prefix) yet decode far fewer, giving a ~21× higher prefill:decode ratio than chatbots — a load-bearing asymmetry that inverts the usual decode-centric optimization focus, since larger shared prefixes mean fewer concurrent resident sessions.



Paper's Figure 4 (caption: "CDF of requests triggered by tool completion versus user input. Tool-initiated requests dominate, indicating a predominantly closed-loop request generation process.").

Tool-completion requests are 20× more frequent than user-initiated at the median: the workload is machine-driven, not human-in-the-loop, justifying session-level (not request-level) metrics.

Headline end-to-end result:



Paper's Figure 13 (caption: "Session completion time (in seconds) for different KVCache management systems under the coding agent workload (sampled from CATraces).").

Below $N\leq10$ all systems tie (no memory contention); at $N>10$ CacheWise is 2.7–3.5× lower than vLLM/InferCept and tracks the oracle CacheWise* — proving the lightweight predictor is good enough.



Paper's Figure 14 (caption: "Serving efficiency... (a) Goodput... (b)-(e) LLM request latency distribution... (f) LLM request throughput...").

CacheWise improves token goodput 1.64–2× and reduces evicted blocks 2–2.6×; goodput decreases with load for all systems but CacheWise minimizes unnecessary evictions. Note the deliberate trade-off: P50 latency drops 13–14× but P99 increases (history-less new requests are deferred) — acceptable under the session-oriented objective.

Argument-level clustering evidence:



Paper's Table 3 (caption: "Bash tool call execution time distributions clustered by argument types. Columns P50, P90, and P99 show percentiles... $n$ is the number of datapoints in the cluster.").

Within the single tool "bash", git operations span P50 0.1s → P99 97s (~1000× intra-cluster), while mypy (P50 10s) and docker compose (P50 22s) differ by tool-name-blind averages — motivating TF-IDF+KMeans clustering on arguments rather than per-tool-name distributions.

6. 论证链 #

Step	Claim	Support (paper-internal)
1	Coding agents are a distinct workload: more turns, closed-loop, long sessions, growing prefixes, structured tool times	CATraces analysis, Fig 2–9, Table 1
2	These properties formalize into a memory model where FCFS thrashes (Impl. #1) and LRU inverts priority (Impl. #2)	§4 notation ($M$, $W(t)$, $a_i$, $\tau_i$), $j^{*}=\arg\max\tau_j$
3	Impl. #1 → prefix-aware scheduling (min $a_i$); Impl. #2 → predictive eviction from tool metadata	§5.1, §5.2, Table 2 mapping
4	Only relative $\tau$-order is needed; TF-IDF+KMeans over args gives enough signal	§5.2 insight, Fig 12, Table 3
5	Both mechanisms combined: 2.7–3.5× session time, 2–2.6× fewer evictions, ≈ oracle	Fig 13, Fig 14
6	Mechanisms are independent and each contributes	Fig 15 (eviction alone 1.7–2×), Fig 16 (scheduling alone 1.8–2.66×)
7	Gains cover the offloading regime too (smaller, 1.19×) and net-positive despite CPU overhead	Fig 17, Fig 18, Fig 20

7. 实现 cross-reference #

Implementation is stated as ~2,500 lines of Python on top of vLLM (§5.3), extending the batch scheduler and KVCache block manager; the traces/dataset are open-sourced at github.com/cachewise-project/cachewise-coding-traces. The serving-system code itself is not linked in the L1 source, so specific file:line citations are [实现未公开].

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

1. Block-attached session metadata + shared predictions. Each KVCache block carries (tool_name, tool_args, T_i) (§5.3). When a block's refcount hits zero it enters an eviction heap keyed by the predicted $\mathbb{E}[\tau_i(t)]$. Crucially, blocks of the same session share one prediction — the predictor is not invoked per block, keeping overhead low.
2. Staleness rebuild parameter $N_{\text{rebuild}}$. Predictions go stale as tool calls progress, so CacheWise periodically re-scores all unreferenced blocks and rebuilds the heap every $N_{\text{rebuild}}$ engine iterations. Set to $N_{\text{rebuild}}=3$ empirically — the freshness/overhead knob is a subtle but load-bearing config that most reimplementations would miss.

核心技术壁垒 (restated). The single hardest insight to replicate is not the plumbing but the observation that near-optimal (Belady-approaching) eviction needs only the relative ordering of reuse times across sessions — often just identifying the one highest-$\tau$ session — which is recoverable from cheap tool-metadata clustering. This is why CacheWise can match a ground-truth oracle without accurate absolute reuse-time prediction, and it is the property that a naive reimplementation (e.g. per-tool moving average, as InferCept does) fails to capture.