What to Keep, What to Forget: A Rate–Distortion View of Memory Compaction in LLMs and Agents

Large language models and their associated agents face a growing bottleneck: the memory required to store attention keys, values, prompts, and historical states often exceeds available hardware capacity. While research communities have developed disparate techniques to manage this—such as KV cache eviction, prompt pruning, architectural state bounding, and agent memory consolidation—these are all fundamentally the same problem. They are rate-distortion decisions that require balancing a resource budget against the need to preserve information for future queries.

By formalizing memory compaction as a rate-distortion problem, the authors derive a layer-agnostic lower bound that applies to all compaction methods. This bound demonstrates that whenever a system's memory budget falls below the information requirement of a specific task, errors are inevitable. The authors identify three critical properties that determine whether a compaction method will succeed or fail:

1. Reversibility: Can the system retrieve or re-derive discarded information if a later query requires it?
2. Query-Conditioning: Does the system know the query before deciding what to discard?
3. Fidelity Profile: Is the representation lossless, near-lossless, or multi-fidelity?

Most current methods fail because they are query-agnostic and irreversible, meaning they discard information before the query is known and provide no mechanism to recover it.

The paper introduces a seven-axis taxonomy to classify compaction methods uniformly across the stack, including granularity, lifecycle stage, fidelity, adaptivity, learnability, mechanism, and storage substrate. This classification reveals that while the substrates differ (e.g., GPU memory for KV caches vs. external databases for agents), the underlying failure modes are identical. The authors propose a new benchmark, COMPACT-Bench, to measure error accumulation across these layers and provide design principles that prioritize reversibility and query-awareness to mitigate the performance penalties of aggressive compression.