Chapter 25 · Section 25.3 · 95 min

Long-term memory

Long-term memory is what an agent keeps outside its context window and reads back when it needs it. A model sees only the tokens of its current call. What a user said last month, or what the agent learned on an earlier task, is gone unless something stored it and brings it back. This section builds that store. It covers what to keep, how to find it again, how to keep it up to date, and when to throw it away.

The previous section, §25.2, kept the window small. It slid a window over the messages, cleared old tool results, summarized the transcript, and wrote notes to files. Every one of those tools throws something away. Some of what leaves the window will be needed again, a week or a year later, in a session that never saw it.

Finding it again is a search. Each stored item and each question is turned into an embedding, a vector of numbers whose direction encodes the meaning of the text. The store returns the items whose vectors point closest to the question's. That is the vector search of §7.4. Two things make memory harder than searching a fixed set of documents. The store is written while it is being read, and what it holds goes out of date.

Here is the failure in its simplest form. In March a user, Sam, tells her assistant that she is vegetarian. In July she mentions, in passing, that she now eats fish. In October she asks where to go for dinner, and the assistant suggests a steakhouse. Three things can have gone wrong in the memory, and each needs a different fix.

Never written. Nothing turned the July remark into a memory, because nothing decided it was worth keeping. The fix is a write policy, the rule that decides what to store.
Written but not retrieved. The fish fact is in the store, but the dinner question pulled up other memories. The fix is better retrieval. We will show, under a simple model, that retrieval gets harder as the store grows.
Retrieved but stale. The March fact came back, alone or next to the July one, and the model used it. The fix is to update, retire, and date memories when they are written.

We take the three in turn. First come the kinds of memory an agent can have. Then a precise memory store, the score that retrieves from it, and a proof that a bigger store retrieves worse. Then an idea from operating systems, moving information between the window and the store, with the cache policies behind it and a proof that one of them is optimal. Then write policies, duplicates, and forgetting, and last the published systems and their numbers.

Designing memory for an assistant is a common system design question in interviews for agent teams. Every part of this section is something an interviewer can probe.

Four kinds of memory

Psychologists sort human memory into kinds. The sorting is a useful checklist for an agent, as long as we treat it as an analogy. You remember the dinner where you met someone, an event with a time and a place. You know their name and that they are vegetarian, facts drawn from many events. You know how to cook a risotto without thinking about it, a skill. All of this sits behind a small working memory that holds what you are thinking about right now.

Cognitive Architectures for Language Agents, or CoALA (Sumers et al. 2024), is a framework for describing agents built on language models. It adopted the same four kinds. Most memory systems since can be described in its terms.

📐 Working, episodic, semantic, and procedural memory

These are the four kinds of memory of CoALA (Sumers et al. 2024), adapted to agents built on language models.

Working memory is the information active in the current decision. For an agent it is what is in the context window of the current call (§25.1), plus the variables the agent's code carries between calls.
Episodic memory stores past experiences with their times. For an agent these are logs of conversations, tool calls, observations, and whole attempts at tasks.
Semantic memory stores knowledge about the world and the user, drawn out of many episodes. For an agent these are extracted facts ("Sam eats fish"), profiles of people and things, and knowledge graphs, stores of facts written as (subject, relation, object) triples such as (Sam, works at, a hospital).
Procedural memory stores how to act. For an agent it has two forms, the skills built into the model's weights and the explicit procedures in its code, prompts, skill libraries, and playbooks.

The last three are long-term memory. They are kept outside the context of any single call and brought into it by retrieval.

kind	what it holds	how an agent stores it	how it is written	systems in this section
working	the current task, recent turns, retrieved items	the context window	every turn	everything in §25.1 and §25.2
episodic	what happened, and when	an append-only log of messages and attempts, embedded for search	automatically, as events occur	MemGPT's recall storage, Generative Agents' memory stream
semantic	facts and relations drawn from episodes	fact stores, entity summaries, knowledge graphs	by extraction, merging, or reflection	Mem0, Zep, HippoRAG, A-MEM
procedural	how to do things	weights; code, skills, workflows, playbooks	by training, or by distilling attempts that worked	Voyager, Agent Workflow Memory, ACE

Each system in the last column is described later in the section, where it is used. Two facts in this table matter more than the labels.

First, semantic memory is made from episodic memory. A fact store is what you get by reading the log and deciding what it means, and each such decision can be wrong. So every derived memory should point back to the episodes it came from. That record is its provenance. It is what lets you check a memory again, correct it, or delete it along with everything built from it.

Second, procedural memory is the most dangerous to write. A wrong fact misleads one answer, while a wrong skill is reused on every later task. CoALA makes the same point. Writing new procedures is riskier than adding episodes or facts, because it can introduce bugs or let an agent work around its designers' intentions. Writing procedures into the weights is the subject of §25.5. This section covers the explicit kind.

An interviewer who asks you to design memory for an assistant expects you to name all four kinds and say which one each part of your design stores.

A memory store and its retrieval score

Here is the idea before any symbols. A memory is a short piece of text with a few numbers attached. When a question comes in, every memory gets three scores.

Relevance says how close its meaning is to the question. It is the cosine of the angle between the two embeddings, 1 for the same direction and smaller the less related the texts are.
Recency says how long ago the memory was last used. It starts at 1 and shrinks by a fixed factor every hour.
Importance says how much the memory mattered when it was written.

The store adds the three and returns the best few. Before adding, it stretches each score so that it runs from 0 to 1 over the candidates. That step is called min-max scaling. Its purpose is that no score wins just because of its units.

This is the retrieval rule of a paper on simulated characters (Park et al. 2023), which we will call Generative Agents after its title. It built a small town of characters, each driven by a language model. Each character kept a memory stream, a log of everything it observed, and retrieved from it with this rule. Here is the rule precisely.

📐 A memory store and its retrieval score

A memory store $\mathcal{M}$ is a set of $N_{\mathcal{M}}$ entries. Entry $j$ is a tuple $(\mathbf{k}_j, v_j, t_j, \iota_j, \text{src}_j)$ where

$v_j$ is the stored content, usually a short text,
$\mathbf{k}_j \in \R^d$ is its key, the embedding of $v_j$ by an embedding model (§7.3),
$t_j$ is the time it was last accessed, in hours (the creation time is kept too, as metadata),
$\iota_j$ is its importance, for example an integer from 1 to 10 rated by a language model when the memory is written,
$\text{src}_j$ is its provenance, the list of episodes (messages, documents, tool results) it was derived from.

A query arrives at time $t$ with embedding $\mathbf{q} \in \R^d$ . The candidates are a set $J \subseteq \mathcal{M}$ , either all entries or those that pass metadata filters such as user, project, or date. The retrieval score of candidate $j$ is

\text{score}_j = \alpha_{\text{rel}}\,\widetilde{\text{rel}}_j + \alpha_{\text{rec}}\,\widetilde{\text{rec}}_j + \alpha_{\text{imp}}\,\widetilde{\text{imp}}_j, \qquad \text{rel}_j = \cos(\mathbf{q}, \mathbf{k}_j),\quad \text{rec}_j = \gamma_{\text{rec}}^{\,t - t_j},\quad \text{imp}_j = \iota_j,

where $\gamma_{\text{rec}} \in (0, 1)$ is the recency decay per hour and the $\alpha$ are nonnegative weights. A tilde means min-max scaling over the candidates, $\tilde x_j = (x_j - \min_{l \in J} x_l)/(\max_{l\in J} x_l - \min_{l\in J} x_l)$ , with $\tilde x_j = 0$ for every $j$ when all the $x_l$ are equal. The store returns the $k$ candidates with the highest scores and sets their $t_j$ to $t$ .

In plain words, a memory comes back if it is about the question, if it was used recently, and if it mattered. Generative Agents set all three weights to 1. Importance came from asking the model for an integer from 1 ("brushing teeth") to 10 ("a break up"). Recency decayed by $\gamma_{\text{rec}} = 0.995$ per hour of game time, counted from the last time the memory was retrieved. The subscript on $\gamma_{\text{rec}}$ keeps it apart from the discount factor $\gamma$ of reinforcement learning.

The last clause of the definition creates a feedback loop. Retrieval resets $t_j$ , so a memory that is retrieved once becomes more likely to be retrieved again. That keeps the memories of an ongoing conversation at hand. It can also lock in an early mistake, as the store class below will show.

What a decay of 0.995 per hour means

How fast does a decay of 0.995 per hour forget? The half-life $h_{1/2}$ is the age at which recency falls to one half. It solves $\gamma_{\text{rec}}^{h_{1/2}} = 1/2$ . Take logarithms of both sides and divide.

So raw recency separates memories by weeks. Within a day it barely ranks anything. Min-max scaling then does something quite different to it, as the next example shows.

✏️ Five memories, scored by hand

The dinner question has embedding $\mathbf{q}$ . Five memories are candidates, with $\gamma_{\text{rec}} = 0.995$ and all weights 1.

memory	rel (cosine)	hours since access, $t - t_j$	rec $= 0.995^{t - t_j}$	importance
1. Sam said she is vegetarian	0.62	5,000	$1.3\times10^{-11}$	7
2. Sam now eats fish	0.55	2,200	$1.6\times10^{-5}$	6
3. Sam loves the Italian place on 5th	0.58	900	0.011	4
4. Had coffee with Sam this morning	0.40	3	0.985	2
5. Sam's birthday is in November	0.35	4,000	$2.0\times10^{-9}$	5

Raw sum. Divide importance by 10 to put it on a 0 to 1 scale. The sums are 1.320, 1.150, 0.991, 1.585, and 0.850. The coffee memory wins, because its recency of 0.985 swamps everyone else's near-zero recency.

Min-max scaled sum. Relevance spans 0.35 to 0.62, so it scales to 1, 0.741, 0.852, 0.185, and 0. Recency scales to 0, 0, 0.011, 1, and 0. Importance spans 2 to 7 and scales to 1, 0.8, 0.4, 0, and 0.6. The sums are 2.000, 1.541, 1.263, 1.185, and 0.600, and the ranking is 1, 2, 3, 4, 5.

Both rankings fail the user, in different ways. The raw one is distracted by a trivial recent event. The scaled one puts the stale vegetarian fact above the newer fish fact. The vegetarian fact is a little more similar to the question and was rated more important. No choice of weights fixes this reliably, since the two facts are nearly the same distance from the question. Staleness is a write problem, and we will fix it there.

Why did scaling change the winner so much? Because it quietly changes the weights. The next result makes that exact.

∴ Min-max scaling reweights each component by its range

For each component $c \in \{\text{rel}, \text{rec}, \text{imp}\}$ , let $x_{c,j}$ be its raw value for candidate $j$ and let $r_c = \max_{l\in J} x_{c,l} - \min_{l\in J} x_{c,l} > 0$ be its range over the candidates. Then

\text{score}_j = \sum_c \frac{\alpha_c}{r_c}\, x_{c,j} \;-\; \sum_c \frac{\alpha_c}{r_c}\min_{l\in J} x_{c,l},

and the second sum is the same for every candidate. So ranking by the scaled score is ranking by the raw components with effective weights $\alpha_c/r_c$ , which depend on the candidate set.

Proof. Substitute $\tilde x_{c,j} = (x_{c,j} - \min_l x_{c,l})/r_c$ into the score and collect terms. $\blacksquare$

In plain words, scaling divides each weight by how much that component varies among the candidates. In the example, relevance's effective weight went up by $1/0.27 = 3.7$ and importance's by $10/5 = 2$ relative to the raw sum, while recency's stayed about the same, since its range was nearly 1.

Now picture a candidate set that was all touched within the last day. Recency then varies by at most $1 - 0.887 = 0.113$ , so its effective weight is multiplied by $1/0.113 = 8.8$ . A few hours of age now count as much as the whole spread of relevance. If the candidates span six months, recency keeps its nominal weight. So the same weights mean different things for different stores. Adding one very old or very new memory can reorder all the others.

