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

# Towards a Formal Definition of Agent Memory: Basis, Span, Optimality, and the Sequential Memory Problem
Source: [https://arxiv.org/html/2608.11654](https://arxiv.org/html/2608.11654)
###### Abstract

#### Abstract

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\.

*“Tell me, Muse, of the man of many ways, who was driven far journeys …”*

*\(the Muse is the daughter of Mnemosyne, the goddess of memory\)*

— Homer,*The Odyssey*1\.1, trans\. R\. Lattimore \(1965\)

## 1Introduction

Modern LLM agents accumulate interaction histories \(dialogues, documents, observation streams\) that quickly exceed the context window\([Bai et al\. 2024](https://arxiv.org/html/2608.11654#bib.bib1)\), and increasingly manage them with explicit memory modules that store, retrieve, and update over time\([Packer et al\. 2023](https://arxiv.org/html/2608.11654#bib.bib16);[Park et al\. 2023](https://arxiv.org/html/2608.11654#bib.bib17)\)\. Memory has become central to agent design, and a growing family of systems, from hierarchical page stores\([Packer et al\. 2023](https://arxiv.org/html/2608.11654#bib.bib16)\)and knowledge graphs\([Jiménez Gutiérrez et al\. 2024](https://arxiv.org/html/2608.11654#bib.bib9)\)to reflection\-based reasoning\([Shinn et al\. 2023](https://arxiv.org/html/2608.11654#bib.bib21)\)and reinforcement\-learned writing\([Yu et al\. 2026](https://arxiv.org/html/2608.11654#bib.bib29)\), attests to its practical importance\.

The literature uses the word for conversation summaries, knowledge graphs, reflection texts, and parameter updates alike; “memory quality” is measured differently from benchmark to benchmark; and optimality is rarely even posed as a problem\([Du et al\. 2025](https://arxiv.org/html/2608.11654#bib.bib6)\)\. The brain sciences, by contrast, have long studied memory as a structured object: episodic and semantic memory are distinguished\([Tulving 1972](https://arxiv.org/html/2608.11654#bib.bib23)\), and their interaction is characterized through complementary learning systems\([Kumaran et al\. 2016](https://arxiv.org/html/2608.11654#bib.bib13)\)\. For large model agents, memory remains an undefined word rather than such an object\. The result is a fragmented space of methods that cannot be compared on a common scale, and a field that cannot yet state its most basic questions\.

1What is a memory for an agent, and how should it be formally defined?2What makes a memory good, and what is an optimal memory?3How should a memory be written, and how should its problem settings be defined?

In this paper, we make our preliminary attempt to answer the three questions above by developing a single formal framework for agent memory\. The framework supplies the three things the field lacks, one for each question: a formal definition of what a memory is, a measure of when a memory is optimal, and a formulation of how a memory is written\.

We begin with the definition\. It rests on a two\-layer separation: an agent stores*events*, atomic statements about a material, but events are not what answer queries; what answers a query is the*knowledge*that a set of events entails\. On this we build the paper’s central idea,memory is a basis, knowledge is its span, and answerability is a coverage problem: a memory is a subset of the events extracted from a material, a generation operatorΦ\\Phimaps any event set to the knowledge it entails, and the span of a memory is what the agent can actually draw on\. Under a single\-item support principle \(every query is answered by a single knowledge item\), a query is answerable exactly when some spanned item covers it, so memory construction becomes a coverage problem: with at mostSSevents, cover as much of the query distribution as possible\.

With the definition in hand, what makes a memory good becomes a well\-posed optimization\. The optimal memory is the capacity\-constrained maximizer of expected coverage, and its value traces theutility–capacity frontier, the best answerability rate achievable withSSevents\. The frontier saturates at the full\-context baseline and delimits the*compression zone*in which memory matters; it maps every memory system to a point in the size–utility plane, where the gap below the frontier is what a write policy loses, and it is the common yardstick on which memory systems can be compared\.

The hardest of the three questions is how a memory gets written, and two features of the real setting make it hard\. Extraction is noisy, so we separatecoverage from precisionand measure how much of a memory’s reported quality is bought with false claims, the*water\-inflation degree*\. The query distribution is unknown, so writing must be learned from queries disclosed one at a time; we organize the settings of memorization into a progressive taxonomy and unify single\- and multi\-material writing in asequential MDP, exposing delayed reward, credit assignment, and trust estimation as the core learning problem\.

To make our formal framework concrete, we present an illustrative example based on Homer’s*Odyssey*, computing the framework’s objects in full so that the frontier, the compression zone, and the divergence of coverage from precision become concrete numbers\. Further, we map representative memory systems onto the framework, showing where existing methods sit and how they become comparable, and we close by distilling the problems left open into a research agenda and stating the framework’s limitations\.

We make the following contributions, the first three answering the three questions above\.

- •A formal definition of agent memory\.Memory is an event subset of a material, and its span is the knowledge the events generate; explicit assumptions \(self\-containment, monotonicity\) together with single\-item support make the object well\-defined and push composition into the generation layer\.
- •An optimality theory and a common yardstick\.The optimal memory is the capacity\-constrained maximizer of a coverage utility, and its value traces the utility–capacity frontier, delimiting the compression zone in which memory matters\. The underlying optimization reduces to weighted maximum coverage with a greedy\(1−1e\)\(1\-\\tfrac\{1\}\{e\}\)\-approximation when the operator is decomposable, and to monotone set\-function maximization in general, where cross\-event synergy defeats such guarantees\.
- •Memorization under noise and over time\.We separate coverage from precision under noisy extraction, organize the settings of memorization into a progressive taxonomy, and unify single\- and multi\-material writing in a sequential MDP, framing writing as a learning problem of delayed reward and credit assignment\.
- •A positioning of existing systems and a research agenda\.We map representative memory systems onto the framework, showing that the field’s methods differ mainly in their choices of generation, writing, reading, and reasoning components, and we turn the problems this leaves open into a concrete research agenda\.

The rest of the paper is organized as follows\. Section[2](https://arxiv.org/html/2608.11654#S2)formalizes events, knowledge, the generation operator, and coverage utility\. Section[3](https://arxiv.org/html/2608.11654#S3)defines optimal memory and the utility–capacity frontier\. Section[4](https://arxiv.org/html/2608.11654#S4)extends the definition to noisy extraction\. Section[5](https://arxiv.org/html/2608.11654#S5)organizes problem settings into a progressive taxonomy and unifies them in a sequential MDP\. Section[6](https://arxiv.org/html/2608.11654#S6)gives an illustrative example, Section[7](https://arxiv.org/html/2608.11654#S7)reviews related work through the framework, and Section[8](https://arxiv.org/html/2608.11654#S8)discusses a research agenda and the framework’s limitations\.

## 2Defining Agent Memory: Basis and Span

The framework rests on three ingredients: what memory stores, what it entails, and how to measure whether it helps\. This section fixes each in turn\. Section[2\.1](https://arxiv.org/html/2608.11654#S2.SS1)separates the stored surface of a material from the knowledge it entails; Section[2\.2](https://arxiv.org/html/2608.11654#S2.SS2)turns knowledge into answerability and then into a utility; Section[2\.3](https://arxiv.org/html/2608.11654#S2.SS3)states the assumptions on the generation operator that give the theory its structure\.

### 2\.1Events, Knowledge, and Memory

Memory operates on raw material: documents, conversations, observation streams, and multimodal sources such as image\-text articles or videos\. To make memory precise we keep two layers apart\. The surface layer is what an agent literally stores,*events*\(atomic statements about the material\); the semantic layer is what those events entail,*knowledge*\. We define the two in turn\.

###### Definition 2\.1\(Events and materials\)\.

LetEEbe a space of\\newtermevents\. We use*event*broadly: an evente∈Ee\\in Eis an atomic statement about a material, whether a happening \(a fact\), a preference, a rule, or a reflection, typically as simple as a subject–predicate–object tuple\. A\\newtermmaterialDDis a long source of information \(a text, a conversation, an observation stream, an image\-text article, a video\); we writeED⊆EE\_\{D\}\\subseteq Efor the set of events contained inDD\.

Events are the unit of storage, but events are not what answer queries\. A raw event \(“the supplier raised prices in March”\) is too low\-level for most questions; what answers a query is the knowledge that a set of events supports \(“why did costs rise?”\)\. We therefore introduce a generation operator that maps any set of events to the knowledge it entails\.

###### Definition 2\.2\(Knowledge and the generation operator\)\.

A\\newtermknowledge itemn∈Nn\\in Nis an atomic, self\-contained unit of information\. The\\newtermgeneration operatorΦ:2E→2N\\Phi:2^\{E\}\\to 2^\{N\}maps a set of eventsA⊆EA\\subseteq Eto the set of knowledge they generate:

n∈Φ\(A\)⊆N⟺nis generated byA\.n\\in\\Phi\(A\)\\subseteq N\\quad\\Longleftrightarrow\\quad n\\text\{ is generated by \}A\.\(1\)A single event is a degenerate knowledge item, i\.e\.E⊂NE\\subset N\. For a materialDDwe writeND=Φ⁡\(ED\)N\_\{D\}=\\Phi\(E\_\{D\}\)for the knowledge contained inDD\.

Events and the generation operator give us the raw ingredients, but the object this paper studies has not yet been named\.

###### Definition 2\.3\(Memory\)\. A\\newtermmemory of a materialDDis a subset of its events,MD⊆ED\.M\_\{D\}\\subseteq E\_\{D\}\.\(2\)In the basis\-and\-span view, the stored events form a\\newtermbasis, and the knowledge they generate,RMD=Φ⁡\(MD\),R\_\{M\_\{D\}\}=\\Phi\(M\_\{D\}\),\(3\)is the\\newtermspan of the memory\. The whole material is the maximal memoryEDE\_\{D\}, whose span is the full knowledgeNDN\_\{D\}\.

Definition[2\.3](https://arxiv.org/html/2608.11654#S2.Thmtheorem3)is the object this paper is about: a memory is a basis of events, and its span is what the agent can actually draw on\. The material’s full knowledgeND=Φ⁡\(ED\)N\_\{D\}=\\Phi\(E\_\{D\}\)is the span of the maximal memory, and any smaller memory forgoes part of it\. The gap betweenRMDR\_\{M\_\{D\}\}andNDN\_\{D\}is the knowledge a memory forgoes, and its utility cost is the query mass the span leaves uncovered; keeping that uncovered mass small is the subject of the rest of the paper\. Figure[1](https://arxiv.org/html/2608.11654#S2.F1)summarizes the two\-layer picture\.

Homer’sOdysseyEvent“Penelope waited twenty years”Knowledge“away from home twenty years”Query“How many years away from home?”answer: “twenty years”CoverageSpanBasisMaterialDDExtractEDE\_\{D\}e1e\_\{1\}e2e\_\{2\}e3e\_\{3\}e4e\_\{4\}e5e\_\{5\}e6e\_\{6\}e7e\_\{7\}e8e\_\{8\}MemoryMD⊆EDM\_\{D\}\\subseteq E\_\{D\}\|MD\|≤S\|M\_\{D\}\|\\leq Sthe rest ofEDE\_\{D\}not in memorySpan byΦ\\Phinan\_\{a\}nbn\_\{b\}ncn\_\{c\}ndn\_\{d\}na​bn\_\{ab\}na​cn\_\{ac\}nb​cn\_\{bc\}na​b​cn\_\{abc\}nen\_\{e\}nfn\_\{f\}ngn\_\{g\}nhn\_\{h\}ne​fn\_\{ef\}ne​gn\_\{eg\}ne​hn\_\{eh\}nf​gn\_\{fg\}nf​hn\_\{fh\}ng​hn\_\{gh\}RMD=Φ⁡\(MD\)R\_\{M\_\{D\}\}=\\Phi\(M\_\{D\}\)ND=Φ⁡\(ED\)N\_\{D\}=\\Phi\(E\_\{D\}\)Queriesq∼pDq\\sim p\_\{D\}q1q\_\{1\}q2q\_\{2\}q3q\_\{3\}q4q\_\{4\}q6q\_\{6\}q5q\_\{5\}q7q\_\{7\}⋯\\cdotsanswerable only from the full materialFigure 1:Memory is a basis; knowledge is its span\. Extracting the eventsEDE\_\{D\}from a materialDDand storing at mostSSof them forms a memoryMD⊆EDM\_\{D\}\\subseteq E\_\{D\}, the dashed box inside the full event set; monotonicity ofΦ\\Phithen lifts the memory to a spanRMD=Φ⁡\(MD\)R\_\{M\_\{D\}\}=\\Phi\(M\_\{D\}\), drawn as the purple box nested inside the full knowledgeND=Φ⁡\(ED\)N\_\{D\}=\\Phi\(E\_\{D\}\)\(gray box\):RMD⊆NDR\_\{M\_\{D\}\}\\subseteq N\_\{D\}\. Under single\-item support a query is answerable exactly when some spanned item covers it \(dashed edges\)\. Queries are drawn from the material’s query distributionpDp\_\{D\}: the purple queries are covered by the memory’s span, while the gray queriesq5,q6,q7,…q\_\{5\},q\_\{6\},q\_\{7\},\\ldotsare answerable only from the full material, the cost of compression\. The itemna​bn\_\{ab\}is spanned bye1e\_\{1\}ande2e\_\{2\}jointly: composition happens insideΦ\\Phi\. The left column instantiates the chain concretely on the*Odyssey*\.
### 2\.2Query Answering with Memory

A memory is useful only insofar as it makes queries answerable\. We define answerability at the level of a single knowledge item, then lift it to memories through an assumption about how items combine\.

###### Definition 2\.4\(Answerability\)\.

Let𝒬\\mathcal\{Q\}be a space of queries\. The atomic relationans⁡\(n,q\)∈\{0,1\}\\mathrm\{ans\}\(n,q\)\\in\\\{0,1\\\}indicates whether the single knowledge itemnnsuffices to answer the queryqq\. The\\newtermanswerable set ofnnis

𝒬⁡\(n\)=\{q∈𝒬:ans⁡\(n,q\)=1\}\.\\mathcal\{Q\}\(n\)=\\big\\\{\\,q\\in\\mathcal\{Q\}:\\mathrm\{ans\}\(n,q\)=1\\,\\big\\\}\.\(4\)

Each knowledge item thus covers a set of queries,𝒬⁡\(n\)\\mathcal\{Q\}\(n\): the questions it alone suffices to answer\. Whether a whole memory answers a query then depends on how these item\-level sets combine, and here we make the central assumption of the framework\.

\{assumption\}

\[Single\-item support\] Every query is answered by a single knowledge item: composition and reasoning do not happen at answer time but are pushed into the generation operatorΦ\\Phi\. Equivalently, a knowledge setKKanswersqqif and only ifq∈⋃n∈K𝒬⁡\(n\)q\\in\\bigcup\_\{n\\in K\}\\mathcal\{Q\}\(n\)\.

This assumption is a design choice, and it is worth saying what it buys and what it costs\. It rules out joint reasoning at answer time: the agent does not combine items on the fly to answer a query, and every chain of reasoning must already be realized insideΦ\\Phiand materialized as a single knowledge item\. The payoff is that answerability becomes a pure coverage question, which makes optimal memory construction a well\-defined optimization problem \(Section[3](https://arxiv.org/html/2608.11654#S3)\)\.

###### Definition 2\.5\(Coverage utility\)\.

The\\newtermcoverage utility of a memoryMDM\_\{D\}on a queryqqis

u\(q,MD\)=𝟏\[q∈⋃n∈Φ⁡\(MD\)𝒬\(n\)\]∈\{0,1\},u\(q,M\_\{D\}\)=\\mathbf\{1\}\\Big\[\\,q\\in\\bigcup\_\{n\\in\\Phi\(M\_\{D\}\)\}\\mathcal\{Q\}\(n\)\\,\\Big\]\\in\\\{0,1\\\},\(5\)whether the memory’s spanned knowledge contains a single item that answersqq\.

The utility has an explicit coverage structure: the answerable set of a memory is the union⋃n∈Φ⁡\(MD\)𝒬⁡\(n\)\\bigcup\_\{n\\in\\Phi\(M\_\{D\}\)\}\\mathcal\{Q\}\(n\), so the expected utility𝔼q∼pD​\[u⁡\(q,MD\)\]\\mathbb\{E\}\_\{q\\sim p\_\{D\}\}\\big\[u\(q,M\_\{D\}\)\\big\]is the probability that a query drawn from the material’s query distribution is covered by the memory’s span\. Optimal memory construction is therefore a coverage problem: use at mostSSevents to cover as much query mass as possible \(Section[3](https://arxiv.org/html/2608.11654#S3)\)\.

Coverage is not correctness\. The utility above records only whether the necessary information is present in memory, not whether the agent produces the right answer\. We keep these two concerns apart\.

###### Definition 2\.6\(End\-to\-end utility\)\.

The coverage utility measures only whether necessary information is available; it does not measure whether the agent answers correctly\. We separately define the\\newtermend\-to\-end utility

ue2e​\(q,MD,πreasoner\)=𝟏​\[Correct⁡\(πreasoner​\(q,MD\),q\)\],u^\{\\mathrm\{e2e\}\}\\big\(q,M\_\{D\},\\pi\_\{\\mathrm\{reasoner\}\}\\big\)=\\mathbf\{1\}\\big\[\\,\\mathrm\{Correct\}\\big\(\\pi\_\{\\mathrm\{reasoner\}\}\(q,M\_\{D\}\),\\,q\\big\)\\,\\big\],\(6\)whereπreasoner\\pi\_\{\\mathrm\{reasoner\}\}is the reasoning policy andCorrect⁡\(⋅,q\)\\mathrm\{Correct\}\(\\cdot,q\)judges whether an output correctly answersqq\. The reasoner is understood to answer from the retrieved subset of the memory’s span \(Section[7](https://arxiv.org/html/2608.11654#S7)\)\. Throughout we take the*proxy stance*that, under noise\-free memory, sufficient information approximately equals answerability, and we optimizeuu; whether the reasoner makes good use of available information is treated as a separate layer\.

So far the utility is defined for a single query\. To optimize a memory we need to weigh queries and materials, which brings us to distributions\.

###### Definition 2\.7\(Query and material distributions\)\.

For a materialDD,pD​\(q\)p\_\{D\}\(q\)denotes the distribution over queries that an agent is expected to face forDD\(in long interactive settings, the questions a user is likely to ask\)\.p⁡\(D\)p\(D\)denotes a distribution over materials\. Both are typically unknown and must be estimated from sequentially disclosed queries \(Section[5](https://arxiv.org/html/2608.11654#S5)\)\.

### 2\.3Assumptions on the Generation Operator

The theory’s structure rests on two defaults aboutΦ\\Phi, which in practice is an abstract procedure implemented by an LLM performing extraction, induction, and summarization\. We assume\\newtermself\-containment \(Assumption[11](https://arxiv.org/html/2608.11654#S11)\): storing an event never throws it away\. We assume\\newtermmonotonicity \(Assumption[11](https://arxiv.org/html/2608.11654#S11)\): more memory is never worse, so coverage is non\-decreasing in the stored set\. Two deliberate omissions matter as much\. We do*not*assume\\newtermdecomposability: cross\-event composition can generate knowledge that no single event yields, which is exactly how a few events span more than the sum of their parts, and what makes the optimality problem of Section[3](https://arxiv.org/html/2608.11654#S3)harder in general\. And real extraction meets these properties only approximately: an LLM is at best*locally*monotone, so injecting a conflicting fact can overturn earlier conclusions\. The full statements, with the rationale and the consequences of relaxing each assumption, are given in Appendix[11](https://arxiv.org/html/2608.11654#S11)\.

## 3Optimal Memory and the Utility–Capacity Frontier

This section gives the question “what is a good memory” a precise answer\. Optimality is always relative to a materialDDand a query distributionpDp\_\{D\}\(or, when marginalized over a material distributionp⁡\(D\)p\(D\), relative to a family of materials, Section[5](https://arxiv.org/html/2608.11654#S5)\)\. Two conventions keep the treatment honest\. First, “optimal memory” is really a property of the*writing*that produces it, so we study memoriesMD=πwrite​\(D\)M\_\{D\}=\\pi\_\{\\mathrm\{write\}\}\(D\)generated by a write policy\. Second, we defer the representation ofMDM\_\{D\}\(graphs, hierarchical pages, parameter vectors\): the account here is about what to store, not how to lay it out\.

### 3\.1Optimal Memory and Write Policy

A\\newtermwrite policy turns a material into a memory,πwrite​\(D\)⊆ED\\pi\_\{\\mathrm\{write\}\}\(D\)\\subseteq E\_\{D\}, and the\\newtermoptimal memory is any maximizer of the expected coverage utility \(Definition[2\.5](https://arxiv.org/html/2608.11654#S2.Thmtheorem5)\)\. By monotonicity \(Section[2\.3](https://arxiv.org/html/2608.11654#S2.SS3)\) this is trivial without a budget: storing every event attains the maximum \(Proposition[3\.2](https://arxiv.org/html/2608.11654#S3.Thmtheorem2)\), so the unconstrained statement and its tied maximizers are spelled out in Appendix[12](https://arxiv.org/html/2608.11654#S12)\. Memory matters precisely because capacity is limited, so from here on we optimize under a bound\.

###### Definition 3\.1\(Optimal memory of constrained capacity\)\. With a capacity boundSS, the\\newtermcapacity\-constrained optimal memory isMD∗​\(S\)=arg⁡maxMD⊆ED\|MD\|≤S​𝔼q∼pD​\[u⁡\(q,MD\)\],M^\{\*\}\_\{D\}\(S\)=\\arg\\max\_\{\\begin\{subarray\}\{c\}M\_\{D\}\\subseteq E\_\{D\}\\\\ \|M\_\{D\}\|\\leq S\\end\{subarray\}\}\\ \\mathbb\{E\}\_\{q\\sim p\_\{D\}\}\\big\[\\,u\(q,M\_\{D\}\)\\,\\big\],\(7\)and the value it attains defines the\\newtermutility–capacity frontierUD∗​\(S\)=maxMD⊆ED\|MD\|≤S⁡𝔼q∼pD​\[u⁡\(q,MD\)\]\.U^\{\*\}\_\{D\}\(S\)=\\max\_\{\\begin\{subarray\}\{c\}M\_\{D\}\\subseteq E\_\{D\}\\\\ \|M\_\{D\}\|\\leq S\\end\{subarray\}\}\\ \\mathbb\{E\}\_\{q\\sim p\_\{D\}\}\\big\[\\,u\(q,M\_\{D\}\)\\,\\big\]\.\(8\)The\\newtermcapacity\-constrained optimal write policy is anyπwrite∗\\pi\_\{\\mathrm\{write\}\}^\{\*\}whose output attains this optimum; the frontier valueUD∗​\(S\)U^\{\*\}\_\{D\}\(S\)is exactly the utility such a policy attains\.

Becauseuuis a\{0,1\}\\\{0,1\\\}indicator, the expected utility is a probability,𝔼q∼pD\[u\(q,MD\)\]=Prq∼pD\[u\(q,MD\)=1\]\\mathbb\{E\}\_\{q\\sim p\_\{D\}\}\\big\[u\(q,M\_\{D\}\)\\big\]=\\Pr\_\{q\\sim p\_\{D\}\}\\big\[u\(q,M\_\{D\}\)=1\\big\]: the chance that a random query is answerable from the memory’s span\. The frontierUD∗​\(S\)U^\{\*\}\_\{D\}\(S\)is thus the\\newtermquery answerability rate achievable withSSevents, and it is the number on which different memory systems can be compared on a common scale: a system’s memory is good insofar as it reaches a high point of the frontier at a small size\.

### 3\.2Properties of the Frontier

The frontier inherits its shape from the generation operator\. Under monotonicity, it settles into a clean picture\.

###### Proposition 3\.2\(Monotonicity of utility\)\.

Under Assumption[11](https://arxiv.org/html/2608.11654#S11), for anyMD⊆MD′⊆EDM\_\{D\}\\subseteq M^\{\\prime\}\_\{D\}\\subseteq E\_\{D\}and any queryqq,u⁡\(q,MD\)≤u⁡\(q,MD′\)u\(q,M\_\{D\}\)\\leq u\(q,M^\{\\prime\}\_\{D\}\); hence the expected utilityMD↦𝔼q∼pD​\[u⁡\(q,MD\)\]M\_\{D\}\\mapsto\\mathbb\{E\}\_\{q\\sim p\_\{D\}\}\\big\[u\(q,M\_\{D\}\)\\big\]is non\-decreasing\.

###### Proof 3\.3\.

IfMD⊆MD′M\_\{D\}\\subseteq M^\{\\prime\}\_\{D\}, thenΦ⁡\(MD\)⊆Φ⁡\(MD′\)\\Phi\(M\_\{D\}\)\\subseteq\\Phi\(M^\{\\prime\}\_\{D\}\)by monotonicity, so the union⋃n∈Φ⁡\(MD\)𝒬⁡\(n\)\\bigcup\_\{n\\in\\Phi\(M\_\{D\}\)\}\\mathcal\{Q\}\(n\)is contained in⋃n∈Φ⁡\(MD′\)𝒬⁡\(n\)\\bigcup\_\{n\\in\\Phi\(M^\{\\prime\}\_\{D\}\)\}\\mathcal\{Q\}\(n\), and the indicator of Definition[2\.5](https://arxiv.org/html/2608.11654#S2.Thmtheorem5)is non\-decreasing\.

###### Proposition 3\.4\(Frontier saturation\)\.

Under Assumption[11](https://arxiv.org/html/2608.11654#S11), the utility–capacity frontier is non\-decreasing inSS, andUD∗​\(S\)=𝔼q∼pD​\[u⁡\(q,ED\)\]U^\{\*\}\_\{D\}\(S\)=\\mathbb\{E\}\_\{q\\sim p\_\{D\}\}\\big\[u\(q,E\_\{D\}\)\\big\]for everyS≥\|ED\|S\\geq\|E\_\{D\}\|: with enough capacity, the trivial memory that stores everything is optimal\.

###### Proof 3\.5\.

The feasible set\{MD⊆ED:\|MD\|≤S\}\\\{M\_\{D\}\\subseteq E\_\{D\}:\|M\_\{D\}\|\\leq S\\\}grows withSS, so the maximum is non\-decreasing\. ForS≥\|ED\|S\\geq\|E\_\{D\}\|the full setEDE\_\{D\}is feasible and, by Proposition[3\.2](https://arxiv.org/html/2608.11654#S3.Thmtheorem2), dominates every other memory\.

Proposition[3\.4](https://arxiv.org/html/2608.11654#S3.Thmtheorem4)gives the definition its empirical content\. It identifies a\\newtermfull\-context baseline: the value𝔼q∼pD​\[u⁡\(q,ED\)\]\\mathbb\{E\}\_\{q\\sim p\_\{D\}\}\\big\[u\(q,E\_\{D\}\)\\big\]that an agent achieves by keeping the entire material in context\. Because the frontier saturates at this value, memory genuinely matters only in the\\newtermcompression zone, the regimeS<\|ED\|S<\|E\_\{D\}\|in which a few events must span knowledge as close as possible to the full\-context level\. The vertical gap betweenUD∗​\(S\)U^\{\*\}\_\{D\}\(S\)and the baseline is exactly the cost of compression\.

The frontier also gives every write policy a yardstick\. A policyπ\\piproduces a memory of size\|π⁡\(D\)\|\|\\pi\(D\)\|with expected utility𝔼q∼pD​\[u⁡\(q,π⁡\(D\)\)\]\\mathbb\{E\}\_\{q\\sim p\_\{D\}\}\\big\[u\(q,\\pi\(D\)\)\\big\], so it defines a point on or below the frontier; its vertical distance fromUD∗​\(\|π⁡\(D\)\|\)U^\{\*\}\_\{D\}\(\|\\pi\(D\)\|\)is the\\newtermmemory\-efficiency loss of the policy\. The three gaps are distinct: the\\newtermspan gapRMDR\_\{M\_\{D\}\}vsNDN\_\{D\}says what a memory fails to span; the compression cost is the vertical gap between the frontier and the full\-context baseline, paid by optimal compression itself; the memory\-efficiency loss is a policy’s vertical gap to the frontier at its own capacity\. Section[6](https://arxiv.org/html/2608.11654#S6)computesUD∗​\(S\)U^\{\*\}\_\{D\}\(S\)on a hand\-checked instance and reads the compression cost and the memory\-efficiency loss off it\.

### 3\.3Solving Optimal Memory as Maximum Coverage

The capacity\-constrained problem is a set\-function maximization, and its tractability hinges on howΦ\\Phicomposes events\. To see why, view each eventeethrough the only thing that makes it useful: the set of queries its knowledge answers, which we denote

Se=⋃n∈Φ⁡\(\{e\}\)𝒬⁡\(n\)\.S\_\{e\}=\\bigcup\_\{n\\in\\Phi\(\\\{e\\\}\)\}\\mathcal\{Q\}\(n\)\.\(9\)Choosing a memory of size at mostSSis then choosing at mostSSof these query sets, and the value of the choice is the query mass they cover\. Whether this is the whole story depends on whether the sets combine additively: whenΦ\\Phidecomposes, a memory’s coverage is exactly the union of its events’ sets; when events interact, the union is enriched by knowledge that no single event yields\. The following proposition characterizes these two extremes\.

###### Proposition 3\.6\(The complexity of optimal memory\)\. LetΦ\\Phibe monotone\.\(a\)IfΦ\\Phiis decomposable,Φ⁡\(MD\)=⋃e∈MDΦ⁡\(\{e\}\)\\Phi\(M\_\{D\}\)=\\bigcup\_\{e\\in M\_\{D\}\}\\Phi\(\\\{e\\\}\), thenUD∗​\(S\)U^\{\*\}\_\{D\}\(S\)equals the value of a weighted maximum\-coverage instance over the per\-event query setsSeS\_\{e\}defined above, with element weightpD​\(q\)p\_\{D\}\(q\)\. This optimization is NP\-hard, and the greedy algorithm attains the classical\(1−1e\)\(1\-\\tfrac\{1\}\{e\}\)\-approximation\.\(b\)In general, the objectiveMD↦𝔼q∼pD​\[u⁡\(q,MD\)\]M\_\{D\}\\mapsto\\mathbb\{E\}\_\{q\\sim p\_\{D\}\}\\big\[u\(q,M\_\{D\}\)\\big\]is a monotone set function \(Proposition[3\.2](https://arxiv.org/html/2608.11654#S3.Thmtheorem2)\) but need not be submodular \(Remark[12\.6](https://arxiv.org/html/2608.11654#S12.Thmtheorem6)\): the reduction to maximum coverage fails, and no greedy\-style guarantee applies\.

###### Proof 3\.7\(Proof sketch\)\.

Under decomposability the expected utility equals the total query mass covered by the chosen events, the value of a weighted maximum\-coverage instance; the classical NP\-hardness and\(1−1e\)\(1\-\\tfrac\{1\}\{e\}\)greedy guarantee then apply\. Part \(b\) follows from Proposition[3\.2](https://arxiv.org/html/2608.11654#S3.Thmtheorem2)together with Remark[12\.6](https://arxiv.org/html/2608.11654#S12.Thmtheorem6); the complete argument is given in Appendix[12](https://arxiv.org/html/2608.11654#S12)\.

Taken together, the two cases give the section’s conclusion in plain terms\. With a decomposable operator, optimal memory is a coverage purchase: buy theSSevents that cover the most query mass, and greedy buying stays within the factor\(1−1/e\)\(1\-1/e\)of the best possible\. With interacting events, the purchase intuition survives but the guarantee does not: once marginal returns can grow, no off\-the\-shelf approximate algorithm applies\. The tension is fundamental rather than incidental: the cross\-event synergy behind a span’s power is exactly what defeats the greedy argument\. This is also the first place the framework points beyond one\-shot optimization: when the query distribution is itself unknown \(Section[5](https://arxiv.org/html/2608.11654#S5)\), the objective𝔼q∼pD\\mathbb\{E\}\_\{q\\sim p\_\{D\}\}cannot even be evaluated, and writing must be learned sequentially rather than solved in one shot\.

## 4Noisy Memory: Coverage versus Precision

So far memory could contain only true events\. Real extraction is noisy: the LLM that implementsΦ\\Phiand the extraction step may hallucinate, quote out of context, or inject claims that contradict the material\. This section drops the assumption that memory is error\-free, and separates two quantities that noise drives apart: how much a memory*covers*and how much of that coverage is*correct*\.

### 4\.1Claims and the Precision Gap

###### Definition 4\.1\(Claims\)\.

A\\newtermclaim is a candidate event: an atomic statement produced by the extraction step, which may or may not be true of the material\. We writeE^D⊇ED\\hat\{E\}\_\{D\}\\supseteq E\_\{D\}for the set of claims extracted from a materialDD, so that a memory is now anyMD⊆E^DM\_\{D\}\\subseteq\\hat\{E\}\_\{D\}\. The generation operator is defined on atomic statements, so it applies to claims as well as events: for any claim set,Φ⁡\(MD\)\\Phi\(M\_\{D\}\)is the knowledge the stored statements would support, whether they are true or not\. Each claimeecarries a truth valueτ⁡\(e\)∈\{0,1\}\\tau\(e\)\\in\\\{0,1\\\}, whethereeis true of the material \(or the world\); the true claims are exactly the events of Definition[2\.1](https://arxiv.org/html/2608.11654#S2.Thmtheorem1),ED=\{e∈E^D:τ⁡\(e\)=1\}E\_\{D\}=\\\{e\\in\\hat\{E\}\_\{D\}:\\tau\(e\)=1\\\}\. The truth value may be relaxed to a confidenceτ⁡\(e\)∈\[0,1\]\\tau\(e\)\\in\[0,1\]\.

A memory that may contain false claims no longer reliably reflects what the agent knows, so the span splits in two:

RMD=Φ⁡\(MD\),RMDgood=Φ⁡\(MD∩ED\)\.R\_\{M\_\{D\}\}=\\Phi\(M\_\{D\}\),\\qquad R\_\{M\_\{D\}\}^\{\\mathrm\{good\}\}=\\Phi\\big\(M\_\{D\}\\cap E\_\{D\}\\big\)\.\(10\)The first is what the memory*believes*it knows; the second, the\\newtermgood span, is what it*truly*knows, since it is generated only by true claims\. This presumes thatΦ\\Phiis reliable on true inputs; failures of that default belong to the end\-to\-end layer \(Definition[2\.6](https://arxiv.org/html/2608.11654#S2.Thmtheorem6)\)\.

The coverage utility of Definition[2\.5](https://arxiv.org/html/2608.11654#S2.Thmtheorem5)ignores truth; where the contrast with a truth\-aware variant matters, we denote the coverage utility byucovu^\{\\mathrm\{cov\}\}\.

###### Definition 4\.2\(Precision utility\)\.

The\\newtermprecision utility is

uprec\(q,MD\)=𝟏\[q∈⋃n∈Φ⁡\(MD∩ED\)𝒬\(n\)\],u^\{\\mathrm\{prec\}\}\(q,M\_\{D\}\)=\\mathbf\{1\}\\Big\[\\,q\\in\\bigcup\_\{n\\in\\Phi\(M\_\{D\}\\cap E\_\{D\}\)\}\\mathcal\{Q\}\(n\)\\,\\Big\],\(11\)whether the memory’s good span contains a single knowledge item that answersqq\.

###### Proposition 4\.3\(Precision is bounded by coverage\)\.

Under Assumption[11](https://arxiv.org/html/2608.11654#S11), for everyqqandMDM\_\{D\},uprec​\(q,MD\)≤ucov​\(q,MD\)u^\{\\mathrm\{prec\}\}\(q,M\_\{D\}\)\\leq u^\{\\mathrm\{cov\}\}\(q,M\_\{D\}\), and therefore, for any write policyπ\\pi,

Δ⁡\(π\)=𝔼q∼pD​\[ucov​\(q,π⁡\(D\)\)−uprec​\(q,π⁡\(D\)\)\]≥0\.\\Delta\(\\pi\)=\\mathbb\{E\}\_\{q\\sim p\_\{D\}\}\\big\[\\,u^\{\\mathrm\{cov\}\}\(q,\\pi\(D\)\)\-u^\{\\mathrm\{prec\}\}\(q,\\pi\(D\)\)\\,\\big\]\\geq 0\.\(12\)

###### Proof 4\.4\(Proof sketch\)\.

Every true claim is a claim, so the good span is a subset of the span and precision can only fall below coverage\. The complete proof is given in Appendix[13](https://arxiv.org/html/2608.11654#S13)\.

The differenceΔ⁡\(π\)\\Delta\(\\pi\)measures how much of a policy’s coverage survives only because the memory stores false claims; we call it the\\newtermwater\-inflation degree of the policy\. A policy whoseucovu^\{\\mathrm\{cov\}\}is high but whoseuprecu^\{\\mathrm\{prec\}\}is low reports a water\-inflated score whose cost is paid at the end\-to\-end layer: false knowledge can mislead the reasoner and, because a conflicting claim can overturn previous conclusions whenΦ\\Phiis only locally monotone \(Remark[11\.3](https://arxiv.org/html/2608.11654#S11.Thmtheorem3), Appendix[11](https://arxiv.org/html/2608.11654#S11)\), it can even destroy coverage that was previously correct\. In this regime, “is there enough information” and “is the information correct” diverge, and coverage ceases to be a proxy for end\-to\-end correctness \(Definition[2\.6](https://arxiv.org/html/2608.11654#S2.Thmtheorem6)\)\.

### 4\.2The Noisy Optimal\-Memory Problem

Under noise, the coverage objective is the wrong target: a memory composed mostly of hallucinations can score near\-perfect onucovu^\{\\mathrm\{cov\}\}while answering almost nothing correctly\. The optimization should target precision instead\.

###### Definition 4\.5\(Noisy optimal memory\)\.

The capacity\-constrained optimal memory under noise maximizes the precision utility, reusing the symbolMD∗​\(S\)M^\{\*\}\_\{D\}\(S\)of Definition[3\.1](https://arxiv.org/html/2608.11654#S3.Thmtheorem1)for the precision objective,

MD∗​\(S\)=arg⁡maxMD⊆E^D\|MD\|≤S​𝔼q∼pD​\[uprec​\(q,MD\)\],M^\{\*\}\_\{D\}\(S\)=\\arg\\max\_\{\\begin\{subarray\}\{c\}M\_\{D\}\\subseteq\\hat\{E\}\_\{D\}\\\\ \|M\_\{D\}\|\\leq S\\end\{subarray\}\}\\ \\mathbb\{E\}\_\{q\\sim p\_\{D\}\}\\big\[\\,u^\{\\mathrm\{prec\}\}\(q,M\_\{D\}\)\\,\\big\],\(13\)and the frontierUDprec​\(S\)U^\{\\mathrm\{prec\}\}\_\{D\}\(S\)it induces, the\\newtermprecision frontier, is defined analogously toUD∗​\(S\)U^\{\*\}\_\{D\}\(S\)\.

WhenΦ\\Phiis decomposable and the truth functionτ\\tauis known, this reduces to a weighted maximum coverage in which each claim’s weight is its truth times the query mass it covers \(Appendix[13](https://arxiv.org/html/2608.11654#S13)\): a false claim contributes nothing touprecu^\{\\mathrm\{prec\}\}yet consumes budget, so the optimum prefers true claims with high coverage\.

The decisive difficulty, however, is not the optimization but the estimation\. A write policy sees only the noisy claimsE^D\\hat\{E\}\_\{D\}, never the truth setEDE\_\{D\}; it must infer which claims are trustworthy\. Each claim’s truthτ⁡\(e\)\\tau\(e\)is an unobserved latent, and the policy decides, before any query is answered, which claims earn their budget\. When a query is answered correctly or wrongly, the precision utility is settled, and that settlement is the only signal the policy receives aboutτ\\tau\. Attributing the outcome to the right stored claim is a credit\-assignment problem, and learning to write well from this signal is what the sequential formulation of Section[5](https://arxiv.org/html/2608.11654#S5)makes precise\. Section[6](https://arxiv.org/html/2608.11654#S6)shows the coverage and precision frontiers parting on a concrete noise instance\.

## 5A Problem Setting Taxonomy and Sequential Memorization MDP

The optimality theory of Sections[3](https://arxiv.org/html/2608.11654#S3)and[4](https://arxiv.org/html/2608.11654#S4)treats the query distributionpDp\_\{D\}and the material distributionp⁡\(D\)p\(D\)as given\. In practice both are unknown, and the only evidence an agent has is the queries it actually faces, disclosed one at a time\. This section makes that learning explicit\. It organizes the problem settings of memory into a progressive taxonomy, isolates two modes of writing and the delayed\-reward structure of the persistent mode, states the agent\-level memorization objective, and unifies the settings in a sequential MDP\.

### 5\.1A Progressive Taxonomy of Problem Settings

Memorization settings differ in what is known and what must be inferred\. Table[1](https://arxiv.org/html/2608.11654#S5.T1)summarizes the progression\.

Table 1:The progressive taxonomy of memorization settings\.LevelMaterial×\\timesquerypDp\_\{D\}knownObject of learning0single, one query—none \(retrieval\)1asingle, many queriesyesoptimal memory, one\-shot1bsingle, many queriesnopDp\_\{D\}, hence the optimal memory, sequential2many, many queriesnotransferable write ruleπ\\piLevel 0 \(single material, single query\)\.Memory is written once and serves a single query\. There is no distribution to speak of: the setting is one\-shot compression, essentially efficient retrieval from a long material, and it cannot separate memory quality from retrieval quality\. It is a degenerate case, useful as a baseline but not as a testbed for memorization\.Level 1 \(single material, many queries\)\.Queries against one material arrive repeatedly, and the two cases split on whether the agent knows their distribution\. WhenpDp\_\{D\}is known \(Level 1a, idealized\), the problem is exactly the one\-shot optimal\-memory problem of Section[3](https://arxiv.org/html/2608.11654#S3); nothing has to be learned\. WhenpDp\_\{D\}is unknown \(Level 1b, realistic\), each disclosed query is a sample ofpDp\_\{D\}, and writing must be multi\-step: after each query the agent holds one more piece of evidence and can revise the memory, so sequential writing is a stepwise search in memory space that approachesMD∗​\(S\)M^\{\*\}\_\{D\}\(S\)\.Level 2 \(many materials, many queries\)\.Marginalizing over the material distribution turns the object of learning from a per\-material memory into a transferable write rule, an agent\-level strategy that must work across materials\. We state this objective formally in Section[5\.2](https://arxiv.org/html/2608.11654#S5.SS2)\.

The two modes of writing\.Write policies come in two modes\.\\newtermQuery\-agnostic writing,MD=πwrite​\(D\)M\_\{D\}=\\pi\_\{\\mathrm\{write\}\}\(D\), fixes the memory before any query and must anticipate the distributionpDp\_\{D\}; this is the persistent form of memory\.\\newtermQuery\-aware writing,πwrite​\(q,D\)\\pi\_\{\\mathrm\{write\}\}\(q,D\), sees the specific query and reduces to per\-query compression; for a single query it is long\-context retrieval, not memory, because nothing survives for reuse across queries\.

The modes and the taxonomy\.Query\-aware writing is viable only at Level 0, where the memory serves the single query that produced it\. From Level 1 up, a memory across queries must be query\-agnostic, and the object of learning in Table[1](https://arxiv.org/html/2608.11654#S5.T1)is exactly what the persistent write must infer: the optimal memory \(1a\), the distribution \(1b\), or a transferable rule \(2\)\. The persistent mode is hard precisely because a write is tested only by queries that arrive after it, so its value is known when a later query settles the account:

πwrite​\(D\)⏟writing, first⟶u​\(q,πwrite​\(D\)\)⏟settlement, later,q∼pD\.\\underbrace\{\\pi\_\{\\mathrm\{write\}\}\(D\)\}\_\{\\text\{writing, first\}\}\\;\\longrightarrow\\;\\underbrace\{u\\big\(q,\\ \\pi\_\{\\mathrm\{write\}\}\(D\)\\big\)\}\_\{\\text\{settlement, later\}\},\\qquad q\\sim p\_\{D\}\.\(14\)This is a\\newtermdelayed\-reward structure, present as soon aspDp\_\{D\}is unknown \(Level 1b\) and persisting at every higher level\. It is what turns memorization into a learning problem, and it gives rise to two difficulties\.

Credit assignment\.Whether a query is answered correctly cannot be traced to a specific prior write: the utility depends on the whole memory, which is the cumulative result of many write decisions, so a success or failure cannot be attributed to any one of them\.

Exploration–exploitation\.To learn which claims are trustworthy \(the truthτ\\tauunder noise\), the agent may need to store an uncertain claim and let a later query confirm or refute it\. The best long\-run memory can require deliberately suboptimal short\-run choices\.

### 5\.2A Sequential MDP for Memorization

Levels 1 and 2 share a core that Section[5\.1](https://arxiv.org/html/2608.11654#S5.SS1)made explicit: write now, be judged by later queries\. Both settings also admit a static form, a single objective over the material distribution: the agent chooses a write ruleπ\\pi, and each material’s memoryπ⁡\(D\)\\pi\(D\)is judged by the queries it serves\.

###### Definition 5\.1\(Agent\-level memorization\)\.

The\\newtermagent\-level memorization objective is

π∗=arg⁡maxπ​𝔼D∼p⁡\(D\)​\[∑t=1TD𝔼qt∼pD​u​\(qt,π⁡\(D\)\)\]s\.t\.\|π⁡\(D\)\|≤S,\\pi^\{\*\}=\\arg\\max\_\{\\pi\}\\ \\mathbb\{E\}\_\{D\\sim p\(D\)\}\\Big\[\\ \\sum\_\{t=1\}^\{T\_\{D\}\}\\ \\mathbb\{E\}\_\{q\_\{t\}\\sim p\_\{D\}\}\\ u\\big\(q\_\{t\},\\ \\pi\(D\)\\big\)\\ \\Big\]\\qquad\\text\{s\.t\.\}\\quad\|\\pi\(D\)\|\\leq S,\(15\)whereπ\\piranges over write policies, andTDT\_\{D\}is the number of queries the memory of materialDDserves\. The memory is a function of the material alone,π⁡\(D\)\\pi\(D\), independent of the queries it serves\. Under noise,uuis replaced byuprecu^\{\\mathrm\{prec\}\}, and estimatingτ\\taubecomes part ofπ\\pi\.

Whenπ\\piis a parametric model \(an LLM with its memory module\), this equation is a learning objective, and it is the formal place of “memory construction and learning” in the framework: what is learned is no longer the optimal memory of one material but a rule that generalizes over a distribution of materials\.

The relation to the earlier theory is exact\. When the material distribution concentrates on a single material, the objective reduces, up to the constant factorTDT\_\{D\}, to the capacity\-constrained problem of Definition[3\.1](https://arxiv.org/html/2608.11654#S3.Thmtheorem1)\. An upper bound follows from the per\-material frontiers: when all materials share capacitySS, no policy can exceed𝔼D∼p⁡\(D\)​\[TD​UD∗​\(S\)\]\\mathbb\{E\}\_\{D\\sim p\(D\)\}\\big\[T\_\{D\}\\,U^\{\*\}\_\{D\}\(S\)\\big\], the individual frontiers weighted by how many queries each material serves, and the gap between a fixed policy and that bound is its regret\.

Real writing, however, is not a single shot: the agent meets materials one at a time, and each write is tested by a later query, so the write rule must be learned online\. Modeling the process as a sequential MDP generalizes the write policy fromD↦MDD\\mapsto M\_\{D\}to a sequential update; we overloadπwrite\\pi\_\{\\mathrm\{write\}\}, whose single\-argument form is the static write of Section[3\.1](https://arxiv.org/html/2608.11654#S3.SS1)and whose four\-argument form is the update below\.

###### Definition 5\.2\(Sequential memorization MDP\)\. The process runs in episodesm=1,…,Km=1,\\dots,K\. Each episode draws a fresh materialDm∼p⁡\(D\)D\_\{m\}\\sim p\(D\); within it, at stepst=1,…,Tmt=1,\\dots,T\_\{m\}, the agent maintains a memoryMm,tM\_\{m,t\}with\|Mm,t\|≤S\|M\_\{m,t\}\|\\leq S\. At each step a queryqm,t∼pDmq\_\{m,t\}\\sim p\_\{D\_\{m\}\}is posed, the agent answersam,t=πreasoner​\(qm,t,Mm,t\)a\_\{m,t\}=\\pi\_\{\\mathrm\{reasoner\}\}\(q\_\{m,t\},M\_\{m,t\}\), and the memory updates asMm,t\+1=πwrite​\(Mm,t,Dm,qm,t,am,t\)\.M\_\{m,t\+1\}=\\pi\_\{\\mathrm\{write\}\}\\big\(M\_\{m,t\},\\ D\_\{m\},\\ q\_\{m,t\},\\ a\_\{m,t\}\\big\)\.\(16\)At the start of an episode the memory is written from the new material alone,Mm,1=πwrite​\(Dm\)M\_\{m,1\}=\\pi\_\{\\mathrm\{write\}\}\(D\_\{m\}\), resetting whatever the previous episode built\. The memory that answersqm,tq\_\{m,t\}was written without seeing it: the query is settled first, and only then does it enter the update\. The objective is the expected cumulative utility over episodes,πwrite∗=arg⁡maxπwrite⁡𝔼⁡\[∑m=1K∑t=1Tmγt​u​\(qm,t,Mm,t\)\],\\pi\_\{\\mathrm\{write\}\}^\{\*\}=\\arg\\max\_\{\\pi\_\{\\mathrm\{write\}\}\}\\ \\mathbb\{E\}\\Big\[\\sum\_\{m=1\}^\{K\}\\sum\_\{t=1\}^\{T\_\{m\}\}\\gamma^\{t\}\\,u\\big\(q\_\{m,t\},M\_\{m,t\}\\big\)\\Big\],\(17\)whereuuis the coverage utility, replaced byuprecu^\{\\mathrm\{prec\}\}under noise and byue2eu^\{\\mathrm\{e2e\}\}when the end\-to\-end layer is in view \(Definition[2\.6](https://arxiv.org/html/2608.11654#S2.Thmtheorem6)\)\. The single\-material setting is the degenerate case of one episode,K=1K=1withD1D\_\{1\}fixed\.

Table 2:The sequential memorization problem as a Markov decision process\.MDP elementMemory\-system meaningepisodea fresh materialDm∼p⁡\(D\)D\_\{m\}\\sim p\(D\), memory resetstatecurrent memoryMm,tM\_\{m,t\}actionwhich claims to write, how to reorganizerewardutility at query timeu⁡\(qm,t,Mm,t\)u\(q\_\{m,t\},M\_\{m,t\}\)transitionMm,t\+1=πwrite​\(Mm,t,Dm,qm,t,am,t\)M\_\{m,t\+1\}=\\pi\_\{\\mathrm\{write\}\}\(M\_\{m,t\},D\_\{m\},q\_\{m,t\},a\_\{m,t\}\)Each level is now a specialization of the MDP\. Level 0 is the single\-step episode \(K=1K=1,T1=1T\_\{1\}=1\); the disclosure timing of Definition[5\.2](https://arxiv.org/html/2608.11654#S5.Thmtheorem2)is relaxed so the query is known before the write\. Level 1 is one episode over a fixed material \(K=1K=1,T1\>1T\_\{1\}\>1\), with the delayed reward of Section[5\.1](https://arxiv.org/html/2608.11654#S5.SS1)\. Level 2 is many episodes over fresh drawsDm∼p⁡\(D\)D\_\{m\}\\sim p\(D\)\(K\>1K\>1\), each material served by its own sequence of queries\.

The MDP reading also makes memory the state representation: the capacity bound\|Mm,t\|≤S\|M\_\{m,t\}\|\\leq Sconstrains the state space, so a write action is literally the choice of whichSSclaims cover the expected future queries, which is the utility–capacity frontier restated as a control problem\. Under noise it closes the estimation loop: settlinguprecu^\{\\mathrm\{prec\}\}lets the agent discover that it stored a wrong claim, feeding the estimate ofτ\\tau, which becomes a trainable object rather than a given\.

## 6An Illustrative Example: The Utility–Capacity Frontier of Homer’s*Odyssey*

This section turns the machinery of Sections[2](https://arxiv.org/html/2608.11654#S2)–[5](https://arxiv.org/html/2608.11654#S5)into numbers, computing the utility–capacity frontier of one instance explicitly and reading the framework’s concepts off it\. The instance is small enough to check by hand and rich enough to exhibit basis and span, the synergy of interacting events, the frontier and its compression zone, the memory\-efficiency loss of a write policy, and the divergence of coverage from precision under noise\. As throughout, the query distribution is treated as known: the Level 1a setting of Table[1](https://arxiv.org/html/2608.11654#S5.T1)\.

The instance\.LetDDbe a summary of Homer’s*Odyssey*, and consider an agent that must answer questions about the epic from memory\. The extraction procedureΦ\\Phiis decomposable, so that the knowledge of a set of events is the union of the knowledge of its members and the coverage of a memory is the union of the per\-event answerable setsSe=⋃n∈Φ⁡\(\{e\}\)𝒬⁡\(n\)S\_\{e\}=\\bigcup\_\{n\\in\\Phi\(\\\{e\\\}\)\}\\mathcal\{Q\}\(n\)\(Section[3\.3](https://arxiv.org/html/2608.11654#S3.SS3)\)\. Six events, one per episode, are extracted, each spanning the atomic facts entailed by its statement, one per query the event answers; these events are the candidate basis of a memory, and Table[3](https://arxiv.org/html/2608.11654#S6.T3)records the span each contributes\.

The query space is eight questions about the epic, with probability masses

pD​\(q1,…,q8\)=\(0\.20,0\.05,0\.10,0\.15,0\.05,0\.20,0\.05,0\.20\),p\_\{D\}\(q\_\{1\},\\dots,q\_\{8\}\)=\(0\.20,\\ 0\.05,\\ 0\.10,\\ 0\.15,\\ 0\.05,\\ 0\.20,\\ 0\.05,\\ 0\.20\),\(18\)over the questionsq1q\_\{1\}\(“How long did Odysseus’s return from Troy take?”\),q2q\_\{2\}\(“From which city did Odysseus set sail for home?”\),q3q\_\{3\}\(“Which nymph held Odysseus on her island for seven years?”\),q4q\_\{4\}\(“Who turned Odysseus’s men into swine?”\),q5q\_\{5\}\(“Who waited twenty years for Odysseus in Ithaca?”\),q6q\_\{6\}\(“To which island did Odysseus finally return?”\),q7q\_\{7\}\(“Why did Poseidon oppose Odysseus’s return?”\), andq8q\_\{8\}\(“Which figures detained Odysseus on their islands during his wanderings?”\)\. Table[3](https://arxiv.org/html/2608.11654#S6.T3)lists each event with the items it spans \(each tagged with the query it answers\) and the query mass the event covers\.

Table 3:The events of the example, the knowledge items each event spans under the decomposableΦ\\Phi, and the query mass each covers\. The detainer eventse2e\_\{2\}ande3e\_\{3\}each span an item answering the detention queryq8q\_\{8\}, a deliberate overlap\.eventeestored statementspansΦ⁡\(\{e\}\)\\Phi\(\\\{e\\\}\)answersmasse1e\_\{1\}“Odysseus spent ten years sailing home from Troy\.”nan\_\{a\}: “the voyage took ten years” \(q1q\_\{1\}\);nbn\_\{b\}: “sailed from Troy” \(q2q\_\{2\}\)q1,q2q\_\{1\},q\_\{2\}0\.25e2e\_\{2\}“The nymph Calypso held Odysseus on Ogygia for seven years\.”ncn\_\{c\}: “held Odysseus for seven years” \(q3q\_\{3\}\);ndn\_\{d\}: “Calypso detained Odysseus” \(q8q\_\{8\}\)q3,q8q\_\{3\},q\_\{8\}0\.30e3e\_\{3\}“Circe kept Odysseus for a year and turned his men into swine\.”nen\_\{e\}: “turned the men into swine” \(q4q\_\{4\}\);nfn\_\{f\}: “Circe detained Odysseus” \(q8q\_\{8\}\)q4,q8q\_\{4\},q\_\{8\}0\.35e4e\_\{4\}“The Phaeacians carried Odysseus asleep to the shore of Ithaca\.”ngn\_\{g\}: “reached the island of Ithaca” \(q6q\_\{6\}\)q6q\_\{6\}0\.20e5e\_\{5\}“Penelope, Odysseus’s wife, waited twenty years in Ithaca\.”nhn\_\{h\}: “waited twenty years for Odysseus” \(q5q\_\{5\}\)q5q\_\{5\}0\.05e6e\_\{6\}“Odysseus blinded Polyphemus, the Cyclops son of Poseidon\.”nin\_\{i\}: “blinded the Cyclops, Poseidon’s son” \(q7q\_\{7\}\)q7q\_\{7\}0\.05Where events interact\.The spans of Table[3](https://arxiv.org/html/2608.11654#S6.T3)are computed event by event, and the frontier below inherits the same choice: every knowledge item is spanned by a single event, and a memory’s span is the union of its events’ items\. Decomposability is an assumption about the operator, not a property of the material, and the same events exhibit the alternative:Φ\\Phicomposes events that belong together, so that pairs of events also span items that no single event entails, each answering a further query beyond the eight queries of Table[3](https://arxiv.org/html/2608.11654#S6.T3):

- •e2e\_\{2\}ande3e\_\{3\}together span “Odysseus was detained by enchantresses for eight years” \(7\+17\{\+\}1\), answering “For how many years in total did enchantresses detain Odysseus?”;
- •e4e\_\{4\}ande5e\_\{5\}together span “Odysseus returned to Penelope after twenty years,” answering “How many years after leaving did Odysseus rejoin his wife?”;
- •e6e\_\{6\}ande1e\_\{1\}together span “Poseidon’s wrath made the homecoming last ten years,” answering “Why did the voyage take so long?”\.

For each of these pairs,Φ⁡\(\{e,e′\}\)\\Phi\(\\\{e,e^\{\\prime\}\\\}\)strictly containsΦ⁡\(\{e\}\)∪Φ⁡\(\{e′\}\)\\Phi\(\\\{e\\\}\)\\cup\\Phi\(\\\{e^\{\\prime\}\\\}\): the span of a memory is more than the union of its parts, and an event’s marginal depends on its companions\. If the composite query of the first pair carries mass0\.050\.05in a variant of the query distribution, thene3e\_\{3\}’s marginal givene2e\_\{2\}is0\.200\.20:0\.150\.15for its unique query plus0\.050\.05for the composite, so composition adds genuinely new coverage\. Even so, this marginal falls short ofe3e\_\{3\}’s standalone0\.350\.35, because the overlap onq8q\_\{8\}outweighs the composite’s gain; on this instance marginals still decrease and the greedy guarantee is not threatened\. The growing marginal behind Proposition[3\.6](https://arxiv.org/html/2608.11654#S3.Thmtheorem6)\(b\) would need the composite mass to dominate the overlap; Remark[12\.6](https://arxiv.org/html/2608.11654#S12.Thmtheorem6)constructs that failure in isolation\. What these pairs do exhibit is where multi\-hop lives in the framework: a compositional query is answerable from memory only when the composition is already realized insideΦ\\Phias a single item\.

The frontier\.Enumerating the capacity\-constrained optima of Definition[3\.1](https://arxiv.org/html/2608.11654#S3.Thmtheorem1)gives Table[4](https://arxiv.org/html/2608.11654#S6.T4)and the frontier of Figure[2](https://arxiv.org/html/2608.11654#S6.F2)\. The marginal gains of successive events in the order of the optimal additions,0\.35,0\.25,0\.20,0\.10,0\.05,0\.050\.35,0\.25,0\.20,0\.10,0\.05,0\.05, never increase: each additional event buys no more new coverage than the one before\. The frontier saturates at the full\-context baseline,𝔼q∼pD​\[u⁡\(q,ED\)\]=1\.00\\mathbb\{E\}\_\{q\\sim p\_\{D\}\}\\big\[u\(q,E\_\{D\}\)\\big\]=1\.00, reached only at the full material, so the entire regimeS<6S<6is the compression zone, and each shaded slab in Figure[2](https://arxiv.org/html/2608.11654#S6.F2)is the cost of compression at that capacity\.

Table 4:The optimal memories and frontier values of the example\.SSoptimal memoryMD∗​\(S\)M^\{\*\}\_\{D\}\(S\)UD∗​\(S\)U^\{\*\}\_\{D\}\(S\)0∅\\emptyset0\.001\{e3\}\\\{e\_\{3\}\\\}0\.352\{e3,e1\}\\\{e\_\{3\},e\_\{1\}\\\}0\.603\{e3,e1,e4\}\\\{e\_\{3\},e\_\{1\},e\_\{4\}\\\}0\.804\{e3,e1,e4,e2\}\\\{e\_\{3\},e\_\{1\},e\_\{4\},e\_\{2\}\\\}0\.905\{e3,e1,e4,e2,e6\}\\\{e\_\{3\},e\_\{1\},e\_\{4\},e\_\{2\},e\_\{6\}\\\}0\.956\{e1,…,e6\}\\\{e\_\{1\},\\dots,e\_\{6\}\\\}1\.00UD∗​\(S\)U^\{\*\}\_\{D\}\(S\)01234560\.250\.500\.751\.00full\-context baseline=1\.00=1\.00compression zonecapacitySSFigure 2:The utility–capacity frontier of the example\. The shaded slabs are the cost of compression at each capacity, the gap between the frontier and the full\-context baseline; they vanish as the capacity reaches the material size\.Reading the frontier\.Two features are visible in the numbers\. First, the optimum adds events in decreasing marginal value, and greedy selection coincides with it on this instance, which is consistent with, but stronger than, the guarantee of Proposition[3\.6](https://arxiv.org/html/2608.11654#S3.Thmtheorem6)\(a\)\. Second, the overlap between events shapes the marginals, and at the knowledge level it is an overlap between items:e2e\_\{2\}ande3e\_\{3\}each span an item that answers the detention queryq8q\_\{8\}\(ndn\_\{d\}andnfn\_\{f\}in Table[3](https://arxiv.org/html/2608.11654#S6.T3)\), so oncee3e\_\{3\}is stored,e2e\_\{2\}’s marginal falls from its standalone mass0\.300\.30to the mass0\.100\.10of its unique query; budget spent on an already\-covered query is the concrete form of overlap waste\.

A write policy on the frontier\.The frontier is the yardstick\. Consider a policy that prioritizes the wanderings and neglects the homecoming: at capacityS=4S=4it stores\{e3,e2,e1,e6\}\\\{e\_\{3\},e\_\{2\},e\_\{1\},e\_\{6\}\\\}, covering0\.750\.75\(queriesq1,q2,q3,q4,q7,q8q\_\{1\},q\_\{2\},q\_\{3\},q\_\{4\},q\_\{7\},q\_\{8\}\)\. The frontier atS=4S=4is0\.900\.90, attained by\{e3,e1,e4,e2\}\\\{e\_\{3\},e\_\{1\},e\_\{4\},e\_\{2\}\\\}, so the policy’s memory\-efficiency loss is0\.150\.15: it spends the same budget yet leaves the high\-mass homecoming queryq6q\_\{6\}\(0\.200\.20\) uncovered and wastes space on the already\-coveredq8q\_\{8\}\. This is the sense in which the frontier, rather than any single accuracy number, defines “how good a memory is\.”

Under noise\.Noise changes what the numbers mean\. Suppose extraction also emits a false claime^\\hat\{e\}: “Odysseus was the prince of Troy who reached the island of Sparta after ten years of wandering,” which answersq1,q2,q6q\_\{1\},q\_\{2\},q\_\{6\}and carries apparent mass0\.450\.45, but whose truth value isτ⁡\(e^\)=0\\tau\(\\hat\{e\}\)=0\. The coverage\-optimal memory of size11is now\{e^\}\\\{\\hat\{e\}\\\}\(apparent0\.450\.45\), beating the true evente3e\_\{3\}\(0\.350\.35\), yet its precision utility is00: its good spanΦ⁡\(MD∩ED\)\\Phi\(M\_\{D\}\\cap E\_\{D\}\)is empty\. At size22the coverage\-optimal\{e^,e3\}\\\{\\hat\{e\},e\_\{3\}\\\}reports0\.800\.80apparent coverage but only0\.350\.35true, a water\-inflation degree ofΔ=0\.45\\Delta=0\.45, while the precision\-optimal memory\{e3,e1\}\\\{e\_\{3\},e\_\{1\}\\\}scores0\.600\.60withΔ=0\\Delta=0\. The coverage and precision frontiers part wherever the false claim is competitive, and a policy that optimizesucovu^\{\\mathrm\{cov\}\}inherits the inflation \(Proposition[4\.3](https://arxiv.org/html/2608.11654#S4.Thmtheorem3)\)\.

## 7Related Work

The framework decomposes a memory system into generation, write, and read \(Sections[2](https://arxiv.org/html/2608.11654#S2)–[5](https://arxiv.org/html/2608.11654#S5)\); earlier sections formalized the first two, and we make the read explicit with a lightweight read policy

πread:\(q,MD\)↦Kq⊆Φ⁡\(MD\),\\pi\_\{\\mathrm\{read\}\}:\(q,M\_\{D\}\)\\mapsto K\_\{q\}\\subseteq\\Phi\(M\_\{D\}\),\(19\)the subset of the memory’s spanned knowledge relevant toqq; settlement then uses only the retrieved subset, which recovers the coverage utility of Definition[2\.5](https://arxiv.org/html/2608.11654#S2.Thmtheorem5)as long as the read retrieves every item that coversqq\. Memory proper is a persistent write coupled with on\-demand reading, the RAG\-style architecture, whereas a query\-aware write for a single query is long\-context retrieval rather than memory\. We organize the literature along three views: by problem setting, by system component, and by memory representation; recent surveys\([Du et al\. 2025](https://arxiv.org/html/2608.11654#bib.bib6)\)map the same space from related angles\.

##### Agent Memory Problem Settings\.

The taxonomy of Section[5\.1](https://arxiv.org/html/2608.11654#S5.SS1)places existing evaluation settings on a progression, summarized in Table[5](https://arxiv.org/html/2608.11654#S7.T5)\. Most long\-context benchmarks sit at Level 0, the single\-material, single\-query case: LongBench\([Bai et al\. 2024](https://arxiv.org/html/2608.11654#bib.bib1)\)and needle\-in\-a\-haystack tests\([Kamradt 2023](https://arxiv.org/html/2608.11654#bib.bib11)\)ask whether information survives inside a long input, and because a single query makes the write query\-aware, the optimal memory degenerates toward storing everything; these settings measure efficient retrieval rather than memory\. MemAgent\([Yu et al\. 2026](https://arxiv.org/html/2608.11654#bib.bib29)\)and ReMemR1\([Shi et al\. 2025](https://arxiv.org/html/2608.11654#bib.bib20)\)train their writes with reinforcement learning yet evaluate one\-shot, and the framework locates them at Level 0 despite the learning machinery\.

The closest testbeds to the disclosure setting of Level 1b are LoCoMo\([Maharana et al\. 2024](https://arxiv.org/html/2608.11654#bib.bib15)\)and LongMemEval\([Wu et al\. 2025](https://arxiv.org/html/2608.11654#bib.bib25)\), long multi\-session conversations probed across many questions; DialSim\([Kim et al\. 2024](https://arxiv.org/html/2608.11654#bib.bib12)\), Mem\-Gallery\([Bei et al\. 2026](https://arxiv.org/html/2608.11654#bib.bib3)\), and MemoryAgentBench\([Hu et al\. 2026](https://arxiv.org/html/2608.11654#bib.bib8)\)extend the setting to multi\-party dialogue, multimodal conversation, and incremental multi\-turn streams\. Most systems evaluated there write the memory once and never update it in response to the questions, so the sequential disclosure ofpDp\_\{D\}goes unused; Memory\-R1\([Yan et al\. 2025](https://arxiv.org/html/2608.11654#bib.bib27)\)is the contrast, training its write policy on LoCoMo and making exactly the disclosure\-driven updates those static systems omit, hence its evaluation at Level 1b rather than the one\-shot Level 0 of MemAgent and ReMemR1\. A recent study on LoCoMo\([Terranova et al\. 2025](https://arxiv.org/html/2608.11654#bib.bib22)\)finds that memory\-augmented systems cut token use by over 90% at competitive accuracy, direct evidence that memory buys most of the full\-context utility at a fraction of the cost\.

Level 1a still has no direct evaluation\. Level 2 evaluations are just emerging: MemoryArena\([He et al\. 2026](https://arxiv.org/html/2608.11654#bib.bib7)\), AMA\-Bench\([Zhao et al\. 2026](https://arxiv.org/html/2608.11654#bib.bib30)\), and Mem2ActBench\([Shen et al\. 2026](https://arxiv.org/html/2608.11654#bib.bib19)\)reuse memory across interdependent tasks, domains, and tool use, approaching the cross\-material setting though persistent systems remain largely tested on single corpora\.

Table 5:Evaluation settings in the literature positioned on the taxonomy of Section[5\.1](https://arxiv.org/html/2608.11654#S5.SS1)\.LevelDefining featureRepresentative work and evaluation0one material, one queryneedle\-in\-a\-haystack\([Kamradt 2023](https://arxiv.org/html/2608.11654#bib.bib11)\); LongBench\([Bai et al\. 2024](https://arxiv.org/html/2608.11654#bib.bib1)\); MemAgent\([Yu et al\. 2026](https://arxiv.org/html/2608.11654#bib.bib29)\); ReMemR1\([Shi et al\. 2025](https://arxiv.org/html/2608.11654#bib.bib20)\)1aone material, many queries; knownpDp\_\{D\}none \(theoretical idealization\)1bone material, many queries; unknownpDp\_\{D\}LoCoMo\([Maharana et al\. 2024](https://arxiv.org/html/2608.11654#bib.bib15)\); LongMemEval\([Wu et al\. 2025](https://arxiv.org/html/2608.11654#bib.bib25)\); DialSim\([Kim et al\. 2024](https://arxiv.org/html/2608.11654#bib.bib12)\); Mem\-Gallery\([Bei et al\. 2026](https://arxiv.org/html/2608.11654#bib.bib3)\); MemoryAgentBench\([Hu et al\. 2026](https://arxiv.org/html/2608.11654#bib.bib8)\); Memory\-R1\([Yan et al\. 2025](https://arxiv.org/html/2608.11654#bib.bib27)\)2many materials; the write rule generalizes across materials \(Definition[5\.1](https://arxiv.org/html/2608.11654#S5.Thmtheorem1)\)emerging: MemoryArena\([He et al\. 2026](https://arxiv.org/html/2608.11654#bib.bib7)\); AMA\-Bench\([Zhao et al\. 2026](https://arxiv.org/html/2608.11654#bib.bib30)\); Mem2ActBench\([Shen et al\. 2026](https://arxiv.org/html/2608.11654#bib.bib19)\)
##### System Components\.

Where existing systems differ most is in which of the framework’s components they instantiate \(Sections[2](https://arxiv.org/html/2608.11654#S2)–[5](https://arxiv.org/html/2608.11654#S5)\)\. Table[6](https://arxiv.org/html/2608.11654#S7.T6)maps representative persistent systems onto the generation operatorΦ\\Phi, the write policyπwrite\\pi\_\{\\mathrm\{write\}\}, and the read policyπread\\pi\_\{\\mathrm\{read\}\}\.

Table 6:Representative persistent memory systems mapped onto the framework’s components\.SystemMemory unitGenerationΦ\\PhiWriteπwrite\\pi\_\{\\mathrm\{write\}\}Readπread\\pi\_\{\\mathrm\{read\}\}MemoryBank\([Zhong et al\. 2024](https://arxiv.org/html/2608.11654#bib.bib31)\)dialogue summariesLLM extraction and consolidationsequential write with forgettingsimilarityGenerative Agents\([Park et al\. 2023](https://arxiv.org/html/2608.11654#bib.bib17)\)observation streamreflective summariesappend, scored by recency and importancerecency, importance, relevanceMemGPT\([Packer et al\. 2023](https://arxiv.org/html/2608.11654#bib.bib16)\)hierarchical pagesLLM summariespaging and evictionon\-demand pagingMemOS\([Li et al\. 2025](https://arxiv.org/html/2608.11654#bib.bib14)\)unified memory storeLLM and automatic organizationvirtual\-memory management and evictionon\-demand retrieval and pagingHippoRAG\([Jiménez Gutiérrez et al\. 2024](https://arxiv.org/html/2608.11654#bib.bib9)\)knowledge graphLLM extraction into a graphgraph storepersonalized PageRankMem0\([Chhikara et al\. 2025](https://arxiv.org/html/2608.11654#bib.bib5)\)user facts and preferencesLLM extractionadd, modify, delete rulesrelevanceA\-MEM\([Xu et al\. 2025](https://arxiv.org/html/2608.11654#bib.bib26)\)linked memory notesLLM extraction and linkingdynamic note constructionlink and similarityReflexion\([Shinn et al\. 2023](https://arxiv.org/html/2608.11654#bib.bib21)\)reflective notesLLM self\-reflectionappendsimilarity over past reflectionsThe generation operator fixes what the stored events span, and the field’s differences lie in how that span is organized: knowledge graphs \(HippoRAG, whose successor HippoRAG 2\([Jiménez Gutiérrez et al\. 2025](https://arxiv.org/html/2608.11654#bib.bib10)\)recasts retrieval itself as non\-parametric memory\), recursive summary trees \(RAPTOR\([Sarthi et al\. 2024](https://arxiv.org/html/2608.11654#bib.bib18)\), MemWalker\([Chen et al\. 2023](https://arxiv.org/html/2608.11654#bib.bib4)\)\), reflective summaries \(Generative Agents, Reflexion\), dialogue consolidation \(MemoryBank\), and linked note networks \(A\-MEM\)\.

The write component decides what to store, and the field splits between heuristics and learning\. Generative Agents score by recency and importance, Mem0 edits memories through explicit add, modify, and delete operations, MemoryBank applies a forgetting schedule, and MemGPT and MemOS manage a paged store with eviction\. MemAgent, ReMemR1, and Memory\-R1\([Yan et al\. 2025](https://arxiv.org/html/2608.11654#bib.bib27)\)instead train the write decision with reinforcement learning, instantiating the sequential MDP of Section[5\.2](https://arxiv.org/html/2608.11654#S5.SS2), the framework’s own learning target\.

The read component decides what the query sees\. Every system in Table[6](https://arxiv.org/html/2608.11654#S7.T6)implements the read policy of this section, through similarity, weighted relevance, graph ranking, or paging, each a way of selecting the subsetKq⊆Φ⁡\(MD\)K\_\{q\}\\subseteq\\Phi\(M\_\{D\}\)the query needs\.

A fourth component acts after the read: Reflexion retries from a written reflection, and ReMemR1 trains the model to reason over its memory; both operate at the end\-to\-end layerue2eu^\{\\mathrm\{e2e\}\}of Definition[2\.6](https://arxiv.org/html/2608.11654#S2.Thmtheorem6), which the framework deliberately separates from coverage\.

##### Memory Representations\.

The framework models memory as an event set withΦ\\Phi\-generated knowledge and defers the layout ofMDM\_\{D\}\(Section[3](https://arxiv.org/html/2608.11654#S3)\)\. The literature’s representations fall into three families\. Explicit symbolic stores keep text items \(MemoryBank, Mem0, Generative Agents, Reflexion\), closest to the framework’s event set\. Structured stores add an index over the symbols, as graphs \(HippoRAG\), trees \(RAPTOR, MemWalker\), hierarchical pages \(MemGPT, MemOS\), or linked note networks \(A\-MEM\), organizing the span and accelerating reading\. Parametric stores write memory into the model itself, as memory tokens or recurrent modules learned at test time \(MemoryLLM\([Wang et al\. 2024](https://arxiv.org/html/2608.11654#bib.bib24)\), Memory3\([Yang et al\. 2024](https://arxiv.org/html/2608.11654#bib.bib28)\), Titans\([Behrouz et al\. 2025](https://arxiv.org/html/2608.11654#bib.bib2)\)\); these live outside the event\-set framing, and the framework leavesMDM\_\{D\}open to them\.

Whatever the component or representation choices, the framework offers a common yardstick: a memory’s quality is an expected utility and a position on the utility–capacity frontier, so systems designed against ad hoc benchmarks become comparable on a single objective\.

## 8Discussion and Limitations

### 8\.1A Research Agenda for Agent Memory

The framework’s payoff is not a particular system but a map of where the unsolved problems live, and the map is organized by the sequential MDP of Section[5\.2](https://arxiv.org/html/2608.11654#S5.SS2), which unifies the taxonomy: memory is the state, writing is the action, settlement is the reward, and a fresh material is an episode\. Three families of open problems remain, one for the state and actions, one for the reward, and one for the episodes\.

##### Representing memory and the write policy\.

The MDP’s state is a memory, a set of at mostSSclaims, and its action is the choice of which claims to write; neither is a fixed\-dimensional vector, so standard policy parameterizations do not apply\. The central question is how to represent a set\-valued state and act on it under the capacity bound, and how to learn the generation and read components rather than fix them by hand, since the generation component decides whether multi\-hop knowledge is materialized in the state at all\.

##### Learning from delayed reward\.

The reward is utility at settlement, arriving long after the writing that earned it \(Section[5\.1](https://arxiv.org/html/2608.11654#S5.SS1)\); its key questions are credit assignment, attributing a settled outcome to the writes that produced it, and, under noise, trust estimation, learning the truth of stored claims from settlement alone\. The sample complexity of this learning, how many settled queries a policy needs to approach the frontier, is open\.

##### Generalizing across materials\.

The final question is whether a write rule learned on some materials transfers to new ones\. Level 2 states the object of learning as a rule over the material distribution \(Definition[5\.1](https://arxiv.org/html/2608.11654#S5.Thmtheorem1)\), but which parts of it generalize, the extraction and composition operators, the read policy, or the estimation of query distributions, is unknown, and benchmarks for this setting are only emerging \(Section[7](https://arxiv.org/html/2608.11654#S7)\)\.

None of these problems is solved by a better storage format\. Each is a learning problem on the MDP’s state, reward, and episodes, which is what it means to build memory rather than to design a data structure\.

### 8\.2Limitations

The framework rests on four simplifying choices, and each is a limit of the theory rather than an implementation detail\.

##### Single\-item support\.

Every query is answered by a single knowledge item, and composition is pushed entirely into the generation operator \(Assumption[2\.2](https://arxiv.org/html/2608.11654#S2.SS2)\)\. This is what makes optimal memory a well\-defined coverage problem, but it excludes answer\-time reasoning: an agent that genuinely combines items to answer a query lies outside the account, and extending the theory would require a joint answer model rather than pure coverage\.

##### Coverage is not correctness\.

The utility the theory optimizes is coverage, not correctness\. The proxy stance of Definition[2\.6](https://arxiv.org/html/2608.11654#S2.Thmtheorem6)treats sufficient information as approximately sufficient for a correct answer; the example supports the stance but does not establish it\. Where the reasoner is fallible, or where misleading memory steers it, coverage and end\-to\-end quality diverge, and the framework’s results do not apply until the end\-to\-end layer is modeled\.

##### Assumptions on the generation operator\.

The assumptions onΦ\\Phihold only approximately in practice\. Real extraction is at best locally monotone, and a conflicting claim can overturn earlier conclusions \(Remark[11\.3](https://arxiv.org/html/2608.11654#S11.Thmtheorem3), Appendix[11](https://arxiv.org/html/2608.11654#S11)\); the framework records this failure mode as a research problem rather than resolving it\. The clean frontier picture of Section[3\.2](https://arxiv.org/html/2608.11654#S3.SS2)depends on monotonicity, and decomposability, which the example assumes, is a special case that real operators meet only roughly\.

##### Representation\-agnostic memory\.

The definition fixes what memory is, a set of events, but not how it is stored, so representation is outside the account: whether a system keeps verbatim records, compressed summaries, graphs, embeddings, or parameters, the theory sees only the eventsMDM\_\{D\}and the operators that map them to knowledge\. This is what lets the frontier compare heterogeneous systems on a common yardstick, but the capacity the theory bounds is counted in events,\|MD\|≤S\|M\_\{D\}\|\\leq S, whereas a real memory pays a representation\-dependent cost in tokens or storage, and the trade\-offs that motivate compressed or parametric memories are set aside\. A fuller definition would couple the account to a representation and its cost, or state how that cost depends on the events chosen\.

## 9Conclusion

The paper set out to give agent memory a definition\. A memory is a basis, a subset of a material’s events, and the knowledge it spans under a generation operator is what an agent can draw on; a memory is good insofar as a few events cover as much of the expected queries as the capacity allows\. This reduces optimal memory to a coverage problem whose solution traces a utility–capacity frontier, and the frontier is the common yardstick the field has been missing: any system’s memory is a point in the size–utility plane, and its worth is the gap to what is attainable at that size\. Under noisy extraction, coverage and precision part company, the water\-inflation degree measures how much reported memory quality is bought with false claims, and writing becomes a learning problem of delayed reward, credit assignment, and trust estimation, unified as a sequential MDP in which memory is the state and writing is the action\. The framework positions existing systems as differing choices of generation, writing, reading, and reasoning, and it turns the field’s open questions, representing and learning write policies and transferring them across materials, into questions that can now be stated precisely\. Whether real systems approach the frontier is an empirical matter the framework does not settle; making that question measurable is the point of the exercise\.

## References

- Bai et al\. \(2024\)Yushi Bai, Xin Lv, Jiajie Zhang, Hongchang Lyu, Jiankai Tang, Zhidian Huang, Zhengxiao Du, Xiao Liu, Aohan Zeng, Lei Hou, Yuxiao Dong, Jie Tang, and Juanzi Li\.LongBench: A bilingual, multitask benchmark for long context understanding\.In*Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics \(ACL\)*, 2024\.arXiv:2308\.14508\.
- Behrouz et al\. \(2025\)Ali Behrouz, Peilin Zhong, and Vahab S\. Mirrokni\.Titans: Learning to memorize at test time\.arXiv preprint arXiv:2501\.00663, 2025\.
- Bei et al\. \(2026\)Yuanchen Bei, Tianxin Wei, Xuying Ning, Yanjun Zhao, Zhining Liu, Xiao Lin, Yada Zhu, Hendrik Hamann, Jingrui He, and Hanghang Tong\.Mem\-Gallery: Benchmarking multimodal long\-term conversational memory for MLLM agents\.In*Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics \(ACL\)*, 2026\.
- Chen et al\. \(2023\)Howard Chen, Ramakanth Pasunuru, Jason Weston, and Asli Celikyilmaz\.Walking down the memory maze: Beyond context limit through interactive reading\.arXiv preprint arXiv:2310\.05029, 2023\.
- Chhikara et al\. \(2025\)Prateek Chhikara, Dev Khant, Saket Aryan, Taranjeet Singh, and Deshraj Yadav\.Mem0: Building production\-ready AI agents with scalable long\-term memory\.arXiv preprint arXiv:2504\.19413, 2025\.
- Du et al\. \(2025\)Yiming Du, Wenyu Huang, Danna Zheng, Zhaowei Wang, Sebastien Montella, Mirella Lapata, Kam\-Fai Wong, and Jeff Z\. Pan\.Rethinking memory in LLM based agents: Representations, operations, and emerging topics\.arXiv preprint arXiv:2505\.00675, 2025\.
- He et al\. \(2026\)Zexue He, Yu Wang, Churan Zhi, Yuanzhe Hu, Tzu\-Ping Chen, Lang Yin, Ze Chen, Tong Arthur Wu, Siru Ouyang, Zihan Wang, Jiaxin Pei, Julian McAuley, Yejin Choi, and Alex Pentland\.MemoryArena: Benchmarking agent memory in interdependent multi\-session agentic tasks\.In*International Conference on Machine Learning \(ICML\)*, 2026\.arXiv:2602\.16313\.
- Hu et al\. \(2026\)Yuanzhe Hu, Yu Wang, and Julian McAuley\.Evaluating memory in LLM agents via incremental multi\-turn interactions\.In*International Conference on Learning Representations \(ICLR\)*, 2026\.arXiv:2507\.05257\.
- Jiménez Gutiérrez et al\. \(2024\)Bernal Jiménez Gutiérrez, Yiheng Shu, Yu Gu, Michihiro Yasunaga, and Yu Su\.HippoRAG: Neurobiologically inspired long\-term memory for large language models\.In*Advances in Neural Information Processing Systems \(NeurIPS\)*, 2024\.
- Jiménez Gutiérrez et al\. \(2025\)Bernal Jiménez Gutiérrez, Yiheng Shu, Weijian Qi, Sizhe Zhou, and Yu Su\.From RAG to memory: Non\-parametric continual learning for large language models\.In*International Conference on Machine Learning \(ICML\)*, 2025\.arXiv:2502\.14802\.
- Kamradt \(2023\)Gregory Kamradt\.Needle in a Haystack: Pressure Testing LLMs\.GitHub repository, 2023\.[https://github\.com/gkamradt/needle\-in\-a\-haystack](https://github.com/gkamradt/needle-in-a-haystack)\.
- Kim et al\. \(2024\)Jiho Kim, Woosog Chay, Hyeonji Hwang, Daeun Kyung, Hyunseung Chung, Eunbyeol Cho, Yeonsu Kwon, Yohan Jo, and Edward Choi\.DialSim: A dialogue simulator for evaluating long\-term multi\-party dialogue understanding of conversational agents\.arXiv preprint arXiv:2406\.13144, 2024\.
- Kumaran et al\. \(2016\)Dharshan Kumaran, Demis Hassabis, and James L\. McClelland\.What learning systems do intelligent agents need? complementary learning systems theory updated\.*Trends in Cognitive Sciences*, 20\(7\):512–534, 2016\.
- Li et al\. \(2025\)Zhiyu Li, Chenyang Xi, Chunyu Li, Ding Chen, Boyu Chen, Shichao Song, Simin Niu, Hanyu Wang, Jiawei Yang, Chen Tang, Qingchen Yu, Jihao Zhao, Yezhaohui Wang, Peng Liu, Zehao Lin, Pengyuan Wang, Jiahao Huo, Tianyi Chen, Kai Chen, Kehang Li, Zhen Tao, Huayi Lai, Hao Wu, Bo Tang, Zhengren Wang, Zhaoxin Fan, Ningyu Zhang, Linfeng Zhang, Junchi Yan, Mingchuan Yang, Tong Xu, Wei Xu, Huajun Chen, Haofen Wang, Hongkang Yang, Wentao Zhang, Zhi\-Qin John Xu, Siheng Chen, and Feiyu Xiong\.MemOS: A memory OS for AI system\.arXiv preprint arXiv:2507\.03724, 2025\.
- Maharana et al\. \(2024\)Adyasha Maharana, Dong\-Ho Lee, Sergey Tulyakov, Mohit Bansal, Francesco Barbieri, and Yuwei Fang\.Evaluating very long\-term conversational memory of LLM agents\.In*Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics \(ACL\)*, 2024\.arXiv:2402\.17753\.
- Packer et al\. \(2023\)Charles Packer, Sarah Wooders, Kevin Lin, Vivian Fang, Shishir G\. Patil, Ion Stoica, and Joseph E\. Gonzalez\.Memgpt: Towards LLMs as operating systems\.*arXiv preprint arXiv:2310\.08560*, 2023\.
- Park et al\. \(2023\)Joon Sung Park, Joseph C\. O’Brien, Carrie J\. Cai, Meredith Ringel Morris, Percy Liang, and Michael S\. Bernstein\.Generative agents: Interactive simulacra of human behavior\.In*Proceedings of the 36th Annual ACM Symposium on User Interface Software and Technology \(UIST\)*, 2023\.
- Sarthi et al\. \(2024\)Parth Sarthi, Salman Abdullah, Aditi Tuli, Shubh Khanna, Anna Goldie, and Christopher D\. Manning\.RAPTOR: Recursive abstractive processing for tree\-organized retrieval\.In*International Conference on Learning Representations \(ICLR\)*, 2024\.arXiv:2401\.18059\.
- Shen et al\. \(2026\)Yiting Shen, Kun Li, Wei Zhou, and Songlin Hu\.Mem2ActBench: A benchmark for evaluating long\-term memory utilization in task\-oriented autonomous agents\.In*Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics \(ACL\)*, 2026\.
- Shi et al\. \(2025\)Yaorui Shi, Yuxin Chen, Siyuan Wang, Sihang Li, Hengxing Cai, Qi Gu, Xiang Wang, and An Zhang\.Look back to reason forward: Revisitable memory for long\-context LLM agents\.arXiv preprint arXiv:2509\.23040, 2025\.
- Shinn et al\. \(2023\)Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao\.Reflexion: Language agents with verbal reinforcement learning\.In*Advances in Neural Information Processing Systems \(NeurIPS\)*, 2023\.
- Terranova et al\. \(2025\)Alessandra Terranova, Björn Ross, and Alexandra Birch\.Evaluating long\-term memory for long\-context question answering\.In*NeurIPS 2025 Workshop on Metacognition in Generative AI*, 2025\.
- Tulving \(1972\)Endel Tulving\.Episodic and semantic memory\.In Endel Tulving and Wayne Donaldson, editors,*Organization of Memory*, pages 381–403\. Academic Press, New York, 1972\.
- Wang et al\. \(2024\)Yu Wang, Yifan Gao, Xiusi Chen, Haoming Jiang, Shiyang Li, Jingfeng Yang, Qingyu Yin, Zheng Li, Xian Li, Bing Yin, Jingbo Shang, and Julian McAuley\.MemoryLLM: Towards self\-updatable large language models\.arXiv preprint arXiv:2402\.04624, 2024\.
- Wu et al\. \(2025\)Di Wu, Hongwei Wang, Wenhao Yu, Yuwei Zhang, Kai\-Wei Chang, and Dong Yu\.LongMemEval: Benchmarking chat assistants on long\-term interactive memory\.In*International Conference on Learning Representations \(ICLR\)*, 2025\.arXiv:2410\.10813\.
- Xu et al\. \(2025\)Wujiang Xu, Zujie Liang, Kai Mei, Hang Gao, Juntao Tan, and Yongfeng Zhang\.A\-MEM: Agentic memory for LLM agents\.In*Advances in Neural Information Processing Systems \(NeurIPS\)*, 2025\.arXiv:2502\.12110\.
- Yan et al\. \(2025\)Sikuan Yan, Xiufeng Yang, Zuchao Huang, Ercong Nie, Zifeng Ding, Zonggen Li, Xiaowen Ma, Jinhe Bi, Kristian Kersting, Jeff Z\. Pan, Hinrich Schütze, Volker Tresp, and Yunpu Ma\.Memory\-R1: Enhancing large language model agents to manage and utilize memories via reinforcement learning\.arXiv preprint arXiv:2508\.19828, 2025\.
- Yang et al\. \(2024\)Hongkang Yang, Zehao Lin, Wenjin Wang, Hao Wu, Zhiyu Li, Bo Tang, Wenqiang Wei, Jinbo Wang, Zeyun Tang, Shichao Song, Chenyang Xi, Yu Yu, Kai Chen, Feiyu Xiong, Linpeng Tang, and Weinan E\.Memory3: Language modeling with explicit memory\.*Journal of Machine Learning*, 3:300–346, 2024\.
- Yu et al\. \(2026\)Hongli Yu, Tinghong Chen, Jiangtao Feng, Jiangjie Chen, Weinan Dai, Qiying Yu, Ya\-Qin Zhang, Wei\-Ying Ma, Jingjing Liu, Mingxuan Wang, and Hao Zhou\.Memagent: Reshaping long\-context LLM with multi\-conv RL\-based memory agent\.In*International Conference on Learning Representations \(ICLR\)*, 2026\.arXiv:2507\.02259\.
- Zhao et al\. \(2026\)Yujie Zhao, Boqin Yuan, Junbo Huang, Haocheng Yuan, Zhongming Yu, Haozhou Xu, Lanxiang Hu, Abhilash Shankarampeta, Zimeng Huang, Wentao Ni, Yuandong Tian, and Jishen Zhao\.AMA\-Bench: Evaluating long\-horizon memory for agentic applications\.arXiv preprint arXiv:2602\.22769, 2026\.
- Zhong et al\. \(2024\)Wanjun Zhong, Lianghong Guo, Qiqi Gao, He Ye, and Yanlin Wang\.Memorybank: Enhancing large language models with long\-term memory\.In*Proceedings of the 38th AAAI Conference on Artificial Intelligence \(AAAI\)*, 2024\.arXiv:2305\.10250\.

Appendix Contents

\\beginappendix

## 10Notation

The table below collects the notation used throughout the paper, in the order it is introduced\.

Events and knowledgeEE,eeevent space; an event, an atomic statement about a materialDDa material: a long source of informationEDE\_\{D\}the events contained in materialDDNN,nnknowledge\-item space; a knowledge item, an atomic self\-contained unit of informationΦ⁡\(A\)\\Phi\(A\)generation operator: the knowledge generated by an event setAANDN\_\{D\}knowledge contained inDD:Φ⁡\(ED\)\\Phi\(E\_\{D\}\)MDM\_\{D\}memory ofDD: a subset ofEDE\_\{D\}, the basisRMDR\_\{M\_\{D\}\}span of memoryMDM\_\{D\}:Φ⁡\(MD\)\\Phi\(M\_\{D\}\)Queries and utility𝒬\\mathcal\{Q\},qqquery space; a queryans⁡\(n,q\)\\mathrm\{ans\}\(n,q\)whether itemnnalone suffices to answerqq𝒬⁡\(n\)\\mathcal\{Q\}\(n\)answerable set ofnn:\{q∈𝒬:ans⁡\(n,q\)=1\}\\\{q\\in\\mathcal\{Q\}:\\mathrm\{ans\}\(n,q\)=1\\\}u⁡\(q,MD\)u\(q,M\_\{D\}\)coverage utility: whether the span ofMDM\_\{D\}answersqquprec​\(q,MD\)u^\{\\mathrm\{prec\}\}\(q,M\_\{D\}\)precision utility: whether the good span ofMDM\_\{D\}answersqque2e​\(q,MD,πreasoner\)u^\{\\mathrm\{e2e\}\}\(q,M\_\{D\},\\pi\_\{\\mathrm\{reasoner\}\}\)end\-to\-end utility: whether the reasoner answersqqcorrectlyπreasoner\\pi\_\{\\mathrm\{reasoner\}\}reasoning policypD​\(q\)p\_\{D\}\(q\)query distribution for materialDDp⁡\(D\)p\(D\)distribution over materialsOptimal memory and the frontierπwrite\\pi\_\{\\mathrm\{write\}\}write policy:D↦MD⊆EDD\\mapsto M\_\{D\}\\subseteq E\_\{D\}MD∗M^\{\*\}\_\{D\}optimal memory: unconstrained maximizer of expected coverage utilitySScapacity bound:\|MD\|≤S\|M\_\{D\}\|\\leq SMD∗​\(S\)M^\{\*\}\_\{D\}\(S\)capacity\-constrained optimal memoryUD∗​\(S\)U^\{\*\}\_\{D\}\(S\)utility–capacity frontier: optimal expected utility at capacitySSSeS\_\{e\}query set of eventee:⋃n∈Φ⁡\(\{e\}\)𝒬⁡\(n\)\\bigcup\_\{n\\in\\Phi\(\\\{e\\\}\)\}\\mathcal\{Q\}\(n\)NoiseE^D\\hat\{E\}\_\{D\}claims extracted fromDD; the true ones form the event setEDE\_\{D\}τ⁡\(e\)\\tau\(e\)truth value of claimee; the true claims are the eventsRMDgoodR\_\{M\_\{D\}\}^\{\\mathrm\{good\}\}good span:Φ⁡\(MD∩ED\)\\Phi\(M\_\{D\}\\cap E\_\{D\}\)ucov​\(q,MD\)u^\{\\mathrm\{cov\}\}\(q,M\_\{D\}\)coverage utility, writtenucovu^\{\\mathrm\{cov\}\}under noiseΔ⁡\(π\)\\Delta\(\\pi\)water\-inflation degree of policyπ\\pi: expected coverage minus precisionUDprec​\(S\)U\_\{D\}^\{\\mathrm\{prec\}\}\(S\)precision frontier: the optimal precision utility at capacitySSSettings and the MDPπ\\piagent\-level write ruleπ∗\\pi^\{\*\}optimal agent\-level write rule: maximizer of the memorization objectiveTDT\_\{D\}number of queries served by the memory of materialDDKKnumber of episodesDmD\_\{m\}material drawn in episodemmMm,tM\_\{m,t\}memory at stepttof episodemmqm,tq\_\{m,t\}query at stepttof episodemmam,ta\_\{m,t\}answer produced at stepttof episodemmγ\\gammadiscount factorReadingπread\\pi\_\{\\mathrm\{read\}\}read policy:\(q,MD\)↦Kq\(q,M\_\{D\}\)\\mapsto K\_\{q\}KqK\_\{q\}subset of the spanΦ⁡\(MD\)\\Phi\(M\_\{D\}\)retrieved for queryqq

## 11Assumptions on the Generation Operator

This appendix states the assumptions on the generation operator in full; Section[2\.3](https://arxiv.org/html/2608.11654#S2.SS3)summarizes them in the main text\. The operatorΦ\\Phiis an abstract procedure \(in practice implemented by an LLM performing extraction, induction, and summarization\), and its properties determine the structure of the optimality theory\.

\{assumption\}

\[Self\-containment\] For every eventee,\{e\}⊆Φ⁡\(\{e\}\)\\\{e\\\}\\subseteq\\Phi\(\\\{e\\\}\): a single event generates at least its own degenerate knowledge item\. This makes the conventionE⊂NE\\subset Nconsistent withRMD=Φ⁡\(MD\)R\_\{M\_\{D\}\}=\\Phi\(M\_\{D\}\)\.

Self\-containment is a consistency condition: storing an event never throws the event away\. The more substantive assumption is that knowledge grows with the stored set\.

\{assumption\}

\[Monotonicity\] IfA⊆BA\\subseteq BthenΦ⁡\(A\)⊆Φ⁡\(B\)\\Phi\(A\)\\subseteq\\Phi\(B\)\. More memory is never worse: coverage is non\-decreasing in the stored set\.

Monotonicity says that more memory is never worse\. Beyond it, the framework can be strengthened or relaxed in specific directions, and we flag the options\.

A related question is how knowledge from different events combines\. It is tempting to assume that the knowledge of a set is simply the union of the knowledge of its elements, and the following remark explains why we do not\.

Finally, real systems meet these assumptions only approximately, and one failure mode matters enough to state explicitly\.

## 12Optimal Memory: Proofs and Remarks

This appendix collects the proofs of the propositions in Section[3](https://arxiv.org/html/2608.11654#S3)and the remarks deferred from the main text\.

The unconstrained problem\.Section[3\.1](https://arxiv.org/html/2608.11654#S3.SS1)works directly with the budgeted problem; for completeness, the unconstrained statement it forgoes is the following\.

###### Definition 12\.1\(Optimal memory and write policy, unconstrained\)\.

For a materialDDand a query distributionpDp\_\{D\}, the\\newtermoptimal memory is any maximizer of the expected coverage utility,

MD∗=arg⁡maxMD⊆ED​𝔼q∼pD​\[u⁡\(q,MD\)\],M^\{\*\}\_\{D\}=\\arg\\max\_\{M\_\{D\}\\subseteq E\_\{D\}\}\\ \\mathbb\{E\}\_\{q\\sim p\_\{D\}\}\\big\[\\,u\(q,M\_\{D\}\)\\,\\big\],\(20\)and an\\newtermoptimal write policy is anyπwrite∗\\pi\_\{\\mathrm\{write\}\}^\{\*\}whose output attains the optimum; a randomized policy may return a distribution over the optimal memories\.

Thearg⁡max\\arg\\maxis a set, so optimal memories \(and hence optimal write policies\) form families of tied maximizers\. Under monotonicity this problem is degenerate: storing every event attains the maximum \(Proposition[3\.2](https://arxiv.org/html/2608.11654#S3.Thmtheorem2)\), so the capacity bound is what makes the question non\-trivial\.

###### Proof 12\.2\(Proof of Proposition[3\.2](https://arxiv.org/html/2608.11654#S3.Thmtheorem2)\)\.

IfMD⊆MD′M\_\{D\}\\subseteq M^\{\\prime\}\_\{D\}, thenΦ⁡\(MD\)⊆Φ⁡\(MD′\)\\Phi\(M\_\{D\}\)\\subseteq\\Phi\(M^\{\\prime\}\_\{D\}\)by monotonicity, so the union⋃n∈Φ⁡\(MD\)𝒬⁡\(n\)\\bigcup\_\{n\\in\\Phi\(M\_\{D\}\)\}\\mathcal\{Q\}\(n\)is contained in⋃n∈Φ⁡\(MD′\)𝒬⁡\(n\)\\bigcup\_\{n\\in\\Phi\(M^\{\\prime\}\_\{D\}\)\}\\mathcal\{Q\}\(n\), and the indicator of Definition[2\.5](https://arxiv.org/html/2608.11654#S2.Thmtheorem5)is non\-decreasing\.

###### Proof 12\.3\(Proof of Proposition[3\.4](https://arxiv.org/html/2608.11654#S3.Thmtheorem4)\)\.

The feasible set\{MD⊆ED:\|MD\|≤S\}\\\{M\_\{D\}\\subseteq E\_\{D\}:\|M\_\{D\}\|\\leq S\\\}grows withSS, so the maximum is non\-decreasing\. ForS≥\|ED\|S\\geq\|E\_\{D\}\|the full setEDE\_\{D\}is feasible and, by Proposition[3\.2](https://arxiv.org/html/2608.11654#S3.Thmtheorem2), dominates every other memory\.

###### Proof 12\.5\(Proof of Proposition[3\.6](https://arxiv.org/html/2608.11654#S3.Thmtheorem6)\)\.

Under decomposability,Φ⁡\(MD\)=⋃e∈MDΦ⁡\(\{e\}\)\\Phi\(M\_\{D\}\)=\\bigcup\_\{e\\in M\_\{D\}\}\\Phi\(\\\{e\\\}\), so the answerable set of a memory is⋃n∈Φ⁡\(MD\)𝒬⁡\(n\)=⋃e∈MDSe\\bigcup\_\{n\\in\\Phi\(M\_\{D\}\)\}\\mathcal\{Q\}\(n\)=\\bigcup\_\{e\\in M\_\{D\}\}S\_\{e\}, andu\(q,MD\)=𝟏\[q∈⋃e∈MDSe\]u\(q,M\_\{D\}\)=\\mathbf\{1\}\\big\[q\\in\\bigcup\_\{e\\in M\_\{D\}\}S\_\{e\}\\big\]\. The expected utility is therefore𝔼q∼pD​\[u⁡\(q,MD\)\]=∑q∈⋃e∈MDSepD​\(q\)\\mathbb\{E\}\_\{q\\sim p\_\{D\}\}\\big\[u\(q,M\_\{D\}\)\\big\]=\\sum\_\{q\\in\\bigcup\_\{e\\in M\_\{D\}\}S\_\{e\}\}p\_\{D\}\(q\), the total weight of the covered queries: exactly the value of the weighted maximum\-coverage instance over the per\-event query sets\{Se\}e∈ED\\\{S\_\{e\}\\\}\_\{e\\in E\_\{D\}\}with element weightspD​\(q\)p\_\{D\}\(q\)\. NP\-hardness follows because a uniformpDp\_\{D\}over a finite query set recovers unweighted maximum coverage, a classical NP\-hard problem, and the greedy algorithm that repeatedly adds the event covering the most uncovered query mass attains the\(1−1e\)\(1\-\\tfrac\{1\}\{e\}\)\-approximation\. For part \(b\), the objective is monotone by Proposition[3\.2](https://arxiv.org/html/2608.11654#S3.Thmtheorem2), and Remark[12\.6](https://arxiv.org/html/2608.11654#S12.Thmtheorem6)constructs a monotone but non\-decomposableΦ\\Phion which the marginal gain grows, so the objective is not submodular, the reduction to maximum coverage fails, and no greedy\-style guarantee applies\.

## 13Noisy Memory: Proofs and Remarks

###### Proof 13\.1\(Proof of Proposition[4\.3](https://arxiv.org/html/2608.11654#S4.Thmtheorem3)\)\.

SinceMD∩ED⊆MDM\_\{D\}\\cap E\_\{D\}\\subseteq M\_\{D\}, monotonicity givesΦ⁡\(MD∩ED\)⊆Φ⁡\(MD\)\\Phi\(M\_\{D\}\\cap E\_\{D\}\)\\subseteq\\Phi\(M\_\{D\}\), so the union of answerable sets in Definition[4\.2](https://arxiv.org/html/2608.11654#S4.Thmtheorem2)is a subset of that in Definition[2\.5](https://arxiv.org/html/2608.11654#S2.Thmtheorem5); the inequality is pointwise, and taking expectations preserves it\.

The decomposable case in detail\.WhenΦ\\Phiis decomposable and the truth functionτ\\tauis known, the noisy optimal\-memory problem of Definition[4\.5](https://arxiv.org/html/2608.11654#S4.Thmtheorem5)reduces to a weighted maximum coverage in which the weight of a claimeeisτ\(e\)⋅Prq∼pD\[q∈⋃n∈Φ⁡\(\{e\}\)𝒬\(n\)\]\\tau\(e\)\\cdot\\Pr\_\{q\\sim p\_\{D\}\}\\big\[q\\in\\bigcup\_\{n\\in\\Phi\(\\\{e\\\}\)\}\\mathcal\{Q\}\(n\)\\big\], up to overlap between claims: the query mass covered by several chosen claims is counted only once\. A false claim contributes nothing touprecu^\{\\mathrm\{prec\}\}yet consumes budget, so the optimum prefers true claims with high coverage\.