🤖 machine learning

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

MemDecay is a training-free, region-aware KV cache eviction policy that leverages the semantic structure of LLM agent contexts to assign distinct retention priorities and decay rates to different token regions, significantly outperforming existing recency- or attention-based baselines in preserving critical information and maintaining inference accuracy under memory constraints.

Original authors: Venkatesha Matam, Keon Kim

Published 2026-07-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Venkatesha Matam, Keon Kim

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you're running a super-smart robot assistant (an LLM agent) that's trying to solve a massive, multi-step mystery. It has to remember the rules of the game, the clues it finds, the tools it uses, and its own messy scratchpad notes. As the mystery gets longer, the robot's "brain" (its memory cache) starts to overflow. If it doesn't make room, it crashes or gets slow.

The big problem? Most robots treat every single piece of memory the same. They might say, "Oh, I haven't looked at this clue in a while, so I'll throw it out," or "This was the very last thing I read, so I'll keep it." But that's like throwing away the map because you looked at it yesterday, while keeping a random doodle you just made.

Enter MemDecay, a new strategy that acts like a smart, organized librarian for the robot's brain. Here's how it works, what it found, and what it definitely didn't find.

The Smart Librarian Strategy

Instead of treating all memories equally, MemDecay asks the robot's manager: "What kind of memory is this?"