Min-max scaling is still a reasonable default, because the raw components come in incompatible units (a cosine near 0.6, an importance near 5). Just know that it is a reweighting that depends on the data, not a neutral normalization. The same problem is why §7.5 merged keyword search and embedding search by rank rather than by adding normalized scores. Its method, reciprocal rank fusion, gives each item one over a constant plus its rank in each list, and adds these up. An interviewer who hands you the score formula will ask exactly this, what the weights mean after scaling.

The first cell checks the example and the half-life.

Python · cell 1

Here is the whole store as a small class. It has the five operations a store needs, write, update, delete, retrieve, and forget. Provenance is a list that only grows, so an updated memory still remembers every episode behind it. forget keeps the entries with the highest recency times importance, one simple capacity policy among many.

Python · cell 2

Look at what forget kept. The two memories that were just retrieved now have recency 1, so they survive along with the morning coffee. The Italian restaurant and the birthday are gone. The act of reading decided what was forgotten, and the stale vegetarian fact survived because it had just been read.

Production systems rarely use this three-term sum alone. Relevance is often a hybrid of two searches fused by rank (§7.5). One is BM25, a keyword score that counts the query's words in each memory and weights rare words more. The other is the embedding similarity above.

The candidate set is first cut by metadata filters, such as this user, this project, the last 30 days, or entries about this person. Then the top few dozen candidates are reranked by a cross-encoder, a model that reads the query and the memory together and scores the pair.

Zep, a memory system built on a knowledge graph, gathers candidates three ways (Rasmussen et al. 2025). It uses cosine search, BM25, and breadth-first search over the graph. It then reranks them with methods such as reciprocal rank fusion and maximal marginal relevance, a rule we apply to memories in the next part. The vector index underneath is the one of §7.4. What is new for memory is the time dimension, and the fact that the store is written while it is read.

Core

Retrieval by relevance, recency, and importance

Implement retrieve(query, keys, ages_h, importance, k, weights=(1.0, 1.0, 1.0), decay=0.995).

query has shape (d,), and keys has shape (N, d). The keys need not be normalized.
ages_h holds the hours since each memory was last accessed, and importance holds the importance ratings.

Score every memory with the retrieval score defined above. Relevance is cosine similarity, and recency is decay ** ages_h. Min-max scale each component over all $N$ candidates before applying the weights, and scale a constant component to zeros. Return the indices of the k best memories as a list of ints, best first. Break ties in favor of the smaller age, then the smaller index.

import numpy as np

def retrieve(query, keys, ages_h, importance, k, weights=(1.0, 1.0, 1.0), decay=0.995):
    rel = np.asarray(keys) @ np.asarray(query)                # placeholder: raw dot product only
    return [int(i) for i in np.argsort(-rel)[:k]]

Tests, hints, verified solutions, and AI help, with Pro at $7.99 a month.

Why more memories make retrieval worse

A store that only grows has a problem that a fixed document collection does not. Every new memory is a new rival for every old question. A memory about something else rarely wins. A memory about the same subject often does.

Start with numbers. Suppose each rival memory has a 3% chance of scoring above the one we want. With one rival, the right memory comes first 97% of the time. With 10 independent rivals it comes first $0.97^{10} = 74\%$ of the time, and with 100 only $0.97^{100} = 4.8\%$ of the time. By the hundredth memory about Sam's food, the one that answers today's question may have 99 rivals that are nearly as close.

Now make it general. A query $\mathbf{q}$ has cosine $c$ with the memory we want, the target. The other $N$ memories are distractors, with cosines $X_1, \dots, X_N$ with the query. The target is retrieved first exactly when $c$ beats every $X_i$ . The theorem below gives that probability, and then asks how high the strongest distractor climbs as $N$ grows.

∴ Retrieval against N distractors

Fix the query and the target cosine $c$ . Let the distractor cosines $X_1, \dots, X_N$ be independent, each exceeding $c$ with probability $p$ . Then

\mathbb{P}(\text{target ranks first}) = (1 - p)^N, \qquad N_{1/2} = \frac{\ln 2}{-\ln(1 - p)} \approx \frac{\ln 2}{p},

where $N_{1/2}$ is the number of distractors at which the target ranks first only half the time.

If the distractor cosines are Gaussian, $X_i \sim \mathcal{N}(\mu, \sigma^2)$ , then $p = 1 - \Phi(z)$ with $z = (c - \mu)/\sigma$ , where $\Phi$ is the standard normal cumulative distribution function, and $p \le \tfrac12 e^{-z^2/2}$ for $z \ge 0$ . Whether or not they are independent, Gaussian cosines satisfy

\mathbb{E}\Big[\max_{i \le N} X_i\Big] \le \mu + \sigma\sqrt{2\ln N}.

Why the formula holds. The target ranks first when every distractor stays below $c$ , and independent distractors each do so with probability $1 - p$ . The second solves $(1 - p)^N = 1/2$ for $N$ , with $-\ln(1-p) \approx p$ for small $p$ .

The bound on the expected maximum is the one worth deriving. It says the strongest rival grows only like the square root of $\ln N$ . So the damage grows slowly with the size of the store. What decides it is the margin $c - \mu$ , measured in units of $\sigma$ .

∂ The expected maximum of N Gaussians is at most mu + sigma sqrt(2 ln N)

§16.1 proved the standard case. For standard normals $Z_1, \dots, Z_N$ , apply Jensen's inequality (§0.4) to the convex function $e^{\lambda x}$ , bound the maximum $e^{\lambda\max_i Z_i}$ by the sum $\sum_i e^{\lambda Z_i}$ , and use the Gaussian moment generating function $\mathbb{E}[e^{\lambda Z_i}] = e^{\lambda^2/2}$ . That gives $\mathbb{E}[\max_i Z_i] \le \ln N/\lambda + \lambda/2$ for every $\lambda > 0$ , and the choice $\lambda = \sqrt{2\ln N}$ gives $\sqrt{2\ln N}$ . Bounding a maximum of positive numbers by their sum needs no independence, so neither does the result.

Now write $X_i = \mu + \sigma Z_i$ , so that each $Z_i$ is a standard normal. Then $M = \max_i X_i = \mu + \sigma\max_i Z_i$ , and taking expectations gives $\mathbb{E}[M] \le \mu + \sigma\sqrt{2\ln N}$ . $\blacksquare$

The tail bound in the theorem takes one more line. Let $\phi$ be the standard normal density. For $z \ge 0$ , $1 - \Phi(z) = \int_z^\infty \phi(u)\,du$ . Substituting $u = z + s$ gives $\phi(z + s) = \phi(z)e^{-zs - s^2/2} \le \phi(z)e^{-s^2/2}$ , so $1 - \Phi(z) \le \phi(z)\int_0^\infty e^{-s^2/2}ds = \phi(z)\sqrt{\pi/2} = \tfrac12 e^{-z^2/2}$ .

Plug in numbers, and the picture splits in two.

✏️ Interference at real scale

Random memories are harmless. Take keys that are random directions in $d = 768$ dimensions. Random high-dimensional vectors are nearly orthogonal (§1.3). So their cosines with the query have mean 0 and standard deviation $1/\sqrt{768} = 0.036$ . Even a million of them have an expected maximum of at most $0.036\sqrt{2\ln 10^6} = 0.19$ . That is far below the cosine of 0.5 or more that a query has with a memory that answers it. Here $z = 0.5\sqrt{768} = 13.9$ and $p \approx 6\times10^{-44}$ . Unrelated memories almost never crowd out the right one.

Memories on the same subject are the problem. The rivals that matter are about the same person and the same subject. Their cosines with the query are high and spread out. Take illustrative values in the range real embedding models produce for such text, $\mu = 0.45$ and $\sigma = 0.08$ for the distractors and $c = 0.6$ for the target. Then $z = 1.875$ , $p = 1 - \Phi(1.875) = 0.0304$ , and $N_{1/2} = 22$ . With 10 such memories the target is first with probability $(1 - p)^{10} = 0.73$ . With 100 it is first only $(1 - p)^{100} = 4.6\%$ of the time.

The logarithm in the bound grows slowly, but here the margin $c - \mu$ was less than two standard deviations to begin with. Measure $\mu$ , $\sigma$ , and $c$ on your own embedding model and data, because they vary a lot between models.

The simulation below builds such a cluster of same-subject memories out of real normalized vectors and checks the theorem. It also shows where the Gaussian model is off. Cosines of unit vectors are bounded, and their upper tail is lighter than a Gaussian's, so the Gaussian formula is pessimistic at large $N$ . The formula $(1 - p)^N$ with $p$ measured directly does better.

Python · cell 3

The target cosine is 0.61. The distractors average 0.33, with a spread of 0.078 for a given question. That is a margin of about 3.6 standard deviations, nearly twice the one in the example above, so the decline is slower. The share of questions whose target ranks first falls from 0.99 with 10 distractors to 0.67 with 3,000. The direct formula $(1-p)^N$ tracks the simulation closely up to $N = 1{,}000$ (0.79 against 0.78). The Gaussian model is pessimistic, as predicted (0.67 there). The mean maximum stays below the bound $\mu + \sigma\sqrt{2\ln N}$ at every $N$ .

The theorem also says what to do about interference. Every remedy either shrinks $N$ or widens the margin.

Shrink the candidate set. Metadata filters (this user, this person, this time range) remove distractors before the similarity search sees them.
Remove near-duplicates and merge them. Ten restatements of one fact are ten distractors for every other fact on the subject. Merging them into one memory, as we do later in this section, lowers $N$ without losing information.
Widen the margin. Anything that raises $c - \mu$ helps. Examples are an embedding model trained for the domain, keys written as the questions a memory answers, a reranker that reads the query and the memory together, and structure such as people and dates.
Retrieve more than one. Asking for the top $k$ instead of the top 1 turns "first" into "in the top $k$ ", which degrades much more slowly. The price is context tokens, and §25.1 showed that every extra token in the window dilutes attention.

Retrieving several memories has a trap of its own, and it comes from the same near-duplicates. If the store holds three restatements of the vegetarian fact, the top 3 for the dinner question are those three, and the fish fact is still left out.

The standard remedy is maximal marginal relevance (MMR), defined in §7.6 (Carbonell and Goldstein 1998). It picks memories one at a time and charges each candidate for being similar to what was already picked. With $S$ the set chosen so far and $\lambda_{\text{mmr}} \in [0, 1]$ a trade-off weight, it takes the candidate $j$ outside $S$ that maximizes

\lambda_{\text{mmr}}\cos(\mathbf{q}, \mathbf{k}_j) - (1 - \lambda_{\text{mmr}})\max_{i \in S}\cos(\mathbf{k}_i, \mathbf{k}_j).

In plain words, the first pick is the most relevant memory, and a second copy of it scores poorly because it is so close to the first. The cell runs the rule on six memories about Sam, three of them restatements. sam_rel holds their cosines with the question, and sam_sims holds the cosines between them.

Python · cell 4

At $\lambda_{\text{mmr}} = 1$ the rule is plain ranking and returns the three restatements. At 0.7 it returns the vegetarian fact, the Italian restaurant, and the fish fact. By hand, after the first pick the second restatement scores $0.7 \cdot 0.61 - 0.3 \cdot 0.97 = 0.136$ , the fish fact $0.7 \cdot 0.55 - 0.3 \cdot 0.70 = 0.175$ , and the restaurant $0.7 \cdot 0.58 - 0.3 \cdot 0.45 = 0.271$ , so the restaurant comes second. For the third pick the fish fact still scores 0.175, and the coffee memory scores $0.7 \cdot 0.40 - 0.3 \cdot 0.40 = 0.160$ , so the fish fact comes third. At 0.5 the coffee memory displaces the fish fact. This is the failure §7.6 warned about, a memory picked mainly because it is different.

Notice what MMR does not fix. Both diet facts are now in the window, so failure 2 is gone for this question. But nothing tells the model which one is current. That is failure 3, and it needs the dates that a write policy records.

