Technical Summary: Remember the Decision, Not the Description

1. Problem Statement

Long-horizon language agents operate under strict runtime memory budgets, yet existing memory mechanisms typically organize experience based on descriptive criteria (e.g., semantic relevance, salience, recency, or summary fidelity). The authors argue that these criteria fail to capture the true purpose of memory in an agent: supporting decisions.

Empirical analysis on the LoCoMo benchmark reveals a critical disconnect: descriptive similarity is a statistically significant but weak predictor of evidence compatibility (Spearman $\rho = 0.103$, AUC = 0.548). Consequently, description-based retrieval recovers only 66% of gold evidence under a matched budget, compared to 83% for the proposed method. The core problem is that agents must compress interaction histories into a fixed number of $K$ runtime memory states without degrading downstream decision quality, a constraint that descriptive organization does not address.

2. Methodology: A Decision-Centric Rate-Distortion Framework

The paper reframes agent memory as a decision-centric rate-distortion problem. Instead of minimizing reconstruction error (faithful description), the goal is to minimize the loss in achievable decision quality induced by compression.

Theoretical Formulation

• Memory Constraint: The agent accesses history only through one of $K$ internal memory states (slots) at decision time.
• Decision Distortion: Defined as the loss in value when a history $h$ is mapped to a memory state $m$ and a policy $\pi$ selects an action based on $m$ rather than $h$.
• Exact Forgetting Boundary: The authors derive a theoretical boundary (Theorem 1) stating that two histories can safely share a memory state if and only if they admit a common $\epsilon$-optimal action for a given query. This is distinct from descriptive similarity; it is purely decision-theoretic.
• Complexity Measures: The paper introduces decision covering and packing numbers to characterize the minimum number of memory states required to maintain a target distortion level.
• Computational Hardness: Finding the optimal partition of histories into $K$ states to minimize distortion is proven to be NP-complete (Theorem 3), motivating the need for online, approximate learning.

The DeMem Algorithm

To address the NP-hardness and the need for online learning, the authors propose DeMem (Decision-aware Memory), an online memory learner with the following mechanisms:

1. Certified Incompatibility: DeMem maintains a "cannot-link" graph over observed contexts. It constructs lower certificates for pairwise decision distances. If the data certifies that two contexts $x, x'$ require conflicting actions (i.e., their decision distance exceeds a threshold $\epsilon$), an edge is added to the graph.
2. Budgeted Encoding: At the start of each epoch, DeMem performs a greedy coloring of the cannot-link graph to partition contexts into $K$ slots. This ensures the hard budget is respected.
3. Refinement on Conflict: Memory slots are refined (split) only when data certifies that a shared state would induce a decision conflict. This avoids unnecessary fragmentation.
4. Regret Guarantees: The algorithm provides near-minimax regret guarantees (Theorem 4), separating the unavoidable compression error (due to the $K$-state limit) from the statistical learning error.

3. Key Contributions

1. Decision-Centric Theory: The paper establishes a formal framework for budgeted agent memory, defining an exact forgetting boundary and a memory-distortion frontier based on decision quality rather than descriptive fidelity.
2. Complexity Analysis: It proves that optimal memory partitioning is NP-complete and provides covering/packing bounds that quantify the tradeoff between memory budget and decision loss.
3. DeMem Algorithm: It introduces an online learner that refines memory states only upon certified decision conflict, offering theoretical regret bounds that match the minimax lower bound up to logarithmic factors.
4. Empirical Validation: The method demonstrates consistent gains over strong baselines (including RAG, Mem0, Mnemis, and LangMem) on synthetic diagnostics and long-horizon conversational benchmarks (LoCoMo, LongMemEval, MemoryArena).

4. Experimental Results

The authors evaluate DeMem under a strictly matched answer-time memory budget (measured by character count injected into the model).

• Synthetic Diagnostics: In a "Decoupled Bandit" environment where descriptive features are intentionally misaligned with decision identities, DeMem achieves the lowest cumulative regret and learns the lowest-distortion partition. It outperforms description-aware baselines (Feature-KMeans, Feature-RAG) as the mismatch between description and decision grows.
• LoCoMo Benchmark: DeMem achieves the highest mean overall score (91.1% with GPT-4o-mini, 92.0% with GPT-4.1-mini), significantly outperforming baselines. The gains are most pronounced in Temporal and Open Domain categories, where preserving distinctions across distant interactions is critical.
• LongMemEval & MemoryArena: DeMem maintains superior performance on cross-session integration tasks (MS, TR) and multi-session agentic tasks, achieving the highest success rates in formal reasoning and web search categories.
• Mechanism Analysis:
  • Ablations: Removing "certified splitting" or "decision-aware routing" significantly degrades performance, confirming that the gains stem from the decision-centric organization, not just the slot structure.
  • Evidence Recall: DeMem recovers 83% of gold evidence under a matched budget, compared to 66% for description-based retrieval.
  • Error Attribution: 85% of errors in description-based baselines are traced to evidence miss or dilution caused by the mismatch between descriptive similarity and decision relevance.

5. Significance and Claims

The paper claims that the fundamental unit of analysis for agent memory should be decisions preserved, not information preserved.

• Paradigm Shift: The work challenges the prevailing view that memory should be organized around descriptive salience or semantic similarity. It argues that such criteria are insufficient for agents operating under strict runtime constraints where the goal is action, not reconstruction.
• Principled Forgetting: The framework provides a rigorous criterion for "what to forget": histories can be merged if they do not induce decision conflict. This allows agents to retain the distinctions that matter for action while discarding irrelevant details.
• Architecture Agnosticism: The decision-aware selection criterion is modular and can be integrated as a drop-in component into existing memory systems (e.g., RAG, graph-based memory) to improve performance without altering the underlying storage or generation layers.
• Theoretical Limits: By characterizing the fundamental limits of budgeted memory via rate-distortion theory, the paper provides a benchmark for evaluating future memory systems and highlights the computational irreducibility of optimal memory allocation.

The authors conclude that "memory should preserve the distinctions that matter for decisions, not descriptions," and that DeMem operationalizes this principle to achieve state-of-the-art performance in long-horizon agent tasks under fixed memory budgets.