Towards a Formal Definition of Agent Memory: Basis, Span, Optimality, and the Sequential Memory Problem

This paper takes a first step toward a unified formal account of agent memory, addressing the lack of a formal definition, a measure of optimality, and a formulation of how memory is written. The central idea is that memory is a basis, knowledge is its span, and answerability is a coverage problem. The framework is built on a two-layer separation: an agent stores events (atomic statements about a material), but what answers queries is the knowledge that a set of events entails, generated by a generation operator Φ. A memory MD is defined as a subset of a material's events (MD ⊆ ED), and its span is RMD = Φ(MD). Under a single-item support assumption—where every query is answered by a single knowledge item—a query is answerable exactly when some spanned item covers it, making memory construction a coverage problem: with at most S events, cover as much of the query distribution as possible.

The paper defines the optimal memory as the capacity-constrained maximizer of expected coverage utility, and its value traces the utility–capacity frontier U*D(S), which is the best answerability rate achievable with S events. The frontier saturates at the full-context baseline (storing all events), delimiting the compression zone (S < ED) where memory matters. The frontier provides a common yardstick: any memory system maps to a point in the size–utility plane, and its vertical gap below the frontier is its memory-efficiency loss. The optimization problem reduces to weighted maximum coverage with a greedy (1 − 1/e)-approximation when Φ is decomposable, but in general it is a monotone set-function maximization where cross-event synergy defeats such guarantees.

The paper then considers noise in memory, separating coverage from precision. Under noisy extraction, a memory may contain false claims, so the span splits into a good span (generated only by true claims) and the full span. The precision utility measures whether the good span answers a query, and the difference between coverage and precision utilities is called the water-inflation degree, measuring how much reported memory quality is bought with false claims. The noisy optimal-memory problem targets precision, but the key difficulty is estimating the truth of claims (τ(e)), which is an unobserved latent that must be inferred from settled queries.

To address how memory is written over time, the paper organizes memorization settings into a progressive taxonomy (Levels 0, 1a, 1b, 2) based on what is known and what must be learned, and unifies single- and multi-material writing in a sequential MDP. In this MDP, memory is the state, writing is the action, and the utility settled at query time is the delayed reward. This formulation exposes delayed reward, credit assignment, and trust estimation as the core learning problems. The agent-level memorization objective is defined as maximizing expected cumulative utility over a distribution of materials, subject to a capacity bound.

To make the framework concrete, the paper instantiates it on Homer's Odyssey, computing the frontier, the compression zone, and the divergence of coverage from precision with concrete numbers. For example, with six events and eight queries, the frontier values are U*D(S) = 0.00, 0.35, 0.60, 0.80, 0.90, 0.95, 1.00 for S = 0 through 6, saturating at the full-context baseline of 1.00. The example also shows how cross-event composition creates new knowledge (e.g., pairs of events spanning composite queries) and how a false claim can inflate apparent coverage (e.g., a false claim with apparent mass 0.45 beats a true event's 0.35, but has zero precision utility).

Finally, the paper positions existing memory systems (e.g., MemoryBank, Generative Agents, MemGPT, HippoRAG, Mem0, Reflexion) within the framework, showing they differ mainly in their choices of generation, writing, reading, and reasoning components. It closes by distilling open problems into a research agenda: representing memory and write policies, learning from delayed reward, and generalizing across materials. The framework's limitations include its single-item support assumption (excluding answer-time reasoning), coverage not being correctness, the approximate nature of assumptions on Φ, and its representation-agnostic view of memory (counting capacity in events rather than tokens or storage cost).

Improvements to AI Systems:

1. Optimal Memory Construction via Coverage Maximization

• Implement a memory-write policy that selects events to store based on expected query coverage, using the greedy (1 − 1/e)-approximation for decomposable generation operators.

• The improved system can autonomously decide which facts to store under a fixed capacity, maximizing the probability of answering future queries correctly—useful for long-horizon agents (e.g., personal assistants, robotics) with limited context windows.

2. Noise-Aware Memory with Precision Utility

• Add a trust-estimation module that scores each stored event’s truthfulness (τ(e)) from settled queries, then optimize memory for precision (good span) rather than raw coverage.

• The improved system can reject or down-weight false memories, preventing hallucination-driven answers and reducing water-inflation where apparent competence hides fabricated knowledge—critical for medical, legal, or financial AI.

3. Sequential Memory Writing as an MDP with Delayed Reward

• Train a reinforcement learning policy where the state is current memory, actions are write operations, and rewards are query-time utilities (delayed). Use credit assignment to learn which past events yield future answerability.

• The improved system can adaptively evolve its memory over time, prioritizing events that compound into new knowledge (cross-event synergy) and discarding obsolete ones—enabling lifelong learning without catastrophic forgetting.

4. Unified Memory Benchmarking and Efficiency Diagnostics

• Compute the utility–capacity frontier U*D(S) for a given domain and map any memory system’s (size, utility) point to measure its memory-efficiency loss.

• The improved system can self-diagnose its compression zone (where memory matters) and identify whether performance gaps stem from poor event selection, noisy claims, or insufficient generation—guiding architectural improvements.

5. Cross-Event Composition for Answering Composite Queries

• Use the generation operator Φ to explicitly model how pairs or sets of events entail new knowledge, and prioritize storing events that maximize composite query coverage.

• The improved system can answer multi-hop questions (e.g., Who is the father of the person who killed the suitors?) by storing synergistic events, rather than only single-fact lookups—enhancing reasoning in retrieval-augmented generation.

6. Capacity-Aware Memory Summarization

• Replace token-count capacity with event-count capacity, and use the coverage objective to select a minimal set of events that spans the most probable queries.

• The improved system can compress large knowledge bases into a compact, high-coverage memory (e.g., for edge devices or API cost reduction) while preserving answerability for the most likely user intents.

7. Adaptive Memory Trust Calibration

• Implement a dynamic τ(e) estimator that updates as queries are settled (correct vs. incorrect), and adjust the write policy to favor high-τ events.

• The improved system can recover from initial misinformation by re-weighting memory, gradually improving precision without manual intervention—useful for agents learning from noisy web data or user feedback.

8. Domain-Specific Frontier Prediction

• Precompute or approximate the utility–capacity frontier for new domains using a small sample of queries and events, then use it as a planning target for memory allocation.

• The improved system can predict how much memory is enough for a task (e.g., 95% answerability) and avoid over-storing, saving resources while meeting performance thresholds.

Despite the wide deployment of memory in large-model agents, there is no unified formal account of what a memory is or when it is optimal. This paper takes a first step toward this account. The central idea is that memory is a basis, knowledge is its span, and answerability is a coverage problem: an agent stores events extracted from a material; a generation operator turns any event set into the knowledge it entails; and a query is answerable exactly when some single item in the span covers it. The optimal memory is then the capacity-constrained maximizer of expected coverage, and its value traces a utility--capacity frontier, the common yardstick on which memory systems can be compared. Next, we consider noise in the memory and discuss coverage versus precision under it: a memory may store false claims, so the write policy must infer the truth of what it stores. Drawing an analogy with biological memory, which is formed continuously through ongoing experience, we formalize the continual agent-memory problem in a sequential MDP that covers multiple levels, where memory is the state, writing is the action, and the utility settled at query time is the delayed reward that drives learning. To make the framework concrete, we instantiate it on Homer's Odyssey, turning the frontier, the compression zone, and the divergence of coverage from precision into concrete numbers. Finally, we position existing systems within the framework, making ``how good is a memory'' measurable and recasting the open problems of constructing and learning agent memory as concrete research questions.