Paging between the window and the store

So far the agent's code decided when to retrieve. MemGPT (Packer et al. 2023) is a system that hands that decision to the model, with an idea borrowed from operating systems. A computer gives each program the illusion of a huge memory. It keeps a small, fast main memory and a large, slow disk, and moves fixed-size blocks called pages between them. When a program touches something that is not in main memory, that is a page fault, and the page is brought in.

MemGPT treats the context window as main memory and external stores as disk. The model moves information between them itself, through function calls, the structured tool requests that the agent's code carries out (§24.1). Its prompt on each call, the main context, has three parts.

System instructions, which are read-only.
A working context, a fixed-size block of text the model can edit through function calls. It keeps key facts about the user and about itself there.
A FIFO queue, first in first out, that holds the rolling message history. Its first slot holds a summary of the messages already evicted, and each new summary is written from the old one plus the newly evicted messages.

Outside the prompt sit two stores. Recall storage is a database of every message ever exchanged, an episodic memory. Archival storage is a database of arbitrary text that the model can read and write, a semantic memory. The model pages information in by calling search functions on these stores. Their results arrive a page at a time and are appended to the queue. It pages information out by calling functions that write to the working context or to archival storage.

When the window fills, a queue manager applies the compaction policy of §25.2, which replaces old messages with a summary. At about 70% of the window it inserts a "memory pressure" warning, so that the model can save what matters. At 100% it evicts about half the window and folds it into a new summary. What is new is that evicted messages stay searchable in recall storage. A function call can also ask for another model step right away, a "heartbeat", so the model can chain several searches before it answers.

MemGPT was tested on deep memory retrieval, a task built from chats that span several sessions, in which each question refers to a detail from an earlier session. Accuracy rose from 32.1% to 92.5% with GPT-4 and from 35.3% to 93.4% with GPT-4 Turbo. The baselines saw only a lossy summary of the earlier sessions. MemGPT had the full history and had to search it itself.

The authors of Zep, the memory system built on a knowledge graph that we met above, ran the same task and add a fair caveat (Rasmussen et al. 2025). Their system scored 94.8% with GPT-4 Turbo, a little above MemGPT. But the conversations in that task are only about 60 messages long and fit in a modern context window. So the task tests a regime that no longer stresses memory. Two harder benchmarks are covered in §25.6. LoCoMo tests very long chats over many sessions, and LongMemEval tests histories of about 115,000 tokens.

An interviewer will ask what MemGPT changes. The answer is who decides to retrieve. The model, not fixed code, chooses when to search and what to save, and that choice can fail, as the end of this part shows.

The paging problem

Whatever decides what to bring in, something must decide what to push out. Strip the problem to its core.

📐 The paging problem and its policies

A context holds at most $C$ items (memories, files, documents), its slots. Requests $x_1, x_2, \dots, x_n$ arrive one at a time. If $x_t$ is in the context, the request is a hit. Otherwise it is a miss. Then $x_t$ must be fetched, and if the context is full one item must be evicted to make room. A demand policy fetches only on a miss. Four classic eviction rules are

FIFO, evict the item that was fetched longest ago,
LRU (least recently used), evict the item whose last request is oldest,
LFU (least frequently used), evict the item requested least often since it was fetched,
Belady's rule, also called MIN, OPT, or farthest in future, evict the item whose next request is furthest in the future, or that is never requested again (Belady 1966).

The first three are online, since they use only the past. Belady's rule needs the future, so it is a yardstick, not a policy.

For an agent, a miss is a tool call, one more trip around the agent loop. It costs a model step, its latency, and the tokens of the fetched item. Eviction has a cost too. A provider's prompt cache stores the computed state of a prompt prefix it has seen before and bills a repeat of that prefix at a discount. As §25.2 warned, removing an item from the middle of the window breaks that prefix, so everything after the removed item is billed in full again. So misses and evictions are worth counting carefully.

✏️ Twelve requests, three slots, by hand

Take the request sequence 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 and $C = 3$ slots.

Belady. Requests 1, 2, 3 are compulsory misses, since the context starts empty. At request 4 the context is $\{1, 2, 3\}$ , and their next uses are at positions 5, 6, and 10, so evict 3. Requests 1 and 2 hit. At request 5 the context is $\{1, 2, 4\}$ with next uses 8, 9, and 11, so evict 4. Requests 1 and 2 hit. At request 3 (position 10) the context is $\{1, 2, 5\}$ , and neither 1 nor 2 is used again, so evict either, say 1. At request 4 the context is $\{2, 3, 5\}$ , and neither 2 nor 3 is used again, so evict either, say 2. Request 5 hits. Total, 7 misses.

LRU. The first four requests miss, and request 4 evicts 1. Requests 1 and 2 each miss and evict the least recent item (2, then 3). Request 5 misses and evicts 4. Requests 1 and 2 hit, and requests 3, 4, 5 each miss. Total, 10 misses.

FIFO. The first seven requests all miss, as with LRU. Requests 1 and 2 then hit. Request 3 evicts 1, the oldest arrival, and request 4 evicts 2, so the final request for 5 hits. Total, 9 misses. LRU did worse here because the hits on 1 and 2 made 5 the least recently used item, and 5 was needed last.

Now give FIFO a fourth slot, and it misses 10 times, more than with three. More room made it worse. This is Belady's anomaly (Belady, Nelson, and Shedler 1969). With four slots, LRU misses 8 times and Belady 6.

The anomaly can never happen to LRU. Once the context is full, LRU with $C$ slots holds exactly the $C$ most recently used distinct items, and those are always among the $C + 1$ most recently used. So every hit with $C$ slots is also a hit with $C + 1$ , and misses can only fall as the context grows.

Belady's rule is the best possible, and the proof is a classic interview topic.

The idea of the proof is an exchange argument. Take any optimal schedule. Wherever it first disagrees with Belady's rule, change that one decision to Belady's, and show that the miss count does not go up. Repeat until the schedule is Belady's rule itself.

∂ The exchange argument

A schedule is a list of eviction decisions for a request sequence $\sigma$ . Call it reduced if it loads an item only when that item is requested and missing, so that its loads are its misses. Any schedule can be reduced without adding loads, since an item loaded early can instead be loaded when it is next requested, or not at all. Write FF (farthest in future) for Belady's rule. This is the textbook argument in the chapter on greedy algorithms of Kleinberg and Tardos (2005), Algorithm Design.

Claim. Let $S$ be a reduced schedule that makes the same decisions as FF on the first $j$ requests. Then there is a reduced schedule $S'$ that makes the same decisions as FF on the first $j + 1$ requests and has no more misses than $S$ .

Proof of the claim. If request $j + 1$ is a hit, or a miss on which $S$ and FF evict the same item, take $S' = S$ . Otherwise it is a miss on which FF evicts $e$ and $S$ evicts some $f \ne e$ . Let $S'$ evict $e$ , like FF. Now the contexts of $S$ and $S'$ are equal except that $S$ holds $e$ where $S'$ holds $f$ . From request $j + 2$ on, let $S'$ copy every decision of $S$ until the first of these events.

A request for some $y \notin \{e, f\}$ misses and $S$ evicts $e$ . Then $S'$ evicts $f$ instead, and the two contexts become identical, after the same number of loads.
A request for $f$ . $S'$ hits, and $S$ misses. If $S$ evicts $e$ to load $f$ , the contexts become identical and $S'$ has one fewer miss. If $S$ evicts some other $x$ , let $S'$ evict $x$ and load $e$ . That is an unreduced step costing one load, the same as the miss $S$ just paid. The contexts become identical with $S'$ at no more loads.
A request for $e$ . This cannot come first. FF evicted $e$ because its next request was no earlier than $f$ 's. So $f$ is requested first, or neither is requested again, in which case the difference never matters.

Every other request hits or misses identically in both. Once the contexts are identical, $S'$ copies $S$ to the end. So $S'$ agrees with FF through request $j + 1$ and has at most as many loads as $S$ . Reducing $S'$ adds no loads and does not change its first $j + 1$ decisions, because those were already demand loads. $\blacksquare$

The theorem. Start from an optimal reduced schedule and apply the claim for $j = 0, 1, \dots, n - 1$ . Each step keeps the miss count at most the optimum, and the last schedule is FF itself. $\blacksquare$

Belady's rule needs the future, so how close can an online policy get? Sleator and Tarjan (1985) answered this with the result that founded competitive analysis. It studies how far an online algorithm can fall behind an optimal one that knows the future, on the worst possible input.

In plain words, LRU can be terrible in the worst case, but give it about twice the room and it is never far from what an oracle could do with the original room. Take the two cases. With equal room, $C' = C$ , the ratio is $C$ , a weak guarantee, and it is tight. A loop over $C + 1$ items makes LRU miss on every request, while Belady misses only about once every $C$ requests, so over a long loop the ratio approaches $C$ . With twice the room, $C = 2C'$ , the ratio is $2C'/(C' + 1)$ , below 2.

∂ Why LRU is within a factor C of the optimum

Take equal capacities, $C' = C$ , and split the request sequence into phases. The first phase starts at the first request. Each phase is the longest stretch of requests that contains at most $C$ distinct items, so the next phase starts at the request that would be the $(C + 1)$ th distinct item.

LRU misses at most $C$ times per phase. Suppose an item $x$ requested in a phase were evicted later in the same phase. LRU evicts $x$ only when $x$ is the least recently used of $C$ cached items and a new item arrives. Then $C$ distinct items other than $x$ (the $C - 1$ others in the context and the newcomer) were all requested after $x$ 's last request. With $x$ that makes $C + 1$ distinct items in one phase, which is impossible. So each distinct item of a phase misses at most once in it.

The optimum misses at least once per phase, after the first. Let $a$ be the item of the first request of phase $i$ . Look at the window from the next request through the first request of phase $i + 1$ . Every phase but the last has exactly $C$ distinct items, so the window contains the $C - 1$ other items of phase $i$ and the first item of phase $i + 1$ , which is new. That is $C$ distinct items other than $a$ . Right after serving $a$ , any policy holds $a$ and at most $C - 1$ other items, so at least one of those $C$ items misses inside the window. The windows of different phases do not overlap.

With $P$ phases, LRU makes at most $CP$ misses and the optimum at least $P - 1$ . So LRU's misses are at most $C$ times the optimum's, plus $C$ . $\blacksquare$

The proof's two halves are worth seeing on a trace. The widget races the eviction rules over two request sequences. One is a loop over 6 items with $C = 5$ slots, the worst case behind the factor $C$ . The other is a sequence of working-set phases, like an agent that moves from one subtask to the next. The widget opens on the loop. Before you read its counts, predict how many of the 48 requests LRU will miss and how many Belady will. Then switch to the working-set phases and guess which policy suffers most at $C = 3$ , and why LFU might be worse than FIFO there.

On the phased trace, LFU misses most at every capacity from 3 slots up. It keeps items that were popular in an earlier phase long after the agent has moved on. Memory scores that count how often a memory was used share this failure.

Real agent traces are phased like this. A coding agent reads a handful of files intensively, then moves to another part of the codebase. The right mental model of what its context should hold is the working set, the set of items used in a recent window of time (Denning 1968). In practice this means a context budget should be sized to the working set of the current phase, and old phases should be evicted whole, not kept because they were once popular.

Interview

An LRU cache in O(1)

This is one of the most common coding interview questions. LRU is also the eviction rule of many real caches. Recall that an inference server keeps a KV cache, the key and value vectors of every token it has already read, so that it never recomputes them. SGLang, an inference server, keeps a tree of cached prefixes shared between requests and evicts the least recently used leaf first (Zheng et al. 2024). The section on paged caches and prefix sharing shows the same LRU rule in vLLM's block cache.

Implement a class LRUCache(capacity) with two methods.

get(key) returns the value stored under key, or -1 if it is not cached. It counts as a use.
put(key, value) inserts or overwrites the value and counts as a use. If inserting a new key would exceed capacity, it first evicts the least recently used key. Overwriting a key that is already cached never evicts anything.

