Skip to content

MemDecay: Region-Aware KV Cache Eviction for Efficient LLM Agent Inference

🕒 Published (v1): 2026-07-12 05:35 UTC · Source: Arxiv · link

Why this paper was selected

Region-aware KV cache eviction for agent inference; efficiency critical for long-horizon harness runs

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

MemDecay is a training-free KV-cache eviction policy for long-horizon LLM agents that uses semantic region labels (supplied by the orchestration layer) to assign region-specific base priorities and temporal decay rates, producing a composite retention score per token. It guarantees survival of pinned system-prompt regions and shows that region lifetimes differ by an order of magnitude across agent trace components. The core win is structural instruction protection; the core loss is that attention-based retention outperforms MemDecay on unpinned content, with a diagnosed fix (attention-term magnitude normalization).

Problem

Existing KV-cache eviction policies (accumulated-attention, recency windows, streaming sinks) apply a uniform retention rule to all tokens, treating the heterogeneous semantic components of an orchestrated agent trace as equivalent. System instructions, plans, tool outputs, and scratchpad reasoning have vastly different expected useful lifetimes, and ignoring this structure wastes budget on short-lived tokens while evicting long-lived ones. The problem is compounded at long contexts, where recency-based policies collapse entirely.

Method

MemDecay receives per-token region labels \(r(i) \in \{\texttt{system}, \texttt{plan}, \texttt{user}, \texttt{tool\_in}, \texttt{tool\_out}, \texttt{retrieval}, \texttt{scratchpad}\}\) from the orchestrator alongside the inference request. Each region is configured with a base priority \(b_r \geq 0\) and decay rate \(\lambda_r \geq 0\). A per-token exponentially-weighted attention importance \(a_i\) is maintained via:

\[a_i \leftarrow \rho\, a_i + (1-\rho)\,\bar{A}_i\]

where \(\bar{A}_i\) is windowed mean attention mass averaged over heads and layers. A decay clock \(\Delta t_i(t)\) tracks time since last attention above threshold \(\tau\), resetting on use. The retention score is:

\[s_i(t) = b_{r(i)}\exp\!\bigl(-\lambda_{r(i)}\,\Delta t_i(t)\bigr) + \alpha\, a_i(t)\]

Under a fixed budget \(B\), pinned tokens (system region by default) are kept unconditionally; remaining pages are evicted by ascending mean score \(S_p(t) = \frac{1}{|p|}\sum_{i\in p} s_i(t)\). Decay rates are calibrated by fitting \(\log\bar{A}_r(\Delta t) \approx \log c_r - \hat{\lambda}_r \Delta t\) on held-out agent traces (leave-one-scenario-out), yielding per-region half-lives \(t_{1/2}^r = \ln 2 / \hat{\lambda}_r\).

Key Contributions

  • Formulation of region-aware selective forgetting as a KV-cache memory-management problem grounded in the semantic structure of orchestrated agent prompts.
  • MemDecay policy: region base priorities + region-specific exponential decay with attention-triggered clock reset + attention EWMA, combined in a single interpretable score under a fixed page-granular budget.
  • Measurement protocol estimating region-conditioned attention half-lives from agent traces, validated across 2 context lengths (405–507 and 1,656–1,723 tokens) and 2 model sizes (Qwen2.5-1.5B, 3B), totaling 4,320 scored eviction probes.
  • Empirical finding that region lifetime ordering is stable across all settings and that the calibrated rate for retrieval overturn the qualitative default (retrieval is the longest-lived movable region, not short-lived as naively assumed).
  • Ablation identifying attention-term magnitude normalization as the root cause of MemDecay's unpinned-recall loss against H2O-style retention.

Results

  • Region half-lives (decode steps): system 148–189 vs. scratchpad 14–16 — an order of magnitude separation with non-overlapping 95% bootstrap CIs in every setting; retrieval is the longest-lived movable region (half-life 48–76) despite arriving at three different insertion positions.
  • Pinning (system recall): MemDecay preserves system-region facts at full-cache ceiling in every setting; no baseline preserves more than 13 of 24 system probes.
  • Short-tier overall recall at 25% budget: MemDecay 0.32 [0.28, 0.36] vs. random 0.20, streaming 0.16, H2O 0.15.
  • Short-tier overall recall at 50% budget: MemDecay 0.49 [0.41, 0.55] vs. random 0.38, streaming 0.27, H2O 0.32.
  • Non-system recall at 25% budget (short tier): MemDecay 0.10 [0.04, 0.15] — a clear loss against H2O (0.19) and streaming (0.21); the policy's attention term cannot compensate at any tested \(\alpha\).
  • Recency-based baselines (streaming): collapse as context grows while MemDecay's structural prior keeps working.

Limitations

  • MemDecay loses on unpinned-content recall against H2O-style accumulated-attention retention; the attention term in equation (4) is insufficient at any tested weight \(\alpha\), and the paper diagnoses but does not fix magnitude normalization.
  • Requires the orchestration layer to emit region labels; this is not yet standard in all serving stacks (though an open SGLang proposal covers it).
  • Uses eager attention to read per-step attention weights, which is incompatible with production fused kernels; sampled observation intervals (\(k > 1\)) are the practical setting but were not fully evaluated.
  • Evaluated only on Qwen2.5-1.5B and 3B; generalization to larger models and other architectures is unverified.
  • Page-granular eviction can mask high-scoring tokens in mixed-region pages (35% straddle rate on short tier, 17% on long tier), introducing deviation from the token-level optimal.
  • Study uses synthetic multi-turn episodes with planted facts; real agentic workloads may have different region distributions and eviction dynamics.
  • Recall metric requires exact token-boundary match of gold values; soft or semantic recall is not reported.

Relevance to Harnesses / Meta-Harnesses

MemDecay is architecturally coupled to the agent harness: it requires the orchestration layer to annotate each prompt segment with a semantic region label at request time, making the cache policy a first-class consumer of harness-level metadata. This establishes a concrete interface contract between meta-harness design (how prompts are assembled and annotated) and inference-serving efficiency (which KV pages survive under memory pressure). For researchers building or studying agent harnesses, the paper demonstrates that the structural choices made at the harness layer — how context regions are typed, ordered, and signaled to the serving stack — directly determine cache effectiveness and long-horizon agent memory fidelity. The measurement protocol (calibrating region decay rates from harness-produced agent traces) also provides a methodology for instrumenting harness behavior to tune serving-layer policies.