Is it a System Instruction? (The robot's core rules, like "Always be polite.")
Is it a Plan? (The steps to solve the mystery.)
Is it Scratchpad? (Temporary math or notes the robot is working on right now.)
Is it Tool Output? (Data from a calculator or search engine.)

MemDecay gives each type of memory a different "expiration date" and a different "importance score."

System Instructions get a "Pinned" badge. They are glued to the shelf and never thrown away, no matter how full the library gets.
Scratchpad notes get a very short shelf-life. If the robot stops using them for a few seconds, they fade away.
Plans and Tools get a medium shelf-life, but if the robot looks at them again, their "expiration clock" resets, keeping them safe.

The system calculates a score for every memory token based on its type and how recently it was used. When the library is full, it kicks out the pages with the lowest scores first.

What the Experiments Actually Showed

The researchers tested this on two robot sizes (1.5 billion and 3 billion parameters) and two memory sizes (about 450 tokens and 1,700 tokens). They planted specific facts in different parts of the robot's memory and then asked the robot to recall them after forcing it to delete half its memory.

1. The "Pinned" Victory
The biggest win was for the "System" instructions. When the memory was squeezed to 25% or 50% of its size, MemDecay kept the system rules safe every single time (24 out of 24 probes on the short test, 21 out of 24 on the long test).

The Contrast: Other methods that just keep the "most recent" memories (like a robot that only remembers the last few sentences) failed completely. On the long tests, they recalled almost zero system instructions. The "recent-only" approach collapses as the story gets longer.

2. The "Scratchpad" Reality Check
The experiments measured exactly how long different memories stayed useful.

System instructions lasted a long time: about 148 to 189 decode steps (the time it takes the robot to generate that many words).
Scratchpad notes vanished incredibly fast: only 14 to 16 steps.
Retrieved documents (like search results) were surprisingly long-lived, lasting longer than tool outputs or user messages, even though the researchers initially thought they would fade quickly.

3. The "Old Fact" Problem (The Loss)
Here is where MemDecay stumbled. When the robot had to remember an old user message or a fact from the beginning of the conversation that wasn't pinned, MemDecay often failed.

On the short test, it recalled 0 out of 24 of these old user facts.
On the long test, it recalled only 5 to 7 out of 24.
Meanwhile, a competitor method that just kept the "most attended-to" tokens (called H2O-style) did much better, recalling 11 to 20 of them.

Why did it fail? The paper explains that the "importance" score from the robot's attention (how much it looked at a word) was too weak to save the old facts. The "decay" (the expiration clock) was ticking so fast for those old, unpinned items that the attention signal couldn't stop the clock. The researchers suggest that simply turning up the volume on the attention signal isn't enough; the math needs to be adjusted so the attention signal is strong enough to compete with the decay.

What MemDecay Is NOT

It's important to know what this paper doesn't claim:

It is not a magic fix for everything. It explicitly ruled out the idea that "recency" (keeping the newest stuff) works for long agent tasks. The data shows that relying on "what was just said" fails miserably as the conversation grows.
It is not a "breakthrough" that solves the recall problem for old facts. The paper admits that for unpinned, older facts, MemDecay actually performed worse than existing attention-based methods in these specific tests.
It doesn't "learn" new weights. It's "training-free," meaning it doesn't retrain the robot's brain. It just uses a smart set of rules and a little bit of measurement to tune the expiration clocks.

The Bottom Line

MemDecay is a clever, rule-based system that organizes a robot's memory by type rather than just age.

It wins big at protecting the robot's core rules and instructions, ensuring they never get lost even when memory is tight.
It loses at remembering old, unpinned facts, where it gets outperformed by methods that just follow the robot's attention.

The researchers measured these results across thousands of test cases and found that while the "type-based" approach is great for structure, it needs a math tweak to stop forgetting the old, useful stuff. It's a solid step forward for making long-running robot agents more reliable, but the job isn't finished yet.

Technical Summary: MemDecay

Problem Statement

Large Language Models (LLMs) are increasingly deployed as agents that execute long-horizon workflows involving multi-turn interactions, tool use, and iterative planning. Unlike static long-context tasks, these agent traces accumulate heterogeneous components: system instructions, safety constraints, evolving plans, user turns, retrieved documents, tool outputs, and intermediate reasoning states.

The Key-Value (KV) cache required for autoregressive decoding grows linearly with this trace, creating significant memory overhead, bandwidth demands, and latency. Existing KV-cache eviction policies typically rely on model-centric signals (e.g., accumulated attention, recency windows, or attention sinks) and apply uniform retention rules across the entire sequence. This approach fails to leverage the inherent semantic structure of orchestrated agent prompts. In agent workloads, different components have vastly different functional roles and expected lifetimes; for instance, system instructions must persist throughout an episode, while scratchpad reasoning or stale tool outputs may only be relevant for short spans. Treating all tokens with the same expected lifetime ignores this structure, leading to suboptimal memory management.

Methodology: MemDecay

The authors propose MemDecay, a training-free, region-aware KV-cache eviction framework designed for long-horizon LLM agents. The method operates under a fixed cache budget and integrates structural priors from the orchestration layer with attention-derived importance.

Core Components

Region Labels: The orchestration layer supplies region labels for contiguous prompt spans (e.g., system, plan, user, tool_in, tool_out, retrieval, scratchpad).
Retention Score: Each token $i$ $i$ is assigned a retention score $s_i(t)$ $s_{i} (t)$ at time $t$ $t$ , calculated as:
$s_i(t) = b_{r(i)} \exp(-\lambda_{r(i)} \Delta t_i(t)) + \alpha a_i(t)$
- Structural Prior: $b_{r(i)}$ is a base priority specific to the token's region.
- Temporal Decay: $\lambda_{r(i)}$ is a region-specific decay rate. The term $\Delta t_i(t)$ represents the time since the token was last "refreshed."
- Attention Importance: $a_i(t)$ is an exponentially weighted moving average (EWMA) of attention mass received by the token.
- Refresh Mechanism: If attention to a token exceeds a threshold $\tau$ , its decay clock resets ( $\Delta t_i$ becomes 0), effectively extending its life based on continued usage.
Pinning: System regions (and optionally plan segments) can be "pinned," meaning they are never evicted regardless of the score.
Eviction Policy: The cache is managed at the page granularity (e.g., 16 tokens per page). When the budget is exceeded, pages are scored by the mean retention score of their constituent tokens. The pages with the lowest scores are evicted first.

Calibration

MemDecay is training-free regarding model weights but employs a lightweight statistical calibration to fit the decay rates ( $\lambda_r$ ) for each region. This process estimates region-conditioned attention lifetimes from agent traces, allowing the system to adapt to specific workload characteristics without retraining the LLM.

Key Contributions

Formulation: The paper formulates region-aware selective forgetting as a memory management problem for LLM agents, grounding the solution in the semantic structure of orchestrated prompts.
Algorithm: It introduces MemDecay, a policy that combines region-specific base priorities, temporal decay, and attention-triggered refresh into a single interpretable retention score. It operates on page-granular layouts compatible with existing serving stacks (e.g., PagedAttention).
Measurement Protocol: The authors specify a protocol to estimate region-conditioned attention lifetimes and calibrate decay rates. They execute this across two context lengths (~450 and ~1,700 tokens) and two model sizes (Qwen2.5-1.5B and 3B), totaling 4,320 scored eviction probes.

Experimental Results

The study evaluates MemDecay against baselines including random eviction, recency-based (streaming) retention, and accumulated attention retention (H2O-style).

Key Findings

Region Lifetime Hierarchy: Measured attention lifetimes differ by an order of magnitude across regions. In all settings, system tokens have half-lives of 148–189 decode steps, while scratchpad tokens decay rapidly (14–16 steps). Retrieval tokens were found to be the longest-lived movable region, contradicting default assumptions that they decay quickly.
Pinning Effectiveness: Pinning system regions guarantees instruction survival. MemDecay preserved 21–24 of 24 system probes across all settings at the full-cache ceiling, whereas recency-based baselines preserved 0–2.
Recency vs. Structure: Recency-based retention (streaming) collapses as context length increases, performing near zero on long tiers. In contrast, the structural prior in MemDecay remains effective.
Accumulated Attention: On unpinned content, accumulated attention (H2O-style) strengthens with model scale, outperforming MemDecay on unpinned recall in the 3B model setting.
MemDecay's Limitation: MemDecay showed a specific loss in unpinned recall for older facts (e.g., user-region facts in the opening turn) compared to attention-based baselines. An ablation study revealed that the attention term ( $\alpha a_i$ ) was too small in magnitude to counteract the structural decay for these tokens. The authors identify that the attention term requires magnitude normalization (e.g., relative to uniform attention levels) to be effective, rather than just weight tuning.

Significance and Claims

The paper positions MemDecay as a practical, training-free solution that aligns cache retention with the semantic structure of agent workflows. Its significance lies in:

Interpretability: The policy is driven by explicit region labels and decay rates, making retention decisions transparent.
Compatibility: It operates on page-granular caches without requiring model retraining or auxiliary modules, fitting into existing serving stacks.
Guaranteed Stability: By pinning critical regions, it ensures that system instructions and safety constraints are never lost due to memory pressure, a guarantee not provided by attention or recency-based methods.
Adaptability: The calibration protocol demonstrates that region lifetimes are workload-dependent and can be measured to optimize decay rates, challenging the use of static, one-size-fits-all eviction policies.

The authors conclude that while MemDecay successfully preserves structural priors and pinned instructions, future work must address the magnitude normalization of the attention term to improve unpinned recall and explore tiered extensions (e.g., offloading to host memory) to handle irreversible eviction.