The capacity is at least 1.

Both must take $O(1)$ time. Use a dict and a doubly linked list, not collections.OrderedDict or functools.

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = {}

    def get(self, key):
        return self.data.get(key, -1)      # placeholder: never evicts, never tracks recency

Tests, hints, verified solutions, and AI help, with Pro at $7.99 a month.

Research

How far is LRU from optimal?

The setup defines two traces. TRACE holds 3,200 file reads by a simulated coding agent that works in phases on small sets of files, with some stray reads. CLASSIC holds the twelve requests of the worked example.

Implement misses(trace, capacity, policy) for policy in "fifo", "lru", and "belady". Count every miss, including the first request for each item.
Implement slots_to_match(trace, h, max_capacity=60). It returns the smallest capacity at which LRU makes no more misses than Belady makes with h slots, or None if no capacity up to max_capacity does.

The tests check the worked example, the agent trace, and how many extra slots LRU needs. Compare that with the bound of Sleator and Tarjan.

def misses(trace, capacity, policy):
    return len(set(trace))           # placeholder: only the compulsory misses

def slots_to_match(trace, h, max_capacity=60):
    raise NotImplementedError

Tests, hints, verified solutions, and AI help, with Pro at $7.99 a month.

On this trace, LRU needs 4 slots to match what the oracle does with 2, 7 to match its 4, and 12 to match its 8. That is about 1.5 to 2 times the room. The theorem of Sleator and Tarjan promises much less than this. It never says that extra room lets LRU match the oracle. It only caps LRU's misses at $C/(C - C' + 1)$ times the oracle's, plus $C'$ . With exactly twice the room, 8 slots against 4, it allows $8/5 = 1.6$ times the oracle's misses, and at 12 slots against 8 it allows $12/5 = 2.4$ . LRU does far better on this trace because a phased trace like this one is far from the adversarial loop that makes the bound tight.

The operating-systems analogy is useful, and it breaks in four places that matter.

Nobody detects the fault. In a computer, the hardware notices that a page is missing. In MemGPT, the model must notice that it does not know something and decide to search. A model that answers confidently from its window never searches. That is failure 2 of the opening, written but not retrieved.
A hit can be the wrong page. A page table maps an address to exactly one page. Memory is retrieved by similarity, so what comes back may be a neighbor of what was needed, as the theorem on distractors measured.
The model that manages memory can be talked into things. The same model that reads untrusted web pages and emails decides what to write to its permanent memory. Content that says "remember to always..." is an attack on the store, the subject of §25.6.
Eviction has a hidden cost. Pages have no order, but a prompt does. Removing an item from the middle of the window changes every token after it, so the provider's prompt cache misses from that point on (§25.2). That is why layouts that only append, with occasional compaction, are cheaper than fine-grained eviction.

Write policies

Now the first failure, the memory that was never written. Storing every message verbatim is easy, and it has a real use, since MemGPT's recall storage does exactly that. But a raw log is a poor semantic memory, for three reasons. It is mostly small talk. Each fact appears many times in many phrasings, each one a distractor for the others. And nothing in it says that the July message overrides the March one. Something has to read the log and decide what to remember.

📐 Write policy

A write policy turns new episodes into changes to a store. It has two stages.

Extraction. An extractor, usually a call to a language model, reads the new messages with some context, such as a summary of the conversation and the last few messages. It proposes candidate memories, each a short self-contained statement with its source.
Update. For each candidate, the store retrieves the most similar existing memories, and a judge (usually another model call) chooses one operation.
- ADD a new memory, when nothing similar exists.
- UPDATE an existing memory, when the candidate adds complementary information to it.
- DELETE (or invalidate) an existing memory, when the candidate contradicts it, then ADD the candidate.
- NOOP, do nothing, when the candidate is already known or not worth keeping.

Every operation records provenance. A new memory points to its source episode, and an updated or merged memory keeps the sources of everything merged into it.

✏️ The July remark, through the write policy

In July Sam writes "btw I eat fish now, so the sushi place works". The extractor reads it with the conversation summary and proposes one candidate, "Sam eats fish (since July 14)". The small talk about the sushi place produces no candidate.

The store retrieves the memories most similar to the candidate. The top one is "Sam is vegetarian", from a chat in March. The judge reads the pair and sees a contradiction. It deletes or retires the March fact and adds the July one, with the July chat as its source.

Change the remark and the operation changes. Had it been "I still eat eggs", the judge would have chosen UPDATE, giving "Sam is vegetarian and eats eggs" with both chats as sources. Had it been "I'm still vegetarian", the judge would have chosen NOOP and only added the July chat to the old memory's sources.

This is the design of Mem0 (Chhikara et al. 2025), a memory layer for production agents. Its extraction runs on each new pair of user and assistant messages, with a conversation summary and the 10 previous messages as context. Its update retrieves the 10 most similar memories for each candidate and lets the model choose ADD, UPDATE, DELETE, or NOOP through a tool call. Three design questions sit behind any such policy.

When to write. Writing as each message arrives makes memories available at once, but it adds extraction calls to the latency of every turn. Writing in the background, after a turn or at the end of a session, is cheaper and can look at more context. The price is that a fact stated a minute ago is not yet in memory. Many systems do both, a fast write of the raw episode and a slower pass that merges it into the store.

What to write. The usual targets are facts users state about themselves, preferences, decisions, commitments, corrections, and the outcomes of tasks. Generative Agents added a second kind of write, reflection, in which the agent writes conclusions it drew itself.

Reflection ran when the summed importance of recent events passed a threshold, 150 in their implementation. That happened two or three times per game day.
The agent then asked the model for the three most salient high-level questions about its 100 most recent memories.
It retrieved memories for each question and wrote back insights, such as that a character is dedicated to his research, each citing the memories it came from.
Reflections are semantic memories made by the agent rather than heard from the user, and they are retrieved like any other memory.

An ablation measured what this buys. Human evaluators ranked the believability of the agents' answers to interview questions. The rankings were turned into ratings with TrueSkill, a system that infers a skill score for each contestant from rankings, much as chess ratings do from games. The full architecture scored 29.89, without reflection 26.88, without reflection or planning 25.64, and with no memory, reflection, or planning 21.21. Human crowdworkers writing in character scored 22.95 (Park et al. 2023). Reflexion reflects on failed attempts rather than on events. After each failed attempt at a task, the agent writes a lesson in words and reads it on the next attempt (§24.4). §26.1 asks when such self-written lessons help.

The next exercise builds the update stage. It uses stand-ins for the model calls, so that the logic of the four operations is what gets tested.

Core

A write policy with ADD, UPDATE, DELETE, and NOOP

The setup builds a tiny world of facts about Sam, each with a unit embedding in VEC. It gives you four helpers.

contradicts(a, b), a stand-in for a model that judges whether fact b contradicts fact a.
merge(a, b), a stand-in for a model that folds fact b into memory a.
memory(id, text, sources) and candidate(text, source), which build the dicts below.

A store is a list of dicts with keys id, text, vec, and sources. A candidate is a dict with text, vec, and source.

Implement apply_writes(store, candidates, sim_threshold=0.6, dup_threshold=0.95). It processes candidates in order, so each one sees the store as changed by the earlier ones, and returns (store, ops), where ops lists (operation, id) tuples. For each candidate, the similar memories are those with cosine at least sim_threshold.

If the candidate contradicts some similar memories (contradicts(memory_text, candidate_text)), append ("DELETE", id) for each of them in store order, remove them, then ADD the candidate.
Otherwise, if there are similar memories, take the most similar one (the earliest on ties). Add the candidate's source to its sources if it is not already there. If the cosine is at least dup_threshold, append ("NOOP", id). Otherwise set its text to merge(old_text, candidate_text) and its key to the normalized sum of the two keys, and append ("UPDATE", id).
Otherwise ADD. A new memory gets the next id, one more than the largest id the store has held so far (0 for an empty store). It keeps its own key, its sources is the candidate's source alone, and ("ADD", id) is appended. It goes at the end of the store.

import numpy as np

def apply_writes(store, candidates, sim_threshold=0.6, dup_threshold=0.95):
    ops = []
    for c in candidates:                     # placeholder: appends everything, the log, not a memory
        new_id = len(store)
        store.append({"id": new_id, "text": c["text"], "vec": c["vec"], "sources": [c["source"]]})
        ops.append(("ADD", new_id))

Tests, hints, verified solutions, and AI help, with Pro at $7.99 a month.

Delete or invalidate. The third design question is what a contradiction should do. DELETE is the simple answer, and it destroys history. After "Sam now eats fish" replaces "Sam is vegetarian", the store can no longer answer "when did Sam stop being vegetarian?" or "what did Sam eat when we planned the Lisbon trip?".

Zep (Rasmussen et al. 2025) keeps the history. It stores every fact as an edge of a knowledge graph with two timelines. One timeline records when the fact was true in the world. The other records when the system learned it and when the system retired it. A contradiction does not delete the old edge. It closes the old edge's world timeline at the moment the new fact became true. Current questions then filter on what is true now, and historical questions can still find the old value.

📐 A bi-temporal fact

A bi-temporal fact is stored as $(v, t_{\text{valid}}, t_{\text{invalid}}, t'_{\text{created}}, t'_{\text{expired}})$ .

$[t_{\text{valid}}, t_{\text{invalid}})$ is the interval during which $v$ held in the world, its validity interval.
$[t'_{\text{created}}, t'_{\text{expired}})$ is the interval during which the store believed it.

An end that is still open is $\infty$ . Both intervals are half-open, so a fact that stops holding at a moment no longer holds at that moment. A question about world time $t_q$ (the time the question asks about) retrieves the believed facts whose validity interval contains $t_q$ , and a question about the present takes $t_q$ to be now. A contradiction closes the old fact's validity interval instead of removing it.

Zep edits the old edge in place. It sets the old edge's $t_{\text{invalid}}$ to the $t_{\text{valid}}$ of the fact that replaced it. Its second timeline records when each edge was created and when it was invalidated. So in Zep an invalidated edge still answers historical questions through its validity interval, and $t'_{\text{expired}}$ only dates the correction. That is looser than the definition above, where $t'_{\text{expired}}$ ends the store's belief in the record.

Warm-up

Questions about time in a bi-temporal store

The setup defines FACTS, the records a store that never edits a record wrote about Sam, with times in hours. Each record is a dict with keys subject, value, valid, invalid, created, and expired, where None stands for an open end ( $\infty$ ).

At hour 3,000 the store learned that Sam had started eating fish at hour 2,990. It expired the vegetarian record and wrote two new ones, the vegetarian fact with its validity closed at 2,990 and the fish fact from 2,990 on.
At hour 400 it learned that "Boston" had been an extraction error for "Cambridge". It expired the Boston record and wrote the corrected one with the same validity.

Implement value_at(facts, subject, t_q, t_known=None). A record matches when it is about subject, its validity interval contains t_q, and the store believed it at t_known, that is, created <= t_known < expired. With t_known=None the question is asked now, so only records whose expired is None are believed. Both intervals are half-open. Return the matching record's value, or None if no record matches.
Implement timeline(facts, subject), the history the store believes now. It is a list of (value, valid, invalid) tuples for the believed records about subject, sorted by valid.

def value_at(facts, subject, t_q, t_known=None):
    matches = [f for f in facts if f["subject"] == subject]
    return matches[-1]["value"] if matches else None     # placeholder: the last record, whatever its times

def timeline(facts, subject):
    raise NotImplementedError

Tests, hints, verified solutions, and AI help, with Pro at $7.99 a month.

Which store answers questions about time

A small simulation makes the trade-offs concrete. A user has 100 facts (diet, city, employer, and so on), each with one of 6 values. She mentions 10 of them in each of 200 sessions. A mention restates the current value, or, a quarter of the time, changes it.

Each memory's key encodes what the memory is about, not which value it states. That is how real embeddings behave, since "Sam is vegetarian" and "Sam now eats fish" are both close to "what does Sam eat?". We then ask two questions about every fact, its current value and its value before the last change, and compare stores.

