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

Problem Statement

Large language models (LLMs) and the agents built upon them increasingly dedicate computational resources to memory management: caching attention keys and values (KV), maintaining long prompts, storing recurrent states, and retaining agent interaction histories. As context lengths grow, memory becomes the primary bottleneck, often exceeding the model's own weight footprint.

Currently, four distinct research communities address this bottleneck in isolation:

1. KV-cache compression: Evicting, quantizing, or merging tokens during inference.
2. Prompt/Context compression: Pruning or distilling input tokens before the model processes them.
3. Architectural constraints: Bounding memory via recurrence, state-space models, or linear attention.
4. Agent memory: Consolidating and summarizing agent trajectories and long-term knowledge.

These communities operate with separate benchmarks, success metrics, and design philosophies, rarely citing one another. The paper argues that these are not distinct problems but rather different instances of a single fundamental challenge: a rate–distortion decision. The core problem is determining what context-derived information to retain versus discard, at what fidelity, under a resource budget, to preserve downstream task utility.

Methodology and Formalism

The authors propose a unified formalism treating memory compaction as a rate–distortion optimization problem.

The Unified Objective

For a given history $H$ (all tokens, states, or memories available), a compaction operator $C_\theta$ produces a compact representation $Z$ subject to a budget $B$ (measured in bytes, tokens, or state dimensions). A usage operator $U$ then generates an output $\hat{Y}$ from $Z$. The design goal is to minimize expected loss (distortion) subject to the rate constraint:
$$\min_\theta \mathbb{E}[\ell(U(C_\theta(H), Q), Y)] \quad \text{s.t.} \quad \text{rate}(Z) \le B$$
This is framed as an Information Bottleneck problem: maximize $I(Z; Y | Q)$ (bits of history predicting the answer) subject to $I(Z; H) \le B$.

Theoretical Lower Bound

The paper derives a layer-agnostic lower bound on error probability $P_e$ using Fano's inequality. Let $I^\star(Q) = I(Y; H | Q)$ be the task-conditioned information content (the bits of history genuinely required to answer query $Q$). If the budget $B < I^\star(Q)$, the error is bounded by:
$$P_e \ge \frac{H(Y|Q) - B - 1}{\log |\mathcal{Y}|}$$
Key Implications:

1. Inevitability of Error: Below the information requirement $I^\star(Q)$, every layer must err; no architecture can escape this.
2. Task Dependence: Compression ratios at fixed quality depend on $I^\star(Q)$. High-entropy tasks (exact retrieval) compress poorly; low-entropy tasks (summarization) compress well.
3. The Query-Agnostic Penalty: Operators that decide what to keep before seeing the query (query-agnostic) must spread their budget across the entire query distribution, paying a penalty of $H(Q)$ (query entropy). Query-conditioned operators can spend the full budget on answer-relevant bits.

Seven-Axis Taxonomy

To classify methods uniformly, the authors introduce a taxonomy based on seven orthogonal axes:

1. Granularity: From bit-width to semantic items.
2. Lifecycle Stage: Pretraining, prefill, decoding, serving, within-task, or between-task.
3. Lossiness/Fidelity: Lossless, near-lossless, uniformly lossy, or multi-fidelity.
4. Query/Task Adaptivity: Query-agnostic vs. query-conditioned.
5. Learnability: Training-free, post-training adapter, or trained-from-scratch.
6. Mechanism: Eviction, retrieval, merging, quantization, etc.
7. Storage Substrate: On-GPU, external store, or model weights.

Key Contributions

1. Unified Formalism and Lower Bound: The paper formalizes memory compaction as a single rate–distortion problem and derives a lower bound (Eq. 2) showing that error rates are governed by the same expression across all layers. It identifies the "query-agnostic penalty" as a quantifiable cost.
2. Seven-Axis Taxonomy: A classification system that unifies methods from KV caches, prompts, architectures, and agent memory, revealing that differences lie primarily in granularity, lifecycle stage, and adaptivity.
3. Cross-Layer Mechanism Transfer: The authors demonstrate that mechanisms refined in one layer can be ported to others. For example:
   • Agent forgetting curves (Ebbinghaus) can serve as priors for KV eviction.
   • No-eviction retrieval (Quest) suggests designs for agent memory.
   • Output-error bounds (Ada-KV) suggest stopping rules for agent summarization.
4. Identification of Failure Modes: Two critical properties determine success: Reversibility (can dropped content be re-derived?) and Query-Conditioning (does the decision depend on the query?). The paper predicts that methods lacking these (e.g., irreversible summarization) will suffer super-linear error accumulation under repeated compaction.
5. COMPACT-Bench Proposal: A new benchmark proposal to measure compaction across a unified "bytes-per-token-of-history" (BPT) axis. It includes tasks to measure loss attribution, reversibility, and calibrated confidence, specifically testing the "repeated compaction" regime which current benchmarks ignore.
6. Reference Experiments: Small-scale experiments on commodity hardware demonstrating:
   • A unified accuracy–budget frontier where performance collapses once the budget drops below $I^\star(Q)$.
   • A divergence between reversible and irreversible operators under repeated compaction, where irreversible methods lose roughly 50% of facts compared to reversible ones.

Results and Observations

• Universal Failure Mode: Across all layers, methods that decide what to keep before the query is known and cannot undo the decision (irreversible, query-agnostic) fail in the same way: they discard information the query later needs.
• Reversibility Dominance: At equal budget, reversible operators (retrieval-backed, archival) consistently outperform irreversible ones (eviction, summarization), particularly on queries dependent on discarded material.
• Measurement Gap: Current benchmarks focus on single-turn long-context tasks. They fail to measure the cost of repeated compaction, which is the actual operating mode of agents. The paper shows that error accumulation in repeated compaction is super-linear for irreversible methods but flat for reversible ones.
• Attention Heuristics as Surrogates: Common heuristics (accumulated attention mass, perplexity, mutual information) are all identified as distortion surrogates. They are comparable because they estimate the same underlying quantity: "how much will dropping this hurt the answer?"

Significance and Claims

The paper claims that viewing memory compaction through a rate–distortion lens provides three specific benefits:

1. A Shared Yardstick: It allows direct comparison of methods across different layers (e.g., comparing a KV quantizer to an agent summarizer) by mapping them to a common budget axis.
2. Unified Failure Analysis: It explains why diverse methods fail similarly (due to irreversibility and lack of query-conditioning) and predicts specific signatures of failure (e.g., U-shaped recall curves, super-linear error growth).
3. Portability of Techniques: It enables the transfer of proven mechanisms between layers, such as applying architectural constraints to agent memory or using agent consolidation strategies to inform KV management.

The authors emphasize that the field lacks a cross-layer benchmark and a predictive scaling law for $I^\star(Q)$. They propose that progress will come not from better heuristics in isolation, but from recognizing the shared objective and measuring compaction with a unified protocol that accounts for reversibility, query-conditioning, and repeated compaction.

Open Problems and Agenda

The paper outlines a prioritized research agenda:

• Developing query-conditioned, reversible, multi-fidelity compaction operators for all layers.
• Creating information-loss attribution and calibrated confidence mechanisms.
• Mapping the composition of operators (e.g., how quantization interacts with eviction).
• Deriving a predictive compression scaling law to estimate $I^\star(Q)$ based on model and task parameters.
• Establishing stop rules for agent summarization based on output-error bounds.
• Addressing safety and auditability in self-editing memory systems.