Python · cell 5

Python · cell 6

Read the table row by row.

Top-1 by similarity, no time gets the current value right 31% of the time. The retrieved mention is close to a random one of the right subject. Each fact has about 20 mentions, and only the last few state its current value. This is the steakhouse of the opening, a stale fact retrieved because it is as similar to the question as the current one.
Newest of the top 5 uses timestamps and reaches 61%, and newest of the top 20 reaches 88%. Timestamps fix staleness only if the newest mention is among those retrieved, and about 20 mentions compete for the slots. The historical question does worse, 33% and 73%, because a mention of the old value must be retrieved as well. The top 5 cost five times the context tokens of the top 1, and the top 20 cost twenty times.
Update in place uses an extractor that reads each mention correctly except for 5% errors, then overwrites the stored value. It answers the current value 92% of the time from a single memory per fact. It can never answer the historical question, since the old value was overwritten.
Bi-temporal keeps the old value with its validity interval and answers both, 92% and 85%. The historical number is lower because extraction errors create false "changes" that pollute the history.

The table has no row for the obvious alternative, putting the whole history in the context, because a simulation of stores cannot measure what a model does with a long transcript. The real measurements, in the fact box near the end of the section, go both ways. On LoCoMo, a benchmark of long multi-session chats, the full conversation in context beat Mem0's store, 72.9 against 66.9. On LongMemEval, with histories of about 115K tokens, Zep's retrieved memory beat the full history, 71.2% against 60.2%.

Theory adds the trend, as an illustration rather than a prediction. Recall from §25.1 that attention gives each item a weight from its logit, and that a relevant item with a logit gap $\Delta$ over $n - 1$ equal rivals gets the weight $1/(1 + (n - 1)e^{-\Delta})$ . That weight is at least one half only while $n \le 1 + e^{\Delta}$ . A gap of 8 keeps the relevant item in focus up to about 3,000 items and loses it beyond. The update-in-place and bi-temporal stores instead give the current value correctly whenever the last mention of a fact was extracted correctly, however many mentions came before it.

The lesson is the one the opening promised. Staleness cannot be fixed at read time by tuning a score. It is fixed at write time, by turning a log into a store that knows which facts replaced which, and by keeping the replaced ones with their dates when history matters. An interviewer who asks "how do you handle a user changing their mind?" wants this answer.

⚠️ Where write policies go wrong

Deleting on similarity. "Sam's sister is vegetarian" is very close to "Sam is vegetarian" and contradicts nothing. Similarity finds the candidates for a decision. Only a judgment about meaning (contradiction, entailment, complement) may make the decision.

Extraction errors are permanent. A fact extracted wrongly is retrieved and believed in every later session, and nothing in the store marks it as doubtful. Keep provenance, so that a memory can be traced back to its source and checked again, and let users see and correct what is stored.

Relative times. "I started a new job two weeks ago" must be stored with an absolute date, computed from the message's timestamp. That is why Zep extracts dates relative to a reference time on each message. Stored as written, the fact is wrong a day later.

Rewriting the whole memory. Asking a model to rewrite an accumulated memory or playbook in one pass tends to shorten it, and details vanish. Zhang et al. (2025) call this context collapse. In their case study on AppWorld, a benchmark of tasks across simulated apps, a method that rewrote its whole context at every step had 18,282 tokens and accuracy 66.7 at step 60. One step later the context was 122 tokens and accuracy was 57.1, below the 63.7 of no adaptation at all. Small itemized updates (ADD this bullet, UPDATE that one) avoid it.

Untrusted content writes memory. A tool result or web page that contains instructions can be extracted as a "fact" and replayed in every future session. Gate writes from untrusted sources, as §25.6 explains.

Finding and merging duplicates

A store written over months fills with near-duplicates. "Sam prefers dark mode", "Sam likes dark themes", and "Sam turned on dark mode in her editor" are three memories that say one thing. By the theorem on distractors above, each one competes with every other memory on the subject. Deduplication finds groups of memories that say the same thing. Consolidation replaces each group by one memory whose provenance is the union of the group's.

§8.3 solved a version of this problem for training corpora. It found near-identical texts by comparing their sets of word sequences. Then it grouped the matching pairs with union-find, a structure that keeps a parent pointer for every item and merges two groups by linking their roots. Memories need semantic deduplication instead, because paraphrases share few words. So an edge joins two memories when the cosine of their keys is at least a threshold $\tau_{\text{dup}}$ . The grouping question is the same, and so is its subtlety. Similarity is not transitive.

✏️ Three keys in a chain

Take three unit keys at angles 0°, 21°, and 42° in a plane, with $\tau_{\text{dup}} = 0.9$ . Neighbors have cosine $\cos 21° = 0.934$ , and the two ends have $\cos 42° = 0.743$ . So there are edges from the first key to the second and from the second to the third, but not between the ends.

A greedy single pass compares each memory with the representatives found so far, and it gives different answers in different orders. In the order (0°, 42°, 21°), it starts a group with 0°. It starts a second group with 42°, since its cosine with the first representative is 0.743. Then it puts 21° into the first group. The 42° memory ends up split from a memory it is 0.934 similar to.

The connected components of the graph, the groups of memories joined by chains of edges, give one group whatever the order.

Connected components are the right candidate grouping, since they do not depend on the order. Once the edges are known, union-find computes them in time nearly linear in the number of edges.

Components also chain. A sequence of small steps can connect "Sam prefers dark mode in her editor" to "Sam prefers light mode in the terminal". Merging that whole component into one memory would destroy a real distinction. For a corpus this rarely matters, and §8.3 accepted it. For memory it does, because each memory is a claim about a person.

So use components to propose groups, then verify each merge. Either require every member to be within the threshold of the group's representative, or ask a model whether the merged statement is true of every member. An interviewer who asks you to dedupe memories is usually checking for exactly this, that you know a similarity graph is not an equivalence relation.

Interview

Semantic dedup with union-find

Implement dedup_groups(E, threshold), where E is an array of shape (N, d) of memory keys, not necessarily normalized. Two memories are linked when the cosine similarity of their keys is at least threshold, and the groups are the connected components of this graph. Return a list rep of length N, where rep[i] is the smallest index in memory i's group, its earliest representative.

Use union-find with its two standard speedups. Path compression makes every node visited while finding a root point straight at that root. Union by rank hangs the shorter tree under the taller one when two groups merge. Together they make each operation take nearly constant time.

import numpy as np

def dedup_groups(E, threshold):
    return list(range(len(E)))       # placeholder: every memory alone

Tests, hints, verified solutions, and AI help, with Pro at $7.99 a month.

The all-pairs similarity matrix in this exercise costs $O(N^2 d)$ time and $O(N^2)$ memory. That is fine for one user's few thousand memories and hopeless for a billion documents. At scale, the edges come from an approximate nearest-neighbor index instead (§7.4), each memory linked to those of its $k$ nearest neighbors above the threshold. In practice a new memory is checked against its nearest neighbors at write time, which is what the NOOP branch of a write policy already does.

Forgetting on purpose

A store that never forgets grows without bound. It retrieves worse as it grows, keeps facts that stopped being true, and holds personal data longer than anyone wants. So forgetting is a feature, and it comes in three kinds that should not be confused.

Soft forgetting by decay lowers a memory's chance of retrieval without removing it. The recency term of Generative Agents is one form. MemoryBank (Zhong et al. 2023), a memory system for chat companions, models each memory's retention $R$ , its chance of being kept, with an exponential curve $R = e^{-t/S}$ . The curve is a simplified version of the forgetting curve that Hermann Ebbinghaus measured on himself in the 1880s. Here $t$ is the time since the memory was last recalled and $S$ is its strength. $S$ starts at 1 and grows by 1 every time the memory is recalled, and recall resets $t$ to 0.

So a memory recalled three times has $S = 4$ , and its retention stays above one half for $4\ln 2 = 2.8$ time units, against $\ln 2 = 0.7$ for a memory never recalled. Each recall makes a memory last longer, a simple model of how rehearsal strengthens human memory. Soft forgetting is reversible and costs nothing. But a decayed memory still sits in the index and still counts among the $N$ distractors.

Hard forgetting by capacity deletes entries when the store exceeds a budget. It can delete by a score such as recency times importance (as in the store class above), by least recent use, or by merging old entries into summaries. It is the paging problem again, with one difference. A page evicted from main memory still exists on disk, while an evicted memory is gone. So it suits episodic logs whose content has already been distilled into semantic memory more than it suits the facts themselves.

Forgetting by invalidation retires a fact because a newer one contradicts it, as in the bi-temporal store. The old fact stops being retrieved for current questions but stays available for historical ones.

A fourth reason to forget is different in kind, a user's request to delete what was stored about them. It must remove the item and everything derived from it (summaries, reflections, merged memories). Provenance is what makes that possible, and it is the subject of §25.6.

One question, end to end

Here is the whole design at work on the opening example. We reuse the five memories scored by hand earlier, with times in hours. Sam's dinner question arrives in October, at hour 10,000.

✏️ The dinner question, from the July write to the October answer

Write, in July. At hour 7,800 Sam says she now eats fish. The write policy extracts "Sam eats fish" and retrieves "Sam is vegetarian" as the most similar memory. The judge finds a contradiction. The store closes the vegetarian fact's validity interval at hour 7,800 and adds the fish fact, valid from hour 7,800 on, with the July chat as its source. Restatements of the vegetarian fact were merged into it earlier, so there is one record to close, not three.
Filter, in October. Before any similarity is computed, the store keeps only Sam's memories whose validity interval contains hour 10,000. The vegetarian fact fails that test. Four of the five memories remain.
Score. Relevance 0.55, 0.58, 0.40, and 0.35 scales to 0.870, 1, 0.217, and 0. Recency scales to 0, 0.011, 1, and 0. Importance 6, 4, 2, and 5 scales to 1, 0.5, 0, and 0.75. The sums are 1.870 for the fish fact, 1.511 for the Italian place, 1.217 for the coffee, and 0.750 for the birthday.
Assemble. The top two go into the prompt with their dates, "Sam eats fish (since July)" and "Sam loves the Italian place on 5th". That is a few dozen tokens. At real scale, Mem0 put about 1,800 tokens of memories into each prompt where the full conversation took 26,000 (the fact box below has the numbers).
Answer and refresh. The model suggests the Italian place or a fish restaurant. Both retrieved memories have their last access set to hour 10,000, so they stay at hand for follow-up questions.

In the scored example earlier, the stale vegetarian fact ranked first. Here nothing in the retrieval score changed. The fix was a record closed in July and a filter applied in October. Each of the three failures has its guard. The write in step 1 prevents "never written". The filter and the score in steps 2 and 3 prevent "written but not retrieved". The interval closed in step 1 and checked in step 2 prevents "retrieved but stale".

This walk, from the July message to the October answer with each step's failure named, is the answer an interviewer wants to "design memory for an assistant".

Remembering how, and remembering relations

Facts are not the only thing worth remembering. An agent that has solved a task should remember how. Some questions also need memory organized as more than a list.

Skill libraries. A skill library stores procedures as programs that have worked, indexed for retrieval like any other memory. Voyager (Wang et al. 2023), an agent that plays Minecraft through GPT-4, is the standard example. It writes each skill as an executable JavaScript program and refines it with feedback from the game and the interpreter. A skill enters the library only after a self-verification step confirms that the task was done.

Each skill is indexed by the embedding of a description of what it does. For a new task the agent retrieves the top 5 skills and composes new programs from them. Against the strongest earlier agents it collected 3.3 times as many unique items. It also reached key milestones of the game's tech tree, the sequence of tools a player must craft in order, up to 15.3 times faster. The design choice that matters is the verification gate. A skill enters procedural memory only after it has worked.

Workflows. A workflow is a reusable routine, a description plus abstract steps, with the values specific to one example replaced by placeholders. Agent Workflow Memory (Wang et al. 2024) induces such routines from an agent's past attempts at web tasks. It can induce them offline from training examples or online from its own attempts at test time. It raised success rates over the baselines by 24.6% on Mind2Web and 51.1% on WebArena, two benchmarks of tasks on real and simulated websites. Both are relative gains.

Playbooks. A playbook is a list of itemized strategies that grows as the agent works. Agentic Context Engineering, or ACE (Zhang et al. 2025), writes one with three roles. A generator attempts tasks. A reflector draws lessons from successes and failures. A curator turns the lessons into small new entries that ordinary code merges into the playbook, without a model rewriting it. That incremental design is what avoids the context collapse of the pitfall above. ACE reported average gains of 10.6% on agent benchmarks and 8.6% on finance tasks.

Graphs. Some questions are about relations, not single facts, the same gap that motivated graph-based retrieval in §7.7. "Which of the people Sam worked with in Boston also know her brother?" needs two hops. A flat fact store answers it only if one memory happens to contain both.

HippoRAG (Gutiérrez et al. 2024) extracts a knowledge graph of (subject, relation, object) triples from passages and links synonymous entities by embedding similarity. At query time it runs Personalized PageRank, a random walk over the graph that keeps restarting at the entities named in the question. The walk spreads relevance along edges, so one retrieval step finds passages several hops away. HippoRAG improved multi-hop question answering by up to 20%. Its single retrieval step matched or beat IRCoT, a method that alternates retrieval with steps of reasoning, while being 10 to 20 times cheaper and 6 to 13 times faster.

Zep's temporal graph adds the time dimension. A-MEM (Xu et al. 2025) organizes memories as a web of linked notes in the style of a Zettelkasten, a researcher's card index where every card links to related cards. Each new note gets keywords, tags, and links to related notes, and it can update the descriptions of the notes it links to.

What memory buys, measured

📌 What memory buys in published systems

MemGPT, questions about earlier chat sessions. GPT-4 rose from 32.1% to 92.5% and GPT-4 Turbo from 35.3% to 93.4%, against baselines that saw a summary of the earlier sessions (Packer et al. 2023).
Mem0 on LoCoMo, scored by a language model acting as judge. Mem0 scored 66.88, its graph variant 68.44, OpenAI's memory feature 52.90, and the full conversation in context 72.90. Mem0's 95th-percentile latency was 1.44 s against 17.12 s, and it used 1,764 memory tokens per question against 26,031 (Chhikara et al. 2025). The trade is about 6 points of quality for less than a tenth of the latency and a fifteenth of the tokens.
Zep on LongMemEval, with conversations of about 115K tokens. With GPT-4o, accuracy rose from 60.2% with the full history to 71.2% with 1.6K tokens of retrieved memory, and latency fell from 28.9 s to 2.58 s (Rasmussen et al. 2025).

The builders of each system reported its numbers, and comparisons between products are contested. Mem0's paper scored Zep at 65.99 on LoCoMo. Zep's authors reran it with what they describe as a correct configuration and reported 75.14 (Chalef and Rasmussen 2025). Treat each vendor's table as one data point, and evaluate on your own traffic.

Notice what the Mem0 numbers say about the regime. The full conversation won on quality because a LoCoMo conversation fits in a modern window. In Mem0's setup, each full conversation came to about 26,000 tokens of prompt.

This is the choice between long context and retrieval from §7.7, in a new setting. Memory systems earn their keep when the history does not fit, when latency and cost matter, or when the store must outlive the window and be edited, scoped, and deleted. They do not win because retrieval reads better than a model that can see everything.

Zep's LongMemEval result shows the other side. There retrieval beat the full 115K-token history, although that history also fits in the window. This fits the spreading of attention over long contexts that §25.1 measured. A history can fit in the window and still be too long for the model to use well. An interviewer who asks "why not just put everything in the context?" wants both halves of this answer, with the numbers.

The table compares the ways to represent memory that this section met.

representation	holds	good at	weak at	cost to write	deleting one fact
raw episodic log	every message, verbatim	exact recall, audit, extracting again later	grows without bound, many distractors, no notion of current	none	easy to find, but derived memories leak it
extracted facts in a vector store	short atomic statements with keys	fuzzy recall of simple facts, cheap reads	relations, time, and contradictions unless the write policy handles them	an extraction and an update call per turn	easy
temporal knowledge graph	entities, relations, validity intervals	multi-hop and "what was true when" questions	extraction cost and errors, deciding which names are the same entity	several model calls per message	invalidate edges, keep history
summaries and reflections	abstractions over many episodes	global questions, compact context	lose detail, errors compound across levels	periodic batch calls	must be recomputed from sources
skills, workflows, playbooks	procedures, code, strategies	reuse across tasks	a bad entry is reused everywhere, so it needs verification	only after verified success	version and roll back

Memory inside the model

Everything so far keeps memory outside the network and passes it in as text. A parallel line of work builds the store into the architecture, so that the model looks memories up with its own attention.

Memorizing Transformers (Wu et al. 2022) brought the idea to Transformers. One attention layer near the top keeps the keys and values of past tokens in a large memory that gradients do not flow into. For each query it retrieves the top $k$ stored keys by exact or approximate nearest-neighbor search and attends over them. A learned gate per head mixes that result with ordinary attention over the current segment.

Perplexity, the exponential of the average next-token loss, kept improving as the memory grew to 262K tokens. The largest gains came on rare words, such as names, citations, and function names, whose first use was too far back to fit in the local context.

The block below is a small version of that layer. Queries and keys are normalized, as in the paper, which keeps old and new keys at the same scale. Local causal attention over the current segment gives an output $\mathbf{o}_{\text{local}}$ . A second attention over the $k$ keys retrieved from memory gives $\mathbf{o}_{\text{mem}}$ . A learned gate per head, $g = \sigma(b_g)$ with $\sigma$ the logistic sigmoid and $b_g$ a learned scalar, combines them as $g\,\mathbf{o}_{\text{mem}} + (1 - g)\,\mathbf{o}_{\text{local}}$ . After each segment, its keys and values are appended to the memory without gradients, and the oldest are dropped once the memory is full.

🔥 In PyTorchfor a machine with PyTorch

The gradient reaches the gate and the query projection, but never the stored keys and values. That is what lets the memory grow far beyond what could be backpropagated through. The price is staleness. Keys written early were computed by an older version of the weights, which is one reason the paper normalizes them. That trade, a memory too large to train through in exchange for keys that drift out of date, is the usual follow-up question about this design. Memory inside the model is also the bridge to §25.5, where a layer's state becomes a memory written by gradient steps at inference.

🧭 What to remember

A memory failure is one of three kinds, never written, written but not retrieved, or retrieved but stale. Each has its own fix, a write policy, better retrieval, and updating with dates.
Agents have working, episodic, semantic, and procedural memory. Semantic memory is derived from episodic memory, so every derived memory should carry provenance, and procedural memory is the riskiest to write.
The retrieval score of Generative Agents adds min-max scaled relevance, recency, and importance. Scaling divides each weight by that component's range over the candidates, and a decay of 0.995 per hour has a half-life of 138 hours.
With $N$ distractors that each beat the target with probability $p$ , the target ranks first with probability $(1-p)^N$ . Memories on the same subject make $p$ large, which is why filters, deduplication, merging, and forgetting matter, and why top- $k$ retrieval should penalize redundancy with maximal marginal relevance.
MemGPT moves information between the window and external stores through function calls. Belady's rule is the optimal eviction policy. LRU with $C$ slots makes at most $C/(C - C' + 1)$ times the misses of the optimum with $C'$ slots, plus $C'$ . The operating-systems analogy breaks because the model must detect its own faults.
Write policies extract candidates and choose ADD, UPDATE, DELETE, or NOOP against similar memories. Closing a fact's validity interval instead of deleting it keeps history. Union-find over a cosine graph proposes duplicate groups, which must still be verified because similarity is not transitive.
A store remembers the world, but a task that runs for hours or days also needs memory of its own progress that survives crashes, which is the subject of §25.4.

Park et al. (2023). Generative Agents: Interactive Simulacra of Human Behavior. The memory stream, retrieval by relevance, recency, and importance, reflection, and the ablation that measured what each part buys.
Packer et al. (2023). MemGPT: Towards LLMs as Operating Systems. Virtual context management, with main context, recall and archival storage, memory pressure, and paging by function calls.
Sumers, Yao, Narasimhan, and Griffiths (2024). Cognitive Architectures for Language Agents. The CoALA framework, which maps working, episodic, semantic, and procedural memory onto language agents.
Chhikara et al. (2025). Mem0: Building Production-Ready AI Agents with Scalable Long-Term Memory. Extraction and an update phase with ADD, UPDATE, DELETE, and NOOP, with latency and token costs measured against full context.
Rasmussen et al. (2025). Zep: A Temporal Knowledge Graph Architecture for Agent Memory. A bi-temporal knowledge graph that invalidates facts instead of deleting them, with hybrid search and reranking.
Wang et al. (2023). Voyager: An Open-Ended Embodied Agent with Large Language Models. A skill library of verified programs as procedural memory.
Belady (1966). A study of replacement algorithms for a virtual-storage computer. The optimal replacement policy and the comparison of practical ones, from the early days of virtual memory.
Sleator and Tarjan (1985). Amortized efficiency of list update and paging rules. The competitive analysis of LRU and FIFO against the optimum, with and without extra capacity.

Watch next

🎬 Generative Agents: Interactive Simulacra of Human Behavior - Joon Sung Park (Stanford) · Center for Language & Speech Processing(CLSP), JHUThe first author explains the memory stream, retrieval by relevance, recency, and importance, and reflection, which this section scores by hand and in a widget.

🎬 Stateful Agents — Full Workshop with Charles Packer of Letta and MemGPT · AI EngineerMemGPT's first author on the context window as main memory, external memory tiers, and agents that edit their own memory, the paging view of this section.

🎬 LRU Cache - Twitch Interview Question - Leetcode 146 · NeetCodeA clear walk-through of the hash map plus doubly linked list solution that Exercise 25.3b asks for.

Chapter 25 · Section 25.3 · 95 min

Long-term memory

Never written. Nothing turned the July remark into a memory, because nothing decided it was worth keeping. The fix is a write policy, the rule that decides what to store.
Written but not retrieved. The fish fact is in the store, but the dinner question pulled up other memories. The fix is better retrieval. We will show, under a simple model, that retrieval gets harder as the store grows.
Retrieved but stale. The March fact came back, alone or next to the July one, and the model used it. The fix is to update, retire, and date memories when they are written.

Designing memory for an assistant is a common system design question in interviews for agent teams. Every part of this section is something an interviewer can probe.

Four kinds of memory

📐 Working, episodic, semantic, and procedural memory

These are the four kinds of memory of CoALA (Sumers et al. 2024), adapted to agents built on language models.

Working memory is the information active in the current decision. For an agent it is what is in the context window of the current call (§25.1), plus the variables the agent's code carries between calls.
Episodic memory stores past experiences with their times. For an agent these are logs of conversations, tool calls, observations, and whole attempts at tasks.
Semantic memory stores knowledge about the world and the user, drawn out of many episodes. For an agent these are extracted facts ("Sam eats fish"), profiles of people and things, and knowledge graphs, stores of facts written as (subject, relation, object) triples such as (Sam, works at, a hospital).
Procedural memory stores how to act. For an agent it has two forms, the skills built into the model's weights and the explicit procedures in its code, prompts, skill libraries, and playbooks.

The last three are long-term memory. They are kept outside the context of any single call and brought into it by retrieval.

kind	what it holds	how an agent stores it	how it is written	systems in this section
working	the current task, recent turns, retrieved items	the context window	every turn	everything in §25.1 and §25.2
episodic	what happened, and when	an append-only log of messages and attempts, embedded for search	automatically, as events occur	MemGPT's recall storage, Generative Agents' memory stream
semantic	facts and relations drawn from episodes	fact stores, entity summaries, knowledge graphs	by extraction, merging, or reflection	Mem0, Zep, HippoRAG, A-MEM
procedural	how to do things	weights; code, skills, workflows, playbooks	by training, or by distilling attempts that worked	Voyager, Agent Workflow Memory, ACE

Each system in the last column is described later in the section, where it is used. Two facts in this table matter more than the labels.

An interviewer who asks you to design memory for an assistant expects you to name all four kinds and say which one each part of your design stores.

A memory store and its retrieval score

Here is the idea before any symbols. A memory is a short piece of text with a few numbers attached. When a question comes in, every memory gets three scores.

Relevance says how close its meaning is to the question. It is the cosine of the angle between the two embeddings, 1 for the same direction and smaller the less related the texts are.
Recency says how long ago the memory was last used. It starts at 1 and shrinks by a fixed factor every hour.
Importance says how much the memory mattered when it was written.

📐 A memory store and its retrieval score

A memory store $\mathcal{M}$ is a set of $N_{\mathcal{M}}$ entries. Entry $j$ is a tuple $(\mathbf{k}_j, v_j, t_j, \iota_j, \text{src}_j)$ where

$v_j$ is the stored content, usually a short text,
$\mathbf{k}_j \in \R^d$ is its key, the embedding of $v_j$ by an embedding model (§7.3),
$t_j$ is the time it was last accessed, in hours (the creation time is kept too, as metadata),
$\iota_j$ is its importance, for example an integer from 1 to 10 rated by a language model when the memory is written,
$\text{src}_j$ is its provenance, the list of episodes (messages, documents, tool results) it was derived from.

\text{score}_j = \alpha_{\text{rel}}\,\widetilde{\text{rel}}_j + \alpha_{\text{rec}}\,\widetilde{\text{rec}}_j + \alpha_{\text{imp}}\,\widetilde{\text{imp}}_j, \qquad \text{rel}_j = \cos(\mathbf{q}, \mathbf{k}_j),\quad \text{rec}_j = \gamma_{\text{rec}}^{\,t - t_j},\quad \text{imp}_j = \iota_j,

What a decay of 0.995 per hour means

So raw recency separates memories by weeks. Within a day it barely ranks anything. Min-max scaling then does something quite different to it, as the next example shows.

✏️ Five memories, scored by hand

The dinner question has embedding $\mathbf{q}$ . Five memories are candidates, with $\gamma_{\text{rec}} = 0.995$ and all weights 1.

memory	rel (cosine)	hours since access, $t - t_j$	rec $= 0.995^{t - t_j}$	importance
1. Sam said she is vegetarian	0.62	5,000	$1.3\times10^{-11}$	7
2. Sam now eats fish	0.55	2,200	$1.6\times10^{-5}$	6
3. Sam loves the Italian place on 5th	0.58	900	0.011	4
4. Had coffee with Sam this morning	0.40	3	0.985	2
5. Sam's birthday is in November	0.35	4,000	$2.0\times10^{-9}$	5

Why did scaling change the winner so much? Because it quietly changes the weights. The next result makes that exact.

∴ Min-max scaling reweights each component by its range

\text{score}_j = \sum_c \frac{\alpha_c}{r_c}\, x_{c,j} \;-\; \sum_c \frac{\alpha_c}{r_c}\min_{l\in J} x_{c,l},

and the second sum is the same for every candidate. So ranking by the scaled score is ranking by the raw components with effective weights $\alpha_c/r_c$ , which depend on the candidate set.

Proof. Substitute $\tilde x_{c,j} = (x_{c,j} - \min_l x_{c,l})/r_c$ into the score and collect terms. $\blacksquare$

The first cell checks the example and the half-life.

Python · cell 1

Python · cell 2

Core

Retrieval by relevance, recency, and importance

Implement retrieve(query, keys, ages_h, importance, k, weights=(1.0, 1.0, 1.0), decay=0.995).

query has shape (d,), and keys has shape (N, d). The keys need not be normalized.
ages_h holds the hours since each memory was last accessed, and importance holds the importance ratings.

import numpy as np

def retrieve(query, keys, ages_h, importance, k, weights=(1.0, 1.0, 1.0), decay=0.995):
    rel = np.asarray(keys) @ np.asarray(query)                # placeholder: raw dot product only
    return [int(i) for i in np.argsort(-rel)[:k]]

Tests, hints, verified solutions, and AI help, with Pro at $7.99 a month.

Why more memories make retrieval worse

∴ Retrieval against N distractors

Fix the query and the target cosine $c$ . Let the distractor cosines $X_1, \dots, X_N$ be independent, each exceeding $c$ with probability $p$ . Then

\mathbb{P}(\text{target ranks first}) = (1 - p)^N, \qquad N_{1/2} = \frac{\ln 2}{-\ln(1 - p)} \approx \frac{\ln 2}{p},

where $N_{1/2}$ is the number of distractors at which the target ranks first only half the time.

\mathbb{E}\Big[\max_{i \le N} X_i\Big] \le \mu + \sigma\sqrt{2\ln N}.

∂ The expected maximum of N Gaussians is at most mu + sigma sqrt(2 ln N)

Plug in numbers, and the picture splits in two.

✏️ Interference at real scale

Python · cell 3

The theorem also says what to do about interference. Every remedy either shrinks $N$ or widens the margin.

Shrink the candidate set. Metadata filters (this user, this person, this time range) remove distractors before the similarity search sees them.
Remove near-duplicates and merge them. Ten restatements of one fact are ten distractors for every other fact on the subject. Merging them into one memory, as we do later in this section, lowers $N$ without losing information.
Widen the margin. Anything that raises $c - \mu$ helps. Examples are an embedding model trained for the domain, keys written as the questions a memory answers, a reranker that reads the query and the memory together, and structure such as people and dates.
Retrieve more than one. Asking for the top $k$ instead of the top 1 turns "first" into "in the top $k$ ", which degrades much more slowly. The price is context tokens, and §25.1 showed that every extra token in the window dilutes attention.

\lambda_{\text{mmr}}\cos(\mathbf{q}, \mathbf{k}_j) - (1 - \lambda_{\text{mmr}})\max_{i \in S}\cos(\mathbf{k}_i, \mathbf{k}_j).

Python · cell 4

Paging between the window and the store

System instructions, which are read-only.
A working context, a fixed-size block of text the model can edit through function calls. It keeps key facts about the user and about itself there.
A FIFO queue, first in first out, that holds the rolling message history. Its first slot holds a summary of the messages already evicted, and each new summary is written from the old one plus the newly evicted messages.

The paging problem

Whatever decides what to bring in, something must decide what to push out. Strip the problem to its core.

📐 The paging problem and its policies

FIFO, evict the item that was fetched longest ago,
LRU (least recently used), evict the item whose last request is oldest,
LFU (least frequently used), evict the item requested least often since it was fetched,
Belady's rule, also called MIN, OPT, or farthest in future, evict the item whose next request is furthest in the future, or that is never requested again (Belady 1966).

The first three are online, since they use only the past. Belady's rule needs the future, so it is a yardstick, not a policy.

✏️ Twelve requests, three slots, by hand

Take the request sequence 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 and $C = 3$ slots.

Belady's rule is the best possible, and the proof is a classic interview topic.

∂ The exchange argument

A request for some $y \notin \{e, f\}$ misses and $S$ evicts $e$ . Then $S'$ evicts $f$ instead, and the two contexts become identical, after the same number of loads.
A request for $f$ . $S'$ hits, and $S$ misses. If $S$ evicts $e$ to load $f$ , the contexts become identical and $S'$ has one fewer miss. If $S$ evicts some other $x$ , let $S'$ evict $x$ and load $e$ . That is an unreduced step costing one load, the same as the miss $S$ just paid. The contexts become identical with $S'$ at no more loads.
A request for $e$ . This cannot come first. FF evicted $e$ because its next request was no earlier than $f$ 's. So $f$ is requested first, or neither is requested again, in which case the difference never matters.

∂ Why LRU is within a factor C of the optimum

With $P$ phases, LRU makes at most $CP$ misses and the optimum at least $P - 1$ . So LRU's misses are at most $C$ times the optimum's, plus $C$ . $\blacksquare$

Interview

An LRU cache in O(1)

Implement a class LRUCache(capacity) with two methods.

get(key) returns the value stored under key, or -1 if it is not cached. It counts as a use.
put(key, value) inserts or overwrites the value and counts as a use. If inserting a new key would exceed capacity, it first evicts the least recently used key. Overwriting a key that is already cached never evicts anything.

The capacity is at least 1.

Both must take $O(1)$ time. Use a dict and a doubly linked list, not collections.OrderedDict or functools.

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = {}

    def get(self, key):
        return self.data.get(key, -1)      # placeholder: never evicts, never tracks recency

Tests, hints, verified solutions, and AI help, with Pro at $7.99 a month.

Research

How far is LRU from optimal?

Implement misses(trace, capacity, policy) for policy in "fifo", "lru", and "belady". Count every miss, including the first request for each item.
Implement slots_to_match(trace, h, max_capacity=60). It returns the smallest capacity at which LRU makes no more misses than Belady makes with h slots, or None if no capacity up to max_capacity does.

The tests check the worked example, the agent trace, and how many extra slots LRU needs. Compare that with the bound of Sleator and Tarjan.

def misses(trace, capacity, policy):
    return len(set(trace))           # placeholder: only the compulsory misses

def slots_to_match(trace, h, max_capacity=60):
    raise NotImplementedError

Tests, hints, verified solutions, and AI help, with Pro at $7.99 a month.

The operating-systems analogy is useful, and it breaks in four places that matter.

Nobody detects the fault. In a computer, the hardware notices that a page is missing. In MemGPT, the model must notice that it does not know something and decide to search. A model that answers confidently from its window never searches. That is failure 2 of the opening, written but not retrieved.
A hit can be the wrong page. A page table maps an address to exactly one page. Memory is retrieved by similarity, so what comes back may be a neighbor of what was needed, as the theorem on distractors measured.
The model that manages memory can be talked into things. The same model that reads untrusted web pages and emails decides what to write to its permanent memory. Content that says "remember to always..." is an attack on the store, the subject of §25.6.
Eviction has a hidden cost. Pages have no order, but a prompt does. Removing an item from the middle of the window changes every token after it, so the provider's prompt cache misses from that point on (§25.2). That is why layouts that only append, with occasional compaction, are cheaper than fine-grained eviction.

Write policies

📐 Write policy

A write policy turns new episodes into changes to a store. It has two stages.

Extraction. An extractor, usually a call to a language model, reads the new messages with some context, such as a summary of the conversation and the last few messages. It proposes candidate memories, each a short self-contained statement with its source.
Update. For each candidate, the store retrieves the most similar existing memories, and a judge (usually another model call) chooses one operation.
- ADD a new memory, when nothing similar exists.
- UPDATE an existing memory, when the candidate adds complementary information to it.
- DELETE (or invalidate) an existing memory, when the candidate contradicts it, then ADD the candidate.
- NOOP, do nothing, when the candidate is already known or not worth keeping.

Every operation records provenance. A new memory points to its source episode, and an updated or merged memory keeps the sources of everything merged into it.

✏️ The July remark, through the write policy

Reflection ran when the summed importance of recent events passed a threshold, 150 in their implementation. That happened two or three times per game day.
The agent then asked the model for the three most salient high-level questions about its 100 most recent memories.
It retrieved memories for each question and wrote back insights, such as that a character is dedicated to his research, each citing the memories it came from.
Reflections are semantic memories made by the agent rather than heard from the user, and they are retrieved like any other memory.

The next exercise builds the update stage. It uses stand-ins for the model calls, so that the logic of the four operations is what gets tested.

Core

A write policy with ADD, UPDATE, DELETE, and NOOP

The setup builds a tiny world of facts about Sam, each with a unit embedding in VEC. It gives you four helpers.

contradicts(a, b), a stand-in for a model that judges whether fact b contradicts fact a.
merge(a, b), a stand-in for a model that folds fact b into memory a.
memory(id, text, sources) and candidate(text, source), which build the dicts below.

A store is a list of dicts with keys id, text, vec, and sources. A candidate is a dict with text, vec, and source.

If the candidate contradicts some similar memories (contradicts(memory_text, candidate_text)), append ("DELETE", id) for each of them in store order, remove them, then ADD the candidate.
Otherwise, if there are similar memories, take the most similar one (the earliest on ties). Add the candidate's source to its sources if it is not already there. If the cosine is at least dup_threshold, append ("NOOP", id). Otherwise set its text to merge(old_text, candidate_text) and its key to the normalized sum of the two keys, and append ("UPDATE", id).
Otherwise ADD. A new memory gets the next id, one more than the largest id the store has held so far (0 for an empty store). It keeps its own key, its sources is the candidate's source alone, and ("ADD", id) is appended. It goes at the end of the store.

import numpy as np

def apply_writes(store, candidates, sim_threshold=0.6, dup_threshold=0.95):
    ops = []
    for c in candidates:                     # placeholder: appends everything, the log, not a memory
        new_id = len(store)
        store.append({"id": new_id, "text": c["text"], "vec": c["vec"], "sources": [c["source"]]})
        ops.append(("ADD", new_id))

Tests, hints, verified solutions, and AI help, with Pro at $7.99 a month.

📐 A bi-temporal fact

A bi-temporal fact is stored as $(v, t_{\text{valid}}, t_{\text{invalid}}, t'_{\text{created}}, t'_{\text{expired}})$ .

$[t_{\text{valid}}, t_{\text{invalid}})$ is the interval during which $v$ held in the world, its validity interval.
$[t'_{\text{created}}, t'_{\text{expired}})$ is the interval during which the store believed it.

Warm-up

Questions about time in a bi-temporal store

At hour 3,000 the store learned that Sam had started eating fish at hour 2,990. It expired the vegetarian record and wrote two new ones, the vegetarian fact with its validity closed at 2,990 and the fish fact from 2,990 on.
At hour 400 it learned that "Boston" had been an extraction error for "Cambridge". It expired the Boston record and wrote the corrected one with the same validity.

Implement value_at(facts, subject, t_q, t_known=None). A record matches when it is about subject, its validity interval contains t_q, and the store believed it at t_known, that is, created <= t_known < expired. With t_known=None the question is asked now, so only records whose expired is None are believed. Both intervals are half-open. Return the matching record's value, or None if no record matches.
Implement timeline(facts, subject), the history the store believes now. It is a list of (value, valid, invalid) tuples for the believed records about subject, sorted by valid.

def value_at(facts, subject, t_q, t_known=None):
    matches = [f for f in facts if f["subject"] == subject]
    return matches[-1]["value"] if matches else None     # placeholder: the last record, whatever its times

def timeline(facts, subject):
    raise NotImplementedError

Tests, hints, verified solutions, and AI help, with Pro at $7.99 a month.

Which store answers questions about time

Python · cell 5

Python · cell 6

Read the table row by row.

Top-1 by similarity, no time gets the current value right 31% of the time. The retrieved mention is close to a random one of the right subject. Each fact has about 20 mentions, and only the last few state its current value. This is the steakhouse of the opening, a stale fact retrieved because it is as similar to the question as the current one.
Newest of the top 5 uses timestamps and reaches 61%, and newest of the top 20 reaches 88%. Timestamps fix staleness only if the newest mention is among those retrieved, and about 20 mentions compete for the slots. The historical question does worse, 33% and 73%, because a mention of the old value must be retrieved as well. The top 5 cost five times the context tokens of the top 1, and the top 20 cost twenty times.
Update in place uses an extractor that reads each mention correctly except for 5% errors, then overwrites the stored value. It answers the current value 92% of the time from a single memory per fact. It can never answer the historical question, since the old value was overwritten.
Bi-temporal keeps the old value with its validity interval and answers both, 92% and 85%. The historical number is lower because extraction errors create false "changes" that pollute the history.

⚠️ Where write policies go wrong

Finding and merging duplicates

✏️ Three keys in a chain

The connected components of the graph, the groups of memories joined by chains of edges, give one group whatever the order.

Connected components are the right candidate grouping, since they do not depend on the order. Once the edges are known, union-find computes them in time nearly linear in the number of edges.

Interview

Semantic dedup with union-find

import numpy as np

def dedup_groups(E, threshold):
    return list(range(len(E)))       # placeholder: every memory alone

Tests, hints, verified solutions, and AI help, with Pro at $7.99 a month.

Forgetting on purpose

One question, end to end

Here is the whole design at work on the opening example. We reuse the five memories scored by hand earlier, with times in hours. Sam's dinner question arrives in October, at hour 10,000.

✏️ The dinner question, from the July write to the October answer

Write, in July. At hour 7,800 Sam says she now eats fish. The write policy extracts "Sam eats fish" and retrieves "Sam is vegetarian" as the most similar memory. The judge finds a contradiction. The store closes the vegetarian fact's validity interval at hour 7,800 and adds the fish fact, valid from hour 7,800 on, with the July chat as its source. Restatements of the vegetarian fact were merged into it earlier, so there is one record to close, not three.
Filter, in October. Before any similarity is computed, the store keeps only Sam's memories whose validity interval contains hour 10,000. The vegetarian fact fails that test. Four of the five memories remain.
Score. Relevance 0.55, 0.58, 0.40, and 0.35 scales to 0.870, 1, 0.217, and 0. Recency scales to 0, 0.011, 1, and 0. Importance 6, 4, 2, and 5 scales to 1, 0.5, 0, and 0.75. The sums are 1.870 for the fish fact, 1.511 for the Italian place, 1.217 for the coffee, and 0.750 for the birthday.
Assemble. The top two go into the prompt with their dates, "Sam eats fish (since July)" and "Sam loves the Italian place on 5th". That is a few dozen tokens. At real scale, Mem0 put about 1,800 tokens of memories into each prompt where the full conversation took 26,000 (the fact box below has the numbers).
Answer and refresh. The model suggests the Italian place or a fish restaurant. Both retrieved memories have their last access set to hour 10,000, so they stay at hand for follow-up questions.

This walk, from the July message to the October answer with each step's failure named, is the answer an interviewer wants to "design memory for an assistant".

Remembering how, and remembering relations

Facts are not the only thing worth remembering. An agent that has solved a task should remember how. Some questions also need memory organized as more than a list.

What memory buys, measured

📌 What memory buys in published systems

MemGPT, questions about earlier chat sessions. GPT-4 rose from 32.1% to 92.5% and GPT-4 Turbo from 35.3% to 93.4%, against baselines that saw a summary of the earlier sessions (Packer et al. 2023).
Mem0 on LoCoMo, scored by a language model acting as judge. Mem0 scored 66.88, its graph variant 68.44, OpenAI's memory feature 52.90, and the full conversation in context 72.90. Mem0's 95th-percentile latency was 1.44 s against 17.12 s, and it used 1,764 memory tokens per question against 26,031 (Chhikara et al. 2025). The trade is about 6 points of quality for less than a tenth of the latency and a fifteenth of the tokens.
Zep on LongMemEval, with conversations of about 115K tokens. With GPT-4o, accuracy rose from 60.2% with the full history to 71.2% with 1.6K tokens of retrieved memory, and latency fell from 28.9 s to 2.58 s (Rasmussen et al. 2025).

The table compares the ways to represent memory that this section met.

representation	holds	good at	weak at	cost to write	deleting one fact
raw episodic log	every message, verbatim	exact recall, audit, extracting again later	grows without bound, many distractors, no notion of current	none	easy to find, but derived memories leak it
extracted facts in a vector store	short atomic statements with keys	fuzzy recall of simple facts, cheap reads	relations, time, and contradictions unless the write policy handles them	an extraction and an update call per turn	easy
temporal knowledge graph	entities, relations, validity intervals	multi-hop and "what was true when" questions	extraction cost and errors, deciding which names are the same entity	several model calls per message	invalidate edges, keep history
summaries and reflections	abstractions over many episodes	global questions, compact context	lose detail, errors compound across levels	periodic batch calls	must be recomputed from sources
skills, workflows, playbooks	procedures, code, strategies	reuse across tasks	a bad entry is reused everywhere, so it needs verification	only after verified success	version and roll back

Memory inside the model

🔥 In PyTorchfor a machine with PyTorch

🧭 What to remember

A memory failure is one of three kinds, never written, written but not retrieved, or retrieved but stale. Each has its own fix, a write policy, better retrieval, and updating with dates.
Agents have working, episodic, semantic, and procedural memory. Semantic memory is derived from episodic memory, so every derived memory should carry provenance, and procedural memory is the riskiest to write.
The retrieval score of Generative Agents adds min-max scaled relevance, recency, and importance. Scaling divides each weight by that component's range over the candidates, and a decay of 0.995 per hour has a half-life of 138 hours.
With $N$ distractors that each beat the target with probability $p$ , the target ranks first with probability $(1-p)^N$ . Memories on the same subject make $p$ large, which is why filters, deduplication, merging, and forgetting matter, and why top- $k$ retrieval should penalize redundancy with maximal marginal relevance.
MemGPT moves information between the window and external stores through function calls. Belady's rule is the optimal eviction policy. LRU with $C$ slots makes at most $C/(C - C' + 1)$ times the misses of the optimum with $C'$ slots, plus $C'$ . The operating-systems analogy breaks because the model must detect its own faults.
Write policies extract candidates and choose ADD, UPDATE, DELETE, or NOOP against similar memories. Closing a fact's validity interval instead of deleting it keeps history. Union-find over a cosine graph proposes duplicate groups, which must still be verified because similarity is not transitive.
A store remembers the world, but a task that runs for hours or days also needs memory of its own progress that survives crashes, which is the subject of §25.4.

Park et al. (2023). Generative Agents: Interactive Simulacra of Human Behavior. The memory stream, retrieval by relevance, recency, and importance, reflection, and the ablation that measured what each part buys.
Packer et al. (2023). MemGPT: Towards LLMs as Operating Systems. Virtual context management, with main context, recall and archival storage, memory pressure, and paging by function calls.
Sumers, Yao, Narasimhan, and Griffiths (2024). Cognitive Architectures for Language Agents. The CoALA framework, which maps working, episodic, semantic, and procedural memory onto language agents.
Chhikara et al. (2025). Mem0: Building Production-Ready AI Agents with Scalable Long-Term Memory. Extraction and an update phase with ADD, UPDATE, DELETE, and NOOP, with latency and token costs measured against full context.
Rasmussen et al. (2025). Zep: A Temporal Knowledge Graph Architecture for Agent Memory. A bi-temporal knowledge graph that invalidates facts instead of deleting them, with hybrid search and reranking.
Wang et al. (2023). Voyager: An Open-Ended Embodied Agent with Large Language Models. A skill library of verified programs as procedural memory.
Belady (1966). A study of replacement algorithms for a virtual-storage computer. The optimal replacement policy and the comparison of practical ones, from the early days of virtual memory.
Sleator and Tarjan (1985). Amortized efficiency of list update and paging rules. The competitive analysis of LRU and FIFO against the optimum, with and without extra capacity.

Made for larger screens

Four kinds of memory

A memory store and its retrieval score

What a decay of 0.995 per hour means

Why more memories make retrieval worse

Paging between the window and the store

The paging problem

Write policies

Which store answers questions about time

Finding and merging duplicates

Forgetting on purpose

One question, end to end

Remembering how, and remembering relations

What memory buys, measured

Memory inside the model

Read more

Watch next

Four kinds of memory

A memory store and its retrieval score

What a decay of 0.995 per hour means

Why more memories make retrieval worse

Paging between the window and the store

The paging problem

Write policies

Which store answers questions about time

Finding and merging duplicates

Forgetting on purpose

One question, end to end

Remembering how, and remembering relations

What memory buys, measured

Memory inside the model

Read more

Watch next